Linux 调度器：从 CFS 到 EEVDF

你的笔记本上现在大概跑着一千多个线程，而 CPU 只有八到十六个逻辑核。每过几毫秒，内核就要回答一次同一个问题：下一微秒，这个核给谁？

这个问题看起来像个排序题，其实是个不可能三角。三个目标同时压在同一段代码上：

• 公平——不能让某个进程饿死，也不能让 nice -19 的备份任务把浏览器挤没；
• 低延迟——你敲下按键到光标出现，中间可能要唤醒五六个线程，每一次唤醒都得尽快拿到 CPU；
• 高吞吐——每次切换任务要刷 TLB、丢失 L1/L2 缓存热度，代价在微秒量级，切得越勤，真正干活的时间越少。

三者互相拆台。绝对公平意味着谁都不许插队，交互延迟就完蛋；为了低延迟疯狂抢占，上下文切换的开销会把吞吐吃掉；为了吞吐把时间片放大到几十毫秒，鼠标就会顿。Linux 在这个三角里的两次主要答案，就是 2007 年的 CFS 和 2023 年的 EEVDF。

这篇文章要讲清楚它们各自把公平变成了什么样的数学量、这个量怎么落到一棵树上、CFS 为什么在延迟这一维上一直靠补丁续命，以及为什么 EEVDF 被认为是更干净的模型。

破除误解#

误解一：CFS 的"完全公平"意思是每个进程分到一样多的 CPU。

不是。CFS 的公平是按权重的比例公平，而且公平的对象是"虚拟时间"而非墙钟时间。两个 nice 0 的进程确实各拿 50%，但一个 nice 0 和一个 nice 5 的进程分到的是约 75% 和 25%——权重表里 nice 0 是 1024，nice 5 是 335。更关键的是，CFS 只保证长期积分上的比例正确，它对"你什么时候拿到你那一份"几乎不作承诺。一个刚被唤醒的线程可能要等好几毫秒才轮到，而这段等待完全不违反"完全公平"。这条缝隙就是后面所有麻烦的来源。

误解二：调度器的主要工作是"决定下一个跑谁"。

在单个 CPU 的运行队列里挑任务，代码量其实很小——CFS 时代那部分核心逻辑只有几百行。kernel/sched/fair.c 有一万多行，大头在负载均衡：任务该放在哪个核上、什么时候从别的核偷任务、怎么照顾 SMT 超线程共享执行单元、怎么避免跨 NUMA 节点搬迁把缓存亲和性毁掉、怎么在 big.LITTLE 上区分大小核。EEVDF 换掉的只是"挑谁 + 何时抢占"这一层，负载均衡那一万行原封未动。

误解三：EEVDF 是一个全新调度器，CFS 被删掉了。

代码还在 kernel/sched/fair.c，调度类还叫 fair_sched_class，用户态看到的策略号还是 SCHED_NORMAL，cgroup 接口还叫 cpu.cfs_quota_us 和 cpu.cfs_period_us。PELT 负载跟踪、cgroup 带宽控制、组调度全都保留。被替换的是三件事：用什么判断该谁跑、时间片怎么定、什么时候允许抢占。这是一次核心规则的置换，不是一次重写。

CFS：把公平压缩成一个可比较的数#

CFS（Completely Fair Scheduler）由 Ingo Molnár 编写，随 2.6.23 内核于 2007 年 10 月发布，取代了 2002 年进入开发树的 O(1) 调度器。它的出发点是一个想象中的理想机器：

一台"理想的、精确的多任务 CPU"，能让 n 个任务同时各以 1/n 的速度运行。

真实 CPU 一次只能跑一个任务，所以 CFS 的做法是：记录每个任务偏离这台理想机器有多远，然后总是让偏离最多的那个先跑。

vruntime：给不同优先级换算成同一种货币#

每个任务带一个 vruntime（虚拟运行时间，单位纳秒）。任务实际跑了 delta 纳秒之后，它的 vruntime 增加：

