0. 프로세스 스케줄링이란

프로세스들 사이에서 CPU가 어떤 프로세스를 어떻게 실행할 것인지를 결정하는 것을 CPU 스케줄링 또는 프로세스 스케줄링, 또는 쓰레드 스케줄링 이라고 한다.

CPU의 활용성(CPU utilization)을 최대화 하기 위해 스케줄링이 필요하다고 할 수 있다.

---

1. Preemptive vs Non-preemptive

어떤 프로세스가 실행 중일 때, OS가 강제로 CPU 사용을 리스케줄링 할 수 있는가?
-> 그 프로세스의 CPU 점유권을 빼앗아 다른 프로세스에게 줄 수 있는가?

Preemptive (선점) 이란 위의 질문으로 요약할 수 있다.

만약 어떤 시스템이 preemptive하다, 라고 하면 어떤 프로세스가 정상적으로 잘 동작하고 있다고 하더라도 CPU가 실행할 프로세스를 중도 변경할 수 있고 (즉 다른 프로세스로 하여금 CPU를 '선점' 할 수 있게 해주고), non preemptive하다 라고 하면 한 프로세스가 실행을 끝마치거나, 스스로 자원을 반납하기 전까지는 계속해서 CPU를 점유하는 것을 말한다.

preemptive의 경우에 한 프로세스가 system call을 handling하고 있을 때 preemption이 발생하면 커널 데이터는 race condition이 발생하여 다른 프로세스는 inconsistent한 (일관성 없는) 데이터를 읽을 우려가 있다.

---

2. Scheduling Criteria

스케줄링의 효율을 분석하는 척도(Criteria)는 여러 가지가 있다.

2-1. CPU Utilization

CPU가 일하고 있는 비율을 나타낸다. 일반적으로 utilization이 높으면 효율적이라고 말할 수 있겠으나 사용률이 100%에 육박하면 오히려 여유 공간이 부족하다는 뜻이므로 좋지 않다.

2-2. Throughput

the number of jobs processed per hour, 단위 시간당 처리할 수 있는 작업의 양(처리량)

2-3. Turnaround time

프로세스의 시작 시간부터 모든 일을 끝내고 종료할 때까지의 경과 시간을 뜻한다. IO waiting time 등 모든 시간을 포함한다.

2-4. Waiting time

실행되기를 기다리며 ready queue에서 대기 중인 프로세스들의 모든 대기 시간을 뜻한다.

2-5. Response time

프로세스의 시작 시간부터 처음으로 응답(반응)이 나올 때까지의 시간을 뜻한다.

2-6. Fairness

공평함. 각각의 프로세스들이 얼마나 공평하게 CPU를 나누어 사용하는가를 뜻한다.

CPU utilization, Throughput, Fairness : 크면 좋다
Turnaround time, Waiting time, Response time : 작으면 좋다

---

3. FCFS Scheduling

First Come First Served

말 그대로, ready queue에 들어오는 순서대로 처리하는 스케줄링 기법을 뜻한다.
사실 그냥 들어오는 대로 처리하는 거라 '스케줄링' 이라고 하기도 뭐하다.

Non-preemptive scheduling 이며 구조 설계가 간단하고 쉽다.

그러나 average waiting time이 높을 수 있다는 단점이 존재한다.

(※ 위와 같이 프로세스의 실행 시간과 실행 계획을 시각화한 그림을 간트 차트 Gantt chart 라고 한다)

위 그림과 같이 P1이 먼저 들어와 먼저 처리되고 있는데 그 뒤에서 P1에 비해 burst time이 상당히 짧은 프로세스 P2, P3이 들어온다.

Non-preemptive이기 때문에 P2, P3은 실행시간이 비교적 짧음에도 불구하고, P1이 끝날 때까지 기다려야 한다.

Average waiting time을 구해 보자면 (0+24+27)/3 = 17ms 이다.

위 예시처럼 비교적 실행 시간이 짧은 프로세스가 앞에 있는 실행 시간이 긴 프로세스에 의해 장시간 대기하는 상황을 호위 효과(Convoy effect) 라고 한다.

뒤따라 오는 빠른 주자가 앞선 느린 주자를 추월하지 못하는 상황

4. SJF Scheduling

Shortest Job First

가장 작은 CPU burst time, 즉 실행 시간이 가장 짧은 프로세스부터 실행하는 스케줄링 기법이다.

burst time이 짧은 순서는 P4, P1, P3, P2이다.

SJF는 최적의 average waiting time을 제공한다.

빨리 끝낼 수 있는 프로세스일수록 먼저 끝내므로 가장 효율적인 스케줄링 기법이지만, 아쉽게도 이 기법은 실제로 적용하기 힘들다.

'실행 시간이 짧은 프로세스' 라는 것을 OS가 어떻게 알까? 실행시간이 짧다. 라는 것은 그 프로세스를 끝내봐야 아는 것이다. 실행하기 전에는 이 프로세스를 완료하는데 얼마의 시간이 걸릴 지 정확히 알 수 없다. 즉 미래에 정해지는 정보를 가지고 현재에 스케줄링을 한다는 것이다.

