王巖 汪晉寬 韓英華

(1. 東北大學(xué) 信息科學(xué)與工程學(xué)院, 遼寧 沈陽 110819; 2. 東北大學(xué)秦皇島分校 控制工程學(xué)院, 河北 秦皇島 066004)

面向云工作流的兩階段資源調(diào)度方法*

王巖1汪晉寬1韓英華2

(1. 東北大學(xué) 信息科學(xué)與工程學(xué)院, 遼寧 沈陽 110819; 2. 東北大學(xué)秦皇島分校 控制工程學(xué)院, 河北 秦皇島 066004)

為提高云計(jì)算系統(tǒng)的資源利用率,優(yōu)化系統(tǒng)性能,同時(shí)兼顧用戶的服務(wù)質(zhì)量(QoS)需求約束,文中結(jié)合云計(jì)算和工作流建立了云工作流系統(tǒng),給出了具有兩個(gè)調(diào)度階段的系統(tǒng)資源調(diào)度模型.在第1階段中,考慮了QoS的時(shí)間及價(jià)格約束、工作流內(nèi)各個(gè)任務(wù)之間的依賴關(guān)系以及各個(gè)任務(wù)所產(chǎn)生的中間數(shù)據(jù)的處理,提出了改進(jìn)的粒子群優(yōu)化(MPSO)算法,并利用Pareto獲得最優(yōu)解,以提高調(diào)度效率;在第2階段中,考慮了資源在主機(jī)上的分配情況,提出了具有負(fù)載感知的調(diào)度策略,根據(jù)系統(tǒng)的負(fù)載情況進(jìn)行資源調(diào)度,以提高系統(tǒng)的資源利用率.實(shí)驗(yàn)結(jié)果表明:在云工作流系統(tǒng)的資源優(yōu)化調(diào)度中,與經(jīng)典的異構(gòu)最早完成時(shí)間算法、單目標(biāo)優(yōu)化的遺傳算法相比,MPSO算法的任務(wù)執(zhí)行速度更快、資源利用率更高,能滿足用戶的QoS需求;具有負(fù)載感知的調(diào)度策略能更有效地根據(jù)負(fù)載情況進(jìn)行調(diào)度,提高任務(wù)執(zhí)行的效率和資源利用率.

云計(jì)算;工作流;粒子群算法;負(fù)載感知

隨著云計(jì)算技術(shù)的不斷發(fā)展,分布式工作流系統(tǒng)逐步發(fā)展到云工作流系統(tǒng).云工作流系統(tǒng)充分結(jié)合了云計(jì)算和工作流的優(yōu)點(diǎn),克服了分布式工作流系統(tǒng)在資源管理和作業(yè)調(diào)度方面的缺陷.

實(shí)例密集型工作流[1-3]應(yīng)用的特點(diǎn)是工作流系統(tǒng)中存在大量的實(shí)例,雖然實(shí)例本身較簡(jiǎn)單,但數(shù)量巨大,因此對(duì)調(diào)度算法要求較高,如何合理調(diào)度資源并提高服務(wù)質(zhì)量(QoS)是系統(tǒng)調(diào)度策略的衡量指標(biāo).Liu等[4]提出了一種針對(duì)實(shí)例密集型應(yīng)用的、使得系統(tǒng)吞吐量最大化的調(diào)度策略,該策略在實(shí)例層的調(diào)度算法提高了任務(wù)調(diào)度的系統(tǒng)吞吐量;在任務(wù)層的調(diào)度算法通過擴(kuò)展等待時(shí)間,減少了資源調(diào)度所需時(shí)間,提高了資源利用率,但僅考慮擴(kuò)展了極小(Min-Min)算法,會(huì)因迭代計(jì)算少、非迭代計(jì)算的時(shí)間收斂性較差而導(dǎo)致負(fù)載不均衡的情況發(fā)生.Javadi等[5]提出了一種適用于實(shí)例密集型應(yīng)用的工作流調(diào)度算法,該算法首先對(duì)工作流實(shí)例進(jìn)行分類,將用戶指定的最后期限分配到各個(gè)任務(wù)中,在調(diào)度執(zhí)行時(shí)動(dòng)態(tài)地調(diào)整后續(xù)子任務(wù)的調(diào)度時(shí)間,進(jìn)而優(yōu)化任務(wù)總的執(zhí)行時(shí)間.該算法能夠在一定程度上減少資源競(jìng)爭(zhēng),提高資源利用率,但算法本身沒有考慮子任務(wù)的執(zhí)行時(shí)間.考慮任務(wù)的優(yōu)先執(zhí)行順序,Jrad等[6]針對(duì)實(shí)例密集型工作流調(diào)度問題提出了基于預(yù)演算的調(diào)度算法,能夠在調(diào)度前根據(jù)任務(wù)的優(yōu)先級(jí)排序,按照優(yōu)先級(jí)從高到低的順序提供空閑的資源執(zhí)行.以上研究均是針對(duì)實(shí)例密集型工作流而提出的不同調(diào)度策略,但云計(jì)算環(huán)境下的工作流作為一項(xiàng)服務(wù),關(guān)鍵問題是如何滿足用戶的QoS需求,提供高水平的QoS服務(wù)[7-10].

