Linux 内核调度器深度实战：从 CFS 完全公平调度到 EEVDF 现代化演进

一、调度器架构概览：从 O(1) 到 CFS 的演进

操作系统调度器是内核的核心组成部分，负责决定哪个进程在 CPU 上执行、执行多久、何时迁移。Linux 内核的调度器经历了多次重大变革：从早期的 O(N) 遍历，到 O(1) 调度器的 140 级优先级数组，再到 2007 年 Ingo Molnar 引入的 CFS（Completely Fair Scheduler，完全公平调度器），最终演进到 Linux 6.6 引入的 EEVDF。

现代 Linux 调度器采用模块化设计，多个调度类（sched_class）按优先级排列：

• SCHED_DEADLINE（截止时间调度，优先级最高）
• SCHED_FIFO / SCHED_RR（实时调度）
• SCHED_NORMAL / SCHED_BATCH / SCHED_IDLE（普通调度，CFS/EEVDF 负责）

每个 CPU 有独立的运行队列（runqueue），包含多个子队列，每个调度类管理自己的队列。调度决策按优先级依次检查，高优先级的调度类先选任务。

---

二、CFS 完全公平调度器：红黑树与虚拟运行时间

2007 年，Ingo Molnar 引入的 CFS（Completely Fair Scheduler，完全公平调度器）替代了 O(1) 调度器，成为 Linux 默认的普通调度类（SCHED_NORMAL）。

2.1 核心思想：把 CPU 时间归一化为"虚拟运行时间"

CFS 的核心对象是 虚拟运行时间（virtual runtime，vruntime）。每个进程有自己的 vruntime，它的增长速率与进程的需求成反比，用函数表示为：

vruntime += delta_exec * (NICE_0_LOAD / weight)

其中 NICE_0_LOAD 是基准权重（nice=0 → 1024），weight 对应于nice 值（-20 → 88761，0 → 1024，+19 → 15）。这意味着低 nice 值（高优先权）的进程 vruntime 增长更慢，从而获得更多的 CPU 时间。

2.2 红黑树（rbtree）组织可运行进程

CFS 使用 红黑树（自平衡二叉搜索树）存储可运行进程，以 vruntime 作为排序键。最左侧节点是 vruntime 最小的进程，即最"需要"CPU 的进程。操作复杂度为：

• 选取下一个进程：取最左节点，O(log N)
• 插入进程：O(log N)
• 删除进程：O(log N)

相比 O(1) 调度器的 140 个优先级队列，CFS 的红黑树设计保证了无论系统中有多少可运行进程，调度决策都能在对数时间内完成。

// CFS 核心数据结构
struct cfs_rq {
    struct rb_root_cached  tasks_timeline;  // 红黑树根
    struct sched_entity   *curr;           // 当前运行实体
    unsigned int          nr_running;      // 可运行进程数
    u64                   min_vruntime;    // 最小 vruntime
};

2.3 新进程的 vruntime 初始化

新创建的进程会被赋予一个 vruntime 值，确保它不会立即抢占所有已有进程。内核使用 min_vruntime 作为新进程的初始值偏移：

// 新进程 vruntime = min_vruntime + sched_latency / nr_running
// 这保证了新进程被放到红黑树的中间偏右位置
// 避免了"新进程饥饿老进程"的问题

2.4 调度延迟配置

CFS 有几个关键的可调参数：

• sched_latency：默认 24ms，目标延迟，所有可运行进程在这个周期内至少运行一次
• sched_min_granularity：默认 3ms，最小时间片，防止过多上下文切换
• sched_wakeup_granularity：默认 4ms，唤醒抢占粒度，防止新唤醒进程过度抢占

时间片计算公式：timeslice = sched_latency / nr_running（但不低于 min_granularity）

# 查看当前调度延迟
sysctl kernel.sched_latency_ns        # 默认 24000000 (24ms)
sysctl kernel.sched_min_granularity_ns # 默认 3000000 (3ms)
sysctl kernel.sched_wakeup_granularity_ns # 默认 4000000 (4ms)

# 调整（减少延迟，适合桌面交互场景）
sysctl -w kernel.sched_latency_ns=12000000
sysctl -w kernel.sched_min_granularity_ns=1500000
sysctl -w kernel.sched_wakeup_granularity_ns=2000000

---

三、EEVDF：Earliest Eligible Virtual Deadline First 现代化更新

Linux 6.6（2023年底） 引入的 EEVDF 替代 CFS 作为默认调度器。由 Peter Zijlstra 设计，旨在解决 CFS 在高负载下的延迟问题。

3.1 三大核心概念

• Virtual Runtime (vruntime)：相同概念，但语义更精确——表示"hearliness"
• Eligible Time (eligible)：允许被调度的最早时间点
• Virtual Deadline (vdl)：虚拟截止时间，= eligible_slice + sched_slice

