陳金棟，劉 偉，馮 新，劉 雷

（山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島266590）

隨著科學(xué)技術(shù)的發(fā)展，單一的流程往往不夠靈活，難以滿足人們的需求［1］，流程組合應(yīng)運(yùn)而生。流程組合體現(xiàn)在各個(gè)方面，例如因特網(wǎng)中雙主機(jī)的信息傳輸過程組合，電子商務(wù)中買賣雙方過程組合等［2］。流程組合可以協(xié)調(diào)多個(gè)目標(biāo)的操作過程，并使其各自完成自己的任務(wù)［3］。但是，流程組合中出現(xiàn)的死鎖是流程組合發(fā)展的障礙［4］。

Petri網(wǎng)是分布式系統(tǒng)的建模和分析工具。作為一種系統(tǒng)模型，Petri網(wǎng)既能描述系統(tǒng)的結(jié)構(gòu)，又能描述系統(tǒng)的動(dòng)態(tài)行為［5-8］。隨著Petri網(wǎng)的廣泛應(yīng)用，目前已經(jīng)提出邏輯Petri網(wǎng)［9］、時(shí)間Petri網(wǎng)［10］、顏色Petri網(wǎng)［11］和模糊Petri網(wǎng)［12］等擴(kuò)展形式。邏輯Petri網(wǎng)是抑止弧Petri網(wǎng)和高級(jí)Petri網(wǎng)的抽象與擴(kuò)展，其變遷的輸入、輸出受邏輯表達(dá)式的限制。與一般Petri網(wǎng)相比，邏輯Petri網(wǎng)能夠更好地描述實(shí)時(shí)協(xié)同工作系統(tǒng)模型的網(wǎng)結(jié)構(gòu)，便于系統(tǒng)設(shè)計(jì)人員掌握和使用［13］。

目前，基于Petri網(wǎng)的死鎖與組合研究已經(jīng)有了許多成果，但是較少使用邏輯Petri網(wǎng)來處理無死鎖組合的工作。文獻(xiàn)［14］使用了有色Petri網(wǎng)對(duì)服務(wù)組合系統(tǒng)行為進(jìn)行驗(yàn)證。文獻(xiàn)［15］提出了一種過渡控制方法，通過添加過渡來處理死鎖。文獻(xiàn)［16］展示了如何在消息位置的邊界處將并行程序的整個(gè)Petri網(wǎng)模型拆分為進(jìn)程網(wǎng)，以及如何將其用于死鎖分析。文獻(xiàn)［17］專注于防止資源不可靠的自動(dòng)化制造系統(tǒng)的死鎖。

本研究在相關(guān)研究的基礎(chǔ)上，借助邏輯工作流網(wǎng)，建模具有批處理和傳值不確定性的系統(tǒng)，提出了邏輯工作流網(wǎng)有限組合和狀態(tài)轉(zhuǎn)換圖的概念。用狀態(tài)轉(zhuǎn)換圖描述邏輯工作流網(wǎng)的活動(dòng)序列，并用來進(jìn)行組合，然后提出了狀態(tài)映射和狀態(tài)賦值用于判斷死鎖，之后提出了有限標(biāo)準(zhǔn)伙伴狀態(tài)轉(zhuǎn)換圖的概念與計(jì)算方法，以描述無死鎖組合允許的邏輯活動(dòng)序列。最后使用一個(gè)電子商務(wù)實(shí)例說明了使用有限規(guī)范伙伴狀態(tài)轉(zhuǎn)換圖判斷有限組合死鎖的方法。

1 基本概念

本部分介紹邏輯工作流網(wǎng)概念，定義狀態(tài)轉(zhuǎn)換圖以及從邏輯工作流網(wǎng)到狀態(tài)轉(zhuǎn)換圖的變換。

1.1 邏輯工作流網(wǎng)

定義1［18］（有限多重集） S 是一個(gè)集合，其上的多重集c是一個(gè)映射c∶S→N，記為c（s）。其中N表示一個(gè)自然數(shù)集合。C（S）表示集合S 上的所有多重集的集合。如果?s∈S，c（s）≤g，其中g(shù)∈N，那么所有c（s）組成的集合稱為g 限多重集，簡寫為Cg（S）。C0（S）表示一個(gè)空的多重集。

定義2［13］（邏輯工作流網(wǎng)） 一個(gè)六元組LWN=（P，T，F(xiàn)，I，O，M）稱為邏輯工作流網(wǎng)，當(dāng)且僅當(dāng)：

