第 9 章 · 调度：比例份额

一句话 + 关键问题

如何按比例分享 CPU？如何设计调度器来按比例分享 CPU？关键的机制是什么？它们效果如何？

CRUX: HOW TO SHARE THE CPU PROPORTIONALLY — How can we design a scheduler to share the CPU proportionally? What are the key mechanisms for doing so? How effective are they?

前两章的调度器都在优化周转时间或响应时间。本章换一个目标：比例份额（proportional-share）调度器，也叫公平份额（fair-share）调度器，它试图保证每个作业获得一定百分比的 CPU 时间。

我们会看三种做法：用随机数"抽签"的彩票调度（lottery scheduling）（Waldspurger 与 Weihl），确定性的步长调度（stride scheduling），以及曾经最广泛使用的真实调度器——Linux 的完全公平调度器（CFS）。这些思想在虚拟化数据中心里特别有用（比如给 Windows 虚拟机分 1/4 的 CPU），下一章讨论多处理器时也会再次遇到 CFS。

核心概念速览

彩票（ticket）

代表一个进程应得的资源份额：持有的彩票占总数的百分比 = 应得的 CPU 百分比。

彩票调度

每个时间片抽一次奖，中奖彩票的持有者运行。概率上正确，但不保证短期精确。

彩票货币 / 转让 / 通胀

货币（currency）：用户用自己的"币种"分配，系统换算成全局值；转让（transfer）：临时把彩票交给别的进程；通胀（inflation）：临时增减自己的彩票。

公平指标 F

两个相同作业中，先完成者的完成时刻 ÷ 后完成者的完成时刻。越接近 1 越公平。

步长调度（stride）

步长 = 大数 ÷ 票数；每次运行 pass 值最小的进程，并让它的 pass 加上步长。确定性地精确按比例。

虚拟运行时间（vruntime）

CFS 为每个进程累计 vruntime，每次挑 vruntime 最小的运行；权重越大，vruntime 涨得越慢。

sched_latency / min_granularity

时间片 = sched_latency（如 48ms）按权重分给 n 个进程，但不小于 min_granularity（如 6ms）。

nice 与红黑树

nice 值 −20…+19 映射为权重；可运行进程按 vruntime 放在红黑树中，插入/删除都是 O(log n)。

图解讲解

9.1 基本概念：彩票代表份额

彩票调度的核心概念就是彩票（ticket）。例如 A 有 75 张、B 有 25 张，我们希望 A 获得 75% 的 CPU、B 获得 25%。调度器每隔一段时间（比如每个时间片）抽一次奖：知道总共 100 张，从 0–99 中随机选一个中奖号码；A 持有 0–74 号，B 持有 75–99 号，中奖号码落在谁的区间就运行谁。（计算机科学家总是从 0 开始数。）

原书的 20 次中奖号码：63 85 70 39 76 17 29 41 36 39 10 99 68 83 63 62 43 0 49 12。上方数轴：每个号码落在哪个区间；下方：得到的调度序列。B 只运行了 20 个时间片中的 4 个（20%），而不是期望的 25%。

这就是随机性带来的概率正确（probabilistic correctness）：能在期望上满足比例，但不保证。两个作业竞争的时间越长，越可能接近期望的比例。

使用随机性。随机方法相比传统决策至少有三个优点：① 常常能避免奇怪的边角情况——例如 LRU 替换策略在某些循环顺序访问的负载下表现最差，随机则没有这种最坏情况；② 轻量，几乎不需要状态——传统公平份额算法要为每个进程记账，每次运行后都要更新，而随机方法只需要最少的每进程状态（比如票数）；③ 很快，只要生成随机数快，决策就快。当然，需求越快，随机数就越趋向于伪随机。

9.2 彩票机制

彩票调度还提供了几种操纵彩票的机制：

彩票货币（ticket currency）：用户在自己的"币种"里任意分配，系统自动换算成全局彩票。A1、A2 各得 50，B1 得 100。

