可靠服务组合的协调策略与分析

可靠服务组合的协调策略与分析范贵生 刘冬梅 陈丽琼虞慧群(华东理工大学运算机科学与工程系 ,上海 200237)摘 要：服务组合是构建复杂 Web软件的有效方法，但服务事务状态的多样性使得服务组合的可靠性难以保证。为此，提出一种构造可靠服务组合的和谐方法。该方法采纳 Petri网对工作流建模，以清晰地表达任务及任务之间的逻辑关系。在此基础上，按照服务的事务属性及服务组合的失效处理机制建立服务组合的失效处理模型，并提出一种构造可靠服务组合的和谐策略及实施方法。利用 Petri网有关理论证明该策略的有效性。旅行服务实例演示了和谐技术的应用方法及其可行性。关键词 Petri网；Web服务；服务组合；事务；可靠性引言随着Internet技术应用的迅速进展，基于Web服务的分布式运算模式差不多成为软件进展的趋势。 Web服务能够统一地封装信息、行为以及业务流程，而无需考虑应用所在的环境。通过Web服务组合来动态生成新的应用系统，以满足实际的需要，已成为Web服务技术持续向前进展的技术动力[1]。然而，Web服务事务状态的多样性使得服务组合变得更为可靠和有效之前，还有一些咨询题需要处理。其中关键咨询题确实是如何构建可靠服务组合，即如何按照服务的事务属性来分配可用服务以满足服务消费者的需求。尽管传统的事务技术在数据

库系统和分布式系统中得到了广泛的应用，但由于Web服务自身的松耦合性、运行时刻长、长事务等特点，使其在系统的可靠性和一致性方面面临新的挑战，如何对服务的事务属性进行形式化分析成为业界广泛讨论并关注的咨询题[2]。Petri网作为一种直观的图形建模工具和一种具有丰富数学基础的形式化模型，能够广泛应用于描述和研究并发、异步和分布式特点的系统，并提供了一种可操作语义及定性和定量分析[3]。最近的研究表明，Petri网适合用来描述服务组合的特性[4,17]。而可靠服务组合的构建不仅能够满足服务消费者的功能需求，同时也能反应出服务的事务属性及失效处理。Petri网及其有关的分析方法为这些目标实现提供了理论基础。本文要解决的确实是如何按照服务消费者的需求来动态地分配可用服务，以构建所需的可靠服务组合。为此，提出一种基于Petri网构建可靠服务组合的方法。差不多思路为：第一利用Petri网对任务及任务间的关系进行建模，生成相应的工作流模型；其次针对服务的事务属性，构建服务组合的失效处理模型（ServiceComposition’sFailureProcessing,SCFP），并分析SCFP模型的动态性质，从而保证所得到模型的正确性；最后给出可靠服务组合的定义，分析可靠服务组合构造的充分必要条件，提出相应的和谐策略并证明其有效性，同时给出和谐策略的具体实施。本文第2节给出了工作流的 Petri网模型；第3节分析服务的事务属性和服务组合的失效处理机制，生成相应的SCFP模型；第4节提出可靠服务组合的和谐策略及实施方法；第5节通过具体实例讲明可靠服务组合的构建与分析过程；第 6节阐述了有关的研究工作；最后是结论和下一步工作。

工作流的Petri网模型服务组合的功能能够由多个独立运行的子功能构成，本文将每个子功能称为任务。在服务组合流程中，每个任务会有多个可用服务与之对应。本文假设每个服务只能完成一个任务的功能，因此在服务组合中服务和任务是一一对应的。带事务属性的服务组合流程能够从工作流和失效处理两方面进行描述[15]，工作流描述任务之间的数据通信或同步，具体讲明了任务组件之间的关系，直观上能够懂得为一系列任务的依靠关系。而服务组合的失效处理则规约了服务运行失败时的处理机制，定义了服务的事务属性和服务的失败处理。两者要紧区别是：前者假设服务还没分配，仅仅描述服务组合流程的数据依靠；后者假设服务差不多分配，要紧考虑服务的事务属性和服务失败处理。本节依据服务消费者提供的功能需求，利用Petri网的差不多原理，按接口匹配的原则建立系统的工作流模型。2.1任务Petri网模型由于系统的功能是由一系列任务组合而成，而任务的组合又能够构成一个新的任务，如此嵌套能够构造出任意复杂的系统。因此，可利用Petri网对任务进行建模，且每个任务在运行过程中需要输入某些参数和输出一定的结果。下面给出任务的形式化定义。定义1：有界Petri网C=(P,T,F)称作任务，其中：1）P=PSPI是一个有限库所集，PI表示任务的接口，PS表示任务的位置，其中PSPI=；2）T是一个有限的变迁集，m≥0，同时PT≠,PPi3T=；Pi1P1t1P2(T×P)是有向（3）F(P×T)弧集合，F称为流关系；tePePintinP3t2P4Pi2图1带有接口的任务C1在任务模型中，接口代表该任务输入或输出（参数则映射为库所中的令牌）。本文假设任务只有获得所需参数才能运行开始操作，且运行终止后统一输出参数，具体接口个数能够按照实际情形增减。图1中的任务C1有三个接口：库所Pi1和Pi2存放任务开始操作（tin）所需的参数，而库所Pi3则存放任务终止（tin）的输出结果。Pin,Pe表示任务C1的开始和终止位置。某时刻各库所中令牌的分布状况称为任务的标识，在标识M下，

