面向虛擬化云數(shù)據(jù)中心的工作流聯(lián)合調(diào)度算法研究

董明剛，范 培，閉玉申，敬 超，3

1(桂林理工大學(xué) 信息科學(xué)與工程學(xué)院，廣西 桂林 541004)2(嵌入式技術(shù)與智能系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)3(可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

E-mail：jingchao@glut.edu.cn

1 引 言

虛擬化技術(shù)是云數(shù)據(jù)中心的核心技術(shù)之一，良好的資源及調(diào)度方法有利于云數(shù)據(jù)中心的虛擬資源管理從而提供快速、安全和可靠的服務(wù).隨著云計(jì)算技術(shù)的不斷成熟和進(jìn)步，基于該技術(shù)的數(shù)據(jù)中心也隨之發(fā)展，其中虛擬化技術(shù)是數(shù)據(jù)中心的關(guān)鍵技術(shù)之一，它能夠?qū)ΜF(xiàn)有的資源進(jìn)行整合，提高服務(wù)器與存儲的利用率，讓用戶對新硬件設(shè)備的增長需求速度放緩，進(jìn)而提高資源的利用率[1-3].由此可見，設(shè)計(jì)合理的方法對虛擬化資源進(jìn)行管理有著重要的意義.

傳統(tǒng)的虛擬化資源管理主要是針對虛擬機(jī)部署的性能優(yōu)化問題[4]，它主要包括將工作流分配到虛擬機(jī)，優(yōu)化虛擬機(jī)部署后工作流的時(shí)延問題[5].還有的研究只是關(guān)注了數(shù)據(jù)中心的資源利用率和高能耗問題，如劉寧等人[6]提出了一種新穎的分層框架，通過強(qiáng)化學(xué)習(xí)進(jìn)行虛擬機(jī)資源分配和有效的動(dòng)態(tài)電源管理策略解決資源調(diào)度過程中高功耗的問題，但是這種方法忽略了數(shù)據(jù)中心費(fèi)用優(yōu)化問題.

針對這一問題，Tong等人[7]提出一種基于強(qiáng)化學(xué)習(xí)的云工作流調(diào)度算法，用Q-learning算法對任務(wù)進(jìn)行預(yù)處理，獲得更加合理的任務(wù)序列，對任務(wù)進(jìn)行分配時(shí)，使用線性加權(quán)法有效的將工作流分配給合適的虛擬機(jī)，完成了優(yōu)化工作流的完成時(shí)間和用戶的費(fèi)用，達(dá)到了同時(shí)優(yōu)化多目標(biāo)的問題.Cheng等人[8]提出一種降低資源成本的算法，主要通過深度強(qiáng)化學(xué)習(xí)算法，從不斷變化的環(huán)境中學(xué)習(xí)進(jìn)而自動(dòng)生成一個(gè)長期決策，使得在保持能源效益的同時(shí)運(yùn)行時(shí)間極大的縮短，節(jié)省開銷.范利利等人[9]為了提高異構(gòu)云計(jì)算系統(tǒng)的處理效率，減少費(fèi)用開銷，在考慮了云環(huán)境的異構(gòu)性、任務(wù)的截止時(shí)間、傳輸開銷的情況下，提出一種基于自學(xué)習(xí)策略和近鄰啟發(fā)機(jī)制的粒子群任務(wù)調(diào)度算法，能夠有效縮短工作流執(zhí)行時(shí)間，減少開銷.

縱觀這些研究可以發(fā)現(xiàn)目前虛擬機(jī)部署問題，主要關(guān)注的是以優(yōu)化費(fèi)用為目的[10，11]，解決工作流到虛擬機(jī)的映射問題，而沒有考慮映射完成后虛擬機(jī)到物理機(jī)的調(diào)度問題，即工作流聯(lián)合調(diào)度問題.這是因?yàn)橄啾扔趥鹘y(tǒng)的虛擬機(jī)部署問題，聯(lián)合調(diào)度問題更加復(fù)雜，因?yàn)樗婕暗搅斯ぷ髁?，虛擬機(jī)以及物理機(jī)三者的資源協(xié)調(diào)問題.雖然Guo等人[12]做了聯(lián)合調(diào)度的研究，但是他們主要是利用影子算法指導(dǎo)實(shí)際的應(yīng)用程序到虛擬機(jī)到物理機(jī)上的分配，提出了在云上的應(yīng)用程序-虛擬機(jī)-物理機(jī)在線聯(lián)合調(diào)度算法，并沒有進(jìn)一步考慮到資源調(diào)度過程中產(chǎn)生的費(fèi)用開銷優(yōu)化問題.

