基于对象池的活动多实例调度研究

张琳

（山西忻州职业技术学院，山西 忻州 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—），女，山西忻州人，本科，毕业于中北大学，现就职于忻州职业技术学院，助教，从事计算机专业的教学。