基于Petri网工作流模型的分析2964.docx

《基于Petri网工作流模型的分析2964.docx》由会员分享，可在线阅读，更多相关《基于Petri网工作流模型的分析2964.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基于Peetrii网工作作流模型型的分析析晋蓓，冯冯卫兵（1. 西北大大学计算算机科学学系，陕陕西 西西安71100669；22. 西西安科技技大学基基础部，陕西 西安77100054）摘要：通通过模型型分析发发现所描描述的过过程定义义中的设设计错误误，以便便对业务务过程重重构提供供正确的的指导和和科学的的依据。首首先将信信牌驱动动模型转转化为PPetrri网，接接着将PPetrri网进进行必要要化简，最最后对化化简后的的Pettri网网进行死死锁等分分析。关键词：工工作流模模型；PPetrri网；死锁 中图分类类号：TTP9111.77 文献标标识码：A 文文章编号号：10000-2744X

2、(220044)00068-007工作流模模型的分分析是指指采用各各种方法法（包括括理论模模型、模模拟、测测量方法法），对工作作流模型型的内部部行为进进行分析析计算，使使得工作作流模型型在理论论上是正正确和有有效的。虽然现在在绝大部部分的工工作流产产品都提提供模型型性能分分析的仿仿真功能能，但由由于复杂杂性等原原因，很难找找到一种种有效的的算法对对模型进进行分析析与验证证。本文在在总结模模型分析析研究成成果现状状的基础础上，针针对目前前模型验验证方法法存在的的不足，总总结了PPetrri网模模型分析析中的一一些图形形化简规规则，针针对企业业经营过过程模型型的特点点并利用用文中提提出的模模型正确

3、确性标准准，提出出了一种种具有完完备性和和高效率率的工作作流模型型的模型型验证方方法分析析。1相关关概念定义1信信牌驱动动模型的的静态结结构: 多元式式称为信信牌驱动动模型的的静态结结构（以以下简称称信牌驱驱动模型型），其其中：1) 表表示扩展展的信牌牌驱动模模型所涉涉及的所所有数据据，其值值域用表表示；2) 表表示活动动集合，和分别称为功能函数和后继函数。被定义为根据出函数定义，参见下边的定义；3）表示示信牌箱箱集合；4），称称为的流流关系，其其中和分别称称为入关关系和出出关系。对对出关系系定义一一个出函函数：表示与与相关的的出函数数，被称称为的后后继函数数。5） 是惟一的活活动，称称为开始

4、始活动，；6） 是是一个活活动的集集合，称称为结束束活动，；7） 称为转转移的权权重；8）是（注注意：中中不包含含）的一一种划分分即是的另一一种划分分，即规定定。若，则；若若，则；如如果，则则被称为为简单元元素。一个信牌牌驱动的的工作流流模型，开开始活动动只能是是一个，但但是结束束活动可可以是多多个。为为了描述述问题方方便，有有时我们们也将信信牌驱动动的模型型简写成成。定义2真真假信牌牌，设。1）上的的一个多多重集是是一个映映射 (自然数数集合)，令表表示上所所有多重重集的集集合；2）表示示多重集集且表示多多重集且且表示多多重集 且。定义3活活动的SSPLIIT，设为信牌牌驱动模模型，令令，称

5、集集合为出弧的的集合。表示出弧的个数。与所联系的信牌箱称为的后信牌箱。或者或者和称为的SPLIT类型，记为。定义4活活动的JJOINN：设为信牌牌驱动模模型，令令，称集集合为入弧的的集合。表示入弧的个数。与联系的信牌箱称为的前信牌箱。或者或者或者或者，和称为的类型，记为。定义 55确定的的Pettri网网1。本文的的讨论均均在有限限网的基基础上进进行，以以下不再再说明。定义6非非确定PPetrri网系系统。参参见文献献1。定义7非非确定变变迁的发发生结果果。参见文文献11。2将信牌牌驱动模模型转化化为Peetrii网Petrri网有有很强的的表达能能力，其其描述能能力与TTuriing机机等价

