具有失效恢復(fù)機制的云資源調(diào)度算法

齊 平，李龍澍，李學(xué)俊

（1.安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，安徽 合肥230039；2.銅陵學(xué)院 數(shù)學(xué)與計算機科學(xué)系，安徽 銅陵244000）

云計算（Cloud computing）是繼并行計算、分布式計算和網(wǎng)格計算后的新型計算模式［1］.云計算平臺利用虛擬化技術(shù)將多種計算資源（包括網(wǎng)絡(luò)、服務(wù)器、存儲、應(yīng)用和服務(wù)等）在云端進行整合，對資源進行統(tǒng)一管理和調(diào)度，使得這些資源可以根據(jù)負載的變化動態(tài)配置，以達到最優(yōu)的資源利用率.研究采用何種資源提供策略對這些大規(guī)模資源進行組織和管理，實現(xiàn)資源提供的高效靈活和按需分配，對云計算具有重要意義.

近些年，在云計算資源管理方面已有較多的研究.針對不同的計算任務(wù)和優(yōu)化目標，云資源調(diào)度算法可以分為以下幾類：1）以提高資源利用率和降低任務(wù)完成時間為目標［2-3］；2）以降低云計算中心能耗為目 標［4-6］；3）以 提 高 用 戶 服 務(wù) 質(zhì) 量（quality of service，QoS）為目標［7-8］；4）基于經(jīng)濟學(xué)的云資源管 理 模 型 研 究［9-10］；5） 多 目 標 優(yōu) 化 的 混 合算法［11-12］.

由于云環(huán)境中包含著大量分散、異構(gòu)資源，這些資源不僅地理位置分布廣泛，甚至屬于不同的自治系統(tǒng)，這些資源節(jié)點往往具有動態(tài)性、異構(gòu)性、開放性、自愿性、不確定性以及欺騙性等特征.云服務(wù)的可靠性是指用戶提交的服務(wù)被成功完成的概率，是從用戶的角度反映云完成用戶提交服務(wù)的執(zhí)行能力.在擁有無數(shù)資源節(jié)點的云環(huán)境中，節(jié)點的不可靠現(xiàn)象不可避免，因此，如何獲取可信的云資源，并將應(yīng)用任務(wù)分配到值得信任的資源節(jié)點上執(zhí)行成為云資源調(diào)度算法研究中急需解決的關(guān)鍵問題之一.

目前，在國內(nèi)外分布式系統(tǒng)資源管理的相關(guān)研究中，有關(guān)如何獲取可信資源的研究已經(jīng)取得了不少成 果.Dogan 等［13-14］提 出 了RDLS（reliable dynamic level scheduling）算法，研究如何在異構(gòu)分布式系統(tǒng)中獲取可信資源.在此基礎(chǔ)上，Dai等［15］提出了網(wǎng)格服務(wù)可靠性概念，采用最小檔案擴展樹對網(wǎng)格服務(wù)可靠性進行求解.Levitin［16］針對星型網(wǎng)格，提出了考慮服務(wù)可靠性和服務(wù)性能的信任評估算法.Foster等［17］將云服務(wù)和網(wǎng)格服務(wù)進行比較，給出云服務(wù)可靠性的評估方法.上述文獻采用不同的信任模型，從不同角度研究網(wǎng)格服務(wù)、云服務(wù)的可靠性，并給出了相應(yīng)的調(diào)度算法，有效地提高了任務(wù)執(zhí)行的成功率.

自從Blaze［18］首先提出了信任管理概念后，Josang［19-20］等引入證據(jù)空間（evidence space）概念，以描述二項事件后驗概率的Beta分布函數(shù)為基礎(chǔ)，將信任分為直接信任和推薦信任，根據(jù)節(jié)點間交互的肯定經(jīng)驗和否定經(jīng)驗計算出實體能夠完成任務(wù)的概率，并以此概率作為實體信任度的度量.基于證據(jù)的信任模型都是通過量化實體行為和計算實體信任度來評估實體間的相互信任關(guān)系.在上述研究中，所建立的信任評估模型并未考慮資源節(jié)點本身的行為特性.Wang［21-22］等在此基礎(chǔ)上，綜合考慮時間、權(quán)重等相關(guān)因素，利用貝葉斯算法構(gòu)造了一個基于節(jié)點行為的可信度評估模型，并將其引入網(wǎng)格服務(wù)、云服務(wù)的可靠性研究中，分別提出了Trust-DLS（dynamic level scheduling）和Cloud-DLS算法.

在Trust-DLS算法和Cloud-DLS算法中，對于網(wǎng)絡(luò)中的2個節(jié)點i和j，使用二項事件（交互成功／交互失敗）表示節(jié)點間的交互結(jié)果，而信任度被定義為節(jié)點i和j 發(fā)生n 次交互后，第n＋1次交互成功的概率估計.然而，在實際的云計算環(huán)境中，由于軟件、硬件以及系統(tǒng)過載等原因，失效問題在軟件系統(tǒng)執(zhí)行過程中不可避免，而失效恢復(fù)機制作為分布式系統(tǒng)可靠性研究的基礎(chǔ)問題，在分布式計算、網(wǎng)格計算的可靠性研究中已經(jīng)得到了廣泛的應(yīng)用［23-24］.

