Processes arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times.
Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?
22
15
37
19
ANSWER
The average turnaround time is 19 ms, option (D).
Official answer: DSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)
Tabulate the processes: SRTF always runs the process with the least remaining time, and re-decides whenever a process arrives.
From to only is present and runs, so its remaining time falls to 9. At , arrives with 13, which is more than 9, so continues.
At , has 8 left and arrives with 6. Since , preempts .
runs from 2 to 8 and completes at . No other arrival happens before that, so it is not interrupted. arrives at .
At the remaining times are , , . is the shortest, so it runs from 8 to 16 and completes at 16. No new process arrives during this time.
Next, (9) is shorter than (13), so runs from 16 to 25 and then runs from 25 to 38.
Gantt chart:
Turnaround time = completion time arrival time: , , , .
Average ms, which is option (D).
KEY IDEA
SRTF is preemptive shortest-job-first: at every arrival and completion, run the process with the least remaining time. Turnaround time is completion time minus arrival time, not minus the start of execution.
WATCH OUT FOR
Treating the schedule as non-preemptive SJF, or using waiting time or completion time instead of turnaround time. Another slip is to let (6) wait for to finish, or to subtract 0 instead of the arrival time for and .
From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 8 CPU scheduling questions, with notes
