Linux CFS 完全公平调度器深度拆解

背景：Linux 6.6（2023 年）引入了 EEVDF 调度器替代了 CFS。但 EEVDF 是在 CFS 的 vruntime + 红黑树基础上增加了 deadline 机制，核心思想完全继承自 CFS。理解 CFS 就等于理解了现代 Linux 调度器 90% 的底层逻辑。读完这篇再看 EEVDF，就是顺水推舟的事。

一、调度器到底在解决什么问题

所有调度器都在解决同一个矛盾：

电脑里的CPU就那么几个，进程可能有成百上千个。所以，哪个进程先被调度，处于运行态多久，什么时候调度其他进程。

根据OSTEP中的描述，评价一个调度器好不好，一般看三个维度：

• 性能（Performance） —— 主要看周转时间，就是进程从开始到结束的时间。一般来说，程序越快跑完越好
• 公平（Fairness） —— 每个进程能不能分到该有的 CPU，别让某个进程被饿死。但性能和公平往往是矛盾的，调度器为了优化性能，可能就得让某些进程多等一会
• 响应（Response） —— 交互式程序的响应速度。打个比方，敲击键盘但屏幕半天没反应，那肯定是响应出问题了

传统的多级反馈队列（MLFQ）靠维护多个优先级队列来平衡这三个指标——高优先级先跑，时间片用完降级。问题在于优先级怎么调，调不好交互式进程就卡了。

CFS 的思路完全不一样：它没有运用优先级队列，而是给每个进程记一个"虚拟运行时间"—谁累计用的 CPU 时间最少(也就是后文介绍的vruntime)，谁就上 CPU。

二、vruntime —— CFS 最核心的概念

概念

虚拟运行时间（vruntime，virtual runtime）：每个进程已经消耗的"加权 CPU 时间"，单位是纳秒。

核心公式

vruntime += 实际运行时间 × (1024 / 进程权重)

这个公式的意思很好理解：

• 1024 是 nice=0 时的标准权重
• 进程权重 由 nice 值决定——优先级高的权重大，优先级低的权重小
• (1024 / 权重) 就是一个"放大/缩小系数"

举个例子：

由此可以看出：高优先级的 vruntime 涨得慢，这会是CFS调度器觉得该进程没怎么运行，所以增加该进程的CPU占用时间。反之亦然

根据内核源码验证公式

翻开 kernel/sched/fair.c，通过命令逐步找到vruntime那段：

rr@rr-VMware-Virtual-Platform:~$ cd /usr/src/linux-source-6.8.0/kernel/sched
rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ grep -n "static void update_curr" fair.c
1151:static void update_curr(struct cfs_rq *cfs_rq)
rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ sed -n '1151,1170p' fair.c

static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
s64 delta_exec;

if (unlikely(!curr)) return;
delta_exec = update_curr_se(rq_of(cfs_rq), curr);
if (unlikely(delta_exec <= 0)) return;

curr->vruntime += calc_delta_fair(delta_exec, curr); // vruntime的核心计算
}

rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ grep -n "calc_delta_fair" fair.c | head -3
296:static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ sed -n '296,301p' fair.c

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
// nice=0 权重正好等于 NICE_0_LOAD(1024)，1024/1024=1 无需缩放
if (unlikely(se->load.weight != NICE_0_LOAD))
delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
return delta;
}

调进去看 __calc_delta 的实现，核心逻辑其实就一件事——算 delta_exec × 1024 ÷ weight，运用了一些定点数技巧避免浮点运算和溢出：

static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
// 预计算 inv_weight = 2^32 / weight（用乘法代替除法）
__update_inv_weight(lw);
// delta_exec × 1024 × (2^32 / weight) >> 32 = delta_exec × 1024 / weight
return mul_u64_u32_shr(delta_exec, fact, shift);
}

内核为了性能和精度，没有直接调用除法（慢），而是用 2^32 / weight 乘法 + 移位运算来实现除法——原理跟编译器优化整数除法一样。但不管底层怎么算，最终结果就是：vruntime += delta × 1024 ÷ weight，跟我们前面推的公式一模一样。