在失效恢復(fù)機制下，并不是所有失效都可以恢復(fù)，如軟件故障和部分通信鏈路故障就不可恢復(fù)［25］.如圖1所示，當網(wǎng)絡(luò)中的節(jié)點間交互結(jié)果為失敗時，按照物理故障（元件、鏈路失效）或軟件故障（設(shè)計、交互原因）的分類，可以將其劃分為可恢復(fù)失效和不可恢復(fù)失效.因此，在上述研究中，簡單使用二項事件來描述節(jié)點間的交互結(jié)果使得相應(yīng)的信任評估模型不太適用.

本文旨在構(gòu)造一種云環(huán)境下考慮失效恢復(fù)機制的信任評估模型，主要研究內(nèi)容包括：1）使用三項事件（交互成功／可恢復(fù)失效／不可恢復(fù)失效）描述節(jié)點的行為特性，建立相應(yīng)的信任評估模型；2）在建模和分析的過程中，評估失效恢復(fù)的執(zhí)行效率和相關(guān)參數(shù)對系統(tǒng)性能的影響；3）將考慮失效恢復(fù)機制的信任評估模型引入傳統(tǒng)的DLS算法中，提出考慮失效恢復(fù)機制的動態(tài)級調(diào)度算法.

1 考慮失效恢復(fù)機制的信任評估模型

考慮上文中所述失效恢復(fù)機制的影響，使用三項事件描述節(jié)點的行為特性，對傳統(tǒng)使用二項事件描述節(jié)點的行為特性的信任評估模型進行擴展，建立考慮失效恢復(fù)機制的信任評估模型.

在信任評估模型中，節(jié)點間信任關(guān)系分為3類.1）直接信任關(guān)系.如圖1（a）所示，節(jié)點i和節(jié)點j 之間存在可作為可信度評估依據(jù)的直接交互，即可以設(shè)法估算出直接交互成功的概率，稱為直接信任度評估，用θdt表示直接信任度.2）推薦信任關(guān)系.如圖1（b）所示，當節(jié)點i和節(jié)點j 之間不存在可作為可信度評估的直接交互，而節(jié)點i可以獲取其他節(jié)點（如：節(jié)點k）關(guān)于節(jié)點j 的可作為可信度評估依據(jù)的交互，這種需要通過第三方來建立的信任關(guān)系，稱為推薦信任度評估，用θrt表示推薦信任度.3）混合信任關(guān)系.當同時存在直接信任關(guān)系和推薦信任關(guān)系時，節(jié)點間的信任關(guān)系稱為混合信任關(guān)系，如圖1（c）所示，需要將上述2種信任關(guān)系進行合并，得到總體的信任評估.如同在人際關(guān)系網(wǎng)絡(luò)中，當個體之間進行信任評估時，往往既存在直接信任關(guān)系也存在推薦信任關(guān)系，不同的個體由于其個性、情緒等主觀因素不同，具有不同的量化判斷標準.本文選擇線性函數(shù)作為2種信任關(guān)系的合并函數(shù)：

式中：θ為合并信任度，λ 表示個體對2種信任關(guān)系的調(diào)節(jié)因子，當0＜λ＜0.5時，表示個體更信任推薦信任關(guān)系；而當λ＞0.5時，表示個體相信直接交互經(jīng)驗超過其他個體的推薦經(jīng)驗.

圖1 節(jié)點間的信任關(guān)系Fig.1 Trust relationship between nodes

1.1 時間因素

為體現(xiàn)信任評估的動態(tài)性，考慮時間因素對信任評估的影響.由人類對歷史信息的認知方法可知，不同時期的歷史交互信息對信任評估過程產(chǎn)生的影響是不同的，越接近的歷史交互信息產(chǎn)生的影響越大，而時間跨度越長的歷史交互信息產(chǎn)生的影響越小，直至對評估失去意義而不對其進行考慮.

采用時間分段概念［26］將時間段設(shè)置為1d，并引入時間影響力衰減因子η刻畫不同時期歷史交互信息的重要程度.設(shè)2個云資源節(jié)點i和節(jié)點j，使用三項事件（不可恢復(fù)失效／可恢復(fù)失效／交互成功）描述節(jié)點i和節(jié)點j 之間的交互結(jié)果.當節(jié)點i和節(jié)點j之間發(fā)生n 次交互時，設(shè)其中不可恢復(fù)失效的次數(shù)為α，可恢復(fù)失效的次數(shù)為β，交互成功的次數(shù)為γ.因此，將其劃分為m 個時間段后，設(shè)其中第i個時間段的不可恢復(fù)失效、可恢復(fù)失效和交互成功次數(shù)分別為αi、βi 和γi，則考慮時間衰減因子η后的第i個時間段的不可恢復(fù)失效α（i）、可恢復(fù)失效β（i）和交互成功次數(shù)γ（i）如下式所示：

式中：0≤η≤1，η＝0表示只考慮最近一次的歷史交互影響；而η＝1表示不考慮時間影響力衰減因子.

1.2 直接信任關(guān)系

直接信任是節(jié)點根據(jù)歷史交互經(jīng)驗，對目標節(jié)點未來行為的主觀期望，在這里運用貝葉斯算法估計直接信任度.

根據(jù)經(jīng)驗分析［27］，由不可恢復(fù)失效產(chǎn)生的因素可知，在一個時間段內(nèi)不可恢復(fù)失效的概率可以認為是不變的.因此，設(shè)第i個時間段的不可恢復(fù)失效概率q0為常數(shù)：

同時，設(shè)第i個時間段內(nèi)可恢復(fù)失效概率為qi，則第i個時間段的成功交互概率可以表示為

對于m 個時間段，設(shè)θ＝（θ1，…，θm）為隨機變量，其驗前分布為均勻分布，則其聯(lián)合概率密度函數(shù)為

