齊 平,王福成,王必晴

1(銅陵學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系,安徽 銅陵 244000) 2(合肥工業(yè)大學(xué) 管理學(xué)院,合肥 230039) E-mail:qiping929@gmail.com

1 引 言

云計(jì)算以網(wǎng)絡(luò)化的方式聚合計(jì)算與通信資源,同時(shí)使用虛擬化技術(shù)將大量成本較低、計(jì)算能力較弱的計(jì)算實(shí)例整合為一個(gè)具有強(qiáng)大計(jì)算能力的資源共享池,為用戶提供可以縮減或擴(kuò)展規(guī)模的計(jì)算資源[1,2].由于云計(jì)算系統(tǒng)資源由廣域分布的異構(gòu)資源構(gòu)成,且各類資源動(dòng)態(tài)加入和退出云系統(tǒng)具有隨機(jī)性,因此如何實(shí)現(xiàn)計(jì)算資源的有效配置和共享使用是云計(jì)算領(lǐng)域研究必須解決的關(guān)鍵問(wèn)題之一[3].目前,關(guān)于云環(huán)境下的資源管理策略已有了較多研究,針對(duì)不同的計(jì)算任務(wù)和優(yōu)化目標(biāo),云資源調(diào)度算法大致可以劃分為以下幾類:①考慮資源負(fù)載均衡、提高資源利用率[4,5];②滿足任務(wù)執(zhí)行時(shí)間[6]、能耗費(fèi)用[7,8]、用戶QoS[9,10]等約束條件;③基于需求預(yù)測(cè)的虛擬機(jī)資源按需分配策略[11,12];④多目標(biāo)優(yōu)化算法[13,14].

云資源的可靠性可定義為在規(guī)定時(shí)間和規(guī)定條件下完成規(guī)定任務(wù)的能力或概率[15].由于云計(jì)算系統(tǒng)是一個(gè)大規(guī)模復(fù)雜系統(tǒng),而云計(jì)算的核心思想是硬件、軟件資源的服務(wù)化,因此云服務(wù)商需要通過(guò)虛擬化軟件將物理機(jī)虛擬化為多臺(tái)具有不同服務(wù)屬性的虛擬機(jī),再以虛擬機(jī)為基本單位提供計(jì)算能力.在此過(guò)程中,物理機(jī)內(nèi)部元件故障或鏈路故障等因素都可能使放置于其上的虛擬機(jī)不能正常工作,從而導(dǎo)致用戶任務(wù)無(wú)法完成.因此,在擁有無(wú)數(shù)資源節(jié)點(diǎn)的云環(huán)境中,如何獲取可信的云資源,并將云任務(wù)分配到值得信任的資源節(jié)點(diǎn)上執(zhí)行就顯得異常重要,而傳統(tǒng)的云資源調(diào)度算法往往只考慮用戶任務(wù)的單一服務(wù)質(zhì)量需求,或多個(gè)服務(wù)質(zhì)量需求的組合優(yōu)化問(wèn)題,并未深入考慮資源節(jié)點(diǎn)的可信需求問(wèn)題.

近年來(lái),在國(guó)內(nèi)外分布式系統(tǒng)資源管理的相關(guān)研究中,有關(guān)如何獲取可信云資源的研究已經(jīng)取得了不少成果.然而,云應(yīng)用對(duì)資源需求的多樣性、動(dòng)態(tài)性和靈活性給云資源管理帶來(lái)了新的挑戰(zhàn).

首先,可靠性驅(qū)動(dòng)的云資源調(diào)度算法通過(guò)各類可靠性模型的構(gòu)建,對(duì)云環(huán)境下資源節(jié)點(diǎn)的可信度進(jìn)行度量.然而,已有可靠性度量模型并未充分考慮云計(jì)算環(huán)境下資源節(jié)點(diǎn)的異構(gòu)性、動(dòng)態(tài)性和廣域性等特點(diǎn),缺乏對(duì)任務(wù)在資源節(jié)點(diǎn)上執(zhí)行可靠性以及數(shù)據(jù)在通信鏈路上傳輸可靠性的綜合分析.

其次,現(xiàn)有可靠性驅(qū)動(dòng)的云資源調(diào)度模型大多采用基于靜態(tài)或動(dòng)態(tài)隊(duì)列的資源調(diào)度模型,即表調(diào)度算法,可表述為基于貪心策略的可信資源需求與虛擬機(jī)資源供給的最優(yōu)匹配問(wèn)題,僅能適用于求解固定目標(biāo)的局部最優(yōu)解,而難以統(tǒng)籌考慮并行任務(wù)的整體可靠性需求,也難以描述云任務(wù)對(duì)物理機(jī)資源的使用偏好問(wèn)題.

針對(duì)上述問(wèn)題和并行任務(wù)圖的特點(diǎn),本文的主要貢獻(xiàn)有:

1) 根據(jù)并行任務(wù)及胖樹形云系統(tǒng)的結(jié)構(gòu)特點(diǎn),綜合考慮云計(jì)算環(huán)境下資源節(jié)點(diǎn)與通信鏈路的可靠性問(wèn)題,在此基礎(chǔ)上提出基于任務(wù)執(zhí)行行為的云系統(tǒng)可靠性度量模型;

2) 針對(duì)表調(diào)度算法表達(dá)能力的局限性,本文設(shè)計(jì)了基于遺傳智能的可信云資源調(diào)度算法.該算法通過(guò)熵值法綜合可靠性需求與服務(wù)質(zhì)量需求,不僅能夠有效提高云任務(wù)執(zhí)行的整體可靠性,還兼顧了云任務(wù)的數(shù)據(jù)本地性問(wèn)題,有效降低云任務(wù)的平均調(diào)度長(zhǎng)度.

2 相關(guān)工作

云資源的信任管理和可信調(diào)度問(wèn)題,目前已得到國(guó)內(nèi)外學(xué)者的大量研究,其核心思想是通過(guò)構(gòu)建各類信任評(píng)價(jià)模型,為應(yīng)用任務(wù)選擇高可信度的虛擬機(jī)資源,從而避開虛擬機(jī)的易失效時(shí)段進(jìn)行使用.

