一句话 + 关键问题

没有完备的先验知识，如何调度？如何设计一个调度器，既能让交互式作业的响应时间最小，又能在不知道作业长度的前提下让周转时间最小？

THE CRUX: HOW TO SCHEDULE WITHOUT PERFECT KNOWLEDGE? — How can we design a scheduler that both minimizes response time for interactive jobs while also minimizing turnaround time without a priori knowledge of job length?

上一章留下了两难：SJF/STCF 周转时间好，但需要知道作业长度；RR 响应时间好，但周转时间差。多级反馈队列（Multi-level Feedback Queue, MLFQ）要同时解决这两件事，而且不需要任何先验知识：它一边运行，一边观察作业的行为，用过去预测未来。

MLFQ 最早由 Corbató 等人于 1962 年在兼容分时系统（CTSS）中提出，这项工作连同后来的 Multics 让 Corbató 获得了图灵奖。BSD UNIX 的衍生系统、Solaris、Windows NT 及其后续版本都以某种形式的 MLFQ 作为基础调度器。本章按书中的节奏，从两条基本规则出发，每发现一个漏洞就加一条规则，最终得到 5 条规则。

核心概念速览

多个队列 = 多个优先级

每个队列有一个优先级；任一时刻，一个就绪作业只在一个队列里。

规则 1、2

优先级高的先运行；优先级相同的轮转（RR）。

反馈（feedback）

优先级不是固定的，而是根据作业观察到的行为调整：频繁让出 CPU 的保持高优先级，长期霸占 CPU 的逐步降级。

时间配额（allotment）

作业在某一优先级上可以使用的 CPU 时间总量，用完就降级。最简单时配额 = 一个时间片。

近似 SJF

新作业先假定"可能很短"放在最高优先级；真短就很快完成，真长就一路沉到底。

饥饿与优先级提升

交互作业太多时长作业会饥饿（starvation）；规则 5 每隔 S 把所有作业提升（boost）到最高队列。

愚弄调度器（gaming）

在配额用完前主动发起 I/O 就能永远留在高优先级。规则 4 的"完整计账"堵住这个漏洞。

巫毒常量（voo-doo constants）

队列数、时间片、配额、S 都很难设定，只能靠经验调优——Ousterhout 定律：尽量避免它们。

图解讲解

8.1 基本规则

MLFQ 有若干个不同的队列，每个队列一个优先级。任何时刻一个就绪作业只在一个队列中。MLFQ 用优先级决定运行谁；同一队列里可能有多个作业（优先级相同），它们之间用轮转。于是得到前两条规则：

[高优先级] [低优先级] Q8 Q7Q6Q5 Q4 Q3Q2 Q1 A B C D A、B 优先级最高：两者轮转（规则 1、2） C、D 永远轮不到？只要 A、B 一直就绪，按目前的规则C 和 D 就不会运行——岂有此理！
图 8.1　MLFQ 的一个静态快照。关键在于：优先级如何随时间变化？

MLFQ 调度的关键在于如何设置优先级。它不给作业固定优先级，而是根据观察到的行为改变优先级：如果一个作业反复在等待键盘输入时让出 CPU（交互式进程的典型行为），MLFQ 就保持它的高优先级；如果一个作业长时间密集使用 CPU，MLFQ 就降低它的优先级。

8.2 尝试 1：如何改变优先级

我们的工作负载是：一些运行时间短、频繁让出 CPU 的交互式作业，加上一些需要大量 CPU、不在乎响应时间的长时间"CPU 密集型"作业。先引入配额（allotment）：作业在某个优先级上能花的时间，用完就降级。先简单地假定配额 = 一个时间片。

下面这些图都由本页模拟器按规则实时生成（时间片 10ms，配额 = 时间片，三个队列 Q2 > Q1 > Q0）。每个队列一行，行内每个作业占一条"泳道"；实心块 = 正在运行，细线 = 在该队列中等待。

例 1：一个长时间运行的作业。作业以最高优先级 Q2 进入；运行一个 10ms 时间片后降到 Q1；再运行一个时间片后降到最低的 Q0，并一直留在那里。

图 8.2　长时间运行的作业随时间的变化

例 2：来了一个短作业。A 是长时间运行的 CPU 密集型作业，已经跑了一段时间，沉在 Q0；B 在 T=100 到达，是一个只需 20ms 的短作业。B 被放入最高队列，两个时间片后（还没沉到底）就运行完毕，然后 A 以低优先级继续运行。

