Jump to content

Chandy–Misra–Haas algorithm resource model

From Wikipedia, the free encyclopedia

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

[edit]

Consider the n processes P1, P2, P3, P4, P5,, ... ,Pn which are performed in a single system (controller). P1 is locally dependent on Pn, if P1 depends on P2, P2 on P3, so on and Pn−1 on Pn. That is, if , then is locally dependent on . If P1 is said to be locally dependent to itself if it is locally dependent on Pn and Pn depends on P1: i.e. if , then is locally dependent on itself.

Description

[edit]

The algorithm uses a message called probe(i,j,k) to transfer a message from controller of process Pj to controller of process Pk. It specifies a message started by process Pi to find whether a deadlock has occurred or not. Every process Pj 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

[edit]

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

Controller receiving a probe

[edit]

On the receiving side, the controller checks whether Pk is performing a task. If so, it neglects the probe. Otherwise, it checks the responses given Pk to Pj and dependentk(i) is false. Once it is verified, it assigns true to dependentk(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

[edit]

In pseudocode, the algorithm works as follows:[1]

Controller sending a probe

[edit]
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

[edit]
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

[edit]
occurrence of deadlock in distributed system

P1 initiates deadlock detection. C1 sends the probe saying P2 depends on P3. Once the message is received by C2, it checks whether P3 is idle. P3 is idle because it is locally dependent on P4 and updates dependent3(2) to True.

As above, C2 sends probe to C3 and C3 sends probe to C1. At C1, P1 is idle so it update dependent1(1) to True. Therefore, deadlock can be declared.

Complexity

[edit]

Suppose there are controllers and processes, at most messages need to be exchanged to detect a deadlock, with a delay of messages.[2]

References

[edit]
  1. ^ Chandy, K. M.; Misra, J.; Haas, L. M. (1983). "Distributed deadlock detection". ACM Transactions on Computer Systems. 1 (2): 144. doi:10.1145/357360.357365. S2CID 9147318.
  2. ^ Kshemkalyani, Ajay; Singhal, Mukesh. "Deadlock Detection in Distributed Systems" (PDF). Retrieved 2024-04-08.