delta_vruntime = delta_exec × NICE_0_LOAD / weight     // NICE_0_LOAD = 1024
```

含义很直白：权重越大的任务，跑同样长的真实时间，账上记的虚拟时间越少。这相当于给高优先级任务发了一种"贬值更慢的货币"。于是所有任务的 vruntime 变得可以直接比大小，不管它们的 nice 值差多少。CFS 的调度规则从此只剩一句话：谁的 vruntime 最小，谁先跑。

nice 值到权重的换算是内核里一张写死的表 sched_prio_to_weight[]，相邻两级的比值约 1.25：

选 1.25 这个比值有个明确目的：内核注释里称之为"10% 效应"——在任意一级上加减 1，该任务相对其他任务的 CPU 份额就变化约 10%。这样 nice 值的语义与绝对优先级无关，只与相对差值有关，符合大多数人的直觉。

红黑树：每次 O(log n) 找到"欠得最多"的那个#

所有可运行任务按 vruntime 插进一棵红黑树（cfs_rq->tasks_timeline）。最左侧节点就是 vruntime 最小的任务，也就是下一个该跑的。内核把这个位置缓存在 rb_leftmost 里，所以"挑下一个"是 O(1)，插入和删除是 O(log n)。

运行队列还维护一个单调不减的 min_vruntime，作为新任务和被唤醒任务的入队基准——否则一个刚 fork 出来、vruntime 为 0 的进程会被当成"欠了一辈子"，从而独占 CPU 直到追上其他人。

时间片：从"周期"倒推出来#

CFS 号称"没有时间片"，实际上它有，只是时间片是算出来的。目标调度周期 sched_latency_ns 默认 6 ms，并按 CPU 数取对数放大（6 ms × (1 + ilog2(ncpus))，四核上约 18 ms）。一个任务在一个周期里分到的时间是：

slice = sched_latency × weight_i / Σ weight
```

再加两个约束：单次不得短于 sched_min_granularity_ns（默认 0.75 ms，同样按 CPU 数放大），以及当可运行任务超过 sched_nr_latency = 8 个时，周期改为 nr_running × min_granularity，防止任务一多时间片碎成尘。

举个具体例子。假设周期 6 ms，三个任务的 nice 分别是 0、0、5（权重 1024、1024、335，总和 2383）：

• 两个 nice 0 各分到 6 × 1024/2383 ≈ 2.58 ms；
• nice 5 分到 6 × 335/2383 ≈ 0.84 ms。

漂亮的地方在于：nice 5 那个任务跑 0.84 ms，vruntime 却增加 0.84 × 1024/335 ≈ 2.57 ms。三个任务在一轮之后 vruntime 增量几乎相同，红黑树里的相对位置自然轮转。权重、时间片、排序，被同一个公式串成了一件事。

CFS 的结构性弱点：公平管得住总量，管不住时刻#

问题出在开头那句话上：CFS 只约束长期积分。

设想一个音频线程，每 10 ms 醒一次，每次只需要 200 µs 填一次缓冲区。它的长期 CPU 占用率只有 2%，vruntime 增长极慢，看起来永远"欠着"。这似乎意味着它一醒来就该被立刻选中——但事实并非如此简单，因为：

1. 它睡觉时被移出了红黑树，vruntime 停止增长；回来时如果直接用原值入队，它会因为"欠得太多"而长时间霸占 CPU；
2. 所以 CFS 用 min_vruntime 把它拉回来，但拉多少是个纯粹的经验判断；
3. 拉得太狠，它醒来后要排队等好几毫秒，音频就爆音；拉得太松，一个反复短睡的进程可以靠"装可怜"骗到超额 CPU。

内核对这个两难的回答，是一层又一层的启发式开关（都挂在 /sys/kernel/debug/sched/features，5.13 之前在 /proc/sys/kernel/）：

这些开关每一个单独看都有道理，合起来却没人能说清系统的整体语义是什么。它们之间还互相耦合：调大唤醒粒度会削弱睡眠者补偿的效果，打开 buddy 又会让唤醒粒度的判断落空。更根本的问题是，用户态没有任何办法表达"我这个线程对延迟敏感"。SCHEDFIFO/SCHEDRR 这些实时策略能做到，但需要特权，而且一个跑飞的实时线程可以直接锁死整机。社区为此提出过多年的 latency-nice 接口——给每个任务一个独立于 nice 的延迟偏好——但始终没能就语义达成一致：它到底该影响抢占判断、唤醒选核，还是时间片？

Peter Zijlstra 在 2023 年 3 月提出替代方案时的说法很直接：这套东西该整个换掉，"它彻底重做了基础调度器：放置、抢占、挑选——所有环节"。

EEVDF：把"多快拿到"变成模型里的一等公民#

EEVDF 的全称是 Earliest Eligible Virtual Deadline First（最早合格虚拟截止期优先），来自 Ion Stoica 与 Hussein Abdel-Wahab 1995 年在 Old Dominion 大学的技术报告。它比 CFS 还早十二年，而且当年就是冲着"比例份额 + 软实时延迟保证"设计的。Zijlstra 的实现随 Linux 6.6 于 2023 年 10 月合入，2024 年的后续工作在 6.12 收尾。

它引入三个概念，替换掉上面整张表。

一、滞后（lag）：一本明确的欠账簿#