图 8.3（左）　来了一个交互式短作业：B 在 100 到达，120 完成

这就是 MLFQ 的主要目标之一：因为它不知道一个作业是短是长，就先假设它是短作业并给予高优先级。如果真的很短，它会很快完成；如果不是，它就会慢慢沉下去，证明自己是一个长时间运行的批处理型进程。MLFQ 以这种方式近似 SJF。

例 3：有 I/O 的情况。按规则 4b，交互式作业 B 每次只用 1ms CPU 就执行 I/O（这里 I/O 需要 5ms），在配额用完之前就让出 CPU，所以一直留在最高优先级；A 只能在 B 做 I/O 的空隙中运行。

图 8.3（右）　交互式作业 B（每运行 1ms 做一次 I/O）与长作业 A 竞争

目前的 MLFQ 有什么问题？

看起来不错：长作业之间公平共享 CPU，短作业和 I/O 密集的交互作业能快速运行。但这个版本有严重缺陷（请尽可能"邪恶"地想一想）：

① 饥饿（starvation）

系统中交互式作业"太多"时，它们合起来会吃掉所有 CPU，长作业一点 CPU 都得不到。

② 愚弄调度器（game the scheduler）

聪明的用户可以改写程序：在配额用完前发一个 I/O（比如对文件）主动让出 CPU，就能留在同一队列，获得更高比例的 CPU。做得好（如用掉配额的 99% 再让出），几乎可以垄断 CPU。

③ 行为会变化

一个程序可能先是 CPU 密集型，后来转为交互式。按目前的规则，它已经沉到底，不会再被当作交互式作业对待。

调度必须能抵御攻击。你可能觉得调度策略（无论在 OS 内部，还是在分布式存储系统的 I/O 请求处理中）不是安全问题，但在越来越多的场景下它恰恰是。现代数据中心里，来自世界各地的用户共享 CPU、内存、网络和存储；如果策略设计和执行不当，一个用户就可能损害他人并为自己谋利。

8.3 尝试 2：优先级提升

为了避免饥饿，最简单的办法是周期性地提升（boost）所有作业的优先级：

规则 5 一次解决两个问题：第一，进程不会饿死——在最高队列里，它会与其他高优先级作业轮转，最终得到服务；第二，如果一个 CPU 密集型作业变成了交互式的，提升之后调度器就会正确地对待它。

下面的例子中，长作业 A 与两个交互式短作业 B、C 竞争（B、C 在 T=100 到达，每运行 2ms 就做一次 2ms 的 I/O）。左边没有优先级提升，B、C 到达后 A 就饿死了；右边每 100ms 提升一次（这个值可能太小了，但用于举例），A 至少能周期性地回到最高优先级运行一下。

图 8.4（左）　没有优先级提升：A 在 100 之后再也得不到 CPU
图 8.4（右）　S = 100ms 的优先级提升：A 每次被提升后在最高队列运行一个时间片，随即降到 Q1 再次等待，直到下一次提升

说明：原书图 8.4 是示意图（A 每 30ms 在 Q2 运行一次，与正文"每 100ms 提升一次"并不严格对应）。本页的图完全按规则 1–5 逐毫秒模拟，定性结论相同：没有提升时 A 饿死；有提升时 A 每个周期都能得到少量 CPU。你可以在下方模拟器里把 S 改成 30 或 50 对比。

那 S 应该设成多少？John Ousterhout 把这类值称为巫毒常量（voo-doo constants），因为它们似乎需要某种黑魔法才能设对。S 设得太大，长作业会饿死；太小，交互式作业又得不到合适的 CPU 份额。这通常留给系统管理员去调，或者在现代，越来越多地交给基于机器学习的自动方法。

避免巫毒常量（Ousterhout 定律）。能避免就避免；可惜往往很难。常见结果是一个充满默认参数的配置文件，老练的管理员在出问题时去调整——而这些值通常没人动，我们只能祈祷默认值在实际中工作良好。

8.4 尝试 3：更好的计账

还剩一个问题：如何防止愚弄调度器？罪魁祸首是规则 4a 和 4b——它们允许作业在配额到期前让出 CPU 从而保住优先级。解决办法是对每一层的 CPU 使用做更好的计账（accounting）：作业做 I/O 时，调度器不再"忘记"它在本层已经用了多少配额，而是一直累计；用完就降级，不管是一次用完还是分很多次用完。于是把规则 4a、4b 合并重写为：

