Local and global deadlock prevention policies for resource allocation systems using partially generated reachability graphs

This paper considers the deadlock prevention problem for a class of conjunctive/disjunctive resource allocation systems (C/D-RAS) which cover relatively general cases in which the multiple resource acquisitions and flexible routings are allowed. First, an improved siphon-based liveness characterization for the Petri nets modeling C/D-RAS is proposed. Subsequently, this characterization facilitates the utilization of a mixed integer programming (MIP) based deadlock prevention policy that can well avoid the explicit enumeration of both siphons and the reachable states. The resulting policy is implemented by an iterative algorithm each step of which is characterized as an MIP formulation in conjunction with both a bad marking detection and a feedback control operation. Finally, the deadlock prevention policy developed in this paper is, respectively, characterized by the local and global ones so as to realize a trade-off between the behavior permissiveness and the structural simplicity of the supervisor. Both the theoretical and experimental results validate the effectiveness and efficiency of such an approach. (C) 2009 Elsevier Ltd. All rights reserved.