EEVDF 的关键创新：不再单纯按 vruntime 最小选进程，而是引入虚拟截止时间作为调度依据，实现了更精确的延迟保证。

// EEVDF 调度实体的关键字段
struct sched_entity {
    u64 vruntime;       // 虚拟运行时间
    u64 vdl;            // 虚拟截止时间
    u64 eligible_time;  // 有资格时间
    u64 slice;          // 本次调度的时间片
    // ...
};

3.2 调度决策流程

1. 从红黑树中找出 vdl 最小的进程
2. 检查该进程是否已 eligible（eligible_time ≤ 当前时间）
3. 如果 eligible 且未过期，则调度执行
4. 执行完后更新 vruntime 和 vdl
5. 如果进程用完时间片，重新计算 vdl 后插入

3.3 与 CFS 的对比

特性	CFS	EEVDF
排序键	vruntime（虚拟运行时间）	vdl（虚拟截止时间）
调度策略	最小 vruntime 先执行	最早 eligible 截止时间先执行
数据结构	红黑树（按 vruntime）	红黑树（按 vdl）
延迟保证	无严格保证	有延迟上界保证
唤醒抢占	固定粒度检查	更精确的智能抢占
适用场景	通用服务器	交互+服务器+实时混合

3.4 延迟改善实测

社区测试显示，EEVDF 在高负载场景下（100%+ CPU 使用率）：

• 尾延迟（P99）降低约 40%
• 交互进程卡顿显著减少
• 更平滑的 CPU 时间分配
• 对 cgroup 带宽控制更高效

---

四、群组调度（Group Scheduling）与 cgroup

群组调度 实现 调度层级化，将 CPU 资源分配给不同用户/组/服务，防止新服务或新任务独占所有 CPU 时间。

4.1 CPU 精准控制：cgroup v2 cpu.max

# 限制 myapp cgroup 每 100ms 周期内最多使用 50ms CPU（即 0.5 CPU）
echo "50000 100000" > /sys/fs/cgroup/myapp/cpu.max

# 查看当前 cgroup 的 CPU 限制
cat /sys/fs/cgroup/myapp/cpu.max

# 查看每周期 CPU 使用率（throttled_time 表示被限制的纳秒数）
cat /sys/fs/cgroup/myapp/cpu.stat
# 输出示例：
# usage_usec 49500000
# user_usec 45000000
# system_usec 4500000
# nr_periods 100
# throttled_usec 12000000
# throttled_nr 5

4.2 带宽控制算法

EEVDF 为 cgroup 提供了更高效的带宽控制实现：

• 层级嵌套：cgroup 可以有子 cgroup，父级的配额被子级共享
• 全局周期：默认 100ms，全局同步所有 cgroup 的刷新时点
• 触顶恢复：当配额用尽时，进程被移入"throttled"队列，下一个周期再恢复

4.3 实战：Kubernetes 与 cgroup

Kubernetes 的 request / limit 对应 cgroup 映射：

• request → cgroup cpu.weight（权重比例分配，非硬限）
• limit → cgroup cpu.max（硬上限，超出即限流）
• Burstable QoS：request < limit，有空闲资源时可突发
• Guaranteed QoS：request = limit，严格保证

# 查看实际 K8s Pod 的 cgroup 限制
cat /sys/fs/cgroup/cpu/kubepods/pod/cpu.max
# 输出示例："100000 100000" = 1 核，"200000 100000" = 2 核

# 查看权重
cat /sys/fs/cgroup/cpu/kubepods/pod/cpu.weight
# 对应 request 量的权重值（1-10000）

---

五、实时调度类：SCHED_FIFO • SCHED_RR • SCHED_DEADLINE

Linux 支持 三种实时调度类，对应不同的生产需求，接入服务调度（QoS）。

5.1 SCHED_FIFO（先进先出）

• 同优先级进程按到达顺序排队
• 一旦获得 CPU，运行到主动 yield 或被更高优先级抢占
• 风险：如果不主动让出 CPU，可能独占系统导致其他进程饥饿
• 优先级范围：1-99（数字越大优先级越高）

// 设置 SCHED_FIFO 策略
struct sched_param param;
param.sched_priority = 50;
sched_setscheduler(pid, SCHED_FIFO, &param);

5.2 SCHED_RR（轮转调度）

SCHED_RR 行为与 FIFO 相同，但有时间片（默认 100ms），同优先级进程轮转执行。当一个进程的时间片用完后，移到同优先级队列末尾。

// 查看/修改 RR 时间片
cat /proc/sys/kernel/sched_rr_timeslice_ms  # 默认 100

5.3 SCHED_DEADLINE（最早截止时间优先）

Kernel 3.14 引入，实现 EDF（Earliest Deadline First），是目前最精确的硬实时调度策略。通过 sched_attr 提交 (runtime, deadline, period) 三元组：

