Four processes arrive at 0, 1, 2 and 3 with bursts 8, 4, 9 and 5. What is the average waiting time under preemptive SJF (SRTF)?
SHORT ANSWER
Run order by remaining time: P1 0-1, P2 1-5, P4 5-10, P1 10-17, P3 17-26. Waiting times are P1 9, P2 0, P3 15, P4 2, so the average is 26 / 4 = 6.5 ms.
Explain it simply
SRTF (Shortest Remaining Time First) is SJF with an interrupt. Whenever a new process arrives, compare its burst with what is left of the running process. If the newcomer is shorter, it takes the CPU.
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
Example
Walk through time:
- t=0: only P1, runs.
- t=1: P2 arrives with 4; P1 has 7 left. P2 preempts.
- t=2 and 3: P3 (9) and P4 (5) arrive, but P2 has less left. P2 keeps running and finishes at 5.
- t=5: remaining are P1 (7), P3 (9), P4 (5). P4 runs until 10.
- t=10: P1 (7) runs until 17.
- t=17: P3 runs until 26.
text
| P1 | P2 | P4 | P1 | P3 |
0 1 5 10 17 26Waiting = completion - arrival - burst:
- P1: 17 - 0 - 8 = 9
- P2: 5 - 1 - 4 = 0
- P3: 26 - 2 - 9 = 15
- P4: 10 - 3 - 5 = 2
Average = (9 + 0 + 15 + 2) / 4 = 26 / 4 = 6.5 ms.
What to say in the interview
"SRTF preempts whenever a newcomer has a shorter remaining time than the running process. The Gantt order is P1, P2, P4, P1, P3, with waits 9, 0, 15 and 2, so the average is 6.5 ms. I use waiting = completion - arrival - burst."
Common mistakes
- Using the burst time instead of the remaining time when comparing.
- Forgetting to subtract the arrival time.