Document Type

Technical Report

Publication Date

Winter 12-1-1977


The problem of deadlocks is an important factor in the design of multiprogramming computer systems. Current techniques for preventing deadlocks, without run-time overhead, are based on violating one of the necessary conditions for deadlocks to occur. One such technique is the linear ordering of resources Rl ,…, Rm and the restriction that a process cannot request resource Rj if it currently holds a resource Ri such that j≤i. In this paper we present an algorithm to detect if any such ordering exists for a given set of flow graphs representing concurrent processes. Even if no such ordering exists it can sometimes be shown that there can be no deadlocks. A graph model for resource requests in a system of processes is developed. It is shown that if this graph is acyclic then there can be no deadlocks. Further, the notions of exclusive and reducible components of the resource graph are defined. It is shown that if the resource graph consists only of these two type of components then there can be no deadlock. Algorithms to detect these components are also given. It should be noted that there are static algorithms and do not require run-time overhead.