阻塞进程醒来怎么办？

如果一个进程阻塞了 100ms，vruntime 还是 0——恢复就绪后 CFS发现了该情况，直接将它插入队列，这就对别的进程不公平。所以内核维护了一个叫 最小虚拟时间（min_vruntime） 的东西，是当前就绪队列里最小的vruntime。进程恢复就绪时：

新 vruntime = max(自己原来的 vruntime, min_vruntime)

比如min_vruntime 已经涨到 80 了？那该阻塞回复就绪态的进程的vruntime就应该从 80 开始，就避免了vruntime太小造成的插队情况。

实际上内核还会从 min_vruntime 里减掉一个很小的偏移量（差不多一个时间片的大小），因为你阻塞时没占 CPU，所以CFS自动补偿了点时间。即不让该进程立刻进入队列，但也不能让其恢复就绪态后等太久——这就是 CFS 在公平和响应之间最精妙的设计。

有了 vruntime 公式，一个自然的问题就来了：公式里的"权重"是怎么来的？这就要说到 nice 值了。

三、nice 值到底怎么影响调度

权重是怎么算的

内核源码：

rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ grep -n "sched_prio_to_weight" ../core.c | head -3
96:const int sched_prio_to_weight[40] = {
rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ sed -n '96,120p' ../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=0 权重 1024
nice=1 权重 1024 ÷ 1.25 ≈ 820
nice=2 权重 820 ÷ 1.25 ≈ 655
…
nice=5 权重 ≈ 335

往上推（优先级提升）：

nice=0 权重 1024
nice=-1 权重 1024 × 1.25 ≈ 1277
nice=-2 权重 1277 × 1.25 ≈ 1586
…
nice=-5 权重 ≈ 3121

两个nice值相差1的进程放一起比

假设两个进程，nice=0（权重 1024）和 nice=1（权重 820）：

nice=0 的 CPU 占比 = 1024 / (1024 + 820) ≈ 55.5%
nice=1 的 CPU 占比 = 820 / (1024 + 820) ≈ 44.5%

差约 11%，跟传统 Unix 里"nice 差 1 对应 10% CPU 差"的语义基本一致。

最极端的情况——nice=0 和 nice=19：

nice=0 占 1024 / (1024 + 15) = 98.6%
nice=19 占 15 / (1024 + 15) = 1.4%

即使是 nice=19 的进程也还能分到 1.4%，可见CFS的公平性，不会饿死任何进程。

那么既然就绪进程按 vruntime 排序，取最小的那个——这个操作每秒发生几百次，用什么数据结构存最合适？

四、底层结构红黑树

从二叉搜索树到红黑树——一路升级了什么

用树来组织就绪进程是最直观的思路，但树的选型经历了好几代演进。

二叉搜索树（BST） 是最朴素的想法：左子节点 < 父节点 < 右子节点。插入、查找、删除平均 O(log n)。但代价是——它不保证平衡。如果你按顺序插入 vruntime = 1, 2, 3, 4, 5…，BST 会退化成一条链表，操作变成 O(n)。调度器每秒查几百次，O(n) 不可接受。

AVL 树 解决了退化问题：它要求"任意节点的左右子树高度差 ≤ 1"，严格保证 O(log n)。代价是插入/删除时可能需要多次旋转来维持这个严格平衡。调度器里进程频繁切换进出，每次插入删除都要旋转——旋转太多所造成的CPU 开销太大。

红黑树 在既考虑平衡度也考虑旋转开销后：它通过 4 条简单的染色规则保证"最长路径不超过最短路径的两倍"——不如 AVL 严格，但足以保证 O(log n)。代价是插入/删除时的旋转次数远少于 AVL。

红黑树的 4 条规则：

1 节点非红即黑
2 根是黑色
3 红节点的子节点必须是黑的（不能连续是红的）
4 根到任意叶子的路径上黑节点数相同

有了这四条，插入/删除后最多旋转 2~3 次就能恢复平衡，O(1) 的修正代价。而且红黑树的查找、插入、删除都是 O(log n)，最左节点（最小值）通过缓存能做到 O(1)——当你不断输入vruntime，它能帮你维护出一棵"最左节点 = 当前最小的 vruntime"的树。

CFS 为什么选红黑树

CFS 需要把就绪进程按 vruntime 排序，每次调度选 vruntime 最小的那个。这个操作太频繁了，选什么数据结构直接决定了调度器性能。

我对比了一下几种候选：

* 数组按下标找是 O(1)，但 CFS 需要按 PID（进程 ID）搜索不是按下标，所以也是 O(n)。

二叉堆各项指标看起来都不错，但有一个致命问题：找指定进程要 O(n) 遍历。因为二叉堆只保证堆顶最小/最大，内部不保证有序。想找某个指定进程，只能遍历整个数组逐个比对——O(n)。而红黑树是严格有序的（左<父<右），二分查找即可 O(log n)。

另外 Linux 内核还做了一个优化：用 rb_root_cached 结构缓存了红黑树最左节点的指针，取最小元素是真正 O(1)，不是 O(log n)。

内核源码：

rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ grep -n "pick_first_entity" fair.c | head -3
828:struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ sed -n '828,838p' fair.c

struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline); // 从缓存取最左节点 O(1)
if (!left)
return NULL;
return __node_2_se(left); // rb_node → sched_entity 的转换
}

