编程语言研究书库
操作系统导论(OSTEP)

调度(上) — 看不见未来的排队术,与 MLFQ

04 调度(上) — 看不见未来的排队术,与 MLFQ

1. 这一章讲什么

机制(怎么换进程)就位后,策略登场:同一时刻一堆进程都Ready,换谁上? 本章把这个问题按「放松一个假设」的顺序推导:先来先服务为什么会护航、 短作业优先为什么需要预知未来、时间轮转为什么快而不公——最后推出全书的 明星算法 MLFQ(多级反馈队列):不预言未来,而是用最近的历史推测 接下来会怎样。

在全书链条里的位置:策略层的第一课。这一章立起的两个度量(周转、响应) 和「用历史预测未来」的思路,在页替换(本库 09 章)、缓存乃至分支预测里反复出现。

2. 顶层全景

  两个度量互相打架:
    周转时间 = 做完时刻 − 到来时刻     「整体多久能完」
    响应时间 = 首次上机 − 到来时刻     「多久有反应」
        │
  FIFO ──▶ 护航效应(短作业堵在长作业后面)
  SJF/STCF ──▶ 周转最优,但需要「预知作业长度」这个不存在的礼物
  RR(轮转) ──▶ 响应最优,但周转最差
        │
        ▼
  MLFQ:多个优先级队列 + 反馈
    新作业一律先进最高队列(先当它是个短作业)
    用完配额就降级;靠 I/O 让出 CPU 的保持原级
    定期把所有作业提拔回顶(防饿死 + 允许行为转变)
    记账累计用量(防「快到配额时故意 I/O」钻空子)

图说:上半部分是问题结构——两个度量天生冲突;下半部分是 MLFQ 的四条补丁, 每条都堵一个具体的窟窿。

3. 核心原理

3.1 主线例子:A、B、C 三个作业,四种排法

书里用同一组作业贯穿两章,我们照原样接住。作业:A 需要跑 100 秒, B 和 C 各需要 10 秒。下面所有数字都是原书算出来的1。

**排法一:FIFO(先来先服务)。**A 先到,先跑满 100 秒,B、C 干等:

 时间轴:  |—— A 100s ——|B|C|
 A 完成于 100,B 完成于 110,C 完成于 120
 平均周转 = (100+110+120)/3 = 110 秒  ← 很惨

这个惨状叫护航效应(convoy effect):一队短途顾客堵在一个买了一个月 口粮的顾客后面2。 groceries 超市为此开「十件以下」快速通道—— 那就是下一行的算法。

**排法二:SJF(最短作业优先)。**B、C 先跑,A 最后:

 平均周转 = (10+20+120)/3 = 50 秒  ← 比 FIFO 好一倍多

同批作业下 SJF 可证最优3。但它有两个致命假设:知道每个作业多长、 作业同时到达。放松「同时到达」:A 在 t=0 来(100 秒),B、C 在 t=10 来 (各 10 秒)——非抢占式 SJF 还是得等 A 跑完,平均周转回落到 103.33 秒4。

**排法三:STCF(最短完成时间优先)= SJF + 抢占。**新作业到来时, 调度器比较「包括新作业在内谁剩下的时间最短」,必要时把正在跑的抢走5。 B、C 在 t=10 到达时立刻抢占 A:平均周转回到 50 秒。 周转指标下,这就是天花板——前提是你知道未来,而操作系统不知道。

**排法四:RR(轮转)。**三个作业各 5 秒、同时到达,时间片 1 秒, 轮转着每人跑 1 秒:

 响应时间:RR 平均 (0+1+2)/3 = 1 秒;SJF 平均 (0+5+10)/3 = 5 秒
 周转时间:RR 平均 (13+14+15)/3 = 14 秒;SJF 是 10 秒

图说:同一个例子,两种度量,名次整个反过来——公平(大家轮流)对响应好, 对周转坏;偏心(短的先走)反之。这是系统里最常见的权衡形状6。 RR 还有工程细节:时间片必须是时钟中断周期的整数倍;时间片越短响应越好, 但短到上下文切换占比升高就亏了(10ms 片、1ms 切换 = 10% 开销; 100ms 片就摊薄到 1% 以下)7。而且切换的真实代价不只是存几个寄存器—— 缓存、TLB、分支预测器里的状态全被冲掉,新作业要冷启动8。

