01-08-2012, 04:07 PM
Edge Chasing Deadlock Detection Algorithm
Edge chasing deadlock detection.pptx (Size: 281.74 KB / Downloads: 29)
Introduction:
This is fully distributed deadlock detection algorithm is given by Chandy, Misra, and Hass .This is considered an edge-chasing, probe-based algorithm.
PROBE - a special message which is a triplet(i,j,k) denoting that it belongs to a deadlock detection initiated for process Pi and it is being sent by the home site of process Pj to the home site of process Pk along the edge of TWF(Transaction -Wait -For Graph).
If a process makes a request for a resource which fails or times out, the process generates a probe message and sends it to each of the processes holding one or more of its requested resources.
INITIATION:
A probe message(i, j, k) belongs to deadlock detection initiated for process Pi and it is being sent by home site of process Pj to the home site of process Pk .
DETECTION:
Detection consists of receiving probes and deciding whether deadlock has occurred and whether to forward the probes.
when a server adds a new edge, it checks whether a cycle is there.
RESOLUTION:
When a cycle is detected, a transaction in the cycle is aborted to break the deadlock.
IN PREVIOUS EXAMPLE:
If process P1 initiates deadlock detection, it sends probe (1, 3, 4) to S2.
Since P6 is waiting for p8 and p7 is waiting for P10, S2 sends probes (1, 6, 8) and (1, 7, 10) to S3 which in turn sends probe (1, 9, 1) to S1.
On receiving probe (1, 9, 1), S1 declares that P1 is deadlocked.
Conclusion:
As the number of processes increase, the number of messages exchanged increase in the same order to detect a deadlock.
But if the number of initiators increase, The number of messages exchanged to detect a deadlock for each of these initiators increase significantly.
Message complexity and time complexity increase significantly with the number of initiators.