張琳

（山西忻州職業(yè)技術(shù)學(xué)院，山西 忻州 034000）

基于對象池的活動多實例調(diào)度研究

張琳

（山西忻州職業(yè)技術(shù)學(xué)院，山西 忻州 034000）

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

工作流；活動多實例；對象池；同步調(diào)度；數(shù)據(jù)共享

引言

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

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

1　工作流活動多實例分析

工作流活動多實例的相關(guān)定義如下：

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

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

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

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

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

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

如下頁圖1所示，活動A結(jié)束后，活動B實例組中的實例依次被激活執(zhí)行，只有當(dāng)前面的活動實例執(zhí)行完畢，后續(xù)實例才可被觸發(fā)。當(dāng)且僅當(dāng)活動B的所有實例執(zhí)行完成，后繼活動C被觸發(fā)。

圖1　串行活動多實例

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

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

并行-與活動多實例調(diào)度是指當(dāng)前活動的所有實例同步執(zhí)行，當(dāng)且僅當(dāng)該活動的實例都完成后才可觸發(fā)后繼活動的執(zhí)行，調(diào)度模式如圖2所示。

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

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

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

并行-或活動多實例調(diào)度是指當(dāng)前活動已完成的實例數(shù)必須達到規(guī)定的閾值后才可觸發(fā)后繼活動的執(zhí)行。

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

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

2　對象池模式實現(xiàn)及活動多實例調(diào)度控制

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

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

1）構(gòu)造對象池。

為每個流程活動創(chuàng)建相應(yīng)的對象池，活動的所有實例存入對象池中，工作流管理系統(tǒng)在調(diào)度執(zhí)行時以對象池為單位對活動實例進行調(diào)度。以下為創(chuàng)建活動多實例對象的部分對象池代碼。

class Activity_Instance_Pool_Factory implements Poolable_Object_Factory｛

private int max_Activity_Instance；//池中允許最大實例數(shù)

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

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）對象池與活動關(guān)聯(lián)。

構(gòu)建好對象池后，將生成的活動實例存入對應(yīng)的對象池中，采用對象池模式，活動的執(zhí)行轉(zhuǎn)化為對對象池的調(diào)度，活動與對象池之間一一映射。這種映射關(guān)系可以通過構(gòu)造哈希表來實現(xiàn)，表內(nèi)分別存儲活動編號和對象池編號。算法如下所述。

輸入：流程活動集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）；

｝

流程運行期間，用戶依據(jù)操作要求選擇執(zhí)行方式和執(zhí)行者。執(zhí)行方式對應(yīng)多實例調(diào)度模式，而選定的執(zhí)行者則對應(yīng)著需要生成的實例數(shù)。因此當(dāng)流程運行時，系統(tǒng)根據(jù)選擇的執(zhí)行方式執(zhí)行不同的調(diào)度策略，對象池內(nèi)所有實例以串行/同步方式進行調(diào)度。

串行調(diào)度模式：對象池中每一個實例對象依照執(zhí)行者的順序順次調(diào)度執(zhí)行，只有當(dāng)前驅(qū)實例執(zhí)行結(jié)束，后繼實例方可執(zhí)行。

并行與調(diào)度模式：對象池中所有實例同步執(zhí)行，當(dāng)且僅當(dāng)池內(nèi)所有實例執(zhí)行結(jié)束后觸發(fā)后繼活動的執(zhí)行。

并行或調(diào)度模式：對象池中所有活動實例同步執(zhí)行，并計算已完成的實例數(shù)，當(dāng)已完成的實例數(shù)達到預(yù)設(shè)的閾值時，就觸發(fā)后繼活動的執(zhí)行，同時將當(dāng)前活動其它實例對象狀態(tài)置為失效，避免同步?jīng)_突。

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

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

加鎖示例代碼如下：

class test｛

public static A a= new A（）；

void method（）｛

…

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

…｝

｝

class A｛…｝

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

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

//流程啟動，活動開始執(zhí)行

②//根據(jù)活動編號獲取對象池

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

//對池內(nèi)實例進行調(diào)度

IF（Activity=MultipleInstanceActivity）

｛

IF（Activity.T==”NULL”）｛//串行調(diào)度

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

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

ActivityInstance.s==”運行”；

ActivityInstance執(zhí)行完成后，更改狀態(tài)為完成；

獲取下一個活動實例；

｝

Run（NextActivity）； //觸發(fā)后繼活動；

RETURN TRUE；

｝

ELSE IF（Activity.T==”AND-JOIN”）｛//并行與調(diào)度

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

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

等待該活動實例執(zhí)行，直至所有活動實例都結(jié)束；

｝

Run（NextActivity）；//觸發(fā)后繼活動；

RETURN TRUE；

｝

ELSE IF（Activity.T==”O(jiān)R-JOIN”）｛//并行-或調(diào)度

同步執(zhí)行所有活動實例；

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

//如果完成的實例數(shù)小于觸發(fā)后繼活動所需的閾值；繼續(xù)等待其它實例的完成；

｝

//達到觸發(fā)的閾值

Run（NextActivity）；//觸發(fā)后繼活動；將其余超時的活//動實例狀態(tài)置為失效；

RETURN TRUE；

｝

｝

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

DESTROY ActivityInstancePool；

｝

3　案例驗證

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

發(fā)文管理的“部門會簽”是一個多實例活動，在觸發(fā)“部門會簽”活動后，由流程操作人員選擇會簽執(zhí)行者（即生成活動多實例）和會簽執(zhí)行模式（活動多實例調(diào)度模式），之后系統(tǒng)根據(jù)選擇的會簽?zāi)Ｊ胶蜁瀳?zhí)行者的個數(shù)生成活動實例，同一個活動的所有實例全部存入對象池中。以并行或活動多實例為例，當(dāng)前活動的所有執(zhí)行者同步執(zhí)行，當(dāng)完成的活動實例數(shù)目達到預(yù)設(shè)的閾值時，就觸發(fā)后繼活動（領(lǐng)導(dǎo)簽發(fā)）的執(zhí)行。若此刻有其它的實例完成，但由于領(lǐng)導(dǎo)簽發(fā)活動已被觸發(fā)，則該實例及其它實例對象均被丟棄，置為失效狀態(tài)。當(dāng)流程實例執(zhí)行結(jié)束后系統(tǒng)自動清空對象池中的所有活動實例。

圖4　發(fā)文管理業(yè)務(wù)流程

4　結(jié)語

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

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

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

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

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

［5］馬敏，劉琳嵐，付錚，等.基于分組-分類的工作流活動多實例調(diào)度［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—），女，山西忻州人，本科，畢業(yè)于中北大學(xué)，現(xiàn)就職于忻州職業(yè)技術(shù)學(xué)院，助教，從事計算機專業(yè)的教學(xué)。