FCFS, SJF, SRTF, RR의 계산 및 비교

*Waiting time, Turnaround time의 계산 및 비교입니다.

 

공룡책

 

Non-preemptive

 

FCFS (First-Come, First-Served)

• 가장 간단한 스케쥴링 알고리즘
• 먼저 도착한 프로세스부터 차례대로 실행
• 도착 순서에 따라 결과가 달라질 수 있음

Gantt chart

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을 아는 것은 불가능하므로 예측 모델을 거쳐야 함

Gantt chart

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이 가장 짧은 프로세스부터 실행

Gantt chart

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의 크기에 따라 결과가 달라질 수 있음

Gantt chart

*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

 

Gantt chart

*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은 다른 알고리즘들과 결합하여 사용되는 것이 일반적이므로 그다지 문제될 일도 아니다.