文一憑 , 王志斌 , 劉建勛 , 許小龍 , 康國勝

(1.湖南科技大學(xué) 知識(shí)處理與網(wǎng)絡(luò)化制造湖南省普通高校重點(diǎn)實(shí)驗(yàn)室, 湖南 湘潭 411201；2.南京信息工程大學(xué) 計(jì)算機(jī)與軟件學(xué)院, 江蘇 南京 210044)

0 引言

隨著云計(jì)算技術(shù)的深入發(fā)展與大數(shù)據(jù)時(shí)代的到來，云計(jì)算逐漸成為一種新的社會(huì)基礎(chǔ)設(shè)施。亞馬遜、微軟、阿里云、谷歌、華為、騰訊、百度等知名企業(yè)紛紛推出了各自的云服務(wù)產(chǎn)品。但是，單個(gè)云提供者 (cloud vendor)擁有的計(jì)算與存儲(chǔ)資源總是有限的。即使是阿里云這樣的龍頭企業(yè)，每年“雙十一”也要減少對外的資源供給，將一些與網(wǎng)購無關(guān)的云服務(wù)消費(fèi)者(cloud service consumer)暫時(shí)遷移到其他云上[1]。如果云提供者根據(jù)其突發(fā)峰值業(yè)務(wù)需求配置資源，將帶來巨大的資源效費(fèi)比問題：資源利用率低而成本顯著增加。而云提供者之間的協(xié)作不僅有助于應(yīng)對突發(fā)峰值業(yè)務(wù)需求，還可規(guī)避用戶依托單一云提供者帶來的平臺(tái)鎖定等問題。因此，使用多方的云資源，近年來成為了云服務(wù)消費(fèi)者的主流選擇[2-3]。而且，隨著云業(yè)務(wù)與云資源需求的不斷擴(kuò)大，云服務(wù)提供者之間的開放協(xié)作成為必然，新一代云計(jì)算將是圍繞云際協(xié)作的云計(jì)算，學(xué)術(shù)界和工業(yè)界也已針對云際協(xié)作環(huán)境的構(gòu)建等問題開展了大量研究[1-2]。

云工作流調(diào)度是映射并管理一組相互依賴的任務(wù)在云資源中執(zhí)行的過程。在云際協(xié)作環(huán)境中，不同云服務(wù)提供者部署的云數(shù)據(jù)中心、提供的虛擬機(jī)種類及收費(fèi)方式都不相同，可更好地滿足一些復(fù)雜工作流(例如，醫(yī)療應(yīng)用領(lǐng)域中的DNA測序工作流[4])對云資源的需求，并可為用戶按需、高效、低成本地獲取云資源提供更好的解決方案。另一方面，從云服務(wù)提供者的角度看，通過協(xié)作管理所共享的資源，將任務(wù)分配到不同的數(shù)據(jù)中心，即有可能更好地提升云數(shù)據(jù)中心的資源利用率，從整體上實(shí)現(xiàn)所有云數(shù)據(jù)中心的節(jié)能減排。但是，現(xiàn)有云工作流調(diào)度研究卻并未考慮在云際協(xié)作環(huán)境中，如何在為用戶節(jié)約云資源租賃成本的同時(shí)，降低或節(jié)約工作流執(zhí)行能耗。而該問題是源于實(shí)踐、符合云計(jì)算實(shí)際應(yīng)用需求的新問題，且與傳統(tǒng)云計(jì)算環(huán)境中的工作流調(diào)度相比，具有更大的挑戰(zhàn)性。

針對該問題，本文在現(xiàn)有云工作流調(diào)度研究的基礎(chǔ)上，提出一種云際協(xié)作環(huán)境下能耗與成本感知的工作流調(diào)度方法。該方法可在滿足工作流截止時(shí)間約束的前提下，優(yōu)化多個(gè)工作流的執(zhí)行費(fèi)用與能耗。

1 相關(guān)研究