式中：Gm為m 維歐氏空間中的點集，Vm為Gm的勒貝格測度.為求得θm的貝葉斯估計，必須先求出｛θ1，…，θm｝的驗后聯(lián)合概率密度以及關(guān)于θm的驗后邊緣概率密度.

設(shè)樣本集X＝｛X11，X12，X13；X21，X22，X23；…；Xm1，Xm2，Xm3｝，p＝1，2，…，m.其中Xp1表示時間段p 中不可恢復(fù)失效次數(shù)，Xp2表示時間段p中可恢復(fù)失效次數(shù)，Xp3表示時間段p 中成功交互次數(shù).設(shè)x0為樣本集X 的一個觀察，且

設(shè)f（θ｜x0）為隨機變量θ 的驗后聯(lián)合概率密度，p（θm｜x0）為θm的驗后邊緣概率密度，為θm的貝葉斯估計.

根據(jù)貝葉斯公式及式（5）得到驗后聯(lián)合概率密度為

根據(jù)上述討論內(nèi)容可知，P｛X ＝x0｜θ｝為

將式（7）代入式（6）可得

為計算式（8），引入恒等式：

式中：u和v 為正整數(shù)，B（u，v）為參數(shù)是u、v 的Beta函數(shù)，x 為自變量，0≤a＜1.設(shè)n（i）＝β（i）＋γ（i），i＝1，2，…，m，可得

綜上可得θ＝｛θ1，…，θm｝的驗后聯(lián)合概率密度f（θ｜x0）為

θm的驗后邊緣概率密度p（θm｜x0）為

若不對不可恢復(fù)失效和可恢復(fù)失效進行區(qū)分，即把這2種失效都作為交互失敗來處理，在這種情況下上面所得結(jié)果式（16）驗后聯(lián)合概率密度，式（17）驗后邊緣概率密度和式（18）貝葉斯估計就與伯努利概率模型中的結(jié)果完全吻合.

由式（18）可以看出，直接信任關(guān)系的評估與節(jié)點間的交互次數(shù)有關(guān).雖然通過式（18）可以得到節(jié)點間的直接信任度，但是當節(jié)點間沒有交互或者交互較少時，較少的樣本數(shù)將不足以評估節(jié)點間的直接信任關(guān)系.

針對該問題，本文使用區(qū)間估計理論［28］對信任度的置信水平進行度量，設(shè)（θdt-δ，θdt＋δ）為直接信任度θdt的置信度為γ 的置信區(qū)間，δ 為可接受誤差，則θdt的置信度為

由于區(qū)間估計的置信度與區(qū)間估計精度相互制約，因此，選定置信度閾值為γ0，通過增加總的交互次數(shù)n提高精度，直到達到可接受水平，即當γ≥γ0時，可以根據(jù)這時的直接交互信息進行信任度計算.此時的樣本容量n0、可接受誤差δ和置信度閾值γ0之間的關(guān)系如下：

通過上述分析可知，根據(jù)節(jié)點間直接交互樣本的置信度值，可以將直接信任關(guān)系評估作如下設(shè)定：1）當節(jié)點間不存在直接交互或交互樣本置信度值γ＜γ0時，先驗分布選擇無信息先驗分布U（0，1），設(shè)定節(jié)點間的直接信任度θdt＝1／2；2）當交互樣本置信度值γ≥γ0時，節(jié)點間的直接信任度θdt按照式（18）計算.

1.3 推薦信任關(guān)系

推薦信任關(guān)系由2 類或多類直接交互關(guān)系形成，由于推薦信任關(guān)系涉及多方實體的直接交互關(guān)系，對推薦信任關(guān)系的評估仍按照上文所述方法，但須考慮多個直接交互信息［29］.

設(shè)網(wǎng)絡(luò)中節(jié)點i和節(jié)點k、節(jié)點j和節(jié)點k 之間的交互獨立，交互次數(shù)分別為n1、n2，其中不可恢復(fù)失效次數(shù)分別為α1、α2，可恢復(fù)失效分別為β1、β2，交互成功次數(shù)分別為γ1、γ2.設(shè)第i個時間段的不可恢復(fù)失效、可恢復(fù)失效和交互成功次數(shù)分別為α1i、β1i、γ1i和α2i、β2i、γ2i，因而考慮時間衰減因子η 后的第i個時間段的不可恢復(fù)失效、可恢復(fù)失效和交互成功次數(shù)可以設(shè)為α（i）1、β（i）1、γ（i）1和α（i）2、β（i）2、γ（i）2.

設(shè)樣本集的一個觀察

取損失函數(shù)為二次損失函數(shù)，則為θ′m的貝葉斯估計，為節(jié)點i和節(jié)點j 之間的推薦信任度，即為上文中所述的θrt，滿足下式：

節(jié)點可以通過搜索整個網(wǎng)絡(luò)中的其他節(jié)點和目標節(jié)點的交互歷史獲得推薦信任度，然而也存在以下問題：1）當推薦交互關(guān)系的樣本數(shù)較少時，無法使用式（26）對推薦信任關(guān)系進行評估；2）當推薦節(jié)點k不止一個時，搜索過多的推薦交互會增加整個網(wǎng)絡(luò)的通信開銷.對于上述問題，本文通過推薦交互關(guān)系的樣本置信度進行設(shè)定：當推薦交互樣本置信度值γ＜γ0時，設(shè)定推薦信任度θrt＝1／2，而當γ≥γ0時，即可停止搜索推薦節(jié)點，并通過累計不可恢復(fù)失效、可恢復(fù)失效和成功交互數(shù)推廣式（26）計算推薦信任度θrt.