// 设置 SCHED_DEADLINE 参数
// 含义：每个 100ms 周期内，该任务必须在 30ms 之前完成 20ms 的工作量
struct sched_attr attr = {
    .sched_policy   = SCHED_DEADLINE,
    .sched_runtime  = 20 * 1000 * 1000,   // 20ms（纳秒）
    .sched_deadline = 30 * 1000 * 1000,   // 30ms（纳秒）
    .sched_period   = 100 * 1000 * 1000,  // 100ms（纳秒）
};
sched_setattr(pid, &attr, 0);

// 核心保证：runtime / period < 1.0
// 如果不满足，初始化系统调用返回 EINVAL

SCHED_DEADLINE 使用全局 EDF 算法，支持多核系统上的任务迁移，确保所有任务的截止时间都能被满足。这是自动驾驶、工业控制系统中最常用的实时调度策略。

---

六、NUMA 负载均衡与调度域

NUMA（Non-Uniform Memory Access） 用于多核/多路服务器，要求进程尽量访问本地内存节点。Linux 内核通过 调度域（Scheduling Domain） 和 NUMA 均衡来优化跨节点访问。

6.1 调度域层级

// Linux 内核根据 CPU Topology 构建 Sched Domain 层级
// 从低到高：
SMT  (Simultaneous Multithreading) - 同一物理核心的逻辑核
MC   (Multi-Core)                    - 同一 CPU 芯片的核心
BOOK                                    - 同一内存域
NUMA                                    - 同一 NUMA 节点
CPU_DIFFERENT                           - 跨 NUMA 节点

6.2 NUMA 均衡策略

• 自动 NUMA 均衡（AutoNUMA）：内核采样进程的内存访问，将进程迁移到其"热内存"所在的 NUMA 节点
• 负载均衡：定期检查各调度域的负载，将任务从繁忙 CPU 迁移到空闲 CPU
• 唤醒均衡：进程唤醒时，选择最优 CPU（考虑缓存亲和性和负载）

# 查看调度域信息
cat /proc/sched_debug | head -100

# 查看 NUMA 拓扑
numactl --hardware

# 查看进程 NUMA 策略
taskset -p <pid>

# 手动绑定进程到 NUMA 节点
numactl --cpunodebind=0 --membind=0 ./myapp

# 禁用自动 NUMA 均衡（某些场景下有利）
echo 0 > /proc/sys/kernel/numa_balancing

---

七、sched_ext（可扩展调度器）：Linux 6.12 新特性

sched_ext（Scheduler Extender）是 Linux 6.12（2024年） 引入的革命性特性，允许用 Rust / C / C++ 编写用户态调度程序并加载运行，为定制化调度策略开辟了新路径。

7.1 核心架构

sched_ext 调度程序是一种特殊的 eBPF-like 程序，但以完整的调度器身份运行。它不是替代 CFS/EEVDF，而是在"fallback"模式下运行——即先尝试自定义调度，如果没有合适任务则回退到默认调度器。

// sched_ext 调度程序核心结构
// 关键回调函数：
 - dispatch(): 决定下一个运行的进程
 - select_cpu(): 为新唤醒进程选择 CPU
 - enqueue(): 进程加入运行队列
 - dequeue(): 进程离开运行队列
 - tick(): 每次时钟中断触发
 - running()/stopping(): 进程开始/结束运行

sched_ext 调度程序通过 BPF 程序 实现，运行在内核态，但使用用户态友好的 API 和工具链。

7.2 应用场景

• 超大规模数据中心：Google、Meta 利用 sched_ext 实现定制化的任务分配策略，优化了异构加速器（GPU/FPGA/DPU）的任务分发
• 高性能计算（HPC）：针对 MPI 应用的通信密集模式优化，减少不必要的任务迁移
• 容器编排：Kubernetes runtime 层通过 sched_ext 精细控制 Pod 的 CPU 亲和性和调度行为
• 研究实验：学者可以快速验证新的调度算法，无需修改内核源码或重启系统

7.3 工具链与使用

# 查看 sched_ext 是否启用
cat /sys/kernel/sched_ext/root/enabled

# 加载自定义 scx 调度程序
scx_simple -f  # 加载 simple 调度器（按 PID 顺序）

# 查看可用调度器
ls /sys/kernel/sched_ext/

# 自定义 Rust 调度器（scx_rustland 示例）
# 源码：https://github.com/sched-ext/scx

# 兼容性：需要 Linux 6.12+ 内核
uname -r
# 返回值应 >= 6.12.0

sched_ext 代表了 Linux 调度器的未来方向：模块化、可扩展、用户态可控。它使得调度器不再是一个"黑盒"基础设施，而是可以根据具体工作负载灵活调整的组件。