任務(wù)調(diào)度一直是云計(jì)算領(lǐng)域的研究熱點(diǎn)，而成本是其中的重要考慮因素之一，文獻(xiàn)[5]對此進(jìn)行了綜述。近年來，隨著云基礎(chǔ)設(shè)施規(guī)模的持續(xù)擴(kuò)張，云數(shù)據(jù)中心的能耗不斷增長，如何實(shí)現(xiàn)云計(jì)算環(huán)境中任務(wù)的節(jié)能調(diào)度，成為學(xué)術(shù)界和產(chǎn)業(yè)界共同關(guān)注的重要問題[6]。在此背景下，提出了許多以降低或節(jié)約能耗為目標(biāo)的云工作流調(diào)度方法。目前，這些方法主要利用關(guān)閉/休眠、動(dòng)態(tài)電壓調(diào)整(Dynamic Voltage Scaling，DVS)和虛擬化(virtualization)等技術(shù)實(shí)現(xiàn)任務(wù)執(zhí)行時(shí)的節(jié)能。

基于DVS的云工作流節(jié)能調(diào)度方法主要根據(jù)互補(bǔ)金屬氧化物半導(dǎo)體(Complementary Metal Oxide Semiconductor，CMOS)電路動(dòng)態(tài)功率公式及任務(wù)截止時(shí)間等約束，通過降低或動(dòng)態(tài)調(diào)整處理器的電壓以實(shí)現(xiàn)節(jié)能。例如，文獻(xiàn)[7]基于多目標(biāo)離散微粒群優(yōu)化與DVS技術(shù)設(shè)計(jì)了一種可最小化完成時(shí)間、成本和能耗的多目標(biāo)云工作流調(diào)度方法。文獻(xiàn)[8]則結(jié)合DVS與虛擬化技術(shù)，給出一種計(jì)算工作流執(zhí)行能耗的新方式，并提出了一種云工作流節(jié)能調(diào)度方法。

但是，DVS技術(shù)在應(yīng)用時(shí)存在僅能降低處理器能耗等局限性[9]。因此，近年來，基于關(guān)閉/休眠或虛擬機(jī)遷移技術(shù)設(shè)計(jì)云工作流節(jié)能調(diào)度方法成為主流。文獻(xiàn)[10]從科學(xué)工作流應(yīng)用在云環(huán)境中執(zhí)行的角度，提出一種能耗感知的資源分配方法，可在任務(wù)執(zhí)行過程中利用虛擬機(jī)實(shí)時(shí)遷移技術(shù)對虛擬機(jī)進(jìn)行動(dòng)態(tài)調(diào)度，從而實(shí)現(xiàn)科學(xué)工作流在動(dòng)態(tài)執(zhí)行過程中的高能效目標(biāo)。文獻(xiàn)[11]考慮了工作流在執(zhí)行時(shí)的截止時(shí)間約束，提出一種成本與能耗感知的科學(xué)工作流調(diào)度算法。該方法根據(jù)成本效用的概念，通過虛擬機(jī)選擇、序列任務(wù)合并、并行任務(wù)合并、空閑虛擬機(jī)重用等策略來降低工作流執(zhí)行成本與能耗。筆者的前期工作[12]則通過引入物理機(jī)資源利用率預(yù)測等策略，提出一種能耗與成本感知的實(shí)例密集型工作流調(diào)度算法。但是，這些方法主要適用于由一個(gè)云提供者管理或者單個(gè)云數(shù)據(jù)中心構(gòu)成的傳統(tǒng)云計(jì)算環(huán)境。

與傳統(tǒng)云計(jì)算環(huán)境相比，云際協(xié)作環(huán)境中的工作流調(diào)度更具挑戰(zhàn)性，現(xiàn)有研究成果也相對較少。在云際協(xié)作研究方面，《中國計(jì)算機(jī)學(xué)會(huì)通訊》以“云際計(jì)算：面向云際協(xié)作的云計(jì)算”為專題介紹了云際計(jì)算研究情況[1]，文獻(xiàn)[2]提出了云際協(xié)作環(huán)境的體系結(jié)構(gòu)模型。在相關(guān)云工作流調(diào)度研究方面，文獻(xiàn)[13]最早考慮了異構(gòu)多云計(jì)算環(huán)境的特點(diǎn)，提出了兩種動(dòng)態(tài)資源分配算法以執(zhí)行可搶占式任務(wù)并提升云資源利用率。文獻(xiàn)[14]考慮了多個(gè)不同類型工作流應(yīng)用在異構(gòu)多云計(jì)算環(huán)境中的調(diào)度問題，并以最小化完成時(shí)間與最大化云資源利用率為目標(biāo)，提出了3種調(diào)度方法。在此基礎(chǔ)上，文獻(xiàn)[15]進(jìn)一步利用歸一化技術(shù)對這些方法進(jìn)行了改進(jìn)，但是，這些算法均未考慮執(zhí)行任務(wù)所需要的成本問題。對此，文獻(xiàn)[16]以最小化科學(xué)工作流在多云環(huán)境中的執(zhí)行成本為目標(biāo)，利用離散微粒群優(yōu)化等技術(shù)優(yōu)化計(jì)算成本與數(shù)據(jù)跨云傳輸成本，提出一種截止時(shí)間約束下基于元啟發(fā)式策略的科學(xué)工作流調(diào)度方法。文獻(xiàn)[17]則進(jìn)一步綜合考慮了多云環(huán)境下工作流調(diào)度的可靠性約束等因素，以最小化完成時(shí)間與執(zhí)行成本為目標(biāo)，提出一種基于微粒群優(yōu)化的多目標(biāo)科學(xué)工作流調(diào)度方法。但是，這些方法均未考慮如何降低工作流執(zhí)行過程中的能耗，而如何實(shí)現(xiàn)兼顧成本與能耗的云工作流調(diào)度是云際協(xié)作應(yīng)用中的重要問題。為此，本文在上述研究的基礎(chǔ)上，進(jìn)一步提出一種云際協(xié)作環(huán)境下能耗與成本感知的工作流調(diào)度方法。

