• In this approach for deadlock detection, the system does not make any attempt to prevent deadlock but allows processes to request resources and wait for each other in uncontrolled manner.
• Deadlock detection algorithms are same in centralized and distributed systems.
• Deadlock detection algorithms get simplified by maintaining Wait-for-graph (WFG) and searching for cycles. The different approaches for deadlock detection are:

1.Centralized Approach for Deadlock Detection

• In this approach a local coordinator at each site maintains a WFG for its local resources and a central coordinator for constructing the union of all the individual WFGs.
• The central coordinator constructs the global WFG from the information received from the local coordinators of all sites.
• Deadlock detection is performed:

i.If a cycle exists in the local WFG of any site then it represents a local deadlock which is detected and resolved by the local coordinator of the site.

ii.Deadlocks involving resources at two or more sites get reflected as cycles in the global WFG are detected and resolved by the central coordinator.

• Local coordinators send local state information to the central coordinator in the form of messages which can use continuous transfer, periodic transfer or Transfer-on-request.
• Advantages: Simple approach.
• Disadvantages: Central coordinator may detect false deadlock, Vulnerable to failure of central coordinator.

2.Hierarchical Approach for Deadlock Detection

• The hierarchical approach overcomes drawbacks of the centralized approach.
• This approach uses a logical hierarchy of deadlock detectors called as controllers.
• Each controller detects only those deadlocks that have the sites falling within the range of the hierarchy. Global WFG is distributed over a number of different controllers in this approach.
• Each site has its own local controller that maintains its own local graph. WFG is maintained by a controller use the following rules:

i.Each controller that forms a leaf of the hierarchy tree maintains the local WFG of a single site. ii.Each non-leaf controller maintains a WFG that is the union of the WFGs of its immediate children in the hierarchy tree.

• The lowest level controller that finds a cycle in its WFG detects a deadlock ant takes necessary action to resolve it. WFG that contains a cycle that will never be passed as it is to higher level controller.

• Advantages: Minimizes communication cost

3. Fully Distributed Approaches for Deadlock Detection

In this approach each site shares equal responsibility for deadlock detection. The first algorithm is based on construction of WFG and second one is a probe-based algorithm.

i.WFG-Based Distributed Algorithm for Deadlock Detection

• In this algorithm each site maintains its own local WFG but for external processes a modified form of WGF is used. In this an extra node Px is added to the local WFG of each site and this node is connected to the WFG if an edge (Pi,Px) is added if process Pi is waiting for resource in another site and if Pjis a process of another site waiting for a resource being held by process of this site.
• Advantages: similar to centralized approach
• Disadvantage: overhead of unnecessary message transfer, Duplication of deadlock detection jobs.

ii.Probe-Based Distributed Algorithm for Deadlock Detection

• This algorithm is also known as Chandy-Misra-Hass algorithm and is considered to be the best algorithm for detecting global deadlocks in distributed systems.
• The algorithm allows a process to request for multiple resources at a time.
• When a process requests for a resource and fails to get the resource and time out occurs it generates a special probe message and sends it to the requested resource process.
• On receiving probe message, the recipient checks if it’s waiting for a resource. It then forwards the message. The probe message contains various fields which might be changed before it is forwarded.
• Every new recipient of the probe message repeats the procedure and if the message returns to the original sender a cycle exists ant system is deadlocked.
• Advantages: Overhead is low, simple to implement, false deadlocks not detected.