第 10 章 · 多处理器调度

一句话 + 关键问题

如何在多个 CPU 上调度作业？操作系统应该如何在多个 CPU 上调度作业？会出现哪些新问题？老办法还管用吗，还是需要新思路？

CRUX: HOW TO SCHEDULE JOBS ON MULTIPLE CPUS — How should the OS schedule jobs on multiple CPUs? What new problems arise? Do the same old techniques work, or are new ideas required?

多处理器系统曾经只存在于高端计算领域，如今桌面机、笔记本甚至手机上都有了。原因是多核处理器（multicore）：架构师很难在不耗费过多功耗的情况下让单个 CPU 变得更快，于是把多个 CPU 核心封装到一个芯片上。

多 CPU 带来很多难题。对应用来说，一个普通的 C 程序只用一个 CPU，加再多 CPU 也不会让它变快，得用线程把它改写成并行程序（本书第二部分"并发"会详细讨论）。对操作系统来说，新问题是多处理器调度（multiprocessor scheduling）：前几章的单处理器调度原则怎么扩展到多个 CPU？要理解它，关键在于硬件缓存在多 CPU 之间如何共享数据。

这是一个"高级章节"：它逻辑上属于虚拟化部分（CPU 调度），但要真正理解，最好先学过并发部分。建议可以在学完第二部分后再回来细读；本页已经把需要的并发背景（锁、竞争条件）用图解补上了。

核心概念速览

缓存（cache）与局部性

小而快的存储，保存主存中热门数据的副本。依赖时间局部性和空间局部性。

缓存一致性（cache coherence）

多个 CPU 各有缓存时，同一地址可能在不同缓存中有不同的值。硬件负责保证"单一共享内存"的视图。

总线窥探（bus snooping）

每个缓存监视连接主存的总线；看到别人更新了自己持有的数据，就使之失效或更新它。

别忘了同步

硬件一致性不等于程序正确：跨 CPU 更新共享数据结构仍需要锁，而锁在 CPU 多时会变慢。

缓存亲和性（cache affinity）

进程在某个 CPU 上运行时会在其缓存中积累状态，下次最好还在同一个 CPU 上运行。

SQMS 单队列

所有作业放一个队列。简单、天然负载均衡，但扩展性差（锁）且缺乏亲和性。

MQMS 多队列

每个 CPU 一个队列。可扩展、天然亲和，但会负载不均衡（load imbalance）。

迁移与工作窃取

把作业从一个 CPU 移到另一个（migration）。工作窃取（work stealing）：作业少的队列偶尔偷看别的队列，并"偷"走作业。

图解讲解

10.1 背景：多处理器架构

单 CPU 系统有一个硬件缓存层次结构，帮助处理器更快地运行程序。缓存保存主存中热门数据的副本；主存保存全部数据，但访问更慢。程序第一次 load 某个数据时，它在主存中，需要很长时间（几十甚至上百纳秒）；处理器预期它会被复用，就把副本放进 CPU 缓存（比如 64KB）。下次再取同一个数据时先查缓存，命中就只需几纳秒。

缓存依赖局部性（locality）：时间局部性（temporal locality）——一个数据被访问后很可能很快再次被访问（循环中反复使用的变量和指令）；空间局部性（spatial locality）——访问了地址 x 的数据后，很可能访问 x 附近的数据（遍历数组、顺序执行指令）。

单 CPU 与多 CPU 的缓存结构。多个 CPU 共享一个主存时，缓存会变得复杂得多。

缓存一致性问题

设想 CPU 1 上的程序读地址 A 的数据（值为 D）：缓存中没有，于是从主存取来 D。程序接着把 A 处的值改成 D′，只更新了自己的缓存（一路写回主存很慢，系统通常稍后再写）。然后操作系统把程序移到 CPU 2 上运行，程序再次读地址 A：CPU 2 的缓存中没有，于是从主存取——得到的是旧值 D，而不是正确的 D′。糟糕！这就是缓存一致性（cache coherence）问题。单步看看，并对比开启总线窥探后的情形：

开启总线窥探（写时使其他缓存的副本失效）

缓存一致性：没有一致性协议时，迁移到 CPU 2 的程序读到了过时的 D；有了总线窥探，CPU 1 写 A 时其他缓存中的副本被作废，CPU 2 读 A 时由 CPU 1 的缓存提供最新值 D′。

