多处理机调度

2026 大纲 二（二）5 多处理机调度，是把单 CPU 的调度问题推广到多个处理器之后新增的一层。指标口径沿用调度的基本概念与目标。

核不止一个的时候，调度要多回答两个问题

前面所有调度算法都默认了一件事：只有一个 CPU，所以"选谁"之后直接就上。

多处理机把这个前提拿掉了，于是同一个动作要多回答两个问题： 选出来的这个线程，派到哪个核上？ 以及 各个核之间忙闲不均怎么办？

这两个问题彼此拉扯，方向正好相反：

处理器亲和性说的是尽量让线程回到它上次跑过的那个核—— 因为那个核的 Cache 和 TLB 里还留着它的东西，换个核等于全部重来。

负载均衡说的是尽量把线程从忙的核挪到闲的核—— 否则一个核排长队、另一个核空转。

一个要"别动"，一个要"挪走"。 所以必须有可执行的权衡判据： 迁移节省的等待时间，要大于 Cache 重建 + TLB 重填的代价 （NUMA 机器上还要再加远程访问的增量）。

除此之外还有一处单核时代不存在的坑：持自旋锁的线程被换出。单核上自旋锁本来就没意义；多核上它有意义，但如果持锁的那个线程恰好被调度换下去， 别的核就会成倍地空转等一把当下不可能被释放的锁。应对在调度层是成组调度 / 专用处理机分配，在同步层是临界区内禁止抢占。

一、四种多处理机调度方式

前三种是一条递进的改进链，每一种都在解决前一种暴露出来的问题；第四种把"分几台"这件事本身交给应用程序一起决定。

方式	调度单位	解决了什么	主要代价
自调度	单个线程	设一个公共就绪队列，处理器空闲就自己来取；单机算法（FCFS、优先级等）几乎不改就能搬过来，且处理机不会忙闲不均	公共队列成瓶颈；Cache 效率低；合作线程切换频繁
成组调度	一组合作线程	把一个进程中的一组线程一次性分配到一组处理器上同时执行，需要对方结果时对方正在跑 ⇒ 阻塞与切换大幅减少；且每次调度一次性解决一组，调度频率显著降低	线程少的应用会让处理机空闲，需按线程数分配时间
专用处理机分配	一个应用的全部线程	应用整个执行期间专门为它分配一组处理机、每线程一台，从而完全避免线程切换	线程阻塞时该处理机就空着；线程总数不能超过处理机数
动态调度	作业 + 作业内自行再分配	进程可在执行期间动态改变线程数目，OS 与应用共同决策（OS 遵循空闲则分配、新作业绝对优先、保持等待、释放即分配四条原则），性能最好	开销之大有可能抵消它的一部分优势

自调度还有一个反直觉的实测结论：在单处理机上表现平平的 FCFS，用于多处理机的线程调度时反而优于优先级类算法——线程本身是较小的运行单位，后面的线程等不了多久，而系统有 $N$ 个处理机又能把等待时间进一步减少为 $1 / N$ ；FCFS 简单、开销小，因而成为一种较好的自调度算法。

自调度的三个缺点正好催生了后两种方式：瓶颈问题（唯一队列要互斥访问，数十上百个处理器时抢锁本身成瓶颈）、低效性（线程阻塞后重新就绪只能回到那个唯一队列，很少可能仍在原处理器上运行，Cache 里为它保留的数据全部失效 ⇒ 催生处理器亲和性）、线程切换频繁（一个应用里的多个线程通常相互合作，自调度下很难同时拿到处理机 ⇒ 催生成组调度）。

成组调度里处理机时间怎么分：两种分法的浪费率通式与代数（想会算任意一组线程数的浪费率时展开）

分法	规则	问题
面向所有应用程序平均分配	系统有 $M$ 个应用，每个应用占 $1 / M$ 的时间去使用全部 $N$ 台处理机	线程少的应用运行时，大量处理机空闲
面向所有线程平均分配	按各应用的线程数占总线程数的比例分配时间	浪费明显更少

设某系统有 6 台处理机，同时运行应用 A（6 个线程）与应用 B（2 个线程）。浪费率定义为 $\frac{空闲的处理机 \times 时间}{全部处理机 \times 总时间}$ ，取总时间为 1 个单位。

