Petri网详细介绍与学习

11962年德国学者CarlAdamPetri在其博士论文《自动机通信》中提出的描述事件和条件关系的网络。这种系统模型后来以Petri网为名流传。现在Petri网一词既指这种模型，又指以这种模型为基础发展起来的理论。有时又把Petri网称为网论(nettheory)。Petri网是一种适合于并发、异步、分布式软件系统规格与分析的形式化方法。Petri网分为位置/迁移Petri网和高级Petri网两类。高级Petri网包括:谓词/迁移Petri网、有色Petri网、计时Petri网等。Petri网的起源2(1)通讯协议的验证通讯协议的验证是Petri网应用最为成功的领域之一最初应用在70年代初期，由于Petri网以形式语言作为基础，可形式化地对通信协议进行正确性验证。(2)计算机通讯网络性能评价及多媒体应用随着计算机网络技术和信息技术的发展，对网络进行性能分析的需要，不仅出现于企业内部的生产控制的局域总线网，而且出现于光纤局域网或ATM网中。(3)软件工程由于产品开发中的竞争和革新需要，导致产品开发者面临巨大压力。在软件工程中Petri网主要用于软件系统的建模和分析，比较成熟的是加色Petri网，可以用于大型软件系统的设计、说明、仿真、确认和实现，在软件开发生命周期的各个阶段，Petri网都可以得到很好的应用。Petri网的应用领域3(4)知识处理Petri网可用于Al中的知识表达和推理的形式化模型的建立，可以表达各个活动之间的各种关系，如顺序关系、与关系、或关系等，并可在模型基础上通过已知的初始状态和初始条件进行逻辑推理。(5)FMS的建模、分析和控制柔性制造系统(FMS)对于现代制造业具有重要作用，Petri网由于其自身优点，在制造系统中应用广泛，如带缓冲区的简单生产线、机床加工中心、自动生产线、柔性制造系统和及时加工系统。(6)系统可靠性分析系统的可靠性不仅包括硬件的可靠性、也包括软件可靠性.利用随机Petri网对系统进行可靠性分析，对软件复用、软件可靠性分析。Petri网的应用领域4Petri网结构基本定义5三元组N=（P，T；F）构成网（net）的充分必要条件：①P∩T=ф，规定了位置和变迁是两类不同的元素；②P∪T≠ф，表示网中至少有一个元素；③F=（P×T）∪(T×P)，建立了从位置到变迁、从变迁到位置的单方向联系，并且规定同类元素之间不能直接联系；Petri网结构基本定义P1P4P5P3P2t1t3t26位置集和迁移集是Petri网的基本成分，流关系是从它们构造出来的。图形表示中，用圆圈表示位置，用黑短线或者方框表示迁移，用有向弧表示流关系。Petri网结构的表示方法变迁的发生受到系统状态的控制，即变迁发生的前置条件必须满足；变迁发生后，某些前置条件不再满足，而某些后置条件则得到满足。位置表示系统的状态。变迁表示资源的消耗、使用及使系统状态产生的变化。7例子：Petri网结构的表示方法8前集和后集P1P4P5P3P2t1t3t29纯网10简单网11x∈Niscalledisolatediff•x∪x•=Ø.孤岛(isolated)P1P4P5P3P2t1t212子网结构13位置/迁移Petri网14Petri网的表示15例子：Petri网的表示16容量函数和权函数均为常量1的Petri网称为基本Petri网(简称基本网)或条件/事件网。容量函数恒为无穷和权函数恒为1的Petri网称为普通Petri网，简称为普通网。基本网和普通网都是Petri网的特殊情形。换言之，Petri网是基本网和普通网的扩展，但事实上它们之间的关系并不那么简单，在某种意义上可以是等价的，因为Petri网和基本网都可改造成普通网。基本网和普通网可以用四元组PN=(P,T,F,M)来表示。基本Petri网和普通Petri网17迁移的使能条件P1P4P5P3P2t1t3t24218迁移的引发规则19迁移的引发规则20一个没有任何输人位置的迁移叫源迁移，一个源迁移的使能是无条件的。一个源迁移的引发只会产生令牌，而不消耗任何令牌；一个没有任何输出位置的迁移叫阱迁移，一个阱迁移的引发只会消耗令牌，而不产生任何新的令牌。源迁移和阱([jǐng])迁移21Petri网具有丰富的结构描述能力，下图给出了顺序、并发、冲突、混惑结构下的Petri网模型。Petri网模型结构22各类关系23各类关系24实例1：工业生产线的Petri网模型有一工业生产线，要完成两项操作，分别为变迁t1和t2表示，变迁t1将进入生产线的半成品s1s2用两个部件s3固定在一起，后形成中间件s4。然后第2个变迁t2将s4和s5用3个部件s3固定在一起形成中间件s6。完成t1和t2都需要用到工具s7假设受空间限制s2s5最多不能超过100件，s4最多不能超过5件，s3最多不能超过1000件。S1S6S7S4t1t2S2S3S5K=100K=1000K=100K=52325实例二生产者、消费者问题的Petri网描述26produceRemovefrombufferconsumeProducerConsumerBufPutinbuffer27实例二生产者、消费者问题的Petri网描述produceRemovefrombufferconsumeProducerConsumerBufPutinbuffer28实例二生产者、消费者问题的Petri网描述produceRemovefrombufferconsumeProducerConsumerBufPutinbuffer29实例二生产者、消费者问题的Petri网描述produceRemovefrombufferconsumeProducerConsumerBufPutinbuffer实例三Petri网的变迁P1P2P3P10P4P5P8P6P7P9t5t1t2t4t8t3t7t630特殊Petri网3132Petri网的行为性质33Petri网的行为性质例子：a图有界，b图无界，P5的令牌可以无限增多。34Petri网的行为性质有界性是一个非常重要的特性,它保证系统在运行过程中不会需要无限的资源.有界性反映一个位置在系统运行过程中能够获得的最大的令牌数,即所能获得的最大资源数,它与系统的初始令牌有关.在实际系统设计中,必须使网络中的每个库所在任何状态下的令牌数小于库所的容量,这样才能保证系统的正常运行。35Petri网的行为性质36Petri网的行为性质对于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活的而不是L(k+1)活的，则称该迁移是严格Lk活的。L4⇒L3⇒L2⇒L1，L0实际上是永不引发的。37Petri网的行为性质38Petri网的行为性质1.若∀M∈[M0，存在M′∈[M使得M′[t，则称t∈T是活的；若∀t∈T，t都是活的，则称该Petri网是活的；2.若∀M∈[M0，存在t∈T使得M[t，则称P/T系统Σ在M下不死锁；否则Petri网在M死锁；3.因此，一个Petri网是活的的必要条件是：Petri网在任何可达标识M都不死锁。39Petri网的行为性质40Petri网的行为性质活的系统一定是不存在死锁的不存在死锁的系统不一定是活的41Petri网的行为性质42Petri网的行为性质43Petri网的行为性质公平性有界公平性对于两个转移，若不发生其中一个转移另一个转移可以发生的最大次数是有界的，则称两个转移为有界-公平（或β-公平）关系。若Petri网（N,M0）中每对转移都是β-公平关系，则外该网为β-公平网无条件（全局）公平性对于一个发生序列，若它为有限的或网中每个转移在中无限次出现，则称为无条件（全局）公平的。若从R（M0）中某个M开始的每个发生序列都是无条公平的，则称Petri网（N,M0）为无条件公平网44Petri网的行为性质45Petri网的结构性质结构化简结构化简是处理复杂问题的一种方法，其基本原则是在保持化简前、后Petri网所具有的某些性质不变的前提下，将多个不同的位置或迁移抽象为单个的位置或迁移。设（N,M）和（N’,M’）分别为化简前后的网，运用以下化简规则，当且仅当（N,M）是活的、安全的和有界的，则（N’,M’）是活的、安全的和有界的。串行位置的合并串行转移的合并并行位置的合并并行转移的合并自循环位置的消除自循环转移的消除46Petri网的结构化简串行位置和转移的合并47Petri网结构化简并行位置和转移的合并48Petri网结构化简自循环位置和转移的消除49Petri网结构化简化简的示例从图（a）发生t2,移去p1中标记,合并t1和t2为t12,合并t3和t4为t34,从而得出图（b）所示的Petri网。从图（b）中消去自循环转移t12和自循环位置p3,又可得以得出图（c）所示的Petri网。50Petri网结构化简所有这三个网都是有界的,非活的和安全的,并且都是不可逆的51覆盖树52覆盖树53覆盖树对于一个Petri网（N,M0），且因此R（M0）是通过使用可覆盖性树可以研究以下特性一个网（N,M0）是有界的，且因此R（M0）是有限的，当且仅当不会出现在可覆盖性树中的任一结点标注中一个网（N,M0）是安全的，当且仅当只有“0”和“1”出现在可覆盖性树的结点标注中一个转移t是死的，当且仅当t不出现在可覆盖性树的任一弧的标注中如果M从M0可达，则存在一个标注M’的结点，使得MM’54使用可覆盖性树可研究Petri网的特性（1）对于一个有界的Petri网，其可覆盖性树被称为可达性树。这是因为它包括所有可能到达的标识。在这种情况下，前面计讨论的所有行为特性的分析问题都可以通过可达性树来解决，这是一种穷举法但在通常情况下，由于使用符号会使一些信息丢失，所以可达性和活性问题不可能单单利用可覆盖性树方法来解决。我们可看下页所示的两个不同的Petri网，它们有相同的可覆盖性树。但其中一个是活的Petri网，而另一个不是活的，因为该网在发生t1、t2和t3以后再也没有可发生的转移55使用可覆盖性树可研究Petri网的特性（2）56使用可覆盖性树可研究Petri网的特性（3）两个不同的Petri网一个活的Petri网一个不活的Petri网57使用可覆盖性树可研究Petri网的特性（4）相同的可覆盖性树58使用可覆盖性树可研究Petri网的特性（5）不同的可达状态一个活的Petri网一个不活的Petri网59关联矩阵和状态方程60关联矩阵和状态方程61关联矩阵和状态方程从关联矩阵和状态方程角度，Petri网的迁移使能条件和引发规则有如下形式:62关联矩阵和状态方程63状态方程在可达性分析中的应用（1）状态方程M=M0+CT·U为部分解决可达性问题提供了一个依据。若Md从M0可达则方程CT·U=Md－M0=△M必然存在一个非负整数解Ux，该解即为发生的计数向量。若无这样的解，Md就不继从M0到达。示例164状态方程在可达性分析中的应用（2）示例1（续）在所示的Petri网中：在状态M0下转移t3是可发生的。设M1是发生t3所得的标识，则有01010M010010000111C