彩票转让（ticket transfer）：进程可以临时把自己的彩票交给另一个进程。这在客户端/服务器场景特别有用：客户端请求服务器替它做事时，把彩票交给服务器，让服务器更快地处理自己的请求；完成后服务器再把彩票还回来。
彩票通胀（ticket inflation）：进程可以临时增加或减少自己持有的彩票数。在互不信任的竞争环境中这没有意义（贪婪的进程会给自己发大量彩票，占领机器）；但在一组相互信任的进程之间，某个进程需要更多 CPU 时可以提高自己的票值来反映这个需求，而无需与其他进程通信。

用彩票表示份额。彩票是彩票调度和步长调度设计中最强大（也最基本）的机制。它不仅可以表示 CPU 份额，还能用得更广：Waldspurger 在后来关于虚拟机监视器内存管理的工作中，用彩票表示客户操作系统的内存份额。需要表示"所有权比例"时，这个概念可能正是你要的……彩票。

9.3 实现

彩票调度最惊人的地方是实现简单：一个好的随机数生成器选中奖号码，一个记录进程的数据结构（例如链表），以及彩票总数。假设三个进程 A、B、C 分别有 100、50、250 张彩票（共 400 张），在链表中按顺序排列。抽到中奖号码后，遍历链表，用计数器累加票数，直到计数器大于中奖号码：

中奖号码按票数从多到少排列链表

图 9.1　彩票调度的决策代码（逐行执行）。中奖号码 300：counter 依次变为 100（A，小于 300 继续）、150（B，继续）、400（C，大于 300，C 中奖）。

为了让这个过程最高效，通常最好把链表按票数从多到少排序。顺序不影响正确性，但能保证总体上遍历次数最少，尤其是少数进程持有大部分彩票时。勾选上面的选项试试：同样的中奖号码，C 排在最前，一步就找到了（注意：换了顺序后，每个号码对应的中奖者会变，但每个进程中奖的概率不变）。

书中脚注提醒：从一个范围里正确地生成均匀随机数并不容易（例如用 rand() % n 会有偏差）。

9.4 一个例子：公平性研究

两个作业竞争 CPU，彩票数相同（各 100 张），运行时间相同（都是 R，我们会改变它）。我们希望它们大致同时完成，但由于随机性，有时一个会先完成。定义一个简单的公平指标 F：第一个作业完成的时刻除以第二个作业完成的时刻。例如 R = 10，第一个作业在 10 完成、第二个在 20 完成，则 F = 10/20 = 0.5。两个作业几乎同时完成时 F 接近 1——完美公平的调度器应当达到 F = 1。（旧版原书把这个指标称为不公平指标 U，定义相同。）

图 9.2　彩票调度公平性研究：R 从 1 变到 1000（对数横轴），每个点是 30 次试验的平均 F。作业短时平均公平性很低，只有运行足够多个时间片后才接近公平。（本图由本页模拟器实时计算，随机种子不同曲线会略有不同。）

9.5 如何分配彩票？

一个我们还没解决的问题是：怎么给作业分配彩票？这是个难题，因为系统的行为强烈依赖于彩票的分配方式。一种做法是假设用户最清楚：给每个用户一些彩票，由用户分给自己运行的作业。但这其实是个"非解决方案"——它并没有告诉你该怎么做。所以给定一组作业，"彩票分配问题"仍然没有答案。

9.6 步长调度（stride scheduling）

你可能会问：为什么要用随机数？随机让调度器简单（且近似正确），但偶尔不能准确地达到比例，特别是在短时间尺度上。因此 Waldspurger 发明了步长调度——一个确定性的公平份额调度器。

每个作业有一个步长（stride），与票数成反比：用一个大数除以票数。A、B、C 有 100、50、250 张票，用 10000 去除，得到步长 100、200、40。每个进程还有一个计数器，称为行程值（pass），记录它的全局进度：每次运行，就把 pass 加上它的步长。调度时总是挑 pass 最小的进程运行：

curr = remove_min(queue);   // 选 pass 最小的客户
schedule(curr);             // 运行一个时间片
curr->pass += curr->stride; // 用步长更新 pass
insert(queue, curr);        // 放回队列

图 9.3　步长调度的一个轨迹（pass 值相同时任选一个，这里按 A、B、C 的顺序）。一个周期内 C 运行 5 次、A 2 次、B 1 次，恰好与票数 250 : 100 : 50 成比例。