鑒于聯(lián)合調(diào)度過程中涉及的資源協(xié)調(diào)以及成本開銷優(yōu)化等問題，因此，本文的主要工作是以費(fèi)用最小化為目的，在保證工作流執(zhí)行效率的前提下，提出了一種以蟻群系統(tǒng)和貪心算法為核心思想的聯(lián)合調(diào)度方法(A joint workflow scheduling algorithm based on improved Ant-colony system and greed algorithm，IAG).與以往的研究相比，該方法不僅考慮了在虛擬化云數(shù)據(jù)中心的工作流-虛擬機(jī)-物理機(jī)的聯(lián)合調(diào)度問題，而且還考慮了虛擬機(jī)多類型的問題，即同類型虛擬機(jī)在部署到同一臺物理機(jī)時(shí)可以免去部署開銷(如時(shí)間)[13].

本文的工作主要是：首先，通過建立工作流、虛擬機(jī)、物理機(jī)以及云數(shù)據(jù)中心的費(fèi)用模型，對虛擬化云數(shù)據(jù)中心工作流聯(lián)合調(diào)度問題進(jìn)行了形式化的描述；接著，針對提出的優(yōu)化問題，提出了一種二階段的工作流聯(lián)合調(diào)度算法(IAG).該算法主要分為兩步：

1)解決了工作流到虛擬機(jī)的映射問題，以縮短工作流執(zhí)行時(shí)間最小化為目的，提出了一種基于蟻群系統(tǒng)思想的算法；

2)利用貪心算法，考慮虛擬機(jī)的多類型問題，在保證工作流完成時(shí)間的前提下，以費(fèi)用支出最小化為目的，將虛擬機(jī)調(diào)度到物理機(jī).

最后，將提出的IAG算法與傳統(tǒng)調(diào)度FCFS算法、PSO算法以及IPSO算法[14]進(jìn)行對比實(shí)驗(yàn)分析.實(shí)驗(yàn)結(jié)果表明：IAG聯(lián)合調(diào)度算法不僅可以保證工作流的執(zhí)行效率，還降低了費(fèi)用開銷，體現(xiàn)了它的可行性及有效性.

2 問題建模

2.1 云數(shù)據(jù)中心調(diào)度模型

該模型展示了云數(shù)據(jù)中心在處理用戶提交的工作流時(shí)所經(jīng)歷的過程.首先用戶在線提交工作流到云數(shù)據(jù)中心，所有的工作流都會(huì)被緩存到工作流隊(duì)列中，通過調(diào)度器將工作流調(diào)度到數(shù)據(jù)中心生成的虛擬機(jī)中處理，并且隨后虛擬機(jī)會(huì)被以開銷最小化為目的部署到相應(yīng)的物理服務(wù)器上，如圖1所示.

圖1 云數(shù)據(jù)中心處理工作流示意圖Fig.1 Schematic diagram of cloud data center processing workflow

2.2 工作流模型

對于每一種類型的工作流，都有截止時(shí)間Dk，將工作流的模型描述為一個(gè)有向無環(huán)圖G=(ν，ε)，工作流中的任務(wù)集用ν={υ0，υ1，…，υ|Q(k)|-1}表示，表示|Q(k)|工作流K中的總?cè)蝿?wù)數(shù)量.其中K∈[0，H(t)-1]，H(t)表示工作流的總數(shù)量.ε表示任務(wù)之間的依賴關(guān)系，由于任務(wù)Tp和它的子任務(wù)Tq的依賴關(guān)系，定義為W(Tp，Tq).任務(wù)Tq只有在執(zhí)行完任務(wù)Tp后才能進(jìn)行.Tlength_i表示任務(wù)υi的數(shù)據(jù)量大小.工作流模型如圖2所示.

