CPU Scheduling

CPU Scheduling이란 뭘까? Scheduling이라는 단어에서 유추할 수 있듯이 CPU의 일정을 계획한다는 의미로 직역할 수 있다. 즉, 현재 CPU 자원을 수행중인 process들 중 누구에게 할당할 것인지를 결정하는 일련의 과정을 의미한다.

Process 실행 도중 I/O 같은 이벤트가 발생한다면 CPU는 위의 그림과 같이 I/O가 끝날 때 까지 기다린다. 그러나, CPU는 초당 매우 많은 작업을 수행하기 때문에 쉰다는 것은 상당한 손실이 아닐 수 없다. 따라서 적절히 CPU에게 작업을 할당해서 최대한 쉬는 것을 방지하도록 해야 한다.

이 그래프를 보면, I/O-bound job과 CPU-bound job의 구분을 위해 CPU burst time과 frequency간의 상관관계를 표현한 그래프이다. Process의 경우 I/O-bound와 CPU-bound로 구분 할 수 있는데 둘의 경우 long / short-term으로도 구분할 수 있기 때문에 CPU 보유 시간이 다르고 이로 인해 CPU Scheduling이 필요하게 된다.

State Transition

[OS] Processes and Threads
이전 post에서 이 그림을 바탕으로 process의 state에 대해 설명했었다.

여기서 더 나아가 Queue의 관점으로 설명을 하자면, 각각의 process들은 상태에 맞는 Queue에 들어가게 되고 Pop이 된 뒤 다른 Queue로 Push되면서 상태가 바뀌게 된다. 여기서 중간중간 보면 Long-term scheduling, Medium-term scheduling, short-term scheduling 단어를 볼 수 있을 것이다. 이 세 scheduler가 process를 scheduling하는데 위에서 말했듯이 process마다 CPU를 할당받았을 때 보유하고 있는 시간이 다 다르기 때문에 이 scheduler들이 적절히 분배를 해서 최대한 CPU가 시간 당 최대의 효율을 낼 수 있도록 하는 것이다.

(더 자세한 설명은 위의 그림의 필기를 보면 이해가 쉬울 것이다.)

CPU Scheduler

CPU Scheduler의 역할은 방금 전 설명했지만 시간 당 CPU가 최대한 많은 process를 실행하도록 memory에 탑재되어 있는 ready 상태의 process들에게 CPU를 할당해서 최대 효율을 얻도록 하는 역할이다.
CPU scheduling은 다음과 같은 상태에서 수행된다.

1. running -> waiting (I/O request)
   : waiting 상태로 있는 경우 CPU가 놀고 있기 때문에 ready queue에서 적절한 process에게 CPU를 할당
2. running -> ready
   :process에게 할당된 시간이 다 끝난 경우 (=timerunout) CPU를 강제로 빼앗아 다른 process에게 넘김
3. waiting -> ready (I/O finished interrupt)
   : I/O interrupt handler가 원래 실행중이였던 process에게 CPU를 다시 넘겨주는 과정. 단, ultitasking을 지원하는 대부분의 컴퓨터의 경우 원래 process의 CPU time이 얼마 남지 않은 경우 context switch를 통해 원래 process에게 다시 CPU를 넘겨주는 overhead가 더 클 수 있기 때문에 무조건적으로 원래 process에게 CPU를 넘겨주지 않을 수도 있다.
4. Terminate
   : Process가 모든 instruction들을 끝마친 경우 CPU를 넘겨주고 terminate 상태로 바뀐다.

이 중 1, 4번은 자발적으로 수행하기 때문에 강제성이 없어서 nonpreemptive 라고 하고, 나머지 2, 3번은 강제로 수행하기 때문에 preemptive 라고 한다.

Scheduling Criteria (Performance Index)

Scheduling 과정에서 Performance에 대한 척도는 총 5가지가 있다.

• CPU utilization - MAX
  : CPU를 최대한 바쁘게 만들어야함
• Throughput - MAX
  : 단위 시간 당 실행하는 process들의 개수
• Turnaround time - MIN
  : 특정 process가 실행을 시작하면서부터 끝마칠 때까지 걸린 시간