库所p中的令牌数量记为 M(p)；变迁t在标识M下使能的，记做M[t>，否则记做M[t<；任意x(PT)，集合●x={y|y(PT)(y,x)F}和x●={y|y(PT)(x,y)F}分别对应于x的输入和输出；其它的定义和触发规则与差不多Petri网的定义一样，具体参照文献[3]。2.2工作流模型本文采纳了进程代数的一种扩展机制来描述工作流中各个任务之间的关系，形成整个系统所对应的表达式[5]。在应用算子的过程中，能够用括弧来表达作用的顺序（其中顺序算子的优先级最高）。由于模型中的循环结构，能够利用文献 [6]介绍的“解循环”操作，即通过统计任务的历史数据，运算循环的平均执行次数n。因此，本文要紧对任务间的顺序、选择和并发关系建模，循环结构能够通过任务的顺序执行来完成。假设Ci和Cj为两个任务，下面先描述任务间的差不多关系：（1）算子>表示顺序：Ci>Cj表示任务Ci和Cj顺序运行，即Cj只有在Ci运行终止后才能开始。（2）算子+表示选择：Ci+Cj表示任务Ci和Cj只有一个能够运行。3）算子||表示并行：Ci||Cj表示任务Ci和Cj能够同时运行，但要它们都执行终止后整个组合才算执行终止。通过采纳上述的算子能够将任务间的关系描述为一个表达式。将在任务Ci运行时刻差不多终止的任务称为Ci的前向任务，而Ci运行终止时还未开始的任务称为Ci的后向任务。为了区别任务的操作，在相应的变迁和库所前标注对应的任务。如任务Ci中的开始变迁，表示为Citin。如果变迁是为了描述任务间关系而引入，则不标注。顺序结构承诺两个任务Ci和Cj顺序地执行，当一个任务需要用到另外一个任务的输出时就要使用顺序结构来组合。顺序运行Ci>Cj的Petri网模型如图2所示。在Ci和Cj中引入接口Pij使得，●Pij=Ci te，Pij●=Cj tin。Pij的存在使得任务 CPijj只能C在i.teCi终止之后C.PC开j.tin始运行。j inCi.Pe图2顺序关系的建模为了构造任务间的并行，选择和循环关系，需要分别对任务间的两对差不多组件即AND-split和OR-split，AND-join和OR-join进行建模，具体的Petri网模型如图3所示（设

任务Ck是Ci1,Ci2, ,Cim的共同前向/后向任务）。AND-split的Petri网模型如图3（a）所示：在Ck中引入接口Pki1,Pki2,,Pkim，每个并行的任务Cij中引入接口Pkij。其中●Pkij=Ck te,Pkij●=Cij tin,j=1,2,,n。OR-split的Petri网模型如图3（b）所示：在Ck和所有的选择任务中引入接口Pij使得●Pij=Ckte,Pij●={Ci1tin,Ci2tin,,Cim tin}。AND-join的Petri网模型如图3c）所示：在Ck中引入接口Pki1,Pki2,,Pkim，每个并行的任务Cij中引入接口Pkij。其中Pkij●=Ck tin,●Pkij=Cij te,j=1,Ck.teCk.PeCkPeCk.te2,,n。PiPki1Cim.PinPkimPki2Ci1.PinCim.PinCi2.PinCi1.Pin网模型如图3OR-join的PetriCi2.Pin............Cim.tinCi2.tinCi2.tinCi1.tinCim.tin(b)OR-split(a)AND-splitCim.teCi2.teCi1.teCim.teCi2.teCi1.tetiCi2.Pe............n,Ci1Pete,,CiPij={Ci1Pki1te,Ci2.ki2Cim.Pin●PkimCk.PinCi1.Pemte}。Ck.PinPiCk.tinCk.tin(c)AND-join(d)OR-join图3 差不多组件的建模下面结合Petri网的合成运算，匹配相应的接口以构造整个系统的工作流模型。定义2：设系统中的任务Ci=(Pi,Ti,Fi)，则按照下列步骤构造的五元组=(C;P,T,F,M0)称为系统的工作流模型：1）C={C1,C2,,Cn}，为系统中任务的个数；2）依据任务间关系，合成C1,C2,,Cn的对应接口；3）引入变迁Tstart和库所Pstart分别描述整个系统的初始位置和开始操作，且：●Tstart={Pstart},Tstart●={Ci1 Pin,Ci2 Pin,,CinPin},●Pstart=,Pstart●={Tstart}；4）设置初始标识M0(Pstart)=1，其余库所为0。工作流模型描述整个系统所能完成的功能，对工作流模型中每个任务分配具体的服务则构成了服务组合。如果分配过程中考虑服务的事务属性，则称它为带事务属性的服务组合。本文中如无专门讲明，服务组合均指带事务属性的服务组合。下面按照所得的工作流模型构造服务组合的失效处理模型。服务组合的失效处理模型

3.1服务的事务属性由于Web服务自身的特点，使得传统的事务处理技术无法直截了当应用在Web服务事务的处理过程，文献[7]提出的模型指明了服务事务属性的语义，该模型是基于文献[8]所考虑的三种不同的类型的事务属性。由此能够延伸Web服务执行任务时要紧有下面三种特性：可重复的（r），可补偿的（cp），不可补偿也不可重复的（p）。相应的服务事务属性能够有以下几种情形：{cp}、{p}、{r}、{r,cp}。按照服务的事务属性，能够建立如图 4所示的模型。图4（a）是对可补偿的服务进行建模，PItr表示该服务事务处理的条件。库所SiPItr中有令牌表示服务组合中有其它服务失败，需要按照服务Si的事务属性进行相应的和谐。而服务的输入和输出（PIin,PIe）按照实际需要能够进行增减。可补偿服务的运行过程可能处于初始、运行、终止、中断、取消、补偿和失败位置，其中Pin,Pac,Pe,Pab,Pca,Pcp,Pfa称为任务的位置库所。其它的事务属性能够用类似的方法进行描述，具体的模型如图4(b)－图4(d)。PIinPcaPIePIinPcaPePItrtcaPePItrtcaPePacPacPinPintintetintetcptabtabtrttfatrttfaPcpPabPabPfaPfa(c)r(d)r,cp图4 服务的事务属性模型通过对图4的分析可知，事务属性不同的服务，运行过程可能到达的位置集和操作也不同。图 4中库所和变迁的实际映射如表 1所示：表1事务属性模型中变迁和库所的对比P/T位置/操作P/T位置/操作P/T位置/操作Pin初始位置Pab中断位置Pfa失败位置Pe终止位置Pca取消位置Pcp补偿位置Pac运行位置PIe终止输出PIc失败输出PItr事务输入PIin运行输入tin运行操作tca取消操作trt重试操作tfa失败操作tcp补偿操作tab中断操作te终止操作从表1可知，采纳Petri网能够精确地描述服务的事务属性。将初始、运行、终止和失败位置称为服务的运行位置，而中断、取消和补偿位置称为服务的事务位置。3.2服务组合的失效处理模型由于每个服务具有自身的事务属性。当某个服务运行失败时，如何和谐其它服务，保证整个系统的可靠运行，成为服务组合中必须解决的一个咨询题。本文引入失效处理模块（FCM）来处理该咨询题。假设同一时刻系统中最多有一个服务失败，其服务失败处理时刻能够忽略。

由于实际情形中有些任务是不可取消的也不能够补偿的（ NCC），这类任务所对应的服务和谐操作比较专门。如其它服务失败的时刻该服务处于运行位置，则和谐其到达终止位置。其对应的服务模型如图 5所示，其中tce是服务的和谐操作。IPIinPIeIPIinPIeePPacPPactPintinPinttinttababtfa结果。PabtrtPfaPabPfa(a)NCCPc(b)r,NCC图5不可取消任务对应的服务模型不妨设服务Si是完成Ci的功能，则服务组合的失效处理机制有：1）设任务Ci是Cj的前向任务，若服务Si失败，则中断服务Sj。2）设任务Ci是Cj的前向任务，若服务Sj失败，分两种情形和谐Si：①服务Si是可补偿的，则对Si进行补偿；②服务 Si是不可补偿的，则不做任何操作，服务 Sj停留在终止位置。3）设任务Ci是Cj并行运行，若服务Si失败，分四种情形和谐Sj：①服务Sj处在运行位置且任务Cj可取消的，则取消 Sj的运行；②服务Sj处在运行位置且任务Cj不可取消的，则和谐Sj的运行使其到达终止位置；③服务 Sj处在终止位置且Sj是可补偿的，则对 Sj运行补偿；④服务Sj处在终止位置且Sj是不可补偿的，则不做任何操作，服务Sj停留在终止位置。失效处理模块的功能为：当系统中某个服务运行失败时，基于上述处理机制，依据其它服务的事务属性和谐系统终止。下面对FCM进行建模（同理在变迁和库所之前标注对应的服务）。引进库所Pc和变迁tc分别表示系统和谐的初始位置和和谐操作，使得：1）Pc={S1tfa,S2tfa,,Sktfa},Pc=tc2）tc=Pc,tc={S1PItr,S2 PItr, ,Sn PItr}条件（1）表明服务组合中若有服务失败则调用FCM模型；条件（2）描述了FCM模块给每个服务都输入事务处理参数。若对工作流模型中的每个任务都分配一个服务，则构成了具体的服务组合，不妨设S为分配好的服务集。基于此，下面给出服务组合的失效处理模型形式化定义：定义3：工作流模型，S是所分配的服务集，则按照下列步骤构造的四元组S=(Ps,Ts,Fs;Ms0)称为

服务组合的失效处理模型（ ServiceComposition’sFailureProcessing,SCFP）：1）按照服务的事务属性建模构造S集合中每个服务的Petri网模型；2）按照中的数据流程合成服务的Petri网模型；3）依据上述FCM模型的建模方式添加相应的变迁和库所。4）保持中的初始状态不变。从定义3能够看出SCFP模型是在工作流模型的基础上对带事务特性的服务组合进行建模。3.3模型性质本文中系统状态由标识 M表示，如M(Ci Pe)=1表示在状态M下，任务Ci差不多运行终止。将任务Ci在状态Ma中不为零的库所记作Mai。下面分析SCFP模型的一些要紧性质。性质1：SCFP模型 S中，任一可达状态M下的每个服务都只能处于一个位置。证明：从建模过程 S可知，服务Si的位置库所满足库所不变量：M(Si Pin)+M(Si Pac)+M(Si Pca)+M(Si Pfa)+M(Si Pe)+M(SiPab)+M(Si

Pcp)=1。而服务组合一

性质

2：SCFP模型

S保证了旦运行，会对每个服务进行初始化 服务组合的失效处理机制。（变迁Tstart），即输入令牌到库所S证明：（1）证明S保证了服务。按照Petri网的运行机制可组合的失效处理机制（1）iPin得：服务只能处于初始、运行、取设任务Ci是Cj的前向任务，在消、失败、终止、中断和补偿位置状态M下服务Si失败中的一个。证毕∴M(Pc)=1同一个SCFP模型由于任务对∵Pc=tc,tc=Pc,tc={S1应的服务失败时刻不同，系统的终PItr,S2PItr,,SnPItr}止位置也会不同。按照任务间的关∴M[tc>M’,其中M’(SjPI系运算出工作流模型的所有可能tr)=1终止状态，记为TS()。其中TS()∵任务Ci是Cj的前向任务={ME}TSF()：∴M’(SjPin)=1（1）正常终止状态ME：i∴M’[Sjtab>[1,n]ME(Ci，表示系统∵M’[Sjtab>M’’,其中M’’Pe)=1ME中所有任务都正常终止的状态。关(SjPab)=1于一个工作流模型，其正常终止状∴系统中断了服务Sj态唯独。即S保证了服务组合的失效（2）失败终止状态集合TSF处理机制（1）。()：MFTSF()有i[1,n]同理按照任务间的关系，能够，表示分别证明S保证了服务组合的失MF(CiPfa)=1MF(CiPfa)系统中任务Ci失败，通过系统和谐效处理机制（2）和（3）。到达的终止状态，也称MF(CiPfa)综上所述，SCFP模型S保证是Ci的失败终止状态。记集合TSF了服务组合的失效处理机制。(,Ci)是任务Ci在TSF()中的所证毕有失败终止状态集合。性质2指出本文建立的模型能在服务组合中，失效处理机制 够确保服务组合的失效处理机制正是系统的核心。因此有必要分析建 确运行，从而讲明了失效处理机制立的模型是否保证该处理机制。 建模方式的正确性。性质3：SCFP模型S中，任，满足下列两个条件Cj(ij)Ma,Mb一可达状态M下若存在某个服务是之一：处于事务位置，则存在唯独的服务（1）Maj=Mbj处于失败位置。（2）Ma(CjPe)+Ma(CjPcp)证明：不妨设在终止状态M下，=Mb(CjPca)+Mb(CjPab)=1服务Si处于事务位置，即中断、取称状态Ma和Mb是相容的，记消或补偿。做MaMb。否则称状态Ma和MbM(SiPca)+M(SiPab)+M是不相容的，记做MaMb。记TS(SiPcp)=1()中与状态Ma相容的状态集合为∵●(SiPca)=Sitca●(SiCS(Ma)。Pab)=Sitab●(SiPcp)=Sit从定义4可知，两个终止状态cp不相容必须同时满足下列两个条且●(Sitca)●(Sitab)●件：（1）属于同一个任务的失败终(Sitcp)=SiPItr止状态；（2）存在某个任务在这两∵●(SiPItr)=tc,tc=Pc,个状态下分别处于终止和补偿位Pc={S1tfa,S2tfa,,Sntf置。否则Ma和Mb是相容的，明显a}状态和自己本身是相容的。∴SjS,M(SjPfa)=1定义5：终止状态集合S，若任∵服务组合中同一时刻最多有意的失败终止状态Ma，MbS(a一个服务失败b)满足下列条件之一，则称S是一致∴!SjS,M(SjPfa)=1的：即存在唯独的服务Sj处于失败（1）Ci,Cj,Ma(CiPfa)=位置证毕Mb(CjPfa)=1CiCj上述要紧分析了SCFP模型的（2）i,Ma(CiPfa)=Mb(Ci差不多性质和特点，下面基于上述Pfa)=1MaMb性质深入分析SCFP模型的一致性。终止状态集合S是一致的指该定义4：任意两个终止状态 Ma, 集合中任意两个状态要么不属于同Mb TSF( ,Ci)，若关于所有任务 一个任务的失败终止状态集，要么相容。下面通过判定模型终止状态∴SjS(ij),使得Ma(CjP集的一致性来分析模型的正确性。e)=Mb(CjPcp)=1定义6：集合STS(S)称为服依据任务Cj和Ci的关系，下面务组合S的可达终止状态集合，若分三种情形来分析：关于任意STSiSTS(S)有：第一设Cj是Ci的前向任务（1）存在变迁序列，使得M按照性质1可知，在Si失败时0[>STSiSj处于终止位置（2）tT,STSi[t<∴Ma(CjPe)=1由于Petri网的特性，服务组合∵Ma(CiPfa)=1的可达状态能够表示各个可用服务∴Ma(Pc)=1的运行终止状态。如M1={S1fa,∴Sj是不可补偿的S2cp,,Snca}表示服务组∵Mb(CjPcp)=1合某次运行终止时：S1处于失败位∴Sj是可补偿的，与上面推出置，S2处于补偿位置，Sn处于取消来Sj是不可补偿的矛盾。位置。而任务与服务是一一对应的，同理能够证明当Cj和Ci是并行因此能够把状态M1中的服务用所关系时（服务Sj分可取消的和不可对应的任务来表示。下面从理论上取消的）也存在矛盾。分析SCFP模型所到达的终止状态综上所述，S的终止状态集合集合是一致的。具有一致性。证毕定理1：SCFP模型S的终止基于服务组合的失效处理机状态集合具有一致性。制，结合任务间的关系能够证明服证明：反证法，假设SCFP模型务组合的终止状态集合满足一致性S的终止状态集合不具有一致性。定义。从而讲明SCFP模型的正确不妨设Ma,MbSTS(S),M性。aMb4可靠服务组合的和谐技术∴SiS:Ma(CiPfa)=Mb(C本节给出可靠服务组合的定iPfa)=1义，分析可靠性的内在条件，提出∵Ma和Mb不相容服务组合的和谐策略并证明其有效性，最后给出和谐策略的实施方法。4.1服务组合的可靠性转化为对可用服务的终止状态要设可用服务集合WS={WS1,W求。S2,WSn}，其中WSi为任务C可靠服务组合不仅能够完成系i的可用服务集合，ij有WSi统的功能要求，而且某个服务失败WSj=。服务组合的构造过程确实时会到达服务消费者可同意的状态是WSi中服务与任务Ci的匹配过[9]。下面结合服务组合的工作流模程。关于具体的服务组合流程，服型，给出服务组合可靠性的定义。务消费者的需求能够归结为可同意定义9：设服务组合的工作流模状态集合。下面给出该集合在SCFP型=(C;P,T,F,M0)，s是基于的模型中的映射。一个服务组合，且服务消费者的可定义7：集合ATS()TS()同意状态集为ATS()。若s满足表示服务消费者对工作流模型的如下条件，则称服务组合s是可靠可同意状态集。可同意状态Mi={Mi的：(C1),Mi(C2),,Mi(Cn)},Mi(C（1）MESTS(S)j){ab,ca,e,fa,cp}。记ATS(,（2）STS(S)ATS();Ci)表示可同意状态集中任务Ci的其中，条件（1）要求服务组合失败终止状态。能够完成服务消费者的功能需求，明显MEATS()，ATS(,Ci)而条件（2）表示S的所有可达终TSF(,Ci)。同样只有一致的可同止状态差不多上服务消费者可同意意状态集才是有效的，下面给出可的，即在任何情形下，服务组合都同意状态集有效性的形式化定义：能达到服务消费者的可同意状态。定义8：可同意状态集ATS()按照ME的定义并结合Petri网的运是有效的，若MATS()有：行机制可知，按照第3节方法所构CiC,M(CiPfa)=1存在唯独的造的s模型必定能够到达正常终状态M’ATS(),M’是Ci的和止状态ME。因此在后面分析服务组谐状态且CCS(M’,Ci)=ATS(,Ci)。合可靠性时，仅需要考虑条件（2）。同理，能够将服务消费者的可4.2服务组合的和谐策略同意状态中对任务的终止状态要求本节引入和谐集的概念，并分析服务组合可靠性与和谐集的关系；其次结合服务消费者的可同意（3）CjC:Ci||Cj且Cj不能状态集，提出和谐策略。取消，则MiCCS(M,Ci)有Mi(Cj定义10：同时满足下列两个条Pca)+Mi(CjPcp)=0件的终止状态M称为任务Ci的和谐从定义11可知CCS(M,Ci)=CS状态：s(M)-kj=1FS(Ci,Cj)，其中k为与C（1）M(CiPfa)=1i并行且不可取消的任务个数。（2）CjC:Ci||CjM(CjP关于分配了可重复服务的任e)+M(CjPcp)=1务，其CCS(M,Ci)=。由于同一个在任务Ci的和谐状态下，其并工作流模型中任务的和谐状态不行任务都处于终止或补偿位置。和唯独，因此和谐集也不唯独。系统谐状态是基于任务的失败状态定义在任务Ci失败的情形下，依据目前的，因此同一个任务的和谐状态不各个任务的位置，和谐系统到达和唯独。设在工作流模型中任务Ci和谐集中的一个状态。下面分析和谐Cj是并行关系，若Cj是不可取消的，集与SCFP模型状态一致性的关系。则称状态集合FS(Ci,Cj)为Cj针对C引理1：在服务组合模型S中，i的错误终止状态。其中MFS(C若任意服务Si失败，则系统存在唯i,Cj)，使得：M(CiPfa)=M(CjPc独与之对应的和谐集。a)+M(CjPcp)=1。FS(Ci,Cj)指系统证明：反证法假设服务组合模中Ci失败而Cj处于取消或补偿的位型S，在服务Si失败的情形下，系置。由于Cj是不可取消的，因此在统存在多个和谐集。任何情形下Cj都可不能到达取消或不妨设服务Si失败时，服务组补偿的位置。合S能够依据和谐集CCS(Ma,Ci)定义11：同时满足下列三个条和CCS(Mb,Ci)对其它服务进行和件的终止状态集合CCS(M,Ci)称为谐。系统在Ci失败情形下的和谐集：∴MaSTS(S)MbSTS（1）M是Ci的和谐状态(S)（2）MiCCS(M,Ci)有Mi∵Ma和Mb差不多上任务CiM的和谐状态∴CjC:Ci||Cj有Ma(Sj

Pe)+Ma(Sj

Pcp)=1，

∴Ma=MFMb(Sj

Pe)+Mb(Sj

Pcp)=1

∴Ma

ATS(

)∵Ma

Mb

(2) Si

S,Ma(Ci

Pfa)

1，∴CjC:Ci||Cj且Ma(SjP即Ci在服务组合S中分配了不可e)=Mb(Sj，即MaMb重复的服务SiPcp)=1∵Ma(SiPfa)=Mb(SiPfa)=1∵服务组合具有一致性∴STS(S)不一致与定理1矛∴唯独的Ci的和谐状态M盾a’，使得MaCCS(Ma’,Ci)∴在服务组合模型S中，若任∵SiS,Ma(CiPfa)1意服务Si失败，则系统存在唯独与∴服务Si是不可重复的之对应的和谐集。∵关于S中不可重复的服务S证毕i，存在Ci的和谐状态MSTS(S)定理2：在服务组合S中，S∵S中关于不可重复的服务STS(S)ATS()当且仅当任意Si只存在一个和谐集中不可重复的服务Si，存在Ci的和∴Ma’=M谐状态MSTS(S)且CCS(M,Ci)=∴MaCCS(M,Ci)ATS(,Ci)。∵CCS(M,Ci)=ATS(,Ci)证明：∴MaATS()∵不妨设任务Ci在S由不可综上，MaSTS(S)Ma重复的服务Si来完成ATS()∴MSTS(S)，M是Ci的∴在服务组合S中，STS(S)和谐状态ATS()当且仅当任意S中不可由引理1可知：CCS(M,Ci)S重复的服务Si，存在Ci的和谐状态TS(S)MSTS(S)且CCS(M,Ci)=ATS∵STS(S)ATS()(,Ci)。证毕CCS(M,Ci)ATS()关于 Ma STS( S)Si S,Ma(Ci Pfa) 1即 Ci C,Ma(Ci Pfa)

1

从定理2可知，服务组合可靠性的咨询题能够通过分析和谐集与可同意状态集的关系来实现。由于可靠服务组合S的可能（1）若MATS()，M(Ci终止状态集合STS(S)ATS()。，且SiWSi,TP(Si)={cPcp)=1因此，按照S的运行机制可知，Ap}，则将Si分配给任务Ci，否则出TS()对S中调用的服务事务属错（可靠服务组合不存在）；性存在如下关系：（2）若MATS(),M(Ci（1）MATS(),使得M(Ci，且SiWSi,TP(Si)=Pcp)=0Pfa)=1，则rTP(Si)；{p}，则将Si分配给任务Ci，否则（2）MATS(),使得M(Ci出错；，则r；（3）若MATS(),M(CiPfa)=0TP(Si)（3）MATS(),使得M(Ci，且SiWSi,TP(Si)={r}，Pfa)=0，则cpTP(Si)；则将Si分配给任务Ci，否则出错；Pcp)=1（4）MATS(),使得M(Ci（4）若MATS(),M(CiPcp)=0，则cpTP(Si)。Pab)=1，任选WSi中的一个可用定义12：按照定理2和上述关服务Si，将Si分配给任务Ci。系，构造可靠服务组合的和谐策略其中，策略1的优先级大于为：策略2，即优先使用策略1，只有策策略1：调整可同意状态集AT略1不能使用时才调用策略2。S()利用和谐策略构造可靠服务组（1）若MATS(),M(CiP合的差不多思想是：针对特定的服cp)=1，且SiWSi,TP(Si)={cp,r}，务消费者的需求（可同意状态集），则将服务Si分配给任务Ci，ATS()按照和谐策略分配服务给任务。=ATS()-TSF(,Ci)；4.3和谐策略的有效性（2）若MATS(),M(CiP和谐策略作用是在服务组合流cp)=0，且SiWSi,TP(Si)={r}，则程中如何按照服务消费者的需求来将Si分配给任务Ci，ATS()=ATS动态地分配服务。因此有必要分析()-TSF(,Ci)。和谐策略的有效性，即按照和谐策策略2：对未分配服务的任务分略构造的服务组合是可靠的。配服务定理3：针对有效的ATS( )， ∴给任务Cj分配的Sj具有不可按照和谐策略构造出来的服务组合 补偿的事务属性S是可靠的。∵Ma’(SjPcp)=1证明：不妨设任务Ci在服务组∴Sj具有可补偿的事务属性，合S中分配了不可重复的服务Si与上述结果矛盾∴MaSTS(S),Ma(CiPfa)∴Ma’=Mb’=1∴S中任意不可重复的服务S∵服务组合S关于Si失败的i，存在Ci的和谐状态MSTS(S)和谐集唯独且CCS(M,Ci)=ATS(,Ci)∴唯独的Ci的和谐状态M∴按照定理2有STS(S)ATa’，使得MaCCS(Ma’,Ci)S()∵任务Ci在服务组合S中分∴服务组合S是可靠的。配了不可重复的服务Si综上所述，针对有效的ATSMbATS(),Mb(CiPc()，按照和谐规策略构造出来的服p)=1（由步骤（）推出）务组合S是可靠的。21∵可同意状态集ATS()有效证毕的因此，针对特定的用户需求，∴唯独的Ci的和谐状态M采纳和谐策略生成整个系统的服务b’，使得CCS(Mb’,Ci)=ATS(,Ci)组合具有可靠性。∴定理证明转化为证Ma’=Mb’4.4和谐策略的实施反证法，假设Ma’Mb’按照上述分析，采纳和谐策略∵Ma’,Mb’为任务Ci的两个构造可靠服务组合的实施步骤如不同的和谐状态下：∴CjC:Ci||Cj,有Ma’(Sj（1）构造工作流模型的和谐Pcp)=Mb’(SjPe)=1集。该集合不随服务消费者改变而∵Mb’(SiPe)=1改变。关于同一个流程，和谐集是∴MATS()，M(CiPcp)可重复使用的。=0（2）分析服务消费者可同意状态集是否有效。如果无效，即服务消费者的可同意状态集本身是矛盾的，则提示服务消费者修改可同意状态集。3）结合服务消费者的可同意状态集，按照和谐策略构造可靠服务组合，实施算法如表2所示。该算法第一按照策略1对任务尽可能分配满足条件的可重复服务，并调整可同意状态集；其次基于新的可同意状态集，按照和谐策略2连续分配服务，直到所有任务都有相应的可用服务能够满足；若某个任务不存在满足要求的服务则报错。表2可靠服务组合的构造算法1:Update_ATS(ATS,C,WS) //调整可同意状态2:If M ATS()andM(Ci?Pcp)=1 //可补偿的3: If Si WSiandTP(Si)={cp,r}SiCi;//表示分配操作ATS()=ATS()-TS(,Ci);C=C-Ci;S=SSi;//C和S分别表示任务集和服务集Update_ATS(ATS,C,WS)//进行下一轮的调整8:ElseIf M ATS()andM(Ci?Pcp)=0)//不可补偿的9: If Si WSiandTP(Si)={r}SiCi;ATS()=ATS()-TS(,Ci);C=C-Ci;S=S-Si;Update_ATS(ATS,C,WS)12:ElsereturnATS;13:Match_Service(ATS,C,WS)//对剩下的任务分配服务14:IfMATS()andM(Ci?Pcp)=115:IfSiWSiandTP(Si)={cp}16:SiCi;C=C-Ci;Match_Service(ATS,C,WS);ElsereturnFalse;19:ElseifMATS()andM(Ci?Pcp)=020:IfSiWSiandTP(Si)={p}21:SiCi;C=C-Ci;Match_Service(ATS,C,WS);

ElsereturnFalse;24:Elseif M ATS()andM(Ci?Pfa)=025: If Si WSiandTP(Si)={r}SiCi;C=C-Ci;Match_Service(ATS,C,WS);ElsereturnFalse;29:Elseif M ATS()andM(Ci?Pab)=1SiWSi;SiCi;C=C-Ci;Match_Service(ATS,C,WS);实例研究本节通过简化的旅行服务来演示和谐策略的实施过程。对旅行服务来讲，它包括飞机票或火车订购、汽车租赁和行程规划等有关业务。具体服务组合流程为：当客户预备旅行时，第一查阅信息并选择目的地（C0），订购火车票(C1)负责处理客户的火车票，订购飞机票(C2)按照服务消费者的要求订购合适的航班，行程规划(C3)负责目的地具体的行程安排，汽车租赁(C4)安排客户到达火车站或者飞机场，宾馆预订(C5)是客户到达目的地后对所住地点的安排，最后通过当地旅行(C6)负责客户的当地旅行有关事宜。利用第2节介绍的算子，该组合流程可表示为表达式：C0>(C1+C2)>C3>(C4||C5)>C6，假设任务C5是不可取消的。按照工作流模型的建模步骤，能够构造出整个系统的所对应工作流模型 =(C;P,T,F,M0)，如图6所PStartTStartC0.PinC1.PinC3.PinC4.PinC6.PinC2.PinC5.PinC0.tinC1.tinC2.tinC3.tinC4.tinC5.tinC6.tinC0.PacC.PC2.PacC3.PacC4.PacC5.PacC.P6ac示。图C0.中te的C1.t库e所C和2.te变C3迁.te刻画C4.t了e任C5.务te C6.teC.PC.PC.PeC.PeC4.PeC5.PeC6.Pe的相应位置及任务之间的关系。P012P123P35P34P56P46图6旅行服务的工作流模型假设目前的可用服务有22个，具体的事务属性如表 3所示：表3 服务的事务属性任务WSTP任务WSTPS01pS11cpC0S02r,cpC1S12PS03cpS13r,cpS21pS31r,cpC2S22pC3S32PS23pS33cpS41rS51cpC4S42cpC5S52pS43pS53r,cpS54rS61cpC6S62pS63cp下面给出服务消费者的当前可同意状态集，如表4所示。其中M8-={C0cp,C1cp/C2e,C3cp,C4e,C5e,C6fa}表示服务S6失败时，服务消费者可同意服务 S0，S1，S3得到补偿，而其余服务不能补偿。表4可同意状态集ATSMCC0C1/C2C3C4C5C6M1eeeeeeM2faabababababM3cpfaababababM4cpcpfaabababM5cpcpcpfaeabM6cpcpcpefaabM7cpcpcpcafaab

M8 cp cp/e cp e e fa第一运算该工作流模型的和谐集，按照可同意状态集的有效性定义可知ATS是有效的。下面基于ATS，按照和谐策略构造服务组合，具体步骤如下：步骤1：应用和谐策略1，分配可重复服务所对应的任务，并按照策略1中可同意状态集的运算公式调整ATS。第一分配服务 S02给任务C0，相应地ATS调整为{M1,M3,M4,M5,M6,M7,M8,M10,M11,M12,M13,M14,M15}。同理对任务C1,C3,C4,C5分别分配服务S13,S31,S41,S54，最后ATS调整为{M1, M8}步骤2：应用和谐策略2，基于可同意状态集{M1, M8}，对剩下的任务C2和C6分配服务。最后分配结果为S2=S23,S6=S62。至此，工作流模型中的每个任务都分配一个服务。按照服务的事务属性和服务组合的失效处理机制，能够得到旅行服务的 SCFP模型S=(Ps,Ts,Fs;Ms0)，如图7所示。该模型的可达终止状态集合STS(S)={M1,M3,M8}ATS，因此服务组合S是可靠的。S0.PcaS1.PcaS2.PeS2.tfaS3.Pca4eS5.teS6.PeS6.PfaS2.PfaS4.PeS0.PeS1.PeS3.tcpS4.PcaS0.tcpS1.tcpS3.PcpP56S5.PePS.PP123P35P34P46PCtC图7旅行服务的SCFP模型由于篇幅的限制，本文仅仅对imthanmaphon对这些协议进行总结简化的旅行服务进行模拟。然而它[10]，但这些协议是要紧是为Web足以讲明服务组合的建模方法和和服务技术制定基于XML的标准，并谐策略的正确性。实例模拟过程可没有考虑到服务消费者的实际需知，应用本文所提出方法能够达到要，且不容易按照服务消费者的需如下成效：（1）能够清晰地描述任要来动态调整。而使用形式化方法务及任务之间的关系。（2）正确刻对服务组合事务进行分析也开始有画了服务的事务属性，所构造的模了一些研究成果和工作。在这些工型能够确保服务组合的失效处理机作中，有基于进程代数的[11-13]，制正确运行。如服务S6运行失败，也有基于演算[14]的。Butler提出按照Petri网的运行机制S模型会使用CCS与CSP结合的方法来描述到达终止状态M8或M15。（3）和Web事务[11]，它的优点是对结构化谐策略的有效性，按照和谐策略所活动的复原机制进行描述，然而它构造的服务组合是可靠的。如图7所采纳的语法比较复杂，不利于对中的STS(S)={M1,M3,M8}，满有关的特性进行推导。Butler等对该足可靠服务组合的定义。因此，S方法进行改进[12]，并采纳进程代数是可靠的。（4）动态调整可同意状来描述相应的语义，但它没有考虑态集，以减少运算量。若每次分配事务运行的不同状态，对模型的正可重复服务后可同意状态集没有进确性验证还没有具体论述。Hashemi行调整，则每次分配服务都要搜索an采纳进程代数的方法来描述无状整个可同意状态集。因此，关于大态的服务[13]，进而描述服务组合的型服务组合，该方法能够在较快的语义，通过使用图的框架能够表示时刻内构造可靠服务组合。服务组合的过程，然而它没有考虑6有关工作服务的状态，而实际中，服务的状现在Web服务事务处理技术正态却是服务消费者比较关怀的结处于持续进展之中，许多公司差不果。多推出处理Web服务事务的协议。L采纳演算要紧是对服务协议Petri网的语义来描述Web服务，进进行研究，给出扩展演算的形式而描述了服务之间的关系，其优点化语义。廖军等利用Pi-演算建立W是考虑了服务的QoS属性，但它没eb服务组合模型的规则[14]，并使用有考虑服务的动态性且没有对其有形式化工具分析所建立组合模型的关的性质进行验证。文献[19]使用P正确性，然而它没有分析服务消费etri网的语义来描述Web服务的原者可同意状态的多样性，且演算子事务和聚合事务，进而使用Petri对设计人员的数学功底要求较高，网的可达图对有关算法进行验证，不利于方法的扩展。最近也显现了它的优点是分析了事务的一致性，一些采纳事务模式的方法来分析服然而它没有描述服务的补偿和取消务的事务属性[15,16]。Bhiri提出了等重要特性。事务模式的方法描述可靠服务组合7终止语[15]，但它没有对模型进行验证，而本文针对带事务属性的服务组且不易对所建立的模型进行分析。M合，提出利用Petri网来构造服务组ontagut提出一种事务需求的服务组合的工作流模型和SCFP模型，给出合方法，它考虑了服务的事务属性。可靠服务组合的和谐策略及事实上然而该方法没考虑服务的失败处施。与现有方法相比，本文工作具理，且采纳状态图描述服务的特性，有如下优点：（1）使用形式化方法造成模型性质分析的复杂性，使得（Petri网）来描述，Petri网有关的方法难以推广。理论能够准确地刻画服务运行的不与本文相近的工作还有文献[17同状态，且能够清晰地表达服务组-19]，它们均采纳Petri网对服务组合的逻辑及服务之间的关系，利用合进行形式化分析。文献[17]提出使有关工具可对系统进行模拟，使得用Petri网对服务的行为进行分析，该方法易于推广；（2）充分考虑了以便验证组合过程是否能得到预期服务的事务属性和服务组合的失效的结果，然而，它在验证的过程中处理机制，保证服务失败时可得到没有考虑服务的事务特性，导致服相应的处理；（3）提出了和谐策略，务失败时，专门难对其语义比较准该策略可减少可靠服务组合构造的确的形式化分析。文献[18]使用着色复杂度，并从理论上证明了该策略的有效性。同时给出了和谐策略的具体实施，为构建大型复杂的服务组合系统奠定基础。本文在服务的事务特性建模方面取得了进展，但没有考虑服务组合流程中的资源调度咨询题，对 SCFP模型的推理机制和工具也没有涉及。另外，本文对可用服务的选择没有考虑服务的 QoS。我们将在这些方面进一步探究。参 考 文 献AmbrogioAD,BocciarelliP.Amodel-drivenapproachtodescribeandpredicttheperformanceofcompositeservices//Proceedingsofthe6thInternationalWorkshoponSoftwareandPerformance.NewYork:ACM,2007:78-89PapazoglouMP,HeuvelWJ.Serviceorientedarchitectures:approaches,technologiesandresearcissues.InternationalJournalonVeryLargeDataBases,2007,16(3):389-415YuanChong-Yi.PetriNetsTheoryandApplication.Beijing:PublishingHouseofElectronicIndustry,2005.1-6(inChinese)

(袁崇义.Petri网原理与应用.北京:电子工业出版社,2005.)HinzS,SchmidtK,StahlC.TransformingBPELtoPetrinets//ProceedingsoftheThirdInternationalConferenceonBusinessProcessManagement.Heidelberg:Springer-Verlag,2005:220-235GiraultC,ValkR.PetriNetsforSystemEngineering:AGuidetoModeling,Verification,andApplications.Berlin:Springer-Verlag,2003CanforaG,PentaMD,EspositoR,VillaniML.QoS-awarereplanningofcompositeWebservices//ProceedingsoftheIEEEInternationalConferenceonWebServices.Washington,USA:IEEEComputerSociety,2005:121-129BhiriS,PerrinO,GodartC.EnsuringrequiredfailureatomicityofcompositeWebservices//Proceedingsofthe14thInternationalConferenceonWorldWideWeb.NewYork:ACMPress,2005:138-147SchuldtH,AlonsoG,SchekH.Concurrencycontrolandrecoveryintransactionalprocessmanagement//ProceedingsoftheEighteenthACMSIGMOD-SIGACT-SIGARTSymposiumonPrinciplesofDatabaseSystems.NewYork:ACMPress,1999:316-326LimthanmaphonB,ZhangYan-Chun.Webservicecompositiontransactionmanagement//Proceedingsothe15thAustralasianDatabaseConference.Darlinghurst,Australia:AustralianComputerSociety,2004:171-179ButlerR,FerreiraC.AnoperationalsemanticsforStAC,alanguageformodellinglong-runningbusinesstransactions//Proceedingsofthe6thInternationalConferenceonCoordinationModelsandLanguages,LNCS2949.Heidelberg:Springer-Verlag,2004:87-104BruniR,MelgrattiH,MontanariU.Theoreticalfoundationsforcompensationsinflowcompositionlanguages//Proceedingsofthe32ndACMSIGPLAN-SIGACTSymposiumonPrinciplesofProgrammingLanguages.NewYork:ACM,2005:209-220

LiaoJun,TanHao,LiuJin-De.DescribingandverifyingWebserviceusingPi-calculus.ChineseJournalofComputer,2005,28(4):635-643(inchinese)(廖军,谭浩,刘锦德.基于Pi-演算的Web服务组合的描述和验证.运算机学报,2005,28(4):635-643)BhiriS,GodartC,PerrinO.TransactionalpatternsforreliableWebservicescompositions//Proceedingsofthe6thInternationalConferenceonWebEngineering.NewYork:ACMPress,2006:137-144MontagutF,MolvaR.AugmentingWebServicesCompositionwithTransactionalRequirements//ProceedingsoftheIEEEInternationalConferenceonWebServices.Washington,USA:IEEEComputerSociety,2006:91-98AalstWP,DumasM,OuyangC,RozinatA,VerbeekE.Conformancecheckingofservicebehavior.ACMTransactionsonInternetTechnology,2008,8(3):1-30LiWen-Jun,LiangXiao-Jun,SongHua-Mei,ZhouXiao-Cong.QoS-drivenservicecompositionmodelingwithextendedhierarchicalCPN//ProceedingsoftheFirstJointIEEE/IFIPSymposiumonTheoreticalAspectsofSoftwareEngineering.Washington,USA:IEEEComputerSociety,2007:483-492TangFei-Long,LiMing-Lu,HuangZhe-Xue,WangZhuo-Li.AtrFANGui-Sheng,bornin1980,Ph.D.candidate.Hisresearchinterestsincludeserviceorientedcomputing,distributedcomputingandformalmethods.LIUDong-Mei,bornin1970,Ph.D.candidate.Herresearchinterestsincludeserviceorientedcomputing,distributedcomputingandformalmethods.

ansactionserviceforservicegridanditscorrectnessanalysisbasedonPetrinet.ChineseJournalofComputers,2005,28(4):667-676(inChinese)(唐飞龙,李明禄,黄哲学,王卓立.服务网格中的事务服务及基于Petri网的正确性分析.运算机学报,2005,28(4):667-67CHENLi-Qiong,bornin1982,Ph.D.candidate.Herresearchinterestsincludedistributedcomputing,embeddedsystemsandformalmethods.YUHui-Qun,bornin1967,professor,Ph.D.supervisor,IEEEseniormember,ACMmember,ChinComputerFederationseniormember.Hisresearchinterestsincludesoftwareengineering,informationsecurityandformalmethods.ACoordinationStrategyforReliableServiceCompositionandItsAnalysisFANGui-Sheng,LiuDong-Mei,ChenLi-Qiong,YUHui-Qun(DepartmentofComputerScienceandEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)Abstract:ServicecompositionisaneffectivewaytobuildcomplexWebsoftwaresystems.However,thediversityofservicetransactionstatesmakesithardtoguaranteereliability