H. Chang

An Analysis of Deadlock Avoidance Schemes and the Resource Utilization For Non-pre-emptible Resources Degree Type: Ph.D. in Computer Science
Advisor(s): Nico Habermann
Graduated: August 1975

Abstract:

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.

Thesis Committee:
Nico Habermann (Chair)

Joseph Traub, Head, Computer Science Department