CS - CPU, Scheduling

한정된 자원으로 최대한 성능을 이끌어내기 위해서는 CPU를 효율적으로 사용해야함

프로세스 - 프로그램을 실행하는 주체 / 쓰레드 - 작업을 처리하는 주체

-> OS는 실행 대기지눙인 프로세스들에게 CPU 자원 배정을 적절히 하여 시스템의 성능을 효율적으로 사용

->오버헤드(프로세스가 필요한 자원보다 더 많이 사용하는 것)를 최소화

->사용률 최대화 (프로세스가 최대한 자원을 많이 받고 빨리 처리하도록)

->기아 현상(프로세스가 자원할당이 되지 않아 대기 상태에 있는 것)을 낮게

 

정책에 따른 3가지 분류

배치 시스템 - 가능하면 많은 일을 수행하며 시간보다는 처리량이 중요

대화형 시스템 - 빠른 응답, 적은 대기시간

실시간 시스템 - 최소 응답 시간

---

스케줄링

 

스케줄링의 단위

1. CPU Burst

프로세스의 사용 중에 연속적으로 CPU를 사용하는 구간, 즉 실제 CPU를 사요하는 스케줄링의 단위

2. I/O Burst

프로세스의 실행 중에 I/O 작업이 끝날때까지 블락되는 구간

 

->프로세스 실행은 “CPU실행 ↔ 입/출력 대기” 의 반복

 

스케줄링 알고리즘 평가 기준

• CPU이용률 : 전체 시스템 시간 중, CPU가 작업을 처리하는 시간의 비율
• 처리량 : CPU가 단위 시간당 처리하는 프로세스의 개수
• 총 처리 시간 : 프로세스가 시작해서 끝날때 까지 걸린 시간
• 대기시간 : 프로세스가 준비완료 큐에서 대기하는 시간의 총 합
• 응답시간 : 대화식 시스템에서 요청 후 첫 응답이 오기까지 걸린 시간

---

스케줄링 종류

1.선점 스케줄링

OS가 CPU의 사용권을 선점하고, 특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식 (처리 시간 예측이 어려움)

가장 자원이 필요한 프로세스에게 CPU를 먼저 할당하여 상황에 따라 강제로 CPU 사용권을 회수할 수도 있음

빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 우선적으로 제어할 수 있음

 

1-1) Priority Scheduling(우선순위 스케쥴링)

정적/동적으로 우선순위를 부여하여 우선순위가 높은 대로 처리

우선순위가 낮은 프로세스는 무한정 대기하는 기아현상 발생 가능

Aging 방법으로 기아현상 문제 해결 가능(기다리는 시간에 따라 우선순위를 증가시켜주는 방법)

 

1-2) Round Robin(라운드 로빈)

정해진 시간 할당량만큼 프로세스를 할당한 뒤 작업이 끝난 프로세스는 순환 큐 가장 마지막에가서 재할당 대기(회전식)

이따 시간 할당량이 너무 작으면 빈번한 Context Switching이 발생하고 너무 길면 기본적인 스케쥴링 알고리즘인 FCFS와 차이가 사실상 없음

 

1-3) Multilevel Queue(다단계 큐)

순환 큐를 여러 개의 큐로 분류하여 각 큐가 다른 스케쥴링 알고리즘을 가지는 방식

메모리 크기, 우선순위, 유형 등 프로세스의 특성에 따라 하나의 큐에 영구적으로 할당되며 큐와 큐 사이의 스케쥴링아 필요

큐와 큐 사이의 스케줄링에서 우선순위가 높은 대화형 프로세스 큐에는 Round Robin을 적용한 Forground Queue를 적용하고 우선순위가 낮은 연산작업 처리 프로세스 큐는 기본 알고리즘인 FCFS를 적용한 Background Queue를 적용할 수 있다. 여기서 Forground Queue가 비어있지 않는 한 Background Queue는 먼저 실행될 수 없으며 Background Queue가 이미 실행중인 상태여도 Forground Queue에 프로세스가 들어오면 Forground Queue가 먼저 실행된다.

비선점 스케줄링

 

 

2.비선점 스케줄링

어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나 I/O Blocking이 발생하여 자발적으로 중지될 때까지 계속 실행되도록 하는 스케줄링 

