CFS Scheduler Internals: A Deep Dive into Linux Completely Fair Scheduler

Introduction: Why CFS Matters

Every process running on a Linux system—from your terminal shell to a high-frequency trading engine—depends on one critical kernel component: the scheduler. Since Linux 2.6.23 (2007), the Completely Fair Scheduler (CFS) has been the default process scheduler for regular (SCHED_NORMAL) tasks. Understanding CFS internals is essential for any systems engineer, kernel developer, or performance analyst who wants to optimize latency-sensitive workloads, debug scheduling anomalies, or simply understand how Linux achieves the illusion of parallelism on finite CPU cores.

This article takes you deep into the CFS architecture: its virtual runtime (vruntime) model, red-black tree task selection, group scheduling with cgroups, NUMA-aware load balancing, and practical tuning parameters. We'll examine real kernel code snippets and explore how modern features like sched_ext in Linux 6.12+ are reshaping scheduler extensibility.

1. The CFS Model: Virtual Runtime at Its Core

CFS is built on a deceptively simple idea: each task's "fair share" of CPU time should be proportional to its weight (priority). The scheduler tracks a virtual runtime (vruntime) for every task—this represents how much CPU time a task has consumed, adjusted by its priority weight.

The fundamental equation is:

delta_vruntime = delta_exec × (NICE_0_LOAD / weight)

Where NICE_0_LOAD is the baseline weight for nice value 0 (1024), and weight is derived from the task's nice value via the sched_prio_to_weight array. A higher-priority task (lower nice value) accumulates vruntime more slowly, so it gets selected for execution sooner—it's been "unfair" less.

In the kernel source, vruntime is stored per-task in struct sched_entity:

struct sched_entity {
    struct load_weight  load;        /* for load-balancing */
    struct rb_node      run_node;    /* rbtree node */
    u64                 vruntime;    /* the heart of CFS */
    u64                 exec_start;  /* clockstamp when execution began */
    u64                 sum_exec_runtime; /* total on-CPU time */
    u64                 prev_sum_exec_runtime;
    /* ... */
};

This vruntime is monotonic per-task and is stored in nanoseconds (though internally it uses the sched_clock() which may be the TSC, jiffies-based, or monotonic raw clock depending on what the architecture provides).

2. The Red-Black Tree: O(log n) Task Selection

CFS organizes runnable tasks in a red-black tree (rbtree) keyed by each task's vruntime. This is one of CFS's key innovations over the O(1) scheduler it replaced—instead of iterating over fixed-priority arrays, CFS picks the leftmost node as the next task, achieving O(1) for selection (staged through the __pick_first_entity() macro) and O(log n) for insertion/deletion.

Key operations:

• Pick next: Leftmost node in the rbtree = smallest vruntime = most underserved task. The cached pointer cfs_rq->next/last/skip variables allow CFS to remember the previously scheduled task if it needs preemption-related logic.
• Enqueue: Called when a task becomes runnable. The task is inserted into the rbtree and a scheduler tick may set TIF_NEED_RESCHED on the currently running task if the newly enqueued task has a lower vruntime.
• Dequeue: Called when a task blocks (sleeps), exits, or is migrated. The task is removed from the rbtree.
• Repick: Called when the scheduler must explicitly decide if the current task should be preempted by the leftmost task.

Preemption logic (check_preempt_tick): When the currently running task's ideal runtime (based on its share of the current scheduling period sched_period) is exceeded, and a more eligible task exists, resched_curr() is called. The "ideal runtime" calculation ensures fairness even with variable task counts:

sched_period = nr_running > 8 ? sched_latency * (nr_running / 8) : sched_latency

Where sched_latency defaults to 24ms (configurable via kernel.sched_latency_ns).

3. Scheduling Granularity and the Scheduling Period

Two tunable parameters govern CFS scheduling behavior:

