多核调度
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
复习
- 先来先服务与最短任务优先：简单调度为何会出现等待和饥饿
- 时间片与优先级调度：让多个程序都感觉自己被及时响应
- 多级反馈队列：不知道任务长短时，靠反馈自动调整优先级
TL;DR
- 多核系统里，调度器要决定的不只是“跑谁”，还有“在哪跑”
- 负载均衡：别让一个核忙死、另一个核闲着
- 缓存亲和性：尽量让进程待在同一个核上，复用它的缓存
- 均衡与亲和互相拉扯，需要折中
正文
现代计算机的 CPU 里往往不止一个核心（还记得前面讲并行时提到的多核吗）。于是调度多了一个新问题：任务该放到哪个核上跑？
不只是“跑谁”
单核时代，就绪队列是一条，调度器挑一个出来跑就行。多核时代，每个核都需要一个任务，于是：
- 每个核都有自己的就绪队列，或者共享一个全局队列
- 调度器要保证每个核都不闲着，同时又不抢同一个任务
如果分配不均，就会出现一个核排着长队、另一个核无所事事。这就是负载均衡要解决的问题。
迁移的代价
一个很自然的想法是：哪个核闲，就把任务挪过去。但把任务从 A 核搬到 B 核，是有代价的：
- 任务在 A 核上积累的缓存内容，到了 B 核用不上（缓存是每个核自己的）
- 迁移本身也要做上下文切换
所以，能不动就不动。
缓存亲和性
由此引出缓存亲和性（cache affinity）：一个进程在某个核上跑得越久，它的数据和指令就越可能留在这个核的缓存里。下次还让它在这个核上跑，就能直接命中缓存，快得多；换来换去，则每次都要重新“预热”缓存。
所以调度器倾向于：让进程尽量待在原来的核上。
均衡与亲和的拉扯
可“尽量不迁移”又和“负载均衡”冲突：死守亲和，可能出现某个核累死、某个核闲着。
现实的调度器，通常这样折中：
- 平时尊重亲和，尽量让任务留在原核
- 当某些核明显过载、另一些明显空闲时，才把任务迁过去
- 定期做一次“再平衡”，但不频繁迁移
核 1：████████ 忙
核 2：██ 闲 ← 触发一次迁移
核 1：█████ 较忙
核 2：█████ 较忙
一句话：多核调度是在“让大家都别闲着”和“别把任务搬来搬去”之间找平衡。
思考题
如果一个进程每隔几毫秒就在两个核之间来回迁移，会带来哪些额外开销？为什么“缓存亲和性”对性能影响这么大？
小结
知识点
- 多核调度要决定“跑谁”和“在哪跑”
- 负载均衡：让每个核都不空闲
- 缓存亲和性：让进程尽量留在同一核
- 均衡与亲和互相冲突，需要折中
参考资料
- Wikipedia(zh)：多处理器调度：多核调度
- Wikipedia(zh)：CPU 缓存：缓存与局部性
思考题答案（仅供参考）
频繁迁移有两个主要开销：一是每次迁移都要做上下文切换，并可能让原核的缓存内容白费；二是到了新核，缓存里没有该进程的数据和指令，需要重新从内存加载，命中率骤降。进程刚“预热”好一个核的缓存，又被搬走，等于反复从头开始。所以缓存亲和性对性能影响很大——它决定了一个进程能不能持续吃到“热”的缓存。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