Wang等[16]借鑒社會(huì)學(xué)中的人際關(guān)系網(wǎng)絡(luò),通過(guò)分析節(jié)點(diǎn)間的歷史交互數(shù)據(jù),利用Bayes方法對(duì)節(jié)點(diǎn)的可信度進(jìn)行評(píng)估,構(gòu)建基于信任機(jī)制的可信調(diào)度模型;Cao[17,18]以人際關(guān)系信任模型為基礎(chǔ),提出一種基于直接信任度、推薦信任度和第三方服務(wù)性能反饋的可信度量模型,該模型通過(guò)基于熵權(quán)的主客觀賦權(quán)法將各評(píng)價(jià)指標(biāo)綜合起來(lái),選擇可信動(dòng)態(tài)級(jí)最大的計(jì)算資源執(zhí)行云任務(wù);文獻(xiàn)[19]通過(guò)云模型刻畫云資源節(jié)點(diǎn)的信任變化,提出基于云模型的主觀信任評(píng)價(jià)方法;Tang[20]、Luo[21]針對(duì)信任評(píng)估的不確定性以及可能存在的樣本不足的問(wèn)題,分別提出了基于模糊邏輯和基于置信度的主觀信任管理模型;Deng等[22]提出了一種可信優(yōu)化的資源調(diào)度算法,構(gòu)建基于身份可信、能力可信、行為可信的綜合信任模型.Abawajy等[23]提出了一種云計(jì)算環(huán)境下基于可信評(píng)估的信譽(yù)系統(tǒng),使得交互能夠在相互信任的基礎(chǔ)上完成;Raghebi等[24]則通過(guò)用戶任務(wù)反饋機(jī)制,在用戶歷史反饋數(shù)據(jù)的基礎(chǔ)上構(gòu)建云服務(wù)信任評(píng)估模型;Li等[25]引入粗糙集理論和誘導(dǎo)有序加權(quán)平均算子評(píng)估云服務(wù)的性能,提出一種自適應(yīng)的信任管理模型;Fan等[26]考慮信任評(píng)估的不同側(cè)面,將各類信任評(píng)估模型通過(guò)模糊邏輯以及證據(jù)推理方法進(jìn)行綜合,構(gòu)造基于模糊推理系統(tǒng)的云服務(wù)信任評(píng)估模型.

上述文獻(xiàn)從不同角度構(gòu)建了各類信任評(píng)估模型來(lái)滿足云任務(wù)對(duì)服務(wù)資源的可信需求.然而,以上算法往往只分析了任務(wù)在云資源上執(zhí)行的可靠性及其失效規(guī)律,或是通過(guò)任務(wù)執(zhí)行行為分析了數(shù)據(jù)在通信鏈路上通信的可靠性,并未綜合分析兩種可靠性及其相互關(guān)系.此外,以上文獻(xiàn)多采用隊(duì)列進(jìn)行資源調(diào)度建模,使用貪心策略為用戶任務(wù)匹配當(dāng)前可信度最高的虛擬機(jī)資源,因而該類算法僅能找到當(dāng)前的局部最優(yōu)解而難以統(tǒng)籌全局,且調(diào)度目標(biāo)單一,不易根據(jù)實(shí)際需求而靈活變化.

3 問(wèn)題建模

云資源調(diào)度問(wèn)題可描述為云計(jì)算環(huán)境下用戶任務(wù)需求與云資源供給的最優(yōu)匹配問(wèn)題,由云環(huán)境下n個(gè)虛擬機(jī)資源與m個(gè)用戶任務(wù)組成.考慮云任務(wù)之間可能具有數(shù)據(jù)先后依賴關(guān)系或優(yōu)先約束,且云資源節(jié)點(diǎn)之間的連接方式復(fù)雜多樣,本文采用有向無(wú)環(huán)圖(Directed Acyclic Graph,DAG)描述云計(jì)算環(huán)境下具有相互依賴關(guān)系和數(shù)據(jù)交換的并行任務(wù),采用胖樹型結(jié)構(gòu)描述云資源節(jié)點(diǎn)的系統(tǒng)構(gòu)成,分別定義如下:

定義1.(并行任務(wù)DAG模型) 考慮云任務(wù)之間的優(yōu)先約束關(guān)系,本文將云計(jì)算環(huán)境下的并行任務(wù)描述為一個(gè)DAG圖,可用四元組表示,即DAG=(T,E,W,Tp).其中T={t1,t2,…,tm},表示m個(gè)云任務(wù)的集合;E={eij|ti,tj∈T}?T×T,表示云任務(wù)之間的相互依賴關(guān)系,即任務(wù)ti為任務(wù)tj的前驅(qū),當(dāng)所有前驅(qū)任務(wù)執(zhí)行完成后,任務(wù)tj才能執(zhí)行;W={w1,w2,…,wm},表示云任務(wù)的計(jì)算量集合;Tp={ti|indegree(ti)=0,1≤i≤m},表示當(dāng)前可并行任務(wù),即入度為0的云任務(wù)集合,同時(shí)設(shè)定云任務(wù)DAG圖的入口節(jié)點(diǎn)和出口節(jié)點(diǎn)都為1.

定義2.(云資源系統(tǒng)) 考慮云計(jì)算環(huán)境下資源節(jié)點(diǎn)之間的相互連接方式多種多樣,本文使用胖樹型拓?fù)浣Y(jié)構(gòu)對(duì)云數(shù)據(jù)中心網(wǎng)絡(luò)進(jìn)行描述,可用五元組表示,即Cloud=(V,C,B,H,R),其中V={v1,v2,…,vn},表示云環(huán)境下n個(gè)虛擬機(jī)資源節(jié)點(diǎn)的集合;C={cij|vi,vj∈V}?V×V,表示虛擬機(jī)資源節(jié)點(diǎn)之間的通信鏈路集合;B={bij|vi,vj∈V,cij∈C},表示通信鏈路cij=(vi,vj)的平均帶寬;H={hij|vi,vj∈V,cij∈C},表示通信鏈路cij的歷史交互數(shù)據(jù);R={r1,r2,…,ri},表示云環(huán)境下i個(gè)物理機(jī)資源的集合.

