vault

The Completely Fair Scheduler and Its History

13 min read

The Completely Fair Scheduler and Its History

The Completely Fair Scheduler (CFS) was the default Linux scheduler for ordinary (SCHED_OTHER/SCHED_NORMAL) tasks from its merge in kernel 2.6.23 (October 2007) until it was superseded by EEVDF in kernel 6.6 (October 2023). Written by Ingo Molnár, CFS replaced the O(1) scheduler and discarded its tangle of interactivity heuristics in favor of one elegant idea: model an ideal, perfectly fair multitasking CPU and, on real hardware that can run only one task at a time, hand the CPU to whichever runnable task is furthest behind its fair share — the task with the smallest virtual runtime (vruntime), tracked in a time-ordered red-black tree (sched-design-CFS.rst). CFS is now historical: it is not a selectable alternative in a current kernel. As of Linux 6.12 LTS (released 2024-11-17) the fair scheduler in kernel/sched/fair.c is EEVDF; CFS’s machinery — vruntime, the per-task weight, the rbtree, the group-scheduling hierarchy — was inherited and extended rather than thrown away. This note explains what CFS was, why it won in 2007, and why its central weakness — no clean way to express latency without also handing out more CPU — eventually forced the move to The EEVDF Scheduler.

Scope of this note

This is the history and design-philosophy note for CFS. The shared vruntime/weight machinery that both CFS and EEVDF use lives in Virtual Runtime and the Fair Scheduling Invariant; the current default scheduler is The EEVDF Scheduler. This note recaps those concepts only enough to tell the story and cross-links the rest.

Mental Model: The Ideal Multitasking CPU

The kernel documentation sums up 80% of CFS in one sentence: “CFS basically models an ‘ideal, precise multi-tasking CPU’ on real hardware” (sched-design-CFS.rst). An ideal multitasking CPU is a fiction: a processor with 100% power that runs every runnable task simultaneously, each at exactly 1/nr_running of full speed. If two tasks are runnable, each runs at 50% speed in parallel; if ten are runnable, each runs at 10% speed. On such a CPU no task ever falls behind — at every instant all tasks have received identical service.

Real hardware runs one task per core at a time, so CFS approximates the ideal by time-slicing very finely and keeping a per-task ledger of how much CPU each task has consumed, weighted by priority. That ledger entry is the task’s virtual runtime (p->se.vruntime, in nanoseconds). On the ideal CPU all tasks would always have equal vruntime; on real hardware they drift apart, and CFS’s entire job is to continually pick the task with the smallest vruntime — the one that has run least relative to its entitlement — thereby pulling the system back toward the ideal where everyone’s vruntime is equal.

flowchart LR
  subgraph IDEAL["Ideal CPU (fiction)"]
    direction TB
    I1["all tasks run in parallel<br/>each at 1/N speed<br/>vruntime always equal"]
  end
  subgraph REAL["CFS on real hardware"]
    direction TB
    R1["one task runs at a time"]
    R2["running task's vruntime grows<br/>(weighted by nice)"]
    R3["rbtree keyed on vruntime"]
    R4["always pick leftmost<br/>(smallest vruntime)"]
    R1 --> R2 --> R3 --> R4 --> R1
  end
  IDEAL -. "approximate by<br/>finely time-slicing" .-> REAL

How CFS approximates fairness. What it shows: the unreachable ideal (left) where every task runs simultaneously and no vruntime ever diverges, versus CFS’s real-hardware approximation (right) — run one task, charge its weighted runtime to vruntime, and always re-pick the task with the smallest vruntime (the leftmost node of a red-black tree). The insight: CFS has no timeslices and no interactivity heuristics; “fairness” is just the discipline of repeatedly serving whoever is furthest behind. This is also exactly the substrate EEVDF kept — see Virtual Runtime and the Fair Scheduling Invariant.

What Came Before: The O(1) Scheduler and the RSDL Episode

To understand why CFS was a relief, recall what it replaced. The O(1) scheduler (merged in 2.6.0, 2003, by Molnár) maintained two priority-indexed arrays per CPU — an active array and an expired array — each a set of 140 run queues (100 real-time priorities plus 40 nice levels). Picking the next task was constant-time: find the highest-priority non-empty queue via a bitmap. When a task exhausted its timeslice it moved to the expired array; when the active array emptied, the two arrays were swapped (“array switch”). The catch was interactivity detection: to keep desktops responsive, the O(1) scheduler used elaborate heuristics to guess which tasks were interactive (sleep-heavy, latency-sensitive) and award them priority bonuses. These heuristics were fragile, gameable, and the source of endless tuning complaints.

The reform came from outside the mainline. Con Kolivas built a series of out-of-tree schedulers — the Staircase scheduler (2004), then the Rotating Staircase Deadline (RSDL) and Staircase Deadline (SD) schedulers — whose thesis was that interactivity detection is the wrong approach: a scheduler that distributes CPU fairly by construction does not need to guess who is interactive (OSnews 2007). Kolivas’s fair-scheduling work directly inspired Molnár, who in 2007 wrote CFS as a mainline answer and credited Kolivas in his announcement (Wikipedia: Completely Fair Scheduler). CFS shipped in 2.6.23 in October 2007, replacing both the O(1) scheduler and its SCHED_OTHER interactivity code (sched-design-CFS.rst).

