《Petri网详细介绍与学习ppt课件.ppt》由会员分享，可在线阅读，更多相关《Petri网详细介绍与学习ppt课件.ppt（90页珍藏版）》请在三一办公上搜索。
1、1,Petri网,2,1962年德国学者Carl Adam Petri在其博士论文自动机通信中提出的描述事件和条件关系的网络。这种系统模型后来以Petri网为名流传。现在Petri网一词既指这种模型，又指以这种模型为基础发展起来的理论。有时又把Petri网称为网论(net theory)。Petri网是一种适合于并发、异步、分布式软件系统规格与分析的形式化方法。Petri网分为位置/迁移Petri网和高级Petri网两类。高级Petri网包括:谓词/迁移Petri网、有色Petri网、计时Petri网等。,Petri网的起源,3,(1)通讯协议的验证 通讯协议的验证是Petri网应用最为成功的
2、领域之一最初应用在70年代初期，由于 Petri网以形式语言作为基础，可形式化地 对通信协议进行正确性验证。(2)计算机通讯网络性能评价及多媒体应用 随着计算机网络技术和信息技术的发展，对网络进行性能分析的需要，不仅出现于企业内部的生产控制的局域总线网，而且出现于光纤局域网或ATM网中。(3)软件工程 由于产品开发中的竞争和革新需要，导致产品开发者面临巨大压力。在软件工程中Petri网主要用于软件系统的建模和分析，比较成熟的是加色Petri网，可以用于大型软件系统的设计、说明、仿真、确认和实现，在软件开发生命周期的各个阶段，Petri网都可以得到很好的应用。,Petri网的应用领域,4,(4)
3、知识处理 Petri网可用于Al中的知识表达和推理的形式化模型的建立，可以表达各个活动之间的各种关系，如顺序关系、与关系、或关系等，并可在模型基础上通过已知的初始状态和初始条件进行逻辑推理。(5)FMS的建模、分析和控制 柔性制造系统(FMS)对于现代制造业具有重要作用，Petri网由于其自身优点，在制造系统中应用广泛，如带缓冲区的简单生产线、机床加工中心、自动生产线、柔性制造系统和及时加工系统。(6)系统可靠性分析 系统的可靠性不仅包括硬件的可靠性、也包括软件可靠性.利用随机Petri网对系统进行可靠性分析，对软件复用、软件可靠性分析。,Petri网的应用领域,5,Petri网结构基本定义,
4、6,三元组N=（P，T；F）构成网（net）的充分必要条件： PT=，规定了位置和变迁是两类不同的元素； PT，表示网中至少有一个元素； F=（PT）(TP)，建立了从位置到变迁、从变迁到位置的单方向联系，并且规定同类元素之间不能直接联系；,Petri网结构基本定义,7,位置集和迁移集是Petri网的基本成分，流关系是从它们构造出来的。图形表示中，用圆圈表示位置，用黑短线或者方框表示迁移，用有向弧表示流关系。,Petri网结构的表示方法,变迁的发生受到系统状态的控制，即变迁发生的前置条件必须满足； 变迁发生后，某些前置条件不再满足，而某些后置条件则得到满足。,位置表示系统的状态。 变迁表示资源
5、的消耗、使用及使系统状态产生的变化。,8,例子：,Petri网结构的表示方法,9,前集和后集,10,纯网,11,简单网,12,xN is called isolated iff xx =.,孤岛(isolated ),13,子网结构,14,位置/迁移Petri网,15,Petri网的表示,16,例子：,Petri网的表示,17,容量函数和权函数均为常量1的Petri网称为基本Petri网(简称基本网)或条件/事件网。容量函数恒为无穷和权函数恒为1的Petri网称为普通Petri网，简称为普通网。基本网和普通网都是Petri网的特殊情形。换言之，Petri网是基本网和普通网的扩展，但事实上它们之
6、间的关系并不那么简单，在某种意义上可以是等价的，因为Petri网和基本网都可改造成普通网。基本网和普通网可以用四元组PN=(P,T,F,M)来表示。,基本Petri网和普通Petri网,18,迁移的使能条件,19,迁移的引发规则,20,迁移的引发规则,21,一个没有任何输人位置的迁移叫源迁移，一个源迁移的使能是无条件的。一个源迁移的引发只会产生令牌，而不消耗任何令牌；一个没有任何输出位置的迁移叫阱迁移，一个阱迁移的引发只会消耗令牌，而不产生任何新的令牌。,源迁移和阱(jng)迁移,22,Petri网具有丰富的结构描述能力，下图给出了顺序、并发、冲突、混惑结构下的Petri网模型。,Petri网
7、模型结构,23,各类关系,24,各类关系,25,实例1：工业生产线的Petri网模型,有一工业生产线，要完成两项操作，分别为变迁t1和t2表示，变迁t1 将进入生产线的半成品s1s2用两个部件s3固定在一起，后形成中间件s4。然后第2个变迁t2 将s4 和s5用3个部件s3固定在一起形成中间件s6。完成t1和t2 都需要用到工具s7假设受空间限制s2 s5最多不能超过100件， s4最多不能超过5件，s3最多不能超过1000件。,26,实例二生产者、消费者问题的Petri网描述,produce,Remove from buffer,consume,Producer,Consumer,Buf,P
8、ut in buffer,27,实例二生产者、消费者问题的Petri网描述,produce,Remove from buffer,consume,Producer,Consumer,Buf,Put in buffer,28,实例二生产者、消费者问题的Petri网描述,produce,Remove from buffer,consume,Producer,Consumer,Buf,Put in buffer,29,实例二生产者、消费者问题的Petri网描述,produce,Remove from buffer,consume,Producer,Consumer,Buf,Put in buffer
9、,30,实例三 Petri网的变迁,P1,P2,P3,P10,P4,P5,P8,P6,P7,P9,t5,t1,t2,t4,t8,t3,t7,t6,31,特殊Petri网,32,Petri网的行为性质,33,Petri网的行为性质,34,例子：a图有界，b图无界，P5的令牌可以无限增多。,Petri网的行为性质,35,有界性是一个非常重要的特性,它保证系统在运行过程中不会需要无限的资源.有界性反映一个位置在系统运行过程中能够获得的最大的令牌数,即所能获得的最大资源数,它与系统的初始令牌有关. 在实际系统设计中,必须使网络中的每个库所在任何状态下的令牌数小于库所的容量,这样才能保证系统的正常运行。
10、,Petri网的行为性质,36,Petri网的行为性质,37,对于Petri网（N，M0）中的一个转移t，实际上可能属于以下情况：L0级活（死的）：仅当t在L（M0）中任何发生序列中都无法发生L1级活（可能能发生）：仅当t 在L（M0）中的一些发生序列中至少可发生一次L2级活：已知任一正整数k，仅当t 在L（M0）中的一些发生序列至少可发生k 次L3级活：仅当t 在L（M0）中的一些发生序列中可以无限制的发生L4级活（活的）：仅当t 在R（M0）中的每个标识至少是L1活的。如果一个Petri网的每一个迁移都是Lk活的，则称该Petri网为Lk活的(k=0,1,2,3,4)。如果一个潜意识Lk活
11、的而不是L(k+1)活的，则称该迁移是严格Lk活的。L4 L3 L2 L1，L0实际上是永不引发的。,Petri网的行为性质,38,Petri网的行为性质,39,若M M0，存在MM 使得Mt，则称tT是活的；若t T，t都是活的，则称该Petri网是活的；若M M0，存在tT使得Mt，则称P/T系统在M下不死锁；否则Petri网在M死锁；因此，一个Petri网是活的的必要条件是：Petri网在任何可达标识 M 都不死锁 。,Petri网的行为性质,40,Petri网的行为性质,活的系统一定是不存在死锁的,不存在死锁的系统不一定是活的,41,Petri网的行为性质,42,Petri网的行为性质
12、,43,Petri网的行为性质,44,公平性有界公平性对于两个转移，若不发生其中一个转移另一个转移可以发生的最大次数是有界的，则称两个转移为有界-公平（或-公平）关系。若Petri网（N,M0）中每对转移都是-公平关系，则外该网为-公平网无条件（全局）公平性对于一个发生序列 ，若它为有限的或网中每个转移在中无限次出现，则称 为无条件（全局）公平的。 若从R（M0）中某个M开始的每个发生序列 都是无条公平的，则称Petri网（N,M0）为无条件公平网,Petri网的行为性质,45,Petri网的结构性质,46,结构化简结构化简是处理复杂问题的一种方法，其基本原则是在保持化简前、后Petri网所具
13、有的某些性质不变的前提下，将多个不同的位置或迁移抽象为单个的位置或迁移。设（N,M）和（N,M）分别为化简前后的网，运用以下化简规则，当且仅当（N,M）是活的、安全的和有界的，则（N,M）是活的、安全的和有界的。串行位置的合并串行转移的合并并行位置的合并并行转移的合并自循环位置的消除自循环转移的消除,Petri网的结构化简,47,串行位置和转移的合并,Petri网结构化简,48,并行位置和转移的合并,Petri网结构化简,49,自循环位置和转移的消除,Petri网结构化简,50,化简的示例从图（a）发生t2,移去p1中标记,合并t1和t2为t12,合并t3和t4为t34,从而得出图（b）所示的
14、Petri网。从图（b）中消去自循环转移t12和自循环位置p3,又可得以得出图（c ）所示的Petri网。,Petri网结构化简,所有这三个网都是有界 的,非活的和安全的,并且都是不可逆的,51,覆盖树,52,覆盖树,53,覆盖树,54,对于一个Petri网（N, M0），且因此R（M0）是通过使用可覆盖性树可以研究以下特性一个网（N, M0）是有界的，且因此R（M0）是有限的，当且仅当不会出现在可覆盖性树中的任一结点标注中一个网（N, M0）是安全的，当且仅当只有“0”和“1”出现在可覆盖性树的结点标注中一个转移t 是死的，当且仅当t 不出现在可覆盖性树的任一弧的标注中如果M从M0可达，则存
15、在一个标注M的结点，使得M M,使用可覆盖性树可研究Petri网的特性（1）,55,对于一个有界的Petri网，其可覆盖性树被称为可达性树。这是因为它包括所有可能到达的标识。在这种情况下，前面计讨论的所有行为特性的分析问题都可以通过可达性树来解决，这是一种穷举法但在通常情况下，由于使用符号会使一些信息丢失，所以可达性和活性问题不可能单单利用可覆盖性树方法来解决。我们可看下页所示的两个不同的Petri网，它们有相同的可覆盖性树。但其中一个是活的Petri网，而另一个不是活的，因为该网在发生t1、t2和t3以后再也没有可发生的转移,使用可覆盖性树可研究Petri网的特性（2）,56,使用可覆盖性树
16、可研究Petri网的特性（3）,两个不同的Petri网一个活的Petri网 一个不活的Petri网,57,使用可覆盖性树可研究Petri网的特性（4）,相同的可覆盖性树,58,使用可覆盖性树可研究Petri网的特性（5）,不同的可达状态一个活的Petri网 一个不活的Petri网,59,关联矩阵和状态方程,60,关联矩阵和状态方程,61,关联矩阵和状态方程,62,从关联矩阵和状态方程角度，Petri网的迁移使能条件和引发规则有如下形式:,关联矩阵和状态方程,63,状态方程在可达性分析中的应用（1）,状态方程M = M0+CT U为部分解决可达性问题提供了一个依据。若Md 从 M0可达则方程CT
17、 U = Md M0 =M必然存在一个非负整数解Ux，该解即为发生的计数向量。若无这样的解，Md 就不继从M0到达。示例1,64,状态方程在可达性分析中的应用（2）,示例1（续）在所示的Petri网中：在状态M0下转移t3是可发生的。设M1是发生t3所得的标识，则有,65,状态方程在可达性分析中的应用（3）,示例1（续）发生序列=t3 t2 t3 t2 t1表示成发生计数向量（1,2,2），发生后产生的新标识为,66,状态方程在可达性分析中的应用（4）,示例1（续）考察标识 ，它可以从标识M0到达方程为有一个解U=（0,4,5），它对应于发生序列=t3 t2 t3 t2 t3 t2 t3 t2
18、 t3,67,状态方程在可达性分析中的应用（5）,再考察后标识 ，因方程无解，所以标识 为不可达标识,68,状态方程在可达性分析中的应用（6）,注意，状态方程有解只是可达性的必要条件，而不是充分条件。这是由于缺少M 初始标识信息导致的示例2 考察所示的Petri网,69,状态方程在可达性分析中的应用（7）,示例2（续）在所示的Petri网中方程,70,状态方程在可达性分析中的应用（8）,示例2（续）有一个解U = 。这个解对应的两个可能发生序列为t1 t2或t2 t1，然而这两个序列都不是可发生序列。因为在M0下，t1、t2都不可能发生。这里若取初始标识为则为可达的，且对应于发生计数向量 的发
19、生序列为t1t2,71,谓词/迁移Petri网有色Petri网计时Petrf网,高级Petri网,72,谓词/迁移Petri网（Predicate/Transition nets, Pr/T网）Pr/T网的转移发生条件和引起的标识变化是通过刻画标记性质的谓词来解释的示例：一个机械制造车间零件加工的简化Pr/T网系统模型问题描述有一名工人分别在机床甲和机床乙上加工零件。先加工完的机床要等待另一台机床加工完后，零件经装配才能卸下。然后，机床转入空闲，再进入就绪。以上加工过程重复进行为简化问题，这里只考虑工人和机床的关系。其他如原材料来源、成品的去处，以及辅助工具（刀、量等）等一概不考虑,谓词/迁移
20、Petri网,73,P/T网系统模型,谓词/迁移Petri网,74,先分析位置从上可知：本系统中有3 个个体：工人、机床甲作和机床乙，用w、a、b来表示这3 个个体可能处于4 种状态：就绪（ready）、工作（working）、等待（waiting）和休息（resting）工作必须是w和a或w和b的结合，为了强调结合用joint（结合）表示working如果用P-元素表示4个状态，用w、a、b三个个体名代替没有个性的标记。就可把逻辑功能相同的位置（状态）折叠在一起这样位置由10个减少为4个,谓词/迁移Petri网,75,谓词/迁移Petri网,逻辑功能相同的位置折叠在一起的图形表示,76,在位
21、置折叠的图中可见它保留了P/T网系统中的全部有向孤和所有转移。有向张上旅弧上标注了孤上流动的个体或由个体结合而成的偶如w,a或w,bP-元素（位置）已不是原P/T网系统中的位置，而是其中个体当前的状态，即谓词。谓词中的标识也不是非负整数，而是由个体组成的集合。如P1中初始标识有3个个体，表明w、a、b都处于就绪状态。P2、P3和P4在初始标识下，均无个体，为空集。由此可见，引进谓词后，减少了P （位置）的个数,谓词/迁移Petri网,77,再分析转移很明显，由上图可见：转移也可分为4类：结合（joint）（开始工作）=t1,t2、完成（finish）（工作完成）=t3,t4、装配（assemb
22、le）=t5和准备（to-ready）=t6,t7,t8由上图还可见：同类转移有相同的前集和后集，t1与t2、t3与t4，以及t6、t7和t8之间的区别在于参与转移的个体不同。如果我们用变量x来代替个体名，则可把同类转移也合并为一个。这就可以得到合并转移后的网系统,谓词/迁移Petri网,78,合并转移后得到的网系统,谓词/迁移Petri网,79,在转移折叠的图中可见把P、T 两个元素间的多条有向弧合并为一条，弧上标注也用“+”号连在一起。如P1与t1、t2之间的两条弧合并为一条后，弧上记为w+x，x表示P1中的任何一个个体。为统一符号，w,a和w,b可改写为w,x。用尖括号及“+”号连在一起
23、的表达式为符号和必须指出，w+x是两个独立的个体，w,x是两个结合在一起的个体新转移joint、finish、assemble和to-ready分别代表系统中的同一类转移当从P1到joint的弧上标注w+x中的变量x取个体a为值时，转移joint发生就是原系统中t1的发生。当x以b为值时，joint发生不是t1，而是t2。但x不能以w为值图中只使用了一个变量名x，但x并非表示同一个变量。事实上，只有同一个转移的所有I/O弧上的变量才是同一个变量，它必须取同一个个体为值。由此可见，引进变量后减少了T-元素的个数,谓词/迁移Petri网,80,谓词/迁移网是通过将位置或迁移进行分类，并引入谓词，进
24、而简化规格的扩展Petri网。若引人颜色来代表不同类的位置或迁移，则形成另一种扩展的Petri网，即有色Petri网，简称为有色网。因此，有色网与谓词/迁移网无本质区别，只是表现形式不同。,有色Petri网,81,有色网通过颜色区分标记，通过增加位置的颜色集和转移出现的颜色集，以及转移的I/O函数来刻画解释 1,定义 =（P,T;F,C,I-,I+,M0） 其中（P,T；F）分广为有向网，即的基网C为颜色集合，并有对p P,C （p）是位置p上所有可能标记颜色非空有限集合对t T,C （t）是转移t 上所有可能出现的颜色非空有限集合I-和I+分别为PT 和TP上的负函数和正函数p P, t T
25、 I-（p,t） 0 I+（t,p） 0t T, p P I-（p,t） 0 I+（t,p） 0M0为的初始标识,有色Petri网,82,这里仍使用Pr/T网系统的示例说明 （1）C（颜色集合）系统有3个个体（a,b,w）和4种状态（就绪、工作、等待和休息），这样就可以给出位置p上的所有可能的标记颜色集合C（p1）=,C（p2）=a,bC（p3）=a,b,w同样系统中的转移也有4类（结合、完成、装配和推产准备），这样也就可以给出所有可以出现的颜色集合C（joint）=,C（finish）=,C（assemble）=C（to-ready）=,有色Petri网,83,这里仍使用Pr/T网系统的示例
26、说明（续）（2） I-和I+（PT和TP上的负函数和正函数）只有上面颜色说明还不够，还应当说明转移发生时其I/O位置中标记的变化I-（joint,p1,）=1 I-（joint,p1,）=1I+（joint ,p2,）=1 I+（joint,p2,）=1 I- （finish,p2,）=1 I -（finish,p2,）=1I+（finish,p3,a）=1 I+（finish,p4,w ）=1I+（finish,p3,b）=1 I+（finish,p4,w ）=1I-（assemble,p3,）=1 I+（assemble,p4,）=1I-（to-ready,p4,）=1 I+（to-ead
27、y,p1,）=1这样，着色网系统表示的语义就非常清楚了从中还可发现a、b也为同类，与Pr/T相同，可引入变量，也可染上同一种颜色，如m。因此，位置p1中的标记颜色为C（p1）=w,m，而不是w,a,b。转移t1的发生颜色为C（joint）=w,m，即中又多了一个变量m，m可为a，也可为b。这样上述形式也应做适当修改,有色Petri网,84,（3）M0（的初始标识） M0=（,0,0,0） （4）着色网系统的图形表示与其他网系统一样，着色网系统也可用图形表示。有向弧（pi,ti）和（ti,pi）上的标注或称权I （pi,ti）和I （ti,pi）可直接写在弧上。标记色和转移出现色可写在相应的位置
28、和转移的旁边。M0（可达标识）的多重集表达式可写在位置中，也可直接用颜色表示本示例的图形表示与Pr/T示例中的图形除变量x改为变量m外，其余的完全相同,有色Petri网,85,有色Petri网,86,1,时间的种类每个转移的可发生与发生之间关联一个固定的延迟时间每个转移关联一个时间范围（段）。即每个转移发生的子延迟时间有一个极小值和极大值，转移只能在这个时间范围（段）内发生2,时间网的形式定义（1）固定时间Petri网系统 =（P,T；F,M0, t） 其中：（P,T；F,M0）为P/T网系统 t：TR,R为非负实数集合 在这种时间Petri网中，对每个t iT，都有一个r R与之对应，即表示
29、转移t 发生的延迟时间为r。也就是说，t 可发生时，其原（可发生）标识消失，经过r时间后，新（后继）标识产生,计时Petri网,87,2,时间网的形式定义（续） （2）一个时间范围Petri网系统 =（P,T；F,M0, t） 其中：（P,T；F,M0）为P/T网系统 t：TAP，AP为非负实数，对ap=（amin,amax）。 其中0 amin amax在这种时间Petri网中，对每个t T，都有一个ap AP与之对应，即转移t的发生要考虑时间，如果t在时钟u时可发生则它可在时间范围（u+ amin,u+ amax）内发生。也就是说，当t 可发生时，在输入位置p中的标记将保持至少amin,直
30、至这些标记由于t 的发生而移出,计时Petri网,88,计时Petri网,3,Petri网引入时间参数后的影响 （1）并行结构的网模型图中t1和t2完全没有偏序关系，它们模拟的是完全独立的两个并行活动。当其中一个转移的时钟值减小到零时，这个转移就发生，并产生一个新标识。在这个新标识中，另一个转移仍可发生，它的时钟值被重新设置。由此可见，在时间参数引入Petri网后，可以同样模拟转移的并行性。不同的是，它们发生的先后次序将受到其时间初始值的影响,89,计时Petri网,3,Petri网引入时间参数后的影响（续） （2）冲突结构网模型在无时间的Petri网中，t1和t2的发生是完全不确定的，哪一个转移发生都有可能，而且一个转移的发生会使另一个转移不可能再发生。在时间的Petri网中，哪个转移可发生与它们所关联的延迟时间有关。这里有3种可用策略、基于优先级的机制给转移赋予不同发生条件的谓词决定转移发生的时间,90,计时Petri网,3,Petri网引入时间参数后的影响（续） （3）系统模型中的竞争策略的选择在实际应用中，系统模型中的竞争策略的选择决定于系统任务的调度和控制策略，这是要重点考虑的。为了避免活动发生时间对调度和控制的影响，在系统模型中常采用即时转移来隔离时间转移，如图所示这种技术可以消除时间转移中的所有冲突这种技术可以消除时间转移中的所有冲突,
