Chandy misra

 

Formal Definition:

The Chandy-Misra-Haas Algorithm is a distributed deadlock detection algorithm designed for message-passing systems. It provides methods to detect deadlocks in both the AND model (where a process waits for all requested resources) and the OR model (where a process waits for any one of several requested resources).

  • In the AND model, the algorithm is based on edge-chasing, where a special control message called a probe(i, j, k) is circulated along the edges of the wait-for graph. A deadlock is detected when the probe message returns to its initiating process, indicating the existence of a cycle in the global wait-for graph.

  • In the OR model, the algorithm is based on diffusion computation, where two types of messages, query(i, j, k) and reply(i, j, k), are exchanged among blocked processes in the dependent set. A deadlock is detected when the initiator process receives reply messages corresponding to all queries it initiated, showing a knot in the wait-for graph.

Thus, the Chandy-Misra-Haas algorithm formally defines a systematic message-passing mechanism to detect cycles or knots in a distributed wait-for graph, thereby identifying deadlocks without constructing a global state explicitly.


Chandy-Misra-Haas Distributed Deadlock Detection Algorithm

The Chandy-Misra-Haas (CMH) algorithm is one of the most important distributed deadlock detection algorithms. It has two models: AND model (edge-chasing approach) and OR model (diffusion-computation approach).

1. AND Model (Edge-Chasing Algorithm)

  • The algorithm uses a special message called probe(i, j, k) where:

    • i = initiator (blocked process that starts detection)
    • j = process sending the probe
    • k = process receiving the probe

  • A deadlock is detected if the probe returns to its initiator.

  • Dependence Rules:

    • Process Pj is dependent on Pk if there exists a chain of blocked processes leading from Pj to Pk.
    • Pj is locally dependent on Pk if they are on the same site.

  • Data Structure:

    • Each process Pi maintains a boolean array dependenti(j), initially false.
    • dependenti(j) = true if Pi knows Pj depends on it.

  • Algorithm Steps:

    1. If a process Pi is locally dependent on itself → deadlock declared.
    2. Otherwise, for every dependency chain (Pi → Pj → Pk) where Pj and Pk are on different sites, Pi sends probe(i, j, k) to the home site of Pk.
    3. When Pk receives a probe(i, j, k), it checks:
      • If Pk is blocked,
      • dependentk(i) = false,
      • Pk has not replied to all requests of Pj,
      • Then set dependentk(i) = true.
        • If k = i → deadlock detected.
        • Else propagate probe(i, m, n) further along dependencies.

  • Performance:

    • At most m(n-1)/2 messages for a deadlock involving m processes over n sites.
    • Message size: 3 words.
    • Deadlock detection delay: O(n).

  • Advantages:

    • Easy to implement, fixed-size messages, low overhead.
    • No need for global graph construction.
    • No false deadlocks.

2. OR Model (Diffusion-Based Algorithm)

  • Based on diffusion computation.

  • Uses two types of messages:

    • query(i, j, k) – sent during deadlock detection initiated by Pi.
    • reply(i, j, k) – response to query.

  • Algorithm Steps:

    1. A blocked process Pi initiates detection by sending query(i, i, j) to all processes Pj in its dependent set (DSi).
      • It sets num(i) = |DSi| and waiti(i) = true.
    2. When a blocked process Pk receives query(i, j, k):
      • If it is the first query (engaging query), it propagates queries to all processes in its dependent set and sets numk(i) accordingly.
      • If not the first query, and waitk(i) = true, it sends a reply(i, k, j) back to Pj. Otherwise, discards it.
    3. When Pk receives a reply(i, j, k):
      • If waitk(i) = true, decrement numk(i).
      • If numk(i) = 0:
        • If k = i → deadlock detected.
        • Else send reply back to the process that sent the engaging query.

  • Performance:

    • For each deadlock detection, at most e query and e reply messages are exchanged, where e = number of edges in the wait-for graph.

3. Deadlock Resolution

  • After detection, resolution is done by aborting one or more processes.
  • Priority-based resolution can be used:
    • Highest priority process detects deadlock,
    • Lowest priority process is aborted.
  • Aborted process releases all resources, and the system resumes normally.