1）P 是一個(gè)有限庫所集，其中有兩個(gè)互不相交的庫所子集PC和PD，P=PC∪PD。PD為數(shù)據(jù)庫所子集，PC為控制庫所子集。PI∪PO=PD，其中PI 表示輸入庫所集，·PI∩PD=?；PO 表示輸出庫所集，PO·∩PD=?。

2）T=TC∪TI∪TO是一個(gè)有限變遷集，T∪P≠?，?t∈TI∪TO，·t∩t·=?，且P，TC，TI和TO兩兩互不相交，其中：①TC表示T 的普通變遷集；②TI表示T 的邏輯輸入變遷集，且?t∈TI，t的所有輸入庫所受一個(gè)邏輯輸入表達(dá)式fI的限制；③TO表示T 的邏輯輸出變遷集，且?t∈TO，t的所有輸出庫所受一個(gè)邏輯輸入表達(dá)式fO的限制。

3）F?（P×T）∪（T×P）是一個(gè)有限弧集。

4）I是一個(gè)邏輯限制輸入函數(shù)，使對(duì)?t∈TI，I（t）=fI是一個(gè)邏輯輸入表達(dá)式。

5）O 是一個(gè)邏輯限制輸出函數(shù)，使對(duì)?t∈TO，O（t）=fO是一個(gè)邏輯輸出表達(dá)式。

6）M∶P→N 是一個(gè)標(biāo)識(shí)函數(shù)，?p∈P，M（p）表示庫所p 中的托肯數(shù)，其中M0表示初始標(biāo)識(shí)且對(duì)?x∈PD，M0（x）=0。

7）LWN 具有以下的變遷發(fā)生規(guī)則：①?t∈TC，若對(duì)p∈·t，M（p）＞0，則變遷t可引發(fā)，變遷引發(fā)后產(chǎn)生一個(gè)新標(biāo)識(shí)M′，記做M［t＞M′。對(duì)p∈·t，M′（p）=0；對(duì)p∈t·，M′（p）=M（p）+1；對(duì)p∈·t∩t·：M′（p）=M（p）；②對(duì)t∈TI，若I（t）｜M=·T·，則邏輯輸入變遷t可引發(fā)，記做M［t＞M′，且對(duì)p∈·t：M′（p）=0；對(duì)p∈t·，M′（p）=1；對(duì)p?·t∪t·：M′（p）=M（p）；③對(duì)t∈TO，若對(duì)p∈·t，M（p）=0，則邏輯輸出變遷t可引發(fā)，且對(duì)p∈·t：M′（p）=0；對(duì)所有p∈·t，需滿足O（t）｜M′=·T·，記做M［t＞M′；對(duì)p?·t∪t·：M′（p）=M（p）。

圖1是一個(gè)簡單的邏輯工作流網(wǎng)例子，t1為邏輯輸入變遷，I（t1）=p1∧（p2∨p3）是t1的邏輯輸入函數(shù)，表示t1觸發(fā)條件是：p1中必須存在托肯，p2和p3中至少有一個(gè)存在托肯。t2為邏輯輸出變遷，I（t2）=p7∧（p6∨p5）是t2的邏輯輸出函數(shù)，表示t2引發(fā)后會(huì)有3種情況：①p7和p5中有托肯；②p7和p6中有托肯；③p7，p6和p5中都有托肯。

定義3（庫所變化集） 對(duì)于標(biāo)識(shí)M 到M'，數(shù)據(jù)庫所變化集L（M，M′）={x∈PD｜M（x）≠M(fèi)′（x）}。如果t·∩PD≠?，L（M，M′）是輸入庫所集；如果·t∩PD≠?，L（M，M′）是輸出庫所集。其中L（M，M′）=LI（M，M′）∪LO（M，M′），LI（M，M′）= {x∈L（M，M′）｜M（x）＞0}，LO（M，M′）={x∈L（M，M′）｜M′（x）＞0}。顯而易見，從標(biāo)識(shí)M 變化到標(biāo)識(shí)M'過程中，在數(shù)據(jù)庫所集LI（M，M′）中消耗了托肯，在數(shù)據(jù)庫所集LO（M，M′）產(chǎn)生了托肯。

圖1 一個(gè)簡單的邏輯工作流網(wǎng)Fig.1 A simple logical network

定義4（伙伴邏輯工作流網(wǎng)） 對(duì)于邏輯工作流網(wǎng)A 和B，A 和B 互為伙伴邏輯工作流網(wǎng)，當(dāng)且僅當(dāng)

