Chapter 4: CPU Scheduling Algorithms

Why this matters

There are almost always more runnable processes/threads than CPU cores available to run them, which means the OS constantly has to decide who runs next and for how long. That decision — the scheduling algorithm — directly determines whether your system feels responsive under load or whether important work waits behind unimportant work. Understanding the trade-offs between scheduling approaches explains real, observable behavior: why a batch job can make an interactive service feel sluggish, and what "nice" values and thread priorities actually do.

The core concept

[BEGINNER] A CPU scheduler decides which ready process/thread gets the CPU next, and for how long, whenever the CPU becomes free (a process finishes, blocks on I/O, or its time slice expires). Every scheduling algorithm makes a trade-off between competing goals: throughput (total work completed per unit time), latency/response time (how quickly a given task gets some CPU time), fairness (no task starves indefinitely), and overhead (the cost of the scheduling decision itself).

The classic algorithms

First-Come, First-Served (FCFS)

• Processes run in the order they arrive, to completion, with no preemption.
• Trade-off: simple, but a single long-running process can block everything behind it — the "convoy effect."

Arrival order: P1 (needs 20ms), P2 (needs 2ms), P3 (needs 2ms)
Timeline: [------- P1 (20ms) -------][P2 (2ms)][P3 (2ms)]
P2 and P3 wait 20ms each for a tiny amount of their own work — poor average wait time.

Round Robin

• Each process gets a fixed time slice ("quantum"); if it doesn't finish, it goes to the back of the queue.
• Trade-off: much better responsiveness (no process waits long for some CPU time) but more context-switch overhead, and the quantum size matters enormously — too short wastes time switching, too long degrades toward FCFS.

Quantum = 4ms. P1 (needs 10ms), P2 (needs 4ms), P3 (needs 4ms)
Timeline: [P1: 4ms][P2: 4ms][P3: 4ms][P1: 4ms][P1: 2ms]
Every process gets attention quickly, at the cost of more context switches than FCFS.

Priority Scheduling

• Each process has a priority; the highest-priority ready process runs first.
• Trade-off: lets important work go first, but risks starvation — a low-priority process can wait indefinitely if higher-priority work keeps arriving. The standard fix is aging: gradually increasing a waiting process's priority the longer it waits, guaranteeing it eventually runs.

Multilevel Feedback Queue (MLFQ)

