工作流引擎核心调度算法与PetriNet_胡长城.pdf

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.25M 资料格式：pdf 举报版权申诉

forestk-1045752-4744300845373743833.pdf-第1页.png

第1页 / 共15页

forestk-1045752-4744300845373743833.pdf-第2页.png

第2页 / 共15页

forestk-1045752-4744300845373743833.pdf-第3页.png

第3页 / 共15页

forestk-1045752-4744300845373743833.pdf-第4页.png

第4页 / 共15页

forestk-1045752-4744300845373743833.pdf-第5页.png

第5页 / 共15页

forestk-1045752-4744300845373743833.pdf-第6页.png

第6页 / 共15页

forestk-1045752-4744300845373743833.pdf-第7页.png

第7页 / 共15页

forestk-1045752-4744300845373743833.pdf-第8页.png

第8页 / 共15页

文本预览

工作流引擎核心调度算法与 PetriNet by 胡长城（银狐 999）工作流引擎核心调度算法与 PetriNet Workflow Kernel and Petri Net 版本：1.0 作者：胡长城 [ 银狐 999 ] http://www.javafox.org http://www.wfchina.org http://blog.csdn.net/james999 完成日期：2005-4-17 version 1.0 联系信箱：james-fly@vip.sina.com MSN ：fcxiao2000@hotmail.com 此篇并不是针对 workflow 的初学者，如果您刚刚接触工作流，本人不建议您阅读本篇更多工作流参考文档，请访问在 http://www.javafox.org 注：转载文章，请注明作者信息。第 1 页

工作流引擎核心调度算法与 PetriNet 目录 by 胡长城（银狐 999）声明 ..............................................................................................................................................2 前言废话 ......................................................................................................................................2 进入正题 ......................................................................................................................................3 先说说四个非 PetriNet 调度算法的开源引擎 ...........................................................................4 OBE 的引擎调度机制..........................................................................................................4 Shark 的引擎调度机制 ........................................................................................................5 OSWorkflow 的引擎执行机制 ............................................................................................6 JBpm 的引擎执行机制 ........................................................................................................6 再说说两个 PetriNet 调度算法的开源引擎 ...............................................................................9 YAWL 的引擎调度机制 ....................................................................................................10 Bossa 的引擎调度机制（标准的 PN 机） .......................................................................12 结尾 ............................................................................................................................................15 声明此篇并不是针对 workflow 的初学者。如果你对 workflow 不了解，或对篇中的几个 workflow engine（OBE，Shark，OSWorkflow，jBpm，YAWL，Bossa）都不了解的话，那么不建议您阅读此篇文章。如果您对 workflow 感兴趣，那么建议你在阅读此篇文档的时候，一边打开这几个开源引擎的源码，跟着文中的演示片断分析。本文为个人所言，难免会有疏忽遗漏错误之处，望斧正。如有疑问，可来信探讨，我的信箱：james-fly@vip.sina.com 。注：转载文章，请注明作者信息。前言废话过年之后，一直忙公司这边平台的重构，忙得我连自己的 blog 和主页都很久没有更新，这两天竟然还发现，我那《工作流之星光》【http://javafox.vip.myrice.com/mywf/bright】竟然快两个月未更新了。直到这几日有个小小阶段性的成果，但接下来又将是一轮新的研发。于是赶紧抓住这宝贵的还不算非常忙的几天，写写心得。这一个多月以来，最主要的工作就是把早先这边的工作流产品彻底的“翻”了一把。重构整个工作流引擎的组件框架和调度算法。也算是对自己这几年来，研究工作流的结果的一个“挑战性”钻研。这几年，做过几个工作流产品了，有成型的，有半成品的，但是由于各种各样的原因，一直没做出一个自己还比较满意的引擎，所以一直也很愧疚。从早期在 huihoo 上做 JFoxFlow，到后来的退出，也是这种思想。总感觉没有找到一个最“内核”的东西，于是最终还是放弃了做开源，把更多的时间用来钻研资料。第 2 页

