二部分Petri网的动态质.ppt

第二部分 Petri网的动态性质 提纲 n网系统(以原型Petri网为模型)运行过程中的一些 性质统称为动态性质(dynamic properties) 或行为性质(behavioral properties) n这些性质同Petri网所模拟的实际系统运行过程中 的某些方面的性质有密切的联系 提纲 n可达性 n有界性和安全性 n活性 n公平性 n持续性 可达性 n可达性是Petri网的最基本的动态动态 性质质，其余各种性质质都要通过过可达 性来定义义 n定义2.1. 设PN=(P,T;F,M)为一个Petri网。 如果存在tT，使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)给给 出系统统运行过过程中可能出现现的全部状态态的集合。 n定义2.2. 设PN=(P,T;F, M0)为一个Petri网, M0为为初始标识标识 。PN的可达标识标识 集R(M0)定义义 为满为满 足下面两条件的最小集合： （1） M0 R(M0)； （2）若M R(M0)，且存在tT，使得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)当且 仅当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为为可逆网系统统（reversible 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)。 有界性和安全性 n定义2.4. 设PN=(P,T;F, M0)为一个Petri网, pP。若存在正整数 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网。如果每个pP都是有 界的，则则称PN为为有界Petri网。称 B(PN)=maxB(p)| p P 为PN的界。当B(PN)=1时，称PN为安全的。 有界性和安全性 p1p2 t1t2 p4p6p5 t3 t4 p3 p0 t0t5 p1 p2 t1t2 p4 t3 t4 p3 Petri网的有界性（boundedness）反映 被模拟系统运行过程中对有关资源的容量要求 库所p3无界 其它库所的界为1 B(p1) =B(p2) =B(p3)=2 其它库所界为1 有界性和安全性 n定理2.2. 设PN=(P,T;F, M0)为一个Petri网。R(M0)为为有限集当且仅仅当 PN是有界的。 证证： 活性 nPetri网活性（Liveness）概念的提出源于对实际对实际 系统统运行中是否会出现现死锁锁的探 索的需要。 n定义2.6. 设PN=(P,T;F, M0)为一个Petri网， M0为初始标识，tT。如果对对任意 M R(M0)，都存在M R(M)，使得Mt，则则称变变迁t为为活的。 如果每个tT 都是活的，则则称PN为为活的Petri网。 p1 p2 t1t2t3 p1 p2 t1t2 p4 t3 t4 p3 2 t1和t2是活的， t3是不活的 不活的 活的 活性 n与实际实际 系统统中的无死锁锁概念更为为接近的定义义。 n定义2.7. 设PN=(P,T;F, M0)为一个Petri网， 如果对对M R(M0)， 使得 tT：Mt，则则称M为为PN的一个死标识标识 （ dead marking）。如果PN中不存在死标识标识 ，则则称PN为为弱活 的（weak live）或者不死的（non-dead）。 n定理2.3.设PN=(P,T;F, M0)为一个Petri网。若PN中有一个 变迁是活的，则PN是弱活的。 证证：用反证证法。假设设PN不是弱活的，则则必存在一个死标识标识 M R(M0)， 即 tT：Mt。从而不存在M R(M)，使得 Mt。即任一个变变迁都不是活的，这这同假设设矛盾。 活性 p1 p5 t1 t2 p4 t5 t4 p3 t3 p2 t6 PN是弱活的，但不是活的 (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) t4t5t3 t2t1 t6 活性 n定义2.8.设PN=(P,T;F, M0)为一个Petri网， tT。 若 M R(M0)： Mt，则则称变变迁t为为死的。 如果一个Petri网中没有死变迁 ，那么它是活的吗？是弱活的 吗？ p1 p2 t1t2t3 t3是死变迁 公平性 n在Petri网中引入公平性（fairness）概念，旨在讨论讨论 网系统统中两个变变迁的 发发生之间间的相互关系。这这种关系反映被模拟拟系统统的各个部分在资资源竞竞争中 的无饥饿饥饿 性问题问题 。 n定义2.9. 设PN=(P,T;F, M0)为一个Petri网， M0为初始标识，t1,t2T 。如果存在正整数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为初始标识，t1,t2T。如果 M R(M0)，都存在正整数k，使得 T*：M都有 #(, ti) =0#(, t3-i)k, i=1,2 则则称变变迁t1和t2处处于弱公平关系。 如果PN中任意两个变变迁都处处于弱公平关系， 则则称PN为为弱公平Petri网。 p1 t1 t2 p4 t4 p3 p2 t3 t2和 t3是公平关 系，也是弱公平 关系 t2和 t3是弱公平 关系，但不是公 平关系 公平性 n定理2.4. Petri网中变迁之间的公平关系是一种等价关系 证：公平关系的自反性和对称性是显然的。下面证明其传递性。 设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 则则由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,t2T (t1 t2)，有 ( Mt1 Mt2M) Mt1 则则称PN为为持续续网系统统。 n定理2.5.设PN=(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,t2T (t1 t2)， t1和t2 在M不存在冲突。 持续性 n定理2.7. 若N=(P,T;F)为一个T-图，则对N的 任意初始标识M0，PN =(N, M0)都是持续网系 统。 证证明：已知 M R(M0) 和任意t1,t2T (t1 t2)，有( Mt1 Mt2M)。 并且 t1t2 = , t1t2 = 证证明Mt1 。 公平性实例 n变迁序列： (1) (t1t2t3t4)* k=1 (2) 弱公平 非公平，因为