Lamport 1974：面包店算法怎样给互斥加上先来先服务

破除误解：号码不是把 1965 年贴上票根，读重叠也不是原子寄存器课#

第一层误解把面包店听成「给 Dijkstra 1965 贴上票根」，或听成与 Peterson 1981 同一张两人配方。1965 年那一页的全体进程都去设置并检查同一个 \(k\)；兰波特点名：先前 Knuth、de Bruijn、Eisenberg 与 McGuire 以及迪科斯彻本人的解，都有这一笔。真多机系统里，存 \(k\) 的那一块存储器坏掉，全体停转。本页把 \(choosing[i]\) 与 \(number[i]\) 放进第 \(i\) 台自己的存储器：别人可以读，只有自己写。人数仍是 \(N\)，仲裁者却被拆掉了。彼得森那则短注要到 1981 年才把两人收成两面旗加一个 \(TURN\)，变量三枚，体裁是 IPL，封面不是门口与号码。把三页听成 1965 年的补丁，或听成两人旗的预习，都会把「谁写哪一块字」这一条装置差抹平。

第二层误解把本页听成「读和写各自必须原子」，或听成必须先有测试并设置。摘要与算法节写得很硬：同一单元上读与写同时发生时，只有写必须被正确完成，读可以返回任意值。后来文献把这种读叫安全寄存器；1974 年的句子还没有这个名字，它直接允许垃圾读数。\(choosing\) 被证明里当成本质上只有零与非零两档，因而从某一台的视角可以把重叠读写收成「先读到零」或「先写成非零」。\(number\) 没有这档简化：取最大值时参数可按任意次序读，读到别人正在改写的号码，不必是任何一个曾经写下的整数。困难正在这里：协议必须在这种任意读数下仍保住互斥与先来先服务。把本页收成原子寄存器上的课堂互斥，等于把论文故意削弱的假设提前加回去。概念证据到此为止，不是配方。

第三层误解把先来先服务听成 1965 年条件 (d) 的同义反复，或听成克努斯已经把公平写完。迪科斯彻要排除的是：临界区空着、又有人在入口打转时，不能全体永远进不去。那是集体进展，并不担保某一个编号不会被别人无限次超过。克努斯 1966 年构造了一种调度，使一台一直想进、却看着别人反复完成临界区；互斥作为安全性可以仍成立。本页把 Knuth 的那条个体活性写进合同第 2 款，再用门口把「先请求」收成可比较的先后：想进的人先执行一段步数固定、不含循环的代码，然后保证比任何更晚才提出请求的人更早进入临界区。于是单独一台不会被堵住，除非整个系统已经死锁。这比 (d) 强，也比「终将有人进去」强。它仍不是等待自由：停在临界区里的人按设计挡住别人；不停失败又重启的人，也可以凭坏运气让别人在检查 \(choosing\) 时永远看见非零。把三页听成「公平已经在 1966 年评论里解决」，或听成「停机也挡不住我」，量词都错了。

第四层误解把标题听成 1978 年的事件偏序、1979 年的多处理器合同、兼职议会，或听成可抄进 pthreads 的临界区模板。逻辑时钟 谈的是消息与编号；本页进程只通过存储器往来。顺序一致性 要把全体取数存数收成某一条尊重程序序的交错；本页连「读必须看见某次写」都拒绝承诺。Paxos 选值，封面更远。把这三页听成教人如何让互斥失效、如何绕过入口、如何把赋值布置进线程库的步骤，类型都错了。

1974 年的装置：门口、号码，以及读可以任意、写必须正确#

问题从 \(N\) 台异步计算机说起。通信手段只有共享存储。每台跑一段可看成循环的程序，循环分成临界区与非临界区。迪科斯彻的问题经克努斯加码之后，解必须满足三条。任意时刻至多一台处于临界区。每一台终将能够进入临界区，除非它停机。任一台可在非临界区停机。此外不得对运行速度作假定。先前解让全体处理器设置并检查同一个 \(k\)；那一单元所在的存储器失效，系统就停。信号量同样暗示依赖单一硬件部件。本页假定每台有自己的存储单元：可以读任何一台的字，只需写入自己的字。处理器可在任意时刻失效。失效后立刻进入非临界区并停机；随后会有一段时间，读它的存储器得到任意值；最终对它的读必须得到零。实践中可用「读请求在时限内无应答」来检测失效。本页复述这些职务，是为了让三页里的断言能被跟上，不是一份把赋值抄进线程库的清单。