工作流引擎核心调度算法与 PetriNet by 胡长城（银狐 999）前不久，公司这边不得不对工作流引擎进行重构，这个“烫手的山芋”也不得不落在了我身上。从理论上说，这是一件让我兴奋得事情；但是，从现实角度上，这又是一件让我头疼的事情（虽然来了有几个月了，但是毕竟这个产品早期不是我做的，很多部分我也不是很清楚，更烦得是，并没有多少文档）：重构已有的产品，是一件危险的事情，成则为王，败为寇。对于接手引擎重构这个任务，我并没有百分百的自信能够做好，毕竟短时间内重构一个自己并不十分了解的引擎，并且涉及到核心的调度算法和调度机制，实在是一个危险的事情。 ——但是最终也不得不这么做，有时候由不得自己。这一个多月来，甚至在深夜入睡的时候，躺在床上，都在想第二天的重构放案。—— 感觉自己那些日子，真像破釜沉舟。一个月之后，终于给自己了一个较为满意的答复，虽然功能上还有些细节未完善，但是整个引擎的框架布局、对外接口、内核调度算法和调度机制都基本上重构了一遍。—— 在重构的时候，更多的压力是来源自“重构出一个良好而又让自己满意的引擎内核”。当重构基本完结的那天下午，心里也是非常的兴奋。兴奋的实在是不想再写第二行代码，哈哈。只想坐在电脑前，哼着小曲，悠然自得；当然现实是不允许的。—— 这种兴奋，似乎压抑了两三年，如今终于让自己重构出一个让自己满意的引擎内核。至少现在，可以对得起自己这几年在 workflow 上扎下的功夫了。那么“内核”到底代表什么呢？这内核就是支撑整个引擎运转的内部调度算法、执行推进机制，以及围绕调度算法的一些 Context、Runner 类，及 kernel 的框架。这内核才是一个引擎的灵魂。进入正题既然说的是调度算法和 PetriNet，那么就有必要先从 PetriNet 说起。这次重构，将 Petri Net 的算法调度的应用和 XPDL 模型结合起来了。受这边产品早期引擎建模结构的影响，模型采用的还是扩展 XPDL。其实我对 XPDL 没有多少好感，但是也不得不承认，XPDL 中有些思想是很不错——还好，模型对引擎的影响并不是很大，真正影响引擎的是上面所说的“内核”。 PN 的算法描述本身是很简单的：任何一次 Token 的转移，都会引起对整个流程（在 PN 重构之前的一些修炼，还有赖于在早先在 Justep 公司的学习。虽然离开有好几个月了，虽然也只 Jjustep 中待了两个多月，但是在老宋的逼迫下，倒是对 Petri Net 的算法研究的了一番。依着我自己的性子，是很难自己去深入探索 PetriNet 的（至少之前，我对 PN 不感冒）。有关 PN 我就不详细解释了（懒得重复的敲文字），有兴趣的自己查阅资料。一定要查，否则这边文章你是看不下去了。中叫 Case）的重新使能（enabled）遍历。—— 就像“蝴蝶效应”。如果上面这句 PN 算法的描述，您并不是很清楚，那么建议你暂停往下阅读。先去查阅一下有关 PN 的资料，看看先。但是，估计绝大多是人，所熟悉的开源引擎的调度机制都不是采用 PN 算法的。比如 OBE， Shark，OSWorkflow，jBpm。—— 当然，有没有采用，对很多人来说，并不关心，他们只关心如何去用。第 3 页