圖1 云數(shù)據(jù)中心結(jié)構(gòu)Fig.1 Cloud data center framework

如圖1所示的三層胖樹型結(jié)構(gòu),由上而下分別為核心層、匯聚層和接入層,物理機(jī)通過(guò)接入層路由器接入網(wǎng)絡(luò)、共享資源,而核心層路由器則是數(shù)據(jù)中心對(duì)外交換數(shù)據(jù)的必經(jīng)橋梁,需要傳遞來(lái)自更多物理機(jī)的大量數(shù)據(jù),其帶寬決定了能夠通過(guò)該數(shù)據(jù)中心的最大任務(wù)數(shù).

4 基于任務(wù)執(zhí)行行為感知的云系統(tǒng)可靠性度量模型

本節(jié)對(duì)可靠性需求、服務(wù)質(zhì)量需求分別進(jìn)行建模描述,構(gòu)建基于任務(wù)執(zhí)行行為感知的可靠性度量模型.

4.1 可靠性需求

將云任務(wù)ti∈T調(diào)度到虛擬機(jī)資源vdst上,且成功執(zhí)行的條件是:

1) 任務(wù)tj所依賴的數(shù)據(jù)成功傳輸?shù)教摂M機(jī)vdst上,即將任務(wù)tj所需數(shù)據(jù)從源虛擬機(jī)資源vsrc成功傳輸?shù)侥繕?biāo)虛擬機(jī)資源vdst上,需要保障通信鏈路的可靠性;

2) 任務(wù)tj在虛擬機(jī)vdst上執(zhí)行時(shí)不能發(fā)生失效,即保障虛擬機(jī)執(zhí)行任務(wù)的可靠性.

因此本文構(gòu)建云系統(tǒng)可靠性度量模型,將云系統(tǒng)可靠性Φ劃分為云資源節(jié)點(diǎn)可信度ΦNode和通信鏈路可信度ΦPath,按照式(1)進(jìn)行綜合,其中f(.)為可信度綜合函數(shù),滿足凸函數(shù)的性質(zhì),由云任務(wù)對(duì)兩類云系統(tǒng)資源的可靠性需求程度決定.

Φ=f(ΦNode,ΦPath)

(1)

4.1.1 云資源節(jié)點(diǎn)可信度度量

假設(shè)云資源節(jié)點(diǎn)執(zhí)行任務(wù)只存在成功和失效兩種狀態(tài).已有研究[23,30,31]通過(guò)對(duì)云計(jì)算系統(tǒng)失效日志進(jìn)行統(tǒng)計(jì)分析發(fā)現(xiàn),云資源節(jié)點(diǎn)失效表現(xiàn)出很強(qiáng)的時(shí)間、空間分布規(guī)律.

時(shí)間分布規(guī)律可表述為:如將物理機(jī)失效的間隔時(shí)間視為隨機(jī)過(guò)程,則該過(guò)程服從形狀參數(shù)k<1,尺度參數(shù)λ>0的Weibull分布.當(dāng)云資源節(jié)點(diǎn)剛啟動(dòng)時(shí),其可靠性較低,隨著運(yùn)行時(shí)間的逐步增加,可靠性也相應(yīng)提高,而當(dāng)執(zhí)行時(shí)間超過(guò)某閾值后,該資源節(jié)點(diǎn)可靠性則越來(lái)越低,直至發(fā)生不可恢復(fù)失效.

設(shè)Weibull分布形狀參數(shù)為k,尺度參數(shù)為λ,則其概率密度函數(shù)和累積分布函數(shù)分別如式(2)和式(3)所示.

(2)

cdf(x)=1-e-(x/λ)k

(3)

失效率函數(shù)表示當(dāng)前未發(fā)生失效,而未來(lái)即將發(fā)生失效的概率.由式(2)和式(3)可得云系統(tǒng)中資源節(jié)點(diǎn)的Weibull分布失效率函數(shù)h(x),如式(4)所示:

(4)

失效概率越大則機(jī)器發(fā)生失效的可能性越高,因此定義云資源節(jié)點(diǎn)執(zhí)行任務(wù)的可信度ΦNode如式(5)所示:

(5)

空間分布規(guī)律可表述為:物理機(jī)失效事件具有空間上的規(guī)律性,即大部分失效發(fā)生在少部分物理機(jī)上,而剛失效的資源節(jié)點(diǎn)由于比較脆弱,較易于再次發(fā)生失效.因此,針對(duì)物理機(jī)失效的空間分布規(guī)律,對(duì)于失效剛恢復(fù)的資源節(jié)點(diǎn),本文選擇將其擱置時(shí)間一定時(shí)間再加入空閑資源池以供調(diào)度使用,設(shè)置擱置時(shí)間為δ.

4.1.2 通信鏈路可信度度量

將任務(wù)tj調(diào)度到目標(biāo)虛擬機(jī)資源vdst上執(zhí)行前,需要將其前驅(qū)任務(wù)的相關(guān)數(shù)據(jù)由源虛擬機(jī)vsrc通過(guò)通信鏈路c(src,dst)傳輸?shù)侥繕?biāo)虛擬機(jī)vdst上.本文通過(guò)分析云資源節(jié)點(diǎn)之間的歷史交互數(shù)據(jù),使用證據(jù)理論和Bayes方法度量通信鏈路c(src,dst)的可信度ΦPath.

