On-line deadlock detection in distributed computer systems

Graduation date: 1983A new algorithm, the Horizontal and Vertical Algorithm, for\ud on-line detection of deadlocks in distributed computer systems, is\ud presented. Two protocols for implementing the algorithm are given.\ud The first protocol, the centralized protocol, is based on the\ud assumption that one site in the network acts as the controller for\ud global resource allocation and deadlock detection. The second\ud protocol, the distributed protocol, distributes the responsibilities\ud of resource allocation and deadlock detection among the sites where\ud the requested resources reside.\ud The new deadlock detection protocols have two important features. Both protocols are characterized by their simplicity in implementation as compared to most published protocols. The storage\ud requirement needed to run the distributed protocol is considerably\ud reduced. The distributed protocol is also characterized by a significant reduction of communication messages passed around the\ud different sites in the network.\ud The new algorithm is compared with the distributed algorithm\ud proposed by Barry Goldman and the preemption method of deadlock\ud prevention on a ring network. The comparison was made by means of\ud simulation models. Simulation models are developed for both the\ud centralized and distributed control of the new algorithm, Goldman's algorithm and the preemption technique.\ud The performances of the algorithms are measured in terms of\ud process response time—average delay per process, and process\ud throughput—the number of processes completed per unit time. Resource request response time—average time to process a resource\ud request and throughput—the number of requests processed per unit\ud time are also measured. Communication overhead associated with the\ud use of each algorithm and frequency of deadlock occurrence are also\ud measured.\ud The simulation results, for the distributed Horizontal and\ud Vertical algorithm, are used to develop an M/M/z queueing model\ud to measure the request response time of the algorithm. This is\ud done by a regression technique. The results of the analytical model\ud show a very close fit with the results of the simulation model