第七章Petri网基础ppt课件.ppt

《第七章Petri网基础ppt课件.ppt》由会员分享，可在线阅读，更多相关《第七章Petri网基础ppt课件.ppt（74页珍藏版）》请在三一办公上搜索。

1、1,第七章 Petri网基础,7.1 Petri 网发展概述1Petri 网的概念最早在1962年Carl Adam Petri 的博士论文中提出来。 Petri网是信息处理系统描述和模型的数学工具之一。主要特性包括: 并行、不确定性、异步和分布描述能力和分析能力。,2,它可应用到很多系统和领域。 做为图形工具除具有可视描述功能，可通过标记( token)的流动模拟系统的动态和活动行为,它还是动态图形工具。 做为数学工具, Petri网可以建立状态方程、代数方程和其它数学方法来描述系统的行为。 Petri 网既可为理论工作者也可为工程人员所使用，便于人们进行交流和理解。,7.1 Petri 网

2、发展概述2,3,系统工程的方法: 系统的形式描述、系统的正确性验证、系统性能的评价、系统的目标实现和测试。可在一个Petri 网系统模型的框架上完成各项任务，其它图形或数学工具一般都不具备如此功能。 从1980年起每年一次Petri网理论和应用的国际研讨会, Petri 网理论和应用的研究成果大部分集中在会议论文集中。 从1985年起, 关于Petri 网和性能模型的国际研讨会也开始召开, 研讨会每两年召开一次。,7.1 Petri 网发展概述3,4,Petri网研究的系统模型行为特性包括：状态的可达(reachability) 位置的限界(boundedness) 变迁的活性(livenes

3、s) 初始状态的可逆达(reversibility) 标识之间的可达(reachability) 变迁之间的坚挺(persistence) 事件之间的同步距离(synchronic distance) 公平性(fairness),7.1 Petri 网发展概述4,5,Petri网模型的主要分析方法依赖于：可达树(reachability tree) 关联矩阵和状态方程(incidence matrix and state equation) 不变量(invariants) 分析化简规则 Petri网的的纵向扩展： 条件/事件(C/E)网 位置变迁(P/T)网 高级网(HLN)(包括谓词/变迁网

4、和着色网),7.1 Petri 网发展概述5,6,Petri网的横向扩展： 从没有参数的网, 发展到时间Petri 网和随机Petri网; 从一般有向弧发展到禁止弧和可变弧; 从自然数标记(token)个数到概率标记个数； 从原子变迁发展到谓词变迁和子网变迁。Petri网描述和分析能力： 描述能力的增强就会在某种程度上增加Petri 网分析的难度。 既要增加模型描述和理解能力, 又要便于模型的分析和计算。,7.1 Petri 网发展概述6,7,Petri网模型应用范围： 研究模型系统的组织结构和动态行为，着眼于系统中可能发生的各种状态变化和以及变化之间的因果关系。不易表示系统中数据值或属性的具

5、体运算。,7.1 Petri 网发展概述7,8,Petri 网应用中要解决的问题： 主要困难是模型状态空间的复杂性, 它将随实际系统的规模增大而呈指数性增长。 对Petri 网模型和求解的化简技术始终是Petri 网研究的主题之一。 采用计算机辅助工具也是Petri 网实际应用的必然步骤。,7.1 Petri 网发展概述8,9,利用internet进行Petri网知识的获取和问题的讨论，可使用如下E-mail地址或网页地址：Post messages and summary of replies: PetriNetsdaimi.au.dkThe moderators address: Petr

6、iNets-ownerdaimi.au.dkTo (un)subscribe: PetriNets-requestdaimi.au.dkWorld Wide Web URL: http:/www.daimi.au.dk/PetriNets/pnl/Read before posting:http:/www.daimi.au.dk/PetriNets/pnl/faq.html,7.1 Petri 网发展概述9,10,7.2 Petri网模型简介1,直观理解什么是Petri网，它们如何应用。一个PN的结构元素包括：位置(place)：描述可能的系统局部状态(条件或状况)，例如，队列、缓冲、资源等。