設(shè)云計(jì)算環(huán)境下存在2個(gè)資源節(jié)點(diǎn)x和y,使用二項(xiàng)事件(成功/失敗)描述其數(shù)據(jù)傳輸結(jié)果,當(dāng)節(jié)點(diǎn)x和y發(fā)生n次交互后,其中成功次數(shù)為u,失敗次數(shù)為v,則將其間通信鏈路c(x,y)的可信度ΦPath定義為第n+1次交互成功的概率.由于資源節(jié)點(diǎn)x和y之間交互成功的后驗(yàn)概率服從Beta分布,如將單次節(jié)點(diǎn)交互過(guò)程中交互成功的先驗(yàn)概率設(shè)為隨機(jī)變量θ,假定θ服從均勻分布U(0,1),則其后驗(yàn)概率密度函數(shù)如式(6)所示:

(6)

通信鏈路可信度ΦPath定義為通信鏈路c(src,dst)在網(wǎng)絡(luò)中提供可靠通信的能力,是對(duì)未來(lái)交互成功概率的預(yù)測(cè),即交互經(jīng)驗(yàn)分布的期望值,如式(7)所示:

(7)

當(dāng)云資源節(jié)點(diǎn)之間不存在歷史交互或交互數(shù)據(jù)較少不足以進(jìn)行評(píng)估時(shí),引入中間推薦節(jié)點(diǎn)計(jì)算鏈路可信度.設(shè)云資源節(jié)點(diǎn)x和z,y和z交互獨(dú)立,交互次數(shù)分別為n1、n2,其中交互成功、失敗次數(shù)分別為(u1,v1)和(u2,v2),則其通信鏈路c(x,y)的可信度ΦPath定義為:

(8)

4.2 服務(wù)質(zhì)量需求

為簡(jiǎn)化模型,本文考慮服務(wù)質(zhì)量屬性為任務(wù)響應(yīng)時(shí)間,實(shí)際應(yīng)用中可按需求進(jìn)行擴(kuò)展.

任務(wù)響應(yīng)時(shí)間(ResponseTime,RT)包括云資源節(jié)點(diǎn)之間進(jìn)行數(shù)據(jù)傳輸?shù)耐ㄐ艜r(shí)間和云任務(wù)的執(zhí)行時(shí)間.由于云系統(tǒng)中資源節(jié)點(diǎn)在不同供應(yīng)電壓下的計(jì)算速度不同,且資源節(jié)點(diǎn)之間的通信帶寬往往隨時(shí)間動(dòng)態(tài)變化,因而定義云任務(wù)的執(zhí)行時(shí)間為計(jì)算資源在最大供應(yīng)電壓下執(zhí)行云任務(wù)所需的時(shí)間,定義通信時(shí)間為以資源節(jié)點(diǎn)間的平均帶寬進(jìn)行數(shù)據(jù)傳輸所需的時(shí)間.

在實(shí)際應(yīng)用中,由于各項(xiàng)服務(wù)質(zhì)量屬性的量綱、數(shù)量級(jí)都不相同,因而需要對(duì)初始數(shù)據(jù)按照式(9)做無(wú)量綱標(biāo)準(zhǔn)化處理,將其轉(zhuǎn)化至[0,1]范圍內(nèi),其中max(xi)和min(xi)分別表示第i項(xiàng)服務(wù)質(zhì)量屬性的最大值和最小值.

(9)

4.3 組合調(diào)度目標(biāo)

本文考慮的調(diào)度指標(biāo)包括可靠性(Reliability)和任務(wù)響應(yīng)時(shí)間(Responsetime),定義組合調(diào)度目標(biāo)如式(10)所示:

(10)

其中WReliability、WRT分別表示可靠性、任務(wù)響應(yīng)時(shí)間的權(quán)重,該權(quán)重通過(guò)熵值法[27]根據(jù)各項(xiàng)指標(biāo)所含信息有序度的差異,即信息的效用價(jià)值確定.云系統(tǒng)可靠性在代入計(jì)算前需按式(11)做無(wú)量綱標(biāo)準(zhǔn)化處理,將其轉(zhuǎn)化至[0,1]范圍內(nèi).

(11)

5 基于任務(wù)執(zhí)行行為的可信云資源調(diào)度算法

5.1 并行任務(wù)調(diào)度描述

云計(jì)算環(huán)境下的并行任務(wù)調(diào)度是在充分考慮任務(wù)之間的相互依賴關(guān)系的基礎(chǔ)上,將云任務(wù)分配到各虛擬機(jī)資源上協(xié)同執(zhí)行的過(guò)程.如在并行任務(wù)DAG圖中,任務(wù)之間存在數(shù)據(jù)的依賴關(guān)系,其中任務(wù)t1為任務(wù)t2和t3的后續(xù)任務(wù),不妨設(shè)任務(wù)t1調(diào)度到虛擬機(jī)資源vi上執(zhí)行,而任務(wù)t2和t3分別調(diào)度到虛擬機(jī)資源vj和vk上執(zhí)行,則任務(wù)t1和t2、t3之間的數(shù)據(jù)傳遞應(yīng)通過(guò)虛擬機(jī)資源vi和vj、vk之間的通信鏈路進(jìn)行,若虛擬機(jī)資源vi和vj處于同一物理機(jī),則通信時(shí)間可忽略不計(jì).

由此,如式(12)所示,可將并行任務(wù)調(diào)度問(wèn)題描述如下:

1)后續(xù)任務(wù)tj在虛擬機(jī)資源vt上的開始執(zhí)行時(shí)間Tstart(tj,vt)應(yīng)大于其所有前驅(qū)任務(wù)的最遲執(zhí)行完成時(shí)間Tpred-exec(tj)與前驅(qū)任務(wù)的最大數(shù)據(jù)傳遞時(shí)間Tpred-comm(tj)之和;

2)同一虛擬機(jī)資源上同一時(shí)間只能執(zhí)行一個(gè)任務(wù);

3)最大化組合調(diào)度目標(biāo),即提高任務(wù)執(zhí)行的整體可靠性,降低任務(wù)調(diào)度長(zhǎng)度.

(12)

5.2 遺傳算法設(shè)計(jì)

5.2.1 染色體編碼

