FCFS, SJF, SRTF, RR의 계산 및 비교
*Waiting time, Turnaround time의 계산 및 비교입니다.
Non-preemptive
FCFS (First-Come, First-Served)
- 가장 간단한 스케쥴링 알고리즘
- 먼저 도착한 프로세스부터 차례대로 실행
- 도착 순서에 따라 결과가 달라질 수 있음
Total waiting time : 0 + 7 + 10 + 18 = 35
Avg. waiting time : 35 / 4 = 8.75
Total turnaround time : 8 + 11 + 19 + 23 = 61
Avg. turnaround time : 61 / 4 = 15.25
SJF (Shortest-Job-First)
- 가장 짧은 CPU Burst time을 가진 프로세스부터 실행
- 항상 최적의 결과를 도출하며, 이를 증명할 수 있음
- 프로세스의 정확한 Burst time을 아는 것은 불가능하므로 예측 모델을 거쳐야 함
Total waiting time : 0 + 7 + 15 + 9 = 31
Avg. waiting time : 31 / 4 = 7.75
Total turnaround time : 8 + 11 + 24 + 14 = 57
Avg. turnaround time : 57 / 4 = 14.25
Preemptive
SRTF (Shortest-Remaining-Time-First)
- SJF의 Preemptive 버전
- 남은 Burst time이 가장 짧은 프로세스부터 실행
Total waiting time : (0 + 9) + 0 + 15 + 2 = 26
Avg. waiting time : 26 / 4 = 6.5
Total turnaround time : 17 + 4 + 24 + 7 = 52
Avg. turnaround time : 52 / 4 = 13
RR (Round-Robin)
- FCFS에 Time quantum을 추가하면서 Preemptive하게 변경한 버전
- 먼저 도착한 프로세스부터 순서대로 1 Time quantum씩 실행함
- Time quantum의 크기에 따라 결과가 달라질 수 있음
*Time quantum = 3
Total waiting time : (0 + 9 + 6) + (2 + 9) + (4 + 7 + 4) + (6 + 7) = 54
Avg. waiting time : 54 / 4 = 13.5
Total turnaround time : 23 + 15 + 24 + 18 = 80
Avg. turnaround time : 80 / 4 = 20
*Time quantum = 5
Total waiting time : (0 + 14) + 4 + (7 + 8) + 11 = 44
Avg. waiting time : 44 / 4 = 11
Total turnaround time : 22 + 8 + 24 + 16 = 70
Avg. turnaround time : 70 / 4 = 17.5
결과 : SRTF < SJF < FCFS < RR
RR이 FCFS보다 나쁜 결과를 도출해냈지만, 이는 종종 있는 일이다.
애초에 RR은 다른 알고리즘들과 결합하여 사용되는 것이 일반적이므로 그다지 문제될 일도 아니다.