（计算机科学与技术专业论文）分布式协作工作流技术研究.pdf

国防科技大学研究生院学位论文摘要工作流技术是实现企业业务过程建模、优化、管理、集成、自动化的核心技术。作为分布式的应用平台，工作流管理系统任务处理能力即吞吐能力是一个重要的性能指标，目前，已有的工作流管理系统在这方面存在较大的不足，成为工作流管理系统广泛应用的严重障碍。本文研究了工作流系统的协作方式和负载平衡技术，定义了工作流系统的负载凶子，给出了一个分布式协作工作流系统模型，并结合工作流流程逻辑，提出了分布式工作流系统负载平衡( d c w f l b ) 调度算法，并开发实现了一个分布式工作流系统。实验表明分布式协作工作流系统有效地扩展了单个工作流系统的吞吐能力。本文将时间有色p e t r i 网的形式化设计方法引入到分布式协作工作流系统的负载平衡的建模中，应用时间有色p e t r i 网理论给出了d c w f l b 的t c p n 模型，该模型由业务流程信息、负载调度算法等构成。本文中详细介绍了d c w f l b 的t c p n 模型工作机理，并利用d e s i g r d c p n 的模拟和出现图两种分析方法分析了该模型的有关性质。关键词：工作流，负载平衡，负载因子，协作方式，时间有色p e t r i 网第1 页国防科技大学研究生院学位论文a b s t r a c tw o r k f i o wt e c h n i q u ei sac o r et e c h n i q u ew h i c hi m p l e m e n t sm o d e l i n g ，o p t i m i z a t i o n ，m a n a g e m e n t ，i n t e g r a t i o na n da u t o m a t i z a t i o no fe n t e r p r i s eb u s i n e s sp r o c e s s a tp r e s e n t ，m a n yw o r k f l o wm a n a g e m e n ts y s t e m s ( w f m s ) h a v ed e f i c i e n c i e si nt h e i rc a p a b i l i t i e s ( i e t h r o u g h p t i t ) f o rh a n d l i n gt a s k s ，w h i c hh a n d i c a pt h ew i d ea p p l i c a t i o no fw f m s t h i sp a p e rd i s c u s s e st h ec o l l a b o r a t i o na n dt h el o a db a l a n c i n gt e c h n i q u ef o rd i s t r i b u t e dc o l l a b o r a t i v ew o r k f l o wm a n a g e m e n ts y s t e m ( d c w f m s ) f i r s t l y , l o a di n d e xi sd e f i n e dt om e a s u r et h el o a dl e v e l so faw o r k f l o we n g i n et h e na l la r c h i t e c t u r ef o rd i s t r i b u t e dc o l l a b o r a t i v ew o r k f l o w sw i t hl o a db a l a n c i n gm a n a g e ri sp r e s e n t e d a c c o r d i n gt ob u s i n e s sl o g i c ，al o a db a l a n c i n gs c h e d u l i n ga l g o r i t h mf o rd c w f m si sp r o p o s e d f h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ed c w f m sp r e s e n t e di n t h i sp a p e rh a sh i g h - t h r o u g h p u tc o m p a r e dt ot h es i n g l e - e n g i n ew f m s t h i sp a p e rd e a l sw i t hm o d e l i n ga n da n a l y s i so ft h el o a db a l a n c i n gb a s e do nd c w f l b at i m e dc o l o u r e dp e t r in e tm o d e l ( t c p nm o d e l ) s u i t e df o rp e r f o r m a n c ea n db e h a v i o u r a la n a l y s i so fd c w f l bi sp r e s e n t e d t h et c p nm o d e lc o v e r sb u s i n e s sp r o c e s si n f o r m a t i o na n dt h el o a db a l a n c i n gs c h e d u l em e t h o d b ym e a n so fs i m u l a t i o n sa n do c c a l t e u c eg r a p ha n a l y s i so f t h ec p nm o d e l ，t h i sp a p e ri n v e s t i g a t e st h ev a l i d m i o no fl o a db a l a n c i n gm o d e l k e y w o r d s ：w o r k f l o w ，l o a db a l a n c i n g ，1 0 a di n d e x ，c o l l a b o r a t i o n ，p e t r in e t ，t i m e dc o l o u r e dp e t r in e t第1 i 页国防科技人学研究生院学位论文图目录图1 1 工作流管理系统功能交互关系图图2 1 单引擎工作流系统架构示意图图3 1 分布式协作工作流系统架构示意图图3 2 负载平衡调度顺序图图3 - 3 工作流引擎体系结构图图3 4 引擎服务器顶级用例图图3 5 顶级包图图3 6s e r v e r 包图图3 7e n g i n e 包图图3 8e n g i n e 主要类图图3 9 调度器队列示意图图3 1 0n o d e 包图，图3 “l b s 包主要类图图3 1 2 节点调度执行顺序图图3 1 3 负载平衡控制器主要类图图3 1 4 业务流程图一图3 1 5 实验结果折线图图3 1 6 业务流程图二图4 1t o p 页图4 2p r o c e s s i n f o 页图4 3l b s c h e d u l e r 页图4 4 出现图分析部分报告第i i i 页2他m堪m拇如控拍”弭弘帖档如”国防科技大学研究生院学位论文表目录3 1 包信息表( d c w fb tp a c k a g e l n f o ) 3 2 模板信息表( d c w fb tt e m p l a t e l n f o ) 3 3 工作流建模时变元信息表( d c w fb tv a r i a b l e i n f o )3 4 节点建模时信息表( d c w fb tn o d e l n f o ) 3 5 流程信息表( d c w f r t p r o c e s s l n f o ) 3 6 工作流运行时变元信息表( d c w fr tv a r i a b l e i n f o )3 7 节点运行时信息表( d c w fr tn o d e l n f o ) 3 8 节点运行时历史信息表( d c w fr tn o d e i n f o h i s ) 3 9 任务实例信息表( d c w fr tt a s k l n f o ) 一3 1 0 任务执行中间结果表( d c w fr tt a s k m i d d l e r e s u i t )3 1 1 定时信息表( d c w fr tt i m e r l n f o ) 3 1 2 事件等待信息表( d c w fr te v e n t w a t c h l n f o ) 3 1 3 实验数据一3 1 4 实验数据二4 1 完全出现图算法4 2 声明4 3 对性质a 的自定义查询4 4 对性质b 的自定义查询4 5 对性质c 的自定义查询第i v 页2 72 82 82 93 03 13 l3 l3 23 23 23 33 53 64 34 65 25 25 3表表表表表表表表表表表表表表表表表表表独创性声明本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文题目：金查基土盘丝兰佳逾越盔盟窒学位论文作者签名：童：查堕1日期：2 m 萝年位月z 6 日学位论文版权使用授权书本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密学位论文在解密后适用本授权书。)学位论文题目：佥壶盛垫堡曼佳逾挂盎盟窥学位论文作者签名掳目作者指导教师签名：星型日期：妒f 年1 2 月，日日期：2 。f 年，2 - 月2 么日国防科技大学研究生院学位论文第一章绪论1 1 研究现状工作流是针对工作中具有固定程序的常规活动而提出的一个概念，通过将工作活动分解定义良好的任务、角色、规则和过程来进行执行和监控，达到提高生产组织水平和工作效率的目的，工作流技术为企业更好地实现经营目标提供了先进的手段。工作流的诞生是因为人们逐渐认识到业务流程的管理已经成为目前信息系统开发中的突出问题。由于当前的组织机构能够比以前提供更多的产品和服务，并且产品和服务的生命周期也大大缩短，因而，导致了组织机构内部的业务过程数量比以前大大增加。在新的业务模式下，传统专的业务流程系统已经不能适应用户的需要，需要有专门的流程管理工具来支持一般的业务流程设计和执行管理，这就是工作流管理系统i ”。工作流技术的迅速发展随之而来也产生了工作流管理技术以及相关产品的标准化问题。1 9 9 3 年工作流管理联盟的成立标志着工作流技术开始进入相对成熟的阶段。为了规范工作流管理系统的设计和实现不同工作流产品之间的互操作，该组织成立后颁布了一系列工作流技术及产品的标准，包括工作流参考模型、工作流术语表、工作流管理系统各部分间的接口规格、不同工作流产品的互操作性标准等。工作流管理联盟给出的工作流定义是：工作流是指整个或部分经营过程在计算机支持下的全自动或半自动化，在实际情况中可以更广泛地把凡是由计算机软件系统( 工作流管理系统) 控制其执行的过程都称为工作流。工作流技术是实现企业业务过程建模、业务过程优化、业务过程管理与集成、最终实现业务过程自动化的核心技术，或者说它是企业资源管理、电予商务等应用的核心技术之一。利用工作流技术，并与其它的应用系统有效地集成，可以生成符合企业需求的各种业务管理系统，如办公自动化系统、客户关系管理系统、供应链管理系统、e r p 系统、项目管理系统、电子商务系统等。这些以工作流技术为核心的业务管理的最大特点是它们具有良好的灵活性，可以依据用户的具体需求，快速生成满足各自需求的应用系统。用于实现工作流技术的软件被称为工作流管理系统，w f m c 给出的关于工作流管理系统的定义是：工作流管理系统是一个软件系统，它完成工作流的定义和管理，并按照在计算机中预先定义好的工作流逻辑推进工作流实例的执行。工作流管理系统是对具体业务流程的一种抽象，它把业务流程的共性和特性相剥离，对流程实现了统一、一致性的管理【2 】。虽然不同的工作流管理系统具有不同的应用范围和不同的实施方式，但是它们具有很多共同的特性。从比较高的层次上来抽象地考察工作流管理系统，可以发现所有的工作流管理系统都提供了以下三种功能：f 一)建立阶段功能主要目标是通过分析、建模及其系统定义手段将现实世界的业务流程转化成某种能够第1 页国防科技大学研究生院学位论文被计算机处理的形式化表示。这种形式化表示称之为流程横板。流程模板中包含对业务流程中的各个任务步骤的描述、同这些步骤相关的各种计算机或人工操作、以及在各个任务步骤之间进行切换的各种控制规则。流程模板所定义的，实际上就是控制工作流流程执行的各种参数。( 二)运行阶段的控制功能在一定运行环境下，工作流程的管理及其任务步骤之间的状态转换。运行时控制系统将解释流程模板，完成流程模板实例的创建和控制，调度流程中各任务步骤，为所涉及到的工作流用户生成待处理的任务，并在合适的时机调用有关的应用程序资源。将这些服务统称为”工作流执行服务”。工作流引擎是工作流运行时控制系统的核心部分，各种流程实例的执行都由它负责完成。( 三)运行阶段的人机交互功能主要完成对工作流实例执行流程中各种任务的处理。在流程实例的执行过程中，经常需要用户通过某种应用程序来完成工作流模板所要求完成的处理或操作，例如填写表单，或使用某个应用程序生成新的文档或处理其它行为传递过来的文档等。另外工作流执行服务也可能需要自动调用有关的应用对数据进行处理，如将某些数据写入到某个数据库系统中，或调用某个应用程序对数据进行转换等。所有这些构成了运行时交互功能的主要内容。这三个功能的交互关系如下图1 i 所示：图1 1 工作流管理系统功能交互关系图目前，工作流研究主要分为三个方面：第一方面是工作流的理论基础，包括工作流管理系统的体系，模型与定义语言( 工作流的建模方法、工作流模型的形式化表示、工作流定义语言3 1 ) 等的研究。这一部分工作目前相对来说比较薄弱，还有许多问题需要进一步研究。第二方面是工作流的实现技术，包括工作流的事务特性、各种先进软件技术的应用、工作流仿真。这方面研究工作主要是提高工作流系统的性能，尤其是提高工作流管理系统第2 页国防科技大学研究生院学位论文的可靠性及其在处理大规模复杂的且具有并行业务的流程方面的能力。第三方面是工作流技术的应用，包括工作流实施技术、在不同领域的应用方法、应用软件集成等。这方面研究的目的是发挥工作流管理系统的优势，为解决具体应用领域的问题提供有效的手段1 4 j 。工作流技术在某种程度上已进入成熟阶段，现阶段工作流产品能够支持一定应用范围内的应用。文献5 ，6 ，7 1 详细说明了工作流技术研究进行的进展和状态。目前，国内外一些公司、研究机构基于国际工作流管理联盟制定的标准推出了各自的工作流产品，较为著名的有i b m 公司a l m a d e n 研究中心的e x o t i c a l 引、美国佐治亚大学的m e t e o r 【9 1 研究项目、美国普度大学开发的c o r b a f l o w 系统i l0 j 等等。1 2 立题依据企业的业务过程是由大量业务人员在多个并发的工作流实例共同驱动下完成的。因此，工作流服务器必须要承受很大的负载。以处理业务过程的一个活动为例，完成这项活动可能需要在工作流服务器和客户之间传递多个消息，其中可能包括：传输活动的输入和输出数据更新不同业务人员的工作项列表调用外部应用系统协助业务人员完成工作流活动交换工作流系统和外部数据源之间的数据显然，如果并发的工作流实例增长到一定数量时，其开销极可能使工作流服务器和通信子网陷于瘫痪。因此，问题的一个解决方法就是采用分布式的工作流管理系统的协同实现。当单个工作流系统超过安全负载时，其运行实例就迁移到其它目标服务器上。来自并行执行分支的活动可由不同服务器控制。在工作流中，一项任务的执行者往往不是固定的，在工作流定义中，有一个叫做角色的概念，所谓角色，是指具有某种共同属性的任务执行者的集合，比如经理就可以是一种角色，当一项任务要求需要经理执行时，显然这时候会有多执行者供系统选择。最佳的选择方案当然是能够让各个经理手头的任务量均匀化，这样，任务将会有最短的平均等待时间，或者说系统将会获得最快的响应速度。对于不需要人员参与的自动化任务同样具有类似的情况，只是这时的候选执行对象变成了服务程序。以上就是单引擎工作流管理系统中的负载平衡问题的大致情形。可以看出，单引擎时的负载平衡问题与一般情况下的集群系统、局域网分布系统在形式上基本相同。主要的区别在于，非工作流系统的节点间的对称性要大大高于工作流系统，在非工作流系统里面，任务的执行者具有较大的选择余地，而在工作流中，任务却要受到流程逻辑的严格约束。对于负载平衡，实际上可以分解为五个更加细致的子问题：( 1 ) 如何定义工作流系统负载，它的基本组成单元如何定义，组成单元的执行状态如第3 页国防科技大学研究生院学位论文何定义( 包括运行的上下文，工作流控制数据，任务数据等) 。( 2 ) 如何发现负载不平衡，即确定哪台机器超载，只有这样，才能知道哪台机器有平衡的必要，从而使任务调度目的明确。( 3 ) 如何进行负载平衡，即系统的不平衡状态已经出现，怎样让它转变到平衡的状态。一种直观的想法是将不平衡机器上的部分任务转移到别的机器上去。应该说，这是负载平衡的关键和难点。要考虑以下几点：a ) 如何传输节点状态数据信息；b ) 任务迁移要对其它工作流系统透明，即迁移不影响其它工作流系统的正常活动；c ) 确定什么时候做迁移以及迁移到哪个工作流系统以获取更好的性能。d ) 迁移后的节点什么时候可以开始在其工作流系统执行。( 4 ) 如何预测不平衡，正常情况下不采取负载平衡策略，当能够预测到哪台机器即将超载时，再采取措施减轻它的负担。这样，整个系统就可以始终保持平衡。它的困难在于，实际情况中的不确定因素太多，预测的准确度会受到很多因素的干扰。( 5 ) 如何进行预防，如果从一开始就对负载进行了很好的分配，那么，系统就不会出现不平衡的情况。从策略上区分，负载平衡方法可以大致分为两类：预防型负载平衡( 又称静态负载平衡) 和任务转移负载平衡( 又称动态负载平衡) 。在单引擎的工作流管理系统中，控制节点掌握着系统的全局信息，因此，可以比较好地了解系统的负载分布情况，及时地进行有关的预防工作。不过，在大型企业中，当工作流环境必须由多个工作流管理系统共同支撑时，单纯的预防型负载平衡策略就不能很好的发挥作用了。这时候，任务的转移常常会成为必然的选择，例如，一个工作流管理系统因为任务过多，不得不把它的一些流程转移到其它的工作流管理系统上，这些流程可能是完整的工作流实例，也可能是执行到路途的实例。另一种更加复杂的情况是，一个流程本身就是跨越工作流管理系统边界的，即它的任务本来就分布在多个工作流管理系统中，这样的流程在任务转移上将牵扯到更多的引擎问的协作过程，相应的也会有更大的系统开销。任务转移型负载平衡的使用通常需要更加的慎重：首先，与任务转移的内容不但包括任务请求，还要转移各种中间数据包括运行的上下文；这些做法的复杂程度有时会超过任务本身，结果使算法的效果大大折扣以至于失去原有的意义。负载平衡机制还能够对意外的故障进行妥善地处理，当工作流系统中的一个节点失效时，其它的正常节点可以很快的替代它完成被中断的任务，使系统具备良好的容错能力。负载平衡方法及其实现技术长期以来一直是分布式并行计算【1 ”、数据库系统f 1 2 1 、中间件【”1 、w e b 服务器集群【”l 、网络流量控制、流程管理1 1 5 i 等不同领域研究者所研究的课题。在一个通用分布式系统中使其工作负载平衡，首先需要的是选取合适的负载因子来描述负载标准。其次需要获取单个系统的当前负载信息，接着应设计负载平衡调度算法使其负载在分布式系统内进行迁移，最后需要设计负载平衡子系统( 或组件) 与系统集成，这样当负载策略有变时，不影响整个分布式系统结构稳定性。第4 页国防科技大学研究生院学位论文工作流系统负载平衡技术同大多分布式系统一样有着诸多同样的挑战性，但是工作流系统负载平衡有着自身的特点。目前工作流这块领域研究并不多，类似相关工作在惠普实验室做过研究。文献 1 5 j 提出了衡量工作流负载的因子并提出了一个工作流负载平衡的集群架构和负载平衡的调度算法。该文负载平衡调度算法是以流程实例为基础而不是以流程节点为基础，粒度较粗，且调度时刻是在流程实例化时进行，是一种静态负载平衡策略，它没有考虑到单引擎在运行过程中流程实例中运行节点的动态迁移过程。1 3 主要工作本文的主要工作包括工作流系统负载的提取、负载平衡模型和应用时间有色p e t r i 网对负载调度算法建模和有关性质分析。主要工作分为以下几个方面：( 1 ) 提出了工作流系统负载因子的计算方法本文以单工作流系统的流程模型为基础，深入分析了单工作流引擎的运行、调度原理，提出了单工作流系统的负载因子的计算方法。工作流系统负载因子值受正在实例化的流程数、非任务节点数，人工型任务个数、自动型任务节点数及其运行工作流系统的硬件平台等因素的影响，较客观、科学计算出工作流系统的负载因子值。( 2 ) 提出了分布式协作工作流负载平衡调度算法本文结合业务流程模型特点从四个过程方面入手，给出了分布式协作工作流系统的负载平衡调度算法，负载平衡调度算法主要涉及流程请求实例化、计算引擎服务器负载、业务流程节点解析和流程节点动态执行调度四个算法。( 3 ) 实现了分布式协作工作流系统基于j 2 e e 技术本文实现了分布式协作工作流系统，分布式协作工作流系统系统由多工作流引擎、负载平衡控制器组成。本文详细定义了各组成部分的功能。在此系统上本文给出的实验表明分布式协作工作流系统有效地扩展了单个工作流系统的吞吐能力。( 4 ) 对负载平衡算法形式化建模和有关性质分析将时间有色p e t r i 网的形式化设计方法引入到分布式协作工作流系统的负载平衡的建模中，应用时间有色p e t r i 网建立了基于负载平衡调度算法的形式化模型。分析研究了d c w f l b 系统时间有色p e t r i 网模型的性质，用模拟和出现图分析方法证明了采用负载平衡调度算法d c w f l b 系统具备有界性、活性、公平性、等重要性质，从而对负载平衡调度算法的有关性质进行了分析。1 4 论文结构整个论文共分为五章，其余各章内容安排如下：第二章介绍单引擎工作流系统的系统架构，详细介绍了单引擎工作流系统每个组成部分的功能，并介绍了系统的流程模型。第5 页国防科技人学研究生院学位论文第三章讨论了工作流系统的协作方式和负载平衡技术，定义了工作流系统的负载因子，给出了一个分布式掷作工作流系统模型，并结合工作流流程逻辑，提出了分布式工作流系统负载均衡调度算法，并在单引擎工作流基础上开发了分布式协作工作流系统，同时做了各种实验，其实验表明分布式协作工作流系统有效地扩展了单个工作流系统的吞吐能力。第四章将时间有色p e t r i 网的形式化设计方法引入到分布式协作工作流系统的负载平衡的建模中，应用时间有色p e t r i 网理论给出了d c w f l b 的t c p n 模型，该模型由业务流程信息、负载调度算法等构成，论文中详细介绍了d c w f l b 的t c p n 模型工作机理，并利用d e s i g n c p n 的模拟和出现图两种分析方法分析了该模型的有关性质。最后第五章总结了本文研究工作的主要贡献和不足，并对将来的工作予以展望。第6 页国防科技大学研究生院学位论文第二章单引擎工作流系统2 1 系统架构图2 ，l 单引擎工作流系统架构示意图文献 1 6 1 中单个工作流管理系统i n t e l l i f l o w 架构示意图如图2 1 所示，它由工作流引擎、业务管理、监控管理、流程设计子系统等组成。 流程设计它是工作流平台重要组成部分，也是实施工作流管理的起点。借助工作流模板定制工具，业务流程将被直观、图形化地建立起来，进而帮助人们理解流程元素间的复杂关系。模板定义可以使用图形化的描述工具来对一个流程实体中的各个元素进行表达，使工作流引擎能够根据模板定义生成的结果进行处理。平台采用x m l文档格式保存工作流模板，x m l 模板交由工作流引擎解释和处理。业务处理模块对登录的用户进行身份验证和角色识别，并根据用户所具有角色，显示该用户的工作项列表( 待办事宣) ，业务处理客户端是在人工型活动中与最终用户交互的第7 页国防科技大学研究生院学位论文软件实体，它能够与工作流引擎交换数据，提供用户参与的界面，或者直接激活预先定义的用来完成任务的其它应用程序。工作流引擎它是工作流平台系统中为业务流程实例和任务实例提供运行环境的软件服务，是核心部分，它主要提供的功能是：解析工作流模板定义；控制工作流实例的创建、激活、挂起和终止等：在任务之间导航，包括各种工作流模式的实现，控制实例生存期：提供用户交互接口，确定用户的工作项列表，并提供用户工作到达；维护工作流控制数据和相关数据，为应用程序或用户传递相关数据；提供激活外部应用程序和链接工作流相关数据的接口；为超级用户提供监控、管理和数据跟踪和分析。工作流引擎主要由流程管理、节点管理、任务管理和节点调度管理器等组成。2 2 流程模型工作流系统的流程模型描述了流程的基本定义元素及元素间相互的关系，在系统中将流程的定义称之为工作流模板，工作流模板定义了工作流的各种必要元素，如任务、路由、事件、业务操作及工作流相关数据等。工作流模板是企业根据自身需要定制的。在进行模板定义时，除了需要定义流程本身的一些必要属性之外，还需要利用各种组成元素来描述一个流程的具体执行情况，它是工作流执行的依据。工作流模板主要包括以下元素：节点：节点又分类为任务节点、路由节点、事件节点、复合节点、定时器节点、开始节点和结束节点。每个工作流模板至多只能有一个开始节点、至少一个结束节点。工作流相关变元：在业务流程处理过程中需要使用这些变元在各处理步骤之间传递信息，以及根据变元的值动态决定执行路由等。其中在路由节点中主要关心节点类型的是：a n d s p l i t ：多个工作流分支的并发执行；o r s p l i t ：从多个工作流分支选择- n 多条执行。具体选择哪些分支，取决于分支边上的条件。业务流程并行处理在单工作流系统中是串行处理的，直观上讲来自上述两类并行执行分支的活动由不同工作流引擎服务器控制执行，这样可提高系统的吞吐量和性能。在任务节点中可将所有任务划分为两大类：人工型任务：构成任务的动作当中存在人j ：型动作；自动型任务：构成任务的动作都是自动型动作。只有人工型任务才会出现在客户端应用程序的工作任务列表中，自动型任务由工作流引擎负责完成。第8 页国防科技大学研究生院学位论文2 _ 3 本章小结单引擎工作流系统是研究分布式协作工作流系统技术研究的基础，在本章中讨论了i n t e l l i f l o w 单引擎工作流系统的架构，并着重分析了其流程模型，在流程模型中重点分析了分支、任务节点，它是下章讨论工作流系统负载因子的基础。第9 页国防科技大学研究生院学位论文第三章分布式协作工作流系统3 1 工作流系统负载模型在考虑怎样在分布式协作工作流系统进行负载平衡之前，需要准确定义单个工作流系统的工作负载，即采用负载因子来描述单个系统的工作流负载，从工作流引擎收集得到当前的工作流负载。工作流系统的主要目的是使企业的业务流程尽可能自动化，对流程中的任务执行的条件和任务间的信息流进行明确定义，从而实现业务过程的高效运转，并能够在最大程度上实现业务过程的重用。因此，在工作流系统中其主要负载就是系统中运行的业务流程。如上一章所述，工作流的流程由各种节点组成且不同类型节点其执行时间有差异。相应地流程执行时间由各种节点的执行时间所构成。人工型任务节点在执行调度时由引擎将相应的任务发送给具有执行该任务权限的客户端应用程序的工作任务列表中，用户执行该任务的时间是无法估计的，但是其时间的长短基本不影响工作流引擎的性能，因此不考虑外部用户执行人工任务的这部分时间。而自动型任务节点则由工作流引擎调用相应的外部应用系统负责完成，其执行的时间长短影响着工作流引擎的执行性能。在工作流引擎执行流程实例过程中，首先实例化流程、创建流程运行时的上f 文环境，接着创建流程节点，系统调度是以待执行流程节点组成的一个队列。因此业务流程的执行时间主要包括流程初始化时间、非任务节点创建调度时间、人工型任务节点创建调度及任务分配时间、自动型任务节点创建调度及任务执行时间。运行工作流系统的硬件平台不同其业务流程的执行时间也不同。从上述分析可得到：影响工作流系统性能的因素有正在进行的流程实例个数、流程中活动( 待执行) 节点的类型及其数目，以及系统硬件平台性能，可用下式给出一个描述：型了1 ，瑚。= 旯( 珊f 。+ ：1 )i = 0其中死。是引擎响应用户请求所需的时间；瓦。是流程进行实例化所需时间；m 是正在进行实例化的流程个数；h 是流程中活动( 待执行) 节点的数目，正是活动( 待执行) 节点执行的时问，不同类型的节点其执行时间也有明显的不同。五是系统硬件平台性能值，硬件平台性能越高，艚就越小，反之亦然。7 赢。值越大，对用户新的请求响应的时间就越长，反之则越短。在系统中正。及r 执行时间可以看成是个固定值( 即使值有所变化，也是由于聊、肝的值所引起的) ，因此影响兀。乇要因素是m 、”和a 。第1 0 页国防科技大学研究生院学位论文由上所述，将工作流系统的负载因子f 表示为：k 2 ( m + d + 6 。)其中a 是正在进行的流程实例的权重，b ，是不同类型节点的权重，五值由系统配置得到。，值越大，表示引擎的负荷越重，对用户的响应时间就越长，3 5 节的实验结果也表明了这一点。3 2 系统架构图图3 1 分布式协作工作流系统架构示意图在原有单工作流管理系统基础上，本文开发了分布式协作工作流系统。如图3 1 所示，分布式协作工作流系统由分布式协作负载平衡控制器和多个工作流引擎服务器组成，每个工作流引擎服务器内含负载平衡管理器，在此分布式系统中工作流引擎是在i n t e l l i f l o w 工作流管理系统m 1 的引擎基础上扩展而成，扩展主要内容是在节点管理器中增加对并行分支节点的特殊处理以及将负载平衡管理器内嵌入引擎中。第1 1 页国防科技大学研究生院学位论文3 _ 3 负载平衡调度算法；蜒剑：竖墼 ；蛭照：嗲州：。r e g i s t ，m )kl 幽j 砒鸣7 i * * n i $ 舞+ 一q 告抻、：少o d i w o m j a 虬) ：j 。一| in o t i f y w o r b k 州，j； 。嘴辫2 i ji n o t j f y w o r k l o a d ( ) _ i ；， 一。，7，+ ：i n 一一h * + 。w _ “_ 一。i 。”i ” 一一一 i 、：，一一、，。7、p 里竺刚d ：”“”j；d e c i s i o n m a k e ( )； 一一7l p r o d e s s 77图3 2 负载平衡调度顺序图：7 ，t 社流c j ：，m * “j l h 、：lm 拽 - n 寓h d - t g 目l h ，l 、，一7第1 2 页拈0 jyj 叱伯一惦刈州g | j：暑_唑薹：唑啦一一一一一一圳国防科技大学研究生院学位论文采用u m l 顺序图1 1 7 j 来描述系统负载平衡调度机理，如图3 2 所示，系统工作机理从逻辑上可分为如下四个过程：过程一：工作流引擎可动态地向控制管理器注册( r e g i s t r y ( ) ) ( 反之可撤销) ，控制器中有一个负载矢量记录各工作流引擎的负载情况。过程二：系统运行时各引擎运行业务流程实例，在一定的时间间隔计算本引擎的负载，将此负载通知控制器且更新本地的负载矢量( m o d i w o r k l o a d ( ) ) ，控制器收到某引擎发送过来的负载情况后，更新控制器的负载矢量，并通知发送负载引擎之外的其它所有引擎更新其本地的负载矢量( n o t i f y w o r k l o a d ( ) ) 。过程三：当业务系统请求业务流程实例化时( i n i t p r o c e s s ( ) ) ，控制器根据当前的负载矢量值及其负载平衡策略决定由哪一个引擎进行实例化( d e c i s i o n m a k e ( ) ) 。过程四：( 1 ) 弓f 擎在动态运行流程实例中，当负载超过其安全负载时，根据本地的负载矢量值及其负载平衡策略( 如实例迁移的网络开销等) 决定实例节点及其上下文迁移到哪个引擎中去d e c i s i o n m a k e ( ) ) ，具体是：首先获取迁移到哪个引擎，然后两者之间进行协商( n e g o t i a t e ( ) ) ，如同意后再在两者之间建立网络连接( c o n n e c t ( ) ) ，接着将节点及其上下文迁移到该引擎中去( t r a n s f e r n o d e ( ) ) ，目标引擎接收到节点后向源引擎发送确认消息( a c k ( ) ) 。( 2 ) 引擎服务器在解析业务流程中节点类型是a n ds p l i t 或o rs p i 。i t 节点时，采用业务流程节点解析算法，根据各个引擎服务器负载情况，尽可能将并行节点的各个分支放在不同的引擎服务器上执行( d e c i s i o n m a k e ( ) ) ，使得执行的总时间和对用户的响应时间最短。从上分析，负载平衡调度主要涉及流程请求实例化、计算引擎服务器负载、业务流程节点解析和流程节点动态执行调度四个算法：令乒 s 川g 垒 为引擎服务器集合，其中k 是引擎服务器的总数。l j = p j ，i1 ! m ) 是第，台引擎服务器上正在进行实例化的流程集合。其中，l 垡t ，k 是引擎服务器的总数，m 是各引擎服务器上正在实例化的流程个数，不同的引擎服务器，m 值可能不同。y = ( v i ，f 2 ) 记录各引擎服务器的负载矢量，u 表示第j 台引擎服务器的负载值。s f l v = ( 妒v ，s t i r ：，妒v 女) ，记录各引擎服务器的安全负载矢量，, s f l v ，表示第f 台引擎服务器的安全负载值，k 是引擎服务器的总数。m = 勘ll s 匹 是第台引擎服务器待处理队列中节点集合。其中，1 9 鱼， 是引擎服务器的总数，h 是各引擎服务器上待执行队列的节点个数，不同的引擎服务器，h 值可能不同。占= b ，f1 5 t 9 为各类型节点执行时所需负载值的集合，其中r 表示流程模板中节点的类型数。第1 3 页国防科技大学研究生院学位论文c ：节点迁移代价，是一个负载值，主要由要迁移节点的数据量大小决定。n ：实例化一个流程所需的负载值，由系统配置。算法i ：流程请求实例化算法输入：负载矢量v s输帆最小负载的引擎服务器，算法：s ：2 s ii = lf o r e a c hh s s id ol f ( v ，v ，)+ l i g h t e r ( v ，叶) 表示取u ，峙值最小的序号( f 或者j )i ：2 l i g h t e r ( v ，1e l s e+ m i n f r e e d o m 0 ) 表示随机取i 或者取+ i ：2 m i n f r e e d o m ( i , )e n d i f5 ：2 e n d f o r算法2 ：计算引擎服务器负载算法产计算引擎服务器畸的本地最新负载v j ，通知平衡负载控制器，更新负载矢量v * 输入：e 、* 、v 、“口、输出：负载矢量v算法：，：= o，+ d 是实例化一个流程所需的负载因子值，卅是只的大小+ f ：= a * mf o r e a e hn r eh | d ob ，是节点n 。执行时所需的负载因子值，：= ，+ 6 ，e n d f o r。爿，lp 引擎服务器岛的负载因子值变化时更新负载矢量+ l f u 札( ”，u ，叶) ：。( ” u q ：)e n d i f国防科技大学研究生院学位论文算法3 ：业务流程节点解析算法输入：解析的节点肿m ，s输出：n算法：7 + g l ，, t y p e 表不节点类型+ ，l f ( n j r t y p e 。a n ds p l i to rn j ，t y p e 2o rs p l i t )s u b n ：= 节点n 。的条件为真的后继节点集 ；采用贪心算法将集台s u b n 中各节点分配给不同的引擎服务器上的待执行节点队列里。e i 。s e将节点 。的后继节点加入到待执行节点队列，。e n d l f算法4 ：节点动态执行调度算法p 从待执行节点队列取第一个节点，节点类型为i 进行调度执行 ，输入：待执行的节点，u 、昂s f l v 、c 、v输出：n算法：p 如果节点n j ，执行时所需的负载因子值加上第j 引擎服务器的当前负载因子值大于第j 引擎服务器的安全负载蹦子值+ i f ( b l + h 印u )从算法i 获取最小负载的引擎服务器跏p 如果节点h ，迁移到s ，弓【擎服务器时所需的网络开销负载因子值加卜第i 引擎服务器的当前负载因子值大于等于第，引擎服务器的负载因子值+ ，i f ( 罐弘+ c )执行该节点，运用算法3 对该节点进行业务流程解析。e l s e将节点迁移到品引擎服务器的待执行节点队列 ，里。e n d i fe l s e执行该节点，运用算法3 对该节点进行业务流程解析。e n d l f在负载平衡调度中，其主要开销来自于算法3 ，其复杂性取决于引擎服务器个数和s “6 的大小。3 4 系统设计与实现分布式协作工作流系统采用面向对象技术进行设计和采用先进的j 2 e e 技术规范架构开发，它主要包括工作流引擎服务器系统和分布式协作负载平衡控制器两大系统。国防科技大学研究生院学位论文3 4 1 工作流引擎服务器在i n t e l l i f l o w 工作流管理系统”1 基础上，本文开发设计了分布式协作工作流系统的工作流引擎服务器。工作流引擎服务器内含负载平衡管理器，是一套开放、灵活、可扩展、性能稳定的工作流管理系统。3 4 1 1 体系结构引擎主要负责根据构造期引擎生成的模板和包的数据包和工作流模板相关数据的实例化，按照建模时定义好的流程实际执行模板中的每个节点。这个过程包括路由选择、任务的分派、任务中每个动作的执行、与用户进行交互、监听引擎外部发的消息、负载平衡管理以及整个过程中的异常处理。引擎并且为工作流监控模块提供外部接口。引擎主要包括以下主要模块：模板管理( p a c k a g em a n a g e ) 、流程管理( p r o c e s sm a n a g e ) 、节点管理( n o d em a n a g e ) 、路由管理( r o u t em a n a g e ) 、任务管理( t a s km a n a g e ) 、动作执行( a c t i o ne x e c u t o r ) 、调度器( s c h e d u l e r ) 、事件管理( e v e n tl i s t e n e r ) 和负载平衡管理( l bm a n a g e ) 。整个体系结构可以用图3 3 表示：3 4 1 2 设计与实现系统用例图图3 3 工作流引擎体系结构图图3 4 给出了引擎服务器系统的顶级用例图，共有模板管理、流程管理、节点管理、路由管理、任务管理、调度管理和负载平衡管理七个用例以及引擎、其它引擎和负载平衡第1 6 页国防科技大学研究生院学位论文控制器三个角色。顶级包图j 模板管理流程管理，7 任务管理+ + 。调度管理t。，7一，?， ，7一i。_ ，7ji? ? ? 79 蕊孝尊理、4，7 + ， u s e 毡j。、( u s e ) )、，一，引擎路由管理负载平衡管理图3 4 引擎服务器顶级用例图负载平衡控制，7器其它引擎如图3 5 所示，工作流引擎服务器的顶级包图分为五个子包图。其中：a d a p t e r 包主要定义了工作流引擎服务器调用的外部程序所遵循的接口；l b s 包主要包括负载平衡管理器管理：m o d e l 包主要包括企业的组织模型和权限管理；u t i l 包主要包括系统所用到的公用方法和接口；s e r v e r 包主要包括模板解析、工作流引擎、表达式管理、公用类等，并提供方法、接口供外部系统调用。a d a p t e rs e r v e rm o d e l图3 5 顶级包图第1 7 页国防科技大学研究生院学位论文s e r v e r 包如图3 6 所示，s e r v e r 包图分为五个子包图。其中：p a r s e r 包中主要包含负责解析工作流模板的j a v a 类；c l i e n t 包中主要提供给各类客户端调用的方法、接口，这些客户端包括工作流建模、业务处理和管理监控客户端：e n g i n e 包是服务器模块的核心包，负责流程实例的调度和执行；e x p r e s s i o n 包主要是使用j a v a c c 工具包产生的j a v a 类对流程变量、表达式进行解析计算；c o m m o n 包中主要包含上述各子包都可能使用的公共类。e n g i n e 包。p a r s e re n g i n erc l i e n t图3 6s e r v e r 包图e 冲r e s s t o n -如图3 7 所示，e n g i n e 包包括下面十一个子包：v a r i a b l e 包：管理构造期和运行期所有的工作流相关变元；p a c k 包：对包这个实体进行控制，如创建包、读取包的属性和包一级的工作流变元、查看包中实例化的模板等；p r o c e s s 包：流程( 模板的实例化) 包，负责对流程这个实体进行控制，如启动流程、取消流程、读取流程的属性和流程一级的工作流变元等等；t a s k 包：对实例化任务这个实体控制，如实例化任务、读取任务的属性和任务一级的工作流变元等；n o d e 包：管理流程中的各个节点，包括八种：s t a r t n o d e 、d o n e n o d e 、s p l i t n o d e 、j