[전산학] CPU 스케줄링

 과거의 Single-processor system에서는 한번에 오직 하나의 프로세스만이 순차적으로 실행될 수 있었다. 다른 프로세스가 실행되기 위해서는 CPU가 현재 실행중인 프로세스를 끝내고 프리 상태에 도달할 때까지 기다려야만 했던 것이다. 하지만 실제적으로는 입출력을 기다리는 시간동안은 CPU는 아무일도 하지 않게되고 이는 CPU utilization에 있어 비효율로 이어진다. 프로세스의 생명 주기동안 CPU를 필요로 하는 시간의 비중이 크지 않기에 굳이 이 전체의 시간동안 CPU를 부여한다는 것은 낭비이다. 전화로 예를 들면 쉬울 것이다. 우리가 누군가와 통화를 할때면 서로 말하고 있는 시간보다 침묵하고 있는 시간의 비중이 압도적으로 크다고 한다. 사실 여러분은 이렇게 전화선을 낭비하고 있는 것이다. 

출처: 컴퓨터인터넷IT용어대사전

그래서 도입된 multiprogramming의 개념은 기본적으로 메모리에 다수의 프로세스를 적재하는 것을 말한다. 하나의 프로세스가 입출력을 처리할 때, CPU가 이를 기다리지 않고 다른 프로세스에 할당되는 것이다. -참고로 IO 작업의 처리 속도는 CPU의 처리 속도에 비교하면 턱없이 느리다- 쉽게 말해 CPU가 잠시라도 쉴틈이 없도록, 노동법따윈 무시하고 뺑뺑이를 돌리자는 것. 어떤 정해진 규칙과 방법에 의해서 프로세스들에게 CPU를 할당하는 것을 CPU Scheduling algorithm이라 한다. 그렇다면, 이 규칙과 방법이란 무엇일까? 상식적으로 생각해봤을때는 모든 프로세스에게 동일한 시간동안 CPU를 쓰게 해주어야 공평하지 않을까? 물론 그런 개념의 기법을 포함해서, CPU의 할당 방법으로 쓰이는 몇 가지 대표적 CPU Scheduling algorithm들이 있다. 흔히 preemptive와 non-preemptive로 구분된다.

간단히만 설명하자면 non-preemptive는 프로세스가 끝날때까지 CPU를 점유하는 것이다. 그렇다면 preemptive는? 반대로 프로세스가 아직 끝나지 않았더라도, 상황에 따라 다른 프로세스로 CPU가 넘어갈 수 있는 것을 뜻한다. 차례차례 소개해보겠다.

Non-preemptive

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

가장 단순한 알고리즘이다. 작업 큐에 먼저 들어온 프로세스를 먼저 처리하는 것이다. 이름하여 공포의 선착순. 일단 가장 단순하기 때문에 간편하다는 이점이 있는 반면, 처리 시간이 오래걸리는 프로세스가 먼저 할당되어 버리면 그 작업이 끝날때까지 다른 프로세스들은 마냥 기다리게 된다는 단점이 있다. convoy effect라고도 한다. 간트차트로 간단히 예를 들어보자. 이렇게 큐에 P1, P2, P3 프로세스가 순차적으로 들어온 상황이다. FCFS 알고리즘은 아주 단순하게, 들어온 순서대로 CPU를 할당한다. 그리고 당연히 non-preemptive이기 때문에 하나의 프로세스가 종료될때까지 다른 프로세스로 CPU가 넘어가지 않는다.

2. Shortest-Job-First(SJF)

간단하게 말하면, "빨리 끝낼 수 있는 것부터 먼저 하자"이다. 큐 안에 있는 프로세스 중 처리 시간이 짧은 것에 먼저 CPU를 할당하는 방식이다. SJF에서는 짧은 작업이 우선적으로 처리되게 되므로 프로세스가 CPU를 기다리는 대기시간의 평균값이 짧아진다는 장점이 있다. 하지만 프로세스가 처리되는데 소요되는 시간인 burst time을 예측하는 것이 쉽지는 않은 일이므로, 이 것이 단점이 된다. burst time의 예측 역시 하나의 주제로 잡고 길게 얘기할 거리가 되므로 여기서 다루지는 않겠다.

Preemptive

3. Shortest-Remaining-Time-First(SRTF)

SJF의 preemptive 버전이라고 할 수 있겠다. 우선 SJF처럼 짧은 birst time의 프로세스에게 CPU를 할당하지만, 큐에 갑자기 더 짧은 프로세스가 들어오면 그 프로세스에게 CPU가 넘어간다. SJF와의 차이점을 알겠는가. 기본적으로 birst time이 짧은 프로세스를 먼저 처리하는 것은 동일하다. 하지만 현재 처리중인 프로세스가 완전히 종료될때까지 남은 시간보다 더 짧은 birst time의 프로세스가 큐에 들어온다면, OS는 즉시 CPU를 새로 들어온 프로세스에 할당한다. 앞선 두 알고리즘에 비해 살짝 복잡한 편인데, 예를 들어보자. 4개의 프로세스가 큐에 도착하는 시간인 Arrival Time와 Burst time이 아래의 표와 같다고 하자. SRTF 알고리즘을 적용한다면, CPU는 다음과 같이 할당된다.

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

