Linux 内核进程调度器深度实战：从 CFS 完全公平调度器到 EEVDF 最早虚拟截止时间优先

1 阅读 0 评论 0 点赞

Linux 内核进程调度器深度实战：从 CFS 完全公平调度器到 EEVDF 最早虚拟截止时间优先

进程调度器是 Linux 内核最核心的组件之一，它决定了哪个进程在何时获得 CPU 时间。本文将从调度器的发展历史出发，深入剖析 CFS（Completely Fair Scheduler）的实现原理，然后重点介绍 Linux 6.6 引入的 EEVDF（Earliest Eligible Virtual Deadline First）调度器——这是 20 年来 Linux 通用调度器的首次重大变革。

一、调度器的历史演进

Linux 内核调度三代架构的更替，每一次变革都是为了解决上一代的核心瓶颈：

1.1 O(n) 调度器（Linux 2.4 时代）

早期内核采用朴素的 O(n) 调度策略。每次选择下一个进程时，需要遍历所有可运行进程，计算其优先级和已用时间片。进程数越多，选择开销越大。同时采用了「过期队列」机制——当进程用完时间片后放入过期队列，等所有活跃进程执行一轮后再批量交换两个队列的指针。这种设计虽然简单，但在多核和大量进程场景下成为性能瓶颈。

1.2 O(1) 调度器（Linux 2.6.0 ~ 2.6.22）

Ingo Molnar 引入 O(1) 调度器后，引入了两个关键数据结构：活跃数组（active array）和过期数组（expired array），每个数组包含 140 个优先级队列（对应 nice 值 -20 ~ +19）。调度选择的过程变为：根据静态优先级选择对应队列的队首进程，O(1) 时间完成；用完时间片后放入过期数组对应优先级位置，也是 O(1)。当活跃数组为空时，交换两个数组指针——仍然是 O(1)。

但 O(1) 调度器的问题在于「交互式进程识别」——它使用复杂的启发式算法判断进程是否交互式，进而给予奖励或惩罚。这些启发式规则在编译进程和GUI程序边界情况下表现糟糕，且时间片分配不够公平。

1.3 CFS 完全公平调度器（Linux 2.6.23 ~ 至今）

Con Kolivas 的 RSDL（Rotating Staircase Deadline）调度器启发了 Ingo Molnar 设计 CFS。CFS 的核心哲学是：模拟一个理想多任务处理器（ideal multitasking processor）。在这个理想 CPU 上，每个进程在同一时刻获得 1/N 的 CPU 时间。CFS 则在任何时刻选择「实际获得 CPU 时间最少的进程」来运行，以逼近理想状态。

1.4 EEVDF 最早虚拟截止时间优先（Linux 6.6+）

2023 年，Peter Zijlstra 提交了 EEVDF 调度器补丁，在 Linux 6.6 中作为默认调度器替代 CFS。EEVDF 的思想源自实时调度领域的最早截止时间优先（EDF），但巧妙引入「合格时间（eligible time）」概念以解决 EDF 在过载时的「多米诺效应」。EEVDF 是对 CFS 的一次工程级重构，保持公平性语义的同时提供 O(log n) 的延迟保证。

二、CFS 完全公平调度器深度剖析

2.1 核心概念：Virtual Runtime（虚拟运行时间）

CFS 的核心指标是 vruntime（virtual runtime），即进程在虚拟时钟上的累计运行时间。其更新公式如下：

delta_vruntime = delta_exec * NICE_0_LOAD / se.load.weight

delta_exec：进程实际消耗的 CPU 时间（纳秒）
NICE_0_LOAD：nice 0 对应的负载权重（默认 1024）
se.load.weight：进程对应的调度实体权重，由 nice 值决定

nice 值越低的进程（优先级越高），权重越大，vruntime 增长越慢——这意味着它被调度的频率更高。nice 0 的权重为 1024，nice -1 的权重为 1277，nice +1 的权重为 820，每差一个 nice 级，CPU 占比差约 10%。

