计算机系统能评价9.doc

第9讲 Petri网基础（第七章）一 Petri 网概述1Petri 网研究与发展简况l Petri 网的概念最早在1962年Carl Adam Petri 的博士论文中提出来。l Petri网是信息处理系统描述和模型的数学工具之一。l 主要特性包括: 并行、不确定性、异步和分布描述能力和分析能力。l 它可应用到很多系统和领域，比如：性能评价、通讯协议、并发和并行计算等。l 做为图形工具除具有可视描述功能，可通过标记( token)的流动模拟系统的动态和活动行为,它是一种动态图形工具。l 做为数学工具, Petri网可以建立状态方程、代数方程和其它数学方法来描述系统的行为。l Petri 网既可为理论工作者也可为工程人员所使用，便于人们进行交流和理解。l 系统工程的方法: 系统的形式描述、系统的正确性验证、系统性能的评价、系统的目标实现和测试。这些都可以在一个Petri 网系统模型的框架上完成，其它图形或数学工具都不具备如此功能。l 从1980年起每年一次Petri网理论和应用的国际研讨会, Petri 网理论和应用的研究成果大部分集中在会议论文集中。l 从1985年起, 关于Petri 网和性能模型的国际研讨会也开始召开, 这个研讨会每两年召开一次。l 2Petri网研究的系统模型行为特性l 状态的可达(reachability)l 位置的限界(boundedness)l 变迁的活性(liveness)l 初始状态的可逆达(reversibility)l 标识之间的可达(reachability)3Petri网模型的主要分析方法依赖于l 可达树(reachability tree)l 关联矩阵和状态方程(incidence matrix and state equation)l 不变量(invariants)l 分析化简规则4 Petri网的的纵向扩展l 条件/事件(C/E)网l 位置变迁(P/T)网l 高级网(HLN)(包括谓词/变迁网和着色网)5Petri网的横向扩展l 从没有参数的网, 发展到时间Petri 网和随机Petri网; l 从一般有向弧发展到禁止弧和可变弧; l 从自然数标记(token)个数到概率标记个数；l 从原子变迁发展到谓词变迁和子网变迁。6Petri网描述和分析能力l 描述能力的增强就会在某种程度上增加Petri 网分析的难度。l 既要增加模型描述和理解能力, 又要便于系统模型的分析和计算。7Petri网模型范围l 研究模型系统的组织结构和动态行为，着眼于系统中可能发生的各种状态变化和以及变化之间的因果关系。l 不易表示系统中数据值或属性的具体运算。8Petri 网应用中存在的问题l 主要困难是模型状态空间的复杂性问题, 它将随实际系统的规模增大而呈指数性增长。l 对Petri 网模型的化简技术始终是Petri 网研究的主题之一。l 采用计算机辅助工具也是Petri 网实际应用的必然步骤。二 Petri网模型介绍 直观理解什么是Petri网，它们如何应用。1一个PN的结构元素l 位置(place)：描述可能的系统局部状态(条件或状况)，例如，队列、缓冲、资源等。l 变迁(transition)：描述修改系统状态的事件，例如，信息处理、发送、资源的存取等。l 弧(arc)：使用两种方法规定局部状态和事件之间的关系：引述事件能够发生的局部状态；由事件所引发的局部状态的转换。l2活动元素标记(token)l 包含在位置中。l 如果一个位置描述一个条件，它能包含一个标记或不包含标记，当一个标记表现在这个位置中，条件为真；否则，为假。l 如果一个位置定义一个状况(状态)，在位置中的标记个数用于规定这个状况。l 用于表示处理的信息单元、资源单元和顾客、用户等对象实体。3变迁实施规则(firing rule)l 如果一个变迁的所有输入位置(这些位置连接到这个变迁，弧的方向从位置到变迁)至少包含一个标记，那么这个变迁可能实施(相联系的事件可能发生)。l 一个可实施变迁的实施导致从它所有输入位置中都清除一个标记，在它的每一个输出位置(这些位置连接到这个变迁，弧的方向从变迁到位置)中产生一个标记。l 当使用大于1的弧权(weight)时，在变迁每一个输入位置中都要包含至少等于连接弧权的标记个数，它才可实施；这个变迁的实施，要根据相连接的弧权，在它每一个输出位置中产生相应标记个数。l 变迁的实施是一个原子操作，在输入位置中清除标记和在输出位置中产生标记是一个不可分割的完整操作。 PN模型的状态转换是局部的，它仅涉及一个变迁通过输入和输出弧连接位置的状态变化。这是PN模型的一个关键特性，利用这个特性可以容易描述并行、分布系统。三几个典型Petri描述的例子 1. 共享资源模型图7.2.2(b)的PN模型描述了资源的行为，使用两个位置(pidele和pbusy)描述了它的两个状态，使用两个变迁(tstart和tend)描述了对两个状态的修改。在这个模型中有一个标记，表示为资源实体，初始时它被包含在位置pidele中。 用户可以有3种状态：(active)活动(做不涉及共享资源的事情)、(requesting)要求、(accessing)存取。用户的行为周期性地通过这3个状态。 图7.2.2(a)的PN模型描述了用户的行为，使用3个位置(pactive、prequesting 和paccessing)描述了它的3个状态，使用3个变迁(trequest 、tstart和tend)描述了对3个状态的修改。在这个模型中有一个标记，表示为用户实体，初始时它被包含在位置pactive中。 通过变迁tstart和tend的合并，可以得到一个用户和一个资源合并的模型，见图7.2.3的PN模型。 图7.2.3的PN模型可以扩充为两个用户竞争存取相同资源的PN模型，资源就变成了共享资源。在这种情况，共享资源涉及的变迁tstart和tend就要扩展，在第一个用户模型中为tstart-1和tend-1，在第二个用户模型中为tstart-2和tend-2，见图7.2.4 的PN模型。 在图7.2.4 的PN模型中，位置pbusy是冗余的(图7.2.3 的PN模型也是一样)。当它包含一个标记时，在两个位置paccessing-1 和paccessing-2中必定有一个位置包含一个标记。在位置pbusy中的标记数量可以表达为位置paccessing-1 和paccessing-2中标记数量的和。进一步，位置pbusy中的标记数量并不表现模型的动态行为。因此，可以删除位置pbusy，简化这个PN模型，得到图7.2.5的PN模型。 当有几个有类似行为特征用户时，可以将多个用户放在一个图7.2.2(a)的用户模型中，亦即，增加用户实体标记。同样的方法也可应用于多个资源的模型。多个用户和多个资源合并的模型表现在图7.2.6中，N个用户标记初始由位置pactive包含，M个资源标记初始由位置pidel包含。当N2和M1时，忽略用户的个性，图7.2.6的模型与图7.2.5的模型等价，这个新模型是图7.2.5模型折叠。2. 分叉(fork)和交汇(join)模型 在图7.2.7 的PN模型中，变迁tfork表现了一个分叉操作，3个变迁texec-1、texec-2 和texec-3表示3个并行的分支。变迁tjoin表示3个并行部分结束的同步。最后，整个处理由变迁trestart从新启动。 借助分叉和交汇子模型，可组织并行系统的模型。图7.2.8描述了一个简单并行计算的PN模型。系统操作描述如下：一组新数据被读(变迁tnewdata的实施)，使用相同一组数据，两个进程并行开始(分叉操作变迁tstart实施)。当两个进程完成操作(变迁tpar1和tpar2分别实施)，同步执行(交汇操作变迁tsyn实施)。两个操作结果的一致性要检测，两个变迁tOK和tKO中的一个要实施，它们分别表示操作结果是可以接收或不可接收。如果结果不一致，在进一步检测后(变迁tcheck实施)，在同一组数据的整个计算要重新执行；否则，结果输出(变迁tI/O实施)，进行新数据的操作。 自由选择冲突模型: 图7.2.8模型包括了由变迁tOK和tKO构成的新结构。这两个变迁和它们的输入位置模拟了一个选择结构，在PN术语中叫做自由选择冲突(free-choice conflict)。冲突是说一个选择存在并且一个变迁的实施将制止另一个变迁做同样的事情.。自由选择冲突子模型结构可用于系统调度、控制策略的表示。3.KanBan 过程4令牌环局域网 上面非形式化地引入了Petri网及其概念，并且显示了它是模拟大量实际系统的有效工具。下面将给出Petri网的形式化描述。四 Petri网的形式化描述 常用记号： = 1, 2, 3, N = 0, 1, 2, 3, Z = , -2, -1, 1, 1, 2, 定义7.3.1 Petri网(或者简称网) 一个三元组N = (S, T; F) 是一个(Petri)网iff: （1）ST(网非空); （2）ST= (二元性); （3）F (ST)(TS) (流关系仅在于S与T的元素之间); （4）dom(F)cod(F) = ST(没有孤立元素)。 在网中, F的元素叫弧; dom(F) = x$y: (x, y)F; cod(F) = x$y: (y, x)F。集合X = ST是网元素的集合。 在图形上, S元素用一个园圈表示, T元素用一个四方形、长方形或者线段表示。在X元素之间的流关系由带箭头的弧表示: (x, y)F(ST) x y (x, y)F(TS) x y定义7.3.2前置集和后置集 让N = (S, T; F)是一个网, 且xX, 那么: = y(y, x)F ( xX的前置集)。 = y(x, y)F ( xX的后置集)。如果X1X, 那么, 。练习1: 找出下列Petri网的S、T和F集合,并说明S、T集合中各元素的前置集和后置集.定义7.3.3 子网 让N1 = (S1, T1; F1), N2 = (S2, T2; F2), 是两个网。 N1是N2的子网iff S1 S2, T1 T2且F1F2 (S1T1) (T1S1)。 网和系统概念之间的区别：网的概念仅包括位置、变迁和弧集合；而系统是指网和相关的初始标识。在不特殊说明的情况下，我们所说的Petri网是指Petri网系统。五 位置/变迁(P/T)系统定义7.4.1 P/T系统 一个六元组S = (S, T; F, K, W, M0)是一个P/T系统iff: (1)(S, T; F)是一个网, S元素是位置, T元素是变迁; (2)K: S是位置容量函数; (3)W: F是弧权函数； (4)M0: S是初始标识(marking), 满足: sS: M0(s) K(s)。在P/T系统的图形表示中, 对于弧fF, 当W(f)1时, 将W(f)标注在弧上。当一个位置的容量有限时, 通常将K(s)写在位置s的园圈旁。当K(s) = 时, 通常省略K(s)的标注。有界P/T系统的K函数仅为K: S, K(s)=1时, 通常忽省略K(s)的标注。标记仍由在位置中的黑点来表示。定义7.4.2 可实施与实施(enabling and firing) 让S = (S, T; F, K, W, M0)是一个P/T系统。(1) 函数M: S叫做S 的标识iff sS: M(s) K(s)(2)一个变迁tT在M下是可实施的iff 若 s t t: W(s, t) M(s);若s t-t : M(s)+ W(t, s) K(s) ;若s t t: M(s) - W(s, t) + W(t, s) K(s)且W(s, t) M(s); (3)如果tT在标识M下是可实施的, 那么t可以实施并产生一个新的后继标识M, M可由下列方程给出: sS， M(s) - W(s, t) 若s t tM(s) + W(t, s) 若s t-tM(s) = M(s) - W(s, t) + W(t, s) 若s t tM(s) 若s t t(4)系统标识M经过t的实施得到新的标识M, 我们可以表示成Mt M或者MM。练习2: 找出下列P/T系统中哪些变迁可以实施? 实施之后的标识M如何变化? t12 2 s2 s1 t2 3 3t3练习3: 考察下面P/T网模型, 它的初始标识及各可实变迁实施后的新标识 2 R C 2 2 B Y D 2 A 2. 2 G注意:本例中w(s,t)和w(t,s)有时可能不同 , 如果变迁s和位置t之间没有弧,则W(s,t)=0)定义7.4.3实施序列让S = (S, T; F, K, W, M0)是一个P/T系统, s = M0t1M1t2tn Mn是S的一个有限实施序列iff i, 1 i n: Mi-1ti Mi; s的长度|s| = n。t1t2tn叫变迁实施序列。定义7.4.4可达树(1)一般P/T系统可达树和可达图构造P/T系统可达树构造: 1. 根结点r由M0标注。2. 一个标注M的结点x是一个叶结点 iff不存在tT: t在M是可实施的或者在从r到x的路上存在一个结点yx, 但结点y也是由M标注的。 3. 如果一个标注M的结点x不是一个叶结点, 那么对于所有tT使得在M下可实施的t实施而产一个新的结点y, 且在从x到y新产生的弧上标注t。 y结点标注的标识M可由M1来计算, M1满足于Mt M1, 即 sS: M(s) - W(s, t) 若s t tM(s) + W(t, s) 若s t-tM1(s) = M(s) - W(s, t) + W(t, s) 若s t t M(s) 若s t tP/T系统可达图构造:让S = (S, T; F, K, W, M0)是一个有限的P/T系统, S的可达图是由标识(标记值可能由w表示)为结点的图, 其弧线由T元素标注。可达图由下列算法构成。 (1) 两个可达树的结点是等价的iff它们有相同的标注M。 (2) 可达图的结点是它的可达树结点的等价类。从结点Y到结点Z的弧线标注为t iff $yY 且$zZ, 使得在可达树中从y到z有弧线t。 可达图是可达树中相同结点的相重叠。练习4计算下面P/T系统的可达树和可达图 t12 2 s2 s1 t2 3 3t3练习5: 计算下面P/T系统的可达树和可达