卷 V · 插队CH 17深度 17/24

先来后到是一种选择，不是天理

队已经排在那儿了。这一卷不再问「怎么让队变短」，只问「谁先走」。而第一个结论就足够让人不适：换一种叫号顺序，平均等待一秒都不会变。

FIFO vs LIFO平均值相同方差给谁
▷ 先估一个数

一条队，利用率 80%。现在把叫号规则从先来后到（FIFO）改成后来先服务（LIFO，像一个栈：最新进来的排最前面）。

不加机器，不改速度，只改顺序。平均等待会怎么变？

A 变长——把人晾着不管，总体肯定更糟 B 完全不变 C 变短——LIFO 有缓存局部性优势，实际会更快 D 取决于负载，高负载时 LIFO 更好

一个守恒量

先看结果：

规则平均等待标准差p50p99最惨的那位
FIFO 先来后到3.7744.6412.21920.9749.2
LIFO 后来先服务3.78812.7700.57157.16405.9

平均等待：3.774 vs 3.788。二十万个请求的模拟，差 0.4%——那是采样噪声，理论上它们精确相等。

而其他每一列都天差地别：

  • 中位数：LIFO 0.571，只有 FIFO 的 四分之一；
  • p99：LIFO 57.16，是 FIFO 的 2.7 倍；
  • 最惨的那位：FIFO 等了 49.2，LIFO 等了 405.9——八倍。

为什么平均值不变

这不是巧合，它有一个非常干净的理由，而这个理由是这一整卷的地基。

定义一个量叫未完成工作量 V(t)：此刻系统里所有活加起来还需要多少时间才能做完。

现在问：换一种叫号顺序，V(t) 会变吗？

不会。因为：

  • 每来一个活，V 就增加那个活的长度——和顺序无关；
  • 服务台每忙一秒，V 就减少一秒——和它在服务谁无关。
# 未完成工作量 V(t)：一条锯齿，只由到达和"服务台忙不忙"决定
V(t)
 │   ╱╲
 │  ╱  ╲   ╱╲
 │ ╱    ╲ ╱  ╲╱╲
 │╱      ╲    ╱ ╲___
 └──────────────────────→ t
   ↑ 来活就跳一格（活有多长跳多高）
   ↓ 服务台忙的时候，以每秒 1 的速度往下走

# ★ 这条锯齿在 FIFO / LIFO / 短作业优先下 **完全一样**
#   只要服务台"有活就干、不偷懒"（这叫 work-conserving，保功）

而 V(t) 的时间平均，通过 Little 定律（第 2 章），直接决定了平均等待。V 不变，平均等待就不变。

◆ 保功原则

只要调度策略满足两个条件：

  1. 保功（work-conserving）：只要有活，服务台就不闲着；
  2. 不看活的长短：决定谁先走时，不参考这个活要做多久。

那么平均等待时间完全相同，不管你是先来后到、后来先服务、还是随机挑一个。

这两个条件都很关键：

  • 破坏第一条（服务台故意闲着），平均等待会变长——这就是第 20 章批处理的攒批阶段在做的事；
  • 破坏第二条（看活的长短），平均等待会变短——这就是第 18 章短作业优先的全部秘密。

这本书剩下的调度章节，本质上都是在讨论怎么破坏第二条，以及破坏它的代价。

那 LIFO 到底改了什么

它改了方差的分配。

FIFO 下，每个人的等待都差不多——大家排在同一条队里，前面有几个人就等几个人的时间。等待时间的分布相对集中（标准差 4.641）。

LIFO 下，情况分裂成两种：

  • 系统不忙的时候来的人：立刻被服务，等待接近 0。大多数人属于这一类（中位数只有 0.571）。
  • 系统忙的时候来的人：被后来的人不断插队，可能等到天荒地老（最惨的等了 405.9）。

总的等待时间是守恒的，所以「大多数人等得更少」必然意味着「少数人等得多得多」。这是一笔零和交易，而不是一次优化。

∑ 算一遍：什么时候该选 LIFO

听起来 LIFO 只有坏处？不一定。它在两种场景下是明确更优的：

1. 有超时的时候。假设所有请求超过 T 就没意义了（用户已经走了）。FIFO 下，队积压时每个人都在慢慢逼近超时，最后可能所有人都超时——你做完的工作全部白费。LIFO 下，新来的人立刻被服务，至少有一部分请求是有效的。

# 极端例子：队里积压了 100 个请求，超时是 10 个服务时长
FIFO：从最老的开始做，做到第 10 个的时候，前面 10 个刚好卡在超时线上，
      后面 90 个全部超时 → 有效产出 ≈ 10 个
LIFO：从最新的开始做，最新的都还很"新鲜"，
      而最老的那些反正已经超时了 → 有效产出高得多