2 問題描述

2.1 系統(tǒng)模型

定義1一組工作流應(yīng)用。一組工作流應(yīng)用可描述為WS={W1,W2,…,Wi,…,WI}為工作流應(yīng)用集合。Wi為第i個(gè)工作流應(yīng)用，可以描述為Wi=(Ti, CEi,DEi,Di)，其中：

(1)Ti是一組工作流任務(wù)的集合，Ti={tij|tij=〈Iij,Wij,Oij,〉}，Iij、Oij分別為任務(wù)tij的輸入與輸出數(shù)據(jù)集，Wij描述了任務(wù)tij的計(jì)算量大小。

(2)CEi為一組有向邊的集合，用以描述工作流任務(wù)間的控制流依賴情況，CEi={〈tia,tib〉|〈tia,tib〉∈Ti×Ti}；若〈tia,tib〉∈CEi，則稱tia為tib的前驅(qū)任務(wù)，稱tib為tia的后繼任務(wù)，任務(wù)tia的前驅(qū)任務(wù)集合可以表示為pre(tia)，它的后繼任務(wù)集合可以表示為succ(tia)；沒有前驅(qū)任務(wù)的工作流任務(wù)被稱為開始任務(wù)，它可以表示為ti, entry。沒有后繼任務(wù)的工作流任務(wù)被稱為結(jié)束任務(wù)，它可以表示為ti, exit。

(3)DEi為工作流任務(wù)間的傳遞數(shù)據(jù)的集合，它可以表示為DEi={dei,ab|〈tia,tib〉∈CEi}，其中dei,ab為任務(wù)tia向tib傳遞的數(shù)據(jù)量大小。

(4)Di為工作流的截止時(shí)間。

定義2云服務(wù)提供者。一組云服務(wù)提供者可描述為PRO={pro1,pro2,…,prom,…,proM}。

定義3云數(shù)據(jù)中心。云服務(wù)提供者prom(1≤m≤M)所提供的云數(shù)據(jù)中心可表示為DCm={dcm,n|1≤n≤N}，其中dcm,n表示云服務(wù)提供者prom的第n個(gè)數(shù)據(jù)中心。

定義4物理機(jī)資源。云數(shù)據(jù)中心dcm,n所提供的物理機(jī)資源可表示為PMm,n={pmm,n,p|cpm,n,p,ωm,n,p,1≤p≤P}，其中pmm,n,p表示云數(shù)據(jù)中心dcm,n的第p臺(tái)物理機(jī)，cpm,n,p表示物理機(jī)pmm,n,p的計(jì)算能力，ωm,n,p為物理機(jī)pm,n,p的運(yùn)行時(shí)間。

定義5虛擬機(jī)資源。云服務(wù)提供者prom可提供不同租賃價(jià)格與配置的虛擬機(jī)類型，可表示為VMm={vmm,k|vmm,k=〈vcpm,k,ctm,k,cm,k〉, 1≤k≤K}，其中vmm,k表示云服務(wù)提供者prom提供的第k類虛擬機(jī)資源，vcpm,k表示vmm,k的計(jì)算能力，ctm,k表示vmm,k的計(jì)價(jià)時(shí)間單位，cm,k表示vmm,k單位時(shí)間內(nèi)的收費(fèi)。

