跳转至

05 调度(下) — 按比例分 CPU,与多核带来的新麻烦

1. 这一章讲什么

MLFQ 优化的还是「快慢」;还有一条完全不同的路线:保证份额—— A 该拿 75%、B 该拿 25%,不管谁长谁短。本章前半讲这条线上的三个算法: 彩票调度(随机)、步幅调度(确定)、Linux 的 CFS(现代默认)。 后半把舞台搬到多核:CPU 从 1 个变 N 个,单机调度的每个老答案都要重写。

在全书链条里的位置:这是 CPU 虚拟化部分的收尾。对话章里教授点出本部分的性格: 操作系统相当偏执——「paranoia rules the day」——想确保自己始终掌控机器1。

2. 顶层全景

  份额路线:
    彩票调度 ── 每片时间开奖,票多者中,概率上逼近份额
    步幅调度 ── 步幅 = 大数/票数,谁 pass 小谁先跑,周期末份额精确
    CFS ── 谁虚拟运行时间(vruntime)少谁先跑,公平内建于数据结构
        │
  多核路线:
    SQMS(单队列)── 简单但锁争用严重 + 进程在 CPU 间乱跳
    MQMS(每 CPU 一队列)── 可扩展且亲和,但会负载不均
        └──▶ 迁移 / 工作窃取:把作业搬去闲的 CPU

图说:左半回答「怎么公平地分」,右半回答「分的时候发现有好几个发令员怎么办」。

3. 核心原理

3.1 主线例子:75/25 的两种实现

彩票调度。A 持 75 张票,B 持 25 张,共 100 张。每个时间片, 调度器从 0–99 抽一个中奖号:A 拿 0–74,B 拿 75–99, 中奖号落在谁区间谁上机。书里的真实模拟输出:连续 20 次开奖号码是 63 85 70 39 76 17 29 41 36 39 10 99 68 83 63 62 43 0 49 12—— B 只中 4 次(20%),而不是期望的 25%2。概率上的正确,不是保证上的正确; 跑得越久,越接近期望。实现惊人地简单:一个随机数、一条进程链表、 一个累加器——从头遍历,累计票数第一次超过中奖号时停,停在哪就是谁3。

步幅调度(stride scheduling)。同一个例子改成确定性:取一个大数 10000,步幅 = 10000 ÷ 票数,得 A=100、B=200、C(假设有,250 票)=40。 每个进程有累计值 pass,初始全 0:每次选 pass 最小的跑,跑完 pass += 步幅。 书里给的轨迹(节选)4:

  Pass(A)=0   Pass(B)=0   Pass(C)=0    → 跑 A(随意选,同低)
  Pass(A)=100 Pass(B)=0   Pass(C)=0    → 跑 B
  Pass(A)=100 Pass(B)=200 Pass(C)=0    → 跑 C
  Pass(A)=100 Pass(B)=200 Pass(C)=40   → 跑 C
  Pass(A)=100 Pass(B)=200 Pass(C)=80   → 跑 C
  Pass(A)=200 Pass(B)=200 Pass(C)=120  → 跑 C …

一个周期跑完:C 跑 5 次、A 2 次、B 1 次——正好按 250:100:50 分配5。 那为什么还需要彩票?因为步幅调度有全局状态:新进程中途插入时, pass 该设成多少?设 0 它就独占 CPU。彩票调度没有这个问题, 新进程拿着票进来、更新总票数就完事6。

3.2 Linux CFS:把「公平」做成默认答案

Linux 的完全公平调度器(CFS)放弃了「固定时间片 + 优先级」的传统结构。 它的计数器叫虚拟运行时间(vruntime):进程跑多少物理时间, vruntime 就涨多少;调度决策永远是挑 vruntime 最小的跑7。

  • 时间片是动态的:sched latency(典型 48ms)÷ 在跑进程数 n。 n=4 时每人 12ms8。
  • 防止 n 太大时片太碎,设了 min granularity(典型 6ms): 时间片永不小于它——n=10 时理论值 4.8ms,实际给 6ms,公平性略损换效率9。
  • 优先级用经典的 nice 值(-20 到 +19,默认 0)映射成权重表 (nice 0 → 1024,nice -5 → 3121,…),时间片按权重比例切; vruntime 的增速则反比于权重——nice -5 的进程 vruntime 涨得慢, 于是更常被选中。书里的例子:A(nice -5)时间片约 36ms,B(nice 0)约 12ms, A 的 vruntime 以 B 的三分之一速度积累10。