7、 变迁(transition)：描述修改系统状态的事件、动作，例如，信息处理、发送、资源的存取等。 弧(arc)：使用两种方法规定局部状态和事件之间的关系：引述事件能够发生的局部条件状态；由事件所引发的局部状态的转换。,11,活动元素标记(token)：包含在位置中 如果一个位置描述一个条件，它能包含一个标记或不包含标记，当一个标记表现在这个位置中，条件为真；否则，为假。 如果一个位置定义一个状况(状态)，在位置中的标记个数用于规定这个状况。用于表示处理的信息单元、资源单元和顾客、用户等对象实体。,7.2 Petri网模型简介2,12,变迁实施规则(firing rule)：如果一个变迁的所有

8、输入位置(这些位置连接到这个变迁，弧的方向从位置到变迁)至少包含一个标记，那么这个变迁可能实施(相联系的事件可能发生)。 一个可实施变迁的实施导致从它所有输入位置中都清除一个标记，在它的每一个输出位置(这些位置连接到这个变迁，弧的方向从变迁到位置)中产生一个标记。当使用大于1的弧权(weight)时，在变迁每一个输入位置中都要包含至少等于连接弧权的标记个数，它才可实施；这个变迁的实施，要根据相连接的弧权，在它每一个输出位置中产生相应标记个数。 变迁的实施是一个原子操作，在输入位置中清除标记和在输出位置中产生标记是一个不可分割的完整操作。,7.2 Petri网模型简介3,13,PN模型的状态转换

9、是局部的，它仅涉及一个变迁通过输入和输出弧连接位置的状态变化。这是PN模型的一个关键特性，利用这个特性可以容易描述并行、分布系统。,7.2 Petri网模型简介4,14,7.2.1 共享资源模型1,图7.2.1(b)的PN模型描述了资源的行为，使用两个位置(pidele和pbusy)描述了它的两个状态，使用两个变迁(tstart和tend)描述了对两个状态的修改。在这个模型中有一个标记，表示为资源实体，初始时它被包含在位置pidele中。,15,图7.2.1(a) 用户PN模型,图7.2.1(b) 资源PN模型,7.2.1 共享资源模型2,16,用户可以有3种状态：(active)活动(做不涉

10、及共享资源的事情)、(requesting)要求、(accessing)存取。用户的行为周期性地通过这3个状态。图7.2.1(a)的PN模型描述了用户的行为，使用3个位置(pactive、prequesting 和paccessing)描述了它的3个状态，使用3个变迁(trequest 、tstart和tend)描述了对3个状态的修改。在这个模型中有一个标记，表示为用户实体，初始时它被包含在位置pactive中。通过将图7.2.1中两个PN模型的共有变迁tstart和tend进行合并，可以得到一个用户和一个资源合并的PN模型，即图7.2.2的PN模型。,7.2.1 共享资源模型3,17,图7.

11、2.2 用户存取资源的PN模型,7.2.1 共享资源模型4,18,图7.2.2的PN模型可以扩充为两个用户竞争存取相同资源的PN模型，资源就变成了共享资源。在这种情况，共享资源涉及的变迁tstart和tend就要扩展，在第一个用户模型中为tstart-1和tend-1，在第二个用户模型中为tstart-2和tend-2，见图7.2.3 的PN模型。,7.2.1 共享资源模型5,19,图7.2.3 两个用户存取共享资源的PN模型,7.2.1 共享资源模型6,20,在图7.2.3 的PN模型中，位置pbusy是冗余的(图7.2.2 的PN模型也是一样)。当它包含一个标记时,在两个位置paccess

12、ing-1 和paccessing-2中必定有一个位置包含一个标记。在位置pbusy中的标记数量可以表达为位置paccessing-1 和paccessing-2中标记数量的和。进一步，位置pbusy中的标记数量并不表现模型的动态行为。因此，可以删除位置pbusy，简化这个PN模型，得到图7.2.4的PN模型。,7.2.1 共享资源模型7,21,图7.2.4 简化的两个用户存取共享资源的PN模型,7.2.1 共享资源模型8,22,当有几个有类似行为特征用户时，可以将多个用户放在一个图7.2.1(a)的用户模型中，亦即，增加用户实体标记。同样的方法也可应用于多个资源的模型。多个用户和多个资源合并