2.2 能耗計(jì)算模型

工作流執(zhí)行過程中的總能耗E可表示為物理機(jī)能耗Eexe與傳輸能耗Etra兩部分：

E=Eexe+Etra

(1)

基于筆者的前期工作[12]，物理機(jī)pmm,n,p產(chǎn)生的能耗Em,n,p可按式(2)和式(3)進(jìn)行計(jì)算：

(2)

(3)

其中:PEm,n,p(t)為物理機(jī)pmm,n,p在時(shí)間t的能耗率；usm,n,p表示物理機(jī)pmm,n,p在t時(shí)刻的CPU利用率；bem,n,p表示物理機(jī)pmm,n,p的基礎(chǔ)能耗；αm,n,p是一個(gè)常數(shù)，αm,n,p=bem,n,p/7。

在傳輸能耗的計(jì)算方面，為簡化問題，本文不考慮同一物理機(jī)中虛擬機(jī)之間數(shù)據(jù)通信所產(chǎn)生的能耗。同一數(shù)據(jù)中心內(nèi)不同物理機(jī)之間數(shù)據(jù)通信所產(chǎn)生的能耗CEsd，不同的數(shù)據(jù)中心間數(shù)據(jù)通信所產(chǎn)生的能耗CEdd可分別按式(4)和式(5)進(jìn)行計(jì)算：

(4)

(5)

其中：dam,n、bwm,n和?m,n分別表示數(shù)據(jù)中心dcm,n中物理機(jī)之間的數(shù)據(jù)通信量、通信帶寬及數(shù)據(jù)傳輸能耗率；DAmn,m′n′、BWmn,m′n′和ηmn,m′n′分別表示數(shù)據(jù)中心dcm,n與數(shù)據(jù)中心dcm′,n′之間的數(shù)據(jù)通信量、通信帶寬及數(shù)據(jù)傳輸能耗率。

綜上所述，工作流執(zhí)行過程中所耗費(fèi)的物理機(jī)能耗Eexe與傳輸能耗Etra可表示為：

(6)

Etra=CEsd+CEdd。

(7)

2.3 工作流完成時(shí)間計(jì)算模型

(8)

(9)

(10)

因此，工作流Wi的完成時(shí)間可通過式(9)計(jì)算其結(jié)束任務(wù)ti,exit的完成時(shí)間獲得。

2.4 云資源使用成本模型

用戶執(zhí)行工作流的成本主要包括虛擬機(jī)的租賃成本costrent與數(shù)據(jù)傳輸成本costtrans，可表示為：

cost=costrent+costtrans。

(11)

按照云服務(wù)提供者的定價(jià)方式，虛擬機(jī)的租賃成本可以表示為：

(12)

(13)

執(zhí)行工作流所需數(shù)據(jù)傳輸成本costtrans可以表示為：

(14)

(15)

3 能耗與成本感知的云工作流調(diào)度算法

3.1 算法介紹

在云際協(xié)作環(huán)境中，將工作流在不同云中執(zhí)行有助于應(yīng)對突發(fā)峰值業(yè)務(wù)需求，并可兼顧云資源租賃成本與能耗，但需要滿足工作流截止時(shí)間約束。為此，本文提出一種云際協(xié)作環(huán)境下能耗與成本感知的工作流調(diào)度方法(Energy and COst aware workflow scheduling in joint cloud cooperation environment, ECO)。該算法的基本思想是根據(jù)截止時(shí)間約束，將工作流任務(wù)分組后再分配資源，以減少能耗與成本。其中，關(guān)鍵路徑與任務(wù)組是該算法的重要概念，具體定義如下：

定義7工作流路徑。工作流路徑是工作流中一個(gè)連通的子圖。給定一個(gè)工作流Wi, 其工作流路徑集合可描述為SPwi={spi,j|spi,j=〈STi,j,SCEi,j,sti,j,entry,sti,j,exit〉,STi,j?Wi.Ti,SCEi,j?Wi.CEi,sti,j,entry∈STi,j,sti,j,exit∈STi,j}，其中sti,j,entry與sti,j,exit分別為該路徑中的開始任務(wù)與結(jié)束任務(wù)。

基于上述定義，ECO算法的主要步驟可用算法1進(jìn)行描述。

算法1ECO算法。

輸入:PM: 物理機(jī)資源，