2 考慮失效恢復(fù)機制的動態(tài)級調(diào)度算法

根據(jù)第1章中討論的考慮失效恢復(fù)機制的信任模型，對傳統(tǒng)的DLS算法［30］進行擴展，針對基于有向無環(huán)圖（directed acyclic graph，DAG）的云資源調(diào)度問題，將考慮失效恢復(fù)機制的信任評估模型引入傳統(tǒng)的DLS算法中，提出考慮失效恢復(fù)機制的動態(tài)級調(diào)度算法.

DLS算法為靜態(tài)啟發(fā)式的表調(diào)度算法，其原理是：對于任務(wù)vi和資源mj，通過貪心方法查找具有最高動態(tài)級的任務(wù)-資源對，從而將基于DAG 的應(yīng)用任務(wù)分配到異構(gòu)的資源節(jié)點（如：云資源節(jié)點）上執(zhí)行.其中任務(wù)-資源（vi-mj）對的動態(tài)級D（vi，mj）定義如下：

式中：S（vi）為任務(wù)靜態(tài)級，在一個調(diào)度期間內(nèi)為常數(shù)，指DAG 中從任務(wù)vi到終止節(jié)點的最大執(zhí)行時間；Max｛tAi，j，tMj｝為資源mj的輸入數(shù)據(jù)時間與應(yīng)用任務(wù)vi的執(zhí)行時間之間的較大者；Δ（vi，mj）表示資源mj的相對計算性能.

當任務(wù)調(diào)度到資源節(jié)點上執(zhí)行時，可信度反映目標資源節(jié)點提供服務(wù)的可靠程度.DLS算法充分考慮了資源節(jié)點的異構(gòu)特征，然而并未考慮云資源節(jié)點可信度對調(diào)度結(jié)果的影響.為解決該問題，Wang等［22-23］考慮節(jié)點間行為特性和歷史交互信息，提出了可信動態(tài)級調(diào)度算法（Cloud-DLS算法），并應(yīng)用到網(wǎng)格服務(wù)和云服務(wù)中，其動態(tài)級定義如下：

式中：R（vi，nj）表示云資源節(jié)點調(diào)度任務(wù)vi到云資源節(jié)點nj上時對nj可信度的評估.

然而，該算法并未考慮云環(huán)境下的失效恢復(fù)機制.在實際的云環(huán)境中，當某一云資源節(jié)點發(fā)生失效時，往往會導(dǎo)致整個任務(wù)的失敗.引入失效恢復(fù)機制后，對于可恢復(fù)失效（如：網(wǎng)絡(luò)瞬間堵塞、CPU 短時衰竭等失效問題），云資源節(jié)點可以通過運行失效恢復(fù)程序?qū)σ阎兄沟娜蝿?wù)進行恢復(fù).節(jié)點執(zhí)行子任務(wù)的過程被分為執(zhí)行過程和恢復(fù)過程2 個部分.如圖2所示，當子任務(wù)i在節(jié)點k 上執(zhí)行時，第1次失效發(fā)生在t1時刻，在t2時刻該失效被恢復(fù)；第2次失效發(fā)生在t3時刻而在t4時刻被恢復(fù)，以此類推直至該任務(wù)執(zhí)行完成或者由于失效不可恢復(fù)而終止.

對于網(wǎng)絡(luò)中的節(jié)點k，失效恢復(fù)機制的相關(guān)參數(shù)如下：

1）失效恢復(fù)率xk.失效恢復(fù)具有一定的概率，為了描述失效的可恢復(fù)能力，定義隨機變量：當節(jié)點k上第j 個失效可以恢復(fù)時，設(shè)＝0；當節(jié)點k上第j 個失效不可恢復(fù)時，設(shè)＝1.

圖2 失效恢復(fù)機制下子任務(wù)i在節(jié)點k 上的執(zhí)行過程Fig.2 Execution process with fault recovery mechanism

假定節(jié)點k的失效恢復(fù)率恒為xk，則對于任意第j次恢復(fù)過程，都有P｛X（j）k＝0｝＝xk，P｛X（j）k＝1｝＝1-xk.同時，失效恢復(fù)率xk越高，每一次失效恢復(fù)過程所需的時間也越長，即較高的失效恢復(fù)率會提高系統(tǒng)的時間花費.

2）最大失效恢復(fù)次數(shù)Nk（Nk≥1）.由于失效恢復(fù)程序的執(zhí)行會給資源節(jié)點帶來較大的服務(wù)開銷，在以下3類情況下，資源節(jié)點k 上執(zhí)行的任務(wù)將被終止，即任務(wù)完成、發(fā)生不可恢復(fù)失效或是超過最大失效恢復(fù)次數(shù)Nk.

本文引入失效恢復(fù)機制，提出云環(huán)境下考慮失效恢復(fù)機制的動態(tài)級調(diào)度算法（FR-DLS），對于任務(wù)vi和云資源節(jié)點nj，其可信動態(tài)級FR-DL（vi，mj）定義如下：

式中：TS（vi，nj，xk，Nk）表示在考慮失效恢復(fù)機制參數(shù)的情況下，云資源節(jié)點ns調(diào)度任務(wù)vi到云資源節(jié)點nj上時對nj可信度的評估，即式（1）中討論的合并信任度θ.

3 仿真實驗及結(jié)果分析