先把通式写出来，再代数。 设共 $N$ 台处理机，应用 $u$ 有 $k_{u}$ 个线程、占用的时间份额为 $t_{u}$ （ $\sum_{u} t_{u} = 1$ ）。成组调度下应用 $u$ 运行时只用得上 $k_{u}$ 台，其余 $N - k_{u}$ 台空着，于是

浪费率 = \frac{\sum_{u} (N - k_{u}) t_{u}}{N \times 1}

每个应用都要算一项——只有 $k_{u} = N$ 的那个应用这一项才为 0。本例里 A 恰好占满，所以它的项是 0，但这只是数据凑巧，不是规律。

分法一：面向应用平均分配。 $t_{A} = t_{B} = 1 / 2$ 。A 有 6 个线程恰好用满 6 台 ⇒ 它运行的那半段时间里 $6 - 6 = 0$ 台空闲；B 只有 2 个线程 ⇒ 它运行的那半段里有 $6 - 2 = 4$ 台空闲。

空闲处理机 \cdot 时间 = 0 \times \frac{1}{2} + 4 \times \frac{1}{2} = 2, 浪费率 = \frac{2}{6 \times 1} = \frac{1}{3} \approx 33.33 %

分法二：面向线程平均分配。 总线程数 $6 + 2 = 8$ ，故 $t_{A} = 6 / 8 = 3 / 4$ ， $t_{B} = 2 / 8 = 1 / 4$ ——把时间按线程数摊，线程多的应用多分时间，正好让"空闲处理机 × 空闲时长"这块面积缩小。

空闲处理机 \cdot 时间 = 0 \times \frac{3}{4} + 4 \times \frac{1}{4} = 1, 浪费率 = \frac{1}{6} \approx 16.67 %

浪费率从 33.33% 降到 16.67%，按线程平均分配处理机时间的方法更有效。规律很直白：每个应用贡献的空闲面积是"它空着的处理机数 $N - k_{u}$ × 它占用的时长 $t_{u}$ "，所以要给线程少（ $N - k_{u}$ 大）的应用少分时间。换一组数（比如 8 台处理机、两个应用各 5 线程与 3 线程，此时两项都不为 0）照这条通式直接算即可。

专用处理机分配为什么容忍浪费，以及"线程数总和不应超过处理机数"这条建议的来历（想理解它的适用前提时展开）

一个线程为了同步而阻塞时，分给它的那台处理机就空闲着，处理机浪费严重。仍然用它的两条理由是：① 在有数十上百个处理机的高度并行系统里，单个处理机的投资费用占比很小，它的利用率已远不像单机系统那样重要；② 每个线程独占一台处理机 ⇒ 完全避免线程切换 ⇒ 程序运行速度大幅提高。

一条重要的实验结论：在一个 16 处理机的系统上运行两个应用（矩阵相乘与 FFT），线程数从 1 变到 24，加速比在每个应用含 7～8 个线程时达到最高，超过 8 个之后反而下降。原因是系统总共只有 16 台处理机，两个应用各 8 个线程时恰好每线程一台；再多就保证不了，线程切换重新出现。由此得出的建议是：同时加工的各应用程序，其线程数总和不应超过系统中处理机的数目。

教材还给了一个很好的类比：同构多处理机的处理器分配酷似请求分页式内存分配——"该给某应用分几台处理机"类似于"该给某进程分几个物理块"，并且同样存在活动工作集的概念：分配的处理器数少于活动工作集时会引起线程频繁切换，正如物理块数少于工作集时会引起页面频繁调进调出（见虚拟内存性能）。

二、处理器亲和性

处理器亲和性是指倾向于让进程/线程在之前运行过的处理器上继续运行。在多处理机上，一次迁移会同时失去三样东西：

迁移会丢掉什么	后果	结构前提
Cache 中的数据	该处理器上为它保留的数据全部作废，新处理器上要重新建立拷贝	UMA、NUMA 都有
TLB 中的页表项	新处理器的 TLB 里没有它的地址映射，切换后要经历一段 TLB 缺失密集期	UMA、NUMA 都有
本地内存的就近性	进程的页框往往分配在它初次运行的那个节点的本地存储器上；迁到别的节点后，原来的"本地访问"全部变成远程访问	仅 NUMA