VM: 虛擬機(jī)資源，

WS: 一組工作流應(yīng)用，

DC: 一組云數(shù)據(jù)中心，

PRO: 一組云服務(wù)提供者，

RC:一組虛擬機(jī)資源位置記錄；

輸出: 資源調(diào)度結(jié)果。

1: for each Wi∈WS

2: {Wi,un=Wi,dc=NULL, pro=NULL

3: while Wi,un≠?do

4: {select the critical path spi,cpin Wi,un, and add all the tasks in spi,cpto nt

5: if ti,exitin Wi,unthen

6: Dnt=Di

7: else

9: if VMReuse(nt,RC,Dnt,dc)==Failed then

10:if dc==NULL then

11:AssignVM_PM_DC_PRO (nt,PRO, DC, PM,VM, RC, Dnt,dc,pro)

12:else

13: AssignVM_PM (nt,PRO, DC, PM, VM, RC, Dnt,dc,pro)

14: Wi,un=Wi,un- spi,cp}

15: }

ECO算法的主要步驟如下：

步驟1(語句1～2)對每一個(gè)待調(diào)度的工作流Wi，首先為其生成一個(gè)臨時(shí)工作流Wi,un，然后設(shè)置其所分配的虛擬機(jī)資源所屬的數(shù)據(jù)中心dc與云服務(wù)提供者pro等信息，以便后續(xù)操作。

步驟2(語句3～8)從臨時(shí)工作流Wi,un中挑選出一條關(guān)鍵路徑spi,cp，根據(jù)該關(guān)鍵路徑生成一個(gè)任務(wù)組nt，并計(jì)算任務(wù)組的最晚完成時(shí)間Dnt。其中，對于Wi,un生成的第一個(gè)任務(wù)組，Dnt設(shè)置為Wi,un的截止時(shí)間Di；其他任務(wù)組則通過已分配資源的后繼任務(wù)的最晚開始時(shí)間計(jì)算得出Dnt。語句8中，LST(tia)為任務(wù)tia的最晚開始時(shí)間，succ(nt)為任務(wù)組nt的后繼任務(wù)集，即succ(nt)={succ(tij)|tij∈nt}。

步驟3(語句9)嘗試通過復(fù)用空閑虛擬機(jī)為任務(wù)組分配資源，如果不能復(fù)用，則進(jìn)入步驟4。復(fù)用空閑虛擬機(jī)的具體步驟為：

首先生成尚存在空閑時(shí)間、可復(fù)用的虛擬機(jī)候選集，并限制同一工作流的任務(wù)只能復(fù)用同一數(shù)據(jù)中心dc中的虛擬機(jī)；然后，在滿足任務(wù)組的最晚完成時(shí)間約束下，從虛擬機(jī)候選集中選擇執(zhí)行成本最低的虛擬機(jī)進(jìn)行復(fù)用。

步驟4(語句10～13)通過資源動(dòng)態(tài)管理，為任務(wù)組nt分配合適的虛擬機(jī)。具體步驟為：

首先判斷當(dāng)前數(shù)據(jù)中心dc信息是否為空，如果為空則執(zhí)行AssignVM_PM_DC_PRO子過程(語句11)，即根據(jù)不同云服務(wù)提供商所提供的虛擬機(jī)類型與租賃費(fèi)用、不同數(shù)據(jù)中心中物理機(jī)的負(fù)載與能耗情況以及任務(wù)組的最晚完成時(shí)間約束，選擇或創(chuàng)建一個(gè)成本最低的虛擬機(jī)，并確定其所屬的物理機(jī)(其能耗最低)、數(shù)據(jù)中心dc與云服務(wù)提供者pro等信息，更新或新增相關(guān)虛擬機(jī)資源位置記錄，然后將該虛擬機(jī)分配給任務(wù)組nt。

如果當(dāng)前數(shù)據(jù)中心dc信息不為空，則執(zhí)行AssignVM_PM子過程(語句13)。具體步驟為：首先嘗試在數(shù)據(jù)中心dc中，根據(jù)任務(wù)組的最晚完成時(shí)間約束、物理機(jī)的負(fù)載情況，選擇或創(chuàng)建一個(gè)成本最低的虛擬機(jī)，并確定其所屬的物理機(jī)；如果數(shù)據(jù)中心dc中無合適的虛擬機(jī)或物理機(jī)(即數(shù)據(jù)中心dc能提供的虛擬機(jī)無法滿足最晚完成時(shí)間約束，或者物理機(jī)已滿負(fù)荷)，則調(diào)用AssignVM_PM_DC_PRO子過程。

