Project ForgeConsider the following four processes with arrival times (ms) and CPU burst times (ms): P1 (arrival 0, burst 3), P2 (arrival 1, burst 1), P3 (arrival 3, burst 3), P4 (arrival 4, burst Z). These processes run on a single processor using preemptive Shortest Remaining Time First scheduling. If the average waiting time of the processes is 1 millisecond, then the value of Z is ____.
Explanation
Trace: [0,1) P1 runs. At t=1, P2 arrives with remaining time 1 < P1's remaining 2, so P2 preempts and runs [1,2), completing at t=2 (wait=0). P1 resumes [2,3); at t=3, P3 arrives (remaining 3) but P1's remaining (1) is shorter, so P1 continues and finishes exactly at t=4 (wait=4−0−3=1). At t=4, P4 also arrives, giving ready processes P3(remaining 3) and P4(remaining Z). Assuming Z<3, P4 runs first to completion at t=4+Z (wait=0), then P3 runs [4+Z, 7+Z) (wait=7+Z−3−3=1+Z). Average waiting = (1+0+(1+Z)+0)/4 = (2+Z)/4. Setting this equal to 1 gives Z=2, which is indeed <3, confirming the assumed case.
Source: GATE CS 2019 (Set-2) (2019)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.