Deadlock Detection in Distributed System

In this tutorial you are going to learn about Deadlock Detection in Distributed System.

Distributed Deadlock Detection

Deadlocks are the fundamental problem in distributed systems.

In concurrent computing, a deadlock is a state in which each process is holding a resource and waiting for some other resources acquired by some other process (in a circular manner).

A system is in a deadlock state if there exists a set of transactions such that every transaction in the set is waiting for another transaction in the set.

If there exists a set of waiting transaction To, T1…Tn-1 such that To🡪T1, T1🡪 T2, So on, none of the transaction can progress in such situation.

An effective tool that is used to detect the deadlock is drawing a Wait-for-Graph (WFG).

Necessary Condition for Deadlock:

1. Mutual exclusion: This is a condition in which at a given point of time there should an existence of at least one resource which can be used by only one process in the system.
2. Hold and wait: A process waits for some resources while holding other resources at the same time. It holds one resource and waits for another resource to complete its task.
3. No preemption: The process which once scheduled will be executed till the completion. Once the process has obtained a resource, the system cannot remove it from the process control until the process has finished using the resources.
4. Circular wait: All the processes must be waiting for the resource in a cyclic manner.

Assume that there are Process A, Process B, Process C and Process D

• Process A will be waiting for Process B to complete the task.
• Process B will be waiting for Process C to complete the task.
• Process C will be waiting for Process D to complete the task.
• Process D will be waiting for process A to complete the task.

Distributed Deadlock detection algorithms can be divided into four classes.

1. Path Pushing
2. Edge Chasing
3. Diffusion Computation
4. Global State Detection

1. Path Pushing Algorithms: In the path pushing algorithm, deadlocks wait for dependency information of the global WFG (Wait for graphs) to be disseminated in the form of paths. i.e., a sequence of wait for dependency edges.
2. Edge Chasing Algorithm: In the edge chasing algorithm, special messages called probes are circulated along the edge of the WFG (Wait for graphs) to detect a cycle. When a blocked process receives a probe, it propagates the probe along its outgoing edges in the WFG. A process declares a deadlock when it receives a probe initiated by it.
3. Diffusion Computation based Algorithm: Diffusion computation type algorithm make use of each algorithm to detect deadlocks. Deadlock detection messages are successively propagated through the edges of the WFG.
4. Global State Detection based Algorithm: These algorithms detect deadlocks by taking a snapshot of the system and by examining it for the conditions for the deadlock. The global state graph is spread over many sites.

---

This article on Deadlock Detection in Distributed System is contributed by Hemalatha P. If you like TheCode11 and would like to contribute, you can also write your article and mail to thecode11info@gmail.com