일반적으로, Single processor 시스템에서는 오직 하나의 프로세스만 실행 가능합니다.
즉, CPU에서 실행되고 있는 프로세스가 완전히 종료(terminated) 될 때까지 Ready queue에 있는
타 프로세스는 실행할 수 없다는 것입니다.
만약 위 상황에서, IO Request 등 기존 프로세스 실행을 잠시 멈춰야 할 때에는 Ready queue에 있는
타 프로세스는 기존 프로세스가 종료되지 않았으므로 실행 불가합니다. (becomes idle)
따라서, OS는 CPU는 보다 효율적으로 사용하기 위해 Ready queue에 있는 프로세스 중
하나를 선택한 뒤, 그 프로세스를 실행시키는데 이를 CPU Scheduling이라 하고, Ready queue 중
다음으로 실행할 프로세스를 고르는 과정을 CPU Scheduling Algorithm이라 합니다.
CPU Scheduling에 관여하는 요소는 크게 두 가지가 있는데, CPU Scheduler과 Dispatcher입니다.
CPU Scheduler는 CPU Scheduling Algorithm을 통해 다음으로 실행할 프로세스를 고르는 역할을,
Dispatcher는 CPU Scheduler가 고른 프로세스에 대해 Context Swtich를 발생시키는 역할을 맡고 있습니다.
CPU Scheduling Algorithm을 평가하기 위한 기준은 총 5가지가 있습니다.
1. CPU Utilization : 해당 CPU Scheduling Algorithm을 채택할 때, 전체 시간 중 CPU가 idle 상태로 있지 않고,
특정 프로세스를 실행시키기 위해 사용된 시간을 %로 표기한 것입니다.
즉, CPU Utilization이 높을수록 CPU가 놀지 않는(프로세스를 실행시키기 않는) 시간이 높다는
것을 의미합니다.
2. Throughtput : 해당 CPU Scheduling Algorithm을 채택할 때, 특정 시간동안 실행한 프로세스의 개수를 의미합니다.
예를 들면 10초 동안 5개의 프로세스를 실행한 CPU A와 3개를 실행한 CPU B 중 보다 Throughput이
높은 것은 CPU A입니다.
3. Turnaround time : 특정 프로세스가 Ready, Running, Waiting 상태일 때의 총 시간의 합계입니다.
즉 특정 프로세스가 Ready queue에 있었던 시간, Waiting queue에 있었던 시간, CPU에서 실행 되었던 시간의 합입니다. 작을수록 유리합니다.
4. Waiting time : 특정 프로세스가 Ready 상태일 때의 총 시간의 합계입니다. 작을수록 유리합니다.
5. Response time : 특정 프로세스가 Ready queue에 도착한 시간과 처음으로 CPU에서 실행되기까지 걸린 시간의
차이입니다. 만약 도착하자마자 즉시 실행될 경우, 그 프로세스의 Response time은 0초입니다.
작을수록 유리합니다.
이제 CPU Scheduling Algorithm을 살펴봅시다.
첫 번째로 FCFS(First come, First served)입니다. 쉽게 말하면 선착순으로, 먼저 도착한 프로세스부터 실행시킨다고
보면 될 거 같습니다. 특정 프로세스가 실행되는 동안 타 프로세스가 Ready queue에 들어와도 context switch가 일어나 지 않는 Non-preemptive scheduling algorithm입니다. (추후 언급되겠지만, Preemptive scheduling algorithm의 경우에 는 반대로 특정 프로세스가 Ready queue에 들어올 경우, 특정 조건을 만족할 경우 프로세스가 terminated되지 않아도
context switch가 일어나는 algorithm입니다.)
다음 예시를 볼까요? 위 사진을 보면 P1, P2, P3 순 도착했다고 가정하고 있고, FCFS(먼저 도착한 프로세스부터 실행) 알고리즘에 따라 CPU Scheduling을 하고 있기 때문에 P1, P2, P3 순으로 실행될 것입니다.
CF> CPU Burst time : 특정 프로세스가 실행을 완료하기까지 필요한 시간의 총합
예를 들어 P1의 경우 실행을 완료하기까지 24초 동안 running 상태로 있어야 함
모든 프로세스는 0초에 도착하였고, Waiting time은 특정 프로세스가 Ready queue에 있었던 총 시간이므로
- P1's waiting time : 0초(도착하자마자 실행되었고, 실행 중 status의 변화 없이 종료되었으므로)
- P2's waiting time : 24-0=24(0초에 도착하였고, 24초에 실행이 시작되었으므로)
- P3's waiting time : 27-0=27(0초에 도착하였고, 27초에 실행이 시작되었으므로)
Turnaround time : 특정 프로세스가 ready, running, waiting status였던 시간의 합
- P1's turnaround time : 0초에 도착하였고, 24초에 도착하였으므로 24-0=24초
- P2's turnaround time : 0초에 도착하였고, 27초에 종료되었으므로 27-0=27초
- P3's turnaround time : 0초에 도착하였고, 30초에 종료되었으므로 30-0=30초
하지만, FCFS 알고리즘은 단점이 있습니다. 바로 CPU Burst time이 긴 프로세스가 먼저 도착할 경우,
나머지 프로세스는 Ready queue에서 긴 프로세스가 종료될 때까지 기다려야 하므로 Waiting time, Turnaround time
이 길어진다는 단점이 있죠. 이를 Convoy Effect라고 합니다.
예를 들어, PPT와 달리 P2->P3->P1 순으로 프로세스가 도착했다면 P1의 waiting time은 6초로 기존 0초보다
커지겠지만, P2와 P3의 waiting time은 0초, 3초로 훨씬 짧아지게 되고, Average waiting time은 (0+3+6)/3 = 3이
되는 걸 볼 수 있습니다.
위 FCFS를 채용함으로써 발생하는 Convy Effect를 막기 위해 어떠한 알고리즘을 사용해야 할까요?
Convoy Effect는 CPU Burst가 긴 프로세스를 실행하는 동안 타 프로세스가 실행되지 못함으로써
발생합니다. 따라서, 프로세스가 도착한 순서가 아니라 CPU Burst가 짧은 프로세스 순으로 실행시키면
average waiting time을 최소화할 수 있을 것입니다.
이러한 CPU Scheduling Algorithm을 SJF(Shortest-Job-First)라 합니다. 직역하면, 가장 짧은 작업부터
실행시킨다는 뜻이죠.
한 번 예시를 살펴볼까요?
위 슬라이드는 Non-Preemptive SJF의 예시입니다.
0초에 도착한 프로세스의 경우 오직 P1이므로 P1이 실행됩니다.
2초, 4초, 5초에 각각 P2, P3, P4가 도착합니다. 위 SJF는 Non-Preemptive, 즉 특정 프로세스가 실행 중일 때
강제로 실행되는 프로세스가 바뀌지 않는 알고리즘이므로 P1은 계속 실행됩니다.
7초에 P1이 종료됩니다. 그 후, SJF 알고리즘을 채용중이므로 Ready Queue에 남아있는 프로세스 중
Burst time이 가장 짧은 프로세스가 실행됩니다. P3의 Burst time이 1초로 가장 짧으므로 P3가 실행됩니다.
8초에 P3가 종료됩니다. 그 후, SJF 알고리즘을 채용중이므로 Ready Queue에 남아있는 프로세스 중
Burst time이 가장 짧은 프로세스가 실행됩니다. 하지만 Queue에 남아있는 프로세스, P2와 P4의 Burst
time이 같습니다. P2가 실행됩니다. (만약 위 상황이 문제로 출제된다면, Burst time이 같을 경우 FCFS에 따 라, 즉 먼저 도착한 프로세스부터 실행시킨다고 문제에 따로 명시되어 있을 것입니다. P2가 2초, P4가 5초에
도착했으므로 P2가 먼저 실행됩니다. 앗, 학교 시험 이야기입니다. 기사 시험은 제가 본 적이 없어서 모르겟 네용...)
12초에 P2가 종료됩니다. 그 후 Queue에 있는 프로세스는 P4 1개이므로 P4가 실행됩니다.
16초에 P4가 종료됩니다.
위 슬라이드는 Preemptive SJF(SRTF)의 예시입니다. Preemptive SJF의 경우, 특정 프로세스가 실행되어 있는 중
타 프로세스가 들어올 경우, 기존 프로세스의 남은 Burst time과 신규 프로세스의 Burst time과 비교해, 신규 프로세스
의 Burst Time이 더 작다면 Context Switch가 일어나는 방식입니다. 이러한 방식 때문에 Preemptive SJF를 SRTF(Shortest Remaining Time First) 라 합니다. 프로세스가 종료될 때까지 남은 Burst time이 더 적은 프로세스가
먼저라는 뜻으로 이해하시면 될 거 같습니다.
0초에 P1이 들어옵니다. Ready Queue에 있는 프로세스는 P1이 유일하므로 P1을 실행시킵시다.
2초에 P2가 들어옵니다. 이 때, Preemptive SJF(SRTF)와 Non-Preemptive SJF의 차이를 알 수 있습니다.
기존 Non-Preemptive의 경우 P1이 종료될 때까지 기다렸지만, Preemptive SJF의 경우 두 프로세스의 Burst
Time을 비교한 뒤, 더 적은 Burst time을 가진 프로세스가 실행됩니다. 2초 상황의 경우, 기존 프로세스 P1이
종료될 때까지 남은 Burst time은 7-2 = 5초이고 (2초동안 P1은 실행되었으므로), P2의 Burst time은 4-0=4초 이므로 Burst time이 더 적은 P2가 실행되고, 이를 위해 Context Switch가 일어납니다.
4초에 P3가 들어옵니다. 이 때 P2의 남은 Burst time은 4-2=2초이고, P3의 Burst time은 1초이므로 P3가 실행
됩니다.
5초에 P3가 종료되면서, P4가 들어옵니다. 이 때 Ready Queue에 있는 프로세스 중 가장 짧은 Burst time
을 가진 프로세스가 실행됩니다.
P1 : 7 - 2 = 5초
P2 : 4 - 2 = 2초
P4 : 4초
따라서 P2가 실행됩니다.
7초에 P2가 종료됩니다. Ready Queue에 있는 P1, P4 중 더 짧은 Burst time을 가진 프로세스는 P4이므로 P4가 실행됩니다.
11초에 P4가 종료됩니다. Ready Queue에는 오직 P1만 있으므로 P1이 실행됩니다.
16초에 P1이 종료됩니다.
지금까지 SJF에 대해 알아보았습니다. 앞서 설명했던 FCFS와 달리, SJF의 경우 Burst time이 가장 짧은 프로세스부터
실행되므로 Convoy Effect가 발생하지 않는다는 장점이 있습니다. 하지만 SJF에는 치명적인 단점이 있습니다.
실행시킬 각 프로세스의 구체적인 Burst time을 사전에 알 수 없다는 거죠. 만약 SJF를 구현할 경우 우리는 OS가 정한 Initial Starting Burst Value와 실행되었던 프로세스의 실제 Burst time을 통해 다음에 올 프로세스의 Burst time을 예측함으로써 SJF를 구현할 수는 있습니다.
- 예측 관련 자세한 내용은 https://cs.stackexchange.com/questions/50438/how-does-the-os-determine-the-cpu-burst-time-of-a-process를 참고해 주세요)
하지만 어디까지나 예측값이지, 위 슬라이드처럼 각 프로세스의 정확한 Burst time을 알기는 어려우므로 좋은 알고리즘은 아니라고 할 수 있습니다. 그렇다면, SJF를 사용하지않고도 FCFS의 Convoy Effect를 막을 수 있는 알고리즘은 어떤 것이 있을까요?
이번에 소개할 Scheduling Algorithm은 RR(Round-Robin)입니다. RR은 Timer를 사용한 Preemptive한 CPU Scheduling Algorithm으로 특정 프로세스가 일정 시간(Quantum)동안 실행되면 Context Switch가 일어나는 알고리즘입니다.
위 슬라이드를 보시면 Time Quantum = 4라고 적혀 있습니다. 즉 기존 프로세스가 4초동안 실행되면 강제적으로 Context Switch가 일어난다는 뜻입니다.
0초에 P1, P2, P3가 들어옵니다. P1이 제일 먼저 들어왔으므로 P1이 실행됩니다.
4초에 P1에 할당된 Time Quantum이 0이 되었습니다. P1은 다시 Ready Queue에 들어가고 두 번째로 들어온 P2 가 실행됩니다.
7초에 P2가 종료되었습니다. FIFO에 의거, P3가 실행됩니다.
10초에 P3가 종료되었습니다. 이 때 Ready Queue에 있는 프로세스는 P1뿐이므로 P1이 실행됩니다.
30초에 P1이 종료됩니다.
위 예시는 FCFS 알고리즘을 기준으로 실행되었다면 Convoy Effect가 일어났을 것입니다. P1이 제일 먼저 들어왔고,
P1의 Burst time이 제일 길기 때문이죠. 하지만 RR은 Quantum을 통해 Burst time이 긴 프로세스가 CPU를 계속 차지하는 걸 막음으로써 타 프로세스의 Waiting time이 길어지는 것을 막을 수 있습니다. 그렇다면 RR의 단점은 무엇이 있을까요?
우선 첫 번째로 Burst time이 비슷한 Process에 대한 Average Turnaround time의 증가를 예시로 들 수 있습니다. 예를 들어서, Burst time이 100인 두 프로세스 P1과 P2가 0초에 들어왔다 가정해 보겠습니다. 만약 FCFS였다면 두 프로세스의 Turnaround time은 어떻게 되었을까요? P1은 0초에 들어와 100초에 종료되므로 100초, P2는 0초에 들어와 200초에 종료되므로 Average Turnaround time은 (100+200)/2 = 150입니다.
RR을 기준으로 실행시켜 보겠습니다. 이 때 Quantum = 1입니다. P1은 0초에 들어와 199초에 종료되고, P2는 0초에 들어와 200초에 종료되므로 Average는 (199+200)/2 = 199.5입니다.
두 번째로 RR은 Time Quantum의 크기에 영향을 많이 받는다는 점입니다. Time Quantum의 크기가 지나치게 작을 경우
Context Switch가 필요 이상으로 많이 일어나 Overhead가 커지고, 크기가 지나치게 커질 경우 FCFS처럼 동작하게 됩니다. 실제로 RR을 구현할 때에 Quantum은 10~100ms로 지정합니다.
이번에 소개할 알고리즘은 Priority Scheduling입니다. 각 프로세스에 우선순위(Priority)를 지정해준 뒤, 우선순위가 높은
프로세스부터 실행시키는 방식입니다. 앞서 언급한 SJF(Shortest-Job-First) 역시 Burst time을 우선순위의 기준으로 한 Priority Scheduling이라고 할 수 있습니다. 위 Prioriy Scheduling의 경우 SJF와 마찬가지로 preemptive와 non-preemptive로 나뉩니다. 관련 문제를 풀 때 주의 깊게 보시길 바랍니다.
예시를 보겠습니다. 위 예시의 경우 Priority의 숫자가 낮을수록 높은 Priority를 가집니다. 즉, P2가 가장 높은 Priority를 가지고 P4가 가장 낮은 Priority를 가집니다. (숫자가 높을수록 높은 Priority를 가질 수 있습니다. 문제에 따라 다릅니다.)
위 Priority Scheduling은 Preemptive하지 않으므로 높은 Priority를 가진 순(P2-P5-P1-P3-P4)으로 실행하면 되겠습니다.
그렇다면, 위 Priority Scheduling의 단점으로는 어떤 것이 있을까요? 바로 낮은 우선순위를 가진 프로세스는 계속 실행이
안 될 수 있다는 것이겠지요. 예를 들어 Priority가 계속 한 자리 숫자인 프로세스만 들어온다면 Priority가 두 자리, 세 자리인 프로세스는 계속 실행될 수 없을 것입니다. 이를 해결하기 위해, Aging("노화"라는 뜻입니다.)을 도입할 수 있습니다.
즉, 계속 실행되지 못하는 프로세스는 Priority를 높여줌으로써 실행되지 못 하는 걸 막을 수 있습니다.
그렇다면, 현대의 OS는 어떠한 Scheduling Algorithm을 채택하고 있을까요? 현대 OS는 Multilevel Queue 알고리즘을 채택하고 있습니다.
알고리즘은 간단합니다. priority가 같은 프로세스끼리 모아놓은 뒤, priority가 높은 프로세스들부터 지정된 Scheduling Algorithm을 통해 Scheduling을 하는 방식입니다. 위 예시의 경우 System Processes는 FCFS, Interactive Processes의 경우 SJF를 통해 Scheduling을 하고 있는 걸 알 수 있습니다.
- 위 사진 출처는 https://mycareerwise.com/content/multi-level-queue-scheduling/content/exam/nta-net/computer-science입니다.
다음 게시글은 Synchronization에 대해 작성하겠습니다. 감사합니다.
'TIL > OS' 카테고리의 다른 글
| 4. Thread (0) | 2023.07.25 |
|---|---|
| 3. Process (0) | 2023.05.05 |