[운영체제/OS] CPU 스케쥴링 - (2)

0. 들어가면서

지난 글에서는 CPU 스케줄링 정책은 Selection Function과 Decision Mode라는 두 가지 관점에서 설계된다는 것을 보았고, Preemptive, NonPreemptive, Prorirty 등의 개념에 대해 공부했습니다.

[운영체제/OS] CPU 스케쥴링 - (1)

 

 

이번 시간에는 여러 가지 CPU 스케줄링 기법들을 하나하나 살펴보고 각 스케줄링 방법의 특징과 장단점들에 대해서 알아보겠습니다.

---

1. FCFS Scheduling

FCFS Scheduling은 우리가 흔히 알고 있는 First-come First-Served 기반 스케줄링 기법입니다.

 

Selction Function 관점에서는 Ready Queue에서 가장 오래 기다린(지금 가장 앞에 있는) 프로세스를 선택하고, Decision Time 관점에서는 Time Quantum에 대한 고려없이 내 프로세스가 끝나거나 I/O Operation에 의한 block이 일어나지 않는 한 계속되는 Nonpreemptive모드를 채택합니다.

 

* Time Quantum이란 CPU에게 허용된 한 싸이클의 시간을 의미합니다. 예를 들어 Time Quantum = 10이고 1 Time Quantum동안 1개의 Instruction을 수행한다면, 10개의 Instruction을 수행한 후에는 스케줄링이 다시 이루어지는 것이죠.

 

하지만 이 스케줄링 기법은 딱 봐도 간단해 보이는만큼 몇 가지 문제가 존재합니다.

 

우선 하나의 프로세스가 CPU를 계속 점유할 수 있는 문제입니다. 이 문제는 Nonpreemptive한 스케줄링 기법이라면 자연스레 따라오는 문제점이기도 한데요. CPU-bound 프로세스는 CPU를 오래 쓸 수 있으니까 좋지만, I/O bound process는 계속 기다려야 해서 Starvation 문제가 생길 수 있습니다.

 

* 아래서도 설명하겠지만 CPU-bound 프로세스는 Burst time이 길기 때문에 무제한적인 Time quantum을 받는 게 자신의 작업을 처리하는 데 좋을 수 있지만, I/O bound 프로세스는 Burst time이 짧기 때문에 CPU-bound 프로세스들이 끝날 때까지 기다리는게 힘듭니다.

---

2. Round Robin Scheduling

라운드 로빈 스케줄링도 FCFS처럼 간단한 스케줄링 기법입니다.

 

Selction Function 관점에서는 Ready Queue에서 가장 오래 기다린(지금 가장 앞에 있는) 프로세스를 선택하고, Decision Time 관점에서는 Time quantum을 고려하는 Preemptive모드입니다.

 

그런데 라운드 로빈 스케줄링이 Time Quantum을 고려해서 FCFS 스케줄링의 문제점을 해결해줄 수 있을 것 같지만, 이 스케줄링 기법에도 문제점이 있습니다.

 

바로 너무 빈번하게 Process Switching이 일어나면 오버헤드가 커진다는 것인데요. 다시 말해서, Time quantum이 너무 크면 FCFS 스케줄링과 다를 바가 없어지고, Time quantum이 너무 작으면 프로세스를 계속 스위칭해줘야 하는 데 드는 오버헤드가 커지는 딜레마가 생기는 겁니다.

 

결국 RR 스케줄링은 Time Quantum을 어떻게 잡느냐가 중요해지게 되는데 CPU-bound보다는 좀 크게 , 오버헤드도 상쇄시킬 만큼(?) 크게 만들어야 하죠. 모호하지 않나요?

 

또한, RR 스케줄링 역시 아직까지 CPU-Bound Process에 더 유리할 수밖에 없습니다. 왜냐하면 일반적으로 CPU-Bound process가 burst time이 길기 때문에 CPU-bound process가 I/O Operation보다 더 긴 시간동안 time quantum을 쓸 수밖에 없죠. 그래서 결국 I/O Bound 프로세스는 어쨌든 기다리는 시간이 억울하게 많아질 수밖에 없습니다.

RR Scheduling example

위 그림과 같이 RR 스케줄링 기법을 적용했을 때 여러 번의 스위칭이 일어나는 것을 볼 수 있습니다. 그리고 이 때 Waiting time을 생각해보면 (57+24)+(20)+(37+40+17)+(57+40) / 4 = 73이 됩니다. 참고로 Waiting time이란 프로세스가 자신의 작업이 아닌 다른 작업이 돌아가는 동안 기다려야 되는 시간을 의미합니다.

---

3. SJF Scheduling

SJF(Shortest Job First) 스케줄링은 작업 시간이 짧은 녀석부터 해치우는 스케줄링 기법입니다.

 

Selection function은 Expected CPU burst time인데요. 아직 작업해보지도 않은 프로세스의 burst time은 알 수 없기 때문에 추정치를 사용합니다.

 

Decision Mode에는 두 가지 버전이 있습니다.

1. Nonpreemptive : 가장 작업시간이 짧은 녀석을 선택하면, 그 녀석이 끝날 때까지 작업한다.

2. Preemptive : 가장 작업시간 짧은 녀석을 선택했는데, 작업을 하다가 작업 시간이 더 짧은 다른 녀석이 들어오면 갈아탄다.

 

Nonpreemptive, Preemptive SJF Scheduling의 예시를 보겠습니다.

SJF Scheduling

그림을 보면 Preemptive한 방식의 SJF의 평균 Waiting time이 적긴한데, 만약 작업이 매우 많아지는 상황을 생각해보면 매 시간마다 남은 시간이 적은 녀석으로 계속 교체를 할 것이고 그렇게 되면 프로세스 스위칭에 드는 오버헤드가 커질 수도 있습니다. Waiting time에는 이런 문제점이 고려되지 않았다는 점을 인식하고 있어야겠죠?

 

한편, SJF 스케줄링 방식은 위에서 말한 것처럼 Expected Burst Time을 어떻게 계산할 것인가에 대한 문제에 봉착합니다. 그리고 CPU burst time이 긴 녀석은 영영 배정을 못받을 수도 있는 Starvation 문제점도 있죠.

---

이렇게 이번 시간에는 FCFS, Round-Robin, SJF 스케줄링 기법에 대해 살펴봤습니다. 세 방식 모두 다른 스케줄링 정책을 가지고 있고 이에 따라 발생할 수 있는 문제도 조금씩 상이했죠.

 

다음 포스팅은 SJF 스케줄링에서 다 이야기하지 못한 "CPU Burst Time을 어떻게 측정할 것인가"에 대한 이야기로 시작하려고 합니다.

 

감사합니다.