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 safe(I), where I is an integer vector representing the system state. safe(I) is true if the system is safe, false otherwise. The resource allocator will make the allocation only when the resulting system has safe(I)=true. Based on the concept of computation trees, several lower bounds for the cost involved in computing safe(I) are established under different conditions. An upper bound is also developed.