13、的模型表现在图7.2.5中，N个用户标记初始由位置pactive包含，M个资源标记初始由位置pidel包含。当N2和M1时，忽略用户的个性，图7.2.5的模型与图7.2.4的模型等价，这个新模型是图7.2.4模型折叠。,7.2.1 共享资源模型9,23,图7.2.5 N个用户和M个资源的PN模型,7.2.1 共享资源模型10,24,7.2.2 分叉(fork)和交汇(join)模型1,在图7.2.6 的PN模型中，变迁tfork表现了一个分叉操作，3个变迁texec-1、texec-2 和texec-3表示3个并行的分支。变迁tjoin表示3个并行部分结束的同步。最后，整个处理由变迁trest

14、art重新启动。由于在位置pstart中有多个标记，位置pstart表示了一个状况而不是一个布尔(boolean)条件。,25,图7.2.6 分叉和交汇操作PN模型,7.2.2 分叉(fork)和交汇(join)模型2,26,借助分叉和交汇子模型，可组织并行系统的模型。图7.2.7描述了一个简单并行计算的PN模型。系统操作描述如下：一组新数据被读(变迁tnewdata的实施)，使用相同一组数据，两个进程并行开始(分叉操作变迁tstart实施)。当两个进程完成操作(变迁tpar1和tpar2分别实施)，同步执行(交汇操作变迁tsyn实施)。两个操作结果的一致性要检测，两个变迁tOK和tKO中的一

15、个要实施，它们分别表示操作结果是可以接收或不可接收。如果结果不一致，在进一步检测后(变迁tcheck实施)，在同一组数据的整个计算要重新执行；否则，结果输出(变迁tI/O实施)，进行新数据的操作。,7.2.2 分叉(fork)和交汇(join)模型3,27,图7.2.7 一个简单并行计算的PN模型,7.2.2 分叉(fork)和交汇(join)模型4,28,应当注意，图7.2.7模型包括了由变迁tOK和tKO构成的新结构。这两个变迁和它们的输入位置模拟了一个选择结构，在PN术语中叫做自由选择冲突(free-choice conflict)。冲突是说一个选择存在并且一个变迁的实施将制止另一个变迁