6、，因因此所有有典型的的流程都都可用PPetrri网予予以描述述。本节节探讨将将工作流流模型中中的各种种基本控控制结构构自动地地转化为为Pettri网网的规则则。由于于工作流流模型是是由这些些基本的的控制结结构组合合而成的的复杂网网络，所所以工作作流模型型就可转转化为一一个Peetrii网模型型2。下面研究究典型流流程到PPetrri网结结构转换换的对应应规则（为为讨论方方便，在在没有特特别说明明的情况况下，在在转换过过程中对对应的信信牌箱与与位子的的容量相相同，对对应连线线的权值值相同）转转化原则则：转化化最重要要的是要要遵守原原系统的的原有逻逻辑顺序序，把对对象的操操作映射射为Peetrii

7、网模型型中的位位子；工工作流中中的活动动即Peetrii中的转转移；工工作流中中的开始始活动即即Pettri网网中的无无输入转转移和该该转移的的输出位位子，它它受外界界因素的的控制，自自动产生生激活整整个Petrri网；工作流流中的结结束标记记即Peetrii中的无无输出库库所得变迁和和单变迁迁的输入入库所；工作流流中的同同步节点点即Peetrii中的多多输人、单单输出变变迁及该该变迁的的库所33。1）开始始流程：结束流流程的转转化如图图1（aa）所示示。2）结束束流程：结束流流程的转转化如图图1（bb）所示示。（a）(b)图1 信牌驱驱动模型型向Peetrii网的转转化Fig. 1 Thhe

8、 ttrannsfoorm froom tthe Xinnpaii-drriveen mmodeel tto PPetrri nnet 3）顺序序流程：在信牌牌驱动模模型中，将将其中的的活动和和信牌箱箱分别对对应为变变迁和位位子，就就可构造造一个与与之等价价的Peetrii网结构构。4）竞争争流程：在扩展展的信牌牌驱动模模型中，竞竞争流程程可表示示为。其其中：；。将其其中的活活动和信信牌箱分分别对应应为变迁迁和位子子，就可可构造一一个与之之等价的的Pettri网网结构，其其中，是是与对应应的元素素，。5）无条条件分支支：它是一一种并发发执行的的结构。在信牌驱动模型中，并行流程可表示为，其中：

9、|。将其中的的活动和和信牌箱箱分别对对应为变变迁和位位子，就就可构造造一个与与之等价价的Peetrii网结构构。其中中：是与对应应的变迁迁，是是与对应应的位子子（见图22）。图2 信牌驱驱动模型型向Peetrii网的转转化Fig. 2 Thhe ttrannsfoorm froom tthe Xinnpaii-drriveen mmodeel tto PPetrri nnet6）分支支流程：在扩展展的信牌牌驱动模模型中，分分支流程程可表示示为，其其中：。根据它的的语义，可可构造一一个Peetrii网结构构与之等等价。其其中：是与对应应的变迁迁是与与 对应应的变迁迁；是是与对应应的位子子是与与对

10、应的的位子。例1图33（a）所所表示的的分支结结构可转转化为图图3（bb）的PPetrri网控控制结构构。（a）（bb）图3 信牌驱驱动模型型向Peetrii网的转转化Fig. 3 Thhe ttrannsfoorm froom tthe Xinnpaii-drriveen mmodeel tto PPetrri nnet7）多分分支流程程（ORR-SPPLITT）：在扩展展的信牌牌驱动模模型中，多多分支流流程可表表示为。其其中：。根据它的的语义，将将其中的的活动和和信牌箱箱分别对对应为变变迁和位位子，就就可构造造一个与与之等价价的非确确定Peetrii网结构构，其中中：是与对应应的非确确定变

