Process Scheduling

When multiple processes compete for CPU time, the OS's scheduler decides which runs when. First-Come-First-Served (FCFS) is the simplest possible policy: run processes in arrival order, no interruptions.

def fcfs_completion_times(burst_times):
    completion = []
    total = 0
    for bt in burst_times:
        total += bt
        completion.append(total)
    return completion

print(fcfs_completion_times([5, 3, 8]))   # [5, 8, 16]

Simple, but has a real problem: a long process arriving first makes every SHORT process behind it wait unnecessarily — the "convoy effect."

Shortest-Job-First (SJF) fixes the convoy effect by always running the SHORTEST remaining job next — provably minimizes average waiting time across all processes:

def sjf_order(burst_times):
    return sorted(range(len(burst_times)), key=lambda i: burst_times[i])

print(sjf_order([10, 1, 1, 1]))   # [1, 2, 3, 0] -- short jobs first, long job last

The catch: SJF requires KNOWING each job's burst time in advance (rarely true in practice — you don't know how long a process will run until it finishes), and it can starve long jobs — if short jobs keep arriving, a long job might wait indefinitely, always getting bumped by whatever's shortest right now. Real OS schedulers use more sophisticated policies (like Round Robin with time slices, or priority-aging) that balance fairness against SJF's efficiency.