張琳

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

基于對(duì)象池的活動(dòng)多實(shí)例調(diào)度研究

張琳

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

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

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

引言

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

本文在研究以上調(diào)度機(jī)制的基礎(chǔ)上，對(duì)支持多個(gè)實(shí)例的活動(dòng)模式進(jìn)行分析，提出一種帶鎖機(jī)制的對(duì)象池調(diào)度模式。

1　工作流活動(dòng)多實(shí)例分析

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

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

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

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

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

參照WfMC的XPDL所允許的工作流拓?fù)淇刂平Y(jié)構(gòu)，工作流活動(dòng)多實(shí)例調(diào)度模式歸納有串行（NULL）、并行與（AND-JOIN）、并行或（OR-JOIN）三種，下面分別對(duì)三種調(diào)度模式進(jìn)行分析。

1）串行（NULL）活動(dòng)多實(shí)例。

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

圖1　串行活動(dòng)多實(shí)例

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

2）并行與（AND-JOIN）活動(dòng)多實(shí)例。

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

圖2　并行-與/并行-或活動(dòng)多實(shí)例

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

3）并行或（OR-JOIN）活動(dòng)多實(shí)例。

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

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

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

2　對(duì)象池模式實(shí)現(xiàn)及活動(dòng)多實(shí)例調(diào)度控制

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

圖3　對(duì)象池中活動(dòng)多實(shí)例存儲(chǔ)方式

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

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

class Activity_Instance_Pool_Factory implements Poolable_Object_Factory｛

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

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

public Activity_Instance_Pool_Factory（）｛｝

public Object create_Object（）throws Exception｛

return new Activity_Control（）；

｝

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

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

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

｝

2）對(duì)象池與活動(dòng)關(guān)聯(lián)。

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

輸入：流程活動(dòng)集A=｛a1，a2，…，an｝

輸出：用于存儲(chǔ)活動(dòng)編號(hào)ai和對(duì)象池編號(hào)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）；

｝

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

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

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

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

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

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

加鎖示例代碼如下：

class test｛

public static A a= new A（）；

void method（）｛

…

synchronized（a）｛…｝//對(duì)a進(jìn)行加鎖

…｝

｝

class A｛…｝

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

①IF PI 啟動(dòng)； THEN Activity.S=”running”

//流程啟動(dòng)，活動(dòng)開(kāi)始執(zhí)行

②//根據(jù)活動(dòng)編號(hào)獲取對(duì)象池

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

//對(duì)池內(nèi)實(shí)例進(jìn)行調(diào)度

IF（Activity=MultipleInstanceActivity）

｛

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

THEN 獲取對(duì)象池中第一個(gè)實(shí)例對(duì)象；

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

ActivityInstance.s==”運(yùn)行”；

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

獲取下一個(gè)活動(dòng)實(shí)例；

｝

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

RETURN TRUE；

｝

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

THEN 對(duì)象池中該活動(dòng)所有實(shí)例對(duì)象都取出并執(zhí)行；

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

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

｝

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

RETURN TRUE；

｝

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

同步執(zhí)行所有活動(dòng)實(shí)例；

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

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

｝

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

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

RETURN TRUE；

｝

｝

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

DESTROY ActivityInstancePool；

｝

3　案例驗(yàn)證

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

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

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

4　結(jié)語(yǔ)

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

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

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

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

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

［5］馬敏，劉琳嵐，付錚，等.基于分組-分類的工作流活動(dòng)多實(shí)例調(diào)度［J］.計(jì)算機(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é)院，助教，從事計(jì)算機(jī)專業(yè)的教學(xué)。