1）PIA=POB，PIB=POA。

2）A 與B 所有其它成分是不相交的。

如果兩個(gè)LWN網(wǎng)互為伙伴邏輯工作流網(wǎng)，那么它們可以組合。組合主要包括合并接口位置。

定義5（邏輯工作流網(wǎng)的組合） 設(shè)A=（PA，TA，F(xiàn)A，IA，OA，MA）和B=（PB，TB，F(xiàn)B，IB，OB，MB）是伙伴LWN，A 與B 的組合為一個(gè)邏輯工作流網(wǎng)A?B=（PA?B，TA?B，F(xiàn)A?B，IA?B，OA?B，MA?B），其中PA?B=PA∪PB，TA?B=TA∪TB，F(xiàn)A?B=FA∪FB；IA?B=OA?B=?，MA?B=MA?MB；MA?B0=MA0?MB0；MA?MB：PA∪PB→N+；如果p∈PA，那么MA?B（p）=MA（p）；如果p∈PB，那么MA?B（p）=MB（p）。

如果存在g∈N，使得∑MA?B（x）≤g，其中x∈PD，MA?B可從標(biāo)識(shí)MA?B0經(jīng)過變遷序列到達(dá)，那么兩個(gè)邏輯工作流網(wǎng)的組合稱為g 限邏輯工作流網(wǎng)組合。

1.2 狀態(tài)轉(zhuǎn)換圖

本節(jié)定義狀態(tài)轉(zhuǎn)換圖用以模擬LWN網(wǎng)的運(yùn)行，找出所有的狀態(tài)，并將狀態(tài)與消息分離討論。

定義6（消息） PI∪PO 是消息接口庫所集，一個(gè)消息c為其上的多重集c∶PI∪PO→N，N表示一個(gè)自然數(shù)集合，記為c（s）。C（PI∪PO）表示集合PI∪PO 上的所有多重集的集合，表示為消息集。如果?s∈S，C（s）≤g，其中g(shù)∈N，那么此時(shí)C 稱為g 限消息集，記為Cg（S）。

定義7（狀態(tài)轉(zhuǎn)換圖） 狀態(tài)轉(zhuǎn)換圖為一個(gè)五元組STN=（S，E，OP，s0，Z，c），其中：

1）S 是一個(gè)有限狀態(tài)集，其中保存LWN中所有可能的狀態(tài)，在圖中表現(xiàn)為頂點(diǎn)集。

2）E 表示一組非確定性的狀態(tài)轉(zhuǎn)換關(guān)系，在圖中表現(xiàn)為弧集，E=S×OP×S。

3）OP=OPI∪OPO∪{τ}為有限消息集且OPI∩OPO=?，表示狀態(tài)轉(zhuǎn)換時(shí)消息的變化，OPI 中元素為狀態(tài)轉(zhuǎn)換時(shí)接收的多集，OPO 中元素為狀態(tài)轉(zhuǎn)換時(shí)發(fā)送的多集，特殊的元素{τ}，表示狀態(tài)轉(zhuǎn)換時(shí)既沒有產(chǎn)生也沒有消耗消息。OP 在圖中表現(xiàn)為弧上的標(biāo)記。

4）s0∈S，表示唯一的初始狀態(tài)。

5）Z?S，表示終止?fàn)顟B(tài)集。

如果狀態(tài)集S是有限的，那么狀態(tài)轉(zhuǎn)換圖STN 也是有限的。狀態(tài)轉(zhuǎn)換圖對(duì)一個(gè)全局消息c∈C（∪（OPI∪OPO））進(jìn)行操作，其中∪Y={x｜x∈y，y∈Y}。初始全局消息一般為空。

對(duì)于兩個(gè)狀態(tài)轉(zhuǎn)換圖STNA=（SA，EA，OPA，s0A，ZA）和STNB=（SB，EB，OPB，s0B，ZB），如果兩個(gè)狀態(tài)轉(zhuǎn)換圖滿足以下條件，那么兩個(gè)狀態(tài)轉(zhuǎn)換圖互為伙伴狀態(tài)轉(zhuǎn)換圖，簡稱為兩個(gè)伙伴狀態(tài)轉(zhuǎn)換圖。有

∪（OPIA∪OPOA）=∪（OPIB∪OPOB）。

與LWN 類似，兩個(gè)伙伴狀態(tài)轉(zhuǎn)換圖可以組合。