公共存储是两个整型数组 \(choosing[1:N]\) 与 \(number[1:N]\)。第 \(i\) 号字落在第 \(i\) 台自己的存储器里，初值都是零。\(number[i]\) 的取值无上界。进程名为 \(1,\ldots,N\)。类比是面包店发号：号最小的下一位被服务；两人拿到同一号，则名字较小的先走。这里没有柜台职员代发号，每台自己选号。选号的那段无循环代码叫做门口：第 \(i\) 台把 \(choosing[i]\) 写成 1，把 \(number[i]\) 写成 1 加上当时读到的全体号码的最大值，再把 \(choosing[i]\) 写回 0。最大值的参数可按任意次序读取。离开门口之后进入论文所说的面包店：对每一个 \(j\)，先等到看见 \(choosing[j]\) 为零，再等到看见 \(number[j]\) 为零，或者序对 \((number[i],i)\) 不大于 \((number[j],j)\)。序对按字典序：先比号码，相同再比进程名。通过这层等待才进入临界区；离开时把 \(number[i]\) 写回 0，进入非临界区，再从门口开始下一轮。执行必须从非临界区开始。允许任意时刻失效后再从非临界区重启并把两字清零；若一台不断失效又重启，则可能把系统卡死。

证明先给两个位置词。第 \(i\) 台在门口，当且仅当 \(choosing[i]=1\)。它在面包店里，从把 \(choosing[i]\) 复位为零起，直到失效或离开临界区。断言一：若 \(i\) 与 \(k\) 都在面包店里，并且 \(i\) 进入面包店早于 \(k\) 进入门口，则 \(number[i]<number[k]\)。理由是 \(k\) 选号时 \(number[i]\) 已经是现在这个值，因而 \(k\) 必须选到至少大一的数。断言二：若 \(i\) 在临界区、\(k\) 在面包店且 \(k\neq i\)，则 \((number[i],i)<(number[k],k)\)。证明把 \(choosing[k]\) 从 \(i\) 的视角收成零与非零两档，再比较 \(i\) 最后一次看见 \(choosing[k]\) 为零的时刻，与 \(k\) 进门口、写完号码、离开门口的时刻。两种情形分别回到断言一，或回到 \(i\) 在等待里读到了 \(k\) 当前的号码。断言三：只允许有界多次失效。若无人处于临界区，又有一台在面包店里且不失效，则必有某台终将进入临界区。否则过了某一时刻再无人进出面包店，那时持有最小序对的那一台会走完对全体 \(j\) 的等待。断言二推出任意时刻至多一人在临界区。断言一与断言二合起来，推出进入临界区按先来先服务。因而单独一台不会被堵住，除非系统整体死锁。断言三推出：死锁只可能来自有人停在临界区里，或来自无界的失效—重启序列。后一种坏运气可以使第 \(i\) 台在检查 \(choosing[j]\) 时永远看见非零。

它证明了什么，没有覆盖什么#

它证明了：在「每台只写自己的字、重叠读可以任意」这一弱于 1965 年字不可分割的装置上，\(N\) 机临界区互斥仍可写成一份不靠中央 \(k\) 的构造；该构造按三则断言满足互斥、门口之后的先来先服务，以及「个体不被堵住除非系统死锁」。意义首先是存在性与故障隔离：真多机里一块存储器失效，不必再让全体停转；读数可以脏，合同仍能被论证。作者自己把「不依赖任何形式的中央控制，因而对部件失效更不敏感」写成收束。号码在持续有人待在面包店时可以任意变大；论文给出实践上界：若门口至多每毫秒进入一台，运行一年后号码仍小于 \(2^{35}\)，前提是读到的值从不大于曾经写下的值。无上界提出一个当时未决的理论问题：能否在有限状态、仍只写自己存储器、仍先来先服务的前提下另写一份算法。脚注说作者后来找到了，但相当复杂。那份后文不是本页封面。

