SJF
Shortest job first. Optimal average waiting time if you magically know run times.
Level: intermediate
What is it?
Shortest Job First (SJF) chooses the ready process with the smallest next CPU burst. The classic non-preemptive form lets that process run until it blocks or completes. The preemptive variant is shortest remaining time first (SRTF), which may interrupt a running job when a shorter remaining job arrives.
Why does it matter?
With known burst lengths and all jobs available together, SJF minimizes average waiting time. Real systems rarely know a job's next burst exactly, and repeatedly favoring short jobs can starve long jobs under an endless stream of arrivals.
Mental model
At a queue of tasks, serve the shortest task first to reduce the time others spend waiting behind long work. The policy is mathematically attractive when the size estimates are accurate.
How it works
- Non-preemptive SJF compares the next burst of ready jobs only when the CPU becomes available.
- SRTF compares remaining CPU time and may preempt the current job.
- Average waiting time can improve greatly when a long burst otherwise blocks many short bursts.
- Operating systems estimate bursts using history or use other policies because exact future runtimes are unknown.
- Starvation risk grows when short jobs continue to arrive before long jobs can be selected.
Steps
- Three jobs arrive at time zero with bursts A=6, B=2, C=1.
- SJF order is C (0–1), B (1–3), A (3–9).
- Waiting times are C=0, B=1, A=3; average waiting time is 4/3.
- Under SRTF, recalculate the remaining time at each arrival because the order can change.
Real-world usage
- Comparing policies using average waiting and turnaround time.
- Understanding burst prediction and short-job bias.
- Explaining the distinction between SJF and SRTF.
Common mistakes
- Saying SJF is always best for every objective; it optimizes average waiting under specific assumptions.
- Confusing a new burst length with remaining execution time in SRTF.
- Ignoring arrival times or starvation when interpreting a scheduling example.
Interview questions
Under what assumptions does SJF minimize average waiting time?
For a set of jobs available together with known CPU burst lengths, the non-preemptive SJF ordering minimizes average waiting time.
How does SRTF differ from SJF?
SRTF is preemptive: a new arrival with a shorter remaining burst can preempt the currently running job.