并行与分布式系统中的死锁检测：Chandy-Misra-Haas算法
字数 1677 2025-10-27 08:13:40

并行与分布式系统中的死锁检测：Chandy-Misra-Haas算法

题目描述
在分布式系统中，多个进程可能因竞争资源陷入死锁（例如进程A持有资源R1并等待R2，进程B持有R2并等待R1）。Chandy-Misra-Haas算法是一种基于资源分配图（Resource Allocation Graph, RAG）的分布式死锁检测方法，适用于每个资源仅能被单个进程独占的场景。算法通过进程间传递特殊消息（如探测消息）来检测是否存在循环等待条件，从而判断死锁是否发生。

解题过程循序渐进讲解

1. 资源分配图（RAG）建模

  • 节点类型：
    • 进程节点（P₁, P₂, ...）
    • 资源节点（R₁, R₂, ...）
  • 有向边：
    • 请求边（Pᵢ → Rⱼ）：表示进程Pᵢ正在等待资源Rⱼ。
    • 分配边（Rⱼ → Pᵢ）：表示资源Rⱼ已分配给进程Pᵢ。
  • 关键假设：
    • 每个资源只有单个实例（如一台打印机）。
    • 边是单向的，且资源分配后才会产生依赖关系。

示例：
假设系统中有两个进程P₁、P₂和两个资源R₁、R₂：

  • P₁持有R₁，但等待R₂（即R₁→P₁，P₁→R₂）。
  • P₂持有R₂，但等待R₁（即R₂→P₂，P₂→R₁）。
    此时资源分配图中存在循环P₁→R₂→P₂→R₁→P₁，系统死锁。

2. 算法核心思想：扩散式探测

Chandy-Misra-Haas算法通过探测消息（probe）在进程中传递，检测循环等待：

  • 触发条件：当进程Pᵢ因等待资源Rⱼ被阻塞时，Pᵢ向Rⱼ的当前持有者发送探测消息。
  • 消息格式：probe(Pᵢ, Pⱼ, Rⱼ)，表示“Pᵢ正在等待被Pⱼ持有的资源Rⱼ”。
  • 传递规则：
    1. 若进程Pⱼ收到probe(Pᵢ, Pⱼ, Rⱼ)，且Pⱼ自身也在等待其他资源，则Pⱼ将消息转发给所有它正在等待的资源持有者。
    2. 若某进程收到一条探测消息，且消息中的初始发起者（Pᵢ）与自己相同，说明检测到循环等待，死锁发生。

3. 算法步骤详解

步骤1：初始化

  • 每个进程维护一个依赖表，记录当前等待关系和已发送的探测消息。
  • 初始时无探测消息传递。

步骤2：发送探测消息

  • 当进程Pᵢ被阻塞（因请求资源Rⱼ未立即满足）：
    • Pᵢ向Rⱼ的当前持有者Pⱼ发送probe(Pᵢ, Pⱼ, Rⱼ)。
    • Pᵢ将本次探测记录在本地，避免重复发送。

步骤3：转发探测消息

  • 进程Pⱼ收到probe(Pᵢ, Pⱼ, Rⱼ)后：
    • 若Pⱼ未被阻塞（未等待任何资源），则忽略该消息（无死锁风险）。
    • 若Pⱼ也被阻塞（例如在等待资源Rₖ），则Pⱼ向Rₖ的持有者Pₗ转发probe(Pᵢ, Pₗ, Rₖ)。
    • 注意：消息中的初始发起者Pᵢ保持不变，但中间进程和资源字段更新。

步骤4：检测死锁

  • 若进程Pᵢ收到一条probe(Pᵢ, Pᵢ, Rₘ)（即发起者与接收者相同），说明存在Pᵢ→...→Pᵢ的循环，死锁被确认。
  • 此时系统可触发死锁处理机制（如终止进程或回滚）。

4. 实例演示

假设系统中有三个进程P₁、P₂、P₃和资源R₁、R₂、R₃：

  • P₁持有R₁，等待R₂。
  • P₂持有R₂，等待R₃。
  • P₃持有R₃，等待R₁。

死锁检测过程：

  1. P₁因等待R₂被阻塞，向R₂的持有者P₂发送probe(P₁, P₂, R₂)。
  2. P₂收到消息后，因自己也在等待R₃，向R₃的持有者P₃转发probe(P₁, P₃, R₃)。
  3. P₃收到消息后，因自己也在等待R₁，向R₁的持有者P₁转发probe(P₁, P₁, R₁)。
  4. P₁收到probe(P₁, P₁, R₁)，发现发起者是自身，死锁确认。

5. 算法特性与注意事项

  • 假阳性问题：算法可能因消息延迟或并发操作误报死锁（但不会漏报）。
  • 复杂度：消息数量在最坏情况下为O(|E|)（E为RAG中的边数）。
  • 局限性：仅适用于单实例资源，多实例资源需使用其他算法（如银行家算法）。

