Process Scheduler
CFS red-black tree, SCHED_DEADLINE EDF, run queues, load balancing, and preemption — the kernel scheduler dissected.
Subsystem Overview
The Linux scheduler is a modular, multi-class system. Each task belongs to a scheduling class — SCHED_DEADLINE, SCHED_FIFO/RR (real-time), or SCHED_NORMAL/BATCH/IDLE (fair) — checked in priority order on every scheduling decision. The Completely Fair Scheduler (CFS) handles the vast majority of tasks using a virtual runtime (vruntime) metric to approximate ideal CPU sharing.
CFS maintains a per-CPU red-black tree of runnable tasks keyed by vruntime. The leftmost node is always the next task to run. When a task runs, its vruntime advances proportionally to its weight (derived from nice value); lower-priority tasks accumulate vruntime faster, ensuring they are eventually preempted by higher-priority ones that have fallen behind.
Linux 7.2 extended SCHED_DEADLINE with group scheduling support, allowing deadline tasks to be organised into cgroups with aggregate bandwidth enforcement. The scheduler tick was also refactored to reduce timer overhead on tickless (NOHZ) kernels running latency-sensitive workloads.
// scheduling policies — sched_setscheduler() values
Diagrams
// interactive · click nodes to explore
CFS Red-Black Tree
Per-CPU runqueue rb-tree keyed by vruntime. Leftmost node is always the next task to schedule.
Scheduling Class Chain
Priority-ordered class vtable: DEADLINE → RT → CFS → IDLE. Each class is checked in turn.
Load Balance Domains
NUMA → MC → SMT domain hierarchy. load_balance() migrates tasks from busiest to idlest group.
Key Concepts
vruntime
Virtual runtime — the CFS fairness metric. Tracks how much CPU time a task has consumed, weighted by its priority. A task with nice -20 accumulates vruntime ~10× slower than a nice +19 task. The scheduler always picks the task with the smallest vruntime from the red-black tree.
sched_entity / sched_class
sched_entity embeds the vruntime, load weight, and rb_node for CFS. sched_class is a vtable of function pointers (enqueue_task, dequeue_task, pick_next_task, etc.) that each scheduling policy implements. Classes are checked in priority order: deadline → rt → fair → idle.
Run Queue (rq)
Per-CPU data structure (struct rq) holding the CFS rb-tree, RT priority array, deadline rb-tree, current task pointer, load statistics, and the scheduler clock. All scheduling decisions are made with the rq lock held.
SCHED_DEADLINE
Earliest Deadline First (EDF) real-time class. Each task declares a runtime budget and a period; the kernel guarantees the budget is available within each period. Uses CBS (Constant Bandwidth Server) to prevent overrun. In 7.2, extended to support cgroup-level bandwidth aggregation.
Load Balancing
Periodic and idle-triggered migration of tasks between CPUs to equalise load. The scheduler builds a domain hierarchy (SMT → MC → NUMA) and migrates tasks from the busiest group to the idlest. Controlled by sched_domain flags and load_balance() in kernel/sched/fair.c.
Preemption & Scheduler Tick
The scheduler tick (triggered by the timer interrupt at CONFIG_HZ) updates vruntime, checks if the current task should be preempted (TIF_NEED_RESCHED), and drives load balancing. NOHZ_FULL suppresses the tick on CPUs running a single task, reducing OS jitter for HPC and RT workloads.
Source References
// kernel/sched/ · annotated entry points
Linux 7.2 Changes
// recent kernel/sched/ commits