基于分組技術的工作流活動多實例的調度研究
2006-12-31 00:00:00楊光張春海
計算機應用研究 2006年9期
摘要：在分析靜態和動態活動多實例模型的基礎上，提出了一種機制——實例池和多實例分組技術，并且提出相應的算法，解決了靜態和動態多實例的調度問題。該機制可以處理靜態和動態多實例的生成、初始化、運行和調度以及銷毀。
關鍵詞：工作流；活動多實例；實例池；分組；調度
中圖法分類號：TP311文獻標識碼：A
文章編號：1001－3695(2006)09－0060－04
工作流是業務過程的模型，它將現實中的業務邏輯和規則以合適的模型在計算機中進行表示并對其實施計算[1，2]。
工作流活動多實例，是由一個工作流活動定義而產生的多個實例，它在多個工作流參與者的參與下共同完成。活動多實例問題是在實際中經常遇到的問題，如調查問卷、投票選舉等。在工作流管理系統中引入對活動多實例的支持，可以為現實環境中的業務流程處理帶來極大的靈活性和方便性。但是由于活動多實例本身的調度控制復雜性，使得大多數工作流管理系統對工作流活動多實例的調度基本不支持或僅提供有限的支持。
1工作流活動多實例
1．1工作流活動多實例的描述
定義：工作流活動[3]。
工作流活動N是一個四元組N
活動實例
根據運行語義的不同，文獻[3]提出了幾種典型的多實例運行模型。在此基礎上，我們歸納出活動多實例的前后觸發情況：
（1）OneJoin。前序活動A的某個實例a完成，就觸發活動A的后繼活動B的實例的執行。根據B被觸發的實例個數，可以分為11觸發和1n觸發兩種觸發方式。
(2)AllJoin。活動A的N個實例均完成后，才觸發A的后繼活動B的實例的執行。同樣可以分成n1觸發和nn觸發。
（3）PartJoin。活動A的一定數量的實例完成后，就可以觸發A的后繼活動B的實例的執行。可以分成n1觸發和nn觸發。對這種匯聚使用m/n連接符表示，如圖1所示。
1．2工作流活動多實例的分類
工作流活動多實例從其產生的方式來看，可以分為兩種：
（1）靜態多實例（又稱為設計期多實例）。它在設計期就能夠確定。某個活動在流程定義時就已經確定了要產生的實例的數目。
業務流程中的問卷調查通常就是靜態多實例的典型代表。問卷的發放數量在定義流程時就可以確定，這種情況只需要在設計流程時指定數目就可以了。
根據靜態多實例的定義，在工作流中出現次數最頻繁的活動單實例也可以歸屬到靜態多實例的范疇中。
（2）動態多實例（又稱為運行期多實例）。它的多實例個數在運行期決定。一般是因為多實例的數目要依據運行期的一些信息而定，而這些信息在設計期是不確定的或者是模糊的。如工作流參與者不明確時，就無法在設計期決定到底應該產生多少個活動實例。
但是在動態多實例活動要被引擎執行前，動態多實例應該被確定化為靜態多實例，否則工作流將無法繼續執行。這就要求每個動態多實例都應該有一個實例確定點，流程實例執行路徑一旦跨越了該實例確定點，則表示相應的動態多實例所需要的產生條件和初始化信息均已經滿足，可以將動態多實例靜態化了。但如果有兩個動態多實例的實例確定點產生了相互依賴，則本流程就會失敗。
流程實例執行路徑跨越了一個實例確定點后，根據相應的動態多實例一次所能產生的多實例個數，動態多實例又可以被分為兩類，即當條件滿足時，一次只產生m（1≤m＜n）個實例；當條件滿足時，一次性產生所有的活動實例。
在線投票流程如圖2所示。對一項決議進行投票，在截止時間前登錄注冊的人員均有權投票，只有當有效票數超過所有注冊人員的80%后，投票結果才算有效。
“網上注冊”和“網上投票”是兩個動態多實例。大多數情況下，注冊一般是一個單實例的活動，有一個活動處理所有的注冊信息。如果要記錄其他的一些和與會者個人相關的信息，可以作為一個多實例來實現。
每當一個用戶登錄后，就會產生一個“網上注冊”的活動實例，當到達截止時間或是注冊人數達到一定數量時，這個多實例活動就可以完成了。當投票人數確定后，所有的投票活動實例會一次性地全部產生。如網絡會議的注冊等，只能是登錄一個工作流參與者就產生一個注冊活動實例。
無論是哪種情況，都需要一種機制來控制活動多實例的生成、運行和銷毀。在此我們引入了活動的實例池，對活動多實例進行管理。
2實例池中活動多實例的分組
2．1活動實例池
活動實例池定義如下：
（1）活動實例的生存期。
工作流活動實例的生存期起始于活動的某個實例被創建時，終止于該實例被銷毀。
（2）活動實例池。
工作流的活動實例池隸屬于一個流程定義，對應著流程定義中某個活動定義。它是一個七元組POOL
在工作流系統運行時，根據某個流程定義可以產生多個流程實例。組成流程實例的活動實例的生存期均是由與ActivityID相對應的活動實例池來管理的。活動所需要的資源等均由實例池在創建活動實例時負責申請。當資源不足時，將活動轉入休眠隊列；待到資源申請成功后，繼續創建活動實例；創建完畢后，執行活動或分派工作項。一個簡單的示意圖如圖3所示。
2．2活動多實例分組
為了管理活動多實例，我們提出活動多實例的分組技術。對一個活動定義的多個實例，根據其不同的執行路徑和觸發條件，分成各不相同的組，每個組含有一個或多個活動實例。首先，我們對工作流活動及其實例的定義進行如下擴展：
（1）擴展的工作流活動。
工作流活動N是一個五元組N
（2）擴展的活動實例。
擴展的活動實例是活動定義
（3）實例組。
一個實例組隸屬于一個活動實例池，是一個四元組
2．3ICB/OCB分組表和OCBICB觸發映射表的生成
活動實例池的管理將以組為單位進行，分組操作在ICB和OCB中分別進行，最終形成一個流程定義的ICB分組表、OCB分組表和OCBICB觸發映射表。ICB分組被實例池用于生成某一組的活動；OCB分組被用于判斷某個分組是否滿足匯聚條件以觸發后續活動；觸發映射表則包含了組與組之間的觸發對應關系。將實例分組后可以形式化地表示為PoolID{gid{inst_id，inst_id，…}，gid{inst_id，…}，…}，其中PoolID表示具體的實例池，gid表示實例池中的某個分組，inst_id表示組中的活動實例。
相關算法如下：
算法1建立ICB/OCB分組表
輸入：流程定義
輸出：ICB/OCB分組表
（1）對起始節點的實例池，ICB分組設為PBegin。
（2）對終止節點的實例池，OCB分組設為PEnd。
（3）對每個實例池：
①實例池中的活動按其觸發源進行分組，相同觸發源的活動分為同一組，形成當前實例池的ICB分組；
②實例池中的活動按其匯聚點進行分組，相同匯聚點的活動分為同一組，形成當前實例池的OCB分組。
(4)將所有活動實例池的ICB分組組合成ICB分組表。
(5)將所有活動實例池的OCB分組組合成OCB分組表。
(6)輸出ICB/OCB分組表。
由算法1可知，當流程定義了動態多實例后，ICB/OCB分組表的生成無法在定義期一次完成。將動態多實例所涉及的分組保留，待運行期動態多實例確定后再填入。
算法2建立OCBICB觸發映射表
輸入：流程定義
輸出：OCBICB觸發映射表
(1)取流程定義圖的有向邊的集合E。
(2)從E中取一條邊
①如果a是PBegin，則表示b是初始節點。如果b不在PBegin的觸發序列中，則在PBegin的觸發序列中填入b，轉(3)。
②如果b是PEnd，則表示a是終止節點。如果PEnd不在a的觸發序列里，則填入PEnd，轉(3)。
③如果IB不在OA的觸發序列中，則將IB填入OA的觸發序列，轉(3)。
(3)如果E中還有其他的邊未處理，則轉(2)。
(4)對各個觸發序列中的實例組按觸發優先級排序。
(5)輸出OCBICB觸發映射表。
首先是因為起始節點和終止節點比較特殊，所以要特殊處理。再者，實例組的觸發優先級不同，即當實例組g1和g2均滿足觸發條件，但又不能同時觸發時，則必須根據觸發優先級來決定g1和g2的觸發次序。因此，觸發映射表中某個OCB組的ICB觸發序列應該是一個偏序集合
邊集E中只包含已經確定了執行路徑的邊，而不包含與動態多實例相關的邊。這些不確定的邊將隨著運行期信息的確定而被確定。當動態多實例“靜態化”時，工作流引擎或者管理員將對邊集E進行更新，并重新執行算法1和算法2，以更新各個表的信息。
此時，算法的執行將被限制在一個局部范圍內，僅在已經確定化了的動態多實例的前后局部執行。
3活動多實例的調度控制
我們使用一個示例流程，B，C，E都是靜態多實例，D則是動態多實例。假設D的實例確定點定義在b1和b2的執行完成時刻。流程定義圖如圖4所示。
首先使用表生成算法生成ICB分組表（表1）、OCB分組表（表2）和OCBICB觸發映射表（表3）。
因為D是動態多實例，所以在設計期算法第一次執行時，相關的分組不能確定，暫時空置。
3．1控制算法描述
為了描述控制算法，首先給出關鍵活動實例和Count算子的定義。
定義：關鍵活動實例。
一個活動實例被掛起時，整個流程實例必須被掛起。若活動實例執行失敗，流程的執行必須終止。這種活動實例就稱為關鍵活動實例。如11，1n，n1匯聚中的“1”端一般自動成為關鍵活動實例，對于其他活動實例則可以根據實際情況決定。
定義：Count算子。
Count算子接收輸入元組
實例池的ICB根據ICB分組表和Input來決定實例化一個或一組活動實例。當活動完成初始化開始執行后，就由OCB來負責。一旦活動完成，則OCB根據活動的完成狀態和OCB分組表來決定如何操作。如果活動執行失敗，且活動是關鍵活動，則終止執行并將信息發送給工作流引擎進行異常處理；若活動是非關鍵活動，則丟棄此活動實例。如果活動執行成功，則OCB使用Count算子更新實例組的狀態State，當其滿足了觸發條件時，OCB就產生Output發送給工作流引擎去引發下一活動。具體的算法實現如下：
算法3實例池POOL的ICB控制算法
（1）ICB接收輸入信息Input。
（2）從Input信息中查找前一活動所屬的OCB分組的組號OP，在OCBICB觸發映射表中找到與OP對應的觸發序列。（3）從觸發序列中找出組狀態State為“NULL”的第一個組g（Priority值最大者，因為生成表時已經排序）。
（4）為組g中的活動申請資源生成組g中的活動實例集合，將組g的State設置為“CREATED”。
此時活動將開始執行，或調用外部程序，或調用WebSer－vice，或分發工作項給工作流參與者。當活動執行完畢并提交后，由實例池的OCB進行調度控制。
算法4實例池POOL的OCB控制算法
（1）OCB接收活動的提交信息。
（2）如果活動是因為發生錯誤而被提交的，則若活動是關鍵活動，置活動所在組g的State為“EXCEPTION”，終止執行，由工作流引擎處理異常；否則，丟棄非關鍵活動并退出算法。
（3）如果活動所在的組g的State已被設置為“COMMIT”或“EXCEPTION”，則丟棄活動，退出算法。
（4）使用Count（gid，joinstyle）算子進行實例組的State更新。
（5）如果實例組g的State狀態為“COMMIT”，將組號放入Output輸出信息，發送給工作流引擎。
3．2多實例控制舉例
假設T1時刻，狀態為“b1，b2剛被提交”，則動態多實例活動D可以被實例化。此時的流程定義圖被更新為如圖5所示。
算法被再次執行，以更新相應的表的內容。相關的更新如表4~表6所示。
此時，流程執行中的不確定因素均已被消除。T2時刻，狀態變為“e1已經開始執行，d3剛被提交”，則PoolE的ICB接收Input信息后，掃描觸發映射表OD2的觸發序列，發現IE2{e2，e3}的State是“NULL”，因此PoolE的ICB分組中IE2為當前應該觸發的分組。PoolE的ICB為組IE2申請資源后，生成了實例e2，e3，并將IE2的STATE設為“CREATED”。T3時刻，狀態為“e1，e2執行成功，陸續被提交，e3還在執行”，則PoolE的OCB收到了e1，e2的提交信息。OCB連續執行了Count（OE1，2/3）和Count（OE1，2/3）后，實例組OE1的狀態State被設置為“COMMIT”。所以OCB產生了Output，交由工作流引擎，觸發活動f。T4時刻，e3完成，但是因為實例組OE1的狀態State已經被設置為“COMMIT”，所以e3將被丟棄。
4相關研究與算法的比較
使用實例池和分組技術進行多實例的工作流調度控制，并將多實例在觸發和匯聚兩方面進行分組，比其他的一些算法機制中復雜的判斷和控制機制更容易理解和實現。而且將多實例的生成和控制與單實例的統一起來，并將活動實例的生存期管理從工作流引擎中分離出來，使工作流引擎以一致的接口僅對實例池進行管理。文獻[3]提出了使用Shell來管理和記錄多實例信息，與本文的研究方向有些類似，但是實現機制不同；文獻[4]提出了活動多實例的不同類別并進行了分類，但缺乏對多實例同步控制的深入分析；文獻[5]提出了工作流多實例建模，但未提出具體的表現形式。
5未來的工作
基于以上的控制機制，我們實現了一個多實例工作流的原型。該原型已可對常見的多實例進行調度，并且能夠比較好地處理動態多實例。但是由于算法需要隨著動態多實例確定而不斷重復執行，因此當工作流的流程定義非常復雜時（包含數十個甚至數百個多實例，靜態和動態多實例相混雜，執行路徑交叉繁雜）耗時較多。雖然這對于長達數天或數月的流程則可以忽略不計，但
對于短時間的流程實例（如生存期只有幾小時的流程實例）的性能影響比較嚴重。因此，我們以后將重點研究和優化短時間流程實例的多實例調度問題。
參考文獻：
［1］HollingsworthD.WorkflowManagementCoalition：TheWorkflowReferenceModel[M].Brussels：WFMCTC001003，1994.
［2］WfMC.WorkflowManagementCoalitionSpecification[M].Brussels：TerminologyandGlossary，WFMCTC1011，1996.
［3］孫瑞志，史美林.工作流活動多實例的調度控制[J］.軟件學報，2005，16(3)：400406.
［4］VanDerAalstWMP，TerHofstedeAHM，KiepuszewskiKB，etal.WorkflowPatterns[M].BETAWorkingPaperSeries，WorkingPaper47.Eindhoven：EindhovenUniversityofTechnology，2000.
［5］范玉順，吳澄.一種提高系統柔性的工作流建模方法研究[J].軟件學報，2002，13(4)：833839.
作者簡介：
楊光(1981)，男，碩士研究生，主要研究方向為數據庫理論及應用、XML數據庫和半結構化數據庫、異構數據集成、工作流等；
張春海(1963)，男，副教授，碩士生導師，主要研究方向為數據庫理論及應用、XML數據庫和半結構化數據庫、異構數據集成等。