定義8（狀態(tài)轉(zhuǎn)換圖的組合） 對(duì)于兩個(gè)伙伴狀態(tài)轉(zhuǎn)換圖STNA=（SA，EA，OPA，s0A，ZA）與STNB=（SB，EB，OPB，s0B，ZB），其組合被定義為狀態(tài)轉(zhuǎn)換圖STNA?STNB=（SA?B，EA?B，OPA?B，s0A?B，ZA?B?，其中SA?B=SA×SB×C，OPA?B= {τ}，EA?B=SA?B（{τ}×SA?B，s0A?B=（s0A，s0B，?），ZA?B=ZA×ZB×?，狀態(tài)轉(zhuǎn)換關(guān)系EA?B包含以下元素：

（（sA，sB，c），τ，（s′A，sB，c））如果（sA，τ，s′A）∈EA，其中c?C（A 的內(nèi)部移動(dòng)）；

（（sA，sB，c），τ，（sA，sB，c））如果（sB，τ，s′B）∈EB，其中c?C（B 的內(nèi)部移動(dòng)）；

（（sA，sB，c），τ，（s′A，sB，c-x））如果（sA，x，s′A）∈EA，其中x∈OPIA，x?C 且c?C（A 接收一個(gè)消息）；

（（sA，sB，c），τ，（sA，s′B，c-x））如果（sB，x，s′B）∈EB，其中x∈OPIB，x?C 且c?C（B 接收一個(gè)消息）；

（（sA，sB，c），τ，（s′A，sB，c+x））如果（sA，x，s′A）∈EA，其中x∈OPOA，c?C 且c+x?C（A 發(fā)送一個(gè)消息）；

（（sA，sB，c），τ，（sA，s′B，c+x））如果（sB，x，s′B）∈EB，其中x∈OPOB，c?C 且c+x?C（B 發(fā)送一個(gè)消息）。

定義9（等待狀態(tài)） 對(duì)于狀態(tài)轉(zhuǎn)換圖A，狀態(tài)s是等待狀態(tài)當(dāng)且僅當(dāng)滿足?s′∈S，（s，x，s′）?E，其中x∈OPO∪{τ}，即s不能在沒有消耗消息下離開。對(duì)于等待狀態(tài)s，等待狀態(tài)集stop（s）={x∈OPI｜?s′∈S，（s，x，s′）∈E}。

定義10（死鎖） 狀態(tài)s為死鎖當(dāng)且僅當(dāng)s為等待狀態(tài)且s?Z 和stop（s）=?。

文中給出的任意邏輯工作流網(wǎng)用A 或者A 的無下標(biāo)表示，A 的伙伴邏輯工作流網(wǎng)用B 表示。A 的狀態(tài)轉(zhuǎn)換圖用STNA 表示，B 的狀態(tài)轉(zhuǎn)換圖用STNB 表示。STNB 一定為A 的伙伴狀態(tài)轉(zhuǎn)換圖。

STN 單次狀態(tài)轉(zhuǎn)換只能接收或者發(fā)送消息，不能同時(shí)接受和發(fā)送消息。因此，如果LWN 中有單個(gè)變遷同時(shí)消耗庫所集PI中的托肯和產(chǎn)生庫所集PO 中的托肯，需要將此變遷拆分為兩個(gè)新的變遷：只消耗PD中的托肯和只產(chǎn)生PD中的托肯。如果存在LI（M，M′）≠? 且LO（M，M′）≠?，其中M［t＞M′，那么變遷t需要拆分為t1和t2。拆分方法如下：

從P 中引入一個(gè)新的庫所p 和從T 中引入兩個(gè)新的變遷t1和t2。t1和t2需滿足{p}，·t2={p}，t2·=t·，且需要根據(jù)t的變遷類型添加條件。如果t∈TC，那么不用添加條件；如果t∈TI，那么I（t1）=I（t）；如果t∈TO，那么O（t2）=O（t）。t2引發(fā)的庫所后集變化與t相同，t1的庫所后集變化與t2的前集變化合理即可。將t1，t2，p 看為一個(gè)變遷的話，則與原來的t相同。

圖2（a）是一個(gè)需要拆分的邏輯工作流網(wǎng)，其中t1變遷發(fā)生需要從p3中消耗托肯和在p3中產(chǎn)生托肯。t1可以拆分為t2和t3，拆分后的LWN 如圖2（b）所示。如果圖2（b）中變遷引發(fā)產(chǎn)生的標(biāo)識(shí)變化可以表示為M1［t2＞M2［t3＞M3，那么對(duì)應(yīng)的圖1中標(biāo)識(shí)變化為M1［t2＞M3。顯而易見，t拆分后LWN 相對(duì)于t拆分前的LWN 多了一個(gè)中間標(biāo)識(shí)M2。

