Distributed deadlock detection algorithms and their performance study

Detecting deadlock is an important problem which has undergone extensive study, since all the processes involved in deadlock sit idle consuming the system resources. Unlike deadlocks in a centralized computer system, those in a distributed system are difficult to handle, since a site does not have global information about the states of all the processes in the system. Recent works on distributed deadlock detection and resolution use a short message called probe to find deadlocks. The initiator of deadlock detection algorithm propagates probes in the system. Upon receiving its own probe back, the initiator declares a deadlock. One major disadvantage of these algorithms is that they detect only those deadlocks to which the initiator belongs, even if its probes may be propagated to all the nodes in the system. If the initiator is transitively waiting for a deadlock, its probes are of no use in detecting deadlocks but just aggravate the communication overhead. We present distributed deadlock detection and resolution algorithms which overcome the above disadvantage of other algorithms. The initiator of our algorithms detects those deadlocks in which it is indirectly involved as well as those deadlocks in which it is directly involved. This is achieved by building a tree through the propagation of probes and classifying the edges of the wait-for graph. Consequently, our algorithms attain faster deadlock detection and fewer algorithm invocations throughout the system than the other algorithms as shown by performance study through simulation.