彩票调度在时间上按概率达到比例；步长调度在每个调度周期结束时精确达到比例。那为什么还要用彩票调度？因为它有一个步长调度没有的好性质：没有全局状态。想象在上面的例子中途加入一个新作业，它的 pass 该设为多少？设为 0 的话，它会独占 CPU 很久。而彩票调度没有每进程的全局状态，只需加入新进程、更新一个全局变量（总票数）即可，因此更容易以合理的方式加入新进程。（在下方步长模拟器里可以试试"中途加入"。）

9.7 Linux 完全公平调度器（CFS）

Linux 的 CFS 以另一种方式实现公平份额，而且高效、可扩展。效率很重要：Google 数据中心的研究发现，即使经过积极优化，调度仍然占用了整个数据中心约 5% 的 CPU 时间。

基本操作

大多数调度器基于固定的时间片，CFS 不同。它的目标很简单：在所有竞争进程之间公平地平分 CPU。它用一种计数方法——虚拟运行时间（virtual runtime, vruntime）来做到这一点：每个进程运行时累积 vruntime；最基本的情况下，所有进程的 vruntime 以相同速率随物理时间增长。需要调度时，CFS 选 vruntime 最小的进程运行。

那什么时候停下当前进程？这里有张力：切换太频繁，公平性提高（即使在很短的时间窗口内每个进程也能得到自己的份额），但性能下降（上下文切换太多）；切换不频繁则相反。CFS 用几个参数管理这种张力：

sched_latency（典型值 48ms）：CFS 用它除以 CPU 上运行的进程数 n，得到每个进程的时间片，从而保证在这段时间内完全公平。例如 n = 4 时时间片为 12ms。
min_granularity（通常约 6ms）：时间片永远不会小于它。例如 10 个进程时 48/10 = 4.8ms，但 CFS 会把时间片设为 6ms——在 48ms 的目标延迟内不再完全公平，但接近，同时保持了较高的 CPU 效率。

图 9.4　CFS 简单例子：4 个作业（A、B、C、D）各运行两个 12ms 时间片；C、D 完成后只剩两个作业，各以 24ms 时间片轮转

CFS 使用周期性时钟中断（例如每 1ms 一次），因此只能在固定时间间隔做决策。如果时间片不是中断间隔的整数倍也没关系：CFS 精确地跟踪 vruntime，长期来看会逼近理想的 CPU 共享。（本页模拟器为清晰起见按精确时间片运行。）

权重（niceness）

CFS 也允许控制进程优先级。它不用彩票，而是用经典的 UNIX 机制——进程的 nice 值：可以设为 −20 到 +19，默认 0。正的 nice 值意味着低优先级，负值意味着高优先级（太 nice 了，就得不到那么多调度关注）。CFS 把 nice 值映射为权重：

有了权重，就可以计算每个进程的有效时间片（n 个进程）：

time_slice_k = weight_k / (Σ_i=0ⁿ⁻¹ weight_i) · sched_latency　（式 9.1）

vruntime 的计算也要调整：把进程 i 实际运行的时间 runtime_i 按权重反比缩放，即乘以默认权重 1024（weight₀）除以它的权重：

vruntime_i = vruntime_i + (weight₀ / weight_i) · runtime_i　（式 9.2）

A 的 nice B 的 nice sched_latency ms

书中的例子：A 很宝贵，nice = −5；B 讨人厌（"we hates it"，致敬《指环王》里的咕噜），nice = 0。权重分别是 3121 和 1024，A 的时间片约为 sched_latency 的 3/4（36ms），B 约 1/4（12ms）；A 的 vruntime 以 B 的约三分之一的速率累积。

权重表的构造很巧妙：nice 值之差恒定时，CPU 比例保持不变。例如 A 的 nice 改为 5、B 改为 10，CFS 的调度方式与之前完全相同（上面的计算器里试试）。原因是表中相邻两项之比大约恒为 1.25，所以权重之比只取决于 nice 值之差。

使用红黑树