圖2 工作流模型Fig.2 Workflow model

2.3 云數(shù)據(jù)中心虛擬機(jī)模型

假設(shè)云數(shù)據(jù)中心里虛擬機(jī)的數(shù)量為N，用V={V1，V2，…，VN}表示.每個(gè)虛擬機(jī)資源需求為CPU、內(nèi)存、帶寬，分別用Vcj，Vmj，Vbwj，j∈N表示.每個(gè)虛擬機(jī)在部署到物理機(jī)時(shí)會(huì)產(chǎn)生的開銷表示為PmC，若虛擬機(jī)由NT種類型組成，則兩個(gè)同類型的虛擬機(jī)部署到同一物理機(jī)時(shí)，在資源充足的情況下可以避免部署的開銷.虛擬機(jī)的處理能力如公式(1)所示：

VMcomp_j=mips×pes

(1)

任務(wù)的傳輸時(shí)間暫且不考慮在內(nèi)，任務(wù)在虛擬機(jī)上的執(zhí)行時(shí)間如公式(2)所示：

(2)

每個(gè)任務(wù)在虛擬機(jī)上的執(zhí)行時(shí)間就是它的完成時(shí)間：

TRTimeij=etij

每個(gè)工作流的完成時(shí)間：

(3)

虛擬機(jī)上前r個(gè)工作流執(zhí)行時(shí)間：

(4)

由于虛擬機(jī)并行執(zhí)行的工作特性，工作流最終完成時(shí)間是最后一臺虛擬機(jī)執(zhí)行完工作流的時(shí)間，如公式(5)所示：

WFFTime=max(vmcomptime_j)，j∈[1，n]

(5)

2.4 云數(shù)據(jù)中心物理機(jī)模型

假設(shè)云數(shù)據(jù)中心中物理機(jī)的數(shù)量為M表示為P={1，2，3…M}，每個(gè)物理機(jī)的資源需求為CPU、內(nèi)存、帶寬，分別用Pci，Pmi，Pbwi，i∈P表示，其中物理機(jī)中的資源要滿足虛擬機(jī)中資源的需求.調(diào)度策略中的物理機(jī)資源需要滿足條件如下：其中X表示鄰接矩陣，若VMj放置在物理機(jī)Pi上，則Xij等于1，否則Xij等于0.

(6)

其中yi表示物理機(jī)數(shù)量.

(6a)

(6b)

(6c)

(6d)

2.5 云數(shù)據(jù)中心成本開銷模型

2.5.1 時(shí)間約束

時(shí)間約束分為兩部分:第1部分為工作流的執(zhí)行時(shí)間，第2部分為物理機(jī)的部署資源時(shí)間.其中物理機(jī)部署資源的啟動(dòng)、結(jié)束時(shí)間分別為Tstart、Toff.每個(gè)虛擬機(jī)部署資源的時(shí)間集合為：PT={T1，T2，T3…}.

其中工作流執(zhí)行時(shí)間約束函數(shù)如公式(7)所示：

(7)

WFFTimemax、WFFTimemin分別表示任務(wù)在處理能力最差、最好的虛擬機(jī)上的執(zhí)行時(shí)間.即Time_1=T_Time(I).物理機(jī)上部署資源時(shí)間如公式(8)所示：

Time_2=Tstart+T1+T2+…+Toff

(8)

物理機(jī)部署資源時(shí)，利用貪心算法先對需求資源大的虛擬機(jī)進(jìn)行資源部署，當(dāng)后續(xù)到達(dá)虛擬機(jī)與前一個(gè)虛擬機(jī)類型相同且所需資源小于前一個(gè)虛擬機(jī)時(shí)，則不需要重新為其部署資源，節(jié)省了部署虛擬機(jī)的開銷，同時(shí)能夠盡可能將資源類型相同的虛擬機(jī)優(yōu)先部署到同一臺物理機(jī)上.其中物理機(jī)啟動(dòng)時(shí)間如公式(9)所示：

Tstart(i)=lnPmi

(9)

將Toff設(shè)置為啟動(dòng)時(shí)間的一半.聯(lián)合調(diào)度的總時(shí)間如公式(10)所示：

f(t)=Time_1+Time_2

(10)

2.5.2 成本開銷問題

不同類型的虛擬機(jī)所需的單位費(fèi)用與它的CPU、內(nèi)存、帶寬資源相關(guān)，記為Vcostj.當(dāng)所有工作流執(zhí)行完成后，虛擬機(jī)所需費(fèi)用如公式(11)所示：

(11)

物理機(jī)的單位費(fèi)用同樣與其CPU、內(nèi)存、帶寬資源相關(guān)，記為Pcosti，物理機(jī)的所需的費(fèi)用開銷如公式(12)所示：

(12)

其中Tstart>0，Toff>0，聯(lián)合調(diào)度的總費(fèi)用表示為：

F(c)=TC+PmC

(13)

2.6 問題定義

本文主要工作是以費(fèi)用最小化為目的，在保證工作流執(zhí)行效率的前提下，將虛擬機(jī)在物理機(jī)上進(jìn)行資源部署，從而達(dá)到了對資源的整體聯(lián)合調(diào)度.優(yōu)化目標(biāo)如公式(14)所示：

minsizeF(c)=TC+PmC

(14)

s.t.f(t)≤T

(14a)

3 算法設(shè)計(jì)

3.1 算法基本思想

一方面，針對工作流-虛擬機(jī)的映射問題，在基于蟻群系統(tǒng)的基本思想上，對工作流執(zhí)行時(shí)間和開銷成本建立相關(guān)函數(shù)，縮短了工作流調(diào)度時(shí)的任務(wù)完成時(shí)間.另一方面，針對虛擬機(jī)-物理機(jī)的部署問題，利用貪心算法將多類型的虛擬機(jī)部署到物理機(jī)上，若同類型的虛擬機(jī)部署到同一個(gè)物理機(jī)上時(shí)可以免去部署開銷.通過對這兩層的資源調(diào)度進(jìn)行優(yōu)化，即節(jié)省了時(shí)間，又縮減了整體的費(fèi)用開銷.

3.2 算法設(shè)計(jì)細(xì)節(jié)

3.2.1 初始化相關(guān)參數(shù)

對蟻群系統(tǒng)中的啟發(fā)函數(shù)、信息素、和信息素轉(zhuǎn)移規(guī)則進(jìn)行初始化.

(15)

τ0表示任務(wù)到虛擬機(jī)路徑上信息素的初始化值.其中VMavg_comp表示虛擬機(jī)的平均計(jì)算能力，如公式(16)所示：

(16)

(17)

ηij是啟發(fā)函數(shù)，表示任務(wù)υi在虛擬機(jī)VMj上的執(zhí)行期望強(qiáng)度.其中，LFj是虛擬機(jī)負(fù)載函數(shù)[15]，如公式(18)所示：

LFj=1-((Ej-Eavg)/∑j∈VMEj)

(18)

etij表示任務(wù)υi在虛擬機(jī)VMj上的執(zhí)行時(shí)間.Ej是虛擬機(jī)j的執(zhí)行時(shí)間，Eavg是所有虛擬機(jī)的執(zhí)行時(shí)間的平均時(shí)間.若先不考慮信息素調(diào)整因子，任務(wù)的執(zhí)行時(shí)間越長，則ηij越大.

3.2.2 虛擬機(jī)節(jié)點(diǎn)選擇

螞蟻在選擇下一個(gè)虛擬機(jī)節(jié)點(diǎn)時(shí)，采用了蟻群系統(tǒng)的隨機(jī)轉(zhuǎn)移概率規(guī)則[16]；

(19)

(20)

其中q為[0，1]之間的隨機(jī)數(shù)，q0為固定參數(shù)，α為信息素的啟發(fā)因子，β為期望啟發(fā)因子，allowedk是螞蟻可以為任務(wù)選擇的虛擬機(jī)集合.τij(t)表示t時(shí)刻時(shí)，任務(wù)υi與虛擬機(jī)VMj的映射路徑上的信息素的值.