QoS主要包括時(shí)間、費(fèi)用、可靠性、安全性等因素.人們針對(duì)用戶QoS保障提出了動(dòng)態(tài)地為用戶提供資源，并采用服務(wù)資源遷移的方法進(jìn)行資源管理[11-12].Buyya等[13]提出的最后期限分配算法根據(jù)不同的任務(wù)分類,將用戶指定的QoS限制進(jìn)行劃分并分配給流程任務(wù),然后進(jìn)行分類調(diào)度,但此算法是面向單實(shí)例任務(wù)的調(diào)度,不適合實(shí)例密集型任務(wù)的調(diào)度;文獻(xiàn)[14-15]提出的資源混合調(diào)度算法修正了單一調(diào)度算法的問題,更好地平衡了云計(jì)算環(huán)境中用戶任務(wù)對(duì)性能和價(jià)格的約束,但其將運(yùn)行時(shí)間作為調(diào)度評(píng)價(jià)的標(biāo)準(zhǔn),對(duì)于另一個(gè)用戶關(guān)心的費(fèi)用標(biāo)準(zhǔn)未予以考慮.

云計(jì)算中具有大量的工作流任務(wù),如果沒有整體調(diào)度策略來保障,將會(huì)嚴(yán)重影響整個(gè)系統(tǒng)的性能,導(dǎo)致任務(wù)的QoS沖突.同時(shí),針對(duì)云計(jì)算的面向市場(chǎng)機(jī)制的服務(wù)特征,云計(jì)算環(huán)境中的工作流系統(tǒng)應(yīng)當(dāng)根據(jù)當(dāng)前的資源分配情況、系統(tǒng)負(fù)載情況進(jìn)行流程處理,以提高資源利用率.

因此,文中針對(duì)實(shí)例密集型工作流的任務(wù)調(diào)度,基于QoS性能優(yōu)化,考慮了子任務(wù)的執(zhí)行順序,建立了符合任務(wù)特點(diǎn)的預(yù)調(diào)度模型,提出了具有兩個(gè)調(diào)度階段的系統(tǒng)資源調(diào)度模型.首先考慮基于QoS性能優(yōu)化的工作流預(yù)調(diào)度,提出了改進(jìn)的粒子群優(yōu)化(MPSO)算法,從整體角度對(duì)云工作流系統(tǒng)的執(zhí)行性能進(jìn)行調(diào)度優(yōu)化;然后考慮系統(tǒng)中的負(fù)載,提出了具有負(fù)載感知的任務(wù)調(diào)度策略,從局部角度對(duì)云工作流系統(tǒng)的性能進(jìn)行優(yōu)化.

1 云工作流系統(tǒng)的第1階段調(diào)度

圖1給出了一個(gè)工作流的例子.圖中的di(i=1,2,…,5)表示數(shù)據(jù)集,rij(i=1,2,…,5;j=2,3,4,5)表示任務(wù)節(jié)點(diǎn)之間任務(wù)數(shù)據(jù)的關(guān)聯(lián)關(guān)系.

圖1 工作流示例圖

定理1 設(shè)a1、a2是工作流中兩個(gè)具有相同深度的任務(wù),并且a2晚于a1執(zhí)行,當(dāng)且僅當(dāng)a2的執(zhí)行時(shí)間大于a1的執(zhí)行時(shí)間時(shí),a2才有意義.

定理1的證明見文獻(xiàn)[16].由此得出如下推論.

推論1 在任務(wù)等待執(zhí)行時(shí),若具有相同深度的任務(wù)在執(zhí)行時(shí)出現(xiàn)死鎖,則其等待時(shí)間不能小于同深度任務(wù)的執(zhí)行時(shí)間,以保證整個(gè)工作流的執(zhí)行.

對(duì)于一個(gè)給定的云工作流應(yīng)用,每個(gè)任務(wù)的執(zhí)行都是非搶占的.每個(gè)應(yīng)用任務(wù)ai都需要在一個(gè)云節(jié)點(diǎn)pj上執(zhí)行,云節(jié)點(diǎn)集合為P={p1,p2,…,pj,…,pm},其執(zhí)行時(shí)間表示為tij,該時(shí)間與任務(wù)的大小及節(jié)點(diǎn)的計(jì)算速度相關(guān),tij表示任務(wù)ai的數(shù)據(jù)到達(dá)云節(jié)點(diǎn)pj的時(shí)間,即任務(wù)ai的父任務(wù)產(chǎn)生并發(fā)送到任務(wù)ai的所有數(shù)據(jù)的時(shí)間之和.

定義3 任務(wù)的平均執(zhí)行時(shí)間為

(1)

定義4 任務(wù)的平均通信量為

(2)

(3)

1.1 云工作流模型

在云工作流系統(tǒng)中,調(diào)度問題的關(guān)鍵在于運(yùn)用合理的調(diào)度策略,使得服務(wù)時(shí)間、服務(wù)費(fèi)用最少.因此,文中提出的云工作流的任務(wù)調(diào)度模型由資源及應(yīng)用中心、監(jiān)控中心、處理器、調(diào)度器組成,如圖2所示.