圖2 t拆分前后的LWNFig.2 LWN before and after t-splitting

算法1：STN 的生成

輸入：LWN=（P，T，F(xiàn)，I，O，M）

輸出：STN=（S，E，OP，s0，Z）

Step 0：s0=M0.在S 中新建一個(gè)狀態(tài)s0，并標(biāo)記為“新”

Step 1：While?s∈S 并且它的標(biāo)簽為“新”Do

從S 中任取一個(gè)標(biāo)簽為“新”的狀態(tài)，并命名為s

Step 2：對(duì)每一個(gè)t∈T IF M［t＞Do

Step 2.1：根據(jù)M［t＞M'，計(jì)算所有的M'

Step 2.2：對(duì)每一個(gè)M'Do

Step 2.2.1：IF M'?S Then

在S 中新建一個(gè)狀態(tài)s=M'

Step 2.2.2：在E 中新建一個(gè)轉(zhuǎn)換關(guān)系（M，L（M，M′），M′）

Step 2.2.3：IF L（M，M′）?OP Then

IF LI（M，M′）=L（M，M′）Then在OPI中新建一個(gè)消息LI（M，M'）

Else IF LI（M，M′）=L（M，M′）Then在OPO 中新建一個(gè)消息LO（M，M'）

Step 2.3：返回Step 2

Step 3：返回Step 1

該算法實(shí)現(xiàn)了從LWN到STN的映射。

2 狀態(tài)轉(zhuǎn)換圖組合研究

本部分將從伙伴邏輯狀態(tài)轉(zhuǎn)換圖的角度理解兩個(gè)狀態(tài)轉(zhuǎn)換圖的組合。首先引入組合狀態(tài)的概念，這些概念允許僅通過考慮伙伴狀態(tài)轉(zhuǎn)換圖來表示組合邏輯工作流網(wǎng)的死鎖。隨后定義狀態(tài)映射與狀態(tài)賦值。

定義11（組合狀態(tài)） 對(duì)于STNA=（S，E，OP，s0，Z），組合狀態(tài)是一個(gè)二元組（s，c），其中s是STNA 中的一個(gè)狀態(tài)，c是一個(gè)消息。

定義12（g 限死鎖） （s，c）是g 限死鎖當(dāng)且僅當(dāng)滿足stop（s）=?和｜c(diǎn)｜=g。

定義13（可達(dá)狀態(tài)集） 對(duì)于組合狀態(tài)（s，c），將（s，c）的可達(dá)狀態(tài)集表示為R（s，c），其歸納定義為：

基礎(chǔ)：（s，c）∈R（s，c）

步驟：如果（s，c）∈R（s，c）且?s′∈S，（s，x，s′）∈E，那么

如果x=τ，（s′，c）∈R（s，c）；或者

如果x∈OPO 且｜c(diǎn)｜-｜x｜＜g，（s′，c（x））∈R（s，c）；或者

如果x∈OPI且x?c，（s′，c（x））∈R（s，c）。

定義14（單步可達(dá)狀態(tài)集） 對(duì)于組合狀態(tài)集SS= {（s，c）｜s∈S，c∈C}，將SS 的單點(diǎn)可達(dá)狀態(tài)集表示為R（SS），其歸納定義如下：

基礎(chǔ)：SS∈R（SS）

步驟：如果（s，c）∈R（SS）且?s′∈S，（s，x，s′）∈E，那么

如果x=τ，（s′，c）∈R（SS）；或者

如果x∈OPO 且｜c(diǎn)｜-｜x｜＜g，（s′，c（x））∈R（SS）；或者

如果x∈OPI且x?c，（s′，c-x））∈R（SS）。

定義15（狀態(tài)單步可達(dá)狀態(tài)集） 對(duì)于組合狀態(tài)（s，c），R（（s，c），x）為狀態(tài)單步可達(dá)狀態(tài)集，其定義為：

如果x=τ，R（（s，c），x）=R（s，c）；或者

如果x∈OPO 且（s，c+x）不是g 限死鎖，R（（s，c），x）=R（s，c+x）；或者

如果x（OPI且x?c，R（（s，c），x）=R（s，c-x）。