CFS 的一个重点是效率。调度器需要尽快找到下一个要运行的作业。链表这种简单结构无法扩展：现代系统有时有上千个进程，每隔几毫秒就遍历一次长链表太浪费了。CFS 把进程放在红黑树（red-black tree）中——一种平衡树，它多做一点工作来保持较低的深度，保证操作是对数时间而不是线性时间。

图 9.5　CFS 红黑树：10 个作业的 vruntime 为 1、5、9、10、14、18、17、21、22、24，按 vruntime 组织（树形与原书一致；节点红黑着色是本页补充的一种合法着色）

如果用有序链表，找下一个作业很简单（取第一个元素），但把作业按顺序放回链表需要扫描，是 O(n)；查找平均也是线性的。而红黑树的插入、删除等大多数操作都是 O(log n)。n 上千时，对数比线性明显高效。CFS 并不把所有进程都放在树中，只放正在运行或可运行的进程；进程睡眠（比如等待 I/O 完成或网络包到达）时会从树中移除，在别处记录。

在合适的时候使用高效的数据结构。很多时候链表就够了，很多时候不够。早期调度器用的简单链表在现代系统上表现不好，特别是在数据中心里负载很重、有上千个活跃进程的服务器上。选择数据结构时，要仔细考虑它的访问模式和使用频率。

处理 I/O 和睡眠的进程

选 vruntime 最小者运行，对长时间睡眠的作业会出问题。设 A 一直运行，B 睡了很久（比如 10 秒）。B 醒来时，它的 vruntime 比 A 落后 10 秒；如果不小心，B 会在接下来的 10 秒里独占 CPU 追赶，A 就饿死了。CFS 的办法是：作业醒来时，把它的 vruntime 设为树中的最小值（树里只有正在运行的作业）。这样避免了饥饿，但有代价：频繁短暂睡眠的作业往往永远得不到公平的份额。（下方 CFS 模拟器的"睡眠者"预设可以对比两种做法。）

CFS 还有很多其他特性：提高缓存性能的各种启发式方法、有效处理多 CPU 的策略（下一章讨论）、能以大的进程组为单位调度等。

9.8 小结

彩票调度巧妙地用随机性实现比例份额；步长调度确定性地实现它；CFS 是本章唯一"真实"的调度器，有点像带动态时间片的加权轮转，但为在负载下扩展良好而构建，多年来一直是使用最广泛的公平份额调度器。

没有哪个调度器是万能药。公平份额调度器也有自己的问题：一是与 I/O 配合得不太好——偶尔做 I/O 的作业可能得不到公平的 CPU 份额；二是彩票或优先级分配这个难题仍悬而未决——你的浏览器该分多少票？文本编辑器的 nice 值该设多少？MLFQ 等通用调度器能自动处理这些问题，因此更容易部署。不过在很多领域里这些问题不是主要矛盾，比例份额调度器用得很成功，例如虚拟化数据中心。最后，Linux 一直在变：从 Linux 6.6 起，最早合格虚拟截止时间优先（EEVDF）调度器（另一种公平共享方法）成为默认调度器。

交互模拟器

模拟器

彩票调度：每次抽奖落在哪里？份额如何收敛？

调整每个作业的票数和随机种子，逐次抽奖：数轴上显示中奖号码落在哪个作业的区间；折线图显示每个作业的实际 CPU 份额如何随抽奖次数逐渐收敛到理论比例（虚线）。

预设：

种子抽奖次数

模拟器

公平性 F 与作业长度（图 9.2）

两个票数相同的作业，长度都是 R。每个 R 做若干次试验，画平均 F。加上步长调度的曲线对比（课后题 5），改变时间片大小观察变化（课后题 4）。

每点试验次数时间片种子显示步长调度

彩票调度（平均 F）步长调度单次试验（彩票）的最小 F

模拟器

步长调度：pass 值表逐步推进（图 9.3）

每一步选 pass 最小的作业运行（相同时选靠前的），它的 pass 加上步长。可以设置在第 k 步中途加入一个新作业，比较它的 pass 初值设为 0 与设为当前最小 pass 的区别。

大数步数

在第步前加入 D，票数 D 的 pass 初值

模拟器

Linux CFS：vruntime、动态时间片与 nice 权重