3.2.3 動(dòng)態(tài)信息素更新

當(dāng)螞蟻為所有任務(wù)進(jìn)行分配后，對其映射路徑上的局部信息素進(jìn)行更新：

a)局部信息素更新規(guī)則

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)

(21)

公式(21)中ρ表示信息素?fù)]發(fā)因子，(1-ρ)表示信息素的殘留度，ρ的值范圍是(0，1]，若ρ越大，則表示信息素?fù)]發(fā)的越快，殘留度越小.Δτij(t)是在t時(shí)刻時(shí)，任務(wù)υi與虛擬機(jī)VMj的映射路徑上的信息素增量.

(22)

其中D為螞蟻完成一輪尋解后的時(shí)間與成本函數(shù)值，表達(dá)式為D=ι1Time_1+ι2TC，ι1、ι2分別為時(shí)間函數(shù)和成本函數(shù)的權(quán)重因子，取值范圍是[0，1].Uk(t)表示第k只螞蟻在第t次的迭代尋解.

b)全局信息素更新規(guī)則

當(dāng)所有螞蟻完成一輪迭代尋解后，得到本次迭代尋解的最佳方案，然后將局部最佳的信息素設(shè)置為全局信息素.

(23)

其中Dbest為螞蟻到目前迭代尋解中的最優(yōu)解.

3.2.4 算法及時(shí)間復(fù)雜度分析

在算法1中，首先初始化所需的各項(xiàng)參數(shù)(行1-3)，為任務(wù)匹配最佳的虛擬機(jī)并更新局部信息素(行4-10)，更新全局信息素，并獲得最佳匹配方案(行11-17).

在算法2中，首先將所需資源最大的虛擬機(jī)優(yōu)先部署到物理機(jī)上(行1-3)，將后續(xù)到達(dá)的虛擬機(jī)與前一個(gè)虛擬機(jī)進(jìn)行類型與資源比較，并為其部署資源(行4-12).

算法1.

輸入：工作流中的任務(wù)總數(shù)TASK_NUM，虛擬機(jī)數(shù)量，物理機(jī)數(shù)量，螞蟻數(shù)量ANT_NUM，迭代次數(shù)I_NUM，揮發(fā)因子，啟發(fā)因子α，啟發(fā)因子β，偽隨機(jī)狀態(tài)轉(zhuǎn)移參數(shù)q0.

輸出：工作流與虛擬機(jī)匹配方案

1.Begin

2. 初始化虛擬機(jī)計(jì)算能力，虛擬機(jī)計(jì)算費(fèi)用，期望執(zhí)行時(shí)間，全局

3. 信息素，螞蟻列表，全局匹配方案.

4. ForD=1 toI_NUM

5. ForN=1 toANT_NUM

6. ForT=1 toTASK_NUM

7. 螞蟻根據(jù)偽隨機(jī)狀態(tài)轉(zhuǎn)移公式，選擇最合適的虛擬機(jī).

8.

9. End

10. 更新局部信息素.

11. End

12. 計(jì)算并選擇最佳的螞蟻.

13. 用最佳螞蟻的局部信息素，來更新全局信息素.

14. 選擇最佳螞蟻的匹配方案，來更新全局匹配方案.

15. 初始化螞蟻列表.

16. End

17.End

輸出結(jié)果：工作流與虛擬機(jī)匹配方案

算法2.

輸入：虛擬機(jī)數(shù)量VM_NUM，虛擬機(jī)類型Type，虛擬機(jī)內(nèi)存RAM，物理機(jī)現(xiàn)存資源數(shù)據(jù)

輸出：虛擬機(jī)與物理機(jī)部署方案

1.Begin

2. Fori=1 toVM_NUM

3. 找出現(xiàn)有資源最大的物理機(jī).

4. 獲取物理機(jī)上最新部署的虛擬機(jī)VM_i的類型Type_i，所

5. 需內(nèi)存大小RAM_i.

6. IfType_i+1不等于Type_i或RAM_i+1大于RAM_i

7. 在該物理機(jī)上重新為VM_i+1部署資源.