2.2 红黑树（Red-Black Tree）数据结构

CFS 使用红黑树（rbtree）来组织所有可运行进程，以 vruntime 为排序键。树的最左节点即为 vruntime 最小、最「亏欠」的进程，被选为下一个执行者。

struct cfs_rq {
    struct rb_root_cached tasks_timeline;  // 红黑树根（带缓存最左节点）
    struct sched_entity *curr;             // 当前运行实体
    struct sched_entity *next;             // 下一个要执行的实体（用于抢占）
    struct sched_entity *last;             // 上次执行的实体（保持缓存热度）
    unsigned long h_nr_running;            // 可运行任务数
    ...
};

红黑树的插入和删除操作是 O(log n)，查找最左节点为 O(1)（通过 rb_leftmost 缓存）。这意味着即使系统有上万个可运行进程，调度决策的开销依然非常小。

2.3 调度实体（sched_entity）层级

不是每个进程都直接关联红黑树节点。CFS 使用 sched_entity 抽象，支持组调度（Group Scheduling）和 cgroups 带宽控制：

struct sched_entity {
    struct load_weight load;        // 权重（由nice值映射）
    struct rb_node run_node;        // 红黑树节点
    unsigned int on_rq;             // 是否在运行队列
    u64 exec_start;                 // 当前执行段开始时间
    u64 sum_exec_runtime;           // 累计运行时间
    u64 vruntime;                   // 虚拟运行时间
    u64 prev_sum_exec_runtime;      // 上次运行时总时间
    struct cfs_rq *cfs_rq;          // 所属CFS运行队列
    struct my_q *my_q;              // 如果是组，指向子CFS队列
    ...
};

当进程属于某个 cgroup 时，其 sched_entity 会挂在父 cfs_rq 的红黑树上，进程自身的 cfs_rq 在组层面维护。这种层级化设计实现了 CPU 带宽在组间的公平分配。

2.4 调度时钟周期（tick / 周期性调度检查）

CFS 在每个定时器中断（tick）或 tickless 内核的 hrtimer 到期时，会执行 task_tick_fair()：

更新当前进程的 vruntime
检查当前进程的 vruntime 是否仍小于最左节点（即是否被新到进程超越）
如果被超越，设置 need_resched 标志，申请抢占
如果未被超过最小粒度（sysctl_sched_min_granularity），允许继续执行

关键可调参数：

sched_latency_ns（默认 24ms）：一个调度周期内，所有可运行进程至少运行一次的时间长度
sched_min_granularity_ns（默认 3ms）：进程最小连续执行时间，低于此值不触发抢占
sched_wakeup_granularity_ns（默认 4ms）：唤醒抢占粒度

实际调度周期 = max(sched_latency_ns / nr_running, sched_min_granularity_ns)

2.5 负载权重表（prio_to_weight）

内核预定义了一个从 nice 值到权重的映射表：

static const int 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 级的权重比值约为 1.25。因此，nice 0 和 nice +1 的进程在相同时间内获得的 CPU 比例为 1024:820 ≈ 1.25:1。

2.6 组调度与 cgroups v1 CPU 带宽控制

CFS 无缝支持 cgroup v1 的 CPU 带宽控制：

cpu.shares：组间 CPU 份额比例。默认 1024，A 组 2048、B 组 1024 意味着 A 获得 2/3 CPU
cpu.cfs_period_us + cpu.cfs_quota_us：硬限制，如 period=100000、quota=50000 表示每 100ms 内最多使用 50ms CPU

cgroup v2 进一步通过 cpu.weight 和 cpu.max 统一了这两类配置。

2.7 NUMA 感知调度

在 NUMA 架构下，CFS 与内核的 NUMA balancing 机制协作：