16、做同样的事情(因为变迁tOK和tKO有一个公共输入位置且仅包含一个标记)。自由选择的含意包括：因为两个变迁总是同时一起可实施的，因此选择是自由的；选择哪一个变迁实施并不依赖网络的标识。自由选择冲突子模型结构可用于系统调度、控制策略的表示。,7.2.3 自由选择冲突模型,29,7.3 Petri网的基本概念1,定义7.3.1 (Petri网(或者简称网) ：一个三元组N = (S, T; F) 是一个(Petri)网iff:ST(网非空); ST= (二元性); F (ST)(TS) (流关系仅存在于S与T元素之间); dom(F)cod(F) = ST(没有孤立元素)。,30,F的元素叫弧;

17、dom(F) = xy: (x, y)F;cod(F) = xy: (y, x)F。集合X = ST是网元素的集合。在图形上, S元素用一个圆圈表示, T元素用一个四方形、长方形或者线段表示。在X元素之间的流关系由带箭头的弧表示,其方法如下:,7.3 Petri网的基本概念2,31,定义7.3.2 (前置集(pre-set)和后置集(post-set) ：让N = (S, T; F)是一个网, 且xX, 那么: = y(y,x)F称为xX的前置集。 =y(x,y)F称为xX的后置集。如果X1X, 那么 , 。 定义7.3.3 (子网)：令N1 = (S1, T1; F1), N2 = (S2,

18、 T2; F2), 是两个网。 则N1是N2的子网,iff S1 S2, T1 T2且F1F2 (S1T1) (T1S1)。 网和系统概念之间的区别：网的概念仅包括位置、变迁和弧集合；而系统是指网和相关的初始标识。在不特殊说明的情况下，Petri网就是指Petri网系统。,7.3 Petri网的基本概念3,32,7.4 位置/变迁(P/T)系统1,定义7.4.1( 位置/变迁(position/transition，P/T)系统) ：一个六元组 = (S, T; F, K, W, M0)是一个P/T系统，iff: (S, T; F)是一个网, S元素是位置, T元素是变迁; K: S 是位置容

19、量函数; W: F 是弧权函数；M0: S 是初始标识(marking), 满足: sS: M0(s) K(s)。,33,定义7.4.2 (可实施与实施(enabling and firing)：让 = (S, T; F, K, W, M0)是一个P/T系统。 函数M: S 叫做 的标识，iff sS: M0(s) K(s)。 一个变迁tT在M下是可实施的，iff sS: W(s, t) M(s) K(s) - W(t, s)。如果tT在标识M下是可实施的, 那么t可以实施并产生一个新的后继标识M, M可由下列方程给出: sS，M(s) = M(s) - W(s, t) + W(t, s)。,

20、7.4 位置/变迁(P/T)系统2,34,系统标识M经过t的实施得到新的标识M, 表示成Mt M或者M M。使用M0表示的最小标识集合，满足: M0M0 ; 如果M1M0且有tT使M1t M2, 那么M2M0。 在一般情况下, M0被称为的可达标识集。,7.4 位置/变迁(P/T)系统3,35,定义7.4.3 (实施序列)： 让 = (S, T; F, K, W, M0)是一个P/T系统, = M0t1M1t2tnMn是的一个有限实施序列，iff i, 1 i n: Mi-1ti Mi; 的长度| = n。t1t2tn叫变迁实施序列。,7.4 位置/变迁(P/T)系统4,36,定义7.4.4(

21、可达树)：首先定义一记号: 对于所有nN, n ; n + = + = - n = 。令 = (S, T; F, K, W, M0)是一个P/T系统。的可达树是由标识(标记值可能由表示)为结点构成的树, 其弧线由T元素标注。可达树由下列递归算法构成。,7.4 位置/变迁(P/T)系统5,37,算法7.4.1 P/T系统可达树构造 根结点r由M0标注。 一个标注M的结点x是一个叶结点，iff不存在tT: t在M是可实施的或者在从r到x的路上存在一个结点yx, 但结点y也是由M标注的。,7.4 位置/变迁(P/T)系统6,38,3.如果一个标注M的结点x不是一个叶结点, 那么对于所有tT使得在M下

22、可实施的t实施而产一个新的结点y, 且在从x到y新产生的弧上标注t。 y结点标注的标识M可由M1来计算, M1满足于Mt M1, 即 sS: M1(s) = M(s) - W(s, t) + W(t, s)。M的计算可区别为两种情况:在从r到y的路上, 如果存在标注 的结点z y且sS: M1(s) ，那么: 其它情况, M = M1。,7.4 位置/变迁(P/T)系统7,39,在图形表示中, 对于弧fF, 当W(f)1时, 将W(f)标注在弧上。当一个位置的容量有限时, 通常将K(s)写在位置s的圆圈旁。当K(s) = 时, 通常省略K(s)的标注。有界P/T系统的K函数仅为K: S , K

23、(s)=1时, 通常忽省略K(s)的标注。标记仍由在位置中的黑点来表示。,7.4 位置/变迁(P/T)系统8,40,例7.4.1 图7.4.1中给出了一个P/T系统和它相应的可达树。,图7.4.1 一个P/T系统和它的可达树,7.4 位置/变迁(P/T)系统9,41,一个有界P/T系统, 指的是它所有的元素集合都是有界的, 自然，它的可达树也是有界的。定义7.4.5 (可达图)： 让 = (S, T; F, K, W, M0)是一个有限的P/T系统, 的可达图是由标识(标记值可能由表示)为结点的图, 其弧线由T元素标注。可达图由下列算法构成。,7.4 位置/变迁(P/T)系统10,42,算法7

24、.4.2 可达图构成 两个可达树的结点是等价的，iff 它们有相同的标注M。 可达图的结点是它的可达树结点的等价类。从结点Y到结点Z的弧线标注为t ，iff yY 且zZ, 使得在可达树中从y到z有弧线t。,7.4 位置/变迁(P/T)系统11,43,可达图是可达树中相同结点的相重叠。例如由图7.4.1的可达树可得图7.4.2的可达图。,图7.4.2 图7.4.1中可达树的可达图,7.4 位置/变迁(P/T)系统12,44,定义7.4.6 (关联矩阵和不变量) ：令 = (S, T; F, K, W, M0)是一个有限的P/T系统, 且S = s1, s2, sn, T = t1, t2, t

25、m。矩阵C = 是的关联矩阵，iff cij = W(tj, si) - W(si, tj)。 一个n元整数列向量x叫作的一个S不变量,iff ,其中 为C的转置矩阵。 一个m元整数列向量y叫作的一个T不变量,iff C y = 0。,7.4 位置/变迁(P/T)系统13,45,S不变量x的支持x是位置的集合, 这些位置在x中相对应的元素为非零正整数。一个S不变量的支持x是最小的,iff除了它本身和空集以外, x不再包含另一个不变量的支持。定理7.4.1：一个P/T系统的每一个S不变量都可以由具有最小支持的S不变量的正系数的线性合并来表达。,7.4 位置/变迁(P/T)系统14,46,由下列算

26、法可求出P/T系统的所有最小支持的S不变量(也包含一些非最小支持的S不变量)。算法7.4.3 最小支持S不变量的计算1. A: = C; D: = In; (In为nn单位矩阵) 2. Repeat For i = 1，Until i = m do 1) 对矩阵DA中的任意两行r1, r2进行非负的线性合并, 以致达到合并行在A中第i列的元素为零, 且将合并行加入DA矩阵中。,7.4 位置/变迁(P/T)系统15,47,2) 删除DA中第n+i列为非零元素的所有行。3. A中的为零行所对应D中的行向量即为的S不变量(需要转置)。 以上定理7.4.1和算法7.4.3对T不变量的计算也是适用的,

27、因为只要将关联矩阵C转置, 就同样可以计算T不变量。,7.4 位置/变迁(P/T)系统16,48,例7.4.2 给出一个P/T系统和关联矩阵C, 见图7.4.3。,图7.4.3 一个P/T系统和它的关联矩阵,7.4 位置/变迁(P/T)系统17,49,根据算法7.4.3可求出的T-不变量, 过程简要如下: 两个具有最小支持T-不变量的支持集分别为:x1= t1, t3 和 x2=t2, t3。,7.4 位置/变迁(P/T)系统18,50,根据算法7.4.3可求的S-不变量, 过程简要如下: 一个最小支持的S-不变量, 其支持集：y1|=p1, p2。,7.4 位置/变迁(P/T)系统19,51

28、,定理7.4.2：一个n 维向量Y是的一个S-不变量，iff , 其中M0是的初始标识, MM0 。定理7.4.3：一个m维向量X 0是的一个T不变量，iff存在的一个标识MM0 ( M0是的初始标识)和一个变迁实施序列从M回到M，亦即， , 的实施计数向量 等于X。,7.4 位置/变迁(P/T)系统20,52,对于例7.4.2中所求的不变量结果, 根据定理7.4.2和定理7.4.3我们可得: MM0 , M(P1) + M(P2) = M0(P1) + M0(P2) = 2, 亦即, M(P1) + M(P2) = C(常数C的值由初始标识确定)。让M1 = 1, 1 则存在实施序列: M0

29、 t1 M1 t3 M0 或写作M0t1 t3 M0; M0 t2M1 t3 M0 或写作M0 t2 t3 M0。,7.4 位置/变迁(P/T)系统21,53,如果记变迁t在关联矩阵C中所对应列向量为 , 则定义7.4.2中关于在M下t实施获得后继标识M的计算公式(标识一般都看作一个行向量), 可以写作: 同样地, 在实施序列定义中, 我们也可以增加关于标识之间可达的概念。,(7.4.1),7.4 位置/变迁(P/T)系统22,54,定义7.4.7 (可达标识)：让 = (S, T; F, K, W, M0)是一有限的P/T系统, C是的关联矩阵且T = t1, t2, tm 。标识M是由M0

30、可达的,iff存在一个变迁实施序列, 使得M0经实施得到M, 亦即, M0M。 假定m元非负整数行向量 是的变迁实施计数向量, 亦即, 的第i元素表示变迁i从 M0到M转换过程中的实施次数，则有:,(7.4.2),7.4 位置/变迁(P/T)系统23,55,7.5 高级Petri网(HLPN)系统1,在HLPN中, 标记是可以有属性或使用颜色加以区别，增加模拟和描述能力, 使得复杂系统的模型易读、易理解。,56,定义7.5.3 (HLPN系统)：一个九元组H=(S,T;F,A,V,D,X,W,M0)是一个HLPN系统，iff:(S, T; F)是一个网; A是有限、非空的标记原子颜色集合; V

31、是有限变量集合;D: VA(A)是变量到标记颜色域的映射。vV, D(v)A; 特别地, aA, D(a)=a。,7.5 高级Petri网(HLPN)系统2,57,5.X: S 和T 是网元素颜色函数。其中n是标记向量的最大向量维数, = 表示空白标记向量, 即无参数标记。X对每一位置给予了一组可能的标记颜色, 且sS, X(s)X(S)。任一变迁的颜色函数是一组变迁周围弧上变量到标记颜色的代换, 且tT, X(t)X(T) W: F , 是定义于F上的权函数, 是弧在 上多重集合的索引。M0: SX(S)Z是H的初始标识, 是S到X(S)上多重集合的索引, 即sS: M0(s) X(S)Z

32、。,7.5 高级Petri网(HLPN)系统3,58,定义7.5.4 (关联矩阵)：令H = (S, T; F, A, V, D, X, W, M0)是一个有界HLPN系统, 且S = s1, s2, sn, T = t1, t2, tm。矩阵C = 是H的关联矩阵,iff cij = Wtj, si - Wsi, tj,7.5 高级Petri网(HLPN)系统,59,定义7.5.5 (标识、可实施和实施):令H = (S, T; F, A, V, D, X, W, M0)是一个有界HLPN系统。M: SX(S)Z是H的标识函数。 在标识M下, 变迁tT是可实施的,iff X(t), sS:

33、Ws, t() M(s)。,7.5 高级Petri网(HLPN)系统,60,如果一个变迁t存在变量标记颜色代换, 即X(t), 我们将说一个动作(t, )是可实施的, 以替代说t是可实施的。另外, 对一个动作u = (t, ), 定义 且 。显然, 不同动作u1 = (t, 1)和u2 = (t, 2)有相同的前置集合和后置集合, 即 且 。同样, 动作集合的前置集合(后置集合)是每个动作前置集合(后置集合)的合并。,7.5 高级Petri网(HLPN)系统,61,7.5 高级Petri网(HLPN)系统7,.如果一个动作u = (t, )在标识M下是可实施的, 那么动作u可以实施并产生一个新

34、的后继标识M, M可由下列方程给出:sS，M(s) = M(s) - Ws, t() + Wt, s(), 且记作Mu M。记H的关联矩阵C与t所对应的列向量为 ,则上式可写为:,(7.5.1),62,定义7.5.6 (实施序列、可达和向前可达集 )：让H = (S, T; F, A, V, D, X, W, M0)是一个有界的HLPN系统, C是H的关联矩阵。 = M0(t1, 1)M1(t2, 2)(tk, k)Mk是H的一个有限实施序列,iff i, 1 i k: Mi-1(ti, i) Mi。q = (t1, 1)(t2, 2)(tk, k)是H的一个动作实施序列, 且记为: M0q

35、Mk。标识M是由M0可达的,iff存在一个动作实施序列q, 使得M0q M。假定非负整数行向量是q的动作实施计数向量, 则有:,(7.5.2),7.5 高级Petri网(HLPN)系统8,63,3.使用M0表示H的最小向前可达标识集使得: M0 M0; 如果M1 M0,且有动作u = (t, )使得M1u M2, 那么M2 M0。 可达集是所有从M0可达的标识所构成的最小集合。,7.5 高级Petri网(HLPN)系统,64,7.6 不同级别网系统之间的变换1,一个具有有界标记颜色集合的HLPH系统与一个P/T系统结构上有等价关系。这个P/T系统可由HLPN系统的展开得到: 每个位置s 展开成

36、一组P/T系统的位置(s, a)| aX(s); 每个变迁t展开成一组P/T系统的变迁(t, )| X(t)。,65,例7.6.1 使用P/T系统和HLPN系统来模拟交通灯系统。交通灯有三种颜色: 红、黄和绿, 交通灯可以在两个不同地方同时点亮。图7.6.1给出交通灯的P/T网模型和可达图。,7.6 不同级别网系统之间的变换,66,图7.6.1 交通灯P/T网模型和可达图,图7.6.2 可达图所描述的亮灯情况,7.6 不同级别网系统之间的变换,67,在图7.6.1中, 位置G、Y、R分别表示三种颜色灯点亮的情况。既然有两个灯, 就在G中设置两个标记。这个系统的动态行为如可达图所描述, 它的解释

37、见图7.6.2。 如果我们考虑的是一个交叉路口的情况, 既不是有一对交通灯, 而是要有两对交通灯。每一对交通灯的点亮情况如上所述。假定两对交通灯之间的关系仅要求不能同时为绿, 否则易发生交通事故。我们可用HLPN网来模拟这个系统如图7.6.3所示。,7.6 不同级别网系统之间的变换,68,图7.6.3 两组交通灯的HLPN网模型,7.6 不同级别网系统之间的变换,69,每个位置的标记颜色有两种: 南北(NS)和东西(EW), NS表示南北方向的交通灯, EW表示东西方向的交通灯。 除位置E以外, 每个位置可包含两种标记: NS标记和EW标记。 使用一个方向的交通灯网模型结构来表示两个方向的交通

38、灯网模型。,7.6 不同级别网系统之间的变换,70,位置E不包括有颜色的标记(由定义中的 = 中的标记表示), 它仅能包含一个标记, 它起控制作用, 它保证两个方向上的交通灯不能同时为绿。即位置G仅能同时包含两个相同颜色的标记, 或不包含标记。在弧上标注的x变量可以取弧所联接位置的颜色值, 既NS或EW。当变迁实施时, 它周围弧上的所有变量必须被代换成具体的标记, NS标记或EW标记; 同一个变量必须被代换成相同的值。,7.6 不同级别网系统之间的变换,71,在初始标识中, 两个NS标记被设置在位置R中, 两个EW标记被设置在位置G中, 位置Y和位置E中设置为空。当然两组交通灯的HLPN模型可

39、以按着上述展开的规则, 转换成两个图7.6.2所示的P/T网模型, 由一个位置E相联接。,7.6 不同级别网系统之间的变换,72,小结1,Petri网是信息处理系统描述和模型的有力数学工具之一，主要特性包括: 并行、不确定性、异步和分布描述能力和分析能力。 Petri网元素的模型含义：位置描述系统局部状态(条件或状况)，变迁描述系统状态的事件，弧规定状态和事件之间的关系，标记用于表示对象实体。 变迁实施规则和标记的流动模拟系统的动态和活动行为。,73,Petri网模型的主要分析方法依赖于：可达图、关联矩阵、状态方程和不变量。 HLPN系统是P/T系统的抽象；抽象有时会丢失一些描述个体的个性信息

40、, 但减小了网模型的规模, 增强了模拟复杂系统的能力。P/T系统是HLPN系统的精细描述；低级网的研究成果可以有条件地扩充到高级网, 扩大高级网的应用范围和分析手段。 从低级网到高级网的演变, 是标记表示能力的不断增加, 从位置含有标记的有无到标记的多少, 从标记的无区别到有区别, 使网的描述能力越来越强。,小结,74,习题,模拟资源共享的Petri网模型方法给出一个读、写进程存取共享存储的Petri网模型。假定有M个读进程，N个写进程，只要一个写进程在共享存储区，其他任何进程都不能进入共享存储区，但读进程在共享存储区，其他读进程仍进入共享存储区。在此模型的基础上，给出其可达图。计算该模型系统的S-不变量和T-不变量 ，并解释不变量的含义。试给出一个生产、消费进程同步的Petri网模型。假定有M个生产进程，N个消费进程，共享一个产品存储区，容量为S。存储区满时，生产进程不能将产品放入存储区，只有消费进程消费了产品，存储区有空闲存储区，生产进程才能将产品放入存储区继续生产。同样，存储区有产品，消费进程才能进行消费。在此模型的基础上，给出其可达图。计算该模型系统的S-不变量和T-不变量 ，并解释不变量的含义。,