并行与分布式系统中的分布式死锁检测：全局等待图（Global Wait-for Graph）算法 题目描述 在分布式系统中，多个进程可能因竞争资源而形成循环等待，导致死锁。全局等待图（Global Wait-for Graph, GWG）算法是一种集中式死锁检测方法，通过维护一个全局资源等待图（包含所有进程和资源节点）来识别循环等待。挑战在于如何高效收集分布式节点的局部等待信息，并保证检测的准确性。假设系统由多个节点组成，每个节点维护本地进程和资源的等待关系，一个协调者（或检测器）负责聚合局部信息并判断全局死锁。 解题过程 问题建模 将系统抽象为有向图：节点包括进程（P）和资源（R），边表示等待关系。例如，边 \(P_ i \to R_ j\) 表示进程 \(P_ i\) 等待资源 \(R_ j\)，边 \(R_ j \to P_ k\) 表示资源 \(R_ j\) 被进程 \(P_ k\) 持有。 死锁存在的充要条件：图中存在环。 局部等待图（LWG）构建 每个节点维护自己的局部等待图，仅包含该节点上的进程和资源（如本地内存块或文件锁）。 示例：节点A的LWG中，若进程 \(P_ 1\) 等待资源 \(R_ 2\)（被 \(P_ 3\) 持有），则存在边 \(P_ 1 \to R_ 2\) 和 \(R_ 2 \to P_ 3\)。 信息收集阶段 协调者定期向所有节点发送请求，要求上报其LWG。 节点将LWG编码为消息（如边列表），发送给协调者。 关键细节 ：消息需包含跨节点依赖。例如，若节点A的进程 \(P_ 1\) 等待节点B的资源 \(R_ 2\)，则节点A的LWG中需包含 \(P_ 1 \to R_ 2\)，且节点B的LWG需包含 \(R_ 2\) 的持有者信息（如 \(R_ 2 \to P_ 3\)）。 全局等待图（GWG）聚合 协调者收到所有LWG后，合并边和节点，构建全局图。 合并时需去重：同一进程或资源在不同LWG中可能出现，需通过唯一标识符（如IP地址+本地ID）合并。 示例：节点A报告 \(P_ 1 \to R_ 2\)，节点B报告 \(R_ 2 \to P_ 3\)，合并后得到路径 \(P_ 1 \to R_ 2 \to P_ 3\)。 环检测算法 协调者对GWG执行深度优先搜索（DFS）或拓扑排序，检测环。 优化 ：使用Tarjan强连通分量算法，高效找出所有环。 若发现环，则判定死锁存在，并识别环中的进程和资源。 死锁处理 协调者通知相关节点终止环中的一个或多个进程（或回滚操作），解除死锁。 挑战 ：需避免误判（如因消息延迟导致过时LWG）。可通过时间戳或版本号确保信息新鲜度。 实例说明 假设系统有两个节点： 节点1：进程 \(P_ 1\) 持有资源 \(R_ 1\)，等待 \(R_ 2\)（位于节点2）。 节点2：进程 \(P_ 2\) 持有资源 \(R_ 2\)，等待 \(R_ 1\)。 协调者收集LWG后，合并得到环 \(P_ 1 \to R_ 2 \to P_ 2 \to R_ 1 \to P_ 1\)，确认为死锁。 总结 GWG算法通过集中式环检测实现死锁发现，适合中小规模系统。局限性在于协调者可能成为瓶颈，且依赖全局信息同步。后续改进可引入分层检测或分布式环搜索（如边追踪算法）。