資源及應(yīng)用中心主要管理云計(jì)算環(huán)境下的資源和服務(wù);監(jiān)控中心負(fù)責(zé)對(duì)系統(tǒng)的負(fù)載情況進(jìn)行監(jiān)控;處理器負(fù)責(zé)對(duì)任務(wù)進(jìn)行預(yù)調(diào)度,預(yù)調(diào)度根據(jù)用戶QoS約束,采用合理的調(diào)度算法對(duì)任務(wù)和資源之間的關(guān)系進(jìn)行優(yōu)化,為調(diào)度預(yù)留資源;調(diào)度器感知資源當(dāng)前的負(fù)載情況,預(yù)計(jì)任務(wù)在當(dāng)前調(diào)度中的耗費(fèi),保證任務(wù)在最佳的時(shí)機(jī)被調(diào)度執(zhí)行.云工作流系統(tǒng)在第1階段的調(diào)度步驟如下:

(1)根據(jù)工作流定義搜索資源;

(2)將用戶的QoS目標(biāo)要求分配到任務(wù)中;

(3)選擇最優(yōu)調(diào)度算法;

(4)將工作流任務(wù)調(diào)度到調(diào)度器準(zhǔn)備執(zhí)行.

圖2 云工作流系統(tǒng)任務(wù)調(diào)度模型

調(diào)度的完成時(shí)間表示為用戶提交一個(gè)工作流應(yīng)用的開始時(shí)間到獲得運(yùn)算結(jié)果的時(shí)間間隔,即

(4)

調(diào)度的完成時(shí)間包括整個(gè)工作流的執(zhí)行時(shí)間、網(wǎng)絡(luò)傳輸時(shí)間,而執(zhí)行時(shí)間與所使用的調(diào)度策略、系統(tǒng)負(fù)載情況和性能相關(guān),網(wǎng)絡(luò)傳輸時(shí)間則取決于系統(tǒng)中的網(wǎng)絡(luò)時(shí)延和任務(wù)的數(shù)據(jù)大小.

一個(gè)云工作流應(yīng)用的價(jià)格表示為

Ctotal=Cdeal+Ctr

(5)

若兩個(gè)任務(wù)ai、aj之間有數(shù)據(jù)依賴性,則這兩者之間的傳輸價(jià)格計(jì)入總價(jià)格中,對(duì)于在同一云節(jié)點(diǎn)上執(zhí)行的任務(wù),其間的傳輸價(jià)格忽略不計(jì).

(6)

調(diào)度策略在執(zhí)行任務(wù)前,根據(jù)任務(wù)的優(yōu)先級(jí)提供一個(gè)保持任務(wù)之間優(yōu)先級(jí)約束的線性順序.工作流調(diào)度問題就是構(gòu)建任務(wù)到云節(jié)點(diǎn)的二元組Q,該二元組由時(shí)間、價(jià)格構(gòu)成,表示為Q=[ttotal,Ctotal],則相應(yīng)的優(yōu)化問題表示為Q′=[minttotal,minCtotal].

1.2Pareto優(yōu)化

文中引入Pareto多目標(biāo)進(jìn)化方法,通過求得變量可行域,再根據(jù)不同的約束條件獲得調(diào)度策略的最優(yōu)解.一般根據(jù)云工作流調(diào)度中兩個(gè)相互影響的調(diào)度目標(biāo)(完成時(shí)間和價(jià)格)的最小化進(jìn)行求解.求解策略傾向于盡最大程度對(duì)兩個(gè)參數(shù)進(jìn)行優(yōu)化,符合該標(biāo)準(zhǔn)的求解策略組成的集合為Pareto最優(yōu)解集合.

在MPSO算法中,根據(jù)優(yōu)化目標(biāo)而確定的優(yōu)化原則如下:

(1)工作流調(diào)度中的變量為離散型,故在定義粒子的位置和速度時(shí),要保證其特征,并且要保持算法搜索的趨優(yōu)性,即進(jìn)行映射關(guān)系的解碼,求得該映射的時(shí)間效用和價(jià)格效用值.

(2)在求解優(yōu)化解的過程中,要求具有滿足不同目標(biāo)的Pareto最優(yōu)解集.每次更新微粒,必須保持上一次尋優(yōu)中搜索到的是比較好的分配方案,這樣才能使得算法收斂到全局最優(yōu)解.因此,文中參考了遺傳算法中染色體的交叉和變異特性,在每次更新分配方案時(shí),與當(dāng)前搜索到的個(gè)體最優(yōu)映射和全局最優(yōu)映射進(jìn)行交叉、變異,這樣就能保存目前搜索到的較優(yōu)分配,使得算法朝更優(yōu)的方向運(yùn)行.

1.3MPSO算法

