（计算机应用技术专业论文）基于图变换的软件演化工作流建模与分析.pdf

摘要 软件演化的研究对于延长软件生命周期、提高软件对新环境的适 应能力以及降低软件运行成本有着重要的意义。但是，现有软件演化 技术还存在如何预先推导变更的结果及其影响范围和如何设计灵活 的演化计划和处理机制等的问题。针对这些问题，论文将工作流引入 软件演化领域。这样做既可以将若干演化操作进行组合，以便于完成 更复杂的软件演化；又可以对演化操作工作流进行分析，以便于对软 件演化结果的判断以及对软件演化操作工作流的优化。 论文基于图变换理论，使用带属性类型图来描述时间与资源工作 流模型，并使用图变换技术，设计一个图变换规则集来实现工作流过 程模型的建立。 为了使所得到的工作流模型能更好的适用于软件演化，论文利用 图规约的办法进行工作流过程模型正确性分析，保证了所得到的工作 流模型在结构上的正确性；设计了一组图变换规则，以实现工作流过 程模型的时间截止性分析和时间约束性分析；在总结前人的基础上提 出了一套工作流过程模型可调度性分析的办法。 最后，论文实现了软件演化工作流建模与分析工具。并利用该工 具实现了数字电视条件接收系统的软件演化工作流建模，并对其进行 了正确性分析、时间截止性分析、时间约束性分析及可调度性分析。 实例分析表明，论文提出的基于图变换的软件演化工作流建模与分析 的方法是行之有效的。 关键词软件演化，带属性类型图，图变换，工作流建模，工作流模 型分析 a b s t r a c t t h es t u d yo ft h es o f t w a r ee v o l u t i o ni ss i g n i f i c a n tf o rt h es o f t w a r e l i f e c y c l ee x t e n s i o na n di m p r o v e m e n to fs o f t w a r ea d a p t a t i o nt ot h en e w e n v i r o n m e n ta n dr e d u c i n go p e r a t i n gc o s t so fs o f t w a r e h o w e v e r , t h e e x i s t i n gs o f t w a r ee v o l u t i o nt e c h n o l o g ya l s oh a sas e r i e so fp r o b l e m s ，s u c h a sh o wt op r e d e r i v et h er e s u l t so fc h a n g ea n dh o wt od e s i g naf l e x i b l e p l a n n i n go rm e c h a n i s mo fs o f t w a r ee v o l u t i o n i no r d e rt o f i xt h e s e p r o b l e m s t h i st h e s i si n t r o d u c e sw o r k f l o wi n t ot h ef i e l do fs o f t w a r e e v o l u t i o n t h u s t h ee v o l u t i o no p e r a t i o n sc a nb ec o m b i n a t e dt od e a lw i t l l m o r ec o m p l e xe v o l u t i o n a n dt h r o u g ht h ea n a l y s i so ft h ee v o l u t i o n w o r k f l o w , w ec a np r e d e r i v et h er e s u l t so fs o f t w a r ee v o l u t i o no ro p t i m i z e t h es o f t w a r ee v o l u t i o nw o r k n o w b a s e do ng r a p ht r a n s f o r m a t i o n ，t hi st h e s i sd e s c r i b e st h ew o r k f l o w m o d e lw i t ht i m ea n dr e s o u r c ea t t r i b u t e sb ya t t r i b u t e dt y p eg r a p h ( a t g ) a n dd e s i g n sas e to fg r a p ht r a n s f o r m a t i o nr u l e sf o rw o r k f l o wm o d e l i n g i no r d e rt oi m p r o v et h ea p p l i c a b i l i t yo ft h ew o r k f l o wm o d e l ，t h i s t h e s i si n t r o d u c e sa na p p r o a c ho fw o r k f l o wm o d e lc o r r e c t n e s sa n a l y s i s u s i n gg r a p hr e d u c t i o nf o rm a k i n g s u r et h ec o r r e c t n e s so fw o r k f l o wm o d e l s t r u c t u r a l l y t h i st h e s i sd e f i n e sa s e to fr u l e st od e a lw i t ht h ew o r k f l o w t i m ec o n s i s t a n c ya n a l y s i sa n dw o r k f l o wd e a d l i n ea n a l y s i sa n di n t r o d u c e s a na p p r o a c hb a s e do nt h ec o n c l u s i o no ft h ee x i s t i n gr e s e a r c ho nt h ef i e l d o fw o r k f l o ws c h e d ula b ili t ya n a l y s i s f i n a l l y , t h et h e s i sr e a l i z e st h es o f t w a r ee v o l u t i o nw o r k f l o wm o d e l i n g a n da n a l y s i st 0 0 1 w h i c hi su s e dt ot of i n i s ht h ew o r k f l o wm o d e l i n go nt h e s o f t w a r ee v o l u t i o no fc o n d i t i o n a la c c e p ts y s t e mf c a s ) t h et h e s i su s e s t h i st o o lt of i n i s ht h ec o r r e c t n e s s a n a l y s i s d e a d l i n ea n a l y s i s ，t i m e c o n s i s t a n c ya n a l y s i sa n ds c h e d u la b i li t y a n a l y s i s i ti sr e a l e f f e c t i v e w h i c hi sp r o v e db yt h er e s u l to fc a s es t u d yt h a tt h ea p p r o a c ho fs o f t w a r e e v o l u t i o nw o r k f l o wm o d e l i n ga n da n a l y s i s k e yw o r d ss o f t w a r ee v o l u t i o n ，a t t r i b u t e d t y p eg r a p h ，g r a p h t r a n s f o r m a t i o n ，w o r k f l o wm o d e l i n g ，w o r k f l o wa n a l y s i s 1 1 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：塑兹日期：巡年月旦日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 鸭期：趔年工月牟日 硕士学位论文 第一章绪论 1 1 课题研究背景 第一章绪论 在传统软件开发周期模型中，软件产品一旦交付使用就进入了软件维护阶 段。然而，以纠错、完善或适应为目的的软件维护仅仅是消极的对软件做某些程 度的局部改变，而没有涉及到较高抽象层次的结构，因而无法积极的适应在新环 境下用户需求的改变。也就是说，随着时间的推移，它不可避免的导致软件生存 状况的恶化因文档的逐渐缺失和开发人员的离去而导致信息丢失，而在较低 层次做出的调整无法满足新技术、新规范以及新需求的引入。这就迫使软件工程 师寻求新的方法。随着观念和技术的进步，人们已经开始在软件再工程活动中区 分软件维护和软件演化。 软件演化【l 】是指在软件系统的生命周期内软件维护和软件更新的动态行为。 在现代软件系统的生命周期内，演化是一项贯穿始终的活动，系统需求的改变、 功能实现的增强、新功能的加入、软件体系结构的改变、软件缺陷的修复，运行 环境的改变无不要求软件系统具有较强的演化能力，使之能够快速适应改变，减 少软件维护的代价【列。 调查表明，软件生命周期内的开销中约有9 0 【3 】用于软件的演化。软件演化 的研究对于延长软件生命周期、提高软件对新环境的适应能力、降低软件运行成 本有着重要的意义。但是，现有软件演化技术还存在一系列的问题没有得到根本 解决【4 j 。例如如何预先推导变更的结果及其影响范围，如何设计灵活的演化计划 和处理机制等。这些问题的存在，使得为进行软件演化而增加的代价和危险可能 超过其带来的好处。从而需要一种新的软件演化技术能够方便的完成更复杂的软 件演化；又可以对演化操作过程进行分析，以便于对软件演化结果的判断以及对 软件演化操作过程的优化。 1 2 国内外研究水平与现状 1 2 1 软件演化的定义 对软件演化目前没有统一的定义，以下为几种常见定义： r i s e ( t h er e s e a r c hi n s t i t u t ef o rs o f t w a r ee v o l u t i o n ) 认为，一般的软件演化涉 及到了软件交付给客户之后所发生的所有活动。它定义软件演化为一系列的活 动，包括技术上和管理上的，这些活动能够确保软件产品不断达到商业要求的目 硕士学位论文第一章绪论 标，目的是低成本高效的完成。 m a n n ym l e h m a na n dj u a ner a m i l 定义软件演化为：有目的地从早期的可 操作版本来产生新的软件版本的所有规划设计活动。 l a b e l a d y 的定义为：软件系统在它们的生命周期里被维护和增强的动态 行为。 n e dc h a p i n 定义软件演化为：它是软件维护活动和过程的一个运用，以及对 这些活动和过程质量的保证和管理。这些活动和过程是用来从一个早期的可运行 版本中来产生一个新的软件版本，这个新的软件必须满足客户要求改变的功能或 属性。 尽管软件演化的定义没有统一，但其实质都是一样的，软件演化是指在软件 系统的生命周期内软件维护和软件更新的动态行为。在现代软件系统的生命周期 内，演化是一项贯穿始终的活动，系统需求的改变、功能实现的增强、新功能的 加入、软件体系结构的改变、软件缺陷的修复，运行环境的改变无不要求软件系 统具有较强的演化能力，能够快速适应改变，减少软件维护的代价。 软件演化的核心问题是软件如何适应改变，软件的演化能力主要体现在四个 方面【7 】 可分析性( a n a l y z a b i l i t y ) ：根据演化需求，定位待修改部分的能力。具有良 好演化能力的软件应该容易分析、理解，从而可以根据变化迅速定位需要改变的 部分。 可修改性( c h a n g e a b i l i t y ) ：实现特定部分修改的能力。具有良好演化能力的软 件可以方便的修改，以支持变化。 稳定性( s t a b i l i t y ) ：避免软件修改造成不良后果的影响。 可测试性( t e s t a b i l i t y ) ：验证软件修改有效性的能力。 1 2 2 现有软件演化技术 现有软件演化技术主要包括： 1 基于自反射中间件的软件动态演化研究 反射式中间件( r e f l e c t i v em i d d l e w a r e ) 是一种通过开放内部实现细节以获取高 灵活性的中间件【引。具体而言，通过引入反射原理，中问件运行时的内部状态和 行为可通过一种受限方式访问和操纵。系统的反射性是指系统能够提供对自身状 态和行为的自我描述( 简称自述) ，并且系统的实际状态和行为始终与自述保持一 致，也就是说，对自述的改变能够立即反映到系统实际的状态和行为，而系统的 实际状态和行为改变也能够立即在自述中反映出来。一个反射系统通常定义了一 个层次化的反射体系，包括一个基层( b a s e 1 e v e l ) 和一个或多个元层( m e t a 1 e v e l ) 。 2 硕士学位论文第一章绪论 工作在基层中的实体( 基层实体) 执行系统正常的业务功能，而工作在元层中的实 体( 元层实体) 负责建立和维护系统自述。 自反射中间件由于在软件系统结构中引入了元数据( m e t a l 1 e v e l ) ，通过改变元 数据，可以有效地改变建立在元层之上的基层运行系统，因此自反射中间件在一 定程度上支持软件系统的开放性、动态性。但是这种方法没有涉及分布式环境下 的演化问题。 2 基于软件体系结构的软件演化研究 软件体系结构( s o f t w a r ea r c h i t e c t u r e ，s a ) 从提出之日起，就受到学术界和产业 界的广泛关注，成为软件工程研究与实践的重要领域之一。 在设计时演化方面，一些研究者希望在设计阶段考虑系统运行时的变化并将 之纪录在设计文档中，如d a r w i n ，x a d l l 9 | 。这种软件体系结构拥有丰富的语义信 息，为在软件系统设计阶段捕获系统的动态特性提供了形式模型和自动化支持。 拥有丰富的语义信息。但是，实际应用中设计阶段可预测的运行时变化有限，准 确度难以保证，运行时如何使能或保障这些变化也没有考虑。 在动态演化方面，o r e i z y t l o 】等人研究了如何基于c 2 1 1 1 】体系结构风格，实现 软件系统的运行时修改，他们开发的一个演化终端a r c h s h e l l 实现了运行时软件 系统构件的动态组装、添加。但是没有涉及没有涉及分布式环境下的演化问题。 3 基于图的动态体系结构的研究 文献 1 2 ，1 3 提出一种面向“图”的分布式w e b 应用软件系统架构技术，利 用严格定义的“图”来作为描述分布式w e b 应用软件体系结构的基本手段，并 用图上的操作来支持系统体系结构的动态重配置。这种以图来表示的软件体系结 构不仅仅是高层的抽象描述，同时也是具体的可操作的对象实体，从而有助于提 高体系结构与最终实现之间的可追溯性。该对象存在于具体的系统实现中，充当 了两个关键的角色：( 1 ) 沟通各分布的计算构件之间的通信中间件：( 2 ) 整个应用 的体系结构框架。通过在系统实现中显式地使用表述体系结构的对象，整个系统 获得了类似自反射中间件的能力，从而为支持体系结构的动态重配置提供了便 利。 基于图的体系结构将分布式系统抽象为一个无向图或有向图，便于对分布式 系统进行理论分析和形式模型的研究。但由于分布式系统的各个节点需要维护一 个全局拓扑结构图，在系统规模增大的情况下，图的维护变得相当困难。同时基 于图的体系结构在进行动态演化时，需要对图的整体拓扑结构进行变换，包括图 的状态信息的转换，当系统规模增大时，动态演化的复杂程度和代价都相当大， 使得这结构难以适应i n t e r n e t 的动态广域计算环境。 除了上述三种软件演化方法各自拥有的不足外，现有软件演化技术还存在一 硕士学位论文 第一章绪论 些问题，例如：如何预先推导变更的结果及其影响范围，如何设计灵活的演化计 划和处理机制等。 1 3 论文工作研究意义及主要内容 为了解决现有软件演化环境所具有的有地域分布性、异步协同性、同步协同 性等新的特点及动态演化普遍存在的问题，如：如何预先推导变更的结果及其影 响范围，如何设计灵活的演化计划和处理机制等。论文将工作流引入软件演化领 域，这样做既可以将若干演化操作进行组合，以便于完成更复杂的软件演化，又 可以对演化操作工作流进行分析，以便于对软件演化结果的判断以及对软件演化 操作工作流的优化。 鉴于现有工作流建模技术中存在的在可视化、形式化、描述的全面性、过程 分析以及建模难度等方面难以均衡的问题，本论文利用带属性类型图来描述工作 流模型，并利用图变换理论进行工作流建模与分析。论文的研究主要内容分为以 下几点： 1 利用带属性类型图来描述时间与资源工作流模型，并使用图变换技术， 设计一个图变换规则集来实现工作流过程模型的建立。 - 2 利用图规约的方法进行工作流过程模型正确性分析，保证所得到的工作 流模型在结构上是正确的；设计一个图变换规则集完成了工作流过程模型的时间 截止性分析和时间约束性分析；并在总结前人的基础上提出了一套工作流过程模 型可调度性分析的办法。 3 实现了软件演化工作流建模与分析原型工具，并利用该软件实现了数字 电视条件接收系统的软件演化建模，最后对所得到的模型进行了正确性分析、时 间截止性分析以及可调度性分析。 1 4 论文章节安排 本论文分为六章，论文结构安排如下： 第二章对工作流相关技术进行了深入研究。在介绍了工作流相关概念后，总 结了现有工作流建模技术的现状及不足，也对现有工作流分析技术进行了总结， 并在介绍了带属性类型图与图变换概念的基础上阐述了基于带属性类型图图变 换的工作流建模的优势。 第三章首先利用图变换技术实现了工作流过程模型的建立包括了工作流建 模的抽象语法、具体语法与操作规则并给出了操作规则的完备性证明。 第四章利用图规约的方法，基于图变换技术，实现了工作流过程模型的正确 4 硕士学位论文第一章绪论 性验证；在工作流时间建模的基础上，完成了工作流过程模型的时间截止性分析 并给出了工作流过程模型时间截止性分析的完备性证明；基于工作流过程模型的 时间性能分析给出了工作流过程模型时间约束下的可调度性分析方法。 第五章设计并完成了基于图变换的软件演化工作流建模与分析工具，利用该 工具成功实现了数字电视条件接收系统的演化建模，并对所得到的模型进行正确 性、时间截止性和可调度性分析。 第六章对本论文工作所进行的主要研究内容进行了总结，及下一步的研究方 向与展望。 硕士学位论文 第二章工作流技术概述 第二章工作流技术概述 工作流( w o r k f l o w ) 技术的发展可以追溯到多个起源，如办公自动化、计算机 辅助协同工作( c o m p u t e rs u p p o r tc o o p e r a t i v ew o r k ，c s c w ) 、文档管理以及数据 库技术。目的是通过将工作流分解定义成良好的人物角色，按照一定的规则和过 程来执行这些任务，并对其进行控制，以达到提高办事效率、完善客户关系服务、 灵活变更活动进程、提高经营管理水平和企业竞争力。 2 1 工作流的有关定义 有关工作流的定义根据工作流工作者的不同而各有不同，十几年以来一直没 有形成一个统一的定义。以下列举一些有代表性的定义，分别从不同的角度对工 作流的概念进行了描述。 工作流管理联盟的定义n 劓：工作流是一类能够完全或者部分自动执行的经营 过程，根据一系列过程规则，文档、信息或任务能够在不同的执行者之间传递、 执行。 g i g a g r o u p 的定义甜：工作流是经营过程中可运转的部分，包括任务的顺序 以及由谁来执行、支持任务的信息流、评价与控制任务的跟踪、报告机制。 m ma l m a d e n r e s e a r c h c e n t e r 的定义n 引：工作流是经营过程中的一种计算机 化的表示模型，定义了完成整个过程所需用的各种参数。这些参数包括对过程中 每一个单独步骤的定义、步骤间的执行顺序、条件以及数据流的建立、每一步骤 由谁负责以及每个活动所需要的应用程序。 g e o r g a k o p o u l o u s 给出的工作流的定义n7 1 ：工作流是将一组任务( t a s k ) 组织起 来完成某个经营过程。在工作流中定义了任务的触发顺序和触发条件。每个任务 可以由一个或多个软件系统完成，也可以由一个或一组人完成，还可以由一个或 多个人与软件系统协作完成。任务的触发顺序和触发条件用来定义并实现任务的 触发、任务的同步和信息流( 数据流) 的传递。 以上这些对工作流的定义是用非形式化语言对工作流所进行的描述，虽然各 有不同，但基本上都达成了这样的一个共识：工作流是经营过程的一个计算机实 现，而工作流管理系统则是这一实现的软件环境。这些工作流的定义分别反映了 经营过程如下几个方面的问题，即经营过程是什么( 由哪些活动、任务组成，也 就是结构上的定义) 、怎么做( 活动间的执行条件、规则以及所交互的信息，也就 是控制流与信息流的定义) 、由谁来做( 人或者计算机应用程序，也就是组织角色 的定义) 、做得怎样( 通过工作流管理系统进行监控) 。 6 硕士学位论文第二章工作流技术概述 图2 1 描述与工作流相关的基本概念及关系n 引。 子 业务流程 图2 1 工作流基本概念之间的关系 工具 业务流程( b u s i n e s sp r o c e s s ) ：在功能确定的组织结构中，能够实现业务目标 和策略的相互连接的过程和活动集。例如，公文处理过程、投保过程及项目开发 过程等。 活动( a c t i v i t y ) ：指的是工作流中的一个逻辑步骤或称环节。它包含的信息有： 开始和结束条件、可参与到此环节中的用户、完成此活动所需的应用程序或数据 以及关于此活动应如何完成的一些限制条件如时间上的限制等。 工作流管理系统( w f m s ) ：w f m c 给出工作流管理系统的定义是，工作流管 理系统是一个软件系统，它完成工作流的定义和管理，并按照在计算机中预先定 义好的工作流逻辑推进工作流实例的执行。 过程定义( p r o c e s sd e f i n i t i o n ) ：业务过程的计算机形式表示，它定义的是过程 运行中涉及到的各种参数，如业务过程的开始和终止条件、各个工作环节及相互 之间的控制流动与数据流动关系等。不同的w 伽s 所实现的工作流模型是各不 相同的，不同的过程模型各有其不同的特点，一个好的模型应该有比较强的描述 能力、易于使用、易于修改以便能够适应不断变化的工作环境的要求。 过程活动实例( p r o c e s sa c t i v i t yi n s t a n c e s ) ：指的是某个工作流过程的一次执 行。在实例的执行过程中，w f m s 将解释相应的过程定义，生成有关的活动并根 据过程定义中的控制规则协调这些活动实例之间的顺序关系，同时根据数据流动 关系的定义完成活动实例之间的数据传送。一般情况下每一个活动实例都将表现 为一个工作项( w o r k l i s t ) ，它将由某个或某组用户负责完成。因此从用户的角度 硕士学位论文第二章工作流技术概述 来说实例的执行实际上是由用户调用相应的应用程序对他所涉及的那个环节有 关的数据进行处理，处理完之后由w f m s 根据相应的结果决定激活后续的那个 环节并生成相应的工作项，同时通知与此有关的那些用户对之进行处理。由此依 次反复进行，直至整个过程的完成。某个用户所负责的所有工作项将构成其工作 项列表( w o r k l i s t ) 。那些被称作是工作流应用数据的，其中有一部分将同工作流过 程定义一道用于控制工作流的执行。这部分数据一般被称作是工作流相关数据。 工作流管理系统可以根据经营过程以及组成活动的复杂程度，采用不同的实 施方式。在实施方中，所应用的信息技术、通信技术和支撑系统结构会有很大的 差别。但从比较高的层次上来抽象地考察工作流管理系统，可以发现工作流管理 系统还是具有许多共同的特性，一般都提供3 种功能： ( 1 ) 建立阶段功能：主要考虑工作流过程和相关活动的定义和建模功能； ( 2 ) 运行阶段的控制功能：在一定的运行环境下，执行工作流过程，并完成 每个过程中活动的排序和调度功能： ( 3 ) 运行阶段的人机交互功能：实现各种活动执行过程中，用户与i t 应用工 具之间的交互。 图2 2 给出了工作流关系系统三个主要功能之间的关系。 过程设计与定义 建立阶段 运行蚧段 过程实饲化与控制 人机交互 经营过程分折、 建摸与定义工具 空 1 。一 过程定义 工作旎执行凰务 奎 图2 2 工作流管理系统的特性 软件工具 与应用 同工作流管理系统的3 个功能相对应，工作流管理系统在实际系统中的应用 一般分为3 个阶段，即模型建立阶段、模型实例化阶段和模型执行阶段。如图 2 3 所示。在模型建立阶段，利用工作流建模工具，完成企业经营过程模型的建 立，将企业的实际经营过程转化为计算机可处理的工作流模型。模型实例化阶段， 给每个过程设定运行所需的参数，并为每个活动分配所需的资源( 包括设备、人 员、应用) 。模型执行阶段，完成经营过程的执行，在这个过程中重要的任务是 完成人机交互和应用的执行，并对过程与活动的执行情况进行监控与跟踪。 8 硕士学位论文 第二章工作流技术概述 过提定义 过程实饲 过程建模 = = = 剖过程实饲化 = = = = 剖过程运行 分析，定义过程 2 2 工作流建模技术 参与 执行 过捏 累坑管理员 一般用户 图2 - 3 工作流管理系统实施阶段 产品 或其他结果 一个工作流系统包括两个重要组成部分，一是工作流过程模型，一是工作流 引擎。工作流建模在工作流技术中具有非常重要的意义，工作流过程模型的好坏 直接影响着整个工作流系统的性能。工作流建模技术一般包括以下几个性能指 标：可视化、形式化语义、验证方法、描述范围、难易程度等。现有工作流建模 主要采用基于活动网络图的方法、基于p e t r i 网的方法、基于逻辑的方法、基于 代数的方法与基于规则的方法等。 1 基于活动网络图的方法 m m 采用了基于活动网络图的方法，工作流用一个有向图来表示n 引。图中的 节点表示任务或活动，节点间的连接弧表示工作流中的数据流或控制流，组成工 作流模型的元素包括了过程、活动、模块、控制连接弧、数据连接弧和条件。 采用基于活动网络图的方法，具有建模可视化及建模难度小的特点，但是， 由于该方法不支持形式化语义，因而不能进行模型验证。且该方法中采用图形节 点与连接弧来描述工作流，并不能描述工作流模型的资源等，描述范围不大。 2 基于p e t r i 网的方法 c a p e t r i 博士建立p e t r i 网的最初想法是从对异步并发的计算机和通信系统 进行建模的过程中产生的。由于p e t r i 网具有图形化的界面与良好的数学语义， 目前针对将p e t r i 网应用于工作流建模中进行了大量研究陋2 3 1 。s t e p h e n 等人他们用 库所表示任务，用变迁来表示控制活动，而工作流过程则采用具有颜色和层次的 高级p e t r i 网来表示，并通过工具n c u p n 对工作流模型进行分析。e l l i s 幢引采用 了信息控制网i c n 描述工作流模型，信息控制网是一种在p e t r i 网e 网的基础上， 扩展了数据流的表示。它由活动节点( 库所) 、o r 控制节点( 变迁) 、a n d 控制 节点( 变迁) 组成。它还有仓库节点，以表示持久数据。此外，信息控制网的形 9 他鎏垤 一 冒 嚣 师 l 1开醒。啊l姐过 硕士学位论文 第二章工作流技术概述 式化表示上还增加了完成活动的角色和人员的映射信息，并引入了s e n d t o 原语 以进一步表示工作流的例外处理。v a nd e rm a s t 陪2 采用了w f n e t 网表示工作流 模型。w f n e t 网是p e t r i 网的一个子集。其中活动和控制元素都用变迁表示，两 者之间采用辅助的库所来连接。n a b i i 啪1 采用了不同的方法来表示任务。它建模 了细粒度的任务状态。在它的p n 框架中，任务不再是单一的库所或变迁来表示。 任务被建模成一组表示任务状态的库所和表示任务间状态转移的变迁来共同表 示。任务状态被区分为：i n i t i a l ，e x c u t i o n ，d o n e ，c o m m i t ，a b o r t 。 可以看到，利用p e t r i 网进行建模的一般思想是采用扩展常规的p c t r i 网，以 表达工作流中活动间的关系，但归纳起来，各种建模方法大致可以分为以下三类： ( 1 ) 用p e t r i 网的库所表示任务，变迁表示控制元素 ( 2 ) 用p e t r i 网的变迁表示任务，库所表示控制元素 ( 3 ) 用一组变迁和库所来表示任务。 采用p e t r i 网的方法具有可视化的界面、形式化语义、能进行模型分析，但是 建模难度大。 3 基于逻辑的方法 d a v u l c a 1 采用并发事务逻辑c t r ( c o n c u r r e n tt r a n s i t i o nl o g i c ) 来表示工作 流模型。在c t r 模型中，除了经典的逻辑连接符号与、或、非、凡是、存在外， 还增加了顺序、并发、可能、单独执行等符号。工作流的控制流程可以用这些逻 辑符号组成的合式公式表示。应用a p p l y 编译算法能够将一个工作流图编译成 c t r 表示的共识。与机遇图的方法相比，采用逻辑的一个优势是能够表达全局 约束。这些全局约束也能够用逻辑来描述。从而使工作流模型的描述和验证位于 一个统一的框架中。但是基于逻辑的建模方法，也具有显著的缺陷：难度大和缺 乏方便的图形化手段。 4 基于进程代数的方法 进程代数是一种刻画并发计算的工具，目前在工作流研究领域还没有得到广 泛的研究和足够的重视。文献【3 0 】采用l o t o s 来进行软件过程的建模。l o t o s 是一种描述通信的进程函数。由于软件过程和业务过程的相似性，因而也证明了 进程代数可以用来描述工作流模型。 同基于逻辑的方法一样，进程代数的方法也具有严密的形式化语义。因而很 容易进行验证。而进程代数由于逻辑的优点是，它提供了一个从低层子系统而复 合系统的方法。其缺点是：缺乏图形化描述，建模难度大。 5 基于规则的方法 e c a 规则，即事件条件一动作规则，来源于主动数据库技术。现在e c a 规 则已经被大量应用于工作流工作流领域。 b u s s l e r n 用e c a 规则来描述对执行试题的通知和同步策略。任务是执行实 1 0 硕士学位论文 第二章工作流技术概述 体的任务列表中的项，它们由执行实体选择一个或多个错作而执行完成。任务的 执行必须根据由e c a 规则规定的同步策略完成。e c a 规则的事件都是一些基本 事件。这些事件可以与w f m s 数据库中任务的状态有关。e c a 规则的条件表示 与任务执行实体关系、执行实体选择、任务完成状况等有关的完整性约束。其 动作表示对数据库中人物状态和执行实体的任务列表的更改。 e c a 规则不仅可以用来描述活动间的控制流关系，而且能够表达组织、角色 之间的约束关系。基于规则的方法还能够支持工作流的动态修改，从而使工作流 具有一定的灵活性。但e c a 规则作为一种低层实现机制，缺乏图示化的手段和 结构化构造工作流模型的方法。另外，当规则不断增加时，处理规则变的很繁琐。 就语义而言，e c a 规则本身必须借助其它方法来表示，因而很难对e c a 规则表 示的工作流模型进行验证。 表2 1 对各种工作流建模技术进行比较。 表2 - 1 工作流建模技术对比 总而言之，现有工作流过程模型在可视化、形式化、描述的全面性、过程分 析以及建模难度等方面难以均衡。 2 3 工作流模型分析 一个工作流模型定义完后，在其执行前需要通过各种分析方法或分析工具验 证其是否能够正确地执行，一般这个验证过程被称为工作流模型分析。工作流模 型在业务过程的理解、分析和重组方面起着关键性的作用，一个定义完善、正确 的工作流模型能使工作流运行效率和可靠性得到提高。工作流模型中任何不足将 使业务目标不能完成，因此，工作流模型分析是必不可少的一个环节。 工作流模型分析主要包括以下2 个方面的内容： 1 正确性证明：验证工作流模型的正确性。 2 性能分析：评价工作流的某些性能参数，如工作流平均执行时间、活动平 硕士学位论文第二章工作流技术概述 均等待时间、资源占有率、服务水平等。 在将工作流引入软件演化领域后，软件演化工作流模型也需要通过正确性分 析来确保模型的正确性。 此外，对软件演化工作流模型进行时间性能分析是非常有必要的。如果整个 软件演化不能在预定的时间内完成，则会造成演化成本上升或者更坏的情况。尤 其是，某些软件演化在演化时可能造成整个系统无法运行，需要严格限制整个软 件演化的执行截止时间。因此需要对软件演化工作流模型进行时间截止性分析。 而有些时候，软件演化的某些操作具有很强的时间约束性，比如某个操作严格限 定只能在某个时间段完成，因此还需要对软件演化工作流模型进行时间约束性分 析。 由于资源的独占性或其他原因，可能会造成整个工作流模型在执行时发生错 误。因此，针对时间与资源进行的软件演化工作流可调度性分析对于保障软件演 化的正确进行是非常有必要的。 2 3 1 正确性分析 工作流正确性分析最普遍使用的是基于p e t r i 网的方法陋矧。它的主要思想 是检查工作流模型是否满足下列条件：1 ) 如果每个库所都存在到达终止库所的路 径；2 ) 存在唯一终止库所；3 ) 每个转换都可触发。如果满足，那么工作流模型可 以称为是正确的。还有通过把工作流模型表示成p e t r i 网的一个变种工作 流网，从而使用经典的p e t r i 网性质对工作流进行验证。工作流是有效的当且仅 当其对应的工作流网是活的并且是有界的。也可以通过化简规则对工作流网进行 化简，如果它最终能够化简为一个库所则工作流模型是正确的。 由于u m l 活动图适合建模数据流，有人用类似于p e t r i 的语义定义了活动图 的数据流语义，验证数据流的正确性m 1 。 除此之外，还出现了基于图规约法的工作流模型验证m 1 ，它使用有向有环图 建立工作流模型，根据规约规则化简模型。基本原理是规约过程从工作流模型中 删去所有已被确认为正确的结构，保留冲突的结构。如果一个工作流模型是正确 的，则该规约过程将会化简为一个空图；反之若该图有冲突存在，则不能完全被 化简。 2 3 2 性能分析 工作流过程模型性能分析的目标评价工作流的某些性能参数，如工作流平均 执行时间、活动平均等待时间、资源占有率、服务水平等。现在工作流模型的性 能分析主要集中在时间性能方面。 1 2 硕士学位论文第二章工作流技术概述 文献提出了由任意多个变迁组成的串联、并联、选择和循环结构的性能等 价公式，给出了定量分析工作流时间性能的通用方法；文献 3 9 也分析了可以由 基本模块组合构造的工作流的时间性能，对于不能由基本模块组合构造的工作 流，提出了一种分析其时间性能上下界的方法。 时序分析关心的是工作流模型中各任务之间的时序依赖关系，包括时序关系 推理1 1 、时序关系一致性验证嘞1 和与时间有关的安全性( s a f e t y ) h 别、活性 ( l i v e n e s s ) h 引、可调度性( s c h e d u l a b i l i t y ) m 1 、截止期限( d e a d l i n e ) h 汹1 、 有界性( b o u n d e d n e s s ) h 刀分析等。时序分析可分为定性分析和定量分析。 传统的基于a l l e n 的时段时序逻辑( i n t e r v a lt e m p o r a ll o g i c ，简称i t l ) h 町的 定性时序推理方法无法解决不确定时段之间的时序关系推理和一致性问题，传统 的定量时序推理方法h 训基于模型的状态可达图，因此时间复杂性很高。 k a f e z a 隋着重于活动间的相对同步关系，将活动间的时序依赖转化为统一的 二元时序约束，通过为工作流图的有向边增加时间标签来包含业务过程的时间信 息。时间管理的关键在于活动的时序协调，考虑到活动延迟与截止期限约束，用 活动开始完成事件发生的顺序来表示工作流的时序约束。 v a nd e ra a l s t 用着色时间p e t r i 网对活动时间固定的工作流的一些时间特性作 了分析m 1 ；李建强临3 1 将工作流网分解成代表事件的t - 图，通过t - 图分析了工作流 模型的时间性能、资源利用率等动态特性。 2 3 3 可调度性分析 调度问题是在现实生活中普通存在的问题。工作流调度是找到一个满足业务 逻辑约束的工作流任务执行的正确序列1 。它与其它领域的调度问题相比，存在 许多不同，其中最主要的是工作流是动态的，它具有较多的不确定性。这些不确 定性包括工作流本身的不确定性，如工作流实例的到达是不确定的、工作流实例 的执行路径和任务执行次数是不确定的；工作流运行环境的不确定性，如由于工 作流执行过程持续较长的时间，可用的资源、数量和组成在这段时间里发生变化； 资源的能力、任务的难度、资源当前的负荷、资源的兴趣等多个因素均会对任务 的资源分配产生影响，而这些因素往往都是动态变化的。 现有的工作流调度方法可以分为两类：静态调度和动态调度。静态调度即事 前调度，一次性地对工作流所包含的所有活动进行调度。这种调度方法理论上可 以达到在当前状态下的全局最优。但随着工作流环境的动态变化、工作流实例的 并发进行，静态调度的结果并不总是最优的。而且静态调度通常无法处理工作流 的不确定性。目前已有的工作流静态调度方面的研究大都没有处理工作流的不确 定性。如基于逻辑m 1 、p e n - i 网等的工作流调度，大多数是只考虑了满足时间和 1 3 硕士学位论文 第二章工作流技术概述 结构约束的工作流静态调度。s e n k u l 等人阳1 提出的静态预调度方法考虑了工作流 的资源约束。b a g g i o 等1 也采用静态调度的方法，他们考虑了工作流的不确定 性，提出使用猜测的方式来处理工作流的不确定性。但采用这种猜测的方法，当 实际情况与猜测情况产生偏差时，需要采取一系列的补救措施。 2 4 图变换理论 2 4 1 带属性的类型图 定义2 1 ( e - 图) 阳：一个e - 图g 2 ( 虼，e g ，耳。，( 舳甜r c e j ，t a r g e t j ) ，。 g 朋默 ， 其中圪为图节点集合，为数据节点集合，最为图边集合，为节点属性边集 合，e 队为边属性边集合。其中， s o u r c e g ：丘j k ，边到源节点( 图节点) 的映射； l a r g e i c ：反一圪，边到终节点( 图节点) 的映射； s o u r c e n ：j 圪，节点属性边到对应图节点的映射； t a r g e t m ：氏一，节点属性边到数据节点的映射； s o u r c e a ：j 鼠，边属性边到对应图边的映射； t a r g e t u ：一，边属性边到数据节点的映射； 定义2 - 2 ( 属性图) 陋：给定一个数据基调d s i g = ( s d ，o p o ) ，s d 为数据类别集， o p o 操作符集，踮s o 为属性值对应的类别集，则一个属性图a g = ( g ，d ) ，其 中g 为e 图，d 为基调d s i g 上的数据代数，且u “皿= 。 定义2 3 ( 带属性的类型图) ：一个带属性的类型图是一个带属性图 a t g = ( r g ，z ) ，其中t g 为e 图，z 为一个终结d s i g 代数，其载体集 乏= s ) ，v ss o 。 带属性类型图具有描述能力强、表达直观、易用等特点，带属性类型图被普 遍应用于软件工程及可视化语言中模型或元模型的建立。 2 4 2 图变换 图变换兼有形式化和直观的特点，尤其是，图变换能为可视化模型的操作提 供可视化、基于规则的方法。这使得图变换已经被广泛的应用于计算机科学的很 多领域，例如模型演化、形式化语言理论、模式识别、软件工程等。 正式由于以上特点，本文致力于将图变换理论引入到工作流模型分析领域中。 在此之前，先对图变换理论中的几个基本概念进行简要说明。 定义2 - 4 ( 图和图态射) 旧：一个图g = ( g e ，g v ，s ，t ) ，包括了一个边集g e