第 03 章

队列——一台价值350万美元的计算机，为什么还要排队？

正在加载交互实验…

第一季 · 人类如何驯服数据

历史主线：1955—1973年，美国麻省理工学院（MIT）及早期分时计算研究

序幕：你写错了一个字母，却要等待几个小时

1959年，美国，剑桥市。如果你是一名麻省理工学院的年轻研究员，想要使用学校的大型计算机，事情可能是这样的：你花费几个小时写出程序。然后把程序交给操作员。操作员将你的程序与其他人的程序收集起来，统一安排计算机执行。你回到办公室，等待结果。几个小时之后，你终于拿到输出，却发现计算机根本没有完成计算。原因可能仅仅是程序中出现了一个错误。你修改它，然后再次排队。这不是虚构的技术困境。20世纪50年代，计算机价格高昂，批处理（Batch Processing）是提高设备利用率的重要方式。程序员通常需要把程序提交给计算中心，等待操作人员统一运行。对于需要反复尝试算法的研究人员来说，这种工作方式十分痛苦。^{[Computer History Museum][MIT CSAIL][Multics]}

想象这样的一天：上午9点，你提交程序。中午，程序终于得到执行机会。下午，你拿到一张错误报告。你发现变量名拼错了。于是，你重新排队。上述时间安排是教学情境，并非某位研究者的具体工作日记录。

在今天，你按下运行键，几乎立即就能看到程序出错的位置。而在那个时代，一次简单的调试可能意味着漫长等待。可是，真正奇怪的地方在于：如此昂贵的计算机，为什么不能让多个人同时使用？为了解答这个问题，我们先认识一个人。

第一幕：1959年，人工智能之父提出了一个奇怪的要求

John McCarthy

1927—2011 · 计算机科学家人工智能领域的奠基者之一，Lisp 语言的发明者，也是计算机分时使用思想的重要推动者。

1955年前后，McCarthy 已经开始思考：既然一台计算机如此昂贵，为什么不能让许多研究人员像使用各自的机器一样，共享它？这种想法在当时并不简单。因为一台计算机只有有限的处理器、内存和输入输出设备。如果两个人同时要求计算机执行不同的程序，谁应该先运行？如果十个人同时提出请求呢？如果第一个程序一直不结束，后面的人怎么办？1959年1月1日，McCarthy 写下了一份备忘录，题为 A Time Sharing Operator Program for our Projected IBM 709，提出为 MIT 的 IBM 709 计算机建立分时使用机制的设想。这份历史文件保存了下来。^{[www.SailDart.org][Computer History Museum]}

历史档案阅读 McCarthy 1959年备忘录的文本记录

不过，分时思想并非 McCarthy 一个人独立发明。同一时期，英国的 Christopher Strachey 等研究者也在探索相关方向。这并不是一个人突然提出一个概念，整个世界就立刻改变的故事。它更像是许多程序员同时遇到了同一种痛苦，开始寻找不同的解决办法。而实现这种梦想，需要一个看似简单、实际上非常关键的东西：让等待中的任务有秩序地轮流运行。我们今天的主角——队列，终于要登场了。

第二幕：队列的思想——先到的人，先获得服务

假设现在有四位研究员，分别向计算机提交任务：

计算中心任务队列

队首 FRONT队尾 REAR

A

B

C

D

已经完成的任务暂无

队列（Queue）的核心规则是：First In, First Out，FIFO，先进先出。与上一章的栈形成鲜明对比：

	栈 Stack	队列 Queue
顺序	后进先出 LIFO	先进先出 FIFO
加入	Push	Enqueue
移除	Pop	Dequeue
典型用途	函数调用、DFS	任务等待、BFS

但是请注意，这里隐藏着一个历史上的重要区别。队列并不是在1959年才被发明的。人类很早就使用排队的组织方式。我们也不能把 FIFO 说成由 McCarthy 或 MIT 的研究者首次提出。真正的新问题是：如何把等待队列与计算机的自动调度机制结合，让很多程序有效共享昂贵的计算资源？这才是改变计算机历史的部分。

第三幕：1961年，Corbató 决定让一台计算机服务多个人

