Scheduling Algorithms

CPU scheduling은 short-term scheduler가 ready queue에 존재하는 process 중 어느 process에게 CPU를 할당할 것인지를 결정하는 문제를 다룬다. 이 과정은 process scheduler 또는 dispatcher에 의해 수행된다.

1. First-Come, First-Served Scheduling (FCFS)

CPU를 먼저 요청하는 process가 CPU를 먼저 할당받는 scheduler이다. 따라서 선입선출(FIFO) queue로 쉽게 관리할 수 있다. FCFS Scheduling은 non-preemptive scheduler이기 때문에 시분할 시스템(대화형 시스템)에서는 사용하지 못한다.

선입선처리 방식이기 때문에 구현하기는 쉽지만, process의 평균 대기시간이 아주 길어질 수 있다. 예를 들어, 아래 그림 1의 프로세스 집합을 보자. 

[그림 1] 프로세스 집합

CPU burst time은 밀리초 단위이다. 프로세스들이 P1, P2, P3순으로 도착한다면 아래 그림 2의 Gantt 차트처럼 나타난다.

[그림 2] P1, P2, P3 순 도착

프로세스의 대기시간은 P1 = 0ms, P2 = 24ms, P3 = 27ms이다. 따라서 평균 대기 시간은 (0 + 24 + 27) / 3 = 17ms이다. 반대로 아래 그림 3처럼 P3, P2, P1처럼 도착한다고 가정해보자.

[그림 3] P3, P2, P1 순 도착

이때, 프로세스의 대기시간은 P1 = 6ms, P2 = 3ms, P3 = 0ms이다. 따라서 평균 대기 시간은 (6 + 3 + 0) / 3 = 3ms이다. 이처럼 순서에 따라 평균 대기 시간이 완전히 달라질 수 있다. process들의 CPU busrt time이 서로 크게 다를 경우, 이런 현상은 더 심해진다.

FCFS scheduling은 비선점형이므로 한 process가 점유하면 CPU burst time만큼 CPU를 점유한 뒤 반환한다. 예를 들어, CPU bound process가 하나 있고, I/O bound process가 여러개 있다고 가정하자. 

I/O bound process는 일반적으로 짧은 CPU burst를 가지고 있기 때문에 CPU를 잠깐 점유하고 I/O를 처리한 뒤 ready queue로 돌아갈 것이다. 그 후 CPU bound process가 CPU를 점유하면 다수의 I/O bound process는 CPU bound process가 끝날때까지 ready queue에서 기다려야 한다.

이렇게 다수의 process가 하나의 긴 process가 CPU를 양도하기를 기다리는 것을 convoy effect라고 한다.

2. Shortest-Job-First Scheduling (SJF)

SJF의 기본 아이디어는 ready queue에 존재하는 process 중 가장 작은 CPU burst time을 가지는 process를 선택하는 것이다. 두 process의 CPU burst time이 같다면 FCFS를 적용한다. SJF는 non-preemptive과 preemptive 둘 다 존재한다.

비선점형 SJF의 예로 아래 그림 4의 프로세스 집합을 보자.

[그림 4] 프로세스 집합

SJF scheduler를 이용하면 아래 그림 5의 Gantt처럼 스케줄하게 된다.

[그림 5] Non-Preemptive SJF Gantt Chart

이 경우 프로세스의 대기시간은 P1 = 3ms, P2 = 16ms, P3 = 9ms, P4 = 0ms이다. 따라서 평균 대기시간은 (3 + 16 + 9 + 0) / 4 = 7ms이다.  FCFS의 경우 10.25ms가 나온다. 주어진 프로세스 집합에서 최소의 대기시간을 가짐이 증명됐지만 문제는 어떻게 다음 CPU burst time을 파악하냐는 것이다. long-term scheduler의 경우 사용자가 작업을 제출할 때 명시한 process의 시간제한 길이를 이용해서 알 수 있다. 따라서 long-term scheduling 할 때 non-preemptive SJF를 많이 사용한다.

비선점형 SJF는 short-term scheduling으로는 구현할 수 없다. 왜냐면 short-term scheduler는 다음 CPU burst time을 알 수 있는 방법이 없기 때문이다. 대신 다음 CPU burst time의 근사 값을 계산해서, 가장 짧은 CPU burst를 가진 process를 선택한다. CPU burst time의 근사 값을 계산하기 위해서 CPU burst들의 측정된 길이를 지수 평균하여 예측할 수 있다. 0 <= alpha <=1인 alpha에 대해 다음을 정의한다.