• Waiting time - MIN
  : ready queue에서의 대기시간의 총합
• Response time - MIN
  : User가 프로그램을 시작했을 때 가장 먼저 발생하는 response까지 걸리는 시간 (= 사용자 입장에서 interactivity [상호작용]를 느끼도록 만들어주는 시간)
  ex) 카카오톡으로 메시지를 보낼 때 키패드의 'ㄱ'을 입력했을 때 그게 화면에 띄워지는데까지 걸린 시간

Scheduling Algorithms

이 부분이 이번 CPU scheduling의 핵심부분이라고 할 수 있다. 지금까지는 CPU Scheduling이 뭔지에 대해 살펴보았다면 지금부터는 어떤 방법으로 CPU Scheduling을 실행하는지 살펴볼 예정이다.

FCFS Scheduling

: FCFS Scheduling이란, First Come First Served의 약자로 먼저 온 Process에게 우선적으로 CPU를 할당하는 알고리즘이다. Queue의 특징인 FIFO (First In First Out)와 같은 기능을 하기 때문에 같은 개념이라고 봐도 무방하다고 한다.

Gantt Chart를 통해 예시로 확인해보면,

Process	Burst Time	Waiting Time
P1	24	0
P2	3	24
P3	3	27

이렇게 표로 나타낼 수 있다. FCFS의 경우 들어온 순서대로 수행하기 때문에 P3의 경우 P1, P2가 끝나야 CPU를 할당받을 수 있기 때문에 P3의 waiting time은 24+3=27이 된다.
따라서 이 3개 process의 평균 waiting time은 (0+24+27)/3=17이 된다.

그러나 만약, process의 순서가 뒤바뀌면 어떻게 될까?

Process	Burst Time	Waiting Time
P2	3	0
P3	3	3
P1	24	6

Process의 순서만 뒤바꼈는데 waiting time이 눈에 띄게 줄은 것을 확인할 수 있다. 이를 Convoy effect라고 한다.
여기서 Convoy effect란, 호위병 효과라고도 하는데 날쌘 호위병들이 느린 왕때문에 함께 느려지는 효과로 이를 process에 대입하면 시간이 짧은 process가 앞에 먼저온 시간이 긴 process를 기다려야 하기 때문에 ready 상태로 대기시간이 길어지는 상황을 의미한다.

따라서 이 경우 먼저온 process에게 먼저 CPU를 주는 것은 fairness 측면에서는 올바른 방법이지만, 비효율적이기 때문에 다음 알고리즘인 SJF Scheduling이 등장하게 되었다.

SJF Scheduling

: SJF Scheduling이란 Shortest Job First scheduling의 약자로 위에서의 문제점을 해결하기 위해 CPU time이 짧은 process부터 먼저 CPU를 할당받도록 scheduling하는 알고리즘이다.

SJF의 경우 Preemptive / Nonpreemptive 두 가지로 분류할 수 있다.

Preemptive : 만약 현재 실행중인 process보다 더 짧은 cpu time을 갖고 있는 process가 올 경우 강제로 cpu 점유권을 넘기는 상황.
SRTF (Shortest-Remaining-Time-First)라고 불린다.
Nonpreemptive : CPU가 주어진 process의 burst time이 끝날때 까지 뺏을 수 없다.

Nonpreemptive SJF

Process	Arrival Time	Burst Time
P1	0	7
P2	2	4
P3	4	1
P4	5	4

예시를 통해 이해해보면, P1의 경우 총 Burst time이 7이다. 그러나 그 다음 process인 P2가 2일 때 도착을 했음에도 넘겨주지 않는다. 그렇게 P1의 burst time이 모두 끝나면 그 다음 process에게 넘겨줘야 하는데, 다 끝난 시기에는 나머지 P2, P3, P4 모두 도착한 상황이기 때문에 이 중 burst time이 제일 짧은 P3에게 넘겨주게 된다. 이 과정을 끝날때까지 반복하고 만약 P2, P4처럼 burst time이 같은 경우 먼저 온 process에게 넘겨준다.