粒子群優(yōu)化算法是一種隨機(jī)全局優(yōu)化算法,通常能夠得到較優(yōu)的結(jié)果,但隨著問題規(guī)模的增加,計(jì)算量和資源使用量迅速增加.因此,文中提出的MPSO算法從以下幾個(gè)方面進(jìn)行改進(jìn):重新定義經(jīng)典PSO算法中的粒子速度、位置的更新,并在利用算法進(jìn)行問題優(yōu)化求解過程引入了Pareto方法.

定義7MPSO算法中粒子i的位置L=[ai,pj],表示任務(wù)ai在云節(jié)點(diǎn)pj上.

定義8MPSO算法中粒子i的速度vi=[w(a),a],權(quán)值w(a)表示任務(wù)分配的可能概率.

定義9 粒子i的速度、位置更新公式如下:

(7)

(8)

在每一次迭代過程中,粒子會(huì)通過追蹤以上兩個(gè)位置來更新自己,并且根據(jù)式(7)、(8)更新速度和位置.

具有目標(biāo)約束的調(diào)度策略中時(shí)間目標(biāo)函數(shù)、價(jià)格目標(biāo)函數(shù)表示如下:

objt(Q)=ttotal(Q)

(9)

objC(Q)=Ctotal(Q)

(10)

由此,將MPSO優(yōu)化算法中的適應(yīng)度函數(shù)表示為

F(Q)=wTttotal(Q)+wCCtotal(Q)

(11)

式中,wT、wC分別為任務(wù)對(duì)于時(shí)間、價(jià)格的期望權(quán)值.

對(duì)于求解具有目標(biāo)約束的粒子群優(yōu)化算法,在盡可能找到被其他解所支配的最優(yōu)解的前提下,MPSO算法對(duì)Pareto最優(yōu)解集中的解進(jìn)行比較,但為了防止陷入局部最優(yōu)而影響全局求解的情況,一般隨機(jī)選擇最優(yōu)解,以加大粒子的全局搜索能力.MPSO算法優(yōu)化求解步驟如下:

(1)隨機(jī)生成一個(gè)初始種群,對(duì)種群中的粒子設(shè)置初始速度,檢驗(yàn)各粒子是否滿足約束條件,若不滿足則對(duì)其重新初始化.

(2)計(jì)算該種群每一個(gè)個(gè)體粒子的多目標(biāo)適應(yīng)度并檢查其Pareto占優(yōu)情況,將非劣解粒子存儲(chǔ)于Pareto解集存儲(chǔ)區(qū)f中. f中至少需要有兩個(gè)粒子,若不足則隨機(jī)產(chǎn)生.

(3)計(jì)算粒子群中各個(gè)體粒子的每個(gè)目標(biāo)適應(yīng)度,并以矢量形式存儲(chǔ).

(4)更新粒子群中個(gè)體粒子的速度和位置,從當(dāng)前Pareto解集中隨機(jī)選取一個(gè)值作為整個(gè)種群的最優(yōu)解.如果更新后的粒子不滿足約束條件,則刪除該粒子后重新隨機(jī)產(chǎn)生.

(5)檢查粒子群中每一個(gè)粒子的Pareto占優(yōu)情況,若某個(gè)占優(yōu)粒子是非劣解,則將該粒子存入f中作為當(dāng)前獲得粒子的一個(gè)Pareto解.

(6)如果f中某個(gè)粒子受控于新存入的粒子,則從f中刪除該粒子.

(7)若未達(dá)到最大迭代次數(shù),則返回步驟(3)繼續(xù)搜索,否則輸出滿足約束要求的映射方案,賦給調(diào)度模型.

MPSO算法描述如下.

輸入:各個(gè)任務(wù)隊(duì)列

輸出:調(diào)度策略

CalculatePriority();∥計(jì)算任務(wù)優(yōu)先級(jí)

SortByPriority();∥任務(wù)優(yōu)先級(jí)排列

Fori= 1ToNum∥Num為粒子的數(shù)目

InitializeParticle();

∥初始化粒子,即將任務(wù)映射到云節(jié)點(diǎn)

InitializeVelocity();∥初始化粒子速度

Lbest[i];∥初始化粒子的個(gè)體極值

EndFor

CalculateObjectValue();

∥計(jì)算粒子的目標(biāo)函數(shù)值

AddPareto();

Fort=lToIterationNum

Fori=lToSNum

CalculateVelocity();∥更新粒子速度

CalculatePosition();∥更新粒子位置

CalculateObjectValue();

∥計(jì)算粒子目標(biāo)函數(shù)值

CalculateFitness(S[i]*);

∥通過適應(yīng)度函數(shù)計(jì)算粒子的當(dāng)前適應(yīng)度值

IfS[i]*BetterThenLbest[i]

UpdateLbest[i];

EndIf

AddPareto();

EndFor

FndFor

ReturnPareto();∥返回調(diào)度策略集合

1.4MPSO算法復(fù)雜度分析

對(duì)于包含n個(gè)任務(wù)的工作流在m個(gè)云計(jì)算實(shí)例資源上運(yùn)行的工作流調(diào)度問題,其算法的復(fù)雜度因任務(wù)之間的相互關(guān)聯(lián)情況不同而不同:

