CPU Scheduling II — Real Schedulers

The classic algorithms from Chapter 11 were each a lesson in one trade-off. Round-robin taught responsiveness through preemption; SJF taught that running short jobs first minimises average waiting time; priority scheduling taught that not all work is equally urgent. A real kernel does not get to pick one lesson. It has to honour all of them at once, for a workload it has never seen before and cannot predict, while spending as little time as possible actually deciding — because every microsecond the scheduler spends choosing is a microsecond no useful work runs.

Look at what a single laptop is juggling right now. An interactive process — your terminal, your editor — spends most of its life blocked, waiting for a keystroke, and needs the CPU for a tiny burst the instant input arrives; if it waits even 100 ms the machine feels sluggish. A batch process — a compile, a video encode, a backup — never blocks for input and simply wants as many CPU cycles as it can get; it does not care about a few milliseconds of delay. These two want opposite things from the scheduler, and both are running.

Interactivity

Low response time for jobs that block often and run in short bursts — the feel of a snappy machine.

Throughput

Total useful work completed per unit time; what CPU-bound batch jobs care about.

Fairness

No runnable job is starved; over time each gets a defensible share of the CPU.

Overhead

Time the scheduler itself burns deciding and switching — pure tax on the workload, so the algorithm must be cheap.

The insight that unlocks everything here is that a job tells you what it is by how it behaves. A process that keeps blocking for I/O is interactive and should be favoured for responsiveness; a process that burns its whole time slice every time is CPU-bound and can afford to wait. The scheduler cannot know a job’s future burst length — but it can watch the recent past and react. That single move, letting observed behaviour drive the decision, is what turns the toy algorithms of Chapter 11 into the schedulers that run the world.

The first step away from a single ready queue is to notice that jobs come in distinct classes that genuinely deserve different treatment. Kernel and system daemons must respond instantly; interactive user programs need to feel snappy; batch jobs just need to finish. Multilevel queue scheduling makes that explicit: it splits the one ready queue into several separate queues, one per class, and gives each queue its own scheduling policy.

A classic arrangement has a high-priority system queue, an interactive queue below it, and a batch queue at the bottom. The interactive queues typically run round-robin so no one job hogs the CPU and response time stays low; the batch queue can run FCFS, since throughput matters more than responsiveness there. Crucially, the queues themselves are ranked: the scheduler runs a job from a lower queue only when every higher queue is empty. Sometimes that strict ordering is softened into a fixed CPU split — say 80% of cycles to interactive, 20% to batch — so the bottom is not entirely starved.

• ▸The ready queue is partitioned into several fixed queues, one per class of job.
• ▸Each queue has its own policy — round-robin for interactive, FCFS for batch, and so on.
• ▸Queues are prioritised: a job runs only if all higher-priority queues are empty (or via a fixed percentage split between them).
• ▸Assignment is permanent: a process is placed into one queue by its type and stays there for its whole life.

The defining limitation is right there in that last point: assignment is fixed. A process is slotted into a queue when it is created — by its type, priority, or class — and it never moves. That is simple and predictable, but it is also rigid and unfair. If an interactive program enters a CPU-heavy phase it stays in the responsive queue it no longer deserves; if a batch job suddenly turns interactive it is stuck at the bottom. And if the higher queues stay busy, the lower ones can starve indefinitely. The fix for all of this is to let jobs move — which is exactly the next idea.

Multilevel queue

Several separate ready queues, one per job class, each with its own scheduling policy.

Fixed assignment

A process is placed in one queue at creation and never changes queue — the key weakness.

Inter-queue scheduling

How the CPU is shared between queues: strict priority (drain top-down) or a fixed percentage split.

The multilevel feedback queue keeps the layered queues of the previous idea but adds the word that changes everything: feedback. Jobs are no longer nailed to one queue — they move up and down based on how they behave. That single change lets one algorithm approximate shortest-job-first without ever being told a burst length, and it is the conceptual heart of every general-purpose scheduler built for the last forty years.

Picture a ladder of queues. The top queue has the highest priority but a short time slice; each queue further down has lower priority but a longer slice. The scheduler always runs jobs from the highest non-empty queue, round-robin within that queue. A brand-new process starts at the very top, given the benefit of the doubt that it might be interactive. What happens next depends entirely on how it uses the CPU.

Here is the rule that does the magic. If a job uses up its entire time slice without blocking, it is behaving like a CPU hog, so it is demoted one level — dropped to a lower-priority queue with a longer slice. If instead a job gives up the CPU before its slice ends — because it blocked for I/O, the signature of an interactive job — it stays at its high priority. Run this for a few milliseconds and the queues sort themselves: short, interactive, I/O-bound jobs float near the top and get scheduled quickly, while long CPU-bound jobs sink to the bottom and run in long, efficient slices when nothing above them needs the CPU. That is SJF-like behaviour, learned purely from observation.