性能动机:Google 数据中心的测量显示,即使重度优化后, 调度仍吃掉约 5% 的 CPU——所以现代调度器必须把「做决定本身」 做得飞快11(补充,不在书里:CFS 用红黑树按 vruntime 排序, 取最小是 O(log n),这是它能压低开销的关键实现手段)。

3.3 彩票的三件小工具

书里还给了三个操纵票数的机制,每个对应一种真实需求12:

机制 做法 场景
货币(currency) 用户在自己的作业间用任意「本币」发票,系统按份额折算成全局票 用户 A 拿 100 票,给自己两个作业各发 500「A 币」,各折成 50 全局票
转让(transfer) 进程临时把票交给另一个进程 客户-服务器:客户把票转给正在为自己干活的服务器,办完再转回
通胀(inflation) 进程临时给自己加票 只适用于互信环境;竞争者之间这么干就是抢机器

图说:三张表说明「票」这个抽象的真正价值不在调度,而在它是 表达「份额所有权」的通用货币——后来的虚拟机内存份额管理也在用12。

3.4 多核:三个物理事实,推翻单机答案

事实一:缓存一致性(coherence)。程序在 CPU 1 上把地址 A 的值 从 D 改成 D′,新值只写在 CPU 1 的缓存里;调度器把它挪到 CPU 2, 重读 A 拿到旧值 D——错了。硬件用总线嗅探之类协议兜底, 保住「共享内存」的假象13。代价:跨 CPU 共享数据天生更贵。

事实二:同步绕不开。即使硬件保证一致性,「从链表头删一个节点」 这样的三步操作在两个 CPU 同时执行仍会出事(两个线程的 tmp 都记住 同一个旧头,双双 free 同一块内存)。要正确就得加锁; 而锁的争用随 CPU 数增长急剧恶化14。

事实三:缓存亲和(affinity)。进程在 CPU 1 上攒了一缓存的热数据, 下次还在 CPU 1 跑就快;每次换 CPU 就全部冷启动15。

两个调度架构的正反面16:

SQMS 单队列 MQMS 每 CPU 一队列
扩展性 差:全系统抢一把队列锁 好:队列数随 CPU 数走
缓存亲和 差:进程在 CPU 间弹跳(书中 A–E 五作业四 CPU 的例子,作业被轮流搬家) 好:作业钉在本 CPU
负载均衡 天然(大家都从一个队列拿) 差:C 先跑完后 A 拿 2 份、B 和 D 各 1 份;A、C 都走后 CPU 0 直接闲置

图说:MQMS 的最后一行「CPU 0 闲置」是本章的戏眼——解法只有一个: 迁移(migration),把作业搬去闲的 CPU;更麻烦的情形 (A 独守 CPU 0,B/D 挤 CPU 1)需要持续迁移,隔几段时间片换一批, 用实现复杂度换公平17。Linux 的做法(多级调度域、负载均衡)书里给了引子, 细节交给参考文献18。

4. 作者的判断与证据

书里给了证据的判断:

  • 彩票的公平性有模拟数据(F 值随作业长度收敛到 1)——公平是 「跑久了才到位」的,这个收敛性有图2。
  • 步幅调度的精确性有完整的手算轨迹45。
  • CFS 的动机引 Google 数据中心的 5% 实测11。

作者的判断(立场):

  • 随机性被作者大力推荐:没有最坏情况、状态极简、决策极快—— 「当你必须做决定时,随机常常是一种稳健而简单的办法」19。 同时承认它的代价:短时间尺度上比例不准,这正是步幅调度存在的原因。
  • 「票数怎么分」被明确标为开放问题——用户知道得最多么? 这只把问题推回去了,没有答案20。