三、负载均衡：与亲和性方向相反

负载均衡要让各处理器的工作负载大致均衡，而亲和性希望别迁移，所以真正要回答的是三个量的问题。

负载均衡三个参数取小取大各会出什么毛病（想在方案层面判断参数怎么定时展开）

参数	取小	取大	判据
检查周期（多久扫一次负载）	反应快，但扫描本身要遍历所有处理器的队列并加锁，开销高	开销低，但负载失衡会持续较久	周期应远大于一次迁移的代价，否则光扫描就把收益吃光
迁移阈值（负载差多少才迁）	稍有差异就迁，容易来回抖动（迁过去后原核又空了，再迁回来）	迁移少，但明显失衡时也不动	阈值至少要大于"一次迁移的代价折算成的负载量"，否则迁移是亏本的
一次迁移几个	收敛慢	可能矫枉过正，造成反向失衡	通常取两者负载差的一半

一次迁移的收益是"目标核空闲的那段时间被利用起来"，代价是上面亲和性那张表里的三项之和。于是判据可以直接写出来：迁移划算，当且仅当"目标核空闲时间带来的收益" $>$ "Cache 重建 $+$ TLB 重填（NUMA 上再加远程访问增量）"。

四、调度与同步的耦合

这一节把二（二）调度和二（三）同步互斥连起来。单处理机上不存在的一个问题，在多处理机上变得很严重：

线程 $T_{1}$ 在核 A 上持有一把自旋锁（见锁）⇒ 调度程序因为时间片到或被抢占，把 $T_{1}$ 从核 A 换下 ⇒ $T_{1}$ 没走出临界区，锁没有释放 ⇒ 核 B、核 C 上等这把锁的线程正在自旋，反复读锁变量而不睡眠 ⇒ 这些核满负荷空转 ⇒ 而且 $T_{1}$ 要等下一次被调度才能继续，这段时间可能很长。

单处理机上自旋锁本来就不该用（持锁者被换下后，自旋者白白烧完自己的整个时间片）；多处理机上自旋锁是有意义的（持锁者可能正在别的核上跑，很快就放），但一旦持锁者被换下 CPU，多个核会同时空转，损失是成倍的。三条应对分属不同层次：

应对	属于哪一层	做法
成组调度	调度层	让合作线程同时上核，持锁者不在跑的窗口大幅缩短
专用处理机分配	调度层	每线程独占一台处理机，根本不发生切换
临界区内禁止抢占	同步层	进入自旋锁保护的临界区时关闭本核的抢占，出临界区再开——这也是不能进行进程调度的时机里"内核临界区中不能调度"那一条在多处理机上的现实理由

五、调度队列的组织

方式	说明	优点	缺点
全局队列	所有处理器共享一个就绪队列	自动实现负载均衡（只要队列不空就没有处理器闲着）	访问必须互斥，处理器数目多时成为瓶颈；破坏亲和性（线程重新就绪后很难回到原处理器）
各处理器私有队列	每个处理器有自己的就绪队列	无互斥开销，天然保持亲和性；便于把一个进程的所有线程放在同一队列/同一处理机上	必须额外提供负载均衡机制（Push/Pull）

这张表正好是自调度（全局队列）与成组调度／专用分配（私有队列）在数据结构层面的映射：全局队列把代价转移到了"锁竞争 + 亲和性丢失"，私有队列把代价转移到了"必须自己做负载均衡"。

考点速记

