What is the Completely Fair Scheduler (CFS) in the Linux operating system

Every time a Linux machine runs more than one program at once — which is always, even on a “quiet” desktop with dozens of background daemons — something has to decide which process gets the CPU next, and for how long. That something, since kernel version 2.6.23 (released in October 2007), is the Completely Fair Scheduler, or CFS. This article is a complete tour of what CFS actually is: where it came from, how it’s structured internally, how it behaves in practice, and how it compares to scheduling approaches on other operating systems.

A Brief History: Why CFS Replaced the O(1) Scheduler

Before CFS, Linux used what was informally called the O(1) scheduler, written by Ingo Molnar for the 2.6 kernel series. It used per-priority run queues (140 priority levels: 100 for real-time, 40 for user processes) and picked the next task in constant time by scanning a bitmap of non-empty queues. It was fast, but fairness was an afterthought bolted on via heuristics that tried to detect “interactive” processes (ones that slept often, like a text editor waiting for keystrokes) and give them priority boosts.

The problem: heuristics are guesses, and guesses are sometimes wrong. Desktop users in the mid-2000s regularly complained about audio skipping during compiles, or mouse lag under load, because the interactivity detector misjudged a workload. Con Kolivar, an independent kernel developer, had already been experimenting with a fairness-first scheduler called the “Rotating Staircase Deadline” scheduler, which influenced the community’s thinking. In 2007, Molnar rewrote the scheduler from scratch around a much simpler and more rigorous idea of fairness, and called it the Completely Fair Scheduler. It was merged into mainline Linux and has been the default scheduler for normal processes ever since (until EEVDF began replacing it starting in kernel 6.6, discussed later).

The Central Idea

CFS models an ideal, hypothetical “perfectly fair CPU” that could divide itself infinitely and run every runnable process simultaneously at an equal (weighted) fraction of full speed. Real CPUs can’t do that — they execute one instruction stream at a time per core — but CFS tracks, for every task, how much virtual runtime (vruntime) it has accumulated, which represents its share of that idealized fair execution. The scheduler’s entire job reduces to one rule:

Always run the runnable task with the smallest vruntime.

Because a task’s vruntime only grows while it’s actually running (weighted by its priority), a task that has run less than others will have a smaller vruntime, and will naturally get picked next. There’s no separate bookkeeping of “whose turn is it” — the ordering emerges directly from the vruntime numbers.

Internal Architecture

Weights and Nice Values

CFS still honors the classic UNIX nice value (-20 to +19), but internally converts it into a weight via a lookup table (sched_prio_to_weight[] in the kernel source). Nice 0 maps to a weight of 1024; each step up or down scales by roughly 1.25x. This weight determines the rate at which a task’s vruntime advances relative to wall-clock time:

vruntime_delta = wall_clock_delta * (1024 / task_weight)

Higher-weight (higher-priority) tasks accumulate vruntime more slowly, so they look “behind” more often and get scheduled more frequently and for longer relative shares.

The Run Queue: A Red-Black Tree

Each CPU maintains its own CFS run queue, implemented as a red-black tree keyed by vruntime. This self-balancing binary tree keeps insertion, deletion, and lookup at O(log n), and the kernel caches the leftmost (smallest-vruntime) node so the “who runs next” decision is O(1). When a task is preempted or finishes its slice, its updated vruntime determines its new position in the tree.

Scheduling Latency and Granularity

CFS defines a target period (sched_latency_ns) during which every runnable task should get scheduled at least once. Each task’s slice within that window is proportional to its weight relative to total runnable weight. A floor (sched_min_granularity_ns) prevents slices from becoming so small that context-switch overhead dominates when many tasks are runnable.

Sleeper Fairness

When a task wakes up after sleeping (e.g., waiting on I/O or a mutex), CFS doesn’t let its vruntime sit unchanged at whatever it was before sleeping — nor does it let the task keep the exact same relative position indefinitely. It’s adjusted (bounded) so that tasks which sleep often, like interactive applications, come back into the tree near the leftmost edge and get low-latency access to the CPU — but not enough to permanently game the scheduler by sleeping strategically.

Scheduling Classes: Where CFS Sits in the Bigger Picture

CFS is only one of several scheduling classes in the Linux kernel, evaluated in this order of priority:

1. Stop-task class — internal, highest priority (CPU hotplug, migration).
2. Deadline class (SCHED_DEADLINE) — Earliest Deadline First, for hard real-time tasks with explicit period/runtime/deadline.
3. Real-time class (SCHED_FIFO, SCHED_RR) — fixed priority, always preempts CFS.
4. CFS class (SCHED_NORMAL/SCHED_OTHER, SCHED_BATCH, SCHED_IDLE) — the fair-share scheduler.

So, “completely fair” only means fair among normal-priority processes. A misbehaving real-time process can still monopolize a CPU core unless the kernel’s RT throttling (sched_rt_runtime_us) or proper cgroup limits are in place.

Multi-Core Behavior: Per-CPU Run Queues and Load Balancing

Each core has its own run queue and its own red-black tree — there’s no single global tree, which would create a scalability-killing lock bottleneck. Instead, the kernel periodically runs load balancing, which:

• Organizes CPUs into scheduling domains (SMT siblings → cores → sockets → NUMA nodes).
• Compares aggregate load between domains.
• Migrates tasks to rebalance, using heuristics to avoid unnecessary cache-cold migrations.

This means fairness on a multi-core Linux box is statistical and per-domain rather than a single strict global ordering — in practice, it converges quickly to balanced utilization.

Group Scheduling and cgroups

