Lesson 3 · Processes, threads, and CPU scheduling

SJF Scheduling: Shortest Job First and SRTF

Run the shortest ready job first. It gives the lowest possible average waiting time, and it cannot be implemented exactly.

What SJF Scheduling Is

SJF scheduling — shortest job first, also called shortest job next — picks the ready process with the smallest next CPU burst and runs it to completion. Everything else about the algorithm follows from that one rule, including both its optimality and the reason it cannot be implemented exactly.

Rule — among all ready processes, run the one with the shortest next CPU burst.
Preemptive? No. Once a process has the CPU it keeps it until the burst ends.
Tie-break — equal bursts fall back to FCFS, so arrival order decides.
Strength — provably the minimum average waiting time of any non-preemptive policy.
Weakness — the next burst length is not known, and long jobs can starve.

Collect the ready processes only jobs that have arrived and are not blocked are candidates.
Compare next CPU bursts not total work, not priority, only the length of the next burst.
Run the shortest to completion non-preemptive SJF never reconsiders mid-burst.
Repeat on the new ready set any job that arrived while the CPU was busy now joins the comparison.
Break ties by arrival two equal bursts are ordered first-come, first-served.

The comparison is on the next burst, not the total service time
Non-preemptive: a shorter arrival waits until the current burst ends
Ties fall back to FCFS ordering
Also written shortest job next, which is the same algorithm

Why SJF Is Provably Optimal

The optimality claim is stronger than it first sounds, and it is worth being able to prove rather than assert. No non-preemptive algorithm can achieve a lower average waiting time than SJF on the same job set.

The argument is an exchange proof. Take any schedule in which a longer job runs immediately before a shorter one, and swap them. The shorter job now finishes earlier by the length of the longer one, while the longer job finishes later by the length of the shorter. Since the shorter length is smaller, the total waiting time strictly decreases. Any schedule that is not in shortest-first order therefore contains such a pair, and swapping it improves the total — so the optimum must already be sorted by burst length.

Two things the proof does not say are where most marks are lost. It says nothing about turnaround being optimal on preemptive systems, and nothing about fairness: the schedule that minimises the average can leave one job waiting arbitrarily long. Optimal on a metric is not the same as good.

Exchange argument: swapping an out-of-order pair always improves the total
The bound is on average waiting time, not on fairness or response
It holds only among non-preemptive schedules
SRTF beats it once preemption is allowed

Implementation

Shortest job first against FCFS

def sjf_schedule(jobs):
    """Non-preemptive SJF. jobs is a list of (name, burst)."""
    order = sorted(jobs, key=lambda job: job[1])
    clock = 0
    waits = {}
    for name, burst in order:
        waits[name] = clock
        clock += burst
    average = sum(waits.values()) / len(waits)
    return order, waits, average


JOBS = [("P1", 6), ("P2", 8), ("P3", 7), ("P4", 3)]

fcfs_clock = 0
fcfs_waits = {}
for name, burst in JOBS:
    fcfs_waits[name] = fcfs_clock
    fcfs_clock += burst
fcfs_average = sum(fcfs_waits.values()) / len(fcfs_waits)

order, waits, average = sjf_schedule(JOBS)

print("FCFS order:", [name for name, _ in JOBS])
print("FCFS waits:", fcfs_waits, "average %.2f" % fcfs_average)
print("SJF  order:", [name for name, _ in order])
print("SJF  waits:", waits, "average %.2f" % average)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Job {
    string name;
    int burst;
};
// Non-preemptive SJF: sort by burst, then run each to completion.
double schedule(vector<Job> jobs, bool shortestFirst) {
    if (shortestFirst) {
        sort(jobs.begin(), jobs.end(),
        [](const Job& a, const Job& b) { return a.burst < b.burst; });
    }
    int clock = 0;
    int total = 0;
    for (const Job& job : jobs) {
        total += clock;
        clock += job.burst;
    }
    return (double)total / jobs.size();
}
int main() {
    vector<Job> jobs = {{"P1", 6}, {"P2", 8}, {"P3", 7}, {"P4", 3}};
    cout << "FCFS average wait " << schedule(jobs, false) << endl;
    cout << "SJF  average wait " << schedule(jobs, true) << endl;
    return 0;
}

