Deadlock avoidance revisited
- 1 October 1982
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 29 (4) , 1023-1048
- https://doi.org/10.1145/322344.322351
Abstract
Several new algorithms that utilize wmt-for relations mduced by processes are developed for deadlock avoidance in operating systems. One of the algorithms allows more concurrency than Havender's scheme and Habermann's algorithm; nonetheless, it can still be computed in polynomial time. Further, the deadlock,prediction problem for a set of processes using locks is reduced to a new NP-complete problem, and the deadlock-avoidanceproblemfor processes with branches is shown to be PSPACE-complete, Finally, the relative power of various algorithms is compared.Keywords
This publication has 10 references indexed in Scilit:
- AlternationJournal of the ACM, 1981
- Testing Deadlock-Freedom of Computer SystemsJournal of the ACM, 1980
- Game interpretation of the deadlock avoidance problemCommunications of the ACM, 1977
- The notions of consistency and predicate locks in a database systemCommunications of the ACM, 1976
- A Combinatorial Problem Which Is Complete in Polynomial SpaceJournal of the ACM, 1976
- Some Deadlock Properties of Computer SystemsACM Computing Surveys, 1972
- Comment on deadlock preventive methodCommunications of the ACM, 1972
- System DeadlocksACM Computing Surveys, 1971
- Comments on prevention of system deadlocksCommunications of the ACM, 1971
- Prevention of system deadlocksCommunications of the ACM, 1969