운영 체제의 프로세스 scheduling 정책들

운영 체제의 scheduling 정책들을 알아보기 전에 프로세스에 대해 다음과 같이 가정합시다.

• 모든 프로세스가 CPU를 사용하는 시간이 똑같다.
• 모든 프로세스가 동시에 도착한다.
• 한 번 시작한 프로세스는 끝날 때까지 CPU를 사용한다.
• 프로세스는 I/O 요청 등 없이 CPU만 쓴다.
• 프로세스가 끝날 시간을 알고 있다.

현실에서는 절대 있을 수 없는 가정들이지만 정책들을 살펴보기 위해 일단 이렇게 가정하고 시작합시다.

 

그리고 2가지의 측정 기준을 정의합니다.

• Turnaround Time: 반환 시간(끝난 시간 - 도착 시간)
• Response Time: 응답 시간(스케줄링된 시간 - 도착 시간)

1. FIFO(First In First Out)

가장 기본적이고 쉽게 구현할 수 있는 정책입니다. 정책을 살펴보기 위해 아래와 같은 상황을 상상해 봅시다.

 

3개의 프로세스(A, B, C)가 있고, 세 프로세스가 동시에 0 시각에 도착했고(사실 정말 자세히 보면 기적적으로 작은 차이로 A-B-C 순서로 왔고), 각 프로세스는 CPU를 10의 시간만큼 사용합니다.

 

이러한 상황에서 운영 체제의 scheduler가 FIFO 정책을 사용한다면 아래와 같이 scheduling을 할 것입니다.

source: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf, 3쪽

이때 세 프로세스의 turnaround time을 각각 구해보면, A는 10 - 0 = 10이고, B는 20 - 0 = 20, C는 30 - 0 = 30입니다. 평균 turnaround time은 (10 + 20 + 30) / 3 = 20입니다. Response time을 계산하면, A는 0 - 0 = 0, B는 10 - 0 = 10, C는 20 - 0 = 20으로 평균 response time은 (0 +10 + 20) / 3 = 10입니다.

 

이제 모든 프로세스의 CPU 사용 시간이 똑같다는 가정을 없앱니다. 만약 A의 CPU 사용 시간이 100이라면 그림은 아래와 같이 바뀝니다.

source: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf, 3쪽

이 상황에서 다시 평균 turnaround time을 계산하면 (100 + 110 + 120) / 3 = 110이 되고, 평균 response time도 계산하면 (0 + 100 + 110) / 3 = 70으로 이전 상황보다 n배 이상 증가했음을 확인할 수 있습니다. 그리고 금방 끝날 수 있는 프로세스 B, C가 끝나는 시간도 뒤로 미뤄졌습니다. Performance 측면으로나, fairness 측면으로나 모두 안 좋아졌음을 확인할 수 있습니다.

2. SJF(Shortest Job First)

위의 문제점을 해결할 수 있는 방법으로 나온 정책입니다. 이 정책은 쉽게 말해, CPU 사용 시간이 짧은 프로세스를 먼저 scheduling 합니다. 만약 프로세스 A의 CPU 사용 시간이 100, B와 C는 10이고, 세 프로세스가 동시에 0의 시각에 도착했다면 SJF 정책을 사용하는 scheduler는 아래의 그림과 같이 scheduling 합니다.

source: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf, 4쪽

이때의 평균 turnaround time은 (10 + 20 + 120) / 3 = 50, 평균 response time은 (0 + 10 + 20) / 3 = 10으로 FIFO의 문제 상황보다 지표가 나아졌음을 확인할 수 있습니다.

 

하지만 프로세스 A가 동시에 도착한다는 가정을 깨고 먼저 도착한다면, 그림은 아래와 같이 바뀝니다.

source: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf, 5쪽

이 상황에서의 평균 turnaround time은 (100 + (110 - 10) + (120 - 10)) / 3 \( \approx \) 103.334, 평균 response time은 (0 + 100 + 110) / 3 = 70입니다. 이 상황에서도 똑같이 짧게 걸리는 프로세스라도 먼저 실행되고 있는 작업량이 많은 프로세스 때문에 늦게 끝납니다.

3. STCF(Shortest Time to Completion First) / PSJF(Preemptive Shortest Job First)

