How Linux CFS Works: vruntime, Red-Black Trees, and Why Fairness Is Approximate

A CPU core runs one thread at a time. Everything else that looks concurrent is a lie the operating system maintains by switching. The policy that decides which runnable thread gets the core next is the scheduler.

On Linux, ordinary user processes run under SCHED_NORMAL. From 2.6.23 through 6.5 that policy was implemented by the Completely Fair Scheduler (CFS). The name oversells the guarantee. CFS does not give every task identical wall-clock slices. It approximates an ideal multiprocessor that could run every runnable task simultaneously, each at a fraction of a core proportional to its weight.

This article is about that approximation: virtual runtime, nice weights, the red-black tree on each CPU runqueue, granularity, sleeper placement, and why the model is still approximate. It is not a second tour of processes versus threads, virtual memory, or system-call entry. Those explain what a task is. CFS explains who runs when several tasks are already runnable on the same core.

Kernels 6.6 and later replaced the CFS pick rule with EEVDF while keeping the same entities and tree. The last section notes that change. The mechanism that still dominates most mental models, textbooks, and production kernels older than 6.6 is CFS.

The ideal that CFS copies

Imagine hardware that could split one core into N simultaneous slices. Three equally nice tasks would each see one-third of the core all the time. No one waits. No one hogs. Reality cannot do that. One core has one program counter.

CFS encodes the same fairness as a number: vruntime. Each schedulable entity accumulates virtual time while it runs. The scheduler always prefers the entity whose vruntime is smallest — the one that has received the least weighted CPU so far. If the tree is kept ordered by that key, “who next” is the leftmost node.

Equal-weight tasks therefore converge on the same vruntime. Whoever ran more sits further right. Whoever ran less sits left and is picked. Over a long enough window the shares approach 1/N. Over a short window they do not, because switching has a cost and CFS refuses to switch after every microsecond.

vruntime is weighted wall time

The update is not “add the nanoseconds that just elapsed.” It is:

vruntime += delta_exec * (NICE_0_WEIGHT / task_weight)

NICE_0_WEIGHT is 1024. A default nice-0 task therefore accumulates vruntime at the same rate as wall time. A higher-weight task (negative nice) accumulates more slowly. A lower-weight task (positive nice) accumulates faster.

That single scaling is how priority enters a scheduler that has no priority queues. The pick rule stays “smallest vruntime.” Shares change because the same real millisecond is worth a different number of virtual nanoseconds.

The kernel stores the mapping from nice (−20 … +19) in sched_prio_to_weight[]. Adjacent nice levels differ by about 1.25× in weight. That is why a one-step nice change is advertised as roughly a 10% shift in CPU share when two tasks compete: 1.25 / (1 + 1.25) versus 1 / (1 + 1.25).

Worked numbers help. Three runnable tasks, weights 3121 (nice −5), 1024 (nice 0), and 335 (nice +5). Total weight 4480.

• A should get 3121/4480 ≈ 69.7% of the core
• B should get 1024/4480 ≈ 22.9%
• C should get 335/4480 ≈ 7.5%

After one second of real time on a busy core, their vruntimes are close. Their real runtimes are not: roughly 697 ms, 229 ms, and 75 ms. Fairness here means equal virtual time, not equal milliseconds.

The red-black tree is the runqueue

Older Linux schedulers kept per-priority lists. CFS keeps one time-ordered tree per CFS runqueue (cfs_rq). The key is vruntime. The node type is sched_entity, not task_struct directly. A task has an entity. A control group can also be an entity that contains a nested cfs_rq. The same pick rule therefore works for tasks and for group scheduling.

The tree is an rb_root_cached. Besides the usual red-black links it caches a pointer to the leftmost node. Finding the next candidate is O(1). Insert and erase after a vruntime update are O(log n). A binary heap would also give O(1) min, but erase-and-reinsert of an arbitrary node is the common operation after every tick and every sleep. An rbtree makes that O(log n) without an auxiliary index.

On every scheduler tick and every context switch, update_curr() adds the elapsed time into the running entity’s vruntime. If that entity is still runnable it is no longer guaranteed to be leftmost. When its vruntime exceeds the leftmost competitor by more than a granularity threshold, it is preempted.

The runqueue also tracks min_vruntime: a monotonic floor used when placing entities that were not on the tree. Without a floor, a task that slept for a long time would keep an ancient vruntime, land far left, and monopolize the core until it caught up. Placement is clamped toward current min_vruntime so a sleeper is treated as slightly behind, not infinitely behind.

Granularity: fairness versus cache heat

If CFS switched at every nanosecond of vruntime gap, two tasks would ping-pong and destroy cache locality. The scheduler therefore requires a minimum distance before preemption.

Classic CFS expressed that as a target latency and a minimum granularity:

• sched_latency_ns — the window in which every runnable task should get a turn when the runqueue is small (commonly 6 ms on desktop-tuned kernels)
• sched_min_granularity_ns — a floor on how short a slice may be (often around 0.75–1.5 ms)

When N is small, the implied slice is latency / N. When N grows past latency / min_granularity, the period stretches: every task still gets at least min_granularity, so the full rotation takes longer. That is the first place “completely fair” becomes approximate. A loaded machine delays the next turn for everyone rather than shrinking slices to zero.

Wakeup preemption used a related knob, sched_wakeup_granularity_ns. A newly woken task does not always steal the CPU immediately. It steals if its vruntime is behind the current task by enough virtual time that the preemption is worth the cache miss. Interactive workloads want that gap small. Throughput workloads want it larger.

These sysctls still exist on many kernels. After the EEVDF switch the primary slice knob became sched_base_slice_ns. The idea is the same: do not schedule more often than the hardware and the caches can absorb.

Sleepers, I/O wait, and the “bonus”

A task blocked in read or futex is not on the CFS tree. It accumulates no vruntime while asleep. When it wakes, CFS must choose a vruntime for re-insertion.

Place it at current min_vruntime and it is even with the pack — no extra urgency. Place it slightly left and it gets a short burst, which is what a UI thread or a packet handler usually needs after a wait. Place it at its old vruntime after a ten-second sleep and it becomes a thundering hog.

CFS historically applied sleeper fairness: a waking task is credited as if it had been receiving its share while blocked, then capped so the credit cannot grow without bound. The result is a modest leftward placement, not a full catch-up of the sleep duration. That heuristic is why a text editor stays responsive on a box compiling the kernel, and also why the behavior is hard to describe with one equation. It is policy layered on the vruntime key, not a second scheduler.

Nice is not realtime

Nice and CFS weights apply only to SCHED_NORMAL (and the batch/idle variants). They do not create deadlines. A nice −20 task can still wait behind whatever is already running until granularity allows a switch. A nice +19 task can still run if it is the only runnable entity on that CPU.

True isolation uses other classes:

• SCHED_FIFO / SCHED_RR — realtime, always preferred over CFS when runnable
• SCHED_DEADLINE — EDF with runtime/period budgets
• cgroup cpu.max / CPU controllers — bandwidth caps across a group of entities

If a latency-sensitive service misses a 2 ms deadline under CFS, that is expected. CFS was built for share fairness among best-effort work, not for bounded response time. Moving that service to deadline scheduling, or isolating it with cpusets, is the actual fix. Lowering nice on everything else is a blunt approximation.

Per-CPU queues and load balancing

Each CPU has its own cfs_rq and its own tree. A task that is running or recently ran tends to stay on that CPU because migrating throws away cache and, on NUMA, remote memory. Fairness across CPUs is a second algorithm: the load balancer compares weighted load, steals from busier runqueues, and tries not to bounce a task every millisecond.

That split matters when you read /proc/sched_debug or per-CPU runqueue lengths. A machine can look “unfair” in a one-second top sample because task A was stuck on a busy CPU while task B sat on an idle one. CFS fairness is defined per runqueue first. Cross-CPU fairness is eventual and heuristic.

The same structure explains why pinning (taskset, cpusets) changes tail latency. You remove balancer surprises. You also remove the chance to use an idle core that the balancer would have found.

A short timeline of one tick

Suppose CPU 2 is running task B. The periodic tick fires.

1. Hardware delivers a timer interrupt. The kernel accounts the delta since the last update to B’s sched_entity.
2. update_curr() increases B’s vruntime by the weighted delta.
3. If B is still the leftmost entity within granularity, B keeps the core. The tick returns to user mode.
4. If another entity A is now left enough, the tick sets TIF_NEED_RESCHED on B.
5. On return to user mode the kernel notices the flag, calls schedule(), picks the leftmost entity, switches address space and registers if the next task is a different mm, and resumes A.

A blocking syscall skips the “wait for the tick” path. The sleeper is dequeued from the tree immediately. schedule() runs before the syscall returns to user space. That is why a read on an empty pipe does not spin the core: the task is no longer a CFS candidate.

Misconceptions

“vruntime is CPU time.” It is weighted CPU time. Two tasks with the same vruntime can have very different sum_exec_runtime.

“The tree is global.” It is per CFS runqueue, which is per CPU, and nested again inside cgroups when group scheduling is on.

“Nice −20 is realtime.” It is a heavier CFS weight. Realtime classes still preempt it.

“A sleeping task’s vruntime freezes, so it always wins when it wakes.” Placement is clamped to the runqueue’s current virtual time. Long sleepers do not cash in the full sleep.

“CFS still picks min vruntime on every modern kernel.” From 6.6 the default pick is EEVDF: earliest virtual deadline among eligible entities. The tree and vruntime accounting remain. The comparison key for “who runs now” does not.

What EEVDF changed without throwing the tree away

CFS’s weakness was latency for tasks that wake often and run briefly. A packet handler can sit a little to the right of a compiler. Until its vruntime looks left enough, it waits, even though it only wanted 50 µs.

EEVDF (Earliest Eligible Virtual Deadline First), merged in Linux 6.6, keeps vruntime as the lag account. It adds a deadline:

deadline = vruntime + weighted(slice)

A task is eligible when it is not running ahead of the weighted average virtual time. Among eligible tasks, the earliest deadline wins. A short-slice waker becomes eligible immediately and has an early deadline, so it cuts in without waiting for the old vruntime race.

If your kernel is older than 6.6, the rest of this article is the live policy. If it is newer, treat CFS as the accounting and tree design you will still see in kernel/sched/fair.c, and treat EEVDF as the pick function sitting on top.

Takeaways

CFS turns “share the core in proportion to weight” into a single ordered key. vruntime is that key. Weights come from nice. The leftmost cached rbtree node is the next candidate. Granularity stops the key from inducing a context-switch storm. Sleeper placement stops a blocked task from becoming a priority inversion or a monopolist. None of that is a deadline. Cross-CPU balance is a separate pass. On current kernels the pick rule itself has moved to virtual deadlines, but the entity, the tree, and the idea of virtual time are the same machinery.

When a box feels unfair, measure per-CPU runqueues, nice and cgroup weights, and whether the work is blocked or runnable. Changing nice is a share adjustment. Changing isolation or scheduling class is a different contract.