Chandy–Misra–Haas algorithm resource model

The Chandy–Misra–Haas algorithm resource model checks for deadlock in a distributed system. It was developed by K. Mani Chandy, Jayadev Misra and Laura M Haas.

Locally dependent

Consider the n processes P₁, P₂, P₃, P₄, P_5,, ... ,P_n which are performed in a single system (controller). P₁ is locally dependent on P_n, if P₁ depends on P₂, P₂ on P_3, so on and P_n−1 on P_n. That is, if [math]\displaystyle{ P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow \ldots \rightarrow P_n }[/math], then [math]\displaystyle{ P_1 }[/math] is locally dependent on [math]\displaystyle{ P_n }[/math]. If P₁ is said to be locally dependent to itself if it is locally dependent on P_n and P_n depends on P₁: i.e. if [math]\displaystyle{ P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow \ldots \rightarrow P_n \rightarrow P_1 }[/math], then [math]\displaystyle{ P_1 }[/math] is locally dependent on itself.

Description

The algorithm uses a message called probe(i,j,k) to transfer a message from controller of process P_j to controller of process P_k. It specifies a message started by process P_i to find whether a deadlock has occurred or not. Every process P_j maintains a boolean array dependent which contains the information about the processes that depend on it. Initially the values of each array are all "false".

Controller sending a probe

Before sending, the probe checks whether P_j is locally dependent on itself. If so, a deadlock occurs. Otherwise it checks whether P_j, and P_k are in different controllers, are locally dependent and P_j is waiting for the resource that is locked by P_k. Once all the conditions are satisfied it sends the probe.

Controller receiving a probe

On the receiving side, the controller checks whether P_k is performing a task. If so, it neglects the probe. Otherwise, it checks the responses given P_k to P_j and dependent_k(i) is false. Once it is verified, it assigns true to dependent_k(i). Then it checks whether k is equal to i. If both are equal, a deadlock occurs, otherwise it sends the probe to next dependent process.

Algorithm

In pseudocode, the algorithm works as follows:

Controller sending a probe

if Pj is locally dependent on itself
    then declare deadlock
else for all Pj,Pk  such that
    (i) Pi is locally dependent on Pj,
    (ii) Pj is waiting for 'Pk and
    (iii) Pj, Pk are on different controllers.
send probe(i, j, k). to home site of Pk

Controller receiving a probe

if
    (i)Pk is idle / blocked
    (ii) dependentk(i) = false, and
    (iii) Pk has not replied to all requests of to Pj
then begin
    "dependents""k"(i) = true;
    if k == i
    then declare that Pi is deadlocked
    else for all Pa,Pb such that
        (i) Pk is locally dependent on Pa,
        (ii) Pa is waiting for 'Pb and
        (iii) Pa, Pb are on different controllers.
    send probe(i, a, b). to home site of Pb 
end

Example

occurrence of deadlock in distributed system

P₁ initiates deadlock detection. C₁ sends the probe saying P₂ depends on P₃. Once the message is received by C₂, it checks whether P₃ is idle. P₃ is idle because it is locally dependent on P₄ and updates dependent₃(2) to True.

As above, C₂ sends probe to C₃ and C₃ sends probe to C₁. At C₁, P₁ is idle so it update dependent₁(1) to True. Therefore, deadlock can be declared.

Complexity

Consider that there are "m" controllers and "p" process to perform, to declare whether a deadlock has occurred or not, the worst case for controllers and processes must be visited. Therefore, the solution is O(m+p). The time complexity is O(n).