For burst times 24, 3 and 3 (all arriving at time 0), what is the average waiting time under non-preemptive SJF?
SJF runs the shortest burst first: P2, P3, then P1. Waiting times are P2 0, P3 3, P1 6, so the average is (0 + 3 + 6) / 3 = 3 ms, which is the minimum possible.
Explain it simply
Shortest Job First is like letting people with one or two items use the express billing counter before the person with a full trolley. The long job waits a little, but several short jobs finish quickly, so the average waiting time drops.
Sort by burst length: P2 (3), P3 (3), P1 (24). Ties are broken by arrival order.
Example
| P2 (3) | P3 (3) | P1 (24) |
0 3 6 30| Process | Burst | Start | Waiting |
|---|---|---|---|
| P2 | 3 | 0 | 0 |
| P3 | 3 | 3 | 3 |
| P1 | 24 | 6 | 6 |
Average waiting time = (0 + 3 + 6) / 3 = 3 ms.
Compare with FCFS on the same jobs, which gave 17 ms. SJF is provably optimal for average waiting time when all jobs are available together.
The catch: the OS does not know burst lengths in advance, so real systems estimate them from past behaviour. And a long job can starve if short jobs keep arriving.
What to say in the interview
"SJF picks the shortest burst first, giving P2, P3, P1 with waits 0, 3 and 6. The average is 3 ms against 17 for FCFS. It is optimal for average waiting time, but it needs burst-time estimates and can starve long jobs."
Common mistakes
- Forgetting that SJF can starve long processes.