工作流引擎核心调度算法与 PetriNet by 胡长城（银狐 999）如果你对 workflow 的调度算法不关心，或者只是想去篡改那些开源引擎的代码（这样的人，大有人在），那么请您停止阅读本篇。因为这篇文章，对你是毫无意义的。接下来，就让我们看看这些开源引擎的核心调度算法。—— 呵呵，没办法了，我只能拿开源的咚咚来跟大家说说了。这样一不涉及保密，二不涉及泄密。注：严重 bs 那些修改或一心想着修改开源引擎代码的家伙。先说说四个非 PetriNet 调度算法的开源引擎主要说几个大家都比较熟悉的：OBE，Shark，OSWorkflow，jBpm。分析一下他们的调度算法，就基本上可以知道其能力有多强。 OBE 的引擎调度机制说到开源引擎，首先就要说一下 OBE，这是最早一款支持 XPDL 的开源工作流引擎。可惜由于没有良好的持续维护，到如今，虽然 Adrian 依然还在对其进行一些补充和修改，但已经掩饰不出其“落寞”的容颜了（http://blog.csdn.net/james999/category/57982.aspx）。的 run 方法。采用遍历循环的方式，这个遍历机制就是： OBE 的引擎运转调度算法是很简单的，其所有的调度规则都是依据于 WorkflowRunner 类 /***** 摘自 WorkflowRunner 类的 run 方法 ****/ while (!_activityStack.isEmpty()) { //_activityStack 中暂存着需要被激活的活动实例 ActivityContext ap = (ActivityContext)_activityStack.pop(); _ctx.setActivityContext(ap.activity, ap.instance); //虽然叫 execute，但是其实际上是一个激活活动实例的行为 executeActivityInstance(ap.activity, ap.instance); } /* 在初始化任何一个活动实例后，将这个活动实例放入_activityStack 这个堆栈中。然后调用 WorkflowRunner 的 run 方法。在这个方法中，遍历_activityStack 堆栈中的活动实例，进行运行。 */ StartProcess，startActivity，completeActivity，executeTransition 这些情况下，但是什么情况下会激活 WorkflowRunner 的 run 呢？都会造成 run 的运行。 OBE 的调度算法是很简单，但是执行这个调度过程，是比较绕的。想弄清楚到底如何运行的，大家有必要去仔细阅读阅读 WorkflowRunner 类。从 StartProcess 方法开始，跟踪起 startActivity，completeActivity，executeTransition 这几个方法之间的调用关系。这样的引擎调度机制是比较单一的。将一些控制判断交给了外围的过程。引擎本身并没有多少实际的调度，只是一个执行体：获取需要执行（激活）的活动实例，然后执行（激活）。第 4 页