순서대로 처리가 되며 다음에 처리해야할 프로세스와 상관없이 응답시간의 예측이 용이 (처리 시간 예측이 용이)

선점방식보다 스케줄러 호출 빈도가 낮고 Context Switching에 따른 오버헤드가 비교적 적음

일괄처리 시스템에 적합하여 CPU 사용시간이 긴 프로세스가 다른 프로세스들을 대기시켜 처리율이 떨어질 가능성이 존재

 

2-1) FCFS (First Come, First Serve)

Queue에 도착한 순서대로 CPU를 할당하는 기본적인 스케줄링 알고리즘

기본적인 Queue를 사용하기 때문에 FIFO 방식으로 간단하게 구현이 가능

다만 Convoy Effect가 발생할 수 잇는데 긴 처리시간의 프로세스가 선점되어버리면 나머지 짧은 처리시간의 프로세스들이 해당 프로세스가 끝날 때까지 대기해야할 가능성이 존재

먼저 도착한 프로세스의 버스트 타임에 따라 평균 대기시간의 편차가 큼

 

2-2) SJF(Shorted Job First)

CPU 버스트 타임이 가장 짧은 최단작업을 우선적으로 스케줄링하는 알고리즘

가장 적은 평균 대기 시간

현재 CPU에 할당된 프로세스의 남은 잔여 시간과 새로 들어온 프로세스의 CPU 버스 타임을 비교하여 더 적은 프로세에게 할당

 

2-3)HRN(Hightes Response-ratio Next)

우선순위를 계산하여 점유 불평등 보완

우선순위 = (대기시간 + 실행시간) / 실행시간

---

스케줄링 동작시점

스케쥴링 알고리즘에 따라 프로세스들은 상태변화가 일어나며 준비/수행 상태일때 CPU를 사용

1. 수행 -> 대기 (Running->Waiting) : I/O요청이 발생하거나, 자식 프로세스가 종료 대기를 할 때
2. 수행 -> 종료 (Running -> Terminate) : 프로세스를 종료시켰을 때
3. 수행 -> 준비 (Running-> Ready) : 인터럽트가 발생했을 때
4. 대기 -> 준비 (Waiting -> Ready) : I/O가 완료되었을 때

타원형은 프로세스의 상태, 화살표는 스케줄링에 따라 상태가 변화되는 동작을 의미

1,2은 프로세스가 스스로 CPU를 반환하기에  비선점 스케쥴링이 발생

 

3,4은 프로세스에서 CPU를 강제로 할당(회수)해야 하므로  선점 스케쥴링이 발생

 

Example - 카카오톡

 

카카오톡 메세지를 보내기 위해 메세지 창을 켜면 카카오톡 프로세스는 신규 > 준비 상태

1. 준비 (Ready) 상태:
   1. 카카오톡을 띄워서 메시지를 입력하고 있을 때, 해당 프로세스는 준비 상태
   2. CPU 스케줄링 알고리즘은 준비 상태의 프로세스 중에서 CPU를 할당할 프로세스를 선택
   3. 이때, 선택하는 선점 알고리즘에 따라 우선순위, 라운드 로빈 등 다양한 방식이 존재
2. 대기 (Waiting) 상태:
   1. 카카오톡이 비활성화 되어있거나, 가만히 상대방의 답장을 기다릴때 대기 상태
   2. 해당 프로세스는 대기 상태로 변경되면서 수행중 이었다면 CPU를 반납
   3. CPU 스케줄링 알고리즘은 다른 준비 상태의 프로그램(프로세스)를 선택하여 CPU를 할당
3. 수행 (Running) 상태
   1. 사용자가 메시지를 발송하거나 상대방의 메시지를 수신할때 수행 상태
   2. CPU 가 준비 상태의 프로세스에 명령을 보내면, 해당 프로세스는 수행 상태로 변경
   3. CPU 스케줄링 알고리즘은 실행 시간을 제어하며, 일정 시간이 지나면 해당 프로세스를 중단하고 실행 대기 상태의 다른 프로세스를 선택 가능
4. 종료 (Terminated) 상태:
   1. 카카오톡 프로그램을 종료하면 해당 프로세스는 중지 상태로 변경
   2. 이때, CPU 스케줄링 알고리즘은 다른 실행 대기 상태의 프로세스를 선택하여 CPU를 할당