The GATE Grind

GATE 2019 CS – Question 51

Operating System · CPU and I/O Scheduling · 2 marks · Numerical answer

Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below:

ProcessP1P2P3P4
Arrival time0134
CPU burst time313Z

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

The source gives P3 a burst time of **3 ms**, not 1 ms. With arrivals 0,1,3,4, the SRTF schedule begins P1 from 0-1, P2 from 1-2, and P1 from 2-4.

At time 4, P3 has 3 ms remaining and P4 has Z ms. For Z<3, P4 runs next, then P3. Waiting times are 1, 0, $1+Z$, and 0 ms, respectively.

Their average is $(2+Z)/4$. Setting it to 1 gives **Z=2 ms**. The completed schedule is P4 from 4-6 and P3 from 6-9.

The earlier apparent source/key conflict came from transcribing P3's burst as 1 ms.

More CPU and I/O Scheduling questions

All CPU and I/O Scheduling questions →