可靠服務(wù)組合的協(xié)調(diào)策略與分析

可靠服務(wù)組合的協(xié)調(diào)策略與分析范貴生 劉冬梅 陳麗瓊虞慧群(華東理工大學(xué)運(yùn)算機(jī)科學(xué)與工程系 ,上海 200237)摘 要：服務(wù)組合是構(gòu)建復(fù)雜 Web軟件的有效方法，但服務(wù)事務(wù)狀態(tài)的多樣性使得服務(wù)組合的可靠性難以保證。為此，提出一種構(gòu)造可靠服務(wù)組合的和諧方法。該方法采納 Petri網(wǎng)對(duì)工作流建模，以清晰地表達(dá)任務(wù)及任務(wù)之間的邏輯關(guān)系。在此基礎(chǔ)上，按照服務(wù)的事務(wù)屬性及服務(wù)組合的失效處理機(jī)制建立服務(wù)組合的失效處理模型，并提出一種構(gòu)造可靠服務(wù)組合的和諧策略及實(shí)施方法。利用 Petri網(wǎng)有關(guān)理論證明該策略的有效性。旅行服務(wù)實(shí)例演示了和諧技術(shù)的應(yīng)用方法及其可行性。關(guān)鍵詞 Petri網(wǎng)；Web服務(wù)；服務(wù)組合；事務(wù)；可靠性引言隨著Internet技術(shù)應(yīng)用的迅速進(jìn)展，基于Web服務(wù)的分布式運(yùn)算模式差不多成為軟件進(jìn)展的趨勢(shì)。 Web服務(wù)能夠統(tǒng)一地封裝信息、行為以及業(yè)務(wù)流程，而無(wú)需考慮應(yīng)用所在的環(huán)境。通過(guò)Web服務(wù)組合來(lái)動(dòng)態(tài)生成新的應(yīng)用系統(tǒng)，以滿(mǎn)足實(shí)際的需要，已成為Web服務(wù)技術(shù)持續(xù)向前進(jìn)展的技術(shù)動(dòng)力[1]。然而，Web服務(wù)事務(wù)狀態(tài)的多樣性使得服務(wù)組合變得更為可靠和有效之前，還有一些咨詢(xún)題需要處理。其中關(guān)鍵咨詢(xún)題確實(shí)是如何構(gòu)建可靠服務(wù)組合，即如何按照服務(wù)的事務(wù)屬性來(lái)分配可用服務(wù)以滿(mǎn)足服務(wù)消費(fèi)者的需求。盡管傳統(tǒng)的事務(wù)技術(shù)在數(shù)據(jù)

庫(kù)系統(tǒng)和分布式系統(tǒng)中得到了廣泛的應(yīng)用，但由于Web服務(wù)自身的松耦合性、運(yùn)行時(shí)刻長(zhǎng)、長(zhǎng)事務(wù)等特點(diǎn)，使其在系統(tǒng)的可靠性和一致性方面面臨新的挑戰(zhàn)，如何對(duì)服務(wù)的事務(wù)屬性進(jìn)行形式化分析成為業(yè)界廣泛討論并關(guān)注的咨詢(xún)題[2]。Petri網(wǎng)作為一種直觀(guān)的圖形建模工具和一種具有豐富數(shù)學(xué)基礎(chǔ)的形式化模型，能夠廣泛應(yīng)用于描述和研究并發(fā)、異步和分布式特點(diǎn)的系統(tǒng)，并提供了一種可操作語(yǔ)義及定性和定量分析[3]。最近的研究表明，Petri網(wǎng)適合用來(lái)描述服務(wù)組合的特性[4,17]。而可靠服務(wù)組合的構(gòu)建不僅能夠滿(mǎn)足服務(wù)消費(fèi)者的功能需求，同時(shí)也能反應(yīng)出服務(wù)的事務(wù)屬性及失效處理。Petri網(wǎng)及其有關(guān)的分析方法為這些目標(biāo)實(shí)現(xiàn)提供了理論基礎(chǔ)。本文要解決的確實(shí)是如何按照服務(wù)消費(fèi)者的需求來(lái)動(dòng)態(tài)地分配可用服務(wù)，以構(gòu)建所需的可靠服務(wù)組合。為此，提出一種基于Petri網(wǎng)構(gòu)建可靠服務(wù)組合的方法。差不多思路為：第一利用Petri網(wǎng)對(duì)任務(wù)及任務(wù)間的關(guān)系進(jìn)行建模，生成相應(yīng)的工作流模型；其次針對(duì)服務(wù)的事務(wù)屬性，構(gòu)建服務(wù)組合的失效處理模型（ServiceComposition’sFailureProcessing,SCFP），并分析SCFP模型的動(dòng)態(tài)性質(zhì)，從而保證所得到模型的正確性；最后給出可靠服務(wù)組合的定義，分析可靠服務(wù)組合構(gòu)造的充分必要條件，提出相應(yīng)的和諧策略并證明其有效性，同時(shí)給出和諧策略的具體實(shí)施。本文第2節(jié)給出了工作流的 Petri網(wǎng)模型；第3節(jié)分析服務(wù)的事務(wù)屬性和服務(wù)組合的失效處理機(jī)制，生成相應(yīng)的SCFP模型；第4節(jié)提出可靠服務(wù)組合的和諧策略及實(shí)施方法；第5節(jié)通過(guò)具體實(shí)例講明可靠服務(wù)組合的構(gòu)建與分析過(guò)程；第 6節(jié)闡述了有關(guān)的研究工作；最后是結(jié)論和下一步工作。

工作流的Petri網(wǎng)模型服務(wù)組合的功能能夠由多個(gè)獨(dú)立運(yùn)行的子功能構(gòu)成，本文將每個(gè)子功能稱(chēng)為任務(wù)。在服務(wù)組合流程中，每個(gè)任務(wù)會(huì)有多個(gè)可用服務(wù)與之對(duì)應(yīng)。本文假設(shè)每個(gè)服務(wù)只能完成一個(gè)任務(wù)的功能，因此在服務(wù)組合中服務(wù)和任務(wù)是一一對(duì)應(yīng)的。帶事務(wù)屬性的服務(wù)組合流程能夠從工作流和失效處理兩方面進(jìn)行描述[15]，工作流描述任務(wù)之間的數(shù)據(jù)通信或同步，具體講明了任務(wù)組件之間的關(guān)系，直觀(guān)上能夠懂得為一系列任務(wù)的依靠關(guān)系。而服務(wù)組合的失效處理則規(guī)約了服務(wù)運(yùn)行失敗時(shí)的處理機(jī)制，定義了服務(wù)的事務(wù)屬性和服務(wù)的失敗處理。兩者要緊區(qū)別是：前者假設(shè)服務(wù)還沒(méi)分配，僅僅描述服務(wù)組合流程的數(shù)據(jù)依靠；后者假設(shè)服務(wù)差不多分配，要緊考慮服務(wù)的事務(wù)屬性和服務(wù)失敗處理。本節(jié)依據(jù)服務(wù)消費(fèi)者提供的功能需求，利用Petri網(wǎng)的差不多原理，按接口匹配的原則建立系統(tǒng)的工作流模型。2.1任務(wù)Petri網(wǎng)模型由于系統(tǒng)的功能是由一系列任務(wù)組合而成，而任務(wù)的組合又能夠構(gòu)成一個(gè)新的任務(wù)，如此嵌套能夠構(gòu)造出任意復(fù)雜的系統(tǒng)。因此，可利用Petri網(wǎng)對(duì)任務(wù)進(jìn)行建模，且每個(gè)任務(wù)在運(yùn)行過(guò)程中需要輸入某些參數(shù)和輸出一定的結(jié)果。下面給出任務(wù)的形式化定義。定義1：有界Petri網(wǎng)C=(P,T,F)稱(chēng)作任務(wù)，其中：1）P=PSPI是一個(gè)有限庫(kù)所集，PI表示任務(wù)的接口，PS表示任務(wù)的位置，其中PSPI=；2）T是一個(gè)有限的變遷集，m≥0，同時(shí)PT≠,PPi3T=；Pi1P1t1P2(T×P)是有向（3）F(P×T)弧集合，F(xiàn)稱(chēng)為流關(guān)系；tePePintinP3t2P4Pi2圖1帶有接口的任務(wù)C1在任務(wù)模型中，接口代表該任務(wù)輸入或輸出（參數(shù)則映射為庫(kù)所中的令牌）。本文假設(shè)任務(wù)只有獲得所需參數(shù)才能運(yùn)行開(kāi)始操作，且運(yùn)行終止后統(tǒng)一輸出參數(shù)，具體接口個(gè)數(shù)能夠按照實(shí)際情形增減。圖1中的任務(wù)C1有三個(gè)接口：庫(kù)所Pi1和Pi2存放任務(wù)開(kāi)始操作（tin）所需的參數(shù)，而庫(kù)所Pi3則存放任務(wù)終止（tin）的輸出結(jié)果。Pin,Pe表示任務(wù)C1的開(kāi)始和終止位置。某時(shí)刻各庫(kù)所中令牌的分布狀況稱(chēng)為任務(wù)的標(biāo)識(shí)，在標(biāo)識(shí)M下，

