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

* * * * * * * * * * * * * * 第二部分 Petri网的动态性质 提纲 网系统(以原型Petri网为模型)运行过程中的一些性质统称为动态性质(dynamic properties) 或行为性质(behavioral properties) 这些性质同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的一个可返回标识或一个家态（home state）。 定义2.4. 设PN=(P,T;F, M0)为一个Petri网。如果M0是一个家态，则称PN为可逆网系统（reversible net system），或称可回复系统。 网系统家态的存在是一个良好性质，在评测系统性能或在系统模拟过程中具有非常关键的作用。 可达性 推论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为安全的。 有界性和安全性 p1 p2 t1 t2 p4 p6 p5 t3 t4 p3 p0 t0 t5 p1 p2 t1 t2 p4 t3 t4 p3 Petri网的有界性（boundedness）反映 被模拟系统运行过程中对有关资源的容量要求 库所p3无界 其它库所的界为1 B(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，则称