基本的解决方案由硬件提供：通过监控内存访问，硬件保证"正确的事"发生，保持单一共享内存的视图。在基于总线的系统上，一种办法是古老的总线窥探（bus snooping）技术：每个缓存都监视连接它们与主存的总线上的内存更新；当某个 CPU 看到自己缓存中持有的数据被更新时，就使其失效（invalidate）（从自己的缓存中删除）或更新（update）它（把新值也放进自己的缓存）。写回缓存（write-back cache）让这件事更复杂（写到主存的操作要稍后才可见），但基本思路可以想象。

10.2 别忘了同步

既然缓存已经做了这么多工作来提供一致性，程序（或操作系统本身）访问共享数据时还需要担心什么吗？很不幸，需要。跨 CPU 访问（特别是更新）共享的数据项或数据结构时，应该使用互斥原语（如锁）来保证正确性（无锁数据结构等其他办法很复杂，只偶尔使用）。例如多个 CPU 同时访问一个共享队列，即使底层有一致性协议，不加锁地并发增删元素也不会得到预期结果。下面是从共享链表删除一个元素的代码：

加锁：在开头 lock(&m)，结尾 unlock(&m)

图 10.3　简单的链表删除代码。蓝色 = CPU 1 上的线程 1 刚执行的行，橙色 = CPU 2 上的线程 2 刚执行的行。不加锁时两个线程都拿到同一个旧 head：A 被 free 两次、值被返回两次，B 还被"跳过"丢失了。

线程 1 执行第一行，把 head 的当前值存进它的 tmp；线程 2 接着也执行第一行，也得到同样的 head 值（tmp 在栈上分配，每个线程各有一份）。于是两个线程不是各删一个元素，而是都试图删除同一个头元素，导致各种问题（例如第 10 行对同一个元素 double free，以及可能两次返回同一个值）。解决方法当然是加锁：分配一个互斥量（如 pthread_mutex_t m;），在函数开头 lock(&m)、结尾 unlock(&m)。但这有性能问题：CPU 数量增加时，访问一个被同步保护的共享数据结构会变得相当慢。

10.3 最后一个问题：缓存亲和性

构建多处理器缓存调度器还有一个问题：缓存亲和性（cache affinity）。进程在某个 CPU 上运行时，会在该 CPU 的缓存（和 TLB）中积累相当多的状态。下次运行时，如果还在同一个 CPU 上，由于部分状态已经在缓存中，它会运行得更快；如果每次都换 CPU，它每次都要重新加载状态，性能会变差（注意：因为硬件的缓存一致性协议，它在别的 CPU 上仍能正确运行）。因此多处理器调度器在做决策时应该考虑缓存亲和性，尽可能让进程留在同一个 CPU 上。

缓存亲和性示意：同样的 CPU 时间，缓存热的时候完成的工作更多。

10.4 单队列调度（SQMS）

最基本的做法是直接复用单处理器调度的框架：把所有需要调度的作业放进一个队列，称为单队列多处理器调度（single-queue multiprocessor scheduling, SQMS）。优点是简单：把一个"挑出最佳作业"的现有策略改成在多个 CPU 上工作不需要多少工作（比如有两个 CPU，就挑最好的两个）。但 SQMS 有明显缺陷：

缺乏可扩展性（scalability）：为保证调度器在多 CPU 上正确工作，代码中要加锁；而锁会大大降低性能，特别是 CPU 数目增加时。对这把锁的争用越激烈，系统花在锁开销上的时间越多，做正事的时间越少。
缓存亲和性：假设有 5 个作业（A、B、C、D、E）和 4 个处理器，每个 CPU 运行一个时间片后从全局队列取下一个作业，每个作业都会在 CPU 之间跳来跳去——与缓存亲和性的要求正好相反。

SQMS 下的一种可能调度（队列：A B C D E）：每个作业在 CPU 之间来回跳。本图由下方模拟器的 SQMS 策略生成，与原书完全一致。

为此，大多数 SQMS 调度器加入了某种亲和性机制，尽量让进程继续在同一个 CPU 上运行：对部分作业提供亲和性，而移动另一些作业来平衡负载。例如：

带亲和性的 SQMS（原书示例）：A 到 D 不在处理器之间移动，只有 E 在 CPU 之间迁移，保住了大多数作业的亲和性。下次还可以换一个作业来迁移，从而实现某种"亲和性公平"——但实现这样的方案可能很复杂。

所以 SQMS 有长处也有短处：给定一个现成的单 CPU 调度器（按定义只有一个队列），实现 SQMS 很直接；但它扩展性不好（同步开销），也不容易保持缓存亲和性。

10.5 多队列调度（MQMS）