庫(kù)所p中的令牌數(shù)量記為 M(p)；變遷t在標(biāo)識(shí)M下使能的，記做M[t>，否則記做M[t<；任意x(PT)，集合●x={y|y(PT)(y,x)F}和x●={y|y(PT)(x,y)F}分別對(duì)應(yīng)于x的輸入和輸出；其它的定義和觸發(fā)規(guī)則與差不多Petri網(wǎng)的定義一樣，具體參照文獻(xiàn)[3]。2.2工作流模型本文采納了進(jìn)程代數(shù)的一種擴(kuò)展機(jī)制來(lái)描述工作流中各個(gè)任務(wù)之間的關(guān)系，形成整個(gè)系統(tǒng)所對(duì)應(yīng)的表達(dá)式[5]。在應(yīng)用算子的過(guò)程中，能夠用括弧來(lái)表達(dá)作用的順序（其中順序算子的優(yōu)先級(jí)最高）。由于模型中的循環(huán)結(jié)構(gòu)，能夠利用文獻(xiàn) [6]介紹的“解循環(huán)”操作，即通過(guò)統(tǒng)計(jì)任務(wù)的歷史數(shù)據(jù)，運(yùn)算循環(huán)的平均執(zhí)行次數(shù)n。因此，本文要緊對(duì)任務(wù)間的順序、選擇和并發(fā)關(guān)系建模，循環(huán)結(jié)構(gòu)能夠通過(guò)任務(wù)的順序執(zhí)行來(lái)完成。假設(shè)Ci和Cj為兩個(gè)任務(wù)，下面先描述任務(wù)間的差不多關(guān)系：（1）算子>表示順序：Ci>Cj表示任務(wù)Ci和Cj順序運(yùn)行，即Cj只有在Ci運(yùn)行終止后才能開(kāi)始。（2）算子+表示選擇：Ci+Cj表示任務(wù)Ci和Cj只有一個(gè)能夠運(yùn)行。3）算子||表示并行：Ci||Cj表示任務(wù)Ci和Cj能夠同時(shí)運(yùn)行，但要它們都執(zhí)行終止后整個(gè)組合才算執(zhí)行終止。通過(guò)采納上述的算子能夠?qū)⑷蝿?wù)間的關(guān)系描述為一個(gè)表達(dá)式。將在任務(wù)Ci運(yùn)行時(shí)刻差不多終止的任務(wù)稱(chēng)為Ci的前向任務(wù)，而Ci運(yùn)行終止時(shí)還未開(kāi)始的任務(wù)稱(chēng)為Ci的后向任務(wù)。為了區(qū)別任務(wù)的操作，在相應(yīng)的變遷和庫(kù)所前標(biāo)注對(duì)應(yīng)的任務(wù)。如任務(wù)Ci中的開(kāi)始變遷，表示為Citin。如果變遷是為了描述任務(wù)間關(guān)系而引入，則不標(biāo)注。順序結(jié)構(gòu)承諾兩個(gè)任務(wù)Ci和Cj順序地執(zhí)行，當(dāng)一個(gè)任務(wù)需要用到另外一個(gè)任務(wù)的輸出時(shí)就要使用順序結(jié)構(gòu)來(lái)組合。順序運(yùn)行Ci>Cj的Petri網(wǎng)模型如圖2所示。在Ci和Cj中引入接口Pij使得，●Pij=Ci te，Pij●=Cj tin。Pij的存在使得任務(wù) CPijj只能C在i.teCi終止之后C.PC開(kāi)j.tin始運(yùn)行。j inCi.Pe圖2順序關(guān)系的建模為了構(gòu)造任務(wù)間的并行，選擇和循環(huán)關(guān)系，需要分別對(duì)任務(wù)間的兩對(duì)差不多組件即AND-split和OR-split，AND-join和OR-join進(jìn)行建模，具體的Petri網(wǎng)模型如圖3所示（設(shè)

任務(wù)Ck是Ci1,Ci2, ,Cim的共同前向/后向任務(wù)）。AND-split的Petri網(wǎng)模型如圖3（a）所示：在Ck中引入接口Pki1,Pki2,,Pkim，每個(gè)并行的任務(wù)Cij中引入接口Pkij。其中●Pkij=Ck te,Pkij●=Cij tin,j=1,2,,n。OR-split的Petri網(wǎng)模型如圖3（b）所示：在Ck和所有的選擇任務(wù)中引入接口Pij使得●Pij=Ckte,Pij●={Ci1tin,Ci2tin,,Cim tin}。AND-join的Petri網(wǎng)模型如圖3c）所示：在Ck中引入接口Pki1,Pki2,,Pkim，每個(gè)并行的任務(wù)Cij中引入接口Pkij。其中Pkij●=Ck tin,●Pkij=Cij te,j=1,Ck.teCk.PeCkPeCk.te2,,n。PiPki1Cim.PinPkimPki2Ci1.PinCim.PinCi2.PinCi1.Pin網(wǎng)模型如圖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 差不多組件的建模下面結(jié)合Petri網(wǎng)的合成運(yùn)算，匹配相應(yīng)的接口以構(gòu)造整個(gè)系統(tǒng)的工作流模型。定義2：設(shè)系統(tǒng)中的任務(wù)Ci=(Pi,Ti,Fi)，則按照下列步驟構(gòu)造的五元組=(C;P,T,F,M0)稱(chēng)為系統(tǒng)的工作流模型：1）C={C1,C2,,Cn}，為系統(tǒng)中任務(wù)的個(gè)數(shù)；2）依據(jù)任務(wù)間關(guān)系，合成C1,C2,,Cn的對(duì)應(yīng)接口；3）引入變遷Tstart和庫(kù)所Pstart分別描述整個(gè)系統(tǒng)的初始位置和開(kāi)始操作，且：●Tstart={Pstart},Tstart●={Ci1 Pin,Ci2 Pin,,CinPin},●Pstart=,Pstart●={Tstart}；4）設(shè)置初始標(biāo)識(shí)M0(Pstart)=1，其余庫(kù)所為0。工作流模型描述整個(gè)系統(tǒng)所能完成的功能，對(duì)工作流模型中每個(gè)任務(wù)分配具體的服務(wù)則構(gòu)成了服務(wù)組合。如果分配過(guò)程中考慮服務(wù)的事務(wù)屬性，則稱(chēng)它為帶事務(wù)屬性的服務(wù)組合。本文中如無(wú)專(zhuān)門(mén)講明，服務(wù)組合均指帶事務(wù)屬性的服務(wù)組合。下面按照所得的工作流模型構(gòu)造服務(wù)組合的失效處理模型。服務(wù)組合的失效處理模型