Uncertain

Verify: exact merge/authorship dates for the O(1) scheduler (2.6.0, 2003) and the precise RSDL→SD→CFS sequence. Reason: these predate the cited primary docs and rest partly on secondary sources (Wikipedia, OSnews, IBM developerWorks); the kernel sched-design-CFS.rst confirms only “merged in 2.6.23” and “implemented by Ingo Molnar.” To resolve: cross-check the original 2007 lkml CFS announcement and 2003 O(1) commit history on git.kernel.org. uncertain

The Mechanism: vruntime, Weights, and the Red-Black Tree

CFS’s accounting rests on three pieces, all of which survive in today’s EEVDF code and are documented fully in Virtual Runtime and the Fair Scheduling Invariant and Nice Values Weights and Priority Scaling. A brief recap so this note stands alone:

Virtual runtime. Each task carries p->se.vruntime (nanoseconds). When a task runs for delta_exec real nanoseconds, its vruntime is advanced not by delta_exec but by delta_exec scaled by the task’s weight — the routine still called calc_delta_fair() in fair.c. A nice-0 task (weight NICE_0_LOAD, 1024) advances its vruntime at exactly real-time rate; a high-priority (negative-nice, heavier) task advances slower, so it sits at the left of the tree longer and is picked more often; a low-priority (positive-nice, lighter) task advances faster and is picked less often. This is how nice levels become CPU shares without any timeslice arithmetic.

The weight is exponential in nice. The 2.6.23 redesign deliberately made nice multiplicative: each nice step changes a task’s CPU share by a constant ratio (~1.25×), regardless of the absolute nice level, so a nice-10-vs-nice-11 pair splits the CPU in the same 55/45 proportion as a nice−5-vs-nice−4 pair (sched-nice-design.rst). This fixed a long-standing O(1)-era complaint that nice behavior depended on the absolute nice level of the parent shell.

The red-black tree. CFS abandoned the O(1) arrays for a time-ordered red-black tree keyed on vruntime. The leftmost node is always the task with the smallest vruntime; picking the next task is O(log n) (a cached leftmost pointer makes the common pick O(1)), and there are no array-switch artifacts (sched-design-CFS.rst). The run queue tracks min_vruntime — a monotonically increasing floor used to place newly woken tasks so a task that slept for an hour cannot return with a near-zero vruntime and monopolize the CPU.

There were no real timeslices: CFS used nanosecond accounting and a single tunable, sysctl_sched_latency (the target period over which every runnable task should get a turn), divided among tasks by weight to derive each task’s slice. A task ran until its vruntime exceeded the next task’s by a granularity threshold, then was preempted (sched-design-CFS.rst).

CFS’s Scheduling Policies and the Class Interface

CFS implemented three policies, all still present: SCHED_NORMAL (the default for regular tasks), SCHED_BATCH (preempts far less often, trading interactivity for cache-friendly long runs — for batch jobs), and SCHED_IDLE (weaker than nice 19, but deliberately not a true idle-only class, to avoid priority-inversion deadlocks). The POSIX real-time policies SCHED_FIFO/SCHED_RR are not CFS — they live in kernel/sched/rt.c and sit above the fair class (see Real-Time Scheduling SCHED_FIFO and SCHED_RR).

Crucially, CFS is also where Molnár introduced scheduling classes — the struct sched_class table of hooks (enqueue_task, dequeue_task, pick_next_task, task_tick, yield_task, wakeup_preempt, …) that lets the core scheduler dispatch to any policy without knowing its internals (sched-design-CFS.rst). That abstraction is the reason EEVDF could later replace CFS’s picking logic without disturbing the rest of the kernel — and the reason sched_ext (BPF schedulers, 6.12) can slot in as just another class. See Scheduling Classes and the sched_class Interface.

The Fatal Limitation: Fairness Cannot Express Latency

CFS’s strength was also its ceiling. Because the only lever was vruntime, the only way to make a task more responsive was to make it heavier — i.e., give it more CPU time. But many latency-sensitive workloads want the opposite trade: an audio thread or an interactive UI handler wants to run promptly when it wakes, run briefly, and then get out of the way — it does not want a larger share of the CPU. CFS had no vocabulary for “wake me fast but don’t give me more.” As the LWN EEVDF write-up put it, “what is lacking is a way to ensure that some processes can get access to a CPU quickly without necessarily giving those processes the ability to obtain more than their fair share” (Corbet, LWN 925371).

The latency-nice saga

