張 婷

（南陽(yáng)師范學(xué)院計(jì)算機(jī)與信息技術(shù)學(xué)院，河南南陽(yáng)473000）

0 引 言

工作流的正確性包括兩個(gè)方面的含義:一方面是結(jié)構(gòu)正確性，也就是說業(yè)務(wù)過程模型是不包含結(jié)構(gòu)沖突的，在沒有錯(cuò)誤發(fā)生時(shí)工作流能正常終止；另一方面是語義正確性，即工作流在正常終止時(shí)應(yīng)達(dá)到所期望的業(yè)務(wù)目標(biāo)［1－2］。其中，結(jié)構(gòu)沖突是導(dǎo)致業(yè)務(wù)過程模型結(jié)構(gòu)不正確的主要原因。由于業(yè)務(wù)過程模型中其它錯(cuò)誤的存在不會(huì)增加或減少結(jié)構(gòu)沖突，因而，結(jié)構(gòu)沖突驗(yàn)證可獨(dú)立于其它方面的驗(yàn)證進(jìn)行。本文僅對(duì)結(jié)構(gòu)沖突進(jìn)行檢測(cè)與消解。

1 結(jié)構(gòu)沖突的特點(diǎn)

結(jié)構(gòu)沖突是指業(yè)務(wù)過程模型的控制流中出現(xiàn)錯(cuò)誤，導(dǎo)致工作流在運(yùn)行時(shí)無法正常終止。它是導(dǎo)致過程模型邏輯錯(cuò)誤的原因，直接影響業(yè)務(wù)過程的執(zhí)行是否可以正常終止［3］。常見的結(jié)構(gòu)沖突有:開始/結(jié)束節(jié)點(diǎn)缺失、死鎖、同步缺失和活鎖［4－5］。分支節(jié)點(diǎn)（Split）和結(jié)合節(jié)點(diǎn)（Join）在組合過程中所具備的特征是過程模型驗(yàn)證的依據(jù)，其具備的特征如下:

（1）若循環(huán)結(jié)構(gòu)存在于一個(gè)Xor－Split節(jié)點(diǎn)和And－Join節(jié)點(diǎn)之間，則存在活鎖；

（2）And－Join輸入的前序路徑中，若有來自Xor－Split的輸出，則And－Join處出現(xiàn)死鎖；

（3）Xor－Join輸入的前序路徑中，若有來自And－Split的輸出，則Xor－Join處有同步缺失。

2 擴(kuò)展的UML活動(dòng)圖元素

為了使業(yè)務(wù)建模過程更方便，采用基本的UML活動(dòng)圖中的圖例描述業(yè)務(wù)過程［6－7］。為了描述復(fù)雜的業(yè)務(wù)過程，還使用擴(kuò)展的圖例來建立業(yè)務(wù)過程模型:

（1）原子活動(dòng)節(jié)點(diǎn)。原子活動(dòng)節(jié)點(diǎn)表示工作流中的一個(gè)不可分解的任務(wù)。它有且僅有一個(gè)輸入路徑和一個(gè)輸出路徑。

（2）控制節(jié)點(diǎn)。控制節(jié)點(diǎn)有4種，分別是多路與分支、多路與結(jié)合、多路或分支、多路或結(jié)合。多路與分支的輸入被使能時(shí)，其所有輸出都會(huì)被激活；多路與結(jié)合在所有輸入都被使能時(shí)，其輸出才會(huì)被激活；多路或分支的輸入被使能時(shí)，其輸出有且僅有一個(gè)被激活；多路或結(jié)合的所有輸入中有且僅有一個(gè)被使能時(shí)，其輸出才能被激活。

（3）活動(dòng)聚合塊?；顒?dòng)聚合塊Sub是由若干原子活動(dòng)節(jié)點(diǎn)和控制節(jié)點(diǎn)組成的聚合結(jié)構(gòu)。

3 基于圖化簡(jiǎn)的沖突消解

3.1 沖突消解策略