Preemptive SJF

Process	Arrival Time	Burst Time
P1	0	7
P2	2	4
P3	4	1
P4	5	4

Preemptive는 burst time과 상관없이 더 빠른 process에게 넘겨준다. 즉 P2가 도착한 시점인 2초에서 P1의 남은 시간이 5초이고 P2의 burst time은 4초이기 때문에 P2에게 넘겨준다. 그 다음 P3가 4초에서 도착했을 때 존재하는 process를 비교해보면 P1=5, P2=2, P3=1이기 때문에 이 때도 P2가 P3에게 CPU를 넘겨주게 된다. 이 과정을 계속 반복하는 것이 preemptive SJF인 SRTF이다.

근데 여기서 의문이 생긴다. 다음 process에게 넘겨주는 것 까지는 그렇다 치는데 다음 process의 burst time이 얼마인지는 어떻게 알 수 있을까? 이 질문에 대한 답은 "알 수 없다"이다. 단지 예측을 할 뿐이지 정확히 알 수는 없다. 그래서 이전의 CPU burst를 토대로 exponential averaging을 이용해 예측을 한다.

$\tau_{n+1}=\alpha t_n + (1-\alpha)\tau_n$ 에서 $\alpha=0$ 인 경우 직전의 평균은 무시하고 과거 전체의 평균을 신뢰한다는 의미이고 $\alpha=1$ 인 경우 반대로 과거 전체의 평균은 무시하고 가장 최근의 평균을 신뢰한다는 의미이다.

Priority Scheduling

이 방식의 경우 각각의 process에게 주어진 priority number를 기준으로 CPU를 할당한다. Priority Scheduling은 하나의 알고리즘이 아니라 알고리즘을 만드는 정책 (틀)이라고 생각하면 편하다. 왜냐하면 priority를 어떤 것에 부여하느냐에 따라 여러 알고리즘이 생성될 수 있기 때문이다. 가장 대표적인 예시로 priority를 예측된 다음 CPU burst time에게 부여한다면 이게 곧 SJF scheduling이 된다.

그러나 Priority의 경우 큰 문제점이 존재하는데 그건 바로 Starvation이다.
Starvation이란 말그대로 굶는다는 의미로 priority가 낮은 process가 자신보다 priority가 높은 process가 ready queue로 들어올 때마다 뒤로 밀려나 결국 실행을 못하게 될 때 발생하는 문제이다.
굶는 상황을 방지하려면 어떻게 해야할까? 바로 "장유유서"이다. 즉, ready queue에 머문시간이 길었기 때문에 priority rule을 깨지 않는 선에서 나이순으로 실행하는 것이다. 시간이 지날 때마다 priority가 낮아서 굶고 있는 process의 priority를 늘려주면서 일정 시간이 지나면 priority가 낮았던 process의 priority가 높아져있게 되어 결국 실행이 되게 되는데 이를 Aging 이라고 한다.

Round Robin (RR)

각각의 process가 10~100 ms 사이의 CPU time (time quantum)을 갖고 있어서 이 시간이 경과하면 다음 process에게 CPU를 넘겨주고 ready queue의 뒤에 push 되는 과정을 반복하게 된다. 간단히 말해 FCFS에 time quantum이 추가된 개념이다. 이 때 time quantum의 경우 적절한 시간을 잡아야 하는데 time quantum이 너무 크게 되면 FCFS랑 다를게 없어지고 너무 작아도 Context Switch의 빈도가 높아져 overhead가 커지기 때문이다.

Process	Burst Time
P1	53
P2	17
P3	68
P4	24

예를 들어 위와 같은 Burst time을 갖는 4개의 process와 20의 time quantum을 갖는 RR가 있다고 하자. 즉, 20이 지나면 다음 process에게 CPU를 넘겨주고 ready queue의 제일 뒤로 들어간다. 이 중 한 사이클이 끝나고 P4에서 P1으로 넘어갈 때를 보면 P1=33, P3=48, P4=4의 값을 갖고 있다. SJF Scheduling의 경우는 P4에게 넘겨주겠지만 Round Robin은 FCFS의 rule을 따르고 있기 때문에 P1에게 넘겨주게 된다. 이 과정을 모든 process의 남은 시간이 0이 될 때까지 반복한다.

