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

1. 这一章讲什么Copy Anchor Link

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

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

2. 顶层全景Copy Anchor Link

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

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

3. 核心原理Copy Anchor Link

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

**彩票调度。**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%²。概率上的正确,不是保证上的正确; 跑得越久,越接近期望。实现惊人地简单:一个随机数、一条进程链表、 一个累加器——从头遍历,累计票数第一次超过中奖号时停,停在哪就是谁³。

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

  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 分配⁵。 那为什么还需要彩票?因为步幅调度有全局状态:新进程中途插入时, pass 该设成多少?设 0 它就独占 CPU。彩票调度没有这个问题, 新进程拿着票进来、更新总票数就完事⁶。

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

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

• 时间片是动态的:sched latency(典型 48ms)÷ 在跑进程数 n。 n=4 时每人 12ms⁸。
• 防止 n 太大时片太碎,设了 min granularity(典型 6ms): 时间片永不小于它——n=10 时理论值 4.8ms,实际给 6ms,公平性略损换效率⁹。
• 优先级用经典的 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 的三分之一速度积累¹⁰。

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

3.3 彩票的三件小工具Copy Anchor Link

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

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

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

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

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

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

两个调度架构的正反面¹⁶:

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

4. 作者的判断与证据Copy Anchor Link

书里给了证据的判断:

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

作者的判断(立场):

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

5. 边界与局限Copy Anchor Link

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

6. 可带走的Copy Anchor Link

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

7. 原文地图Copy Anchor Link