进程的 vruntime 中包含 NUMA 局部的「迁移代价」惩罚
唤醒时倾向于选择 NUMA 亲和的 CPU 运行
负载均衡在 NUMA 节点内优先，跨节点后有更高的迁移代价门槛
通过 numactl --cpunodebind 或 taskset 可以强制绑定 CPU 节点

三、实时调度类与 SCHED_DEADLINE

除了 CFS 管理的普通进程，Linux 还有三个实时调度类，优先级高于 CFS：

3.1 SCHED_FIFO 与 SCHED_RR

SCHED_FIFO：先进先出，高优先级进程一直运行直到主动让出
SCHED_RR：轮转法，同优先级进程按固定时间片（默认 100ms）轮流执行
优先级范围：1~99（数值越大优先级越高）
配置工具：chrt -f -p [priority] [pid]（FIFO），chrt -r -p [priority] [pid]（RR）

3.2 SCHED_DEADLINE — 基于 EDF 的硬实时调度

SCHED_DEADLINE 使用三个参数定义周期性任务模型：

runtime = 10ms    # 每个周期内需要执行的时间
deadline = 20ms   # 完成截止时间
period = 50ms     # 任务周期

可调度性判定：Σ(runtime_i / period_i) ≤ 1.0

该调度类使用红黑树按 deadline 排序，在每次调度时选择 deadline 最近的任务。它实现了 Constant Bandwidth Server（CBS）算法处理非周期性行为：当任务在 deadline 之后还没结束，CBS 将其 deadline 推迟一个 period，但不会允许它抢占其他已就绪的 DEADLINE 任务，避免了「饥饿链」。

内核会做准入控制（admission control），如果 Σ(runtime/period) > 1.0，sched_setattr() 会返回 EBUSY。

四、EEVDF：下一代调度器

4.1 CFS 的工程痛点

尽管 CFS 已服役近 20 年，但在日益复杂的计算场景下暴露出几个问题：

延迟抖动：CFS 的「延迟目标」参数是启发式的，无法给出严格的延迟上界保证
抢占延迟：CFS 的 wakeup_preempt 逻辑通过 wakeup_granularity 参数微调，但这不是基于严格的截止时间推导
维护复杂度：CFS 的补丁不断累积，特殊功能使代码复杂度急剧膨胀
缓存亲和性妥协：CFS 用 next/last 缓存优化亲和性，但这破坏了公平性的严格性

4.2 EEVDF 的核心思想

EEVDF 融合了三个核心概念：

Virtual Runtime（vruntime）：继承自 CFS，保证长期公平性
Virtual Deadline（vdl）：每个调度实体的虚拟截止时间，vdl = vruntime + 配额
Eligible time（合格时间）：一个实体必须等到其 eligible time 后才能参与调度

EEVDF 的红黑树以 vruntime + lag 为排序键，在满足合格性条件的前提下选择最左节点。

4.3 EEVDF 调度周期

EEVDF 的一个调度周期内，每个实体运行其时间片长度（slice），slice 大小取决于就绪数量：

slice = max(sched_period / nr_running, sysctl_sched_min_granularity)

关键性质：

任何时刻，最多只有一个实体的 lag 为负（即欠债状态）
lag 为负的实体总是排在树的最前，实际上是「立即调度」
通过 lag 机制，EEVDF 比 CFS 更精确地实现了公平性保证

4.4 EEVDF vs CFS 关键差异

维度	CFS	EEVDF
排序键	vruntime（虚时间累计）	vruntime + lag（含亏欠补偿）
时间片分配	delta_exec / 权重	固定 slice（period/nr_running）
抢占条件	wakeup_granularity（启发式）	严格基于 deadline 的 O(1) 检查
延迟保证	启发式近似	严格的 O(log n) 延迟上界
唤醒抢占	依赖经验参数	自适应，无需调参
代码复杂度	大量特例	精简约 2000 行差异

4.5 EEVDF 的实践部署

在 Linux 6.6+ 上，EEVDF 已成为默认调度器。检查当前调度器版本：

