1;3409;0c Testing Deadlock-Freedom of Computer Systems

Testing Deadlock-Freedom of Computer Systems

Journal of the ACM, vol. 27, no. 2, 1980
Pages: 270-280DOI: 10.1145/322186.322192



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 by O(mn1.5) if the system consists of n processes sharing m types of serially reusable resources.