為驗證所提出的信任評估模型和動態(tài)級調(diào)度算法，在PlanetLab 環(huán)境［31］中設(shè)計基于云仿真軟件CloudSim［32］的實驗平臺.分布全球的計算機群項目PlanetLab始于2003 年，由普林斯頓大學(xué)、華盛頓大學(xué)、加州大學(xué)和Intel研究人員共同開發(fā)，其目標是提供一個用于開發(fā)下一代互聯(lián)網(wǎng)技術(shù)的開放式全球性測試實驗平臺.云仿真軟件CloudSim 是一個通用、可擴展的新型仿真框架，通過在離散事件模擬包SimJava上開發(fā)的函數(shù)庫支持基于數(shù)據(jù)中心的虛擬化建模、仿真功能和云資源管理、云資源調(diào)度模擬.同時，CloudSim 為用戶提供了一系列可擴展的實體和方法，用戶根據(jù)自身的要求調(diào)用適當?shù)腁PI實現(xiàn)自定義的調(diào)度算法.

本文所有的仿真試驗中，每組實驗分為10次，最終結(jié)果采用平均值.相關(guān)實驗參數(shù)設(shè)置如下：在PlanetLab的網(wǎng)絡(luò)模擬實驗環(huán)境中，節(jié)點數(shù)和節(jié)點之間的鏈路數(shù)預(yù)先給定，鏈路間的數(shù)據(jù)傳輸速度介于1～10 Mbit／s；由于算法的性能與應(yīng)用任務(wù)的大小和通信／計算比rCC（communication to computation ratio）［32］有關(guān)，任務(wù)類型按照通信／計算比給出，rCC＞1表示該任務(wù)為通信密集型，而0＜rCC＜1則表示該任務(wù)為計算密集型.同時，設(shè)定用戶任務(wù)在資源節(jié)點上的執(zhí)行時間介于10～100s.其他實驗參數(shù)設(shè)置如 下：λ＝0.8，η＝0.8［22-23］，δ＝0.1，γ0＝0.95.同時設(shè)置2 類惡意節(jié)點，分別占節(jié)點總數(shù)的20%和30%，在分配到任務(wù)時，2類惡意節(jié)點分別以80%和50%的概率執(zhí)行任務(wù)失敗.

3.1 失效恢復(fù)機制

在以下實驗中，討論失效恢復(fù)機制及其參數(shù)對信任評估的影響，并在不同任務(wù)數(shù)和不同節(jié)點數(shù)的情況下，比較DLS 算法、Cloud-DLS算法和本文所提出的FR-DLS算法的性能.

為考察失效恢復(fù)機制的有效性，對于不同類型的用戶任務(wù)（rCC分別取0.1、1.0、10.0），討論失效恢復(fù)率xk、最大失效恢復(fù)次數(shù)Nk對任務(wù)執(zhí)行成功率ra（average ratio of successful execution）和任務(wù)完成時間ta（average completion time）的影響.實驗環(huán)境參數(shù)設(shè)置如下：云資源節(jié)點數(shù)為200，鏈路數(shù)為200，任務(wù)數(shù)為50.

3.1.1 失效恢復(fù)率xk對于rCC分別取0.1、1.0、10.0的不同類型任務(wù)，討論在不考慮最大失效恢復(fù)次數(shù)Nk的情況下，失效恢復(fù)率xk對任務(wù)執(zhí)行成功率的影響.實驗結(jié)果如圖3 所示，當失效恢復(fù)率xk＝0時，表示未使用失效恢復(fù)機制，任務(wù)執(zhí)行成功率相對較低.隨著失效恢復(fù)率xk的增加，3 種類型任務(wù)的執(zhí)行成功率都相應(yīng)提高；而當失效恢復(fù)率xk＝1時，任務(wù)執(zhí)行成功率相對較高，充分體現(xiàn)了失效恢復(fù)機制的有效性.

當失效恢復(fù)率xk＝1時，任務(wù)執(zhí)行成功率并未達到100%.這是由于在不設(shè)置最大失效恢復(fù)次數(shù)的情況下，雖然可恢復(fù)失效可以通過恢復(fù)程序的不斷執(zhí)行得以恢復(fù)，使得任務(wù)執(zhí)行完成，但如通信鏈路故障、軟件故障等不可恢復(fù)失效并不能夠被失效恢復(fù)機制所恢復(fù).

討論在設(shè)置最大失效恢復(fù)次數(shù)Nk＝3時，失效恢復(fù)率xk對任務(wù)執(zhí)行成功率的影響，實驗結(jié)果如圖4所示.由圖可見，隨著失效恢復(fù)率xk的增加，3種類型任務(wù)的執(zhí)行成功率增長速率較不限制最大失效恢復(fù)次數(shù)時緩慢.此外，rCC＝10.0時的任務(wù)執(zhí)行成功率明顯低于rCC＝0.1時，這是由于通信密集型任務(wù)有著較高的失效率，因此對于不同類型的任務(wù)，選取合適的失效恢復(fù)率十分重要.

圖3 不同失效恢復(fù)率下平均任務(wù)執(zhí)行成功率的比較（Nk 無約束）Fig.3 Comparison of average success rates of task execution under varying recoverability probability（Nk without constraint）

圖4 不同失效恢復(fù)率下平均任務(wù)執(zhí)行成功率的比較（Nk＝3）Fig.4 Comparison of average success rates of task execution under varying recoverability probability（Nk＝3）

圖5 不同失效恢復(fù)率下平均任務(wù)完成時間的比較（Nk＝3）Fig.5 Comparison of average task completion time under varying recoverability probability（Nk＝3）