3.1服務(wù)的事務(wù)屬性由于Web服務(wù)自身的特點(diǎn)，使得傳統(tǒng)的事務(wù)處理技術(shù)無(wú)法直截了當(dāng)應(yīng)用在Web服務(wù)事務(wù)的處理過(guò)程，文獻(xiàn)[7]提出的模型指明了服務(wù)事務(wù)屬性的語(yǔ)義，該模型是基于文獻(xiàn)[8]所考慮的三種不同的類(lèi)型的事務(wù)屬性。由此能夠延伸Web服務(wù)執(zhí)行任務(wù)時(shí)要緊有下面三種特性：可重復(fù)的（r），可補(bǔ)償?shù)模╟p），不可補(bǔ)償也不可重復(fù)的（p）。相應(yīng)的服務(wù)事務(wù)屬性能夠有以下幾種情形：{cp}、{p}、{r}、{r,cp}。按照服務(wù)的事務(wù)屬性，能夠建立如圖 4所示的模型。圖4（a）是對(duì)可補(bǔ)償?shù)姆?wù)進(jìn)行建模，PItr表示該服務(wù)事務(wù)處理的條件。庫(kù)所SiPItr中有令牌表示服務(wù)組合中有其它服務(wù)失敗，需要按照服務(wù)Si的事務(wù)屬性進(jìn)行相應(yīng)的和諧。而服務(wù)的輸入和輸出（PIin,PIe）按照實(shí)際需要能夠進(jìn)行增減?？裳a(bǔ)償服務(wù)的運(yùn)行過(guò)程可能處于初始、運(yùn)行、終止、中斷、取消、補(bǔ)償和失敗位置，其中Pin,Pac,Pe,Pab,Pca,Pcp,Pfa稱(chēng)為任務(wù)的位置庫(kù)所。其它的事務(wù)屬性能夠用類(lèi)似的方法進(jìn)行描述，具體的模型如圖4(b)－圖4(d)。PIinPcaPIePIinPcaPePItrtcaPePItrtcaPePacPacPinPintintetintetcptabtabtrttfatrttfaPcpPabPabPfaPfa(c)r(d)r,cp圖4 服務(wù)的事務(wù)屬性模型通過(guò)對(duì)圖4的分析可知，事務(wù)屬性不同的服務(wù)，運(yùn)行過(guò)程可能到達(dá)的位置集和操作也不同。圖 4中庫(kù)所和變遷的實(shí)際映射如表 1所示：表1事務(wù)屬性模型中變遷和庫(kù)所的對(duì)比P/T位置/操作P/T位置/操作P/T位置/操作Pin初始位置Pab中斷位置Pfa失敗位置Pe終止位置Pca取消位置Pcp補(bǔ)償位置Pac運(yùn)行位置PIe終止輸出PIc失敗輸出PItr事務(wù)輸入PIin運(yùn)行輸入tin運(yùn)行操作tca取消操作trt重試操作tfa失敗操作tcp補(bǔ)償操作tab中斷操作te終止操作從表1可知，采納Petri網(wǎng)能夠精確地描述服務(wù)的事務(wù)屬性。將初始、運(yùn)行、終止和失敗位置稱(chēng)為服務(wù)的運(yùn)行位置，而中斷、取消和補(bǔ)償位置稱(chēng)為服務(wù)的事務(wù)位置。3.2服務(wù)組合的失效處理模型由于每個(gè)服務(wù)具有自身的事務(wù)屬性。當(dāng)某個(gè)服務(wù)運(yùn)行失敗時(shí)，如何和諧其它服務(wù)，保證整個(gè)系統(tǒng)的可靠運(yùn)行，成為服務(wù)組合中必須解決的一個(gè)咨詢(xún)題。本文引入失效處理模塊（FCM）來(lái)處理該咨詢(xún)題。假設(shè)同一時(shí)刻系統(tǒng)中最多有一個(gè)服務(wù)失敗，其服務(wù)失敗處理時(shí)刻能夠忽略。

由于實(shí)際情形中有些任務(wù)是不可取消的也不能夠補(bǔ)償?shù)模?NCC），這類(lèi)任務(wù)所對(duì)應(yīng)的服務(wù)和諧操作比較專(zhuān)門(mén)。如其它服務(wù)失敗的時(shí)刻該服務(wù)處于運(yùn)行位置，則和諧其到達(dá)終止位置。其對(duì)應(yīng)的服務(wù)模型如圖 5所示，其中tce是服務(wù)的和諧操作。IPIinPIeIPIinPIeePPacPPactPintinPinttinttababtfa結(jié)果。PabtrtPfaPabPfa(a)NCCPc(b)r,NCC圖5不可取消任務(wù)對(duì)應(yīng)的服務(wù)模型不妨設(shè)服務(wù)Si是完成Ci的功能，則服務(wù)組合的失效處理機(jī)制有：1）設(shè)任務(wù)Ci是Cj的前向任務(wù)，若服務(wù)Si失敗，則中斷服務(wù)Sj。2）設(shè)任務(wù)Ci是Cj的前向任務(wù)，若服務(wù)Sj失敗，分兩種情形和諧Si：①服務(wù)Si是可補(bǔ)償?shù)?，則對(duì)Si進(jìn)行補(bǔ)償；②服務(wù) Si是不可補(bǔ)償?shù)?，則不做任何操作，服務(wù) Sj停留在終止位置。3）設(shè)任務(wù)Ci是Cj并行運(yùn)行，若服務(wù)Si失敗，分四種情形和諧Sj：①服務(wù)Sj處在運(yùn)行位置且任務(wù)Cj可取消的，則取消 Sj的運(yùn)行；②服務(wù)Sj處在運(yùn)行位置且任務(wù)Cj不可取消的，則和諧Sj的運(yùn)行使其到達(dá)終止位置；③服務(wù) Sj處在終止位置且Sj是可補(bǔ)償?shù)模瑒t對(duì) Sj運(yùn)行補(bǔ)償；④服務(wù)Sj處在終止位置且Sj是不可補(bǔ)償?shù)模瑒t不做任何操作，服務(wù)Sj停留在終止位置。失效處理模塊的功能為：當(dāng)系統(tǒng)中某個(gè)服務(wù)運(yùn)行失敗時(shí)，基于上述處理機(jī)制，依據(jù)其它服務(wù)的事務(wù)屬性和諧系統(tǒng)終止。下面對(duì)FCM進(jìn)行建模（同理在變遷和庫(kù)所之前標(biāo)注對(duì)應(yīng)的服務(wù)）。引進(jìn)庫(kù)所Pc和變遷tc分別表示系統(tǒng)和諧的初始位置和和諧操作，使得：1）Pc={S1tfa,S2tfa,,Sktfa},Pc=tc2）tc=Pc,tc={S1PItr,S2 PItr, ,Sn PItr}條件（1）表明服務(wù)組合中若有服務(wù)失敗則調(diào)用FCM模型；條件（2）描述了FCM模塊給每個(gè)服務(wù)都輸入事務(wù)處理參數(shù)。若對(duì)工作流模型中的每個(gè)任務(wù)都分配一個(gè)服務(wù)，則構(gòu)成了具體的服務(wù)組合，不妨設(shè)S為分配好的服務(wù)集?；诖?，下面給出服務(wù)組合的失效處理模型形式化定義：定義3：工作流模型，S是所分配的服務(wù)集，則按照下列步驟構(gòu)造的四元組S=(Ps,Ts,Fs;Ms0)稱(chēng)為

