《第二分Petri网的动态性质》由会员分享，可在线阅读，更多相关《第二分Petri网的动态性质（23页珍藏版）》请在金锄头文库上搜索。
1、第二部分 Petri网的动态性质提纲n网系网系统(以原型以原型Petri网网为模型模型)运行运行过程中的一些程中的一些性性质统称称为动态性性质(dynamic properties) 或行或行为性性质(behavioral properties)n这些性些性质同同Petri网所模网所模拟的的实际系系统运行运行过程中程中的某些方面的性的某些方面的性质有密切的有密切的联系系提纲n可达性可达性n有界性和安全性有界性和安全性n活性活性n公平性公平性n持持续性性可达性n可达性是可达性是Petri网的最基本的网的最基本的动态性性质，其余各种性，其余各种性质都要通都要通过可达可达性来定性来定义n定定义2.1
2、. 设PN=(P,T;F,M)为一个一个Petri网。网。如果存在如果存在t T，使，使MtM，则称称M为从从M直接可达的直接可达的如果存在如果存在变迁序列迁序列t1, t2, t3,tk和和标识序列序列M1,M2, M3,Mk使得使得 Mt1M1t2M2,Mk-1 tkMk (2.1) 则称称Mk为从从M可达的可达的从从M可达的一切可达的一切标识的集合的集合记为R(M)，约定定M R(M) 如果如果记变迁序列迁序列t1, t2, t3,tk为 ，则(2.1)式也可式也可记为M Mk 可达性n设初始初始标识M0表示系表示系统的初始状的初始状态，R(M0)给出系出系统运行运行过程中可能出程中可能
3、出现的全部状的全部状态的集合。的集合。n定定义2.2. 设PN=(P,T;F, M0)为一个一个Petri网网, M0为初始初始标识。PN的的可达可达标识集集R(M0)定定义为满足下面两条件的最小集合：足下面两条件的最小集合： （1） M0 R(M0)； （2）若）若M R(M0)，且存在，且存在t T，使得，使得MtM，则，则M R(M0) 可达性n定理定理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)
4、当且当且仅当仅当M1 R(M2)且且M2 R(M1) 。证：证：(1) 由于由于M R(M0)，所以，所以 M R(M): M R(M0) ，从而，从而R(M) R(M0) 。 同理可证同理可证(2)。可达性n定定义2.3. 设PN=(P,T;F, M0)为一个一个Petri网，网，M R(M0)。如果。如果 M R(M0)，都有，都有M R(M )，则称称M为PN的一个的一个可返回可返回标识或一个或一个家家态（home state）。）。n定定义2.4. 设PN=(P,T;F, M0)为一个一个Petri网网。如果。如果M0是一个家是一个家态，则称称PN为可逆网系可逆网系统（reversib
5、le net system），或称可回复系），或称可回复系统。网系统家态的存在是一个良好性质，在评测系统性能或在系统模拟过程中网系统家态的存在是一个良好性质，在评测系统性能或在系统模拟过程中具有非常关键的作用。具有非常关键的作用。可达性n推推论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)。有界性和
6、安全性n定定义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)=minB| M R(M0): M(p) B 当当B(p)=1时，称，称库所所p为安全的安全的（safe）。）。n定定义2.5. 设PN=(P,T;F, M0)为一个一个Petri网网。如果每个。如果每个p P都是都是有界的，有界的，则称称PN为有界有界Petri网网。称。称 B(P
7、N)=maxB(p)| p P为为PN的界。当的界。当B(PN)=1时，称时，称PN为为安全的安全的。有界性和安全性p1p2t1t2p4p6p5t3t4p3p0t0t5p1p2t1t2p4t3t4p3PetriPetri网的有界性（网的有界性（boundednessboundedness）反映）反映被模拟系统运行过程中对有关资源的容量要求被模拟系统运行过程中对有关资源的容量要求库所库所p p3 3无界无界其它库所的界为其它库所的界为1 1B(p1) =B(p2) =B(p3)=2 其它库所界为其它库所界为1 1有界性和安全性n定理定理2.2. 设PN=(P,T;F, M0)为一个一个Petri
8、网网。R(M0)为有限集当且有限集当且仅当当PN是有界的。是有界的。 证：活性nPetri网活性（网活性（Liveness）概念的提出源于）概念的提出源于对实际系系统运行中是否会出运行中是否会出现死死锁的探索的探索的需要。的需要。n定定义2.6. 设PN=(P,T;F, M0)为一个一个Petri网，网， M0为初始初始标识，t T。如果。如果对任意任意M R(M0)，都存在，都存在M R(M)，使得，使得Mt，则称称变迁迁t为活的活的。 如果每个如果每个t T 都是活的，都是活的，则称称PN为活的活的Petri网。网。p1p2t1t2t3p1p2t1t2p4t3t4p32t1 1和和t t2
9、 2是活的，是活的， t3是不活的是不活的不活的不活的活的活的活性n与与实际系系统中的无死中的无死锁概念更概念更为接近的定接近的定义。n定定义2.7. 设PN=(P,T;F, M0)为一个一个Petri网，网， 如果如果对M R(M0)， 使得使得 t T： Mt，则称称M为PN的一个的一个死死标识（dead marking）。如果）。如果PN中不存在死中不存在死标识，则称称PN为弱弱活的活的（weak live）或者）或者不死的不死的（non-dead）。）。n定理定理2.3.设PN=(P,T;F, M0)为一个一个Petri网。若网。若PN中有一个中有一个变迁是活的，迁是活的，则PN是弱活
10、的。是弱活的。 证：用反用反证法。假法。假设PN不是弱活的，不是弱活的，则必存在一个死必存在一个死标识M R(M0)， 即即 t T： Mt。从而不存在。从而不存在M R(M)，使得，使得Mt。即任一个。即任一个变迁都不是活的，迁都不是活的，这同假同假设矛盾。矛盾。活性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活性n定定义2.8.设PN=(P,T;F, M0)为一个一个Petr
11、i网，网， t T。若若 M R(M0)： Mt，则称称变迁迁t为死的死的。如果一个如果一个PetriPetri网中没有死变迁，网中没有死变迁，那么它是活的吗？是弱活的吗那么它是活的吗？是弱活的吗？p1p2t1t2t3t3是死变迁是死变迁公平性n在在Petri网中引入公平性（网中引入公平性（fairness）概念，旨在）概念，旨在讨论网系网系统中两个中两个变迁的迁的发生之生之间的相互关系。的相互关系。这种关系反映被模种关系反映被模拟系系统的各个部分在的各个部分在资源源竞争中的争中的无无饥饿性性问题。n定定义2.9. 设PN=(P,T;F, M0)为一个一个Petri网，网， M0为初始初始标识
12、，t1,t2 T。如果存在正整数如果存在正整数k，使得，使得 M R(M0) ， T*：M都有都有 #(, ti) =0#(, t3-i) k, i=1,2 则称称变迁迁t1和和t2处于于公平关系公平关系。 如果如果PN中任意两个中任意两个变迁都迁都处于公平关系，于公平关系，则称称PN为公平公平Petri网网。其中。其中 #(, ti)表示在序列表示在序列中中ti的出的出现次数。次数。n如果如果PN中不存在可中不存在可发生的无限生的无限变迁序列，迁序列，则网系网系统总是公平的。是公平的。公平性n定定义2.10. 设PN=(P,T;F, M0)为一个一个Petri网，网， M0为初始初始标识，t
13、1,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是弱公平是弱公平关系，但不是公关系，但不是公平关系平关系公平性n定理定理2.4. Petri网中网中变迁之迁之间的公平关系是一种等价关系的公平关系是一种等价关系
14、证：公平关系的自反性和公平关系的自反性和对称性是称性是显然的。下面然的。下面证明其明其传递性。性。 设t1和和t2处于公平关系，即存在于公平关系，即存在k1，使得，使得 M R(M0) ， T*：M都有都有 #(, t1) =0#(, t2) k1 #(, t2) =0#(, t1) k1 把把写成写成 = 0 t2 1 t2 2 t2 3 j-1 t2 j, j k1. 显然然#(i , t2) =0 设t2和和t3处于公平关系，即存在于公平关系，即存在k2，使得，使得 M R(M0) ， T*：M都有都有 #(, t2) =0#(, t3) k2 #(, t3) =0#(, t2) k2
15、则由由t2和和t3的公平关系可知的公平关系可知#(i, t3) k2 ， #(, t3) k2(j+1) k2 (k1+1) k. 其中其中k=maxk2 (k1+1) , k1 (k2+1) 即即#(, t1) =0#(, t3) k 同理可同理可证#(, t3) =0#(, t1) k 所以，所以，t1和和t3处于公平关系。于公平关系。持续性n定定义2.11.设PN=(P,T;F, M0)为一个一个Petri网。如果网。如果对任意任意 M R(M0) 和任意和任意t1,t2 T (t1 t2)，有，有 ( Mt1 Mt2M) Mt1 则称称PN为持持续网系网系统。n定理定理2.5.设PN=
16、(P,T;F, M0)为一个持一个持续网系网系统。对于于任意任意 M R(M0)，如果，如果 Mt1 且且M， #(, t1) =0，则有有Mt1 且且Mt1。证明：明：对的的长度度进行数学行数学归纳。持续性n定理定理2.6. 设N=(P,T;F)为一个一个纯网，那网，那么么PN =(N, M0)是持是持续网系网系统的充要条件的充要条件 M R(M0) ， t1,t2 T (t1 t2)， t1和和t2 在在M不存在冲突。不存在冲突。持续性n定理定理2.7. 若若N=(P,T;F)为一个一个T-图，则对N的的任意初始任意初始标识M0，PN =(N, M0)都是持都是持续网系网系统。证明：已知明
17、：已知 M R(M0) 和任意和任意t1,t2 T (t1 t2)，有，有( Mt1 Mt2M)。并且并且 t1t2 = , t1t2 = 证明明Mt1 。公平性实例n变变迁序列：迁序列：(1) (t1t2t3t4)* k=1(2) 弱公平弱公平非公平，因非公平，因为若若选定某个定某个k, 则只要只要让p1中存中存储k+1个个token, 就无法就无法满足条件足条件定理2.5n(1) |sigma|=1,Mt1 且且 Mt2, 则根据持根据持续网的定网的定义，Mt1t2且且Mt2t1(2) 假假设|sigma|且且Mt2, 所以所以Mt2Msigma t3且且Mt2Mt1 ，根据根据归纳归纳假假设设，M sigma t3t1, 所以所以Mt1t2sigma t3同同时，Mt2sigma Mt3, 而根据而根据归纳归纳假假设设，Mt2sigma t1，所以所以Mt1,
