四川大学硕士学位论文——基于WEB技术的工作流管理系统设计与实现
5.3.1任务调度策略
如果说工作流引擎是工作流管理系统的灵魂，那么，任务调度策略就是工作
流引擎的灵魂，也就是说任务调度策略是工作流管理系统的核心之核心。工作流引擎的任务调度策略的性能的优劣以及调度策略能否很好的进行扩展将直接关系到工作流管理系统的功能是否强大。
不同的工作流管理系统的任务调度策略通常是不一样的，本文所述及的工作
流管理系统的任务调度策略采用的是Petri网的经典调度算法。下面将首先介绍Petri网的基本调度算法，然后结合实例说明任务是如何依据Petri网调度算法被调度的。
5.3.1.1 Petri网调度算法
Petri网调度算法的核心思想非常简单。在本文第2部分曾介绍过Petri网的四
种基本图元：库所、变迁、弧、标记。其中，标记是一种流程实例状态信息的载体，标记在库所中的分布情况反映的是流程实例的状态信息。Petri网的调度算法或者说Petri网流程的推进过程实质上是token的创建和消耗的过程。具体来说，当任意一个token被创建在某个库所中时，算法都将查看是否因为该token的产生而使得某些变迁从常态迁移到就绪态，根据第2部分的介绍，即是说，是否因为该token的产生而使得某些变迁的所有输入库所中都至少具有了一个token，如果存在满足该条件的变迁，那么，该变迁就从常态迁移到了就绪态，也就是说该变迁当前可以被执行，但是，什么时候被执行将取决于该变迁的触发类型。当一个处于就绪态的变迁被触发前，其状态一直保持为就绪态，并且会将其所有输入库所中的一个token进行锁定，直到该变迁被触发时，变迁才从就绪态迁移到激发态，具体来说，一个处于就绪态的变迁被触发的过程包含如下步骤：
1. 变迁所对应的任务实体被实际执行；
2. 变迁从其所有输入库所中消耗掉在该变迁成为就绪态时锁定的token； 3. 变迁为其所有输出库所生成新的token；
34
四川大学硕士学位论文——基于WEB技术的工作流管理系统设计与实现
4. 变迁从就绪态迁移到激发态并瞬间变回常态。
从该过程不难看出，变迁从就绪态迁移到激发态的过程实质上是变迁消耗其输入库所中的token同时为其输出库所产生token的过程。一个token的创建可能引起了变迁状态的迁移，变迁状态的迁移消耗了输入库所中的token并为其输出库所生成新的token，新生成的token又会重复该过程，形成了迭代。该迭代过程也就是任务的调度过程、流程状态的改变过程。因此，前文提到过token在库所中的分布情况反映的是流程实例的状态信息。
当一个流程模型被实例化的时候，工作流引擎会自动为该流程模型实例的起
始库所生成一个token，就是这个被最初放置在起始库所中的token，触发了整个流程实例的运行。当任意时刻我们观察一个流程实例的时候，如果该时刻没有新的token生成时，我们称流程模型处于饱和状态，或静止状态；如果因为一个token的产生引起了新的token的产生并且这样的过程在瞬间迭代下去，那么，在该时刻所观察到的流程实例将是不稳定状态，或不饱和状态，这样的状态最终将会趋于饱和状态，也就是说流程实例将最终进入静止状态，我们称这种现象为“桌球碰撞现象”。当桌球的球台上分布着许多桌球的时候，如果击出其中一球，该球在运动中可能会碰撞到其它球而引起其它球的运动，而被引起运动的球在其运动过程中又可能会引起另外的球运动，这样的迭代下去，如果某一时刻球台上仍然有在运动的球，那么我们就说其处于不饱和状态，直到所有球都不再运行，我们说此时处于了饱和状态或静止状态。于是，某个变迁从就绪态迁移到激发态的动作过程所产生的新token就好像是被击出的桌球一样，这些token的产生很可能会引起新的token的生成，直到处于饱和为止。
这种“桌球碰撞现象”即是Petri网调度算法的核心所在，在下节中我们将根
据一个实例来说明Petri网的调度算法。 5.3.1.2调度实例说明
本节内容将结合一个简单的Petri网模型来说明Petri网的调度算法。本节中
各个Petri网模型图中白色矩形代表的是处于常态和激发态的变迁，具有花岗石底纹的矩形代表的是当前处于就绪态的变迁。Petri网模型图中的小黑点代表的是当
35
四川大学硕士学位论文——基于WEB技术的工作流管理系统设计与实现
前token的分布。
P2 T2 P1 T1 P3 T3 P5 T4 P6 P4
图14：T1就绪即刻迁移为激发态
图14说明当前模型实例刚刚被工作流引擎实例化，由工作流引擎在起始库所P1种生成了第一个token，该token的产生即刻引起了变迁T1从常态迁移到了就绪态，当前模型实例的状态并非饱和状态，因为处于就绪态的变迁T1处触发类型为系统自动触发，因此，当其从常态迁移到就绪态时即刻被调度执行，T1将会从就绪态即刻进入激发状态（常态），该变化将会将T1的输入库所P1种的token消耗掉，并为其所有输出库所P2、P3生成新的token，模型实例进入图15所示的饱和状态。
P2 T2 P1 T1 P3 T3 P5 T4 P6 P4
图15：T2和T3处于就绪态
图15所示的模型实例处于了一种饱和状态，即P2中产生的token使得变迁T2从常态迁移到了就绪态；P3种产生的token使得变迁T3从常态迁移到了就绪态，但是，因为T2、T3与T1的触发类型不同，T2、T3都是手工触发的变迁，因此，T2、T3迁移到就绪态时会将其各自输入库所及P2、P3中的token锁定，T2、T3何时被激发将取决于用户何时来执行T2、T3所对应的任务实体。T2、T3的激发是没有时序限定的，也就是说，既可能是T2先被激发，也可能是T3先被激发，
36
四川大学硕士学位论文——基于WEB技术的工作流管理系统设计与实现
这里我们假定T2先被激发，模型实例进入图16所示状态。
P2 T2 P1 T1 P3 T3 P5 T4 P6 P4
图16：T2激发，T3仍处于就绪态
图16所示的状态是T2被激发后的状态，T2的激发使得P2中的token被消耗，同时为T2的输出库所P4产生了token，调度算法此时会尝试找到因为P4中token的产生而可能会成为就绪态的变迁，但是，却没有这样的变迁，因为对于变迁T4来说，虽然其输入库所P4拥有了token，但是，T4的另外一个输入库所P5中却没有token，因此，T4不满足从常态迁移到就绪态的条件，因此，当前模型实例处于稳定状态。只有T3的激发会引起模型实例状态的改变。假定此时T3被激发了，按照规则，将会把P3中的token消耗掉，同时为P5产生新的token，状态如图17
P2 T2 P1 T1 P3 T3 P5 T4 P6 P4
图17：T3激发，T4处于就绪态
图17所示的是T3被激发后的状态，当P5中产生token时，调度算法尝试找到因为P5中token的产生而可能会成为就绪的变迁，于是，找到了T4，T4的状态就从常态迁移到了就绪态，T4的触发类型为手工触发，T4被调度等待用户进行触发。假定此时用户进行了触发操作，使得T4从就绪态迁移到了激发态（常态），按照规则，将会把其输入库所P4、P5中的token消耗掉，同时为其输出库所P6
37