第二章-Petri网的基本概念及性质

第二部分Petri网的动态性质提纲网系统(以原型Petri网为模型)运行过程中的一些性质统称为动态性质(dynamicproperties)或行为性质(behavioralproperties)这些性质同Petri网所模拟的实际系统运行过程中的某些方面的性质有密切的联系提纲可达性有界性和安全性活性公平性持续性可达性可达性是Petri网的最基本的动态性质，其余各种性质都要通过可达性来定义定义2.1.设PN=(P,T;F,M)为一个Petri网。如果存在tT，使M[tM’，则称M’为从M直接可达的如果存在变迁序列t1,t2,t3,,tk和标识序列M1,M2,M3,,Mk使得M[t1M1[t2M2,,Mk-1[tkMk(2.1)则称Mk为从M可达的从M可达的一切标识的集合记为R(M)，约定MR(M)如果记变迁序列t1,t2,t3,,tk为，则(2.1)式也可记为M[Mk可达性设初始标识M0表示系统的初始状态，R(M0)给出系统运行过程中可能出现的全部状态的集合。定义2.2.设PN=(P,T;F,M0)为一个Petri网,M0为初始标识。PN的可达标识集R(M0)定义为满足下面两条件的最小集合：（1）M0R(M0)；（2）若MR(M0)，且存在tT，使得M[tM’，则M’R(M0)可达性定理2.1.设PN=(P,T;F,M0)为一个Petri网，M0为初始标识。则：(1)对任意MR(M0)，都有R(M)R(M0)；(2)对任意M1,M2R(M0)，R(M1)=R(M2)当且仅当M1R(M2)且M2R(M1)。证：(1)由于MR(M0)，所以M’R(M):M’R(M0)，从而R(M)R(M0)。同理可证(2)。可达性定义2.3.设PN=(P,T;F,M0)为一个Petri网，MR(M0)。如果M’R(M0)，都有MR(M’)，则称M为PN的一个可返回标识或一个家态（homestate）。定义2.4.设PN=(P,T;F,M0)为一个Petri网。如果M0是一个家态，则称PN为可逆网系统（reversiblenetsystem），或称可回复系统。网系统家态的存在是一个良好性质，在评测系统性能或在系统模拟过程中具有非常关键的作用。可达性推论2.1.设PN=(P,T;F,M0)为一个Petri网，M1,M2是PN的家态，则R(M1)=R(M2)。证明：因为M1,M2是PN的家态，所以首先有M1R(M0)，M2R(M0)，进而M1R(M2)，M2R(M1)。根据定理2.1(2)，则有R(M1)=R(M2)。有界性和安全性定义2.4.设PN=(P,T;F,M0)为一个Petri网,pP。若存在正整数B,使得MR(M0):M(p)B,则称库所p为有界的(bounded)。并称满足此条件的最小正整数B为库所p的界，记为B(p)。即B(p)=min{B|MR(M0):M(p)B}当B(p)=1时，称库所p为安全的（safe）。定义2.5.设PN=(P,T;F,M0)为一个Petri网。如果每个pP都是有界的，则称PN为有界Petri网。称B(PN)=max{B(p)|pP}为PN的界。当B(PN)=1时，称PN为安全的。有界性和安全性p1p2t1t2p4p6p5t3t4p3p0t0t5p1p2t1t2p4t3t4p3Petri网的有界性（boundedness）反映被模拟系统运行过程中对有关资源的容量要求库所p3无界其它库所的界为1B(p1)=B(p2)=B(p3)=2其它库所界为1有界性和安全性定理2.2.设PN=(P,T;F,M0)为一个Petri网。R(M0)为有限集当且仅当PN是有界的。证：活性Petri网活性（Liveness）概念的提出源于对实际系统运行中是否会出现死锁的探索的需要。定义2.6.设PN=(P,T;F,M0)为一个Petri网，M0为初始标识，tT。如果对任意MR(M0)，都存在M’R(M)，使得M’[t，则称变迁t为活的。如果每个tT都是活的，则称PN为活的Petri网。p1p2t1t2t3p1p2t1t2p4t3t4p32t1和t2是活的，t3是不活的不活的活的活性与实际系统中的无死锁概念更为接近的定义。定义2.7.设PN=(P,T;F,M0)为一个Petri网，如果对MR(M0)，使得tT：M[t，则称M为PN的一个死标识（deadmarking）。如果PN中不存在死标识，则称PN为弱活的（weaklive）或者不死的（non-dead）。定理2.3.设PN=(P,T;F,M0)为一个Petri网。若PN中有一个变迁是活的，则PN是弱活的。证：用反证法。假设PN不是弱活的，则必存在一个死标识MR(M0)，即tT：M[t。从而不存在M’R(M)，使得M’[t。即任一个变迁都不是活的，这同假设矛盾。活性p1p5t1t2p4t5t4p3t3p2t6PN是弱活的，但不是活的(1,0,0,0,0)(0,0,0,1,0)(0,0,1,0,0)(0,0,0,0,1)(0,1,0,0,0)t4t5t3t2t1t6活性定义2.8.设PN=(P,T;F,M0)为一个Petri网，tT。若MR(M0)：M[t，则称变迁t为死的。如果一个Petri网中没有死变迁，那么它是活的吗？是弱活的吗？？p1p2t1t2t3t3是死变迁公平性在Petri网中引入公平性（fairness）概念，旨在讨论网系统中两个变迁的发生之间的相互关系。这种关系反映被模拟系统的各个部分在资源竞争中的无饥饿性问题。定义2.9.设PN=(P,T;F,M0)为一个Petri网，M0为初始标识，t1,t2T。如果存在正整数k，使得MR(M0)，σT*：M[σ都有#(σ,ti)=0→#(σ,t3-i)k,i=1,2则称变迁t1和t2处于公平关系。如果PN中任意两个变迁都处于公平关系，则称PN为公平Petri网。其中#(σ,ti)表示在序列σ中ti的出现次数。如果PN中不存在可发生的无限变迁序列，则网系统总是公平的。公平性定义2.10.设PN=(P,T;F,M0)为一个Petri网，M0为初始标识，t1,t2T。如果MR(M0)，都存在正整数k，使得σT*：M[σ都有#(σ,ti)=0→#(σ,t3-i)k,i=1,2则称变迁t1和t2处于弱公平关系。如果PN中任意两个变迁都处于弱公平关系，则称PN为弱公平Petri网。p1t1t2p4t4p3p2t3t2和t3是公平关系，也是弱公平关系t2和t3是弱公平关系，但不是公平关系公平性定理2.4.Petri网中变迁之间的公平关系是一种等价关系证：公平关系的自反性和对称性是显然的。下面证明其传递性。设t1和t2处于公平关系，即存在k1，使得MR(M0)，σT*：M[σ都有#(σ,t1)=0→#(σ,t2)k1#(σ,t2)=0→#(σ,t1)k1把σ写成σ=σ0t2σ1t2σ2t2σ3σj-1t2σj,jk1.显然#(σi,t2)=0设t2和t3处于公平关系，即存在k2，使得MR(M0)，σ’T*：M[σ’都有#(σ’,t2)=0→#(σ’,t3)k2#(σ’,t3)=0→#(σ’,t2)k2则由t2和t3的公平关系可知#(σi,t3)k2，#(σ,t3)k2(j+1)k2(k1+1)k.其中k=max{k2(k1+1),k1(k2+1)}即#(σ,t1)=0→#(σ,t3)k同理可证#(σ,t3)=0→#(σ,t1)k所以，t1和t3处于公平关系。持续性定义2.11.设PN=(P,T;F,M0)为一个Petri网。如果对任意MR(M0)和任意t1,t2T(t1t2)，有(M[t1M[t2M’)→M’[t1则称PN为持续网系统。定理2.5.设PN=(P,T;F,M0)为一个持续网系统。对于任意MR(M0)，如果M[t1且M[σ，#(σ,t1)=0，则有M[t1σ且M[σt1。证明：对σ的长度进行数学归纳。持续性定理2.6.设N=(P,T;F)为一个纯网，那么PN=(N,M0)是持续网系统的充要条件MR(M0)，t1,t2T(t1t2)，t1和t2在M不存在冲突。持续性定理2.7.若N=(P,T;F)为一个T-图，则对N的任意初始标识M0，PN=(N,M0)都是持续网系统。证明：已知MR(M0)和任意t1,t2T(t1t2)，有(M[t1M[t2M’)。并且•t1∩•t2=Φ,t1•∩t2•=Φ证明M’[t1。公平性实例变迁序列：(1)(t1t2t3t4)*k=1(2)弱公平非公平，因为若选定某个k,则只要让p1中存储k+1个token,就无法满足条件定理2.5(1)|\sigma|=1,M[t1且M[t2,则根据持续网的定义，M[t1t2且M[t2t1(2)假设|\sigma|=n时结论成立，那么对于t2\sigma’t3(|\sigma’|=n-1)则有:M[t1且M[t2,所以M[t2M’[\sigma’t3且M[t2M’[t1，根据归纳假设，M’[\sigma’t3t1,所以M[t1t2\sigma’t3同时，M[t2\sigma’M’[t3,而根据归纳假设，M[t2\sigma’t1，所以M’[t1],