물론 실행 시간을 예측하는 기법은 존재한다. 당연히 실제와는 괴리가 크다.

Exponential Average

Tn을 n번째 CPU burst의 길이라고 정의하고,
τn+1을 다음(n+1번째) CPU burst의 예측치라고 정의하자.

즉 τ는 현재까지의 과거 정보, T는 현재 정보라고 할 수 있다.

그러면 τn+1은 다음과 같이 식을 세워볼 수 있다.

여기서 α 기호는 현재의 값과 과거의 값 중에서, 다음 값을 예측하는 데 반영할 가중치 이다. α가 1이라는 것은 τn을 무시하겠다, 즉 경향성을 무시하겠다는 뜻이다.

이 때 τ 값들을 쭉 써보면 위의 식에서 τn은 또다시 Tn-1과 τn-1의 관계식으로 나타낼 수 있을 것이고, 이를 더더욱 확장하면 τn+1은 다음과 같이 쓸 수 있다.

여기서 α는 1보다 작거나 같은 값, 즉 거듭제곱을 할수록 값이 작아진다. 즉 τn에서 n값이 작아질수록 계수가 작아지기 때문에 τn+1을 결정하는 데 더 적은 영향을 미친다.

이렇게 n 값에 따라 미치는 영향이 n제곱만큼 지수적으로 작아지기 때문에 Expotential 이라는 이름이 붙은 것이다.

이 기법을 가지고 CPU burst를 예측하면 다음과 같이 나온다. 파란 선이 예측치, 검은 선이 실제이다.

Preemptive vs Nonpreemptive

SJF 스케줄링은 선점형으로도, 비선점형으로도 구현할 수 있다.

비선점형은 위에서 다루었으므로 선점형으로 구현하면 어떻게 되는지 살펴보자.

각 프로세스들의 도착 시간과 burst time이 위와 같고, 선점형이라면 간트 차트는 아래와 같다.

t=0일 때는 P1만 들어와 있으므로 P1을 수행한다. 그리고 1ms가 지나 P2가 들어왔는데 burst time이 P2가 더 짧다. 이러면 P2를 먼저 수행시킨다.

P2가 실행되는 동안에는 P2보다 burst time이 짧은 프로세스가 없으므로 P2는 중단되지 않고 종료할 수 있다. 그 후에는 그 다음으로 burst time이 짧은 P4가 실행, 그리고 P1, P3이 차례로 실행된다.

위와 같이 실행됐을 때에 Average waiting time을 구해 보면 다음과 같다 :

{(10-1)+(1-1)+(17-2)+(5-3)}/4 = 6.5ms

중간에 중단 됐었다면, 도착 시점과 마지막 실행 시간 사이에 다른 프로세스가 실행되고 있던 길이를 빼 주면 된다.

P0은 10에 마지막 실행이 되었고 그 사이에 9ms의 대기를 하였으므로 9ms, P2는 1에 들어와서 1에 바로 실행 되었으므로 0ms, P3은 2에 들어와서 17에 실행되었으므로 17-2=15ms, P4는 3에 들어와서 5에 실행되었으므로 5-3=2ms이다.

위의 프로세스들이 Non-preemptive로 실행되었다면 어떨까?

먼저 P1이 온전히 실행될 것이고 P1이 끝난 시점에는 P2, P3, P4 모두 도착해 있는 상태이다. 그러면 Burst time 순서인 P2, P4, P3 순서로 실행이 되고 Average waiting time은 다음과 같다 :

{0+(8-1)+(17-2)+(12-3)}/4 = 7.75ms

---

5. Priority Scheduling

우선순위 스케줄링은 우선순위가 높은 프로세스를 우선 실행하는 스케줄링 기법이다.

우선순위는 숫자로 표현되며 숫자가 큰 것이 우선순위가 높다고 할 것인지, 작은 것이 우선순위가 높다고 할 것인지는 사람 마음이지만 여기서는 작은 숫자가 더 우선순위가 크다고 하겠다.

우선 순위는 burst time이나 기타 요소들과 관계가 있을 수도 있고 없을 수도 있다. 아무튼 priority가 주어지면 거기에 맞게 Non-preemptive로 실행한다.

우선순위 순서는 P2->P5->P1->P3->P4 이고 그 순서대로 실행 되었다.

Average waiting time은 (6+0+16+18+1)/5 = 8.2ms이다.

Internally defined priority vs Externally defined priority

• Internally defined : 시간 제한, CPU burst에 대한 I/O burst의 비율, 열린 파일의 개수 등 운영체제 내적으로 측정 가능한(measurable) 요인들을 가지고 우선순위를 매긴다.

• Externally defined : 운영체제 외적으로 정해지는 우선순위이다. 정치적 요소들이 있거나, 돈을 많이 낸 유저의 프로세스거나, 프로세스의 중요성 등을 따진다.

special case of Priority Scheduling??

앞서 살펴본 FCFS 기법과 SJF 기법이 우선순위 스케줄링이라고 할 수 있을까?

