이 글은 건국대학교 2024년 1학기 운영체제 수업과 『Operating Systems: Three Easy Pieces』 를 참고하여 작성되었습니다.

『Operating Systems: Three Easy Pieces』
7장. Scheduling: Introduction

CPU는 어떠한 기준으로 context switch를 발생시킬까요?
각 프로세스에게 한번에 얼마동안 CPU 자원을 할당할까요?

CPU Scheduling

가정

1. 모든 프로세스의 job들은 동일한 시간동안 실행된다.
2. 모든 프로세스들은 동시에 도착한다.
3. 프로세스가 한번 시작하면, 끝날 때까지 실행된다.
4. 모든 프로세스들은 I/O작업 없이 CPU자원을 사용하는 job만 수행한다.
5. CPU는 모든 프로세스들의 실행 시간을 미리 알 수 있다.

위의 가정들을 하나씩 지워 나가며 CPU scheduling 방법에 대해 알아봅시다.

성능 측정의 기준은 Turnaround time

💡 𝑇 𝑡𝑢𝑟𝑛𝑎𝑟𝑜𝑢𝑛𝑑 = 𝑇 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑖𝑜𝑛− 𝑇 𝑎𝑟𝑟𝑖𝑣𝑎𝑙

Turnaround time 은 프로세스가 도착한 시간부터 모든 작업을 완료한 시간까지의 전체 소요시간을 의미합니다. 앞으로 살펴볼 CPU 스케줄링 알고리즘에서 Turnaround time 을 기준으로 성능을 비교 분석할 예정입니다.

1. FIFO : First In, First Out

Fist Come, First Served라는 의미의 FCFS로도 불립니다. 해당 알고리즘은 의미 그대로 먼저 온 프로세스 순서대로 CPU 자원을 제공하므로 구현하기 쉽다는 장점이 있습니다. 3개의 프로세스가 모두 10ms 동안 실행된다고 가정하면, 평균 turnaround time 은 (10+20+30)/3 = 20ms 가 됩니다.

이 때, 모든 프로세스가 동일한 시간만큼 실행된다는 첫번째 가정을 지워보겠습니다.
100ms 동안 실행되는 프로세스 A가 0ms에 가장 먼저 도착했고, 실행 시간이 10ms인 프로세스 B, C가 0ms에 곧이어 들어왔다고 가정해봅시다. 이 경우, B와 C는 A가 종료될 때까지 대기해야 합니다. 이 상황에서 평균 turnaround time은 (100+110+120) / 3 = 110ms 가 됩니다.

이처럼 실행 시간이 긴 작업이 끝날 때까지 실행 시간이 짧은 작업들이 기다려야 하는 현상을 'convey effect' 라고 합니다.

2. SJF : Shortest Job First

convey effect 문제를 해결하기 위해, 실행 시간이 짧은 프로세스를 먼저 실행시키는 SJF 알고리즘을 사용할 수 있습니다. 이 알고리즘을 사용하면 동시에 도착한 A, B, C 중 실행 시간이 짧은 B와 C가 먼저 실행되므로 평균 turnaround time이 (120+10+20)/3 = 50ms 이 됩니다. 이 스케줄링 알고리즘은 모든 프로세스들이 동시에 도착했을 경우 최적의 해를 제공해줍니다.

이 때, 모든 프로세스들이 동시에 도착한다는 두번째 가정을 지워보겠습니다.
모든 프로세스는 한번 실행되면 업무를 모두 마칠 때까지 CPU 자원을 양보하지 않으므로, A가 0ms에 도착하고 B와 C가 10ms에 도착하는 상황에서 convey effect 가 발생합니다. 평균 turnaround time도 다시 악화될 수밖에 없습니다. (100+100+110)/3 = 103.33

Preemptive Scheduler

위와 같이 모든 프로세스들이 자신의 작업이 완료될 때까지 CPU 자원을 양보하지 않고 계속 점유하는 스케줄링 방식을 'Non-preemptive sheduler'라고 합니다.
반면, 실행 중인 프로세스를 중간에 멈춘 뒤 다른 프로세스에게 CPU 자원을 할당할 수 있는 방식을 'Preemptive Scheduler'라고 입니다. 이 방식은 실행 중인 프로세스를 중단하고, 다른 프로세스에게 CPU 자원을 할당하기 위해 context switch를 수행할 수 있습니다.

