Lamport Bakery — 用取号排队解决并发互斥

是什么

Bakery algorithm（面包店算法）是一种只靠共享内存读写，让多个处理器轮流进入临界区的互斥算法。

日常类比：面包店门口没有保安，也没有叫号机总控；每个顾客自己看一眼别人手里的号码，给自己拿一个更大的号，然后大家按“小号先服务、同号看姓名”排队。

放到程序里，“顾客”就是处理器，“服务柜台”就是只能一个人进去的临界区。

Lamport 1974 的妙处在于：它不依赖一个中心锁变量，也不要求“读和写同一格时读到的值一定正确”。

只要每个处理器只写自己的 number[i] 和 choosing[i]，别人可以读它们，算法仍然能证明互斥和先来先服务。

这篇论文因此成了共享内存并发里解释“公平性、故障、非原子读写”时绕不开的经典。

为什么重要

不理解 bakery algorithm，下面这些事都很难说清楚：

• 为什么互斥不一定要靠硬件 test-and-set、CAS 或中央信号量。
• 为什么“先来先服务”比“总会有人进去”更强，它还要避免某个线程长期饿死。
• 为什么并发算法证明常常要先给状态命名，比如 doorway、bakery、critical section。
• 为什么 Lamport 后来能提出逻辑时钟、TLA+，因为他一直在把“顺序”从直觉变成可证明对象。

核心要点

1. 每个人自己取号：想进临界区前，处理器先声明自己正在取号，再把号码设成当前最大号码加一。类比：你进店先举手说“我正在拿号”，防止别人误以为你还没参加排队。

2. 按二元组排队：比较顺序不是只看号码，而是看 (number[i], i)；号码小的先，号码一样时编号小的先。类比：两个人同时拿到 17 号，就按身份证尾号固定打破平局。

3. 先等别人取完号，再比较：choosing[j] 的作用是让你不要在别人号码写到一半时就下结论。类比：柜台员看到顾客还在撕号码纸，就先等他撕完再判断谁排前面。

4. 不靠中心故障点：早期算法常让所有人抢一个变量，那个内存单元坏了系统就停。Bakery algorithm 把状态分散到每个处理器自己的内存里，坏一个人不一定拖垮全场。

实践案例

案例 1：面包店算法的最小伪代码

choosing[i] = true
number[i] = 1 + max(number[1..N])
choosing[i] = false

for each j:
  wait until choosing[j] == false
  wait until number[j] == 0 or (number[i], i) < (number[j], j)

critical_section()
number[i] = 0

逐部分解释：

• choosing[i] 是“我正在取号”的门牌，不是锁。
• number[i] 是自己的排队号；0 表示我现在不排队。
• 两个 wait 先确认别人取号完成，再确认自己排在别人前面。
• 离开临界区时把号码清零，等于把票丢掉。

案例 2：为什么同号也不会冲突

def before(me, other):
    my_number, my_id = me
    other_number, other_id = other
    return (my_number, my_id) < (other_number, other_id)

print(before((7, 2), (7, 5)))  # True
print(before((8, 1), (7, 9)))  # False

逐部分解释：

• 两个处理器可能同时看见最大号是 6，于是都拿到 7。
• 只看号码会打平，算法就把处理器编号放进比较。
• (7, 2) 永远排在 (7, 5) 前面，所以所有人会得出同一个顺序。
• 这个平局规则是人为规定，但它足够让互斥证明成立。

案例 3：为什么要有 choosing

P1: choosing[1] = true
P1: number[1] = 8
P1: choosing[1] = false

P2: wait choosing[1] == false
P2: compare (number[1], 1) with (number[2], 2)

逐部分解释：

• 如果没有 choosing[1]，P2 可能在 P1 写号码的中间读到旧值或奇怪值。
• Lamport 的论文甚至允许“读写重叠时，读可以返回任意值”。
• choosing 把“正在取号”这段短窗口标出来，让别人不要把半成品当最终排队号。
• 这也是论文最反直觉的地方：不要求读一定正确，却还能保证整体顺序正确。

踩过的坑