染色體編碼有多種方式,本文設(shè)計(jì)遺傳算法采用資源—任務(wù)的間接編碼方式,即染色體由資源串與任務(wù)串兩部分組成.其中,任務(wù)串為滿足任務(wù)之間優(yōu)先關(guān)系的拓?fù)湫蛄?資源串為執(zhí)行各任務(wù)的虛擬機(jī)資源標(biāo)號(hào).不妨設(shè)染色體為{t1,t2,…,tm|v1,v2,…,vn},則t1,t2,…,tm為滿足優(yōu)先約束的并行任務(wù)拓?fù)湫蛄?v1,v2,…,vn為執(zhí)行任務(wù)的相應(yīng)虛擬機(jī)資源標(biāo)號(hào).

通過(guò)分析可知,當(dāng)并行任務(wù)數(shù)量大于虛擬機(jī)資源數(shù),即m>n時(shí),序列v1,v2,…,vn中存在相同資源,即將不同任務(wù)先后調(diào)度到同一虛擬機(jī)資源上執(zhí)行;反之,即m

5.2.2 適應(yīng)度函數(shù)

遺傳算法通過(guò)適應(yīng)度函數(shù)的計(jì)算來(lái)完成下一代的選擇進(jìn)化,本文所述并行任務(wù)的組合調(diào)度目標(biāo)是在滿足任務(wù)執(zhí)行優(yōu)先順序的前提下,最大化任務(wù)執(zhí)行的可靠性需求,最小化任務(wù)調(diào)度長(zhǎng)度.因此對(duì)于有效染色體X,定義適應(yīng)度函數(shù)為:

(13)

5.2.3 選擇操作

選擇操作是對(duì)個(gè)體適應(yīng)性的評(píng)價(jià)方式,利用選擇操作可將當(dāng)前群體中的優(yōu)良基因復(fù)制到下一代群體.本文采用比例選擇操作,即個(gè)體被選擇的概率由個(gè)體的適應(yīng)度大小決定,即Psel(Xi)=f(Xi)/∑f(X).

5.2.4 交叉操作

由于本文構(gòu)造的染色體由任務(wù)串和資源串組成,因此交叉操作也分別由任務(wù)串交叉操作與資源串交叉操作組成.任務(wù)串的交叉操作具體方法為:對(duì)于一對(duì)染色體X1、X2,其任務(wù)串分別為X1task和X2task,隨機(jī)產(chǎn)生同一位置的斷點(diǎn),將X1task的左半部分作為其后代第1部分,將X2task的右半部分作為后代的第2部分;資源串的交叉操作具體方法為:對(duì)于一對(duì)染色體X1、X2,其資源串分別為X1VM和X2VM,隨機(jī)產(chǎn)生同一位置的斷點(diǎn),將斷點(diǎn)右半部分進(jìn)行交換.

5.2.5 變異操作

變異操作是在當(dāng)前群體中按照一定概率產(chǎn)生新的個(gè)體.如上文所述,變異操作也由任務(wù)串變異操作和資源串變異操作組成,其具體方法為在任務(wù)串和資源串中分別選擇一位進(jìn)行突變.

5.3 任務(wù)執(zhí)行行為感知的遺傳調(diào)度算法(Execution Behavior Aware Genetic Scheduling Algorithm,EBAGS)

算法1.任務(wù)執(zhí)行行為感知的遺傳調(diào)度算法EBAGS()輸入: 并行任務(wù)T={t1,t2,…,tm},云虛擬機(jī)資源V={v1,v2,…,vn}輸出:任務(wù)—資源分配序列,任務(wù)調(diào)度長(zhǎng)度,任務(wù)執(zhí)行成功率1生成初始種群X0={t10,t20,…,tm0|v10,v20,…,vn0}2分別計(jì)算云資源節(jié)點(diǎn)可信度與通信鏈路可信度;3設(shè)迭代次數(shù)t=04IF(t<最大迭代次數(shù)||滿足適應(yīng)度閾值;t++)5 {選擇操作,選擇與復(fù)制概率為Ps;6 交叉操作,交叉概率為Pc;7 變異操作,變異概率為Pm;8 計(jì)算當(dāng)前種群適應(yīng)度;}9由染色體解碼調(diào)度方案;10計(jì)算任務(wù)調(diào)度長(zhǎng)度與任務(wù)執(zhí)行成功率

6 仿真實(shí)驗(yàn)及分析

6.1 仿真實(shí)驗(yàn)環(huán)境和設(shè)置

為驗(yàn)證和評(píng)價(jià)提出的基于任務(wù)執(zhí)行行為感知的可信云資源調(diào)度算法性能,本文對(duì)開源云仿真軟件CloudSim3.0[28]進(jìn)行擴(kuò)展,構(gòu)建云仿真實(shí)驗(yàn)平臺(tái).CloudSim是基于Java的離散事件模擬工具包,能夠?qū)ξ锢碇鳈C(jī)、虛擬機(jī)資源、云服務(wù)和虛擬化云數(shù)據(jù)中心進(jìn)行仿真,其資源分配層提供了可擴(kuò)展接口,支持云計(jì)算的資源管理和調(diào)度模擬.在CloudSim中,云數(shù)據(jù)中心由大量物理主機(jī)構(gòu)成,而每個(gè)物理主機(jī)都可虛擬化為多臺(tái)虛擬機(jī)資源,云數(shù)據(jù)中心根據(jù)預(yù)置的分配參數(shù)與策略為虛擬機(jī)分配物理資源(包括CPU、內(nèi)存、帶寬等),之后由虛擬機(jī)根據(jù)用戶定義的調(diào)度策略執(zhí)行云任務(wù).

