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:

Priority from high to low:

// 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)

// 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

// 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

// 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

// 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:

// 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

// 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

// 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:

Dynamic Adjustment of Slice and Deadline

// 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

// 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

// 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

// 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

// 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

// 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:

// 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

// 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)

// Enable: CONFIG_CGROUP_SCHED
// Interface: /sys/fs/cgroup/cpu/<group>/

// 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.

Debugging and Observation

# Process scheduling statistics (Most critical file)
cat /proc/<pid>/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