6-2강. CPU 스케줄링 알고리즘

 이번 강에서는 CPU 스케줄링 알고리즘에 대해 설명한다. 이를 설명하기에 앞서 스케줄링의 성능의 기준을 알아보자.

 

1. CPU utilization (CPU 이용률)은 전체 시간 중에서 CPU가 놀지 않고 일한 시간의 비율을 의미한다.
2. Throughput (처리량)은 단위 시간당 CPU의 처리량을 의미한다. CPU가 얼마나 많은 일을 했는가를 나타낸다.
3. Turnaround time (소요 시간) 부터는 모두 시간과 관련된 것이다. 
4. Waiting time (대기 시간)
5. Response time (응답 시간)

이 다섯 가지 기준을 쉬운 예시를 통해 살펴보자.

 

 우리가 건물주가 되어 중국집을 차려서 중국집 주방장(CPU)을 고용한다고 가정하자. 우리로서는 주방장이 최대한 많은 시간 동안 일을 하는 것이 좋을 것이다. 뿐만 아니라 하루 동안에 많은 손님을 받아 많은 요리를 만들어 내면 더 좋을 것이고, 한 가지 요리를 완성하는 시간이 짧으면 더 좋을 것이다. 그러나 손님들이 똑같은 음식들을 주문하더라도 그 주방장이 어떤 순서로 요리를 하느냐에 따라 주방장이 일한 시간(CPU utilization)이 달라질 수 있을 것이다. 게다가 요리 순서에 따라 하루에 손님을 얼마나 받는지(Throughput)도 달라질 수 있다. 추가적으로 요리 순서를 바꿈으로써 중국집을 찾은 손님들이 기다린 시간(Waiting time)이나, 음식이 나오는 시간(Response time), 모두 먹고 나가는 데 걸리는 시간(Turnaround time)이 전부 달라질 수 있다. 여기서 음식의 스케줄링, 컴퓨터로 치면 CPU 스케줄링의 필요성이 대두된다.

 

 '시간'에 대해 조금 더 이야기해보자. 우리가 중국집에 들어갔으면 물이라도 먼저 가져다주거나 하물며 단무지라도 먼저 제공이 되어야 손님 입장에서는 내 주문이 확실히 들어갔다는 것을 느낄 수 있다. 이것이 응답 시간(Response time)이다. CPU를 얻기까지 '최초로' 걸린 시간을 의미한다. '최초'라는 단어가 중요한데 그 이유는 대부분의 운영체제는 preemptive scheduling을 선택하기 때문이다. Preemptive scheduling은 중간중간 CPU를 점유하는 CPU burst가 나뉘어 있기 때문에 이들 중간에 있는 CPU burst time의 시작이 아니라 가장 처음 CPU를 잡게 되는 시간이 프로세스 입장에서 Response time인 것이다. 대기 시간은 응답 시간과는 다르며, 중국집 요리를 먹으러 와서 기다린 시간(Waiting time)의 전체 합(프로세스가 CPU를 얻기 위해 기다린 시간의 총합)이다. 마지막으로 소요 시간(Turnaround time)은 기다린 시간과 밥 먹는 시간 전부 합친 것이다.

그림 1 : 스케줄링의 성능 척도

---

스케줄링 알고리즘

 

그림 2 : 스케줄링 알고리즘들

---

FCFS(First-Come First-Served)

 FCFS는 우리가 자료 구조 시간에 배운 큐(FIFO)와 같은 개념이다. 먼저 온 프로세스가 먼저 CPU를 차지한다. 그러나 결론부터 말하면 Job Scheduling에 있어서는 매우 비효율적인 알고리즘이다.

 

 다음 두 가지 케이스를 생각해보자. 프로세스 1, 프로세스 2, 프로세스 3이 거의 동시에 왔지만 1, 2, 3번의 순서대로 CPU를 배정받았다고 가정하고 다음 그림 3을 살펴보자. 프로세스 1의 Burst time이 24, 2번이 3, 3번이 3이라면 평균적으로 프로세스들이 기다리는 시간은 (0 + 24 + 27)/3 = 17이다. 

 