(1)對(duì)于包含n個(gè)串行任務(wù)的工作流在m個(gè)云計(jì)算實(shí)例資源上運(yùn)行的云工作流調(diào)度問題,則有分配矩陣n·m·T,其算法復(fù)雜度為O(nmT);若任務(wù)數(shù)量增加,云節(jié)點(diǎn)保持不變,則算法的復(fù)雜度為O(n).

(2)對(duì)于動(dòng)態(tài)任務(wù)尤其是價(jià)格動(dòng)態(tài)變化的調(diào)度中,若任務(wù)均為并行任務(wù),則算法復(fù)雜度為O(mn);若任務(wù)數(shù)量增加,其中單個(gè)任務(wù)的執(zhí)行復(fù)雜度為O(m),云節(jié)點(diǎn)保持不變,則算法的復(fù)雜度為O(2n).

(3)對(duì)于應(yīng)用了優(yōu)化搜索算法的云工作流調(diào)度系統(tǒng),n個(gè)任務(wù)的工作流在m個(gè)云計(jì)算實(shí)例資源上運(yùn)行時(shí),任務(wù)執(zhí)行的復(fù)雜度為O(m),進(jìn)行最優(yōu)解搜索的復(fù)雜度為O(m2q),其中q為搜索的價(jià)格復(fù)雜度,則一個(gè)任務(wù)完整執(zhí)行的復(fù)雜度為O(m)+O(m2q),整個(gè)工作流的復(fù)雜度為n(O(m)+O(m2q)).若工作流中任務(wù)數(shù)不斷增加,云節(jié)點(diǎn)保持不變,價(jià)格為常數(shù),則算法的復(fù)雜度為O(n).

2 云工作流系統(tǒng)的第2階段調(diào)度

在云計(jì)算系統(tǒng)任務(wù)執(zhí)行的密集期,大量任務(wù)使用一個(gè)服務(wù)資源,這樣會(huì)嚴(yán)重影響系統(tǒng)的整體性能,導(dǎo)致沖突發(fā)生.因此在第2階段,文中采用延遲調(diào)度策略,根據(jù)系統(tǒng)中機(jī)器的負(fù)載情況選擇合適的時(shí)機(jī)將應(yīng)用任務(wù)調(diào)度到機(jī)器上執(zhí)行.

云工作流系統(tǒng)在第2階段的調(diào)度步驟如下:

(1)通過監(jiān)控中心獲得系統(tǒng)的負(fù)載信息;

(2)計(jì)算調(diào)度所消耗的通信量;

(3)按照調(diào)度消耗的通信量確定調(diào)度時(shí)機(jī);

(4)繼續(xù)監(jiān)控任務(wù)調(diào)度,并處理沖突.

(12)

定義11 設(shè)A中下一個(gè)任務(wù)的開始時(shí)間間隔Δtstart為

(13)

(14)

第2階段調(diào)度考慮了系統(tǒng)負(fù)載參數(shù),因此在第1階段調(diào)度的基礎(chǔ)上,文中建立如下的負(fù)載模型:

設(shè)op為CPU負(fù)載率,om為內(nèi)存負(fù)載率,則系統(tǒng)資源負(fù)載率o為

o=opom

(15)

相應(yīng)地,任務(wù)a發(fā)出請(qǐng)求等待時(shí)的資源負(fù)載率為owait=opwaitomwait,任務(wù)a開始執(zhí)行時(shí)的資源負(fù)載率為ostart=opstartomstart.

此負(fù)載模型作為第2階段調(diào)度機(jī)制的參數(shù)模型,為整個(gè)系統(tǒng)的第2階段調(diào)度提供調(diào)度算法的參數(shù)選擇標(biāo)準(zhǔn).

根據(jù)以上定義,第2階段調(diào)度算法描述如下.

輸入:任務(wù)列表

輸出:任務(wù)調(diào)度完成列表

SearchTask();∥搜索工作流中有請(qǐng)求的任務(wù)

SearchResource();

∥搜索處于預(yù)備狀態(tài)的服務(wù)資源

CalculateΔtA;

If ΔtA≥0

Wait for delay;∥等待延遲

Else

ExecuteSchedulingPolicy;

AllocateResource;∥執(zhí)行調(diào)度策略,分配資源

End If

3 仿真實(shí)驗(yàn)與結(jié)果分析

整個(gè)實(shí)驗(yàn)系統(tǒng)共有10臺(tái)服務(wù)器,服務(wù)器設(shè)置為Pentium(R)Dual-Core E5300 2.60 GHz、2.0 GB RAM, Windows 7;系統(tǒng)提供4～15個(gè)資源節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)配置為2.0 GB內(nèi)存及1 TB硬盤空間,另配置空載機(jī)器,僅運(yùn)行操作系統(tǒng)等必要軟件;由于目前數(shù)據(jù)中心局域網(wǎng)所使用的交換機(jī)和路由器基本上能夠?qū)崿F(xiàn)傳輸速率不受影響,因此假設(shè)傳輸速率為1 Gb/s.利用CloudSim進(jìn)行仿真實(shí)驗(yàn),并對(duì)此開源工具進(jìn)行了修改:創(chuàng)建工作流生成器,可以生成一系列具有依賴關(guān)系的任務(wù);將原工具中的數(shù)據(jù)中心分代理分為任務(wù)調(diào)度器和工作流執(zhí)行引擎兩個(gè)部分.調(diào)度器根據(jù)數(shù)據(jù)中心信息和任務(wù)信息制定調(diào)度方案,工作流執(zhí)行引擎根據(jù)調(diào)度方案將任務(wù)提交到數(shù)據(jù)中心.

