Research On Cycle And Knot Oriented Distributed Deadlock Detection Algorithm

During the running of distributed computing, deadlock would happen if the re-source allocation and requirement confliction occur. It is an infinite waiting state: a part of a process set which have held some resources send new resource requests to other resources, at the same time they find the requested resources have been held by another part of the same set of processes, all the processes are waiting each other for the holding resources releasing, then the system running stop.Deadlock can be overcome by avoiding method, while this method either re-quires the system possesses enough resources or assigns strict rules for the resource requirement of processes before in order to prolong the running time to get unblock-ing. So the avoid method need to know the total running states of the system, it is appropriate for the systems which have fixed concurrent running scale and time, such as the real-time control system of airport. While for most of the network-based dis-tributed systems, resource requirement scale and time of the processes are uncer-tainty, the avoid method can not forecast all the possible states, therefore another deadlock resolve method, the deadlock detection method may be the better choice for distributed systems.Research about the deadlock detection method experienced a long time. Ac-cording to the resource requirement types of the processes, the distributed computa-tion models can be divided into single resource model, AND model, OR model and AND-OR model. Generalization of these models is stronger gradually and the dead-lock topologies of these models are single cycle, cycle and knot respectively. Dead-lock detection algorithm is developed gradually in the same order of the resource re-quire models. Some classical algorithms were proposed in last decades, such as the single cycle detection algorithm proposed by Mitchell and Merritt, the cycle detec-tion algorithm proposed by Chandy and Misra, the knot detection algorithm proposed by Lee and the generalized algorithm proposed by Manivannan. In our opinion, the algorithms proposed for the single resource model and AND model can be reduced to the Resource node Dependent (RD) and the Resource node Independent (RI) meth-ods, and the algorithms proposed for the OR model and the AND model can be re-duced to the Initial node Reduction (IR) and the Neutral node Reduction (NR) methods. Study on these methods show that the RD and RI methods have the defi-ciencies such as low detection efficiency and incorrect resolution for the overlapped cycles, and the IR and NR methods have the deficiencies such as complication and useless in dynamic environment. Furthermore, there are still common problems exist...