定義16（狀態(tài)集單步可達(dá)狀態(tài)集） 對(duì)于組合狀態(tài)集SS={（s，c）｜s∈S，c∈C}，R（（s，c），x）為其狀態(tài)集單步可達(dá)狀態(tài)集，其定義為：

如果x=τ，R（SS，x）={y∈R（s，c）｜（s，c）∈SS}；或者

如果x∈OPO，R（SS，x）={y∈R（s，c+x）｜（s，c）∈SS}；或者

如果x∈OPI且x?c，R（SS，x）= {y∈R（s，c-x）｜（s，c）∈SS}。

定義17（狀態(tài)映射） 對(duì)于STNA 和STNB，K：SB→2x，x=SA×C 為從STNB 到STNA 的狀態(tài)映射，K（sB）={（sA，c）｜（sA，sB，c）能夠從A 和B 的組合狀態(tài)轉(zhuǎn)換圖STNA?STNB 中可達(dá)}。

定義18（動(dòng)態(tài)和靜態(tài)） 組合狀態(tài)（s，c）是動(dòng)態(tài)當(dāng)且僅當(dāng)存在s′∈S 使得（s，x，s′）∈E 成立，其中

如果x=τ且（s′，c）∈R（s，c）；或者

如果x∈OPO 且（s′，c+x）∈R（s，c），或者

如果x∈OPI∧x?c且（s′，c（x）∈R（s，c），

否則（s，c）是靜態(tài)。

僅從STNB 的角度來看，死鎖定義如下：

（sA，sB，c）是組合狀態(tài)轉(zhuǎn)換圖A?B 并且滿足以下條件：

sA?ZA，或sB?ZB，或者c≠?；

SB是B 的停止?fàn)顟B(tài)并且x?stop（sB）∧x?c；

且（sA，c）是一個(gè)靜態(tài)。

定義19（狀態(tài)賦值） 對(duì)于組合STNA?STNB 中STNB 的狀態(tài)sB，死鎖的三個(gè)定義可以使用邏輯表達(dá)式來表示，稱為sB的狀態(tài)賦值，表示為live（sB），其定義如下：

live（sB）=final∨output∨input，其中：

final是真需滿足sA∈ZA且c=?，否則final是假賦值；

output是真需滿足?（sA，x，s′A）∈EA，其中s′A∈SA且x∈stop（sB），否則output是假賦值；

input是真對(duì)每個(gè)x∈stop（sA），需滿足?（sB，x，s′B）∈EBi，其中s′B∈SB，否則input是假賦值。

?sB∈SB，（sA，c）是K（sB）中的一個(gè)靜態(tài)。

其中，live（sB）表達(dá)式為sB對(duì)應(yīng)組合狀態(tài)集K（sB）中靜態(tài)（sA，c）的條件final∨output∨input的合取式；final表示sA是否是最終狀態(tài)；input和output分別表示STNA 和STNB 可以進(jìn)行信息接收。

當(dāng)且僅當(dāng)庫所B 中狀態(tài)SB，所有狀態(tài)賦值中的live（sB）的值為真時(shí)，STNA?STNB 是無死鎖的。

3 伙伴狀態(tài)轉(zhuǎn)換圖生成

本節(jié)根據(jù)一個(gè)邏輯工作流網(wǎng)計(jì)算其伙伴狀態(tài)轉(zhuǎn)換圖。由于這個(gè)伙伴轉(zhuǎn)換圖可以表示伙伴邏輯工作流網(wǎng)的無死鎖邏輯序列，將其稱為規(guī)范伙伴轉(zhuǎn)換圖。

定義20（規(guī)范伙伴轉(zhuǎn)換圖）SPN

對(duì)于LWN=（P，T，F(xiàn)，I，O，M），其伙伴轉(zhuǎn)換圖SPN=（S，E，OP，s0，Z）遞歸定義如下

步驟0：SPN0=（S0，E0，OP0，s00，Z0）其中S0={x∈2y，y=S×（OPI∪OPO）｜x=R（x）}；E0={（s，x，s′）｜s∈S0，x∈OP，s′∈S0，s′=R（s，x）}；OP0=OPI0∪OPO0∪{τ}，其中OPI0=OP0且OPO0=OPI；s00=R （s0，?）且s0=M0；Z0={（x，?）｜x∈Z，（x，?）∈S0}。

步驟i：SPNi=（Si，Ei，OPi，s0i，Zi）。