由于单队列调度器的问题，一些系统使用多个队列，比如每个 CPU 一个，称为多队列多处理器调度（multi-queue multiprocessor scheduling, MQMS）。每个队列可以使用自己的调度规则（比如轮转，当然任何算法都可以）。作业进入系统时，按某种启发式规则（随机，或者选作业较少的队列）被放入恰好一个调度队列，此后基本上独立调度，避免了单队列方法中信息共享和同步的问题。

例如两个 CPU（CPU 0、CPU 1），作业 A、B、C、D 进入系统，操作系统可能这样放：Q0 = {A, C}，Q1 = {B, D}。用轮转策略，得到的调度可能是：

MQMS：Q0 = A C，Q1 = B D，每个队列各自轮转。作业待在同一个 CPU 上，天然具有缓存亲和性。

MQMS 比 SQMS 有明显的优势：天然更具可扩展性——CPU 增多，队列也增多，锁和缓存争用不会成为核心问题；而且天然提供缓存亲和性。但它有一个根本性的新问题：负载不均衡（load imbalance）。假设 C 完成了：

C 完成后：Q0 = A，Q1 = B D。A 得到的 CPU 是 B 和 D 的两倍——这不是我们想要的结果。

更糟的情况：A 和 C 都完成了，只剩 B 和 D。CPU 0 空闲！（此处插入戏剧性的阴森音乐）

如何处理负载不均衡？多队列多处理器调度器应该如何处理负载不均衡，从而更好地实现它的调度目标？

CRUX: HOW TO DEAL WITH LOAD IMBALANCE

显然的答案是移动作业，这种技术称为迁移（migration）。把作业从一个 CPU 迁移到另一个，就能实现真正的负载均衡。只剩 B、D 时很简单：把 B 或 D 之一移到 CPU 0 即可。更棘手的是 A 单独在 CPU 0、B 和 D 在 CPU 1 交替的情形：一次迁移解决不了问题，答案是持续地迁移一个或多个作业。例如下面的时间线：一开始 A 独占 CPU 0，B 和 D 在 CPU 1 交替；几个时间片后把 B 移过去与 A 竞争 CPU 0，D 则独享 CPU 1 几个时间片……负载就均衡了：

持续迁移实现负载均衡（原书示例）。当然还有很多其他可能的迁移模式。

那系统该如何决定何时迁移？一种基本方法是工作窃取（work stealing）：作业较少的（源）队列偶尔偷看一下另一个（目标）队列有多满；如果目标队列（明显）比源队列满，源队列就从目标队列"偷"走一个或多个作业来平衡负载。这里有天然的张力：看得太频繁，开销就大，难以扩展——而扩展性正是实现多队列调度的初衷；看得太少，又可能遭受严重的负载不均衡。找到合适的阈值，和系统策略设计中常见的情形一样，是一门黑艺术。

10.6 Linux 多处理器调度器

有趣的是，Linux 社区并没有形成统一的多处理器调度方案，先后出现了三种：

调度器	队列	思路
O(1) 调度器	多队列	基于优先级（类似 MLFQ），随时间改变进程优先级，调度最高优先级的进程以实现各种目标，特别关注交互性。
完全公平调度器（CFS）	多队列	确定性的比例份额方法（更像第 9 章的步长调度）。
BF 调度器（BFS）	单队列	三者中唯一的单队列方法，也是比例份额，但基于更复杂的"最早合格虚拟截止时间优先（EEVDF）"方案。

这说明单队列和多队列两种方法都能成功。（BF 代表什么请自行查阅——事先警告，不适合胆小者。）

交互模拟器

模拟器

多处理器调度：SQMS vs MQMS，缓存变暖后运行更快

仿照 OSTEP 作业 multi.py 的模型：每个 CPU 有大小为 M 的缓存；作业有运行时间和工作集大小；作业在某个 CPU 上连续累计运行满"预热时间"且工作集装得下时，该 CPU 的缓存对它变"热"，之后每 tick 完成"加速倍率"份工作。观察：作业在 CPU 间的迁移（▼）、冷/热运行、负载不均衡与工作窃取。

载入示例：

策略 CPU 数时间片缓存大小 M 预热时间热缓存加速倍率

工作窃取偷看间隔 P 窃取阈值

种子

作业	运行时间	工作集	限定 CPU（-A）

缓存热（快）缓存冷（慢）▼ 迁移（换了 CPU）竖线 = 当前 tick

先预测再验证

（课后题 1、2）一个 CPU、一个作业 a（运行时间 30，工作集 200），缓存 100，要多久？把缓存加到 300 呢？（预热时间 10，加速倍率 2）

看答案