8. Else

9. 將VM_i+1直接放置到該物理機(jī)上.

10. End

11. End

12.End

輸出結(jié)果：虛擬機(jī)與物理機(jī)部署方案

假設(shè)工作流中的任務(wù)數(shù)量為T，虛擬機(jī)數(shù)量為S，且任務(wù)的數(shù)量T大于虛擬機(jī)資源的數(shù)量S(T>S)，迭代次數(shù)為R，螞蟻數(shù)量為N.本文提出的IAG算法的時(shí)間復(fù)雜度主要分為兩部分：1)利用改進(jìn)的蟻群系統(tǒng)算法解決工作流到虛擬機(jī)上的映射問題，即算法1的時(shí)間復(fù)雜度為O(R·T·N).2)將貪心算法應(yīng)用到虛擬機(jī)到物理機(jī)的部署問題上，即算法2的時(shí)間復(fù)雜度為O(S).

4 實(shí)驗(yàn)?zāi)M

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

本文在Cloudsim-3.0.3云計(jì)算仿真平臺進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證提出算法的有效性.

表1 實(shí)驗(yàn)參數(shù)配置Table 1 Experimental parameter configuration

測試中的參數(shù)配置如表1所示.本文采用CyberShake、Montage、LIGO、SIPHT等數(shù)據(jù)集上任務(wù)數(shù)量為100，200的2組任務(wù)進(jìn)行實(shí)驗(yàn)，迭代100次后得出最佳結(jié)果，并與FCFS算法、PSO算法、IPSO算法對比，為確保實(shí)驗(yàn)結(jié)果的有效性，每種算法進(jìn)行獨(dú)立實(shí)驗(yàn)10次，取其平均值，對比結(jié)果如圖3所示.

圖3 不同任務(wù)大小下的實(shí)驗(yàn)結(jié)果Fig.3 Experimental results under different task sizes

算法1中涉及到一些參數(shù)設(shè)置，具體如下：α=0.5，β=0.5，ρ=0.2，q0=0.2螞蟻數(shù)量ANT_NUM=20，最大迭代次數(shù)為I_NUM=100.

4.2 實(shí)驗(yàn)結(jié)果分析

由圖3可以看出，在不同大小的任務(wù)下，IAG算法與IPSO算法、PSO算法、FCFS算法相比較，在聯(lián)合調(diào)度的資源開銷方面均有明顯的優(yōu)勢.由圖3(a)、圖3(b)可以看出，當(dāng)任務(wù)數(shù)量為100和200時(shí)，在數(shù)據(jù)集CyberShake、Montage、LIGO、SIPHT上，IAG算法在費(fèi)用這一指標(biāo)上明顯優(yōu)于其他算法.其中當(dāng)任務(wù)數(shù)量為100時(shí)，在LIGO這一數(shù)據(jù)集上，IAG算法的開銷為3116，而IPSO算法、PSO算法、FCFS算法的開銷分別是3125、3126、3125.當(dāng)任務(wù)數(shù)量為200時(shí)，IAG算法表現(xiàn)更為顯著，IAG算法的開銷為5405，而IPSO算法、PSO算法、FCFS算法的開銷分別是5442，5443，5443.這是由于提出的IAG算法將蟻群系統(tǒng)進(jìn)行改進(jìn)，對工作流執(zhí)行時(shí)間和開銷成本建立相關(guān)函數(shù)，同時(shí)采用蟻群算法加快對虛擬機(jī)的搜尋，將工作流中的任務(wù)匹配給更適合的虛擬機(jī)，從而提高任務(wù)的完成時(shí)間，另一方面，在將虛擬機(jī)部署到物理機(jī)上時(shí)，該算法針對同類型的虛擬機(jī)的部署可以免去部署開銷，節(jié)省部署時(shí)間.而IPSO算法、PSO算法相較于FCFS算法能夠在執(zhí)行時(shí)間和費(fèi)用開銷方面有明顯提升，但是，由于虛擬機(jī)在物理機(jī)上進(jìn)行部署時(shí)，以上算法是針對同類型的虛擬機(jī)沒有免去部署時(shí)間，增加了部署時(shí)間與開銷，從而在實(shí)驗(yàn)中顯示出劣勢.