5. 边界与局限

  • CFS 一节写于它较早期的形态(红黑树、组调度等后来演进未覆盖; 补充,不在书里:此后 CFS 增加了组调度、EEVDF 取代部分启发式,即经验规则)。
  • 多核部分对缓存一致性「跳过所有细节」——需要体系结构课补; NUMA(非一致访存)只字未提,而它在今天的多路服务器上是主导因素。
  • 工作窃取(work stealing)作为经典解法在本章没有出现(它出现在 本章参考文献之外的并发文献里),迁移一节讲的 OS 级方案较重。

6. 可带走的

  1. 想保证份额,只有两条路:随机逼近(彩票:简单、无全局状态、短期不准) 或确定计数(步幅/CFS:精确,但有全局状态/排序结构的负担)。
  2. CFS 的心法一句话:谁欠的运行时间少,谁先跑;欠多少用 vruntime 记。
  3. 优先级不必做成「抢占级别」,可以做成记账速度——涨得慢的自然常跑。 这是对「权重」最优雅的实现方式之一。
  4. 多核调度的三件套矛盾:锁争用(单队列)、负载不均(多队列)、 缓存亲和(两边都想要)——任何方案都是三者的折中。
  5. 「随机没有最坏情况」是彩票调度给整个系统的启示:遇到要在 坏例上崩的传统算法时,先问一句随机化能不能救。
  6. 份额型调度都有同一个没答案的问题:初始份额怎么分。 遇到「保证公平」的需求,先追问「按什么分」。

7. 原文地图

