공룡책으로 정리하는 운영체제 Ch.5

Process Scheduling 2018.05.03

Scheduling Criteria
FCFS (First-Come, First-Served)
SJF (Shortest Job First)
SRF (Shortest Remaining Time First)
RR (Round Robin)
Priority Scheduling

운영체제가 어떤 프로세스를 프로세서에 할당할 것인가 정하는 프로세스 스케줄링(Process scheduling)에 대해 다루는 챕터다. FCFS, SJF, RR 등 다양한 프로세스 스케줄링에 대해 소개한다.

Scheduling Criteria

운영체제가 프로세스를 프로세서에 할당하는 것을 디스패치(Dispatch)라고 한다. (이때 프로세스 상태가 ready에서 running으로 바뀐다.) 그리고 운영체제가 레디 큐(Ready queue)에 있는 프로세스들 중에서 어떤 프로세스를 디스패치할 것인가 정하는 것이 프로세스 스케줄링(Process scheduling)이다.

스케줄링 알고리즘에는 대표적으로 FCFS, SJF, SRF, RR 네 가지 방식이 있고, 알고리즘을 평가할 때는 수행 시간(Burst time)과 CPU 사용량(CPU utilization), 단위 시간 당 끝마친 프로세스의 수(Throughput), 하나의 프로세스가 레디 큐에서 대기한 시간부터 작업을 마칠 때까지 걸리는 시간(Turnaround time), 프로세스가 레디 큐에서 대기한 시간(Wating time), 프로세스가 처음으로 CPU를 할당받기까지 걸린 시간(Response time)을 기준으로 한다.

선점(Preemptive) 방식과 비선점(Non-Preemptive) 방식으로 나뉜다. 선점 스케줄링은 운영체제가 강제로 프로세스의 사용권을 통제하는 방식이고, 비선점 스케줄링은 프로세스가 스스로 다음 프로세스에게 자리를 넘겨주는 방식이다. 즉, 선점 스케줄링 방식에서는 CPU에 프로세스가 할당되어 있을 때도 운영체제가 개입해 다른 프로세스에게 CPU를 할당할 수 있다.

FCFS (First-Come, First-Served)

먼저 들어온 프로세스를 먼저 프로세서에 할당하는 방식이다.
Queue의 FIFO(First-In First-Out)와 동일하다.
구현이 쉬워서 간단한 시스템에 자주 사용된다.
프로세스 처리 순서에 따라 성능이 크게 달라질 수 있다.
수행 시간이 큰 프로세스가 먼저 들어오면 그 뒤에 들어온 프로세스들이 불필요하게 오랜 시간을 기다리게 되는 콘보이 효과(Convoy effect)가 발생한다.
먼저 온 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점 스케줄링 방식이다.

Process	Burst time	Response time	Turnaround time	Waiting time
P1	9	0	9	0
P2	1	9	10	9
P3	1	10	11	10

+----+----+----+----+----+----+----+----+----+----+----+
|                     P1                     | P2 | P3 |
+----+----+----+----+----+----+----+----+----+----+----+
0                                            9    10   11

\text{Average wating time} = {0 + 9 + 10 \over 3} = 6.33

P1, P2, P3 프로세스가 들어온 순서대로 할당됐다. P2, P3는 수행 시간이 짧음에도 P1이 끝날 때까지 기다리게 되어 평균 대기 시간이 늘어났다.

SJF (Shortest Job First)

프로세스의 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.
FCFS에서 발생하는 콘보이 효과를 해결할 수 있다.
최적 알고리즘이지만 수행 시간을 정확히 알 수 없다. (앞서 처리한 프로세스들의 기록을 보고 추측한다.)
버스트 시간이 큰 프로세스는 계속 뒤로 밀려나는 기아(Starvation)가 발생한다.
버스트 시간이 짧은 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점 스케줄링 방식이다.

Process	Burst time	Response time	Turnaround time	Waiting time
P1	6	3	9	3
P2	8	16	24	16
P3	7	9	16	9
P4	3	0	3	0

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|      P4      |              P1             |                P3                |                   P2                  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0              3                             9                                  16                                      24

\text{Average wating time} = {3 + 16 + 9 + 0 \over 4} = 7

