吴国凤， 胡德启， 安 磊， 郑礼良

（合肥工业大学 计算机与信息学院，安徽 合肥 230009）

含有不可控变迁的Petri网死锁避免策略

吴国凤， 胡德启， 安 磊， 郑礼良

（合肥工业大学 计算机与信息学院，安徽 合肥 230009）

文章针对Petri网建模的并发系统中的死锁问题，利用Petri网可达树分析方法检测系统死锁的存在，结合Petri网控制器的设计来达到预防和避免死锁的目的；提出了一种新的约束设计思想，进行控制器设计，使得系统不会出现死锁；更进一步地考虑到控制器设计过程中存在不可控变迁的情况下系统避免死锁的设计问题。

Petri网；控制器；混合约束；死锁

并发进程的死锁问题是分布式系统中的一个重要研究课题［1］。在多个并发进程系统中，如果每个进程持有某种资源，同时又等待其他进程所持有的各种资源，此时，每个进程都持有一定资源但又都无法推进，这样就形成了死锁［2］，这样的死锁在分布式系统中时有出现，因此，发现和提出好的死锁检测、预防和解除方法尤为重要。

文献［3］提出了基于库所不变量的控制器设计算法，该方法利用整个Petri网的关联矩阵来计算控制器，计算的复杂度比较大，而且只适用于安全网。文献［4］提出了Parikh向量不等式的约束转换算法，再用基于库所不变量的控制器算法设计控制器。但是，以上各种方法并没有把控制器算法应用于解决Petri网的死锁问题。

本文在总结上述控制器设计算法时存在问题和研究Petri网建模的并发系统中的死锁问题基础上，利用Petri网可达树分析方法检测系统死锁的存在，设计出一种可以避免死锁的约束条件，结合Petri网控制器的设计来达到预防和避免死锁的目的［5－6］。……