CFS（Completely Fair Scheduler，完全公平调度器）是 Linux 普通进程（SCHED_NORMAL/SCHED_BATCH/SCHED_IDLE）曾经使用的调度算法，自 2007 年发布的 Linux 2.6.23 版本起取代了此前的 O(1) 调度器，用红黑树替代了原来的按优先级分桶的数组结构（调度器体系的整体介绍见 Linux 进程调度）。

需要先说明的是：CFS 已经不是当前内核的默认实现。从 2023 年 10 月发布的 Linux 6.6 起，普通进程的默认调度算法换成了 EEVDF，CFS 退居历史。本文仍以 CFS 为主，因为它的 vruntime 和红黑树是理解现在这套调度器的基础。

EEVDF：6.6 之后的默认调度器

EEVDF（Earliest Eligible Virtual Deadline First，最早合格虚拟截止时间优先）由 Peter Zijlstra 实现并在 Linux 6.6 合入，取代 CFS 成为 SCHED_NORMAL 等普通调度策略的默认算法。算法本身并不新，出自 Ion Stoica 和 Hussein Abdel-Wahab 1995 年的一篇论文。

它要解决的是 CFS 的一个短板：CFS 只保证长期的 CPU 时间份额公平，但对"什么时候该轮到我"没有约束，交互式任务的调度延迟不好控制。CFS 时期只能靠 sched_latency_ns 之类的旋钮和一些启发式补偿去调，效果有限。

EEVDF 引入两个概念：

  • lag：进程"应得的 CPU 时间"与"实际获得的 CPU 时间"之差。lag 大于等于 0 说明它还欠着账，才有资格（eligible）被调度；lag 为负说明它已经超额使用，暂时靠边。
  • virtual deadline：在合格的进程中，按各自请求的时间片长度算出一个虚拟截止时间，调度器每次挑选虚拟截止时间最早的那个。

这样一来，份额公平由 lag 保证，响应延迟由 deadline 保证，需要低延迟的任务可以通过请求更短的时间片来更频繁地被调度，而不必牺牲它的总 CPU 份额。

实现上 EEVDF 并没有推倒重来：它仍然复用 CFS 的 fair.c、vruntime 和红黑树这套基础设施，主要换掉的是"挑选下一个进程"的判据——从"取 vruntime 最小的"变成"在合格进程里取虚拟截止时间最早的"。所以下面 CFS 的内容并没有过时，它依然是这套调度器的底座。

为什么会有 CFS：调度算法的演进

调度程序选择下一个可执行进程的算法，随 Linux 内核版本经历了几次重大变化：

  • O(n) 调度器（Linux 2.4）：可执行状态的进程被挂在一个链表中，每次调度都要扫描整个链表找出最优的进程，复杂度为 O(n)，进程数一多性能就明显下降。
  • O(1) 调度器（Linux 2.6 早期，Ingo Molnar 开发）：把进程按优先级（0139，实时进程占 099，普通进程占 100~139）分别挂在 140 个链表里，每个 CPU 维护一个 active 数组和一个 expire 数组；调度器用一个 bitmap 记录哪些优先级链表非空，选择下一个进程时直接查 bitmap 找到最高优先级的非空链表，复杂度降到 O(1)。进程用完时间片就从 active 数组移到 expire 数组，active 数组空了就整体和 expire 数组互换，开始新一轮调度。这个设计解决了扩展性问题，但对交互式/批处理进程的区分依赖平均睡眠时间等经验公式，很容易被一些特殊负载模式（如频繁 IO 但非交互的批处理进程）误判。
  • 楼梯算法 SD（Staircase，Con Kolivas 提出）：放弃了动态优先级估计，改为让进程每用完一次时间片就"下一级楼梯"（优先级降低一级），走到最低一级后回到起点的下一级，并给予双倍时间片，从根本上简化了代码，也证明了"完全公平"思路的可行性。
  • RSDL（Rotating Staircase Deadline，SD 的改进版）：为每个优先级组分配一个"组时间配额"，配额用完后无论组内进程是否都用完了自己的时间片，都强制整体降级，从而给低优先级进程一个可预期的调度延迟上限。
  • CFS（Ingo Molnar 在 RSDL 之后开发，2.6.23 起采用）：不再跟踪睡眠时间、不再区分交互式/批处理进程，用一个统一的"虚拟运行时间"指标对待所有进程，并用红黑树替代 140 个链表来维护进程的调度顺序。
  • EEVDF（Peter Zijlstra 实现，6.6 起采用）：在 CFS 的基础设施上，把选择依据从"vruntime 最小"改为"合格进程中虚拟截止时间最早"，在保持份额公平的同时给调度延迟一个可控的上界（见上文）。

