Skip to main content
Be Bitwise

CPU Scheduling Algorithms

Process Management & Scheduling · OS Core Internals track

5 min read

In this module

The Scheduling Problem

When more processes are ready to run than there are CPU cores, the kernel has to pick who runs next. That call is made by the scheduler, and the algorithm it uses has outsized effects on responsiveness, throughput, and fairness.

First-Come, First-Served (FIFO)

The simplest possible approach: processes run in the order they arrive, each running until it finishes or blocks.

The problem is the convoy effect. If a CPU-intensive process arrives first, every shorter process behind it has to wait. Average wait times can be horrible even though the algorithm is trivially fair.

Linux exposes FIFO scheduling via the SCHED_FIFO policy for real-time tasks. A SCHED_FIFO process runs until it voluntarily blocks or yields. There's no time quantum. Only suitable for tasks that demand deterministic latency and know how to cooperate.

Shortest Job First (SJF)

SJF picks the process with the shortest expected execution time. If every burst length is known in advance and the jobs are all waiting at once, it provably minimises average wait time (its preemptive cousin, shortest-remaining-time-first, handles jobs that arrive later). The fatal flaw: the kernel rarely knows how long a process will actually run. In practice, SJF is a theoretical benchmark, not a deployable algorithm.

Round Robin

Round Robin hands each process a fixed time quantum, a slice of CPU time. When the quantum expires, the process is preempted and shoved to the back of the queue.

Key Concept

Round Robin scheduling gives every process equal time slices. Short quanta sharpen responsiveness but pile on context switch overhead. Long quanta drift toward FIFO behaviour and risk the convoy effect. The kernel has to balance these trade-offs.

Linux's SCHED_RR policy is basically FIFO with a quantum attached. Among processes at the same real-time priority, each gets a time slice before yielding to the next.

Completely Fair Scheduler (CFS)

For ordinary (non-real-time) processes, Linux uses the Completely Fair Scheduler. Instead of fixed time slices, CFS tracks a metric called vruntime: the virtual runtime of each process, weighted by its priority (nice value).

The idea is simple. The process with the smallest vruntime has received the least CPU time relative to its fair share, so it should run next. CFS keeps all runnable processes in a red-black tree keyed by vruntime. The leftmost node (smallest vruntime) is always the next to run.

When a process runs, its vruntime ticks up. After enough running, another process naturally becomes the leftmost node and takes over. Higher-priority processes accumulate vruntime more slowly, so they get more CPU time without needing a fundamentally different algorithm.

CFS was the default Linux scheduler from kernel 2.6.23 (2007) until kernel 6.6 (2023), when EEVDF (Earliest Eligible Virtual Deadline First) replaced it. EEVDF tightens up latency fairness while keeping the vruntime concept.

Windows Scheduling

Windows takes a priority-driven approach with 32 priority levels (0-31). The scheduler always runs the highest-priority ready thread. The timer interrupt fires every 15.625 ms (the clock tick interval), and the default thread quantum on Windows client editions is two clock ticks (~31 ms).

To keep things responsive, Windows applies dynamic priority boosting when I/O completes:

  • +1 after completing a disk I/O (IO_DISK_INCREMENT)
  • +6 after completing a keyboard I/O (IO_KEYBOARD_INCREMENT)
  • +8 after completing a sound I/O (IO_SOUND_INCREMENT)

Each boost decays by one level after each quantum, letting interactive processes briefly leapfrog background work.

Try It Yourself

Here's the textbook convoy: P1 needs 24 time units, P2 and P3 need 3 each, and all three arrive at time 0 in that order. Before you reveal anything, work out the average waiting time under FIFO on paper. P1 waits for nobody, P2 waits for P1, P3 waits for both.

Then switch to SJF and predict again, and only then press the button. Round robin comes with a quantum switch: try 1, 4 and 30, and watch the Gantt chart slide from chopped-up fairness to plain FIFO as the slice outgrows every burst.

Non-preemptive. Processes run in arrival order until completion. Simple but can cause the convoy effect.

ProcessArrivalBurst
P1024
P203
P303

Gantt Chart

P1
P2
P3
024681012141618202224262830

Work out the average waiting time from the chart, then check it.

FIFO comes out at (0 + 24 + 27) / 3 = 17. SJF runs the two short jobs first and drops it to (0 + 3 + 6) / 3 = 3, the convoy effect in one number. Round robin with a quantum of 4 lands in between at about 5.7, and nobody waits long for a first turn, which is the property interactive systems care about. A quantum of 1 gives the same average here while switching tasks at every tick. That's free in the simulator, which ignores context-switch cost; on real hardware every one of those switches eats time.

Choosing the Right Algorithm

No single algorithm wins universally. Real-time systems lean on deterministic, analysable policies: fixed priorities assigned by rate-monotonic analysis (run on SCHED_FIFO or SCHED_RR on Linux), or deadline-driven scheduling such as earliest-deadline-first, which Linux offers as SCHED_DEADLINE. Desktop systems demand the interactive responsiveness that CFS and Windows' dynamic boosting deliver. Understanding the trade-offs is what separates knowing what a scheduler does from understanding why it does it.