아래 간트차트에서 눈에 띄는 특징이 보이는가? P1이 수행되다 말고 P2로넘어간다. P1이 1초(편의상 초 단위로 가정) 수행됐을때, P2가 큐에 들어온다. 그러면 P1은 여전히 8-1=7초가 남은데 반해 P2는 Burst time이 4초에 불과하므로, P2로 CPU가 넘어가게 되는것이다.

4. Round-Robin(RR)

RR 또한 단순하고 간단한 알고리즘이다. time quantum 혹은 time slice라고 불리는 일정한 시간 단위만큼 공평하게 CPU를 할당하는 것이다. 그러면 Birst time이 긴 프로세스가 먼저 수행되더라도, 한번의 time quantum이 끝나면 CPU가 다른 프로세스로 넘어가게 되므로 전체적으로 CPU 할당이 고르게 되는 장점이 있다. 하지만 RR에서 이 time quantum을 어느 정도 길이로 정하느냐는 아주 중요한 이슈이다. 너무 길면 결국 큐에 먼저 들어온 프로세스에 오래 머무르게 되므로 FIFO로 다를바가 없어지고, 너무 짧으면 CPU가 옮겨가는 과정인 context switching의 오버헤드가 커지기 때문이다. 길이가 4초인 time quantum을 가진 RR의 예시를 보자.

Process	Burst Time
P1	24
P2	3
P3	3

P1이 나머지 프로세스들에 비해 긴 burst time을 가졌다. FCFS였다면 P2가 수행되기 위해서는 최소 24초를 기다려야 했겠지만, RR의 경우 CPU를 일정한 시간동안 공평하게 할당한다. P1에서 4초가 할당된 후, P2로 넘어간다. P2는 burst time이 3초이기 때문에, time quantum 안에 작업이 끝나게 된다. CPU는 다시 P3으로 넘어가고, P3 역시 time quantum 안에 종료된다. 그러면 다시 CPU는 P1의 차지가 되는 것이다. 어찌보면 가장 이상적인 방식으로 보이지 않는가.

5. Multilevel Queue

multilevel queue는 사실 하나의 알고리즘으로 분류하기 보다는, 여러가지 알고리즘을 적절하게 모두 다 이용하자는 하이브리드 알고리즘의 개념이다. 예컨대, 아래 그림과 같이 여러 개의 큐를 두어 프로세스를 분류하는 것이다. 그리고 각 큐마다 그 성격에 맞는 CPU 스케쥴링 알고리즘을 적용하는 것이다. 또한, 큐 사이에도 우선 순위가 있다. 일반적으로 foreground 큐가 background 큐보다 높은 우선순위를 가지게 된다. 아래 그림의 예시에서는 아래로 내려갈수록 큐의 우선순위가 낮은 것이다.

출처: gitam.edu

하지만, multilevel queue에서는 프로세스를 적절한 큐에 넣어주는 것 자체가 어려운 문제이다. 그래서 탄생한 것이 마지막으로 소개할 Multilevel Feedback Queue다.

6. Multilevel Feedback Queue

MFQ 역시 여러 개의 큐를 둔다. 하지만 multilevel queue와의 차이점은, 프로세스를 적절한 큐에 넣어줄 필요가 없다는 것이다. 단계별로 3개의 큐를 두어, 프로세스들이 각기 다른 스케쥴링 정책을 가진 이 큐들을 통과하며 수행되는 것이다. 마치 음식물이 아래로 내려가면서 여러 소화기관을 거쳐 소화되는 모습과도 비슷하다. 그림을 본다면 더 이해가 빠를 것이다.

출처: gitam.edu

모든 프로세스는 가장 상위의 큐로 들어온다. 이 큐는 quantum time이 8초인 RR 알고리즘이 적용되며, 여기서 끝나지 못하는 프로세스는 다시 두번째 큐로 넘어가게 된다. 두번째 큐는 quantum time이 첫 큐의 두배인 16초이다. 이 quantum 동안에도 못끝나고 남은 프로세스들은 마지막 큐로 넘어오게 되는데, 마지막 큐는 넘어온 순서대로 처리를 하는 FCFS 방식이다. 짧은 burst time의 프로세스는 상위에서 끝나게 되고, 긴 프로세스들만 마지막까지 남게 되므로 전체적으로 봤을때는 SJF와도 유사하게 동작한다고 볼 수 있다. 하지만 burst time을 예측해야하는 SJF와는 달리, MFQ는 그러한 예측 과정이 필요없다. 또한, 적절한 큐에 프로세스를 넣어주는 수고도 하지 않아도 된다.