（计算机应用技术专业论文）流程的并发与协同.pdfVIP

南京邮电大学硕士研究生学位论文 摘要 摘要 随着企业的发展以及工作流技术应用的不断深入，企业业务流程之间的协作交互不断 地加强，业务流程需要通过相互之间的协作与同步，实现企业复杂的流程活动。因此，为 了提高工作流引擎对流程对象之问协作和同步的能力，本文在染色p e t r i 网理论基础上，扩 展了多维染色t o k e n 概念，利用多维染色p e t r i 网模型对流程引擎进行分析、建模与设计。 通过引入多维染色t o k e n 以后，可以使流程引擎能够更加灵活地处理主从流程实例之间的 协调和同步。 流程引擎利用p e t r i 网分布式异步并发特性实现流程的并发，即利用染色t o k e n 的并发 调度实现不同流程实例的并发执行：同时引擎也可以通过同一库所或变迁中t o k e n 的维度 调度，实现主流程实例与其子流程实例的并发执行。对于不同流程之间的协作，引擎通过 利用触发对变迁的控制，实现了不同流程实例之间的协同功能。 整个流程引擎系统的设计采用微内核( 文献 3 5 】) 架构，其系统的核心为流程引擎内 核，引擎内核为系统的关键部件，主要负责流程的调度和执行。在引擎内核扩展基础上， 流程引擎系统实现了引擎的基本服务和扩展功能，为企业提供有效的流程解决方案。 关键词：工作流，工作流引擎，p e t r i 网，多维染色p e t r i 网，并发，协同 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fa l le n t e r p r i s e sa n dw i d e l ya p p l i c a t i o no fw o r k f l o wi ni t s b u s i n e s s ，c o l l a b o r a t i o nb e t w e e nb u s i n e s sp r o c e s s e sb e c o m e sm o r ea n dm o r ei m p o r t a n t ，w h i l e e n t e r p r i s e sh a v et oi n t e g r a t ec o o r d i n a t i o na n ds y n c h r o n i z a t i o ni nb u s i n e s sp r o c e s s e ss ot h a t c o m p l e xb u s i n e s sa c t i v i t i e sc a nb ei m p l e m e n t e df l e x i b l y t h e r e f o r e ，i no r d e rt oi m p r o v et h e c a p a b i l i t yo faw o r k f l o we n g i n ei nc o l l a b o r a t i o na n ds y n c h r o n i z a t i o na m o n gt h ew o r k f l o w i n s t a n c e s ，t h ec o n c e p to ft h em u l t i d i m e n s i o n a lc o l o r e dt o k e nb a s e do nt h ep e t r i n e tt h e o r y , a p p l i e df o ra n a l y z i n g ，m o d e l i n ga n dd e s i g no fw o r k f l o we n g i n e s ，i se x p a n d e da n di m p r o v e db y t h i sp a p e r w o r k f l o we n g i n ec o u l dp r o c e s st h ec o o r d i n a t i o na n ds y n c h r o n i z a t i o nb e t w e e nt h e m a s t e rw o r k f l o wa n dt h es l a v ew o r k f l o wm o r es m o o t h l yb yt h ea p p r o a c hp r o p o s e di nt h i sp a p e r b a s e do nt h ed i s t r i b u t e da s y n c h r o n o u sc o n c u r r e n tc h a r a c t e r i s t i co fp e t r i - n e t s ，aw o r k f l o w e n g i n ec a ng e tg o o dc o n c u r r e n tp r o p e r t y c o n c u r r e n c ee x e c u t i o ni nd i v e r s ep r o c e s si n s t a n c e sc a n b ec a r r i e do u t b yc o n c u r r e n t l y s c h e d u l e dc o l o r e dt o k e n s b yt h e i m p r o v e m e n t o f m u l t i d i m e n s i o n a lc o l o r e dt o k e n , aw o r l d l o we n g i n ec a na l s or u nm a s t e ri n s t a n c e sa n ds l a v e i n s t a n c e si nc o n c u r r e n t ，a n ds h a r es a m ep l a c es e ta n dt r a n s i t i o ns e t c o n t r o l l i n gt r a n s i t i o nb y t r i g g e r , c o o r d i n a t i o nc a nb et a k e ne f f e c tt om e e tt h er e q u i r e m e n to fc o l l a b o r a t i o na m o n gd i f f e r e n t p r o c e s si n s t a n c e s t h ew o r k f l o we n g i n es y s t e md e s i g ni nt h i sp a p e ri sm i c r o - k e r n e ls t r u c t u r e d t h ec o r eo f t h es y s t e mi st h ee n g i n ek e r n e l t h ee n g i n ek e r n e li st h ec r i t i c a lc o m p o n e n to f t h es y s t e m ，w h i c h m a i n l ys c h e d u l e sa n de x e c u t e st h ew o r k f l o w t h es y s t e ma c c o m p l i s h e st h eb a s i cs e r v i c ea n dt h e e x p a n d a b l ef u n c t i o n sb ye x t e n d i n gt h ee n g i n ek e r n e l ，w h i c hp r o v i d e st h ee f f e c t i v es o l u t i o n sf o r e n t e r p r i s e s k e y w o r d s ：w o r k f l o w ，w o r k f l o we n g i n e ，p e t r i - n e t ，m u l t i d i m e n s i o n e dc o l o r e d p e t r i n e t ，c o n c u r r e n t ，c o o r d i n a t i o n 南京邮电大学学位论文原创性：声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 罢圣日期：皇! 仝：鱼罩 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名： 买主 导师签名研究生签名： 垄工 导师签名日期：鏖! 里z ：垒17 南京邮电人学硕士研究生学位论文第一章绪论 第一章绪论 1 1 工作流技术的研究背景以及现状 工作流技术源于办公自动化技术( o a ，o f f i c e a u t o m a t i c ) ，伴随着业务流程再造( b p r ， b u s i n e s sp r o c e s sr e e n g i n e e r i n g ) 概念的兴起而逐渐发展起来的( 文献【1 】) 。工作流技术主 要功能是将企业复杂的业务分解成定义好的任务、角色，按照一定的规则和过程来执行这 些任务并对流程进行监控，从而提高办事效率、降低生产成本、提高企业生产经营管理水 平和企业竞争力( 文献【2 】) 。工作流技术已经成为企业挖掘信息系统的潜能、7 实施业务过 程再造的重要技术，并逐步成为当代组织信息系统的标准核心构件。 伴随着企业信息技术的发展，工作流技术与企业应用集成( e a i ，e n t e r p r i s ea p p l i c a t i o n i n t e g r a t i o n ) 不断地融合，进一步发展形成业务流程管理( b p m ，b u s i n e s sp r o c e s s m a n a g e m e n t ) ( 文献 3 】) 。b p m 不仅关注业务流程的自动化、流程的实时监控和流程的优 化，而且还注重跨系统的流程协作，允许业务流程以松耦合的方式将企业与客户，及其业 务伙伴联系在一起，实现包括组织内外的所有系统间的互联。b p m 的一个重要特征就是： 允许人与系统协同参与的、横亘多个组织的业务流程流转( 文献【3 】) 。目前市场上成熟的 产品包括，i b m 公司的w e b s p h e r eb u s i n e s sp r o c e s sm a n a g e m e n t ，这是一个用于企业业务 流程建模、组装部署和管理具有面向服务体系结构( s e r v i c eo r i e n t e da r c h i t e c t u r e ，s o a ) 并使用企业服务总线( e n t e r p r i s es e r v i c eb u s ，e s b ) 进行集成的应用程序的解决方案( 文 献 4 】) ；b e a 公司的a q u a l o g i cb p m ，主要是用于创建和管理分布式环境的面向服务的业 务流程( 文献【5 】) ；微软公司的b i z t a l k 主要是面向企业b 2 b 业务流程的建模、调度和管 理的工具，而且还提供了业务流程活动监控( b u s i n e s s a c t i v i t ym o n i t o r i n g ，b a m ) 和流程 的优化，提高企业业务流程的效率( 文献【6 】) 。 在工作流管理技术的理论基础、实现技术与应用等方面也取得了许多研究成果。工作 流管理联盟w f m c 提出了工作流参考模型，并且进一步标发展和完善一系列相关的标准和 规范，为工作流管理系统研究与开发提供成熟的理论参考依据( 文献【7 】) ；由w i lv a nd e r a a l s t 领导的工作流模式( 文献【8 】) 的理论研究，目的是为工作流系统和业务流程建模语言的能 力进行考察与评估，并为工作流技术提供一个统一的概念性基础，流程模式可以帮助研发 者对实际流程场景与需求有更为全面的认识，对工作流系统以及流程引擎的设计和实现有 更为深刻的理解( 文献【3 】) ；流程建模方法进一步发展成熟，并且很好地支持实际的应用， 南京邮电大学硕士研究生学位论文 第一章绪论 主要的建模方法有限状态机( f s m ，f i n i t es t a t em a c h i n e ) 、活动图( a c t i v i t yd i a g r a m ) 、事 件驱动过程链( e p c ，e v e n t d r i v e np r o c e s sc h a i n ) 和p e t r i 网，其中p e t r i 网对流程的建模 发展最为完善和成熟，它不仅可以描述复杂的流程，而且可以有效支持流程的并发建模( 文 献 9 】) ：s o a 与b m p 技术进一步融合，面向服务的流程执行语言b p e l ( b u s i n e s sp r o c e s s e x e c u t i o nl a n g u a g e ) ( 文献【3 4 】) 正逐渐成为实现企业机构内外的业务流程编制与业务协作 的基础；b p e l 不仅可以实现服务的编制和编排，而且成为了一种广义编程的手段，提高 了企业业务应用快速开发的能力，提升了企业开发效率。 国内的工作流技术研究起步比较晚，相对比较滞后国外发展水平，理论研究发展缓慢， 产品的研发比较薄弱不够成熟，现有的产品多数倾向于o a 的实现，比较成功的产品包括 西安协同数码的s y n c h r o f l o w ，基本上严格遵循w f m c 规范基础上开发的产品，有一定的 市场应用( 文献 1 0 】) ；杭州信雅达的s u n f l o w 也是发展比较迅速的产品，主要特色是采用 基于域的系统架构，支持分布式管理，并且可以支持流程仿真( 文献【l l 】) 。 1 2 课题的主要研究内容和结构安排 本课题研究的主要内容为流程的并发与协同，课题的提出主要是为了改进原有系统的 流程引擎，提高原有系统的业务流程执行效率。 原系统中流程引擎的设计基于有限状态机( f s m ) 机制( 文献【9 】) ，有限状态机机制 对复杂的业务流程描述比较繁芜，而且有限状态机难以有效地描述流程任务之间的并发以 及流程实例之间的协同。因此本文使用p e t r i 网建模方法对原有系统进行改进，使用染色 p e t r i 网工作流模型取代有限状态机模型，依据p e t r i 网的相关概念和理论，结合工作流的 理论技术，使用染色p e t r i 网理论模型对工作流引擎进行分析与建模，从而利用染色p e t r i 网的异步并发特性，有效地定义和描述流程任务之间的并发以及同步：同时，为了解决原 系统中组合业务与子业务协作与同步的问题，本文在染色t o k e n 的基础上，扩展了多维染 色p e t r i 网概念，通过p e t r i 网的多维染色t o k e n 的调度处理，有效地实现了组合对象流程 实例与子对象流程实例的协作与同步。而且，引擎还通过设计变迁的触发功能，灵活地定 义和控制流程变迁的实施，从而能够利用触发，有效地控制流程之间的协作交互，实现流 程实例之间的协同交互功能。 本课题希望通过多维染色p e t r i 网对流程引擎的改进，使引擎能够简化流程定义，提高 业务流程定义的灵活性，有效地适应企业繁重复杂的业务活动：并且使引擎能够支持多流 程实例的并发与协同，以及主从流程实例之间的协作与同步，从而增加业务流程的协作能 2 南京邮电大学硕士研究生学位论文第一章绪论 力，提高流程引擎的执行效率，提高企业生产效率，解决企业快速增长的业务流程，适应 企业发展的需求；同时也希望通过流程引擎与b p e l 的结合，使引擎能够支持流程服务的 编排和编制，从而提高企业流程的机动性和灵活性，降低业务流程实施复杂性，提升企业 跨系统的流程协作能力。 本文的组织结构如下： 第l 章为绪论，主要介绍了工作流技术的背景和意义，对工作流技术的发展现状进行 的分析，并且对本文主要研究内容和具体组织结构进行介绍。 第2 章为基础理论，主要介绍工作流和工作流管理系统的相关概念，对工作流系统的 特征、工作流参考模型和工作流相关建模技术进行论述；同时对p e t r i 网基本理论和p e t r i 网的工作流建模进行了详细分析。 第3 章主要内容为多维染色p e t r i 网的分析，以及多维染色p e t r i 网功能与作用的研究。 第4 章主要内容为基于多维染色p e t r i 网模型的工作流引擎机制和原理的分析与设计。 第5 章为流程并发与协同，主要是对流程引擎的并发与协同理论技术的分析与设计。 第6 章为流程引擎的系统设计，主要内容是在流程参考模型基础上，以微内核架构为 核心，设计与开发流程引擎系统结构和功能。 第7 章为结束语，主要是对当前工作的论述和总结，以及进一步的发展。 南京邮电人学硕士研究生学位论文第二囊基础理论 2 1 工作流技术 第二章基础理论 工作流技术是2 0 世纪八九十年代发展起来的一项新兴技术，它为实现企业经营过程 重组、经营过程自动化和过程优化和管理提供了方法和软件支持( 文献【1 1 ) 。 工作流技术主要是利用计算机科学技术，并结合企业具体开发过程与经营管理进行信 息化软件系统的应用开发，达到企业经营和生产过程全自动或半自动化的执行和管理。工 作流技术不仅仅是- f - 计算机应用技术，它还要与管理学科等其他学科紧密结合起来，是 一个涉及多学科交叉的研究领域。 2 1 1 工作流 工作流是一个比较抽象的概念，在工作流技术的发展过程中，不同研究者和厂商从不 同的角度对工作流的概念给予了描述。 工作流管理联盟( w f m c ，w o r k f l o wm a n a g e m e n tc o a l i t i o n ) 从一个相对成熟的标准上 对工作流进行了普遍适应的概括性定义：工作流是一类能够完全或者部分自动执行的经营 过程，它根据一系列的过程规则、文档、信息或任务能够在不同的执行者之间进行传递与 执行( 文献【1 3 】) 。 工作流就是业务过程的部分或整体在计算机应用环境下的自动化，就是一系列相互 衔接、自动进行的业务活动或任务。一个工作流包括一组任务及它们的相互顺序关系，还 包括流程及任务的启动和终止条件，以及对每个任务的描述( 文献【2 】) 。 2 1 2 工作流的基本概念( 文献 1 ) 一个工作流主要表现为企业的一个业务活动流程过程，其包括在计算机应用环境下自 动化任务和人工任务，用于处理业务案例。工作流主要包括如下基本概念： l 、案例 工作流系统主要是处理案例，一个具体的企业业务流程就是一个案例，例如电信的客 户关系管理系统中一个订单处理流程。每个案例都有一个唯一的标识。每个案例的生命周 期都是有限的，从开始出现在工作流系统中，直到执行结束，然后从工作流系统中消失。 4 南京邮电大学硕士研究生学位论文第二章基础理论 案例属性是一系列与案例相关的变量，能够用来管理案例，案例的属性值可以随着案例的 进展而发生变化。 2 、任务 任务是一个工作的逻辑单元，是企业的一个具体业务活动，它不可分割且必须完整 执行。如果在执行任务期间发生任何错误，那么必须返回任务执行前的状态，即任务必须 “回滚r o l l b a c k ”。任务的不可分割性依赖于定义它的环境。 任务具体分为： ( 1 ) 手动任务( m a n u a l ) ，完全由人来执行： ( 2 ) 自动的任务( a u t o m a t i c ) ，在没有人干涉的情况下执行，通常为应用软件完全基 于数据来执行任务； ( 3 ) 半自动的任务( s e m i a u t o m a t i c ) ，有人和应用程序共同参与执行。 3 、过程 某种类型的案例的执行方式由相关的过程来描述。过程指出了哪些任务需要执行，以 什么次序执行。通常，一个过程可以执行多个不同的案例，根据案例属性采取不同的措施。 由于案例属性的不同，任务的执行次序也可能发生变化。条件用来决定任务的执行次序。 本质上，过程由任务和条件构成。 过程定义了案例的生命周期，每个案例的生命周期都是有限的，都有清晰的开始和结 束，因而过程要与此相符：于是每个过程都有开始和结束，用来分别标识案例的出现和完 成。 4 、路由 过程决定了案例的生命周期，我们称之为案例的“路由”。沿着特定分支的路由决定 了哪些任务需要被执行，以及按照何种次序执行。在路由案例时，采用以下4 种基本结构： ( 1 ) 顺序路由，即按照顺序一个接个地执行。通常它们之间存在清晰的依赖关系。 ( 2 ) 并行路由，如果两个任务能够被同时执行或以任意次序执行，称之为并行路由。 ( 3 ) 选择路由，当两个或更多任务间存在选择时。该选择依可能依赖于案例相关属性值 所体现出的特定性质。选择路由，也被称为条件路由。 ( 4 ) 循环路由或迭代路由，即对一个任务进行多次反复运行的执行过程。 南京邮电大学硕士研究生学位论文第二章基础理论 5 、启动 只有当案例的状态允许时，一个工作项才能被执行。但是实际执行一个工作项，通常 还需要其他的前提，激活任务启动事件的称之为触发，即工作项由个资源或事件来启动。 其他的触发形式还包括：外部事件和某个特定时刻。因此触发分为三类：资源驱动、外部 事件、时间信号。如果工作项不需要外部激励总是必须被立即执行，则不需要触发。 2 1 3 工作流参考模型w f r m 工作流参考模型( w f r m ，w o r k f l o wr e f e r e n c em o d e l ) ( 文献【1 3 】) 为w f m c 一个重 要标准，它是工作流管理系统结构的通用描述，如图l 所示 臣困 - ? i 图l 工作流参考模型 l 、工作流参考模型数据w o r k f l o wr e f e r e n c em o d e ld a t a 工作流控制数据( w o r k f l o wc o n t r o ld a t a ) ：工作流执行服务通过内部的工作流控制数 据来辨别每个过程和活动实例的状态，这些数据由工作流执行服务进行控制。 工作流相关数据( w o r k f l o wr e l e v a n td a t a ) ：工作流管理系统通过工作流相关数据来确 定过程实例状态转换的条件，并选择下一个将执行的活动。这些数据可以被工作流应用程 序访问并修改。工作流管理软件需要在活动实例之间传递工作流相关数据。 工作流应用数据( w o r k f l o w a p p l i c a t i o nd a t a ) ：这种数据指那些由应用程序操作的数 据。它们是针对应用程序的，是企业完成具体的业务功能所需要的数据，如产品结构数据、 6 南京邮电大学硕士研究生学位论文第二章基础理论 订单数据、生产作业计划数据等。工作流管理系统无法也不需要对它们进行访问。 2 、工作流执行服务器w o r l d l o we n a c t m e n ts e r v i c e s 工作流执行服务器使用一个或多个工作流机，为过程实例和活动提供运行环境，负责 解释和激活过程定义，与过程所需的外部资源进行交互。 “工作流执行服务器”定义：由一个或多个工作流机构成的软件服务器，用来创建、 管理、执行工作流实例。在参考模型中，过程与活动控制逻辑间有一个逻辑上的分离，活 动控制逻辑构成工作流执行服务器；过程与应用工具间、与终端用户任务间也有一个逻辑 上的分离，应用工具和任务建立起对每个相关活动的处理。这种逻辑上的分离，为系统带 来了更大的灵活性。 3 、工作流引擎w o r k f l o we n g i n e 工作流引擎为参考模型的核心，引擎主要负责执行服务器中的部分或者全部运行控制 环境。工作流引擎定义：为工作流实例提供运行时期的执行环境的软件服务器或引擎。工 作流引擎主要功能包括： ( 1 ) 解释流程定义； ( 2 ) 控制流程实例的创建、激活、挂起、终止等： ( 3 ) 为流程的活动导航，对工作流相关数据进行解释； ( 4 ) 维护工作流控制数据和相关数据，在应用程序间或者用户问传递工作流相关数据； ( 5 ) 提供调用外部程序的接口，连接所有工作流相关数据。 工作流引擎主要提供完成流程案例所需的主要功能。在特定情况下，几个工作流引擎 彼此协作，每一个引擎负责案例或过程的一部分。 4 、工作流参考模型的组件接口 参考模型有5 个标准接口，这些接口标准不仅有助于提高工作流管理系统间的数据交 换，而且有利于促进完全独立于特定工作流管理系统的应用开发。 ( 1 ) 接口1 为过程定义工具，此接口提供y g j 建和修改工作流定义的工具与工作流执行 服务器之间的关系； ( 2 ) 接口2 为工作流客户端应用程序，第二个接口用于工作列表处理器和执行服务器之 间的交互； ( 3 ) 接口3 为被调用的应用程序，应用程序由工作流管理系统通过接口3 控制和管理 7 南京邮电大学硕士研究生学位论文第二章基础理论 ( 4 ) 接口4 为其他工作流执行服务器，主要用于若干个自治工作流系统之间的工作交换。 该接口促进了工作流互操作性： ( 5 ) 接口5 为管理和监控工具，主要用于管理和监控工具与工作流执行服务器之间的链 接。它可分为两部分：工作流管理功能和工作流追踪功能。 2 1 4 工作流管理系统w f m s 工作流表现为企业的一系列业务流程，它由一系列在逻辑上相关的任务组成。工作流 管理系统关注系统如何识别、建模、开发、部署和管理工作流程( 也包括涉及i t 系统与人 工交互的流程) 。主要功能是通过计算机技术的支持去定义、执行和管理工作流，协调工 作流执行过程中任务以及群体成员之间的信息交互。 w f m c 给出的关于工作流管理系统的定义是：工作流管理系统是一个软件系统，它完 成工作流的定义和管理，并按照计算机中预先定义好的工作流逻辑推进工作流实例的执行 ( 文献 1 3 】) 。 w f m s 系统的目标是协助达到“流程与期望业务结果一致”，并确保i t 系统能够支持 这些工作流程。w f m s 的独特之处在于，显式地将业务逻辑从实现应用程序中分离出来， 从而有利于企业提高生产力、降低运营成本和增加机动性，企业能够更快地对不断变化的 市场环境作出响应，以把握获取竞争优势的机会。 2 2 工作流建模技术 2 2 1 工作流建模技术的概述 工作流模型是对工作流业务活动的抽象描述，工作流过程模型包括一些离散的活动模 型、相关的资源、信息和角色描述以及反映上述元素关系的管理规则。工作流建模为工作 流管理系统的核心所在，其反映了需要描述的经营过程的计算机可处理的形式化定义，便 于更清晰地认识和理解复杂业务流程( 文献 9 】) 。工作流建模具有如下特点： ( 1 ) 面向过程的建模，工作流建模的对象是过程，是以过程为中心的，因此建模方法 可以更好地描述流程； ( 2 ) 支持静态分析与动态分析，使流程建模具有灵活的静态和动态模拟功能； ( 3 ) 具备形式化的能力，过程模型通过形式化的语言进行表达，便于计算机更好地解 释和处理过程模型。 8 南京邮电大学硕士研究生学位论文第二章基础理论 2 2 2 工作流建模技术的分类 在工作流建模方面，传统的建模方法有很多种，这些方法在对业务过程的描述能力和 模型本身的灵活性等方面有所差异，主要建模技术有如下： l 、基于流程图的建模方法 采用计算机程序流程图建模标准和基本方法，有顺序、选择和循环基本结构( 文献 9 】) ， 该方法描述的过程比较直观，容易理解，计算机容易实现；但是没有抽象机制，不具备形 式化描述功能，描述动态过程能力欠缺。 2 、基于活动网络图建模技术 活动网络图( a c t i v i t yd i a g r a m ) 建模技术的显著特点也是直观、简易，其使用一个无 自环的有向图描述，有向图使用节点和有向弧表示，其中节点元素表示过程执行的任务或 是活动，节点间的连接弧代表了过程中的控制流和数据流( 文献 1 4 】) ；但是其在形式化建 模能力上不够丰富。 3 、基于有限状态机建模技术 有限状态机( f s m ，f i n i t es t a t em a c h i n e ) 建模技术，使用有限个状态，以及在这些状 态之间的转移和动作等行为，对工作流程进行建模( 文献 9 】) 。有限状态机使用状态转移图 和状态转移表，描述流程过程活动之间的关系。这种建模方法直观、易懂，能够反映过程 节点的时序关系，以及状态变迁过程；但是在复杂业务流程活动建模上比较弱，而且难以 支持过程的并发和异步建模。 4 、基于事件驱动过程链建模技术 基于事件驱动过程链( e p c ，e v e n t p r o c e s sc h a i n ) 建模技术，主要元素就是功能和事 件，功能被事件触发，功能也产生相应的事件( 文献【9 】) 。流程过程的控制由交替出现的功 能和事件彼此连接而构成；控制流的分支选择、汇合连接以及并发进行则通过逻辑操作符 或更复杂的表达式来实现。这种建模方法模型简单直观，而且可以很好支持形式化描述， 但是其对复杂业务过程描述比较困难，难以很好地支持复杂业务场景。 5 、基于p e t r i 网建模技术 p e l r i 网是一种是适用于多种系统的图形化、数学化的建模工具，为描述和研究具有并 行、异步以及分布式等特性的复杂系统提供了强有力手段。p e t r i 网既有严格的形式化定义， 又有直观的图形表示，既有丰富的系统描述手段和系统行为分析技术，又为计算机科学提 供坚实的概念基础。p e t r i 网包括库所和变迁两个基本元素，对于工作流来说，库所可以表 达为流程的条件或是状态，而变迁主要是表达业务流程的任务或活动，通过变迁的实施实 q 堕室堂皇查兰堡主堕窒竺兰垡堡奎至三兰兰型堡笙 现流程的运行( 文献 1 5 】) 。因此，p e t r i 网可以很好地实现对业务流程的建模，以及复杂业 务场景的描述：而且严格的数学形式化描述手段，为流程建模提供了丰富建模和分析的手 段和工具。 对于以上五种建模技术，常用的技术主要是基于活动网络和基于有限状态机的建模技 术，这两种技术不适于复杂的业务流程：基于事件驱动过程链e p c ，同样是建模过程过于 复杂，对业务过程的并发和同步描述欠缺。综合比较，虽然p e t r i 网并不适合于直接描述业 务过程，但p e t r i 网在处理各种控制结构( 分布、井发、异步等) 上具有很大优势，可用以描 述存在于条件与事件间的关系。具有形式化步骤与数学图论相支持的理论严密性。作为一 种可用图形表示的组合模型，p e t r i 网具有直观、易用、通用性强的优势，增加一些流程控 制所需的限制和扩展以后，尤其适合工作流领域的建模需求。 2 3p e t r i 网的一般论述 p e t r i 网是对离散并行系统的数学表示。p e t r i 网是1 9 6 0 年代由c a r l a d a mp e t r i 发明的， 适合于描述异步的、并发的计算机系统模型。p e t r i 网既有严格的数学表述方式，也有直观 的图形表达方式，避免了模糊性、不确定性和矛盾性，非常适合过程建模和分析( 文献【1 2 】) 。 2 3 1 p e t r i 网基本概念( 文献 1 】) p e t r i 网由库所( p l a c e ) 和变迁( t r a n s i t i o n ) 组成，圆圈表示库所，矩形表示变迁， 如图2 所示，为一个保险索赔过程的p e t r i 网建模。 发送通知 图2 保险索赔过程的p e t r i 网过程图 p e t r i 网中库所和变迁可以用有向弧连接，共有两种类型的弧：从库所到变迁；从变 迁到库所。从库所到库所，或从变迁到变迁的弧都是不允许的。 输入库所，库所p 是变迁t 的输入库所，当且仅当从p 到t 存在一条有向弧。 l o 南京邮电大学硕士研冗生学位论文 第二章基础理论 输出库所，库所p 是变迁t 的输出库所，当且仅当从t 到p 存在一条有向弧。 库所可以容纳托肯( t o k e n ) ，由黑点表示。p e t r i 网结构是固定的，而库所中的t o k e n 分布是可变的。p e t r i 网的状态用库所中t o k e n 的分布来描述。 变迁的实施( f i r i n g ) ，是指变迁从输入库所获取t o k e n ，执行变迁任务，然后生成t o k e n 输出到输出库所的过程。变迁只有满足可实施的条件才能实施，也就是，只有每个输入库 所都至少有一个t o k e n ，变迁才能被“装弹”，实施就绪。变迁一旦就绪( e n a b l e ) 即可以 实施。变迁实施时，从它的每个输入库所都取走一个t o k e n ，并往它的每个输出库所都增 加一个t o k e n 。也就是，实施时，变迁消耗掉来自输入库所的t o k e n ，并为输出库所生产 t o k e n 。 变迁是p e t r i 网的主动元素。通过实施变迁，过程从一个状态转变到另一状态。因此变 迁经常表示事件、操作、转换或传输。库所是p e t d 网的被动元素，它们不能改变网的状态， 库所通常表示媒介、状态、阶段或条件。t o k e n 通常表示对象，对象可以是具体的事务， 也可以是抽象的信息。 2 3 2 染色p e t r i 网 高级p e t r i 网是对传统p e t r i 网的扩展，通过扩展，可以对复杂情况用结构化的、容易 理解的方式建模，主要有三种模式的扩展：颜色扩展、时间扩展、层次扩展。染色p e t r i 网是对传统p e t r i 网的颜色扩展，通过对t o k e n 的进行染色，对流程案例属性赋予颜色特征， 从而更好地控制流程运行过程，实现p e t r i 功能的扩展( 文献【1 】) 。 t o k e n 可以表示各种各样的事务。但是传统p e t r i 网不能区分两个t o k e n ，即两个在同 一库所中的t o k e n 无法通过定义进行区分。为了使对象特征与对应的t o k e n 相结合，所以 用“颜色 对传统p e t r i 网进行扩展，形成染色p e t r i 网。染色p e t r i 网确保每个t o k e n 都被 提供一个值，即颜色。因为每个t o k e n 都有一个值，通过它可以对t o k e n 进行区分。通过 给t o k e n 赋值，即为t o k e n 染上不同的颜色。 变迁实施所产生的t o k e n ，取决于实施时被消耗的t o k e n 的值，生产出的t o k e n 的值也 可以依赖于那些被消耗的t o k e n 的值。与传统p e t r i 网的不同，生产的t o k e n 数目也是变化 的，即生产的t o k e n 数目由被消耗的t o k e n 的值决定。 在经过颜色扩展到p e t d 网中，流程可以为将要被消耗的t o k e n 的值设置前置条件。变 迁只有在每个输入库所中都有个t o k e n 并且前置条件满足时才能就绪。一个变迁的前置 条件是与将要消耗的t o k e n 的值相联系的逻辑需求，从而可以通过颜色值控制流程的运行， 南京邮电大学硕士研究生学位论文 第二章基础理论 扩展流程的运行能力，实现复杂业务流程。 2 3 3 p e t r i 网的数学模型( 文献 1 6 1 ) p e t r i 网中有两类元素：p 元素( 状态元素，库所) 和t 元素( 变迁元素，变迁) ，它 们组成的集合是不相交的。 p e t r i 网的数学定义：p e t r i 网是一个三元组n = ( p ，t ，f ) ，其中p 为库所合集；t 为 变迁合集，并且和p 不相交；f 为流关系，( p xt ) u ( r xp ) ，即连接弧集合( “ 表 示笛卡尔积) ；d o m ( f ) u c o d ( f ) = p u t 其中： d o m ( f ) = 工p u t i3 y p u t ：( x ，y ) f c o d ( f ) = x p u t i3 y p u t ：( j ，x ) f ) 为了表示连接弧从库所指向变迁或者从变迁指向库所，使用如下的表示方法。设 n = ( p ，t ，f ) 为一个网，对于工p u t ， 元素。工：= 抄p u ti ( y ，工) f ) 表示x 的输入元素集或前集： 元素x # p u t i ( x ，y ) ef 表示x 的输出元素集或后集； 称。x u x 为元素x 的外延。 染色p e t r i 网的定义：染色p e t r i 网为一个七元组= ( p ，t ，f ，c ，w ，1 ，m ) ，其中( p ，t ， f ) 为一个网，c 是颜色的一个有限集c = c 1 , c 2 ，c k ) ，矿：f 专三( c ) + ，：t 一( c ) + ， m ：s 一( c ) 。w 为有向边集f 到k 维非负整数向量集的映射( 带颜色的权函数) ，m 为 库所集s 到k 维非负整数向量集的映射( 带颜色的标识) ，i 为变迁集t 到k 维非负整数向 量集的映射，l ( c ) 表示定义在颜色集c 上的一个非负整数系统线性函数，上( c ) + 表示系数 不全为0 的l ( c ) ，即 t ( c ) = a ；c i - i - 口2 c 2 + 。+ a k c k 工( c ) + = 岛c l + 岛c 2 + 。+ 6 i q a s , 6 ( f = 1 ，2 ，七) 均为非负整数，且岛+ 6 2 + 。+ o k 0 1 2 南京邮电大学硕士研究生学位论文第二章基础理论 2 3 4 p e t r i 网并发论( 文献【l7 ) p e t r i 网是分布式系统的建模和分析工具，它特别便于描述系统的并发与同步等等关 系。p e t r i 网可以使用其直观的图形化模式描述并发，使并发这一概念直观化；而且完备的 数学模型和原理可以正确的定义、描述和分析并发的性质。， 并发( c o n c u r r e n t ) 的定义即“不相依赖( i n d e p e n d e n t ) ”，系统有两个事件a 和b ，如果 a b 和b a 的执行顺序结果一样，那么a 和b 就并行，或a 与b 并行则a b 或b a 结果一样( 文 献 1 6 】) 。 并发结构可以借助严格偏序关系来表述，严格偏序结构定义如下： 定义l 设x 为一个集合， 是x 上的一个二元关系，并满足 1 ) 、 v x ，j ，：工 y - - 4 工，y z 2 ) 、 v x x ：( x ，x ) 仨 3 ) 、 v x ，y ，z 。r ：( x y ) a ( j ， z ) ( 工 z ) 则称( x ， ) 是一个严格偏序结构，记为s p o ( x ， 则严格偏序可以定义 为：s p o ( x ，勺：营( 一 xx 彳) a “m = ) 人卜2 ) ，其中 2 _ 是序关系 满足传递性 的另一种表达方式。 定义2设( x ， ) 为一个严格偏序结构，若z ，y x ，既非石 y ，也非y x ，则称x 和y 存在并发关系，记为xc oy ，即xc oy ：( x ，y x ) a - - , ( x y ) 人一( y - ：= 1 ) ，把二元关系c o ， - 都看作集合( 都为x xx 的子集) ，则有c o ：丽。 把( x ，c o ) 成为一种并发结构。因为一个并发结构可以由一个严格偏序结构s p o ( x ， ) 唯一确定。 定义3 设( x ，- 9 为一个严格偏序结构，c o = - - ，则说( x ，c o ) 为( x ， ) 所确定的 并发结构。 由定义2 和3 得到并发结构( x ，c o ) 的2 个基本性质： 1 3 南京邮电大学硕士研究生学位论文第二章基础理论 1 、i d ，即表示并发关系满足自反性； 2 、c o = c o 一，即表示并发关系满足对称性。 从耐sc o 即并发的自反性可以得知p e t r i 网图中的一个元素自身满足并发特性，也就是库 所和变迁的自身满足并发特性，表明同一个库所和变迁中的不同颜色标记t o k e n 的运行， 具有并发特性，满足并发关系的自反性；从面向对象的观点就是，p e t r i 网中的某个库所和 变迁中的不同的对象之间的执行，满足并发特性，这是p e t r i 直观的并发特性之一。 c o = 一并发关系的对称性质，保证了a 与b 并发特性，同时也保证b 与a 的并发特 性，即a 和b 的运行相互独立，无因果关系。 定义4 全序结构为严格偏序的一个子类，通常使用f o ( x ， ) 表示全序结构 v x ，y x ：x y x - y v y - x ；s e o ( x ， ) 中一个最大全序结构成为一条线。在x 中如果 x ，y 在一条线上，则说x 和y 存在线关系，记为xl iy ，即 l i ：- - - - 或者l i ：= c o oi d 定义5 设( x