每一步是一次调度决策：可运行作业按 vruntime 排成有序列表（红黑树的中序遍历），CFS 取最左边的作业，按式 9.1 计算它的时间片。改 nice 值、sched_latency、min_granularity 观察时间片和份额的变化。

预设：

sched_latency ms min_granularity ms 加入/唤醒时 vruntime

作业	nice	权重	到达（醒来）	运行时长

先预测再验证

（课后题 2）两个长度都是 10 的作业，作业 0 只有 1 张票，作业 1 有 100 张。作业 0 会在作业 1 完成前运行吗？频率多高？这种票数失衡对彩票调度有什么影响？

看答案

每次抽奖作业 0 只有 1/101 ≈ 1% 的概率中奖。作业 1 需要 10 个时间片，在此期间作业 0 至少运行一次的概率约为 1 − (100/101)¹⁰ ≈ 9.4%。所以大多数情况下作业 0 要等作业 1 完成后才运行——严重的票数失衡使彩票调度的行为接近"严格优先级"。用"课后题 2"预设换几个种子看看。

（课后题 3）两个长度为 100、各 100 张票的作业，调度器有多不公平？用不同种子试试（用 F 或"先完成者早了多少"衡量）。

看答案

在公平性模拟器里看 R = 100 的点：平均 F 大约在 0.93–0.95（先完成的作业平均早完成约 5%–7% 的时间），而 30 次试验中最差的一次 F 可能只有 0.82–0.86（见图中灰色的“最小 F”曲线）。作业越长，这个差距（相对）越小。

（课后题 4）时间片变大时，公平性会怎样变化？

看答案

作业长度固定时，时间片越大，完成所需的抽奖次数越少，随机波动相对越大，F 下降。例如 R = 100、时间片 10 时相当于只抽约 10 次签（每个作业各需 10 次），平均 F 从约 0.94 降到约 0.8–0.85，接近 R = 10、时间片 1 的情形（约 0.85）。把公平性模拟器的时间片改成 10 对比。

（课后题 5）步长调度下，图 9.2 会是什么样子？

看答案

两个票数相同的作业在步长调度下严格交替，先完成者在 2R−1 完成、后完成者在 2R 完成，F = (2R−1)/(2R)：R = 1 时 F = 0.5，R = 10 时已是 0.95，之后迅速逼近 1，而且没有任何随机波动（模拟器中的绿色曲线）。

在步长模拟器里勾选"在第 8 步前加入 D"，D 的 pass 初值设为 0，预测接下来谁会运行多少次？再改成"当前最小 pass"。

看答案

初值为 0 时，D 的 pass 远低于其他作业（它们已经到了几百），D 会连续运行很多次直到追上——这就是书中说的"独占 CPU"。设为当前最小 pass 时，D 立刻与其他作业公平竞争。CFS 对新加入和醒来的进程做的正是类似的事（设为最小 vruntime）。

动手实验：nice 值真的决定 CPU 份额吗？

labs/09-lottery/nice_share.c 创建两个子进程，把它们绑定到同一个 CPU（sched_setaffinity），给其中一个设置 nice 值（setpriority），然后两个进程都拼命做空循环计数若干秒。最后比较两者完成的循环次数之比，与 CFS 权重表算出的理论比例对照。

cd labs/09-lottery && make
./nice_share 0 5 3     # 子进程 1 nice=0，子进程 2 nice=5，运行 3 秒
./nice_share 5 10 3    # nice 差值同样是 5：比例应当几乎不变
sudo ./nice_share -5 0 3  # 负的 nice 需要 root 权限

示例输出（本机 WSL2 实测，你的机器上数字会不同）：

$ ./nice_share 0 5 3
both children pinned to CPU 0, running 3 s
child 1: nice   0  weight  1024  loops  5841542322  share 75.5%  (expected 75.3%)
child 2: nice   5  weight   335  loops  1894193102  share 24.5%  (expected 24.7%)
$ ./nice_share 5 10 3
both children pinned to CPU 0, running 3 s
child 1: nice   5  weight   335  loops  3099903477  share 74.7%  (expected 75.3%)
child 2: nice  10  weight   110  loops  1052312924  share 25.3%  (expected 24.7%)

