Project ForgeConsider the set of processes with arrival time (ms), CPU burst time (ms), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time.
P1: arrival 0, burst 11, priority 2 P2: arrival 5, burst 28, priority 0 P3: arrival 12, burst 2, priority 3 P4: arrival 2, burst 10, priority 1 P5: arrival 9, burst 16, priority 4
The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling is ____.
Explanation
Trace: [0,2) P1 runs (2ms of 11). At t=2, P4 (priority 1 < P1's priority 2) preempts; [2,5) P4 runs (3ms of 10). At t=5, P2 (priority 0, highest) preempts; [5,33) P2 runs uninterrupted its full 28ms (no arriving process ever has priority < 0), finishing at 33. At t=33, ready processes are P1(9ms left,pri2), P4(7ms left,pri1), P3(2ms,pri3,arrived 12), P5(16ms,pri4,arrived 9) — highest priority is P4: [33,40) P4 finishes. Next highest is P1: [40,49) P1 finishes. Next is P3: [49,51) P3 finishes. Last is P5: [51,67) P5 finishes. Waiting time = completion − arrival − burst: P1=49−0−11=38, P2=33−5−28=0, P3=51−12−2=37, P4=40−2−10=28, P5=67−9−16=42. Average = (38+0+37+28+42)/5 = 145/5 = 29.
Source: GATE CS 2017 (Session 2) (2017)
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.