SJF Scheduling — Step-Wise Animated Numericals

The Story That Explains SJF

Galvin proves that SJF gives the provably minimum average waiting time for any set of processes — no other algorithm can do better. This makes SJF the theoretical gold standard against which every other scheduler is measured.

The Two Flavours of SJF

SJF Algorithm — Six Steps

The Metrics — Same As FCFS

Numerical 1 — Basic SJF (All Arrive at t=0)

Problem: Four processes arrive at time 0. Compute all metrics under non-preemptive SJF.

Sort By Burst Time First

Animated Step-Wise Gantt Chart

Solution Table

Numerical 2 — Non-Preemptive SJF With Different Arrivals

Problem: Processes arrive at different times. Apply non-preemptive SJF.

Step-by-Step Timeline

Animated Gantt Chart

Numerical 3 — Preemptive SJF (SRTF)

Same data as Numerical 2, but now the scheduler is Shortest Remaining Time First (SRTF). Every arrival is a scheduling event.

Second-By-Second Reasoning

Numerical 3B — Preemption That Actually Fires

Animated Preemptive SJF Gantt

SRTF Solution Table

Numerical 4 — Starvation Demonstration

SJF's dark side: if short jobs keep arriving, long jobs may never run. This is called starvation.

Predicting the Next CPU Burst

Since we can't know a process's burst time in advance, we estimate it from the process's past bursts using an exponential-averaging formula.

# Simple exponential burst predictor
class BurstPredictor:
    def __init__(self, alpha=0.5, initial_guess=10):
        self.alpha = alpha
        self.tau   = initial_guess

    def predict(self) -> float:
        return self.tau

    def update(self, actual_burst: float) -> None:
        self.tau = self.alpha * actual_burst + (1 - self.alpha) * self.tau

# Example run
p = BurstPredictor(alpha=0.5, initial_guess=10)
history = [6, 4, 6, 4, 13, 13, 13]
for b in history:
    print(f"predicted={p.predict():5.2f}   actual={b}")
    p.update(b)

Full Python Implementation

from dataclasses import dataclass
from typing import List

@dataclass
class Process:
    pid:        str
    arrival:    int
    burst:      int
    remaining:  int = 0
    start:      int = -1
    completion: int = -1

# --- NON-PREEMPTIVE SJF -------------------------------------
def sjf(procs: List[Process]) -> List[Process]:
    procs    = [Process(p.pid, p.arrival, p.burst) for p in procs]
    finished = []
    clock    = 0
    while procs:
        ready = [p for p in procs if p.arrival <= clock]
        if not ready:
            clock = min(p.arrival for p in procs)
            continue
        # Pick shortest burst, break tie by arrival
        next_p = min(ready, key=lambda p: (p.burst, p.arrival))
        next_p.start      = clock
        next_p.completion = clock + next_p.burst
        clock             = next_p.completion
        procs.remove(next_p)
        finished.append(next_p)
    return finished

# --- PREEMPTIVE SJF (SRTF) ----------------------------------
def srtf(procs: List[Process]) -> List[Process]:
    procs = [Process(p.pid, p.arrival, p.burst, remaining=p.burst)
             for p in procs]
    total_burst = sum(p.burst for p in procs)
    clock = 0
    while any(p.remaining > 0 for p in procs):
        ready = [p for p in procs
                 if p.arrival <= clock and p.remaining > 0]
        if not ready:
            clock += 1
            continue
        current = min(ready, key=lambda p: p.remaining)
        if current.start == -1:
            current.start = clock
        current.remaining -= 1
        clock += 1
        if current.remaining == 0:
            current.completion = clock
    return procs

def report(name, procs):
    print(f"\n=== {name} ===")
    tat = wt = 0
    for p in procs:
        t = p.completion - p.arrival
        w = t - p.burst
        tat += t; wt += w
        print(f"{p.pid} start={p.start:2}  CT={p.completion:2}  TAT={t:2}  WT={w:2}")
    n = len(procs)
    print(f"Avg TAT={tat/n:.2f}  Avg WT={wt/n:.2f}")

# --- Run both on the SRTF numerical -------------------------
workload = [
    Process("P1", 0, 8),
    Process("P2", 1, 4),
    Process("P3", 2, 9),
    Process("P4", 3, 5),
]
report("Non-Preemptive SJF", sjf(workload))
report("Preemptive SJF (SRTF)", srtf(workload))

SJF vs FCFS Side-By-Side

Advantages & Disadvantages

Golden Rules