Parameter	Default	Meaning
sched_latency_ns	24,000,000 ns (24ms)	Target latency. All runnable tasks should be serviced at least once within this window.
sched_min_granularity_ns	3,000,000 ns (3ms)	Minimum time slice per task. Prevents excessive switching regardless of task count.
sched_wakeup_granularity_ns	4,000,000 ns (4ms)	Threshold for a waking task to preempt the current task.

The minimum time slice for each task is calculated as

min_gran = max(sched_latency / nr_running, sched_min_granularity)

With nr_running tasks, each task receives at least min_gran nanoseconds before being preempted. This ensures that even with many runnable tasks, switching overhead remains bounded.

4. nice Values and Priority Weights

Linux maps the user-facing nice value (-20 to 19) to a weight via a geometric sequence. Each +1 nice level means approximately 10% less CPU share; each -1 means ~10% more:

nice	Weight	Approximate % of CPU (vs nice 0 equal task)
-20	88761	~85% more CPU share per unit time
-10	15861	~39% more
0	1024	Baseline
5	335	~3× less than baseline
10	110	~9× less
19	15	~68× less

This geometric progression ensures that the ratio of weights between adjacent nice levels is approximately 1.25:1. This property is critical because CFS's normalization of vruntime by weight means tasks at all nice levels get proportional CFS scheduling—not linearly proportional to nice values.

5. Group Scheduling with Cgroups

CFS extends fairness to groups of tasks via cgroup v1 cpu controller or cgroup v2 CPU bandwidth limits. Each cgroup has its own cfs_rq (CFS runqueue) and shares CPU via the same vruntime mechanism at the group level.

This creates a two-level hierarchy:

1. Group selection: CFS selects the group whose se-entity has the smallest vruntime at the root-level rbtree.
2. Task selection within group: The selected group's internal CFS rbtree then picks its own leftmost task.

Key cgroup CPU knobs:

• cpu.shares (v1) / cpu.weight (v2): Relative weight among sibling cgroups (default 1024).
• cpu.cfs_quota_us / cpu.cfs_period_us: Hard bandwidth cap (e.g., quota=50000, period=100000 means 0.5 CPU max).
• cpu.idle (v2): New in Linux 6.12, reduces scheduling overhead for low-priority idle-class cgroups.

The "shares" mechanism is proportional-share (like CFS task weights); "quota/period" is a hard ceiling (like a leaky bucket):

# Limit a cgroup to 2 CPUs of capacity
echo 200000 > /sys/fs/cgroup/myapp/cpu.max    # 200ms per 100ms period = 2 CPU cores

6. Load Balancing Across CPU Cores

On multi-core systems, CFS runqueues are per-CPU. The load balancer migrates tasks across runqueues to balance active load. This is implemented in kernel/sched/fair.c via the load_balance() function and the SD (sched domain) hierarchy.

Modern NUMA-aware load balancing works in layers:

• Busy balancing (CONFIG_NUMA_BALANCING): Periodic migration of tasks to NUMA nodes closer to their memory.
• Idle balancing: When a CPU goes idle, it immediately steals work from busy runqueues.
• Periodic balancing: Timer-driven scanning of all runqueues on each tick—comparable across scheduling domains (MC, DIE, NUMA levels).
• Wake_affine: On task wakeup, attempts to place the task on the same CPU it last ran on (or a nearby idle domain) to preserve cache warmth.

The sched domain topology on a modern server might look like:

NUMA Level (distance: 10 local, 20 remote)
  └── DIE Level (shared L3 cache)
        └── MC Level (shared L2, SMT siblings)
              └── SMT Level (logical CPUs sharing physical core)