首先,CloudSim中的工作流生成器生成工作流,并將工作流提交給任務(wù)調(diào)度器,任務(wù)調(diào)度器通過查詢數(shù)據(jù)中心信息生成一個(gè)調(diào)度方案,并將調(diào)度方案提供給工作流引擎,工作流引擎按照提供的調(diào)度方案申請(qǐng)?zhí)摂M機(jī)并將工作流的子任務(wù)提交給數(shù)據(jù)中心.

工作流定義中所設(shè)定流程任務(wù)數(shù)為30,在第1階段調(diào)度中,不失一般性,粒子群操作中的選擇概率分別設(shè)為40%和60%,以綜合考慮小于、大于對(duì)應(yīng)種群選擇折中即50%時(shí)的變化情況,去除折中時(shí)的選擇無關(guān)性.

3.1 優(yōu)化調(diào)度結(jié)果分析

文中采用經(jīng)典的HEFT算法、只針對(duì)單一目標(biāo)優(yōu)化的局部優(yōu)化遺傳算法(GA)與文中改進(jìn)的MPSO算法進(jìn)行對(duì)比.HEFT算法沒有進(jìn)行優(yōu)化,而GA算法實(shí)現(xiàn)局部最優(yōu)調(diào)度,MPSO則通過改進(jìn)適應(yīng)度函數(shù)實(shí)現(xiàn)全局隨機(jī)優(yōu)化.

表1為HEFT算法、遺傳算法、MPSO算法(種群選擇概率分別為40%和60%)的工作流任務(wù)執(zhí)行時(shí)間情況,其中任務(wù)執(zhí)行時(shí)間為整個(gè)工作流的分任務(wù)執(zhí)行時(shí)間,整個(gè)表的數(shù)據(jù)表示工作流在一個(gè)數(shù)據(jù)庫的不同節(jié)點(diǎn)執(zhí)行完畢的總時(shí)間.

由表中可知,雖然在算法的復(fù)雜程度上,MPSO算法比HEFT算法和GA算法復(fù)雜,但由于云計(jì)算技術(shù)的使用,調(diào)度過程中計(jì)算能力的增強(qiáng)使算法的復(fù)雜度影響降低,而算法本身為資源調(diào)度效率的提高帶來了較大的影響.

在實(shí)驗(yàn)中,采用改進(jìn)的MPSO算法時(shí)云計(jì)算中的工作任務(wù)最早完成,即該算法進(jìn)行全局調(diào)度優(yōu)化的結(jié)果優(yōu)于沒有優(yōu)化調(diào)度的HEFT算法和具有局部優(yōu)化的遺傳算法.

采用HEFT算法、GA算法及文中改進(jìn)的MPSO算法(選擇概率分別為40%和60%)時(shí),云工作流系統(tǒng)的總費(fèi)用對(duì)比如圖3所示.

表1 4種算法的任務(wù)執(zhí)行時(shí)間比較

圖3 不同資源數(shù)下幾種算法的任務(wù)執(zhí)行費(fèi)用

Fig.3 Task execution cost of several algorithms with different numbers of resources

由圖3可知,由于改進(jìn)MPSO算法的優(yōu)化效率高,對(duì)資源的調(diào)度更有效,從而提升工作流中任務(wù)的執(zhí)行效率,因此,在相同條件下對(duì)資源的消耗會(huì)降低.

設(shè)定不同資源數(shù),比較HEFT算法、GA算法、改進(jìn)MPSO算法的工作流任務(wù)運(yùn)行時(shí)間情況,結(jié)果如圖4所示.

圖4 不同資源數(shù)下幾種算法的任務(wù)執(zhí)行時(shí)間

Fig.4 Task execution time of several algorithms with different numbers of resources

由圖4可以看出,在服務(wù)資源比較少的情況下,各算法的調(diào)度結(jié)果具有一定的差別,隨著資源數(shù)的增加,改進(jìn)MPSO算法雖然因?yàn)榱Ｗ尤簝?yōu)化算法具有的不確定性而發(fā)生抖動(dòng),但并未產(chǎn)生強(qiáng)烈的影響,相對(duì)其他兩種算法仍具有一定的優(yōu)勢(shì),使資源調(diào)度更加優(yōu)化,執(zhí)行時(shí)間更短.

3.2 具有負(fù)載感知調(diào)度結(jié)果分析

實(shí)驗(yàn)將基于有、無負(fù)載感知機(jī)制的PSO算法分別應(yīng)用于云工作流系統(tǒng)中,PSO算法的適應(yīng)度隨代數(shù)的變化如圖5所示.衡量系統(tǒng)負(fù)載狀況的內(nèi)存利用率、CPU利用率的實(shí)驗(yàn)結(jié)果如圖6所示.

