第5章Petri网 本章学习目标 (1) 掌握库所/变迁Petri网的基本概念、基本性质。 (2) 掌握库所/变迁Petri 网的可达标识图、关联矩阵和状态方程等相关分析方法。 (3) 掌握库所/变迁Petri网的基本应用。 (4) 掌握谓词/变迁Petri网和着色Petri网的基本概念。 Petri网是德国著名学者C.A Petri (1926—2010)于1962年在其博士论文Kommunikation mit Automaton(《用自动机通信》)中首次提出的，它是一种以物理学为基础，用计算机科学语言提出的系统模型。Petri网作为一种集图形化与数学化于一体的建模工具，既可以通过直观的图形刻画系统的结构，又可以引入数学方法对其性质进行分析。作为最早的通用并发模型，Petri网在计算机、自动化等领域得到了广泛的研究和应用，是并发系统建模和分析的一种重要工具。 Petri网可分为库所/变迁Petri网和高级Petri网两类。高级Petri网包括谓词/变迁Petri网、着色Petri网、随机Petri网、时间Petri网及混成Petri网等。限于篇幅，本章主要讨论库所/变迁Petri网的基本定义、性质及分析方法，并对谓词/变迁Petri网及着色Petri网进行简要介绍。 5.1库所/变迁Petri网 库所/变迁Petri网又称P/T_网，它是一类以描述资源在系统中的流动为特征的网系统。物质流、数据流和信息流均为网系统中的“资源流”。资源在库所中的分布称为网的标识，网结构加上初始标识就是网系统。标识决定变迁能否发生，变迁的规则则决定标识的变化。规定标识和变迁之间依存关系的法则称为变迁规则。网结构和标识给出了网系统的静态结构，变迁规则给出了网系统的动态行为。 5.1.1基本概念 定义5.1Petri网结构是一个由库所集P，变迁集T和流关系F构成的有向网N=P,T;F，其中： (1) P={p1,p2,…,pm}为有限库所集合。 (2) T={t1,t2,…,tn}为有限变迁集合(P∪T≠,P∩T=)。 (3) F(P×T)∪(T×P)为流关系。 (4) dom(F)∪cod(F)=P∪T(无孤立元素)。 其中, dom(F)={x∈P∪T|y∈P∪T:(x,y)∈F} cod(F)={y∈P∪T|x∈P∪T:(x,y)∈F} dom(F)代表F的定义域; cod(F)代表F的值域。 库所集和变迁集是网的基本成分，流关系是在它们的基础上构造出来的，所以在P、T和F之间使用分号(;)隔开。库所和变迁是两类不同的元素，所以P∩T=，而P∪T≠表示网中至少有一个元素。库所中存放资源，资源的流动由流关系规定，所以变迁只能与库所有直接的流关系F(P×T)∪(T×P)，不参与任何变迁的库所表现为孤立的P元素，不引起资源流动的变迁表现为孤立的T元素，dom(F)∪cod(F)=P∪T规定网中不能有孤立元素。 定义5.2设N=P,T;F为一个网，x∈P∪T： (1) x={y|y∈P∪T∧(y,x)∈F}称为x的前集(preset)。 (2) x={y|y∈P∪T∧(x,y)∈F}称为x的后集(postset)。 (3) x∪x称为元素x的外延。 若是有库所p∈P和变迁t∈T满足p∈t∩t，那么在变迁t发生时库所p既会失去令牌又会得到令牌。把没有这种结构的网称为单纯网(pure net)，简称纯网。若是x,y∈P∪T，x≠y但x=y∧x=y，那么无论从网结构上还是从行为上，x和y都无法被区分，把不包含这种元素的网称为简单网。 定义5.3对于一个Petri网结构，其中X=P∪T： (1) 若x∈X:x∩x=，则N为单纯网。 (2) 若x,y∈X:x=y∧x=yx=y,则N为简单网。 (3) 通常用|D|表示集合D的元素个数，若D为无限集合，则|D|=∞。 网结构是系统的结构框架，活动在框架上的是系统中流动的资源。从网到网系统的过程必须指明资源的初始分布，规定框架的活动规则，即库所的容量与资源的数量关系。 定义5.4(Petri网系统的定义)库所/变迁Petri网系统，简称Petri网系统，可定义为一个六元组PN=(P,T;F,K,W,M0)，其中： (1) N=(P,T;F)为Petri网结构。 (2) K:P→Z+∪{∞}为库所的容量函数，规定了库所的容量。对于任意库所p∈P,K(p)表示标识向量K中库所p对应的分量，若K(p)=∞表示库所p的容量没有限制。 (3) W:F→Z+(正整数集合)称为PN上的权函数，对于f=x,y∈F，Wf为弧的权，规定了令牌传递中的加权系数。 (4) M0:P→Z(非负整数集合)是库所集合上的初始标识(marking)向量。对于任一库所p∈P，M0(p)表示标识向量M0中库所p对应的分量，称为库所p上的标识或者令牌数目，并且必须满足M0(p)≤K(p)，M0为初始标识向量。 在Petri网的图形表示中，对于f∈F，如果Wf>1时，则需要将W(f)标注在弧上，否则可以省略Wf的标注； 当一个库所的容量K(p)为无穷时，可以省略库所容量的标注，否则需要将库所的容量K(p)标注在库所旁。令牌使用黑点表示，同一个库所中的多个标记代表同一类完全等价的个体。标识向量表示了令牌在库所中的分布。 例5.1在如图51所示的Petri网系统中，W(t2,P3)=W(t3,P5)=W(P5,t4)=W(t4,P6)=3，W(t1,P4)=W(P3,t4)=2，未被标注的弧的权值都默认为1； K(P2)=5，K(P5)=4，其余未被标注的库所的容量都默认为无穷。 例5.2如图52所示的四季变迁系统Petri网系统模型，其中库所P1、P2、P3、P4分别表示当前处于春季、夏季、秋季、冬季，当库所中存在令牌则表示处于该库所对应的季节，例如初始标识为M0=(1,0,0,0)，表示当前处于春季。变迁t1、t2、t3、t4则表示季节的变迁，如变迁t1的发生表示由春天到夏天的季节变迁。 图51Petri网系统实例 图52四季变迁系统Petri网系统模型 定义5.5(变迁使能条件)变迁t∈T在标识M下的使能条件是： p∈t:M(p)≥W(p,t)∧p∈t:M(p)+W(t,p)≤K(p)，t在标识M下的使能记作M［t>，也称M授权(enables)t可发生或者t在M授权下(enabled)可发生。 定义5.6(变迁发生规则)若是M［t>，即t在M下可以发生，变迁t的发生将使库所中的令牌重新分布，从而将标识M变成后继标识(successor)M′，M′的定义是： 对p∈P,有 M′(p)=M(p)-W(p,t),p∈t-t M(p)+W(t,p),p∈t-t M(p)-W(p,t)+W(t,p),p∈t∩t M(p),其他 t和t分别代表变迁t的输入库所集和输出库所集，即一个使能变迁的发生导致从它的所有输入库所中移除令牌，在它的输出库所中产生令牌。另外，变迁的发生是一个原子操作，从输入库所中移除令牌和在输出库所中产生令牌是一个不可分割的原子操作。 应当注意到，Petri网模型的状态转换是局部的，它仅涉及一个变迁通过输入和输出弧所连接的库所的状态变化，换言之，Petri网系统的全局状态不是变迁的控制因素，这是Petri网的一个关键特性，利用这个特性可以容易地描述并发系统。 图53Petri网系统实例 例5.3如图53所示的Petri网系统实例，在初始阶段只有库所P2拥有唯一的令牌，变迁t2和t4在初始标识M0下使能，即M0［t2>或M0［t4>。在这种情况下，令牌的变化就存在两种可能的情况： t2发生或t4发生。也就是说，在给定Petri网的初始标识向量后，其演化过程具有不确定性。在图53的标识M0下，变迁t2发生得到的下一个状态如图54(a)所示，变迁t4发生得到的下一个状态如图54(b)所示。在图54(a)的状态下，变迁t1具有发生权，t1的发生将使系统返回初始状态； 在图54(b)的状态下，变迁t3具有发生权，t3的发生也将使系统返回初始状态。 图54Petri网系统行为演化实例 需要注意的是，一个没有任何输入库所的变迁被称为源变迁，一个源变迁是无条件具有发生权的，并且一个源变迁的发生只会产生令牌而不会消耗令牌； 一个没有任何输出库所的变迁被称为阱变迁，一个阱变迁的发生只会消耗令牌而不会产生任何令牌。 Petri网是一种直观的图形化建模工具，具有丰富的结构描述能力，下面介绍4种Petri网系统的基本结构。 (1) 顺序结构。 设M为Petri网PN的一个标识，若存在t1和t2使M［t1>M′，且瘙綈M［t2>，M′［t2>，则称t1和t2在M下有顺序关系，如图55所示。 (2) 并发结构。 设M为Petri网PN的一个标识，若存在t1和t2使M［t1>和M［t2>，并满足M［t1>M1M1［t2>，且M［t2>M2M2［t1>，则称t1和t2在M下并发，如图56所示。 图55Petri网系统的顺序结构 图56Petri网系统的并发结构 (3) 冲突结构。 设M为Petri网PN的一个标识，若存在t1和t2，使M［t1>和M［t2>，并满足M［t1>M1瘙綈M1［t2>，且M［t2>M2瘙綈M2［t1>，则称t1和t2在M下冲突，如图57所示。 图57Petri网系统的冲突结构 (4) 混惑结构。 当同时存在着并发和冲突，而且并发变迁的发生会引起冲突的消失或出现，在如图58所示的Petri网中，变迁t1和t3是两个并发变迁，若是t3先于t1发生，则t2获得发生权，而且t1和t2处于竞争资源的冲突状态。若t2先发生，则t1就失去了曾经拥有的发生权。如果在t1和t2的冲突中让t1发生，则P5获得令牌，系统达到最终状态M′=0,0,1,0,1,0，从初始状态M0=1,1,0,1,0,0到达最终状态M′=0,0,1,0,1,0的另一种可能是t1先发生，然后t3发生，或者t1和t3并发也到达最终状态，后两种情况都不会出现冲突。也就是说，从初始状态M0=1,1,0,1,0,0到达最终状态M′=0,0,1,0,1,0，无法判断期间是否出现过冲突，像这样并发和冲突混合在一起产生的困惑，使人无法从最终态判断是否有冲突发生，这种现象称为“混惑”，如图58所示。 图58Petri网系统的混惑结构 5.1.2基本性质 Petri网的基本性质可以分为两类： 与初始标识相关的和与初始标识无关的。前者被称为标识有关性或者行为性质，后者被称为标识无关性或者结构性质。 行为性质主要包括： (1) 可达性。 设PN=(P,T;F,M0)为一个Petri网系统。如果存在t∈T，使M［t>M′，则称M′为从M直接可达的。如果存在变迁序列t1,t2,…,tk和标识序列M1,M2,…,Mk，使 M［t1>M1［t2>M2…Mk-1［tk>Mk 则称Mk为从M可达的，一切从M可达的标识的集合记为R(M)。可达性是Petri网最基本的动态性质，许多性质都要通过可达性来定义。 (2) 可逆性。 设PN=(P,T;F,M0)为一个Petri网系统，M∈R(M0)。如果M′∈R(M)，都有M∈R(M′)，则称M为PN的一个可返回标识或一个家态。可逆性反映了系统的可回复性。 (3) 可覆盖性。 设PN=(P,T;F,M0)为一个Petri网系统，M为网的一个标识。若M′∈R(M0)，对p∈P, 有M（p)≤M′(p)，则称M为PN的一个可覆盖标识。 (4) 有界性与安全性。 设PN=(P,T;F,M0)为一个Petri网系统，p∈P。若存在正整数B，使M∈R(M0):M(p)≤B，则称库所p为有界的，并称满足此条件的最小正整数B为库所p的界，记为B(p)，即B(p)=min{B|M∈R(M0):M(p)≤B}。 当B(p)=1时，称库所p为安全的。若p∈P都是有界的，则称PN为有界Petri网系统。称B(PN)=max{B(p)|p∈P}为PN的界。当B(PN)=1时，称PN为安全的。 有界性反映被模拟系统运行过程中对有关资源的容量要求。 (5) 活性。 设PN=(P,T;F,M0)为一个Petri网系统，M0为初始标识，t∈T。如果任意M∈R(M0)，都存在M′∈R(M)，使M′［t>，则称变迁t为活的。如果t∈T都是活的，则称PN为活的Petri网系统。活性概念的提出是为了检测系统运行中是否会出现死锁状态。 (6) 公平性。 设PN=(P,T;F,M0)为一个Petri网系统，t1,t2∈T。如果存在正整数k，使得M∈R(M0)和σ∈T*:M［σ>都有 #(ti/σ)=0→#(tj/σ)≤k，i,j∈{1,2}且i≠j 则称t1和t2处于公平关系。其中，#(ti/σ)表示在序列σ中ti出现的次数。如果PN中任意两个变迁都处于公平关系，则称PN为公平Petri网系统。公平性主要针对某些存在无限运行序列的网系统。 (7) 持续性。 设PN=(P,T;F,M0)为一个Petri网系统。如果对任意M∈R(M0)和任意t1,t2∈T(t1≠t2)有 (M［t1>∧M［t2>M′)→M′［t1> 则称PN为一个持续网系统。 Petri网的结构性质由网的结构(基网)确定，而与网的初始标识无关。结构性质主要包括： (1) 结构有界性。 设N=(P,T;F)为一个网，如果对N赋予任意初始标识M0。网系统(N,M0)都是有界的，则称N为结构有界网。 (2) 结构守恒性。 设N=(P,T;F)为一个网。如果存在一个m(m=|P|)维正整数权向量Y=［y(1),y(2),…,y(m)］T，使对N的任一初始标识M0和任意M∈R(M0)都有 ∑mj=1M(pj)Y(j)=∑mj=1M0(pj)Y(j) 则称N为守恒的。特别地，当Y=［1,1,…,1］T时，有 ∑mj=1M(pj)=∑mj=1M0(pj) 这时称N为严格守恒的。若N为守恒网，则必为有界网。 (3) 结构活性。 设N=(P,T;F)为一个网，若存在活的初始标识M0，则称N为结构活的。 (4) 结构可重复性。 设N=(P,T;F)为一个网。若存在N的一个初始标识M0和一个无限的变迁序列σ，使得M0［σ>，且t∈T在σ中无限多次出现，则称N为可重复的。 (5) 结构公平性。 设N=(P,T;F)为一个网。如果对任意初始标识M0，网系统(N,M0)都是一个公平Petri网系统，则称N为一个公平网。 5.1.3分析方法 对于一般的系统来说，可以通过观察其运行过程得到它的一些性质。然而观察运行的方法对于像Petri网一样的复杂系统并不适用，为了能够正确分析Petri网模型的性质及性能，需要一些更加完备的分析方法。Petri网问世至今，研究人员提出了许多基于Petri网的分析方法，主要有可达标识图、覆盖树、关联矩阵、状态方程等。 (1) 可达标识图。 设PN=(P,T;F,M0)为一个有界Petri网系统。PN的可达标识图定义为一个三元组RG(PN)=(R(M0),E,RP)，其中： E={(Mi,Mj)|Mi,Mj∈R(M0),tk∈T:Mi［tk>Mj)} RP:E→T,RP(Mi,Mj)=tkiffMi［tk>Mj 称R(M0)为RG(PN)的结点集，E为RG(PN)的弧集； 若RP(Mi,Mj)=tk，则称tk为弧(Mi,Mj)的旁标。 通过可达标识图可以分析有界Petri网的各种性质。 例5.4如图59(a)所示的Petri网系统实例，在初始阶段只有库所P2拥有唯一的令牌，变迁t2或t4在初始标识M0=(0,1,0)下具有发生权，如果变迁t2发生，则到了下一状态M1=(1,0,0)，在标识M1下变迁t1具有发生权，变迁t1的发生使系统返回初始状态M0； 若在初始标识M0下变迁t4 先于变迁t2发生，则系统到达另一状态M2=(0,0,1)，在标识M2下变迁t3具有发生权，t3的发生使系统返回初始状态M0，图59(a)的Petri网系统对应的可达标识图如图59(b)所示。 图59Petri网实例及可达标识图 (2) 覆盖树。 Petri网系统是否有界、是否有死变迁的问题等均可以归纳为标识覆盖问题，即给定一个标识M或者一组标识Mi，问是否有某个或者某些标识能够覆盖M或Mi。这里先定义覆盖(coverability)的概念。 定义5.7设M和M′为Petri网系统的两个标识： ① 若p∈P:M(p)≤M′(p)，就说M被M′覆盖，记作M≤M′。 ② 若M≤M′且M≠M′，就说M小于M′，记作M Then 把M的标记改为“端点”，返回Step 1。 Step 4： For每个满足M［t>的t∈T Do 4.1： 计算M［t>M′中的M′。 4.2： If从M0到M′的有向路上存在M″使M″+，x代表P1中的任何一个个体。为统一符号，(a,w)和(b,w)也改写为。用<>和+号连接在一起的表达式称为符号和，其中+是两个独立的个体，而是两个结合在一起的个体。新变迁A、B、C、D分别代表图515及图516(a)系统中的一类变迁。以变迁A为例，当从P1到A的弧上的标记中的变量x取个体a为值时，变迁A的发生就是图515的系统中t1的发生； 当x以b为值时A就是t2的发生。形式上，+中的x可以取P1中的任何个体值，但当x以w为值时+代表两个w个体，但P1中只有一个w，所以x以w为值时变迁A不能发生，或者说x不能以w为值。为体现x不能以w为值的事实，可以在变迁A的方框中写下公式x≠w，这样可以避免x取值的随意性。就本例来说，A的方框中写不写都可以，一般的谓词/变迁Petri网系统中允许对变迁加标记。B、C、D上没有标记表明相关的变量可以取谓词中的任何个体为值。 图516(b)中只是用了一个变量名x，但这些x并非代表同一个变量。事实上，只有同一个变迁的所有输入输出弧上的变量名相同才是同一个变量，必须取同一个个体为值。在图516(b)中，若把变迁B的输入输出弧上的x改为y，把变迁D输入输出弧上的x改为z，得到的仍是同一个高级网系统。围绕变迁的弧就是这些弧上的变量的作用范围。 5.3着色Petri网 着色Petri网(colored Petri net,CPN)是K. Jensen于1981年在经典Petri网基础上提出的一种图形化的高级Petri网。CPN通过将相似状态或动作进行折叠，提供了一种以紧凑、简明的方式表示一个具有若干相似状态或动作的大系统，从而解决系统模型规模不可控制的问题。 5.3.1基本概念 定义着色网系统需要多重集的概念，因为同类个体可能不止一个，由它们组成的已不是集合，而是多重集。 定义5.9一个多重集合S′为一个定义于非空集合S上的函数，S′:S→N，N为非负整数。 实际上，多重集合是相同元素可重复出现的集合，本文只考虑有限的多重集合。给定一多重集合S′，设s∈S′，s元素的重复度记为|s|。 例如，设S={a,b,c}，那么S′={a,a,a,c}是S上的一多重集合，则|a|=3，|b|=0，|c|=1。上述S′也可以简写为S′={3a,c}。 定义5.10着色Petri网系统是一个七元组CPN=(P,T;F,C,I-,I+,M0)，其中： (1) P为库所集合。 (2) T为变迁集合 (P∪T≠,P∩T=)。 (3) F(P×Τ)∪(Τ×Ρ)为流关系。 (4) C为颜色集。对于p∈P，C(p)为库所p上所有可能的令牌颜色之集合。对于t∈T，C(t)为变迁t上所有可能出现的颜色集合。 (5) I-:P×T→N为负函数，表示变迁t发生时将从p(p∈t)中移走的着色令牌数。 (6) I+:P×T→N为正函数，表示变迁t发生时将向p(p∈t)中移入的着色令牌数。 (7) M0:P→N为初始标识，M0(P)是库所p的令牌颜色集合上的多重集。 (8) 在标识M下，如果p∈t中着色令牌的颜色均属于C(t)，则变迁t使能； 使能变迁t发生后产生新的后继标识M′(p)=M(p)-I-(p,t)+I+(p,t)。 5.3.2应用举例 由5.2节可知，与库所/变迁Petri网不同，谓词/变迁Petri网系统中的每个个体都有区别于其他个体的名字，以备变量替换时使用，例如图516(b)的系统中，机床a和机床b使用不同的名字区分。但是机床a和机床b起着同样的作用，并没有区别于彼此的个性，因此没有必要以名字对它们加以区分，只要能表明它们属于同一类即可。同类的个体染上同一种颜色，不同类的个体则使用不同的颜色区分，这就是着色网系统。这里的“染色”只是一种形象的说法，不必和生活中的染色混同。 图516(b)的谓词/变迁Petri网中有3个个体： 机床a、机床b及工人w，其中a和b属于同类，可以给a和b染上同一种颜色m，工人w的颜色仍然使用w表示。因此，库所P1的令牌颜色为C(P1)={m,w}，库所P2的令牌为或，表示工人正在操作机床进行加工，因此C(P2)={} (可以认为是一种复合色)。库所P3只有一种颜色，C(P3)=m。库所P4表示休息状态，C(P4)={m,w}。变迁A的发生需要两类资源，其发生色为C(A)={}，它与B上的出现色相同： C(B)={<(m,w)>}。类似地，C(C)={m}，C(D)={m,w}。 变迁上的出现色与谓词/变迁Petri网系统的可行替换类似，表明该变迁不同的发生方式。A只有一种发生方式，即(m,w)，D有两种方式： m或w。I-和I+则是在确定了变迁的发生方式后计算资源个数的。例如，对于复合色，需要计算消耗及产生m色的资源和w色的资源个数。通常使用pr1、pr2表示投影映射，即pr1()=m为复合色中的第一色，pr2()=w为复合色的第二色。若是有更多单色的复合色，则可以使用pr3、pr4等获取单色名。变迁A的发生需要从库所P1中取一个m色和一个w色资源，所以I-(P1,A)=1×pr1+1×pr2=pr1+pr2，A向P2输出的令牌色和A的出现色一致，所以I+(P2,A)=1×pr1+1×pr2=pr1+pr2。 图517生产流水线系统所对应的 着色Petri网系统 类似地，可以计算出变迁B、C、D对应的I-和I+。图517为生产流水线系统所对应的着色Petri网系统。 从图517可以看出，与其他网系统一样，着色网系统也可以使用图形表示。图形的基网和有向网一样。有向弧(pi,tj)和(tj,pi)上的权函数(或称权)I-(pi,tj)、I+(pi,tj)可以直接写在弧上。令牌色和出现色可以写在库所和变迁的旁边(如同容量函数)。初始标识及可达标识则有不同的表示方式。可以把每个库所的多重集合写在代表库所的圆圈中，如图517中库所P1中的2m+w。也可以使用不同颜色的令牌代表不同类的资源，例如可以使用黑色令牌代表m(机床)，使用红色令牌代表w(工人)，那么可以在库所P1中画上两个黑点和一个红点表示库所P1的初始标识M0(P1)。使用彩色点表示标识直观醒目，也有助于理解，但是与形式化定义相去较远，不利于动态行为的自动分析。 着色Petri网中还可以引入层次概念，对系统的建模过程可以采用自顶向下或者自底向上的方式进行，适合大型复杂系统的建模与分析。 5.4本 章 小 结 作为一种并发系统建模与分析的重要工具，与迁移系统、自动机不同的是Petri网描述的并发是“真并发”。如果两个变迁的前集和后集两两不相交，则这两个变迁对应的事件间无因果关系，当它们都处于使能状态时，它们发生的先后在时间上无法区分，在Petri网中系统不存在统一的时钟，除因果关系外没有其他信息可以用来判断两个事件的依赖关系，Petri网强调的是系统所发生的事件之间的因果关系，用因果关系建立事件之间的相互依赖关系。 Petri网对真并发的有效刻画方式及图形化的表现形式，使其能以直观方式表达系统中的并发、顺序、冲突、同步、共享等关系，可以有效构造系统模型，描述系统的物理结构； 同时，Petri网还拥有严格的理论分析工具，既可以应用线性代数分析的方法，分析网的结构性质，反映实际系统的固有特性； 也可以利用基于可达性的分析手段研究网运行的动态行为，分析被模拟系统的可达性、活性、公平性、有界性等一系列性质。 习题5 1. 简述库所/变迁Petri网的变迁中使能条件及变迁引发规则。 2. 为什么Petri网能描述系统的并发特性？ 3. Petri网主要有哪些分析方法？它们的原理各是什么？ 4. 利用覆盖树可以分析Petri网系统的哪些性质？ 5. 有了库所/变迁Petri网，为什么还要有着色Petri网？着色Petri网在系统建模过程中有什么优势？ 6. 选择一些你自己熟悉的实际应用系统，构造出相应的Petri网模型。