11、迁迁是与与对应的的位子。8）XOOR-合合并流程程：在扩展展的信牌牌驱动模模型中，XXOR-合并流流程可表表示为，其其中：。根据它的的语义，可可以构造造一个PPetrri网结结构与其其等价。其其中：是与对应应的变迁迁；是与的每每个前信信牌箱对对应的变变迁；是与对应应的位子子是与对应应的位子子。例2(aa)表示示的信牌牌网结构构可转化化为 (b)的的Pettri网网结构。（aa） (b)图4 信牌驱驱动模型型向Peetrii网的转转化Fig. 4 Thhe ttrannsfoorm froom tthe Xinnpaii-drriveen mmodeel tto PPetrri nnet注意：它

12、它如果在在同步区区中出现现，该活活动的出出弧要加加权。9）ANND-同同步流程程：在扩展展的信牌牌驱动模模型中，AND-同步流程可表示为。其中：。根据它的的语义，将将其中的的活动和和信牌箱箱分别对对应为变变迁和位位子，就就可构造造一个与与之等价价的非确确定Peetrii网结构构。其中：是与对应应的变迁迁是与与对应的的位子。（在在同步区区中，设设SS为为同步区区的“门门”，则则F还应加加入，它它的权值值为，详详见同步步区的描描述）。10）OOR-同同步流程程：在扩展展的信牌牌驱动模模型中，它它一定要要有一个个OR-SPLLIT与与之对应应（可以以是配对对，也可可以是局局焦点。这这里选用用聚焦点点

13、）。为为了保证证在同步步区避免免多流交交叉问题题，这里里规定：只有当当OR-JOIIN节点点执行之之后，它它的聚焦焦点才能能再次执执行。11）TT-ANND合并并：它和ANND合并并的含义义类似，不不过它只只能出现现在非同同步区内内，而AAND合合并只能能出现在在同步区区内。所所以，它它的转化化与ANND合并并相识。12）循循环流程程：循环流流程就是是有一条条向前的的转移线线所构成成的控制制结构。向向Pettri网网转化时时，无论论是在同同步区还还是在非非同步区区中的循循环，只只要按照照上面讨讨论的各各种分支支和合并并的规则则进行即即可44。3Peetrii网的化化简3.1伪位置置化简法法定义

14、8在在一个带带标识MM的Peetrii网中，定定义表示示的输入入元素的的集合；表示的输输出元素素的集合合。表示示代中的元元素个数数。如果，且且满足， ；，那么称称位子伪伪位子。化简规则则1如果一一个确定定的Peetrii网存在在一个伪伪位子，则则可以删删除这个个位子及及相连的的所有的的弧（证证明见文文献55），如图55所示。tp(a)含含有一伪伪位子pp(b)消除伪伪位子pp图5 伪位置置化简法法的例子子Fig 5 TThe exaamplle oof rreduucattionn定义9在在一个带带标识MM的Peetri网网中，如如果，且且满足，； ，那那么称位位子伪转转移。3.2伪转移移化简

15、法法化简规则则2如果一一个确定定的Peetrii网存在在一个伪伪转移，则则可以删删除这个个转移及及相连的的所有的的弧。3.3等价位位子化简简法定义100在一个个带标识识M的PPetrri网中，如如果存在在 ，且且满足=；=；=， 那么称位位子，是等价价位子。化简规则则3如果一一个确定定的Peetrii网存在在等价的的转移，则则可以删删除这些些等价转转移中任任意一个个及相连连的所有有的弧。3.4转移合合并化简简法该方法指指的是当当两相邻邻的转移移及中间间的位子子满足一一定的条条件时，可可以删除除中间位位子，并并将两个个位子合合并成一一个转移移5。此外，还还有等价价转移化化简法，因因与等价价位子化