它没有重做 Dijkstra 1965 的 \(b,c,k\) 合同，也没有把克努斯、德布鲁因、艾森伯格与麦圭尔的评论收成自己的正文。那些解仍围着一个 \(k\) 转，是邻居。它没有覆盖 Peterson 1981：两人、三枚变量、旗与 \(TURN\) 是七年后的短注。它没有给出测试并设置，也没有把互斥收成系统调用。信号量属于 迪科斯彻 在 THE 里的另一条工作，本页只当作依赖单一硬件的对照。它没有覆盖 1978 时钟，没有覆盖 顺序一致性，更没有覆盖兼职议会。

它没有覆盖 线性化：临界区是一段程序文本，不是对象上带调用—返回区间的生效点。它没有覆盖 等待自由：持有临界区或在门口失败重启的进程，按设计可以挡住别人。它没有覆盖 内存一致性模型 在弱序下哪些号码比较会失效。它允许两台在特定情形下同时处于临界区、以及按优先级而不是按先来先服务接待——那是论文预告的推广，将另文描述，不是这三页已经闭合的证明。本页不提供如何把上述赋值抄进 pthreads、如何布置锁省略、如何让互斥失效或绕过临界区的步骤。三页回答的是「没有中央 \(k\)、读可以任意时，互斥能否带上先来先服务」；1965 年那一页回答的是「没有仲裁者时 \(N\) 机互斥能否被推理」。两句都不是操作单。

跨域连接#

• 证明：兰波特把正确性收成门口、面包店与三则断言，等于承认：一段并发控制若不能在「读可以任意」之下被论证，就不算解。可是这份证明仍是操作叙事。互斥靠断言二的序对比较；先来先服务靠断言一把「先进面包店」焊到「号码更小」上；活性靠有界失效之下最小序对终将走完等待。证明不依赖读到的值是哪一次写。并发里最常见的事故，正是把「先来先服务」听成等待自由，或把「读可以任意」听成已经在弱内存模型上闭包。
• 认识论：门口回答的不是「我心里觉得我先到」，而是「我已经把选号这一段固定步数做完，并且把 \(choosing\) 放倒」。别人能够合法使用的证据，只有已经写进各台存储器的字。重叠读可以返回任意值，意味着你不能把一次读数提升为关于他人号码的确定知识；你只能把 \(choosing\) 的零与非零当成「他是否还在门口」的信号，再在他离开门口之后去读号码。把一次可能脏的读当成「他的号比我小」的私有知识，正是这三页要拒绝的那类解。
• 等待自由：1991 年的尺从反面量这篇。等待自由要求我完成自己的操作只靠自己的有限步，哪怕别人已经停机。临界区按定义把别人的进入交给我何时离开；若我停在里面，等待者永远进不去。本页的先来先服务保护已经走出门口的人，并不保护停在临界区里的人，更不保护被不断失效重启的邻居按在 \(choosing\) 检查上的人。赫利希后来证明：只用寄存器，两个进程甚至无法等待自由地达成共识。1974 年能做成的，恰好是一种必须阻塞、却把阻塞排成票号的协调。寄存器够写带先来先服务的互斥，不够写两人的等待自由共识——两句话可以同时真。
• 顺序一致性：顺序一致性要求执行看起来像某一条尊重程序序的交错，因而一次读应当看见某次已完成的写。本页连这句都不要求：重叠读可以与任何已写下的值无关。证明仍使用跨单元的先后——先把 \(choosing\) 放倒，再让别人读 \(number\)——但把「读到的号码必须是写进去的那个」从装置里删掉了。1979 年命名的是让「先写后读」互斥合法的外观；1974 年演示的是：即使外观再弱一档，只要写自己的字、并把门口当成选号尚未完成的信号，互斥与先来先服务仍可能被保住。
• 自由：没有中央 \(k\)，意味着没有一块存储器可以充当永久立法者；每台只为自己的号码立法。先来先服务把「不得被后来者无限超过」写成已经走出门口的人可以主张的权利，比 1965 年只保护集体进展更靠近个体。可是互斥本身又是一种严格的消极自由：当我处于临界区，别人进入的自由被暂停。暂停有期限，前提是我终将离开并把号码清零。去掉仲裁者，并不自动得到等待自由意义上的不受阻挡；加上票号，也不自动得到停在临界区里仍不挡住他人的权利。