在一個(gè)非結(jié)構(gòu)化的業(yè)務(wù)過程建模過程中，Split和Join通常沒有嚴(yán)格的一對(duì)一的關(guān)系，從而導(dǎo)致過程模型中的結(jié)構(gòu)錯(cuò)誤。沖突消解策略是針對(duì)結(jié)構(gòu)沖突而制定的。

（1）開始/結(jié)束結(jié)點(diǎn)缺失:給出提示，用戶可自行添加。

（2）活鎖:活鎖是由于在定義循環(huán)結(jié)構(gòu)時(shí)，循環(huán)的輸出節(jié)點(diǎn)為與分支節(jié)點(diǎn)而引起的。如圖1（a）中所示，由于B節(jié)點(diǎn)是與分支，使得模型的結(jié)構(gòu)中出現(xiàn)活鎖，節(jié)點(diǎn)B出錯(cuò)，則修改方案是將B節(jié)點(diǎn)修改為或分支節(jié)點(diǎn)，消解的方案如圖1（b）所示。

圖1 活鎖的消解方法

（3）死鎖:如圖2（a）在結(jié)構(gòu)中存在死鎖。這時(shí)若修改節(jié)點(diǎn)B，將B節(jié)點(diǎn)改為或結(jié)合節(jié)點(diǎn)，修改后的結(jié)構(gòu)如圖2（c）所示；若修改節(jié)點(diǎn)A，將A節(jié)點(diǎn)改為與分支節(jié)點(diǎn)，修改后的結(jié)構(gòu)如圖2（d）所示。由于死鎖的原因是由于一個(gè)或分支節(jié)點(diǎn)后跟隨一個(gè)與結(jié)合節(jié)點(diǎn)引起的，顯然節(jié)點(diǎn)B出錯(cuò)可能性大，修改節(jié)點(diǎn)B的提示會(huì)優(yōu)先。

圖2 死鎖和同步缺失的消解方法

（4）同步缺失:如圖2（b）在結(jié)構(gòu)中存在同步缺失。這時(shí)若修改節(jié)點(diǎn)B，將B節(jié)點(diǎn)改為與結(jié)合節(jié)點(diǎn)，修改后的結(jié)構(gòu)如圖2（d）所示；若修改節(jié)點(diǎn)A，將A節(jié)點(diǎn)改為或分支節(jié)點(diǎn)，修改后的結(jié)構(gòu)如圖2（c）所示。由于同步缺失一般是由于一個(gè)與分支節(jié)點(diǎn)后跟隨一個(gè)或結(jié)合節(jié)點(diǎn)引起的，顯然節(jié)點(diǎn)B出錯(cuò)的可能性大，選擇修改節(jié)點(diǎn)B的提示會(huì)優(yōu)先。

3.2 沖突消解算法

圖化簡(jiǎn)的規(guī)則［1，8，9］包含6個(gè)類別，分別是:①終端化簡(jiǎn)，②順序化簡(jiǎn)，③臨近化簡(jiǎn)，④閉合化簡(jiǎn)，⑤重疊化簡(jiǎn)，⑥循環(huán)化簡(jiǎn)。已知活動(dòng)圖AD，其基本結(jié)構(gòu)正確。

（1）在AD中應(yīng)用規(guī)則①，去掉活動(dòng)圖中的開始和終止節(jié)點(diǎn)。若化簡(jiǎn)結(jié)果為空，則AD正確，沖突檢測(cè)結(jié)束；否則轉(zhuǎn)步驟（2）。

（2）判斷AD中是否存在循環(huán)，若是或分支的循環(huán)結(jié)構(gòu)，則按規(guī)則⑥進(jìn)行轉(zhuǎn)換；若是與分支的循環(huán)結(jié)構(gòu)，則存在沖突，沖突檢測(cè)結(jié)束。

（3）應(yīng)用規(guī)則②將AD中所有活動(dòng)節(jié)點(diǎn)去除。若化簡(jiǎn)結(jié)果為空，則AD是正確的，沖突檢測(cè)結(jié)束；否則轉(zhuǎn)步驟（4）。

