Accession Number:

ADA021732

Title:

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

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Chang,Hsiau-chung

Report Date:

1975-06-20

Pagination or Media Count:

234.0

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.

Descriptors:

• *COMPUTER PROGRAMMING
• *CENTRAL PROCESSING UNITS
• ALGORITHMS
• THESES
• ALLOCATIONS

Subject Categories:

• Computer Programming and Software
• Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE