Four processes arrive at time 0 in the order P1, P2, P3, P4 with CPU burst times 5, 9, 2 and 4 ms respectively. Compute the average waiting time and average turnaround time under FCFS and under non-preemptive SJF. Which is better and why?
Show hints
Waiting time = start time − arrival time when each process runs in one go.
Show the explanation
Worked answer. All arrivals are at t = 0 and each process runs to completion once started, so waiting time = start time, and turnaround = completion time.
FCFS (order P1, P2, P3, P4)
| Process | Start | Finish | Waiting | Turnaround |
|---|---|---|---|---|
| P1 | 0 | 5 | 0 | 5 |
| P2 | 5 | 14 | 5 | 14 |
| P3 | 14 | 16 | 14 | 16 |
| P4 | 16 | 20 | 16 | 20 |
- Total waiting = 0 + 5 + 14 + 16 = 35 → average 8.75 ms
- Total turnaround = 5 + 14 + 16 + 20 = 55 → average 13.75 ms
Non-preemptive SJF (order P3, P4, P1, P2 by burst 2, 4, 5, 9)
| Process | Start | Finish | Waiting | Turnaround |
|---|---|---|---|---|
| P3 | 0 | 2 | 0 | 2 |
| P4 | 2 | 6 | 2 | 6 |
| P1 | 6 | 11 | 6 | 11 |
| P2 | 11 | 20 | 11 | 20 |
- Total waiting = 0 + 2 + 6 + 11 = 19 → average 4.75 ms
- Total turnaround = 2 + 6 + 11 + 20 = 39 → average 9.75 ms
Sanity check: turnaround = waiting + burst, and the bursts sum to 20, so 35 + 20 = 55 and 19 + 20 = 39. Both match.
Why SJF wins: running short jobs first means fewer processes are kept waiting behind a long job (the "convoy effect" in FCFS, here P3 and P4 waiting behind P2). For a set of jobs that are all available together, SJF gives the minimum possible average waiting time.
Follow-up: "What is the catch with SJF?" The OS cannot know future burst lengths, so it estimates them (often by exponential averaging of past bursts), and long jobs can starve. The preemptive version is Shortest Remaining Time First (SRTF).
Original UniCircle question. Last reviewed 28 Oct 2026.