• ▸A new job enters at the top (highest-priority) queue.
• ▸Uses its whole time slice → it is CPU-bound → demote it one queue (lower priority, longer slice).
• ▸Yields before the slice ends (blocks for I/O) → it is interactive → keep it at its current priority.
• ▸The scheduler always serves the highest non-empty queue, round-robin within each queue.

But there is a poison in this design, and good MLFQ implementations must swallow the antidote. A steady stream of interactive jobs can keep the top queues perpetually busy, so a long job that sank to the bottom could wait forever — classic starvation. Worse, a sneaky program could game the rules by issuing a token I/O call just before its slice expires, tricking the scheduler into treating it as interactive and never demoting it. The fix for both is a periodic priority boost: every so often, sweep every job back up to the top queue. Starved jobs get their turn again, and any behaviour that has drifted since the last boost gets re-measured from scratch. Modern implementations also account for the total time a job has used at a level, rather than resetting on each block, so a slice cannot be gamed by a single well-timed yield.

Feedback

A job’s queue changes based on observed behaviour — the mechanism that lets MLFQ learn what a job is.

Demotion

Using a full time slice signals CPU-bound behaviour and drops a job to a lower-priority, longer-slice queue.

Priority boost

Periodically lifting all jobs back to the top queue to prevent starvation and re-measure behaviour.

Approximating SJF

By favouring jobs that block quickly, MLFQ runs short jobs first without ever knowing burst lengths.

On Unix and Linux, the user-facing knob for scheduling priority is the nice value, and its name is a small joke worth remembering: a high nice value means you are being nice to everyone else by asking for less CPU. Nice ranges from -20 (least nice, highest priority, grabs the most CPU) to +19 (most nice, lowest priority), with 0 as the default. Any user can make their own process nicer; only the superuser can make a process less nice than default, because lowering your nice value takes CPU away from others.

Nice values do not carve the CPU into fixed shares — they weight it. On Linux each step of nice changes a task’s weight by roughly 1.25×, so a difference of one nice level translates to about a 10% difference in CPU share between two competing tasks. This is a soft, proportional priority: a niced-down job still runs, just less often, and it never starves as long as the CPU has spare cycles. That is the crucial difference from the strict-priority scheduling of Chapter 11, where a low-priority job could wait forever.

# Start a backup at the lowest priority so it never disturbs interactive work
$ nice -n 19 tar -czf backup.tar.gz /home/me

# Renice an already-running process (PID 4123) to be nicer
$ renice -n 10 -p 4123
4123 (process ID) old priority 0, new priority 10

# Only root can go below 0 (higher priority than default)
$ sudo renice -n -5 -p 4123

Nice values live inside the normal scheduling class, but Linux also has entirely separate real-time classes that sit above it. A process scheduled SCHED_FIFO or SCHED_RR has a static real-time priority from 1 to 99 and will always preempt every normal task — no matter how many normal tasks are waiting, a runnable real-time task runs first. SCHED_FIFO runs a task until it blocks or voluntarily yields (no time slicing at all); SCHED_RR is the same but round-robins between real-time tasks of equal priority. These are for hard deadlines — audio processing, robotics, industrial control — where a few milliseconds of jitter is a failure, not an annoyance.

# Inspect a process’s current scheduling policy and priority
$ chrt -p 4123
pid 4123’s current scheduling policy: SCHED_OTHER
pid 4123’s current scheduling priority: 0

# Launch an audio engine as SCHED_FIFO at real-time priority 80
$ sudo chrt -f 80 ./audio-engine

# Move a running PID to SCHED_RR (round-robin real-time) at priority 50
$ sudo chrt -r -p 50 4123

For over fifteen years the default Linux scheduler for normal tasks was the Completely Fair Scheduler, and its central idea is a beautiful simplification. Instead of guessing which jobs are interactive and shuffling them between queues like MLFQ, CFS chases one goal directly: perfect fairness. It models an ideal machine that runs every runnable task simultaneously at an equal fraction of the CPU. Real hardware cannot do that, so CFS approximates it by always running whichever task has so far received the least CPU time.