CFS supports hierarchical group scheduling. Under cgroups (v1’s cpu controller or v2’s unified cpu.weight/cpu.max), a whole group of tasks — e.g., every process inside a container — can be treated as a single scheduling entity competing against other groups, with fairness then recursively applied within the group. This is the mechanism behind:

• Docker’s --cpu-shares
• Kubernetes’ CPU requests (via cpu.weight) and limits (via cpu.max, aka CFS bandwidth control)
• systemd resource control slices (CPUWeight=, CPUQuota=)

Diagram: CFS Decision Flow

        ┌─────────────────────────────┐
        │   Timer tick / task wakeup   │
        └───────────────┬──────────────┘
                         ▼
        ┌─────────────────────────────┐
        │ Update running task's        │
        │ vruntime (weighted by nice)  │
        └───────────────┬──────────────┘
                         ▼
        ┌─────────────────────────────┐
        │ Compare vruntime to leftmost │
        │ node in red-black tree       │
        └───────────────┬──────────────┘
             vruntime exceeds slice?
             /                     \
           Yes                      No
            │                        │
            ▼                        ▼
   Set need_resched flag     Continue running
            │
            ▼
   Pick leftmost task from tree,
   context switch to it

Practical Examples

Observe fair CPU sharing between equal-priority tasks:

for i in 1 2 3; do (while true; do :; done) & done
top -o %CPU

You’ll see each busy loop getting roughly a third of one CPU core, converging over time regardless of the order they were started.

Influence CFS fairness with nice values:

nice -n 15 stress --cpu 1 &
nice -n -5 stress --cpu 1 &

(Requires root for negative nice values, or appropriate CAP_SYS_NICE capability.)

Inspect a process’s scheduling stats:

cat /proc/<pid>/sched | grep -E "vruntime|nr_switches|sum_exec"

Restrict a cgroup to 50% of one CPU:

echo "50000 100000" > /sys/fs/cgroup/mygroup/cpu.max

CFS vs. Scheduling on Other Operating Systems

Windows and macOS both still rely heavily on dynamic priority adjustment and explicit boosts, whereas CFS achieves comparable responsiveness as an emergent side effect of tasks that block often having low vruntime. Android layers power-awareness on top of the same fairness core, showing how CFS’s clean abstraction (a red-black tree of weighted tasks) can be extended without redesigning the fairness model itself.

Troubleshooting and Diagnostics

High context-switch rate hurting throughput:

vmstat 1
pidstat -w 1

If cs (context switches) is unusually high relative to workload, check whether sched_min_granularity_ns is too low for the workload, or whether too many short-lived threads are being spawned.

Interactive lag under heavy background load: Move batch workloads to SCHED_BATCH or SCHED_IDLE:

chrt -b 0 -p <pid>   # SCHED_BATCH — disables wakeup preemption, better throughput
chrt -i 0 -p <pid>   # SCHED_IDLE — only runs when nothing else wants the CPU

Container getting throttled despite “idle” host:

cat /sys/fs/cgroup/<container>/cpu.stat

Check nr_throttled and throttled_usec — these indicate the cgroup hit its cpu.max quota, a bandwidth limit independent of fairness weighting.

Best Practices

• Use nice values for lightweight relative prioritization of trusted processes on a single-user system.
• Use cgroup cpu.weight for fairness between services or containers, and cpu.max only when you need a hard ceiling (e.g., preventing one tenant from starving others in a shared environment).
• Don’t fight CFS’s fairness model with manual CPU pinning unless you have a specific latency or cache-locality reason — load balancing usually does a good job automatically.
• For genuinely latency-critical workloads, don’t rely on tuning CFS parameters — use SCHED_FIFO/SCHED_DEADLINE with proper CPU isolation instead.

Summary

The Completely Fair Scheduler is Linux’s default CPU scheduler for ordinary processes, and its defining trait is architectural simplicity: rather than juggling priority queues and interactivity heuristics, it tracks each task’s virtual runtime against an idealized fair-share baseline and always runs whoever has fallen furthest behind. Implemented with a red-black tree for efficiency, extended with cgroup-based hierarchical fairness for containers, and layered with power-awareness on mobile devices, CFS demonstrates how a mathematically principled core idea can scale from embedded devices to massive multi-socket servers without needing constant special-casing.

FAQs

Is CFS still the default scheduler in the latest Linux kernels? As of kernel 6.6 (2023), Linux introduced EEVDF (Earliest Eligible Virtual Deadline First) as the new algorithm for the SCHED_NORMAL class, gradually superseding classic CFS. It keeps the same weighted-fairness philosophy but refines task ordering with eligibility times and virtual deadlines to reduce latency outliers. Many distributions have already switched to it by default.

Does “completely fair” mean every process gets identical CPU time? No — it means every process gets a share of CPU proportional to its weight (from nice value or cgroup settings), not an equal share. Two processes with equal weight will converge to equal shares over time.

Can CFS be disabled or replaced? The Linux scheduler framework is pluggable at the class level; alternative out-of-tree schedulers exist (e.g., MuQSS, BORE patches), but replacing CFS/EEVDF entirely requires a custom kernel build.

Does CFS affect I/O scheduling too? No — CFS is purely a CPU scheduler. I/O scheduling is handled separately by block-layer I/O schedulers like mq-deadline, bfq, or kyber.

References

• Documentation/scheduler/sched-design-CFS.rst in the Linux kernel source tree
• Linux kernel source: kernel/sched/fair.c, kernel/sched/core.c
• man 7 sched manual page
• LWN.net: “Reworking the CFS load balancer” and related scheduler coverage
• Linux Weekly News coverage of EEVDF merge (kernel 6.6 changelog)