Mumbai University > Information Technology > Sem 6 > Distributed System

Marks: 10 Marks

Year: Dec 2016

A deadlock is a condition in a system where a set of processes (or threads) have requests for resources that can never be satisfied.

An algorithm for detecting deadlocks in a distributed system was proposed by Chandy, Misra, and Haas in 1983. Processes request resources from the current holder of that resource. Some processes may wait for resources, which may be held either locally or remotely. Cross-machine arcs make looking for cycles, and hence detecting deadlock, difficult. This algorithm avoids the problem of constructing a Global WFG.

Each node has the same responsibility for, and will expend the same amount of effort in detecting deadlock

• The WFG becomes an abstraction, with any single node knowing just some small part of it
• Generally detection is launched from a site when some thread at that site has been waiting for a “long” time in a resource request message.

Four common models are used in building distributed deadlock control algorithms:

• Path-pushing

  path info sent from waiting node to blocking node

• Edge-chasing

  probe messages are sent along graph edges

• Diffusion computation

  echo messages are sent along graph edges

• Global state detection

  sweep-out, sweep-in (weighted echo messages); WFG construction and reduction.

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:
• the id of the process that is blocked (the one that initiates the probe message);
  1. the id of the process is sending this particular version of the probe message; and
• 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!