$ dmesg | grep -i eevdf
$ uname -r    # 需要 >= 6.6

对于延迟敏感型应用（音视频处理、高频交易、实时音视频），建议：

使用 sched_setattr() + SCHED_DEADLINE 获取硬实时保证
或使用 SCHED_FIFO/SCHED_RR 配合 isolcpus 内核参数隔离专用 CPU
对于通用延迟要求，EEVDF 的默认行为已优于 CFS

五、调度器性能分析与调优实战

5.1 调度延迟分析工具箱

perf sched — 调度事件记录与分析：

# 记录 30 秒调度事件
perf sched record -a sleep 30

# 生成延迟直方图
perf sched latency --sort max

# 可视化时间线
perf sched map

# 统计汇总
perf sched script | head -100

schedstat — 内核调度统计：

/proc/schedstat                                       # 全局统计
/sys/devices/system/cpu/cpu0/schedstat                 # 每CPU统计
/proc/<pid>/sched                                     # 进程级调度统计

关键字段解释：

se.exec_start — 当前段开始时间（ns时钟）
se.vruntime — 虚拟运行时间
se.sum_exec_runtime — 累计实际运行时间
se.load.weight — 当前权重
nr_switches — 上下文切换次数
nr_voluntary_switches / nr_involuntary_switches — 主动让出/被抢占

5.2 运行时参数调优

# 查看当前调度参数
sysctl kernel.sched_latency_ns          # 默认 24000000（24ms）
sysctl kernel.sched_min_granularity_ns  # 默认 3000000（3ms）
sysctl kernel.sched_wakeup_granularity_ns # 默认 4000000（4ms）
sysctl kernel.sched_migration_cost_ns   # 默认 500000（0.5ms）
sysctl kernel.sched_autogroup_enabled   # 默认 1（开）

# 交互式优化（桌面/低延迟场景）
sysctl -w kernel.sched_latency_ns=12000000
sysctl -w kernel.sched_min_granularity_ns=1500000
sysctl -w kernel.sched_wakeup_granularity_ns=2000000

# 吞吐量优化（批处理/HPC场景）
sysctl -w kernel.sched_latency_ns=48000000
sysctl -w kernel.sched_min_granularity_ns=6000000
sysctl -w kernel.sched_wakeup_granularity_ns=8000000

5.3 CPU 频率对调度的影响

现代 CPU 的调频策略与调度器密切相关：

schedutil governor 直接与调度器挂钩，当检测到高负载时立即升频
schedutil 使用 sched_irqwork_pending 和 cpufreq_update_util() 在每次调度 tick 和任务唤醒时更新频率请求
相比 ondemand 和 performance governor，schedutil 在调度器感知延迟需求和能效平衡上表现最佳
推荐配置：echo schedutil > /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor

5.4 cgroup v2 CPU 控制实践

# 创建 cgroup v2 子组
mkdir /sys/fs/cgroup/myapp

# 设置 CPU 权重（cgroup v2 替代 cpu.shares）
echo 200 > /sys/fs/cgroup/myapp/cpu.weight     # 范围 1~10000

# 设置 CPU 硬限制
echo "50000 100000" > /sys/fs/cgroup/myapp/cpu.max  # 每100ms用50ms

# 将进程加入 cgroup
echo $PID > /sys/fs/cgroup/myapp/cgroup.procs

# 查看实际使用情况
cat /sys/fs/cgroup/myapp/cpu.stat
# nr_periods / nr_throttled / throttled_usec 等字段

六、内核模块实战：自定义调度类简介

为了深入理解调度器的运行，可以自定义一个最简单的 LIFO 调度类（演示目的，仅用于学习）：

// minimal_sched_class.c
#include <linux/module.h>
#include <linux/sched.h>
#include <linux/sched/task.h>