이러한 상황의 해결책으로 나온 정책입니다. 이 정책은 완료까지 짧게 걸릴 프로세스를 먼저 scheduling 하는 정책입니다. 이렇게 말로만 설명하면 SJF와 차이점을 딱히 못 느낄 수도 있습니다. 그러니 위의 문제 상황에서 STCF 정책을 적용해 봅시다.

프로세스 A가 진행되는 와중, 10의 시각에서 B, C 프로세스가 동시에 도착했을 때, 세 프로세스의 남은 CPU 사용 시간을 비교합니다. 프로세스 A는 100에서 10을 사용했기 때문에 90이 남았고, B와 C는 10씩 남았습니다. 따라서 사용량이 적은 B와 C 중 하나를 10의 시각에 새롭게 scheduling 합니다. 따라서 그림은 아래와 같이 바뀝니다.

source: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf, 6쪽

이때의 평균 turnaround time을 계산하면 ((20 - 10) + (30 - 10) + (120 - 0)) / 3 = 50이 되고, response time은 (0 + 0 + 10) / 3 \( \approx \) 3.334입니다. 위의 문제 상황보다 지표가 나아졌음을 확인할 수 있습니다.

4. RR(Round Robin)

지금까지 살펴본 앞의 3가지 정책은 사실 response time보다 turnaround time에 집중한 정책입니다. 그렇기 때문에 SJF 같은 정책에서 response time 수치가 안 좋은 것을 알 수 있습니다. 그래서 response time에 집중해서 만든 scheduling 정책이 RR입니다.

한 번 시작한 job은 끝날 때까지 멈출 수 없다는 가정을 깬다면, 운영 체제는 timer를 사용해 각 프로세스가 사용할 CPU 사용 시간을 제한할 수 있습니다.

source: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf, 7쪽

위의 그림은 세 프로세스 A, B, C 모두 0의 시각에 동시에 도착했고 각 프로세스의 CPU 사용 시간이 5로 동일하다는 가정에서 그린 그림입니다. 이 경우, SJF 정책을 사용할 때의 turnaround time은 (5 + 10 +15) / 3 = 10, response time은 (0 +5 +10) / 3 = 5입니다. RR 정책을 쓰고 timer 간격을 1로 설정하면, turnaround time은 (13 + 14 + 15) / 3 = 14, response time은 (0 + 1 + 2) / 3 = 1입니다. SJF 정책을 사용했을 때보다 turnaround time은 길어졌지만, response time은 짧아졌음을 확인할 수 있습니다. 이를 통해 RR 정책은 성능보다는 공정성에 중시한 정책임을 알 수 있습니다.

 

Timer의 간격을 줄일수록 response time은 더 짧아집니다. 하지만 timer의 간격을 너무 줄이면 프로세스 간의 context switch 비용이 증가하게 됩니다. 즉, response time과 context switch 비용 간에 trade-off가 발생하므로 상황에 맞는 적절한 timer 값이 필요합니다.

I/O 요청하는 프로세스

이제 프로세스가 I/O 요청을 할 수 있다고 합시다. 2개의 프로세스 A, B가 있고 모두 CPU 사용 시간이 50이고, 0의 시각에 동시에 도착했으며, 프로세스 A는 10의 시간을 사용할 때마다 10만큼의 I/O 작업을 수행한다고 합시다. 이러한 상황에서 STCF 정책을 따라 scheduling 하면 아래의 그림과 같이 됩니다.

source: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf, 10쪽

A가 먼저 scheduling 되면 위와 같은 그림으로 됩니다. 이때의 turnaround time은 (90 + 140) / 2 = 115, response time은 (0 + 90) / 2 = 45가 됩니다. 이때의 가장 큰 문제는 I/O 관련 일을 하는 동안 CPU가 놀고 있다는 점입니다. 이를 해결하기 위해 아래의 그림과 같이 overlap 하는 방법이 있습니다.

source: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf, 10쪽

이는 I/O 작업하는 동안 CPU가 프로세스 B에게 CPU를 할당하면서 turnaround time과 response time을 모두 단축시킬 수 있습니다. Turnaround time은 (90 + 100) / 2 = 95, response time은 (0 + 10) / 2 = 5가 됩니다.