3.2 把 I/O 算进来:重叠是隐藏的主题

作业不是纯 CPU 的。例:A 需要 50ms CPU,但每跑 10ms 就发一次 10ms 的 I/O; B 是纯 50ms CPU。如果傻乎乎先跑完 A 再跑 B,CPU 和磁盘各自一半时间在闲。 把 A 的每个 10ms CPU 段当成独立作业交给 STCF:A 的段最短,永远优先, 它去等 I/O 时 B 顶上——CPU 与磁盘永远有人在用9。 书里给这个技巧起名「重叠」(overlap),它是高利用率系统的通用心法10。

3.3 MLFQ:用历史顶替预言

MLFQ 回答第 7 章结尾留下的问题:不知道作业多长,怎么逼近 SJF? 还能保住响应时间?1962 年 CTSS 系统首次描述了这个调度器11。 它的骨架是多个优先级队列,规则一、二定基调:

  • 规则 1:优先级高的跑,低的等着。
  • 规则 2:同级的轮转(RR)。

剩下全部戏码在「优先级怎么动」。先立一条心法:宁可一开始高估一个作业 (先当它是短的、交互的),让它用行为自证——真是短作业就很快做完; 是长作业就一层层往下掉,很快「证明」自己是批处理型的12。

具体规则(每补丁堵一个窟窿,数字都是书里的演示值):

规则内容堵的窟窿
3新作业进最高队列「先当它是短作业」的假设13
4a/4b(初版)用完配额降级;I/O 让出 CPU 则保持原级优待交互作业14
5每隔 S(演示取 100ms)把所有作业提拔回顶饿死:交互作业太多时长作业永无 CPU;顺带允许作业「性格转变」15
4(终版)配额按累计计算,不管让出多少次 CPU钻空子:每次快到配额时故意发个 I/O 赖在高优先级,几乎独占 CPU16

图说:规则 4 从初版改到终版是本章最妙的一笔——漏洞不在策略方向, 在记账方式;「让出 CPU 就不罚」听起来合理,合起来就是一条给投机者的缝。

主线例子走一遍(三条队列 Q2/Q1/Q0,配额=时间片=10ms):

  1. 长作业 A 进场,进 Q2。10ms 用完,掉 Q1;再用 10ms,掉 Q0,从此安居17。
  2. t=100 时短作业 B(只需 20ms)到来,直接进 Q2——B 两段时间片就跑完, 全程最高优先级,近似了 SJF 的效果而调度器从不知道 B 多长18。
  3. 交互作业 C 每 1ms 就让出 CPU 等输入:按规则 4 记账,C 在 Q2 的累计 用量其实很少,基本不掉级——快速响应保住了19。
  4. 若无规则 5,再来两个 C 这样的作业,A 就饿死了;有了每 100ms 的提拔, A 至少定期回到 Q2 分一份轮转20。

调参没有干净答案:Solaris 的实现给到 60 条队列、时间片从 20ms 递增到 几百 ms、每秒左右提拔一次——Ousterhout 把这类拍脑袋的参数叫 巫毒常数(voo-doo constants),能避开就避开,避不开就靠管理员或机器学习21。

4. 作者的判断与证据

书里给了证据的判断:

  • SJF 在同批到达下、STCF 在允许抢占下,周转时间可证最优(直觉: 让等待的人越少等越好)——书里明说「这是系统课,不许证明」,但结论成立35。
  • 规则 4 的记账修订有对照图(有无防钻空子两种轨迹),钻空子行为被明确 描述为「gaming the scheduler」,并升格为安全问题:调度策略是 共享系统安全的一部分22。

作者的判断(立场):

  • 「从过去学习」被点名为 OS 与计算机科学里反复出现的手法(分支预测、 缓存算法),但作者同时警告:历史预测会错,错得比没有预测还糟23。
  • 对巫毒常数的态度继承 Ousterhout:厌恶,承认常常避不开21。