The bookkeeping for this is the virtual runtime, or vruntime — for each task, the amount of CPU time it has consumed, scaled by its weight. A task with default nice 0 accumulates vruntime at real time; a high-priority (negative nice) task accumulates it more slowly, so it looks like it has run less and therefore gets picked more often; a niced-down task accumulates it faster and is picked less. Fairness and priority fall out of the same single number. The scheduler’s job reduces to: always run the task with the smallest vruntime, let it run a while, update its vruntime, repeat.

To do that efficiently across hundreds of tasks, CFS keeps them in a red-black tree keyed by vruntime — a balanced binary tree where insertion and removal are O(log n) and, critically, the leftmost node is always the task with the smallest vruntime. Picking the next task to run is just walking left to the smallest node; there are no priority arrays and no queue juggling. How long each task runs before being preempted comes from the targeted latency (Linux calls it the scheduling period): the span in which every runnable task should get at least one turn. That period is divided among the runnable tasks in proportion to their weights, so with more tasks each slice shrinks — down to a floor called the minimum granularity, so slices never get so tiny that context-switch overhead dominates.

Virtual runtime (vruntime)

Per-task CPU time consumed, weighted by nice; the task with the smallest vruntime runs next.

Weight

A number derived from nice value; it scales how fast vruntime grows, encoding priority as a share.

Red-black tree

The balanced tree ordering runnable tasks by vruntime; leftmost = smallest = next to run, in O(log n).

Targeted latency

The scheduling period in which every runnable task should run once; split by weight into per-task slices.

