进程调度器是 Linux 内核最核心的组件之一，它决定了哪个进程在什么时候获得 CPU 时间。从早期的 O(n) 调度器，到 O(1) 调度器，再到 2.6.23 引入的 CFS（Completely Fair Scheduler），再到 Linux 6.6 开始采用的 EEVDF（Earliest Eligible Virtual Deadline First），Linux 调度器经历了巨大的架构演进。本文将深入剖析调度器的核心数据结构、算法原理，并结合实际案例展示如何观察、调试和优化调度行为。
一、调度器架构总览
Linux 内核的调度器采用分级调度类（sched_class）的设计。每个调度类定义了一组操作函数，调度器按优先级从高到低依次检查每个调度类，选择最高优先级的可执行任务。调度类的优先级顺序如下：
| 优先级 | 调度类 | 说明 | 策略标志 |
|---|---|---|---|
| 最高 | stop_sched_class | 停机调度类，用于 CPU 热插拔、停机操作 | N/A |
| ↑ | dl_sched_class | Deadline 调度类，基于 EDF 算法 | SCHED_DEADLINE |
| ↑ | rt_sched_class | 实时调度类，FIFO 或 Round-Robin | SCHED_FIFO / SCHED_RR |
| ↑ | fair_sched_class | 完全公平调度类（CFS/EEVDF） | SCHED_NORMAL / SCHED_BATCH / SCHED_IDLE |
| 最低 | idle_sched_class | 空闲调度类，仅在没有任务时运行 | N/A |
这种层次设计保证了实时任务的确定性延迟、死限期任务的截止时间满足，以及普通任务的公平分配。每个 CPU 的运行队列（rq）中嵌入了各个调度类的私有数据结构，形成如下结构：
struct rq {
raw_spinlock_t lock;
unsigned int nr_running; /* 当前可运行任务数 */
unsigned long nr_load; /* 负载统计 */
struct cfs_rq cfs; /* CFS 运行队列 */
struct rt_rq rt; /* 实时运行队列 */
struct dl_rq dl; /* Deadline 运行队列 */
struct task_struct *curr; /* 当前运行的进程 */
struct task_struct *idle; /* 空闲进程 */
struct mm_struct *prev_mm; /* 上一个进程的 mm_struct */
// ...
} ____cacheline_aligned;二、CFS 完全公平调度器
2.1 设计理念：理想多任务处理器
CFS 的核心思想非常简单：如果有一个无限快的 CPU（理想多任务处理器），每个 n 个可运行进程应该恰好获得 1/n 的 CPU 时间。CFS 通过维护每个进程的虚拟运行时间（vruntime）来逼近这一理想状态。vruntime 增长越慢，说明进程获得的 CPU 时间越多；vruntime 增长越快，说明获得的越少。调度器每次选择 vruntime 最小的进程运行，从而保证长期上的公平性。
vruntime 的计算公式如下：
Δvruntime = Δwall_time × (NICE_0_LOAD / se.load.weight)其中 NICE_0_LOAD 是 nice=0 时的权重（值为1024），se.load.weight 是进程的实际权重。低 nice 值（高优先级）的进程权重更大，因此相同真实时间下 vruntime 增长更慢，从而更容易被选中执行。具体映射关系：
| Nice 值 | 权重 | 每 1ms 真实时间 vruntime 增量 |
|---|---|---|
| -20 | 88761 | ~0.0115 ms |
| -10 | 11058 | ~0.0926 ms |
| 0 | 1024 | 1.0000 ms |
| 10 | 110 | ~9.3091 ms |
| 19 | 15 | ~68.2667 ms |
这意味着 nice=-10 的进程获得的 CPU 时间大约是 nice=0 进程的 (1024/110) ≈ 9.3 倍，而在用户感知上表现为 nice=-10 的进程 vruntime 增长更慢，频繁获得运行机会。
2.2 红黑树与 vruntime 管理
CFS 使用红黑树（rbtree）来组织所有可运行进程，以 vruntime 为键值。红黑树的所有操作都是 O(log n) 时间复杂度，即使系统中存在数千个可运行进程，调度决策的开销仍然可控。
关键数据结构：
/**
* CFS 运行队列 - 每个 CPU 一个
*/
struct cfs_rq {
struct load_weight load; /* 队列总权重 */
unsigned int nr_running; /* 可运行进程数 */
u64 min_vruntime; /* 队列最小 vruntime */
struct rb_root_cached tasks_timeline; /* 红黑树根（rbtree） */
struct rb_node *rb_leftmost; /* 最左节点（vruntime 最小） */
/* 组调度相关 */
struct sched_entity *curr; /* 当前正在运行 */
struct sched_entity *next; /* 抢占时被唤醒立即运行 */
struct sched_entity *last; /* 上次运行，用于上下文切换预测 */
};
/**
* 调度实体 - 嵌入在 task_struct 中
*/
struct sched_entity {
struct load_weight load; /* 权重 */
struct rb_node run_node; /* 红黑树节点 */
u64 vruntime; /* 虚拟运行时间 */
u64 exec_start; /* 本轮执行开始时间 */
u64 sum_exec_runtime;/* 累计执行时间 */
u64 prev_sum_exec; /* 上次切换时累计值 */
/* 组调度：指向包含此实体的运行队列 */
struct cfs_rq *cfs_rq;
struct cfs_rq *my_q; /* 如果是组，指向子队列 */
};rb_leftmost 指针指向红黑树的最左节点，这是 vruntime 最小的进程，调度器的 pick_next_task_fair() 可以直接取出它，无需遍历整棵树。这是 CFS 的关键性能优化——通常只需要一次指针解引用。
当新进程被唤醒或被创建时，place_entity() 函数将其 vruntime 设置为当前队列的 min_vruntime 附近。如果新进程已经落后太多（比如从睡眠中醒来），则补偿一部分 vruntime，避免饥饿但又不会过度补偿导致老进程饿死。
2.3 时间片与调度周期
CFS 不使用固定时间片，而是基于调度周期（sched_latency）动态计算。调度周期是指所有可运行进程各运行一轮的总时间：
sysctl_sched_latency = 24 ms /* 调度周期默认值 */
sysctl_sched_min_granularity = 3 ms /* 最小粒度 */
sysctl_sched_wakeup_granularity = 4 ms /* 唤醒粒度 */
/* 计算时间片: */
if (nr_running > (sched_latency / min_granularity))
time_slice = min_granularity /* 进程太多时缩到最小 */
else
time_slice = sched_latency / nr_running# 查看调度器参数
$ cat /proc/sys/kernel/sched_latency_ns
24000000
$ cat /proc/sys/kernel/sched_min_granularity_ns
3000000
$ cat /proc/sys/kernel/sched_wakeup_granularity_ns
4000000
$ cat /proc/sys/kernel/sched_cfs_bandwidth_slice_us
5000三、Linux 6.6 的 EEVDF：调度器的又一次革新
3.1 CFS 的痛点与 EEVDF 的诞生
CFS 存在几个长期被诟病的问题：
- 延迟敏感性不足：CFS 的公平性模型在处理延迟敏感工作负载时表现不够好，特别是交互式进程的响应时间波动较大。
- 唤醒抢占开销：新唤醒进程需要从
min_vruntime开始计算，补偿机制复杂且容易误判。 - 调度延迟抖动：红黑树虽然效率高，但最坏情况下的调度延迟难以保证确定性边界。
- NUMA 扩展性：在大型 NUMA 系统上，CFS 的负载均衡机制不够精细。
2023 年，Peter Zijlstra 提交了 EEVDF（Earliest Eligible Virtual Deadline First）调度器，并被合并到 Linux 6.6 内核中作为 CFS 的替代方案。EEVDF 论文的作者是 MIT 的 Julia Lawley，其思想来自经典的实时调度理论。
3.2 EEVDF 的核心算法
EEVDF 为每个调度实体引入三个时间参数：
struct sched_entity {
u64 vruntime; /* 虚拟运行时间 - 与 CFS 相同 */
u64 vdeadline; /* 虚拟截止时间 - 新增 */
u64 vslice; /* 虚拟时间片 - 新增 */
// ...
};
/* 计算 deadline: */
se.vdeadline = se.vruntime + (se.vslice * sched_period) / total_weight;
/* 选择下一个任务：取 vdeadline 最小的进程 */
pick_next = min(entity.vdeadline) for all runnable entitiesEEVDF 同时维护两个数据结构：一个按 vruntime 排序的红黑树（用于入队/出队），一个按 vdeadline 排序的红黑树（用于调度决策）。实际上，EEVDF 使用了一种高效的单一红黑树结构，以 (vruntime, vdeadline) 为复合键，兼顾公平性和延迟确定性。
EEVDF 的关键优势在于它是 延迟确定性 的：在任意长度为 L 的窗口内，每个权重为 w、总权重为 W 的任务都保证获得至少 (w/W) × L 的 CPU 时间，且最大连续空闲时间有严格上界。
3.3 EEVDF vs CFS：性能对比
在实际基准测试中，EEVDF 在以下场景有显著提升：
发表评论 取消回复