（4）在AD中依次應(yīng)用規(guī)則③～規(guī)則④，直到AD不能再化簡(jiǎn)為止。若化簡(jiǎn)結(jié)果為空，則AD是正確的，沖突檢測(cè)結(jié)束；否則轉(zhuǎn)步驟（5）。

（5）在AD中依次應(yīng)用規(guī)則⑤，直到AD不能再化簡(jiǎn)為止。

（6）經(jīng)過步驟（4）－（5），若活動(dòng)圖AD未發(fā)生變化，則活動(dòng)圖存在結(jié)構(gòu)沖突，沖突檢測(cè)結(jié)束，轉(zhuǎn)入步驟（7）進(jìn)行沖突消解；否則轉(zhuǎn)步驟（4）。

（7）根據(jù)沖突消解策略進(jìn)行沖突消解，轉(zhuǎn)步驟（5）。

4 沖突消解的實(shí)現(xiàn)

4.1 結(jié)構(gòu)沖突的描述

結(jié)構(gòu)沖突報(bào)告中包含有沖突類型、沖突原因、以及與之有關(guān)的節(jié)點(diǎn)、業(yè)務(wù)過程模型部分字段信息；另外也應(yīng)指出引起沖突的分支或結(jié)合節(jié)點(diǎn)的詳細(xì)信息。表1為結(jié)構(gòu)沖突的描述。其中，錯(cuò)誤類型有:或分支死鎖（Dead Lock－Source），與結(jié)合死鎖（Dead Lock Target），與分支同步缺失（Syn LackSource），或結(jié)合同步缺失（Syn Lack Target），活鎖（Lock Target）；節(jié)點(diǎn)類型有:分支（Split），結(jié)合（Join）；節(jié)點(diǎn)邏輯有:與（And），或（Xor）。

表1 結(jié)構(gòu)沖突描述

4.2 沖突消解的實(shí)現(xiàn)

圖3為用于業(yè)務(wù)過程模型結(jié)構(gòu)沖突消解的類圖，圖4為沖突檢測(cè)的類圖。

（1）進(jìn)行數(shù)據(jù)預(yù)處理，讀取活動(dòng)節(jié)點(diǎn)（Act Node）、控制節(jié)點(diǎn)（Control Node）、活動(dòng)塊節(jié)點(diǎn)（ActBlock Node），將這些節(jié)點(diǎn)保存入一個(gè)工作流實(shí)例（workflow）中。每個(gè)節(jié)點(diǎn)類包含兩個(gè)屬性:前趨節(jié)點(diǎn)集（pre Nodes）和后繼節(jié)點(diǎn)集（next Nodes），用來表示節(jié)點(diǎn)間弧關(guān)系。

（2）對(duì)業(yè)務(wù)過程模型中的各種結(jié)構(gòu)沖突進(jìn)行檢測(cè)。經(jīng)數(shù)據(jù)預(yù)處理，業(yè)務(wù)過程模型轉(zhuǎn)換為workflow的實(shí)例?；?jiǎn)規(guī)則的實(shí)現(xiàn)都繼承于基類Reduction Rules，在Reduction Rules中定義操作workflow實(shí)例的方法。EReduction Rules類只有一個(gè)ReductionProcess方法，參數(shù)是描述過程模型的文件路徑，返回值是通過屬性FileName來指出保存沖突節(jié)點(diǎn)的文件路徑。

（3）業(yè)務(wù)過程模型類（workflow）的方法handleConflict實(shí)現(xiàn)沖突消解的功能。沖突消解是給出UML模型圖的結(jié)構(gòu)沖突及相應(yīng)的消解方案。沖突消解具體實(shí)施時(shí)，采用了圖化簡(jiǎn)的方式進(jìn)行沖突檢測(cè)，對(duì)活動(dòng)圖邊化簡(jiǎn)邊消解。針對(duì)某一個(gè)沖突，不論選擇哪種消解方案，都會(huì)使這個(gè)沖突結(jié)構(gòu)滿足化簡(jiǎn)規(guī)則，可以在圖化簡(jiǎn)的過程中被化簡(jiǎn)掉。因此，在給出某一個(gè)沖突的可選消解方案后，選擇任何一種方案加以實(shí)施，其結(jié)果是等價(jià)的。