16、化简法相相似，不不再赘述述。若原网是是有界的的，那么么转化后后也是有有界的；若原网网是无界界的，那那么转化化后也是是无界的的；若原网网是活的的，则转转化后也也是活的的；若原原网存在在死锁，则则转化后后也存在在死锁。即即按照上上边的55条规则则转化，性性质保持持不变。4死锁检检测算法法定义111在Peetrii网中，对对于，设设=，= ，则死锁锁定义可可以描述述为位子子的非空空子集，且且满足定义122 若若非空子子集是死死锁的，而，不是死死锁的，则称称为最小小死锁。其其他的定定义参见见文献6。图图6是死死锁的检检测算法法。图6 死死锁的检检测Fig.6 TThe cheeck of deaadl

17、oock5结语语工作流模模型是工工作流管管理系统统的基础础和核心心，模型型分析有有助于发发现所描描述的过过程定义义中的设设计错误误，以便便对业务务过程重重构提供供正确的的指导和和科学的的依据。本本文首先先将信牌牌驱动模模型转化化为Peetrii网，接接着将PPetrri网进进行必要要的化简简，大大大简化了了模型分分析的难难度，在在此基础础上对化化简后的的Pettri网网进行死死锁等分分析，方法简简单实用用。参考文献献：1 王斌君君. 工工作流过过程模型型的层次次研究及及其分析析D. 西西安：西西北大学学计算机机科学系系, 220022.2 潘启澍澍, 姜姜兵.基于于Pettri网网的工作作流建

18、模模技术及及应用J. 清华华大学学学报（自自然科学学版）, 20000, 400( 99): 866-89.3 岳晓丽丽, 杨杨斌, 郝克刚刚. 信信牌驱动动式工作作流计算算模型J. 计算算机研究究与发展, 20000, 37(12): 115133- 115199.4 vann deer AAALSST WWMP. Pettri-nett-baasedd woorkffloww maanaggemeent sofftwaareA . SSHETTH AA. PProcceeddinggs oof tthe NFSS Woorksshopp onn Woorkffloww annd PProc

19、cesss Auutommatiion in Infformmatiion SysstemmsCC.Geoorgiia： Atthenns , 19996,11441118.5 张明明明，杨文文龙. Pettri网网化简与与实现 A . 杨文龙龙.基于于Pettri网网的并发发软件开开发方法法及其支支持工具具的研究究C. 北北京: 科学技技术文献献出版社社,19993. 555-65.6任任爱华, 唐培培和, 雒力旭旭, 等等. 基基于Peetrii网的并并发系统统死锁检检测方法法A. 杨杨文龙. 基于于Pettri网网的并发发软件开开发方法法及其支支持工具具的研究究C. 北北京: 科学技技术

20、文献献出版社社,19993. 666811.(编 辑辑曹大刚刚)Workkfloow mmodeel aanallysiisJINBBei FFENGG Weei-binng(Insstittutee off Sooftwwaree Ennginneerringg, NoorthhwesstUnniveersiity, Xiian71100669,Chinna)Absttracct:Thee deefauult of proocesss ddesiign is fouund by Worrkfllow moddel Anaalyssis. Thhe ppropper dirrecttionn

21、annd sscieentiificc giist aree prroviidedd.Thhe XXinppai-driivenn moodell iss trranssforrmedd too Peetrii neet aand norrmall Peetrii neet, andd thhen to genneraal PPetrri nnet. Thhe ccharractterss off exxtenndinng XXinppai-driivenn moodell arre rreseearcchedd inn Peetrii neet sspacce.TThe deaadloock

22、 in Pettri nett prrediigesstedd iss annalyysissed. Keywwordds: workkfloow mmodeel Pettri nett ddeaddlocck作 者 简 介介晋 蓓蓓，女，陕陕西韩城城人，生生于19973年年10月月。20000年年至20003年年于西北北大学计计算机系系进修计计算机软软件与理理论专业业，并攻攻读硕士士学位。主主要从事事计算机机软件理理论中的的系统学学研究工工作。近近期在西西北大学学学报(自然科学版)增刊上发表有“Java AWT中的设计模式举例”、“建立在工作流基础上的回退解决方案”、“浅谈软件项目管理”等学术论文。11