5. 边界与局限

  • 本章所有数字基于「时间片 10ms、配额=时间片」的演示设定; 真实系统(Solaris、FreeBSD)各有各的表和公式,书里给了指针但没展开24。
  • MLFQ 的「队列」是现代调度器(包括 Linux 的 CFS 之前的设计、 Windows 多级优先级的祖先)的直系祖先,但现代 Linux 默认调度器 CFS 已经不走 MLFQ 路线(补充,不在书里:它用红黑树按「虚拟运行时间」 直接实现公平,没有显式的多级队列)。
  • 「响应时间」的定义取了最好情况(首次调度即响应),实际交互体验还受 I/O 延迟、图形栈等影响——书里用脚注承认了这一点25。

6. 可带走的

  1. 调度问题先问优化哪个度量:周转和响应常常不可兼得,没有「又好又公平」。
  2. SJF/STCF 是天花板:知道了未来就该这么排;一切实用算法都是在 「不知道未来」的约束下逼近它。
  3. MLFQ 的三段论:先给最高的信任(新作业进顶级)→ 用行为降信任 (累计配额降级)→ 定期重置信任(提拔)。这个形状在缓存替换、 信用评分里都能认出来。
  4. 堵漏洞要堵记账方式,不是堵行为表象:「让出 CPU 不罚分」 与「累计用量罚分」的差别就是公平与可被游戏之间的差别。
  5. 时间片是摊销问题:切换有固定成本,片长要能把这个成本摊薄, 又不能长到失去响应——10ms 量级是实践答案。
  6. 上下文切换的真实代价是缓存冷启动,不是寄存器存取——评估「换人多频繁」 时永远记着这一条。

7. 原文地图

主题原书章原文位置
周转时间定义7. Scheduling: Introductiontext/09-ch07-7-scheduling-introduction.txt:53(搜「turnaround time」)
FIFO 与护航效应7. Scheduling: Introductiontext/09-ch07-7-scheduling-introduction.txt:110(搜「110 seconds」)与:112(搜「convoy effect」)
SJF 把 110 降到 507. Scheduling: Introductiontext/09-ch07-7-scheduling-introduction.txt:155(搜「factor of two」)
晚到的 B、C 让 SJF 失效7. Scheduling: Introductiontext/09-ch07-7-scheduling-introduction.txt:181(搜「arrives at t = 0」)
STCF 抢占与最优7. Scheduling: Introductiontext/09-ch07-7-scheduling-introduction.txt:212(搜「preempt」)
响应时间定义7. Scheduling: Introductiontext/09-ch07-7-scheduling-introduction.txt:239(搜「response time」)
RR 响应 1 秒 vs SJF 5 秒7. Scheduling: Introductiontext/09-ch07-7-scheduling-introduction.txt:303(搜「average response time」)
时间片与摊销7. Scheduling: Introductiontext/09-ch07-7-scheduling-introduction.txt:291(搜「AMORTIZATION」)
切换冲掉缓存/TLB7. Scheduling: Introductiontext/09-ch07-7-scheduling-introduction.txt:313(搜「caches, TLBs」)
I/O 按 CPU 段当独立作业7. Scheduling: Introductiontext/09-ch07-7-scheduling-introduction.txt:402(搜「sub-job」)
MLFQ 源于 CTSS8. Scheduling:The Multi-Level Feedback Queuetext/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:7(搜「Corbato」)
规则 1、28. Scheduling:The Multi-Level Feedback Queuetext/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:55(搜「Priority(A)」)
历史预测未来的心法与警告8. Scheduling:The Multi-Level Feedback Queuetext/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:34(搜「learns from the past」)
规则 3、4a、4b8. Scheduling:The Multi-Level Feedback Queuetext/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:137(搜「highest priority」)
饿死与钻空子两个漏洞8. Scheduling:The Multi-Level Feedback Queuetext/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:194(搜「starvation」)与:197(搜「gaming」)
规则 5 优先级提升8. Scheduling:The Multi-Level Feedback Queuetext/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:235(搜「topmost queue」)
巫毒常数8. Scheduling:The Multi-Level Feedback Queuetext/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:267(搜「voo-doo」)
规则 4 终版:记账8. Scheduling:The Multi-Level Feedback Queuetext/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:307(搜「Better Accounting」)
Solaris/FreeBSD 的真实参数8. Scheduling:The Multi-Level Feedback Queuetext/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:356(搜「Solaris」)

