基于扩展UML图化简的过程模型冲突消解

张 婷

（南阳师范学院计算机与信息技术学院，河南南阳473000）

0 引 言

工作流的正确性包括两个方面的含义:一方面是结构正确性，也就是说业务过程模型是不包含结构冲突的，在没有错误发生时工作流能正常终止；另一方面是语义正确性，即工作流在正常终止时应达到所期望的业务目标［1－2］。其中，结构冲突是导致业务过程模型结构不正确的主要原因。由于业务过程模型中其它错误的存在不会增加或减少结构冲突，因而，结构冲突验证可独立于其它方面的验证进行。本文仅对结构冲突进行检测与消解。

1 结构冲突的特点

结构冲突是指业务过程模型的控制流中出现错误，导致工作流在运行时无法正常终止。它是导致过程模型逻辑错误的原因，直接影响业务过程的执行是否可以正常终止［3］。常见的结构冲突有:开始/结束节点缺失、死锁、同步缺失和活锁［4－5］。分支节点（Split）和结合节点（Join）在组合过程中所具备的特征是过程模型验证的依据，其具备的特征如下:

（1）若循环结构存在于一个Xor－Split节点和And－Join节点之间，则存在活锁；

（2）And－Join输入的前序路径中，若有来自Xor－Split的输出，则And－Join处出现死锁；

（3）Xor－Join输入的前序路径中，若有来自And－Split的输出，则Xor－Join处有同步缺失。

2 扩展的UML活动图元素

为了使业务建模过程更方便，采用基本的UML活动图中的图例描述业务过程［6－7］。为了描述复杂的业务过程，还使用扩展的图例来建立业务过程模型:

（1）原子活动节点。原子活动节点表示工作流中的一个不可分解的任务。它有且仅有一个输入路径和一个输出路径。

（2）控制节点。控制节点有4种，分别是多路与分支、多路与结合、多路或分支、多路或结合。多路与分支的输入被使能时，其所有输出都会被激活；多路与结合在所有输入都被使能时，其输出才会被激活；多路或分支的输入被使能时，其输出有且仅有一个被激活；多路或结合的所有输入中有且仅有一个被使能时，其输出才能被激活。

（3）活动聚合块。活动聚合块Sub是由若干原子活动节点和控制节点组成的聚合结构。

3 基于图化简的冲突消解

3.1 冲突消解策略

在一个非结构化的业务过程建模过程中，Split和Join通常没有严格的一对一的关系，从而导致过程模型中的结构错误。冲突消解策略是针对结构冲突而制定的。

（1）开始/结束结点缺失:给出提示，用户可自行添加。

（2）活锁:活锁是由于在定义循环结构时，循环的输出节点为与分支节点而引起的。如图1（a）中所示，由于B节点是与分支，使得模型的结构中出现活锁，节点B出错，则修改方案是将B节点修改为或分支节点，消解的方案如图1（b）所示。

图1 活锁的消解方法

（3）死锁:如图2（a）在结构中存在死锁。这时若修改节点B，将B节点改为或结合节点，修改后的结构如图2（c）所示；若修改节点A，将A节点改为与分支节点，修改后的结构如图2（d）所示。由于死锁的原因是由于一个或分支节点后跟随一个与结合节点引起的，显然节点B出错可能性大，修改节点B的提示会优先。

图2 死锁和同步缺失的消解方法

（4）同步缺失:如图2（b）在结构中存在同步缺失。这时若修改节点B，将B节点改为与结合节点，修改后的结构如图2（d）所示；若修改节点A，将A节点改为或分支节点，修改后的结构如图2（c）所示。由于同步缺失一般是由于一个与分支节点后跟随一个或结合节点引起的，显然节点B出错的可能性大，选择修改节点B的提示会优先。

3.2 冲突消解算法

图化简的规则［1，8，9］包含6个类别，分别是:①终端化简，②顺序化简，③临近化简，④闭合化简，⑤重叠化简，⑥循环化简。已知活动图AD，其基本结构正确。

（1）在AD中应用规则①，去掉活动图中的开始和终止节点。若化简结果为空，则AD正确，冲突检测结束；否则转步骤（2）。

（2）判断AD中是否存在循环，若是或分支的循环结构，则按规则⑥进行转换；若是与分支的循环结构，则存在冲突，冲突检测结束。

（3）应用规则②将AD中所有活动节点去除。若化简结果为空，则AD是正确的，冲突检测结束；否则转步骤（4）。

（4）在AD中依次应用规则③～规则④，直到AD不能再化简为止。若化简结果为空，则AD是正确的，冲突检测结束；否则转步骤（5）。

（5）在AD中依次应用规则⑤，直到AD不能再化简为止。

