공룡책 요약하기 05

2019-09-06

CPU Scheduling

CPU 스케줄링은 준비 완료 큐로부터 대기 중인 프로세스를 선택해 CPU를 할당하는 작업이다.

CPU는 디스패처에 의해 선택된 프로세스를 할당한다.

CPU 스케줄링 결정은 다음의 네 가지 상황 하에서 발생할 수 있다.

  1. 실행 상태에서 대기 상태로 전환될 때(입출력 요청이나 wait를 호출할 때)

  2. 실행 상태에서 준비 완료 상태로 전환될 때(인터럽트가 발생)

  3. 대기 상태에서 준비 완료 상태로 전환될 때(입출력의 종료 시)

  4. 프로세스가 종료될 때

상황 1과 4의 경우에는 선택의 여지가 없지만 상황 2와 3을 위해서는 선택의 여지가 있다.

상황 1과 4에서만 스케줄링이 발생할 경우, 비선점(non-preemptive) 또는 협조적(cooperative)라 하고, 그렇지 않으면 선점(preemptive)이라고 한다.

CPU burst
the amount of time the process uses the processor before it is no longer ready

CPU 버스트는 말 그대로 CPU 명령을 실행하는 것을 의미하며

입출력 버스트는 I/O를 요청한 다음 기다리는 시간이다.

프로세스 실행은 CPU 버스트로 시작하여 입출력 버스트와 CPU 버스트가 번갈아 발생하며 진행된다.

결국 마지막 CPU 버스트는 또 다른 입출력 버스트가 뒤따르는 대신, 실행을 종료하기 위한 시스템 요청과 함께 끝난다.

5-1

###스케줄링 알고리즘

선입 처리기 스케줄링(FCFS)

CPU 스케줄링은 준비 완료 큐에 있는 어느 프로세스에게 CPU를 할당할 것인지를 결정하는 문제를 다룬다.

가장 간단한 CPU 스케줄링 알고리즘은 선입 처리기 스케줄링이다.

이름 그대로, 먼저 CPU를 요청한 프로세스가 먼저 할당받는다.

비선점형 알고리즘인 선입 처리기 스케줄링은 CPU에 한 프로세스가 할당되면, 그 프로세스가 종료하든지 또는 입출력 처리를 요구하든지 하여 CPU를 방출할 때까지 CPU를 점유하기 때문에 선입 처리기 스케줄링은 평균 대기 시간이 종종 대단히 길 수 있다.

최단 작업 우선(SJF)

CPU 스케줄링의 다른 접근 방법은 최단 작업 우선 알고리즘이다.

이 알고리즘은 CPU가 이용 가능해지면, 가장 작은 다음 CPU 버스트를 가진 프로세스에게 할당한다.

SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가진다는 점에서 최적임이 증명 가능하다.

짧은 프로세스를 긴 프로세스의 앞으로 이동함으로써, 짧은 프로세스의 대기 시간을 긴 프로세스의 대기 시간이 증가되는 것보다 더 많이 줄일 수 있다.

5-2

5-3

우선순위 스케줄링(Priority Scheduling)

SJF 알고리즘은 일반적인 우선순위 스케줄링 알고리즘의 특별한 경우이다.

각 프로세스들은 우선순위를 가지고 있으며 CPU는 가장 높은 우선순위를 가진 프로세스에게 할당된다.

우선순위는 내부적 또는 외부적으로 정의될 수 있다.

내부적으로 정의된 의선순위는 프로세스의 우선순위를 계산하기 위해 어떤 측정 가능한 양들을 사용한다.

예를 들어 시간 제한, 메모리 요구, 열린 파일의 수, 평균 입출력 버스트의 평균 CPU 버스트에 대한 비율 등이 우선순위의 계산에 사용된다.

외부적 우선순위는 프로세스의 중요성, 컴퓨터 사용의 비용, 정치적 요인 등과 같은 운영체제 외부적 기준에 의해 결정된다.

우선순위 스케줄링의 주요 문제는 무한 봉쇄(indefinite blocking) 또는 기아 상태(starvation)이다.

우선순위 스케줄링 알고리즘을 사용하는 부하가 과중한 시스템의 경우 높은 우선순위의 프로세스들이 꾸준히 들어와 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생한다.

이 문제에 대한 한 가지 해결 방안은 노화(aging)이다.

노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.

라운드 로빈 스케줄링(Round-Robin Scheduling)

라운드 로빈 스케줄링 알고리즘은 특별히 시분할 시스템을 위해 설계되었다.

이는 선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다.

시간 할당량(time quantum) 또는 시간 조각(tiem slice)이라고 하는 작은 단위의 시간을 정의한다.

준비 완료 큐는 원형 큐로 동작한다. CPU 스케줄러는 준비 완료 큐를 돌면서 한 번에 한 프로세스에게 한 번의 시간 할당량 동안 CPU를 할당한다.

5-4

5-5

P1은 6밀리초를 기다리고, P2는 4밀리초, P3는 7밀리초를 기다린다.

RR 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다.

극단적인 경우 시간 할당량이 매우 크면 RR 정책은 선입 선처리와 같다.

반대로 시간 할당량이 매우 적다면 RR 정책은 매우 많은 문맥교환을 야기한다.

문맥 교환 시간이 시간 할당량의 10퍼센트에 근접하다면, CPU 시간의 10퍼센트는 문맥 교환에 사용된다.

실시간 시스템은 마감시간 이내에 결과가 나와야만 하는 컴퓨터 시스템이다.

마감시간이 지난 후의 결과는 아무 소용이 없다.

경성 실시간 시스템은 실시간 태스크들이 마감시간 이내에 수행될 것이라는 사실을 보장해야 한다.

연성 실시간 시스템은 제약이 더 적은 시스템으로 다른 태스크들보다 실시간 태스크에게 더 높은 스케줄링 우선순위를 제공한다.