Shortest Job First (SJF) Scheduling

Prioritizing the Shortest Job, Not the Earliest Arrival

Shortest Job First (SJF) picks, among all currently waiting processes, whichever one needs the least total CPU time - directly targeting the convoy effect that FCFS (covered in the previous note) suffers from.

The Same Processes, Scheduled with SJF Instead

Process   Arrival Time   Burst Time
P1        0              8
P2        1              4
P3        2              9

Execution order (SJF, assuming all have arrived): P2 -> P1 -> P3

Timeline:
|-- P2 (0-4) --|---- P1 (4-12) ----|------ P3 (12-21) ------|

Notice P2, the shortest job, now runs first - dramatically reducing its own waiting time compared to FCFS, even though P1 arrived earlier.

Why SJF Produces the Lowest Possible Average Waiting Time

Among all possible non-preemptive scheduling orders, SJF is mathematically proven to produce the lowest average waiting time - a genuinely strong theoretical guarantee, which is exactly why it's used as a benchmark other algorithms are often compared against.

The Practical Catch: You Rarely Know Burst Time in Advance

SJF requires knowing each process's exact CPU burst time before scheduling it - information that's rarely known with certainty in a real, general-purpose system. In practice, systems must estimate future burst times based on a process's past behavior, and an inaccurate estimate can significantly undermine SJF's theoretical advantage.

A Real Risk: Starvation of Long Processes

If short processes keep arriving continuously, a long process can be repeatedly pushed back and effectively starved from ever getting the CPU - a genuine fairness problem that pure SJF does not solve on its own (aging, covered later in this section, is one common fix for exactly this issue).

Preemptive SJF: Shortest Remaining Time First

A preemptive variant of SJF can interrupt a currently running process if a newly arrived process has an even shorter remaining burst time - trading additional context-switch overhead (covered earlier in this section) for potentially even better average waiting time.