Mumbai University > Information Technology > Sem 6 > Distributed System

Marks: 10 Marks

Year: May 2016

Distributed deadlock detection algorithms can be divided into four classes:

1. Path-Pushing Algorithms

In path-pushing algorithms, distributed deadlocks are detected by maintaining an explicit global WFG. The basic idea is to build a global WFG for each site of the distributed system. In this class of algorithms, at each site whenever deadlock computation is performed, it sends its local WFG to all the neighboring sites

2. Edge-Chasing Algorithms

In an edge-chasing algorithm, the presence of a cycle in a distributed graph structure is be verified by propagating special messages called probes, along the edges of the graph. These probe messages are different than the request and reply messages. The formation of cycle can be deleted by a site if it receives the matching probe sent by it previously.

3. Diffusing Computations Based Algorithms

In diffusion computation based distributed deadlock detection algorithms, deadlock detection computation is diffused through the WFG of the system. These algorithms make use of echo algorithms to detect deadlocks. This computation is superimposed on the underlying distributed computation. If this computation terminates, the initiator declares a deadlock global state detection.

4. Global State Detection Based Algorithms

Global state detection based deadlock detection algorithms exploit the following facts:

1 A consistent snapshot of a distributed system can be obtained without freezing the underlying computation and

2 If a stable property holds in the system before the snapshot collection is initiated, this property will still hold in the snapshot.

Probe Based distributed Deadlock Detection Algorithm:

• This is considered an edge-chasing, probe-based algorithm. It is also considered one of the best deadlock detection algorithms for distributed systems.
• 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.
• Each probe message contains the following information:
  1. the id of the process that is blocked (the one that initiates the probe message);
  2. the id of the process is sending this particular version of the probe message; and
  3. the id of the process that should receive this probe message.
• When a process receives a probe message, it checks to see if it is also waiting for resources.
• If not, it is currently using the needed resource and will eventually finish and release the resource.
• If it is waiting for resources, it passes on the probe message to all processes it knows to be holding resources it has itself requested.
• The process first modifies the probe message, changing the sender and receiver ids.
• If a process receives a probe message that it recognizes as having initiated, it knows there is a cycle in the system and thus, deadlock.

• The following example is based on the same data used in the Silberschatz-Galvin algorithm example. In this case P1 initiates the probe message, so that all the messages shown have P1 as the initiator. When the probe message is received by process P3, it modifies it and sends it to two more processes. Eventually, the probe message returns to process P1. Deadlock!