# Per-task scheduler statistics the kernel exposes for any PID
$ cat /proc/4123/sched | head -n 6
audio-engine (4123, #threads: 3)
se.exec_start                    :        981234.512300
se.vruntime                      :          4521.883917
se.sum_exec_runtime              :          1203.442100
nr_switches                      :               84213
prio                             :                 120

One honest, up-to-date note. Since Linux 6.6 (released in 2023), CFS has been replaced as the default by EEVDF — Earliest Eligible Virtual Deadline First. EEVDF keeps fairness as its foundation but tracks each task’s lag: how far its actual CPU time is from the fair share it was owed. A task is "eligible" only once it has not run ahead of its fair share, and among all eligible tasks the scheduler picks the one with the earliest virtual deadline. That deadline is derived from a per-task requested time slice, so a latency-sensitive task can ask for a shorter slice and thereby earn an earlier deadline and quicker scheduling — a cleaner, more principled way to serve interactivity than the pile of heuristics CFS grew over the years. The mental model barely changes: still fair, still driven by weighted virtual time, now with an explicit latency knob.

Everything so far assumed one CPU. Real machines have many cores, and the naive fix — one big shared ready queue that all cores pull from — collapses under its own locking. Every core taking a task would have to grab the same lock, and with dozens of cores that single lock becomes a bottleneck that serialises the very parallelism the cores exist to provide. So real kernels give each CPU its own run queue. A core schedules from its own queue with no contention, and CFS/EEVDF runs independently per core.

Per-CPU queues create a new problem: they drift out of balance. One core’s queue can pile up with runnable tasks while another sits idle. The kernel therefore runs periodic load balancing, migrating tasks from busy cores to idle ones so no core is overworked while another loafs. But migration is not free, and understanding why is the key insight of this section.

The cost is cache warmth. While a task runs on a core, that core’s L1 and L2 caches fill with the task’s data and instructions — the cache is "hot", and memory accesses are fast. Move the task to another core and it starts cold: the new core’s caches know nothing about it, so it stalls fetching from slower shared cache or main memory until warmth rebuilds. On NUMA machines it is worse still — the task’s memory may be physically attached to the old core’s node, so every access now crosses the interconnect. A good scheduler is therefore reluctant to migrate: it prefers to leave a task where its cache is warm, and it models the machine’s topology (which cores share caches, which belong to the same NUMA node) so that when it must migrate, it moves a task the shortest distance possible.

Sometimes you, the engineer, know better than the balancer. CPU affinity lets you pin a thread to a specific core or set of cores, so the scheduler never migrates it away. This is a common tactic for latency-critical threads — a trading engine, a packet-processing loop — where a cold cache after migration is a measurable, unacceptable stall. Pinning keeps the cache reliably hot at the cost of flexibility.

# Which cores is PID 4123 allowed to run on?
$ taskset -cp 4123
pid 4123’s current affinity list: 0-7

# Pin it to cores 2 and 3 only (keeps its cache warm on those cores)
$ taskset -cp 2,3 4123
pid 4123’s new affinity list: 2,3

# Launch a program pinned to a single core from the start
$ taskset -c 2 ./latency-sensitive-worker

Per-CPU run queue

Each core has its own ready queue, avoiding contention on a single global scheduler lock.

Load balancing

Periodically migrating tasks from busy cores to idle ones to keep cores evenly utilised.

Cache warmth

A task’s data sitting hot in a core’s caches; migration throws it away and forces a cold, slow restart.

CPU affinity

Pinning a task to specific cores so the scheduler will not migrate it — trading flexibility for warm caches.

So far the unit of fairness has been the process, but that is not how the cloud thinks. A server hosts many containers, each possibly belonging to a different customer, and fairness has to hold between those groups, not just between individual processes. If one container spawns a hundred CPU-hungry threads, per-process fairness would happily hand it most of the machine — a hundred shares against everyone else’s one. Linux solves this with control groups (cgroups): the kernel feature that lets you bound and share CPU (and memory, and I/O) between entire groups of processes.

The CPU controller offers two distinct levers, and the difference matters. The first is proportional: cpu.weight (default 100) sets a group’s relative share of the CPU when there is contention — a group with weight 200 gets twice the CPU of a group with weight 100, but only when the CPU is actually busy. Idle cycles are still free for the taking. This is exactly nice values, lifted up from processes to groups. The second lever is a hard cap: cpu.max expresses a quota and a period, such as "50000 100000" — 50 ms of CPU every 100 ms — which limits the group to half a core even when the rest of the machine is idle. Hit the quota and every task in the group is throttled, frozen until the next period begins.

# Give this group double the default proportional share
$ echo 200 > /sys/fs/cgroup/mygroup/cpu.weight

# Hard-cap the group to 0.5 CPU: 50ms of runtime per 100ms period
$ echo "50000 100000" > /sys/fs/cgroup/mygroup/cpu.max

# Docker exposes the same two knobs directly:
$ docker run --cpu-shares 512 --cpus 0.5 my-service
#   --cpu-shares -> cpu.weight (proportional, only under contention)
#   --cpus       -> cpu.max     (hard ceiling, always enforced)

This is precisely how the cloud slices a CPU. When you set a Kubernetes CPU "request", you are setting a proportional weight; when you set a CPU "limit", you are setting a cpu.max quota that will throttle the container. It is also the mechanism behind one of the most common performance surprises in production: CPU throttling. A container with a tight limit can be forcibly stopped mid-computation the instant it exhausts its quota, adding latency that has nothing to do with the code and everything to do with the cgroup ceiling — a bill that comes due precisely when the service is busiest.

cgroup

A kernel group of processes with collective resource limits and shares — the unit of fairness for containers.

cpu.weight

Proportional CPU share between groups under contention; the group-level equivalent of a nice value.

cpu.max (quota/period)

A hard CPU ceiling; exceed the quota within a period and the whole group is throttled until the next.

Throttling

The kernel freezing a group’s tasks once they hit their quota — a frequent, non-obvious source of latency.

It is tempting to file scheduling under "the kernel handles it" and move on. But the scheduler is on the critical path of every request your software serves, and its behaviour shows up as symptoms you will absolutely meet in production. Knowing the mechanisms in this chapter turns those symptoms from baffling into diagnosable.

• ▸A busy box feels laggy: a CPU-bound batch job is competing with your interactive work. Renice the batch job to +19, or put it in a low-weight cgroup, and the machine feels responsive again — the compile barely slows.
• ▸A latency-critical thread has erratic tail latency: it is being migrated between cores and paying the cold-cache cost. Pin it with taskset/affinity and the spikes often vanish.
• ▸A container is slow despite low CPU usage graphs: it is being throttled by its cgroup cpu.max limit, stopped mid-work every period. Raise the limit or remove it, and measure.
• ▸A "noisy neighbour" is starving your service on a shared host: another tenant’s group is eating the CPU. Proportional weights and hard quotas exist precisely to fence that off.

Notice how each fix is just one of this chapter’s ideas applied deliberately. Nice values and cgroup weights are proportional priority. Affinity is a stand you take against the load balancer’s migration bet. Throttling is cpu.max doing exactly what you configured. None of it is mysterious once you can name the mechanism — and naming the mechanism is the whole point of studying the OS.

Step back and see the arc. Chapter 11 gave us pure algorithms, each optimal for one metric and hopeless at the others. This chapter watched real systems refuse to choose: the multilevel feedback queue learns a job’s nature from its behaviour to get SJF-like results with no crystal ball; Linux’s CFS and EEVDF pursue weighted fairness through virtual time and a balanced tree; multiprocessor scheduling guards cache warmth across cores; and cgroups lift fairness from processes to whole containers so the cloud can share a machine. Theory became practice by combining the classic ideas and letting observed behaviour drive the decisions.