作者 Ingo Molnar 对 CFS 的概括是：“CFS 在真实的硬件上模拟了完全理想的多任务处理器。“在理想的多任务处理器下，n 个可运行进程应该同时各获得 CPU 时间的 1/n；而真实硬件同一时刻只能运行一个进程，CFS 要做的就是让实际调度结果尽可能逼近这个理想状态。

vruntime：虚拟运行时间

CFS 给每个进程维护一个 虚拟运行时间（vruntime）：进程每获得一段 CPU 时间，vruntime 就相应增加；选择下一个执行的进程时，不是选优先级最高的，而是选 vruntime 最小 的——它获得的 CPU 时间最少，理应优先补上。

用一个简化的例子说明。假设系统中有 A、B、C、D 四个进程，当前 vruntime（纳秒）如下：

进程 vruntime
A 1000
B 1200
C 1400
D 1600

此时新建一个进程 E。新进程的 vruntime 不会从 0 开始（否则它会长时间独占 CPU 追平其他进程），而是被设置为当前所有进程里最小的 vruntime，即 A 的 1000：

进程 vruntime
A 1000
E 1000
B 1200
C 1400
D 1600

调度器选择 vruntime 最小的进程执行，A 和 E 并列最小，假设 A 被选中运行。A 运行了 300 纳秒后被换下，vruntime 相应增加到 1300：

进程 vruntime
E 1000
B 1200
A 1300
C 1400
D 1600

A 的排序从并列第一降到了第三位，下一个被调度的进程变成了 E。从本质上看，vruntime 代表了一个进程已经消耗了多少 CPU 时间：消耗得越少，就越应该优先获得计算资源。

nice 值与权重

只按"消耗的 CPU 时间"公平分配，会让进程的优先级（nice 值）变得毫无意义，所以 CFS 会根据进程的 nice 值给 vruntime 的增长速度加权：同样是运行一段时间，nice 值低（优先级高）的进程 vruntime 增长得慢，nice 值高（优先级低）的进程 vruntime 增长得快。vruntime 增长越慢，就越容易保持在红黑树的左侧，从而更频繁地被调度——这样优先级高的进程实际获得的 CPU 时间自然更多。

CFS 如何选择下一个进程：红黑树

CFS 抛弃了 O(1) 调度器的 active/expire 数组，改用一棵按 vruntime 排序的红黑树来管理所有处于 RUNNABLE 状态的进程：

  • 进程入队时，按 vruntime 作为键值插入红黑树；
  • 每次需要选择下一个执行的进程时，直接取红黑树中最左边的节点——它的 vruntime 最小；
  • 红黑树是平衡树，插入和查找的复杂度都是 O(log n)，虽然比 O(1) 调度器名义上的复杂度高，但红黑树对进程数量的取值范围没有限制，能更精细地区分不同进程的调度顺序，实际综合表现优于 O(1) 调度器。

tick 中断中的处理

每次时钟中断（tick）到来时，CFS 会先更新当前正在运行进程的 vruntime，然后把它从红黑树中移除再重新插入（因为 vruntime 变大了，它在树中的位置可能要后移）。如果调整后当前进程不再是红黑树最左边的节点，就说明有其他进程的 vruntime 比它小，内核会设置重新调度标志（_TIF_NEED_RESCHED），等中断返回时触发 schedule() 完成进程切换；否则当前进程继续执行。

这也意味着 CFS 彻底抛弃了传统的"时间片"概念——不再有固定长度的时间片需要在 tick 中被递减，调度粒度可以做得比以前的调度器更小。

参考

维护记录

时间 修改内容 原因
2026-07-19 开头补充 EEVDF 小节并说明 CFS 自 Linux 6.6 起已非默认实现；演进列表追加 EEVDF 条目；补充 scheduler、eevdf 标签与 LWN 参考链接 原文将 CFS 表述为当前内核使用的调度算法，与 6.6 之后的实际情况不符