基于面向對象Petri-net的LWF建模方法

鄭學恩, 許承東, 范國超, 趙 靖

(北京理工大學宇航學院, 北京 100081)

0 引 言

在20世紀90年代,事件流程管理成為計算機行業研究的熱點之一。在軟件工程鄰域中,工作流管理系統的建立,使事件流程管理和程序自動化運行成為可能[1-2]。比較成功的工作流管理系統應用實例是荷蘭國家稅務局的Sagitta2000申報處理系統[3]。此項目在設計中將應用軟件與事件邏輯成功分離,單獨設計了工作流系統,以解決海關申報流程難以描述的問題。此后,研究人員針對工作流的死鎖、活鎖及合理性[4]進行了諸多改進,文獻[5]提出工作流化簡規則,來避免工作流出現死鎖狀態;文獻[6]在工作流中加入時間特性,拒絕使用環形流程,以避免工作流出現活鎖狀態;文獻[7-8]對工作流進行分塊設計和分層設計,提高工作流的容錯性和執行效率;文獻[9]提出循環工作流優化方法,該方法改變原有工作流的結構,盡量減少環形工作流(loop workflow,LWF),避免因LWF造成的活鎖。但諸如上述方法,其根本都是減少LWF的使用,以提高工作流程的安全性。

彈箭產品設計是典型的復雜系統工程,它由若干子系統組成,子系統之間存在著通信、繼承、調用關系。每個子系統設計完成后,需要將方案匯總,進行方案評審。由于產品設計過程復雜,通常要經過3～5次的迭代設計，產品的各項性能才能滿足技術指標。彈箭產品設計工作流程是事件迭代的過程,描述設計流程的工作流需要使用環形結構。通常情況下,基于公平性假設的環形結構是安全的,但產品設計工作流中,基于“評審”結果的任務選擇已經不再滿足公平性假設,這樣的工作流程增加了模型陷入活鎖狀態的風險,為了避免設計工作流進入活鎖狀態,有必要設計一種擴展工作流網(expanded workflow network, EWF-net),對彈箭產品設計工作流程進行正確建模。

針對設計工作流的活鎖問題,本文提出了基于面向對象Petri網(object-oriented petri-net, OPN)的EWF-net,它具有躍遷和虛擬托肯(虛托)2個重要標志。躍遷和虛托的聯合使用,能夠使陷入活鎖的LWF跳出環形結構,從而避免了活鎖的發生。為了正確表達工作流中虛托的狀態,本文給出了描述虛托的標識方法,并對線性代數的可達性分析方法進行了擴展,使其能夠對擁有虛托的工作流進行可達性分析。最后,以彈箭設計工作為背景,分別用傳統工作流網 (workflow network, WF-net) 和EWF-net 2種方法對彈箭設計工作流進行建模,在活鎖狀態下對2個模型進行了可達性分析,分析的結果表明本文所提的EWF-net方法能夠避免活鎖,解決因非公平性假導致的活鎖問題。

1 基礎知識

1.1 OPN

Petri網反映事物之間的依賴關系,是一種描述事件分步、并發和異步的圖形工具[10]。為了描述復雜系統工程中子系統之間的關系,面向對象技術與Petri-Net相結合[11-13],擴展成為OPN。它具有繼承性。子類網可以通過繼承,對父類網進行調用。這種繼承性的應用,一定程度上避免Petri網出現狀態空間爆炸的情況。

定義1OPN定義。N=(O,T;F,M)的四元組構成了網結構,其中:

(1)O={O1,O2,…Oi}是對象的有限集,對象用來描述系統的狀態,i>0為對象的個數。

(2)T={T1,T2,…,Tn}是變遷的有限集,變遷用來描述系統的行為,n>0為變遷的個數。

(3)F代表對象與變遷之間的關系,F?O×T∪T×O。

(4)M0是網系統的初始狀態標識。

定義2繼承性定義。對象O1繼承于對象O2的充分必要條件是:

(1)O1≠O2∧O1∈R(O)∧O2∈R(O),R(O)表示對象的全體集。繼承關系的2個對象都屬于全體類集,且對象O1不能自我繼承。

(2) ?O1,?O1?O2?…?Ox,L(O1)={O2,O3,…,Ox},O1?L(O1)。L(O1)表示對象O1的父類集。對象O1不能通過連續的繼承,成為自身的父類。

圖1描述O1與O2的繼承關系及O2調用O1的過程。對象O2繼承于對象O1,表示為在對象O2中可以通過托肯調用對象O1。

圖1 對象的繼承Fig.1 Inheritance of objects

1.2 工作流網

