Please use this identifier to cite or link to this item:
|Title:||What is deadlock?|
|Citation:||Tay, Y.C. (1993). What is deadlock?. IFIP Transactions A: Computer Science and Technology (A-39) : 49-60. ScholarBank@NUS Repository.|
|Abstract:||All distributed systems share some resources, including data. Where a resource cannot be simultaneously used by more than one process, some of these processes may be forced to wait for other processes that are using the resource. This can lead to deadlocks. Therefore, the design and specification of any distributed system must usually deal with the issue of deadlocks. One possible design choice is to detect and resolve deadlocks. Unfortunately, although deadlock detection for centralized systems is trivial, detection algorithms for distributed systems are notoriously prone to errors - many detectors either fail to detect deadlocks, or declare a deadlock when there is none. In trying to understand this anomaly, we have constructed a theory for deadlocks. One hopes that such a theory will settle the confusion caused by the errors, and provide a body of results to draw upon in the design of deadlock detectors for new systems. The first step to constructing the theory is to formally define what a deadlock is. Surprisingly, the source of many errors lies in the absence, the ambiguity, or the incorrectness of this definition. We offer here a definition that is rigorous and, moreover, based on facts that processes can observe and verify locally. In particular, the definition does not use real time and simultaneity, which are not locally observable. Such a locally verifiable definition is especially useful in the design of deadlock detectors.|
|Source Title:||IFIP Transactions A: Computer Science and Technology|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Sep 21, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.