rb_first_cached() 直接返回缓存的最左节点指针，O(1)。如果此时最左结点被取走，如果没有新节点插入，那么严谨来说，缓存指针此时指向被删结点右子树的最小值；如果有新节点插入，那么对比是否比缓存的最左节点还小，如果是，只需更改指向即可。

五、调度延迟和最小粒度

矛盾

切换太频繁 → CPU 全花在切换进程上了
切换太少 → 进程等太久，响应差

目标延迟

CFS 定了一个目标：所有就绪进程在 6ms 内至少各跑一次。这个值叫目标延迟（sched_latency_ns），
可以通过 cat /proc/sys/kernel/sched_latency_ns 查看。

2 个进程 → 各跑 3ms → 轮一圈 6ms
4 个进程 → 各跑 1.5ms → 轮一圈 6ms
10 个进程 → 各跑 0.6ms → 轮一圈 6ms

问题来了——进程太多怎么办？

但是实际开发中，我们的电脑都是同时出现大量的并发进程
假如有100 个进程，如果还按照上文逻辑，每个分 6/100 = 0.06ms。上下文切换一次约几微秒，开销占比反超执行时间了。

所以 CFS 设了一个底线：最小粒度（sched_min_granularity_ns）= 0.75ms。每个进程至少跑 0.75ms 才能被换走。

≤ 8 个进程 → 动态分配时间片，6ms 轮一圈
> 8 个进程 → 每人固定 0.75ms，轮一圈超过 6ms（牺牲延迟保效率）

完整公式就一行：

time_slice = max(min_granularity, targeted_latency / nr_running);

六、一次完整的调度是怎么发生的

为什么不能直接在时钟中断里切换？

因为中断处理程序不在进程上下文里——它可能正持有自旋锁，这个时候让它阻塞会死锁。然后就坏菜了。。。。。
所以中断里只做两件事：更新 vruntime、决定要不要切换进程。真要切换则是之后的事。

查询源码，看看时钟中断里具体怎么跑的：

rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ grep -n "static void task_tick_fair" fair.c
12680:static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ sed -n '12680,12693p' fair.c

static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
struct sched_entity *se = &curr->se;
for_each_sched_entity(se) { // 如果有组调度，遍历层级
entity_tick(cfs_rq_of(se), se, queued);
}
}

rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ grep -n "entity_tick" fair.c | head -3
5483:entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ sed -n '5483,5488p' fair.c

entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
update_curr(cfs_rq); // 委托给 update_curr 更新 vruntime
}

调用链：task_tick_fair → entity_tick → update_curr → calc_delta_fair。
每个时钟中断跑一次这个链条，更新当前进程的 vruntime。

完整流程

