并行与分布式系统中的分布式互斥算法：Suzuki-Kasami广播算法 分布式互斥是指多个节点在分布式系统中竞争访问共享资源时，确保任意时刻至多一个节点能进入临界区的机制。Suzuki-Kasami广播算法是一种基于令牌的分布式互斥算法，它通过传递一个特殊的令牌来保证互斥，同时通过广播请求减少令牌传递的延迟。算法的核心思想是：持有令牌的节点可直接进入临界区；无令牌的节点需广播请求，等待令牌持有者按规则传递令牌。 1. 算法背景与问题定义 场景 ：在无中心节点的分布式系统中，多个节点需要互斥地访问共享资源（如打印机、共享文件）。 目标 ： 安全性 ：任意时刻至多一个节点在临界区内。 活性 ：请求临界区的节点最终能进入。 公平性 ：避免饥饿，请求应按一定顺序被满足。 挑战 ：无全局时钟，消息传递存在延迟，节点可能故障。 2. 算法核心概念 算法依赖两类对象： 令牌（Token） ：一个特殊的消息，持有令牌的节点有权进入临界区。令牌中维护一个序列号数组 LN[1..N] （记录每个节点最近一次获得令牌时自身的请求号）和一个队列 Q （等待令牌的节点列表）。 请求消息（Request） ：节点在需要进入临界区时广播的消息，包含节点ID和自增的请求号。 每个节点维护以下局部变量： RN[i] ：数组，记录节点已知的节点 i 的最新请求号（初始为0）。 令牌持有状态：标记自己是否持有令牌。 3. 算法详细步骤 步骤1：节点请求进入临界区 当节点 i 想进入临界区时： 递增局部变量 RN[i] （表示自己发起新请求）。 广播请求消息 REQUEST(i, RN[i]) 给所有其他节点。 等待获取令牌。 步骤2：其他节点收到请求消息 节点 j 收到 REQUEST(i, sn) 时： 更新 RN[j][i] = max(RN[j][i], sn) 。 如果节点 j 当前持有令牌，且令牌未被使用（即不在临界区），且满足传递条件（见步骤3），则立即将令牌发送给节点 i 。 步骤3：令牌持有者传递令牌的规则 设当前令牌持有者为节点 k ，令牌中包含： LN[1..N] ：记录上次传递令牌时各节点的请求号。 Q ：等待队列。 传递条件：当令牌空闲（未被用于进入临界区）时，检查是否有其他节点在请求： 对任意节点 i ，如果 RN[k][i] = LN[i] + 1 ，说明节点 i 有新请求但未记录在令牌中，则将 i 加入令牌队列 Q 。 如果队列 Q 非空，从队首取出节点 m ，将令牌发送给 m ，并更新 LN[m] = RN[k][m] 。 步骤4：节点进入临界区与退出 节点收到令牌后： 用令牌中的 LN 更新自己的 RN （同步全局请求信息）。 进入临界区执行操作。 退出临界区时： 更新令牌中的 LN[i] = RN[i] （记录自己已满足请求）。 检查令牌队列 Q ，若有等待节点，按步骤3传递令牌；否则保留令牌。 4. 关键机制与正确性分析 互斥保证 ：令牌唯一，只有持令牌者可进入临界区。 避免饥饿 ：请求按队列 Q 顺序满足，且请求号机制确保不会遗漏请求。 消息复杂度 ： 每次请求广播 N-1 条消息（ N 为节点数）。 令牌传递需1条消息。 最坏情况下每次进入临界区需 O(N) 条消息，优于某些轮询算法。 5. 示例演示 假设3个节点（0,1,2），初始令牌在节点0。 节点1请求进入临界区： 更新 RN[1][1]=1 ，广播 REQUEST(1,1) 。 节点0收到后更新 RN[0][1]=1 ，发现 RN[0][1] = LN[1]+1 ，将节点1加入令牌队列 Q 。 节点0传递令牌给节点1，更新 LN[1]=1 。 节点1持令牌进入临界区，退出时队列为空，保留令牌。 若节点0和节点2同时请求，请求号更高的节点可能先入队列（取决于接收顺序），但最终按队列顺序获取令牌。 6. 算法优化与局限 优化方向 ： 令牌可携带更多状态以减少广播（如记录最近请求的节点）。 使用物理时钟戳辅助排序请求（但算法本身不需要时钟同步）。 局限 ： 广播开销随节点数增加。 令牌丢失需容错机制（如超时重新生成）。 不适合大规模动态拓扑。 7. 总结 Suzuki-Kasami算法通过 令牌传递+广播请求 平衡了消息开销与公平性，是经典的分布式互斥解决方案。其核心在于利用令牌中的 LN 数组和请求号检测未处理的请求，确保活性。实际应用中需结合故障检测（如心跳）增强鲁棒性。