The community spent roughly four years (2019–2023) trying to bolt a latency knob onto CFS, and the failure of that effort is the direct motivation for EEVDF. The proposal, latency-nice, was a second per-task [-20, 19] value (set via sched_setattr() / a new sched_attr field) where −20 meant “very latency-sensitive” and 19 meant “indifferent,” analogous to but independent of ordinary nice (Corbet, “The many faces of latency nice”, LWN 820659). The trouble was that everyone wanted it to mean something different: Oracle wanted latency-nice to skip the expensive idle-CPU search on wakeup; Facebook wanted the opposite — find an idle core to ramp a task up fast; IBM wanted to avoid co-locating tasks with already-latency-sensitive ones; Android wanted a cgroup “prefer idle” knob (LWN 820659). One participant observed the feature was “trying to control too many functionalities with a single knob,” and the consensus was that the design was backwards — an interface defined before the use cases were pinned down.

A later, narrower revival by Vincent Guittot (2022–2023) scoped latency-nice down to a preemption-and-placement hint: a negative latency_nice lets a waking CFS task preempt the current task sooner, implemented with a separate red-black tree of latency-sensitive entities; Android testing cut missed-deadline frames from ~5% to under 0.1% (Corbet, “Add latency priority for CFS class”, LWN 924284; “Improved response times with latency nice”, LWN 887842). It worked, but it was visibly a patch on top of a model that fundamentally tied responsiveness to CPU share.

Why EEVDF was the clean answer

Peter Zijlstra argued that rather than graft latency hints onto CFS, the kernel should adopt EEVDF — a fair-scheduling algorithm from a 1995 paper by Ion Stoica and Hussein Abdel-Wahab — which has a built-in, principled latency lever: each task requests a time slice (request size r_i), and a shorter requested slice yields an earlier virtual deadline, so latency-sensitive tasks are picked sooner without being granted more total CPU (Corbet, LWN 925371; referenced as [1] in sched-eevdf.rst). The latency-nice user interface survived — it now maps onto EEVDF’s slice request — but the mechanism underneath changed entirely. Zijlstra’s EEVDF series first appeared as sched: EEVDF using latency-nice (LWN 927530) and merged as the new default fair picking algorithm in 6.6 (October 2023), with follow-up work in 2024 to “complete” it (Corbet, “Completing the EEVDF scheduler”, LWN 969062). The full story of the successor is in The EEVDF Scheduler and Eligibility Lag and Virtual Deadlines in EEVDF.

Uncertain

Verify: that the 2009 Linux 2.6.32 BFS/Con Kolivas era and the precise authorship of every latency-nice revision (Parth Shah, Vincent Guittot, Peter Zijlstra) are attributed correctly. Reason: the latency-nice saga spanned many posters over four years; the cited LWN articles name the major figures but a one-line attribution risks crediting the wrong person for a given revision. To resolve: read the full lkml threads behind LWN 820659 / 924284 / 927530. uncertain

What Replaced What — Precisely

A common misconception worth correcting: EEVDF did not ship as a toggleable alternative alongside CFS. In 6.6 it replaced the task-picking algorithm inside kernel/sched/fair.c — the same file, the same fair_sched_class, the same vruntime/weight/rbtree substrate — so CFS’s code was folded into the EEVDF implementation, not kept beside it (sched-eevdf.rst). This is why, in a 6.12 LTS kernel, there is no CONFIG_SCHED_CFS to flip and no /sys knob to choose CFS: the fair class is EEVDF, and “CFS” is a historical name for the lineage. (The kernel doc’s phrasing “a new option in 2024” is imprecise on both counts — the change landed in 6.6, October 2023, and it was a replacement, not an option.)

Failure Modes and Common Misunderstandings

  • “CFS is the current Linux scheduler.” No — as of 6.6 (Oct 2023) and through 6.12 LTS (2024-11-17), the default fair scheduler is EEVDF. Treating CFS as current is the single most common error; flag it whenever you see it.
  • “vruntime is wall-clock time.” No — it is weighted runtime. A heavily-niced (low-priority) task accrues vruntime faster than wall-clock; a high-priority task slower. Equal vruntime means equal fair share, not equal seconds.
  • “sched_latency/base_slice is a hard timeslice.” No — CFS had no fixed quantum; it derived a per-task slice from a target period and weights, and preempted on vruntime divergence plus granularity. EEVDF reintroduced an explicit request size (base_slice, 750 µs in 6.12) — see Time Slices and Request Sizes in EEVDF.
  • “Nice is linear.” No — since 2.6.23 nice is multiplicative; each step is a ~1.25× ratio in CPU share (sched-nice-design.rst).

Contrast: a userspace scheduler with the same problem

Go’s runtime multiplexes goroutines onto OS threads with its own run queues and work-stealing — a userspace M:N scheduler. It is instructive precisely because it made a different trade-off than CFS: Go does not aim for proportional fairness at all; it aims for throughput and cheap context switches, originally relying on cooperative yield points (later signal-based preemption). It has no vruntime, no nice weights, and no fairness invariant — it preempts a long-running goroutine only to prevent starvation, not to equalize CPU shares. Seeing what Go omits sharpens what CFS is: CFS’s entire complexity exists to deliver weighted fairness across untrusted, uncooperative tasks, a guarantee a language runtime scheduling its own cooperative goroutines does not need. See GMP Scheduler Model and Goroutine Preemption.

See Also

Graph View

Backlinks