Shortest-Job-First Scheduling

Shortest-Job-First (SJF) scheduling selects, from the set of processes ready to run, the one with the smallest CPU burst time — the length of its next uninterrupted stretch of CPU use. In the non-preemptive form, once a process starts running it continues until it either finishes or voluntarily blocks (e.g., for I/O); the scheduler only chooses among waiting jobs at those decision points. In the preemptive form, called Shortest-Remaining-Time-First (SRTF), the scheduler re-evaluates every time a new process arrives: if the newcomer's total burst is shorter than the remaining burst of the currently running process, the running process is preempted immediately. The key performance metric SJF targets is average waiting time, $\bar{W} = \frac{1}{n}\sum_i W_i$, where $W_i$ is the time process $i$ spends ready but not running (see Scheduling Performance Metrics). SJF's central theoretical result is that among all non-preemptive scheduling disciplines applied to a fixed, known set of burst times all available at time zero, ordering by ascending burst time minimizes $\bar{W}$. SRTF extends this to dynamic arrivals: at every instant, running whichever ready process has the least remaining work minimizes cumulative waiting time, again assuming perfect knowledge of future bursts. The catch, which the rest of this article treats seriously rather than glossing over, is that no scheduler can observe a process's future CPU burst directly — it must be predicted from the process's own history, typically via an exponentially weighted moving average. And because short jobs are always preferred, a steady stream of newly arriving short jobs can delay a long job forever: this is starvation, the price SJF pays for its optimality.

Non-preemptive SJF. At every scheduling decision point (CPU becomes idle, or the running process finishes/blocks), scan the ready queue and dispatch the process with the smallest burst time. Ties are broken by arrival order (FCFS) or process ID, by convention.

SRTF. Maintain, for the running process, its remaining burst time, decremented as it executes. On every arrival event, compare the new process's total burst against the running process's remaining burst; if the new one is strictly smaller, preempt. On every completion event, pick the minimum-remaining-burst process from the ready queue. The efficient implementation uses a min-heap (priority queue) keyed on (remaining) burst time, so that "find the smallest" is $O(\log n)$ rather than a linear scan. ``` // SRTF scheduler using an event-driven simulation with a min-heap // ready_heap: min-heap of (remaining_burst, arrival_time, pid) // events: arrivals sorted by arrival_time function SRTF_schedule(processes): sort processes by arrival_time ready_heap = empty min-heap current = NONE // currently running process time = 0 completed = [] i = 0 // index into arrival-sorted processes n = len(processes) while len(completed) < n: // 1. Admit all processes that have arrived by 'time' while i < n and processes[i].arrival_time <= time: push(ready_heap, processes[i]) i += 1 // 2. If nothing to run, jump to next arrival (idle CPU) if current == NONE and ready_heap is empty: time = processes[i].arrival_time continue // 3. Choose the process with smallest remaining burst candidate = peek_min(ready_heap) if current == NONE or candidate.remaining < current.remaining: if current != NONE: push(ready_heap, current) // preempt: requeue current = pop_min(ready_heap) // may equal candidate // else current keeps running // 4. Advance time by 1 unit (or until next event, for efficiency) next_event_time = min(next_arrival_time(i, processes), time + current.remaining) run_for = next_event_time - time current.remaining -= run_for time = next_event_time // 5. Handle completion if current.remaining == 0: current.completion_time = time completed.append(current) current = NONE return completed ```

Correctness of the event-driven step: instead of simulating one time unit at a time — which is correct but slow — the loop advances directly to the next meaningful event: either the next arrival or the current process's completion, whichever comes first. No preemption decision can occur strictly between these two events, because the ready-process set and the running process's remaining time only change at those moments. This turns an $O(T)$ simulation (where $T$ is total time) into an $O(n)$-event simulation.

Time complexity. With a min-heap of size at most $n$, each arrival is one $O(\log n)$ insertion and each preemption/dispatch decision is one $O(\log n)$ extract-min, giving $O(n \log n)$ total for $n$ processes across the whole schedule — because there are at most $O(n)$ arrival and completion events. Non-preemptive SJF over a static batch is simply sorting: $O(n \log n)$, dominated by the sort itself (or $O(n)$ if bursts are already sorted or bucketed).

Space complexity is $O(n)$ for the ready-queue heap and per-process bookkeeping.

