Chandy Misra Haas algorithm resource model

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. P₁ is said to be locally dependent to itself if it is locally dependent on P_n and P_n depends on P₁.

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 P_j is locally dependent on itself then declare deadlock else for all P_j,P_k such that (i) P_i is locally dependent on P_j, (ii) P_j is waiting for 'P_k and (iii) P_j, P_k are on different controllers. send probe(i, j, k).

Controller receiving a probe

if (i)P_k is idle, (ii) dependent_k(i) = false, and (iii)requests responded by P_k to P_jthen begin "dependents"_"k"(i) = true; if k == i then declare that P_i is deadlocked else for all P_a,P_b such that (i) P_k is locally dependent on P_a, (ii) P_a is waiting for 'P_b and (iii) P_a, P_b are on different controllers. send probe(i, a, b). end

Example

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).