调度器

覆盖: CFS (vruntime/红黑树) → EEVDF (6.6+) → 调度类架构 → 负载均衡 → 抢占 内核版本: 2.6 ~ 6.x，重点标注 CFS→EEVDF 变革

概述

调度器是内核中调用最频繁的子系统之一。每一次 schedule() 调用都要回答一个问题：⁠下一个该跑谁？ 这个问题看似简单，但要在"交互响应快、吞吐高、公平、节能、多核扩展"之间取得平衡，复杂度极高。

Linux 的答案经历了三个时代：

• 2.4: O(n) 调度器 — 遍历所有进程选最高 priority
• 2.6 ~ 6.5: CFS (Completely Fair Scheduler) — vruntime 驱动的红黑树
• 6.6+: EEVDF — Earliest Eligible Virtual Deadline First

本文聚焦 CFS 和 EEVDF 的设计原理，追溯关键代码路径。

---

调度类架构

Linux 调度器不是单一算法，而是可堆叠的调度类⁠：

优先级从高到低：

调度类	策略	典型场景
stop_sched_class	最高优先级，抢占一切	CPU hotplug, migration
dl_sched_class	Deadline (EDF + CBS)	硬实时任务
rt_sched_class	POSIX RT (FIFO / RR)	软实时，chrt -f
fair_sched_class	CFS / EEVDF	所有普通进程
idle_sched_class	只在无其他任务时运行	idle task (PID 0 per-CPU)

// kernel/sched/sched.h
struct sched_class {
    const struct sched_class *next;  // 链表

    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);  // ← 更新 vruntime 的核心
    void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
    void (*task_fork)(struct task_struct *p);     // fork 初始化
    void (*task_dead)(struct task_struct *p);     // exit 清理
    void (*switched_from)(struct rq *rq, struct task_struct *p);
    void (*switched_to)(struct rq *rq, struct task_struct *p);
};

调度类的可堆叠设计是 Linux 调度器最优雅的架构决策之一：实时和普通任务共享同一个 schedule() 入口，无需特殊处理。任何一个调度类返回 NULL，框架就往下问下一个类。最终 idle_sched_class 保证永远有进程可跑。

---

核心数据结构

runqueue (struct rq)

// kernel/sched/sched.h
struct rq {
    raw_spinlock_t      __lock;         // 保护整个 runqueue
    unsigned int        nr_running;     // 可运行进程数 (不含 idle)
    unsigned long       nr_switches;    // 调度次数计数

    struct cfs_rq       cfs;            // CFS 的运行队列
    struct rt_rq        rt;             // RT 的运行队列
    struct dl_rq        dl;             // Deadline 的运行队列

    struct task_struct  *curr;          // 当前在跑的进程
    struct task_struct  *idle;          // 本 CPU 的 idle task
    struct task_struct  *stop;          // 本 CPU 的 stop task

    int                 cpu;            // CPU ID
    unsigned long       clock;          // rq 内部时钟
    unsigned long       clock_task;     // 减去 IRQ/softirq 时间的实际执行时间

    struct sched_domain *sd;            // 调度域 (负载均衡)
};

每个 CPU 有自己的 struct rq。锁粒度是 per-rq，这意味着调度决策只需拿本 CPU 的锁——这是调度器在大核数系统上能扩展的关键。raw_spinlock_t 意味着拿这个锁时必须关中断——因为 scheduler tick 可能在任何时候触发。

sched_entity — 调度实体

// include/linux/sched.h
struct sched_entity {  // 内嵌在 task_struct 中
    struct load_weight  load;           // 权重 (nice 值转换)
    unsigned long       runnable_weight;
    struct rb_node      run_node;       // CFS 红黑树节点
    unsigned int        on_rq;          // 是否在 runqueue

    u64                 exec_start;     // 当前执行开始时间
    u64                 sum_exec_runtime;  // 累计物理执行时间
    u64                 vruntime;       // 虚拟运行时间 (CFS/EEVDF 排序键)
    u64                 prev_sum_exec_runtime;

    // EEVDF 新增 (6.6+)
    u64                 deadline;       // 虚拟截止时间
    u64                 min_vruntime;   // 当前 cfs_rq 最低 vruntime
    u64                 min_deadline;   // 当前 cfs_rq 最早 deadline
    u64                 vlag;           // 滞后值 (lag) — 被唤醒时追赶用