static const struct sched_class minimal_sched_class = {
    .next = &fair_sched_class,
    .enqueue_task = minimal_enqueue_task,
    .dequeue_task = minimal_dequeue_task,
    .pick_next_task = minimal_pick_next_task,
    .task_tick      = minimal_task_tick,
};

// 调度类链表：stop_sched_class → dl_sched_class → rt_sched_class → fair_sched_class → idle_sched_class
MODULE_LICENSE("GPL");

实际上，自定义调度类需要实现 sched_class 结构体中的多个函数指针，按照优先级顺序插入调度类链表中。这在生产环境中极少需要，主要用于教育目的和极端定制化需求。

七、常见调度问题与排障

7.1 优先级反转（Priority Inversion）

当高优先级进程等待低优先级进程持有的锁时，如果低优先级进程被中等优先级进程抢占，就会形成死锁级联。Linux 内核通过 Priority Inheritance（PI）互斥锁解决：

// 创建 PI mutex
pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
pthread_mutex_init(&lock, &attr);

当高优先级进程阻塞在低优先级进程持有的 PI-mutex 时，内核暂时提升低优先级进程的优先级到等待者中的最高优先级，使其尽快执行释放锁。

7.2 CPU 暴涨与调度器 Bug 排查

系统 CPU 使用率异常高但无可见进程占用大量 CPU，可能是调度器相关内核线程异常：

# 检查 softirq/ksoftirqd 占用
top -H -p $(pgrep ksoftirqd)

# 检查 RCU 回调积压
cat /sys/kernel/debug/rcu/rcu_preempt/rcudata

# 检查调度器 tick 配置
cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor

# 检查 IRQ风暴
perf top -e irq:irq_handler_entry

7.3 NUMA 调度失衡

NUMA 系统上频繁跨节点访问内存导致性能严重下降：

# 查看 NUMA 拓扑
numactl --hardware

# 查看进程 NUMA 内存分布
numastat -p $PID

# 强制进程绑定到 NUMA node 0
numactl --cpunodebind=0 --membind=0 ./myapp

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

八、总结与展望

Linux 调度器从 O(n) 到 O(1) 到 CFS 再到 EEVDF，每一次变革都是在公平性、延迟保证和工程复杂度之间寻找更优的平衡点。CFS 以其简洁的公平性证明和优秀的通用性统治了近 20 年，而 EEVDF 的引入则标志着 Linux 进入「严格延迟保证」的新时代。

对于不同场景的推荐策略：

桌面/低延迟交互：EEVDF 默认 + schedutil governor + 较低的 latency_ns
数据库/OLTP：EEVDF + SCHED_RR 隔离关键 IO 线程到独立核（isolcpus）+ 绑定中断
HPC/批处理：CFS 调高 latency_ns，或使用 SCHED_BATCH 进行周期性大吞吐任务
实时控制/音视频：SCHED_DEADLINE + RT_PREEMPT 补丁 + 核心隔离

随着异构计算（big.LITTLE/Intel Thread Director）和云端混部的普及，调度器也在持续演进。sched_ext（schedular extensible）框架在 Linux 6.12+ 允许用户态定义调度策略，进一步将调度器从内核态解放出来，值得持续关注。

点赞(0) 打赏

本文分类：Linux内核
本文标签：Linux 内核调度器 CFS EEVDF 进程管理实时系统
浏览次数：1 次浏览
发布日期：2026-10-08 12:43:51
本文链接：https://www.ybb.press/linux-kernel/15967.html

Linux 内核进程调度器深度实战：从 CFS 完全公平调度器到 EEVDF 最早虚拟截止时间优先

Linux 内核进程调度器深度实战：从 CFS 完全公平调度器到 EEVDF 最早虚拟截止时间优先

一、调度器的历史演进

1.1 O(n) 调度器（Linux 2.4 时代）

1.2 O(1) 调度器（Linux 2.6.0 ~ 2.6.22）

1.3 CFS 完全公平调度器（Linux 2.6.23 ~ 至今）