Fernando Corbató 与 MIT 的 IBM 7090，1962年前后。MIT Museum 藏有该历史照片。接下来登场的，是 Fernando J. Corbató，通常被同事称为 Corby。他在1956年获得 MIT 物理学博士学位，后来投身于计算中心的工作。Corbató 观察到，研究人员与计算机之间的关系存在严重问题。计算机本来应该帮助人们更快地探索想法，可人们反而要花费大量时间等待计算机。1961年，Corbató 与 Robert Daley、Marjorie Merwin-Daggett 等人开始开发一种新的计算机系统：CTSS — Compatible Time-Sharing System（兼容分时系统）。它的目标不是简单提高计算机的运算速度，而是改变人们使用计算机的方式。

历史时间线

1959年：McCarthy 提出分时操作程序的书面设想。
1961年春：Corbató 团队开始 CTSS 的设计与开发。
1961年11月：CTSS 早期版本公开演示，支持多个用户共享计算机。
1962年：团队发表论文，介绍其实验性分时系统。
1963年：CTSS 发展为实际使用的多用户系统，并为 Project MAC 的研究提供基础。

这些时间点可在 MIT 的历史资料、CTSS 早期论文与参与者的回忆中相互印证。^{[MIT CSAIL][IEEE Xplore][Multics]}

机器并没有突然变成四台

CTSS 的魔法，并不是让一颗处理器同时真正执行四份计算。而是不断地让不同用户的程序获得执行机会。用户 A 运行一段时间。然后切换到 B。B 运行一段时间。再切换到 C。只要切换足够及时，每个用户就能获得一种近似于独占计算机的交互体验。不过这需要解决三个困难。第一，计算机必须能够中断正在执行的程序，不能总是等待程序主动退出。第二，计算机必须记住每个程序运行到了哪里。否则，下次轮到它时，就不知道从哪里继续。第三，不同用户的程序必须互相隔离，避免一个程序破坏其他程序或操作系统。为此，CTSS 的硬件配置逐渐增加了间隔计时器、内存保护和内存重定位等机制。用户程序与操作系统也需要受到适当隔离。^{[Multics][Wikisource, the free online library]}这已经不是简单的排队，而是操作系统设计的开端。

第四幕：现在，让我们亲自经营1960年代的计算中心

接下来不是历史事件的原样复现，而是一个简化的教学模拟。假设计算机面前有三个任务：

A：需要执行 5 个时间单位。
B：需要执行 3 个时间单位。
C：需要执行 4 个时间单位。

而我们的规则是：每个任务一次最多运行 2 个时间单位。时间用完却还没完成的任务，必须回到队尾等待。这种调度思想叫作时间片轮转（Round Robin）。真实的 CTSS 有更复杂的优先级、时间片与交换策略，并不等同于下面这个简单的轮转队列。

1963年的迷你调度室

简化的单核 CPU · 轮转调度

模拟器

时间片长度2 单位

1（切换频繁）5（等待较久）

等待执行的任务队列

A剩余 5

B剩余 3

C剩余 4

CPU 执行时间线已运行 0 / 12 单位

012

先将时间片设成 2，然后连续执行，观察 A、B、C 如何不断回到队列尾部。你可能发现了两个现象。现象一：每个任务不必等待前一个任务彻底结束。这正是交互式计算的重要需求。如果 A 是一个很长的程序，B 不应该因此永远无法得到响应。现象二：时间片不能无限缩短。因为真实操作系统切换任务并不是免费的。切换时，需要处理 CPU 寄存器、执行上下文、调度状态等信息，还可能造成缓存和内存管理方面的额外开销。时间片过长，用户响应速度可能下降；时间片过短，CPU 又会花费过多时间处理任务切换。这说明一个有趣的事实：调度算法不是简单地追求公平，而是在响应速度、吞吐量与系统开销之间寻找平衡。

第五幕：一个并不完美，却改变世界的系统

CTSS 的研究发展没有止步于1961年的演示。1963年前后，系统逐渐加入磁盘存储、文件管理和更成熟的终端支持。研究人员不再只能把一叠程序交给操作员，然后等待打印结果。他们开始能够通过自己的终端与计算机直接交互。

甚至，一个新的问题也出现了：当许多用户都开始拥有自己的文件时，系统怎样管理这些文件？怎样防止用户之间互相干扰？怎样分享数据？CTSS 推动了文件系统、用户管理和信息保护等领域的发展。MIT 的 Project MAC 在1963年开始进一步开展分时计算研究。后来，CTSS 的经验又影响了 Multics 的设计。Multics 最终于1969年在 MIT 投入一般使用，而它的设计与实践又对后来的 Unix 产生了重要影响。这条技术发展线索延续到了现代操作系统之中。^{[MIT CSAIL][计算机历史协会][Multics]}