参考文献#

• Leslie Lamport, "A New Solution of Dijkstra's Concurrent Programming Problem", Communications of the ACM 17(8), 1974, pp. 453–455. DOI: 10.1145/361082.361093. —— 本文对象：门口与号码、重叠读可任意、先来先服务的 \(N\) 机互斥。
• E. W. Dijkstra, "Solution of a Problem in Concurrent Programming Control", Communications of the ACM 8(9), 1965, p. 569. DOI: 10.1145/365559.365617. —— 原问题与共享变量解；本页标明其 \(k\) 是单点故障，且未证明先来先服务。
• Donald E. Knuth, "Additional Comments on a Problem in Concurrent Programming Control", Communications of the ACM 9(5), 1966, p. 321. DOI: 10.1145/355592.365595. —— 指出 1965 年解的个体可被无限超过；本页邻居，不是封面。
• N. G. de Bruijn, "Additional Comments on a Problem in Concurrent Programming Control", Communications of the ACM 10(3), 1967, pp. 137–138. DOI: 10.1145/363162.363167. —— 对等待上界的后续评论，仍属围着共享控制变量打转的邻居。
• M. A. Eisenberg and M. R. McGuire, "Further Comments on Dijkstra's Concurrent Programming Control Problem", Communications of the ACM 15(11), 1972, p. 999. DOI: 10.1145/355606.361895. —— 本页开篇点名的又一先前解。
• E. W. Dijkstra, "The Structure of the 'THE'-Multiprogramming System", Communications of the ACM 11(5), 1968, pp. 341–346. DOI: 10.1145/363095.363143. —— 本页当作信号量对照的来源；依赖单一硬件，封面不是面包店。
• G. L. Peterson, "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3), 1981, pp. 115–116. DOI: 10.1016/0020-0190(81)90106-7. —— 两进程旗与 \(TURN\)，用以标明人数、变量与年份都不是本页。
• Leslie Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE Transactions on Computers C-28(9), 1979, pp. 690–691. DOI: 10.1109/TC.1979.1675439. —— 顺序一致性，用以标明本页连「读须看见某次写」都不要求。
• Maurice Herlihy, "Wait-Free Synchronization", ACM Transactions on Programming Languages and Systems 13(1), 1991, pp. 124–149. DOI: 10.1145/114005.102808. —— 等待自由与共识数，用以标明带票号的互斥仍落在该尺的反面。

延伸阅读#

• 与 Dijkstra 1965 对读：把 \(b/c\) 数组与整数 \(k\) 留在那一页；本页问的是没有中央 \(k\)、读可以任意时能否加上先来先服务。
• 与 Peterson 1981 对读：两人三枚变量是后至短注；不要把门口与号码听成旗与 \(TURN\)。
• 与 并发 对读：总览里的锁与死锁是教学装置；本页停在弱寄存器合同上。
• 与 艾兹格·迪科斯彻 对读：信号量、THE 与 EWD 123 是邻居，不是封面。
• 与 1978 时钟 对读：先于关系需要消息；本页只有各台自己的字。
• 与 顺序一致性 对读：先写后读的外观是后文；本页连干净的读都不要求。
• 与 等待自由 对读：票号上的公平，并不能升格成停机也挡不住我。
• 与 莱斯利·兰波特 对读：人物页上的面包店一节是线索；装置与断言以本页为准。