SJF Scheduling — New Short Jobs Starve Long Builds

SJF is provably optimal for average waiting time among all non-preemptive scheduling algorithms — and SRTF is optimal among all algorithms including preemptive ones. This optimality is not a heuristic or approximation; it follows directly from an exchange argument. If any solution does not follow SJF order, you can swap adjacent jobs to improve average waiting time.

The practical problem: burst times are not known in advance. Linux's CFS (Completely Fair Scheduler) approximates SJF by tracking vruntime — the virtual runtime each process has accumulated — and always scheduling the process with the smallest vruntime. It is SJF-like without requiring burst time prediction, at the cost of true optimality.

Non-Preemptive SJF

When the CPU becomes free, pick the arrived process with the shortest burst time. Once a process starts, it runs to completion. This is provably optimal among non-preemptive algorithms.

Common misconception: 'Shortest' means smallest expected burst, not actual burst. In practice, we use predicted burst times. The algorithm is also called Shortest Process Next (SPN).

import heapq

def sjf_non_preemptive(processes: list[dict]) -> list[dict]:
    procs = sorted(processes, key=lambda p: p['arrival'])
    results = []
    current_time = 0
    heap = []  # (burst, arrival, process)
    i = 0
    while i < len(procs) or heap:
        # Add all processes that have arrived
        while i < len(procs) and procs[i]['arrival'] <= current_time:
            heapq.heappush(heap, (procs[i]['burst'], procs[i]['arrival'], procs[i]))
            i += 1
        if not heap:
            current_time = procs[i]['arrival']
            continue
        burst, arrival, p = heapq.heappop(heap)
        start = current_time
        ct  = start + p['burst']
        tat = ct - p['arrival']
        wt  = tat - p['burst']
        current_time = ct
        results.append({**p, 'start': start, 'ct': ct, 'tat': tat, 'wt': wt})
    return results

processes = [
    {'pid':'P1','arrival':0,'burst':8},
    {'pid':'P2','arrival':1,'burst':4},
    {'pid':'P3','arrival':2,'burst':2},
    {'pid':'P4','arrival':3,'burst':1},
]
results = sjf_non_preemptive(processes)
for r in results:
    print(f"{r['pid']}: WT={r['wt']}, TAT={r['tat']}")
print(f"Avg WT: {sum(r['wt'] for r in results)/len(results):.2f}")

Preemptive SJF — SRTF

Shortest Remaining Time First preempts the running process when a new process arrives with shorter remaining time. It is SJF applied continuously — at every arrival, the scheduler re-evaluates and picks the process with smallest remaining burst.

SRTF achieves the absolute minimum average waiting time among all scheduling algorithms, but at a cost: frequent preemptions can increase context switch overhead, and tracking remaining times adds complexity.

def srtf(processes: list[dict]) -> list[dict]:
    """Shortest Remaining Time First — preemptive SJF."""
    procs = [dict(p, remaining=p['burst'], start=-1) for p in processes]
    procs.sort(key=lambda p: p['arrival'])
    n = len(procs)
    time = 0
    completed = 0
    current = None
    results = {}
    while completed < n:
        # Find process with shortest remaining time among arrived
        arrived = [p for p in procs if p['arrival'] <= time and p['remaining'] > 0]
        if not arrived:
            time += 1
            continue
        current = min(arrived, key=lambda p: p['remaining'])
        if current['start'] == -1:
            current['start'] = time
        current['remaining'] -= 1
        time += 1
        if current['remaining'] == 0:
            ct  = time
            tat = ct - current['arrival']
            wt  = tat - current['burst']
            results[current['pid']] = {**current,'ct':ct,'tat':tat,'wt':wt}
            completed += 1
    return list(results.values())

results = srtf(processes)
for r in results:
    print(f"{r['pid']}: WT={r['wt']}, TAT={r['tat']}")
print(f"Avg WT: {sum(r['wt'] for r in results)/len(results):.2f}")

Why SJF is Optimal

SJF minimises average waiting time among all non-preemptive algorithms. Proof by exchange argument: if a longer job runs before a shorter one, swapping them reduces total waiting time. SRTF minimises average waiting time among ALL scheduling algorithms (preemptive and non-preemptive).

The exchange argument is simple: consider two adjacent jobs in a schedule. If a longer job precedes a shorter one, you can swap them and reduce the waiting time of the shorter job by the full length of the longer job, while the longer job waits only the short job's burst. The reduction is always positive.

Starvation and Aging

Starvation occurs when a long process never gets CPU because shorter processes keep arriving. Aging is the standard solution: increase the priority of a process the longer it waits. Priority can be based on waiting time (e.g., priority = base_priority + waiting_time / quantum). Once priority surpasses current running process, the scheduler may preempt.

Aging transforms SJF into a priority-based scheduler with time-dependent boosting. It guarantees every process eventually makes progress, at the cost of slightly increased average waiting time for short processes.

Burst Time Prediction

Real schedulers don't know burst times in advance. Prediction via exponential averaging: τ_{n+1} = α × t_n + (1-α) × τ_n where t_n is actual burst time, τ_n is predicted, α controls responsiveness (typically 0.5).

α close to 1 makes the predictor react quickly to changes but noisy. α close to 0 produces stable predictions but slow to adapt. In Linux's CFS, vruntime replaces burst prediction entirely – the scheduler uses actual CPU usage history instead of predicting future bursts.

Frequently Asked Questions