一个特别值得记住的细节

CTSS 并没有在演示成功后的几年里就退出历史舞台。它一直运行到了1973年。这意味着从1961年首次公开演示，到最终退役，这套系统经历了十多年的改进与实际使用。Corbató 后来因为在分时系统及现代操作系统方面的贡献，获得了1990年 ACM 图灵奖。^{[MIT CSAIL][Multics]}但是，我们还没有解释一个问题：队列里的数据，在内存中究竟应该怎样存储？因为如果实现不当，一个看起来只需要拿走队首元素的操作，可能比你想象得慢得多。

第六幕：队列为什么还需要一个圆环？

你之前学习过 Python 的列表。很容易写出这样的代码：

queue = [10, 20, 30, 40]

queue.append(50)  # 入队

first = queue.pop(0)  # 出队

逻辑完全正确。但是，如果列表中有一百万个元素呢？pop(0) 会把第一个元素移除，并使后面的元素向左移动。因此，Python 列表的队首删除通常需要

O(n)

时间。作为工程师，我们当然不能接受队列越长，出队就越慢。于是出现了两种常见的实现方式。一种是使用链表，维护头、尾指针。另一种是使用循环队列（Circular Queue）。循环队列的思想非常巧妙：既然物理内存是一段固定长度的数组，为什么不让尾部逻辑上连接回开头？

循环队列：首尾相连的存储空间

容量 3 / 6Front: A

试着出队两次，再连续入队，观察数据如何绕过数组末尾，重新使用前面的空位。

这里最重要的公式是：

\text{rear}=(\text{front}+\text{size})\bmod \text{capacity}

其中 % 表示取模运算。当索引走到数组末尾后，下一次便回到开头。这让固定容量循环队列的入队和出队都可以在

O(1)

时间内完成。而在 Python 中，我们通常不必自己实现这些细节，因为标准库提供了 collections.deque：

from collections import deque

queue = deque()

queue.append("A")
queue.append("B")
queue.append("C")

print(queue.popleft())  # A
print(queue.popleft())  # B

它支持两端高效插入和删除，通常都是

O(1)

。注意，Python 的 deque 并不是简单的单个固定长度循环数组，而是采用更复杂的分块存储实现。

第七幕：1959年，另一个数学家用队列找到了走出迷宫的方法

这一幕，我们要回到同样的年代，但换一个场景。这一次，问题不再是让用户轮流使用计算机，而是一个古老的数学难题：从迷宫的一端走到另一端，怎样才能保证找到最短的路线？

Edward F. Moore（1925—2003）美国数学家与计算机科学家，在自动机理论和计算理论方面作出了重要贡献。

1959年，Moore 发表了题为 The Shortest Path Through a Maze（穿越迷宫的最短路径）的论文。这篇论文成为广度优先搜索及无权图最短路径算法历史上的重要文献之一。^[BibBase]请注意，广度优先搜索（BFS）的思想不是简单地沿着一条路一直走到底。它采取一种完全不同的策略。假设你站在迷宫入口。首先，检查距离入口一步的所有位置。然后，检查距离入口两步的所有位置。接着，检查距离入口三步的所有位置。一层一层向外扩散。只要所有移动的代价相同，第一次到达终点时，就找到了步数最少的路线。这听起来像什么？没错，队列。先发现的位置，先被探索；后发现的位置，排在队尾等待。

迷宫搜索实验：亲眼看看 BFS 怎样找到最短路径

迷宫探索实验室

BFS · 无权网格最短路径

0 / 35 步探索

墙壁

已探索

最短路径

拖动进度条，观察 BFS 如何从入口向外逐层探索。格子中的数字表示距离入口的步数。

刚才的实验展示了一个非常重要的关系：队列保证了探索的层次顺序，层次顺序保证了 BFS 在无权图中第一次发现节点时得到的路径长度最短。如果我们把队列换成栈，会发生什么？那就变成了一种深度优先的探索方式。它可能一口气沿着某条走廊走很远，之后才回来寻找另一条路。DFS 可以找到通路，但一般不能保证找到最短通路。而 BFS 利用 FIFO 顺序，天然优先探索距离更近的位置。这不是偶然，而是数据结构直接影响算法行为的典型例子。

