Petri网

1Chapter3Petri网（一）基本定义（1）Petri网结构（2）普通网（3）位置/迁移Petri网（二）Petri网的性质（1）行为性质（2）结构性质（三）Petri网分析技术（1）结构化简（2）可达树、覆盖树（3）状态方程、不变量（四）Petri网规格的例（1）哲学家就餐问题（2）生产者-消费者问题Petri网的概念最早是由德国的CarlAdamPetri于1962年在其博士论文《自动机通信》中提出来的。它是一种适合于并发、异步、分布式软件系统规格与分析的形式化方法。Petri网分为位置/迁移Petri网和高级Petri网两类。高级Petri网包括：谓词/迁移Petri网、有色Petri网、计时Petri网等。2（一）基本定义任何系统都可抽象为状态（或者条件）、活动（或者事件）及其之间关系的三元结构。在Petri网中，状态用位置（place）表示，活动用迁移（transition）表示。迁移的作用是改变状态，位置的作用是决定迁移能否发生，迁移和位置之间的这种依赖关系用流来表示。Petri网结构---Petri网结构是一个三元组N=（P，T，F），其中，①P={p1，p2，…，pn}是有限位置集合；②T={t1，t2，…，tn}是有限迁移集合（PT，PT=）；③F（P×T）（T×P）为流关系。p2p4t2p1p3p5p6t1t3t4t5例：Petri网结构N=（P，T，F）P={p1，p2，p3，p4，p5，p6}；T={t1，t2，t3，t4，t5}；F={(p1，t1)，(t1，p2)，(t1，p3)，(p2，t2)，(p3，t3)，(t2，p4)，(t3，p5)，(p4，t4)，(p5，t4)，(t4，p6)，(p6，t5)，(t5，p1)}3（一）基本定义子网结构---对于N1=（P1，T1，F1）和N2=（P2，T2，F2），如果P1P2，T1T2且F1=F2（（P1×T1）（T1×P1）），则称N1是N2的子网结构。p2p4t2p1p3p5p6t1t3t4t5p2p4t2p1p3p5p6t1t3t4p2p4t2p1p3p5t1t3t4t5前集和后集：对于一个Petri网结构N=（P，T；F），设x∈(PT)，令x={y︱y：(y，x)F};x={y︱y：(x，y)F}，那么称x为x的前集或输入集，x称为x的后集或输出集。在N=（P，T，F）中，如果对所有的x∈(PT)，都有xx=，则称N为单纯网（purenet），简称纯网；如果对所有的x，y∈X，都有(x=y)(x=y)x=y，则称N为简单网（simplenet）。Petri网允许位置中包含令牌（token），令牌可以依据迁移的引发而重新分布。具有动态特征的Petri网定义如下：普通Petri网：普通Petri网形式上定义为一个四元组PN=(P,T,F,M0）=(N，M0)，其中，①N=（P，T，F）是一个Petri网结构；②M：PZ（非负整数集合）是位置集合上的标识（marking）向量。对于任一位置pP,以M(p)表示标识向量M中位置p所对应的分量，称为位置p上的标识或者令牌数目。M0是初始标识向量。在Petri网的图形表示中，标记或令牌用位置中的黑点或数字表示，同一位置中的多个标记代表同一类完全等价的个体。标识向量表示了令牌在位置中的分布。5（一）基本定义在Petri网中，依据迁移的使能（enable）条件，可以使得使能的迁移引发（fire），迁移的引发会依据引发规则实现令牌的移动。不断变化着的令牌重新分布就描述了系统的动态行为演化。迁移的使能条件I---对于Petri网PN=（P,T,F,M），如果(p1)p1tM(p1)1，则称t在M下使能，记为M[t。迁移的引发规则I---对于Petri网PN=（P,T,F,M），任何在M下使能的迁移t将会引发，迁移t的引发使得位置中令牌重新分布，从而将标识M变成新标识M，并称M′为M的后继标识，并记为M[tM。对于pP，M(p)可通过下式计算：M(p)-1pt-tM(p)=M(p)+1pt-tM(p)其它p1p2t1t2p4p5p3t3t4p6p7t6t5（a）初始p1p2t1t2p4p5p3t3t4p6p7t6t5（b）引发t1p1p2t1t2p4p5p3t3t4p6p7t6t5（c）引发t2p1p2t1t2p4p5p3t3t4p6p7t6t5（d）引发t1和t2在图（a）所示Petri网中，变迁t1和t2是使能的。在这种情况下，该Petri网的演化，即令牌的变化就可能存在如下3种不同方式：引发t1，引发t2，或者引发t1和t2。也就是说，在给定Petri网的初始标识后，其演化过程可能是不同的，具有不确定性。引发t1所得到的图（b）所示状态；引发t2所得到的图（c）所示状态；引发t1和t2得到图（d）所示状态。在图（b）的情况下，变迁t2和t3使能。在引发变迁t2后，将得到图（d）所示状态。在图（c）的情况下，变迁t1和t4使能。在引发变迁t1后，将同样得到图（d）所示状态。p1p2t1t2p4p5p3t3t4p6p7t6t5(e)引发t3p1p2t1t2p4p5p3t3t4p6p7t6t5（f）引发t4图（d）所示Petri网中，变迁t3和t4是使能的。令牌的变化就可能存在如下2种不同方式：引发t3，或者引发t4。引发t3得到图（e）所示的下一个状态；引发t4得到图（f）所示状态。在图（e）的情况下，变迁t5使能，引发变迁t5后，将得到图（c）所示状态。在图（f）的情况下，变迁t6使能,引发变迁t6后，将得到图（b）所示状态。p1p2t1t2p4p5p3t3t4p6p7t6t5（b）引发t1p1p2t1t2p4p5p3t3t4p6p7t6t5（c）引发t2（一）基本定义一个没有任何输入位置的迁移叫源迁移，一个源迁移的使能是无条件的。一个源迁移的引发只会产生令牌，而不消耗任何令牌；一个没有任何输出位置的迁移叫阱迁移，一个阱迁移的引发只会消耗令牌，而不产生任何新的令牌。p2p4t2p3p5t1t3t4t5位置/迁移Petri网---位置/迁移Petri网，简称为Petri网，形式上定义为一个六元组PN=（P,T,F,K,W,M0）=(N，K,W,M0)，其中，①N=（P，T，F）是一个Petri网结构；②K：P→Z+{}是位置上的容量函数（Z+是正整数集合），规定了位置上可以包含的令牌的最大数目。对于任一位置pP,以K(p)表示向量K中位置p所对应的分量，若K（p）=，表示位置p的容量为无穷；9③W：F→Z+，是流关系上的权函数，规定了令牌传递中的加权系数。对于任一弧f∈F，以W(f)表示向量W中弧f所对应的分量；④M：PZ（非负整数集合）是位置集合上的标识向量。对于任一位置pP,以M(p)表示标识向量M中位置p所对应的分量，并且必须满足M(p)K(p)。M0是初始标识向量。10在Petri网的图形表示中，对于弧f∈F，当W（f）1时，将W（f）标注在弧上，当W（f）=1时，省略W（f）的标注；当一个位置的容量有限时，通常将K（p）写在位置p的圆圈旁。当K（p）=∞时，通常省略K（p）的标注。容量函数和权函数均为常量1的Petri网称为基本Petri网（简称基本网）或条件/事件网。容量函数恒为无穷和权函数恒为1的Petri网称为普通Petri网，简称为普通网。显然，基本网和普通网都是Petri网的特殊情形。基本网和普通网可以用四元组PN=（P，T，F，M）来表示。迁移的使能条件II：对于Petri网PN=（P,T,F,K,W,M），如果(p1)p1tM(p1)W（p1，t）且(p2)p2∈tK(p2)M(p2)+W(t,p2)，则称t在M下使能，记为M[t。迁移的引发规则II：对于Petri网PN=（P,T,F,K,W,M），任何在M下使能的迁移t将会引发，迁移t的引发使得位置中令牌重新分布，从而将标识M变成新标识M，并记为M[tM。对于pP，M(p)可通过下式计算：M(p)–W(p,t)pt-tM(p)=M(p)+W(t,p)pt-tM(p)–W(p,t)+W(t,p)pttM(p)pttp1p23464p3p4p5p6t12t2t333t4t5W（t1，p2）=2，W（t3，p5）=3，W（p6，t5）=3，W（p1，t1）=W（t1，p3）=W（p2，t2）=W（p3，t3）=W（t2，p4）=W（p4，t4）=W（p5，t4）=W（t4，p6）=W（t5，p1）=1，K（p2）=3，K（p4）=K（p5）=4，K（p6）=6，K（p1）=K（p3）=K（p5）=∞，M=（1，0，0，1，0，0）的Petri网p1p23464p3p4p5p6t12t2t333t4t5p4t2p1p23464p3p5p6t12t333t4t5p4t2p1p23464p3p5p6t12t333t4t5p4t2p1p23464p3p5p6t12t333t4t5p4t2p1p23464p3p5p6t12t333t4t5p4t2p1p23464p3p5p6t12t333t4t5p4t2p1p23464p3p5p6t12t333t4t5p4t2p1p23464p3p5p6t12t333t4t5p4t2p1p23464p3p5p6t12t333t4t5p4t2p1p23464p3p5p6t12t333t4t5顺序、并发、冲突、混惑结构的Petri网模型：顺序关系：设M为Petri网PN的一个标识，若存在t1和t2使得M[t1M，且M[t2，M[t2，亦即，在M标识下，t1使能，而t2不使能，且t1的引发会使t2使能，即t2的使能以t1的引发为条件，则称t1和t2在M下有顺序关系。并发关系：设M为Petri网PN的一个标识，若存在t1和t2使得M[t1和M[t2，并满足M[t1M1M1[t2，且M[t2M2M2[t1，则称t1和t2在M下并发。就是说在M标识下，t1和t2都使能，且它们当中任一个迁移的引发都不会使另一个迁移不使能。冲突关系：设M为Petri网PN的一个标识，若存在t1和t2使得M[t1和M[t2，并满足M[t1M1M1[t2，且M[t2M2M2[t1，则称t1和t2在M下冲突。就是说M标识下，t1和t2都使能，但它们当中任一个迁移引发都会使另一个迁移不使能。p2t2p1p3t1p1p3p2p4t2t1t3p1p3p2p4t2t1p5混惑关系：某些情形下，一个Petri网中可能同时存在着并发和冲突，而且并发迁移的引发会引起冲突的消失或出现。下图所示的Petri网中，t1和t3是两个并发迁移，若t3先于t1引发，则t2获得发生权，而且t2和t1处于竞争资源的冲突状态。若进一步在解决冲突时让t2引发，则t1就失去了曾经拥有的发生权。如果在t1和t2的冲突中让t1引发，则p5获得令牌，系统到达最终状态（0，0，1，0，1，0）。从初始状态（1，1，0，1，0，0）到达（0，0，1，0，1，0）的另一种可能是t1先引发，然后t3引发。t1和t3并发也到达这一状态。这后两种情况不会出现冲突。换句话说，从所观察到的状态变化（1，1，0，1，0，0）→（0，0，1，0，1，0），无法判断其间是否出现过冲突，象这样并发和冲突混合在一起产生的困惑，使人无法从终态判断是否有冲突发生过，所以将这种情况称为“混惑”。p6t1p1p5t2p3p4p2t316（二）Petri网的性质Petri网具有两类性质：与初始标识有关的和与初始标识无关的。前者称为标识有关性质或者行为性质，后者称为标识无关性质或者结构性质。（1）行为性质可达性：可达性是研究任何系统动态行为的基础。按照迁移引发规则，使能迁移的引发将改变令牌的分布（产生新的标识）。对于初始标识M0，如果存