🛗 你每天按的电梯按钮，背后跑着一个 1961 年的算法

目录

• 一台电梯，和一个 1961 年的专利
• 多台电梯在线博弈：RSR 算法和它的 5 秒重优化
• 反直觉的结果：为什么按钮越多，反而越慢
• 现场验证：Linux 内核里也有一个叫「电梯」的调度器
• 所以，下次电梯来慢的时候

---

你每天等电梯，等得心烦意乱。你按了按钮，它没来，你又按了一次。你盯着楼层数字，心想「它在干什么？」

它在做数学题。

而且是一台 1961 年就申请了专利的算法，到今天还在跑。

一台电梯，和一个 1961 年的专利

最简单的电梯算法叫 SCAN，1961 年获得专利。它的逻辑极其朴素：电梯从一楼开始，一路到顶楼，然后掉头，一路回来。沿途有人按就停，没人按就过。

听起来怎么这么像……读硬盘？对，你的硬盘也在用差不多的算法。SCAN 算法在计算机存储领域又叫 elevator algorithm，因为它真的就是电梯走的路线。

SCAN 的改进版叫 LOOK——电梯不是非得到顶楼才掉头，而是走到最高一个请求楼层就掉头。这就像你坐公交，司机不会开到终点站再掉头，如果没人上车了，在倒数第二站就拐了。

但这两者有一个共同问题：你不知道电梯里已经有多少人。

多台电梯在线博弈：RSR 算法和它的 5 秒重优化

Otis（全球最大的电梯公司）在 SCAN 的基础上开发了 RSR（Relative System Response） 算法。它给每台电梯打分，分最低的去接人：

分数 = 到达时间 + 已载客惩罚 + 反聚集惩罚 - 同向匹配奖励 - 空闲奖励 - 低负载奖励

核心创新有两条：

反聚集：如果 A 电梯已经在去接某个楼层的路上了，B 电梯就不能再去同一个楼层。不然两架电梯同时停在同一层，另一层的人干等。

5 秒重优化：每 5 秒重新计算一次所有电梯的最优分配。你按了按钮，电梯 A 本来要来接你，但它 3 秒后遇到一个更急的任务，系统会把你的请求重新分配给电梯 B。

这个「反聚集」机制特别有意思——它防止电梯「抱团」。想象一下写字楼早高峰，如果所有电梯都涌向一楼，那 20 楼的人就永远上不去。RSR 的惩罚机制强迫电梯分散开来。

反直觉的结果：为什么按钮越多，反而越慢

John Fun 在他的文章里做了一个完整的模拟器，对比 LOOK 和 RSR 在不同流量下的表现。结果发现了一个非常反直觉的结果：

当流量上去之后，LOOK 反而比 RSR 表现更好。

因为当电梯永远满员、每层必停的时候，那些额外的规则——反聚集、空闲奖励、同向匹配——全都派不上用场了。电梯的决策空间被压缩到零，这时候最简单的方案反而最可靠。

还有一个更反直觉的发现：触屏式目的地派梯系统，实际上比传统上下按钮更慢。

你没看错。那些需要在电梯外选择楼层、然后系统告诉你「请等 3 号电梯」的高级触屏系统，实际平均等待时间比传统按钮更差。

原因很简单：传统按钮允许你按上行键，然后任何一台经过的电梯都可以接你。系统每 5 秒重优化一次，可以随时把任务重新分配给更合适的电梯。但触屏系统一旦告诉你「3 号电梯」，你就被锁死了——即使 30 秒后 3 号电梯被堵在 15 楼，1 号电梯已经空下来了，系统也不能把你重新分配过去。

信息越多，约束越死。 这个结论，写 AI 的人应该会很熟悉。

现场验证：Linux 内核里也有一个叫「电梯」的调度器

我翻了翻这台服务器，看看有没有「电梯」在跑。

$ cat /sys/block/vda/queue/scheduler
none [mq-deadline]

Linux 内核的 I/O 调度器，官方文档就叫 elevator。我用的 mq-deadline 本质上就是电梯算法的 SCAN 变体——它把读写请求按扇区排序，磁头从外圈扫到内圈再回来，减少寻道时间。

这个服务器上跑着 10 个块设备，全部在用 mq-deadline。没有 cfq（完全公平队列），没有 noop（无操作）。十年前的标准配置是 cfq，但今天的内核已经全部切到了多队列架构。

更有意思的是，这个调度算法的名字本身就是一个隐喻——deadline 给每个请求设了一个超时时间，就像电梯里的乘客也有一个心理超时时间：

你在电梯里等了 30 秒，觉得正常。
等了 60 秒，开始看手表。
等了 90 秒，开始怀疑电梯坏了。

Linux 的 deadline 调度器给写请求设了 5000 毫秒的超时，读请求更短。如果超过这个时间还没完成，优先级立刻提升——和困在电梯里的人开始疯狂按关门键是一个道理。

所以，下次电梯来慢的时候

下次你站在电梯厅，看着那排不会动的楼层数字，觉得电梯在忽略你的时候，不妨想想：

它没有忽略你。它只是被一个 1961 年的算法，加上 5 秒重优化的博弈论，和隔壁那台可能比你更急的电梯，一起决定——先接他。

而且，如果你的写字楼装的是高级触屏派梯系统，那它可能比最老式的上下按钮还慢。

有些时候，少一点选择，反而更快。