FCFS, SJF, SRTF, and Why SJF Minimizes Average Turnaround
What This Concept Is
Three baseline non-interactive scheduling policies:
- FCFS (First-Come-First-Served) -- run jobs in arrival order, non-preemptive. Simple, predictable, sometimes disastrous.
- SJF (Shortest Job First) -- among all arrived jobs, run the one with the shortest total burst. Non-preemptive.
- SRTF (Shortest Remaining Time First) -- same idea as SJF but preemptive: if a new, shorter job arrives, preempt and run it now.
Each pair (arrival time, burst time) describes a job. A policy produces a schedule. The schedule has metrics.
Why It Matters Here
These policies are the ruler. Every more sophisticated policy (round-robin, MLFQ, CFS) is justified by comparing against SJF / SRTF on paper. If you cannot hand-execute them on five jobs, you cannot evaluate real schedulers.
Also: SJF's optimality proof is the prototype for proving any ordering policy optimal -- an exchange argument, just like greedy correctness in Semester 2.
Concrete Example
Three jobs, all arriving at t=0:
| Job | Arrival | Burst |
|---|---|---|
| A | 0 | 10 |
| B | 0 | 2 |
| C | 0 | 3 |
FCFS in the order A, B, C:
0 10 12 15
├────────┼────┼───┤
│ A │ B │ C │
Turnaround: A=10, B=12, C=15. Average = (10+12+15)/3 = 12.33.
SJF order B, C, A:
0 2 5 15
├──┼────┼──────────┤
│B │ C │ A │
Turnaround: B=2, C=5, A=15. Average = (2+5+15)/3 = 7.33.
SJF cut average turnaround by about 40% on the same workload. That is the convoy effect of FCFS in action: A, the long job, was delaying everyone.
SRTF with staggered arrivals:
| Job | Arrival | Burst |
|---|---|---|
| A | 0 | 10 |
| B | 2 | 2 |
SRTF preempts A at t=2 because B's remaining (2) < A's remaining (8):
0 2 4 12
├─────┼─────┼─────────────────┤
│ A │ B │ A │
Turnaround: B = 4 - 2 = 2, A = 12 - 0 = 12. Average = 7.
Common Confusion / Misconception
"SJF is optimal, so always use it." SJF is optimal only for minimizing average turnaround on a uniprocessor when bursts are known. In practice bursts are not known; real schedulers must estimate, which leads to the MLFQ idea of "infer short via behavior."
Also: "optimal" does not mean "fair." SJF can starve a long job indefinitely if short jobs keep arriving -- exactly the fairness failure that motivates round-robin and aging.
How To Use It
Proof sketch of SJF optimality (exchange argument). Suppose SJF order is j_1, j_2, ..., j_n sorted by burst b_1 <= b_2 <= ... <= b_n. Total turnaround in this order:
T_SJF = b_1 + (b_1 + b_2) + (b_1 + b_2 + b_3) + ... = sum_i (n - i + 1) * b_i
In any other order, swap two adjacent jobs where b_i > b_{i+1}. Their combined contribution changes from k*b_i + (k-1)*b_{i+1} to k*b_{i+1} + (k-1)*b_i, which decreases the total by (b_i - b_{i+1}). So any non-SJF order can be improved by a swap, which means SJF is optimal.
When asked which policy to pick, use the decision table:
| Goal | Policy |
|---|---|
| Minimize average turnaround, bursts known | SJF |
| Same but with preemption allowed | SRTF |
| Simplicity, predictable ordering | FCFS |
Check Yourself
- Construct a workload where FCFS's average turnaround is twice SJF's.
- Why can SRTF produce a lower average turnaround than SJF on the same inputs?
- Why does SJF fail in real operating systems?
Mini Drill or Application
Workload:
| Job | Arrival | Burst |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
- Draw the Gantt chart for FCFS, SJF (non-preemptive, decide at each completion), and SRTF.
- Compute turnaround and waiting time for each job under each policy.
- Write one sentence explaining why SRTF does not always beat SJF in turnaround sum when ties are broken poorly.