[공룡책] CPU 스케줄링 (CPU Scheduling)

CPU 스케줄링의 필요성

- 다중 프로그래밍의 목적은 CPU 이용률 최대화 => 가능한 CPU가 항상 실행중인 프로세스를 가지게 한다.

- 프로세스가 대기 중일 때, 운영체제가 해당 프로세스가 할당된 CPU를 회수해 다른 프로세스에 할당

 

CPU 스케줄러

- CPU가 idle(유휴상태)이 되었을 때, ready queue의 프로세스 중 어떤 프로세스를 할당할 것인지 결정

- 일반적으로 ready queue에 저장된 레코드는 PCB

- ready queue는 FIFO가 아닌 우선순위 큐, 트리 등 여러 구조를 띈다.

 

CPU  스케줄링이 발생하는 상황

- 프로세스가 실행 상태(run)에서 대기 상태(waiting)로 전환될 때

ex) I/O 요청, 자식 프로세스의 종료를 기다리기 위해 wait() 호출 시

- 프로세스가 실행 상태(run)에서 준비 상태(ready)로 전환될 때

ex) 인터럽트 발생

- 프로세스가 대기 상태(waiting)에서 준비 상태(ready)로 전환될 때

ex) I/O 종료

- 프로세스가 종료될 때

 

선점 및 비선점 스케줄링(Preemptive and Nonpreemtive Scheduling)

- 위 1,4 상황은 비선점이다. => 프로세스가 자신에게 할당되었던 CPU를 반환한 경우이기 때문이다.

- 위 2,3 상황은 선점이다. => 이미 run상태인 프로세스에 할당된 CPU를 가져와 준비 상태인 프로세스에게 주는 경우이기 때문이다.

 

디스패처(Dispatcher)

- CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 건내주는 모듈

- 문맥 교환, 사용자 모드 전환, 프로그램을 다시 시작할 때 프로그램의 적절한 위치로 이동하는 일

- 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데 소요되는 시간 => 디스패처 지연

- 문맥 교환 시 항상 호출되기 때문에, 문맥 교환의 오버헤드를 줄이기 위해 디스패처의 시간 효율은 매우 중요하다.

 

스케줄링 기준

- CPU 이용률(utilization): CPU를 얼마나 사용하고 있는가

- 처리량(throughput): 단위 시간 당 완료된 프로세스의 개수

- 총처리 시간(turnaround time):

프로세스의 제출 시간과 완료 시간의 간격 (프로세스의 대기 시간(ready queue에서의) + CPU 실행 시간 + I/O 시간)

- 대기 시간(waiting time): 프로세스의 대기 시간(ready queue에서의)

- 응답 시간(response time): 요구한 후, 첫 응답이 나올 때 까지의 시간 (응답을 모두 처리할 때가 아니다.)

=> CPU 이용률, 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다.

 

스케줄링 알고리즘

- FCFS (First-Come, First-Served)

• 프로세스가 CPU를 요청한 순서대로, 해당 프로세스에 CPU를 할당한다.
• 비선점형
• ready queue는 FIFO 구조
• 다른 모든 프로세스들이 하나의 긴 CPU 실행 시간을 갖는 프로세스를 기다리는 상황 발생
  => 호위 효과(convoy effet)

- SJF (Shortest Job First)

• 가장 짧은 CPU burst time을 가진 순서대로, 프로세스에 CPU를 할당한다.
• 다음 CPU burst time을 알 방도가 없어, 구현이 힘들어 예상치를 계산해 할당하는 방법으로 구현할 수 있다.
• 선점형 SJF => SRF (Shorted Remaining time First)

- RR (Round-Robin)

• 특정한 타임 슬라이스를 설정해, 해당 시간 할당량만큼 프로세스가 순서대로 실행된다.
• ready queue는 원형 큐
• CPU burst time이 time slice보다 작으면, 프로세스 종료 시 CPU 자동 반환
• CPU burst time이 time slice보다 크면, 운영체제에 인터럽트 발행 후, ready queue로 들어간다.
• time slice가 크면, FCFS
• time slice가 작으면, 잦아진 문맥 교환으로 오버헤드 상승 (비효율적)

- Priory Scheduling (우선순위 스케줄링)

• 각 프로세스가 우선순위를 가져, 가장 높은 우선순위를 가진 프로세스에 CPU 할당
• 서로 같은 프로세스는 FCFS
• SJF는 CPU birst time의 오름차순으로 우선순위를 갖는 우선순위 스케줄링이라고 볼 수 있다.
• 우선순위가 낮은 프로세스가 높은 프로세스들에 밀려 무한히 대기하는 경우가 발생한다.
  => 기아 현상(Starvation)
  => 노화(aging): 오랫동안 대기하는 프로세스들의 우선순위를 점진적으로 증가시켜, starvation을 해결할 수 있다.

- Multilevel Queue Scheduilng (다단계 큐 스케줄링)

• 여러 개의 Queue를 둔다.
• 각 Qeueu마다의 스케줄링이 반드시 필요하며, 주로 고정 우선순위의 선점형 스케줄링으로 구현된다.
  => Queue마다 우선순위가 있어, 우선순위가 높은 Queue부터 실행
• 우선순위로 Queue를 선택해, Queue 내부에서는 Round-Robin을 실행하면 효율적
• foreground queue에서는 RR, background queue에서는 FCFS로도 구현 가능
• 선점, 비선점 둘다 가능

 

참조)

braham Silberschats, Greg Gagne, Peter B. Galvin. (2018). Operating System Concepts (10/E)