먼저 SJF 기법은 우선순위를 CPU burst time 그대로 할당하면 burst time이 짧은 프로세스가 숫자가 낮을 것이고, 즉 우선 순위가 높을 것이다. 만약 숫자가 큰 프로세스가 우선순위가 높다고 가정하면 burst time에 역수를 취하는 등의 방법을 사용 가능하다.

FCFS 기법 또한 모두 동일한 우선 순위를 부여한다고 생각하면, 역시 마찬가지로 Priority Scheduling의 일종이라고 할 수 있다.

Starvation Problem

priority scheduling은 starvation(굶주림) 문제가 발생할 수 있다.

만약 우선 순위가 비교적 낮은 프로세스가 있는데, 뒤이어 계속 우선 순위가 높은 프로세스들이 들어온다면 그 프로세스는 계속 실행이 되지 않은 채 대기하고 있을 수 있다.

다르게 말하자면 얼마나 기다려야 하는지에 대한 보장이 없다. 이를 해결하기 위해 Aging 을 사용한다.

Aging

프로세스가 큐 안에 대기하는 일정 시간마다 해당 프로세스의 우선 순위를 올려 주는 것이다.

결국, 처음에는 우선순위가 낮은 프로세스였다 할지라도 점점 우선순위가 높아져 waiting time에 상한선(bound)가 생긴 것이라 할 수 있다.

---

6. Round-Robin Scheduling

기본적으로 FCFS처럼 동작하나, 자원 사용 제한 시간(Time quantum)이 존재한다.

Time quantum이 지나면 프로세스가 다 수행되지 않았더라도 다음 프로세스로 소유권이 넘어가게 된다. 아직 덜 끝난 프로세스는 다시 ready queue의 맨 끝으로 들어간다.

그리고 위와 같은 실행 방법에서 직관적으로 알 수 있듯, Preemptive scheduling이다.

초록색 표와 같은 프로세스 정보가 주어지고 time quantum을 4ms로 정했다고 가정해 보자.
ready queue의 헤드에 위치한 P1부터 수행한다. 4ms이 지나면 아직 P1은 20ms만큼의 작업량이 남았음에도 CPU 소유권을 P2에게 넘겨준다.

P2, P3의 burst time은 3ms이므로 제한 시간인 4ms안에 온전히 작업을 마칠 수 있다.

그 뒤로는 남은 P1만 계속해서 실행되어 최종적으로 30ms만에 세 프로세스가 모두 끝난다.

Average waiting time을 구해 보면 다음과 같다 :

(6+4+7)/3 = 5.66ms

P1은 중간에 P2, P3가 실행되는 동안 3ms씩 대기하였으므로 waiting time이 6ms이다.

이렇듯 time quantum을 어떻게 설정하느냐에 따라 프로세스들의 진행 양상이 달라진다. 어떻게 설정하느냐는 정하기 나름이지만, time quantum이 너무 클 경우 사실상 FCFS와 비슷해지고, 반대로 time quantum이 너무 작을 경우 프로세스가 너무 자주 switch 하게 되어 context switching에 소모하는 시간이 너무 많아진다. 즉 적절하게 설정해 주는 것이 좋으며, 일반적으로는 time quantum은 10ms로 설정한다.

7. Multilevel Queue Scheduling

실행 대기에 사용되는 ready queue를 여러 클래스로 세분화하여 나눠 놓은 것을 의미한다.

위 그림은 큐를 5개의 클래스로 나누어 세분화한 그림이고, 아래로 갈수록 우선순위가 낮아진다.

• 각각의 큐에는 절대적 우선순위가 존재하여 상위 큐가 비어있지 않는 한 무한정 대기한다.
• 각각의 큐는 자신만의 scheduling algorithm이 존재한다.
• 프로세스는 큐 사이를 이동할 수 없다. (한번 특정 큐에 들어가면 계속해서 그 큐에 상주한다)

절대적 우선순위가 존재하기 때문에 하위 큐에서 프로세스가 무한정 대기함으로써 발생하는 starvation에 대해서는 고려하지 않는다.

8. Multilevel Feedback Queue Scheduling

우선순위가 부여된 여러 큐가 존재하고 각각의 큐마다 scheduling algorithm이 존재하는 것은 Multilevel queue scheduling과 흡사하지만 각각의 큐 사이에서 이동이 가능하다는 점에서 차이가 있다.

맨 처음에는 queue 0인 higher priority queue에서 시작한다. 위 queue는 Round-Robin 방식으로 동작하여 time quantum은 8ms이다.

만약 time quantum을 다 채우고도 아직 실행이 끝나지 않은 프로세스는 그 하위 큐로 이동하는데 이 큐는 time quantum이 16ms이다.

16ms만에도 실행이 끝나지 않으면 가장 하위에 FCFS 방식으로 동작하는 큐로 넘어간다.
그리고 각각의 큐는 그 상위 큐가 비어있지 않는 한 계속해서 대기한다.

이 때 하위 큐에서 starvation이 발생할 수 있으므로, 일정 시간이 지나면 다시 상위 큐로 이동시켜주는 Aging 기법을 이용한다.