CPU Scheduling

1. 기본 개념

다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스가 존재하도록 하는 것이다. 다중 프로그래밍을 달성하기 위해선 process를 CPU에 할당하는 작업인 Scheduling이 필수이다. 사실 process가 아니라 kernel thread를 scheduling 하는 것인데, 일반적으로 process scheduling과 thread scheduling은 같다고 여겨진다. 

2. CPU-I/O burst cycle

CPU가 수행되는 구간을 CPU burst, I/O때문에 block되는 구간을 I/O burst라고 한다. 아래 그림 1처럼, process는 CPU burst와 I/O burst의 cycle로 구성된다.

[그림 1] CPU-I/O burst cycle

CPU burst 크기가 크면 CPU intensive (CPU bound)한 프로그램, 반대로 작으면 I/O intensive (I/O bound)한 프로그램이다. 

아래 그림 2는 일반적으로 나타나는 CPU burst의 시간 도표이다. 이를 통해 Scheduling 시 얼마만큼 오래 CPU를 할당해줄 것인지 유추할 수 있다.

[그림 2] CPU burst duration

3. CPU scheduler

kernel thread 또는 process에 CPU를 할당하는 scheduler는 short-term scheduler이다. short-term scheduler는 ready queue에 존재하는 process(또는 thread) 중 하나를 선택하여 CPU를 할당한다.

ready queue는 FIFO queue, priority queue, tree, linked list 등으로 구현된다. ready queue에 저장되는 값은 보통 Process Control Block(PCB)이다.

(thread와 process의 state diagram과 PCB 내용이 기억이 안난다면 이전 글을 복습하자.)

CPU scheduling은 아래 네가지 상황에서 발생한다. (그림 3을 참고)

1) running -> waiting: I/O 요청이나 wait 등 CPU를 스스로 yield할 때

2) running -> ready: interrupt가 발생했을 때

3) waiting -> ready: I/O 종료 등 이벤트를 마쳤을 때

4) running -> terminated: 종료할 때

[그림 3] process state diagram

scheduler는 선점(preemptive) 또는 비선점(non-preemptive) scheduler로 나뉜다. 1)과 4)는 CPU scheduler와 관계 없이 process가 CPU를 반환하는 것이다. 이렇게 1), 4)만 scheduling이 발생하면 비선점형 scheduler이다. 반대인 경우 선점형 scheduler이다.

4. Preemptive / Non-Preemptive Scheduler

비선점형 스케줄러는 어떤 process가 CPU를 할당받으면, 스스로 CPU를 반환할 때까지 계속 실행되도록 보장한다. 선점형보다  scheduler 호출 빈도가 낮고 context switching overhead가 적다. 하지만 응답성(responsive)이 너무 적어 현대 운영체제들은 거의 사용하지 않는다.

선점형 스케줄러는 어떤 process가 CPU를 할당받아서 실행 중이어도, 다른 process가 실행 중인 process를 중지하고 CPU를 강제로 점유할 수 있게한다. 비선점형과 달리 응답성이 좋고 우선순위가 높은 process를 빠르게 처리할 수 있다. 하지만 overhead가 크다. 예를 들어, 어떤 process가 자료를 갱신하고 있던 도중 다른 process가 선점되어 그 자료에 접근하면, 정확하지 않은 자료에 접근하게 되는 것이다. 이런 경우를 위해 동기화(synchronize)를 해야한다.

동기화 된 자료에 접근하는 동안은 interrupt가 불능화되므로 동기화 되는 부분은 반드시 짧아야 한다.

5. Dispatcher

Dispatcher는 process를 ready에서 running 상태로 만드는 역할을 한다. 다시 말해, short-term scheduler가 process에게 CPU를 할당하도록 하는 모듈이다. Dispatcher가 하는 일은 아래와 같다.

1) Context Switching

2) User Mode로 전환

3) 프로그램의 재시작을 위해 해당 주소로 이동

Dispatcher는 Context Switching 시 호출되므로, 가능한 한 빨라야 한다. 어떤 process를 중단시키고 다른 process를 실행시키는 데까지 소요되는 시간을 Dispatch Latency라고 한다.

6. Scheduling Criteria

CPU scheduling 알고리즘들은 서로 다른 특성을 가지고 있으며, 상황에 따라 선호되는 알고리즘이 다르다. CPU scheduling 알고리즘을 비교하기 위한 여러 기준은 아래와 같다.

1) CPU utilization (CPU 이용률): CPU가 놀지 않고 일한 시간의 비율

2) Throughput (처리량): 주어진 시간동안 얼마나 처리했는가

3) Turnaround time(총처리 시간): CPU를 할당받기 위해 ready queue에서 대기한 시간부터 작업을 마치고 반환하기까지 걸린 시간

4) Waiting time(대기 시간): CPU를 할당받기 위해 ready queue에서 대기한 시간의 총합

5) Response time(응답 시간): ready queue에 들어와서 첫 번째 응답을 내기까지의 시간

일반적으로 CPU 이용률과 처리량을 최대화하고, 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다.

다음 글에서 여러 CPU scheduling 알고리즘을 살펴볼 것이다. 이 알고리즘들은 평균 대기 시간을 기준으로 평가할 것이다.

* 참고

선점형, 비선점형 스케줄링

http://umbum.tistory.com/60

CPU scheduling

https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/5_CPU_Scheduling.html