工作流描述了工作流程的邏輯關系。使用Petri網這種過程形式化體系對工作流建模和分析,避免工作流出現模糊性、不確定性和矛盾性。Aalst提出的工作流網是建立在Petri網的基礎上的。

定義3WF-net定義。傳統Petri網被稱為WF-net的充要條件是:

(1) 存在一個源庫所Pi∈P,使得·Pi=?;

(2) 存在一個終止庫所Po∈P,使得Po·∈?;

(3) 每個節點x∈P∪T都位于從Pi到Po的路徑上。

在基于OPN的WF-net中,條件對應Petri網中的對象,任務對應Petri網中的變遷。

2 EWF-net

2.1 非公平性LWF

定義4LWF定義。在工作流中,如果某個任務被反復執行,直到滿足其后面的“要求”結果為止,稱為LWF。

在工作流網中,LWF的安全性建立在公平性假設的基礎上。公平性假設認為如果一個任務有可能被執行,就不會無限期地推遲[14]。LWF只在原則上可能無限地循環,因為一個任務有可能被執行,就不會讓這個任務永遠地“饑餓”。但在設計工作中,如果設計結果無法滿足設計指標,LWF不可能在不滿足設計指標的情況下,提交設計結果,因此設計工作流模型有可能陷入活鎖,無法進行下一步設計。為了解決上述問題,下面給出EWF-net的定義。

2.2 EWF-net的定義

定義5EWF-net定義。EN=(P,T,O;F,OI,OO,TI,TO,W,M)稱為EWF-net的充分必要條件是:

(1)P≠Φ,T≠Φ,T∩P=Φ,F=P×T∪T×P∪T×O∪O×T,其中P表示條件,T表示任務,O表示對象,F表示他們之間的關系,其中P、T和O都是有限集。

(2) OI表示對象的源節點,OO表示對象的匯節點,·OI≠?,OO·≠?。

(3) TI表示任務輸入,TO表示任務輸出。

(4)W:F→N,W為權函數,將關系F映射到一個自然數。

(5)M是網的標識,M0為初始標識。

(6) 存在一個源節點Pi∈P,使得·Pi=?;

(7) 存在一個匯節點Po∈P,使得Po·=?;

(8) 每個節點a∈P∪T,都位于從Pi到Po的路徑上,沒有孤立節點。

基于OPN和WF-net的EWF-net,具有繼承性和描述工作流的能力,適合用于復雜系統的工作流建模。為了解決LWF的活鎖問題,EWF-net引入了躍遷的狀態轉移規則。

2.3 躍遷的定義

定義6躍遷定義。在EWF-net中,如果任務輸出TO具有計數能力,且計數的上限值為n,且n∈N,則稱該TO為躍遷,記為TOn,計數的上限值n為迭代數。

當標記了躍遷的任務T被執行一次,條件TOn·增加一個虛托用來記錄任務T被執行的次數,當T的執行次數等于迭代數n時,TOn被執行,結束LWF程。每個任務中只能存在一個躍遷,原則上如果任務序列足夠長,躍遷一定會被執行。圖2描述了EWF-net的躍遷。

圖2 EWF-net躍遷示意圖Fig.2 Schematic diagram of EWF-net jump-turning

2.4 虛托的定義

定義7虛托定義。在EWF-net中,當標記了躍遷的任務被執行一次后,沒有得到托肯的條件P(即TOn·)將得到一個虛托,用符號“○”表示。在標識中表示為M(P)=1/n,n∈N,P∈P。標識中自然數n表示生成虛托的上限值。

虛托具有以下2點性質:

(1) 虛托不代表資源;

(2) 虛托不能觸發任務。

定理1虛托觸發定理。n∈N,虛托在標識中表示為M(P)=1/n,則?P∈·T,任務T觸發的充要條件是條件P的虛托數m等于虛托上限值n。

