The Completely Fair Scheduler
From 2007 until the EEVDF rewrite of 2023, the default Linux scheduler was the
Completely Fair Scheduler (CFS), written by Ingo Molnár in a famously terse few thousand
lines. It replaced the older O(1) scheduler's pile of heuristics — interactivity bonuses, sleeper credits,
magic constants — with a single, almost philosophical idea: model an ideal, perfectly fair CPU that
runs every runnable task at once, each at a fraction of full speed, and then, on real hardware that can run
only one task at a time, always dispatch the task that has fallen furthest behind that ideal.
"How far behind is each task?" is answered by one number per task: its virtual runtime, or
\texttt{vruntime}. If you did the previous lesson on
lottery
and stride, you already know the trick — CFS is stride scheduling with "pass" renamed
"vruntime", weights coming from Unix nice values, and the run queue stored in a
red-black tree (a
self-balancing binary search tree) so the minimum is always at your fingertips.
Virtual runtime: fairness in one counter
Each task accumulates \texttt{vruntime} as it runs, but at a rate scaled by its
weight. Run a task for \Delta nanoseconds of real time and its
virtual runtime grows by
\Delta \texttt{vruntime} \;=\; \Delta \cdot \frac{W_0}{w_i},
\qquad W_0 = 1024 = \text{the weight of a nice-0 task}.
A heavy task (high weight, low nice value) has its clock run slow — its
\texttt{vruntime} creeps up gently, so it keeps looking "behind" and gets picked
again and again. A light task's clock runs fast, its
\texttt{vruntime} races ahead, and it waits longer between turns. The scheduler's
entire policy is then one line: run the runnable task with the smallest
\texttt{vruntime}. Fairness is not a special case bolted on; it is the
definition.
Weights come from the classic Unix nice value (-20 to
+19, default 0) through a fixed table in which each
step of nice changes CPU share by roughly 1.25\times. Nice
0 weighs 1024; nice +5
weighs 335; nice -5 weighs
3121. Two tasks split the CPU in proportion to their weights.
The run queue is a tree
To "pick the least \texttt{vruntime}" fast, CFS keeps the runnable tasks in a
red-black tree keyed by \texttt{vruntime} — a self-balancing
binary search tree. The task to run next is always the leftmost node (smallest key), which CFS
caches, so dispatch is O(1) and inserting a woken task or re-inserting a
preempted one is O(\log n). When a task has run, its
\texttt{vruntime} has grown, so it is removed and reinserted further right, and
the next-leftmost task takes its turn.
A newly woken task is not inserted at \texttt{vruntime} = 0 — that would let it
hog the CPU to "catch up" for all the time it slept. Instead CFS places it near the tree's minimum
(with a small sleeper credit), so it gets a prompt but bounded turn. This is how CFS gives sleepers — that
is, interactive tasks — good response without a special interactivity heuristic.
Target latency and minimum granularity
How long is one "turn"? CFS aims to run every runnable task once within a window called the
target latency (\texttt{sched\_latency}, e.g.
6 ms). It divides that window among tasks by weight, so task
i's time slice is
\text{slice}_i \;=\; \texttt{sched\_latency} \cdot \frac{w_i}{\sum_j w_j}.
With two equal tasks and a 6 ms latency, each runs
3 ms per round. But if a hundred tasks are runnable, dividing
6 ms a hundred ways gives 60\,\mu\text{s} slices —
and the cost of context switching would swamp useful work. So CFS enforces a
minimum granularity (\texttt{sched\_min\_granularity}, e.g.
0.75 ms): no slice drops below it, even if that means the target latency
stretches. This is the eternal scheduler tension — fairness/responsiveness (short slices) versus
throughput (long slices amortising switch cost).
- each task carries a \texttt{vruntime} that grows by
\Delta \cdot W_0/w_i when it runs for real time
\Delta;
- the scheduler always runs the runnable task with the least
\texttt{vruntime} — the leftmost node of a red-black tree keyed by it;
- weights come from nice values (each step ≈ 1.25\times the
CPU share); shares are proportional to weight;
- slices divide a target latency by weight but never fall below a minimum
granularity, trading responsiveness against context-switch overhead.
Watch vruntime steer the CPU
The simulator runs two tasks — one at nice 0 (weight
1024) and one at nice 5 (weight
335) — under the exact CFS rule: repeatedly dispatch the least-vruntime task for a
1 ms tick and charge it W_0/w_i. Because the heavy task's clock runs slow, it
wins roughly three ticks for every one the light task gets — matching the weight ratio
1024/335 \approx 3.06.
// CFS core: always run the task with the least vruntime; charge vruntime by W0/weight.
const W0 = 1024;
interface Task { name: string; weight: number; vruntime: number; ticks: number; }
const tasks: Task[] = [
{ name: "nice 0", weight: 1024, vruntime: 0, ticks: 0 }, // heavy: runs often
{ name: "nice 5", weight: 335, vruntime: 0, ticks: 0 }, // light: runs rarely
];
const TICKS = 40; // each tick = 1 ms of real CPU time
for (let t = 0; t < TICKS; t++) {
// Pick the least-vruntime task (the leftmost node of the RB tree).
let pick = tasks[0];
for (const task of tasks) if (task.vruntime < pick.vruntime) pick = task;
pick.vruntime += 1 * (W0 / pick.weight); // charge 1 ms, scaled by weight
pick.ticks++;
}
for (const task of tasks) {
const share = ((task.ticks / TICKS) * 100).toFixed(0);
console.log(`${task.name}: ran ${task.ticks}/${TICKS} ticks (${share}%), ` +
`final vruntime = ${task.vruntime.toFixed(1)}`);
}
console.log("weight ratio 1024/335 = " + (1024 / 335).toFixed(2) + " -> CPU-share ratio should match");
CFS is fair about throughput — over time everyone gets their weighted share — but it has no notion
of latency requirements. A task that wants "not much CPU, but please run me soon when I
wake" (audio, input handling) could only ask by lowering its nice value, which also (wrongly) grants it a
bigger share. EEVDF (Earliest Eligible Virtual Deadline First), which became the
default in Linux 6.6, separates the two: each task declares a latency requirement that sets a
virtual deadline, and the scheduler runs the eligible task with the earliest deadline while still
honouring weighted fairness for throughput. It is CFS's fairness plus a deadline dimension — and it retired
a lot of the interactivity hacks that had accreted around CFS over sixteen years.
The name misleads a lot of students. CFS is not egalitarian — a nice--5 task
legitimately gets about nine times the CPU of a nice-+5 task
(3121/335). "Fair" here means proportional to weight: each task gets
exactly the share its weight entitles it to, no more and no less, with no task starved. The fairness is in
the faithfulness to the weights, not in equal division. Equal division is just the special case
where all weights are equal. Likewise, a lower \texttt{vruntime} is not a
"reward" — it simply means "this task has received less than its share so far," which is precisely why it
should run next.
The through-line
Trace the lineage: SJF wanted to know job lengths;
MLFQ
estimated them by watching behaviour;
stride
gave exact shares with a per-task counter; and CFS made that counter the only state, stored it in a
balanced tree, and shipped it to billions of devices. Every one of these is answering the same question —
"who runs next, and for how long?" — with progressively less magic. The next question is what changes when
there is more than one CPU to schedule onto, which is exactly where
multiprocessor
scheduling begins.