Deadlock avoidance for sequential resource allocation systems: Hard and easy cases

Deadlock is a major problem for systems that allocate resources in real tim e. The key issue in deadlock avoidance is whether or not a given resource a llocation state is safe: that is, whether or not there exists a sequence of resource allocations that completes all processes. Although safety is esta blished as NP-complete for certain broad resource allocation classes, newly emerging resource allocation scenarios often exhibit unique features not c onsidered in previous work. In these cases, establishing the underlying com plexity of the safety problem is essential for developing the best deadlock avoidance approach. This work investigates the complexity of safe resource allocation for a class of systems relevant in automated manufacturing. For this class, the resource needs of each process are expressed as a well-def ined sequence. Each request is for a single unit of a single resource and i s accompanied by a promise to release the previously allocated resource. Ma nufacturing researchers have generally accepted that safety is computationa lly hard, and numerous suboptimal deadlock avoidance solutions have been pr oposed for this class. Recent results, however, indicate that safety is oft en computationally easy. The objective of this article is to settle this qu estion by formally establishing the NP-completeness of safety for this clas s and investigating the boundary between the hard and easy cases. We discus s several special structures that lead to computationally tractable safety characteristics.