The Completely Fair Scheduler (CFS)

Proportional-share scheduling

The Completely Fair Scheduler (CFS) — the default Linux scheduler since 2.6.23 — takes a different approach from strict priority or round-robin. Instead of fixed quanta, it allocates CPU time in proportion to weight, and it tracks how much each process has received using virtual runtime (vruntime).

Virtual runtime

Each process has a vruntime value measured in nanoseconds. When a process runs for $t$ real nanoseconds, its vruntime advances by:

$\Delta\text{vruntime} = t \times \frac{\text{weight}_0}{\text{weight}_{\text{process}}}$

where $\text{weight}_0$ is the weight for nice 0 (1024). A higher-weight (lower nice) process accumulates vruntime more slowly, so it gets more CPU time for the same vruntime budget.

CFS always picks the process with the smallest vruntime — the one that has received the least CPU time, compensated for its weight.

Target latency

CFS aims to give every runnable process at least one CPU turn within a target latency (default 6 ms, scaled by nr_running). The time slice given to process $i$ is:

$q_i = \frac{w_i}{\sum_j w_j} \times \text{target\_latency}$

where $w_i$ is process $i$‘s weight. So if two processes have equal weight, each gets roughly half the target latency. If one has weight 1024 and the other has weight 335 (nice 5), the higher-priority process gets $1024/(1024+335) \approx 75\%$ of the CPU.

But there is a minimum granularity (default 0.75 ms) to prevent the quantum from becoming so short that context-switch overhead dominates. If target latency divided by the number of processes would give a sub-granularity slice, CFS increases the effective latency instead.

The red-black tree

CFS stores all runnable processes in a red-black tree (a self-balancing binary search tree) keyed by vruntime. The leftmost node (smallest vruntime) is the process to run next. Insertion and removal are $O(\log n)$, and finding the minimum is $O(1)$ (cache the leftmost node).

This is more efficient than scanning an array of all runnable processes, and it handles large numbers of runnable processes without degrading to linear search.

Idle and sleeping processes

When a process sleeps (blocks on I/O), its vruntime does not advance. When it wakes up, it has a relatively small vruntime compared to processes that continued running — so it gets the CPU immediately (good for interactive response). As it runs, its vruntime catches up.

This is a deliberate design choice: processes that sleep (typically I/O-bound, interactive) are rewarded with lower vruntime relative to CPU-bound processes that consumed their full allocation.

CFS vs Round Robin

CFS generalises RR by making the quantum proportional to weight and by tracking total CPU time received rather than just cycling through a list. A pure RR with equal weights and a fixed quantum is approximately CFS with all weights equal and no redistribution to catch-up sleepers.

Worked example (2024 Q3)

Five CPU-bound processes arrive simultaneously with CPU demands of 10, 20, 30, 40, 50 ms. Target latency = 60 ms, minimum granularity = 2 ms. All have default nice (weight 1024).

First, compute how many processes get CPU within the target latency:

• At 60 ms / 5 = 12 ms per process, but minimum granularity is 2 ms (irrelevant here since 12 >> 2). Actually, CFS gives each a proportional share. With equal weights, each gets 60/5 = 12 ms in the first round.
• After the first round: P1 has used 10/10 ms (finishes after 10 ms of its 12 ms slice — rest goes unused), P2 has used 12/20 ms, P3 12/30 ms, P4 12/40 ms, P5 12/50 ms.
• Remaining: P2(8 ms), P3(18 ms), P4(28 ms), P5(38 ms). Now 4 runnable processes: each gets 60/4 = 15 ms. P2 uses 8 ms and finishes, etc.
• Continue until all complete.

The resulting schedule interleaves processes, giving fair proportional shares, and automatically redistributes unused quota (P1 left 2 ms unused, which the others benefit from).

Summary

• CFS uses vruntime to track proportional CPU usage; smaller vruntime → run next.
• Vruntime advances faster for lower-weight (higher nice) processes.
• Target latency and minimum granularity bound the time-slice extremes.
• Sleeping processes are rewarded with reduced vruntime, favouring interactivity.
• The red-black tree orders runnable processes by vruntime, enabling $O(\log n)$ scheduling operations.