圖5 有、無負(fù)載感知機(jī)制的PSO算法的適應(yīng)度隨代數(shù)的變化Fig.5 Change of fitness with iteration number of PSO algorithm with or without load-aware

從圖5可知,使用負(fù)載感知機(jī)制后,系統(tǒng)的調(diào)度算法在執(zhí)行時(shí)能較早地趨于穩(wěn)定,因此也保證了在系統(tǒng)中進(jìn)行資源調(diào)度時(shí)負(fù)載的平衡性.

圖6 內(nèi)存利用率和CPU利用率對(duì)比

從圖6可知,在系統(tǒng)工作流任務(wù)執(zhí)行18、30、42 s左右的時(shí)間段內(nèi),選用有負(fù)載感知的調(diào)度策略時(shí),系統(tǒng)的內(nèi)存利用率和CPU利用率降低,這表明在該時(shí)間段內(nèi),任務(wù)在調(diào)度器中等待調(diào)度,故內(nèi)存利用率下降,后續(xù)調(diào)度迅速安排任務(wù)執(zhí)行,所以在以上時(shí)間段后CPU利用率迅速上升,符合工作流中任務(wù)調(diào)度的特點(diǎn).在同樣的時(shí)間段,選取無負(fù)載感知的調(diào)度策略時(shí),系統(tǒng)的內(nèi)存利用率處于增長狀態(tài),CPU利用率同樣有所變化,并且變化幅度較大.

綜合考慮內(nèi)存、CPU利用率可知,在截取的60 s任務(wù)執(zhí)行時(shí)間內(nèi),有負(fù)載感知的調(diào)度策略在任務(wù)請(qǐng)求調(diào)度中由于任務(wù)調(diào)度時(shí)機(jī)合適,使資源利用率沒有發(fā)生大的波動(dòng),一直處于平穩(wěn)狀態(tài),并沒有因?yàn)檎?qǐng)求服務(wù)數(shù)的突增而加大調(diào)度器的負(fù)擔(dān),因此,利用具有負(fù)載感知的調(diào)度策略能更好地保證云工作流系統(tǒng)的資源利用率,提高系統(tǒng)性能.

4 結(jié)論

根據(jù)用戶的QoS需求,考慮系統(tǒng)的資源利用率對(duì)云計(jì)算資源進(jìn)行有效調(diào)度,以實(shí)現(xiàn)效益最大化是當(dāng)前云計(jì)算的資源分配所遇到的挑戰(zhàn).文中將云計(jì)算與工作流相結(jié)合,建立了云工作流系統(tǒng),給出了具有兩個(gè)調(diào)度階段的系統(tǒng)調(diào)度模型.針對(duì)整體優(yōu)化及對(duì)用戶QoS的需求,文中提出了改進(jìn)的MPSO算法,通過整體的優(yōu)化策略進(jìn)行預(yù)調(diào)度;為了保證系統(tǒng)任務(wù)在高負(fù)載時(shí)正常執(zhí)行,保證系統(tǒng)的執(zhí)行能力,將文中提出的考慮負(fù)載感知的調(diào)度策略應(yīng)用于局部的調(diào)度中,根據(jù)調(diào)度策略求解負(fù)載情況,給出調(diào)度的恰當(dāng)時(shí)機(jī)進(jìn)行資源調(diào)度,以提高系統(tǒng)的資源利用率.實(shí)驗(yàn)結(jié)果表明:改進(jìn)的MPSO算法應(yīng)用于云工作流系統(tǒng)的資源優(yōu)化調(diào)度中,相較于HEFT算法和GA算法,任務(wù)響應(yīng)時(shí)間更快,能夠高效地利用資源,滿足用戶一定的QoS需求;具有負(fù)載感知的調(diào)度策略能有效平衡系統(tǒng)負(fù)載,提升資源利用率.今后擬考慮QoS的綜合約束條件,提出相應(yīng)的資源調(diào)度策略.

[1] SINGH L,SINGH S.A genetic algorithm for scheduling workflow applications in unreliable cloud environment [C]∥Recent Rends in Computer Networks and Distributed Systems Security.Berlin/Heidelberg:Springer,2014:139-150.

[2] CHEN W N,ZHANG J.A set-based discrete PSO for cloud workflow scheduling with user-defined QoS constraints [C]∥Proceedings of 2012 IEEE International Conference on Systems,Man,and Cybernetics.Seoul: IEEE,2012:773-778.[3] TORDSSON J,MONTERO R S,MORENO-VOZMEDIA-NO R,et al.Cloud brokering mechanisms for optimized placement of virtual machines across multiple providers [J].Future Generation Computer Systems,2012,28(2):358-367.

[4] LIU Ke,GHAREHCHOPOGH F S,AHADI M,et al.Ana-lysis of scheduling algorithms in grid computing environment [J].International Journal of Innovation and Applied Studies,2013,4(3):560-567.

