基于事件驱动的有限状态机实现工作流引擎的核心调度算法

 

有限状态机（FSM）又称为有限状态自动机或简称状态机，是表示有限个状态以及这些状态之间的转移和动作等行为的数学模型。

 

状态存储关于过去的信息，就是说它反映从系统开始到现在时刻的输入变化。转移指示状态变更，并且用必须满足来确使转移发生的条件来描述它。动作是在给定时刻要进行的活动的描述。有多种类型的动作：

进入动作（Entry action）

         在进入状态时进行

退出动作

         在退出状态时进行

输入动作

         依赖于当前状态和输入条件进行

转移动作

         在进行特定转移时进行

 

有限状态机是一种算法思想，简单而言，有限状态机由一组状态、一个初始状态、输入和根据输入及现有状态转换为下一个状态的转换函数组成。在Gof的23种设计模式里的state模式是一种面向对象的状态机思想，可以适应非常复杂的状态管理。

现在，在硬件领域，FSM被用于电路设计，而在软件领域被普遍用于搜索引擎的分词、编译器实现、游戏开发和工作流引擎实现。游戏开发中，通常用FSM实现NPC控制。在工作流引擎实现中，通常用FSM来实现对于流程实例、活动实例、转移实例、工作项实例的状态迁移。FSM的实现方式有多种，在工作流引擎中我们一般采用面向对象的方式来实现FSM。

图一、有限状态机逻辑图

在上图中，我们可以看出，FSM下一个状态和输出是输入和当前状态的函数，也就是说，输入和条件触发当前状态变迁为下一个状态，而下一个状态的实现会产生输出结果。

图二、工作流引擎内部对象关系图

工作流引擎中工作项状态转移表：

图三、 工作项状态转移表

工作流引擎中工作项状态转移图：

图四、工作项状态转移图

图三以状态转移表的形式描述了在工作流引擎中，单个工作项（任务实例）的有限的多个状态、这些状态之间的转移、转移条件及触发转移的事件（执行动作）。图四以状态转移图的形式描述了在工作流引擎内部一个具有2个节点的串行流程的工作项（任务实例）的状态转移情况：

加载并初始化第一个活动节点的任务实例形成待签à签收第一个任务实例形成待办à结束第一个任务实例à初始化第二个任务实例形成待签à签收第二个任务实例形成待办à结束第二个任务实例à流程实例结束

从图四可以看出工作流引擎内部的核心引擎的调度算法都是基于事件驱动的有限状态机来实现的，例如，签收动作（sign in）会触发待签状态（to sign in）到待办状态（to do）的变迁。通过图一我们设计出了工作流实例对象，通过图三、图四我们给出了工作流引擎内部工作流实例对象的基于事件驱动的有限状态机的转移表及转移图。下面给出工作项实例的伪代码实现：

public class Workitem{	
    public void initialize(){
	//todo: 
    }

    public void signin(String userId, String userName){
    		//todo:
    		setState("todo");
    		setSignInTime(currentTime);
    }
    
    public void take(String userId,String userName){
    
    }
    
    public void complete(){
    		setState("completed");
        setCompleted(currentTime);
        
        //compute the post activity instances by route pattern
        
        //signal the transition of current activity instance	
        
        //to initialize the post activity instance
        
        //to initialize the workitem instance of the post activity instance
    }

    public void delegate(String userId, String userName){
    
    }

    public void cancelDelegate(){
    
    }

    public void cancelCompete(){
    
    }

    public void suspend(){
    
    }

    public void resumeSuspend(){
    
    }

    public void terminate(){
    
    }

    public void callback(){
    
    }

    public void backword(){
    
    }

}

 当然，以上只是给出了工作流引擎内部工作项的状态变迁描述及实现，在工作流引擎内部，还有活动实例，流程实例，转移实例的状态变迁，还有21种基本流转模式的实现等。但是我们掌握了有限状态机的理论及实现，就解决了工作流引擎内部最为核心的所有工作流实例的状态变迁问题。在下一篇文章中，我会继续描述怎样实现工作流引擎的21种基本的流转模式。

评论

3 楼 itstarting 2009-07-31  

我也在关注这个话题：
http://www.iteye.com/topic/436329

大家可以先看看jFSM的实现，我主要的考虑和顾虑：
1、FSM的模型能否满足需求，尤其是自由流程（楼上说的对，模式很多了，有谁论证过是否适用？）；
2、FSM的使用范围：工作流有很多的状态，都适用还是？

2 楼 nychen2000 2009-06-28  

今天再拜读大作。顺便提一个我一直没有捉摸透的疑问。
我感觉FSM只是描述了某个节点状态转移规则，从一个节点complete到下一个节点的initialize是一个很复杂的问题，尤其在下一个节点有汇聚的情况下。FSM如何解决这个问题呢？

1 楼 huidian 2009-06-04  

现在已经是44种流转模式了。
期待作者的实现描述！