论文摘要
Petri网适合于描述异步并发行为的系统。首先,Petri网直接展现并发系统的物理结构层次及资源状态的初始分布状况。其次,在Petri网引发规则的作用下将间接展现出该并发系统的动态行为机理。这两个层面相互关联,形成了一个集物理结构和行为机理于一体的集成模型。它提供的的系统信息更加的丰富,其分析在理论上也更为深刻。Petri网的主要行为特性包括:状态的可达(reachability)、位置的有界性(boundedness)、变迁的活性(liveness)、状态的可逆达(reversibility)、标识之间的可达(reachability)、变迁之间的坚挺(persistence)、事件之间的同步距离(synchronic distance)和公平性(fairness)等。Petri网模型的主要分析方法依赖于:可达标识图、关联矩阵和状态方程、不变量(invariants)和分析化简规则。Petri网以研究模型系统的组织结构和动态行为为目标,着眼于系统中可能发生的各种状态变化以及变化之间的关系,易于表示系统变化发生的条件及变化发生后的系统状态。Petri网应用的主要困难是模型状态空间的复杂性问题,它将随实际系统的规模增大而呈指数性增长。因此,对于一般的Petri网,只要一涉及网的性质,常常得到的算法都是NP难的(又称作状态空间爆炸)。对于这些NP问题,目前国内、国外的理论研究基本停留在一般子类上的研究。尽管得到了许多好的结果,但是由于子类的特殊性,使得所得结果缺乏很好的应用性。本人的工作是基于一般网的一些性质的研究。本人的研究主要是从网的基本性质出发。利用结构性分析理论和不变技术,对Petri网的主要行为特征进行了较为深入细致的研究,得到了一些新的结果。主要贡献包括:(1)冲突是Petri网系统的基本现象.冲突使得库所中的托肯分配具有不确定性,产生的结果更加具有多样性。本文讨论的范围是变迁与库所数量有限的C/E系统,根据C/E对冲突的定义,找到能产生冲突的静态冲突向量结合相应的情态(case)来确定在什么情态下哪些变迁产生了冲突。最后给出寻找冲突的算法。(2)相对与C/E系统中的冲突而言,P/T系统由于库所的容量和流上的权值都大于等于1,因此冲突更加的复杂。本文讨论的范围是变迁与库所数量有限的P/T系统,提出了P/T网中的冲突和不完全冲突的概念,并给出了冲突和不完全冲突发生的条件。确定了冲突和不完全冲突发生时,库所所必须的取值范围,并给出算法。(3)公平性(fairness)是Petri网的基本性质。在本文中利用网的关联矩阵求解出一般网中的基本可重复向量组,在其中找出该网的极小支集,并构造出该极小支集构的外延子网,然后利用文献[1]中给出的方式求解结构公平网的极小标识,得到了一个多项式时间算法。
论文目录
相关论文文献
- [1].关于进程段的T向量有效性[J]. 甘肃高师学报 2016(12)
- [2].Petri网系统中变迁的分级活性判定[J]. 长江大学学报(自然科学版)理工卷 2010(04)
- [3].Petri网系统的公平性判定[J]. 长春师范学院学报 2010(10)
- [4].一般网中结构公平的极小标识的求解算法[J]. 电脑知识与技术 2011(05)
- [5].Petri网本原可重复向量的求解算法及实现[J]. 小型微型计算机系统 2009(09)
- [6].Petri网死锁的求解算法[J]. 漳州师范学院学报(自然科学版) 2011(01)