---

八、性能调优与调度分析

调度器的优化需要结合具体工作负载特征。以下是一个调优清单：

8.1 关键 sysctl 参数

# ========== 调度延迟 ==========
# 查看默认值
sysctl -a | grep sched_ | grep -E "latency|granularity|wakeup"

# 交互式桌面（低延迟）
sysctl -w kernel.sched_latency_ns=6000000     # 6ms
sysctl -w kernel.sched_min_granularity_ns=750000  # 0.75ms
sysctl -w kernel.sched_wakeup_granularity_ns=1000000 # 1ms

# 批处理服务器（高吞吐）
sysctl -w kernel.sched_latency_ns=48000000     # 48ms
sysctl -w kernel.sched_min_granularity_ns=6000000  # 6ms

# ========== NUMA ==========
sysctl -w kernel.numa_balancing=1              # 开启自动 NUMA 均衡

# ========== 调度器特性 ==========
# 查看当前调度器特性标志
cat /proc/sys/kernel/sched_features

# 禁用 NEXT_BUDDY（可能改善缓存命中率）
echo NO_NEXT_BUDDY > /proc/sys/kernel/printk
# 注意：不要在生产环境随意修改

8.2 调度质量分析工具

# ========== bpfcc-tools ==========
# 安装
apt install bpfcc-tools || yum install bpfcc-tools

# 调度延迟分布（单位：微秒）
runqlat 1 5
# 输出示例：
# usecs               : count     distribution
#  0 - 1          : 0        |
#  2 - 3          : 1        |**
#  4 - 7          : 3        |******
#  8 - 15         : 8        |****************
#  16 - 31        : 12       |***************************
#  32 - 63        : 5        |***********
# ...

# 队列长度
runqlen 1 5

# 进程的调度延迟
Runqlat -p <pid> 1 10

# ========== perf sched ==========
# 记录调度事件
perf sched record -- sleep 5

# 查看调度延迟统计
perf sched latency

# 生成调度时间线
perf sched map

# ========== 内置工具 ==========
# 进程的调度统计
cat /proc/<pid>/sched

# 系统上下文切换速率
vmstat 1 5
# 输出中的 cs 列表示每秒上下文切换次数（正常 <5000，高负载可能10000+）

# 进程切换统计
pidstat -w 1 5

8.3 高负载场景优化策略

• 减少不必要的上下文切换：合理设置线程数（CPU 密集型建议 = CPU 核心数，IO 密集型可更多）
• CPU 亲和性绑定：对延迟敏感进程使用 taskset 或 sched_setaffinity 绑定固定 CPU
• NUMA 感知：在 NUMA 架构上，使用 numactl 绑定内存访问到本地节点
• cgroup 隔离：生产环境与批处理任务通过 cgroup 分开，避免互相影响
• 中断亲和性：将网卡中断绑定到特定 CPU（IRQ affinity），避免干扰关键线程

---

九、总结与展望

Linux 内核调度器经历了从 O(1) 队列 → CFS 红黑树 → EEVDF 截止时间调度的演进，核心目标是：在保证公平性的前提下，提供可预测的延迟和更灵活的调度策略。

目前（2024年底）的 Linux 调度器生态：

• 默认调度器：EEVDF（Linux 6.6+），提供比 CFS 更好的延迟特性
• 实时调度：SCHED_DEADLINE 提供硬实时保证，适用于工业/车载系统
• 可扩展调度：sched_ext（Linux 6.12+），允许用户态编写自定义调度策略
• cgroup v2：通过 cpu.max 和 cpu.weight 提供精确的 CPU 资源管控
• NUMA 优化：AutoNUMA 自动迁移减少跨节点内存访问

未来发展方向：

• 与 eBPF 更深度的集成，实现数据驱动的调度决策
• 对 异构计算（big.LITTLE、GPU、NPU）的统一调度支持
• 能源感知调度：在保证性能的前提下优化功耗
• 延迟敏感任务（Latency Sensitive） 的进一步优化

EEVDF 已在 Ubuntu 24.04+、Fedora 41+、Arch Linux 等主流发行版中默认启用。通过理解调度器原理和调优参数，可以让系统在不同工作负载下达到最优性能。

---

推荐学习资源：

• 《Understanding the Linux Kernel》— Bovet & Cesati，第10章调度器
• 《Linux Kernel Development》— Robert Love，详细介绍 CFS 实现
• Linux 内核源码：kernel/sched/fair.c — CFS 源码
• Linux 内核源码：kernel/sched/deadline.c — SCHED_DEADLINE
• Linux 内核源码：kernel/sched/ext.c — sched_ext 可扩展调度器
• LWN.net：https://lwn.net/Kernel — 调度器相关内核开发文章
• Kernel.org 文档：https://www.kernel.org/doc/html/latest/scheduler/