4.3 沖突消解算法分析

沖突檢測(cè)的限制主要來源于工作流模型復(fù)雜度的增長(zhǎng)，以及能檢測(cè)出的沖突種類。因此，側(cè)重于對(duì)比可檢的沖突類別、節(jié)點(diǎn)個(gè)數(shù)與參數(shù)的變化對(duì)檢測(cè)時(shí)間的影響。在業(yè)務(wù)過程模型中選取出現(xiàn)結(jié)構(gòu)沖突的實(shí)例，作為各結(jié)構(gòu)驗(yàn)證算法的輸入進(jìn)行實(shí)驗(yàn)。其中，基于Petri網(wǎng)歸約算法的輸入是轉(zhuǎn)換為Petri網(wǎng)后的業(yè)務(wù)過程模型。

（1）分析以下幾種結(jié)構(gòu)驗(yàn)證算法:基于狀態(tài)轉(zhuǎn)換［3，10］，基于Petri網(wǎng)歸約［11－12］，基于語義推理［13－14］，和基于擴(kuò)展UML活動(dòng)圖化簡(jiǎn)，結(jié)果見表2?？蓹z測(cè)是指對(duì)于模型中相應(yīng)的結(jié)構(gòu)沖突，結(jié)構(gòu)驗(yàn)證算法能檢測(cè)出；可識(shí)別是指對(duì)于檢測(cè)出的沖突，可通過檢測(cè)結(jié)果分析出沖突的類型。

表2 結(jié)構(gòu)驗(yàn)證算法的比較

（2）過程模型的節(jié)點(diǎn)數(shù)目分別為5、10、20、30時(shí)，每樣各30個(gè)實(shí)例，實(shí)例中包含死鎖實(shí)例、同步缺失實(shí)例和活鎖實(shí)例各10個(gè)?？刂乒?jié)點(diǎn)的入度和出度為小于等于2時(shí)，結(jié)構(gòu)驗(yàn)證算法的運(yùn)算時(shí)間如圖5所示。

圖5 節(jié)點(diǎn)數(shù)目遞增的沖突檢測(cè)平均處理時(shí)間

（3）過程模型的節(jié)點(diǎn)數(shù)為10，控制節(jié)點(diǎn)的度為2、3、4時(shí)，每樣各有30個(gè)實(shí)例，實(shí)例中包含死鎖實(shí)例、同步缺失實(shí)例和活鎖實(shí)例各10個(gè)。結(jié)構(gòu)驗(yàn)證算法的運(yùn)算時(shí)間如圖6所示。

從表2可以看出，基于語義推理算法只能檢測(cè)沖突，不能識(shí)別沖突，對(duì)于沖突消解不適用?；跔顟B(tài)轉(zhuǎn)換算法不能檢測(cè)出現(xiàn)循環(huán)結(jié)構(gòu)的過程模型，基于語義推理的算法不能檢測(cè)出現(xiàn)重疊結(jié)構(gòu)的過程模型，這兩種算法對(duì)于復(fù)雜的業(yè)務(wù)過程模型來說是不適用的。

圖6 控制節(jié)點(diǎn)度數(shù)遞增的沖突檢測(cè)平均處理時(shí)間