服務(wù)組合的失效處理模型（ ServiceComposition’sFailureProcessing,SCFP）：1）按照服務(wù)的事務(wù)屬性建模構(gòu)造S集合中每個(gè)服務(wù)的Petri網(wǎng)模型；2）按照中的數(shù)據(jù)流程合成服務(wù)的Petri網(wǎng)模型；3）依據(jù)上述FCM模型的建模方式添加相應(yīng)的變遷和庫(kù)所。4）保持中的初始狀態(tài)不變。從定義3能夠看出SCFP模型是在工作流模型的基礎(chǔ)上對(duì)帶事務(wù)特性的服務(wù)組合進(jìn)行建模。3.3模型性質(zhì)本文中系統(tǒng)狀態(tài)由標(biāo)識(shí) M表示，如M(Ci Pe)=1表示在狀態(tài)M下，任務(wù)Ci差不多運(yùn)行終止。將任務(wù)Ci在狀態(tài)Ma中不為零的庫(kù)所記作Mai。下面分析SCFP模型的一些要緊性質(zhì)。性質(zhì)1：SCFP模型 S中，任一可達(dá)狀態(tài)M下的每個(gè)服務(wù)都只能處于一個(gè)位置。證明：從建模過(guò)程 S可知，服務(wù)Si的位置庫(kù)所滿(mǎn)足庫(kù)所不變量：M(Si Pin)+M(Si Pac)+M(Si Pca)+M(Si Pfa)+M(Si Pe)+M(SiPab)+M(Si

Pcp)=1。而服務(wù)組合一

性質(zhì)

2：SCFP模型