Multilevel Queue

Multilevel Queue는 이름에서 알 수 있듯이 여러 개의 ready queue를 사용하는 방법이다. 예를 들어 foreground에는 CPU 사용시간이 정해져 있는 Round Robin을. background에는 한번 CPU를 잡으면 process가 끝날때까지 사용하는 FCFS를 사용하여 여러 process들을 다룰 수 있도록 하는 것이다. Round Robin은 여러 알고리즘의 기반이 되는 것은 맞지만, RR 하나 만으로는 I/o-bound job에 우선순위를 주는 정책이 불가능하기 때문에 $+\alpha$가 필요하고 이에 대하여 생각하게 된게 queue를 여러개 사용하는 것이다.

Queue를 여러개 사용하였기 때문에 scheduling 역시 각각의 queue에 대해 따로따로 해주어야 한다.

• Fixed Priority Scheduling
  : Foreground의 job이 모두 끝나고 나서 Background에게 CPU를 할당
  -> Starvation의 가능성이 있음
• Time slice
  : Foreground가 끝날때까지 기다리지 않고 적절히 분배하여 CPU를 할당 (각각의 queue가 특정 CPU time을 가짐)
  ex) foreground (RR) - 80% / background (FCFS) - 20%

Multilevel Feedback Queue

Parameters that define MLFQ

• Queue의 개수
• 각각의 Queue에 적용된 Scheduling Algorithm
• 언제 process를 upgrade 해야할지 결정하는 방법
• 언제 process를 demote 해야할지 결정하는 방법
• process가 필요할 때 어떤 queue에 들어가야 하는지 결정하는 방법

여기 3개의 queue가 있다고 하자. 위에서부터 time quantum이 각각 8ms, 16ms인 queue와 FCFS scheduling algorithm을 사용하는 queue가 있다. 이 경우 다음과 같이 동작한다.

1. 첫 번째 Queue에 새로운 job이 들어간다
2. 이 경우 CPU를 할당받고 8ms 만큼의 시간이 주어진다
3. 만약 이 작업이 8ms 안에 끝나지 않은 경우 다음 Queue로 이동하고, 8ms 안에 끝난 경우 Pop 된다.
4. 다음 Queue로 넘어간 경우 추가적으로 16ms 만큼의 시간을 얻는다.
5. 여기서도 끝나지 않는다면 preempted 되어 다음 FCFS Scheduling이 적용된 Queue로 이동한다.

이 알고리즘을 적용할 경우 Short-term scheduling인 I/O-bound와 Long-term scheduling인 CPU-bound를 Queue로 분리할 수가 있게된다.
I/O-bound인 경우 Many short 이기 때문에 8ms만으로도 충분히 job이 끝나고도 남는다. 따라서 이 경우 다음 Queue로 넘어가는 경우가 매우 드물고 넘어가더라도 FCFS까지 가는일은 없을 것이다. 그러나 반대로 연산 작업과 같이 한번 CPU를 할당받으면 최대한 오래 사용하려고 하는 CPU-bound 의 경우 Few Long 이므로 8ms + 16ms 로도 부족할 가능성이 존재한다. 이 두개의 Queue로도 작업이 끝나지 않게 되면 FCFS가 적용된 Queue로 Push되어 들어간 순서대로 작업이 끝날때까지 실행되게 된다.

그러므로 MLFQ에서는 Multilevel Queue에서와는 달리 모든 process가 하나의 Queue로 들어가서 Queue 안에서 CPU burst time과 Queue의 time quantum에 의해 저절로 구분이 되도록 하는 방법을 사용하고 있다.

MLFQ의 규칙

1. Priority(A) > Priority(B) 이면, A가 실행된다 (B는 실행되지 않는다)
2. Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다.
3. 작업이 시스템에 진입하면, 가장 높은 Priority, 즉 맨 위의 큐에 놓여진다.
4. 주어진 time slice를 모두 사용하면 priority는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
5. time slice를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다