    struct sched_entity *parent;
    struct cfs_rq       *cfs_rq;        // 所属的 cfs_rq (组调度)
    struct cfs_rq       *my_q;          // 如果这是一个 group se, 其子 cfs_rq
};

---

CFS: vruntime 驱动的公平性

核心思想

CFS 不按时间片分配 CPU，而是按照虚拟运行时间 (vruntime) 排序：

vruntime = 物理执行时间 × (NICE_0_LOAD / weight_of_process)

进程的 nice 值越低 (优先级越高)，weight 越大 → 相同的物理时间累计更少的 vruntime → 排在红黑树更左边 → 更早被选中。

本质：CFS 追求的是 vruntime 的收敛⁠。所有进程的 vruntime 应该趋同；优先调度 vruntime 最小的进程，就是在补偿"亏欠 CPU 最多"的进程。

nice → weight 映射

// 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,
};

关键性质：每降低一个 nice 值，weight 大约增加 25%。这意味着 nice -20 的进程获得的 CPU 时间大约是 nice 0 的 87 倍（不是简单的线性关系）。这种指数衰减的设计来自 CFS 的原始论文——它确保相邻 nice 值的公平差是一致的。

关键函数

// kernel/sched/fair.c

// 更新 vruntime (每次 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))  // 防御: 时钟不应倒退
        return;

    curr->exec_start = now;
    curr->sum_exec_runtime += delta_exec;

    // 核心转换: 物理时间 → 虚拟时间
    curr->vruntime += calc_delta_fair(delta_exec, curr);
}

// 挑选下一个: 红黑树最左节点
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() 实现 delta * (NICE_0_LOAD / weight)。它使用 128 位定点运算避免溢出，并处理了精度问题（对于很小的 delta 不做缩水，防止 vruntime 完全不增长）。

vruntime 的边界处理

新进程的 vruntime 初始值不能从 0 开始——否则新 fork 的进程会垄断 CPU 很长时间。CFS 的做法：

// 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;  // 从当前 cfs_rq 的 min 起步

    if (initial && sched_feat(START_DEBIT))
        // fork 的新进程: vruntime += 一次性 penalty
        vruntime += sched_vslice(cfs_rq, se);

    // EEVDF (6.6+): 同时设 deadline
    se->deadline = vruntime + calc_delta_fair(se->slice, se);
    se->vruntime = vruntime;
}

sched_vslice() 返回的 penalty 约等于这个进程第一次能跑的时间片——这样新进程不会比已在运行的进程"更穷"，保持了公平。

min_vruntime 追踪

// cfs_rq->min_vruntime 单调递增，追踪所有出队进程的最小 vruntime
// 在 update_min_vruntime() 中更新:
static void update_min_vruntime(struct cfs_rq *cfs_rq) {
    struct sched_entity *se = __pick_first_entity(cfs_rq);
    // 从所有可能的来源中取最大:
    //   当前进程的 vruntime
    //   红黑树最左节点的 vruntime (如果有)
    //   cfs_rq->curr->vruntime (如果存在)
    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 永不倒退——这是保证公平的关键不变量

---

EEVDF: 6.6 的范式转移

为什么需要 EEVDF

CFS 的 vruntime 排序在 CPU-bound 场景下很公平，但在延迟敏感场景有缺陷：

• 进程 slept 了很久 → vruntime 极度低于所有人 → 被唤醒后长时间占据 CPU（延迟突发）
• CFS 没有"该什么时候完成"的概念，只有"谁最该跑"
• 响应延迟不可预测——sleep 后的进程可能要等很久才能上 CPU（vruntime 虽然低但不保证立即响应）

EEVDF 通过引入 deadline 解决了这个问题。每个实体在入队时计算一个 eligible time（何时有资格运行）和 deadline（期望完成时间）。调度器按 deadline 排序，但只从 eligible 的进程中选择。

EEVDF 核心算法

// kernel/sched/fair.c (6.6+)

// 请求时间 (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)
    // 权重越大的进程，slice 越大 → deadline 越远 → 不会被频繁中断
    return calc_delta_fair(sysctl_sched_base_slice, se);
}

