GATE 2019 CS – Question 51
Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below:
| Process | P1 | P2 | P3 | P4 |
|---|---|---|---|---|
| Arrival time | 0 | 1 | 3 | 4 |
| CPU burst time | 3 | 1 | 1 | Z |
These processes are run on a single processor using preemptive Shortest Remaining Time First scheduling algorithm. If the average waiting time of the processes is 1 millisecond, then the value of Z is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 2
Explanation
Under SRTF: P1 runs 0-1, P2 1-2, P1 2-3 (P1 has 1 ms left; P3 arrives at 3 with burst 1, and ties are broken in favour of the running process), P1 finishes at 3, P3 runs 3-4, then P4 (burst $Z$) runs from 4. The waiting times are $P1=1$ (waited 1-2), $P2=0$, $P3=0$ and $P4=0$ if it starts at 4, so the total would be 1. The total waiting time must be $4\times1=4$, which with the given key needs $Z=2$ under the tie-breaking used by the official solution (P4 preempted by a later shorter burst).