S保證了旦運(yùn)行，會(huì)對(duì)每個(gè)服務(wù)進(jìn)行初始化 服務(wù)組合的失效處理機(jī)制。（變遷Tstart），即輸入令牌到庫(kù)所S證明：（1）證明S保證了服務(wù)。按照Petri網(wǎng)的運(yùn)行機(jī)制可組合的失效處理機(jī)制（1）iPin得：服務(wù)只能處于初始、運(yùn)行、取設(shè)任務(wù)Ci是Cj的前向任務(wù)，在消、失敗、終止、中斷和補(bǔ)償位置狀態(tài)M下服務(wù)Si失敗中的一個(gè)。證畢∴M(Pc)=1同一個(gè)SCFP模型由于任務(wù)對(duì)∵Pc=tc,tc=Pc,tc={S1應(yīng)的服務(wù)失敗時(shí)刻不同，系統(tǒng)的終PItr,S2PItr,,SnPItr}止位置也會(huì)不同。按照任務(wù)間的關(guān)∴M[tc>M’,其中M’(SjPI系運(yùn)算出工作流模型的所有可能tr)=1終止?fàn)顟B(tài)，記為T(mén)S()。其中TS()∵任務(wù)Ci是Cj的前向任務(wù)={ME}TSF()：∴M’(SjPin)=1（1）正常終止?fàn)顟B(tài)ME：i∴M’[Sjtab>[1,n]ME(Ci，表示系統(tǒng)∵M(jìn)’[Sjtab>M’’,其中M’’Pe)=1ME中所有任務(wù)都正常終止的狀態(tài)。關(guān)(SjPab)=1于一個(gè)工作流模型，其正常終止?fàn)睢嘞到y(tǒng)中斷了服務(wù)Sj態(tài)唯獨(dú)。即S保證了服務(wù)組合的失效（2）失敗終止?fàn)顟B(tài)集合TSF處理機(jī)制（1）。()：MFTSF()有i[1,n]同理按照任務(wù)間的關(guān)系，能夠，表示分別證明S保證了服務(wù)組合的失MF(CiPfa)=1MF(CiPfa)系統(tǒng)中任務(wù)Ci失敗，通過(guò)系統(tǒng)和諧效處理機(jī)制（2）和（3）。到達(dá)的終止?fàn)顟B(tài)，也稱(chēng)MF(CiPfa)綜上所述，SCFP模型S保證是Ci的失敗終止?fàn)顟B(tài)。記集合TSF了服務(wù)組合的失效處理機(jī)制。(,Ci)是任務(wù)Ci在TSF()中的所證畢有失敗終止?fàn)顟B(tài)集合。性質(zhì)2指出本文建立的模型能在服務(wù)組合中，失效處理機(jī)制 夠確保服務(wù)組合的失效處理機(jī)制正是系統(tǒng)的核心。因此有必要分析建 確運(yùn)行，從而講明了失效處理機(jī)制立的模型是否保證該處理機(jī)制。 建模方式的正確性。性質(zhì)3：SCFP模型S中，任，滿(mǎn)足下列兩個(gè)條件Cj(ij)Ma,Mb一可達(dá)狀態(tài)M下若存在某個(gè)服務(wù)是之一：處于事務(wù)位置，則存在唯獨(dú)的服務(wù)（1）Maj=Mbj處于失敗位置。（2）Ma(CjPe)+Ma(CjPcp)證明：不妨設(shè)在終止?fàn)顟B(tài)M下，=Mb(CjPca)+Mb(CjPab)=1服務(wù)Si處于事務(wù)位置，即中斷、取稱(chēng)狀態(tài)Ma和Mb是相容的，記消或補(bǔ)償。做MaMb。否則稱(chēng)狀態(tài)Ma和MbM(SiPca)+M(SiPab)+M是不相容的，記做MaMb。記TS(SiPcp)=1()中與狀態(tài)Ma相容的狀態(tài)集合為∵●(SiPca)=Sitca●(SiCS(Ma)。Pab)=Sitab●(SiPcp)=Sit從定義4可知，兩個(gè)終止?fàn)顟B(tài)cp不相容必須同時(shí)滿(mǎn)足下列兩個(gè)條且●(Sitca)●(Sitab)●件：（1）屬于同一個(gè)任務(wù)的失敗終(Sitcp)=SiPItr止?fàn)顟B(tài)；（2）存在某個(gè)任務(wù)在這兩∵●(SiPItr)=tc,tc=Pc,個(gè)狀態(tài)下分別處于終止和補(bǔ)償位Pc={S1tfa,S2tfa,,Sntf置。否則Ma和Mb是相容的，明顯a}狀態(tài)和自己本身是相容的。∴SjS,M(SjPfa)=1定義5：終止?fàn)顟B(tài)集合S，若任∵服務(wù)組合中同一時(shí)刻最多有意的失敗終止?fàn)顟B(tài)Ma，MbS(a一個(gè)服務(wù)失敗b)滿(mǎn)足下列條件之一，則稱(chēng)S是一致∴!SjS,M(SjPfa)=1的：即存在唯獨(dú)的服務(wù)Sj處于失?。?）Ci,Cj,Ma(CiPfa)=位置證畢Mb(CjPfa)=1CiCj上述要緊分析了SCFP模型的（2）i,Ma(CiPfa)=Mb(Ci差不多性質(zhì)和特點(diǎn)，下面基于上述Pfa)=1MaMb性質(zhì)深入分析SCFP模型的一致性。終止?fàn)顟B(tài)集合S是一致的指該定義4：任意兩個(gè)終止?fàn)顟B(tài) Ma, 集合中任意兩個(gè)狀態(tài)要么不屬于同Mb TSF( ,Ci)，若關(guān)于所有任務(wù) 一個(gè)任務(wù)的失敗終止?fàn)顟B(tài)集，要么相容。下面通過(guò)判定模型終止?fàn)顟B(tài)∴SjS(ij),使得Ma(CjP集的一致性來(lái)分析模型的正確性。e)=Mb(CjPcp)=1定義6：集合STS(S)稱(chēng)為服依據(jù)任務(wù)Cj和Ci的關(guān)系，下面務(wù)組合S的可達(dá)終止?fàn)顟B(tài)集合，若分三種情形來(lái)分析：關(guān)于任意STSiSTS(S)有：第一設(shè)Cj是Ci的前向任務(wù)（1）存在變遷序列，使得M按照性質(zhì)1可知，在Si失敗時(shí)0[>STSiSj處于終止位置（2）tT,STSi[t<∴Ma(CjPe)=1由于Petri網(wǎng)的特性，服務(wù)組合∵M(jìn)a(CiPfa)=1的可達(dá)狀態(tài)能夠表示各個(gè)可用服務(wù)∴Ma(Pc)=1的運(yùn)行終止?fàn)顟B(tài)。如M1={S1fa,∴Sj是不可補(bǔ)償?shù)腟2cp,,Snca}表示服務(wù)組∵M(jìn)b(CjPcp)=1合某次運(yùn)行終止時(shí)：S1處于失敗位∴Sj是可補(bǔ)償?shù)?，與上面推出置，S2處于補(bǔ)償位置，Sn處于取消來(lái)Sj是不可補(bǔ)償?shù)拿?。位置。而任?wù)與服務(wù)是一一對(duì)應(yīng)的，同理能夠證明當(dāng)Cj和Ci是并行因此能夠把狀態(tài)M1中的服務(wù)用所關(guān)系時(shí)（服務(wù)Sj分可取消的和不可對(duì)應(yīng)的任務(wù)來(lái)表示。下面從理論上取消的）也存在矛盾。分析SCFP模型所到達(dá)的終止?fàn)顟B(tài)綜上所述，S的終止?fàn)顟B(tài)集合集合是一致的。具有一致性。證畢定理1：SCFP模型S的終止基于服務(wù)組合的失效處理機(jī)狀態(tài)集合具有一致性。制，結(jié)合任務(wù)間的關(guān)系能夠證明服證明：反證法，假設(shè)SCFP模型務(wù)組合的終止?fàn)顟B(tài)集合滿(mǎn)足一致性S的終止?fàn)顟B(tài)集合不具有一致性。定義。從而講明SCFP模型的正確不妨設(shè)Ma,MbSTS(S),M性。aMb4可靠服務(wù)組合的和諧技術(shù)∴SiS:Ma(CiPfa)=Mb(C本節(jié)給出可靠服務(wù)組合的定iPfa)=1義，分析可靠性的內(nèi)在條件，提出∵M(jìn)a和Mb不相容服務(wù)組合的和諧策略并證明其有效性，最后給出和諧策略的實(shí)施方法。4.1服務(wù)組合的可靠性轉(zhuǎn)化為對(duì)可用服務(wù)的終止?fàn)顟B(tài)要設(shè)可用服務(wù)集合WS={WS1,W求。S2,WSn}，其中WSi為任務(wù)C可靠服務(wù)組合不僅能夠完成系i的可用服務(wù)集合，ij有WSi統(tǒng)的功能要求，而且某個(gè)服務(wù)失敗WSj=。服務(wù)組合的構(gòu)造過(guò)程確實(shí)時(shí)會(huì)到達(dá)服務(wù)消費(fèi)者可同意的狀態(tài)是WSi中服務(wù)與任務(wù)Ci的匹配過(guò)[9]。下面結(jié)合服務(wù)組合的工作流模程。關(guān)于具體的服務(wù)組合流程，服型，給出服務(wù)組合可靠性的定義。務(wù)消費(fèi)者的需求能夠歸結(jié)為可同意定義9：設(shè)服務(wù)組合的工作流模狀態(tài)集合。下面給出該集合在SCFP型=(C;P,T,F,M0)，s是基于的模型中的映射。一個(gè)服務(wù)組合，且服務(wù)消費(fèi)者的可定義7：集合ATS()TS()同意狀態(tài)集為ATS()。若s滿(mǎn)足表示服務(wù)消費(fèi)者對(duì)工作流模型的如下條件，則稱(chēng)服務(wù)組合s是可靠可同意狀態(tài)集。可同意狀態(tài)Mi={Mi的：(C1),Mi(C2),,Mi(Cn)},Mi(C（1）MESTS(S)j){ab,ca,e,fa,cp}。記ATS(,（2）STS(S)ATS();Ci)表示可同意狀態(tài)集中任務(wù)Ci的其中，條件（1）要求服務(wù)組合失敗終止?fàn)顟B(tài)。能夠完成服務(wù)消費(fèi)者的功能需求，明顯MEATS()，ATS(,Ci)而條件（2）表示S的所有可達(dá)終TSF(,Ci)。同樣只有一致的可同止?fàn)顟B(tài)差不多上服務(wù)消費(fèi)者可同意意狀態(tài)集才是有效的，下面給出可的，即在任何情形下，服務(wù)組合都同意狀態(tài)集有效性的形式化定義：能達(dá)到服務(wù)消費(fèi)者的可同意狀態(tài)。定義8：可同意狀態(tài)集ATS()按照ME的定義并結(jié)合Petri網(wǎng)的運(yùn)是有效的，若MATS()有：行機(jī)制可知，按照第3節(jié)方法所構(gòu)CiC,M(CiPfa)=1存在唯獨(dú)的造的s模型必定能夠到達(dá)正常終狀態(tài)M’ATS(),M’是Ci的和止?fàn)顟B(tài)ME。因此在后面分析服務(wù)組諧狀態(tài)且CCS(M’,Ci)=ATS(,Ci)。合可靠性時(shí)，僅需要考慮條件（2）。同理，能夠?qū)⒎?wù)消費(fèi)者的可4.2服務(wù)組合的和諧策略同意狀態(tài)中對(duì)任務(wù)的終止?fàn)顟B(tài)要求本節(jié)引入和諧集的概念，并分析服務(wù)組合可靠性與和諧集的關(guān)系；其次結(jié)合服務(wù)消費(fèi)者的可同意（3）CjC:Ci||Cj且Cj不能狀態(tài)集，提出和諧策略。取消，則MiCCS(M,Ci)有Mi(Cj定義10：同時(shí)滿(mǎn)足下列兩個(gè)條Pca)+Mi(CjPcp)=0件的終止?fàn)顟B(tài)M稱(chēng)為任務(wù)Ci的和諧從定義11可知CCS(M,Ci)=CS狀態(tài)：s(M)-kj=1FS(Ci,Cj)，其中k為與C（1）M(CiPfa)=1i并行且不可取消的任務(wù)個(gè)數(shù)。（2）CjC:Ci||CjM(CjP關(guān)于分配了可重復(fù)服務(wù)的任e)+M(CjPcp)=1務(wù)，其CCS(M,Ci)=。由于同一個(gè)在任務(wù)Ci的和諧狀態(tài)下，其并工作流模型中任務(wù)的和諧狀態(tài)不行任務(wù)都處于終止或補(bǔ)償位置。和唯獨(dú)，因此和諧集也不唯獨(dú)。系統(tǒng)諧狀態(tài)是基于任務(wù)的失敗狀態(tài)定義在任務(wù)Ci失敗的情形下，依據(jù)目前的，因此同一個(gè)任務(wù)的和諧狀態(tài)不各個(gè)任務(wù)的位置，和諧系統(tǒng)到達(dá)和唯獨(dú)。設(shè)在工作流模型中任務(wù)Ci和諧集中的一個(gè)狀態(tài)。下面分析和諧Cj是并行關(guān)系，若Cj是不可取消的，集與SCFP模型狀態(tài)一致性的關(guān)系。則稱(chēng)狀態(tài)集合FS(Ci,Cj)為Cj針對(duì)C引理1：在服務(wù)組合模型S中，i的錯(cuò)誤終止?fàn)顟B(tài)。其中MFS(C若任意服務(wù)Si失敗，則系統(tǒng)存在唯i,Cj)，使得：M(CiPfa)=M(CjPc獨(dú)與之對(duì)應(yīng)的和諧集。a)+M(CjPcp)=1。FS(Ci,Cj)指系統(tǒng)證明：反證法假設(shè)服務(wù)組合模中Ci失敗而Cj處于取消或補(bǔ)償?shù)奈恍蚐，在服務(wù)Si失敗的情形下，系置。由于Cj是不可取消的，因此在統(tǒng)存在多個(gè)和諧集。任何情形下Cj都可不能到達(dá)取消或不妨設(shè)服務(wù)Si失敗時(shí)，服務(wù)組補(bǔ)償?shù)奈恢谩：蟂能夠依據(jù)和諧集CCS(Ma,Ci)定義11：同時(shí)滿(mǎn)足下列三個(gè)條和CCS(Mb,Ci)對(duì)其它服務(wù)進(jìn)行和件的終止?fàn)顟B(tài)集合CCS(M,Ci)稱(chēng)為諧。系統(tǒng)在Ci失敗情形下的和諧集：∴MaSTS(S)MbSTS（1）M是Ci的和諧狀態(tài)(S)（2）MiCCS(M,Ci)有Mi∵M(jìn)a和Mb差不多上任務(wù)CiM的和諧狀態(tài)∴CjC:Ci||Cj有Ma(Sj

Pe)+Ma(Sj

Pcp)=1，