时钟中断触发后，调度器不会立即切换进程，而是分三步走。每次硬件时钟中断触发 scheduler_tick()，先调 update_curr() 更新当前进程的 vruntime，再调 check_preempt_tick() 检查该不该切换进程——具体判断是算一个预期时间片（= 6ms / 就绪进程数），如果当前进程实际跑超了这个份额，设 TIF_NEED_RESCHED 标志位。但到这里只是做了标记，不切换，因为中断处理程序里可能正持锁，直接切换会导致死锁。真正切换发生在第二步：中断处理结束、准备返回用户态时检查 TIF_NEED_RESCHED，如果设置了就调用 schedule()。第三步由 schedule() 执行真正的切换：pick_next_task() 从红黑树取最左节点（vruntime 最小的进程），然后 context_switch() 保存当前进程的寄存器和栈指针到 PCB，加载新进程的，完成切换。

sched_yield()：主动让出 CPU

Linux 还提供了一个系统调用 sched_yield()，让进程主动放弃 CPU。直接读源码：

rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ grep -n "yield_task_fair" fair.c | head -3
8561:static void yield_task_fair(struct rq *rq)
rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/kernel/sched$ sed -n '8561,8582p' fair.c

static void yield_task_fair(struct rq *rq)
{
struct task_struct *curr = rq->curr;
struct cfs_rq *cfs_rq = task_cfs_rq(curr);
struct sched_entity *se = &curr->se;

if (unlikely(rq->nr_running == 1))
return; // 只有一个进程，yield 之后保持原样

update_curr(cfs_rq); // 先更新 vruntime 到最新值
se->vruntime = cfs_rq->min_vruntime; // vruntime 拉到最小值

__dequeue_entity(cfs_rq, se); // 出队
__enqueue_entity(cfs_rq, se); // 重新入队
}

关键在于理解为什么要 min_vruntime + 出队再入队。
当前进程在红黑树里的位置是按 vruntime 排好的，直接修改 vruntime 而不动树会破坏红黑树的有序性，所以必须先出队再按新值重新入队。设成 min_vruntime 而不是更大值，是为了不让这个进程在树里排得太靠后——它确实想主动让出 CPU，但不是想让自己被饿死。我查阅资料后发现，真正实现"让出"的是 pick_next_entity() 的 last 参数逻辑：last 指向刚让出 CPU 的进程，如果红黑树最左节点就是 last，pick_next_entity() 会跳过它选次小的，让别人先跑。如果就绪队列里只有它自己，last 和 leftmost 是同一个，但就一个进程也选不了别的进程，yield 之后还是返回自身——白白做一次上下文切换。

man 手册也明确说了：

Use of sched_yield() with SCHED_OTHER (即默认 CFS) is unspecified and very likely means your application design is broken.

翻译：在 CFS 下调 sched_yield()，大概率是你代码设计有问题。

正常业务代码不应该用到它，实时调度（SCHED_FIFO 或 SCHED_RR）下才是正确使用场景。

七、上下文切换到底慢在哪

切换一个进程大概要几到十几微秒（因 CPU 架构而异）。开销分成三块：

1 寄存器保存/恢复

把当前进程的所有寄存器值存到 PCB（进程控制块），把下一个进程的寄存器值从它的 PCB 加载回来。纯 CPU 指令操作，相对快。

2 TLB 刷新

TLB 是 CPU 里的"地址翻译缓存"——存着最近用过的虚拟地址到物理地址的映射。切换进程意味着换页表（加载 CR3 寄存器），CPU 硬件检测到 CR3 变了就自动清空所有 TLB。新进程刚开始运行的时候，每次访问内存都要去内存里查页表（TLB 未命中），比 TLB 命中慢一到两个数量级。

3 缓存污染

一个进程跑久了，CPU 的 L1/L2/L3 缓存里全是它的数据。一切换到别的进程，新进程的数据把旧进程的数据挤出缓存。等再切回来的时候，旧进程全得重新从内存加载——主存延迟比 L1 缓存慢一个数量级。这才是上下文切换最贵的部分，占了总开销的大头。

寄存器这一块的具体实现可以看 arch/x86/entry/entry_64.S，上下文切换的汇编代码：

rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/arch/x86/entry$ grep -n "__switch_to_asm" entry_64.S
177:SYM_FUNC_START(__switch_to_asm)
rr@rr-VMware-Virtual-Platform:/usr/src/linux-source-6.8.0/arch/x86/entry$ sed -n '177,216p' entry_64.S

SYM_FUNC_START(__switch_to_asm)
/*
* Save callee-saved registers
*/
pushq %rbp # 保存当前进程的寄存器到自己的内核栈
pushq %rbx
pushq %r12
pushq %r13
pushq %r14
pushq %r15

/* switch stack */
movq %rsp, TASK_threadsp(%rdi) # rdi = prev, 当前栈指针保存到 prev 的 PCB
movq TASK_threadsp(%rsi), %rsp # rsi = next, 加载 next 的栈指针到 rsp

/* restore callee-saved registers */
popq %r15 # 恢复 next 进程之前保存的寄存器
popq %r14
popq %r13
popq %r12
popq %rbx
popq %rbp

jmp __switch_to # 跳到 C 函数 __switch_to 继续处理
SYM_FUNC_END(__switch_to_asm)

八、IO 密集 和 CPU 密集

IO 密集型进程（如文本编辑器、数据库查询）的特点是：跑一小段时间就发起 IO，然后阻塞等待，等 IO 完成后再恢复运行。
CPU 密集型进程（如视频编码、科学计算）的特点是：一直处于就绪队列，持续占用 CPU。

在 CFS 的 vruntime 机制下，这两种进程天然被区别对待。IO 密集进程在阻塞期间不处于就绪队列，vruntime 不增长。恢复就绪时，内核按 新 vruntime = max(原 vruntime, min_vruntime – 补偿) 初始化它的 vruntime。而 CPU 密集进程一直在跑，vruntime 持续增长。所以 IO 密集进程每次恢复就绪时，它的 vruntime 都被拉平到 min_vruntime 附近，天然比 CPU 密集进程的 vruntime 小，CFS 自然优先调度它。

九、CFS 总结

CFS 围绕 vruntime 一个核心概念展开：vruntime 是按权重加权的虚拟运行时间，nice 值通过权重影响 vruntime 增长速率。就绪进程以 vruntime 为 key 组织在红黑树中，每次调度取最左节点（最小值）。调度延迟保证所有就绪进程在规定时间内至少跑一次，最小粒度防止进程太多时切换开销过大。整个调度流程分三步：时钟中断更新 vruntime、设 TIF_NEED_RESCHED 标志、中断返回时检查标志并调 schedule() 切换。IO 密集和 CPU 密集进程由 vruntime 机制自动区别对待，不需要手动干预。

关于 EEVDF…

开篇提了一嘴 EEVDF——Linux 6.6 后接替 CFS 的调度器。理解了 CFS，EEVDF 就很好懂了：

• EEVDF 保留了 CFS 的 vruntime + 红黑树 核心框架
• 在此基础上加了 deadline（截止时间）——每个进程除了有 vruntime，还有一个期望完成时间
• 调度时优先选 deadline 最近的任务，而不是单纯比 vruntime

这样做的好处是交互式进程的响应延迟更可控。CFS 下交互式进程的快速调度靠的是阻塞后 vruntime 不增长、恢复时被自动拉低，这是一种间接的、由时间积累决定的机制。EEVDF 的 deadline 直接表达了"这个进程应该在什么时间前得到 CPU"，调度器据此做优先级判断。

但 vruntime 的计算、nice 值对权重的影响、红黑树维护、调度延迟的分配——这些 CFS 定下来的核心机制，EEVDF 基本都沿用了。

写这篇文章的起因是在读 OSTEP 时发现它对 CFS 的讲解比较简略，大部分篇幅集中在 FIFO、RR、MLFQ 等经典调度算法上，而 CFS——Linux 从 2.6.23 到 6.5 近二十年的默认调度器——只占了很少的篇幅。花了较多时间读内核源码和资料后，整理出了这篇文章。

这是作者关于操作系统系列的第一篇文章，仍在不断学习中，如有错误，欢迎指正。