Deadlock Detection in Computer Networks
Abstract
The problem of detecting process deadlocks is common to transaction oriented computer systems which allow data sharing. Several good algorithms exist for detecting process deadlocks in a single location facility. However, the deadlock detection problem becomes more complex in a geographically distributed computer network due to the fact that all the information needed to detect a deadlock is not necessarily available in a single node, and communications may lead to synchronization problems in getting an accurate view of the network state. In this thesis, two published algorithms dealing with deadlock detection in computer networks are discussed, and examples demonstrating the failure of these algorithms are given. Two algorithms are then presented for detecting deadlocks in a computer network which allows processes to wait for access to a portion of a database, or a message from another process. The first algorithm presented is based on the premise that there is one control node in the network, and this node has primary responsibility for detecting process deadlocks. The second, and recommended, algorithm distributes the responsibility for detecting deadlocks among the nodes in which the involved processes and resources reside. Thus a failure of any single node has limited effect upon the other node in the network. A computer model of the decentralized (second) algorithm was designed and it is described in the thesis.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1977
- Accession Number
- ADA047025
Entities
People
- Barry Goldman
Organizations
- Massachusetts Institute of Technology