用 Python 实现 BFS

from collections import deque

def bfs(graph, start, target):
    queue = deque([start])
    visited = {start}

    while queue:
        node = queue.popleft()

        if node == target:
            return True

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return False

如果图用邻接表表示，BFS 的时间复杂度为：

O(V+E)

其中

V

是顶点数，

E

是边数。因为每个顶点最多被访问一次，每条边也只需要被检查有限次数。这里的代码只判断目标是否可达。如果还要重建最短路径，需要像刚才的迷宫模拟一样，额外记录各节点的前驱。

第八幕：从1961年到今天，队列一直没有离开我们

在现代计算系统中，队列的思想比你想象的更普遍。

操作系统等待运行的线程、设备 I/O 请求和异步事件，需要由内核按照调度策略组织与处理。许多场景会使用一个或多个队列，但不一定严格遵守 FIFO。

消息队列生产者不断产生任务，消费者按照处理能力逐步取出。实际系统还要考虑确认、重试、并发、持久化和消息顺序等问题。

计算机网络网络设备可能暂时缓存等待传输的数据包，再由不同的队列管理或调度策略决定发送顺序。

不过，现代调度问题也告诉我们：FIFO 并不总是最好的选择。例如，一个需要执行10小时的后台任务排在前面，而一个只需要几毫秒的紧急请求排在后面。如果所有任务必须严格执行完毕才能轮到下一个，那么短任务的响应时间可能非常糟糕。所以人类又继续发明了优先队列、最短作业优先调度、多级反馈队列等机制。这正是算法不断演化的原因。

本章思考：当公平与效率发生冲突

假设有三份任务同时到达：

任务	所需 CPU 时间
A	10 ms
B	2 ms
C	1 ms

我们比较两种执行顺序。按提交顺序 FIFO：A → B → C按最短任务优先 SJF：C → B → A只考虑等待时间，不计切换成本，两种方式的平均等待时间分别为：

FIFO： $(0+10+12)/3 \approx 7.33\text{ ms}$
SJF： $(0+1+3)/3 \approx 1.33\text{ ms}$

第二种方式显著降低了平均等待时间。可是，如果新的短任务源源不断出现，长任务又会怎样？它可能一直得不到执行机会。这叫作饥饿（Starvation）。于是你发现，调度算法面临的选择已经不只是先进先出：它还必须回答什么叫公平、什么叫高效，以及什么样的等待是可以接受的。

尾声：一个队列，改变了人与计算机的关系

回顾这个故事：1950年代，程序员不得不等待昂贵的计算机。1959年，McCarthy 等研究者推动让多人交互式共享计算机的思想。1961年，Corbató 的团队演示了 CTSS，证明多用户分时系统具有现实可行性。而在同样的年代，Moore 的迷宫最短路径研究，也展示了逐层探索这一算法思想的力量。这些研究并不是同一个项目，也不是由队列这一数据结构单独创造出来的。但它们共同说明了一件事：在复杂系统中，决定谁先得到处理，有时与决定怎样处理同样重要。

第三章的知识总结

概念	最重要的思想
Queue	先进先出，FIFO
Enqueue / Dequeue	队尾加入，队首取出
Circular Queue	利用取模运算复用数组空间
Round Robin	让多个任务轮流获得时间片
BFS	按距离逐层探索
复杂度	合适的队列实现可使入队、出队达到 $O(1)$

历史延伸阅读

本章重点依据三类史料：计算机历史博物馆：John McCarthy 的分时计算回忆、CTSS 参与者 Tom Van Vleck 对 IBM 7094 与 CTSS 的回顾，以及 MIT CSAIL：Fernando Corbató 生平与研究贡献。Moore 的1959年论文可通过《The Shortest Path Through a Maze》书目信息进一步查找。

下一章预告

第四章：哈希表——一个让寻找几乎不再需要等待的发明

想象一名图书管理员，面对一百万本没有排序的书。有人问：“能不能不打开目录、不进行二分查找，直接算出这本书应该放在哪里？”这种看起来近乎不可能的要求，最终成为哈希技术的核心思想。下一章，我们将从20世纪50年代计算机存储与检索的实际困境出发，探索哈希技术的早期历史、冲突处理的不同发明路线，以及为什么哈希表可以把很多查找操作的平均复杂度降到

O(1)

。而最有意思的问题是：如果两个不同的东西，计算出来的位置完全一样，怎么办？