프로세스의 수행 시간을 정확히 예측했다는 가정하에, 수행 시간이 짧은 순서대로 프로세서에 할당됐다.

SRF (Shortest Remaining Time First)

프로세스의 남은 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.
SJF에서 발생하는 기아 문제를 해결할 수 있다.
수행 중 다른 프로세스보다 남은 수행 시간이 적어지면 운영체제가 개입해 자리를 바꾸는 선점 스케줄링 방식이다.

Process	Arrival time	Burst time	Response time	Turnaround time	Waiting time
P1	0	8	0	17	9
P2	1	4	1	5	0
P3	2	9	17	24	15
P4	3	5	5	7	2

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| P1 |         P2        |           P4           |                P1                |                     P3                     |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0    1                   5                        10                                 17                                           26

\text{Average wating time} = {9 + 0 + 15 + 2 \over 4} = 26

P1이 수행되던 중, 1ms에 P2가 들어왔다. 이때 P1의 남은 수행 시간은 7ms이고, P2의 남은 수행 시간은 4ms이기 때문에 운영체제가 개입해 P1의 수행을 중단하고 P2를 프로세서에 할당한다. P2가 프로세서에 할당된 사이, 2ms에 P3가 들어왔으나 P2의 남은 수행 시간은 3ms이고, P3의 남은 수행 시간은 9ms이기 때문에 프로세서는 P2를 계속 수행한다. 이어서 3ms일 때 P4가 들어왔지만 P2의 남은 수행 시간은 2ms이고, P4의 남은 수행 시간은 5ms이기 때문에 여전히 P2가 수행된다. 이후에도 같은 방식으로 프로세스의 작업이 끝나거나 새로운 프로세스가 들어올 때마다 남은 수행 시간을 비교해 자리를 바꿔준다.

RR (Round Robin)

일정 시간 할당량(Time quantum) 단위로 여러 프로세스를 번갈아가며 프로세서에 할당한다.
시스템의 time-sharing과 같은 방식이다.
반응성이 좋다.
주로 우선순위 스케줄링(Priority scheduling)과 결합해 프로세스의 시간 할당량을 조절하는 방식으로 활용한다.
시간 할당량에 따라 운영체제가 계속 개입하는 선점 스케줄링 방식이다.

Process	Burst time	Response time	Turnaround time	Waiting time
P1	15	0	19	4
P2	2	3	5	3
P3	2	5	7	5

Time quantum = 3ms

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|      P1      |    P2   |    P3   |      P1      |      P1      |      P1      |      P1      |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0              3         5         7              10             13             16             19

\text{Average wating time} = {4 + 3 + 5 \over 3} = 4

모든 프로세스들이 동일하게 3ms씩 프로세스에 할당된다. P2와 P3의 경우 수행 시간이 2ms이기 때문에 할당된 3ms를 모두 사용하지 않았다.

Priority Scheduling

특정 기준으로 프로세스에게 우선순위를 부여해 우선순위에 따라 프로세서에 할당한다.
프로세스를 에이징(Aging)해서 오래 대기한 프로세스의 우선순위를 높이는 방식으로 사용된다.
SRF의 경우 남은 수행 시간을 기준으로 우선순위를 부여한다고 할 수 있다.
다른 스케줄링 알고리즘과 결합해 사용할 수 있으므로 선점, 비선점 모두 가능하다.

Process	Priority	Burst time	Response time	Turnaround time	Waiting time
P1	3	5	4	9	4
P2	1	1	0	1	0
P3	4	2	9	11	9
P4	5	1	11	12	11
P5	2	3	1	4	1

+----+----+----+----+----+----+----+----+----+----+----+----+
| P2 |      P5      |           P1           |    P3   | P4 |
+----+----+----+----+----+----+----+----+----+----+----+----+
0    1              4                        9         11   12

\text{Average wating time} = {4 + 0 + 9 + 11 + 1 \over 5} = 5

우선순위에 따라 프로세스가 할당되었다. 사용자가 자주 사용하는 프로세스의 우선순위를 높게 부여하는 식으로 기준을 만들 수 있다. 다만 특정 프로세스의 우선 순위가 계속 밀려 기아가 발생할 수 있으므로, 시간이 지날 때마다 프로세스의 나이를 증가시켜 오래 대기한 프로세스의 우선순위를 높여주는 조치가 필요하다.