基于對象池的活動多實例調度研究

張琳

（山西忻州職業技術學院，山西 忻州 034000）

基于對象池的活動多實例調度研究

張琳

（山西忻州職業技術學院，山西 忻州 034000）

設計并實現一種帶鎖機制的對象池調度模式，為每個活動構造一個對象池，活動的所有實例存入對象池中，根據活動類型執行不同的實例調度策略。采用對象池模式，每個活動的多個實例可以實現同步調度并且不會有沖突，同時鎖機制的設計也使得共享數據能夠安全訪問。

工作流；活動多實例；對象池；同步調度；數據共享

引言

工作流活動多實例，是指多個參與者共同完成一個活動，該活動由多個實例組成［1］。活動多實例的引入簡化了工作流程的定義，增強了工作流的柔性，提高了工作流處理的靈活性和動態性，但同時引發了同步調度和共享數據訪問沖突的問題。目前，解決此類問題的方法主要是對工作流原模型進行屬性擴展，增加一些限制條件和約束元素等。例如，文獻［2］提出一種用于控制活動多實例分配和提交的控制體shell；文獻［3］提出一種可動態展開的基于“活動數組”的工作流模型以及結合ECA規則提出的π形演算方法。上述方法在一定程度上解決了活動多實例的同步問題，但由于引入了新元素，增加了系統代價，導致了通用性的降低。除了上述方法外，文獻［4］提出一種多實例分組技術，將活動的多個實例根據不同的執行路徑和觸發條件分成不同的組，對組內實例執行相應的調度；文獻［5］提出基于“分組-分類”的工作流活動多實例調度機制，將活動多實例分組啟動、在同組中分類同步。此類方法能實現活動多實例的同步調度，但未能解決活動多實例引發的數據共享沖突問題。

本文在研究以上調度機制的基礎上，對支持多個實例的活動模式進行分析，提出一種帶鎖機制的對象池調度模式。

1　工作流活動多實例分析

工作流活動多實例的相關定義如下：

定義1（活動定義）：工作流活動A可由四元組＜ID，U，T，S＞表示。其中，ID是活動的唯一標識符；U是活動的所有執行者集合；T是活動的類型，T∈｛NULL，AND-JOIN，OR-JOIN｝，NULL表示串行關系，AND-JOIN表示并行與關系，OR-JOIN表示并行或關系；S是活動的狀態，S∈｛未啟動，運行，掛起，完成｝。

定義2（活動實例定義）：活動的任意一個實例ai可由四元組＜id，a_id，u，s＞表示。其中，id是活動實例的唯一標識符；a_id是活動實例對應的活動編號；u是活動實例的執行者，u∈U；s是活動實例的狀態，s∈｛未啟動，運行，掛起，完成，失效｝。

定義3（活動多實例定義）：一個活動a（a∈A）被稱為多實例活動，當且僅當該活動至少存在2個活動實例aii和aij，且aii（a_id）=aij（a_id）。

定義4（多實例活動上下文定義）：一個多實例活動的上下文C可由三元組＜Trigger，Join-Type，Threshold＞表示。其中，Trigger是計數器，用以記錄多實例活動提交完成的數目；Join-Type是標識活動節點的類型，同定義1的T；Threshold是人工設定的閾值，即觸發后繼活動執行所需最小完成的實例數。

參照WfMC的XPDL所允許的工作流拓撲控制結構，工作流活動多實例調度模式歸納有串行（NULL）、并行與（AND-JOIN）、并行或（OR-JOIN）三種，下面分別對三種調度模式進行分析。

1）串行（NULL）活動多實例。

如下頁圖1所示，活動A結束后，活動B實例組中的實例依次被激活執行，只有當前面的活動實例執行完畢，后續實例才可被觸發。當且僅當活動B的所有實例執行完成，后繼活動C被觸發。

圖1　串行活動多實例

串行模式時，由于任意時刻至多只有一個實例處于運行狀態，因此此類模式不存在調度沖突問題。

2）并行與（AND-JOIN）活動多實例。

并行-與活動多實例調度是指當前活動的所有實例同步執行，當且僅當該活動的實例都完成后才可觸發后繼活動的執行，調度模式如圖2所示。

圖2　并行-與/并行-或活動多實例

并行-與調度模式時，活動A執行完成后，激活活動B，此時活動B分化為多個實例同步執行。只有當活動B的所有實例（b1，b2，…，bn）均被完成，后繼活動C才可觸發執行，因此此類模式的調度一定是同步的。

3）并行或（OR-JOIN）活動多實例。

并行-或活動多實例調度是指當前活動已完成的實例數必須達到規定的閾值后才可觸發后繼活動的執行。

