20.4 令牌环互斥

一句话

令牌环用 “环上只有一个令牌” 保证互斥：拿到令牌才能进临界区，用完传给下一个；消息量 O(1)，但延迟 O(N)——它的全部难点不在算法，而在环的维护（加入、离开、令牌丢失）。

节点按环排列：A → B → C → D → A
令牌在环上单向传递；持有者进临界区，用完后把令牌传给后继。

“重新生成令牌” 是最危险的操作：若旧令牌还活着，就会出现双令牌 = 双进入。所以重建必须由唯一权威（leader）执行，并配合 fencing。

若每跳 1ms，N=500 时平均等待 250ms——对高频互斥不可接受。

同一套模拟（每次进入 = 令牌传递一圈中的一段）：

若每跳 1ms，N=50 时平均要等 25ms 才能进入临界区——对 “每秒上万次加锁” 的场景完全不可用；但对 “每分钟几次” 的仲裁类操作（选主、配额分配）完全够用。

总跳数 = N × 进入次数        平均等待 = N / 2 跳
N=50、进入 10 次 → 500 跳，平均等 25 跳

🔑 单令牌是互斥的全部；任何 “可能有第二个令牌” 的实现都是错的。

🔑 令牌重建必须唯一权威，并配 fencing。

🔑 环适合 “低竞争、成员稳定”；规模大或竞争高时换方案。

Q1 令牌丢了怎么办？为什么不能随便重建？

▸ 答案：需要超时检测 + 唯一重建者。随便重建的风险是 “旧令牌仍在环上”：两个令牌同时存在 → 两个节点同时进临界区，互斥被破坏。所以重建要选一个权威（leader/最小 ID），并给令牌带单调版本号。

Q2 为什么令牌环的延迟是 O(N)？

▸ 答案：因为令牌只能沿环逐跳传递，一个节点想进入必须等令牌转一圈到达自己。平均要等 N/2 个节点各持有一段时间，最坏 N 个。规模越大，等待越久——这是拓扑决定的，不是实现问题。

Q3 令牌环与集中式互斥相比，优势在哪？

▸ 答案：没有中心单点，且天然公平轮转、消息量小（每次 1 条）。适合 “节点数少、竞争不激烈、希望严格轮流” 的场景（如总线仲裁、某些硬件/实时系统）。代价是容错差、延迟随 N 增长。

Q4 节点 “假死”（进程卡住但网络通）会怎样？

▸ 答案：令牌被它扣住，环停摆。需要租约式令牌：令牌带有效期，超时未传递则由后继发起 “跳过该节点” 的流程；但这又需要成员视图与防双令牌机制。

Q5 工程上还有哪些系统用类似令牌的思路？

▸ 答案：租约/令牌广泛用于选主（leader 持有租约）、限流（令牌桶）、以及某些分布式锁（带 TTL 的锁本质是 “时间受限的令牌”）。思路一致：用一个可验证的凭证把并发变成串行。

Q7 令牌环的 “消息少” 与 “延迟高” 为什么能同时成立？

▸ 答案：因为 “消息数” 与 “延迟” 是两个维度：每次进入只传 1 条令牌（消息少），但令牌要沿环逐跳走到你这里（延迟 O(N)）。而 RA 是 “一次广播”（消息多、延迟 1 RTT）。所以令牌环适合 “节点少、竞争低、要求严格轮流”，不适合 “高频、大规模”。

Q6 令牌环的 “严格轮转” 会不会让热门节点总是等很久？

▸ 答案：会——轮转是按位置而不是按需求分配的，热点节点每次都要等令牌转一圈。这是 “公平” 的另一面：它保证没人被饿死，但不保证高需求方获得更多机会。高竞争场景应换成集中式（按队列）或按权重分配。

Q7 如果环上节点数动态变化，令牌环还成立吗？

▸ 答案：能成立，但复杂度会跳一个量级：需要成员视图（谁在环上）、加入/离开协议（前驱改指向）、令牌重建（唯一权威 + 版本号）。很多实现最终退化成 “用共识维护环成员”，那时令牌环的优势（消息少）已被成员管理的开销抵消。