Each level has its own sched_domain with explicit interval—higher (more distant) levels rebalance less frequently because migration costs more. CFS computes "imbalance" in terms of runnable task count weighted by load (tracked in sched_avg running averages for each task's demand).

7. Sched Stats: PELT and Utilization Estimation

CFS relies heavily on the Per-Entity Load Tracking (PELT) algorithm introduced in 2016 (Linus accepts sched/avg rewrite). Pelt computes per-task and per-runqueue load_avg and util_avg using an infinite-impulse response (IIR) filter with a 32ms half-life:

// Simplified from kernel/sched/pelt.c:
static __always_inline void
___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
{
    u32 frag = sched_avg_frac(sa);
    u64 period = PELT_PERIOD;
    
    sa->load_sum += load * period;
    sa->period_contrib = frag;
    sa->load_avg = sa->load_sum / PELT_DIVIDER;
}

PELT serves three critical purposes:

1. Load balancer decisions: Determines how "busy" a runqueue is, compared to others.
2. CPU frequency scaling (CPUFreq): The schedutil governor uses Pelt utilization to set P-state frequency proactively.
3. Energy-Aware Scheduling (EAS): On ARM big.LITTLE, Pelt utilization across CPUs informs energy-optimal task placement.

Pelt was augmented in Linux 6.6+ with a util_est (utilization estimate) subsystem that uses exponential moving average of task runnable vs. running time. This gives a faster-rising utilization signal for bursty workloads, helping frequency scaling and task placement respond within 1-2 scheduling ticks instead of Pelt's 32ms half-life.

8. Scheduler Tick and Preemption Points

In tickless kernels (CONFIG_NO_HZ_FULL), CFS supports adaptive tick—when a runqueue has only one runnable task, the scheduler tick is suppressed entirely to avoid unnecessary timer interrupts on CPU-isolated threads. The next "wake-up" point is set by hrtimer_forward() when the next enqueue or preemption threshold arrives.

Preemption can happen at these points:

• Tick-driven preemption: In task_tick_fair(), if the current task has exceeded its ideal_runtime, resched_curr() sets the TIF_NEED_RESCHED flag.
• Wakeup preemption: In check_preempt_wakeup(), if a newly woken task's vruntime is sufficiently lower than the current task's (by wakeup_granularity), preemption occurs immediately on the syscall/irq return to userspace.
• Cooperative preemption: Explicit preemption at the next preempt point in kernel code (cond_resched(), might_sleep()).
• Tickless resumes: When a runqueue transitions from 0 to 1 runnable tasks, the tick is re-enabled; when it transitions from 1 to 2, a preemption check runs inside enqueue_task_fair().

9. The sched_class Hierarchy

CFS resides in one of five sched_class entries in a linked list (in priority order):

stop_sched_class (highest, CPU hotplug/migration)
  -> dl_sched_class (SCHED_DEADLINE, EDF-based)
      -> rt_sched_class (SCHED_FIFO/SCHED_RR)
          -gt; fair_sched_class (SCHED_NORMAL/SCHED_BATCH/SCHED_IDLE)  ← CFS
              -> idle_sched_class (swaps in the per-CPU swapper thread)

Each class has a pick_next_task() method. The scheduler iterates from stop_sched_class down through fair_sched_class—the first class that returns a task wins. This is why real-time tasks (SCHED_RR, SCHED_FIFO) always preempt CFS tasks, and SCHED_DEADLINE preempts even RT tasks.

CFS-specific scheduling policies:

• SCHED_NORMAL: Standard CFS scheduling. Interactive-ness heuristic was removed; CFS is now purely proportional.
• SCHED_BATCH: Same algorithm but with wakeup_granularity set significantly higher—batch jobs don't aggressively preempt. Ideal for long-running compute workloads that want minimal cache disruption.
• SCHED_IDLE: Tasks at the lowest priority band; only run when the CPU would otherwise be idle. Weight < 1 (~1/32 of SCHED_NORMAL).

10. Tuning CFS for Production Workloads

10.1 Latency-Sensitive Workloads (Trading, Real-Time Audio)

Reduce sched_min_granularity_ns to shorten slices and lower dispatch latency:

sysctl -w kernel.sched_min_granularity_ns=1000000   # 1ms slices
sysctl -w kernel.sched_wakeup_granularity_ns=500000  # aggressive preempt

Use SCHED_FIFO or SCHED_RR with sched_setscheduler() for real-time threads. For latency monitoring, use perf sched latency or trace sched_switch tracepoints.

10.2 Throughput-Oriented Workloads (Analytics Batch, Compilers)

Increase granularity and disable aggressive preemption; ensure SCHED_BATCH:

chrt -b 0 $SHELL   # SCHED_BATCH for current shell tree
nice -n 19 make -j$(nproc)   # nice'd batch compile

You can also disable CONFIG_HZ_PERIODIC tick overhead by enabling CONFIG_NO_HZ_FULL on dedicated CPU cores.

10.3 Container Density Tuning (Kubernetes / Docker)

Cgroup CPU quotas vs. shares: quota is a hard ceiling; shares acts for proportional distribution during contention. In Kubernetes, set CPU requests as shares and CPU limits as quota:

# Pod manifest snippet
resources:
  requests:
    cpu: "500m"   # becomes cpu.shares = 512
  limits:
    cpu: "2000m"  # becomes cpu.max = 200000/100000

Use cpu.idle (v2) to ensure daemon-set and monitoring pods always run with minimal scheduling overhead.

11. sched_ext: The Future of Extensible Scheduling

Linux 6.12 (December 2024) introduced sched_ext (scheduler extensibility), allowing BPF-based user-defined schedulers to override the default CFS/RT hierarchy.

The primary model: a BPF program registers as a custom sched_class, and at every scheduling event (task enqueue, dequeue, tick, pick_next_task, etc.), BPF callbacks can make local CPU placement decisions. This unlocks decades of scheduler research to be deployed without kernel recompilation.

An example: scx_rustland (a BPF+DTMC-pick heuristic) or scx_rlq (run-length quanta for game engines) can be loaded with one line:

scx_rustland # BPF scheduler replaces CFS on all CPUs
# or for selective CPUs:
scx_layered --cpumask 0-7    # layered scheduler on cores 0-7 only

sched_ext is significant because:

1. It replaces the need for out-of-tree patches (e.g., PDS-MQ from Valve).
2. It allows rapid iteration—scheduler logic lives in BPF maps and C/Rust structs.
3. Production schedulers can be installed/uninstalled via bpftool at runtime.
4. Power-of-two choices, lottery scheduling, and work-conserving/nc-conserving policies are now feasible without kernel hacking.

12. Monitoring and Debugging CFS Behavior

Essential tools for CFS observability:

Tool	What It Shows
perf sched record + perf sched latency	Per-task scheduling latency histogram (wake-to-run delay in µs).
perf stat -e 'sched:*'	ftrace tracepoint counters for enqueues, dequeues, migrations.
/proc/<pid>/sched	Per-task vruntime, nr_switches, avg_atom (avg slice), nr_migrations.
/sys/kernel/debug/sched/debug	Per-CPU runqueue state, load averages, Pelt averages.
bpftrace -e 'tracepoint:sched:sched_switch { ... }'	Custom in-kernel latency probes.

Quick diagnostic checklist:

1. High scheduling latency? Check /proc/schedstat for runqueue lengths and compare to sched_latency_ns.
2. Stuck tasks? Verify dmesg | grep -i "hung_task" and check sched_rt_runtime_us.
3. Wrong CPU affinity? Check taskset -p <pid>, IRQ affinity, NUMA locality.
4. Thundering herd in thread pool? Use SCHED_IDLE for non-critical background tasks to avoid caches thrash.

13. Conclusion

CFS remains one of the most elegant designs in OS schedulers—a blend of theoretical rigor and engineering pragmatism. Its vruntime model provides proportional fairness with O(log n) complexity. Modern additions like Pelt, schedutil integration, group scheduling through cgroups, and now sched_ext extensibility have kept it relevant for both classical servers and bleeding-edge workloads.

For practitioners: know your scheduling parameters, match them to your workload class, and leverage sched_ext when the default isn't enough. The scheduler is no longer just a kernel black box—it's an API your infrastructure can optimize directly.

References: Linux kernel source mm/sched/fair.c, sched/pelt.c; "The Completely Fair Scheduler" (Ingo Molnar, 2007); kernel Documentation/scheduler/; scx wiki at kernel.org/doc/html/latest/scheduler/sched-ext.html.