// 入队: 计算 deadline
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial) {
    u64 vruntime = se->vruntime;
    
    // 1. eligible time: lag 补偿
    //    vlag = 平均 vruntime - 自己的 vruntime
    //    如果 vlag > 0 (自己落后于平均) → 优先被 eligible
    //    如果 vlag < 0 (自己超前于平均) → 延迟 eligible
    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: 从 eligible 实体中选 deadline 最早的
static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) {
    struct sched_entity *se = __pick_first_entity(cfs_rq);  // vruntime 最小
    struct sched_entity *best = NULL;

    // 线性扫描红黑树 (按 vruntime 排序)，直到找到所有 eligible 实体中 deadline 最小的
    while (se) {
        // eligible: vlag > 0 → 自己的 vruntime < 平均 → 有资格获得 CPU 时间
        if (entity_eligible(cfs_rq, se)) {
            if (!best || se->deadline < best->deadline)
                best = se;
            // deadline 最小但 vruntime 更小的可能还在后面 → 继续扫
            if (best && best->deadline < se->vruntime)
                break;  // 后面的实体 vruntime 更大，deadline 不可能比 best 更好
        }
        se = __pick_next_entity(se);  // 红黑树中序后继
    }

    return best ?: __pick_first_entity(cfs_rq);  // nobody eligible → 选最左
}

关键区别：

	CFS	EEVDF
选择标准	vruntime 最小	deadline 最早 (从 eligible 中)
slept 进程行为	长时间垄断 CPU (vruntime 极低)	被唤醒后有 lag 补偿，但 slice 用完就得重排队
延迟保证	无	有 (每个进程有明确的完成截止)
实现复杂度	较低	中等 (多了 eligibility 检查和 vlag)

slice 与 deadline 的动态调整

// sysctl_sched_base_slice: 基准时间片 (默认 3ms for EEVDF)
// 每个进程的实际 slice = base × (weight / cfs_rq_weight)
// 权重大的进程获得更长的 slice → 更少的上下文切换

// 如果进程在 slice 用完之前就让出 CPU (如 block 在 IO):
//   → vruntime 停止增长 → vlag 变大 → 唤醒时更容易 eligible
//   → 交互式的"用一下就等"模式得到补偿

lag 补偿机制

// lag: 这是 EEVDF 与 CFS 最大的实现差异
// 定义: lag = avg_vruntime - se->vruntime
//   lag > 0: 进程落后于平均 → 应该优先
//   lag < 0: 进程超前 → 应该等待

// 被唤醒时:
static int wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se) {
    // EEVDF: deadline 比较
    if (se->deadline < curr->deadline)
        return 1;  // 新唤醒的进程 deadline 更早 → 抢占

    // 额外考虑 vlag 边界
    // 如果新进程的 lag 远大于当前进程的 lag → 也要抢占
    // (防止某些进程被饿死)
    return 0;
}

---

抢占

唤醒抢占 (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 旧逻辑: 被唤醒进程比当前进程"穷很多"才抢占
    //   wakeup_preempt_entity(curr, se) → calc_delta_fair(gran, se)
    //   要求被唤醒的 vruntime 至少落后 granularity 的量

    // EEVDF 新逻辑 (6.6+):
    //   谁的 deadline 更早 → 抢占
    if (se->deadline < curr->deadline)
        resched_curr(rq);
}

tick 抢占

// kernel/sched/fair.c: entity_tick()
// 每个 scheduler tick (CONFIG_HZ, 通常 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. 当前进程用完了应有时间片 → 设 NEED_RESCHED
    if (delta_exec > ideal_runtime) {
        resched_curr(rq_of(cfs_rq));
        return;
    }

    // 2. EEVDF: 如果红黑树中有 deadline 早于当前进程的 eligible 实体
    if (pick_eevdf(cfs_rq) != curr)
        resched_curr(rq_of(cfs_rq));
}

NEED_RESCHED 与延迟调度

// resched_curr() 只设 TIF_NEED_RESCHED 标志
// 不是在这里做 schedule() —— 我们在中断上下文！
// 真正的上下文切换在返回用户态之前的 exit_to_user_mode_loop() 中:
//
// exit_to_user_mode_loop() {
//     if (ti_work & _TIF_NEED_RESCHED)
//         schedule();
// }
//
// 或者在抢占内核 (CONFIG_PREEMPT=y) 的 preempt_schedule_irq() 中

---

负载均衡

调度域层级

// 现代 2-socket AMD EPYC 的典型层级:
// SMT (超线程, L1 共享) < MC (多核, L3 共享) < DIE (同 socket) < NUMA (跨 socket)
// 每层有自己的 sched_domain，构成嵌套的 CPU mask

