--- title: 调度器 url: https://doc.liz6.com/linux-kernel/01-process-management/02-scheduler locale: zh area: linux-kernel tags: - linux-kernel - 进程管理 date: 2026-06-30 modified: 2026-07-11 description: '覆盖: CFS (vruntime/红黑树) → EEVDF (6.6+) → 调度类架构 → 负载均衡 → 抢占内核版本: 2.6 ~ 6.x，重点标注 CFS→EEVDF 变革' --- # 调度器 > 覆盖: 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) | ```c // 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) ```c // 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 — 调度实体 ```c // 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 映射 ```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, }; ``` 关键性质：每降低一个 nice 值，weight 大约增加 25%。这意味着 nice -20 的进程获得的 CPU 时间大约是 nice 0 的 87 倍（不是简单的线性关系）。这种指数衰减的设计来自 CFS 的原始论文——它确保相邻 nice 值的公平差是一致的。 ### 关键函数 ```c // 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 的做法： ```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; // 从当前 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 追踪 ```c // 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 核心算法 ```c // 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 的动态调整 ```c // sysctl_sched_base_slice: 基准时间片 (默认 3ms for EEVDF) // 每个进程的实际 slice = base × (weight / cfs_rq_weight) // 权重大的进程获得更长的 slice → 更少的上下文切换 // 如果进程在 slice 用完之前就让出 CPU (如 block 在 IO): // → vruntime 停止增长 → vlag 变大 → 唤醒时更容易 eligible // → 交互式的"用一下就等"模式得到补偿 ``` ### lag 补偿机制 ```c // 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) ```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 旧逻辑: 被唤醒进程比当前进程"穷很多"才抢占 // 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 抢占 ```c // 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 与延迟调度 ```c // 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 ``` ```c // kernel/sched/topology.c: 启动时由 arch 代码初始化 // x86: arch/x86/kernel/smpboot.c 构造调度域拓扑 // ARM: drivers/base/arch_topology.c 从 DT/ACPI 获取 ``` ### 均衡触发时机有四类均衡： ```c // 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 实现 ```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() — 只在 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) ```c // 启用: CONFIG_CGROUP_SCHED // 接口: /sys/fs/cgroup/cpu// // 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` 中按组内进程的权重二次分配。 --- ## 调试与观测 ```bash # 进程的调度统计 (最关键的文件) cat /proc//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*