實(shí)驗(yàn)結(jié)果表明雖然4種算法的時(shí)間復(fù)雜度是相同的，但是在節(jié)點(diǎn)數(shù)目或控制節(jié)點(diǎn)度數(shù)增加時(shí)，UML活動(dòng)圖化簡(jiǎn)的算法的平均處理時(shí)間少?；赨ML活動(dòng)圖化簡(jiǎn)的算法適用于處理復(fù)雜的業(yè)務(wù)過程模型，在處理過程中采用了化簡(jiǎn)的方法降低模型的規(guī)模，降低沖突檢測(cè)時(shí)間。同時(shí)它能夠識(shí)別出沖突適合于對(duì)下一步對(duì)沖突進(jìn)行消解。4種結(jié)構(gòu)驗(yàn)證算法在時(shí)間復(fù)雜度相同的情況下，在處理節(jié)點(diǎn)數(shù)目遞增的業(yè)務(wù)過程模型時(shí)，實(shí)際的平均處理時(shí)間相差較大?；跔顟B(tài)轉(zhuǎn)換算法和基于語義推理算法都沒有使用化簡(jiǎn)，不能使模型的規(guī)模縮小?；赑etri網(wǎng)歸約的算法雖然使用了化簡(jiǎn)，但UML活動(dòng)圖表示的過程模型轉(zhuǎn)換為用Petri網(wǎng)表示的過程模型后，實(shí)際節(jié)點(diǎn)的數(shù)目會(huì)增加，這弱化了化簡(jiǎn)方法的處理能力。在處理節(jié)點(diǎn)度數(shù)遞增的業(yè)務(wù)過程模型時(shí)，由于基于UML活動(dòng)圖化簡(jiǎn)的算法對(duì)控制節(jié)點(diǎn)進(jìn)行了擴(kuò)展，可以處理度數(shù)大于2的控制節(jié)點(diǎn)。其它算法對(duì)于度數(shù)大于2的控制節(jié)點(diǎn)只能先轉(zhuǎn)化為度數(shù)不大于2的控制節(jié)點(diǎn)后才能運(yùn)算，增加了節(jié)點(diǎn)數(shù)目，也使運(yùn)算時(shí)間增長(zhǎng)。

5 結(jié)束語

為了描述復(fù)雜的業(yè)務(wù)過程模型的邏輯結(jié)構(gòu)，擴(kuò)展了UML活動(dòng)圖，定義了業(yè)務(wù)過程模型中的控制節(jié)點(diǎn)，如多路合并和多路分支節(jié)點(diǎn)。沖突檢測(cè)算法采用圖化簡(jiǎn)方法來進(jìn)行將模型縮減到適當(dāng)規(guī)模，便于進(jìn)行驗(yàn)證，并將化簡(jiǎn)方法總結(jié)為規(guī)則集的形式，易于理解和實(shí)現(xiàn)。沖突檢測(cè)可以對(duì)重疊結(jié)構(gòu)和循環(huán)結(jié)構(gòu)進(jìn)行有效地化簡(jiǎn)，并能檢測(cè)常見的結(jié)構(gòu)沖突。通過分析各種沖突產(chǎn)生的原因，并給出了相應(yīng)的沖突消解方案。沖突消解方案可以針對(duì)各種建模過程中產(chǎn)生的各種結(jié)構(gòu)沖突，給出消解方法，協(xié)助操作人員處理沖突。

創(chuàng)新點(diǎn):擴(kuò)展UML圖適用于描述大規(guī)模復(fù)雜應(yīng)用的業(yè)務(wù)過程模型，能檢測(cè)含有循環(huán)和重疊結(jié)構(gòu)的結(jié)構(gòu)沖突，并能指出沖突結(jié)構(gòu)類型，給出相應(yīng)沖突消解方案，協(xié)助處理沖突。

［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）.［周建濤，史美林，葉新銘.工作流過程建模中形式化驗(yàn)證技術(shù)［J］.計(jì)算機(jī)研究與發(fā)展，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］.計(jì)算機(jī)應(yīng)用研究，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）.［崔立真，王海洋.一種工作流模型正確性驗(yàn)證方法［J］.系統(tǒng)仿真學(xué)報(bào)，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）.［趙合計(jì)，張立春.UML活動(dòng)圖支持下的工作流建模方法與設(shè)計(jì)［J］.計(jì)算機(jī)應(yīng)用與軟件，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）.［劉怡，張子剛，張戡.工作流模型研究述評(píng)［J］.計(jì)算機(jī)工程與設(shè)計(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網(wǎng)化簡(jiǎn)技術(shù)的工作流過程模型結(jié)構(gòu)驗(yàn)證［J］.計(jì)算機(jī)技術(shù)與發(fā)展，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）.［凌鴻，周江波，胥正川.基于語義推理的工作流結(jié)構(gòu)驗(yàn)證方法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2006，12（6）:893－898.］