第二部分Petri网的动态质

1、第二部分 petri网的动态性质提纲n网系统网系统(以原型以原型petri网为模型网为模型)运行过程中的一些运行过程中的一些性质统称为动态性质性质统称为动态性质(dynamic properties) 或行为性质或行为性质(behavioral properties)n这些性质同这些性质同petri网所模拟的实际系统运行过程中网所模拟的实际系统运行过程中的某些方面的性质有密切的联系的某些方面的性质有密切的联系提纲n可达性可达性n有界性和安全性有界性和安全性n活性活性n公平性公平性n持续性持续性可达性n可达性是可达性是petri网的最基本的动态性质，其余各种性质都要通过可达网的最基本的动态性质，

2、其余各种性质都要通过可达性来定义性来定义n定义定义2.1. 设设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

3、设初始标识设初始标识m0表示系统的初始状态，表示系统的初始状态，r(m0)给给出系统运行过程中可能出现的全部状态的集合。出系统运行过程中可能出现的全部状态的集合。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为初始标识。

4、则：为初始标识。则： (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的一个的一个可返回标识可返回标识或一个或一个家态家态

5、（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) 。证

6、明：证明：因为因为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网网, p p。若存在正整数。若存在正整数b, 使得使得 m r(m0): m(p) b, 则称库所则称库所p为为有界的有界的(bounded)。并称满足此条件的最小正整数并称满足此条件的最小正整数b为库所为库所p的界，记为的界，记为b(p)。即。即b(p)=minb| m r(m0):

7、 m(p) b 当当b(p)=1时，称库所时，称库所p为为安全的安全的（safe）。）。n定义定义2.5. 设设pn=(p,t;f, m0)为一个为一个petri网网。如果每个。如果每个p p都是都是有界的，则称有界的，则称pn为为有界有界petri网网。称。称 b(pn)=maxb(p)| p p为为pn的界。当的界。当b(pn)=1时，称时，称pn为为安全的安全的。有界性和安全性p1p2t1t2p4p6p5t3t4p3p0t0t5p1p2t1t2p4t3t4p3petripetri网的有界性（网的有界性（boundednessboundedness）反映）反映被模拟系统运行过程中对有关资源

8、的容量要求被模拟系统运行过程中对有关资源的容量要求库所库所p p3 3无界无界其它库所的界为其它库所的界为1 1b(p1) =b(p2) =b(p3)=2 其它库所界为其它库所界为1 1有界性和安全性n定理定理2.2. 设设pn=(p,t;f, m0)为一个为一个petri网网。r(m0)为有限集当且仅当为有限集当且仅当pn是有界的。是有界的。 证：证：活性npetri网活性（网活性（liveness）概念的提出源于对实际系统运行中是否会出现死锁的探索）概念的提出源于对实际系统运行中是否会出现死锁的探索的需要。的需要。n定义定义2.6. 设设pn=(p,t;f, m0)为一个为一个petri网

9、，网， m0为初始标识，为初始标识，t t。如果对任意。如果对任意m r(m0)，都存在，都存在m r(m)，使得，使得mt，则称变迁，则称变迁t为为活的活的。 如果每个如果每个t t 都是活的，则称都是活的，则称pn为活的为活的petri网。网。p1p2t1t2t3p1p2t1t2p4t3t4p32t1 1和和t t2 2是活的，是活的， t3是不活的是不活的不活的不活的活的活的活性n与实际系统中的无死锁概念更为接近的定义。与实际系统中的无死锁概念更为接近的定义。n定义定义2.7. 设设pn=(p,t;f, m0)为一个为一个petri网，网， 如果对如果对m r(m0)， 使得使得 t t

10、： 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)， 即即 t t： mt。从而不存在。从而不存在m r(m)，使得，使得mt。即任一个变迁都不是活

11、的，这同假设矛盾。即任一个变迁都不是活的，这同假设矛盾。活性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)为一个为一个petri网，网， t t。若若 m r(m0)： mt，则称变迁，则称变迁t为为死的死的。如果一个如果一个petripetri网中没有死变迁，网中没有死变迁，那么它是活的吗？是弱活的吗？那么它是活的吗？是弱活的

12、吗？p1p2t1t2t3t3是死变迁是死变迁公平性n在在petri网中引入公平性（网中引入公平性（fairness）概念，旨在讨论网系统中两个变迁的）概念，旨在讨论网系统中两个变迁的发生之间的相互关系。这种关系反映被模拟系统的各个部分在资源竞争中的发生之间的相互关系。这种关系反映被模拟系统的各个部分在资源竞争中的无饥饿性问题。无饥饿性问题。n定义定义2.9. 设设pn=(p,t;f, m0)为一个为一个petri网，网， m0为初始标识，为初始标识，t1,t2 t。如果存在正整数如果存在正整数k，使得，使得 m r(m0) ， t*：m都有都有 #(, ti) =0#(, t3-i)k, i=

13、1,2 则称变迁则称变迁t1和和t2处于处于公平关系公平关系。 如果如果pn中任意两个变迁都处于公平关中任意两个变迁都处于公平关系，则称系，则称pn为为公平公平petri网网。其中。其中 #(, ti)表示在序列表示在序列中中ti的出现次数。的出现次数。n如果如果pn中不存在可发生的无限变迁序列，则网系统总是公平的。中不存在可发生的无限变迁序列，则网系统总是公平的。公平性n定义定义2.10. 设设pn=(p,t;f, m0)为一个为一个petri网，网， m0为初始标识，为初始标识，t1,t2 t。如果。如果 m r(m0)，都，都存在正整数存在正整数k，使得，使得 t*：m都有都有 #(,

14、ti) =0#(, t3-i)k, i=1,2 则称变迁则称变迁t1和和t2处于处于弱公平关系弱公平关系。 如果如果pn中任意两个变迁都处于弱公平关系，则中任意两个变迁都处于弱公平关系，则称称pn为为弱公平弱公平petri网网。p1t1t2p4t4p3p2t3t2和和 t3是公平关是公平关系，也是弱公平系，也是弱公平关系关系t2和和 t3是弱公平是弱公平关系，但不是公关系，但不是公平关系平关系公平性n定理定理2.4. petri网中变迁之间的公平关系是一种等价关系网中变迁之间的公平关系是一种等价关系 证：证：公平关系的自反性和对称性是显然的。下面证明其传递性。公平关系的自反性和对称性是显然的。

15、下面证明其传递性。 设设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

16、 ， #(, 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=(p,t;f, m0)为一个持续网系统。对于为

17、一个持续网系统。对于任意任意 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)都是持续网系都是持续网系统统。证明：已知证明：已知 m r(m0) 和任意和任意t1,t2 t (t1 t2)，有，有( mt1 mt2m)。并且并且 t1t2 = , t1t2 = 证明证明mt1 。公平性实例n变迁序列：变迁序列：(1) (t1t2t3t4)* k=1(2) 弱公平弱公平非公平，因为若