缓存 100 时工作集装不下，缓存永远是冷的：30。缓存 300 时，前 10 个 tick 冷运行完成 10 份工作，缓存变热后剩下 20 份工作以 2 倍速度用 10 个 tick 完成：20。点预设"课后题 1""课后题 2"验证，注意面板中缓存条何时出现 a。

（课后题 5）两个 CPU，三个作业 a:100:100、b:100:50、c:100:50，用集中式（SQMS）轮转调度，多久完成？缓存被有效利用了吗？

看答案

本模拟器中为 150——总工作量 300 平摊到两个 CPU 上，几乎没有得到加速。作业在两个 CPU 之间不断迁移（统计里迁移次数很多），而且 a 的工作集 100 会把整个缓存占满、与 b、c 互相驱逐，缓存很少是热的。

（课后题 6）同样三个作业，把 a 限定在 CPU 0，b、c 限定在 CPU 1。预测完成时间，并解释为什么更快。

看答案

110。CPU 0 上 a 独享缓存：10 个冷 tick 后以 2 倍速度完成剩下 90，共 55。CPU 1 上 b、c 的工作集 50+50 = 100 恰好装得下，两者都预热后以 2 倍速度轮转：b 在 105、c 在 110 完成。其他组合（比如 a 和 b 放一起）会让工作集超出缓存，互相驱逐，更慢。

（课后题 7）三个作业都是 100:100。缓存 50 时，1、2、3 个 CPU 分别要多久？缓存 100 呢？什么是"超线性加速"？

看答案

缓存 50 时工作集永远装不下：300、150、100，线性加速。缓存 100 时：1 个 CPU 300（三者轮流、互相驱逐），2 个 CPU 150，3 个 CPU 只要 55——每个作业独占一个 CPU 和它的缓存，变热后跑得更快，加速比 300/55 ≈ 5.5 > 3，这就是超线性加速（super-linear speedup）：多了 CPU 的同时也多了缓存。

（课后题 8）MQMS + 工作窃取，两个 CPU，a:100:100、b:100:50、c:100:50。偷看间隔 P 变小或变大时，完成时间怎样变化？

看答案

初始放置为 Q0 = {a, c}、Q1 = {b}。CPU 1 上的 b 很快完成，之后 CPU 1 空闲，直到下一次偷看才把 c 偷过来。P 越小，空闲越短：本模拟器中 P = 5 时约 85，P = 30 时 105，P = 100 时 130，P = 1000 时（相当于不偷）200。现实中 P 太小的代价是频繁查看其他队列带来的开销和锁争用（本模拟器没有计算这部分开销）。

（C 实验）运行 ./affinity 之前先预测：工作集 64KB 时，"每遍都换 CPU"比"一直待在一个 CPU 上"慢几倍？工作集 64MB 时呢？

看答案

本机实测：64KB 时约慢 5 倍（2.9 ns → 15 ns 每条缓存行）。64KB 装得进每个核私有的 L1/L2，固定在一个 CPU 上时全部命中；换了 CPU，新核的缓存是冷的，脏数据还在旧核那边，每一行都要经缓存一致性协议搬过来。64MB 时几乎没有差别：工作集远超 16MB 的共享 L3，无论在哪个 CPU 上，每次访问都要去内存。亲和性只在"工作集装得进私有缓存"时才重要。

动手实验：测量缓存亲和性

程序 affinity.c 把工作集切成 64 字节缓存行，串成随机顺序的环，一遍遍"走"它（读下一跳、写本行）。pin 模式用 sched_setaffinity() 把自己固定在 CPU 0；migrate 模式每走完一遍就换到另一个 CPU。随机顺序的指针追逐让硬件预取器帮不上忙，测到的就是真实的访存延迟。

cd labs/10-multicpu && make
./affinity                 # 扫描 16KB ~ 64MB 的工作集，约 5 秒
./affinity 256 401 0 1     # 256KB，401 遍，在 CPU 0 和 CPU 1 之间迁移

示例输出（本机：AMD Ryzen 7 8745H，每核 32KB L1d + 1MB L2，8 核共享 16MB L3，WSL2；你的机器上数字会不同）：

$ ./affinity
在线 CPU 16 个；pin = 一直在 CPU 0；migrate = 每遍之后在 CPU 0 和 CPU 2 之间换
每种配置取各遍耗时的中位数，单位：纳秒 / 缓存行（随机顺序访问）

 工作集        pin    migrate    migrate/pin
     16 KB       1.49      11.74           7.9x
     64 KB       2.91      15.13           5.2x
    256 KB       2.87      16.59           5.8x
      1 MB       7.66      13.99           1.8x
      4 MB      11.47      16.83           1.5x
     16 MB      94.21      95.82           1.0x
     64 MB     126.10     118.63           0.9x

