Consider the following four processes with arrival times (in milliseconds) and…
2019
Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below:
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________.
Attempted by 144 students.
Show answer & explanation
Correct answer: 2
Key idea: simulate the preemptive Shortest Remaining Time First schedule and compute each process's waiting time; then use the given average waiting time to solve for Z.
From t=0 to t=1: P1 (burst 3) runs. At t=1 P2 (burst 1) arrives and runs from t=1 to t=2, finishing. P1 has 2 ms remaining.
From t=2 to t=3: P1 runs (1 ms left). At t=3 P3 (burst 3) arrives. From t=3 to t=4 P1 finishes. So P1's waiting time = 4 - 0 - 3 = 1 ms; P2's waiting time = 0 ms.
At t=4 P4 (burst Z) arrives. If Z < 3 then P4 runs immediately from t=4 to t=4+Z (waiting 0), and then P3 runs from t=4+Z to t=7+Z. P3's waiting time = (4+Z) - 3 = 1 + Z.
Compute average waiting time (for the Z < 3 case): (P1 + P2 + P3 + P4) = (1 + 0 + (1+Z) + 0)/4 = (2+Z)/4. Set this equal to the given average 1:
(2 + Z)/4 = 1 => 2 + Z = 4 => Z = 2.
Conclusion: Z = 2 ms (this satisfies Z < 3, so the derived schedule is valid).
A video solution is available for this question — log in and enroll to watch it.