失效、恢復(fù)過程會給節(jié)點帶來較大的服務(wù)開銷，而提高失效恢復(fù)率也會使恢復(fù)過程所需的時間增加.為研究失效恢復(fù)率xk對任務(wù)完成時間的影響，比較隨著xk逐步增長，不同類型任務(wù)的完成時間，設(shè)置最大失效恢復(fù)次數(shù)Nk＝3，實驗結(jié)果如圖5所示.當0＜xk＜0.6時，任務(wù)完成時間的增長速率較緩；而當xk＞0.6時，任務(wù)完成時間的增長速率相對較快；當xk＝1.0時，3種類型任務(wù)的完成時間急劇增長.可見，選擇較高的失效恢復(fù)率在提高任務(wù)執(zhí)行成功率的同時，也帶來了較大的時間花費.

3.1.2 最大失效恢復(fù)次數(shù)Nk如前文所述，每一次失效、恢復(fù)都會給節(jié)點帶來較大的服務(wù)開銷.在某些情況下（見圖2），失效恢復(fù)過程被不斷執(zhí)行多次，直至任務(wù)完成.這對系統(tǒng)的可用性有較大影響，因此有必要限定節(jié)點的失效恢復(fù)次數(shù).本實驗對于rCC分別為0.1、1.0和10.0的不同類型任務(wù)，考察最大失效恢復(fù)次數(shù)Nk對任務(wù)執(zhí)行成功率和任務(wù)完成時間的影響，在以下實驗中，失效恢復(fù)率xk設(shè)置為0.6.如圖6所示，隨著最大失效恢復(fù)次數(shù)Nk的增加，3種類型任務(wù)的執(zhí)行成功率都有不同程度的提高.當Nk≤4時，執(zhí)行成功率增長的較快；而當5≤Nk≤10時，執(zhí)行成功率增長較緩，這說明大部分可恢復(fù)失效可以在最多執(zhí)行4 次失效恢復(fù)過程后恢復(fù).

圖6 不同失效恢復(fù)次數(shù)下平均任務(wù)執(zhí)行成功率的比較（xk＝0.6）Fig.6 Comparison of average success rates of task execution under varying number of recoverable failures（xk＝0.6）

如圖7所示為隨著最大失效恢復(fù)次數(shù)Nk的增加，rCC分別為0.1、1.0和10.0的不同類型任務(wù)的任務(wù)完成時間.由圖可見，隨著最大失效恢復(fù)次數(shù)Nk的增加，3種類型任務(wù)的完成時間都有不同程度的提高.當Nk≤5時，任務(wù)完成時間的增長速率較快；而當Nk趨向于10 時，任務(wù)完成時間的增長趨向平緩.該實驗從另一方面證實了大部分可恢復(fù)失效可以在執(zhí)行4～5次失效恢復(fù)過程后被恢復(fù).

圖7 不同失效恢復(fù)次數(shù)下平均任務(wù)完成時間的比較（xk＝0.6）Fig.7 Comparison of average task completion time under varying number of recoverable failures（xk＝0.6）

由上述實驗結(jié)果可見，失效恢復(fù)機制可以顯著地提高任務(wù)執(zhí)行成功率，充分體現(xiàn)了失效恢復(fù)機制的有效性.與此同時，失效恢復(fù)機制也給系統(tǒng)帶來了一定的服務(wù)開銷和時間花費，因此，對于不同類型的任務(wù)，應(yīng)當按照需要選擇合適的失效恢復(fù)率和最大失效恢復(fù)次數(shù).

3.2 不同任務(wù)數(shù)情況下的比較

本實驗在網(wǎng)絡(luò)中具有不同任務(wù)數(shù)的情況下，比較FR-DLS算法、Cloud-DLS算法和傳統(tǒng)的DLS算法在任務(wù)執(zhí)行成功率、平均調(diào)度長度la（average schedule length）和任務(wù)完成時間方面的性能.其中，xk和Nk分別被設(shè)置為0.6和3.實驗環(huán)境參數(shù)設(shè)置如下：設(shè)定rCC＝1.0，云資源節(jié)點數(shù)為200，鏈路數(shù)為200，并隨機產(chǎn)生擁有10～100個子任務(wù)數(shù)nt（number of tasks）的任務(wù)圖.

圖8 不同任務(wù)數(shù)下DLS、Cloud-DLS和FR-DLS的平均任務(wù)執(zhí)行成功率比較Fig.8 Comparison of average success rates of task execution of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of tasks

圖9 不同任務(wù)數(shù)下DLS、Cloud-DLS和FR-DLS的平均調(diào)度長度比較Fig.9 Comparison of average schedule lengths of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of tasks

圖10 不同任務(wù)數(shù)下DLS、Cloud-DLS和FR-DLS的平均任務(wù)完成時間比較Fig.10 Comparison of average task completion time of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of tasks

實驗結(jié)果如圖8～10所示，由圖可見，隨著任務(wù)數(shù)的增加，3種算法的任務(wù)執(zhí)行成功率都略有降低，而調(diào)度長度和任務(wù)完成時間則有不同程度的提高.其中，F(xiàn)R-DLS算法的調(diào)度長度和任務(wù)完成時間略高于Cloud-DLS 算法和DLS 算法.由圖8 可以看出，F(xiàn)R-DLS算法的執(zhí)行成功率遠高于Cloud-DLS算法和DLS算法.結(jié)果表明：失效恢復(fù)機制在較小的服務(wù)開銷和時間花費下可以有效地提高任務(wù)執(zhí)行成功率.

3.3 不同節(jié)點數(shù)情況下的比較