两条分界线：SMP（对称，无主从）vs 非对称（主处理机独揽调度，实现简单但有瓶颈与单点失效两个致命问题）；UMA（访存均匀）vs NUMA（访存延时随位置变化、三层存储、可扩展但远程延时高）。NUMA 让"放到哪个核"变成了半个内存分配决策。
四种调度方式是一条改进链：自调度（公共队列，可沿用单机算法，但队列成瓶颈、Cache 效率低、合作线程难同时上核）→ 成组调度（一组合作线程同时上核，且调度频率降低）→ 专用处理机分配（每线程一台，完全免切换）→ 动态调度（线程数可变，性能最好但开销大）。
⚠️亲和性与负载均衡方向相反：一个要"别动"，一个要"挪走"。权衡判据是——迁移节省的等待时间要大于 Cache 重建 + TLB 重填（NUMA 上再加远程访问增量）。
⚠️持自旋锁的线程被换出会让别的核成倍空转。应对在调度层是成组调度 / 专用分配，在同步层是临界区内禁止抢占。
单处理机上自旋锁没有意义（见锁），多核上才有——但代价是第 4 条那个坑。

这一节在真题里被考过的形式：

多处理机调度至今不单独成题，本页下方因此没有练习区。

它在大纲里（二（二）5 多处理机调度），不能跳过，但投入按"读懂即可"来定。逐题反查过全部真题的题干与选项后确认：唯一沾边的两道也不考它—— os-2016-27 提到多核只是为了说明 TSL 自旋锁的适用场景（在同步互斥实现方法讲）， os-2018-23 提到"多 CPU"是为了考并发与并行的分界（在操作系统基本概念讲）。

不单独成题不等于白读，它有两处结论会被别处用到：

第一，速记第五条与锁的"自旋锁在单处理机上无意义"是同一件事的两面。 凡出现"为什么多核编程才大量使用自旋锁"这类问法，答案由它们合起来给出。

第二，第一条里 SMP 与非对称的分界是选项素材。 "非对称多处理有瓶颈和单点失效" 这句话在判断题里出现过，判据是调度决策集中在一台机器上。

复习优先级：读一遍即可，不必细记四种调度方式的名字。 真正值得记的是第三条那个权衡判据（迁移的收益要盖过 Cache 与 TLB 重建的代价）与第四条那个自旋锁的坑——它们都是"多核让原本正确的做法失效"的例子。

易错：认为亲和性与负载均衡是一回事。方向正好相反——一个要别动，一个要挪走。

易错：认为迁移线程总是划算的。要比"省下的等待时间"与"Cache 重建 + TLB 重填"的大小。

易错：认为多核上自旋锁没有风险。持锁线程被换出时，别的核会成倍空转。

易错：认为非对称多处理只是"实现简单"。它有瓶颈与单点失效两个致命问题。

教材出处

汤小丹《计算机操作系统》10.2.1 UMA 多处理机系统的结构、10.2.2 NUMA 多处理机系统结构（UMA/NUMA 的定义、NUMA 的三层存储、CC-NUMA 与 NC-NUMA、远程访问延时导致性能无法线性增长），印刷 p309、p312–p314
汤小丹《计算机操作系统》10.5.2 进程分配方式（非对称 MPS 主从式分配的优点，以及"由一台主机控制一切潜在着不可靠性——主机故障将导致整个系统瘫痪，且易因主机太忙形成系统瓶颈"），印刷 p328–p329
汤小丹《计算机操作系统》10.5.3 进程(线程)调度方式（自调度的机制、优点与三条缺点；成组调度的提出动机与两种处理机时间分配方式；专用处理机分配的理由与 Tucker 的加速比实验、"线程数总和不应超过处理机数目"的建议、与请求分页/活动工作集的类比；动态调度的四条原则），印刷 p329–p332

多处理机调度

核不止一个的时候，调度要多回答两个问题

一、四种多处理机调度方式

二、处理器亲和性

三、负载均衡：与亲和性方向相反

四、调度与同步的耦合

五、调度队列的组织

考点速记

相关知识

相关文章

多处理机调度 ​

核不止一个的时候，调度要多回答两个问题 ​

一、四种多处理机调度方式 ​

二、处理器亲和性 ​

三、负载均衡：与亲和性方向相反 ​

四、调度与同步的耦合 ​

五、调度队列的组织 ​

考点速记 ​

相关知识 ​

相关文章

多处理机调度

核不止一个的时候，调度要多回答两个问题

一、四种多处理机调度方式

二、处理器亲和性

三、负载均衡：与亲和性方向相反

四、调度与同步的耦合

五、调度队列的组织

考点速记

相关知识