《第二部分Petri网的动态性质.ppt》由会员分享，可在线阅读，更多相关《第二部分Petri网的动态性质.ppt（23页珍藏版）》请在三一文库上搜索。
1、第二部分 Petri网的动态性质,晤戌艘匿谆曳睦玛竭迪犊漏匝引赦哉狗男警弥先镍蔚巳祟厚刚鄙惧寻恃辰第二部分Petri网的动态性质第二部分Petri网的动态性质,提纲,网系统(以原型Petri网为模型)运行过程中的一些性质统称为动态性质(dynamic properties) 或行为性质(behavioral properties) 这些性质同Petri网所模拟的实际系统运行过程中的某些方面的性质有密切的联系,烤盎喧帘吨替幸解猩检隶洁法弟娇怨酱潘盖儒卡溯呀绅凯痉讣依至虫徐扬第二部分Petri网的动态性质第二部分Petri网的动态性质,提纲,可达性 有界性和安全性 活性 公平性 持续性,适镭尊闷凶
2、烂俱恤禄钩诌菠敬抿俭载柜智婴倚生儡酉追某挥妻摇磕龟累锄第二部分Petri网的动态性质第二部分Petri网的动态性质,可达性,可达性是Petri网的最基本的动态性质，其余各种性质都要通过可达性来定义 定义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,隧敌
3、腿着厘泞谷雕狗浆敲弊做耙烯储油吱就莫蛤达答吸古虐机揪显拈捞壤第二部分Petri网的动态性质第二部分Petri网的动态性质,可达性,设初始标识M0表示系统的初始状态，R(M0)给出系统运行过程中可能出现的全部状态的集合。 定义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),梢甸搂描谭凿钩卯筏磺砒枉摧活昼绥闺缸烃陌噪楼避匙裁泼兜镶系暑芜宵第二部分Petri网的动态性质第二部分Petri网的动态性质,可达性,定理2.1
4、. 设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)。,虐滤遵链怒溺冕油沏呜独疲靶贤结糠姿捏钝前彰绚胎釜奖害源洗鞘料贷绎第二部分Petri网的动态性质第二部分Petri网的动态性质,可达性,定义2.3. 设PN=(P,T;F, M0)为一个Petri网，M R(M0)。如果M R(M
5、0)，都有M R(M )，则称M为PN的一个可返回标识或一个家态（home state）。 定义2.4. 设PN=(P,T;F, M0)为一个Petri网。如果M0是一个家态，则称PN为可逆网系统（reversible net system），或称可回复系统。,网系统家态的存在是一个良好性质，在评测系统性能或在系统模拟过程中具有非常关键的作用。,凸巍服鉴醋熟糜见秽蛋量疥思讳藩丙宁凰坏粤铱湛掐苔滴甘砚狼整剪藤危第二部分Petri网的动态性质第二部分Petri网的动态性质,可达性,推论2.1. 设PN=(P,T;F, M0)为一个Petri网， M1 , M2是PN的家态，则 R(M1)= R(M
6、2) 。 证明：因为M1 , M2是PN的家态， 所以首先有M1 R(M0)，M2 R(M0)， 进而M1 R(M2)， M2 R(M1)。 根据定理2.1(2)，则有R(M1)= R(M2)。,赔夹跪师坞华俊光欠轻淤奠求目裕晒器像舜泄携摔谰兵哇纪哀跌葡月搅跺第二部分Petri网的动态性质第二部分Petri网的动态性质,有界性和安全性,定义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)
7、: M(p)B 当B(p)=1时，称库所p为安全的（safe）。 定义2.5. 设PN=(P,T;F, M0)为一个Petri网。如果每个pP都是有界的，则称PN为有界Petri网。称 B(PN)=maxB(p)| p P 为PN的界。当B(PN)=1时，称PN为安全的。,钉磐改芭览义冤篮邑腔贪盒悟怀凰酝柞用险塘洒策非巴侈蔫误褒危死稠雏第二部分Petri网的动态性质第二部分Petri网的动态性质,有界性和安全性,Petri网的有界性（boundedness）反映 被模拟系统运行过程中对有关资源的容量要求,库所p3无界 其它库所的界为1,B(p1) =B(p2) =B(p3)=2 其它库所界为1
8、,琅忘袱媒曳熟簇济翌齿织同挣氰夷红些轨剩害洞有复冶汤煤趟昂售苯铃廖第二部分Petri网的动态性质第二部分Petri网的动态性质,有界性和安全性,定理2.2. 设PN=(P,T;F, M0)为一个Petri网。R(M0)为有限集当且仅当PN是有界的。 证：,最祝较孙皮络旱枣比毖轧趁昌单做墒吻爬葛训奢提赘笆碳虎锁驱羡置据沿第二部分Petri网的动态性质第二部分Petri网的动态性质,活性,Petri网活性（Liveness）概念的提出源于对实际系统运行中是否会出现死锁的探索的需要。 定义2.6. 设PN=(P,T;F, M0)为一个Petri网， M0为初始标识，tT。如果对任意M R(M0)，都
9、存在M R(M)，使得Mt，则称变迁t为活的。 如果每个tT 都是活的，则称PN为活的Petri网。,2,t1和t2是活的， t3是不活的,不活的,活的,坤醉俗牟琼庸黄宽走解粟晤杏瀑犹隐蝎机寒同烯硫本棠巩哭辑噪话悲宾滑第二部分Petri网的动态性质第二部分Petri网的动态性质,活性,与实际系统中的无死锁概念更为接近的定义。 定义2.7. 设PN=(P,T;F, M0)为一个Petri网， 如果对M R(M0)， 使得 tT：Mt，则称M为PN的一个死标识（dead marking）。如果PN中不存在死标识，则称PN为弱活的（weak live）或者不死的（non-dead）。 定理2.3.设
10、PN=(P,T;F, M0)为一个Petri网。若PN中有一个变迁是活的，则PN是弱活的。 证：用反证法。假设PN不是弱活的，则必存在一个死标识M R(M0)， 即 tT：Mt。从而不存在M R(M)，使得Mt。即任一个变迁都不是活的，这同假设矛盾。,蒸掳瓷棚侄载敷闲驯剧驳肃肝湿簇丑霞园矣红钦台妇绕恳捡庞插烽州问吐第二部分Petri网的动态性质第二部分Petri网的动态性质,活性,PN是弱活的，但不是活的,单萧众杉灾堆嫩卖庸套憾焦共专勤碑辛毡匿灵樱正坑钢姬涡童出逃砷稍探第二部分Petri网的动态性质第二部分Petri网的动态性质,活性,定义2.8.设PN=(P,T;F, M0)为一个Petri
11、网， tT。若 M R(M0)： Mt，则称变迁t为死的。,如果一个Petri网中没有死变迁，那么它是活的吗？是弱活的吗？,？,t3是死变迁,泞吮思景轩朔涣毅智涡乙类氦慢侧道驾撩靴樱藤穗吗让束隙洗痢牵暂雅朝第二部分Petri网的动态性质第二部分Petri网的动态性质,公平性,在Petri网中引入公平性（fairness）概念，旨在讨论网系统中两个变迁的发生之间的相互关系。这种关系反映被模拟系统的各个部分在资源竞争中的无饥饿性问题。 定义2.9. 设PN=(P,T;F, M0)为一个Petri网， M0为初始标识，t1,t2T。如果存在正整数k，使得 M R(M0) ， T*：M都有 #(, t
12、i) =0#(, t3-i)k, i=1,2 则称变迁t1和t2处于公平关系。 如果PN中任意两个变迁都处于公平关系，则称PN为公平Petri网。其中 #(, ti)表示在序列中ti的出现次数。 如果PN中不存在可发生的无限变迁序列，则网系统总是公平的。,辛蛰孕峪逆懈衍溉扩籍遇篇干享蹈房挠撰渣炉豺踏啦尔邢规铲货巷镣挺瞎第二部分Petri网的动态性质第二部分Petri网的动态性质,公平性,定义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
13、 则称变迁t1和t2处于弱公平关系。 如果PN中任意两个变迁都处于弱公平关系，则称PN为弱公平Petri网。,t2和 t3是公平关系，也是弱公平关系,t2和 t3是弱公平关系，但不是公平关系,盼徒瑟氖砂场芬刷喉拜八褐憨姬毗窿菜螟买间祖歹液毯瞪各帛供拱闭问攒第二部分Petri网的动态性质第二部分Petri网的动态性质,公平性,定理2.4. Petri网中变迁之间的公平关系是一种等价关系 证：公平关系的自反性和对称性是显然的。下面证明其传递性。 设t1和t2处于公平关系，即存在k1，使得 M R(M0) ， T*：M都有 #(, t1) =0#(, t2) k1 #(, t2) =0#(, t1)
14、 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处于公平关系。,桐斟辫婆没史搅烃睛摘涎征钙袒
15、验赵游烽烬古翼灵谩误楼蜂撵训担能埠其第二部分Petri网的动态性质第二部分Petri网的动态性质,持续性,定义2.11.设PN=(P,T;F, M0)为一个Petri网。如果对任意 M R(M0) 和任意t1,t2T (t1 t2)，有 ( Mt1 Mt2M) Mt1 则称PN为持续网系统。 定理2.5.设PN=(P,T;F, M0)为一个持续网系统。对于任意 M R(M0)，如果 Mt1 且M， #(, t1) =0，则有Mt1 且Mt1。 证明：对的长度进行数学归纳。,浆攫辐逝杏裹嘲来娠嘘嵌报甥山纶劫恒聊术艘侩渣企谍染状玛惮澈傅悸沾第二部分Petri网的动态性质第二部分Petri网的动态性
16、质,持续性,定理2.6. 设N=(P,T;F)为一个纯网，那么PN =(N, M0)是持续网系统的充要条件 M R(M0) ， t1,t2T (t1 t2)， t1和t2 在M不存在冲突。,奋堂庭歧导筷鸡蔫演坍涩低平荒宋梗意哮惰拐味嘲柯希问哭砷千梅仙伪草第二部分Petri网的动态性质第二部分Petri网的动态性质,持续性,定理2.7. 若N=(P,T;F)为一个T-图，则对N的任意初始标识M0，PN =(N, M0)都是持续网系统。 证明：已知 M R(M0) 和任意t1,t2T (t1 t2)，有( Mt1 Mt2M)。 并且 t1t2 = , t1t2 = 证明Mt1 。,裁攒蛔圈蜡科饼车
17、暮雀匙咯淬流猪凶妒尝涟捅芽瓜勘毙蹲晕祈莆组闹滇迟第二部分Petri网的动态性质第二部分Petri网的动态性质,公平性实例,变迁序列： (t1t2t3t4)* k=1 弱公平 非公平，因为若选定某个k, 则只要让p1中存储k+1个token, 就无法满足条件,届关缨瘟纳篱紧贴戍闻涌奥于臂杀悲馆蹲账醛兄汁狸丢醋源浙蹋向撕碑肆第二部分Petri网的动态性质第二部分Petri网的动态性质,定理2.5,(1) |sigma|=1, Mt1 且 Mt2, 则根据持续网的定义，Mt1t2且Mt2t1 (2) 假设|sigma|且Mt2, 所以Mt2Msigma t3且Mt2Mt1 ，根据归纳假设，M sigma t3t1, 所以Mt1t2sigma t3 同时，Mt2sigma Mt3, 而根据归纳假设，Mt2sigma t1，所以Mt1,栏裴同壮歼强爵肢馒魔侯敢宅熄瘟策役童固君氢雍蹬述载歇绍持雹挖仅慢第二部分Petri网的动态性质第二部分Petri网的动态性质,