下面的工作负载试图愚弄调度器：A 是长作业，B 在 T=100 到达，每运行 5ms 就发起一次 1ms 的 I/O（总是在 10ms 配额用完之前让出 CPU）。

图 8.5（左）　旧规则 4a/4b：B 永远待在 Q2，在 100–219 之间拿走了约 84% 的 CPU（100/119）
图 8.5（右）　新规则 4：B 在 Q2、Q1 各用完 10ms 配额后被降级，最终与 A 在 Q0 公平竞争

细看右图有个有趣的细节：A 在 123–130 只运行了 7ms。这是因为 A 在 Q0 的这个时间片里之前已经被 B 抢占过 3 次、每次运行 1ms；被高优先级作业抢占不会重置 A 的时间片，所以 A 只剩 7ms。

8.5 调优 MLFQ 及其他问题

MLFQ 还有一个大问题：如何参数化？应该有多少个队列？每个队列的时间片多长？配额多大？多久提升一次优先级？这些问题没有简单答案，只有积累对工作负载的经验并据此调优。

例如，大多数 MLFQ 变体允许不同队列有不同的时间片长度。高优先级队列通常时间片较短（例如 10ms 或更少），因为里面是交互式作业，快速切换合理；低优先级队列则是 CPU 密集型的长作业，较长的时间片（例如数百毫秒）效果更好。下图中，两个作业在最高队列运行 20ms（时间片 10ms），在中间队列运行 40ms（时间片 20ms），在最低队列时间片为 40ms：

图 8.6　优先级越低，时间片越长（Q2/Q1/Q0 的时间片分别为 10/20/40ms，Q2、Q1 的配额分别为 20/40ms）
实现做法
Solaris 分时调度类（TS）特别容易配置：提供一组表，精确规定进程优先级在生命周期中如何变化、每个时间片多长、多久提升一次。默认 60 个队列，时间片从 20ms（最高优先级）缓慢增加到几百毫秒（最低），大约每 1 秒提升一次。管理员可以修改这张表来改变调度行为。
FreeBSD（4.3 版）不用表，而是用数学公式根据进程用了多少 CPU 计算优先级；使用量随时间衰减（decay），以另一种方式实现了优先级提升。可参考 Epema 关于衰减使用（decay-usage）调度的论文。
其他特性一些调度器为操作系统工作保留最高的几个优先级，普通用户作业永远得不到；一些系统允许用户给出建议，例如用命令行工具 nice 提高或降低作业的优先级。

尽可能使用建议（advice）。操作系统很少知道什么对每个进程最好，因此提供接口让用户或管理员给出一些提示通常很有用。这类提示称为建议：OS 不一定要理会，但可以参考它们做出更好的决定。调度器（nice）、内存管理器（madvise）、文件系统（informed prefetching and caching）都有这样的接口。

8.6 小结：完整的 MLFQ 规则

MLFQ 有意思的地方在于：它不要求对作业性质有先验知识，而是观察作业的执行并据此确定优先级。这样它能两全其美：对运行时间短的交互式作业，性能接近 SJF/STCF；对长时间运行的 CPU 密集型作业，也公平并能保证进展。

从历史中学习。MLFQ 是用过去预测未来的一个绝佳例子。这类方法在操作系统中很常见（在计算机科学的其他领域也是，例如硬件分支预测器和缓存算法）。当作业有阶段性的行为、因而可预测时，这种方法就有效；但必须小心，预测可能出错，让系统做出比完全不知道时还糟糕的决定。

交互模拟器

模拟器

MLFQ 调度器：规则逐条开关，逐毫秒单步

每个队列一行、每个作业一条泳道，看作业如何在队列之间上下移动。可以逐条关闭/开启规则 1–5、改时间片和配额、给作业设置"每运行 X ms 就发起 I/O"（设成小于时间片即可"愚弄"调度器）。预设复刻原书图 8.2–8.6 和课后题。
载入示例：
作业到达运行时长每运行几 ms 发 I/OI/O 时长
事件 = 到达、降级、提升、发起 I/O、完成等
实心块 = 在该队列中运行细线 = 在该队列中等待竖线 = 当前时刻；虚线 = 优先级提升

