第七章Petri网基础

1第七章Petri网基础§7.1Petri网发展概述1Petri网的概念最早在1962年CarlAdamPetri的博士论文中提出来。Petri网是信息处理系统描述和模型的数学工具之一。主要特性包括:并行、不确定性、异步和分布描述能力和分析能力。2它可应用到很多系统和领域。做为图形工具除具有可视描述功能，可通过标记(token)的流动模拟系统的动态和活动行为,它还是动态图形工具。做为数学工具,Petri网可以建立状态方程、代数方程和其它数学方法来描述系统的行为。Petri网既可为理论工作者也可为工程人员所使用，便于人们进行交流和理解。§7.1Petri网发展概述23系统工程的方法:系统的形式描述、系统的正确性验证、系统性能的评价、系统的目标实现和测试。可在一个Petri网系统模型的框架上完成各项任务，其它图形或数学工具一般都不具备如此功能。从1980年起每年一次Petri网理论和应用的国际研讨会,Petri网理论和应用的研究成果大部分集中在会议论文集中。从1985年起,关于Petri网和性能模型的国际研讨会也开始召开,研讨会每两年召开一次。§7.1Petri网发展概述34Petri网研究的系统模型行为特性包括：状态的可达(reachability)位置的限界(boundedness)变迁的活性(liveness)初始状态的可逆达(reversibility)标识之间的可达(reachability)变迁之间的坚挺(persistence)事件之间的同步距离(synchronicdistance)公平性(fairness)§7.1Petri网发展概述45Petri网模型的主要分析方法依赖于：可达树(reachabilitytree)关联矩阵和状态方程(incidencematrixandstateequation)不变量(invariants)分析化简规则Petri网的的纵向扩展：条件/事件(C/E)网位置变迁(P/T)网高级网(HLN)(包括谓词/变迁网和着色网)§7.1Petri网发展概述56Petri网的横向扩展：从没有参数的网,发展到时间Petri网和随机Petri网;从一般有向弧发展到禁止弧和可变弧;从自然数标记(token)个数到概率标记个数；从原子变迁发展到谓词变迁和子网变迁。Petri网描述和分析能力：描述能力的增强就会在某种程度上增加Petri网分析的难度。既要增加模型描述和理解能力,又要便于模型的分析和计算。§7.1Petri网发展概述67Petri网模型应用范围：研究模型系统的组织结构和动态行为，着眼于系统中可能发生的各种状态变化和以及变化之间的因果关系。不易表示系统中数据值或属性的具体运算。§7.1Petri网发展概述78Petri网应用中要解决的问题：主要困难是模型状态空间的复杂性,它将随实际系统的规模增大而呈指数性增长。对Petri网模型和求解的化简技术始终是Petri网研究的主题之一。采用计算机辅助工具也是Petri网实际应用的必然步骤。§7.1Petri网发展概述89利用internet进行Petri网知识的获取和问题的讨论，可使用如下E-mail地址或网页地址：[[Postmessagesandsummaryofreplies:[e-mail]]][[Themoderator'saddress:[e-mail]]][[To(un)subscribe:[e-mail]]][[WorldWideWebURL:]][[Readbeforeposting:]]§7.1Petri网发展概述910§7.2Petri网模型简介1直观理解什么是Petri网，它们如何应用。一个PN的结构元素包括：位置(place)：描述可能的系统局部状态(条件或状况)，例如，队列、缓冲、资源等。变迁(transition)：描述修改系统状态的事件、动作，例如，信息处理、发送、资源的存取等。弧(arc)：使用两种方法规定局部状态和事件之间的关系：引述事件能够发生的局部条件状态；由事件所引发的局部状态的转换。11活动元素－标记(token)：包含在位置中如果一个位置描述一个条件，它能包含一个标记或不包含标记，当一个标记表现在这个位置中，条件为真；否则，为假。如果一个位置定义一个状况(状态)，在位置中的标记个数用于规定这个状况。用于表示处理的信息单元、资源单元和顾客、用户等对象实体。§7.2Petri网模型简介212变迁实施规则(firingrule)：如果一个变迁的所有输入位置(这些位置连接到这个变迁，弧的方向从位置到变迁)至少包含一个标记，那么这个变迁可能实施(相联系的事件可能发生)。一个可实施变迁的实施导致从它所有输入位置中都清除一个标记，在它的每一个输出位置(这些位置连接到这个变迁，弧的方向从变迁到位置)中产生一个标记。当使用大于1的弧权(weight)时，在变迁每一个输入位置中都要包含至少等于连接弧权的标记个数，它才可实施；这个变迁的实施，要根据相连接的弧权，在它每一个输出位置中产生相应标记个数。变迁的实施是一个原子操作，在输入位置中清除标记和在输出位置中产生标记是一个不可分割的完整操作。§7.2Petri网模型简介313PN模型的状态转换是局部的，它仅涉及一个变迁通过输入和输出弧连接位置的状态变化。这是PN模型的一个关键特性，利用这个特性可以容易描述并行、分布系统。§7.2Petri网模型简介414§7.2.1共享资源模型1图7.2.1(b)的PN模型描述了资源的行为，使用两个位置(pidele和pbusy)描述了它的两个状态，使用两个变迁(tstart和tend)描述了对两个状态的修改。在这个模型中有一个标记，表示为资源实体，初始时它被包含在位置pidele中。15图7.2.1(a)用户PN模型activeprequesttrequestingpstarttendtgaccespsinstarttendtbusypidlep图7.2.1(b)资源PN模型§7.2.1共享资源模型216用户可以有3种状态：(active)活动(做不涉及共享资源的事情)、(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共享资源模型317图7.2.2用户存取资源的PN模型activeprequesttrequestingpidlepstarttgaccespsinbusypendt§7.2.1共享资源模型418图7.2.2的PN模型可以扩充为两个用户竞争存取相同资源的PN模型，资源就变成了共享资源。在这种情况，共享资源涉及的变迁tstart和tend就要扩展，在第一个用户模型中为tstart-1和tend-1，在第二个用户模型中为tstart-2和tend-2，见图7.2.3的PN模型。§7.2.1共享资源模型519图7.2.3两个用户存取共享资源的PN模型1activep2activep1requestt2requestt1requestingp2requestingp1startt2startt1endt2endt1singaccesp2singaccespidlepbusyp§7.2.1共享资源模型620在图7.2.3的PN模型中，位置pbusy是冗余的(图7.2.2的PN模型也是一样)。当它包含一个标记时,在两个位置paccessing-1和paccessing-2中必定有一个位置包含一个标记。在位置pbusy中的标记数量可以表达为位置paccessing-1和paccessing-2中标记数量的和。进一步，位置pbusy中的标记数量并不表现模型的动态行为。因此，可以删除位置pbusy，简化这个PN模型，得到图7.2.4的PN模型。§7.2.1共享资源模型721图7.2.4简化的两个用户存取共享资源的PN模型1activep2activep1requestt2requestt1requestingp2requestingp1startt2startt1endt2endt1singaccesp2singaccespidlep§7.2.1共享资源模型822当有几个有类似行为特征用户时，可以将多个用户放在一个图7.2.1(a)的用户模型中，亦即，增加用户实体标记。同样的方法也可应用于多个资源的模型。多个用户和多个资源合并的模型表现在图7.2.5中，N个用户标记初始由位置pactive包含，M个资源标记初始由位置pidel包含。当N＝2和M＝1时，忽略用户的个性，图7.2.5的模型与图7.2.4的模型等价，这个新模型是图7.2.4模型折叠。§7.2.1共享资源模型923图7.2.5N个用户和M个资源的PN模型activeprequesttrequestingpstarttendtgaccespsinidlepNM§7.2.1共享资源模型1024§7.2.2分叉(fork)和交汇(join)模型1在图7.2.6的PN模型中，变迁tfork表现了一个分叉操作，3个变迁texec-1、texec-2和texec-3表示3个并行的分支。变迁tjoin表示3个并行部分结束的同步。最后，整个处理由变迁trestart重新启动。由于在位置pstart中有多个标记，位置pstart表示了一个状况而不是一个布尔(boolean)条件。25图7.2.6分叉和交汇操作PN模型§7.2.2分叉(fork)和交汇(join)模型226借助分叉和交汇子模型，可组织并行系统的模型。图7.2.7描述了一个简单并行计算的PN模型。系统操作描述如下：一组新数据被读(变迁tnewdata的实施)，使用相同一组数据，两个进程并行开始(分叉操作－变迁tstart实施)。当两个进程完成操作(变迁tpar1和tpar2分别实施)，同步执行(交汇操作－变迁tsyn实施)。两个操作结果的一致性要检测，两个变迁tOK和tKO中的一个要实施，它们分别表示操作结果是可以接收或不可接收。如果结果不一致，在进一步检测后(变迁tcheck实施)，在同一组数据的整个计算要重新执行；否则，结果输出(变迁tI/O实施)，进行新数据的操作。§7.2.2分叉(fork)和交汇(join)模型327图7.2.7一个简单并行计算的PN模型newdatatstartt1part2partsyntOKtKOtOIt/checkt§7.2.2分叉(fork)和交汇(join)模型428应当注意，图7.2.7模型包括了由变迁tOK和tKO构成的新结构。这两个变迁和它们的输入位置模拟了一个选择结构，在PN术语中叫做自由选择冲突(free-choiceconflict)。冲突是说一个选择存在并且一个变迁的实施将制止另一个变迁做同样的事情(因为变迁tOK和tKO有一个公共输入位置且仅包含一个标记)。自由选择的含意包括：因为两个变迁总是同时一起可实施的，因此选择是自由的；选择哪一个变迁实施并不依赖网络的标识。自由选择冲突子模型结构可用于系统调度、控制策略的表示。§7.2.3自由