工作流模型验证与数据访问冲突分析方法研究分析

分类号 U D C ： 工! ! j !密缎：垒匠 学号：Q 2 9 8 2 1 I Y 7 q 0 4 6 1 - y i 9 0 S 0 0 隶南大譬 硕士学位论文 工作流模型验证与数据访问冲突分析方法研究 研究生姓名旦生! 垩 导师姓名( 职称) 一王茜( 熬援! 蝗昱2 申请学位类别工堂亟专业名称进篡拯鏖墨挂苤 论文提交R 期2 Q Q 5 生2 旦论文答辩日期2 Q Q 至3 县3 Q 目 学位授予单位 壅直太堂一 学位授予日期一 一廿 答辩委员会丰席 评阅人 蔓锄 二O O 五年三月 工作流模型验证与数据访问冲突分析方法研究 摘要 工作流技术是重要的协同应用支撑技术之一，它通过对业务过程进行建模、执行和管理 来完成业务目标。工作流模型建立起来之后，模型正确性验证和工作流执行时的并发控制成 为需要解决的问题。本文的模型验证由语法分析和结构验证组成，采用了一种基于有向图的 归约法的工作流模型结构冲突分析方法，结合数据流分析方法，探讨了工作流模型的正确性 验证问题，并且开发了一个工作流模型验证工具。此外，当多个工作流实例并发执行时，这 些实例之间的某些任务可能通过共享数据对象而存在约束关系，这将引发严重的数据访问不 一致问题。本文扩展了结构化工作流定义语言S W D L ，在此基础上，采用集合约束系统对 工作流内部以及实例之间所有可能引起冲突的任务进行分析，生成数据资源的任务冲突集， 在此基础上划分出任务调度具有互斥眭质的关联任务子集，并且引入动态任务约束，以保证 各实例中可能引发数据冲突的任务子集运行时的临时事务性。本文提出的调度算法在保证工 作流实例运行正确性的同时，提供了一种多实例间灵活的、尽可能多的任务并发调度方法， 实验验证了本文调度算法的有效性，性能分析表明，该算法提高了工作流的执行性能。 关键 司：工作流，模型验证，集合约束，工作流并发，数据访问冲突 R e s e a r c ho nW o r k f l o w M o d e lv e r i f i c a t i o na n dD a t a A c c e s sC o n f l i c tA n a l y z e A b s t r a c t W o r k f l o wi so n eo ft h ei m p o r t a n ts u p p o r t i n gt e c h n i q u e si nC S C W I tf a c i l i t a t e s p e o p l e s c o o p e r a t i o nb ym o d e l i n g ，e x e c u t i n ga n dm a n a g i n gp r o c e s s e st oa c h i e v et h e i rb u s i n e s sg o a l sA f t e r aw o r k f i o wm o d e li sb u i l t t h eq u e s t i o no fm o d e lv e r i f i c a t i o na n dw o r k f l o wc o n c u r r e n c yi st ob e s o l v e d T ov e r i 白t h es e m a n t i ca n ds t r u c t u r a Ic o r r e c t n e s s ，ag r a p hr e d u c t i o nm e t h o di si n t r o d u c e d i nt h i sp a p e r , c o m b i n e dw i t hd a t af l o wa n a l y z em e t h o d ，w ec o m p l e t eam o d e lv e r i f i c a t i o nt 0 0 1 W h e nm u l t i p l ew o r k f l o wj n s t a n e e se x e c u t ei np a r a l l e l t h e ym i g h th a v es o m ec o n s t r a i n t r e l m i o n s h i p sb e c a u s es o m et a s k so ft h ei n s t a n c e sm i g h ts h a r et h es a m ed a mo b j e c t s T h i sw i l l C a L I s es e r i o u sp r o b l e m so fi n c o n s i s t e n c yi nd a t aa C C e S S T h i sp a p e re x t e n d st h eS t r u c t u r e d W o r k f l o wD e f n i t i o n L a n g u a g e ( S W D L ) B yu s i n g s e tc o n s t r a i n t s y s t e m s ，a l lp o s s i b l e c o n f l i c t c a u s i n gt a s k si nt h ew o r k f l o wa n da m o n gt h ei n s t a n c e sa r ea n a l y z e da n dt h ec o n f l i c t e d t a s ks e to ft h ed a t as o u r c e si sg e n e r a t e d B a s e do nt h a t t h es u b s e to ft h er e l a t e dt a s k sa n dt h e d y n a m i ct a s kc o n s t r a i n t sa r eg e n e r a t e d ，e n s u r i n gt h et e m p o r a r yt r a n s a c t i o na m o n gt h ei n s t a n c e so f t h et a s ks u b s e tw h i c hm i g h tl e a dt od a t ac o n f l i c tw h e ne x e c u t i n g T h l sp a p e rp r o v i d e saf l e x i b l e a l g o r i t h mf o r a s m a n ya sp o s s i b l ei n s t a n c e so ft a s k st or u nc o n c u r r e n t l yw h i l ee n s u r i n gt h e c o i T e c t n e s so f t h ew e r k f l o wi n s t a n c e ss ot h a tt h ep e r f o r m a n c eo f t h ew o r k f l o ws y s t e mi si m p r o v e d A ne x p e r i m e n tp r o v e st h ev a l i d i t yo f t h i sa l g o r i t h mi sd i s c u s s e d K e yW o r d s ： W o r k f l o w , M o d e lV e r i f i c a t i o n ，S e tC o n s t r a i n t ，W o r k f l o wC o n c u r r e n c y , D a t aA c c e s sC o n f l i c t 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他入己经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了 谢意。 研究生签名：0 雌日期：盟) 东南大学学位论文使用授权声明 东南扶学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件 电子芏档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论 E 的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅可以公布( 包括刊 羔) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名 期斗摊各日期 查塑查兰堕主兰些堡苎 三垡鎏堡型墅至兰墼塑堕塑苎窭竺堑查婆塑窒 第一章绪论 1 。1 工作流技术的发展及应用现状 工作流的概念起源于生产制造业与办公自动化领域。根据工作流管理联盟( W F M C ) 对工 作流的定义，工作流是一类能够完全或者部分自动执行的经营过程，它根据一系列过程规则、 文档、信息或任务能够在不同的执行者之间进行传递与执行。工作流管理系统是利用软件来 定义、创建和管理工作流执行的计算机系统，该系统运行在一个或多个能理解流程定义并与 流程参与人相互协作的工作流引擎之上I l 】。 8 。年代中期，F n e N e t 和v i e w S t a r t 等公司率先开拓了工作流产品市场，成为最早的一批 工作流产品供应商。他们把图像扫描、复合文档、结构化路由、实例跟踪、关键字索引以及 光盘存储等功能结合在一起，形成种全面支持某些业务流程的集成化的软件。比较典型的 有F i l e N e t 于1 9 8 4 年推出的W o r k F i o w 商用系统，v L e 瞒t a r c 于1 9 8 8 年推出的v i e 瞒t a r ，I B M 于1 9 8 8 年推出的I m a g e P l u s 。 进入9 0 年代，随着计算机的普及，计算机网络技术的迅速发展，企业的信息化程度提 高，企业信息资源越来越表现出异构、松散耦台的特点。I n t e m e t 的发展和普及为电子商务 提供了技术可能，而电子商务的重要功能就是商务流程的管理和监控，如企业供应链管理系 统S C M ( S u p p l yC h a i nM a n a g e m e n t ) 和企业客户关系管理C R M ( C u s t o m e rR e l a t i o n s h i p M a n a g e m e n t ) 。在这种技术背景下，工作流管理系统也由最初的无纸化办公环境，转而成为 集成企业复杂业务流程，实现业务流程自动执行的工具，工作流技术进入了一个崭新的发展 阶段，1 9 9 3 年工作流管理联盟W F M C ( W o r k f i o wM a n a g e m e n tC o a l i t i o n ) 成立，工作流相关 的概念和术语得到了人们的认可。 目前，在全球范围内，对工作流技术的研究及相关产品的开发进入了更为繁荣的阶段， 更多更新的技术被集成进来，文件管理系统、数据库、电子邮件、移动式计算、W e b 服务 等已被容纳于工作流管理系统之中。工作流产品市场每年以两位数字的速度迅猛增长。随着 计算机技术的发展，新的技术不断地融入工作流系统中，使得工作流产品得到不断完善。作 为支持企业经营过程重组( 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 ，B P R ) 、经营过程自动化( B u s i n e s s p r o c e s sa u t o m a t i o n ，B P A ) 的一种手段，工作流技术的研究和应用日益受到学术界与企业界 的重视，国内外许多大学和研究机构也致力于工作流技术的研究和开发项目，其中比较有影 响力的。i ：作流研究中心主要有t B M 的A L M A D E N 研究中t ：, T nw I D E 工作流研究组等。 工作流定义了W h a t ( 流程的基本描述、流程各组成活动及活动描述) ，H o w ( 流程各间 的时序及选择约束关系、活动阊信息流、活动任务完成内容) ，W h o ( 流程活动的角色，包 括参与人、管理人等) ，W h e n ( 流程启动时间、任务完成的时间约束) ，W h e r e ( 任务完成地 点的分布) ，相对于一般的流程，丁= 作流主要具有如下的一些特点： ( 计算机管理：工作流管理是由计算机管理的企业业务流程，而不是手工管理 的流程，也不是部分步骤由计算机来完成的计算机应用： ( 2 ) ( 3 ) 自动流程：流程实现任务及任务信息在流程参与人之间自动流转： 流程具有计算机可以理解的定义：流程具有显式或者隐式的计算机定义，它 将实际的经营过烈转化为计算机可处理的形式化定义，通常称这种定义为工 作流模型： 东南大学硕士学位论文 工作流模型验证与数据访问冲突分析方法研究 1 。2 工作流模型验证与数据访问冲突分析的必要性 二怍流模型是对工作流的抽象表示它将实际的经营过程转化为计算机可处理的形式化 定义。为了使计算机能够支持业务过程处理，就要对业务过程进行分析，抽象出业务过程的 本质特征，并使用某种计算机可处理的方式来表示。 在W f M S 中对业务过程描述的目的是便于工作流管理系统的控制执行，因此，过程模 型的正确陛是业务目标实现的基本保证。工作流模型的正确性验证是工作流建模环境的一个 核心功能，其目的是对已建立的工作流模型按照菜种正确性原则进行验证。工作流模型的正 确性主要包含两方面的含义： ( 1 ) 过程模型的结构正确性，即过程模型是结构无冲突的在没有错误发生的情 况下，工作流能够正常终止。 ( 2 ) 过程模型的语义正确性，也就是说工作流在正常终止时应该达到所期望的业 务目标。 由于工作流模型的复杂性，目前还没有有效的算法可以对工作流模型的正确性进行完备 的分析。由于P e t r i 网严格的数学基础和图形化的规范语义。许多研究人员采用P e t r i 网对工 作流进行建模和分析，文献”3 提出了一种基于P e t r i 网的验证方法， S a d i q 等在有向无环图( d i r e c t e da c y c l i cg r a p h ，D A G ) 的基础上，通过定义一些归约规 则【6J ，如果一个工作流模型可以通过使用这些归约规则归约为空，则认为该工作流模型是正 确的，否U 判定该模型存在某些结构冲突，但是，S a d i q 的验证方法不允许工作流模型中存 在循环结构，这与实际应用中的工作流模型不符合，此外，S a d i q 方法对嵌套重叠结构 ( O v e r l a p p e dS t r u c t u r e ) 的处理存在着错误”。 为了实现预期的业务目标，就需要上E 确地定义过程模型，这就要求在工作流执行之前对 其模型进行分析。对j ：作流模型的分析主要包含3 个方面 3 1 ： ( 1 ) 有效性分析( v a l i d a t i o na n a l y s i s ) ：测试工作流的执行是否能实现预期的业务目 标。 ( 2 )正确性证明( c o r r e c t n e s sv e r i f i c a t i o n ) ：验证工作流模型的正确性。 ( 3 ) 性能分析( p e r f o r m a n c ea n a l y s i s ) ：评价下作流的某些性能参数，例如1 = 作流 的平均执行时间、活动执行的平均等待时间，吞吐率、资源占用率等。 其中对工作流模型的有效性分析和性能分析可以通过谊真来进行，可惜目前有效的工作 流仿真技术近乎空白，模型验证也往往是通过运行一些_ l 作流实例由有经验的专业人员来检 查1 1 作流的执行是否符合设计要求，这通常需要比较氏的时间周期。我们认为在一作流执 行之兹妞果采燃一些验证1 ：具对所建立的 j 作流模型进行验汪，将有助于及早发现模型中存 在的一些例如结构冲突等错误，提高建模效率。因此，探讨工作流模型验证方法，并为工作 流管理系统提供模型验证工具成为需要研究的问题。 1 ：作流模型验证通常从语法验证和结构验证方面着手一般是对单个l ：作流模型进行分 析验证。然而，在工作流实例的执行过程中，如果多个在逻辑上可以同时执行的活动共享同 一数据，则有可能造成数据访问冲突，这种数据访问冲突可能来自于一个工作流实例内部的 并行活动之间，也可能来自T 不同工作流实例的活动之间，甚至可能是同- - T I 作流的不同实 例之间。这种数据访问冲突将导致严重的数据不一致现象。因此，必须在 ：作流模酗定义阶 段进行数据访问冲突分析，并寻求j 1 ：作流数据访问止确性保证方法。 2 东南大学硕士学位论文 工作流模型验证与数据访问冲突分析方法研究 1 3 论文的主要内容与章节安排 论文以工作流模型验证和数据访问正确性保证为研究目标，内容安排如下：在第二章主 要基于工作流有向图模型，采用数据流分析方法和图形归约方法进行模型验证。第三章实现 了一个图形化的工作流建模和模型验证工具，并给出一个复杂工作流模型的验证实例。接下 来的第四章分析了工作流系统中的并发问题，通过采用集合约束系统，文章对工作流多实例 间数据访问冲突进行了分析，并生成数据访问冲突集。在此基础上，第五章采用任务调度具 有互斥性质的任务子集及任务约束概念，给出了工作流多实例数据访问正确性保证方法，并 且设计丁实验进行性能分析和验证。文章最后总结了全文，归纳了论文的创新点，并阐述进 一步研究的方向。 2 1 研究现状 第二章工作流模型分析 目前，用来描述业务过程的方法主要包括有向图J 、P e t r i 网u 】、形式逻辑【4 l 、事件一条 件一动作规则E C A A ，1 等，其中有向图的使用虽为普遍，它采用图形符号来表示活动之间的 约束关系，简单直观。而P e 订i 网由于严密的形式语言结构，适合对工作流动态性质进行分 析，但这种方法使用不直观，不易使用。形式逻辑使用符号来表示活动之间的逻辑关系，该 方法不易描述活动之间的复杂关系和活动数量很多的业务过程。E C A A 方法则是从事件的角 度来描述业务过程，但是它对业务过程的描述缺乏严密性。 在对业务过程描述的基础上，为了检验所建立的业务过程模型的正确性，必须进行模型 分析和验证。目前，_ 作流模型分析大多停留在理论层次上，带有工作流模型验证工具的成 熟工作流产品不多。在模型分析方法中，比较有代表性的是S a d i q 的有向无环图的归约法【6 1 和A a l s t 的j 作流网( W F N e t ) 方法 7 1 。S a d i q 认为，通过反复使用预先定义的一些归约规 则。如果能将一个工作流图归约为空，则认为该工作流模型是结构正确的。然而，这种方法 存在以下缺陷：( 1 ) 由于归约的前提是有向无环圈( D A G 图) 。因此不允许所分析的工作流 图具有任何形式的循环结构，这与实际的业务过程相悖。( 2 ) 对某些正确的嵌套重叠结构， S a d i q 归约法无法把正确的工作流图归约为空。( 3 ) 由于没有对数据流进行分析该分析方 法无法检验出模型中的无效活动节点。文献【1 ”对S a d i q 的错误之处进行了证明，并定义了一 套转换规则，试图解决重叠结构的归约问题。A a l s t 使用W F - N e t 来描述和分析业务过撑， 其中W F N e t 是从基本P e t r i 网派生而来的，A a l s t 方法通过分析W F - N e t 的性质来证明业务 过程模型的正确性，但是，W F N e t 方法不易在实际工作流产品中实现。本章引入数据流分 析方法，对无效活动节点和循环结构进行判定，改进了S a d i q 归约规则，简化了具有重叠结 构的上作流模型的验证过程。 东南大学硕士学位论文工作流模型验证与数据访问冲突分析方法研究 2 2 工作流模型 2 2 1 工作流元模型 元模型( m e t a m o d e l ) 是用来定义语义模型的构造( c o n s t r u c t ) 和规则( r u l e ) 的， 通常称为定义表达模型的语言的模型1 ，工作流元模型是用于描述工作流内部的各个元素， 元素之间关系以及元素属性的。 工作流元模型通常涉及相互关联的3 个子元模型，即： ( 1 ) 过程定义元模型：用于定义描述业务过程的模型元素，控制工作流的执行； ( 2 ) 相关数据元模型：工作流执行所处理的数据以及它们之间的流动关系； ( 3 ) 组织机构元模型：描述单位，部门，人员的组织关系以及所担当的角色： 工作流元模型的核心是过程定义元模型，工作流管理联盟为过程定义开发了一个基本的 元模型。工作流元模型归约出元素类型的一个基本集合，这些元素类型适台于相对简单的过 程定义，工作流开发人员可以根据需要对该元模型进行适当的扩展。 工作流管理联盟的过程定义元模型中元素的定义和重要属性如F ： 活动( A c t i v i t y ) ：完成工作流的一个逻辑步骤，重要属性包括活动名称活动类型， 前后活动条件，其他调度约束等。 转移条件( t r a n s i t i o nc o n d i t i o n s ) ：从当前活动到下一活动流转或状态转移的规则， 主要参数包括过程条件，执行条件，通知条件等。 工作流相关数据( w o r k f l o wr e l e v a n td a t a ) ：被工作流管理系统用作决定个工作流 实例状态转移的数据。重要属性包括数据名称或路径，数据类型等。 角色( r o l e ) ：把参与者与一系列活动相联系的机制，重要属性包括名称，组织实体等。 被调应用( i n v o k e da p p l i c a t i o n ) ：应用主要描述用于完成业务过程所采用的工具蒴l 手段，重要属性包括类型或名称，执行参数，位置或存取路径等。 圈2 - I 是W f M C 给出的过程定义元模型”： 图2 - 1W f M C 的过槲定义元模型 4 东南大学硕士学位论文 工作流模型验证与数据访问冲突分析方法研究 2 2 2 过程描述语言 在描述业务过程时往往使用某种语言符号来表示过程模型中的各种元素，在有向图中， 基本符号分为两类：节点和弧，节点包括活动节点和控制节点，活动节点包括开始活动、原 子活动、子过程、结束节点，而控制节点则包括与节点( A N D n o d e ) 、或节点( O R n o d e ) ， 如图2 2 所示： 图2 2 过程描述语言的基本符号 起始活动表示一个工作流过程的开始，终止活动表示一个工作流过程的结束。原子活动 是可以直接由工作流管理系统执行的基本实体。由于过程模型中的活动也可能是具有复杂结 构的过程模型，因此引入子过程的概念，子过程本身可以是一个工作流模型，它与主流程组 成一个层次化的工作流模型。控制节点和弧表示业务处理规则和约束关系，或节点表示工作 流执行的路径选择和合并，与节点表示工作流执行的分叉和同步，弧通过连接两个节点表示 控制流和数据流的流动方向。如果弧带有条件表达式，则表示在工作流执行时计算表达式的 值，结果为真时触发相应的变迁发生。 工作流管理联盟W f M C 定义了工作流执行的6 种基本控制结构，它们分别是：顺序 ( S e q u e n t e ) 、循环( I t e r a t i o n ) 、与分支( A N D s p l i t ) 、与合并( A N D j o i n ) 、或分支 ( O R s p l i t ) 、或合并( O R j o i n ) ，这些控制结构用有向图表示为： 图2 - 31 二作流执行的基本控制结构 顺序( S e q u e n c e ) 表示一个活动执行结束后另一个活动可以开始执彳丁= 循环( i t e r a t i o n ) 表示若干个活动反复被执行直到满足某个条, f l ：； 5 查堕查兰堡主堂些笙壅 三丝迹堡型壁堑量塑塑堕塑壁窭坌塑变鲨竺窒 与分支( A N D s p l t ) 异j 来触发后续多个活动的执行，需要注意的是，后续的多条路径 可以以任意的次序执行。 与合并( A n d - j o i n ) 用来N 步输入进来的多条路径，表示著行执行的路径在该节点上同 步。 或分支( O R s p l i t ) 工作流引擎计算所有的布尔表达式，选择其中的一条正确的执行路 径。 或合并( O R - j o i n ) 只要其输入路径中有一条执行完毕，就触发执行后续活动。 图2 4 是一个用以上控制结构构成的简单工作流模型，包含闭合结构，循环结构等基本 控制结构。 2 3 模型验证 图2 4 普通的工作流模型示例 对于面向过程的工作流系统而言，过程定义是业务过程自动流转的基础，然而，过程定 义比较容易出错，仅凭流程设计者的经验或者操作者的反复实验来发现差错的方法效率低 F 。因此，在工作流执行前之前，需要采用验证方法，对业务过程中的各项特性进行检测， 以保证工作流模型的正确性。这里的正确性主要包括三方面的含义：一是指工作流模型的语 法正确陛，即所建立的工作流模型符合基本的语法要求：二是指工作流模型的结构正确性， 也就是说工作流模型姓无结构冲突的，在没有错误发生情况下工作流可以正常终J t ；三是指 工作流模型的语义正确性，也就是说工作流在正常终止时应该达到所期望的业务目标。下面 将集中对语法正确性和结构正确性进行分析，语义正确洼留待第四章进行分析 2 ，3 。t 语法检查 为便于分析，我们定义工作流图G = 犯q 毋，其中： ( 1 ) N = s t a r t N o d e ，n I ，”2 n 。，e n d N o d e 为节点集，其中s t a r t N o d e 为开始节点 n i f 原子活动节点，子过程节点、控制节点) ，e n d N o d e 为结柬节点。 2 ) E N x N ，是连接弧的集合，- ( n E N ，n j N ) J j 连接两个_ 节点的弧。 对于任意结点n N ，我WJ 定义n 的入度I n D e g r e e ( n ) ： C o u n t ( e ) IV e ，e ( m ，n ) ，即 所有终点为n 的边的总数； 对于任意结点n N ，我仃J 定义n 的出度I n D e g r e e ( n ) ： C o u n t ( e ) IV e ，e ，即 所有始点为n 的边的总数； 一个语法正确的 ：作流图G 必须满足以F 性质： 图G 有唯一的s t a r t N o d e 和结束节点，流程起始于s t a r t N o d e1 ，点，终f 丁e n d N o d e 6 查塑查兰堡主兰些鲨壅 三堡亟堡型堕堑兰塑塑堕塑壁窒坌堑查鲨竺塞 节点； 任一原子活动节点和子过程有且仅有一个出度和入度a 开始节点s t a r t N o d e 的入度为0 ，出度为1 ； 结束节点e n d N o d e 的出度为0 ，入度为1 ； 或分支、与分支节点的入度为1 ，出度大于1 ： 或合并、与合并节点的出度为1 ，入度大于1 ： 其中性质规定原子活动节点和子过程节点有且只有一个出度和入度，不符合该性质的 工作流模型将不能通过语法检查，语法验证可以识别工作流图的简单语法错误，对于复杂工 作流图的结构冲突，我们采用有向图归约法对其进行验证。原型系统实现见第三章。 2 3 2 过程模型的结构冲突 过程模型的结构冲突主要分为三类州”l ：死锁、同步丢失、无效活动。 ( 1 ) 死锁 在一个结构正确的工作流模型中，一个与分支( A N D s p l i t ) 需要和一个与合并 ( A N D - j o i n ) 对应，如果将一个或分支( O R s p l i t ) 和与合并( A N D - j o i n ) 对应，将导致 与合并节点的输入弧至少有一条不能触发，从而引发死锁，流程无法进入正常结束。 死锁的另一种情况是无限循环循环出口条件始终无法成立。( 图2 - 5 ( a ) 、( d ) 、( f ) 所示) ( 2 ) 同步丢失 同样。一个或分支( O R s p l i t ) 也需要一个或合并( O R - j o i n ) 对应。如果一个与分支和 一个或合并对应将导致与分支的多个输出弧在汇聚时未能相互等待以达到同步，从而只有一 个分支上的活动有效。( 图2 5 ( b ) 、( e ) 所示) ( 3 ) 无效活动 工作流模型中某些活动在所有的实例中永远不能无法执行，这种清况通常发生在或分支 的某个分支条件永远为假或者死锁结构冲突引起的后续活动无效。( 图2 - 5 ( c ) 、( g ) 所示) 口 ( a ) 死锁 ( b ) 同步丢失( c ) 无效活动 口辱孔驴 矗 ( d ) E 锁、无效活动 7 ( e ) 同步丢父 东南大学硕士学位论文工作流模型验证与数据访问冲突分析方法研究 口 ( f ) 死锁 图2 - 5 常见的工作流结构冲突 ( g ) 无效活动 需要注意的事，结构冲突并不是过程模型中仅有的错误，其他如活动之间的数据依赖也 可能引发工作流的错误执行。然而工作流模型中其他错误的存在并不会增加或消除结构冲 突，因而工作流模型中结构冲突的识别可以独立于其他类型的验证分析而进行。 2 3 3 模型归约法则 S a d i q 等在文献【6 1 中对有向无环图定义了4 种归约规则：顺序归约、邻接归约、闭合归 约、重叠归约。对一个工作流图反复使用归约规则，删去所有已被确认为正确的结构，保留 冲突结构，若能将一个工作流图归约化简为仅由一个起始节点和一个结束节点组成的有向 圈，则认为该工作流图无结构冲突，否则认为该图存在结构冲突。本章首先对文献【6 1 中的归 约进行了介绍，然后对其进行了扩展，增加了循环归约和终结符归约，并且引入数据流分析 方法，讨论了循环结构和无效活动节点的判定，并简化了重叠结构的验证过程。 顺溽；野约詹，1 6 1 ：两个顺序执行的活动节点可以合并成为一个活动节点。 图2 7 循环归约 为一个活动节点。 专瑚一曲 = 卜争= h 刘 查塑查兰堡主兰堡堡苎 三堡鎏堡型壁堡童墼塑堕塑壁窒坌堑立璧塑塞 在进行循环归约之前，验证程序必须首先识别出循环结构，我们采用数据流分析的方法 进行循环检测。 我们知道，在工作流图中，从开始节点出发可以到达工作流图中的任何节点。 定义l ：在一个工作流图中，从开始节点触发到达某节点n j 的各条通路都必须经过节点 n 。，则称n i 为n 的必经节点，记做n ，d o mn J 。n j 的全部必经节点的集台记为D ( n j ) ，称作n j 的必经节点集。 图2 - 8 循环结构 图2 - 8 各个节点的必经节点集有： D ( ) ： D ( ) = ，) D ( ) = ，) D ( ) = ， D ( ) = ，) 定义2 ：设e = 是工作流图中的一条边，若bd o r aa ，则称e = 为工作流图中的 一条回边。 图2 - 8 中有一条回边，即 。 性质：每条回边构成一个循环，殴 是一条回边，则该回边构成的循环包括下列 节点：a 、b 、不经过b 能够到达a 的所有节点。 根据这个性质，回边 构成的循环= ，) ，从而识别出上图中的循环结构。 留台妇缈置，7 ：两个并行执行的活动节点可以归约为一个活动节点、两个选择执行的活 动节点可以归约为一个活动节点。 日亭日争 日口口口日口 1 IV0 彩蜜i 廊约见刚：在工作流图中可能出现两个控制型节点直接相连的情况，此时可采用 邻接归约，邻接归约通常有两种情况： 若当前节点为分支型节点( 与分支、或分支) ，且当前节点的逻辑类型与其前驱节点相 同( 均为与分支或者均为或分支) ，可以把当前节点的输出弧转移到其前驱节点上，同时删 除当前节点。 9 查堕查兰堡主兰垡堡塞 三堡堕堡型墅壁量墼塑堕塑翌窒坌堑塑鲨堕翌 图2 - 1 0 邻接归约一 若当前节点为合并型节点( 与合并、或合并) ，且当前节点的逻辑类型与其后继节点相 同( 均为与合并或者均为或合并) ，则可以把当前节点输入弧转移到其后继节点上，同时删 除当前节点。 +士 + + 图2 - l l 邻接归约 磐秽妇约R s ：为了简化工作流模型的验证过程，在归约的过程中往往把活动节点去掉， 一个正确的工作流模型经过归约化简后将只存在一个起始节点和结束节点，以及由起始节点 指向结束节点的有向弧。终端归约示例如下： 2 4 无效活动的判定 图2 ，1 2 终端归约 S q d i q 规则忽略了过程模型语义相关的属性和弧上的条件表达式可以看作仅仅是对l 作流模型的控制结构进行验证。而事实上，过程模型中弧上表达式的语义可能会造成条件的 永远无法满足，例如图2 - 5 ( c ) 、( g ) 就是条件表达式永远无法满足转移条件的例子，造成 了无效活动。另外，死锁结构也可能造成某些活动成为无效活动，如图2 - 5 ( d ) 所示。通 过对死锁结构的判定能够识另0 由死锁结构引起的无效活动，因此，下面主要讨论通过检查相 关弧上的条件表达式而完成对无效活动的判定。 具体判定过程为： 搜索模型中“或分支”节点： 依次取“或分支”节点的输出弧上的条件表达式，如果该弧上的条什表达式永远为 假，则删除该弧： 遍历1 i 作流模型，如果存在除起始点以外的入度为0 的活动仙点，则标，占该活动 O ，0 专 东南大学硕士学位论文 工作流模型验证与数据访问冲突分析方法研究 节点为无效节点，并且删除其出边，循环； 如对图2 1 3 的所示一个工作流模型，经过上述判定算法可以划分出两个无效活动节点 ( 图中红色节点所示) 。 国2 1 3 无教活动的判定 对于或分支节点，一般情况下其输出弧中应该有条e l s e 路径，系统实现以保持一条 不设定守卫条件的选择边来充当该条e l s e 路径，以防止存在选择路径都不满足条件而流程 无法继续执行下去和无效活动的情况。 2 5 重叠结构的化简 S e N t 6 1 中提出种特殊的归约方法即重叠结构归约，但是，这种归约方法并不完备， 清华大学的李红臣在文献【1 0 1 证明了其无法验证某些复杂的重叠嵌套结构针对这种情况， 文献 t O l 对重叠结构进行了定义，他认为重叠结构是这样的一种结构：输入层为与：带点，输 出层为或节点，两层间存在交叉全连接的结构( 图2 - 1 4 ) ； 重叠结构可以按照图2 1 4 的方法进行归约，为了避免归约所带来的语法错误问题，文 献作了如下定义： 规则一：假如控制节点只有一条输入弧和一条输出弧，则可以移去控制肯点，将其输入 弧与输出弧合并。 文献l I 的重叠结构归约方法如下： 嚣一X 事实上，我”J 可以推论，重叠结构的的输入层一定为或分支节点，即倒2 - 1 5 所示 东南大学硕士学位论文 工作流模型验证与数据访问冲突分析方法研究 第一层 第二层 第三层 图2 1 5 重叠结构的输入层必为或分支 证明，采用r J - 7 宝内 去，假设重叠结构的输入层为并分支节点，即图中第一层为并分支， 则流程启动后，由于第二层并分支的同时触发将引发第三层或合并节点的同步丢失问题 故重叠结构的输入层必为或分支节点。 同理，重叠结构的输出层一定为与合并节点，即图所示： 第一层 一 第二层 一 第三层 一 第四层 图2 - 1 6 重叠结构的输出层必为与台并 证明，采用归纳法，假设重叠结构的输出层为或合并节点，即图中第四层为或合并 则流程启动后，由于数据流皆到达第三层的所有或合并肖点，将引发第四层或合并节点的同 步丢失问题，故重叠结构的输出层必为与合并节点。 基于以上分析，结合圈2 - 1 4 和规则一，我们认为，典型重叠结构的归约如幽2 ，1 7 ： 闭合归约 匕= = l 规则一 图2 1 7 重叠结构的归约 需要注意的是，由于各人的建模习惯不同，可以派生出众多的类似重蹙结构的复杂l ：作 流结构，而且这些结构在逻辑上可能是正确的此时往往需要对流程进行修改，例如图2 18 是一个信用矗消费流穰图，流程描述如下：首先并行执行信用度奇淘利卡余额贲询酮个任务 如果信用良好并且余额充足，则进行信川 消费：若余额不足或者信川度判定为差，则不进 1 2 。9 令 东南大学硕士学位论文 工作流模型验证与数据访问冲突分析方法研究 行信崩卡消费，流程结束。 信用卡消费 图2 - 1 8 信用卡消费流程图 把上述图中的活动节点去掉，只留下控制节点和弧，将得到如下的一个结构 图2 1 9 信用卡消费流程重叠结构 根据定义，它并不属于重叠结构，事实上，该结构应该避免，因为它可以通过变更余额 查询和信用查询为串行结构，使得模型更加简便而直观。重叠结构是工作流图中的一种特殊 结构，它比较少出现，在结构验证中，对识别出来的重叠结构，可以依照上述规则将其化简 归约为一个空结构。 至堕查兰堡主兰堡堕塞 三堡堕堡型墅堡兰塑塑堕塑壁窭坌堑立壁堕塞 第三章工作流模型验证工具及其实现 3 1 带有模型验证工具的W f M S 体系结构 本节的工作流模型验证工具集成在我们所开发的工作流管理系统中，可以对所建立的工 作流模型进行语法和结构验证。系统体系结构如图3 - 1 所示： 图3 - 1 集成模型验证工具的工作流管理系统 3 2 图形化工作流过程定义工具 医习 l 1 ，J 工作流模型是工作流执行的基础，它为业务过程描述提供了一种直观的方法。建模工具 的主要功能如F ： 提供工作流模型定义所需的基本元素，如起始结点、任务结点、子过程、连接弧、 终止结点等i 对工作流程的集中式管理、定义、修改及监视：流程定义在服务器端由管理员身份 用户集中建模，并且进行角色定义，任务描述，系统设置： 提供模型的导入导山接I Z l ，所建立的工作流模型可以方便存储和读写； 支持子过程建模； 提供与外部应用盼接口： 在图形化的工作流建模工具中，主要存在下面建模元素： 起始活动节点：表示个工作流过程的开始。 终止活动节点：表示个工作流过程的结束。 简单活动节点：描述了流程中执行的简单业务活动，简单活动节点不带有子过程。 子过程竹点：子过程本身可以是一个一F 作流模型，它与主流程组成一个层次化的层次T 1 4 东南大学硕士学位论文工作流模型验证与数据访问冲突分析方法研究 作流模型。 选择分支节点：选择分支表示在这个活动完成后将从其多个后续活动中选择一个活动执 行。选择的依据可以是其前趋活动的输出参数也可以是自定义的外部变量，还可以为 外部事件，如人工干预或时钟控制等。 同步结点：分为同步分支结点和同步合并结点。同步分支结点表示在这个活动执行完成 后，同时触发多个后续活动，这些触发的后续活动并行地执行。圊步合并节点用来同步 汇聚多个并行执行流程的特殊节点，通过它实现多流程结果的汇合，从而实现业务过程 所需要的同步。 图形化的建模工具可以使用户形象、准确地对业务过程进行定义并且控伟0 这些过程的执 行。本系统采用继承J a v a xs w i n g J p a n e I 类的G r a p h P a n e l 类实现模型可视化定义画板，其中 的模型元素继承J a v a x s w i n g J l a b e l 类进行实现，建模系统的类图如图3 - 2 所示。 图3 - 2 工作流建模工具类图 东南大学硕士学位论文工作流模型验证与数据访问冲突分析方法研究 用该建模工其，用户可以进行方便的圈形化过程定义，系统建模运行界面如图3 - 3 ，3 - 4 所示： 圈3 - 3 工作流建模工具界面 图3 - 4 对任务节点进行角色，名称，描述定义 3 3 工作流模型的存取 由于X M L 具有较好的保值性，而且最为重要的是X M L 提供了一种不同的应用间交换 数据的理想格式，有利于不同系统工作流模型的相互转换，因此本系统采_ L I jX M L 米保存业 务模型。 6 东南大学硕士学位论文 工作流模型验证与数据访问冲突分析方法研究 3 3 1X M L 可扩展的标记语言X M L ( E x t e n s i b l eM a r k u pL a n g u a g e ) 通过提供了一个标准、灵活的可 扩展的数据格式，解决了在许多应用场合的一个关键技术需求。X M L 主要的优点在于它既 是平台无关的，X M L 可以用于机器与机器间的数据交换：又是厂商无关的，厂商无关性使 得X M L 能够更加容易地被广大的软件厂商所接受和应用。 X M L 是S G M L ( S t a n d a r dG e n e r a l i z e dM a r k u pL a n g u a g e ) 的一个子集，它是由W 3 C 制 定的一种使用者可以用来创建自己标记的标记语言”“。相比较S G M L 和H T M L ，X M L 具有 如下的优点： X M L 允许各种不同的专业开发与自己的特定领域有关的标记语言。这就使得该领域中 的八们可以交换数据和信息，而不用担心接收端的人是否有特定的软件来创建数 据。 X M L 具有较好的保值- 性。过去4 0 年来的大多数计算机数据都丢失了，不是因为自然 损害或是各份介质的磨损，而只是因为没有人来写出如何读取这些数据介质和格式 的文档。以不常用的格式保存的二进制数据，数据也许会永远地消失了。X M L 在 基本水平上使用的是非常简单的数据格式。可以用1 0 0 的纯A S C I i 文本来书写， 也可以用几种其他定义好的格式来书写。A S C I I 文本是几乎不会“磨损”的。 应用间交换数据。由于X M L 是非专有的并易于阅读和编写，就使得它成为在不同的 应用间交换数据的理想格式。X M L 使用的是菲专有的格式，不受版权、专利、商 业秘密或是其他种类的知识产权的限制。X M L 的功能是非常强大的，同时对于人 类或是计算机程序来说，都容易阅读和编写。因而成为交换语言的酋选。 相对于H T M L ，X M L 具有先天的优越性。它无需为了自己的