Correctness (optimality of non-preemptive SJF, static case). Claim: if all $n$ processes are available at time 0 with known burst times $b_1, \dots, b_n$, then running them in non-decreasing order of $b_i$ minimizes $\bar W$. Proof (exchange argument). Fix any schedule that is not sorted by burst time. Then there exist two adjacent jobs $A$ (scheduled before $B$) with $b_A > b_B$. Swapping their order changes only their own waiting times (every other job's waiting time is unaffected, since the total time consumed before and after this pair is unchanged). Before the swap, $A$ waits $W$ and $B$ waits $W + b_A$ (where $W$ is the time already elapsed before this pair starts). After swapping, $B$ waits $W$ and $A$ waits $W + b_B$. The change in total waiting time is:

So the swap strictly decreases total waiting time whenever $b_A > b_B$. Any non-sorted schedule therefore admits an improving swap, so it cannot be optimal; repeating swaps (a bubble-sort argument) drives any schedule toward the sorted order, and since total waiting time strictly decreases with each improving swap and is bounded below, the process terminates at the sorted schedule. Hence sorted-by-burst is optimal, and it is unique up to ties. $\blacksquare$

Correctness (optimality of SRTF, dynamic arrivals). The same exchange idea extends via an interval-exchange argument: at any instant where a shorter job is ready but a longer one is running, deferring the short job's start only postpones its own completion without shortening anyone else's wait, while running it first cannot lengthen any other job's wait by more than it shortens the short job's own — a formal proof uses an inductive exchange over completion order, showing any schedule can be transformed into the SRTF schedule without increasing total waiting time. The result: SRTF minimizes $\bar W$ among all schedules (preemptive or not) given perfect knowledge of burst times, at every arrival pattern.

The honest tradeoff. This optimality is conditional on knowing the future. Real schedulers only have an estimate $\tau_i$ of the next burst, not the true value $t_i$. If estimates are poor, SJF-by-estimate can perform arbitrarily worse than true SJF, and worse than simpler policies in pathological cases. Moreover, SJF/SRTF ignores fairness entirely — it optimizes a system-wide average at the expense of individual long jobs, a tradeoff made explicit below.

Consider four processes, non-preemptive SJF is inapplicable here because arrival times differ, so we trace SRTF:

Trace:

Completion times: P2 = 5, P4 = 10, P1 = 17, P3 = 26. Turnaround time $= \text{completion} - \text{arrival}$; waiting time $= \text{turnaround} - \text{burst}$.

Compare to FCFS on the same input (order P1, P2, P3, P4, run to completion in arrival order): P1 waits 0, P2 waits 7 (8−1), P3 waits 10 (12−2), P4 waits 16 (17−3), giving $\bar W_{FCFS} = 33/4 = 8.25$. SRTF's 6.5 is strictly lower, illustrating (not proving, since this is one instance) the general optimality result. Notice also that P3 — the longest job — accumulates the largest wait (15), a preview of the starvation problem discussed next.

Burst-time prediction. Since true bursts are unknown, systems estimate the next CPU burst $\tau_{n+1}$ from the actual duration of the most recent burst $t_n$ and the previous estimate $\tau_n$, using exponential averaging:

Expanding recursively,

so each historical burst contributes with geometrically decaying weight — recent bursts matter more, and the influence of the ancient past (and the arbitrary initial guess $\tau_0$) vanishes as $(1-\alpha)^{n+1} \to 0$. Setting $\alpha = 0.5$ weighs recent and historical bursts equally per step; $\alpha \to 1$ makes the estimator track only the last observed burst (fast-adapting, noisy); $\alpha \to 0$ makes it ignore recent history (stable, slow to adapt). This estimator, not the true burst time, is what a real "SJF" scheduler actually sorts by — making it heuristic, not literally optimal.

Pure SJF/SRTF is almost never deployed as-is in general-purpose operating systems, precisely because burst times are unknown and starvation is unacceptable for interactive workloads. But its optimality result is the theoretical anchor for an entire family of practical schedulers. Batch-processing systems (e.g., HPC job schedulers like Slurm) approximate SJF using user-supplied or historically estimated job-length hints to minimize mean queue delay, often with anti-starvation caps. Multilevel feedback queue schedulers, the ancestor of both Windows and traditional Unix schedulers, use observed CPU-burst behavior to demote CPU-bound processes and promote I/O-bound ones — effectively estimating "shortness" from recent behavior, exactly as the exponential-averaging predictor does. Network packet scheduling and disk I/O schedulers borrow the shortest-job intuition in disciplines like Shortest-Seek-Time-First. Understanding SJF is also the necessary stepping stone to Priority Scheduling, which generalizes "run the smallest burst" to "run the highest priority" (of which burst-time-based priority is one instance), and to Round-Robin Scheduling, which explicitly sacrifices SJF's optimal average waiting time to guarantee bounded response time and eliminate starvation.

Ask the tutor: How would the SRTF optimality proof change if context-switch overhead were charged for every preemption?