∴Ma=MFMb(Sj

Pe)+Mb(Sj

Pcp)=1

∴Ma

ATS(

)∵M(jìn)a

Mb

(2) Si

S,Ma(Ci

Pfa)

1，∴CjC:Ci||Cj且Ma(SjP即Ci在服務(wù)組合S中分配了不可e)=Mb(Sj，即MaMb重復(fù)的服務(wù)SiPcp)=1∵M(jìn)a(SiPfa)=Mb(SiPfa)=1∵服務(wù)組合具有一致性∴STS(S)不一致與定理1矛∴唯獨(dú)的Ci的和諧狀態(tài)M盾a’，使得MaCCS(Ma’,Ci)∴在服務(wù)組合模型S中，若任∵SiS,Ma(CiPfa)1意服務(wù)Si失敗，則系統(tǒng)存在唯獨(dú)與∴服務(wù)Si是不可重復(fù)的之對(duì)應(yīng)的和諧集。∵關(guān)于S中不可重復(fù)的服務(wù)S證畢i，存在Ci的和諧狀態(tài)MSTS(S)定理2：在服務(wù)組合S中，S∵S中關(guān)于不可重復(fù)的服務(wù)STS(S)ATS()當(dāng)且僅當(dāng)任意Si只存在一個(gè)和諧集中不可重復(fù)的服務(wù)Si，存在Ci的和∴Ma’=M諧狀態(tài)MSTS(S)且CCS(M,Ci)=∴MaCCS(M,Ci)ATS(,Ci)?！逤CS(M,Ci)=ATS(,Ci)證明：∴MaATS()∵不妨設(shè)任務(wù)Ci在S由不可綜上，MaSTS(S)Ma重復(fù)的服務(wù)Si來(lái)完成ATS()∴MSTS(S)，M是Ci的∴在服務(wù)組合S中，STS(S)和諧狀態(tài)ATS()當(dāng)且僅當(dāng)任意S中不可由引理1可知：CCS(M,Ci)S重復(fù)的服務(wù)Si，存在Ci的和諧狀態(tài)TS(S)MSTS(S)且CCS(M,Ci)=ATS∵STS(S)ATS()(,Ci)。證畢CCS(M,Ci)ATS()關(guān)于 Ma STS( S)Si S,Ma(Ci Pfa) 1即 Ci C,Ma(Ci Pfa)

1