[5] JAVADI B,THULASIRAM R K,BUYYA R.Characterizing spot price dynamics in public cloud environments [J].Future Generation Computer Systems,2013,29(4):988-999.

[6] JRAD F,TAO J,BRANDIC I,et al.SLA enactment for large-scale healthcare workflows on multi-cloud [J].Future Generation Computer Systems,2015,43(4):135-148.

[7] IOSUP A.Performance analysis of cloud computing ser-vices for many-tasks scientific computing [J].IEEE Tran-sactions on Parallel Distributed System,2010,22(6):931-945.[8] 郭禾,陳征,于玉龍,等.帶通信開銷的DAG工作流費(fèi)用優(yōu)化模型與算法 [J].計(jì)算機(jī)研究與發(fā)展,2015,52(6):1400-1408.

GUO He,CHEN Zheng,YU Yu-long et al.A communication aware DAG workflow cost optimization model and algorithm [J].Journal of Computer Research and Development,2015,52(6):1400-1408.

[9] 張鵬,王桂玲,徐學(xué)輝.云計(jì)算環(huán)境下適于工作流的數(shù)據(jù)布局方法 [J].計(jì)算機(jī)研究與發(fā)展,2013,50(3):636-647.

ZHANG Peng,WANG Gui-ling,XU Xue-hui.A data placement approach for workflow in cloud [J].Journal of Computer Research and Development,2013,50(3):636-647.[10] 朱勇,羅軍舟,李偉.一種工作流環(huán)境下能耗感知的多路徑服務(wù)組合方法 [J].計(jì)算機(jī)學(xué)報(bào),2012,35(3):627-638.

ZHU Yong,LUO Jun-zhou,LI Wei.An approach for energy aware multipath service composition based on workflow [J].Chinese Journal of Computers,2012,35(3):627-638.

[11] WU Zhangjun,LIU Xiao,NI Zhiwei,et al.A market-oriented hierarchical scheduling strategy in cloud workflow systems [J].The Journal of Supercomputing,2013,63(1):256-293.

[12] YANG Bo,TAN Feng,DAI Yuanshun,et al.Performance evaluation of cloud service considering fault recovery [J]. The Journal of Supercomputing,2013,65(1):426-444.

[13] BUYYA R,VENUGOPAL S.The gridbus toolkit for ser-vice oriented grid and utility computing:an overview and status report [C]∥Proceedings of the 1st IEEE International Workshop on Grid Economics and Business Mo-dels.Seoul:IEEE,2008:19-36.

[14] LIU Xiao,YANG Yun,JIANG Yuan-chun,et al.Preventing temporal violations in scientific workflows:where and how [J].IEEE Transactions on Software Enginee-ring,2011,37(6):805-825.

[15] YUAN Dong,YANG Yun,LIU Xiao.A data dependency based strategy for intermediate data storage in scientific cloud workflow systems [J].Concurrency and Computation:Practice and Experience,2012,24(9):956-976.

[16] LIU Jun-xiang,WANG Yong-ji,CARTMELL Matthew.An improved rate monotonic schedulability test algorithm [J].Journal of Software,2005,16(1):89-100.

A Two-Stage Resource Scheduling Method for Workflow Cloud Computing System

WANGYan1WANGJin-kuan1HANYing-hua2

(1. College of Information Science and Engineering, Northeastern University, Shenyang 110819, Liaoning, China;2. School of Control Engineering, Northeastern University at Qinhuangdao, Qinhuangdao 066004, Hebei, China)

In order to improve the resource utilization of cloud computing systems and optimize the system perfor-mance, by taking into account the users’ QoS demand, a workflow cloud computing system is established by integrating cloud computing with workflow, and a two-stage resource scheduling model is constructed for the cloud computing workflow system. In the first stage, by considering the time and cost constraints of QoS, the dependencies among the tasks in the workflow, and the processing of the intermediate data from each task, a modified particle swarm optimization algorithm (MPSO) is proposed, and the Pareto is used to obtain an optimal solution so as to improve scheduling efficiency. In the second stage, by considering the resource allocation on hosts, a scheduling stra-tegy with load-aware is proposed to perform resource scheduling according to system loads, so as to improve the resource utilization of the system. Experimental results show that, in the resource scheduling process of the workflow cloud computing system, the modified MPSO algorithm is superior to the earliest heterogeneous finish-time algorithm and single-objective optimization genetic algorithm in terms of execution speed, resource utilization and users’ satisfaction with QoS, and that, the proposed scheduling strategy with load-aware can schedule more efficiently accor-ding to the system loads, and the task execution efficiency and the resource utilizationare are thus improved.

cloud computing; workflow; particle swarm optimization; load-aware

1000-565X(2017)01- 0080- 08

2016- 03- 18

國家自然科學(xué)基金資助項(xiàng)目(61300194)

Foundation item： Supported by the National Natural Science Foundation of China(61300194)

王巖(1981-),女,博士生,講師,主要從事云計(jì)算資源調(diào)度研究.E-mail:wangyan3215931@163.com

TP 393

10.3969/j.issn.1000-565X.2017.01.012