DISTRIBUTED DEADLOCK DETECTION IN DISTRIBUTED DATABASE SYSTEMS.

摘要

Deadlock detection in distributed database systems is very complicated and difficult to handle because of the distributed nature of the system and the communication delay of the network. Many detection algorithms have been proposed in the past, but most of them have been shown to be incorrect and inefficient. Designing an applicable algorithm is still worthy of intensive study.;A message generation scheme based on transaction ordering has been applied to the proposed deadlock detection algorithm to reduce the number of reaching messages transmitted and increase the efficiency of the deadlock detection. For a deadlock state with n transactions involved, this algorithm needs half the number of reaching messages of the original algorithm in the worst case.;The proposed algorithm has been shown to be correct and more efficient compared to previously proposed algorithms. It has been shown that the reaching message generation scheme of the algorithm will ensure the detection of all possible deadlocks, and the comparison of timestamps in graph edges and messages will prevent false deadlocks.;A simulator in PATH PASCAL has been written during the design of the algorithm for testing correctness and improving performance. Four network sites with I/O channels to the virtual network model have been simulated.;In this thesis, a distributed deadlock detection algorithm is proposed. Checking a cycle in a graph, called an "RTR" graph, is used to detect a deadlock state. The inter-communication scheme of the algorithm generates and propagates "reaching" messages in order to update the RTR graphs at other sites. The reaching message is a fixed-size message containing a transaction node, a resource node and a timestamp. Timestamps are also attached to the graph edges in order to avoid false deadlocks. A deadlock recovery approach is also proposed to break deadlock after it is detected. A minimum cost policy and a "polling" synchronization scheme are used in the algorithm in order to break the detected deadlock state with a minimum communication cost.