從定理2可知，服務(wù)組合可靠性的咨詢(xún)題能夠通過(guò)分析和諧集與可同意狀態(tài)集的關(guān)系來(lái)實(shí)現(xiàn)。由于可靠服務(wù)組合S的可能（1）若MATS()，M(Ci終止?fàn)顟B(tài)集合STS(S)ATS()。，且SiWSi,TP(Si)={cPcp)=1因此，按照S的運(yùn)行機(jī)制可知，Ap}，則將Si分配給任務(wù)Ci，否則出TS()對(duì)S中調(diào)用的服務(wù)事務(wù)屬錯(cuò)（可靠服務(wù)組合不存在）；性存在如下關(guān)系：（2）若MATS(),M(Ci（1）MATS(),使得M(Ci，且SiWSi,TP(Si)=Pcp)=0Pfa)=1，則rTP(Si)；{p}，則將Si分配給任務(wù)Ci，否則（2）MATS(),使得M(Ci出錯(cuò)；，則r；（3）若MATS(),M(CiPfa)=0TP(Si)（3）MATS(),使得M(Ci，且SiWSi,TP(Si)={r}，Pfa)=0，則cpTP(Si)；則將Si分配給任務(wù)Ci，否則出錯(cuò)；Pcp)=1（4）MATS(),使得M(Ci（4）若MATS(),M(CiPcp)=0，則cpTP(Si)。Pab)=1，任選WSi中的一個(gè)可用定義12：按照定理2和上述關(guān)服務(wù)Si，將Si分配給任務(wù)Ci。系，構(gòu)造可靠服務(wù)組合的和諧策略其中，策略1的優(yōu)先級(jí)大于為：策略2，即優(yōu)先使用策略1，只有策策略1：調(diào)整可同意狀態(tài)集AT略1不能使用時(shí)才調(diào)用策略2。S()利用和諧策略構(gòu)造可靠服務(wù)組（1）若MATS(),M(CiP合的差不多思想是：針對(duì)特定的服cp)=1，且SiWSi,TP(Si)={cp,r}，務(wù)消費(fèi)者的需求（可同意狀態(tài)集），則將服務(wù)Si分配給任務(wù)Ci，ATS()按照和諧策略分配服務(wù)給任務(wù)。=ATS()-TSF(,Ci)；4.3和諧策略的有效性（2）若MATS(),M(CiP和諧策略作用是在服務(wù)組合流cp)=0，且SiWSi,TP(Si)={r}，則程中如何按照服務(wù)消費(fèi)者的需求來(lái)將Si分配給任務(wù)Ci，ATS()=ATS動(dòng)態(tài)地分配服務(wù)。因此有必要分析()-TSF(,Ci)。和諧策略的有效性，即按照和諧策策略2：對(duì)未分配服務(wù)的任務(wù)分略構(gòu)造的服務(wù)組合是可靠的。配服務(wù)定理3：針對(duì)有效的ATS( )， ∴給任務(wù)Cj分配的Sj具有不可按照和諧策略構(gòu)造出來(lái)的服務(wù)組合 補(bǔ)償?shù)氖聞?wù)屬性S是可靠的?！進(jìn)a’(SjPcp)=1證明：不妨設(shè)任務(wù)Ci在服務(wù)組∴Sj具有可補(bǔ)償?shù)氖聞?wù)屬性，合S中分配了不可重復(fù)的服務(wù)Si與上述結(jié)果矛盾∴MaSTS(S),Ma(CiPfa)∴Ma’=Mb’=1∴S中任意不可重復(fù)的服務(wù)S∵服務(wù)組合S關(guān)于Si失敗的i，存在Ci的和諧狀態(tài)MSTS(S)和諧集唯獨(dú)且CCS(M,Ci)=ATS(,Ci)∴唯獨(dú)的Ci的和諧狀態(tài)M∴按照定理2有STS(S)ATa’，使得MaCCS(Ma’,Ci)S()∵任務(wù)Ci在服務(wù)組合S中分∴服務(wù)組合S是可靠的。配了不可重復(fù)的服務(wù)Si綜上所述，針對(duì)有效的ATSMbATS(),Mb(CiPc()，按照和諧規(guī)策略構(gòu)造出來(lái)的服p)=1（由步驟（）推出）務(wù)組合S是可靠的。21∵可同意狀態(tài)集ATS()有效證畢的因此，針對(duì)特定的用戶(hù)需求，∴唯獨(dú)的Ci的和諧狀態(tài)M采納和諧策略生成整個(gè)系統(tǒng)的服務(wù)b’，使得CCS(Mb’,Ci)=ATS(,Ci)組合具有可靠性?！喽ɡ碜C明轉(zhuǎn)化為證Ma’=Mb’4.4和諧策略的實(shí)施反證法，假設(shè)Ma’Mb’按照上述分析，采納和諧策略∵M(jìn)a’,Mb’為任務(wù)Ci的兩個(gè)構(gòu)造可靠服務(wù)組合的實(shí)施步驟如不同的和諧狀態(tài)下：∴CjC:Ci||Cj,有Ma’(Sj（1）構(gòu)造工作流模型的和諧Pcp)=Mb’(SjPe)=1集。該集合不隨服務(wù)消費(fèi)者改變而∵M(jìn)b’(SiPe)=1改變。關(guān)于同一個(gè)流程，和諧集是∴MATS()，M(CiPcp)可重復(fù)使用的。=0（2）分析服務(wù)消費(fèi)者可同意狀態(tài)集是否有效。如果無(wú)效，即服務(wù)消費(fèi)者的可同意狀態(tài)集本身是矛盾的，則提示服務(wù)消費(fèi)者修改可同意狀態(tài)集。3）結(jié)合服務(wù)消費(fèi)者的可同意狀態(tài)集，按照和諧策略構(gòu)造可靠服務(wù)組合，實(shí)施算法如表2所示。該算法第一按照策略1對(duì)任務(wù)盡可能分配滿(mǎn)足條件的可重復(fù)服務(wù)，并調(diào)整可同意狀態(tài)集；其次基于新的可同意狀態(tài)集，按照和諧策略2連續(xù)分配服務(wù)，直到所有任務(wù)都有相應(yīng)的可用服務(wù)能夠滿(mǎn)足；若某個(gè)任務(wù)不存在滿(mǎn)足要求的服務(wù)則報(bào)錯(cuò)。表2可靠服務(wù)組合的構(gòu)造算法1:Update_ATS(ATS,C,WS) //調(diào)整可同意狀態(tài)2:If M ATS()andM(Ci?Pcp)=1 //可補(bǔ)償?shù)?: If Si WSiandTP(Si)={cp,r}SiCi;//表示分配操作ATS()=ATS()-TS(,Ci);C=C-Ci;S=SSi;//C和S分別表示任務(wù)集和服務(wù)集Update_ATS(ATS,C,WS)//進(jìn)行下一輪的調(diào)整8:ElseIf M ATS()andM(Ci?Pcp)=0)//不可補(bǔ)償?shù)?: 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)//對(duì)剩下的任務(wù)分配服務(wù)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);實(shí)例研究本節(jié)通過(guò)簡(jiǎn)化的旅行服務(wù)來(lái)演示和諧策略的實(shí)施過(guò)程。對(duì)旅行服務(wù)來(lái)講，它包括飛機(jī)票或火車(chē)訂購(gòu)、汽車(chē)租賃和行程規(guī)劃等有關(guān)業(yè)務(wù)。具體服務(wù)組合流程為：當(dāng)客戶(hù)預(yù)備旅行時(shí)，第一查閱信息并選擇目的地（C0），訂購(gòu)火車(chē)票(C1)負(fù)責(zé)處理客戶(hù)的火車(chē)票，訂購(gòu)飛機(jī)票(C2)按照服務(wù)消費(fèi)者的要求訂購(gòu)合適的航班，行程規(guī)劃(C3)負(fù)責(zé)目的地具體的行程安排，汽車(chē)租賃(C4)安排客戶(hù)到達(dá)火車(chē)站或者飛機(jī)場(chǎng)，賓館預(yù)訂(C5)是客戶(hù)到達(dá)目的地后對(duì)所住地點(diǎn)的安排，最后通過(guò)當(dāng)?shù)芈眯?C6)負(fù)責(zé)客戶(hù)的當(dāng)?shù)芈眯杏嘘P(guān)事宜。利用第2節(jié)介紹的算子，該組合流程可表示為表達(dá)式：C0>(C1+C2)>C3>(C4||C5)>C6，假設(shè)任務(wù)C5是不可取消的。按照工作流模型的建模步驟，能夠構(gòu)造出整個(gè)系統(tǒng)的所對(duì)應(yīng)工作流模型 =(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庫(kù)e所C和2.te變C3遷.te刻畫(huà)C4.t了e任C5.務(wù)te C6.teC.PC.PC.PeC.PeC4.PeC5.PeC6.Pe的相應(yīng)位置及任務(wù)之間的關(guān)系。P012P123P35P34P56P46圖6旅行服務(wù)的工作流模型假設(shè)目前的可用服務(wù)有22個(gè)，具體的事務(wù)屬性如表 3所示：表3 服務(wù)的事務(wù)屬性任務(wù)WSTP任務(wù)WSTPS01pS11cpC0S02r,cpC1S12PS03cpS13r,cpS21pS31r,cpC2S22pC3S32PS23pS33cpS41rS51cpC4S42cpC5S52pS43pS53r,cpS54rS61cpC6S62pS63cp下面給出服務(wù)消費(fèi)者的當(dāng)前可同意狀態(tài)集，如表4所示。其中M8-={C0cp,C1cp/C2e,C3cp,C4e,C5e,C6fa}表示服務(wù)S6失敗時(shí)，服務(wù)消費(fèi)者可同意服務(wù) S0，S1，S3得到補(bǔ)償，而其余服務(wù)不能補(bǔ)償。表4可同意狀態(tài)集ATSMCC0C1/C2C3C4C5C6M1eeeeeeM2faabababababM3cpfaababababM4cpcpfaabababM5cpcpcpfaeabM6cpcpcpefaabM7cpcpcpcafaab

