--- title: Scheduler url: https://doc.liz6.com/en/linux-kernel/01-process-management/02-scheduler locale: en area: linux-kernel tags: - linux-kernel - process-management date: 2026-06-30 modified: 2026-07-16 description: 'Coverage: CFS (vruntime/Red-Black Tree) → EEVDF (6.6+) → Scheduling Class Architecture → Load Balancing → Preemption Kernel Versions: 2.6 ~ 6.x, highlighting the CFS→EEVDF transition' --- # Scheduler > Coverage: CFS (vruntime/Red-Black Tree) → EEVDF (6.6+) → Scheduling Class Architecture → Load Balancing → Preemption > Kernel Versions: 2.6 ~ 6.x, highlighting the CFS→EEVDF transition ## Overview The scheduler is one of the most frequently called subsystems in the kernel. Every `schedule()` call must answer one question: **Who runs next?** This question seems simple, but balancing "interactive responsiveness, high throughput, fairness, energy efficiency, and multi-core scalability" is extremely complex. Linux has gone through three eras of scheduling: - **2.4**: O(n) scheduler — iterates through all processes to select the highest priority - **2.6 ~ 6.5**: CFS (Completely Fair Scheduler) — Red-Black Tree driven by vruntime - **6.6+**: EEVDF — Earliest Eligible Virtual Deadline First This article focuses on the design principles of CFS and EEVDF, tracing key code paths. --- ## Scheduling Class Architecture The Linux scheduler is not a single algorithm, but a **stackable scheduling class** architecture: Scheduling Class Framework: How schedule() selects the next process schedule() __schedule() pick_next_task() for_each_class(class) — Traverse scheduling classes from high to low p = class->pick_next_task(rq) if (p) return p → Stop traversal upon match, hand over this process Priority: stop → dl → rt → fair(CFS/EEVDF) → idle Stackable scheduling classes are the most elegant architectural decision: Any class returning non-null stops the search; idle_sched_class acts as a fallback, ensuring there is always a process to run. Priority from high to low: | Scheduling Class | Policy | Typical Scenario | |--------|------|---------| | `stop_sched_class` | Highest priority, preempts everything | CPU hotplug, migration | | `dl_sched_class` | Deadline (EDF + CBS) | Hard real-time tasks | | `rt_sched_class` | POSIX RT (FIFO / RR) | Soft real-time, `chrt -f` | | `fair_sched_class` | CFS / EEVDF | All normal processes | | `idle_sched_class` | Runs only when no other tasks exist | Idle task (PID 0 per-CPU) | ```c // kernel/sched/sched.h struct sched_class { const struct sched_class *next; // Linked list void (*enqueue_task)(struct rq *rq, struct task_struct *p, int flags); void (*dequeue_task)(struct rq *rq, struct task_struct *p, int flags); void (*yield_task)(struct rq *rq); void (*wakeup_preempt)(struct rq *rq, struct task_struct *p, int flags); struct task_struct *(*pick_next_task)(struct rq *rq); void (*put_prev_task)(struct rq *rq, struct task_struct *p); void (*set_cpus_allowed)(struct task_struct *p, ...); void (*update_curr)(struct rq *rq); // ← Core function to update vruntime void (*task_tick)(struct rq *rq, struct task_struct *p, int queued); void (*task_fork)(struct task_struct *p); // fork initialization void (*task_dead)(struct task_struct *p); // exit cleanup void (*switched_from)(struct rq *rq, struct task_struct *p); void (*switched_to)(struct rq *rq, struct task_struct *p); }; ``` The stackable design of scheduling classes is one of the most elegant architectural decisions in the Linux scheduler: real-time and normal tasks share the same `schedule()` entry point, requiring no special handling. If any scheduling class returns NULL, the framework asks the next class. Finally, `idle_sched_class` ensures there is always a process to run. --- ## Core Data Structures ### runqueue (struct rq) ```c // kernel/sched/sched.h struct rq { raw_spinlock_t __lock; // Protects the entire runqueue unsigned int nr_running; // Number of runnable processes (excluding idle) unsigned long nr_switches; // Counter for scheduling events struct cfs_rq cfs; // CFS runqueue struct rt_rq rt; // RT runqueue struct dl_rq dl; // Deadline runqueue struct task_struct *curr; // Currently running process struct task_struct *idle; // Idle task for this CPU struct task_struct *stop; // Stop task for this CPU int cpu; // CPU ID unsigned long clock; // rq internal clock unsigned long clock_task; // Actual execution time (excluding IRQ/softirq) struct sched_domain *sd; // Scheduling domain (load balancing) }; ``` Each CPU has its own `struct rq`. The lock granularity is per-rq, meaning scheduling decisions only require locking **this CPU**'s lock—this is key to the scheduler's scalability on systems with many cores. `raw_spinlock_t` means interrupts must be disabled when acquiring this lock, because the scheduler tick can trigger at any time. ### sched_entity — Scheduling Entity ```c // include/linux/sched.h struct sched_entity { // Embedded within task_struct struct load_weight load; // Weight (converted from nice value) unsigned long runnable_weight; struct rb_node run_node; // CFS Red-Black Tree node unsigned int on_rq; // Whether in runqueue u64 exec_start; // Start time of current execution u64 sum_exec_runtime; // Cumulative physical execution time u64 vruntime; // Virtual run time (sorting key for CFS/EEVDF) u64 prev_sum_exec_runtime; // EEVDF additions (6.6+) u64 deadline; // Virtual deadline u64 min_vruntime; // Minimum vruntime in current cfs_rq u64 min_deadline; // Earliest deadline in current cfs_rq u64 vlag; // Lag value — used to catch up when woken up struct sched_entity *parent; struct cfs_rq *cfs_rq; // Associated cfs_rq (group scheduling) struct cfs_rq *my_q; // If this is a group se, its child cfs_rq }; ``` --- ## CFS: Fairness Driven by vruntime ### Core Idea CFS does not allocate CPU by time slices, but sorts by **virtual run time (vruntime)**: ``` vruntime = Physical Execution Time × (NICE_0_LOAD / weight_of_process) ``` The lower the nice value (higher priority), the larger the `weight` → The same physical time accumulates less vruntime → Positioned further left in the Red-Black Tree → Selected earlier. Essence: CFS pursues **vruntime convergence**. All processes' vruntime should converge; prioritizing the process with the smallest vruntime compensates for the process that has "owed the most CPU time." ### nice → weight Mapping ```c // kernel/sched/core.c const int sched_prio_to_weight[40] = { /* -20 */ 88761, 71755, 56483, 46273, 36291, /* -15 */ 29154, 23254, 18705, 14949, 11916, /* -10 */ 9548, 7620, 6100, 4904, 3906, /* -5 */ 3121, 2501, 1991, 1586, 1277, /* 0 */ 1024, 820, 655, 526, 423, /* 5 */ 335, 272, 215, 172, 137, /* 10 */ 110, 87, 70, 56, 45, /* 15 */ 36, 29, 23, 18, 15, }; ``` Key property: For every one level decrease in nice value, weight increases by approximately 25%. This means a nice -20 process gets about 87 times the CPU time of a nice 0 process (not a simple linear relationship). This exponential decay design comes from the original CFS paper—it ensures consistent fairness gaps between adjacent nice values. ### Key Functions ```c // kernel/sched/fair.c // Update vruntime (called on every tick / enqueue / dequeue / put_prev) static void update_curr(struct cfs_rq *cfs_rq) { struct sched_entity *curr = cfs_rq->curr; u64 now = rq_clock_task(rq_of(cfs_rq)); u64 delta_exec; if (unlikely(!curr)) return; delta_exec = now - curr->exec_start; if (unlikely((s64)delta_exec <= 0)) // Defense: clock should not go backward return; curr->exec_start = now; curr->sum_exec_runtime += delta_exec; // Core conversion: Physical time → Virtual time curr->vruntime += calc_delta_fair(delta_exec, curr); } // Pick next: Leftmost node in Red-Black Tree static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq) { struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline); if (!left) return NULL; return rb_entry(left, struct sched_entity, run_node); } ``` `calc_delta_fair()` implements `delta * (NICE_0_LOAD / weight)`. It uses 128-bit fixed-point arithmetic to avoid overflow and handles precision issues (preventing shrinkage for very small deltas to avoid vruntime stagnation). ### vruntime Boundary Handling The initial vruntime for a new process cannot start from 0—otherwise, a newly forked process would monopolize the CPU for a long time. CFS's approach: ```c // kernel/sched/fair.c: place_entity() static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial) { u64 vruntime = cfs_rq->min_vruntime; // Start from current cfs_rq's min if (initial && sched_feat(START_DEBIT)) // Newly forked process: vruntime += one-time penalty vruntime += sched_vslice(cfs_rq, se); // EEVDF (6.6+): Also set deadline se->deadline = vruntime + calc_delta_fair(se->slice, se); se->vruntime = vruntime; } ``` The penalty returned by `sched_vslice()` is approximately equal to the time slice this process could run for the first time—this ensures the new process is not "poorer" than processes already running, maintaining fairness. ### min_vruntime Tracking ```c // cfs_rq->min_vruntime monotonically increases, tracking the minimum vruntime of all dequeued processes // Updated in update_min_vruntime(): static void update_min_vruntime(struct cfs_rq *cfs_rq) { struct sched_entity *se = __pick_first_entity(cfs_rq); // Take the maximum from all possible sources: // Current process's vruntime // Leftmost node's vruntime in Red-Black Tree (if any) // cfs_rq->curr->vruntime (if exists) u64 vruntime = cfs_rq->min_vruntime; if (se) vruntime = max(vruntime, se->vruntime); if (cfs_rq->curr) vruntime = max(vruntime, cfs_rq->curr->vruntime); cfs_rq->min_vruntime = vruntime; } // min_vruntime never goes backward—this is the key invariant ensuring fairness ``` --- ## EEVDF: The Paradigm Shift in 6.6 ### Why EEVDF is Needed CFS's vruntime sorting is fair in CPU-bound scenarios, but has flaws in **latency-sensitive** scenarios: - A process sleeps for a long time → vruntime becomes extremely low compared to others → Occupies CPU for a long time after being woken up (latency spike) - CFS has no concept of "when it should finish," only "who should run most" - Response latency is unpredictable—sleeping processes may take a long time to get on the CPU (vruntime is low but doesn't guarantee immediate response) EEVDF solves this by introducing **deadlines**. Each entity calculates an **eligible time** (when it is eligible to run) and a **deadline** (expected completion time) upon enqueue. The scheduler sorts by deadline but only selects from eligible processes. ### EEVDF Core Algorithm ```c // kernel/sched/fair.c (6.6+) // Request time (request): scale the slice by weight static u64 calc_se_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) { // se->slice = sysctl_sched_base_slice × (se->load.weight / cfs_rq->load.weight) // Processes with higher weights get larger slices → deadlines further away → less frequent interruption return calc_delta_fair(sysctl_sched_base_slice, se); } // Enqueue: Calculate deadline static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial) { u64 vruntime = se->vruntime; // 1. Eligible time: lag compensation // vlag = average vruntime - own vruntime // If vlag > 0 (own vruntime lags behind average) → Prioritized for eligibility // If vlag < 0 (own vruntime leads average) → Delay eligibility se->vlag = avg_vruntime(cfs_rq) - se->vruntime; // 2. deadline = vruntime + slice se->slice = calc_se_slice(cfs_rq, se); se->deadline = se->vruntime + se->slice; } // pick_next: Select the earliest deadline from eligible entities static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) { struct sched_entity *se = __pick_first_entity(cfs_rq); // Smallest vruntime struct sched_entity *best = NULL; // Linear scan of Red-Black Tree (sorted by vruntime) until finding the smallest deadline among all eligible entities while (se) { // Eligible: vlag > 0 → own vruntime < average → Eligible for CPU time if (entity_eligible(cfs_rq, se)) { if (!best || se->deadline < best->deadline) best = se; // Smallest deadline but smaller vruntime might still be later → Continue scan if (best && best->deadline < se->vruntime) break; // Later entities have larger vruntime, deadline cannot be better than best } se = __pick_next_entity(se); // In-order successor in Red-Black Tree } return best ?: __pick_first_entity(cfs_rq); // No one eligible → Select leftmost } ``` Key Differences: | | CFS | EEVDF | |---|---|---| | Selection Criteria | Smallest vruntime | Earliest deadline (from eligible) | | Slept Process Behavior | Monopolizes CPU for long time (extremely low vruntime) | Has lag compensation upon wake-up, but must re-queue after slice expires | | Latency Guarantee | None | Yes (each process has a clear completion deadline) | | Implementation Complexity | Lower | Medium (adds eligibility checks and vlag) | ### Dynamic Adjustment of Slice and Deadline ```c // sysctl_sched_base_slice: Base time slice (default 3ms for EEVDF) // Actual slice per process = base × (weight / cfs_rq_weight) // Processes with higher weights get longer slices → Fewer context switches // If a process yields CPU before slice expires (e.g., blocking on IO): // → vruntime stops growing → vlag increases → Easier to become eligible upon wake-up // • Compensates for interactive "use briefly then wait" patterns ``` ### Lag Compensation Mechanism ```c // Lag: This is the biggest implementation difference between EEVDF and CFS // Definition: lag = avg_vruntime - se->vruntime // lag > 0: Process lags behind average → Should be prioritized // lag < 0: Process leads average → Should wait // Upon wake-up: static int wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se) { // EEVDF: Deadline comparison if (se->deadline < curr->deadline) return 1; // Newly woken process has earlier deadline → Preempt // Additional consideration for vlag boundaries // If new process's lag is much larger than current process's lag → Also preempt // (Prevent starvation of certain processes) return 0; } ``` --- ## Preemption ### Wakeup Preemption ```c // kernel/sched/fair.c: check_preempt_wakeup() static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags) { struct sched_entity *se = &p->se; struct sched_entity *curr = &rq->curr->se; // CFS Old Logic: Preempt only if woken process is "much poorer" than current // wakeup_preempt_entity(curr, se) → calc_delta_fair(gran, se) // Requires woken vruntime to lag by at least granularity amount // EEVDF New Logic (6.6+): // Whoever has earlier deadline → Preempt if (se->deadline < curr->deadline) resched_curr(rq); } ``` ### Tick Preemption ```c // kernel/sched/fair.c: entity_tick() // Triggered by every scheduler tick (CONFIG_HZ, typically 250/500/1000) static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) { unsigned long ideal_runtime = sched_slice(cfs_rq, curr); unsigned long delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime; // 1. Current process has used its fair share of time slice → Set NEED_RESCHED if (delta_exec > ideal_runtime) { resched_curr(rq_of(cfs_rq)); return; } // 2. EEVDF: If there is an eligible entity in Red-Black Tree with earlier deadline than current if (pick_eevdf(cfs_rq) != curr) resched_curr(rq_of(cfs_rq)); } ``` ### NEED_RESCHED and Deferred Scheduling ```c // resched_curr() only sets the TIF_NEED_RESCHED flag // schedule() is not called here — we are in interrupt context! // Actual context switch happens in exit_to_user_mode_loop() before returning to user mode: // // exit_to_user_mode_loop() { // if (ti_work & _TIF_NEED_RESCHED) // schedule(); // } // // Or in preempt_schedule_irq() for preemptible kernel (CONFIG_PREEMPT=y) ``` --- ## Load Balancing ### Scheduling Domain Hierarchy ``` // Typical hierarchy for modern 2-socket AMD EPYC: // SMT (Hyper-threading, L1 shared) < MC (Multi-core, L3 shared) < DIE (Same socket) < NUMA (Cross-socket) // Each layer has its own sched_domain, forming nested CPU masks ``` ```c // kernel/sched/topology.c: Initialized by arch code at boot // x86: arch/x86/kernel/smpboot.c constructs scheduling domain topology // ARM: drivers/base/arch_topology.c obtains from DT/ACPI ``` ### Load Balancing Trigger Times There are four types of balancing: ```c // 1. Idle balance: CPU about to idle → newidle_balance() called in schedule() // → Actively pull tasks from busy CPUs (Fast startup, avoids idle latency) // 2. Periodic balance: scheduler_tick() → trigger_load_balance() // → SCHED_SOFTIRQ → run_rebalance_domains() // → Executed asynchronously by softirq, frequency = 1 / (4 * sched_domain->interval) // 3. Fork/exec balance: wake_up_new_task() → select_task_rq_fair() // → find_idlest_cpu() → Find least busy CPU within scheduling domain // 4. Wake balance: try_to_wake_up() → select_task_rq_fair() // → find_idlest_cpu() or wake_affine() (Prefer wake-up CPU) ``` ### load_balance Implementation ```c // kernel/sched/fair.c: load_balance() static int load_balance(int this_cpu, struct rq *this_rq, struct sched_domain *sd, enum cpu_idle_type idle) { // 1. should_we_balance() — Only perform balancing on the first idle CPU in group (Reduce conflicts) // 2. find_busiest_group() — Find busiest in sd's sched_group linked list // 3. find_busiest_queue() — Find busiest CPU's runqueue in busiest group // 4. detach_tasks() — Detach <= 32 processes from busy rq (sysctl_sched_nr_migrate) // Only detach those allowed to migrate (cpus_allowed, cgroup not pinned, etc.) // 5. attach_tasks() — Attach to this_rq, activate_task() → enqueue_task_fair() for each } ``` --- ## Group Scheduling (CGroup CPU Controller) ```c // Enable: CONFIG_CGROUP_SCHED // Interface: /sys/fs/cgroup/cpu// // cpu.shares — Weight allocation (default 1024) // Groups share CPU proportionally by shares. A=2048, B=1024 → A:B = 2:1 // cpu.cfs_quota_us — Max CPU time within period // cpu.cfs_period_us — Period length (default 100ms) // quota=50000, period=100000 → Max 50% CPU usage ``` Each cgroup corresponds to a `task_group`, containing a `sched_entity` embedded in the parent `cfs_rq`. This se "disguises" itself as a normal process to participate in parent group scheduling. After receiving CPU time, it performs secondary allocation within its own `cfs_rq` based on weights of processes within the group. Group Scheduling Hierarchy: Nested cfs_rq Secondary Allocation of CPU Root cfs_rq se_A weight 2048 · se_B weight 1024 Group A cfs_rq Receives 2/3 CPU Group B cfs_rq Receives 1/3 CPU task1, task2 (Internal competition) task3 Each cgroup corresponds to a task_group; the embedded se disguises as a normal process to participate in parent group scheduling; After receiving CPU time, it performs secondary allocation within its own cfs_rq based on weights of processes within the group. --- ## Debugging and Observation ```bash # Process scheduling statistics (Most critical file) cat /proc//sched # Content: se.sum_exec_runtime, se.vruntime, se.statistics.wait_sum, # nr_switches, nr_voluntary_switches, nr_involuntary_switches # System-level scheduler debug info cat /proc/sched_debug # Contains: Per-CPU cfs_rq stats, nr_running, min_vruntime, Red-Black Tree size # ftrace: Capture scheduling events echo 1 > /sys/kernel/debug/tracing/events/sched/sched_switch/enable echo 1 > /sys/kernel/debug/tracing/events/sched/sched_wakeup/enable echo 1 > /sys/kernel/debug/tracing/events/sched/sched_migrate_task/enable cat /sys/kernel/debug/tracing/trace_pipe | head -50 # bpftrace: Statistics scheduling latency by process bpftrace -e 'kprobe:finish_task_switch { @[comm] = hist(nsecs - @start[tid]); } kprobe:__schedule /args->prev/ { @start[args->prev->pid] = nsecs; }' # Check if EEVDF is enabled grep CONFIG_SCHED_EEVDF /boot/config-$(uname -r) # Kernel cmdline: Debug switches # sched_verbose — More dmesg info # skew_tick=1 — Offset CPU ticks to reduce lock contention ``` --- ## References and Further Reading - **Kernel Documentation**: `Documentation/scheduler/` directory, especially `sched-design-CFS.rst` and `sched-eevdf.rst` - **LWN**: - "EEVDF scheduler design" series (2023, lwn.net/Articles/925371/) - "The EEVDF scheduler" (lwn.net/Articles/940176/) - "CFS group scheduling" (lwn.net/Articles/240474/) - "The multi-queue block and CPU schedulers" (lwn.net/Articles/552451/) - **Source Files**: - `kernel/sched/fair.c` — CFS/EEVDF (~8000 lines, main scheduler body) - `kernel/sched/core.c` — General interfaces like schedule(), try_to_wake_up() - `kernel/sched/sched.h` — Definitions of struct rq, struct cfs_rq, sched_class - `kernel/sched/topology.c` — Scheduling domain construction - `kernel/sched/debug.c` — Implementation of /proc/sched_debug - **Classic Papers**: - "EEVDF: Earliest Eligible Virtual Deadline First" (Stoica & Abdel-Wahab, 1995) - "CFS: Completely Fair Process Scheduling in Linux" (MolNar, 2007 LWN) --- *Keywords: CFS, EEVDF, vruntime, sched_entity, cfs_rq, wakeup preemption, load_balance, sched_domain, cgroup scheduling, vlag*