（6）经过步骤（4）－（5），若活动图AD未发生变化，则活动图存在结构冲突，冲突检测结束，转入步骤（7）进行冲突消解；否则转步骤（4）。

（7）根据冲突消解策略进行冲突消解，转步骤（5）。

4 冲突消解的实现

4.1 结构冲突的描述

结构冲突报告中包含有冲突类型、冲突原因、以及与之有关的节点、业务过程模型部分字段信息；另外也应指出引起冲突的分支或结合节点的详细信息。表1为结构冲突的描述。其中，错误类型有:或分支死锁（Dead Lock－Source），与结合死锁（Dead Lock Target），与分支同步缺失（Syn LackSource），或结合同步缺失（Syn Lack Target），活锁（Lock Target）；节点类型有:分支（Split），结合（Join）；节点逻辑有:与（And），或（Xor）。

表1 结构冲突描述

4.2 冲突消解的实现

图3为用于业务过程模型结构冲突消解的类图，图4为冲突检测的类图。

（1）进行数据预处理，读取活动节点（Act Node）、控制节点（Control Node）、活动块节点（ActBlock Node），将这些节点保存入一个工作流实例（workflow）中。每个节点类包含两个属性:前趋节点集（pre Nodes）和后继节点集（next Nodes），用来表示节点间弧关系。

（2）对业务过程模型中的各种结构冲突进行检测。经数据预处理，业务过程模型转换为workflow的实例。化简规则的实现都继承于基类Reduction Rules，在Reduction Rules中定义操作workflow实例的方法。EReduction Rules类只有一个ReductionProcess方法，参数是描述过程模型的文件路径，返回值是通过属性FileName来指出保存冲突节点的文件路径。

（3）业务过程模型类（workflow）的方法handleConflict实现冲突消解的功能。冲突消解是给出UML模型图的结构冲突及相应的消解方案。冲突消解具体实施时，采用了图化简的方式进行冲突检测，对活动图边化简边消解。针对某一个冲突，不论选择哪种消解方案，都会使这个冲突结构满足化简规则，可以在图化简的过程中被化简掉。因此，在给出某一个冲突的可选消解方案后，选择任何一种方案加以实施，其结果是等价的。

4.3 冲突消解算法分析

冲突检测的限制主要来源于工作流模型复杂度的增长，以及能检测出的冲突种类。因此，侧重于对比可检的冲突类别、节点个数与参数的变化对检测时间的影响。在业务过程模型中选取出现结构冲突的实例，作为各结构验证算法的输入进行实验。其中，基于Petri网归约算法的输入是转换为Petri网后的业务过程模型。

（1）分析以下几种结构验证算法:基于状态转换［3，10］，基于Petri网归约［11－12］，基于语义推理［13－14］，和基于扩展UML活动图化简，结果见表2。可检测是指对于模型中相应的结构冲突，结构验证算法能检测出；可识别是指对于检测出的冲突，可通过检测结果分析出冲突的类型。

表2 结构验证算法的比较

（2）过程模型的节点数目分别为5、10、20、30时，每样各30个实例，实例中包含死锁实例、同步缺失实例和活锁实例各10个。控制节点的入度和出度为小于等于2时，结构验证算法的运算时间如图5所示。

图5 节点数目递增的冲突检测平均处理时间

（3）过程模型的节点数为10，控制节点的度为2、3、4时，每样各有30个实例，实例中包含死锁实例、同步缺失实例和活锁实例各10个。结构验证算法的运算时间如图6所示。

从表2可以看出，基于语义推理算法只能检测冲突，不能识别冲突，对于冲突消解不适用。基于状态转换算法不能检测出现循环结构的过程模型，基于语义推理的算法不能检测出现重叠结构的过程模型，这两种算法对于复杂的业务过程模型来说是不适用的。

图6 控制节点度数递增的冲突检测平均处理时间

实验结果表明虽然4种算法的时间复杂度是相同的，但是在节点数目或控制节点度数增加时，UML活动图化简的算法的平均处理时间少。基于UML活动图化简的算法适用于处理复杂的业务过程模型，在处理过程中采用了化简的方法降低模型的规模，降低冲突检测时间。同时它能够识别出冲突适合于对下一步对冲突进行消解。4种结构验证算法在时间复杂度相同的情况下，在处理节点数目递增的业务过程模型时，实际的平均处理时间相差较大。基于状态转换算法和基于语义推理算法都没有使用化简，不能使模型的规模缩小。基于Petri网归约的算法虽然使用了化简，但UML活动图表示的过程模型转换为用Petri网表示的过程模型后，实际节点的数目会增加，这弱化了化简方法的处理能力。在处理节点度数递增的业务过程模型时，由于基于UML活动图化简的算法对控制节点进行了扩展，可以处理度数大于2的控制节点。其它算法对于度数大于2的控制节点只能先转化为度数不大于2的控制节点后才能运算，增加了节点数目，也使运算时间增长。