그림 3 : FCFS 예시 1

 

 이제 같은 프로세스이지만 간발의 차로 2, 3, 1의 순서로 배정받았다고 가정하고 그림 4를 살펴보자. 평균적으로 프로세스가 기다리는 시간은 (6 + 0 + 3)/3 = 3으로 위의 예시 1보다 눈에 띌 정도로 waiting time이 줄어든 것을 확인할 수 있다. 이건 너무 운빨 게임이 아닌가? 고작 0.000 몇 초로 기다리는 시간의 합이 이렇게나 차이가 날 수 있다니...

 

 이렇든 앞의 긴 프로세스가 먼저 도착해서 CPU를 오래 쓰는 바람에 뒤에 있는 짧은 프로세스가 오래 기다려야 하는 상황을 Convoy effect(호위 효과)라고 한다. CPU 스케줄링에 있어서는 부정적인 효과이다.

 

그림 4 : FCFS 예시 2

---

SJF(Shortest-Job-First) & SRTF(Shortest-Remaining-Time-First)

 

 FCFS를 살짝 보완한 것이 SJF(Shortest-Job-First)이다. SJF는 CPU를 가장 짧게 쓰려는 프로세스에게 CPU를 먼저 주는 것이다. Greedy Algorithm에서 보았을지 모르나 Waiting time 측면에서 본다면 가장 짧은 waiting time을 갖는 Optimal 한 방법이다. 즉, 다른 어떤 스케줄링 방법을 쓰더라도 SJF보다 waiting time 측면에서 더 나은 방식으로 스케줄링할 수 없다. 즉, minimum average waiting time을 보장한다.

 

 이 SJF도 preemptive한 버전과 nonpreemptive 버전이 있다. Nonpreemptive는 프로세스가 실행되는 도중에 ready queue에 현재 수행 중인 프로세스의 남은 CPU burst time보다 더 짧은 CPU burst time을 갖는 프로세스가 들어오더라도, 현재 프로세스의 CPU를 빼앗지 않고 남은 시간을 수행하는 것을 말한다. 반면 preemptive는 그런 상황에서 강제로 CPU를 빼앗아 버리는데 이것을 Shortest-Remaining-Time-FIrst(SRTF)라고 한다.

 

 그렇다면 둘 중 어느 것이 더 Optimal한 방법일까? 직관적으로도 알 수 있지만 당연히 빼앗는 방법이다.

 

 다음 예시 두 개로 nonpreemptive SJF와 preemptive SJF(SRTF)의 차이를 살펴보자. 그림과 같이 프로세스 네 개가 각각 도착시간이 다르고 Burst time도 다르다고 하자.

 

Non-preemptive SJF 스케줄링에 따르면 Average waiting time 은 (0 + 6 + 3 + 7)/4 = 4 가 된다.

그림 4 : SJF 예시(Nonpreemptive)

 

반면 Preemptive SJF(SRTF) 스케줄링일 때를 고려하자. 처음 0초에 P1이 CPU를 7초 쓰고자 하는데 Ready queue에 아무도 없기 때문에 CPU를 점유한다. 그러던 중 2초가 지났을 때 Burst time이 4인 P2가 들어왔다. 그러나 P1은 2초가 지났더라도 Burst time이 5가 남았기 때문에 후순위로 밀리게 된다. 이런 식으로 스케줄링이 되면 다음 그림 5와 같은 양상이 되며 Average waiting time은 (9+ 1 + 0 + 2)/4 = 3으로 Nonpreemptive SJF 보다 줄어든 waiting time을 얻을 수 있다. 

 

그림 5 : preemptive SJF 예시(SRTF)

 

 그러나 이 방법에는 아주 치명적인 두 가지 약점이 있다. 첫 번째는 Starvation problem, 즉, 굶어죽는 문제가 발생한다. 그러니까 CPU burst time long 프로세스는 영원히 후순위로 밀리며 CPU를 얻지 못하게 되는 문제가 발생할 수 있다는 것이다. 두 번째는 프로세스의 정확한 CPU burst time을 측정할 수 없기 때문에 burst time을 추정해야 하는데 (그림 9를 참고하자) '추정'하는 과정에서 발생하는 문제가 발생한다. 현재 n + 1 번째 CPU burst time을 예측한다고 한다면, n번째 CPU burst time과 n번째를 위해 예측했던 cpu burst time의 가중 평균으로 예측한다. 이것의 점화식을 연결하여 수식으로 전개하면 그림 6, 그림 7과 같을 것이다. 현재와 가까운 CPU burst의 CPu burst time을 더 많이 반영하고, 현재에서 멀어질수록 적게 반영한다는 것인데 이를 Exponential averaging이라 한다. 어찌 되었든 이러한 추정을 통해 스케줄링을 하기 때문에 정확한 CPU burst time을 알 수 없다. 따라서 짧은 CPU burst time을 예상했지만 CPU를 훨씬 길게 점유할 수도 있게 되는 문제가 발생할 수 있다.

 