步驟5(語句14)從Wi,un中刪除包含在當(dāng)前關(guān)鍵路徑spi,cp中的任務(wù)與邊，以便生成下一個(gè)任務(wù)組。

3.2 算法復(fù)雜度介紹

算法一共分為5個(gè)步驟，步驟1的算法復(fù)雜度為O(J)，其中J為工作流的任務(wù)數(shù)；步驟2的最壞算法復(fù)雜度為O(J×J!);步驟3的最壞算法復(fù)雜度為O(MNKJ);步驟4的最壞情況為先嘗試數(shù)據(jù)中心的虛擬機(jī)，失敗后調(diào)用AssignVM_PM_DC_PRO子過程，嘗試數(shù)據(jù)中心虛擬機(jī)的算法復(fù)雜度為O(K)，AssignVM_PM_DC_PRO子過程的算法復(fù)雜度為O((MNK)2);步驟5的算法復(fù)雜度為O(J)。因此，總體的最壞算法復(fù)雜度為O(I(J×J!+MNKJ+(MNK)2))。

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

為分析和評估本文提出的ECO算法的性能。假設(shè)各個(gè)數(shù)據(jù)中心均使用3種不同規(guī)格的物理機(jī)器來構(gòu)建云仿真環(huán)境，參照文獻(xiàn)[18]中的實(shí)驗(yàn)方案，設(shè)置了3個(gè)云服務(wù)提供商、共15種不同類型的虛擬機(jī)實(shí)例進(jìn)行仿真實(shí)驗(yàn)，詳細(xì)參數(shù)如表1～表3所示。實(shí)驗(yàn)時(shí)設(shè)置各個(gè)數(shù)據(jù)中心均使用3種不同規(guī)格的物理機(jī)，物理機(jī)的具體結(jié)構(gòu)和相關(guān)的能耗設(shè)置如表4所示。每個(gè)云服務(wù)提供者均擁有3個(gè)數(shù)據(jù)中心，數(shù)據(jù)中心內(nèi)部帶寬為200 MB/s，屬于同一云服務(wù)提供者的不同數(shù)據(jù)中心之間的數(shù)據(jù)傳輸帶寬為100 MB/s，屬于不同云服務(wù)提供者的數(shù)據(jù)中心之間的數(shù)據(jù)傳輸帶寬為50 MB/s。

此外，實(shí)驗(yàn)中使用的4種不同的工作流如圖1所示，這些工作流實(shí)例的到達(dá)時(shí)間服從泊松分布且λ=0.01，任務(wù)所需的計(jì)算量大小服從范圍[10 000,50 000] MIPS的均勻分布。而且，參照文獻(xiàn)[17]中的設(shè)置，任務(wù)輸入/輸出數(shù)據(jù)的大小服從[50,350] MB的均勻分布。

表1 云服務(wù)提供商1虛擬機(jī)實(shí)例參數(shù)設(shè)置

表2 云服務(wù)提供商2虛擬機(jī)實(shí)例參數(shù)設(shè)置

表3 云服務(wù)提供商3虛擬機(jī)實(shí)例參數(shù)設(shè)置

表4 物理機(jī)參數(shù)設(shè)置

為評估ECO算法的性能，選用以下5個(gè)算法作為對比算法：

(1)在線多工作流調(diào)度框架[19](onliNe multi-workflOw Scheduling Framework，NOSF)。通過采用本文中的能耗計(jì)算模型，ECO算法與該算法比較執(zhí)行工作流所需成本與能耗。

(2)能耗感知的虛擬機(jī)調(diào)度方法[20](Energy-aware VM Scheduling method，EVMS)。該算法參數(shù)設(shè)置與文獻(xiàn)[20]相同，ECO算法與該算法比較所需能耗。

(3)改進(jìn)的微粒群優(yōu)化算法[21](Improved Particle Swarm Optimization， Improved PSO)。該算法參數(shù)設(shè)置與文獻(xiàn)[21]相同，ECO算法與該算法比較所需能耗。