主题 原书章 原文位置
彩票的 75/25 例子与随机输出 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:55(搜「85 70 39」)
随机性的三个优点 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:33(搜「USE RANDOMNESS」)
票 = 份额所有权的通用机制 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:71(搜「TICKETS TO REPRESENT」)
货币/转让/通胀三机制 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:84(搜「ticket currency」)
抽奖实现代码与 300 号例子 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:150(搜「300」)
公平性随作业长度收敛 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:180(搜「Fairness Study」)
步幅与 pass 定义 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:228(搜「stride」)
步幅调度轨迹 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:259(搜「Who Runs」)
彩票 vs 步幅:全局状态 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:283(搜「no global state」)
CFS 与 Google 5% 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:292(搜「Completely Fair」)
vruntime 挑最小 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:319(搜「virtual runtime」)
sched latency / min granularity 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:331(搜「sched latency」)
nice 值与权重表 9. Scheduling: Proportional Share text/11-ch09-9-scheduling-proportional-share.txt:368(搜「Niceness」)
缓存一致性问题(D 与 D′) 10. Multiprocessor Scheduling (Advanced) text/12-ch10-10-multiprocessor-scheduling-advanced.txt:104(搜「Oops」)
同步:链表删除的双 free 10. Multiprocessor Scheduling (Advanced) text/12-ch10-10-multiprocessor-scheduling-advanced.txt:151(搜「List_Pop」)
缓存亲和 10. Multiprocessor Scheduling (Advanced) text/12-ch10-10-multiprocessor-scheduling-advanced.txt:178(搜「cache affinity」)
SQMS 的锁与弹跳 10. Multiprocessor Scheduling (Advanced) text/12-ch10-10-multiprocessor-scheduling-advanced.txt:199(搜「single queue」)
MQMS 与负载不均(CPU 0 闲置) 10. Multiprocessor Scheduling (Advanced) text/12-ch10-10-multiprocessor-scheduling-advanced.txt:325(搜「CPU 0 is idle」)
迁移与持续迁移 10. Multiprocessor Scheduling (Advanced) text/12-ch10-10-multiprocessor-scheduling-advanced.txt:339(搜「migration」)
「偏执统治这一天」 11. Summary Dialogue on CPU Virtualization text/13-ch11-11-summary-dialogue-on-cpu-virtualization.txt:26(搜「Paranoia rules the day」)

  1. 出处:「11. Summary Dialogue on CPU Virtualization」第 18–26 段(text/13-ch11-11-summary-dialogue-on-cpu-virtualization.txt:26,搜「Paranoia rules the day」)。学生总结:操作系统想当神经质,既要程序高效跑,又要随时能说「且慢」。 ↩

  2. 出处:「9. Scheduling: Proportional Share」第 54–65 段(text/11-ch09-9-scheduling-proportional-share.txt:55,搜「85 70 39」)。原文记录 20 次开奖与由此产生的调度,B 实得 20% 而非 25%。 ↩↩

  3. 出处:「9. Scheduling: Proportional Share」第 136–160 段(text/11-ch09-9-scheduling-proportional-share.txt:148,搜「pick a random number」)。 ↩

  4. 出处:「9. Scheduling: Proportional Share」第 247–270 段(text/11-ch09-9-scheduling-proportional-share.txt:259,搜「Who Runs」)。 ↩↩

  5. 出处:「9. Scheduling: Proportional Share」第 277–280 段(text/11-ch09-9-scheduling-proportional-share.txt:278,搜「exactly in proportion」)。 ↩↩

  6. 出处:「9. Scheduling: Proportional Share」第 281–290 段(text/11-ch09-9-scheduling-proportional-share.txt:283,搜「no global state」)。 ↩

  7. 出处:「9. Scheduling: Proportional Share」第 315–323 段(text/11-ch09-9-scheduling-proportional-share.txt:319,搜「virtual runtime」)。 ↩

  8. 出处:「9. Scheduling: Proportional Share」第 331–345 段(text/11-ch09-9-scheduling-proportional-share.txt:331,搜「sched latency」)。 ↩

  9. 出处:「9. Scheduling: Proportional Share」第 349–360 段(text/11-ch09-9-scheduling-proportional-share.txt:349,搜「min granularity」)。 ↩

  10. 出处:「9. Scheduling: Proportional Share」第 394–408 段(text/11-ch09-9-scheduling-proportional-share.txt:395,搜「most precious job」)。 ↩

  11. 出处:「9. Scheduling: Proportional Share」第 299–304 段(text/11-ch09-9-scheduling-proportional-share.txt:302,搜「5%」)。 ↩↩

  12. 出处:「9. Scheduling: Proportional Share」第 81–114 段(text/11-ch09-9-scheduling-proportional-share.txt:84,搜「ticket currency」)。 ↩↩

  13. 出处:「10. Multiprocessor Scheduling (Advanced)」第 91–121 段(text/12-ch10-10-multiprocessor-scheduling-advanced.txt:105,搜「cache coherence」)。 ↩

  14. 出处:「10. Multiprocessor Scheduling (Advanced)」第 123–176 段(text/12-ch10-10-multiprocessor-scheduling-advanced.txt:151,搜「List_Pop」)。 ↩

  15. 出处:「10. Multiprocessor Scheduling (Advanced)」第 178–190 段(text/12-ch10-10-multiprocessor-scheduling-advanced.txt:178,搜「cache affinity」)。 ↩

  16. 出处:「10. Multiprocessor Scheduling (Advanced)」第 195–262 段(text/12-ch10-10-multiprocessor-scheduling-advanced.txt:199,搜「single queue」)与第 264–298 段(text/12-ch10-10-multiprocessor-scheduling-advanced.txt:266,搜「multiple queues」)。 ↩

  17. 出处:「10. Multiprocessor Scheduling (Advanced)」第 299–359 段(text/12-ch10-10-multiprocessor-scheduling-advanced.txt:339,搜「migration」)。 ↩

  18. 出处:「10. Multiprocessor Scheduling (Advanced)」第 360 段之后(text/12-ch10-10-multiprocessor-scheduling-advanced.txt:386,搜「Linux」)。 ↩

  19. 出处:「9. Scheduling: Proportional Share」第 33–49 段(text/11-ch09-9-scheduling-proportional-share.txt:33,搜「USE RANDOMNESS」)。 ↩

  20. 出处:「9. Scheduling: Proportional Share」第 212–220 段(text/11-ch09-9-scheduling-proportional-share.txt:212,搜「Assign Tickets」)。 ↩