Footnotes

  1. 出处:「7. Scheduling: Introduction」第 100–111 段(text/09-ch07-7-scheduling-introduction.txt:101,搜「100 seconds」)。A 跑 100 秒、B 和 C 各 10 秒的设定与 FIFO 平均周转 110 秒的计算见该例。 ↩

  2. 出处:「7. Scheduling: Introduction」第 112–131 段(text/09-ch07-7-scheduling-introduction.txt:112,搜「convoy effect」)。 ↩

  3. 出处:「7. Scheduling: Introduction」第 171–174 段(text/09-ch07-7-scheduling-introduction.txt:172,搜「optimal scheduling algorithm」)。 ↩ ↩2

  4. 出处:「7. Scheduling: Introduction」第 181–194 段(text/09-ch07-7-scheduling-introduction.txt:181,搜「arrives at t = 0」)。原文给出平均周转 103.33 秒。 ↩

  5. 出处:「7. Scheduling: Introduction」第 216–229 段(text/09-ch07-7-scheduling-introduction.txt:218,搜「Preemptive Shortest Job First」)。 ↩ ↩2

  6. 出处:「7. Scheduling: Introduction」第 317–341 段(text/09-ch07-7-scheduling-introduction.txt:432,搜「inherent trade-off」)。 ↩

  7. 出处:「7. Scheduling: Introduction」第 291–298 段(text/09-ch07-7-scheduling-introduction.txt:291,搜「AMORTIZATION」)。 ↩

  8. 出处:「7. Scheduling: Introduction」第 311–316 段(text/09-ch07-7-scheduling-introduction.txt:313,搜「caches, TLBs」)。 ↩

  9. 出处:「7. Scheduling: Introduction」第 365–409 段(text/09-ch07-7-scheduling-introduction.txt:402,搜「sub-job」)。 ↩

  10. 出处:「7. Scheduling: Introduction」第 333–338 段(text/09-ch07-7-scheduling-introduction.txt:333,搜「OVERLAP」)。 ↩

  11. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 7 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:7,搜「Corbato」)。 ↩

  12. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 154–160 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:160,搜「approximates SJF」)。 ↩

  13. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 110–116 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:137,搜「highest priority」)。 ↩

  14. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 112–116 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:114,搜「gives up the CPU」)。 ↩

  15. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 234–241 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:235,搜「topmost queue」)。 ↩

  16. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 307–316 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:307,搜「Better Accounting」)。 ↩

  17. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 132–141 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:132,搜「Single Long-Running Job」)。 ↩

  18. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 143–160 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:151,搜「T = 100」)。 ↩

  19. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 176–187 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:176,搜「What About I/O」)。 ↩

  20. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 242–264 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:241,搜「boost」)。 ↩

  21. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 266–273 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:267,搜「voo-doo」)。 ↩ ↩2

  22. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 205–214 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:205,搜「SECURE FROM ATTACK」)。 ↩

  23. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 32–40 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:34,搜「learns from the past」)。 ↩

  24. 出处:「8. Scheduling:The Multi-Level Feedback Queue」第 326–375 段(text/10-ch08-8-scheduling-the-multi-level-feedback-queue.txt:356,搜「Solaris」)。 ↩

  25. 出处:「7. Scheduling: Introduction」第 244–246 段(text/09-ch07-7-scheduling-introduction.txt:245,搜「best-case」)。 ↩

受限直接执行 — 高效与控制的第一次交锋

Previous Page

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

Next Page

On this page

04 调度(上) — 看不见未来的排队术,与 MLFQ1. 这一章讲什么2. 顶层全景3. 核心原理3.1 主线例子:A、B、C 三个作业,四种排法3.2 把 I/O 算进来:重叠是隐藏的主题3.3 MLFQ:用历史顶替预言4. 作者的判断与证据5. 边界与局限6. 可带走的7. 原文地图Footnotes