Local and global deadlock prevention policies for resource allocation systems using partially generated reachability graphs
Local and global deadlock prevention policies for resource allocation systems using partially generated reachability graphs
复制标题
DOI：
10.1016/j.cie.2009.05.006
复制
发表时间：
2009-11
期刊：
影响因子：
--
通讯作者：
Hesuan Hu;Zhiwu Li
中科院分区：
文献类型：
--
作者：
Hesuan Hu;Zhiwu Li
本文研究了一类合取/析取资源分配系统（C/D-RAS）的死锁预防问题，该系统涵盖了允许多个资源获取和灵活路由的相对一般情况。首先，提出了一种改进的基于虹吸的Petri网建模C/D-RAS活性表征方法。随后，这种特性有助于使用基于混合整数规划（MIP）的死锁预防策略，该策略可以很好地避免对虹吸和可达状态的显式枚举。由此产生的策略由一个迭代算法实现，该算法的每一步都被描述为与不良标记检测和反馈控制操作相结合的MIP公式。最后，本文提出的死锁预防策略分别具有局部和全局的特征，从而实现了行为容错性和监管者结构简便性之间的权衡。理论和实验结果都验证了该方法的有效性和高效性。
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.