實(shí)驗(yàn)參數(shù)設(shè)置如下:本文構(gòu)建了胖樹型數(shù)據(jù)中心網(wǎng)絡(luò),接入層、匯聚層和核心層路由器數(shù)及轉(zhuǎn)發(fā)延遲預(yù)先給定,設(shè)定每臺(tái)物理機(jī)最多可虛擬化為4臺(tái)虛擬機(jī)資源,通信鏈路傳輸速度介于2Mbit/s ～10Mbit/s.并行任務(wù)DAG圖由并行仿真任務(wù)自動(dòng)生成軟件隨機(jī)生成,設(shè)定云任務(wù)在云資源上的執(zhí)行時(shí)間介于10s～50s;云任務(wù)類型以及任務(wù)間傳輸?shù)臄?shù)據(jù)量根據(jù)其通信計(jì)算比率CCR(Communication to Computation Ratio,CCR)決定,CCR為并行任務(wù)DAG圖中所有任務(wù)間通信量與所有任務(wù)計(jì)算量的比值,CCR>1表示云任務(wù)為通信密集型任務(wù),反之則為計(jì)算密集型任務(wù);根據(jù)大規(guī)模云計(jì)算實(shí)驗(yàn)床的系統(tǒng)失效日志分析,設(shè)置資源節(jié)點(diǎn)執(zhí)行任務(wù)時(shí)節(jié)點(diǎn)失效事件服從Weibull分布,其形狀參數(shù)k為0.75,尺度參數(shù)為λ為60,設(shè)定剛失效資源近期再次發(fā)生失效的頻率在1～3之間滿足均勻分布.在所有仿真實(shí)驗(yàn)中,對(duì)于上述每一組隨機(jī)產(chǎn)生的參數(shù)集,實(shí)驗(yàn)結(jié)果采用10次實(shí)驗(yàn)的平均值.

6.2 云系統(tǒng)可靠性度量模型的有效性

本文選擇可靠性綜合函數(shù)f(ΦNode,ΦPath)為線性函數(shù):Φ=αΦNode+(1-α)ΦPath,其中ΦNode和ΦPath代入計(jì)算前先進(jìn)行歸一化處理,α為可靠性需求因子,反映了云任務(wù)對(duì)云資源節(jié)點(diǎn)以及通信鏈路的可靠性需求程度,且α∈(0,1).本項(xiàng)實(shí)驗(yàn)討論可靠性需求因子α對(duì)任務(wù)執(zhí)行成功率的影響.

本組實(shí)驗(yàn)對(duì)算法在不同可靠性需求因子下的任務(wù)平均執(zhí)行成功率進(jìn)行比較,實(shí)驗(yàn)相關(guān)參數(shù)設(shè)置如下:隨機(jī)生成云任務(wù)數(shù)為100的應(yīng)用程序任務(wù)圖,服務(wù)資源數(shù)為200,鏈路數(shù)為400.本組實(shí)驗(yàn)中,可靠性需求因子α的取值分別為:0、0.3、0.7和1,當(dāng)α=0時(shí),可靠性綜合函數(shù)f(ΦNode,ΦPath)=ΦPath,即只考慮通信鏈路的可信度;當(dāng)α=1時(shí),可靠性綜合函數(shù)f(ΦNode,ΦPath)=ΦNode,只考慮云資源節(jié)點(diǎn)的可信度.

圖2 可靠性需求因子對(duì)任務(wù)平均執(zhí)行成功率的影響Fig.2 Effect of reliability requirement factor to average ratio of successful execution

實(shí)驗(yàn)結(jié)果如圖2所示,由圖可見(jiàn),對(duì)于不同類型任務(wù),當(dāng)只考慮通信鏈路的可信度或只考慮云資源節(jié)點(diǎn)的可信度時(shí),任務(wù)平均執(zhí)行成功率均較低,而綜合考慮兩方面影響因素時(shí),任務(wù)平均執(zhí)行成功率得到顯著地提高;與此同時(shí),對(duì)于CCR<1的計(jì)算密集型任務(wù),α=0.3時(shí)的任務(wù)平均執(zhí)行成功率明顯低于α=0.7時(shí)的任務(wù)平均執(zhí)行成功率,而對(duì)于CCR>1的通信密集型任務(wù),實(shí)驗(yàn)結(jié)果則相反.實(shí)驗(yàn)說(shuō)明,對(duì)于不同類型的云任務(wù)應(yīng)根據(jù)其通信計(jì)算比率選擇適當(dāng)?shù)目煽啃孕枨笠蜃?同時(shí)也體現(xiàn)了本文提出云系統(tǒng)可靠性度量模型的有效性.

6.3 不同任務(wù)數(shù)量情況下的算法性能比較

為驗(yàn)證本文提出基于任務(wù)執(zhí)行行為感知的遺傳調(diào)度算法性能,在不同任務(wù)數(shù)量的情況下,比較經(jīng)典表調(diào)度算法HEFT算法[29]、CTDLS算法[17]和本文算法在任務(wù)平均執(zhí)行成功率,平均調(diào)度長(zhǎng)度兩方面的性能.實(shí)驗(yàn)參數(shù)設(shè)置如下:CCR=1,可靠性需求因子α為0.5,服務(wù)資源數(shù)為200,鏈路數(shù)為400,隨機(jī)生成云任務(wù)數(shù)為50～140的應(yīng)用程序任務(wù)圖.

實(shí)驗(yàn)結(jié)果如圖3,圖4所示.由圖3可見(jiàn),隨著任務(wù)數(shù)量的增加,三種算法的任務(wù)平均執(zhí)行成功率均有降低,其中EBAGS的執(zhí)行成功率高于CTDLS,同時(shí)遠(yuǎn)高于HEFT,充分體現(xiàn)了本文提出算法對(duì)并行任務(wù)整體執(zhí)行成功率的提升.

