Deadlock Avoidance for Sequential Resource Allocation Systems: Hard and Easy Cases

摘要: Deadlock is a major problem for systems that allocate resources in real time. The key issue deadlock avoidance whether or not given resource allocation state safe: is, there exists sequence of allocations completes all processes. Although safety established as NP-complete certain broad classes, newly emerging scenarios often exhibit unique features considered previous work. In these cases, establishing the underlying complexity essential developing best approach. This work investigates safe class relevant automated manufacturing. For this class, needs each process are expressed well-defined sequence. Each request single unit and accompanied by promise to release previously allocated resource. Manufacturing researchers have generally accepted computationally hard, numerous suboptimal solutions been proposed class. Recent results, however, indicate easy. objective article settle question formally NP-completeness investigating boundary between hard easy cases. We discuss several special structures lead tractable characteristics.