本實驗在網(wǎng)絡(luò)中具有不同節(jié)點數(shù)的情況下，比較FR-DLS算法、Cloud-DLS算法和傳統(tǒng)的DLS算法在任務(wù)執(zhí)行成功率、調(diào)度長度和任務(wù)完成時間方面的性能.實驗環(huán)境參數(shù)設(shè)置如下：設(shè)定rCC＝1，鏈路數(shù)為200，任務(wù)數(shù)為100，并隨機產(chǎn)生擁有100～1 000個節(jié)點數(shù)nr（number of resource nodes）的隨機網(wǎng)絡(luò).

實驗結(jié)果如圖11～13所示，由圖可見，在不同節(jié)點數(shù)的情況下，可以得到與不同任務(wù)數(shù)時相類似的結(jié)論：在犧牲一定完成時間和調(diào)度長度的代價下，失效恢復(fù)機制可以顯著地提高任務(wù)執(zhí)行成功率，體現(xiàn)了該機制的有效性.

在不同任務(wù)數(shù)和不同節(jié)點數(shù)情況下，如表1所示為FR-DLS算法相對于Cloud-DLS算法和DLS算法在調(diào)度長度、任務(wù)執(zhí)行時間和任務(wù)執(zhí)行成功率方面的改善情況.

通過表1可以看出：1）任務(wù)調(diào)度在調(diào)度長度、執(zhí)行時間和執(zhí)行成功率方面存在權(quán)衡，無法達到多方面服務(wù)質(zhì)量的同時提高，而是以某一部分服務(wù)質(zhì)量為代價換取另一部分更高的服務(wù)需求；2）本文所提出FR-DLS算法的性能與云計算環(huán)境下的節(jié)點數(shù)、任務(wù)數(shù)和任務(wù)類型（rCC的取值）有關(guān).其中，隨著云環(huán)境中節(jié)點數(shù)增加，F(xiàn)R-DLS算法在可靠性方面提升的性能遠高于其在任務(wù)完成時間和調(diào)度長度代價方面的所提升的性能，顯示了FR-DLS算法在云計算環(huán)境下對于大規(guī)模任務(wù)的實用性.

圖11 不同節(jié)點數(shù)下DLS、Cloud-DLS和FR-DLS的平均任務(wù)執(zhí)行成功率比較Fig.11 Comparison of average success rates of task execution of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of resource nodes

表1 FR-DLS算法相對Cloud-DLS算法和DLS算法在調(diào)度長度、任務(wù)執(zhí)行時間和任務(wù)執(zhí)行成功率方面的增加情況（不同任務(wù)數(shù)和不同節(jié)點數(shù)）Tab.1 Comparison of Cloud-DLS algorithm and DLS algorithm in scheduling lengths，completion time and success rates of task execution with FR-DLS algorithm（varying numbers of tasks and resource nodes）%

圖12 不同節(jié)點數(shù)下DLS、Cloud-DLS和FR-DLS的平均調(diào)度長度比較Fig.12 Comparison of average schedule lengths of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of resource nodes

圖13 不同節(jié)點數(shù)下DLS、Cloud-DLS和FR-DLS的平均任務(wù)完成時間比較Fig.13 Comparison of average task completion time of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of resource nodes

4 結(jié) 語

本文將節(jié)點失效可恢復(fù)的情況引入到云服務(wù)可靠性分析中，在此基礎(chǔ)上將原有的以二項事件（成功／失敗）描述節(jié)點間交互結(jié)果的信任模型擴展為以三項事件（成功／可恢復(fù)失效／不可恢復(fù)失效）描述交互結(jié)果的信任評估模型，并提出了考慮失效恢復(fù)機制的可信動態(tài)級調(diào)度算法.仿真實驗證實該算法能夠為云環(huán)境中主體節(jié)點的信任決策提供有效的支持，有效地提高云服務(wù)的可靠性.同時，該算法允許資源所有者自行調(diào)節(jié)資源失效恢復(fù)次數(shù)限制和失效恢復(fù)率，從而增加了失效恢復(fù)機制的靈活性.

本文的進一步工作是將考慮云計算環(huán)境中的相關(guān)安全機制與時間花費、價格花費等服務(wù)質(zhì)量因素相結(jié)合，同時將如鏈路故障、節(jié)點故障和云節(jié)點本身安全軟件的部署等安全因素相結(jié)合，提出相應(yīng)的任務(wù)調(diào)度算法，從不同角度滿足用戶對云服務(wù)可靠性、服務(wù)質(zhì)量和服務(wù)花費的多方面要求.

（

）：

［1］BUYYA R，YEO C S.VENUGOPAL S，et al.Cloud computing and emerging IT platforms：vision，hype，and reality for delivering computing as the 5th utility［J］.Future Generation Computer Systems，2009，25（6）：599-616.

［2］DARBHA S，AGRAWAL D P.Optimal scheduling algorithm for distributed memory machines ［J］.IEEE Transactions on Parallel and Distributed Systems，2002，9（1）：87-95.

［3］LEE Y C，ZOMAYA A Y.A novel state transition method for metaheuristic-based scheduling in heterogeneous computing systems［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19（9）：1215-1223.

［4］ZHU D，MOSSE D，MELHEM R.Power-aware scheduling for and／or graphs in real-time systems［J］.IEEE Transactions on Parallel and Distributed Systems，2004，15（9）：849-864.

［5］KIM K H，BUYYA R，KIM J.Power aware scheduling of bag-of-tasks applications with deadline constraints on DVS-enabled clusters ［C］∥Proceedings of the 7th IEEE International Symposium on Cluster Computing and the Grid.Rio de janeiro：IEEE，2007：541-548.