estimate[ i + 1 ] = alpha * burst[ i ] + ( 1.0 - alpha ) * estimate[ i ]

estimate[i + 1]은 다음 CPU burst에 대한 예측 값이다. estimate[i]는 과거 CPU burst의 추이를 저장한다. burst[i]는 n번째 burst의 길이이다. 아래 그림 6은 alpha가 1/2일 때 CPU burst의 길이 추정을 보여준다.

[그림 6] Prediction of the length of the next CPU burst

비선점형 SJF는 평균 대기 시간을 최소화 할 수 있지만, CPU burst가 큰 process가 무한 대기하는 현상이 발생할 수 있다.(starvation)

선점형 SJF는 SRTF(shortest remaining time first) scheduling이라고도 불린다. 만약 현재 실행되고 있는 process보다 더 짧은 CPU burst time을 가지는 process가 ready queue에 들어오면 새로운 process가 실행된다. 아래 그림 7의 4개의 process를 예시로 들자.

[그림 7] 프로세스 집합

그림 7의 Arrival Time에 process가 ready queue에 도착하면 아래 그림 8의 Gantt 차트처럼 결과가 나타난다.

[그림 8] Preemptive SJF Gantt Chart

이때, 평균 응답 시간은 ((17 - 0) + (5 - 1) + (26 - 2) + (10 - 3)) / 4 = 13ms 이고, 평균 대기 시간은 ((10 - 1) + (1 - 1) + (17 - 2) + (5 - 3)) / 4 = 6.5ms이다. 비선점형 SJF의 경우 7.75ms가 나온다.

비선점형 SJF와 마찬가지로 CPU burst가 긴 porcess는 무한 대기할 수 있고, ready queue에 CPU burst가 짧은 process가 자주 도착할 경우 선점이 자주이루어져(schedule이 잦아서) context switching의 부담이 있다.

3. Priority Scheduling

우선순위가 각 process에 부여되고 가장 높은 우선순위를 가진 process에게 CPU가 할당되는 scheduling이다. SJF는 CPU burst 길이의 역순으로 우선순위가 부여된다고 생각할 수 있다. preemptive, non-preemptive 둘 다 가능하다.

아래 그림 9와 같이 process가 존재한다고 하자.

[그림 9] 프로세스 집합

이 경우 아래 그림 10처럼 gantt 차트가 나올 것이다.

[그림 10] Priority Scheduling Gantt Chart

이 경우 평균 대기 시간은 (6 + 0 + 16 + 18 + 1) / 5 = 8.2ms, 평균 응답 시간은 (16 + 1 + 18 + 19 + 6) / 5 = 12ms이다.

선점형 priority scheduling의 경우 새로 도착한 process의 우선순위가 현재 실행되고 있는 process의 우선순위보다 높다면 CPU를 선점한다. 위에서 설명한 선점형 SJF를 보면 CPU burst가 더 짧은 process가 ready queue에 도착하면 현재 실행되고 있는 process를 선점하는 것을 볼 수 있다.

priority scheduling은 Starvation이 발생할 수 있다. ready queue에 존재하지만 우선순위가 너무 낮아서 CPU를 점유하지 못하는 문제이다. 낮은 우선순위의 process의 무기한 봉쇄를 막기 위해선 aging 기법을 사용할 수 있다.

예를 들어 15분마다 ready queue에 존재하는 process의 우선순위를 1씩 증가시킬 수 있을 것이다.

4. Round-Robin Scheduling

시분할 시스템을 위해 설계된 preemptive scheduling 기법이다. FCFS scheduling을 기반으로 CPU를 process에게 할당하지만, 각 process는 time quantum(or time slice)라고 불리는 CPU 점유 시간이 지나면 시간 종료 interrupt에 의해 CPU를 반환한다. 이 때, CPU burst time이 아직 남은 process는 context switching이 일어나고, ready queue의 끝에 다시 추가된다. 그림으로 표현하면 아래 그림 11처럼 circular queue로 동작한다.

[그림 11] Round-Robin ready queue

아래 그림 12처럼 프로세스 집합이 있다고 하자.

[그림 12] 프로세스 집합

이때, time quantum을 4ms로 하면, 아래 그림 13의 Gantt 차트처럼 scheduling 결과가 나올 것이다.

[그림 13] Round-Robin Gantt Chart