M8 cp cp/e cp e e fa第一運(yùn)算該工作流模型的和諧集，按照可同意狀態(tài)集的有效性定義可知ATS是有效的。下面基于ATS，按照和諧策略構(gòu)造服務(wù)組合，具體步驟如下：步驟1：應(yīng)用和諧策略1，分配可重復(fù)服務(wù)所對(duì)應(yīng)的任務(wù)，并按照策略1中可同意狀態(tài)集的運(yùn)算公式調(diào)整ATS。第一分配服務(wù) S02給任務(wù)C0，相應(yīng)地ATS調(diào)整為{M1,M3,M4,M5,M6,M7,M8,M10,M11,M12,M13,M14,M15}。同理對(duì)任務(wù)C1,C3,C4,C5分別分配服務(wù)S13,S31,S41,S54，最后ATS調(diào)整為{M1, M8}步驟2：應(yīng)用和諧策略2，基于可同意狀態(tài)集{M1, M8}，對(duì)剩下的任務(wù)C2和C6分配服務(wù)。最后分配結(jié)果為S2=S23,S6=S62。至此，工作流模型中的每個(gè)任務(wù)都分配一個(gè)服務(wù)。按照服務(wù)的事務(wù)屬性和服務(wù)組合的失效處理機(jī)制，能夠得到旅行服務(wù)的 SCFP模型S=(Ps,Ts,Fs;Ms0)，如圖7所示。該模型的可達(dá)終止?fàn)顟B(tài)集合STS(S)={M1,M3,M8}ATS，因此服務(wù)組合S是可靠的。S0.PcaS1.PcaS2.PeS2.tfaS3.Pca4eS5.teS6.PeS6.PfaS2.PfaS4.PeS0.PeS1.PeS3.tcpS4.PcaS0.tcpS1.tcpS3.PcpP56S5.PePS.PP123P35P34P46PCtC圖7旅行服務(wù)的SCFP模型由于篇幅的限制，本文僅僅對(duì)imthanmaphon對(duì)這些協(xié)議進(jìn)行總結(jié)簡(jiǎn)化的旅行服務(wù)進(jìn)行模擬。然而它[10]，但這些協(xié)議是要緊是為Web足以講明服務(wù)組合的建模方法和和服務(wù)技術(shù)制定基于XML的標(biāo)準(zhǔn)，并諧策略的正確性。實(shí)例模擬過(guò)程可沒(méi)有考慮到服務(wù)消費(fèi)者的實(shí)際需知，應(yīng)用本文所提出方法能夠達(dá)到要，且不容易按照服務(wù)消費(fèi)者的需如下成效：（1）能夠清晰地描述任要來(lái)動(dòng)態(tài)調(diào)整。而使用形式化方法務(wù)及任務(wù)之間的關(guān)系。（2）正確刻對(duì)服務(wù)組合事務(wù)進(jìn)行分析也開(kāi)始有畫(huà)了服務(wù)的事務(wù)屬性，所構(gòu)造的模了一些研究成果和工作。在這些工型能夠確保服務(wù)組合的失效處理機(jī)作中，有基于進(jìn)程代數(shù)的[11-13]，制正確運(yùn)行。如服務(wù)S6運(yùn)行失敗，也有基于演算[14]的。Butler提出按照Petri網(wǎng)的運(yùn)行機(jī)制S模型會(huì)使用CCS與CSP結(jié)合的方法來(lái)描述到達(dá)終止?fàn)顟B(tài)M8或M15。（3）和Web事務(wù)[11]，它的優(yōu)點(diǎn)是對(duì)結(jié)構(gòu)化諧策略的有效性，按照和諧策略所活動(dòng)的復(fù)原機(jī)制進(jìn)行描述，然而它構(gòu)造的服務(wù)組合是可靠的。如圖7所采納的語(yǔ)法比較復(fù)雜，不利于對(duì)中的STS(S)={M1,M3,M8}，滿(mǎn)有關(guān)的特性進(jìn)行推導(dǎo)。Butler等對(duì)該足可靠服務(wù)組合的定義。因此，S方法進(jìn)行改進(jìn)[12]，并采納進(jìn)程代數(shù)是可靠的。（4）動(dòng)態(tài)調(diào)整可同意狀來(lái)描述相應(yīng)的語(yǔ)義，但它沒(méi)有考慮態(tài)集，以減少運(yùn)算量。若每次分配事務(wù)運(yùn)行的不同狀態(tài)，對(duì)模型的正可重復(fù)服務(wù)后可同意狀態(tài)集沒(méi)有進(jìn)確性驗(yàn)證還沒(méi)有具體論述。Hashemi行調(diào)整，則每次分配服務(wù)都要搜索an采納進(jìn)程代數(shù)的方法來(lái)描述無(wú)狀整個(gè)可同意狀態(tài)集。因此，關(guān)于大態(tài)的服務(wù)[13]，進(jìn)而描述服務(wù)組合的型服務(wù)組合，該方法能夠在較快的語(yǔ)義，通過(guò)使用圖的框架能夠表示時(shí)刻內(nèi)構(gòu)造可靠服務(wù)組合。服務(wù)組合的過(guò)程，然而它沒(méi)有考慮6有關(guān)工作服務(wù)的狀態(tài)，而實(shí)際中，服務(wù)的狀現(xiàn)在Web服務(wù)事務(wù)處理技術(shù)正態(tài)卻是服務(wù)消費(fèi)者比較關(guān)懷的結(jié)處于持續(xù)進(jìn)展之中，許多公司差不果。多推出處理Web服務(wù)事務(wù)的協(xié)議。L采納演算要緊是對(duì)服務(wù)協(xié)議Petri網(wǎng)的語(yǔ)義來(lái)描述Web服務(wù)，進(jìn)進(jìn)行研究，給出擴(kuò)展演算的形式而描述了服務(wù)之間的關(guān)系，其優(yōu)點(diǎn)化語(yǔ)義。廖軍等利用Pi-演算建立W是考慮了服務(wù)的QoS屬性，但它沒(méi)eb服務(wù)組合模型的規(guī)則[14]，并使用有考慮服務(wù)的動(dòng)態(tài)性且沒(méi)有對(duì)其有形式化工具分析所建立組合模型的關(guān)的性質(zhì)進(jìn)行驗(yàn)證。文獻(xiàn)[19]使用P正確性，然而它沒(méi)有分析服務(wù)消費(fèi)etri網(wǎng)的語(yǔ)義來(lái)描述Web服務(wù)的原者可同意狀態(tài)的多樣性，且演算子事務(wù)和聚合事務(wù)，進(jìn)而使用Petri對(duì)設(shè)計(jì)人員的數(shù)學(xué)功底要求較高，網(wǎng)的可達(dá)圖對(duì)有關(guān)算法進(jìn)行驗(yàn)證，不利于方法的擴(kuò)展。最近也顯現(xiàn)了它的優(yōu)點(diǎn)是分析了事務(wù)的一致性，一些采納事務(wù)模式的方法來(lái)分析服然而它沒(méi)有描述服務(wù)的補(bǔ)償和取消務(wù)的事務(wù)屬性[15,16]。Bhiri提出了等重要特性。事務(wù)模式的方法描述可靠服務(wù)組合7終止語(yǔ)[15]，但它沒(méi)有對(duì)模型進(jìn)行驗(yàn)證，而本文針對(duì)帶事務(wù)屬性的服務(wù)組且不易對(duì)所建立的模型進(jìn)行分析。M合，提出利用Petri網(wǎng)來(lái)構(gòu)造服務(wù)組ontagut提出一種事務(wù)需求的服務(wù)組合的工作流模型和SCFP模型，給出合方法，它考慮了服務(wù)的事務(wù)屬性?？煽糠?wù)組合的和諧策略及事實(shí)上然而該方法沒(méi)考慮服務(wù)的失敗處施。與現(xiàn)有方法相比，本文工作具理，且采納狀態(tài)圖描述服務(wù)的特性，有如下優(yōu)點(diǎn)：（1）使用形式化方法造成模型性質(zhì)分析的復(fù)雜性，使得（Petri網(wǎng)）來(lái)描述，Petri網(wǎng)有關(guān)的方法難以推廣。理論能夠準(zhǔn)確地刻畫(huà)服務(wù)運(yùn)行的不與本文相近的工作還有文獻(xiàn)[17同狀態(tài)，且能夠清晰地表達(dá)服務(wù)組-19]，它們均采納Petri網(wǎng)對(duì)服務(wù)組合的邏輯及服務(wù)之間的關(guān)系，利用合進(jìn)行形式化分析。文獻(xiàn)[17]提出使有關(guān)工具可對(duì)系統(tǒng)進(jìn)行模擬，使得用Petri網(wǎng)對(duì)服務(wù)的行為進(jìn)行分析，該方法易于推廣；（2）充分考慮了以便驗(yàn)證組合過(guò)程是否能得到預(yù)期服務(wù)的事務(wù)屬性和服務(wù)組合的失效的結(jié)果，然而，它在驗(yàn)證的過(guò)程中處理機(jī)制，保證服務(wù)失敗時(shí)可得到?jīng)]有考慮服務(wù)的事務(wù)特性，導(dǎo)致服相應(yīng)的處理；（3）提出了和諧策略，務(wù)失敗時(shí)，專(zhuān)門(mén)難對(duì)其語(yǔ)義比較準(zhǔn)該策略可減少可靠服務(wù)組合構(gòu)造的確的形式化分析。文獻(xiàn)[18]使用著色復(fù)雜度，并從理論上證明了該策略的有效性。同時(shí)給出了和諧策略的具體實(shí)施，為構(gòu)建大型復(fù)雜的服務(wù)組合系統(tǒng)奠定基礎(chǔ)。本文在服務(wù)的事務(wù)特性建模方面取得了進(jìn)展，但沒(méi)有考慮服務(wù)組合流程中的資源調(diào)度咨詢(xún)題，對(duì) SCFP模型的推理機(jī)制和工具也沒(méi)有涉及。另外，本文對(duì)可用服務(wù)的選擇沒(méi)有考慮服務(wù)的 QoS。我們將在這些方面進(jìn)一步探究。參 考 文 獻(xiàn)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網(wǎng)原理與應(yīng)用.北京:電子工業(yè)出版社,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服務(wù)組合的描述和驗(yàn)證.運(yùn)算機(jī)學(xué)報(bào),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)(唐飛龍,李明祿,黃哲學(xué),王卓立.服務(wù)網(wǎng)格中的事務(wù)服務(wù)及基于Petri網(wǎng)的正確性分析.運(yùn)算機(jī)學(xué)報(bào),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