［6］BUNDE D P.Power-aware scheduling for makespan and flow［J］.Journal of Scheduling，2009，12（5）：489-500.

［7］李茂勝，楊壽保，付前飛，等.基于賠償?shù)木W(wǎng)格資源交易模型［J］.軟件學(xué)報，2006，17（3）：472-480.LI Mao-sheng，YANG Shou-bao，F(xiàn)U Qian-fei，et al.A grid resource transaction model based on compensation［J］.Journal of Software，2006，17（3）：472-480.

［8］XU B M，ZHAO C Y，HU E Z，et al.Job scheduling algorithm based on Berger model in cloud environment［J］.Advances in Engineering Software，2011，42（3）：419-425.

［9］BUYYA R，MURSHED M M，ABRAMSON D，et al.Scheduling parameter sweep applications on global grids：a deadline and budget constrained cost-time optimization algorithm ［J］.Software Practice and Experi-ence，2005，35（5）：491-512.

［10］BLANCO C V，HUEDO E，MONTERO R S，et al.Dynamic provision of computing resources from grid infrastructures and cloud providers［C］∥Grid and Pervasive Computing Conference，Geneva：IEEE，2009：113-120.

［11］TOPCUOGLU H，HARIRI S，WU M Y.Performance-effective and low complexity task scheduling for heterogeneous computing ［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（3）：260-274.

［12］MEZMAZ M，MELAB N，KESSACI Y，et al.A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems［J］.Journal of Parallel and Distributed Computing，2011，71（10）：1497-1508.

［13］DOGAN A，OZGUNER，F(xiàn).Reliable matching and scheduling of precedence constrained tasks in heterogeneous distributed computing［C］∥Proceedings of the 29th international conference on parallel processing，Toronto：IEEE，2000：307-314.

［14］DOGAN A，OZGUNER，F(xiàn).Matching and scheduling algorithms for minimizing execution time and failure probability of applications in heterogeneous computing［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（3）：308-323.

［15］DAI Y S，XIE M.Reliability of grid service systems［J］.Computers and Industrial Engineering，2006，50（1／2）：130-147.

［16］LEVITIN G，DAI Y S.Service reliability and performance in grid system with star topology［J］.Reliability Engineering and System Safety，2007，92（1）：40-46.

［17］FOSTER I，ZHAO Y，RAICU I，et al.Cloud Computing and Grid Computing 360-Degree Compared［M］.Texa：IEEE Grid Computing Environments，2008：1014-1017.

［18］BLAZE M.Toward a broader view of security protocols［C］∥12th Cambridge International Workshop on Security Protocols，Cambridge：IEEE，2004：1014-1017.

［19］JOSANG A，OZGUNER F.Matching and scheduling of minimizing execution time and failure probability of applications in heterogeneous computing ［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（3）：308-323.

［20］JOSANG A.A logic for uncertain probabilities［J］.International Journal of Uncertainty，F(xiàn)uzziness and Knowledge-Based Systems，2001，9（3）：279-311.

［21］WANG W，ZENG G S，YUAN L L.A reputation multi-agent system in semantic web［C］∥Proceedings of the 9th Pacific Rim International Workshop on Multi-Agents.Guilin：PRIMA，2006：211-219.

［22］WANG W，ZENG G S，TANG D Z，et al.Cloud-DLS：dynamic trusted scheduling for cloud computing［J］.Expert Systems with Applications，2012，39（5）：2321-2329.

［23］DAI Y S，WANG X L.Optimal resource allocation on grid systems for maximizing service reliability using a genetic algorithm［J］.Reliability Engineering and System Safety，2006，91（9）：1071-1082.

［24］TREASTER M.A survey of fault-tolerance and faultrecovery techniques in parallel systems ［R］.ACM Computing Research Repository（CoRR），2005：1-11.

［25］ABAWAJY J H.Fault-tolerant scheduling policy for grid computing systems［C］∥Proceedings of the 19th IEEE International conference on Parallel and Distributed Processing Symposium，New York：IEEE，2004：50-58.

［26］JOSANG A，ISMAIL R.The beta reputation system［C］∥Proceedings of the 15th Bled Conference on Electronic Commerce，Slovenia：Bled EC，2002：2502-2511.

［27］GUO S C，HUANG H Z，LIU Y.Modeling and analysis of grid service reliability considering fault recovery［J］.New Generation Computing，2011，29（4）：345-364.

［28］THOMAS L，JOHN S J.Bayesian methods：an analysis of statisticians and interdisciplinary ［M］.New York：Cambridge University Press，1999：341-355.

［29］SULISTIO A，CIBEJ U，VENUGOPAL S，et al.A tutorial for modeling and simulating data grids：an extension to Gridsim ［J］.Concurrency and Computation：Practice and Experience，2008，20（13）：1591-1609.

［30］ZHU M，GUO W，XIAO S L，et al.Availability-driven scheduling for real-time directed acyclic graph applications in optical grid［J］.Journal of Optical Communications and Networking，2010，2（7）：469-480.

［31］PETERSON L，BAVIER A，F(xiàn)IUCZYNSK M，et al.Towards a comprehensive PlanetLab architecture technical report PDN-05-030［R］.Sydney：PlanetLab Consortium，2005.

［32］CALHEIROS R N，RANJAN R，ROSE D，et al.CloudSim：a novel framework for modeling and simulation of cloud computing infrastructures and services［R］.Melbourne：Grid Computing and Distributed Systems Laboratory，the University of Melbourne，2009.