A polynomial-complexity deadlock avoidance policy for sequential resource allocation systems with multiple resource acquisitions and flexible routings

The need for effective and efficient deadlock avoidance policies (DAPs) is ever increasing due to the higher demand for system automation. This paper considers the deadlock avoidance problem for the class of conjunctive/disjunctive (sequential) resource allocation systems (C/D-RAS), in which multiple resource acquisitions and flexible routings are allowed. A new siphon-based characterization of deadlocks arising in C/D-RAS is developed, and subsequently, this characterization facilitates the development of a polynomial complexity deadlock avoidance policy for the considered RAS class. The developed policy can be perceived as a generalization of RUN DAP, originally developed for sequential RAS with unit resource allocations and no routing flexibility. The proposed approach is demonstrated by an example