步驟i+1：SPNi+1=（Si+1，Ei+1，OPi+1，s0i+1，Zi+1），其中Si+1={s∈Si｜?x∈s，live（x）=true}；Ei+1={（s，x，s′）｜s，s′∈Si+1，x∈OP，s′=R（s，x）}；OPi+1=OPI0∪OPO0∪{τ}，OPIi+1=OPO，OPOi+1=OPI；s0i+1=R （s0，?）；Zi+1={（x，?）｜x∈Z，（x，?）∈Si+1}；

直到SPNi+1=SPNior s0i+1?Si+1。

對(duì)于最小的i+1，使SPN 等于SPNi+1。如果s0i+1?Si+1，那么SPN 不存在，說明這個(gè)邏輯工作流網(wǎng)沒有無死鎖伙伴邏輯工作流網(wǎng)。在計(jì)算SPN 時(shí)，SP 的所有狀態(tài)live（s）的值都為真（不為真的被刪除），根據(jù)死鎖的定義得出，SPN 描述了組合時(shí)伙伴邏輯工作流網(wǎng)的無死鎖活動(dòng)序列。在計(jì)算消息集C時(shí)，由于C 是一個(gè)無限集合，無法全部計(jì)算出來。所以引入一個(gè)常數(shù)g，用g 限消息集Cg代替無限大的集合C，此時(shí)規(guī)范伙伴轉(zhuǎn)換圖稱為g 限規(guī)范伙伴狀態(tài)轉(zhuǎn)換圖，記為SPNg。g 限規(guī)范伙伴狀態(tài)轉(zhuǎn)換圖的生成算法如下。

算法2：SPNg的計(jì)算

輸入：LWN=（P，T，F(xiàn)，I，O，M）

輸出：SPN=（S，E，OP，s0，Z）

Step 0：s0=R（s0，?），從S 中引入一個(gè)新的組合狀態(tài)s0，并標(biāo)記為“新”；

Step 1：While?s∈S 并且標(biāo)識(shí)是“新”Do

從S中任取一個(gè)標(biāo)識(shí)為“新”的狀態(tài)，并將其賦值給s

Step 1.1：對(duì)于每個(gè)op∈OP，Do

Step 1.1.1：計(jì)算R（s，op）

Step 1.1.2：IF R（s，op）=?Then返回Step 1.1

Step 1.1.3：IF R（s，op）?S Then

從S中引入一個(gè)新的狀態(tài)R（s，op）并標(biāo)記為“新”

Step 1.1.4：從E 中引入一個(gè)新的狀態(tài)轉(zhuǎn)換關(guān)系（s，op，R（s，op））

Step 1.2：返回Step1

Step 2：對(duì)于每個(gè)s∈S Do

IF?（s，op，s′）?E 對(duì)所有op∈OP 成立，其中s′∈S 和s≠s0 Then標(biāo)記S為“死鎖”

Step 3：While?s∈S 且它的標(biāo)簽是“死鎖”Do

Step 3.1：對(duì)于每個(gè)s Do

IF標(biāo)識(shí)是“死鎖”Then從S 中移除s

Step 3.2：對(duì)于每個(gè)（s，op，s′）∈S Do

IF s?S 或s′?S Then從E 中移除（s，op，s'）

Step 3.3： 對(duì)于每個(gè)s∈S Do

IF?（s，op，s′）?E 對(duì)所有op∈OP 成立，其中s′∈S 和s≠s0，Then標(biāo)記s為“死鎖”

Step 3.4： 返回Step 3

對(duì)于計(jì)算出的g 限規(guī)范伙伴轉(zhuǎn)換圖，一般是進(jìn)行死鎖預(yù)判。在不進(jìn)行組合前，判斷伙伴邏輯工作流網(wǎng)與本邏輯工作流網(wǎng)的組合后會(huì)不會(huì)出現(xiàn)死鎖。下面將給出一個(gè)簡單的實(shí)例進(jìn)行說明。

圖3是一個(gè)邏輯工作流網(wǎng)，表示兩位用戶分別購買兩件不同的商品。其中，p1和p2分別表示兩位用戶對(duì)商品購買確認(rèn)，p3和p4表示商品付款，p5和p6表示商品，p1和p2表示商品的退款；t1表示接收訂單，I（t1）=p9∧（p1∨p2）；t2表示確認(rèn)付款，I（t2）=p10∧（p13∨p14）；t3表示處理結(jié)果，O（t3）=p12∧（（（p7⊕p5）⊕p1）∨（（p8⊕p6）⊕p2））），且O（t2）≠p12∧p1∧p2。⊕表示異或操作。