// kernel/sched/topology.c: 启动时由 arch 代码初始化
// x86: arch/x86/kernel/smpboot.c 构造调度域拓扑
// ARM: drivers/base/arch_topology.c 从 DT/ACPI 获取

均衡触发时机

有四类均衡：

// 1. idle balance: CPU 即将 idle → 在 schedule() 中调用 newidle_balance()
//    → 主动从 busy CPU 拉任务 (启动快，避免 idle 延迟)

// 2. periodic balance: scheduler_tick() → trigger_load_balance()
//    → SCHED_SOFTIRQ → run_rebalance_domains()
//    → 由 softirq 异步执行，频率 = 1 / (4 * sched_domain->interval)

// 3. fork/exec balance: wake_up_new_task() → select_task_rq_fair()
//    → find_idlest_cpu() → 在调度域内找最空闲的 CPU

// 4. wake balance: try_to_wake_up() → select_task_rq_fair()
//    → find_idlest_cpu() 或 wake_affine() (优先唤醒 CPU)

load_balance 实现

// 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() — 只在 group 的第一个 idle CPU 上做均衡 (减少冲突)
    // 2. find_busiest_group() — 在 sd 的 sched_group 链表中找最忙的
    // 3. find_busiest_queue() — 在最忙 group 中找最忙 CPU 的 runqueue
    // 4. detach_tasks() — 从 busy rq 摘 <= 32 个进程 (sysctl_sched_nr_migrate)
    //    只摘那些允许迁移的 (cpus_allowed, cgroup 未钉核等)
    // 5. attach_tasks() — 挂到 this_rq，逐个 activate_task() → enqueue_task_fair()
}

---

组调度 (CGroup CPU controller)

// 启用: CONFIG_CGROUP_SCHED
// 接口: /sys/fs/cgroup/cpu/<group>/

// cpu.shares   — 权重分配 (默认 1024)
//   各组按 shares 比例分 CPU。A=2048, B=1024 → A:B = 2:1

// cpu.cfs_quota_us   — 周期内最大 CPU 时间
// cpu.cfs_period_us  — 周期长度 (默认 100ms)
//   quota=50000, period=100000 → 最多用 50% CPU

每个 cgroup 对应一个 task_group，包含一个 sched_entity 嵌入父 cfs_rq。这个 se "伪装"成普通进程参与父组的调度。收到 CPU 时间后，再在自己的 cfs_rq 中按组内进程的权重二次分配。

---

调试与观测

# 进程的调度统计 (最关键的文件)
cat /proc/<pid>/sched
# 内容: se.sum_exec_runtime, se.vruntime, se.statistics.wait_sum,
#       nr_switches, nr_voluntary_switches, nr_involuntary_switches

# 系统级调度器调试信息
cat /proc/sched_debug
# 含: 每 CPU 的 cfs_rq 统计, nr_running, min_vruntime, 红黑树大小

# ftrace: 抓调度事件
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: 按进程统计调度延迟
bpftrace -e 'kprobe:finish_task_switch { 
    @[comm] = hist(nsecs - @start[tid]); 
} 
kprobe:__schedule /args->prev/ { 
    @start[args->prev->pid] = nsecs; 
}'

# 查看 EEVDF 是否启用
grep CONFIG_SCHED_EEVDF /boot/config-$(uname -r)

# Kernel cmdline: 调试用开关
# sched_verbose — 更多 dmesg 信息
# skew_tick=1   — 让各 CPU tick 偏移，减少锁竞争

---

参考与延伸

• 内核文档⁠: Documentation/scheduler/ 目录，尤其是 sched-design-CFS.rst 和 sched-eevdf.rst
• LWN:
  • "EEVDF scheduler design" 系列 (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/)
• 源码文件⁠:
  • kernel/sched/fair.c — CFS/EEVDF (~8000行，调度器主体)
  • kernel/sched/core.c — schedule(), try_to_wake_up() 等通用接口
  • kernel/sched/sched.h — struct rq, struct cfs_rq, sched_class 定义
  • kernel/sched/topology.c — 调度域构建
  • kernel/sched/debug.c — /proc/sched_debug 实现
• 经典论文⁠:
  • "EEVDF: Earliest Eligible Virtual Deadline First" (Stoica & Abdel-Wahab, 1995)
  • "CFS: Completely Fair Process Scheduling in Linux" (MolNar, 2007 LWN)

---

关键词: CFS, EEVDF, vruntime, sched_entity, cfs_rq, wakeup preemption, load_balance, sched_domain, cgroup scheduling, vlag