이 경우 평균 대기 시간은 ((10-4) + 4 + 7) / 3 = 5.66ms이다. Round-Robin scheduling은 CPU를 한 process가 독점하는 것은 방지하지만, context switching에 따른 overhead를 감수해야 한다.  context switching을 하는데 걸리는 시간은 보통 10ms 미만이므로 현대 운영체제들은 10~100ms 범위의 time quantum을 사용한다. time quantum이 context switching 시간보다 커야하지만, 너무 크면 FCFS와 다를게 없어지므로 주의해야 한다. (책에 의하면 CPU burst의 80%는 time quantum보다 짧아야 한다.)

5. Multilevel Queue Scheduling

process들이 서로 다른 그룹으로 분류돼야 할 때 사용하는 scheduling이다. 그룹별로 ready queue가 존재하며 queue마다 우선순위가 다르다. 예를 들어, foreground process는 background process 보다 절대적인 우선순위가 높을 수 있다. 또한, 각 ready queue는 서로 다른 scheduling을 사용할 수 있다. 예를 들어, foreground process는 Round-Robin 알고리즘을, background process는 FCFS 알고리즘을 이용해 scheduling 할 수 있다.

아래 그림 14는 Multilevel Queue Scheduling을 그림으로 나타낸 것이다.

[그림 14] Multilevel queue scheduling

queue마다 서로 다른 알고리즘을 적용 가능하고 우선순위를 매길 수 있기때문에 세밀한 process의 관리가 가능하지만, 우선순위가 높은 queue에 process가 계속 추가된다면 우선순위가 낮은 queue의 process는 Starvation이 생긴다. Priority Scheduling은 Aging 기법으로 해결했으나, Multilevel Queue Scheduling은 queue가 여러개이고 process가 다른 queue로 이동이 불가능하다. 이런 문제를 Multilevel Feedback Queue Scheduling을 이용해 해결했다.

6. Multilevel Feedback Queue Scheduling

Multilevel Queue Scheduling의 process가 정적 우선순위를 가졌다면, Multilevel Feedback Queue Scheduling의 process는 동적 우선순위를 가진다. 이 scheduling의 아이디어는 어떤 process가 CPU를 너무 오래 사용하면, 낮은 우선순위의 queue로 보내는 것이다. 반대로, 낮은 우선순위의 queue에서 너무 오래 대기하는 process가 있으면, 높은 우선순위의 queue로 보낸다. 이러한 Aging 기법으로 Starvation을 방지한다. 

예를 들어, 아래 그림 15처럼 queue가 존재한다고 가정하자.

[그림 15] Multilevel feedback queues

Multilevel feedback queue scheduling은 선점형(preemptive) 방식으로 이루어지는데, 마지막 우선순위의 queue를 제외하고 나머지 queue는 time quantum을 가지고 있다. CPU를 점유한 process는 자신이 존재하는 queue의 time quantum 내에 종료하지 않으면 하위 우선순위 queue에 들어가고 선점된다. (time quantum 8인 queue의 process가 8ms 내에 종료되지 못하면 16ms의 queue에 추가되고 선점된다.) Multilevel queue scheduling과 마찬가지로, 상위 우선순위 queue들이 비어있어야만 해당 queue의 process가 CPU를 점유할 수 있다.

Multilevel feedback queue scheduler는 아래와 같은 매개변수에 의해 정의된다.

1) queue의 개수

2) 각 queue를 위한 scheduling algorithm

3) 한 process를 높은 우선순위 queue로 올려주는 시기를 결정하는 방법 (time quantum 이전에 I/O으로 CPU를 선점당하는 등)

4) 한 process를 낮은 우선순위 queue로 강등시키는 시기를 결정하는 방법 (time quantum 내에 작업을 못 끝내는 경우 등)

5) process가 서비스를 필요로 할 때 process가 들어갈 queue를 결정하는 방법

Multilevel feedback queue scheduling은 가장 일반적인 CPU scheduling algorithm이지만 위와 같이 다양한 매개변수 때문에 가장 복잡한 scheduling algorithm이다.

* 참고

FCFS, SJF

http://itdexter.tistory.com/392?category=623976

http://taesun1114.tistory.com/entry/CPU-Scheduling-SJF

Round Robin

http://itdexter.tistory.com/393?category=623976

Multilevel Queue Scheduling

http://itdexter.tistory.com/394?category=623976

Scheduling Algorithm

https://www2.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/6_CPU_Scheduling.html