18 让短的先走

▷ 先估一个数

一条队，利用率 80%，服务时间很不齐（cs² = 10：大部分活很小，偶尔来个巨无霸）。先来后到时，平均等待是 20.292 个服务时长。

现在改成：永远先做剩余时间最短的那个活（可以打断正在做的）。

平均等待会变成多少？

A 大约 15——能改善，但改不了多少 B 大约 10——减半左右 C 大约 6 D 不到 1

为什么「先做短的」能凭空变出时间

上一章说未完成工作量 V(t) 是守恒的，跟顺序无关。这一章的策略并没有违反它——V(t) 仍然完全一样。

那省下来的时间从哪来？

从「等待的人数」来。

# 三个活：A 要 10 秒，B 要 1 秒，C 要 1 秒
# 总工作量 12 秒，两种顺序下 V(t) 完全相同

# 先来后到（A B C）
   A: 等 0，做完于 10
   B: 等 10，做完于 11
   C: 等 11，做完于 12
   总等待 = 0 + 10 + 11 = 21，平均 7.0

# 短的先走（B C A）
   B: 等 0，做完于 1
   C: 等 1，做完于 2
   A: 等 2，做完于 12
   总等待 = 0 + 1 + 2 = 3，平均 1.0     ★ 只有原来的七分之一

# ★ 最后一个活的完成时刻都是 12 —— 总工作量守恒
#   变的是"有多少人在等那个巨无霸做完"

关键在最后那行注释：先做长的，会让后面所有人都等那么久；先做短的，只有那个长的在等。

这是一笔非常划算的交易，因为短活的数量通常远多于长活——让一个人多等，换很多人少等。

三档策略

策略	平均等待	说明
FIFO 先来后到	20.292	基准
SJF 短作业优先（不打断）	6.260	挑队里最短的做，但正在做的不打断
SRPT 剩余最短优先（可打断）	0.548	随时都在做「离做完最近」的那个

SRPT 把平均等待压到 FIFO 的 2.7%。

而且这不是启发式，是有证明的：SRPT 在所有调度策略里最小化平均逗留时间。没有任何策略能比它更好。这在调度理论里是个定理。

那张账单：谁付了钱

把活按长短分成四档，看每一档的遭遇：

策略	第 1 档（最短，平均长 0.076）	第 4 档（最长）
FIFO 平均等待	20.204	20.340
SJF 平均等待	4.317	10.471
SRPT 平均等待	0.003	2.074

先看 FIFO 那一行：最短的活和最长的活，等待时间几乎一样（20.204 vs 20.340）。

这就是 FIFO 的隐藏不公平：它对所有人「一视同仁」，而一视同仁本身就是不公平的。一个要办 0.076 秒的小事，和一个要办好几秒的大事，凭什么等一样久？

用放大倍数（总耗时 ÷ 实际工作量）看更清楚：

策略	第 1 档的放大倍数	第 4 档的放大倍数
FIFO	2025.1×	15.83×
SJF	400.4×	6.94×
SRPT	1.0×	1.32×

2025 倍。先来后到时，一个只要 0.076 个时间单位就能做完的请求，实际要花 20 多个时间单位——它 99.95% 的时间在等一个跟它无关的巨无霸。

而 SRPT 下，它是 1.0 倍——几乎感觉不到队列的存在。

◆ 一个反直觉的结果

看 SRPT 那一行的第 4 档：2.074，比 FIFO 的 20.340 还小。

也就是说，在这个负载下，SRPT 连长作业都变快了——它没有牺牲任何人。

为什么？因为 SRPT 把队列清得极快，长作业等待时前面积压的东西少得多。这是「效率提升让所有人受益」的少数情况之一。

但这个好消息有条件：它成立于负载不太高、活的长短差异很大的时候。当 ρ 逼近 1、或者长作业占的工作量比例很高时，长作业会开始饿死——新来的短活源源不断地插队，长活永远轮不上。SRPT 在最坏情况下能让某个作业等待无限久。

为什么大家还在用 FIFO

SRPT 又快又（在很多情况下）不伤害任何人，为什么它不是默认？三个很实在的理由：

1. 你通常不知道活要做多久。这是最大的障碍。SJF 和 SRPT 都需要预知服务时间，而请求进来时你只有一个 HTTP 方法和一堆参数。

不过这个障碍没有想象中大——你不需要精确预测，只需要能区分「大概是短的」和「大概是长的」。而这通常做得到：按接口路径分、按参数里的分页大小分、按用户是不是重度用户分。

还有一个更聪明的办法叫多级反馈队列：不预测，而是观察。所有活先进最高优先级队列，跑了一小段还没完就降级到下一级。这样长活会自动沉下去，而完全不需要预知任何东西。Unix 的进程调度器几十年来就是这么干的。

2. 饿死风险。纯 SRPT 下长作业可能永远等不到。实践中的解法是老化（aging）：等得越久优先级越高，保证每个活最终都会被执行。这牺牲一点最优性，换来一个上界。

3. 抢占是有成本的。SRPT 需要打断正在执行的任务。对 CPU 上的线程，这是上下文切换；对一个正在写数据库的事务，这可能根本做不到。SJF（不打断）通常是更现实的选择，而它已经能拿到大部分收益（20.292 → 6.260，改善 69%）。

∑ 算一遍：为什么 c² 越大，收益越大

