Chapter 4: CPU Scheduling and Process Placement

Updated

October 31, 2026

Chapter 4: CPU Scheduling and Process Placement

The Linux CPU scheduler is responsible for allocating processor time across competing threads, ensuring fair resource distribution while minimizing context switch latency and maximizing cache locality. In modern Linux (kernel 6.6+), the scheduling subsystem evolved from the classic Completely Fair Scheduler (CFS) to the Earliest Eligible Virtual Deadline First (EEVDF) scheduler, refining latency guarantees for interactive and latency-sensitive workloads.

This chapter details the internal mechanics of Linux CPU scheduling, real-time priorities, core affinity, task isolation, and cross-NUMA load balancing.

The Completely Fair Scheduler: Internal Mechanics

The fundamental goal of CFS is to simulate an “ideal multi-tasking CPU” on real hardware:

  • In an ideal system with \(N\) runnable tasks, every task would run simultaneously at \(\frac{1}{N}\) speed.
  • On real hardware with discrete cores, CFS tracks how much time each task has consumed and picks the task that has received the least CPU time.
  • Red-Black Tree Runqueues: CFS maintains a per-CPU time-ordered red-black tree (struct cfs_rq). The leftmost node in the tree is the task with the smallest virtual runtime; it is chosen for execution next (\(O(1)\) pick, \(O(\log N)\) insert).
┌────────────────────────────────────────────────────────────────────────┐
│                   CFS / EEVDF RUNQUEUE ARCHITECTURE                    │
│                                                                        │
│                      Per-CPU Runqueue (cfs_rq)                         │
│                                  │                                     │
│                                  ▼                                     │
│                            [ Root Node ]                               │
│                            vruntime: 12ms                              │
│                            /           \                               │
│             [ Left Node ]                 [ Right Node ]               │
│             vruntime: 8ms                 vruntime: 18ms               │
│                   /                                                    │
│        [ Leftmost Candidate ] ◄── Selected Next by Scheduler           │
│        vruntime: 4ms                                                   │
└────────────────────────────────────────────────────────────────────────┘

The Transition to EEVDF (Linux 6.6+)

While CFS ensured proportional throughput fairness over longer windows, it often penalized latency-sensitive tasks that slept frequently. EEVDF addresses this by introducing: - Virtual Time: Tracks fair progress. - Lag: The difference between the time a task should have received according to its weight and the actual time it consumed. - Virtual Deadline: When a task’s allocated time slice must finish. EEVDF selects the eligible task with the earliest virtual deadline, providing dramatically more deterministic wakeup latency.

Virtual Runtime, Timeslices and Fairness

  • vruntime (Virtual Runtime): Measures the execution time consumed by a task, scaled inversely by its nice level (priority weight). Tasks with higher priority (lower nice value) accumulate vruntime more slowly, allowing them to run longer and more frequently before falling behind in the red-black tree.
  • Timeslice Calculation: The dynamic slice assigned to a task is calculated based on sysctl_sched_latency divided by the number of active runnable tasks, bounded by sysctl_sched_min_granularity.
# View active scheduler configuration knobs
sysctl kernel.sched_latency_ns 2>/dev/null || sysctl kernel.sched_base_slice_ns 2>/dev/null

Real-Time Scheduling: SCHED_FIFO, SCHED_RR, SCHED_DEADLINE

For workloads that cannot tolerate the dynamic timeslicing of CFS/EEVDF, Linux provides real-time scheduling classes that strictly preempt normal tasks:

Class Policy Preemption Behavior Target Use Case
SCHED_FIFO First-In, First-Out Runs until it voluntarily yields, blocks on I/O, or is preempted by a higher-priority RT task. No timeslicing. High-frequency trading, audio DSP, industrial robotics.
SCHED_RR Round-Robin Similar to FIFO, but preempted when its fixed round-robin timeslice expires if equal-priority tasks exist. Real-time multi-threaded pipelines.
SCHED_DEADLINE Earliest Deadline First (EDF) Constant Bandwidth Server (CBS). Specified by runtime, deadline, and period. Hard real-time audio/video streaming, avionics. 
# Run a process with real-time FIFO priority 80
sudo chrt --fifo 80 ./latency-critical-worker

# Inspect scheduling policy and priority of an existing PID
chrt -p <PID>

[!CAUTION] A misbehaving SCHED_FIFO thread that enters an infinite busy-wait loop will starve all normal userspace processes and kernel background threads on that core, freezing system management unless kernel.sched_rt_runtime_us bandwidth throttling is enabled.

CPU Affinity, Isolation and Task Migration

By default, the scheduler migrates tasks between CPU cores to balance load. However, task migration flushes private L1/L2 caches and forces remote memory access across interconnects.

Pinning Tasks with CPU Affinity

Using sched_setaffinity or taskset, an engineer can bind a process to a dedicated set of CPU cores:

# Launch an application bound strictly to physical cores 2 and 3
taskset -c 2,3 ./database-engine

# Query existing core affinity of a running PID
taskset -cp <PID>

Full Core Isolation (isolcpus & nohz_full)

For deterministic microsecond latency, physical cores can be completely isolated from the standard scheduler and kernel housekeeping:

  1. isolcpus=24-31: Removes cores 24 through 31 from the general CFS load-balancing domain. No standard tasks will be scheduled there unless explicitly pinned with taskset.
  2. nohz_full=24-31: Stops the scheduler timer tick on isolated cores whenever exactly one task is runnable, eliminating periodic 1000Hz timer interrupt interruptions.
  3. rcu_nocbs=24-31: Offloads Read-Copy Update (RCU) callback processing to housekeeping cores.

Load Balancing Across NUMA Nodes

The Linux scheduler organizes CPU cores into a hierarchical tree of Scheduling Domains (sched_domain): - SMT Domain (hyperthreads on the same core, shared L1/L2) - MC Domain (cores sharing L3 cache) - NUMA Domain (cores sharing local memory controller) - System Domain (interconnect hops to remote sockets)

Load balancing occurs frequently within SMT and MC domains because the cache penalty of moving a thread to an adjacent core sharing the same L3 cache is negligible. Conversely, cross-NUMA balancing is deferred and amortized because moving a thread across sockets forces all its existing memory pages to be accessed remotely over inter-socket buses.