import java.util.Arrays;
import java.util.Comparator;
public class SjfScheduling {
    record Job(String name, int burst) {
    }
    // Non-preemptive SJF: sort by burst, then run each to completion.
    static double schedule(Job[] jobs, boolean shortestFirst) {
        Job[] order = jobs.clone();
        if (shortestFirst) {
            Arrays.sort(order, Comparator.comparingInt(Job::burst));
        }
        int clock = 0;
        int total = 0;
        for (Job job : order) {
            total += clock;
            clock += job.burst();
        }
        return (double) total / order.length;
    }
    public static void main(String[] args) {
        Job[] jobs = {new Job("P1", 6), new Job("P2", 8),
        new Job("P3", 7), new Job("P4", 3)};
        System.out.printf("FCFS average wait %.2f%n", schedule(jobs, false));
        System.out.printf("SJF  average wait %.2f%n", schedule(jobs, true));
    }
}

Watch it run

Step through it

Running on P1=6, P2=8, P3=7, P4=3 all at t=0

Output

Preemptive SJF: Shortest Remaining Time First

Preemptive shortest job first — usually called SRTF, shortest remaining time first — applies the same rule but re-decides whenever a process arrives. If the newcomer's burst is shorter than what remains of the running job, the running job is preempted immediately.

That change lowers average waiting time further, because a short job no longer sits behind a long one that happened to start first. The cost is context switches, and a sharper starvation problem: a long job can be preempted repeatedly and make almost no progress while short jobs keep arriving.

The distinction matters in exams because the two produce different Gantt charts on the same input whenever arrival times differ. With all jobs arriving together they are identical — preemption never triggers, because no job arrives to trigger it. That is why worked examples of SRTF always stagger the arrivals.

SJF and SRTF differ only when arrival times differ
	SJF	SRTF
Decision point	When a burst ends	When a burst ends or a job arrives
Preemption	Never	Whenever the arrival is shorter
Average wait	Optimal among non-preemptive	Lower still
Context switches	n − 1	Potentially many more
Same output as the other?	Only when all jobs arrive together	Only when all jobs arrive together

SRTF re-decides on every arrival, SJF only when a burst ends
Identical results when all jobs arrive at once
SRTF lowers average wait at the cost of switching
Starvation is worse under SRTF, not better

The Problem: Burst Length Is Unknown

SJF requires a number the scheduler does not have. The length of a process's next CPU burst is not recorded anywhere — it depends on what the program does next, which is undecidable in general.

τ(n+1) — the predicted length of the next burst.
t(n) — the length of the burst that just finished.
α — the weight on recent history, usually 0.5.
Formula — τ(n+1) = α·t(n) + (1−α)·τ(n).

Real systems therefore estimate it, using an exponential average over observed history. The standard formula is τ(n+1) = α·t(n) + (1−α)·τ(n), where t(n) is the burst just observed and τ(n) was the previous prediction. With α = 0.5 the estimate weights recent behaviour and older history equally, halving the influence of each burst as it recedes.

This is why SJF is rarely deployed as written, and why it matters anyway. It sets the lower bound that every practical scheduler is measured against, and its prediction machinery survives inside multilevel feedback queues, which infer interactivity from observed burst lengths rather than being told.

The next burst length is genuinely unknown, not merely inconvenient
Exponential averaging predicts it from observed history
α = 0.5 halves each older burst's influence
The idea survives in multilevel feedback queues

On Paper: SJF Against FCFS

Four jobs arrive together: P1 with burst 6, P2 with 8, P3 with 7, P4 with 3. This is the standard textbook set, and doing it by hand once is what makes the Gantt chart readable at speed.

Jobs: P1 = 6, P2 = 8, P3 = 7, P4 = 3, all arriving at t = 0
FCFS order: P1, P2, P3, P4
SJF order: P4, P1, P3, P2

FCFS runs them in arrival order — P1, P2, P3, P4 — giving waits of 0, 6, 14 and 21, an average of 10.25. SJF sorts by burst: P4 (3), P1 (6), P3 (7), P2 (8), giving waits of 0, 3, 9 and 16, an average of 7.00.

The difference is entirely in the ordering; the total work is 24 units either way. Note also that P2, the longest job, waited 6 under FCFS but 16 under SJF — the average improved by making the longest job wait longer, which is exactly the fairness cost the optimality proof does not mention.

FCFS average wait 10.25; SJF average wait 7.00
Total work is 24 units under both — only the order changed
The longest job P2 waits 16 under SJF against 6 under FCFS
A 32% cut in average wait, paid for by the longest job

What SJF Scheduling Is

Why SJF Is Provably Optimal

Shortest job first against FCFS

Step through it

Preemptive SJF: Shortest Remaining Time First

The Problem: Burst Length Is Unknown

On Paper: SJF Against FCFS

Continue this course

Introduction to Operating Systems

Types of Operating Systems

Kernel, User Mode, and System Calls