Deadlock Detection

In deadlock detection, there is no control of how and when the processes should acquire locks to resources. The probe or query computation is a deadlock detection sequence of messages, separated from the underlying computation. The detection algorithm thus can be run concurrently with the computation. Any circular waits (hence cycles in WFG of the system) is only the necessary condition for deadlock in the communication model. The algorithm then resolves the deadlock detection by using its deadlock resolution algorithm.

Types of Deadlock Detections

There are three types of deadlock detections:

1. Centralized deadlock detection
2. Distributed deadlock detection
3. Hierarchical deadlock detection

Centralized Deadlock Detection

In this type of detection, a designate site, called the control site, has the responsibility of constructing the global WFG of the system. Cycles are searched by this site and resolved by the control site. It is conceptually simple to implement such a system. Since the control site has the full picture of the system, optimal decisions can be made. However, this approach suffers from drawbacks that centralized deadlock control site is a single point of failure. As the system consists of a larger number of sites and processes, the centralized control site has to serve a larger number of processes, message traffics in that site will be increased and the computational load of the cycle search algorithm will be increased. These affect the performance of the system as well as the stability of it.

Distributed Deadlock Detection

In distributed deadlock detection, processes are responsible to detect the deadlock by themselves. They utilise control messages between the processes to detect deadlocks. This type of detection enjoys the concurrency of the algorithm as well as the tolerance to process failures. However, this type of detection also suffers from a number of drawbacks. First, as the messages between processes are asynchronous and the system is dynamic, a distributed algorithm solving the problem is hard to implement and design correctly. Second, this type of algorithms is not as efficient as the centralised type because no processes can have the full picture of the WFG. Third, all processes need to run the deadlock detection algorithm continuously and concurrently with the underlying computation. While it is possible that the algorithm would use a small portion of the computational resource, it is a performance leak.

Hierarchical Deadlock Detection

In hierarchical deadlock detection, sites are arranged into clusters hierarchically , where sites detect deadlocks that involve only its descendant sites. Hierarchical algorithms tend to get the best out of the two types of deadlock detection algorithms presented above. There is no single point of failure and sites are not going to be overloaded with the deadlock detection algorithm when it is unnecessary for deadlock detection. This kind of algorithm make uses of the access patterns of the system in order to design the hierarchy of the clusters so that deadlocks are as localised in a cluster as possible. This is one of the biggest challenges in implementing such kind of detection algorithm.