圖4 不同數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果Fig.4 Experimental results under different data sets

圖4為不同數(shù)據(jù)集下的任務(wù)在由6臺物理機(jī)，20臺類型數(shù)為8的虛擬機(jī)構(gòu)成的小型數(shù)據(jù)中心的測試結(jié)果.同樣分別采用了CyberShake、Montage、LIGO、SIPHT數(shù)據(jù)集，任務(wù)量分別為100，200進(jìn)行測試.將由圖4可以看出，在圖4(a)、圖4(b)、圖4(c)中，當(dāng)任務(wù)數(shù)量為100、200時(shí)，在CyberShake、SIPHT、Montage數(shù)據(jù)集上，IAG算法的費(fèi)用開銷在750左右浮動(dòng)，而IPSO算法、PSO算法、FCFS算法在3個(gè)數(shù)據(jù)集上的費(fèi)用在880左右浮動(dòng).同時(shí)在LIGO數(shù)據(jù)集上，IAG算法也明顯優(yōu)于其他算法.因此，在構(gòu)造的小型數(shù)據(jù)中心中，IAG算法在不同任務(wù)大小的數(shù)據(jù)集上表現(xiàn)優(yōu)于IPSO算法、PSO算法、FCFS算法.

表2 任務(wù)為100的完成時(shí)間(s)Table 2 Completion time of task 100

各個(gè)算法在執(zhí)行任務(wù)為100、200的時(shí)間如表2、表3所示，任務(wù)數(shù)量為100時(shí)，IAG算法在CyberShake、Montage、SIPHT上面時(shí)間上均優(yōu)于其他算法，其中在CyberShake上，對比FCFS算法、PSO算法、IPSO算法分別提高了1.45%、1.38%、2.03%；在Montage上，分別提高了2.14%、2.01%、2.16%；在LIGO上，分別提高了1.14%、1.18%、1.58%；在SIPHT上，分別提高了2.26%、2.26%、2.28%.表3可以看出，

表3 任務(wù)為200的完成時(shí)間(s)Table 3 Completion time of task 200

當(dāng)任務(wù)數(shù)量為200時(shí)，IAG算法較其他算法在任務(wù)完成時(shí)間上也有明顯提高.隨著任務(wù)數(shù)量的不斷增加，IAG算法的優(yōu)勢更加明顯，這是因?yàn)槿蝿?wù)數(shù)量的不斷增加，相對應(yīng)的虛擬機(jī)、物理機(jī)數(shù)量也在不斷增多，而對于工作流到虛擬機(jī)上的映射問題，利用改進(jìn)的蟻群系統(tǒng)能夠?yàn)楣ぷ髁髦械娜蝿?wù)更加快速需找到合適的虛擬機(jī)，節(jié)省了時(shí)間；同時(shí)隨著虛擬機(jī)數(shù)量的增多，虛擬機(jī)到物理機(jī)上進(jìn)行部署時(shí)，同類型的虛擬機(jī)的部署也會(huì)節(jié)省更多的時(shí)間和費(fèi)用開銷.

5 結(jié)束語

本文提出一種基于蟻群系統(tǒng)和貪心思想的二階段工作流聯(lián)合調(diào)度算法(IAG)，該算法首先基于現(xiàn)有的蟻群系統(tǒng)算法，以最小化工作流完成時(shí)間為目的，設(shè)計(jì)了啟發(fā)式函數(shù)和信息激素更新規(guī)則，將工作流映射到虛擬機(jī).然后，再以最小化費(fèi)用開銷為目的，保證工作流完成的前提下，提出了一種基于貪心思想的虛擬機(jī)到物理機(jī)的部署方法，該方法主要的特點(diǎn)在于考慮了虛擬機(jī)多類型的特點(diǎn)，從而避免了虛擬機(jī)部署開銷大的問題.最后，通過Cloudsim仿真平臺，以及與 FCFS算法、PSO算法、IPSO算法分別比較，驗(yàn)證了提出IAG算法的有效性和優(yōu)越性.