從圖4可見(jiàn),EBAGS和CTDLS的平均調(diào)度長(zhǎng)度均低于HEFT.這是由于HEFT雖然盡可能將任務(wù)調(diào)度到具有最早完成時(shí)間的資源上執(zhí)行,然而HEFT并未考慮云任務(wù)的可信需求,任務(wù)執(zhí)行失效增加了任務(wù)被重新調(diào)度的次數(shù).與此同時(shí),EBAGS充分考慮了云任務(wù)的可信需求與服務(wù)質(zhì)量需求,在構(gòu)建基于遺傳智能的全局調(diào)度優(yōu)化基礎(chǔ)上,還通過(guò)數(shù)據(jù)本地性設(shè)置(即當(dāng)待調(diào)度虛擬機(jī)處于同一物理機(jī)時(shí),其通信時(shí)間忽略不計(jì)),將任務(wù)盡可能調(diào)度到該任務(wù)所依賴的數(shù)據(jù)所放置的物理機(jī)上執(zhí)行,縮短了任務(wù)通信時(shí)間,有效地降低了任務(wù)的平均調(diào)度長(zhǎng)度.

圖3 三種算法在不同任務(wù)數(shù)下的任務(wù)執(zhí)行成功率比較Fig.3 Comparison ratio of successful execution of three algorithms under varying number of tasks

圖4 三種算法在不同任務(wù)數(shù)下的平均調(diào)度長(zhǎng)度比較Fig.4 Comparison ratio of scheduling length of three algorithms under varying number of tasks

6.4 不同任務(wù)類型情況下的算法性能比較

本組實(shí)驗(yàn)在不同任務(wù)類型的情況下,比較HEFT算法、CTDLS算法和EBAGS算法在任務(wù)平均執(zhí)行成功率,平均調(diào)度長(zhǎng)度兩方面的性能.實(shí)驗(yàn)相關(guān)參數(shù)設(shè)置如下:隨機(jī)生成任務(wù)數(shù)為100的應(yīng)用程序任務(wù)圖,服務(wù)資源數(shù)為200,鏈路數(shù)為400,設(shè)置云任務(wù)CCR值分別為0.1、1、10,相應(yīng)設(shè)定EBAGS算法的可靠性需求因子分別為0.7、0.5、0.3.

實(shí)驗(yàn)結(jié)果如圖5、圖6所示,對(duì)于不同類型任務(wù),EBAGS的任務(wù)平均執(zhí)行成功率總是高于CTDLS和HEFT,而EBAGS的平均調(diào)度長(zhǎng)度低于其他2個(gè)算法,從另一側(cè)面說(shuō)明了本文提出云資源調(diào)度算法的有效性.

7 結(jié)束語(yǔ)

云計(jì)算環(huán)境下任務(wù)執(zhí)行的可靠性是當(dāng)前云資源調(diào)度算法的研究熱點(diǎn).針對(duì)現(xiàn)有以隊(duì)列方式進(jìn)行建模的可信云資源調(diào)度模型的局限性,本文首先構(gòu)建了基于任務(wù)執(zhí)行行為的云系統(tǒng)可靠性度量模型,該模型根據(jù)并行任務(wù)及胖樹形云系統(tǒng)的結(jié)構(gòu)特點(diǎn),以及資源節(jié)點(diǎn)失效規(guī)律分析,綜合考慮了云計(jì)算環(huán)境下資源節(jié)點(diǎn)與通信鏈路的可靠性問(wèn)題;其次,設(shè)計(jì)了基于遺傳智能的可信云資源調(diào)度算法,該算法將云任務(wù)的資源需求與云資源的動(dòng)態(tài)供給的最優(yōu)匹配問(wèn)題轉(zhuǎn)換為考慮整體可靠性的全局最優(yōu)化問(wèn)題,同時(shí)考慮了云任務(wù)的服務(wù)質(zhì)量需求與數(shù)據(jù)本地性需求,為用戶任務(wù)選擇可信資源提供了切實(shí)可行的辦法.本文的下一步工作將進(jìn)一步考慮如何根據(jù)云計(jì)算環(huán)境的動(dòng)態(tài)變化自適應(yīng)調(diào)整資源節(jié)點(diǎn)可信度與通信鏈路可信度的權(quán)值.

圖5 三種算法在不同任務(wù)類型下的任務(wù)執(zhí)行成功率比較Fig.5 Comparison ratio of successful execution of three algorithms under varying kinds of tasks

圖6 三種算法在不同任務(wù)類型下的平均調(diào)度長(zhǎng)度比較Fig.6 Comparison ratio of scheduling length of three algorithms under varying kinds of tasks

[1] Rochwerger B,Breitgand D,Levy E,et al.The reservoir model and architecture for open federated cloud computing[J].IBM Journal of Research and Development,2009,53(4):1-17.

[2] DanielNurmi,Rich Wolski,Chris Grzegorczyk,et al.The eucalyptus open-source cloud-computing system[C].Proceedings of the 2009 9thIEEE/ACM International Symposium on Cluster Computing and the Grid,2009:124-131.

[3] Buyya R,Yeo C,Venugopal S,et al.Cloud computing and emerging IT platforms:Vision,hype and reality for delivering computing as the 5thutility[J].Future Generation Computer Systems,2009,25(6):599-616.

[4] Cao Jie,Zeng Guo-sun,Kuang Gui-juan,et al.An on-demand physical resource allocation method for cloud virtual machine to support random service requests[J].Journal of Software,2017,28(2):457-472.

[5] Xu Li,Zeng Zhi-bin,Yao Chuan.Study on virtual resource allocation optimization in cloud computing environment[J].Journal on Communications,2012,33(1):9-16.

[6] Darbha S,Agrawal D.Optimal scheduling algorithm for distributed memory machines[J].IEEE Transactions on Parallel and Distributed Systems,2012,9(1):87-95.

[7] Zhu Da-kai,D Mosse,R Melhem.Power-aware scheduling for and/or graphs in real-time systems [J].IEEE Transactions on Parallel and Distributed Systems,2014,15(9):849-864.

[8] Kim K,Buyya R,Kim J.Power aware scheduling of bag-of-tasks applications with deadline constraints on DVS-enabled clusters[C]. Proceedings of the 7thIEEE International Symposium on Cluster Computing and the Grid,2007:541-548.

[9] Xu Bao-min,Zhao Chun-yan,Hua En-zhao,et al,Job scheduling algorithm based on Berger model in cloud environment[J].Advances in Engineering Software,2011,42(3):419-425.

