Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order .
If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to 2 decimal places) is ______.
ANSWER
The absolute difference between the average turnaround times of SJF (10.5 ms) and RR (15.75 ms) is 5.25 ms.
Official answer: 5.25Source: Official answer key, GATE 2020 CS (IIT Delhi)
All four processes arrive at time 0, so turnaround time equals completion time.
SJF (non-preemptive, all arrive together) runs in order of burst time: . Completion times: , , , .
RR with ms, queue order . Gantt chart:
After the first round, has ms left and has ms left. (2 ms) finishes at 10 and (4 ms) finishes at 14. In the second round runs 14 to 18 and finishes, then runs 18 to 21 and finishes.
Difference: ms.
KEY IDEA
With all arrivals at time 0, turnaround time equals completion time. Build the SJF order by burst length and trace the RR queue quantum by quantum, then compare the two averages.
WATCH OUT FOR
Forgetting that a process with less than one quantum left (P3 with 2 ms) gives up the CPU early, which shifts every later start time. Another slip is using waiting time instead of turnaround time.
From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 8 CPU scheduling questions, with notes