先预测再验证

（课后题 2）如何配置模拟器来复现书中的每个例子？先自己想参数，再点对应预设对照。例如图 8.5 需要哪些条件？
看答案
图 8.5：3 个队列，时间片与配额都是 10ms；A 在 0 到达、长 200；B 在 100 到达、长 100、每运行 5ms 做一次 1ms 的 I/O。左图关闭规则 4（旧规则 4a/4b），右图开启规则 4。左图中 B 在 219 完成，A 在 300 完成；右图中 A 在 265 就完成了，因为 B 被降到 Q0 后只能与 A 轮流。
（课后题 3）如何配置参数，让 MLFQ 的行为和一个时间片为 10 的轮转（RR）调度器完全一样？
看答案
只用 1 个队列，时间片 10（规则 2 开启）。只有一个优先级时，规则 1、3、4、5 都不起作用，剩下的就是纯轮转。（另一种思路：关闭规则 1，让所有作业不分优先级按排队先后轮转——但各层时间片不同时就不是严格的 RR 了。）
（课后题 4）构造两个作业和调度参数，让其中一个作业利用旧规则 4a/4b 在某段时间内拿到 99% 的 CPU。
看答案
关闭规则 4，时间片（和配额）设为 100；A 为普通长作业，B 每运行 99ms 就发起一次 1ms 的 I/O。B 每次都在配额用完前让出 CPU，永远留在最高队列；它做 I/O 的那 1ms 里 A 才能运行。B 的份额 = 99/(99+1) = 99%。预设"课后题 4"就是这个配置，统计里能看到 B 的 CPU 份额。打开规则 4 再看看。
（课后题 5）最高队列时间片为 10ms。为了保证一个可能饥饿的长作业至少得到 5% 的 CPU，需要多久提升一次优先级？
看答案
在最坏情况下（交互式作业占满高优先级队列），长作业每次被提升后只能在最高队列运行一个 10ms 时间片，随即被降级、再次饥饿。要求 10/S ≥ 5%，所以 S ≤ 200ms。预设"课后题 5"用 S = 200 跑 1000ms，A 的 CPU 份额约为 5%（提升时刻与作业到达的相位不同会有少许偏差）。
（课后题 6）I/O 完成后的作业应该放在队列的哪一端？打开"I/O 完成后插到队首"，在图 8.5（右）上观察变化。
看答案
插到队首时，B 在 Q0 里每次 I/O 返回都排到 A 前面：A 的时间片一结束（或下一次调度决策时）B 就先运行，交互式作业的响应更快；但在同一队列中，频繁做 I/O 的作业会因此获得更多 CPU，又给了"愚弄"一定的空间。插到队尾则对同层作业更公平。这是一个典型的权衡。

自测题

1. MLFQ 如何在不知道作业长度的情况下近似 SJF？
MLFQ 先假设每个新作业"可能是短作业"（规则 3），用行为反馈调整：用完配额就降级（规则 4）。
2. 按旧规则 4a/4b，作业如何"愚弄"调度器？
规则 4b 在作业放弃 CPU 时重置配额，因此只要每次在配额用完前做一次 I/O（例如用掉 99% 再让出），就永远不会降级。
3. 规则 5（优先级提升）一次解决了哪两个问题？
提升保证所有作业定期回到最高队列与其他作业轮转（不饿死），也让变成交互式的作业重新获得高优先级。愚弄问题要靠规则 4 的完整计账来解决。
4. 下列哪种配置下，MLFQ 的行为与时间片为 q 的 RR 完全相同？
只有一个队列时就只有一个优先级，规则 2 的轮转就是全部行为。多个队列时，作业仍会降级，行为不同于 RR。
5. 关于提升周期 S，说法正确的是？
书中明确说 S 设大了会饥饿、设小了会损害交互作业。规则 4 防愚弄，不能防饥饿。
6. 为什么大多数 MLFQ 让低优先级队列的时间片更长？
这就是图 8.6 的思路。Solaris TS 默认从 20ms 到几百毫秒。
7. 在图 8.5（右）的例子中，A 在 Q0 被 B 抢占了 3 次（每次运行 1ms），之后 A 连续运行了多久才让出 CPU？
A 在 123–130 运行 7ms，加上之前的 3×1ms 恰好用完 10ms 时间片，于是轮到同在 Q0 的 B。

常见误区

本章小结