怎么读这些数字：

装得进私有缓存（≤ 1MB 的 L2）：迁移慢 4~8 倍。这正是 10.3 节说的：进程在某个 CPU 上积累了缓存状态，换个 CPU 就要重新预热。数据是脏的，还得靠缓存一致性协议从旧核那边搬过来（10.2 节）。
只装得进共享 L3（4MB）：差距缩小。两个核都得去 L3 取数据，在哪儿跑都差不多。
超过 L3（16MB 以上）：没有差别。每次都要访问内存（约 100 ns，其中还有随机访问造成的 TLB 未命中），亲和性无关紧要。
这里每遍都迁移，是最坏情况。真实调度器偶尔迁移一次（比如工作窃取），只付一次预热代价，之后新 CPU 的缓存就热了。所以调度器要在负载均衡和亲和性之间权衡。

自测题

1. CPU 1 修改了地址 A 的值（只写在自己的写回缓存里），随后程序被迁移到 CPU 2 并读 A。如果没有缓存一致性机制，会发生什么？

写回缓存不会立即写到主存，CPU 2 的缓存又没有副本，于是从主存读到旧值 D。总线窥探等一致性协议正是为解决这个问题。

2. 硬件已经保证了缓存一致性，为什么多 CPU 并发操作共享链表仍然需要锁？

图 10.3 中两个线程都读到了同一个 head，这是操作序列的交错问题，与缓存一致性无关，需要互斥来解决。

3. SQMS 的两个主要缺点是？

SQMS 简单且天然负载均衡；负载不均衡是 MQMS 的问题。

4. MQMS 相比 SQMS 的优点和新问题分别是？

每个 CPU 一个队列，作业待在同一个 CPU 上；但作业完成后各队列长度可能不同，甚至有 CPU 空闲。

5. Q0 = {A}，Q1 = {B, D}，都用轮转。为什么一次迁移解决不了不均衡？

这正是书中"continuous migration"的例子：先让 B 去和 A 竞争 CPU 0，过一阵再换，长期看三者份额相同。

6. 关于工作窃取的"偷看频率"，正确的说法是？

原书原话：Finding the right threshold remains, as is common in system policy design, a black art.

7. 3 个作业（工作集都能装进单个 CPU 缓存，但装不下两个）从 1 个 CPU 换到 3 个 CPU，完成时间从 300 降到 55。这种现象叫？

加速比 5.5 大于 CPU 数 3，因为每个作业都能独占一个缓存、以热缓存速度运行。

8. Linux 的三种多处理器调度器中，哪一个使用单队列？

O(1) 和 CFS 都用多队列，BFS 是唯一的单队列方法——说明两条路都能走通。

常见误区

"有了缓存一致性就不需要锁。"一致性保证的是每个地址的值最终一致，不是多步操作的原子性。共享数据结构仍然需要同步。
"作业换到别的 CPU 会算错。"不会——一致性协议保证它照样正确运行，只是缓存是冷的、会变慢。亲和性是性能问题，不是正确性问题。
"MQMS 天然均衡负载。"恰恰相反，负载不均衡是 MQMS 的根本问题；SQMS 才天然均衡（所有 CPU 从同一个队列取作业）。
"多加 CPU，单个程序就会变快。"普通的单线程程序只能用一个 CPU，要改写成多线程才能利用多个 CPU。
"迁移越多，负载越均衡，所以越好。"每次迁移都要付出重新预热缓存的代价，工作窃取本身也有开销；需要在均衡和亲和性之间权衡。

本章小结

多处理器的新问题源于硬件缓存：需要缓存一致性（硬件用总线窥探等协议解决），软件访问共享数据仍需同步（锁，但锁在 CPU 多时变慢），调度要考虑缓存亲和性。
SQMS：实现简单、负载天然均衡，但扩展性差（锁争用）且缺乏亲和性；可以加入亲和性机制，让大多数作业留在原 CPU、少数作业迁移。
MQMS：扩展性好、天然亲和，但有负载不均衡；用迁移（如工作窃取）解决，偷看的频率和阈值需要仔细权衡。
Linux 中 O(1) 与 CFS 是多队列，BFS 是单队列——没有简单答案。构建通用调度器仍然是一项艰巨的任务：小的代码改动可能导致大的行为差异。
这一章把 CPU 虚拟化告一段落。接下来进入内存虚拟化（地址空间）；第二部分"并发"会深入讲本章提到的锁、线程和竞争条件。