这个道理是：当工作会「变质」时，先做新鲜的。Facebook 的负载脱落系统、很多消息队列的过载策略，用的就是这个思路（有时叫 LIFO 或者 CoDel 式的丢弃）。

2. 缓存局部性。最近提交的任务，它的数据大概率还在缓存里。LIFO 能提高命中率，也就是降低 E[S]——这是在打第 8 章的第三个因子。工作窃取调度器（Go、tokio、ForkJoinPool）本地队列用 LIFO、偷别人的时候从队尾偷（也就是对被偷者是 FIFO），正是在同时吃这两个好处。

✎ 术语正名：「公平」（第二次）

第 13 章说过叫号机卖的不是公平是效率。这一章给出真正只关于公平的那个选择。

但「公平」本身也得拆开。至少有三种互相冲突的公平：

  • 顺序公平：先来的先服务。FIFO 满足，LIFO 严重违反。
  • 比例公平：等待时间应该和你的活的长短成正比（办一件小事不该等一件大事那么久）。FIFO 严重违反这一条——第 18 章会看到，FIFO 下一个 0.076 长的小活平均要等 20.204，被放大 2025 倍。
  • 结果公平：没有人等得特别惨。FIFO 满足，LIFO 严重违反。

FIFO 之所以是默认选择，是因为它同时满足第一和第三条，而这两条是看得见的。它违反的第二条是看不见的——没有人会注意到「我这个简单请求本来只该等 0.1 秒」。

默认值往往不是最优的，只是最不容易被投诉的。

▸ 在现实里

过载时把队列从 FIFO 换成 LIFO。这是一个在几家大厂被独立发现过的技巧。系统过载时，FIFO 队列里堆的全是「客户端早就超时放弃了」的请求，服务器在拼命处理没人要的结果。改成 LIFO，先处理最新的，有效吞吐立刻回升。注意这不是在提高吞吐，是在提高「有效」吞吐——总工作量守恒，但浪费在死请求上的部分变少了。

电梯不是 FIFO。电梯用的是「扫描」算法（SCAN，也叫电梯算法）：往一个方向走到底，再折返。这既不是 FIFO 也不是 LIFO，而是为了降低 E[S]（移动距离）而牺牲顺序公平。磁盘调度器用的是同一个算法，理由也一样。

客服工单。大多数工单系统默认 FIFO。但如果积压严重，先处理最老的意味着客户已经等了三天而且很生气，而新提的工单还有救。这里的「变质」是客户满意度。很多成熟的客服团队会做分流，而不是纯 FIFO。

✗ 这个直觉是错的
调度策略能提高系统的整体效率——选对了算法，同样的机器能处理更多的活。 调度不生产时间。在保功且不看活长短的前提下，它连平均等待都改不了。它能改的只有三样：方差怎么分、谁先谁后、以及（如果它看活的长短）把总等待压低。

这个直觉的错误之处在于把「调度」和「优化」混为一谈。真正能提高吞吐的调度只有两类：

  • 改变 E[S] 的：比如通过缓存局部性、批量合并、减少上下文切换。这不算调度的功劳，算局部性的功劳。
  • 避免浪费的：比如不去处理已经超时的请求。这也不是提高效率，是减少无效工作。

除此之外，调度就是一场分配游戏。而认清这一点其实是解放性的：当你在争论「用哪个调度算法」时，你争的不是效率，是价值判断——谁该等，谁不该等。那是一个产品问题，不是技术问题。

◇ 结算

B完全不变。二十万个请求的模拟：FIFO 3.774，LIFO 3.788，差 0.4%（采样噪声，理论上精确相等）。

但标准差从 4.641 涨到 12.770，最惨的那位从等 49.2 变成等 405.9。

如果你选了 A，你的直觉抓住了「有人会等很久」这件事——那是对的，只是它被「大多数人等得更少」精确地抵消掉了。

A 「把人晾着不管，总体肯定更糟」——直觉上完全合理，而且它抓住了真实的一半（尾巴确实更糟）。它错在没意识到另一半（中位数好了四倍），而两半恰好抵消。 C 「LIFO 有缓存局部性优势」——这在真实系统里确实成立，而且是工作窃取调度器选择 LIFO 的原因之一。但那是在改 E[S]（第三个因子），不是调度本身的效果。在这道题的纯排队模型里，服务时间是给定的。 D 「取决于负载」——平均等待相等这件事在任何负载下都成立，它不依赖 ρ。变的只是方差的差距有多大（ρ 越高差距越夸张）。

这一章的一句话

只要服务台不偷懒、而且不看活的长短，换任何顺序都改不了平均等待——你能改的只有把方差分给谁。

下一章去破坏第二个条件：看活的长短。这是唯一一个能真正压低平均等待的调度手段，而效果大得惊人——同一批活，先来后到平均等 20.292，剩余时间最短优先只要 0.548。那些最小的活，从被放大 2025.1 倍变成被放大 1.0 倍。而代价，写在第四档那一列里。