定义一个"零滞后点" V，即所有可运行任务 vruntime 的加权平均：

V = Σ(w_i × v_i) / Σ w_i
lag_i = w_i × (V − v_i)
```

内核里 cfs_rq->avg_vruntime 存的就是分子（相对某个基准以防溢出），avg_load 存分母。含义：lag 为正表示"系统欠这个任务时间"，为负表示"这个任务已经超支"。CFS 里"欠多少"只能靠比较 vruntime 间接推断，EEVDF 里它是个显式的量。

二、资格（eligible）：超支的人先别急#

只有 lag ≥ 0（等价于 v_i ≤ V）的任务才有资格被选中。 这一条就是公平的全部保证——不管你把时间片设成多短、多频繁地要求运行，只要你超支了就自动出局，直到 V 涨上来把你重新变成合格。这正是 CFS 那些防作弊启发式想做却做不干净的事。

三、虚拟截止期：延迟偏好的旋钮#

每个任务带一个"请求大小" slice——它希望一次连续跑多久。虚拟截止期是：

deadline_i = vruntime_i + slice_i × 1024 / weight_i
```

在所有合格任务中，挑虚拟截止期最早的那个。

这个式子的效果值得停下来体会。同样是 nice 0（权重 1024）：

• 声明 slice = 0.75 ms（默认）→ 截止期 = v + 0.75 ms；
• 声明 slice = 0.1 ms（延迟敏感）→ 截止期 = v + 0.1 ms，明显更早。

于是延迟敏感的任务几乎每次合格时都会被优先选中，但每次只跑 0.1 ms。它插队的频率高了，拿走的总量却没变——因为总量由资格条件（lag ≥ 0）独立守住。反过来，一个批处理任务可以声明 10 ms 的长 slice，换来更少的切换、更热的缓存、更高的吞吐，代价是被选中的频率降低。

延迟和吞吐第一次变成同一个旋钮的两端，而这个旋钮不影响公平。 这是 EEVDF 相对 CFS 最实质的进步：CFS 里想降延迟只能调全局的 sched_latency，那会同时改变所有任务的行为。

权重也自然地融进来：nice 5（权重 335）用默认 slice 时，截止期是 v + 0.75 × 1024/335 ≈ v + 2.29 ms，比 nice 0 晚得多，自然被选中得更少。优先级和延迟偏好在同一个公式里，不再需要两套机制。

数据结构：增广红黑树#

CFS 只需要"最左节点"，所以缓存一个指针就够了。EEVDF 要在合格集合（按 vruntime 排序的一个前缀）里找截止期最早的节点——两个不同的键。实现方式是增广红黑树：树仍按 vruntime 排序，但每个节点额外维护"以我为根的子树中最小的截止期"。pick_eevdf() 沿树下行时用这个增广字段剪枝，仍是 O(log n)。插入时用 rb_add_augmented_cached() 顺带维护增广值。

配套的参数只剩一个：sched_base_slice_ns，默认 750000 ns（0.75 ms），同样按 CPU 数对数放大。从 6.12 起，用户态可以用 sched_setattr() 的 sched_runtime 字段为普通任务指定 slice，范围 100 µs 到 100 ms——这就是 latency-nice 争论多年没做成的那个接口，最终以"请求大小"的形式落地。

被删掉的东西是这次改动最能说明问题的部分：sched_latency_ns、sched_min_granularity_ns、sched_wakeup_granularity_ns 这三个调优旋钮，以及 GENTLE_FAIR_SLEEPERS、START_DEBIT 这些特性开关，全部消失。抢占判断也变简单了：新唤醒任务的虚拟截止期比当前任务早，就抢占，不再需要一个凭经验设定的阈值。

两代模型对照#

EEVDF 放弃了什么#

只讲优点的对比表是没用的。这次替换有明确的代价。

睡眠任务的 lag 怎么办，是最难的一块。 如果任务一睡就把负 lag 清零，那么"跑一会儿→睡一下→回来重新变成合格"就是一条稳定的作弊路径。6.6 的做法是入睡时保留 lag，醒来时再按 lag 重新放置 vruntime。这在原理上正确，但意味着一个超支后睡了很久的任务，回来还得先还债，在批处理与交互混合的负载上确实制造了一批回归报告。6.12 引入 DELAY_DEQUEUE（延迟出队）来收口：负 lag 的任务入睡时不立刻离开运行队列，而是留在树上让 lag 沿虚拟时间衰减，等还清了再真正出队。这比"直接清零"和"永久记账"都更接近模型本意，但它也是一处新的复杂度。

