Testing Deadlock-Freedom of Computer Systems
- 1 April 1980
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 27 (2) , 270-280
- https://doi.org/10.1145/322186.322192
Abstract
The problem of determining whether it is possible for a set of “free-running” processes to become deadlocked is considered. It is assumed that any request by a process is immediately granted as long as there are enough free resource units to satisfy the request. The question of whether or not there exists a polynomial algorithm for predicting deadlock in a “claim-limited” serially reusable resource system has been open. An algorithm employing a network flow technique is presented for this purpose. Its running time is bounded byO(mn1.5) if the system consists ofnprocesses sharingmtypes of serially reusable resources.Keywords
This publication has 7 references indexed in Scilit:
- Locking and Deadlock Detection in Distributed Data BasesIEEE Transactions on Software Engineering, 1979
- Network flow and generalized path compressionPublished by Association for Computing Machinery (ACM) ,1979
- Game interpretation of the deadlock avoidance problemCommunications of the ACM, 1977
- Some Deadlock Properties of Computer SystemsACM Computing Surveys, 1972
- System DeadlocksACM Computing Surveys, 1971
- Prevention of system deadlocksCommunications of the ACM, 1969
- Flows in NetworksPublished by Walter de Gruyter GmbH ,1963