On Siphon Computation for Deadlock Control in a Class of Petri Nets
On Siphon Computation for Deadlock Control in a Class of Petri Nets
复制标题
DOI：
10.1109/tsmca.2008.918605
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
Zhiwu Li;Mengchu Zhou
中科院分区：
文献类型：
--
作者：
Zhiwu Li;Mengchu Zhou
虹吸管作为一个结构对象，在用Petri网建模的资源分配系统的死锁分析和控制中得到了很好的认可。许多死锁预防策略用虹吸来描述系统的死锁行为，并利用这种特征来避免死锁。本文开发了一种新的方法来寻找一类Petri网（即具有资源的简单顺序过程系统）中用于死锁控制目的的有趣虹吸。首先检测a中的资源电路，一般地，从中可以得到一小部分可清空的最小虹吸管。剩下的空的可以通过它们的组成来找到。提出了一种多项式时间算法来查找基本虹吸集合，避免了完全虹吸枚举。结果表明，依赖虹吸管总是可以通过适当地监视其基本虹吸管来控制。因此，开发了一种计算效率高的死锁控制策略。实验研究表明了虹吸计算方法的有效性。
As a structural object, siphons are well recognized in the analysis and control of deadlocks in resource allocation systems modeled with Petri nets. Many deadlock prevention policies characterize the deadlock behavior of the systems in terms of siphons and utilize this characterization to avoid deadlocks. This paper develops a novel methodology to find interesting siphons for deadlock control purposes in a class of Petri nets, i.e., a system of simple sequential processes with resources . Resource circuits in an are first detected, from which, in general, a small portion of emptiable minimal siphons can be derived. The remaining emptiable ones can be found by their composition. A polynomial-time algorithm for finding the set of elementary siphons is proposed, which avoids complete siphon enumeration. It is shown that a dependent siphon can always be controlled by properly supervising its elementary siphons. A computationally efficient deadlock control policy is accordingly developed. Experimental study shows the efficiency of the proposed siphon computation approach.