그림 6 : CPU burst time의 추정

그림 7 : Exponential Averaging

그림 9 : 프로세스의 흐름

 

---

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

 사실 이전의 SJF나 SRTF도 Priority scheduling이다. Priority가 predicted next CPU burst time인 셈이다. Priority scheduling도 Nonpreemptive와 preemptive 버전으로 구현 가능하며 SJF와 마찬가지로 starvation problem이 발생할 수 있다.

 

 이를 해결할 수 있는 방법잊 존재하는데 그것은 바로 'Aging'기법이며 쉽게 말하면 경로사상이다. 시간이 지날수록 우선순위를 높여주는 것이며 그러다 보면 언젠가 문제가 될 수 있는 프로세스의 우선순위가 가장 높아지는 순간이 올 것이라는 발상에서 도입한 것이다.

 

그림 8 : Priority Scheduling의 문제와 해결 방안

---

Round Robin (RR Scheduling)

 

 RR Scheduling은 현대 preemptive 운영체제의 근간이 되는 스케줄링이다. 그 동안 우리가 프로세스를 운영체제가 어떻게 관리하는지 설명을 들었던 방식이다. Timer가 존재하여 timer의 시간을 세팅하고 프로세스에게 넘기며 timer interrupt로 프로세스의 CPU 독점을 막는 방법이다. I/O bound job의 경우, 짧은 시간 동안 빠르게 I/O를 요청하며 빠른 응답 시간을 기대할 수 있고, CPU bound job의 경우, 무작정 오래 CPU를 점유하는 것이 아니라 적절히 CPU를 내주고 받으며 수행된다. 이 방법은 n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit으로 CPU 시간의 1/n을 얻게 된다. 즉 모든 프로세스들이 (n-1)*q time 이상 기다리지 않게 된다. 만약 q time(할당 시간)이 무한정 길어지게 되면 FCFS와 똑같은 방법이 되며 q time이 작아지게 되면 context switch 오버헤드가 굉장히 커지게 되어 비효율적이 된다.

 

 다음 그림 10의 예시를 통해 살펴보자. 할당 시간을 20이라고 설정한다면 P1, P2, P3, P4 모두 최대 20만큼의 시간 동안 CPU를 사용할 수 있으며 총 4개의 프로세스가 있기 때문에 아무리 밀려도 60 time 내에서는 CPU를 맛볼 수 있게 된다(Response time).

 

그림 10 : RR 스케줄링 예시

 그러면 Round Robin의 장점은 무엇인가? SJF는 대기 시간의 총합이 가장 적다고 했다. RR은 대기 시간의 총합은 SJF보다 길지 모르나 response time은 더 짧다는 장점이 있다. Time sharing OS에서 사용자와 interact하는 job이 많을 때 유리하다. Interactive job은 짧은 응답 시간이 대단히 중요하기 때문이다. RR이 좋은 이유는 Long job과 Short job이 섞여 있기 때문이다. 모든 job이 homogeneous 하다면 오히려 Context switch의 오버헤드가 더 커질 것이다. 가령 10분씩 은행 업무를 처리해야 하는 사람이 100명이라 하자. FCFS를 쓰게 된다면 그냥 10분마다 한 사람씩 집에 갈 수 있지만, RR로 10초마다 한 사람씩 바꿔가며 처리해주게 되면 맨 마지막에 모든 사람이 같이 집에 가게 되는 비효율적인 상황이 된다. Response time은 빠를 수 있으나 꼭 좋은 양상은 아니라는 것이 핵심이다. 요컨대 RR은 일반적으로 SJF보다 average turnaround time이 길지만 response time이 더 짧으며, Homogeneous job들이 있는 상태보다는 Heterogeneous job들이 queue를 이루고 있을 때 더 효과적이 된다..

 

그림 11 : RR 스케줄링 요약

---

그림 12 : 할당 시간에 따른 Turnaround time 추이

 추가적으로 time quantum(할당 시간)이 길다고 해서 반드시 average turnaround time이 짧아지는 것은 아니라는 것도 알아두자.

---

---

본 글들은 이화여대 반효경 교수님 2014학년도 1학기 운영체제 강의를 기반으로 작성됩니다.

링크 : http://www.kocw.net/home/search/kemView.do?kemId=1046323