Lecture 14: Distributed Mutual Exclusion — 分布式互斥算法
Lecture 14: Distributed Mutual Exclusion — 分布式互斥算法
讲义对应：CS 425 FA2026 Lecture 16（本笔记第 14 章）。对应 FA25 讲义
L18.FA25.txt：Lecture 18: Mutual Exclusion（56 页，Final 版）。 教材对应：Coulouris, Dollimore, Kindberg & Blair, Distributed Systems 5th Ed. Ch. 15（Coordination and Agreement，§15.2 Mutual Exclusion）；原始论文：G. Ricart & A. K. Agrawala, An Optimal Algorithm for Mutual Exclusion in Computer Networks, ACM TOCS 1981；M. Maekawa, A $\sqrt{N}$ Algorithm for Mutual Exclusion in Decentralized Systems, IEEE Trans. Computers 1985；K. Raymond, A Tree-Based Algorithm for Distributed Mutual Exclusion, ACM TOCS 1989。 前置知识：Lecture 12（Time and Ordering：happens-before、Lamport 时间戳、逻辑时钟的收发规则）；Lecture 11（Leader Election，集中式算法需要先选出协调者）。 阅读材料：Chubby 论文（Burrows, The Chubby Lock Service for Loosely-Coupled Distributed Systems, OSDI 2006）；Apache ZooKeeper 与 etcd 的锁原语文档；Martin Kleppmann, How to do distributed locking（关于 Redlock 的争论）。
14.1 概述
分布式互斥（Distributed Mutual Exclusion）要解决的问题只有一句话：在没有共享内存、只用消息传递的系统中，重建”单机互斥锁”的语义——确保任意时刻最多一个进程执行某段被称为临界区（Critical Section, CS）的代码。它之所以是分布式系统最基础的问题，是因为一切”读—改—写”都被它保护：银行账户余额、文件与目录锁、元数据、分片的主副本指派、工作划分的边界，等等。
本讲的骨架是四个经典算法：集中式（Central Server）、环式（Ring-based / Token Ring）、Ricart-Agrawala（Lamport 时间戳 + 请求-回复）、Maekawa（投票集 / quorum），再加上作为对比的树形令牌算法（Raymond）与基于序列号的令牌算法（Suzuki-Kasami）。它们共用同一套评价坐标：安全性、活性、公平性，以及消息复杂度、客户端延迟、同步延迟、容错性。学完本章你应该能一眼看出一句”这个算法用中心队列 / 用一个令牌 / 用时间戳全序 / 用两次 quorum 相交来打破争用”，并且能独立写出正确性证明——证明才是本讲的灵魂。
14.2 核心概念与分布式机制图解
14.2.1 临界区与临界区问题（Critical Section Problem）
- 定义与目的：临界区是在每个进程上都存在的一段代码（例如”读余额—加金额—写余额”），互斥算法要保证任意时刻最多一个进程在执行它。进程通过三个接口使用它：
enter(S)申请进入，AccessResource()执行临界区代码本身，exit(S)离开并释放。 - 直观解释（”它是什么？”）：合租房里只有一个厕所，门上有一把锁。
enter(S)就是去拿钥匙，AccessResource()是在里面办正事，exit(S)是把钥匙挂回墙上。互斥的全部难点在于：这把”钥匙”必须由消息来传递，而不是由一段可以被所有线程读写的共享内存来传递。 - 机制图解（银行账户的丢失更新）：
ATM1 银行服务器 (amount) ATM2
│ │ │
│──────────────read()───────────────►│ → 返回 1000 │
│ │◄─────────────read()────────────────│ → 返回 1000
│ 本地：1000 + 10000 = 11000 │ │ 本地：1000 + 10000 = 11000
│───────────write(11000)────────────►│ → 服务器 = 11000 │
│ │◄──────────write(11000)─────────────│ → 服务器 = 11000（覆盖上一次）
两个 ATM 都读到 1000，各自加 10000 后写回：客户存了 20000，账户里只剩 11000。
根因：两次"读—改—写"交错执行，后写覆盖了先写。
两段代码必须被互斥地执行：
ATM1: enter(S); ATM2: enter(S);
amount ← read(); amount ← read();
amount ← amount + deposit; amount ← amount + deposit;
write(amount); write(amount);
exit(S); exit(S);
有了互斥，两次存款会被串行化：第二次读到的是 11000，最终 21000。
- 关键假设与系统模型：单机系统中，
wait(S)/signal(S)的原子性由硬件指令（compare-and-swap、test-and-set）在同一块内存上保证；分布式系统中不存在这样一块内存，这正是问题变难的根本原因。
补充说明（单机对照）：单机信号量 $S=1$ 的 wait(S) 是”自旋直到 $S>0$ 再 $S\text{–}$”，每次循环体与 S++ 都由硬件保证原子。它之所以不能直接搬到分布式系统：$S$ 是一个共享变量，而”共享”在分布式系统里恰恰是我们要用算法去构造的东西。
14.2.2 为什么单机方案失效：从信号量到消息传递
- 定义与目的：本小节要建立”必须发明新算法”的必要性论证。
- 直观解释：单机互斥依赖三样东西：(1) 一块所有进程都能访问的共享内存；(2) 硬件提供的原子指令；(3) 一个全局统一的”现在”（内存序）。分布式系统三者全无：进程各自有内存，只有消息能跨越边界，网络延迟不可预测，时钟不同步。
- 机制图解（两个层次的能力对照）：
单机：有共享变量 + 硬件原子指令 分布式：只有消息，没有共享内存
┌────────────────────────────────────────┐ ┌────────────────────────────────────────┐
│ P1 ──┐ │ │ P1 ──消息──► P2 │
│ P2 ──┼──► [共享变量 S] │ │ P2 ──消息──► P3 │
│ P3 ──┘ ▲ │ │ P3 ──消息──► P1 │
│ compare-and-swap / test-and-set│ │ 互斥只能由"消息协议"实现 │
└────────────────────────────────────────┘ └────────────────────────────────────────┘
- 关键结论：分布式互斥算法的正确性完全来自协议本身（谁在什么条件下回复、谁在什么条件下延迟），没有任何硬件可以兜底。因此后续每个算法都必须给出安全性证明，而不能说”因为它是原子操作”。
14.2.3 三条必须满足的性质：安全性、活性、公平性
这是本章的评判标准：后面所有算法的优劣，都是相对这三条性质与三个性能指标而言的。
性质 1：安全性 / 互斥（Safety / Mutual Exclusion）——必需，绝对不能违反
\[\text{在任何时刻，处于临界区内的进程数} \le 1\]违反安全性的后果是数据损坏（银行例子丢钱），而且往往不可恢复。安全性是”坏事情永远不发生”（safety property）的典型：它要求算法在所有可能的交织（interleaving）下都成立，不能靠”实际很少同时发生”来辩护。
性质 2：活性 / 进展（Liveness / Progress）——必需
\[\text{若临界区空闲（无人持有），则任何提出请求的进程最终都能进入临界区}\]更精确的表述是两条：(a) 无死锁：若在某时刻之后没有进程持有临界区，那么某个请求者最终会进入；(b) 无饥饿：任何一次具体的 enter() 调用最终都会被满足。违反活性的后果是系统停滞：所有进程都在等，却谁也不能前进。
性质 3：公平性 / 顺序性（Fairness / Ordering）——期望，非必需
讲义把它列为”desirable（期望）”性质。最常用的定义是基于 happens-before 序：
\[\text{若 } \text{request}(P_i) \rightarrow \text{request}(P_j) \text{（前者因果先于后者），则 } P_j \text{ 不能先于 } P_i \text{ 进入临界区}\]即”先到先服务”的分布式版本。它比”无饥饿”更强：无饥饿只要求每个请求最终被满足，而公平性还规定了被满足的顺序。当一个算法的公平性只能做到”无饥饿”时，我们常说它只有弱公平性——这正是 Maekawa 算法最著名的软肋。
- 机制图解（三条性质的分工）：
┌──────────────────────────────────────────────────────────────────────────────┐
│ 安全性 Safety ：至多一个进程在 CS 违反 ⇒ 数据损坏（必须） │
│ 活性 Liveness ：请求最终被授予 违反 ⇒ 死锁 / 饥饿（必须） │
│ 公平性 Fairness：按 happens-before 授予 违反 ⇒ 插队（期望，非必需） │
│ │
│ 四种"打破争用"的机制：中央队列 │ 唯一令牌 │ 时间戳全序 │ 两个 quorum 必相交 │
└──────────────────────────────────────────────────────────────────────────────┘
- 关键假设：性质 2 中的”最终”是无故障假设下的”最终”；一旦允许崩溃，集中式与 Ricart-Agrawala 都可能永久阻塞（见 14.5 的容错讨论）。
14.2.4 三个评价指标
- 定义与目的：用统一指标横向比较算法，避免”感觉更快”。
| 指标 | 英文 | 精确定义 | 典型最优值 |
|---|---|---|---|
| 消息复杂度（带宽） | Bandwidth / Message complexity | 每次 enter()+exit() 全过程在系统中发送的消息总数，重点看它随进程数 $N$ 的增长阶 | 集中式：3 条（与 $N$ 无关） |
| 客户端延迟 | Client delay | 从发出 enter() 到真正进入临界区的延迟（无争用时测量） | 1 个 RTT |
| 同步延迟 | Synchronization delay | 一个进程 exit() 到下一个进程进入临界区之间的时间间隔（只有一个等待者时测量） | 1 个消息传输时间 |
- 直观解释：消息复杂度衡量”要花多少钱“（带宽/能耗），客户端延迟衡量”单个请求者等多久“，同步延迟衡量”临界区这把钥匙交接得多快“。三个指标互相制衡：集中式的消息数最少但有单点；环式的中心化程度最低但延迟 $O(N)$；Ricart-Agrawala 把延迟压到 $O(1)$ 却把消息数抬到 $O(N)$。
- 还要额外记录两个维度：(a) 是否需要在
exit()时也发消息——集中式与 Maekawa 需要（RELEASE），环式与 RA 的”退出”由令牌传递或延迟队列的 REPLY 顺带完成；(b) 容错性——能容忍几个进程崩溃、是否需要故障检测与恢复。 - 机制图解（三个指标在时间轴上的位置）：
P_i: enter() ────等待 REPLY────────►进入 CS exit()
│◄───客户端延迟────────────────►│
P_j: │─同步延迟────►enter()
客户端延迟：「发出 enter()」→「真正进入 CS」的时长（无争用时测量，通常是 1 个 RTT）。
同步延迟 ：「上一个进程 exit()」→「下一个进程进入 CS」的时长（只有一个等待者时测量）。
14.2.5 系统模型与假设（本讲所有算法共用）
- 固定假设（先声明模型，再解问题）：
- 异步系统：没有全局时钟，消息延迟无上界（但有限），不能假设”超时 = 故障”作为正确性依据。
- 可靠 FIFO 通道：每对进程之间有类似 TCP 的通道，消息最终送达且按发送顺序送达，不重复、不丢失。
- crash-stop 故障模型之外：基础版本假设进程不失败（讲义明确写 “Processes do not fail”）；容错变体存在于文献中。
- 无共享内存、无共享时钟；每个进程有唯一 ID；进程数 $N$ 已知；进程知道彼此的身份（可以直接一对一发送）。
- 临界区执行时间有限：每个进入临界区的进程最终都会
exit()。
- 为什么这些假设很重要：安全性证明的每一步都在用它们。例如”消息最终送达 + FIFO”保证了 RA 中”每个请求最终被所有进程看到”；”进程不失败”保证了集中式的队列一定有人来取、”环式”的令牌一定绕回来。放宽任何一条，就需要引入新的机制（超时、确认、故障检测、成员变更、共识），这正是第 14.5 节”现代系统为什么改用共识”的伏笔。
14.2.6 两大类算法：许可型 vs 令牌型
- 定义与目的：
- 许可型（Permission-based）：进程想进入临界区时，必须向一组进程请求许可并收集到足够的许可才能进入；许可的授予是”一次性”的，持有许可者有义务在适当时机归还（RA 用延迟回复隐含归还，Maekawa 用 RELEASE 显式归还）。代表：集中式、Ricart-Agrawala、Maekawa、Lamport 的分布式队列算法。
- 令牌型（Token-based）：系统中只有一个令牌（token），持有令牌即有权进入临界区；进程之间只传递令牌，不需要收集许可。代表：环式令牌、Raymond 树形、Suzuki-Kasami。
- 直观解释：许可型像是”开会前逐个打电话确认所有人都同意“，令牌型像是”只有一把钥匙的会议室，谁拿着钥匙谁就能进去“。前者的代价是每次开会都要打一圈电话，好处是”公平且能表达优先级”；后者的代价是钥匙必须靠接力传递，好处是”如果大家频繁开会，钥匙一直在传，几乎不用额外通信”。
- 机制图解（集中式 vs 环式的结构对比）：
集中式（Central Server） 环式（Ring-based / Token Ring）
┌──────────────────────────────┐ ┌─────────令牌─────── ┐
│ Leader / 协调者 │ ▼ │
│ 等待队列: P2, P3 │ ┌──────┐ ──────► ┌──────┐
│ 令牌 : 空闲 / 已借出 │ │ P0 │ │ P1 │
└──┬──────────┬──────────┬────┘ └──────┘ └──────┘
│ REQUEST │ REQUEST │ REQUEST ▲ │
▼ ▼ ▼ │ ▼
P0 P1 P2 ┌──────┐ ◄────── ┌──────┐
│ P3 │ │ P2 │
优点：3 条消息/次、FIFO 公平 └──────┘ └──────┘
缺点：单点故障 + 性能瓶颈
优点：无中心、每跳仅 1 条消息
缺点：延迟 0~N；令牌丢失需再生
- 关键假设：两类都用同一套系统模型；令牌型额外要求”令牌唯一性“这一全局不变式在任何时刻都成立（路由/再生协议必须维护它）。
14.2.7 三状态状态机与 Lamport 时间戳全序
（1）三状态状态机（RELEASED / WANTED / HELD）
Ricart-Agrawala 与 Maekawa 都用同一个本地状态机描述进程对临界区的”态度”，这是读伪代码时最重要的心智模型：
enter()：clock+1，my_ts ← clock，向全体（或投票集）发 REQUEST
│
▼
┌──────────────────────┐ ┌────────────────────────┐ ┌────────────────────┐
│ RELEASED │ ────收齐 N-1 个 REPLY─►│ WANTED │ ─────收齐全部 REPLY─►│ HELD │
│ 我不在 CS，也不排队 │ │ 请求已发出，等 REPLY │ │ 正在执行临界区 │
└──────────────────────┘ └────────────────────────┘ └────────────────────┘
▲ │
│ exit()：state ← RELEASED；回复 deferred 队列中每个请求 / 向投票集发 RELEASE │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
（RELEASED / WANTED / HELD 恰好穷尽安全性证明要讨论的三种情形；WANTED 期间 my_ts 不变。）
（2）Lamport 时间戳与全序（回顾 Lecture 12）
- 每个进程维护计数器 $C_i$（初值 0）。发送/本地事件时 $C_i \leftarrow C_i + 1$，事件时间戳取新的 $C_i$；收到消息时 $C_i \leftarrow \max(C_i, \text{消息时间戳}) + 1$。
- 由三条 happens-before 规则（同进程顺序、发送→接收、传递性），得到保证：$a \rightarrow b \Rightarrow T(a) < T(b)$。反之不成立：$T(a)<T(b)$ 不能推出 $a \rightarrow b$（可能是并发事件）。
- 关键推论（本讲两个算法都靠它）：Lamport 时间戳没有唯一性——两个并发事件的计数器可以取到相同的值（例如两个进程各自从 0 出发同时请求，都得 $T=1$）。用词典序$(T, i)$ 比较，其中 $i$ 是进程 ID，就得到一个全序（total order）：
这个全序是所有进程都能独立算出同一个结果的（因为 $T$ 随消息传播、ID 是常量），因此它可以在无中心的前提下充当”裁决者”。“唯一性 + 全局一致”这两点，正是打破循环等待的死锁避免机制。
14.3 算法伪代码与正确性分析
算法 14.3.1：集中式算法（Central Server / Coordinator）
假设与系统模型
- 异步系统；可靠 FIFO 通道；进程不失败（协调者也不失败）；存在一个通过选举算法（见 Lecture 11）选出的唯一协调者（Leader）；$N$ 个客户端进程，协调者自己不使用临界区。
- 协调者维护：一个 FIFO 等待队列
queue、一个布尔量token_free（等价于讲义的”协调者是否持有令牌”）。
伪代码
常量: Leader = 由选举算法选出的协调者；N = 进程数
-- 协调者状态 --
queue ← 空 FIFO 队列 -- 等待进入 CS 的进程
token_free ← true -- true 表示"临界区空闲，可以立刻授予"
-- 客户端进程 P_i --
upon event <enter(S)>: -- 想进入临界区
send REQUEST(i) to Leader
wait until receive GRANT from Leader -- 阻塞直到拿到令牌
state ← HELD
AccessResource()
upon event <exit(S)>: -- 离开临界区
state ← RELEASED
send RELEASE(i) to Leader -- 把令牌还给协调者
-- 协调者 --
upon receiving REQUEST(i) from P_i:
if token_free = true: -- 临界区空闲
token_free ← false
send GRANT to P_i -- 立刻授予（令牌发出）
else: -- 已有人在 CS 或令牌在路上
queue.append(i) -- 排队（FIFO）
upon receiving RELEASE(i) from P_i:
if queue ≠ ∅:
j ← queue.popleft() -- 队首下一个
send GRANT to P_j -- 令牌直接转交，token_free 仍为 false
else:
token_free ← true -- 收回令牌，保持在协调者手中
算法逻辑解说（$N=3$ 的数值小例子）
- $P_0,P_1,P_2$ 同时
enter()，各自向 Leader 发REQUEST（3 条消息）。 - Leader 收到 $P_0$ 的请求时
token_free = true，于是置false并发送GRANT（第 4 条消息）；收到 $P_1,P_2$ 的请求时令牌已借出，把它们依次入队（顺序由 FIFO 通道决定，这里假设 $P_1$ 在前）。 - $P_0$ 收到
GRANT，进入临界区，执行完发RELEASE（第 5 条）给 Leader。 - Leader 收到
RELEASE，从队首取出 $P_1$，直接发GRANT（第 6 条）。$P_1$ 进入，退出后RELEASE（第 7 条）→ Leader 发GRANT给 $P_2$（第 8 条）→ $P_2$ 退出后RELEASE（第 9 条）。 - 总计 $3N=9$ 条消息：每次”进入临界区”恰好
REQUEST + GRANT + RELEASE = 3条，与 $N$ 无关。
正确性论证
安全性（互斥）：依赖”令牌唯一性”这一不变式。证明用不变式法：初始时 token_free = true 且没有任何进程持有令牌，”系统中的令牌数 = 1”成立。检查所有可能改变状态的事件：
- 协调者收到
REQUEST且token_free = true：令牌从协调者转移到 $P_i$，令牌数仍为 1（协调者不再持有）。 - 协调者收到
REQUEST且token_free = false：不发送任何令牌，令牌数不变。 - 协调者收到
RELEASE且有等待者：令牌从 $P_i$ 转移到 $P_j$，令牌数不变；无等待者时令牌回到协调者，令牌数不变。 因此”令牌数恒为 1”始终成立。而客户端只有在收到GRANT之后才会执行AccessResource()，所以进入临界区的进程必然是当前令牌持有者；令牌唯一 $\Rightarrow$ 至多一个进程在临界区。$\blacksquare$
活性（进展）：
- 若临界区空闲（令牌在 Leader 手中），任何到达的
REQUEST都会立即被满足（走第一条分支）。 - 若令牌被 $P_k$ 持有，$P_k$ 依假设最终
exit()（临界区执行时间有限），发出RELEASE；通道可靠最终送达。 - Leader 收到
RELEASE时若队列非空，必然取出队首并授予；由于每次enter()只入队一次、RELEASE恰好触发一次出队，且队列是 FIFO，一个进程前面最多有 $N-1$ 个进程，因此每个请求最多被 $N-1$ 个临界区访问”挡”在前面，最终都会被授予。无故障假设下不会死锁，也不会饥饿。$\blacksquare$
公平性：请求被授予的顺序恰好是 Leader 收到请求的顺序（单队列 FIFO）。若 $\text{request}(P_i) \rightarrow \text{request}(P_j)$，则 $P_i$ 的请求在因果上先于 $P_j$ 的请求发出；由于请求沿 FIFO 通道到达 Leader，Leader 不会先收到 $P_j$ 的请求（除非两者并发——并发的请求之间的顺序本来就无因果约束），所以 $P_i$ 先入队、先出队、先进入临界区。集中式算法满足基于 happens-before 的公平性。$\blacksquare$
缺陷：Leader 是单点故障（SPoF）（崩溃则全系统无法进入临界区）也是性能瓶颈（吞吐量上限 = 协调者处理能力；所有消息都要经过它）；客户端延迟为 REQUEST+GRANT 两跳 $\approx$ 1 RTT；同步延迟为 RELEASE+GRANT 两跳 $=2$ 个消息传输延迟（比 RA 和环式都差）。另外它还引入了”选举 + 成员管理”的额外复杂度（见 Lecture 11）。
复杂度
| 维度 | 结果 |
|---|---|
| 消息复杂度 | 3 条/次进入（REQUEST+GRANT+RELEASE），与 $N$ 无关——所有算法中消息数最少 |
| 客户端延迟 | 2 个消息延迟（$\approx$ 1 RTT） |
| 同步延迟 | 2 个消息延迟（RELEASE + GRANT） |
| 空间复杂度 | 协调者 $O(N)$（队列），客户端 $O(1)$ |
| 容错 | 差：不允许任何进程失败；Leader 崩溃需要重新选举 + 状态恢复 |
算法 14.3.2：环式令牌算法（Ring-Based / Token Ring）
假设与系统模型
- 同 14.2.5；额外假设 $N$ 个进程逻辑上组成一个单向环，每个进程只与后继（successor）有通道；系统中有且仅有一个令牌；初始令牌唯一性由一个令牌再生协议保证（见下文缺陷部分）。
伪代码
初始: 恰好一个进程满足 token_here = true（由令牌初始化/再生协议保证）；
ring_succ(i) = (i + 1) mod N；每个进程 waiting ← false
-- 进程 P_i --
upon event <enter(S)>: -- 想进入临界区
waiting ← true
while token_here = false:
wait -- 等令牌沿环转到我这里
-- 此刻持有令牌 ⇒ 有权进入
waiting ← false
state ← HELD
AccessResource()
upon event <exit(S)>: -- 令牌已在手，直接传走
state ← RELEASED
token_here ← false
send TOKEN to ring_succ(i)
upon receiving TOKEN from ring_pred(i):
token_here ← true
if waiting = false: -- 我不需要进入 CS
token_here ← false -- 不做停留
send TOKEN to ring_succ(i) -- 立刻转发给后继
-- 若 waiting = true，则本进程继续执行上面的 enter() 循环体
算法逻辑解说
- 令牌按固定方向（$P_0 \to P_1 \to \cdots \to P_{N-1} \to P_0$）无限循环。
- 进程只有拿到令牌才能进入临界区；不需要进入的进程只是”中转站”，收到令牌后立即转发（仍然消耗 1 条消息）。
- 想进入的进程把
waiting置位，然后等令牌转过来；进入前后都不需要额外的请求或释放消息——”释放”就是”把令牌传给后继”这一动作本身。 - 数值例子（$N=4$，令牌初始在 $P_0$，$P_2$ 之后想进入）：$P_0$ 不想用则转发给 $P_1$（1 条消息），$P_1$ 转发给 $P_2$（1 条），$P_2$ 持有令牌进入临界区；退出时传给 $P_3$（1 条）。$P_2$ 的客户端延迟 = 2 个消息传输时间。
正确性论证
安全性（互斥）：依赖”环中恰好一个令牌”。这由两条保证：(i) 无复制——令牌只在 send TOKEN 时被转移，发送者立即置 token_here ← false，即”先交出后失权”，任何进程都不会在自己仍持有令牌的情况下又收到一个令牌（可靠 FIFO 通道保证不重复、不乱序）；(ii) 不新增——算法中没有任何”创建令牌”的动作（令牌再生协议是唯一的例外，它必须保证在旧令牌确实不存在的前提下才创建）。因此令牌数守恒且为 1。而进程进入临界区的唯一条件是 token_here = true，故至多一个进程在临界区。$\blacksquare$
活性（进展）：若某进程 waiting = true，令牌沿环持续单向传递：持有令牌的进程若不进入临界区就立即转发；若进入临界区则依假设最终 exit() 并转发。环是强连通的（$N$ 跳覆盖所有进程），因此令牌最多 $N-1$ 跳必然到达该等待者。无故障假设下无死锁。$\blacksquare$
公平性：令牌单向传递 ⇒ 等待请求被服务的顺序是”令牌到达的先后”，即近似 FIFO（”近似”是因为请求的发起时刻与令牌位置无关：一个晚发出的请求可能因为令牌恰好即将到达而先被满足）。它不满足严格的 happens-before 公平性，但满足无饥饿。$\blacksquare$
缺陷：
- 令牌丢失（持有者崩溃）⇒ 必须运行令牌再生协议（例如：检测到令牌长时间缺席后，由某个确定规则选出的进程重新生成令牌——难点在于”旧令牌真的不存在了”不可判定，需要超时+优先级+确认，且必须保证不会出现两个令牌）。
- 对环的拓扑敏感：任何一个进程崩溃都会断环（后继收不到令牌），必须重建逻辑环。
- 最坏延迟 $O(N)$：刚把令牌传给后继的进程要等整整一圈。
复杂度
| 维度 | 结果 |
|---|---|
| 消息复杂度 | 每次进入 1 条（请求者本身发送令牌的动作），但整个系统为此可能传递最多 $N$ 条；平均 $N/2$。总消息数与 $N$ 成线性关系 |
| 客户端延迟 | 0 到 $N$ 个消息传输：最好情况是”刚拿到令牌”，最坏是”刚把令牌传给后继” |
| 同步延迟 | 1 到 $N-1$ 个消息传输：最好情况是后继想要进入（1 跳），最坏是前驱想要进入（$N-1$ 跳） |
| 空间复杂度 | $O(1)$（每进程只需 waiting、token_here） |
| 容错 | 中：无中心，但需令牌再生 + 环重建；库/框架中通常配合成员管理 |
算法 14.3.3：Ricart-Agrawala 算法（本章最重要的算法）
假设与系统模型
- 异步系统；每对进程之间存在可靠 FIFO 通道；进程不失败；$N$ 个进程各有唯一 ID；无令牌、无中心；使用 Lamport 时间戳（不需要物理时钟同步）。文献中记为 Ricart & Agrawala (1981)。
核心思想：“请求-回复” + “时间戳优先级”。想要进入的进程向所有其他 $N-1$ 个进程发出 REQUEST（带自己的 Lamport 时间戳），并收齐所有 REPLY 后才能进入；每个收到请求的进程独立地按时间戳全序决定”立刻回复”还是”先欠着（延迟回复）”。因为所有进程用同一个全序裁决，不可能出现循环等待。
机制图解：三进程的消息交互时序图（用讲义的例子；★ 标出两条关键路径）
N32 (T=102) N80 (T=110) N12 (T=115)
│ │ │
t1 │──────REQUEST(102,32) ★───────►│ │ ① N32 广播请求
│───────────────────────REQUEST(102,32)────────────────────────►│
t1 │◄──────REQUEST(110,80)─────────│ │ ② N80、N12 也广播请求
│ │───────REQUEST(110,80)────────►│
t1 │◄──────────────────────REQUEST(115,12)─────────────────────────│
│ │◄──────REQUEST(115,12)─────────│
│ │ │
t2 │◄──────REPLY(110,80) ★─────────│ │ ③ 让路：立即 REPLY，
t2 │◄───────────────────────REPLY(115,12)──────────────────────────│ 同时确保对方知道
t2 │ │◄───────REPLY(115,12)──────────│ "我也在等"（★ 路径）
t2 │ ← N32 把 (110,80)、(115,12) 都放进 deferred │ ④ 延迟回复（★ 路径）
│ │ │
t3 │────────REPLY(110,80)─────────►│ │ ⑤ N32 退出 CS，才还债
t3 │────────────────────────REPLY(115,12)─────────────────────────►│
t3 │ │ ← N80 收齐 REPLY，进入 CS │
│ │ │
t4 │ │────────REPLY(115,12)─────────►│ ⑥ N80 退出后 N12 才进入
t4 │ │ │ ← N12 收齐 REPLY，进入 CS
两条关键路径：
★ 延迟回复（deferred）路径：优先级更高的一方"欠着" REPLY，直到自己退出临界区才回复 —— 这是
许可的归还通道，也是【为什么不需要 RELEASE 消息】的答案（见关键细节 3）。
★ "把请求也发给对方"路径：在"让路"分支里，回复者必须确保对方知道自己仍处于 WANTED —— 标准
广播版由 ① 的 multicast 天然满足；任何"定向 / 懒发送"优化都必须显式补发，否则破坏不变式 I。
最终进入顺序 N32 → N80 → N12 恰好等于时间戳全序 (102,32) < (110,80) < (115,12)。
伪代码（完整三状态状态机）
每个进程 P_i 维护:
clock : Lamport 逻辑时钟，初值 0
state : RELEASED | WANTED | HELD -- 初值 RELEASED
my_ts : 本进程当前这次请求的时间戳（WANTED 期间不得改变）
replies : 本次请求已收到的 REPLY 数量
deferred : 延迟回复队列，元素为 (T_j, j)，初值 ∅
-- ① enter()：发起请求 --
upon event <enter(S)>:
clock ← clock + 1
my_ts ← clock -- 得到请求时间戳 T_i
state ← WANTED
replies ← 0
for each P_j such that j ≠ i:
send REQUEST(my_ts, i) to P_j -- 向【所有】其他进程请求
wait until replies = N - 1 -- 收齐全部 REPLY 才能进入
state ← HELD
AccessResource()
-- ② 收到 REQUEST：按时间戳全序裁决（本算法的核心） --
upon receiving REQUEST(T_j, j) from P_j (j ≠ i):
clock ← max(clock, T_j) + 1 -- Lamport 接收规则
if state = HELD
or (state = WANTED and (my_ts, i) < (T_j, j)): -- 我优先级更高 / 我在 CS 中
deferred.append((T_j, j)) -- ★ 延迟回复（欠着）
if state = WANTED and (my_ts, i) < (T_j, j):
send REQUEST(my_ts, i) to P_j -- ★★ 让 P_j 知道"我也在等"
else: -- 我 RELEASED，或我在等但它优先级更高
send REPLY(T_j, i) to P_j -- 立刻回复：我让路
-- ③ 收到 REPLY --
upon receiving REPLY(T_j, j) from P_j:
clock ← max(clock, T_j) + 1
if state = WANTED and T_j = my_ts: -- 只统计"回答我本次请求"的 REPLY
replies ← replies + 1
-- ④ exit()：只回复被延迟的请求，不需要广播 RELEASE --
upon event <exit(S)>:
state ← RELEASED
for each (T_j, j) in deferred:
send REPLY(T_j, i) to P_j -- 现在"我还债"
deferred ← ∅
算法逻辑解说（用讲义里的数值例子走一遍）
设 $N=6$（$N_{32},N_{80},N_{12},N_5,N_6,N_3$），消息格式为 $\langle T, P_i\rangle$。上面的时序图是一种可能的交织，下面按讲义给出的另一种交织逐步走一遍——两者得到的进入顺序完全相同，这正是”算法不依赖具体时序”的体现：
时刻 谁 事件
----------------------------------------------------------------------------
t1 N32 clock+1 → T = 102；向 N5,N6,N3,N80,N12 广播 REQUEST<102,32>
t2 N32 收齐 5 个 REPLY ⇒ state = HELD，进入临界区
t3 N80 clock+1 → T = 110；广播 REQUEST<110,80>
t3 N12 clock+1 → T = 115；广播 REQUEST<115,12>
t4 N32 仍在 CS 中（state = HELD）⇒ 两个请求都进 deferred：
deferred = [<110,80>, <115,12>]
t4 N80 state = WANTED 且 (110,80) < (115,12) ⇒ 延迟回复，把 <115,12> 入队
t4 N12 state = WANTED 且 (115,12) > (110,80) ⇒ 立即 REPLY 给 N80（让路）
N12 自己的请求仍在等 N80 的 REPLY
t5 N32 exit() ⇒ state = RELEASED，对 deferred 中两个请求各回一个 REPLY
⇒ N80 收齐全部 5 个 REPLY ⇒ 进入 CS ✔（因为 (110,80) < (115,12)）
t6 N80 exit() ⇒ 回复 N12 的 <115,12> ⇒ N12 收齐 ⇒ 进入 CS
注意两件”看似绕”的事：N32 在临界区时把请求入队而不是立即回复（否则两个进程会同时进入）；N12 明明也想进入，却在收到优先级更高的 N80 的请求时立刻回复（让路，因为按全序应当 N80 先进入，N12 的请求会被 N80 在退出时回复）。最终顺序 $\langle102,32\rangle \to \langle110,80\rangle \to \langle115,12\rangle$，恰好是时间戳全序。
关键细节 1：为什么必须用 $(T_i, i)$ 而不是只比较 $T_i$
Lamport 时间戳不唯一：两个进程在同一时刻各自 enter()，时钟都从 0 加 1，于是 $T_i = T_j = 1$。若只用 $T$ 比较，判决规则 (my_ts < T_j) 在 $T_i = T_j$ 时两边都判”不小于”，于是两个进程都会立刻回复对方的请求 ⇒ 双方都收齐了 $N-1$ 个 REPLY ⇒ 同时进入临界区，安全性被违反。
加入进程 ID 做决胜（tie-break）后，$(T_i,i)$ 是全序：$T$ 相同时按 ID 比大小，双方得到同一个、且不一致的判决（一方”小于”、另一方”大于”），绝不会出现”互相让路”。全序是死锁避免与互斥的共同基础——这一点在第 14.4 节的代码里可以直接跑出违反互斥的日志（ra_bugs.py 的 notie 模式：审计变量立刻变成 2）。本讲反复强调的公式：
关键细节 2：为什么”也要把自己的请求发给 $P_i$”（学生最容易漏掉的一步）
这条规则背后是一个不变式：
不变式 I（双向知情）：任何处于
WANTED状态的进程，其请求最终会被其他所有 $N-1$ 个进程看到；并且任何”立刻回复了对方”的进程，都要确保对方知道自己仍在等待。
为什么它决定成败：RA 的延迟回复队列是许可的归还通道。$P_j$ 在 WANTED 时收到优先级更高的 $P_i$ 的请求，立刻回 REPLY 是”让路”；可是 $P_j$ 自己还在等 $P_i$ 的 REPLY（$P_i$ 正处于 WANTED/HELD，已经把 $P_j$ 的请求入队）。若 $P_i$ 根本不知道 $P_j$ 在等（请求没有到过 $P_i$），那么 $P_i$ 退出时的 deferred 队列里没有 $P_j$，它不会回 REPLY，$P_j$ 永远等不到——活性被破坏（饥饿/死锁）；更糟的变体里，$P_j$ 若同时认为”我既然让了路，就不必再等 $P_i$ 的许可”，它就会在 $P_i$ 仍在临界区时进入，直接破坏互斥。
反例（漏掉这一步的两种典型后果）。
反例 A：活性被破坏（$P_j$ 永远等不到 REPLY）。 设 $N=3$，$P_1$（$T=5$）与 $P_2$（$T=9$）都要进入，$P_3$ 不想进入。实现者做了一个”省消息”的优化：$P_i$ 变成 WANTED 时，只向还没有回复过自己的进程发 REQUEST（理由是”已经许可我的进程不用再打扰”），并且在”让路”分支里也不补发自己的请求：
P1 (T=5) P2 (T=9) P3
│ │ │
│─────────REQUEST(5,1)─────────►│ │
│─────────────────────────REQUEST(5,1)─────────────────────────►│ → REPLY
│◄────────REQUEST(9,2)──────────│ │
│ │─────────REQUEST(9,2)─────────►│ → REPLY
│ ③ P1 收到 REQUEST(9,2) │ │
④ P1 处理它：state = WANTED 且 (5,1) < (9,2) ⇒ 把 P2 的请求放进 deferred
⑤ P2 收到 REQUEST(5,1)：state = WANTED 且 (9,2) > (5,1) ⇒ 立刻 REPLY 给 P1
✗ 缺陷版在这里【没有】把自己的 REQUEST(9,2) 告知 P1（"省消息"版认为 P1 已经知道、
或认为自己已让路无需再等），于是 P1 的 deferred 队列中始终没有 P2
⑥ P1 收齐 REPLY 进入 CS ⇒ 退出时 deferred 为空 ⇒ 一条 REPLY 都不发
⇒ P2 永远等不到 P1 的 REPLY：活性被违反（P2 的请求永远不被授予）
反例 B：安全性被破坏（双方同时进入 CS）。 同样的场景，缺陷版让 $P_2$ 把”我已让路”进一步理解为”本轮不需要 $P_1$ 的许可”，于是把 $P_1$ 从自己的等待集合中划掉：$P_2$ 只需收齐 $N-2$ 个 REPLY 就认为自己可以进入。于是 $P_1$ 拿到 $P_2$ 的 REPLY 进入临界区，$P_2$ 也认为自己”已经收齐”而进入——两个进程同时在临界区。第 14.4 节的 ra_bugs.py 的 noannounce 模式把这条路径完整跑了出来：
t=0.001 P0 defer REQUEST(ts=1,P1) ← P0 把 P1 的请求入队（等 P1 的 REPLY）
t=0.001 P1 REPLY -> P0 ← P1 让路
t=0.003 P0 ENTER CS ← P0 收齐 REPLY 进入
t=0.003 P1 (bug) 认为无需 P0 的 REPLY ← 缺陷：不再等 P0 的 REPLY
t=0.003 P1 ENTER CS ← ❌ 两个进程同时在临界区
审计: 同一时刻最多 2 个进程在临界区 / ❌ 违反 SAFETY(互斥)
补充说明（严谨边界）：在教科书的标准表述——即”进程一旦 WANTED 就向全体 $N-1$ 个进程广播 REQUEST“——下，不变式 I 由最初的那次广播天然满足，因此”在让路分支里补发请求”只是冗余的一条重复消息，不会改变结果。它之所以被反复写进伪代码，是因为：(a) 它是”每个 WANTED 进程的请求必须到达所有进程”这一不变式的显式保护，任何”定向发送 / 懒发送 / 只问还没回复我的人”的优化都会立刻违反这个不变式；(b) 它使算法的正确性不依赖”广播确实发给了所有人”这一实现假设。记住结论：漏掉它是否出错，取决于你的实现是否仍满足不变式 I——这才是要检验的东西。
关键细节 3：为什么不需要 RELEASE 消息
集中式与 Maekawa 都需要显式 RELEASE，RA 不需要，原因在于许可的语义不同：
- RA 的
REPLY表达的是”我此刻不在临界区，且（若我也想要）你的优先级更高，我让你先“，这是一个不携带锁的承诺：回复者不会因此被”锁死”，也不需要在对方退出时被”解锁”。 - 真正需要等待的人已经被对方放进
deferred队列了：$P_i$ 若处于WANTED/HELD收到优先级更低的请求，就会入队，并在自己的exit()时回复。也就是说，“我释放了”这件事是通过”给队列里的请求回 REPLY”精确投递给需要知道的人的，而不是广播给所有人。REPLY同时充当了”释放通知”和”许可授予”两个角色。 - 反过来说，”没进队列的进程”根本不需要知道 $P_i$ 何时退出——它们的请求要么已经得到了
REPLY（在 $P_i$ 进入之前就回复过了），要么尚未发出。
正确性论证
安全性（互斥）：假设存在某个时刻 $P_i$ 与 $P_j$（$i \ne j$）同时处于临界区。
- $P_i$ 能进入，说明它在进入前收到了来自 $P_j$ 的
REPLY（它对 $P_i$ 的请求的回复）；同理 $P_j$ 收到了来自 $P_i$ 的REPLY。记两者的请求时间戳为 $(T_i,i)$ 与 $(T_j,j)$，由全序性，两种情况之一成立：$(T_i,i) < (T_j,j)$，或 $(T_j,j) < (T_i,i)$。不妨设 $(T_i,i) < (T_j,j)$（另一情况对称）。
安全性论证的时序图（为什么两者不可能同时收齐 REPLY）
P_i (T_i = 102) P_j (T_j = 115)
│ │
t1 │───────────REQUEST(102,i)───────────►│
t1 │◄──────────REQUEST(115,j)────────────│
裁决 │ 优先级更高 ⇒ 延迟回复 │ 优先级更低 ⇒ 立即 REPLY
t2 │◄────────────REPLY(115)──────────────│ P_j 的 REPLY 立刻到达，但——
t2 │ 收齐 REPLY ⇒ 进入 CS │ P_i 的 REPLY 被欠着，P_j 进不去
t3 │─────────────REPLY(102)─────────────►│ 只有 P_i 退出，P_j 才拿到 REPLY
t3 │ │ 收齐 REPLY ⇒ 进入 CS
结论：T 更小的一方必然把 T 更大的一方的请求放进 deferred，因此"后者的临界区区间"必然
整体晚于"前者的临界区区间" —— 两个区间不可能重叠，互斥成立。
- 考察 $P_j$ 处理 $P_i$ 的
REQUEST的那一刻（该请求依可靠通道必然送达，且在 $P_j$ 进入临界区之前就被处理过——否则 $P_j$ 无法收到它所需要的全部 REPLY 中的 $P_i$ 那一个）。此时 $P_j$ 的状态只有三种可能，逐一排除：- $P_j$ 处于
RELEASED：它当时不在临界区，会立即回复 $P_i$；并且由于它当时没有未决请求（RELEASED就是”不排队”），它自己的REQUEST必然是在处理 $P_i$ 的请求之后才发出的。由 $P_i$ 的请求抵达 $P_j$ 就因果先于 $P_j$ 的请求发出，Lamport 规则给出 $T_j \ge T_i + 1$，即 $T_i < T_j$——这与假设 $(T_i,i) < (T_j,j)$ 相容，因此这条分支不能用”互相回复不可能”直接排除，必须继续追下去：$P_j$ 要进入临界区，必须收齐全部 $N-1$ 个 REPLY，其中包括 $P_i$ 的 REPLY。而 $P_i$ 收到 $P_j$ 的请求时处于WANTED或HELD（它随后确实进入了临界区），并且 $(T_i,i) < (T_j,j)$ 成立，于是 $P_i$ 的条件为真，把 $P_j$ 的请求放入deferred队列，只在自己退出临界区之后才回复 $P_j$。因此 $P_j$ 的进入时刻必然晚于 $P_i$ 的退出时刻 ⇒ 二者不可能同时在临界区。 - $P_j$ 处于
WANTED：由假设 $(T_i,i) < (T_j,j)$，判决条件state = WANTED and (my_ts, j) < (T_i, i)为假（$(T_j,j)$ 不小于 $(T_i,i)$），故 $P_j$ 走else分支立即回复 $P_i$ 而不入队。但 $P_j$ 自己也在请求，它必须收齐包括 $P_i$ 在内的全部 REPLY；$P_i$ 收到 $(T_j,j)$ 时处于WANTED/HELD且 $(T_i,i)<(T_j,j)$ 为真 ⇒ 入队，直到 $P_i$ 退出才回复。于是 $P_j$ 的进入只能发生在 $P_i$ 退出之后 ⇒ 二者不同时在临界区。 - $P_j$ 处于
HELD：说明 $P_j$ 已经在处理 $P_i$ 的请求之前进入了临界区。$P_j$ 会把 $P_i$ 的请求入队，并在自己exit()时才回复；于是 $P_i$ 只能在 $P_j$ 退出之后收齐 REPLY，$P_i$ 的临界区区间整体晚于 $P_j$ 的临界区区间 ⇒ 二者不可能同时在临界区。 三种状态（恰好穷尽RELEASED/WANTED/HELD的全部可能）都被排除，因此 $(T_i,i) < (T_j,j)$ 与”两者同时在临界区”不相容；由全序性对称地排除 $(T_j,j) < (T_i,i)$。二者必居其一而又都不能成立 ⇒ 假设不成立，互斥成立。$\blacksquare$ 依赖的机制：时间戳全序（消除”互相回复”的可能）+ 延迟回复队列（把 REPLY 推迟到exit()之后）+ 可靠 FIFO 通道（保证请求/回复一定送达）。
- $P_j$ 处于
- 讲义还特别点出一个”看似反例”的情形：若 $(T_i,i) < (T_j,j)$，而 $P_i$ 是在”发出自己的请求之前”就回复了 $P_j$ 的请求呢？ 那么看起来两个进程都批准了对方。但这是不可能的：$P_i$ 回复 $P_j$ 的动作发生在 $P_i$ 发出自己请求之前，意味着 $\text{REQUEST}(P_j) \rightarrow \text{REPLY}(P_i) \rightarrow \text{REQUEST}(P_i)$，由 Lamport 时间戳的因果律得 $T_i > T_j$，与 $(T_i,i) < (T_j,j)$ 矛盾。所以这种情形根本不会出现。
活性（进展 + 无死锁 + 无饥饿）：用反证 + 时间戳全序的最小元。
- 假设存在死锁：在某个时刻之后，所有想进入临界区的进程都停在
WANTED且没有任何进程进入。设这些等待者集合为 $W \neq \emptyset$。 - 取 $W$ 中时间戳最小的请求者 $P_{m}$，即 $(T_m, m) = \min_{(T,i)\in W}(T_i,i)$。这个最小值存在且唯一（全序）。
- 考虑 $P_m$ 需要的 $N-1$ 个 REPLY。对任意其他进程 $P_k$：
- 若 $P_k \notin W$（不想进入 / 已在
RELEASED且无请求）：$P_k$ 收到 $P_m$ 的请求时状态为RELEASED，判决条件为假 ⇒ 立即回复。 - 若 $P_k \in W$（也在等待）：$P_k$ 处于
WANTED，且由最小性 $(T_m,m) < (T_k,k)$，判决条件state = WANTED and (my_ts,k) < (T_m,m)为假（$T_k > T_m$）⇒ 立即回复。 - 若 $P_k$ 正处于
HELD：依假设”临界区执行时间有限”，$P_k$ 最终exit()，在exit()中把deferred里的请求（其中包含 $P_m$ 的）全部回复。 于是 $P_m$ 必然收齐全部 $N-1$ 个 REPLY，进入临界区——与”没有进程进入”矛盾。故不会死锁。
- 若 $P_k \notin W$（不想进入 / 已在
- 无饥饿：同样的论证逐次应用即可。每次进入临界区的进程是”当前所有等待者中时间戳最小者”（第 3 步证明它必然能进入），因此等待者的集合随着一次次的”最小元被服务”而单调缩小，任何请求者排在自己前面的只有那些时间戳更小的请求，数量有限（每个进程同时最多只有一个未决请求），故每个请求最终都被授予。$\blacksquare$ 依赖的机制：时间戳全序提供的”最小元” + 所有等待者都会立即回复更大的时间戳——这就是”用全序打破循环等待”的经典论证。注意它依赖”进程不失败”：若某个进程崩溃永不回复，$P_m$ 就永远收不齐 REPLY。
公平性：请求按 Lamport 时间戳全序被授予。若 $\text{request}(P_i) \rightarrow \text{request}(P_j)$，则由 Lamport 时钟的因果性质 $T_i < T_j$，于是 $(T_i,i) < (T_j,j)$：在第 3 步的论证中 $P_j$ 属于”会立即回复 $P_i$”的一方，而 $P_i$ 会把 $P_j$ 的请求入队到退出后再回复。因此 $P_i$ 必然先于 $P_j$ 进入临界区——RA 满足基于 happens-before 的公平性（比”无饥饿”更强）。$\blacksquare$
复杂度
| 维度 | 结果 | 说明 |
|---|---|---|
| 消息复杂度 | $2(N-1)$ 条/次进入 | $N-1$ 条 REQUEST + $N-1$ 条 REPLY；若底层支持组播则为 $N$ 条（1 条 multicast + $N-1$ 条单播 REPLY） |
| 退出消息 | 最坏 $N-1$ 条 REPLY（只发给 deferred 队列成员，不是广播） | 讲义记账为”每次 exit() $N-1$ 条单播 / 1 条 multicast” |
| 客户端延迟 | 1 个 RTT | 发出请求到收齐回复 |
| 同步延迟 | 1 个消息传输时间 | 退出者的 REPLY 到达下一个进程即进入——比集中式（2）与环式（$1\sim N-1$）都优 |
| 空间复杂度 | 每进程 $O(N)$（deferred 最坏 $N-1$ 项），系统中 $O(N^2)$ 潜在状态 | |
| 容错 | 差：任何一个进程崩溃 ⇒ 所有需要它 REPLY 的进程永久阻塞（$N-1$ 个进程失败则完全瘫痪） | 需超时+故障检测+成员变更才能容错 |
理论地位（务必记住）：在许可型（permission-based）模型中，$2(N-1)$ 是消息数的下界。下界论证的直觉是：任何一个进程都可能正在临界区中，因此请求者无法预先排除任何人——它必须征询全部 $N-1$ 个进程（至少 $N-1$ 条请求消息），并且每个被征询者都必须表态（至少 $N-1$ 条许可消息），否则”沉默者”是被允许进入还是被拒绝就无法确定，安全性无从保证。于是每次进入至少 $2(N-1)$ 条消息，RA 恰好达到这个下界，因此它在”必须收集全体许可”这一类算法中是消息复杂度最优的。它同时把客户端延迟与同步延迟压到 $O(1)$——用 $O(N)$ 的消息换来 $O(1)$ 的延迟，这就是 RA 的历史地位。
算法 14.3.4：Maekawa 的投票 / 法定人数算法（Quorum-Based）
动机：RA 要求全体 $N-1$ 个进程的回复，消息数 $O(N)$。Maekawa 的关键洞察是：互斥并不需要所有人同意，只需要”任何两个请求者的许可集合有交集”——只要交集中的那个进程（作为”裁判”）一次只投一票，两个请求者就不可能同时收齐许可。于是消息数可以从 $O(N)$ 降到 $O(\sqrt N)$。
投票集（Voting Set / Quorum）的定义与五个条件
每个进程 $P_i$ 关联一个投票集 $V_i \subseteq \{P_1,\dots,P_N\}$，必须满足：
| # | 条件 | 作用 |
|---|---|---|
| 1 | $P_i \in V_i$（每个进程属于自己 的投票集） | 允许”给自己投票”，请求者不必等自己 |
| 2 | $V_i \cap V_j \neq \emptyset$，$\forall i \neq j$ | 互斥的保障：交集里的进程一次只投一票 |
| 3 | $\vert V_i\vert = K$，$\forall i$ | 每个请求者需要收集的许可数相同（延迟可比） |
| 4 | 每个进程被包含在恰好 $M$ 个投票集中 | 各进程负载均衡（不设”最忙的裁判”） |
| 5 | 最优性：$K = M \approx \sqrt N$ | 把每次进入的消息数（$\propto K$）与每个进程的投票负载（$\propto M$）同时压到最小 |
为什么最优是 $K = M \approx \sqrt N$（讲义的推导，逐步补全）
- 统计”投票集成员”的总出现次数：每个投票集大小 $K$，共 $N$ 个投票集 $\Rightarrow$ 总出现次数 $= K\cdot N$。
- 另一方面，每个进程出现在恰好 $M$ 个投票集中 $\Rightarrow$ 总出现次数 $= M\cdot N$。
- 两者相等给出 $K = M$。 —— 但这只是”相等”，还需要一个”越小越好”的下界。考虑任取进程 $P_i$：属于 $V_i$ 的成员共有 $K$ 个，而这些成员又各自出现在 $M-1$ 个其他投票集中。要让每个进程在 $P_i$ 的”影响范围”（他必须与之通信或与之竞争的进程）内不重复出现（重复意味着浪费：同一个进程被算了两次却没覆盖新进程），需 \(N = (M-1)\cdot K + 1\) （$+1$ 是 $P_i$ 自己）。代入 $K=M$：$N = (K-1)K + 1$，解得 $K \approx \sqrt N$。这就是 $K = M \approx \sqrt N$ 的来源。
- 构造方法：(a) 矩阵构造：把 $N$ 个进程排成 $\sqrt N \times \sqrt N$ 矩阵，$V_i = $”$P_i$ 所在的行 $\cup$ 所在的列”，大小 $K = 2\sqrt N - 1$（例如 $N=4$ 时 $V_1=\{p_1,p_2,p_3\}$）；(b) 射影平面构造：当 $N = (K-1)K+1$ 时存在每个集合恰好相交于 1 个元素的最优构造（例如 $N = 7,\ K=3$，即 Fano 平面）——这正是 $N=7$ 这个例子的价值。
机制图解：$N=7$ 的投票集（Fano 平面，$K = M = 3$）
V1={1,2,3} V2={1,4,5} V3={1,6,7} V4={2,4,6}
V5={2,5,7} V6={3,4,7} V7={3,5,6}
校验 ① 每个 V_i 大小 = 3 = K ✔ 校验 ② 每个进程恰好出现在 M = 3 个集合中：
P1: V1,V2,V3 P2: V1,V4,V5 P3: V1,V6,V7 P4: V2,V4,V6
P5: V2,V5,V7 P6: V3,V4,V7 P7: V3,V5,V6 ✔
交集矩阵（|V_i ∩ V_j|，任意两个集合恰好交于 1 个进程）：
V1 V2 V3 V4 V5 V6 V7
V1 - 1 1 1 1 1 1 例：V1∩V4={2}, V2∩V7={5}, V3∩V6={7}
V2 1 - 1 1 1 1 1 V4∩V7={6}, V1∩V7={3} …
V3 1 1 - 1 1 1 1
V4 1 1 1 - 1 1 1 ⇒ 任意两个请求者共享至少一个"裁判"，
V5 1 1 1 1 - 1 1 而裁判一次只投一票 ⇒ 不可能同时获批
V6 1 1 1 1 1 - 1
V7 1 1 1 1 1 1 -
形象化：把 7 个进程看作"7 条线 / 7 个点"，"点在线上的关联"就是成员关系；
7 点 7 线、每线 3 点、每点 3 线、任意两线恰好交于一点 —— 这就是 Fano 平面。
（对照：$N = (K-1)K+1$ 在 $K=3$ 时正好给出 $N=7$，所以 $N=7$ 能构造出 $K=M=3=\sqrt N$ 的完美投票集；而矩阵构造对一般的 $N$ 给出 $K = 2\sqrt N - 1$，稍差但通用。）
伪代码
每个进程 P_i 维护:
V_i : 投票集（含 P_i 自己）
state : RELEASED | WANTED | HELD -- 初值 RELEASED
voted : 布尔，初值 false -- "我的票是否已经投出且尚未归还"
granted_to : 我把票投给了谁（⊥ 表示没有） -- ★ 来源检查所必需
vote_queue : 收到但未能投票的请求队列（FIFO）
votes : 已收到的票数
-- ① enter() --
upon event <enter(S)>:
state ← WANTED
votes ← 1 -- 自己给自己投一票（P_i ∈ V_i）
for each P_j in V_i, j ≠ i:
send REQUEST(i) to P_j -- 只问投票集，不是全体！
wait until votes = |V_i| = K -- 收齐整个投票集的票
state ← HELD
AccessResource()
-- ② 收到 REQUEST：一次只投一票 --
upon receiving REQUEST(j) from P_j:
if state = HELD or voted = true: -- 我已经把票给了别人 / 我自己在 CS
vote_queue.append(j) -- 入队，等 RELEASE 后再投
else:
voted ← true -- ★ 承诺：在归还之前不再投别人
granted_to ← j
send REPLY to P_j
-- ③ 收到 RELEASE：归还票，并转给队列里的下一个 --
upon receiving RELEASE(j) from P_j:
if voted = false or granted_to ≠ j:
return -- ★★ 来源检查：只有"我投票给的那个人"
-- 才能解除我的承诺（见正确性论证）
if vote_queue = ∅:
voted ← false
granted_to ← ⊥
else:
k ← vote_queue.popleft()
granted_to ← k -- 票直接转给 k（承诺不中断）
send REPLY to P_k
-- ④ exit() --
upon event <exit(S)>:
state ← RELEASED
for each P_j in V_i: -- ★ 必须向整个投票集广播 RELEASE
send RELEASE to P_j --（这是我"解锁"各位裁判的唯一手段）
算法逻辑解说（$N=7$，$K=3$，$P_1$ 与 $P_4$ 竞争的例子）
- $P_1$ 想进入：向 $V_1=\{P_1,P_2,P_3\}$ 发
REQUEST，自己先投自己一票，等 $P_2,P_3$ 的票。 - $P_4$ 同时想进入：向 $V_4=\{P_2,P_4,P_6\}$ 发
REQUEST。 - $V_1 \cap V_4 = \{P_2\}$。$P_2$ 先收到谁就投给谁，另一个进
vote_queue；假设先收到 $P_1$，则voted=true，投给 $P_1$，把 $P_4$ 入队。 - $P_1$ 收齐 $P_2,P_3$ 的票（加自己共 3 票）⇒ 进入临界区。$P_4$ 拿到 $P_6$ 的票但缺 $P_2$ 的票 ⇒ 等待。
- $P_1$
exit()，向 $V_1$ 全体（$P_1,P_2,P_3$）发RELEASE；$P_2$ 检查发送者确实是它投票给的 $P_1$，于是把票转给队首 $P_4$ ⇒ $P_4$ 收齐票进入。 - 消息数：进入 $P_1$ 用 2 条
REQUEST（不含自己）+ 2 条REPLY$= 2K-2$，退出 3 条RELEASE$= K$；按讲义记账为 $2\sqrt N$ 条进入 + $\sqrt N$ 条退出 $= 3\sqrt N$。
正确性论证
安全性（互斥）：先陈述本算法真正依赖的不变式。
不变式 INV（一票一承诺）：若进程 $P_k$ 在时刻 $t$ 把票投给了 $P_x$，那么在收到来自 $P_x$ 的
RELEASE之前，$P_k$ 不会把票投给任何其他进程。
伪代码 ②③ 恰好维护 INV：② 中只有 voted = false 才投票，投出后置 voted = true 并记下 granted_to = j；③ 中只有发送者等于 granted_to 的 RELEASE 才会解除承诺（要么置 voted = false，要么把票转交给队列里的下一个请求者）。
为什么必须做”来源检查”（这一步最容易被漏掉）：RELEASE 是广播给退出者的整个投票集 $V_x$ 的，而 $V_x$ 中很多进程从来没有给 $P_x$ 投过票。如果它们”一收到 RELEASE 就解锁”，就会出现这样的坏事：$P_k$ 刚把票投给 $P_i$（$P_i$ 正在临界区），此时另一个早已退出的 $P_x$（$P_k \in V_x$）的 RELEASE 到达，$P_k$ 被错误地解锁并转手把票投给 $P_j$ ⇒ $P_i$ 与 $P_j$ 同时收齐了票，互斥被破坏。所以实现必须做来源检查（或为每个请求者单独记录票的状态）。这正是历史上关于 Maekawa 算法的一处著名争议点：算法是否保证互斥，取决于这种”票的归还规则”是否被精确定义。
现在假设 $P_i$ 与 $P_j$（$i \ne j$）同时处于临界区，则 $P_i$ 收齐了 $V_i$ 中每一个进程的 REPLY（票），$P_j$ 收齐了 $V_j$ 中每一个进程的票。由投票集条件 2，存在 $P_k \in V_i \cap V_j$，因此 $P_k$ 既投了 $P_i$ 又投了 $P_j$。设 $P_k$ 先投给 $P_i$（另一种次序对称）。按 INV，$P_k$ 要再投给 $P_j$，必须在此之间收到来自 $P_i$ 的 RELEASE；而按伪代码 ④，$P_i$ 只在自己退出临界区之后才广播 RELEASE。也就是说：$P_j$ 收齐票而进入临界区的时刻，必然晚于 $P_i$ 退出临界区的时刻——但”$P_i$ 已退出”与假设”$P_i$ 此时仍在临界区”矛盾。于是不可能同时进入临界区。$\blacksquare$ 依赖的机制：投票集相交（$V_i \cap V_j \ne \emptyset$）与不变式 INV（一票一承诺 + 只由被投者的 RELEASE 归还）两者合起来。任缺一条都不成立：没有相交，两个请求者可以无交集地各自收齐票；没有 INV（例如”收到任何 RELEASE 都解锁”的错误实现），裁判可以在前一个承诺还没归还时把票转给别人。
活性（进展）——Maekawa 算法的著名难题
结论先行：朴素版本的 Maekawa 算法可能死锁（讲义明确给出反例：”all 4 processes need access：P1 等 P3，P3 等 P4，P4 等 P2，P2 等 P1 —— No progress in the system!”）。原因正是 RA 里那套”最小时间戳必然拿到所有回复”的论证在这里失效了：RA 中每个请求者都向全体发请求，所以时间戳最小的那个人的请求在所有人手里；而 Maekawa 中请求者只发给自己的投票集，$P_i$ 的请求可能根本到不了 $P_k$，于是”等待关系”可以形成与时间戳顺序无关的环——$P_i$ 在等 $P_k$ 的票，只是因为 $P_k \in V_i$，而 $P_k$ 在等另一个与 $P_i$ 无直接关系的人。
反例（3 进程的最简单循环等待）。取 $N=3$，$K=M=2$：$V_1=\{P_1,P_2\}$，$V_2=\{P_2,P_3\}$，$V_3=\{P_1,P_3\}$。三个条件都满足（每个集合大小 2；每个进程恰好出现在 2 个集合中；任意两个集合恰好交于 1 个进程）。
投票集： V1 = {P1,P2} V2 = {P2,P3} V3 = {P1,P3} （K = M = 2, N = 3）
┌────────────────────────────────────────────────────────────────────────────┐
│ 步骤 1：每个进程先收到"环中下一个"的请求，并投出自己唯一的一票 │
│ ① P2 收到 P1 的 REQUEST（P2 ∈ V1 ✔）⇒ voted = true，投给 P1 │
│ ② P3 收到 P2 的 REQUEST（P3 ∈ V2 ✔）⇒ voted = true，投给 P2 │
│ ③ P1 收到 P3 的 REQUEST（P1 ∈ V3 ✔）⇒ voted = true，投给 P3 │
│ │
│ 步骤 2：每个进程又收到另一个请求，但票已投出，只能入队等待 │
│ ④ P1 收到 P2 的 REQUEST（P2 ∈ V1 ✔）⇒ 入队，于是 P2 等 P1 的票 │
│ ⑤ P2 收到 P3 的 REQUEST（P3 ∈ V2 ✔）⇒ 入队，于是 P3 等 P2 的票 │
│ ⑥ P3 收到 P1 的 REQUEST（P1 ∈ V3 ✔）⇒ 入队，于是 P1 等 P3 的票 │
└────────────────────────────────────────────────────────────────────────────┘
投票环： P1 ──投给──► P2 ──投给──► P3 ──投给──► P1 （每人各投出一票，都被锁住）
等待环： P1 ──等 P2 的票──► P2 ──等 P3 的票──► P3 ──等 P1 的票──► P1
结果：三人都等着别人 RELEASE，却谁也没能进入临界区 ⇒ 死锁，系统零进展。
注意：无论三者时间戳的大小关系如何，这个环都存在 —— "等谁"由投票集成员关系决定，
而不由时间戳决定（时间戳只在"投给谁"的判决中起作用）。
讲义给出的 4 进程版本同理（矩阵构造 $N=4$：$V_1=\{p_1,p_2,p_3\},V_2=\{p_1,p_2,p_4\},V_3=\{p_1,p_3,p_4\},V_4=\{p_2,p_3,p_4\}$，环为 $P_1 \to P_3 \to P_4 \to P_2 \to P_1$，其中每个 $P_x$ 都把票投给了环上的下一个：$P_1$ 投给 $P_3$（$P_3\in V_1$）、$P_3$ 投给 $P_4$（$P_4\in V_3$）、$P_4$ 投给 $P_2$（$P_2\in V_4$）、$P_2$ 投给 $P_1$（$P_1\in V_2$），四人的投票集与等待关系完全自洽，因此该场景是可实现的，不是假想）。
解决方案：基于时间戳的优先级 + 超时/失败（FAILED）消息 ⇒ 死锁检测与恢复
死锁免版本（文献中的标准做法，称为”带优先级与失败通知的 Maekawa”）在伪代码上增加三件事：
- 每个请求携带时间戳：$P_i$ 的
REQUEST变成REQUEST(i, ts_i)，$ts_i$ 取当前 Lamport 时钟值。 - 裁判按优先级重排，并向被挤掉的人发 FAILED：当 $P_k$ 已经把票投给 $P_x$，随后又收到优先级更高（时间戳更小）的 $P_y$ 的请求时，$P_k$ 可以（在实现允许时）改投 $P_y$，并向 $P_x$ 发送
FAILED消息；收到FAILED的 $P_x$ 放弃本轮，稍后带着一个全新的、更大的时间戳重新发起请求。 - 超时兜底：请求者若在超时后仍未收齐票，同样视为失败并重试（异步系统里超时只能作为启发式，不能作为正确性依据——这也正是它的争议点）。
为什么时间戳的单调递增性最终保证进展：每一次重试都会让该进程的 Lamport 时钟严格增大（重试本身是一个新的本地事件，$C \leftarrow C+1$；期间收到的任何消息又会把它抬到 $\max(C, \text{msg})+1$），于是”重试 ⇒ 时间戳变大”。考虑一个死锁环：环中的每个成员都在等环中下一个成员释放。若环里还有任何成员被 FAILED（被更高优先级的请求挤掉），它就会退出这个环并重试；时间戳单调递增意味着被挤掉的一方下次的优先级一定比这次高。随着系统运行，环中优先级最低的成员会被反复挤掉；只要系统最终静默（不再有新的请求注入，重试次数足够多），就会有一个请求者拥有全局最大的时间戳——没有人能 FAILED 它，它在自己的投票集中必然拿到所有票并进入临界区，从而打破等待环。这就是”用时间戳的单调性把死锁变成可恢复的活锁再收敛为进展”的论证。
补充说明（严谨边界，务必知道）：这个论证不是无条件的——它依赖”最终静默”与重试次数的界，异步系统中不存在”必须重试几次就一定成功”的硬上界；事实上历史上关于 Maekawa 算法与 FAILED 机制是否在并发争用下仍严格保证互斥曾有过公开争论（Sanders 对 Maekawa 原始版本的批评）。因此工程上更常见的选择是不用它：要么用令牌型算法，要么直接上共识（见 14.5）。考试与作业中，请把”Maekawa 需要额外的死锁检测/恢复机制，否则会死锁”作为标准答案。
公平性（Maekawa 的著名软肋）
- 不满足 happens-before 公平性：请求只发给投票集，且裁判的判决只依据”票是否已投出”以及（在死锁免版本中）时间戳比较。一个进程的请求可能因为其投票集成员正在给别人排队而被长期挡住。
- 可能饥饿：一个 $P_i$ 若在自己的投票集中刚好是”被排队的那个”，而且每次它快拿到票时又有时间戳更新（更大，但先到裁判处）的请求插进来（尤其是死锁免版本中”改投更高优先级请求”的机制），它可能被反复插队。“按时间戳改投”提高安全性的同时恰恰削弱了公平性：因为它允许后来者（时间戳更小者）抢走已经排上的队。因此 Maekawa 算法只能声称弱的无饥饿性质，而不是 RA 那样的因果公平性——这是文献中对它的标准批评，也是”用 $\sqrt N$ 的消息换公平性”的真实代价。
复杂度
| 维度 | 结果 |
|---|---|
| 消息复杂度 | 进入 $2K \approx 2\sqrt N$ 条（$\sqrt N$ 条 REQUEST + $\sqrt N$ 条 REPLY）+ 退出 $K \approx \sqrt N$ 条 RELEASE $=$ $3\sqrt N$ 条/次。$N \approx 10^6$ 时 $\sqrt N = 1000$，而 RA 需要 $2(N-1)\approx 2\times10^6$ 条 |
| 客户端延迟 | 1 个 RTT（等自己投票集全体表态）——与 RA 同级 |
| 同步延迟 | 2 个消息传输时间（退出者先要把 RELEASE 送到裁判，裁判再把票转给下一个）——比 RA（1）差 |
| 空间复杂度 | 每进程 $O(\sqrt N)$（vote_queue），投票集配置 $O(N\sqrt N)$ |
| 容错 | 差：投票集中任意一个进程崩溃 ⇒ 使用该投票集的所有进程都无法进入临界区（比 RA 的”任意进程崩溃影响所有人”稍好，但仍不可接受）；且需要额外的死锁检测/恢复开销 |
算法 14.3.5：令牌型算法的另外两个代表（Raymond 树形 / Suzuki-Kasami）
算法 14.3.5(a)：Raymond 树形令牌算法（Tree-Based Token）
- 核心思想：把 $N$ 个进程组织成任意一棵生成树（spanning tree），令牌只有一个；每个节点维护一个指向”令牌可能所在方向”的指针
holder（初始时令牌持有者是树根，所有人指向父节点）与一个 FIFO 请求队列。请求沿树朝根（令牌）方向向上传递，令牌沿同一路径向下移动到请求者。 - 伪代码（要点化）：
每个进程 P_i 维护: holder_i（令牌可能在我的哪个邻居方向）, q_i（FIFO 请求队列）
upon event <enter(S)>:
把自己的请求放入 q_i 队尾
forward_if_possible() -- 见下
upon receiving REQUEST from neighbor P_j: -- 邻居（含子节点）想要令牌
把 P_j 放入 q_i 队尾
forward_if_possible()
procedure forward_if_possible():
if q_i 为空: return
if holder_i = 自己 and 令牌在手:
if q_i 队首是本进程:
取出队首; state ← HELD; AccessResource() -- 自己用
else:
把令牌沿"指向 q_i 队首"的方向发出; holder_i ← 该方向
else:
if q_i 在本次入队前为空: -- 只转发"第一个"请求，避免重复
把 REQUEST 发给 holder_i; holder_i ← holder_i（等待方向可能改变）
upon event <exit(S)>:
state ← RELEASED
forward_if_possible() -- 把令牌继续发给队首
- 解说：请求”逐跳向上”直到遇到令牌所在方向，令牌再”逐跳向下”到达请求者；沿途每个节点用 FIFO 队列维持局部的先来先服务。树高为 $h$ 时，令牌走 $O(h)$ 跳。
- 正确性：安全性仍靠唯一令牌（与环式同）；活性靠”请求必然被转发到令牌持有者 + 令牌必然沿路径送达”，依赖树连通且无故障；公平性是逐节点的局部 FIFO，全局只是近似公平。
- 复杂度：平均 $O(\log N)$ 条消息（随机/平衡树），最坏 $O(N)$（退化成链）；客户端延迟按距离变化；空间每进程 $O(1)$ 队列。相对环式的优势是平均通信量大幅下降，且不需要固定环（拓扑可动态调整）。
- Suzuki-Kasami 对比：Suzuki-Kasami 用序列号让令牌”知道”谁在等：每个进程维护 $RN_i[j]$（它见到的 $P_j$ 的最大请求序号），令牌里携带 $LN[1..N]$（已满足的请求序号）与一个 FIFO 队列。请求时广播
REQUEST(i, sn)给全体（$N-1$ 条消息），但不需要收集许可——持有令牌的进程发现某个 $RN_j[k] = LN[k]+1$ 就把令牌交给它。因此它每次进入的消息数是固定的 $N$ 条（广播 $N-1$ + 令牌 1 跳），但在临界区使用非常频繁的场景下更划算（见 14.5 的频率分析）。
14.3.6 横向对比总表（本讲的”地图”）
| 算法 | 类型 | 每次进入消息数 | 退出消息 | 客户端延迟 | 同步延迟 | 公平性 | 容错性 | 单点故障 |
|---|---|---|---|---|---|---|---|---|
| 集中式 Central | permission | 3（与 $N$ 无关） | 1（RELEASE） | 2 个消息延迟 ≈ 1 RTT | 2 个消息延迟 | 队列 FIFO，强公平 | 差（不允许任何失败） | 有（协调者） |
| 环式 Ring / Token Ring | token | 每次进入 1 条、系统内共 $1\sim N$ 条（均值 $\approx N/2$） | 1（传令牌） | $0 \sim N$ | $1 \sim N-1$ | 近似 FIFO，无饥饿 | 中（需令牌再生 + 环重建） | 无 |
| Ricart-Agrawala | permission | $2(N-1)$（组播时 $N$） | 最坏 $N-1$ 个 REPLY | 1 RTT | 1 个消息延迟 | happens-before 序，强公平 | 差（任一进程崩溃即全阻塞） | 无 |
| Maekawa | permission | $2\sqrt N$ | $\sqrt N$（RELEASE） | 1 RTT | 2 个消息延迟 | 弱（可能饥饿，不满足因果序） | 差（投票集内任一进程故障即阻塞） | 无 |
| Raymond 树形令牌 | token | 平均 $O(\log N)$，最坏 $O(N)$ | 令牌随传递 | 随树距离变化 | — | 局部 FIFO，弱 | 中（树断需重建） | 无 |
| Suzuki-Kasami 序列号令牌 | token | $N$（广播 $N-1$ + 1 跳令牌） | 令牌随传递 | 1 RTT（若持牌则 0） | 1 个消息延迟 | 按请求序号，近似 FIFO | 中（令牌需再生） | 无 |
“没有免费的午餐”：这张表里没有任何一行是全面最优的——
- 集中式消息数最少且公平性最强，代价是单点故障 + 单点瓶颈；
- 环式没有中心、每跳只 1 条消息，代价是延迟 $O(N)$ 与令牌丢失的处理；
- Ricart-Agrawala 把延迟压到 $O(1)$ 且给出最强的因果公平性，代价是 $O(N)$ 消息（在许可型中它已达下界，无法再省）；
- Maekawa 用 $O(\sqrt N)$ 的消息换来延迟不变，代价是公平性、容错性与死锁风险（必须外加检测/恢复）；
- Raymond / Suzuki-Kasami 等令牌型在”临界区使用频繁”时最划算，代价是”不使用时也要传令牌”的常态开销。
14.4 代码示例与分布式实现
本节三份代码只用 Python 标准库，可直接 python3 运行。第一份是 Ricart-Agrawala 的完整实现，重点在对安全性的直接审计；第二份是对照实验：故意破坏两个关键细节，看它们如何违反互斥；第三份是离散事件模拟，把三种算法的消息数与延迟指标量化出来，并与 14.3 的理论值逐项对照。
14.4.1 代码一：Ricart-Agrawala 的完整实现与互斥性审计
"""
Ricart-Agrawala 分布式互斥：N 个进程 = N 个线程，用 queue.Queue 模拟可靠 FIFO 通道。
运行: python3 ra_mutex.py
"""
import queue
import random
import threading
import time
N, ROUNDS = 4, 3 # 进程数 / 每个进程请求临界区的次数
VERBOSE = False # True 则打印完整事件日志
MSG_DELAY, CS_TIME = 0.001, 0.002 # 消息延迟 / 临界区执行时间
STOP = threading.Event() # 所有进程完成自己的请求后由 main 置位
class Msg:
__slots__ = ("kind", "ts", "src")
def __init__(self, kind, ts, src):
self.kind, self.ts, self.src = kind, ts, src
class Resource:
"""被互斥保护的共享变量 + 用于审计"是否真的互斥"的簿记。"""
def __init__(self):
self.book = threading.Lock() # 只保护审计结构本身(见 14.4.1 机制透视)
self.value = 0 # 共享变量：故意不加锁，保护它是算法的职责
self.in_cs = []
self.max_concurrent = 0
self.violation = None
def enter(self, pid):
with self.book:
self.in_cs.append(pid)
self.max_concurrent = max(self.max_concurrent, len(self.in_cs))
if len(self.in_cs) > 1: # ← 安全性的直接检验
self.violation = "MUTEX VIOLATION: in CS = %s" % sorted(self.in_cs)
def read_modify_write(self):
v = self.value # 读
time.sleep(0.0003) # 放大竞态窗口
self.value = v + 1 # 写回
def leave(self, pid):
with self.book:
self.in_cs.remove(pid)
class Process(threading.Thread):
def __init__(self, pid, schedule, res, channels, t0):
super().__init__(daemon=True)
self.pid, self.schedule, self.res = pid, schedule, res
self.channels, self.t0, self.inbox = channels, t0, channels[pid]
self.clock = 0 # Lamport 逻辑时钟
self.state = "RELEASED" # RELEASED / WANTED / HELD
self.my_ts = 0 # 本轮请求的时间戳（WANTED 期间不变）
self.replies = 0 # 本轮已收到的 REPLY 数
self.deferred = [] # 延迟回复队列 [(ts, src), ...]
self.done, self.log = 0, []
def send(self, dst, msg):
time.sleep(MSG_DELAY)
self.channels[dst].put(msg)
def note(self, text):
self.log.append("t=%.3f P%d %s" % (time.time() - self.t0, self.pid, text))
# ---------------- enter() ----------------
def request_cs(self):
self.clock += 1 # Lamport：本地事件使计数器 +1
self.my_ts = self.clock
self.state, self.replies = "WANTED", 0
self.note("REQUEST ts=%d -> all" % self.my_ts)
for j in range(N):
if j != self.pid:
self.send(j, Msg("REQUEST", self.my_ts, self.pid))
# ---------------- exit() ----------------
def release_cs(self):
self.state = "RELEASED"
pend, self.deferred = self.deferred, []
if pend:
self.note("RELEASE -> reply to %s" % [s for _, s in pend])
for ts, src in pend: # 只回复被延迟的请求
self.send(src, Msg("REPLY", ts, self.pid))
# ---------------- 收到 REQUEST ----------------
def on_request(self, m):
self.clock = max(self.clock, m.ts) + 1 # Lamport 接收规则
# 关键：比较的是"我的请求时间戳 my_ts"，而不是刚更新过的 clock
defer = (self.state == "HELD") or (
self.state == "WANTED" and (self.my_ts, self.pid) < (m.ts, m.src))
if defer:
self.deferred.append((m.ts, m.src))
self.note("defer REQUEST(ts=%d,P%d)" % (m.ts, m.src))
else:
self.note("REPLY -> P%d" % m.src)
self.send(m.src, Msg("REPLY", m.ts, self.pid))
# ---------------- 收到 REPLY ----------------
def on_reply(self, m):
self.clock = max(self.clock, m.ts) + 1
if self.state == "WANTED" and m.ts == self.my_ts: # 只认本轮请求的 REPLY
self.replies += 1
# ---------------- 事件循环（不阻塞等待） ----------------
def run(self):
idx = 0
# 自己的请求做完后仍要继续当"服务员"：否则会漏掉后来到达的 REQUEST，
# 使对方永远等不到 REPLY（违反活性）。
while not STOP.is_set():
if self.res.violation:
return
if (self.done < ROUNDS and self.state == "RELEASED" and idx < ROUNDS
and time.time() - self.t0 >= self.schedule[idx]):
idx += 1
self.request_cs()
try:
m = self.inbox.get(timeout=0.0004)
except queue.Empty:
m = None
if m is not None:
(self.on_request if m.kind == "REQUEST" else self.on_reply)(m)
if self.state == "WANTED" and self.replies == N - 1:
self.state = "HELD"
self.res.enter(self.pid) # 审计：记录我进了 CS
self.note("ENTER (replies=%d)" % self.replies)
time.sleep(CS_TIME)
self.res.read_modify_write() # 访问共享变量
self.res.leave(self.pid)
self.done += 1
self.note("EXIT %d/%d" % (self.done, ROUNDS))
self.release_cs()
if __name__ == "__main__":
random.seed(425)
t0 = time.time()
res, channels = Resource(), [queue.Queue() for _ in range(N)]
procs = [Process(i, sorted(random.uniform(0.0, 0.030) for _ in range(ROUNDS)),
res, channels, t0) for i in range(N)]
print("=== Ricart-Agrawala: N=%d, 每个进程进入 CS %d 次 ===" % (N, ROUNDS))
for p in procs:
p.start()
deadline = time.time() + 10.0 # 活性观察窗口
while time.time() < deadline and not res.violation:
if all(p.done == ROUNDS for p in procs):
break
time.sleep(0.005)
STOP.set()
for p in procs:
p.join(timeout=2.0)
alive = [p.pid for p in procs if p.is_alive()]
merged = sorted(sum((p.log for p in procs), []), key=lambda x: float(x.split()[0][2:]))
print("\n--- 事件日志%s ---" % ("" if VERBOSE else "（前 14 行）"))
for line in (merged if VERBOSE else merged[:14]):
print(" ", line)
print("\n--- 每个进程的统计 ---")
for p in procs:
cnt = lambda k: sum(k in l for l in p.log)
print(" P%d: 进入 CS %d/%d 次 | 发 REQUEST %d | 发 REPLY %d | 延迟回复 %d"
% (p.pid, p.done, ROUNDS, cnt(" REQUEST "), cnt(" REPLY "), cnt(" defer ")))
print("\n--- 校验 ---")
print(" 审计：同一时刻最多 %d 个进程在 CS（必须 == 1）" % res.max_concurrent)
print(" 共享计数器 value = %d（期望 %d）" % (res.value, N * ROUNDS))
print(" 已完成请求数 = %d（期望 %d）；仍卡住的进程 = %s"
% (sum(p.done for p in procs), N * ROUNDS, alive or "无"))
assert res.violation is None, res.violation
assert res.max_concurrent == 1, "违反互斥！"
assert res.value == N * ROUNDS, "共享变量丢失更新！"
assert not alive, "违反活性：进程 %s 永远等待" % alive
print("\n[PASS] 安全性（互斥）成立；活性（所有请求最终被授予）成立；共享变量无丢失更新。")
【代码做什么？】
N=4个进程，每个都是独立的threading.Thread；每个进程有一个专属的收件箱queue.Queue，进程 $i$ 给 $j$ 发消息就是对channels[j]做一次put——这就是”可靠 FIFO 通道”的实现。request_cs()对应伪代码①：Lamport 时钟+1、记下my_ts、状态置WANTED、向其余 $N-1$ 个进程各发一条REQUEST。on_request()对应伪代码②：先按 Lamport 接收规则更新时钟，再用(my_ts, pid) < (m.ts, m.src)判决”延迟回复”还是”立即回复”；被延迟的请求进deferred队列。on_reply()对应伪代码③：只统计”回答我本轮请求”的 REPLY（m.ts == my_ts）。- 主循环是事件驱动的：每轮最多取一条消息、判断”是否到了我该发起下一次请求的时刻”、判断”是否已收齐 $N-1$ 个 REPLY”。
- 临界区里做两件事：登记审计结构，以及对共享计数器做”读—$+1$—写回”（读与写之间
sleep0.3 ms，把竞态窗口放大到足以暴露问题）。 - 全部进程完成后主线程置位
STOP，打印事件日志、每进程统计与三项校验，最后用四条assert给出机器可验证的结论。
【分布式机制透视】
- 如何模拟分布式环境：一个进程 = 一个线程 + 一个
queue.Queue收件箱；send()里的time.sleep(MSG_DELAY)模拟消息传输时间；Queue自身提供 FIFO 与”不丢失、不重复”，正好对应系统模型里的可靠 FIFO 通道。在真实系统里，这一段被 TCP 连接 / RPC 取代，语义完全一致。 - 并发与交织如何体现：线程调度本身就是异步系统”任意交织”的建模——任何两条消息的处理顺序都可能被操作系统打乱。因此请求时刻用固定种子
random.seed(425)保证可复现，而”无论怎么交织都必须成立”的性质交给审计不变式来检验，而不是交给运气。 - 审计为什么要加锁、被保护的共享变量为什么不加锁：
in_cs列表与max_concurrent是”测量仪器”，它们必须自己线程安全（否则测不准）；而共享变量value故意不加锁——保护它是临界区算法的职责。如果在这里再加一把threading.Lock，那么即使算法写错也不会出现丢失更新，实验就失去了意义。这是做”正确性实验”时非常关键的一个设计选择。 STOP与服务循环：进程做完自己ROUNDS次请求后不能退出，必须继续从收件箱取消息、对别人的REQUEST作出裁决（真实系统中的进程永远在运行）。否则已完成任务的进程会漏掉后来到达的REQUEST，让对方永远等不到REPLY，实验会以”活性违反”的假象收场。代码里用注释显式标注了这个坑。
【与理论的对应】
replies == N - 1才能进入 ↔ 伪代码①的wait until replies = N-1，也对应安全性证明中”$P_i$ 进入前必然收到 $P_j$ 的 REPLY”这一前提；deferred队列 +release_cs()只回复队列成员 ↔ 关键细节 3（为什么不需要 RELEASE 消息）；(my_ts, pid) < (m.ts, m.src)↔ 关键细节 1（$T$ 与 ID 的词典序全序）；max_concurrent == 1的审计 ↔ 安全性（互斥） 的直接检验；value == N * ROUNDS（12）↔ 银行例子的丢失更新检验：互斥成立 ⇒ 12 次”读-改-写”被串行化 ⇒ 计数精确等于 12；- “没有进程卡住” ↔ 活性（无死锁、无饥饿）。
运行输出（python3 ra_mutex.py，节选）：
=== Ricart-Agrawala: N=4, 每个进程进入 CS 3 次 ===
--- 事件日志（前 14 行） ---
t=0.002 P0 REQUEST ts=1 -> all
t=0.003 P1 REPLY -> P0
t=0.004 P2 REPLY -> P0
t=0.005 P3 REPLY -> P0
t=0.006 P0 ENTER (replies=3)
t=0.007 P2 REQUEST ts=3 -> all
t=0.009 P0 EXIT 1/3
t=0.009 P0 REQUEST ts=5 -> all
t=0.009 P1 REPLY -> P2
t=0.010 P1 REPLY -> P0
t=0.010 P3 REPLY -> P2
t=0.011 P2 defer REQUEST(ts=5,P0)
t=0.012 P0 REPLY -> P2
t=0.012 P3 REPLY -> P0
--- 每个进程的统计 ---
P0: 进入 CS 3/3 次 | 发 REQUEST 3 | 发 REPLY 6 | 延迟回复 3
P1: 进入 CS 3/3 次 | 发 REQUEST 3 | 发 REPLY 6 | 延迟回复 3
P2: 进入 CS 3/3 次 | 发 REQUEST 3 | 发 REPLY 5 | 延迟回复 4
P3: 进入 CS 3/3 次 | 发 REQUEST 3 | 发 REPLY 6 | 延迟回复 3
--- 校验 ---
审计：同一时刻最多 1 个进程在 CS（必须 == 1）
共享计数器 value = 12（期望 12）
已完成请求数 = 12（期望 12）；仍卡住的进程 = 无
[PASS] 安全性（互斥）成立；活性（所有请求最终被授予）成立；共享变量无丢失更新。
14.4.2 代码二：对照实验——故意破坏算法会发生什么
"""
对照实验：故意破坏 Ricart-Agrawala 的两个关键细节，观察后果。
correct : 正确实现（含 (T,Pid) 全序 tie-break）
noannounce : 让路时只发 REPLY，不再让"自己的请求"被对方知晓（省略 announce 一步）
notie : 只用时间戳 T 比较，丢掉 Pid tie-break
运行: python3 ra_bugs.py
"""
import queue
import threading
import time
CS_TIME = 0.05 # 拉长临界区，让"重叠"可观测
class Msg:
__slots__ = ("kind", "ts", "src")
def __init__(self, kind, ts, src):
self.kind, self.ts, self.src = kind, ts, src
class Node(threading.Thread):
def __init__(self, pid, lab):
super().__init__(daemon=True)
self.pid, self.lab, self.n = pid, lab, lab.n
self.inbox = lab.channels[pid]
self.clock = 0
self.state = "RELEASED"
self.my_ts = 0
self.replies = 0
self.deferred = []
self.waived = set() # 仅供 noannounce 缺陷使用
self.done = False
def send(self, dst, msg):
time.sleep(0.001)
self.lab.channels[dst].put(msg)
def note(self, text):
self.lab.log.append("t=%5.3f P%d %s" % (time.time() - self.lab.t0, self.pid, text))
def request_cs(self):
self.clock += 1
self.my_ts = self.clock
self.state = "WANTED"
self.replies = 0
self.note("REQUEST ts=%d -> all" % self.my_ts)
for j in range(self.n):
if j != self.pid:
self.send(j, Msg("REQUEST", self.my_ts, self.pid))
def on_request(self, m):
self.clock = max(self.clock, m.ts) + 1
me, other = (self.my_ts, self.pid), (m.ts, m.src)
if self.lab.mode == "notie": # 缺陷：只用 T 比较
defer = (self.state == "HELD") or (self.state == "WANTED" and me[0] < other[0])
else:
defer = (self.state == "HELD") or (self.state == "WANTED" and me < other)
if defer:
self.deferred.append((m.ts, m.src))
self.note("defer REQUEST(ts=%d,P%d)" % (m.ts, m.src))
else:
self.note("REPLY -> P%d" % m.src)
self.send(m.src, Msg("REPLY", m.ts, self.pid))
if self.lab.mode == "noannounce" and self.state == "WANTED":
# 缺陷：以为"让路"就等于"不需要对方的许可了"，
# 于是既不把自己的 REQUEST 告知对方，也不再等它的 REPLY
self.waived.add(m.src)
self.note("(bug) 认为无需 P%d 的 REPLY" % m.src)
def on_reply(self, m):
self.clock = max(self.clock, m.ts) + 1
if self.state == "WANTED" and m.ts == self.my_ts:
self.replies += 1
def ready(self):
return self.replies + len(self.waived) >= self.n - 1
def run(self):
self.request_cs()
self.lab.start_barrier.wait() # 保证双方的 REQUEST 都在处理之前发出
while not self.done and not self.lab.abort.is_set():
try:
m = self.inbox.get(timeout=0.001)
except queue.Empty:
continue
(self.on_request if m.kind == "REQUEST" else self.on_reply)(m)
if self.state == "WANTED" and self.ready():
self.state = "HELD"
self.lab.enter_cs(self.pid)
self.note("ENTER CS")
time.sleep(CS_TIME)
self.lab.counter_read_modify_write()
self.lab.leave_cs(self.pid)
self.note("EXIT CS")
self.done = True
self.state = "RELEASED"
pend, self.deferred = self.deferred, []
for ts, src in pend:
self.send(src, Msg("REPLY", ts, self.pid))
class Lab:
def __init__(self, mode, n=2):
self.mode, self.n = mode, n
self.channels = [queue.Queue() for _ in range(n)]
self.lock = threading.Lock()
self.abort = threading.Event()
self.start_barrier = threading.Barrier(n)
self.in_cs = []
self.violations = []
self.counter = 0
self.max_concurrent = 0
self.log = []
self.t0 = time.time()
def enter_cs(self, pid):
with self.lock:
self.in_cs.append(pid)
self.max_concurrent = max(self.max_concurrent, len(self.in_cs))
if len(self.in_cs) > 1:
self.violations.append("in CS = %s" % sorted(self.in_cs))
self.abort.set()
def leave_cs(self, pid):
with self.lock:
self.in_cs.remove(pid)
def counter_read_modify_write(self):
v = self.counter # 故意不加锁：保护它是算法的职责
time.sleep(0.005)
self.counter = v + 1
def run(self):
self.t0 = time.time()
nodes = [Node(i, self) for i in range(self.n)]
for nd in nodes:
nd.start()
deadline = time.time() + 3.0
while time.time() < deadline and not self.abort.is_set():
if all(nd.done for nd in nodes):
break
time.sleep(0.002)
self.abort.set()
for nd in nodes:
nd.join(timeout=1.0)
stuck = [nd.pid for nd in nodes if not nd.done]
return stuck
if __name__ == "__main__":
print("N=2，两个进程同时请求临界区（Barrier 保证两个 REQUEST 同时在路上）\n")
for mode in ("correct", "noannounce", "notie"):
lab = Lab(mode)
stuck = lab.run()
print("=" * 66)
print("[%s] 事件日志:" % mode)
for line in sorted(lab.log):
print(" ", line)
print(" --- 结论 ---")
print(" 审计: 同一时刻最多 %d 个进程在临界区" % lab.max_concurrent)
if lab.violations:
print(" ❌ 违反 SAFETY(互斥): %s" % lab.violations[0])
else:
print(" ✅ 未违反互斥")
if stuck:
print(" ❌ 违反 LIVENESS: 进程 %s 的请求永远得不到满足" % stuck)
else:
print(" ✅ 所有请求都被授予")
print(" 共享计数器 = %d (期望 %d)%s"
% (lab.counter, lab.n, "" if lab.counter == lab.n else " ❌ 丢失更新"))
print()
【代码做什么？】
- 用
threading.Barrier让两个进程同时发出REQUEST，从而确定性地构造出”两个请求时间戳相同（都是 1）”这一最危险的场景——否则这种并发要碰运气才会出现。 - 三种模式共用一套代码：
correct（正确实现）、noannounce（让路后不再让对方知道自己也在等，即 14.3.3 关键细节 2 的缺陷版）、notie（只用 $T$ 比较，丢掉 ID 决胜）。 CS_TIME = 0.05把临界区拉长到 50 ms，使”两个进程同时在临界区”这种转瞬即逝的重叠必然被审计捕捉。- 每个模式输出完整事件日志、审计到的最大并发数、是否违反互斥、是否有进程被饿死、共享计数器的最终值。
【分布式机制透视】
Barrier在分布式测试里对应”同步起跑“（同一条 RPC 被多个客户端同时发出）；它把”低概率的交织”变成”必然发生的交织”，这是并发缺陷复现的标准手法。- 审计采用”进入时若发现
in_cs非空就永久记录”的写法，而不是在退出时比较——因为违反互斥的窗口可能只有几微秒，只有”进入时刻的快照”才可靠。 - 共享计数器是第二个独立的证人：审计看的是”谁在临界区”，计数器看的是”临界区是否真的保护了数据”。两者同时报警，说明违反互斥不是测量假象，而是会真实损坏数据的错误。
【与理论的对应】
noannounce精确对应 14.3.3 的关键细节 2：它模拟”让路方不再维持不变式 I（双方互相知情）“的实现错误，后果是让路方把对方从自己的等待集合里划掉，于是双方都认为自己已收齐许可。notie精确对应关键细节 1：当 $(T_i,i)$ 的 ID 决胜被丢掉，判决规则在 $T_i = T_j$ 时对双方都为假，两边都走”立即回复”分支——这正是安全性证明里被排除的那种情形。- 两者的输出都落在”
max_concurrent = 2+ 共享计数器丢失更新（$2 \to 1$）”上：理论上的反例在代码里被复现了一次，而且因为固定了Barrier与时间常数，两次运行的日志几乎完全一致（可复现）。
运行输出（python3 ra_bugs.py，完整）：
N=2，两个进程同时请求临界区（Barrier 保证两个 REQUEST 同时在路上）
==================================================================
[correct] 事件日志:
t=0.000 P0 REQUEST ts=1 -> all
t=0.000 P1 REQUEST ts=1 -> all
t=0.002 P0 defer REQUEST(ts=1,P1)
t=0.002 P1 REPLY -> P0
t=0.003 P0 ENTER CS
t=0.058 P0 EXIT CS
t=0.059 P1 ENTER CS
t=0.114 P1 EXIT CS
--- 结论 ---
审计: 同一时刻最多 1 个进程在临界区
✅ 未违反互斥
✅ 所有请求都被授予
共享计数器 = 2 (期望 2)
==================================================================
[noannounce] 事件日志:
t=0.000 P0 REQUEST ts=1 -> all
t=0.000 P1 REQUEST ts=1 -> all
t=0.001 P0 defer REQUEST(ts=1,P1)
t=0.001 P1 REPLY -> P0
t=0.003 P0 ENTER CS
t=0.003 P1 (bug) 认为无需 P0 的 REPLY
t=0.003 P1 ENTER CS
t=0.058 P0 EXIT CS
t=0.058 P1 EXIT CS
--- 结论 ---
审计: 同一时刻最多 2 个进程在临界区
❌ 违反 SAFETY(互斥): in CS = [0, 1]
✅ 所有请求都被授予
共享计数器 = 1 (期望 2) ❌ 丢失更新
==================================================================
[notie] 事件日志:
t=0.000 P0 REQUEST ts=1 -> all
t=0.000 P1 REQUEST ts=1 -> all
t=0.001 P1 REPLY -> P0
t=0.002 P0 REPLY -> P1
t=0.003 P0 ENTER CS
t=0.003 P1 ENTER CS
t=0.058 P0 EXIT CS
t=0.058 P1 EXIT CS
--- 结论 ---
审计: 同一时刻最多 2 个进程在临界区
❌ 违反 SAFETY(互斥): in CS = [0, 1]
✅ 所有请求都被授予
共享计数器 = 1 (期望 2) ❌ 丢失更新
14.4.3 代码三：三种算法的对比实验（离散事件模拟）
"""
离散事件模拟：集中式 / 令牌环 / Ricart-Agrawala 三种互斥算法对比。
场景：N 个进程在 t=0 同时请求临界区、各进入一次（最坏争用）。
运行: python3 me_compare.py
"""
import heapq
LAT, CS_TIME = 1.0, 4.0 # 单跳消息延迟 / 临界区执行时间
class Sim:
def __init__(self, cls, n):
self.n, self.t, self.q, self.seq = n, 0.0, [], 0
self.messages = 0 # 总消息数
self.enter_t = [None] * n # 每个进程进入 CS 的时刻
self.spans = [] # [{'pid','enter','exit'}, ...]
self.done = False
self.algo = cls(self, n) # 每个算法自带状态机
self.algo.init()
def post(self, delay, fn): # 在未来某个时刻执行 fn
self.seq += 1
heapq.heappush(self.q, (self.t + delay, self.seq, fn))
def send(self, src, dst, kind, data=None): # 发一条消息：占用 1 个"消息传输时间"
self.messages += 1
self.post(LAT, lambda: self.algo.deliver(dst, src, kind, data))
def enter_cs(self, pid):
self.enter_t[pid] = self.t
self.spans.append({"pid": pid, "enter": self.t, "exit": None})
self.post(CS_TIME, lambda: self.exit_cs(pid))
def exit_cs(self, pid):
for s in reversed(self.spans):
if s["pid"] == pid and s["exit"] is None:
s["exit"] = self.t
break
self.algo.exit_cs(pid)
def run(self):
while self.q:
self.t, _, fn = heapq.heappop(self.q)
fn()
if self.done:
break
def metrics(self):
n = self.n
client = [self.enter_t[i] for i in range(n)]
sync = [b["enter"] - a["exit"] for a, b in zip(self.spans, self.spans[1:])]
return {"total": self.messages, "per_entry": self.messages / n,
"avg_client": sum(client) / n,
"avg_sync": (sum(sync) / len(sync)) if sync else 0.0}
class Base:
"""公共接口：init() 发起请求，deliver() 处理消息，exit_cs() 释放。"""
name = "?"
def __init__(self, sim, n): self.sim, self.n = sim, n
class Central(Base):
name = "Central(集中式)"
LEADER = "L" # 协调者：唯一持有令牌者
def init(self):
self.has_token, self.queue = True, []
for i in range(self.n):
self.sim.send(src=i, dst=self.LEADER, kind="REQUEST")
def deliver(self, dst, src, kind, data):
if dst == self.LEADER:
if kind == "REQUEST":
if self.has_token: # 空闲 -> 立刻授予（令牌借出）
self.has_token = False
self.sim.send(src=self.LEADER, dst=src, kind="GRANT")
else:
self.queue.append(src) # 否则 FIFO 排队
elif self.queue: # 收到 RELEASE 且有等待者 -> 转交令牌
nxt = self.queue.pop(0)
self.sim.send(src=self.LEADER, dst=nxt, kind="GRANT")
else:
self.has_token = True # 令牌收回
elif kind == "GRANT":
self.sim.enter_cs(dst)
def exit_cs(self, pid):
self.sim.send(src=pid, dst=self.LEADER, kind="RELEASE")
class Ring(Base):
name = "Ring(令牌环)"
def init(self):
self.want = set(range(self.n))
self._visit(0) # 初始令牌在 P0 手中
def _visit(self, i):
if i in self.want: # 令牌到我且我想要 -> 进入 CS
self.want.discard(i)
self.sim.enter_cs(i)
else: # 不想要 -> 立即传给后继
self.sim.send(src=i, dst=(i + 1) % self.n, kind="TOKEN")
def deliver(self, dst, src, kind, data): self._visit(dst)
def exit_cs(self, pid):
if self.want:
self.sim.send(src=pid, dst=(pid + 1) % self.n, kind="TOKEN")
else:
self.sim.done = True # 测量窗口结束（此后令牌仍会空转）
class RicartAgrawala(Base):
name = "Ricart-Agrawala"
def init(self):
self.clock = [0] * self.n
self.my_ts = [0] * self.n
self.state = ["RELEASED"] * self.n
self.replies = [0] * self.n
self.deferred = [[] for _ in range(self.n)]
for i in range(self.n): # 所有人同时请求，时间戳都是 1
self.clock[i] += 1
self.my_ts[i] = self.clock[i]
self.state[i] = "WANTED"
for j in range(self.n):
if j != i:
self.sim.send(src=i, dst=j, kind="REQUEST", data=self.my_ts[i])
def deliver(self, dst, src, kind, data):
if kind == "REQUEST":
self.clock[dst] = max(self.clock[dst], data) + 1
if self.state[dst] == "HELD" or (self.state[dst] == "WANTED"
and (self.my_ts[dst], dst) < (data, src)):
self.deferred[dst].append((data, src)) # 延迟回复
else:
self.sim.send(src=dst, dst=src, kind="REPLY", data=data)
else: # 收到 REPLY
self.clock[dst] = max(self.clock[dst], data) + 1
if self.state[dst] == "WANTED" and data == self.my_ts[dst]:
self.replies[dst] += 1
if self.replies[dst] == self.n - 1:
self.state[dst] = "HELD"
self.sim.enter_cs(dst)
def exit_cs(self, pid):
self.state[pid] = "RELEASED"
pend, self.deferred[pid] = self.deferred[pid], []
for ts, src in pend:
self.sim.send(src=pid, dst=src, kind="REPLY", data=ts)
def measure(cls, n):
sim = Sim(cls, n)
sim.run()
return sim.metrics()
if __name__ == "__main__":
algos = [Central, Ring, RicartAgrawala]
print("场景：N 个进程在 t=0 同时请求临界区，各进入一次；消息延迟 %.1f，CS 时长 %.1f\n"
% (LAT, CS_TIME))
print("%-20s %4s %10s %12s %12s %12s" %
("算法", "N", "总消息数", "每次进入消息", "平均客户端延迟", "平均同步延迟"))
print("-" * 74)
for n in (3, 5, 10):
for cls in algos:
m = measure(cls, n)
print("%-20s %4d %10d %12.2f %12.2f %12.2f"
% (cls.name, n, m["total"], m["per_entry"], m["avg_client"], m["avg_sync"]))
print()
print("理论校验：")
for n in (3, 5, 10):
c, r, g = measure(Central, n), measure(RicartAgrawala, n), measure(Ring, n)
assert c["per_entry"] == 3, c
assert r["per_entry"] == 2 * (n - 1), r
print(" N=%-3d 集中式 %.0f 条/次（=3 ✔）| RA %.0f 条/次（=2(N-1)=%d ✔）"
"| 环式全程共 %d 条（随 N 线性增长）"
% (n, c["per_entry"], r["per_entry"], 2 * (n - 1), g["total"]))
print("\n[PASS] 集中式恒定 3 条/次；RA 恰为 2(N-1) 条/次；环式消息数随 N 线性增长。")
【代码做什么？】
Sim是一个离散事件模拟器：事件堆heapq按虚拟时刻排序，send()让消息在LAT个时间单位后到达——1 个”消息传输时间”被精确建模。- 三个算法类各自实现
init()（发起请求）、deliver()（处理到达的消息）、exit_cs()（退出临界区时的动作），互不干扰。 - 场景固定为”$N$ 个进程在 $t=0$ 同时请求、各进入一次”，这是最坏争用，也是讲义三个指标定义中”只有一个等待者”的连续版本。
- 输出总消息数、每次进入的消息数、平均客户端延迟、平均同步延迟，并在 $N=3,5,10$ 下各跑一遍，最后用
assert把理论值写成可执行断言。
【分布式机制透视】
- 为什么用事件模拟而不是线程：线程版（代码一）检验正确性，事件版检验性能指标——后者需要”精确到整数刻度的时间”和”完全可复现的调度”，这是真实线程做不到的。研究工作中”原型 + 模拟器”的搭配正是这个道理。
- 事件堆天然实现了”可靠 FIFO 通道”：同一对进程之间的消息按
seq先后到达，不会乱序、不会丢失，也不会重复投递。 - 三个算法共用同一个模拟内核，因此唯一变量就是算法本身——这是做对照实验的基本要求。
【与理论的对应】（输出与 14.3 的理论值逐项吻合）
- 集中式：总消息 $3N$、每次进入恰好 3 条（与 $N$ 无关）；最小客户端延迟 $=2$ 个消息传输时间 $=$ 1 个 RTT；平均同步延迟 $=2$（
RELEASE$+$GRANT）——与讲义”release + grant 两个消息延迟”一致。 - Ricart-Agrawala：每次进入恰好 $2(N-1)$ 条（$N=3,5,10$ 时分别是 4、8、18）；最小客户端延迟 $=2=$ 1 RTT；平均同步延迟 $=1$ 个消息传输时间——正是讲义所说的”one message transmission time”。
- 环式：全程只传 $N-1$ 条消息（每人传一次令牌），最小客户端延迟 $=0$（令牌恰在手中），平均同步延迟 $=1$（后继就在旁边，属于讲义说的最好情况）；若把令牌初始位置改成”刚离开请求者”，同一模型立刻给出最坏情况 $N-1$。
- 一个容易被误读的现象：平均客户端延迟随 $N$ 线性增长（RA 在 $N=3,5,10$ 时是 7、12、24.5）。这不是算法开销，而是”所有人都要排队”的必然结果——第 $k$ 个进入者必须等前 $k-1$ 个把临界区执行完，三种算法都如此。若把请求错开发出，这个量就会回落到算法本身的 1 RTT。
运行输出（python3 me_compare.py，完整）：
场景：N 个进程在 t=0 同时请求临界区，各进入一次；消息延迟 1.0，CS 时长 4.0
算法 N 总消息数 每次进入消息 平均客户端延迟 平均同步延迟
--------------------------------------------------------------------------
Central(集中式) 3 9 3.00 8.00 2.00
Ring(令牌环) 3 2 0.67 5.00 1.00
Ricart-Agrawala 3 12 4.00 7.00 1.00
Central(集中式) 5 15 3.00 14.00 2.00
Ring(令牌环) 5 4 0.80 10.00 1.00
Ricart-Agrawala 5 40 8.00 12.00 1.00
Central(集中式) 10 30 3.00 29.00 2.00
Ring(令牌环) 10 9 0.90 22.50 1.00
Ricart-Agrawala 10 180 18.00 24.50 1.00
理论校验：
N=3 集中式 3 条/次（=3 ✔）| RA 4 条/次（=2(N-1)=4 ✔）| 环式全程共 2 条（随 N 线性增长）
N=5 集中式 3 条/次（=3 ✔）| RA 8 条/次（=2(N-1)=8 ✔）| 环式全程共 4 条（随 N 线性增长）
N=10 集中式 3 条/次（=3 ✔）| RA 18 条/次（=2(N-1)=18 ✔）| 环式全程共 9 条（随 N 线性增长）
[PASS] 集中式恒定 3 条/次；RA 恰为 2(N-1) 条/次；环式消息数随 N 线性增长。
14.5 性能与可扩展性分析
14.5.1 消息复杂度曲线：$N$ 是唯一重要的变量
| 算法 | 每次进入消息数公式 | $N=10$ | $N=100$ | $N=10^4$ | $N=10^6$ | 增长阶 |
|---|---|---|---|---|---|---|
| 集中式 | $3$ | 3 | 3 | 3 | 3 | $O(1)$ |
| 环式（令牌） | $1 \sim N$（系统内合计） | $\le 10$ | $\le 100$ | $\le 10^4$ | $\le 10^6$ | $O(N)$ |
| Ricart-Agrawala | $2(N-1)$ | 18 | 198 | 19 998 | $\approx 2\times10^6$ | $O(N)$ |
| Maekawa | $3\sqrt N$ | $\approx 9$ | 30 | 300 | 3 000 | $O(\sqrt N)$ |
| Raymond（树形令牌） | 平均 $O(\log N)$ | $\approx 4$ | $\approx 7$ | $\approx 13$ | $\approx 20$ | $O(\log N)$ 平均，$O(N)$ 最坏 |
| Suzuki-Kasami | $N$（广播 $N-1$ + 令牌 1 跳） | 10 | 100 | $10^4$ | $10^6$ | $O(N)$ |
读法：讲义特别点出 $N \approx 10^6$ 时 $\sqrt N = 1000$——这时 Maekawa 的 $3\sqrt N \approx 3000$ 条消息，比 Ricart-Agrawala 的约 $2\times10^6$ 条少了三个数量级。“降低消息复杂度”是 1980 年代这条研究路线的核心动机；而集中式的 3 条之所以”看起来无敌”，代价在下面两小节里。
14.5.2 延迟：三个指标的分工
| 算法 | 客户端延迟（无争用） | 同步延迟（只有一个等待者） | 备注 |
|---|---|---|---|
| 集中式 | 2 个消息延迟 $=$ 1 RTT | 2 个消息延迟 | 协调者成为延迟与吞吐的双重瓶颈 |
| 环式 | $0 \sim N$ | $1 \sim N-1$ | 令牌位置决定一切，最坏 $O(N)$ |
| Ricart-Agrawala | 1 RTT | 1 个消息延迟（最优） | 延迟最优，但消息 $O(N)$ |
| Maekawa | 1 RTT | 2 个消息延迟 | 退出者要先把 RELEASE 送到裁判，裁判再投票 |
| Raymond / Suzuki-Kasami | 随树距离 / 1 RTT | 1 个消息延迟 | 令牌在手时为 0 |
“没有免费的午餐”在此处最直观：RA 用 $O(N)$ 的消息买到 $O(1)$ 的延迟；Maekawa 用 $O(\sqrt N)$ 的消息买到同样的客户端延迟，但同步延迟退化为 2，并且引进了死锁与饥饿风险；集中式消息最少（3）却有单点；环式延迟最差却最”去中心”。没有一行能同时占优，选择取决于你更怕什么。
14.5.3 容错性：经典算法几乎都”零容错”
讲义在系统模型里明确写着 “Processes do not fail”，并在最后补充 “There are fault-tolerant versions of the algorithms we’ve discussed… One other way to handle failures: Use Paxos-like approaches!”。把这一点讲透很重要：
| 算法 | 能容忍的故障 | 故障后果 | 需要什么才能容错 |
|---|---|---|---|
| 集中式 | 0（含协调者） | 协调者崩溃 ⇒ 全系统无法进入临界区 | 重新选举（Lecture 11）+ 队列/令牌状态恢复（这已是共识问题） |
| 环式 | 0（任一进程或令牌丢失） | 断环 ⇒ 令牌循环终止；令牌丢失 ⇒ 永久停滞 | 令牌再生协议（难点：”旧令牌是否真的不存在”不可判定）+ 环重建 |
| Ricart-Agrawala | 0 | 任一进程崩溃 ⇒ 所有等它 REPLY 的进程永久阻塞；$N-1$ 个崩溃 ⇒ 完全瘫痪 | 超时 + 故障检测 + 成员变更；但异步系统中”慢”与”挂”不可区分 ⇒ 超时只能当启发式 |
| Maekawa | 0（投票集内任一进程） | 依赖该裁判的进程全部阻塞 | 稀疏投票集的故障恢复（学界有专门研究） |
| Raymond / Suzuki-Kasami | 0（令牌持有者一崩即失令牌） | 令牌丢失 ⇒ 停滞 | 令牌再生 + 拓扑修复 |
结论：经典互斥算法关心的是”在无故障的异步系统里，用多小的代价重建锁语义“，它们不解决“有故障时怎么办”。而真实分布式系统一定会有故障，因此工程上必须换一条路——见 14.5.5。
14.5.4 临界区使用频率：令牌型还是许可型？
设临界区请求率为 $\lambda$（次/秒），$N$ 个进程。
- 低频（$\lambda$ 很小，临界区长期空闲）⇒ 许可型更优。 空闲时零开销：没人请求就没有任何消息。而令牌型必须持续维护令牌：环式即使在无人使用时也要让令牌一圈圈转（每 $N$ 跳一次，常态带宽与能耗）；Suzuki-Kasami 的令牌虽能静止在最后使用者处，但每次请求要广播 $N-1$ 条。
- 高频（$\lambda$ 很大，临界区几乎总被占用）⇒ 令牌型更优。 令牌一直在”有用”地流动，边际成本被摊薄：请求者只需”等令牌传到我”，不必每次都向全体收集许可。RA 的带宽随 $\lambda$ 线性上升（$2(N-1)$ 条/次），而 Raymond 平均只需 $O(\log N)$ 跳、环式每跳 1 条消息。
- 定量小例子：$N=100$、每秒 1000 次临界区请求。Ricart-Agrawala 需要 $1000 \times 198 = 1.98\times10^5$ 条/秒；Maekawa 需要 $1000\times30=3\times10^4$ 条/秒；Suzuki-Kasami 需要 $1000\times100=10^5$ 条/秒；而 Raymond 平均 $\approx 1000\times7=7000$ 条/秒。一旦临界区被高频使用，$O(\log N)$ 的令牌型优势非常明显。
- 判定经验：临界区使用稀疏 + 要求强公平 ⇒ 许可型（RA / 集中式）；使用密集 + 追求低带宽 ⇒ 令牌型（Raymond / Suzuki-Kasami）；$N$ 很大且必须全省消息 ⇒ Maekawa（但要接受公平性与死锁风险）。
14.5.5 真实系统中的应用：分布式锁服务与”用共识替代经典互斥”
工业界并没有把 Ricart-Agrawala 或 Maekawa 直接搬进生产系统，而是走了另一条路：把”锁服务”做成一个用共识协议复制的状态机。
- Chubby（Google）：为大名鼎鼎的 BigTable、Megastore 等系统提供锁与”小配置文件”读写。技术要点：(1) 一组服务器（通常 5 个）用 Paxos 类共识复制同一份信息，其中一个被选为 Master/Leader；(2) 客户端读请求发给 Leader 就地服务，写请求发给 Leader 后由它发给所有服务器并取得多数派（quorum）确认后才回应客户端；(3) Leader 失败则重新选举，副本失败则替换并让它追赶日志。关键限制（讲义原文）：Chubby 只提供 advisory locks（建议性锁）——除非每个客户端在访问资源前都真的去检查锁，否则不保证互斥。这与本章的算法形成对照：算法层面的互斥是”硬”的（协议保证），而工程中的锁服务往往是”软的”（依赖客户端自觉）。
- ZooKeeper：用 ZAB 共识协议；锁定通常用”创建顺序临时节点 + 监视比自己小的那个节点”实现，客户端崩溃导致会话过期时临时节点自动删除 ⇒ 锁自动释放（这是经典算法完全没有的能力：RA 里一个崩溃的持有者会让所有人永远等待）。
- etcd：用 Raft 共识 + lease（租约） 实现分布式锁，加锁就是一次 Raft 日志提交。
为什么现代系统用共识替代经典互斥算法？ 四条理由：
- 容错：共识在 $f < n/2$ 的崩溃故障下仍可工作（需要 $2f+1$ 个副本），而经典算法一个进程崩溃就全阻塞。
- 持久状态：锁服务必须记住”谁持有锁、租约还剩多久、客户端死了怎么释放”，这些状态需要复制到多数派上持久化，本质上是”共识 + 复制状态机”，而不是”一次性收集许可”。
- 次序：共识提供的全序广播恰好覆盖了互斥所需的次序保证，而且这个次序在故障切换后仍然有效（RA 的时间戳次序在进程重启后需要额外机制维持）。
- 组合能力：Chubby/ZooKeeper 同时提供锁、配置、成员、选主等原语，用一套共识内核统一支撑，工程上更划算。
代价也要清楚：共识需要多数派、至少 3 个副本、每次加锁一次日志提交（1 RTT + 落盘），比 RA 的”纯消息收集”更贵——这是用延迟和部署复杂度换容错与持久性。
- Redlock 的争议（务必知道）：Redis 社区提出的 Redlock 方案向 $N$ 个相互独立的 Redis 实例请求锁，若多数实例在锁有效期内成功加锁则认为持有成功。Martin Kleppmann 的批评集中在两点：(a) 它依赖时钟与超时假设——异步系统里进程可能长时间暂停（GC、换页）、时钟可能跳变，一个”已经过期”的锁持有者可能在恢复后继续写入；(b) 它没有 fencing token（栅栏令牌）——即使锁服务本身判断正确，被暂停的旧持有者仍能写入。由此引出的工程准则极其重要：锁只保证”进入临界区”这一步，而”临界区内的写入必须能被下游识别并拒绝”是另一个独立问题。正确做法是让持有者在每次写入时携带单调递增的 fencing token，由存储侧拒绝旧 token 的写入；或者直接使用有共识的协调服务（ZooKeeper/etcd）。
14.5.6 汇总：一页决策表
| 算法 | 每次进入消息数 | 客户端延迟 | 同步延迟 | 容错 | 公平性 | 最适用 |
|---|---|---|---|---|---|---|
| 集中式 | 3（$O(1)$） | 1 RTT | 2 msg | 0（含协调者） | 强（FIFO） | $N$ 不大、可接受单点、追求极小消息量 |
| 环式 | $1\sim N$ | $0\sim N$ | $1\sim N-1$ | 0 | 近似 FIFO | 已有环拓扑、请求稀疏、要求去中心 |
| Ricart-Agrawala | $2(N-1)$ | 1 RTT | 1 msg | 0 | 强（happens-before） | 追求低延迟与强公平、$N$ 中等、无故障假设 |
| Maekawa | $3\sqrt N$ | 1 RTT | 2 msg | 0 | 弱（可饥饿） | $N$ 很大、消息带宽是首要约束、可接受额外机制 |
| Raymond | 平均 $O(\log N)$ | 随树距离 | 1 msg | 0 | 弱 | 高频率使用、能维护生成树 |
| Suzuki-Kasami | $N$ | 1 RTT | 1 msg | 0 | 近似 FIFO | 高频率使用、$N$ 不大 |
| 共识型锁服务（Chubby/ZooKeeper/etcd） | 每次加锁一次共识提交（1 RTT + 落盘） | 1 RTT | 由共识决定 | $f < n/2$ | 由共识的全序决定 | 生产环境：需要容错与持久状态 |
14.6 关键要点
- 黄金法则：分布式互斥 = 用消息传递在无共享内存的环境中重建”单机锁”的语义；所有算法的差异只在于用什么机制打破争用——中央队列、令牌、时间戳全序、还是两次 quorum 相交。记住这四种机制，就等于记住了本章所有算法。
- 三条性质是唯一评判坐标：安全性（至多一个进程在临界区）绝对不能违反；活性（空闲时请求最终被授予）是系统”活着”的标志；公平性（按 happens-before 授予）是”好”的标志而非”对”的标志。任何算法的正确性证明都必须分别覆盖前两条。
- 打破争用的四种机制与它们的代价一一对应：中央队列最省消息（3 条）但引入单点；唯一令牌最去中心但延迟 $O(N)$ 且令牌会丢；时间戳全序使 RA 的延迟最优（1 RTT / 1 msg）却要 $O(N)$ 消息；quorum 相交把消息降到 $O(\sqrt N)$ 却牺牲公平性与容错，还带进死锁。
- Ricart-Agrawala 的理论地位：它用”每个请求者必须征询全体、每个被征询者必须表态”这一模型下界，达到了 $2(N-1)$ 的最优消息数，同时把客户端延迟与同步延迟都压到 $O(1)$——许可型互斥算法中的效率标杆。它的两个关键细节（$(T_i,i)$ 全序决胜、让路时维持双方互相知情）缺一不可。
- Maekawa 的教训比它的成就更重要：把消息从 $O(N)$ 降到 $O(\sqrt N)$ 完全可行，但投票集相交只保证互斥，不保证进展；死锁必须靠时间戳优先级 + 失败重试（检测与恢复）来消除，而”允许高优先级请求插队”必然削弱公平性。这是”优化一个指标会侵蚀另一个指标”的经典案例。
- 经典算法都假设”进程不失败”；生产系统用共识替代它们：真实锁服务（Chubby/ZooKeeper/etcd）用 Paxos/Raft 复制锁状态、用租约与临时节点处理崩溃释放，代价是多数派与日志落盘。而锁本身从来不是终点——Redlock 之争提醒我们：即使锁的判断正确，也需要 fencing token 之类的机制来防止过期持有者的写入。
- 现实类比收束：许可型像”开会前逐个打电话征求同意”（每次都要打一圈，但能表达先后与优先级）；令牌型像”只有一把钥匙的会议室”（谁拿到钥匙谁进，钥匙靠接力传递）；集中式像”宿管阿姨手里那本登记册”（最省事，但阿姨不在全楼都进不去）；共识型锁服务则像”有五个公证人、必须多数签字才生效的登记处”（贵，但公证人倒下也不会乱）。
14.7 常见陷阱与注意事项
- 用”更新后的 Lamport 时钟”去比较请求优先级
- 为什么错：收到
REQUEST时要先按接收规则更新时钟（clock = max(clock, T_j)+1），如果紧接着拿这个新clock去和请求的时间戳比较，就相当于把自己的请求时间戳抬高到了”看到对方之后”的值，判决结果完全错误（常常表现为”我永远优先”或”我永远让路”）。 - 正确做法：在
WANTED期间用发送请求时记下的my_ts作比较（代码一里的my_ts），时钟更新与优先级比较是两件独立的事。
- 为什么错：收到
- 只用 $T$ 比较，丢掉 $(T, i)$ 的 ID 决胜
- 为什么错：Lamport 时间戳不唯一，并发请求可以取到相同的 $T$；此时”小于”对双方同时为假，两边都走”立即回复”分支 ⇒ 互相发许可 ⇒ 同时进入临界区（14.4.2 的
notie实验稳定复现）。 - 正确做法：一律用词典序 $(T_i, i)$ 比较，得到全序。这不仅是为了互斥，也是死锁避免（最小元存在且唯一）的基础。
- 为什么错：Lamport 时间戳不唯一，并发请求可以取到相同的 $T$；此时”小于”对双方同时为假，两边都走”立即回复”分支 ⇒ 互相发许可 ⇒ 同时进入临界区（14.4.2 的
- 忘记”让对方知道我也在等”（破坏不变式 I）
- 为什么错：延迟回复队列是许可的归还通道。如果对方根本不知道有你这个请求，它退出时不会给你回
REPLY⇒ 你永远等待（违反活性）；若你进一步认为”我让路了就不必再等它的许可”，就会在它仍在临界区时进入（违反安全性）。任何”只问还没回复我的人”“懒发送”之类的省消息优化都会踩这个坑。 - 正确做法：保证每个
WANTED进程的请求最终到达其他所有 $N-1$ 个进程；在”让路”分支里显式地把自己的请求也发给对方，把这条件为不变式来维护（14.3.3 关键细节 2）。
- 为什么错：延迟回复队列是许可的归还通道。如果对方根本不知道有你这个请求，它退出时不会给你回
- 进程做完自己的请求就退出，不再回复别人的
REQUEST- 为什么错：这是一个真实的实现 bug（代码一的开发过程中真的出现过）：最后发起请求的进程会等一个”已经下班”的进程回
REPLY，于是永远阻塞；表现为”大部分进程顺利完成，最后一个卡死”。 - 正确做法：进程的服务循环必须比客户端循环活得久——完成自己的请求后继续处理收件箱、继续裁决他人请求，直到系统整体停机（代码一的
STOP与注释）。
- 为什么错：这是一个真实的实现 bug（代码一的开发过程中真的出现过）：最后发起请求的进程会等一个”已经下班”的进程回
- 把
REPLY当成”永久有效”的许可- 为什么错：
REPLY只对某一次具体请求有效。若不用时间戳匹配（m.ts == my_ts）就累加计数，前一轮残留或重复的REPLY会被错误计入本轮，导致”提前进入”。 - 正确做法：
REPLY携带它所回答的请求时间戳，接收方只在”状态为WANTED且时间戳匹配”时计数；每轮开始（enter()）把计数与延迟队列全部重置。
- 为什么错：
- 认为”投票集相交就万事大吉”，以及”收到 RELEASE 就解锁”
- 为什么错：相交只保证安全性的一半。Maekawa 的等待环可以在任何时间戳组合下存在（14.3.4 的 3 进程反例），因为”等谁”由成员关系决定，而不是由时间戳决定；此外，
RELEASE是广播给退出者的整个投票集的，其中许多进程并没有给它投过票——如果这些进程”收到任何RELEASE就解锁”，就会出现”前一个承诺尚未归还就把票转给别人”的情形，直接违反互斥。 - 正确做法：伪代码里要维护不变式 INV（一票一承诺）——只有发送者等于自己投票对象的
RELEASE才能解除承诺（见 14.3.4 安全性论证的”来源检查”）；同时明确写出”Maekawa 需要额外的死锁检测/恢复机制（超时 +FAILED+ 带更大时间戳重试）；并且它不满足 happens-before 公平性，可能饥饿”。
- 为什么错：相交只保证安全性的一半。Maekawa 的等待环可以在任何时间戳组合下存在（14.3.4 的 3 进程反例），因为”等谁”由成员关系决定，而不是由时间戳决定；此外，
- 以为这些算法能容忍故障，或者以为”加个超时”就万事大吉
- 为什么错：RA 少一个
REPLY就永远进不去；集中式协调者一崩就全停；环里令牌一丢就停滞。异步系统中“慢”与”挂”不可区分，超时只能当启发式，不能作为正确性依据（可能误判一个只是慢的进程为故障，从而违反安全性）。 - 正确做法：需要容错就换工具——用共识（Paxos/Raft）复制的锁服务、租约、临时节点/会话，以及资源侧的 fencing token。
- 为什么错：RA 少一个
- 把”活性”理解成”请求立刻被授予”
- 为什么错：活性的定义是”若临界区空闲，则某个请求最终能进入”，它允许请求者排队等待（互斥本身就意味着等待）。把”等待”当成违反活性会导致错误结论（例如误判集中式或环式”不满足活性”）。
- 正确做法：证明活性时分清”进度（progress）”与”有界等待（bounded wait）”：前者要求”不会所有人都停住”，后者才是”等待时间有上界”。本章里集中式的等待有界（至多 $N-1$ 个临界区），环式也有界（至多 $N-1$ 跳），RA 与 Maekawa 只证明了”最终”。
14.8 思考题（带答案）
题 1（计算与推演） 设 $N = 16$ 个进程，使用矩阵构造的 Maekawa 投票集（把进程排成 $4\times4$ 矩阵，$V_i$ = 所在行 $\cup$ 所在列）。请算出 $\vert V_i\vert = K$ 与每个进程所属的投票集数 $M$，并比较 Ricart-Agrawala 与 Maekawa 每次进入临界区的消息数；再说明为什么 $K$ 不等于 $\sqrt N$。
答：$4\times4$ 矩阵中，$P_i$ 所在行有 4 个进程、所在列有 4 个，交集只有 $P_i$ 自己，故 $K = 4+4-1 = 7 = 2\sqrt N - 1$。每个进程出现在”自己所在的行对应的 4 个投票集 + 自己所在的列对应的 4 个”中，$P_i$ 自己被重复计一次，故 $M = 4+4-1 = 7$。于是 $K = M = 7$，符合 Maekawa 的 $K=M$ 条件。
- Ricart-Agrawala 每次进入 $2(N-1) = 2\times15 = 30$ 条；Maekawa 每次进入 $2K = 14$ 条，退出 $K = 7$ 条，合计 $3K = 21$ 条。Maekawa 省了约 30%。
- 但 $K = 7$ 而 $\sqrt N = 4$，比理论最优值大：理想的最优构造要求 $N = (K-1)K+1$，$K=4$ 时给出 $N = 13$、$K=5$ 时给出 $N=21$，$N=16$ 恰好落在两者之间，无法用射影平面构造出 $K\approx\sqrt N$ 的完美投票集，只能用矩阵构造得到 $2\sqrt N-1$。这说明”$K=M\approx\sqrt N$”是最优性结论，而具体的构造能达到的常数因子取决于 $N$ 是否落在 $(K-1)K+1$ 这些特殊值上（$N=3,7,13,21,31,\dots$）。
题 2（为什么不需要 RELEASE） 集中式与 Maekawa 都需要 RELEASE 消息，Ricart-Agrawala 为什么不需要？请从”许可的语义”角度解释。
答：因为在 RA 中 REPLY 表达的是一个不携带锁的承诺：“我此刻不在临界区；如果我也在请求，那么你的优先级更高，我让你先”。回复者不会因此被”锁住”，因此不需要被显式解锁。真正需要等待的人已经被放进了回复者的 deferred 队列——回复者在 exit() 时只对队列里的请求发 REPLY，这条 REPLY 同时完成了”通知我释放了”和”授予许可”两件事，而它精确地只发给需要知道的人，不必广播。 对照 Maekawa：裁判投出一票后就进入 voted = true 的锁定状态，在收到 RELEASE 之前不能再投票给任何人。锁是被裁判自己持有的状态，所以必须由持锁者主动广播 RELEASE 来解锁（而且必须发给投票集全体，因为裁判可能来自投票集中任何一个成员）。“许可是否在授予者身上留下状态”决定了要不要 RELEASE。
题 3（直观但错误的想法） 有同学提出一个”省消息”的 RA 优化：“收到 REQUEST 后不必回复，一个 RTT 内没有 REPLY 就默认对方同意”（沉默即同意）。这个想法错在哪里？
答：错在把”沉默”当成了”许可”，而沉默在分布式系统中是多义的。收到请求而不回复的进程可能处于三种完全不同的情形：(a) 它处于 HELD（正在临界区）——此时它的沉默绝不能被解释为同意，否则请求者会与它同时进入临界区，直接破坏安全性；(b) 它处于 WANTED 且优先级更高——它本应让请求者等待，沉默却成了许可；(c) 它崩溃了或消息在路上——沉默变成了”对可能已经永久消失的进程的永恒同意”。这一改动同时破坏了安全性与”许可必须显式”的模型假设，并且把异步系统中不可判定的”慢 vs 挂”引入了判决逻辑。 正确做法是保持显式的双向消息：REPLY 必须由对方主动发出，且请求者必须收齐 $N-1$ 个；这也正是 $2(N-1)$ 下界成立的原因——沉默无法承载信息。
题 4（应用与辨析） 你要为一个跨数据中心的配置服务实现”写配置前先加锁”。请说明：为什么直接用 Ricart-Agrawala 不合适？Chubby/ZooKeeper/etcd 这类服务是怎么做的？如果客户端在持锁期间被 JVM 长 GC 暂停了 30 秒，会发生什么，工程上如何补救？
答：
- RA 不合适的原因：(1) 它假设进程不失败，而数据中心的进程、网络、机器随时会失败，任一进程崩溃会让所有竞争者永久阻塞；(2) 它不提供复制与持久化——锁的状态只存在于各进程的内存里，进程重启后时间戳与等待状态全部丢失；(3) 它没有”锁泄漏”的处理机制，客户端拿到锁后崩溃，别人只能永远等；(4) 每加一次锁要 $2(N-1)$ 条消息，跨数据中心还要承受广域 RTT，$N$ 大时完全不可扩展。
- 工程做法：用基于共识的协调服务。Chubby 用 Paxos 类协议把锁状态复制到一组服务器上，写请求必须获得多数派确认，Leader 失败则重新选举；ZooKeeper 用 ZAB 共识 + 顺序临时节点/监视器；etcd 用 Raft + 租约。加锁 = 一次共识提交，因此锁状态在多数派上持久化，Leader 切换也不会丢。
- 30 秒 GC 暂停的后果：客户端的租约（lease）会在暂停期间到期，锁被服务端判定为已释放并授予其他客户端；而暂停结束的旧持有者并不知道自己已经失去了锁，它可能继续写入 ⇒ 两个客户端同时写同一份配置，互斥在”应用层”名义上成立但在数据层被破坏。
- 补救措施：(a) fencing token（栅栏令牌）：锁服务在每次授予时返回全局单调递增的编号，客户端每次写入都带上它，存储侧记住见过的最大编号并拒绝更小的编号——即使旧持有者迟到，它的写也会被丢弃；(b) 缩短租约并配合续租（心跳），让”暂停超过租约”更容易被发现；(c) 把写路径做成幂等 + 版本号检查（compare-and-set），避免”迟到的写”覆盖新值。核心认识：分布式锁只解决”进入临界区”，不能解决”持锁者的写入是否还有效”——后者需要 fencing 或 CAS 这类资源侧保护。