5 结束语

为了描述复杂的业务过程模型的逻辑结构，扩展了UML活动图，定义了业务过程模型中的控制节点，如多路合并和多路分支节点。冲突检测算法采用图化简方法来进行将模型缩减到适当规模，便于进行验证，并将化简方法总结为规则集的形式，易于理解和实现。冲突检测可以对重叠结构和循环结构进行有效地化简，并能检测常见的结构冲突。通过分析各种冲突产生的原因，并给出了相应的冲突消解方案。冲突消解方案可以针对各种建模过程中产生的各种结构冲突，给出消解方法，协助操作人员处理冲突。

创新点:扩展UML图适用于描述大规模复杂应用的业务过程模型，能检测含有循环和重叠结构的结构冲突，并能指出冲突结构类型，给出相应冲突消解方案，协助处理冲突。

［1］ZHOU Jian－tao，SHI Mei－lin，YE Xin－ming.Formal verification techniques in workflow process modeling［J］.Computer Research and Development，2005，42（1）:1－2（in Chinese）.［周建涛，史美林，叶新铭.工作流过程建模中形式化验证技术［J］.计算机研究与发展，2005，42（1）:1－2.］

［2］Cai J，Zhao W，Zhang S K，et al.Correctness verification of synchronization based workflow model［C］.Beijing:Proceeding of the IEEE International Conference on e－Bossiness Engineering，2005:527－530.

［3］Fode T，Karim B，Khalid B.An efficient algorithm for workflow graph structural verification［G］.Lecture Notes In Computer Science 5331:On the Move to Meaningful Internet Systems，2008:392－408.

［4］ZHANG Min，GUO Yu－bin.Survey for correctness problem of workflow system［J］.Application Research of Computers，2009，26（5）:1645－1648（in Chinese）.［张民，郭玉彬.工作流正确性问题综述［J］.计算机应用研究，2009，26（5）:1645－1648.］

［5］CUI Li－zhen，WANG Hai－yang.Verification method for workflow model correctness［J］.System simulations，2008，20（8）:1950－1968（in Chinese）.［崔立真，王海洋.一种工作流模型正确性验证方法［J］.系统仿真学报，2008，20（8）:1950－1968.］

［6］ZHAO He－ji，ZHANG Li－chun.Workflow modeling method and design based on UML activity diagram［J］.Computer Applications and Software，2004，21（8）:44－45（in Chinese）.［赵合计，张立春.UML活动图支持下的工作流建模方法与设计［J］.计算机应用与软件，2004，21（8）:44－45.］

［7］LIU Yi，ZHANG Zi－gang，ZHANG Kan.Overview of workflow models［J］.Computer Engineering and Design，2007，28（2）:449－450（in Chinese）.［刘怡，张子刚，张戡.工作流模型研究述评［J］.计算机工程与设计，2007，28（2）:449－450.］

［8］Li Ye－bai，Mao Fu－qi.Research of the verification in workflow process modeling on the application of Petri nets［C］.International Conference on e－Education，e－Business，e－Management and e－Learning，2010:21－24.

［9］Nazia Leyla，Ahmed Shah Mashiyat，Hao Wang，et al.Towards workflow verification［C］.Proceedings of the Conference of the Center for Advanced Studies on Collaborative Research，2010:255－260.

［10］Zhao Lei，Qian Leqiu，Zhao Wenyun.State－space based verification of workflow model［J］.Computer Engineering and Application，2004，40（10）:220－222.

［11］XU Jing－ming，DU Bao－zhu.Workflow process model structure verification based on Petri net reduction techniques［J］.Computer Technology and Development，2009，19（6）:51－57（in Chinese）.［徐晶明，杜宝珠.基于Petri网化简技术的工作流过程模型结构验证［J］.计算机技术与发展，2009，19（6）:51－57.］

［12］Wang Bao－yi，Zhang Shao－min，Xue Qiao－li.The analysis on grid workflow’s deadlock by Petri nets［C］.World Congress on Intelligent Control and Automation，2008:5428－5431.

［13］Ling Hong，Zhao Jiang－bou.Research on workflow process structure verification［C］.IEEE International Conference on e－Business Engineering，2005:160－166.

［14］LING Hong，ZHOU Jiang－bo，XU Zheng－chuan.Semantic deduction－based workflow structure verification method［J］.Computer Integrated Manufacturing Systems，2006，12（6）:893－898（in Chinese）.［凌鸿，周江波，胥正川.基于语义推理的工作流结构验证方法［J］.计算机集成制造系统，2006，12（6）:893－898.］