Subsystems of processes with deadlock avoidance

Abstract

A graph-oriented approach to deadlock avoidance, which treates both shared and exclusive locking, has been described [6]. The method is particularly suited for database systems. With enhancements introduced here, the problem of indefinite delay, i.e., the possibility that a process will not run to completion (will be delayed indefinitely) can be eliminated. The approach taken is to partition the resource system into subsystems, each of which can be scheduled independently. Indefinite delay is avoided by the construction of subsystems mat guarantee the completion of a process or the granting of a resource request. Further, we show how the subsystem approach can be applied systematically so as to approximate FIFO scheduling of resource requests, while avoiding deadlock and indefinite delay. Other scheduling disciplines can also be realized. A lock manager program utilizing the FIFO method has been implemented. © 1980 by The Institute of Electrical ind Electronics Engineers, Inc.