• Multiple priority queues, each with progressively longer time quanta; a process that uses its entire quantum without blocking (suggesting it's CPU-bound, not interactive) gets demoted to a lower-priority queue with a longer quantum; a process that blocks quickly (suggesting it's interactive, doing lots of I/O) stays at higher priority.
• Trade-off: this is the approach most general-purpose OS schedulers (including Linux's, in spirit) actually approximate, because it adapts automatically — it doesn't need to know in advance whether a process is interactive or CPU-bound, it infers it from observed behavior.

+----------------+  Quantum 8ms   (new/interactive processes start here)
|   Queue 0      |  ---> uses full quantum without blocking? demote.
+----------------+
        | demoted
        v
+----------------+  Quantum 16ms
|   Queue 1      |  ---> uses full quantum without blocking? demote further.
+----------------+
        | demoted
        v
+----------------+  Quantum 32ms  (CPU-bound batch work settles here)
|   Queue 2      |
+----------------+

[IN PRACTICE] This is exactly why an interactive process (a text editor waiting on your keystrokes, blocking on I/O constantly) stays snappy even while a CPU-bound batch job (video encoding, a data processing script) runs in the background — the interactive process keeps getting bumped back to a high-priority, short-quantum queue because it keeps voluntarily blocking before its quantum expires, while the batch job sinks to a low-priority, long-quantum queue because it never blocks early.

Linux's actual scheduler, briefly

[SENIOR INSIGHT] Modern Linux uses the Completely Fair Scheduler (CFS) (or, in recent kernels, EEVDF as its successor) rather than a literal multilevel feedback queue — but it's solving the same underlying problem with a different mechanism: CFS tracks each task's accumulated "virtual runtime" (CPU time received, weighted by priority/nice value) and always picks the task with the least virtual runtime to run next, keeping every task's actual CPU time proportionally fair over time. The nice value (from -20, highest priority, to 19, lowest) adjusts how fast a task's virtual runtime accumulates — a "nicer" (higher nice value) task's virtual runtime grows faster, so it gets picked less often, without ever being fully starved.

$ nice -n 10 ./batch_job.sh     # lower priority — won't starve interactive work
$ renice -n -5 -p 4821          # raise priority of an already-running process

When each approach conceptually fits: FCFS-like behavior is fine for simple batch systems with no interactivity concerns; Round Robin fits time-sharing systems needing baseline fairness; Priority + aging fits systems with genuine, known task-importance differences; MLFQ/CFS-style adaptive scheduling fits general-purpose systems mixing interactive and batch work without knowing in advance which is which — which is why it's the real-world default in Linux, Windows, and macOS.

Common mistakes

1. Assuming a "priority" setting guarantees immediate execution rather than just favoring it probabilistically/proportionally — most real schedulers (CFS especially) use priority as a weighting factor over time, not an absolute override, specifically to avoid starving lower-priority work entirely.
2. Setting an extremely large Round Robin quantum "to reduce overhead" without recognizing this degrades responsiveness toward FCFS-like behavior — the quantum size is a direct trade-off between overhead and responsiveness, not a free efficiency gain.
3. Not considering that a batch job competing with latency-sensitive services on the same machine can degrade the latency-sensitive service's responsiveness, even without exhausting total CPU capacity, especially under a scheduler not well-tuned for the mix (this is a large part of why dedicated resources/nice values/cgroup CPU shares matter in shared production environments).
4. Assuming starvation is a purely theoretical concern. Priority scheduling without aging is a real, demonstrable risk in systems with a steady stream of high-priority work — it's not just a textbook edge case.

Checklist: reasoning about scheduling in practice

1. When diagnosing unexplained latency on a shared machine, check what else is running and at what priority (top, ps -eo pid,ni,pri,cmd) — competing CPU-bound work is a common, invisible-from-the-application-layer cause.
2. Use nice/renice deliberately for genuinely low-priority batch work sharing a machine with latency-sensitive services, rather than leaving all processes at default priority.
3. Remember priority is typically a weighting, not an absolute guarantee, when reasoning about whether a high-priority task could still be delayed by lower-priority work.
4. In containerized/cloud environments, understand that CPU limits (cgroups) interact with scheduling — a container "throttled" at its CPU limit will show scheduling-like symptoms (processes ready but not running) even with no other competing load, an important production debugging pattern (Chapter 11 covers virtualization/containers in depth).

Discussion / interview questions

1. "Compare First-Come-First-Served and Round Robin scheduling — what problem does Round Robin solve, and at what cost?" Strong answer: FCFS suffers the "convoy effect" — a long process blocks short ones behind it, hurting average wait time; Round Robin bounds how long any process waits for some CPU time by using fixed time slices, at the cost of more context-switch overhead, especially with a poorly-chosen quantum size.

2. "What is a Multilevel Feedback Queue, and why is it well-suited to general-purpose operating systems?" Strong answer: Multiple queues with increasing quantum sizes; processes that use their full quantum (CPU-bound) get demoted to lower-priority, longer-quantum queues, while processes that block early (interactive) stay at high priority — it adapts automatically to a process's actual behavior without needing to know in advance whether it's interactive or batch.

3. "What is starvation in the context of scheduling, and how is it typically prevented?" Strong answer: A process waiting indefinitely because higher-priority work keeps arriving ahead of it; typically prevented via aging — gradually increasing a waiting process's effective priority the longer it waits, guaranteeing it eventually gets scheduled.

4. "How does Linux's Completely Fair Scheduler decide what runs next, at a conceptual level?" Strong answer: Tracks each task's accumulated virtual runtime (CPU time received, weighted by nice value/priority) and picks the task with the least virtual runtime next, keeping CPU time allocation proportionally fair over time rather than using fixed queues or absolute priority levels.

Chapter summary / cheat sheet

• Scheduling trades off throughput, latency/responsiveness, fairness, and overhead — no algorithm optimizes all four simultaneously.
• FCFS: simple, but suffers the convoy effect. Round Robin: bounded wait via time slices, at the cost of context-switch overhead. Priority: favors important work, but risks starvation without aging. MLFQ: adapts automatically to interactive vs. CPU-bound behavior — closest in spirit to what real general-purpose OS schedulers do.
• Linux's CFS/EEVDF tracks virtual runtime and always favors the task that's received proportionally the least CPU time so far, weighted by nice value.
• Priority is usually a weighting factor over time, not an absolute guarantee of immediate execution — a common point of confusion worth correcting explicitly.
• In shared/containerized environments, competing scheduled work (and cgroup CPU throttling) is a common, often invisible cause of latency that looks like an application problem.

---