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''_''1'', ''P''_''2'', ''P''_''3'', ''P''_''4'', ''P''_''5,'', ... ,''P''_''n'' which are performed in a single system (controller). ''P''_''1'' is locally dependent on ''P''_''n'', if ''P''_''1'' depends on ''P''_''2'', ''P''_''2'' on ''P''_''3,'' so on and ''P''_''n−1'' on ''P''_''n''. That is, if $P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow \ldots \rightarrow P_n$, then $P_1$ is locally dependent on $P_n$. If ''P''_''1'' is said to be locally dependent to itself if it is locally dependent on ''P''_''n'' and ''P''_''n'' depends on ''P''_''1'': i.e. if $P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow \ldots \rightarrow P_n \rightarrow P_1$, then $P_1$ 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 ''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). to home site of ''P''_''k''

Controller receiving a probe

if
(i)''P''_''k'' is idle / blocked
(ii) ''dependent''_''k''(i) = false, and
(iii) ''P''_''k'' has not replied to all requests of to ''P''_''j''
then 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). to home site of ''P''_''b''
end

Example

''P''_''1'' initiates deadlock detection. ''C''_''1'' sends the probe saying ''P''_''2'' depends on ''P''_''3''. Once the message is received by ''C''_''2'', it checks whether ''P''_''3'' is idle. ''P''_''3'' is idle because it is locally dependent on ''P''_''4'' and updates ''dependent''_''3''(2) to True.

As above, ''C''_''2'' sends probe to ''C''_''3'' and ''C''_''3'' sends probe to ''C''_''1''. At ''C''_''1'', ''P''_''1'' is idle so it update ''dependent''_''1''(1) to True. Therefore, deadlock can be declared.

Complexity

Suppose there are $n$ controllers and $m$ processes, at most $m(n-1)/2$ messages need to be exchanged to detect a deadlock, with a delay of $O(n)$ messages.

References

{{DEFAULTSORT:Chandy-Misra-Haas algorithm resource model
Algorithms