根據(jù)算法1，其狀態(tài)轉(zhuǎn)換圖如圖3所示。其中初始狀態(tài)為s0；初始全局消息為空；使用操作-x 表示從全局消息中接收消息；操作+y 表示往全局消息中發(fā)送消息；多集符號(hào)被簡寫，比如-［p1］，簡寫為p1，表示從全局消息中接收消息［p1］。

根據(jù)算法2，其2限規(guī)范伙伴轉(zhuǎn)換圖如圖3所示。其中，不同狀態(tài)都用數(shù)字來區(qū)分，0表示初始狀態(tài)。

對(duì)于g 限規(guī)范伙伴轉(zhuǎn)換圖，簡略分析其算法時(shí)間復(fù)雜度。組合狀態(tài)的數(shù)目最多為x×yg，其中x=｜S｜，y=｜∪（OPI∪OPO）｜，組合狀態(tài)集的數(shù)目與組合狀態(tài)大約呈正相關(guān)，所以可以認(rèn)為算法的時(shí)間復(fù)雜度與組合狀態(tài)數(shù)目呈正相關(guān)。可以看出，如果狀態(tài)轉(zhuǎn)換圖狀態(tài)過多或者g 過大，算法計(jì)算時(shí)間將會(huì)很大。

對(duì)于上面的網(wǎng)上購物系統(tǒng)和它的2限規(guī)范伙伴轉(zhuǎn)換圖，分別用A 和SPNA2表示。圖5（a）是A 的伙伴邏輯工作流網(wǎng)，用B 表示。其中I（t7）=p5⊕p7。圖5（b）是B 的狀態(tài)轉(zhuǎn)換圖，用STNB 表示。使用SPNA2來預(yù)測2限組合邏輯工作流網(wǎng)A?B 有無死鎖。判斷過程如下。

STNB 沒有孤立狀態(tài)，說明STNB 本身不存在死鎖。然后將STNB 對(duì)應(yīng)到SPNA2上，s0對(duì)應(yīng)狀態(tài)0，s1對(duì)應(yīng)狀態(tài)1，s2對(duì)應(yīng)狀態(tài)8，并且所有對(duì)應(yīng)的兩個(gè)狀態(tài)，其消耗信息一致。因此，邏輯工作流網(wǎng)A 與B的2限組合沒有死鎖。

4 總結(jié)

圖3 一個(gè)簡易網(wǎng)上購物系統(tǒng)Fig.3 A simple online shopping system

圖4 實(shí)例的狀態(tài)轉(zhuǎn)換圖Fig.4 State transition diagram

圖5 2限規(guī)范伙伴轉(zhuǎn)換圖Fig.5 2-limit standard canonical partner transition diagram

本研究使用邏輯工作流網(wǎng)建模相關(guān)系統(tǒng)，使用邏輯變遷替代普通變遷，簡化了普通petri網(wǎng)的結(jié)構(gòu)，可建模具有批處理和傳值不確定的系統(tǒng)。最終得到一個(gè)邏輯工作流網(wǎng)的g 限標(biāo)準(zhǔn)伙伴狀態(tài)轉(zhuǎn)換圖，此狀態(tài)轉(zhuǎn)換圖描述了伙伴邏輯工作流網(wǎng)的無死鎖邏輯活動(dòng)序列。只要是能被g限標(biāo)準(zhǔn)伙伴狀態(tài)轉(zhuǎn)換圖完全描述的伙伴邏輯工作流網(wǎng)，組合后不會(huì)出現(xiàn)死鎖。根據(jù)死鎖的充分條件，提出狀態(tài)映射用以判斷兩個(gè)工作流網(wǎng)組合后出現(xiàn)的死鎖。通過刪除進(jìn)入死鎖的邏輯活動(dòng)序列，計(jì)算出可與其無死鎖組合的伙伴狀態(tài)轉(zhuǎn)換圖。由于伙伴邏輯工作流網(wǎng)的無死鎖邏輯活動(dòng)過多，導(dǎo)致伙伴狀態(tài)轉(zhuǎn)換圖狀態(tài)過多。即使是簡單的系統(tǒng)，如果g 的取值過大，其伙伴狀態(tài)轉(zhuǎn)換圖的狀態(tài)也會(huì)特別多。因此，本方法不適用于太過巨大的系統(tǒng)。

圖6 A的一個(gè)伙伴邏輯工作流網(wǎng)及其狀態(tài)轉(zhuǎn)換圖Fig.6 A partner logical workflow net of A and its state transition graph