1.4 EEVDF 最早虚拟截止时间优先（Linux 6.6+）

二、CFS 完全公平调度器深度剖析

2.1 核心概念：Virtual Runtime（虚拟运行时间）

2.2 红黑树（Red-Black Tree）数据结构

2.3 调度实体（sched_entity）层级

2.4 调度时钟周期（tick / 周期性调度检查）

2.5 负载权重表（prio_to_weight）

2.6 组调度与 cgroups v1 CPU 带宽控制

2.7 NUMA 感知调度

三、实时调度类与 SCHED_DEADLINE

3.1 SCHED_FIFO 与 SCHED_RR

3.2 SCHED_DEADLINE — 基于 EDF 的硬实时调度

四、EEVDF：下一代调度器

4.1 CFS 的工程痛点

4.2 EEVDF 的核心思想

4.3 EEVDF 调度周期

4.4 EEVDF vs CFS 关键差异

4.5 EEVDF 的实践部署

五、调度器性能分析与调优实战

5.1 调度延迟分析工具箱

5.2 运行时参数调优

5.3 CPU 频率对调度的影响

5.4 cgroup v2 CPU 控制实践

六、内核模块实战：自定义调度类简介

七、常见调度问题与排障

7.1 优先级反转（Priority Inversion）

7.2 CPU 暴涨与调度器 Bug 排查

7.3 NUMA 调度失衡

八、总结与展望

评论列表共有 0 条评论

发表评论取消回复

Linux 内核进程调度器深度实战：从 CFS 完全公平调度器到 EEVDF 最早虚拟截止时间优先

Linux 内核进程调度器深度实战：从 CFS 完全公平调度器到 EEVDF 最早虚拟截止时间优先

一、调度器的历史演进

1.1 O(n) 调度器（Linux 2.4 时代）

1.2 O(1) 调度器（Linux 2.6.0 ~ 2.6.22）

1.3 CFS 完全公平调度器（Linux 2.6.23 ~ 至今）

1.4 EEVDF 最早虚拟截止时间优先（Linux 6.6+）

二、CFS 完全公平调度器深度剖析

2.1 核心概念：Virtual Runtime（虚拟运行时间）

2.2 红黑树（Red-Black Tree）数据结构

2.3 调度实体（sched_entity）层级

2.4 调度时钟周期（tick / 周期性调度检查）

2.5 负载权重表（prio_to_weight）

2.6 组调度与 cgroups v1 CPU 带宽控制

2.7 NUMA 感知调度

三、实时调度类与 SCHED_DEADLINE

3.1 SCHED_FIFO 与 SCHED_RR

3.2 SCHED_DEADLINE — 基于 EDF 的硬实时调度

四、EEVDF：下一代调度器

4.1 CFS 的工程痛点

4.2 EEVDF 的核心思想

4.3 EEVDF 调度周期

4.4 EEVDF vs CFS 关键差异

4.5 EEVDF 的实践部署

五、调度器性能分析与调优实战

5.1 调度延迟分析工具箱

5.2 运行时参数调优

5.3 CPU 频率对调度的影响

5.4 cgroup v2 CPU 控制实践

六、内核模块实战：自定义调度类简介

七、常见调度问题与排障

7.1 优先级反转（Priority Inversion）

7.2 CPU 暴涨与调度器 Bug 排查

7.3 NUMA 调度失衡

八、总结与展望

深入解析 Linux CFS 完全公平调度器：从红黑树到 vruntime 的算法之美

Linux 内核进程调度器深度实战：从 CFS 完全公平调度器到 EEVDF 最早虚拟截止时间优先

Linux 容器网络深度实战：从 Docker 网络模型到 Kubernetes CNI

Linux epoll 高性能 I/O 深度实战：从 select 演进到百万并发架构

评论列表 共有 0 条评论

发表评论 取消回复

评论列表共有 0 条评论

发表评论取消回复