要观察的点：两个 CPU 密集型进程争同一个 CPU 时，份额非常接近 1024 : 335 ≈ 3 : 1。再试 ./nice_share 5 10 3，比例几乎一样——这正是"nice 差值恒定则比例不变"。注意：Linux 6.6 起默认调度器已换成 EEVDF，但它沿用了同一张 nice→权重表，按权重分配 CPU 的比例行为不变。

自测题

1. A 有 100 张、B 有 50 张、C 有 250 张彩票，按 A、B、C 的顺序存在链表中。中奖号码为 120 时谁运行？

counter 先变为 100（不大于 120，继续），再变为 150（大于 120），所以是 B。中奖号码 0–99 → A，100–149 → B，150–399 → C。

2. 相比步长调度，彩票调度的主要优势是？

步长调度在每个周期结束时精确，但新作业的 pass 初值不好定；彩票调度只需更新总票数。票数分配问题两者都没有解决。

3. 步长调度中 A、B、C 的票数为 100、50、250，大数取 10000。它们的步长分别是？

步长 = 10000 / 票数：10000/100 = 100，10000/50 = 200，10000/250 = 40。票数越多，步长越小，pass 涨得越慢，运行得越频繁。

4. sched_latency = 48ms、min_granularity = 6ms，有 10 个 nice 值都为 0 的进程。CFS 给每个进程的时间片是？

48/10 = 4.8 小于 min_granularity，所以取 6ms。代价是在 48ms 窗口内不再完全公平（10 × 6 = 60ms 才轮完一圈）。

5. A 的 nice = −5（权重 3121），B 的 nice = 0（权重 1024）。以下哪个说法正确？

time_slice 按权重比例分 sched_latency；vruntime 增量 = runtime × 1024 / weight，A 的系数 ≈ 0.33。

6. nice 值从（−5, 0）改为（5, 10），CPU 比例会怎样？

3121/1024 ≈ 3.05，335/110 ≈ 3.05。权重表是按几何级数（约 1.25 倍）构造的。

7. CFS 为什么在进程醒来时把它的 vruntime 设为树中的最小值？代价是什么？

这正是书中"Dealing With I/O And Sleeping Processes"一节的内容。

8. CFS 为什么用红黑树而不是有序链表保存可运行进程？

取最小值两者都快，但把运行完的进程按新 vruntime 放回去时，链表要线性扫描。睡眠的进程不在树中。

常见误区

"彩票调度保证每个作业恰好得到它的比例。"它只在概率上（长期期望上）正确；短时间内可能明显偏离，如原书例子中 B 只得到 20% 而不是 25%。
"步长 = 票数。"步长与票数成反比：票越多，步长越小，pass 增长越慢，越常被选中。
"CFS 有固定的时间片。"CFS 的时间片是动态的：sched_latency 按权重分给当前可运行的进程，并受 min_granularity 下限约束，进程数一变时间片就变。
"nice 值越大优先级越高。"相反，nice 越大（越"客气"），权重越小，得到的 CPU 越少。
"比例份额调度器能解决所有调度问题。"它们与 I/O 配合不佳，并且把"该给多少票 / 设什么 nice"这个难题留给了用户。

本章小结

比例份额调度的目标是让每个作业获得一定百分比的 CPU，而不是优化周转或响应时间。
彩票调度：票数代表份额，随机抽奖决定谁运行；实现极简、无全局状态，但只是概率正确，短作业的公平性较差（图 9.2）。还有货币、转让、通胀等机制。
步长调度：步长 = 大数 / 票数，总是运行 pass 最小者；确定性且精确，但新作业的 pass 初值是个问题。
Linux CFS：按 vruntime 选最小者，时间片由 sched_latency 与权重动态决定（不小于 min_granularity），nice 值通过权重表影响时间片和 vruntime 增速，用红黑树保证 O(log n)，醒来的进程 vruntime 设为最小值以防饥饿。
下一章讨论多处理器调度：多个 CPU、缓存亲和性、单队列与多队列——Linux 的 O(1)、CFS、BFS 分别采用了哪种方式。