(4)異構(gòu)計(jì)算環(huán)境下最早完成時(shí)間算法[22](Heterogeneous Earliest-Finish-Time algorithm，HEFT)與異構(gòu)計(jì)算環(huán)境下多目標(biāo)最早完成時(shí)間算法[22](Multi-Objective Heterogeneous Earliest-Finish-Time algorithm，MOHEFT)。這兩種算法的參數(shù)設(shè)置均與文獻(xiàn)[22]相同，ECO算法與其比較所需成本。

4.2 對比實(shí)驗(yàn)結(jié)果

如圖2所示為在工作流實(shí)例數(shù)量變化的條件下各算法性能比較實(shí)驗(yàn)結(jié)果。由圖2a能耗對比可以看出，ECO算法比其他算法在節(jié)能方面的性能優(yōu)于其他算法，這是因?yàn)镮mproved PSO算法與EVMS算法雖然為任務(wù)找到了合適的虛擬機(jī)類型，但未考慮虛擬機(jī)復(fù)用，虛擬機(jī)的計(jì)算資源閑置導(dǎo)致資源浪費(fèi)；NOSF算法雖然考慮到了虛擬機(jī)復(fù)用，但是忽略了輸出數(shù)據(jù)集對算法性能的影響。由圖2b成本對比可以看出，ECO算法在降低或節(jié)約成本方面也優(yōu)于其他對比算法。而且，通過圖2中的實(shí)驗(yàn)結(jié)果可知，隨著所調(diào)度的工作流實(shí)例數(shù)量的增長，ECO算法相對其他算法在降低能耗與成本方面的效果越明顯。

圖3展示了在不同的數(shù)據(jù)中心資源利用率情況下各算法性能比較實(shí)驗(yàn)結(jié)果。其中，60%的初始資源利用率意味著在待調(diào)度的工作流任務(wù)未到達(dá)數(shù)據(jù)中心之前，已有60%的物理機(jī)資源被占用。從結(jié)果對比可以看出，隨著數(shù)據(jù)中心初始資源利用率變高，任務(wù)不能在同一數(shù)據(jù)中心處理的概率的越高，因此所有算法的結(jié)果曲線的增長速率一直在增長，但可以看出ECO算法是增長最緩慢的，這是因?yàn)镋CO中的任務(wù)組選擇策略將多個(gè)連續(xù)任務(wù)交由同一虛擬機(jī)執(zhí)行，大大減少了數(shù)據(jù)傳輸損耗。值得一提的是HEFT算法的執(zhí)行花費(fèi)不會(huì)隨著數(shù)據(jù)中心初始資源利用率變化，這是因?yàn)镠EFT算法為每個(gè)任務(wù)分配的最高級的虛擬機(jī)，所以虛擬機(jī)存在大量空閑時(shí)間可用于跨數(shù)據(jù)中心的數(shù)據(jù)傳輸，則執(zhí)行花費(fèi)不變。而且，通過圖3中的實(shí)驗(yàn)結(jié)果可知，隨著數(shù)據(jù)中心利用率的增長，ECO算法相對其他算法在降低能耗與成本方面的效果越明顯。

圖4展示了在不同規(guī)模的工作流任務(wù)輸出數(shù)據(jù)量情況下各算法性能比較實(shí)驗(yàn)結(jié)果。由圖4a能耗對比可以看出，EVMS和PSO算法隨任務(wù)平均輸出數(shù)據(jù)量的增大變化較小，這是因?yàn)樗鼈儧]有虛擬機(jī)復(fù)用策略導(dǎo)致虛擬機(jī)存在空閑時(shí)間，而輸出數(shù)據(jù)量增大時(shí)所形成的傳輸數(shù)據(jù)的時(shí)間可以由這些虛擬機(jī)的空閑時(shí)間完成。而且，ECO算法結(jié)果曲線比NOSF算法更為平緩。這說明ECO算法中的任務(wù)組選擇策略能有效降低由數(shù)據(jù)傳輸導(dǎo)致的能源與成本。由圖4b對比可以看出相似的規(guī)律。

5 結(jié)束語

針對如何在云際協(xié)作環(huán)境中高效實(shí)現(xiàn)兼顧成本與能耗的云工作流調(diào)度問題，本文在前期研究工作的基礎(chǔ)上，建立了該問題對立的工作流調(diào)度模型，并設(shè)計(jì)了一種云際協(xié)作環(huán)境下能耗與成本感知的工作流調(diào)度方法ECO。在今后的工作中，將結(jié)合數(shù)據(jù)中心資源利用率預(yù)測方法，進(jìn)一步研究云工作流節(jié)能調(diào)度問題。