如圖2所示，活動A結束后，活動實例組中的實例b1，b2，…，bn同步執行，僅當該組中完成的實例數達到設定的閾值i（1≤i＜n）時，后續活動C才可觸發執行。（備注：當閾值i為n時則為并行-與調度模式，此處為了區別對待，故i不取上限n）。

然而，假定活動B的實例完成數目已達到觸發活動C所需的閾值，則活動C被觸發執行，但此時活動實例組B中若存在其它正在執行的實例提交時，就可能由于后繼活動C已被觸發而產生沖突。

2　對象池模式實現及活動多實例調度控制

對象池是一種存放多個相同對象實例的數據結構。采用對象池模式，為每個活動構造一個單獨的對象池，活動與對象池一一映射，池內存儲各自活動的所有實例，以類似鏈表的方式進行管理。對象池中活動實例存儲方式如下所示（以圖3為例）：

圖3　對象池中活動多實例存儲方式

1）構造對象池。

為每個流程活動創建相應的對象池，活動的所有實例存入對象池中，工作流管理系統在調度執行時以對象池為單位對活動實例進行調度。以下為創建活動多實例對象的部分對象池代碼。

class Activity_Instance_Pool_Factory implements Poolable_Object_Factory｛

private int max_Activity_Instance；//池中允許最大實例數

private long wait；//活動實例執行的最長等待時間

public Activity_Instance_Pool_Factory（）｛｝

public Object create_Object（）throws Exception｛

return new Activity_Control（）；

｝

public void destroy_Object（Object object） throws Exception｛｝//銷毀失效的對象；

public void activate_Object（Object object） throws Exception｛｝//激活對象

public void suspend_Object（Object object） throws Exception｛｝//掛起對象；

｝

2）對象池與活動關聯。

構建好對象池后，將生成的活動實例存入對應的對象池中，采用對象池模式，活動的執行轉化為對對象池的調度，活動與對象池之間一一映射。這種映射關系可以通過構造哈希表來實現，表內分別存儲活動編號和對象池編號。算法如下所述。

輸入：流程活動集A=｛a1，a2，…，an｝

輸出：用于存儲活動編號ai和對象池編號pooli的HashMap

算法描述：

HashMap map = new HashMap（）；？

for each ai in A

Activity_Instance_Pool_Factory pool_factory =new Activity_Instance_Pool_Factory（）；

Object obj=pool_factory.create_Object（）；

Vector obj_pooli =new Vector（）；

obj_pooli.add（obj）；

map.put（ai， obj_pooli）；

｝

流程運行期間，用戶依據操作要求選擇執行方式和執行者。執行方式對應多實例調度模式，而選定的執行者則對應著需要生成的實例數。因此當流程運行時，系統根據選擇的執行方式執行不同的調度策略，對象池內所有實例以串行/同步方式進行調度。

串行調度模式：對象池中每一個實例對象依照執行者的順序順次調度執行，只有當前驅實例執行結束，后繼實例方可執行。

并行與調度模式：對象池中所有實例同步執行，當且僅當池內所有實例執行結束后觸發后繼活動的執行。

并行或調度模式：對象池中所有活動實例同步執行，并計算已完成的實例數，當已完成的實例數達到預設的閾值時，就觸發后繼活動的執行，同時將當前活動其它實例對象狀態置為失效，避免同步沖突。

同步沖突處理：由于串行/并行與調度模式不存在同步沖突，因此本文只對并行或調度模式進行特殊處理。解決方法有：一是通過站內消息的方式通知實例的執行者，該實例已失效，由用戶手動刪除該實例；二是不通知用戶，由系統強制將超期未完成實例的狀態更改為失效，并刪除。方法一需要人工參與，等待用戶手動刪除超期的實例，耗時長，本文采用方法二。

共享數據訪問：由于活動可能存在多個實例對象，每個實例對象處理的工作項也基本相同，因此極有可能訪問同一個數據資源，為了避免共享數據的訪問沖突，本文采用加鎖機制實現數據的共享訪問。

加鎖示例代碼如下：

class test｛

public static A a= new A（）；

void method（）｛

…

synchronized（a）｛…｝//對a進行加鎖

…｝

｝

class A｛…｝

對象池對實例對象進行管理，同時處理用戶的調度需求。對象池處理用戶請求的基本思想是：首先根據執行的活動，確定與之匹配的對象池。利用實例執行者與實例對象的映射關系，確定當前調度的實例對象，根據活動類型，分別對實例對象執行不同的調度策略。下面給出具體的算法。

①IF PI 啟動； THEN Activity.S=”running”