證明(必要性):假設m為條件P獲得的虛托數,?m∈N。當庫所獲得m個虛托后,根據定義6可知,M(P)=1/n1+1/n2+…+1/nm,當m=n時,M(P)=1,即M[T>。

(充分性):假設變遷T被觸發時的狀態標識M(P)=1,式中P∈·T。根據定義6可知,M(P)=1/n1+1/n2+…+1/nm,且M(P)=1,能夠推導出m=n,即虛托數m等于迭代次數n。

證畢

圖3描述了躍遷和虛托跳出活鎖的工作流程。如圖3(a)所示,條件P1觸發任務T1執行,經過任務T1的選擇,托肯經由任務輸出TO1回到條件P1,P1再次觸發任務T1,當任務T1無法選擇TO2時,模型將不斷重復由任務輸出TO1到條件P1的流程。無限循環的任務流程為σ=TO1…TO1…。在圖3(b)中,使用躍遷TO13取代TO2,每次T1執行后,躍遷指定的條件P2會得到一個虛托。圖3(b)和圖3(c)給出了虛擬托肯的狀態標識。當P2得到的虛托個數達到迭代數3時,托肯將會通過躍遷TO13到達P2。如圖3(d)所示,此時活鎖狀態結束,LWF運行了3次。

2.5 EWF-net可達性分析方法

傳統可達性分析方法,無法描述虛托的狀態標識。為了描述WF-net存在虛托時的狀態,需要構建適用于EWF-net的關聯矩陣和狀態方程。

圖3 LWF中虛托的狀態標識圖Fig.3 State identification of virtual-token in LWF

稱A為EN的關聯矩陣。

給出EWF-net系統的狀態方程，即

M=M0+A×U+B

式中,U為發生數向量;B為虛托狀態標識。U中一個位置的值對應網模型中的一個任務(或對象O)在變遷序列中出現的次數。如果任務有躍遷,在向量U中會有2個位置分別對應該任務的輸出量和躍遷。B=B1+B2+…+Bm-k是描述虛托狀態標識的方程,由m-k個向量組成,每個向量對應一個躍遷。Bi的維度與M相同,每個位置對應一個條件，或者對象O的源節點和匯節點。向量B的構建方法如下:

準備將模型中的躍遷添加到向量組C中,C中含有組元m-k個,每個組元用C[i]表示,i的初始值為1。

步驟1與C[i]同屬一個任務T的任務輸出記為Vi;

步驟2在任務序列σ(有限序列)中,逆序查找C[i]。

步驟3當第1次查找到C[i]后,計算從此位置到任務序列結束這一段中,Vi出現的次數,記為yi。如果序列中沒有出現C[i],那么計算整個序列σ中Vi出現的次數,同樣記為yi。

步驟4在向量Bi中,C[i]·所對應的條件位置的值設為yi/mi,其他位置設為0,式中mi對應躍遷C[i]的迭代數。

步驟5如果i=m-k,完成向量B構建,否則i=i++,返回步驟1。

根據工作流的任務序列,建立模型的狀態方程用于計算工作流的可達狀態。通常情況下,模型的可達性分析按以下步驟進行[15]:

步驟1構建關聯矩陣;

步驟2給出工作流的任務序列;

步驟3構建狀態方程;

步驟4工作流可達性計算。

用于網模型可達性分析的任務序列應該具有普遍性,它需要滿足以下要求:

(1) 任務序列應該由源節點Pi開始,以匯節點Po結束;

(2) 在任務序列中網中每個任務都至少被執行一次,確保網中沒有不起作用的任務。

躍遷和虛托的引入,為解決LWF活鎖問題提供一種新方法。下面以彈箭設計工作流程為例,分別利用WF-net和EWF-net兩種方法為彈箭設計建立工作流模型,并進行可達性對比分析。

3 彈箭設計工作流建模及分析

彈箭產品設計工作是權衡和迭代的過程。產品的設計

流程復雜,需要清晰的工作流程圖描述設計工作的邏輯關系。在工程中,通常以單向網絡流圖描述產品的研發周期。這種方法適用于描述設計工作的時間節點,并不適合描述工作之間的邏輯關系,也無法與軟件結合,應用在彈箭設計平臺中。在軟件程序設計中,EWF-net建立的工作流模型描述工作事件的邏輯關系更清晰、更嚴謹,也更適合與應用程序和數據庫之間進行交互通信,將物理進程與計算機程序連接[16]。

3.1 彈箭數字化設計平臺

彈箭數字化設計平臺集成多種設計資源,是彈箭產品建模及分析的設計軟件。它將彈箭產品設計工作劃分為4個子模塊,子模塊之間是相互聯系與制約的關系。彈箭設計工作流作為設計工作調度的核心,描述各子系統之間的數據交互流程,將設計流程的邏輯關系可視化。在彈箭數字化設計平臺中,工作流是產品數字化設計工作能夠順利進行的保障[17]。系統在調度數據時,將按照工作流的邏輯關系進行。

圖4描述了彈箭數字化設計平臺的總體結構:資源層、通信層、功能層和服務層。功能層包括工作流系統、應用程序系統和數據庫系統,是實現設計平臺主要功能的核心層。在功能層內部,工作流系統、應用程序系統與數據庫系統之間互相通信,形成環狀結構。工作流系統主要的功能是管理工作流模型,安排產品設計工作的邏輯關系;數據庫系統負責存儲和管理工作流系統與應用程序系統產生的數據;應用程序系統負責定義算法模塊,根據工作流系統建立的邏輯關系,處理任務。3個系統的聯合運行實現彈箭設計工作流程化和自動化。

圖4 彈箭數字化設計平臺結構圖Fig.4 Structure map of the missile digital design platform

3.2 彈箭設計工作流建模及可達性分析

在方案階段設計中,設計平臺將彈箭產品設計工作劃分為彈體模塊、戰斗部模塊、動力模塊和控制模塊。圖5展示了利用WF-net建立的工作流模型,它使用OR-split結構對評審事件進行建模。當設計結果沒有達到設計指標時,工作流將進行下一次的迭代設計;當設計結果滿足設計指標后,工作流將結束設計工作。圖6展示了利用EWF-net建立的工作流模型,它使用躍遷對評審事件進行建模。

圖5 基于WF-net的彈箭產品設計工作流模型Fig.5 Workflow model for missile design based on WF-net

圖6 基于EWF-net的彈箭產品設計工作流模型Fig.6 Workflow model for missile design based on EWF-net

表1分別介紹了2個模型中變遷所對應的工作事件。

表1 工作流中任務對應的工程事件

以圖5的工作流模型為例,當狀態M0(Pi)=1時,工作流系統開始運行,首先任務T1被觸發,下達研制任務。當節點OI1得到托肯后,O1運行,完成彈箭總體的設計工作。O1結束后將托肯傳遞給匯節點OO1。?M∈R(M0),M(OO1)≥1→M[T2>,任務T2將托肯傳遞給條件P1和源節點OI2,OI3和OI4。條件P1表示彈體系統設計已經完成,等待反饋迭代被觸發。另外3個模塊O2、O3、O4的源節點得到托肯后,將分別觸發各自的模塊進入工作狀態。?M∈R(M0),M(OO2)≥1→M[T3>,任務T3將托肯傳遞給條件P1,戰斗部系統設計工作完成,等待反饋迭代被觸發。T4、T5具有相同的作用,當動力系統和控制系統被設計完成后,托肯將進入條件P1,等待進行彈箭迭代設計被執行。條件P1得到4個系統反饋的托肯后,根據評審結果觸發T6或T7中的一個,選擇的依據是設計結果能否滿足設計指標。這種選擇依據不再滿足公平性假設,增加了工作流陷入活鎖風險。如果設計指標一直沒有達到,工作流將進入活鎖狀態。利用線性代數的方法對圖5的工作流模型進行可達性分析。首先,建立工作流的關聯矩陣為

AWF-net=

給出活鎖狀態的任務序列，即

式中,n∈∞;σWF-net是變遷的多重集。UWF-net是σWF-net的重數,即

給出系統初始狀態為

應用狀態方程，即

M=M0+AWF-net×UWF-net

求解彈箭產品設計工作流的終止狀態為

結果表明托肯無法達到Po,工作流處在活鎖狀態,彈箭數字化設計平臺不能為用戶輸出一個設計結果。

利用EWF-net建立的彈箭設計工作流模型如圖6所示,任務T6的輸出TO6表示設計結果沒有滿足設計指標,需要開始下一輪迭代設計;TO63表示設計結果滿足研制任務要求,通過評審,托肯傳遞給匯節點Po。引入躍遷后,任務T6被執行的次數達到迭代數3的上限時,將會觸發躍遷TO63,結束設計工作。他的工程意義表現為現有的設計手段和方法,無法滿足預定的技術指標。假設設計結果一直無法滿足設計指標,根據虛托觸發定理得到的任務序列為

σEWF-net=T1,O1,T2,O2,T3,O3,T4,O4,T5,TO6,

O1,T2,O2,T3,O3,T4,O4,T5,TO6,O1,T2,

O2,T3,O3,T4,O4,T5,TO63

根據圖6的工作流模型建立關聯矩陣為

AEWF-net=

T1T2T3T4T5TO6TO63O1O2O3O4

根據給出的任務序列求得σEWF-net的重數，即

給出系統初始狀態為

計算標識虛托的狀態向量為

應用狀態方程，即

M=M0+AEWF-net×UEWF-net+B

求解彈箭產品設計工作流系統的終止狀態為

狀態方程的計算結果表明，利用EWF-net構建的彈箭產品設計工作流能夠避免活鎖,使匯節點Po具有可達性,在任務序列結束后,除Po外其他條件中沒有托肯。這個結果表明系統描述的工作流可以正常運行。

4 結 論

產品設計自動化一直是科研設計部門提高設計能力的一個發展方向。彈箭設計平臺集成了知識、經驗和方法等設計要素,利用工作流模型實現產品設計任務的自動調度。工作流模型是設計自動化的核心部分，對設計工作流的安全性提出高標準的需求。本文為解決設計工作流模型的活鎖問題,提出了EWF-net建模方法,該方法依靠躍遷和虛托的狀態轉移規則,避免WF-net陷入活鎖狀態。在彈箭設計工作流建模實例中,將傳統WF-net方法和EWF-net方法進行了對比分析,結果表明EWF-net方法能夠使匯節點可達。

參考文獻：

[1] MAYER B, KILLIAN M, KOZEK M. Modeling workflow for a building model for control purposes[C]∥Proc.of the IEEE International Conference on Systems and Control,2013:551-556.

[2] WINKLER D, SCHOENBAUER M, BIFFL S. Towards automated process and workflow management: a feasibility study on tool-supported and automated engineering process modeling approaches[C]∥Proc.of the 40th Euromicro Conference on Software Engineering and Advanced Applications, 2014: 102-110.

[3] VAN DER AALST W, VAN HEE K. Workflow management models,methods,and systems[M].London:MIT Press,2002.

[4] YAMAGUCHI S, WU H. Protocol inheritance preserving soundizability problem and its polynomial time procedure for acyclic free choice workflow nets[J]. IEICE Trans.on Information and Systems, 2014, 97(5): 1181-1187.

[5] ZHAO W, YUAN C Y, LIU G, et al. Workflow process model verification using reduction method based on P/T System[J]. Journal of Software, 2004, 15(10): 1423-1430.

[6] CICIRELLI F, FURFARO A, NIGRO L. Using time stream Petri-nets for workflow modelling analysis and enactment[J]. Simulation, 2013, 89(1): 68-86.

[7] RUTLE A, WANG H, MACCAULL W. A formal diagrammatic approach to compensable workflow modelling[C]∥Proc.of the 2nd International Symposium foundations of Health Information Engineering and Systems, 2013: 194-212.

[8] NAZARLOU M M. Research on application of hierarchy Petri-net in dynamic workflow modeling[J].Life Science Journal-Acta Zhengzhou University Overseas Edition,2013,10(1):821-825.

[9] CHOI Y S, KONGSUWAN P, JOO C M, et al. Stepwise structural verification of cyclic workflow models with acyclic decomposition and reduction of loops[J]. Data & Knowledge Engineering, 2015, 95: 39-65.

[10] MURATA T. Petri nets: properties, analysis and applications[J]. Proceedings of the IEEE, 1989, 77(4): 541-580.

[11] 朱錦泉, 苑森淼. 支持動態修改的可適應工作流模型[J]. 兵工學報, 2004, 25(5): 649-652.

ZHU J Q, YUAN S M. An adaptive workflow model supporting dynamic modification[J].Acta Armamentarii,2004,25(5): 649-652.

[12] RIBAS M, FURTADO C G, SOUZA J N D, et al. A Petri net-based decision-making framework for assessing cloud services adoption: the use of spot instances for cost reduction[J]. Journal of Network & Computer Applications, 2015, 57(C):102-118.

[13] 徐劍,葉文華,楊斌,等.基于擴展Petri網的飛機裝配線建模及平衡方法[J].計算機集成制造系統,2015,21(10):2596-2603.

XU J, YE W H, YANG B, et al. Assembly line modeling and balancing of aircraft based on extended Petri-net[J]. Computer Integrated Manufacturing Systems,2015,21(10):2596-2603.

[14] TIPLEA F L, LEAHU I. The reversible released form of Petri nets and its applications to soundness of workflow nets[J]. IEEE Trans.on Systems, Man and Cybernetics: Systems, 2014, 46(2): 303-304.

[15] 許玉堂,殷永峰,孫靜,等.基于時間擴展Petri網的實時嵌入式軟件體系結構建模及可靠性評估[J].兵工學報,2015,36(2): 363-373.

XU Y T, YIN Y F, SUN J, et al. Real-time embedded software architecture modeling and reliability estimation based on time-extended Petri-net[J].Acta Armamentarii,2015,36(2): 363-373.

[16] 魯法明, 曾慶田, 段華, 等. Petri網不可達標識的判定方法研究及其在死鎖檢測中的應用[J]. 計算機集成制造系統, 2016, 22(2): 465-475.

LU F M, ZENG Q T, DUAN H, et al. Decidability method of Petri-net non-reachability marks and its application in deadlock detection[J]. Computer Integrated Manufacturing Systems, 2016, 22(2): 465-475.

[17] LEVI M, PASHA P, HENRY P, et al. Small spacecraft software modeling: a petri net-based approach[J]. Journal of Aerospace Information Systems, 2014, 11(10): 679-690.