通过以上步骤，Chandy-Misra-Haas算法以分布式方式高效检测死锁，无需全局状态同步，适合大规模系统。

并行与分布式系统中的死锁检测：Chandy-Misra-Haas算法 题目描述 在分布式系统中，多个进程可能因竞争资源陷入死锁（例如进程A持有资源R1并等待R2，进程B持有R2并等待R1）。Chandy-Misra-Haas算法是一种基于 资源分配图（Resource Allocation Graph, RAG） 的分布式死锁检测方法，适用于每个资源仅能被单个进程独占的场景。算法通过进程间传递特殊消息（如探测消息）来检测是否存在循环等待条件，从而判断死锁是否发生。 解题过程循序渐进讲解 1. 资源分配图（RAG）建模 节点类型 ： 进程节点 （P₁, P₂, ...） 资源节点 （R₁, R₂, ...） 有向边 ： 请求边 （Pᵢ → Rⱼ）：表示进程Pᵢ正在等待资源Rⱼ。 分配边 （Rⱼ → Pᵢ）：表示资源Rⱼ已分配给进程Pᵢ。 关键假设 ： 每个资源只有单个实例（如一台打印机）。 边是单向的，且资源分配后才会产生依赖关系。 示例 ： 假设系统中有两个进程P₁、P₂和两个资源R₁、R₂： P₁持有R₁，但等待R₂（即R₁→P₁，P₁→R₂）。 P₂持有R₂，但等待R₁（即R₂→P₂，P₂→R₁）。 此时资源分配图中存在循环P₁→R₂→P₂→R₁→P₁，系统死锁。 2. 算法核心思想：扩散式探测 Chandy-Misra-Haas算法通过 探测消息（probe） 在进程中传递，检测循环等待： 触发条件 ：当进程Pᵢ因等待资源Rⱼ被阻塞时，Pᵢ向Rⱼ的当前持有者发送探测消息。 消息格式 ： probe(Pᵢ, Pⱼ, Rⱼ) ，表示“Pᵢ正在等待被Pⱼ持有的资源Rⱼ”。 传递规则 ： 若进程Pⱼ收到 probe(Pᵢ, Pⱼ, Rⱼ) ，且Pⱼ自身也在等待其他资源，则Pⱼ将消息转发给所有它正在等待的资源持有者。 若某进程收到一条探测消息，且消息中的初始发起者（Pᵢ）与自己相同，说明检测到循环等待，死锁发生。 3. 算法步骤详解 步骤1：初始化 每个进程维护一个 依赖表 ，记录当前等待关系和已发送的探测消息。 初始时无探测消息传递。 步骤2：发送探测消息 当进程Pᵢ被阻塞（因请求资源Rⱼ未立即满足）： Pᵢ向Rⱼ的当前持有者Pⱼ发送 probe(Pᵢ, Pⱼ, Rⱼ) 。 Pᵢ将本次探测记录在本地，避免重复发送。 步骤3：转发探测消息 进程Pⱼ收到 probe(Pᵢ, Pⱼ, Rⱼ) 后： 若Pⱼ未被阻塞（未等待任何资源），则忽略该消息（无死锁风险）。 若Pⱼ也被阻塞（例如在等待资源Rₖ），则Pⱼ向Rₖ的持有者Pₗ转发 probe(Pᵢ, Pₗ, Rₖ) 。 注意：消息中的初始发起者Pᵢ保持不变，但中间进程和资源字段更新。 步骤4：检测死锁 若进程Pᵢ收到一条 probe(Pᵢ, Pᵢ, Rₘ) （即发起者与接收者相同），说明存在Pᵢ→...→Pᵢ的循环，死锁被确认。 此时系统可触发死锁处理机制（如终止进程或回滚）。 4. 实例演示 假设系统中有三个进程P₁、P₂、P₃和资源R₁、R₂、R₃： P₁持有R₁，等待R₂。 P₂持有R₂，等待R₃。 P₃持有R₃，等待R₁。 死锁检测过程 ： P₁因等待R₂被阻塞，向R₂的持有者P₂发送 probe(P₁, P₂, R₂) 。 P₂收到消息后，因自己也在等待R₃，向R₃的持有者P₃转发 probe(P₁, P₃, R₃) 。 P₃收到消息后，因自己也在等待R₁，向R₁的持有者P₁转发 probe(P₁, P₁, R₁) 。 P₁收到 probe(P₁, P₁, R₁) ，发现发起者是自身，死锁确认。 5. 算法特性与注意事项 假阳性问题 ：算法可能因消息延迟或并发操作误报死锁（但不会漏报）。 复杂度 ：消息数量在最坏情况下为O(|E|)（E为RAG中的边数）。 局限性 ：仅适用于单实例资源，多实例资源需使用其他算法（如银行家算法）。 通过以上步骤，Chandy-Misra-Haas算法以分布式方式高效检测死锁，无需全局状态同步，适合大规模系统。