CPU Scheduling Algorithms

What is CPU scheduling?#

There are usually far more ready threads than CPU cores. The scheduler decides which one runs next and for how long. Good scheduling keeps the CPU busy, finishes work quickly and keeps interactive apps responsive.

Key terms#

Scheduling can be non-preemptive (a process runs until it finishes or blocks) or preemptive (the OS can interrupt it, e.g. when its time slice ends).

We'll compare algorithms on the same workload:

First-Come, First-Served (FCFS)#

Run processes in arrival order, each to completion. Simple and fair in order — but short jobs stuck behind long ones wait a long time (the convoy effect).

Gantt: | P1 0–8 | P2 8–12 | P3 12–21 | P4 21–26 |

Shortest Job First (SJF)#

When the CPU is free, pick the ready process with the smallest burst. SJF gives the minimum average waiting time of all non-preemptive algorithms — but it needs to know burst times in advance (real systems estimate them), and long jobs can starve.

Gantt: | P1 0–8 | P2 8–12 | P4 12–17 | P3 17–26 |

At time 8, P2 (4), P3 (9) and P4 (5) are ready, so P2 runs, then P4, then P3. The preemptive version, Shortest Remaining Time First (SRTF), switches whenever a shorter job arrives.

Round Robin (RR)#

Each process gets a fixed time quantum (e.g. 3 units). If it hasn't finished, it goes to the back of the queue. Round Robin is preemptive and great for response time — every process gets the CPU regularly — which is why time-sharing systems are built on it.

• Quantum too large → behaves like FCFS.
• Quantum too small → too much time is wasted on context switches.

Priority scheduling#

Each process has a priority; the highest runs first. Risk: low-priority processes starve. The fix is aging — gradually increasing the priority of processes that have waited a long time.

Simulating the algorithms#

from collections import deque

processes = [  # (name, arrival time, burst time)
    ("P1", 0, 8),
    ("P2", 1, 4),
    ("P3", 2, 9),
    ("P4", 3, 5),
]

def report(algorithm, finish):
    waits, turnarounds = [], []
    for name, arrival, burst in processes:
        turnaround = finish[name] - arrival
        turnarounds.append(turnaround)
        waits.append(turnaround - burst)
    n = len(processes)
    print(f"{algorithm:<16} avg waiting = {sum(waits) / n:5.2f}   avg turnaround = {sum(turnarounds) / n:5.2f}")

def fcfs():
    time, finish = 0, {}
    for name, arrival, burst in sorted(processes, key=lambda p: p[1]):
        time = max(time, arrival) + burst
        finish[name] = time
    return finish

def sjf():
    """Non-preemptive shortest job first."""
    time, finish, pending = 0, {}, list(processes)
    while pending:
        ready = [p for p in pending if p[1] <= time] or [min(pending, key=lambda p: p[1])]
        job = min(ready, key=lambda p: p[2])
        name, arrival, burst = job
        time = max(time, arrival) + burst
        finish[name] = time
        pending.remove(job)
    return finish

def round_robin(quantum):
    time, finish = 0, {}
    remaining = {name: burst for name, _, burst in processes}
    arrivals = deque(sorted(processes, key=lambda p: p[1]))
    queue = deque()
    while arrivals or queue:
        if not queue:
            time = max(time, arrivals[0][1])
        while arrivals and arrivals[0][1] <= time:
            queue.append(arrivals.popleft()[0])
        name = queue.popleft()
        run = min(quantum, remaining[name])
        time += run
        remaining[name] -= run
        while arrivals and arrivals[0][1] <= time:      # new arrivals join before the preempted process
            queue.append(arrivals.popleft()[0])
        if remaining[name]:
            queue.append(name)
        else:
            finish[name] = time
    return finish

report("FCFS", fcfs())
report("SJF", sjf())
report("Round Robin q=3", round_robin(3))

Output:

FCFS             avg waiting =  8.75   avg turnaround = 15.25
SJF              avg waiting =  7.75   avg turnaround = 14.25
Round Robin q=3  avg waiting = 13.50   avg turnaround = 20.00

Round Robin has the worst average waiting time here, yet it's what interactive systems use. Why? Its goal is response time: every process gets its first turn by time 9 (P4 starts after waiting 6 units), instead of P4 waiting 18 units before it runs at all under FCFS. Averages don't tell the whole story — choose the metric that matters for the workload.

Comparison#

What real operating systems use#

• Linux used the Completely Fair Scheduler (CFS), which tracks how much CPU time each task has had and runs the one that's had the least; since kernel 6.6 it uses EEVDF, a refinement that also considers latency.
• Windows and macOS use priority-based, preemptive schedulers with multilevel queues that boost interactive threads.

Containers and Kubernetes add another layer: CPU limits throttle a container when it uses its quota, which can cause latency spikes in busy services.

Common mistakes#

• Mixing up turnaround and waiting time — waiting excludes the process's own burst.
• Forgetting arrival times when drawing Gantt charts.
• Assuming one algorithm is "best" — it depends on whether you optimise throughput, waiting or response time.

Key takeaways#

• Turnaround = completion − arrival; waiting = turnaround − burst.
• FCFS is simple but suffers the convoy effect; SJF minimises average waiting time.
• Round Robin trades turnaround for responsiveness.
• Real schedulers combine priorities, fairness and preemption.