短作业优先的收益，完全来自「活的长短差异」。如果所有活一样长（cs²=0），那 SJF 和 FIFO完全等价——没有「短的」可挑。

# 收益的来源：FIFO 下，一个短活撞上长活的概率
# 由第 7 章的检查悖论决定：
P(撞上一个长度为 x 的活) ∝ x × f(x)      ← 长度加权

# 所以 cs² 越大，短活撞上巨无霸的概率越高，
# 而"把巨无霸挪到后面"省下的时间也越多。

# 这一章的例子 cs²=10，收益是 97.3%
# 如果 cs²=1（指数服务），SRPT 相对 FIFO 的收益大约是 60%–70%
# 如果 cs²=0，收益是 0

这给出一条实用的判断规则：先去量你的 cs²。如果它大于 4，那么「按大小分流」几乎一定值得做；如果它接近 0，别费劲了。

顺便，这也是这本书里第 5 章那个 c² 的第三个用途：它既决定了排队的成本（第 8 章），也决定了扇出的风险（第 16 章），还决定了调度优化的潜力（这一章）。一个数，三笔账。

✎ 术语正名：「放大倍数」（slowdown）

这一章那张最有说服力的表，用的不是等待时间，是放大倍数：

放大倍数 = (等待 + 服务) ÷ 服务

这个指标在调度理论里叫 slowdown 或 stretch，我认为它比延迟本身更接近「用户是否觉得系统卡」。

理由是用户的期望是随任务大小缩放的：上传一个 1GB 的文件等 30 秒，没人抱怨；点一个按钮等 30 秒，用户会砸键盘。用户在意的不是绝对延迟，是「这件事本该多久」和「实际多久」的比值。

而按这个指标看，FIFO 的表现是灾难性的：小请求被放大 2025 倍。如果你的监控只有绝对延迟，这个问题是完全不可见的——因为小请求和大请求的延迟被平均在了一起。

一个具体建议：把延迟按请求大小分桶看，或者直接画放大倍数。

▸ 在现实里

超市的「十件以下快速通道」。这就是 SJF，而且是它最成功的民间实现。它没有让超市多收一分钱，也没有让收银员变快，但它让大多数顾客的体验显著改善——因为大多数人买得少。注意它同时也是一种「按大小分流」，也就是第 12 章说的「把一条 c² 大的队拆成两条 c² 小的队」。两个机制叠加。

为什么把「大查询」隔离出去那么有效。数据库里把分析型查询和事务型查询分到不同的连接池，这个动作在总工作量上什么都没改，但它让 OLTP 请求不再排在 OLAP 后面。这就是这一章 + 第 12 章的组合拳。

操作系统的进程调度。Linux 的 CFS 不是 SRPT，但它有类似的效果：交互式进程（经常睡眠、CPU 用得少）会积累「虚拟运行时间」上的优势，被优先调度。这让打字有响应，而后台编译慢一点没人在意。这是「按观察分类」而不是「按预测分类」的又一个例子。

反例：不要在支付系统里用 SJF。如果「短」和「金额小」相关，那么 SJF 会系统性地让大额交易变慢。当任务的长短和它的价值相关时，按长短调度就变成了按价值反向调度。这时候该用的是第 19 章的显式优先级。

✗ 这个直觉是错的

让短的先走，等于牺牲长任务来讨好短任务。这是把痛苦转移，不是消除痛苦——总体上是零和的。总的工作量是零和的，总的等待时间不是。让短的先走能真正减少「人次 × 等待」的总量，因为它减少了「有多少人在等同一个巨无霸」。

上面那个三个活的例子最能说明问题：总等待从 21 降到 3，而两种顺序下最后一个活的完成时刻都是 12。没有任何工作被消灭，也没有任何工作被加速，但总等待少了 86%。

这是这本书里少有的「真的能凭空变好」的地方，值得说清楚它为什么不违反守恒：守恒的是 V(t)（未完成工作量），不是 Σ 等待时间。后者取决于「在每个时刻有多少人在队里」，而这个数是可以被调度改变的。

反过来，上一章那些「不看活长短」的策略之所以改不了平均等待，正是因为它们没有能力影响「多少人在队里」这个量——它们只是在同一群人里换顺序。

◇ 结算

D不到 1。精确地说是 0.548——FIFO 的 2.7%。

如果你选了 A 或 B，你偏了 20 到 40 倍。这个方向的低估很常见，因为「调度只是换顺序」的印象太强了——而上一章刚刚证明过换顺序确实没用。这一章的全部意思就是：一旦允许看活的长短，游戏规则完全变了。

A 「能改善但改不了多少」——低估了 37 倍。这个直觉在 cs² 小的时候是对的（活都差不多长时，SJF 确实没什么可优化的）。 B 「减半左右」——「减半」是一个很多人对优化的默认期望值。在这里它低估了一个数量级。 C 「大约 6」——这是 SJF（不打断）的答案：6.260。如果题目里没写「可以打断」，这就是正确答案。抢占能力值 11 倍。

这一章的一句话

守恒的是工作量，不是等待时间；而让短的先走，是唯一能真正把总等待压下去的调度手段。

下一章处理「谁先走」的另一种版本：不按活的长短，按业务上的重要程度排。你会看到一个精确到小数点后六位都不动的守恒律——拖动优先级的分配比例，两个类别的等待一高一低地变，而一个加权和纹丝不动地停在 3.200000。优先级不生产时间，它只搬账单。