[10] Li Qin,Li Yong,Tu Bi-bo,et al.QoS-guaranteed dynamic resource provision in Internet data centers[J].Chinese Journal of Computers,2014,37(12):2395-2406.

[11] Song Ying,Sun Yu-zhong,Shi Wei-song.A two-tiered on-demand resource allocation mechanism for VM-based data centers[J].IEEE Trans on Services Computing,2013,6(1):116-129.

[12] Shi Xue-lin,Xu Ke.Utility Maximization model of virtual machine scheduling in cloud environment[J].Chinese Journal of Computers,2013,36(2):252-262.

[13] 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,2012,13(3):260-274.

[14] 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.

[15] Ding Yan,Wang Huai-min,Shi Pei-chang,et al.Trusted cloud service[J].Chinese Journal of Computers,2015,38(1):133-149.

[16] Wang Wei,Zeng Guo-sun,Tang Dai-zhong,et al.Cloud-DLS:dynamic trusted scheduling for cloud computing[J].Expert Systems with Applications,2012,39:2321-2329.

[17] Cao Jie,Zeng Guo-sun,Jiang Huo-wen,et al.Trust-aware dynamic level scheduling algorithm in cloud environment [J].Journal on Communications,2014,35(11):39-49.

[18] Cao Jie,Zeng Guo-sun,Niu Jun,et al.Availability-aware scheduling method for parallel task in cloud environment[J].Journal of Computer Research and Development,2013,50(7):1563-1572.

[19] Wang Shou-xin,Zhang Li,Li He-song.Evaluation approach of subjective trust based on cloud model[J].Journal of Software,2010,21(6):1341-1352.

[20] Tang Wen,Chen Zhong.Research of subjective trust management model based on the fuzzy set theory[J].Journal of Software,2003,14(8):1401-1408.

[21] Luo Jun-hai,Fan Ming-yu.A subjective trust management model based on certainty-factor for MANETs[J].Journal of Computer Research and Development,2013,47(3):516-523.

[22] Deng Xiao-heng,Lu Xi-cheng,Wang Huai-min.Study on trust evaluation based resource scheduling in iVCE[J].Chinese Journal of Computers,2017,30(10):1750-1762.

[23] Abawajy J.Determining service trustworthiness in inter-cloud computing environments[C].In Proceedings of 2009 10thInternational Symposium on Pervasive Systems,Algorithms and Networks,2009:784-788.

[24] Raghebi,Zohre,Mahmoud.A new trust evaluation method based on reliability of customer feedback for cloud computing[C]. In Preceedings of 2013 10thInternational ISC Conference on Information Security and Cryptology,2013:1-6.

[25] Li Xiao-yong.Du Jun-ping.Adaptive and attribute-based trust model for service-level agreement guarantee in cloud computing[J].IET Information Security,2013,7(2):144-154.

[26] Fan Wen-juan,Yang Shan-lin,Pei Jun.A novel two-stage model for cloud service trustworthiness evaluation[J].Expert Systems,2014,31(2):136-153.

[27] Yager R.On the entropy of fuzzy measures[J].IEEE Transactions on Fuzzy Systems,2000,8(4):453-461.

[28] Calheiros R N,Ranjan R,Rose C A F D,et al.Cloudsim:a novel framework for modeling and simulation of cloud computing infrastructures and services[R].GRIDS-TR-2009-1.Grid Computing and Distributed Systems Laboratory,The University of Melbourne,Australia,March 2009.

[29] Topcuoglu H,Hariri S,Wu M Y.Performance-effective and low complexity task scheduling for heterogeneous computing[J].IEEE Transaction on Parallel Distribution System,2002,13(3):260-274.

附中文參考文獻(xiàn)：

[4] 曹 潔,曾國(guó)蓀,匡桂娟,等.支持隨機(jī)服務(wù)請(qǐng)求的云虛擬機(jī)按需物理資源分配方法[J].軟件學(xué)報(bào),2017,28(2):457-472.

[5] 許 力,曾智斌,姚 川.云計(jì)算環(huán)境中虛擬資源分配優(yōu)化策略研究[J].通信學(xué)報(bào),2012,33(1):9-16.

[10] 李 青,李 勇,涂碧波,等.QoS保證的數(shù)據(jù)中心動(dòng)態(tài)資源供應(yīng)方法[J].計(jì)算機(jī)學(xué)報(bào),2014,37(12):2395-2406.

[12] 師雪霖,徐 恪.云虛擬機(jī)資源分配的效用最大化模型[J].計(jì)算機(jī)學(xué)報(bào),2013,36(2):252-262.

[15] 丁 滟,王懷民,史佩昌,等.可信云服務(wù)[J].計(jì)算機(jī)學(xué)報(bào),2015,38(1):133-149.

[17] 曹 潔,曾國(guó)蓀,姜火文,等.云環(huán)境下服務(wù)信任感知的可信動(dòng)態(tài)級(jí)調(diào)度算法[J].通信學(xué)報(bào),2014,35(11):39-49.

[18] 曹 潔,曾國(guó)蓀,鈕 俊,等.云環(huán)境下可用性感知的并行任務(wù)調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展,2013,50(7):1563-1572.

[19] 王守信,張 莉,李鶴松.一種基于云模型的主觀信任評(píng)價(jià)方法[J].軟件學(xué)報(bào),2010,21(6):1341-1352.

[20] 唐 文,陳 鐘.基于模糊集合理論的主觀信任管理模型[J].軟件學(xué)報(bào),2003,14(8):1401-1408.

[21] 羅俊海,范明鈺.基于置信度的MANETs主觀信任管理模型[J].計(jì)算機(jī)研究與發(fā)展,2013,47(3):516-523

[22] 鄧曉衡,盧錫成,王懷民.iVCE中基于可信評(píng)價(jià)的資源調(diào)度研究[J].計(jì)算機(jī)學(xué)報(bào),2017,30(10):1750-1762.