Analysis of Deadlock Avoidance Schemes and Resource Utilization for Non-Preemptible Resources,

Two aspects of the performance of deadlock avoidance schemes are studied. The first is the cost of deadlock avoidance algorithms. This represents the system overhead. The second is the resource utilization under different schemes. For the first, the basic cost is the computation of the boolean function safeI, where I is an integer vector representing the system state. safeI is true if the system is safe, false otherwise. The resource allocator will make the allocation only when the resulting system has safeItrue. Based on the concept of computation trees, several lower bounds for the cost involved in computing safeI are established under different conditions. An upper bound is also developed.