GATE CS 2025 Set 2 Q.26: CPU Scheduling

Processes $P_1, P_2, P_3, P_4$ 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?

Official answer and solution

Official answer: D
From: Official GATE 2025 answer key

Solution

Construct the Gantt chart for SRTF scheduling, compute each process's completion time and turnaround time ( $\text{TAT} = \text{CT} - \text{AT}$ ), and take the average.

Tracing the SRTF schedule:

$t = 0$ to $1$ : $P_1$ runs ( $9\text{ ms}$ remaining). At $t = 1$ , $P_2$ arrives with burst $13 > 9$ , so $P_1$ continues.
$t = 1$ to $2$ : $P_1$ runs ( $8\text{ ms}$ remaining). At $t = 2$ , $P_3$ arrives with burst $6 < 8$ and preempts $P_1$ .
$t = 2$ to $8$ : $P_3$ runs to completion at $t = 8$ . At $t = 8$ , $P_4$ arrives with burst $9$ .
$t = 8$ to $16$ : Remaining times are $P_1 = 8, P_4 = 9, P_2 = 13$ . $P_1$ runs to completion at $t = 16$ .
$t = 16$ to $25$ : $P_4$ ( $9 < 13$ ) runs to completion at $t = 25$ .
$t = 25$ to $38$ : $P_2$ ( $13$ ) runs to completion at $t = 38$ .

Process	Arrival Time (AT)	Burst Time (BT)	Completion Time (CT)	Turnaround Time (TAT = CT - AT)
$P_1$	0	10	16	16
$P_2$	1	13	38	37
$P_3$	2	6	8	6
$P_4$	8	9	25	17

Average turnaround time $= \frac{16 + 37 + 6 + 17}{4} = \frac{76}{4} = 19\text{ ms}$ .

Final answer

Option (D)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 26 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source