3. STCF : Shortest Time-to-Completion First

Preemptive Shortest Job First라는 의미의 PSJF로도 불립니다. 이 알고리즘을 사용하면, 처음 A만 도착한 시점에서는 A가 실행됩니다. 이후, A보다 실행 시간이 짧은 B, C가 들어오면 각 프로세스가 업무를 모두 마치기까지 남은 시간을 비교하여 더 짧은 프로세스를 실행시킵니다.
위에서 살펴봤던 예시 상황에서 STCF 알고리즘을 적용하면 turnaround time을 (120+10+20)/3 = 50 으로 줄일 수 있습니다.

여기선 context switch가 발생할 때 오버헤드가 0이라고 가정했습니다.

성능 측정의 기준으로 Response time을 추가

(𝑇 𝑡𝑢𝑟𝑛𝑎𝑟𝑜𝑢𝑛𝑑 : 도착~종료, 𝑇 𝑟𝑒𝑠𝑝𝑜𝑛𝑠𝑒 : 도착~시작)
지금까지는 알고리즘의 성능 지표로 turnaround time 만 고려했지만, 지금부터는 response time도 함께 고려하도록 하겠습니다.

💡 𝑇 𝑟𝑒𝑠𝑝𝑜𝑛𝑠𝑒 = 𝑇 𝑓𝑖𝑟𝑠𝑡𝑟𝑢𝑛− 𝑇 𝑎𝑟𝑟𝑖𝑣𝑎𝑙

response time이란, 프로세스가 처음 레디큐에 도착한 시간부터 처음 실행되기까지 걸린 시간을 의미합니다.

위의 예시에서 평균 turnaround time은 최적화되었으나, 평균 response time은 (0+0+10)/3 = 3.333... ms 로 상대적으로 좋지 않습니다. 평균 response time을 개선하려면 어떤 스케줄링 알고리즘을 사용해야 할까요?

4. RR : Round Robin

time slicing 기법을 사용하는 Round Robin 알고리즘을 사용하면 됩니다!
프로세스의 작업 시간을 time slice 단위로 쪼개어 실행하다가, time slice 시간이 지나면 그 때마다 context switch를 하는 방식입니다.

위에처럼 time slice를 2ms 로 지정하면 평균 response time 을 (0+2+4) = 2ms 로 개선할 수 있습니다. 평균 response time은 time slice 단위를 어떻게 설정하는지에 따라 달라질 수 있습니다.

하지만, 이 방식은 turnaround time을 악화시킨다는 문제가 있습니다. 또한 context switch가 빈번히 발생하여 오버헤드가 증가하고, 결과적으로 성능이 저하됩니다.

이 때, 모든 프로세스들은 CPU자원을 사용하는 job만 수행한다는 4번째 가정을 지워보겠습니다. 이제 프로세스에서는 실행 도중에 I/O 작업을 수행할 수도 있습니다.

Incorporating I/O

프로세스 A 실행 도중 디스크 I/O 요청이 발생하면, A는 I/O 작업이 완료될 때까지 blocked 상태가 됩니다. 이 기간 동안 A는 CPU를 사용하지 않으므로, CPU 자원이 낭비되지 않도록 스케줄러가 다른 프로세스를 실행시킵니다. A가 I/O 작업을 시작할 때 스케줄러를 호출하고, I/O 작업이 끝나면 다시 스케줄러를 호출하여 CPU 자원을 재할당받아 실행을 재개합니다. 이로써 CPU를 항상 최적으로 활용할 수 있습니다.

이 gant chart 속 상황에서는 RR을 사용하지 않았습니다.

마지막 가정인 'CPU는 모든 프로세스들의 실행 시간을 미리 알 수 있다.' 만 남았는데요, 현대에서는 프로세스이 총 실행 시간을 미리 알 수 없습니다.
이후 실행 시간을 모르는 상황에서 CPU 스케줄링을 진행하는 방식에 대해 알아보겠습니다.