//流程啟動，活動開始執行

②//根據活動編號獲取對象池

Vector obj_pool=（Vector）map.get（Activity_id）；

//對池內實例進行調度

IF（Activity=MultipleInstanceActivity）

｛

IF（Activity.T==”NULL”）｛//串行調度

THEN 獲取對象池中第一個實例對象；

WHILE（ActivityInstance.s！=”完成”）｛

ActivityInstance.s==”運行”；

ActivityInstance執行完成后，更改狀態為完成；

獲取下一個活動實例；

｝

Run（NextActivity）； //觸發后繼活動；

RETURN TRUE；

｝

ELSE IF（Activity.T==”AND-JOIN”）｛//并行與調度

THEN 對象池中該活動所有實例對象都取出并執行；

WHILE（Exist（ActivityInstance！=”完成”）｛

等待該活動實例執行，直至所有活動實例都結束；

｝

Run（NextActivity）；//觸發后繼活動；

RETURN TRUE；

｝

ELSE IF（Activity.T==”OR-JOIN”）｛//并行-或調度

同步執行所有活動實例；

IF（NUM（Finished（ActivityInstance）＜ Threshold）｛

//如果完成的實例數小于觸發后繼活動所需的閾值；繼續等待其它實例的完成；

｝

//達到觸發的閾值

Run（NextActivity）；//觸發后繼活動；將其余超時的活//動實例狀態置為失效；

RETURN TRUE；

｝

｝

③IF所有PI（ACTIVITY）.S=”完成”｛

DESTROY ActivityInstancePool；

｝

3　案例驗證

活動多實例經常用于會簽、投票等需要多人共同操作才可完成的任務中。為了驗證基于對象池模式的活動多實例調度機制的可行性，本文抽取某上市公司辦公自動化系統中的會簽流程進行校驗，如圖4所示。

發文管理的“部門會簽”是一個多實例活動，在觸發“部門會簽”活動后，由流程操作人員選擇會簽執行者（即生成活動多實例）和會簽執行模式（活動多實例調度模式），之后系統根據選擇的會簽模式和會簽執行者的個數生成活動實例，同一個活動的所有實例全部存入對象池中。以并行或活動多實例為例，當前活動的所有執行者同步執行，當完成的活動實例數目達到預設的閾值時，就觸發后繼活動（領導簽發）的執行。若此刻有其它的實例完成，但由于領導簽發活動已被觸發，則該實例及其它實例對象均被丟棄，置為失效狀態。當流程實例執行結束后系統自動清空對象池中的所有活動實例。

圖4　發文管理業務流程

4　結語

基于加鎖機制的對象池調度機制能夠比較好的解決活動多實例的調度問題。但由于設計時強調調度的準確性和便利，需要將活動的全部實例存儲在對象池中，耗時較多，對工作流的性能稍有影響。因此，下一步的工作主要在于改進對象池，使其代碼是“輕量的、運行高速的”。

［1］Aalst W M P，Hofstede A H M，Kiepuszewski K B.WorkflowPatterns［M］. Eindhoven，Netherlands：Eindhoven University ofTechnology，200 0.

［2］孫瑞志，史美林.工作流活動多實例的調度控制［J］.軟件學報，20 0 5，16（3）：400-406.

［3］梁愛南，李云長，黃賢明.多實例工作流模式的π演算形式化［J］.計算機應用，2007，2 7（1）：2 19-2 20：2 2 4.

［4］楊光，張春海.基于分組技術的工作流活動多實例的調度研究［J］.計算機應用研究，2006（9）：6 0-6 3.

［5］馬敏，劉琳嵐，付錚，等.基于分組-分類的工作流活動多實例調度［J］.計算機工程，2009，35（1）：6 8-70.

（編輯：劉楠）

Scheduling Analysis on Multiple Instances Based on the Object Pool

Zhang Lin
（Xinzhou Vocational and Technical College，Xinzhou Shanxi 034000）

This paper designed and implemented a lock mechanism of object pool scheduling model， constructs an object pool for each activity， the activity of all instances in the object pool， depending on the type of activity instances perform different scheduling policies. USES the object pool pattern， multiple instances of each activity can realize synchronous scheduling and there would be no conflict， at the same time， the design of locking mechanism enables the sharing data to secure access.

work flow； multiple instance； objective pool； synchronization schedule； data sharing

TP311

A

2095-0748（2016）15-0064-04

10.16525/j.cnki.14-1362/n.2016.15.27

2016-06-20

張琳（1987—），女，山西忻州人，本科，畢業于中北大學，現就職于忻州職業技術學院，助教，從事計算機專業的教學。