工作流引擎核心调度算法与 PetriNet by 胡长城（银狐 999）补充一下，OBE 有个非常值得参考和吸收的地方，就是其 Listener 的应用。虽然 Listener 对引擎来说只是一个外设，但是却为其跟踪整个引擎得调度留下了很多可扩展接口。当然 OBE 内核主要是两个类：WorkflowRunner（负责引擎调度）和 EngineContext（运行环境）。 Shark 的引擎调度机制和 OBE 同样支持 XPDL 的模型描绘语言的还有一个引擎 Shark，Shark 是目前体系结构最为庞大和完善的开源工作流引擎。不光提供了对分布式的支持（基于 Corba），而且提供了多线程的事务安全控制。 Shark 的内部调度机制也比较简单，与 OBE 类似。Shark 的整个调度方法也基本上是基于 WfProcessImpl 内的 run 方法，也采用的是遍历循环的方式。只是 OBE 是遍历待激活的活动实例，而 Shark 是遍历已经完成的活动实例，然后往下推进。—— 估计 Shark 是故意为了避免与 OBE 类似，所以选择了这么一种算法。因为你会发现，他们的执行推进机制是较为相像的。 Shark 遍历循环的机制是： /***** 摘自 WfProcessImpl 类的 run 方法 ****/ protected void run (SharkTransaction t, WfActivityInternal lastFinishedActivity){ //如说是启动流程，启动流程实例的时候，不指定 lastFinishedActivity if (lastFinishedActivity==null) { Set starts=getProcessDefinition(t).getStartingActivities(); for (Iterator it=starts.iterator(); it.hasNext();) { startActivity(t,asDefId,actDef,null); } } //开始遍历已经结束的活动实例 while (lastFinishedActivities.size()>0) { if (!state.equals(SharkConstants.STATE_OPEN_NOT_RUNNING_SUSPENDED)) { //执行当前活动实例后续的行为 queueNext(t, (WfActivityInternal)lastFinishedActivities.get(0)); lastFinishedActivities.remove(0); } else { return; } } } /* 任何一个活动点完成之后（不论是 Complete 还是 Terminate），会将自身放入 lastFinishedActivities 列表中，然后调用 run 方法，促发对这个列表的循环遍历。 */ 有兴趣对这方面研究的，可以看看 WfProcessImpl 内的 start、run、activity_complete、 activity_terminate 这几个方法。第 5 页

工作流引擎核心调度算法与 PetriNet by 胡长城（银狐 999）从调度机制上说，shark 和 obe 基本雷同。甚至可以看到，其两个运行类都基本上有些类似：shark 是 WfProcessImpl 类， obe 是 WorkflowRunner 类。两个类都是即包含了调度的前推因素（比如起动流程实例、活动实例结束等方法），也包含了调度的规则运算（run 方法）。唯一不同的就是，shark 是对已经完成的活动实例进行遍历，然后前推；而 OBE 则是对需要激活的活动实例进行遍历，进行前推。点评： OBE 和 Shark 的 run 调度方法，是比较常用的调度机制。首先效率上比较还是可以，其实比较直观，也容易理解。而且连个引擎的执行机制有一定的雷同，这可能是由于两者都采用 XPDL 的缘故。但是，受他们调度机制的影响。OBE 和 Shark 是很难支持复杂的运转模型，比如“抢占模式（Workflow Pattern 中叫延迟选择）”。 OSWorkflow 的引擎执行机制 OSWorkflow 与其说是一个工作流引擎，不如说是一个“可嵌入式状态机”。其机制并不类似于我们通常所说的“流程”。其是以“动作（Action）”作为驱动的。所以 OSWorkflow 用在如“bug 跟踪”等处理流程中，是非常适合的。从狭义上说，OSWorkflow 是不存在什么调度机制的。如果硬要说的话，那么就可以从 AbstractWorkflow 这个类的两个方法来看：doAction 和 transitionWorkflow。—— OSWorkflow 应该说是一个执行机制：执行某一个 Action，并将状态从 A 转变为 B。这个状态的转变，可能是从一个 step 的某一个 status 变为另一 status；也可能是从一个 step 的某一个 status 变为另一个 step 的某一个 status。（注：对 osworkflow 来说，step+status 表现为一个 state）。在这种状态变迁过程中，会执行一系列的 Function。当然，OSWorkflow 有很大的灵活性取决于其 Function 机制。这种 Function 机制，有兴趣的可以参考参考。最近很多人询问我，是否可以将 OSWorkflow 用于他们的办公自动化系统中。其实这方面 OSWorkflow 处理起来并不是很适合，通常一个 OA 的审批流程是很难用 OSWorkflow 做的完美的。 JBpm 的引擎执行机制如果大家对 UML 的 Activity Diagram 很熟悉的话，理解 jBpm 就易如反掌了。在 jBpm 中也应用了 Token。但是这个 Token 和 PetriNet 的概念和语义是不同的。jBpm 的 token 是用于表示“任务分配给某一个 actor（执行者，可以是人、系统等等）的依据”，也就是说，只有某一个 actor 拿到 token，才有可能去执行任务。—— 当然，由于 jBpm 这一块的算法，也局限了 jBpm 的复杂逻辑处理。从狭义上说，jBpm 这个也不能算是什么调度机制，也只能说是执行机制。只是这个执行第 6 页

工作流引擎核心调度算法与 PetriNet by 胡长城（银狐 999）机制要比 OSWorkflow 复杂很多。OSWorkflow 的推进执行机制是 Action 的执行，而 jBpm 的推进机制则是 Token 的转移。在往下阅读阅读的时候，大家有必要把 jBpm 的一些基本元素和理念搞懂。可以参考： http://blog.csdn.net/james999/category/57982.aspx。首先需要说明的是，jBpm 在将任务分配给某一个 Actor（也就是 jBpm 所描述得执行者）的时候，也会将一个 Token 对象分配给这个 Actor。不论这个 Actor 是执行“接受任务”还是 “提交任务”，其首选都必须获取一个 ExecutionService 对象（当然，每一个 Actor 在获取其所需要执行的任务的时候，也就是获取一个 token 对象标识，那么这个时候， token 的作用又似乎类似于我们通常所理解的 WorkItem 意图）。 /***** jBpm 如何开发调用****/ ExecutionService executionService = JbpmServiceFactory.getInstance().openExecutionService(actorId); InvocationLog invocationLog = null; //如果是启动流程实例 invocationLog = executionService.startProcessInstance( definitionId, variables, transitionName ); //如果是结束任务 State（State 是 jBpm 的任务点，不要理解成了状态） invocationLog = executionService.endOfState( tokenId, variables, transitionName ); 当然，看到这儿，大家一定很关心，这个 Token 到底是如何产生的？ jBpm 引擎会在 start of Process Instance 的时候，产生一个 root-token。并把这个 root token 放入 ExecutionContext 中，而这个 token 对象会在流程实例运行过程中，跟随着转移，从而来表示任务的转移。先来看看流程实例在 ExecutionService 中是如何启动的： /***** 摘自 ExecutionServiceImpl 类的 startProcessInstance 方法 ****/ //直接构造流程实例对象， //并且在构造过程中，产生一个属于这个流程实例的 Token 对象 ProcessInstanceImpl processInstance = new ProcessInstanceImpl( definition ); TokenImpl rootToken = (TokenImpl) processInstance.getRoot(); //创建执行环境对象 ExecutionContextImpl executionContext = new ExecutionContextImpl( actorId, this, rootToken ); //获取后续 Transition，然后将当前执行环境赋予此转移 TransitionImpl transition = ((StateImpl) definition.getStartState()). getLeavingTransition( transitionName ); transition.acceptToken( executionContext ); /* 第 7 页

工作流引擎核心调度算法与 PetriNet by 胡长城（银狐 999）又是 ExecutionContext,这一块很多引擎都维护了一套执行环境对象,比如 OBE 中的 EngineContext */ 让我们再来看看，如果一个 State 被结束了，那么在 ExecutionService 中是如何驱动的： /***** 摘自 ExecutionServiceImpl 类的 endOfState 方法 ****/ //首先需要构造一个执行环境对象 ExecutionContextImpl executionContext = new ExecutionContextImpl( actorId, this, token ); //获取 Token 所在的 State StateImpl state = (StateImpl) token.getState(); //转移 Token TransitionImpl transition = state.getLeavingTransition( transitionName ); transition.acceptToken( executionContext ); 接下来让我们跟踪一下 Transition 到底干了些什么： /***** 摘自 TransitionImpl 类的 acceptToken 方法 ****/ public void acceptToken( ExecutionContextImpl executionContext ) { //为当前的执行环境对象设置下一个节点。 //在 jBpm 中，用 Node 对象来表示抽象的任务点 executionContext.setNode( to ); //下一个 Node 节点来执行接受 Token 的行为 to.acceptToken( executionContext ); } /* 经过层层执行，一个 token 对象就由一个 state 转移到下一个 stata 了，并在 state 的 acceptToken 方法中分配给一个 Actor。 */ 补充一下，jBpm 中主要有如下几种节点：判断点（Decision），分支（Fork），聚合（Join），状态点（State），其中状态点就是我们通常所理解的活动点（Activity）。而对于 State 也有四个基本类型：StartState（启动节点），EndState（结束节点），ProcessState（子流程节点），Milestone （里程碑节点）第 8 页

分享到：

赞收藏

资料库

工作流引擎核心调度算法与PetriNet_胡长城.pdf

相关推荐

开发技术

热门标签

最新资料