Distributed deadlock detection and its application to real-time systems

Deadlock is one of the most serious problems in multitasking concurrent programming systems. The problem is further complicated when the underlying system is distributed and when tasks have timing constraints. Although deadlock detection has been studied to some extent in database systems and timesharing operating systems, it has not been widely used in real-time systems. In this dissertation we analyze, develop, and formally validate deadlock detection algorithms in distributed environments. The results are then extended to real-time applications by considering timing constraints in the algorithms. Also, attempts are made to apply these algorithms to real systems such as Ada environments. The Ada runtime environment is used as a system model to address problems and issues related to distributed deadlock detection in real-time applications. One of the major achievements of this dissertation study is the development of a systematic method for the design and the verification of distributed deadlock detection algorithms. This novel methodology is applied to a variety of deadlock models ranging from simple (resource) deadlock models (e.g., the Single-Resource request model) to complex (communication) deadlock models (e.g., the OR request model). The developed algorithms are then extended for real-time applications. For verification and performance evaluation, these algorithms are implemented in a distributed real-time database testbed called RT-CARAT (Real-Time Concurrency And Recovery Algorithm Testbed) where transaction timing constraints and soft real-time scheduling protocols are supported. Various experiments are conducted to study and evaluate these algorithms. Our experimental results show that distributed deadlock detection can be very efficient. Compared to a baseline scheme break deadlocks by deadline, any of these deadlock detection algorithms can significantly improve the overall system performance. Also, the deadlock detection/resolution approach outperforms another class of baseline schemes timeout from waiting state and retry when the deadlocks are simple and short (e.g., the simple resource deadlocks). However, the former approach performs worse than the latter when the average deadlock length is long (e.g., the complex communication deadlocks). The results also suggest that in real-time applications when the average wait-for path is long, an integrated solution is necessary to detect and resolve both the deadlocks and the long wait-for paths