1. 把 number[i] 当成锁：它只是排队票，原因是多个处理器可以同时持有非零号码。

2. 忽略 choosing 数组：少了它会在别人取号未完成时比较，原因是读写重叠可能看到不稳定状态。

3. 以为号码有固定上限：论文里的号码理论上无界，原因是持续有人排队时最大号码会一直增长。

4. 把“互斥”误解成“高性能”：算法证明漂亮，但每次进临界区要扫描 N 个处理器，原因是它优先解决正确性而不是速度。

适用 vs 不适用场景

适用：

• 操作系统课程里学习互斥、饥饿、公平性和临界区规约。
• 形式化验证练习，比如用 TLA+ 写一个小模型验证互斥。
• 早期或理论化的共享内存模型：只用普通读写，不借助硬件原子指令。
• 理解“先来先服务”这种强公平承诺到底需要什么状态。

不适用：

• 现代高性能 mutex 实现；CAS、futex、MCS 锁通常更合适。
• 处理器数量很大且临界区很短的场景；每次 O(N) 扫描会浪费缓存和总线。
• 号码必须固定宽度且不能溢出的严格环境；需要额外设计有界变体。
• 弱内存模型下直接照抄到 C/C++；还要考虑编译器重排和内存屏障。

历史小故事（可跳过）

• 1965 年：Dijkstra 提出并发互斥问题和早期纯软件解法，定义了“最多一个进临界区”的核心规约。
• 1966-1972 年：Knuth、de Bruijn、Eisenberg 与 McGuire 继续改进 Dijkstra 的方案，重点解决公平和饥饿问题。
• 1974 年：Lamport 发表这篇 CACM 论文，用面包店取号类比给出更简单的先来先服务算法。
• 后来：Lamport 发现这个算法真正特别的地方，是读写重叠时读值可以任意，这推动了他对共享内存和顺序的后续研究。
• 1990 年代以后：TLA+、模型检查和教材把 bakery algorithm 当作验证并发算法的标准练习。

学到什么

1. 互斥的本质是共同认可的顺序：大家不需要一个中心裁判，只要对“谁排前面”达成一致。

2. 公平性要写进协议，不会自动出现：先来先服务靠取号和二元组比较保证，不是靠操作系统善意调度。

3. 正确性证明比代码更重要：代码只有十几行，但论文大部分篇幅在证明为什么不会两个人同时进入。

4. 共享内存不是天然可靠的黑板：读写重叠、处理器失败、内存分散都会影响算法设计。

延伸阅读

• 原论文 PDF：A New Solution of Dijkstra’s Concurrent Programming Problem。
• DOI 页面：ACM DOI 10.1145/361082.361093。
• Lamport 自述：The Bakery Algorithm。
• dijkstra-1965 —— Dijkstra 先提出互斥问题和早期纯软件解法。
• lamport-time-clocks-1978 —— 同一作者继续研究分布式系统里“顺序”怎么定义。
• sequential-consistency-1979 —— 进一步把共享内存多处理器的正确执行定义成一致性模型。

关联

• dijkstra-1965 —— Bakery algorithm 直接回答 Dijkstra 的并发互斥题，并加强公平性。
• hoare-monitors-1974 —— Monitor 把互斥和等待队列封装成语言结构，是另一条工程路线。
• mcs-locks-1991 —— 同样追求公平排队，但面向现代多核缓存一致性和高性能自旋。
• sequential-consistency-1979 —— 讨论共享内存读写在多处理器里应该呈现什么顺序。
• lamport-time-clocks-1978 —— 从共享内存排队走向消息系统中的因果顺序。
• lamport-tla-1994 —— 这类并发算法后来很适合用 TLA+ 写规格和验证。
• rcu-2001 —— 展示另一种并发思想：不让读者排队，而是延迟回收旧版本。

反向链接

• dijkstra-1965 —— Dijkstra 1965 — N 个进程怎么轮流上厕所而且谁也别卡死
• herlihy-moss-tm —— Herlihy-Moss 事务内存 — 把数据库事务搬进 CPU