6.6 的截止期基准是工程妥协。 论文里 deadline = eligible_time + request/weight，其中 eligible time 是任务重新变得合格的那个时刻；Linux 的实现直接用了当前 vruntime。在多数情况下两者接近，但这意味着内核里的 EEVDF 并不是论文的严格实现，它继承了论文的结构而非论文的全部保证。

短 slice 的吞吐代价是真的。 把 slice 从 0.75 ms 降到 0.1 ms，同样的 CPU 时间里上下文切换次数增加数倍，每次切换伴随流水线清空、TLB 与缓存失效。EEVDF 让你更精确地做这笔交易，但没有让交易本身消失。

用户态声明的 slice 没有准入控制。 sched_setattr() 设置短 slice 不需要特权（这正是设计目标——不想再走 SCHED_FIFO 那条特权路），代价是所有人都可以声明 100 µs。当机器上每个进程都自称延迟敏感时，短 slice 提供的相对优势归零，只剩下切换开销。这是典型的公地问题，模型本身解不了。

跨 CPU 的公平仍然不归 EEVDF 管。 lag、资格、截止期全都是单个运行队列内部的概念。任务放在哪个核上、什么时候被迁走，依然由 PELT 负载跟踪和周期性负载均衡决定。EEVDF 让一个核内部的行为变干净了，多核层面的老问题一个没少。

为什么调度器是内核里最难改的子系统之一#

第一，没有正确性判据。 文件系统写坏数据是 bug，网络协议栈丢包是 bug，调度器"某个负载慢了 8%"算不算 bug？取决于问的是谁。任何调度改动都是零和的：让交互任务更快，就是让别人更慢。所以调度补丁的评审标准不是"对不对"，而是"哪些 benchmark 涨了、哪些掉了、掉的那些能不能接受"。

第二，失效是统计性的，几乎无法归因。 EuroSys 2016 的论文《The Linux Scheduler: a Decade of Wasted Cores》（Lozi、Lepers、Funston、Gaud、Quéma、Fedorova）是这方面的经典证据：作者在负载均衡代码里找到四个 bug，会让部分核心在有就绪任务排队时长时间空转。后果是 make 内核延迟高出 13%、某商业数据库的 TPC-H 吞吐下降 14–23%，而同步密集的科学计算负载出现数倍差距。这些 bug 潜伏多年没人发现，不是因为没人用 Linux，而是因为没人能把"我的程序有点慢"追溯到调度器的某一行。作者最后只能自己写可视化工具来看清运行队列的状态。

第三，硬件太不一样了。 同一份代码要同时跑在双核 ARM 手机、有大小核的笔记本、单插槽 128 核的服务器、以及跨多个 NUMA 节点和多个 CCX 的双路机器上。缓存共享边界、迁移代价、频率调节延迟在这些平台上差一到两个数量级。调度器还与 cpufreq（schedutil 调速器直接读调度器的利用率信号）和 cpuidle（唤醒空闲核要付出退出深睡眠的延迟）双向耦合——改调度可能连带改了功耗和频率行为。

第四，cgroup 带宽控制这一层还在上面叠加语义。 cpu.cfs_period_us 默认 100 ms，cpu.cfs_quota_us 决定每周期能用多少。Kubernetes 上给容器设 CPU limit 就是在写这两个值，而"限制 2 核"实际含义是"每 100 ms 用满 200 ms 就停到周期结束"——如果应用在前 30 ms 就用完配额，剩下 70 ms 全部被节流，表现为周期性的延迟毛刺。5.4 修掉了一个让本地 CPU 剩余配额被过早作废的问题（在高核数机器上尤其严重），5.14 又加了 cpu.cfs_burst_us 允许跨周期攒一点额度。这些机制与 EEVDF 的 lag 语义如何交互，本身就是一个未完全探明的区域——6.6 合入时，EEVDF 与组调度的配合就被明确列为待验证项。

第五，社会性阻力。 2007 年 Ingo Molnár 提交 CFS 时，明确写过是 Con Kolivas 的 RSDL/SD 调度器证明了"公平调度是可行的，而且桌面表现更好"。但最终被合并的是 Molnár 的实现，Kolivas 随后离开了内核开发。这件事之后常被引用，不是因为谁对谁错，而是因为它展示了一个结构性事实：调度器只有一个，槽位只有一个，任何替代方案都必须先说服所有人放弃现有的那个。

最后一点正在改变。Linux 6.12（2024 年 11 月）合入了 sched_ext，允许把调度策略写成 BPF 程序从用户态加载，运行时切换，出问题自动回退到内核默认调度器。它没有改变上面四个技术难点，但改变了第五个：试一个新调度策略的成本，从"改内核 + 说服 Linus + 等三年"降到了"加载一个程序"。 对一个二十年只换过两次核心模型的子系统来说，这可能比 EEVDF 本身影响更远。

跨域连接#

• 概率论：调度器面对的从来不是一组已知长度的作业，而是服务时间分布未知、且通常重尾的请求流——排队论的结论是，当服务时间方差很大时，先来先服务的平均等待会被少数长作业彻底拖垮，而"处理器共享"（processor sharing）恰恰是对分布形状最不敏感的策略之一；CFS 的 vruntime 正是处理器共享的离散近似，这解释了它为什么在平均意义上足够好。但均值的稳健不等于尾部的稳健：p99 延迟由"最坏一次被插队多久"决定，而这正是 EEVDF 用虚拟截止期显式限定的量。
• 电网：最大的实时平衡系统：CPU 时间和电力一样无法库存，发多少必须当场用掉——电网的经济调度按边际成本排序机组，同时必须逐秒满足供需相等的硬约束，这与调度器"按权重排序 + 每个时刻有且只有一个任务占用核"的结构完全同构；cgroup 的配额与 burst 机制就是需求响应和调峰的翻版：允许短时超发，但要在周期尺度上把账还回来。电网的教训同样适用——系统稳定靠的不是平均功率对得上，而是秒级偏差被压住，这正是"长期公平但瞬时抖动"的 CFS 所忽略的那一维。
• 公地治理：一台机器上的 CPU 时间是标准的公共池资源——Ostrom 归纳的可持续治理规则里，最关键的两条是"占用规则必须与资源状况匹配"和"存在低成本的冲突解决机制"；CFS 的 vruntime 账本就是一套占用规则，nice 值则是一种非对称权限，任何进程可以自降优先级，提升却需要 CAPSYSNICE。EEVDF 把 slice 开放给用户态时正面撞上了同一个问题：没有准入控制，人人都声明 100 µs 就等于人人都没有优先，制度设计上唯一的出路仍是配额或计费。
• 失效分析：从事故残骸中长出来的工程：调度改动可怕的地方在于失效模式是统计性的——失效分析要求可复现的失效路径与清晰的根因链条，而调度回归的典型形态是"某客户的某负载在某代 CPU 上 p99 涨了 15%"，中间隔着调频、缓存亲和、NUMA 放置等十几个混杂因子，二分定位到单一提交往往不可行。这解释了为什么社区宁可长期堆启发式补丁也不敢换模型：在缺乏可靠归因手段的系统里，任何重写都是拿已知的坏去换未知的坏，而后者无法定价。
• 科学与技术研究（STS）：2007 年 CFS 与 Con Kolivas 方案的那场竞争是 STS 的标准素材——技术物里嵌着关于"什么算公平"的价值判断，而判定优劣的 benchmark 集合本身是被社区选定的：桌面交互的流畅感难以量化，hackbench 与数据库吞吐却有现成数字，于是可测量的目标系统性地压过不可测量的目标。EEVDF 的意义不只在算法更优，还在于它把"延迟需求"变成了一个可以被声明、被记录、被测量的参数，从而改变了这场争论里哪一方手里有证据可用。

参考文献#

• Ion Stoica, Hussein Abdel-Wahab, Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation, Old Dominion University Technical Report TR-95-22, 1995.
• Linux 内核文档，EEVDF Scheduler（Documentation/scheduler/sched-eevdf.rst）与 CFS Scheduler（sched-design-CFS.rst），docs.kernel.org，持续更新。
• Jonathan Corbet, "An EEVDF CPU scheduler for Linux", LWN.net, 2023 年 3 月。
• Jonathan Corbet, "Completing the EEVDF scheduler", LWN.net, 2024 年 4 月。
• Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Quéma, Alexandra Fedorova, "The Linux Scheduler: a Decade of Wasted Cores", EuroSys 2016。
• Linux 内核文档，CFS Bandwidth Control（Documentation/scheduler/sched-bwc.rst），docs.kernel.org。

延伸阅读#

• Robert Love, Linux Kernel Development（第 3 版，2010）第 4 章"进程调度"：CFS 从 O(1) 调度器演化而来的完整代码级讲解，是理解 vruntime 与红黑树实现的最短路径。
• Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces（免费在线）调度相关章节：多级反馈队列与比例份额调度的原理对照，讲清楚了 CFS 这一支路线在调度算法谱系里的位置。
• Linux 内核文档 Extensible Scheduler Class（Documentation/scheduler/sched-ext.rst）与 sched-ext 项目文档：如何用 BPF 写一个可热插拔的调度器，以及为什么这会改变调度器演进的节奏。