黃志剛 劉 峰

1(湖南科技職業(yè)學(xué)院 湖南 長(zhǎng)沙 410004 )2(長(zhǎng)沙理工大學(xué)計(jì)算機(jī)學(xué)院 湖南 長(zhǎng)沙 410082)

0 引 言

工作流是復(fù)雜計(jì)算問(wèn)題的常用建模方式，云計(jì)算特有的按需提供和即付即用的資源定制模式使得云環(huán)境下進(jìn)行調(diào)度工作流變得更為復(fù)雜[1]。工作流任務(wù)結(jié)構(gòu)與傳統(tǒng)批或包任務(wù)的調(diào)度方法極為不同，工作流任務(wù)通常擁有嚴(yán)格的執(zhí)行次序，或稱(chēng)邏輯依賴(lài)，需要在滿(mǎn)足用戶(hù)指定的服務(wù)質(zhì)量約束的前提下，對(duì)各任務(wù)實(shí)現(xiàn)與其對(duì)應(yīng)虛擬機(jī)資源的映射。工作流調(diào)度過(guò)程中的調(diào)度任務(wù)選擇與虛擬機(jī)實(shí)例提供決策對(duì)于是否能夠滿(mǎn)足給定約束和全局調(diào)度代價(jià)均具有重要影響[2]。傳統(tǒng)的調(diào)度方法偏向于關(guān)注調(diào)度效率，忽略了資源利用費(fèi)用，此時(shí)的調(diào)度問(wèn)題在不同資源和不同調(diào)度方案下的執(zhí)行時(shí)間和代價(jià)均有所不同。因此，云環(huán)境下需要同步考慮用調(diào)度時(shí)間和調(diào)度代價(jià)，這更符合云工作流的調(diào)度場(chǎng)景[3]。

有關(guān)研究中，文獻(xiàn)[4]設(shè)計(jì)了基于執(zhí)行時(shí)間和調(diào)度費(fèi)用的多目標(biāo)工作流調(diào)度算法，作者將多目標(biāo)轉(zhuǎn)化為單目標(biāo)優(yōu)化進(jìn)行了優(yōu)化方案的求解，但卻忽略了云資源虛擬機(jī)的性能變化，僅討論了同質(zhì)資源的情形。文獻(xiàn)[5]設(shè)計(jì)基于局部關(guān)鍵路徑的調(diào)度算法IC-PCP，IC-PCP優(yōu)先將處于局部關(guān)鍵路徑上的任務(wù)調(diào)度至最低代價(jià)虛擬機(jī)上執(zhí)行，避免了每個(gè)局部關(guān)鍵路徑的通信代價(jià)，實(shí)現(xiàn)截止時(shí)間的約束，但算法卻忽略了虛擬機(jī)的啟動(dòng)和部署時(shí)間，這在實(shí)際場(chǎng)景中占比較重。文獻(xiàn)[6]中提出的RTC和RCT算法是分別針對(duì)執(zhí)行時(shí)間優(yōu)先和執(zhí)行代價(jià)優(yōu)先提出的工作流調(diào)度最優(yōu)化算法，均是單目標(biāo)無(wú)約束式優(yōu)化，費(fèi)用與時(shí)間只考慮了一種，不符合云工作流實(shí)際調(diào)度特征。與上文不同，文獻(xiàn)[7]提出一種基于粒子群的工作流調(diào)度優(yōu)化算法，雖然考慮了資源提供彈性與異構(gòu)特征，但利用智能優(yōu)化算法仍然無(wú)法擺脫時(shí)間復(fù)雜度過(guò)高和早熟問(wèn)題。文獻(xiàn)[8]在混合云中設(shè)計(jì)一種整數(shù)非線(xiàn)性規(guī)化方法求解工作流調(diào)度，其目標(biāo)是滿(mǎn)足截止時(shí)間約束最小化執(zhí)行總代價(jià)。文獻(xiàn)[9]提出一種動(dòng)態(tài)規(guī)化方法處理多約束工作流調(diào)度問(wèn)題，但沒(méi)有考慮多類(lèi)型異構(gòu)虛擬機(jī)提供場(chǎng)景。

本文將設(shè)計(jì)時(shí)間復(fù)雜度更低的工作流調(diào)度算法，滿(mǎn)足截止時(shí)間的同時(shí)尋找工作流調(diào)度優(yōu)化最優(yōu)可行解。本文設(shè)計(jì)了一種代價(jià)優(yōu)化的工作流調(diào)度算法WSCO，算法著重考慮了云資源提供時(shí)虛擬機(jī)性能的動(dòng)態(tài)性和異構(gòu)性，最終實(shí)現(xiàn)在不同要求的截止時(shí)間約束程度下的工作流調(diào)度代價(jià)的最小化。

1 系統(tǒng)模型

1.1 應(yīng)用模型

云計(jì)算工作流應(yīng)用W=(T,E)可表示為有向無(wú)循環(huán)圖DAG，T={t1,t2,…,tn}代表任務(wù)的圖頂點(diǎn)集，E代表任務(wù)間數(shù)據(jù)傳輸關(guān)系的有向邊集，邊eij表示任務(wù)對(duì)(ti,tj)間的順序約束關(guān)系，ti,tj∈T,ti≠tj，表明任務(wù)tj(子任務(wù))只能在ti(父任務(wù))完成并傳輸相關(guān)數(shù)據(jù)后才可以開(kāi)始執(zhí)行。換言之，子任務(wù)在其所有父任務(wù)完成且數(shù)據(jù)傳輸完成之前是無(wú)法執(zhí)行的。截止時(shí)間D用于限定所有工作流任務(wù)完成的最后期限。工作流示例如圖1所示，每個(gè)節(jié)點(diǎn)代表一個(gè)任務(wù)，邊值代表任務(wù)間的數(shù)據(jù)傳輸時(shí)間。

圖1 工作流示例

1.2 資源模型

云資源由IaaS云服務(wù)提供者提供的虛擬機(jī)資源構(gòu)成，假設(shè)所有計(jì)算或存儲(chǔ)資源處于同一數(shù)據(jù)中心內(nèi)，則服務(wù)間的帶寬是相同的。計(jì)算資源由不同類(lèi)型的虛擬機(jī)VMs提供，各VMs類(lèi)型擁有不同的CPU類(lèi)型、內(nèi)存大小和定價(jià)。假設(shè)應(yīng)用任務(wù)租用的VM實(shí)例數(shù)量不受限制，且一個(gè)VM被租用時(shí)，需要有啟動(dòng)時(shí)間進(jìn)行初始化。相應(yīng)地，VM被釋放時(shí)，需要有一定的關(guān)機(jī)時(shí)間停止服務(wù)。VM定價(jià)模型使用基于即付即用的帳單策略(與商業(yè)云Amazon EC2相似)，用戶(hù)根據(jù)租用VM的時(shí)間間隔Tintervals進(jìn)行付費(fèi)，Tintervals由云提供商定義，如Amazon以一小時(shí)作為付費(fèi)間隔。因此，即使VM利用不足一小時(shí)，也將以一小時(shí)付費(fèi)。云資源模型中，將VM類(lèi)型VMv定義為一個(gè)二元組{(ETti)v,Cv}，描述每個(gè)任務(wù)ti的估計(jì)計(jì)算時(shí)間和每個(gè)Tintervals的代價(jià)。任務(wù)ti執(zhí)行于VMv類(lèi)型的VM上的代價(jià)計(jì)算為：

調(diào)度于不同VM的任務(wù)間的數(shù)據(jù)傳輸時(shí)間TT(eij)計(jì)算為dti/β，其中，dti為ti與tj間的輸出數(shù)據(jù)量，β為數(shù)據(jù)中心的帶寬。當(dāng)兩個(gè)任務(wù)調(diào)度于同一VM時(shí)，TT(eij)=0。

1.3 問(wèn)題定義

本文的目標(biāo)是尋找工作流的調(diào)度方案，使得執(zhí)行代價(jià)達(dá)到最小，并且滿(mǎn)足用戶(hù)定義的截止時(shí)間要求。為了得到截止時(shí)間限定下的調(diào)度方案，首先需要確定截止時(shí)間是否可達(dá)，若不可達(dá)，調(diào)度問(wèn)題將沒(méi)有可行解，需要修正截止時(shí)間。在截止時(shí)間內(nèi)可完成的情況下，目標(biāo)即是在截止時(shí)間約束下為每個(gè)任務(wù)尋找合適的調(diào)度決策，進(jìn)而實(shí)現(xiàn)調(diào)度代價(jià)的最小，該過(guò)程涉及以下三個(gè)決策問(wèn)題：

1)cheapesttask-VMmapping：代價(jià)最低映射，用于為等待調(diào)度的每個(gè)任務(wù)尋找代價(jià)最低的VM類(lèi)型：

cheapesttask-VMmapping={(ti→VMv)}

2)ProvisioningPlan：用于基于運(yùn)行任務(wù)的狀態(tài)和等待任務(wù)的cheapesttask-VMmapping確定不同階段工作流執(zhí)行時(shí)每種VM類(lèi)型的利用數(shù)量。定義資源池中的每一個(gè)VMvk均擁有類(lèi)型type、開(kāi)始時(shí)間stk及結(jié)束時(shí)間etk等屬性：

VMPool={vk,type(vk),stk,etk}

3)SchedulingPlan：用于決定任務(wù)ti調(diào)度于資源池中的哪個(gè)VM類(lèi)型vk及任務(wù)相應(yīng)的估計(jì)開(kāi)始時(shí)間tstart和結(jié)束時(shí)間tend：

Schedule={ti,vk,tstart,tend}

算法目標(biāo)是尋找工作流應(yīng)用W的調(diào)度方案S，使得工作流的調(diào)度總代價(jià)達(dá)到最小，并且總體執(zhí)行時(shí)間TET不超過(guò)截止時(shí)間D的約束，可形式化為：

(1)

s.t.TET≤D，TET=maxti{AFT(ti)}

2 相關(guān)說(shuō)明與定義

文中涉及的主要符號(hào)含義說(shuō)明如表1所示。

表1 符號(hào)說(shuō)明

續(xù)表1

1)MET(ti)：任務(wù)ti的最小執(zhí)行時(shí)間定義為任務(wù)ti在所有可用VM類(lèi)型中，在擁有最小執(zhí)行時(shí)間ET(ti,VMv)的VM實(shí)例類(lèi)型VMv∈VMset上執(zhí)行時(shí)得到的時(shí)間，表示為：

(2)

2)EST(ti)：任務(wù)ti的最早開(kāi)始時(shí)間定義為其所有前驅(qū)任務(wù)在最快VM類(lèi)型上調(diào)度且關(guān)聯(lián)數(shù)據(jù)已傳送至ti時(shí)的開(kāi)始執(zhí)行時(shí)間，表示為：

(3)

3)EFT(ti)：任務(wù)ti的最早完成時(shí)間定義為：

EFT(ti)=EST(ti)+MET(ti)

(4)

4)XFT(ti)：任務(wù)ti調(diào)度至VMvk時(shí)的期望完成時(shí)間定義為：

(5)

5)XST(ti)：任務(wù)ti的期望開(kāi)始時(shí)間定義為其所有前驅(qū)調(diào)度后ti開(kāi)始執(zhí)行的估計(jì)時(shí)間，表示為：

(6)

6)XIST(vk)：資源池中一個(gè)活動(dòng)VMvk的期望空閑開(kāi)始時(shí)間為vk期望完成其上調(diào)度的最近任務(wù)的時(shí)間。若tp為調(diào)度于vk的最近任務(wù)，則vk的期望空閑開(kāi)始時(shí)間為：

(7)

7)LFT(ti)：任務(wù)ti的最遲完成時(shí)間定義為所有任務(wù)在工作流截止時(shí)間D之前完成時(shí)ti完成的最遲時(shí)間，表示為：

(8)

8)LST(ti)：任務(wù)ti的最遲開(kāi)始時(shí)間定義為所有任務(wù)在工作流截止時(shí)間D之前完成時(shí)ti開(kāi)始執(zhí)行的最遲時(shí)間，表示為：

LST(ti)=LFT(ti)-MET(ti)

(9)

9)XET(ti,VMv)：VM類(lèi)型VMv上從任務(wù)ti開(kāi)始的關(guān)鍵路徑(最長(zhǎng)執(zhí)行路徑)的期望執(zhí)行時(shí)間定義為從ti開(kāi)始執(zhí)行整個(gè)關(guān)鍵路徑任務(wù)的總時(shí)間，表示為：

(10)

10)MET_W：工作流最小執(zhí)行時(shí)間為所有任務(wù)均執(zhí)行于最快VM時(shí)的關(guān)鍵路徑長(zhǎng)度(時(shí)間)，即最長(zhǎng)的執(zhí)行路徑，表示為：

(11)

11)CLI(vk)：租用VMvk的當(dāng)前租用間隔定義的是該VM被租用索價(jià)的時(shí)間跨度。給定vk提供的時(shí)間stk，帳單的時(shí)間單位Tintervals以及當(dāng)前的Tintervals(n)，則CLI(vk)可表示為：

CLI(vk)=[stk,stk+n×Tintervals]

(12)

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

算法1給出了WSCO算法的偽代碼。算法首先需要驗(yàn)證截止時(shí)間D的可達(dá)性。對(duì)于可達(dá)的截止時(shí)間，需要大于工作流的最小執(zhí)行時(shí)間MET_W。因此，算法首先評(píng)估MET_W并將其與截止時(shí)間D作比較，若D大于MET_W，算法繼續(xù)尋找合適的調(diào)度；否則，用戶(hù)將修正截止時(shí)間D。一旦確定了截止時(shí)間的可達(dá)性，算法通過(guò)預(yù)處理步驟和控制循環(huán)過(guò)程確定所需的調(diào)度方案。預(yù)處理步驟通過(guò)合并管道任務(wù)為單個(gè)任務(wù)降低算法運(yùn)行開(kāi)銷(xiāo)，控制循環(huán)過(guò)程維持運(yùn)行任務(wù)的更新信息并相應(yīng)為等待的未調(diào)度任務(wù)作出調(diào)度決策。以下對(duì)算法作詳細(xì)描述。

算法1WSCO算法

輸入: 工作流W(T,E) ，代價(jià)矩陣C，執(zhí)行時(shí)間矩陣ET，傳輸時(shí)間TT，截止時(shí)間D以及作務(wù)請(qǐng)求間隔

1.開(kāi)始

2. 以式(2)(3)(4)(11)計(jì)算MET_W

3. 若D>MET_W

4. 調(diào)用算法2進(jìn)行管道任務(wù)合并

5. 計(jì)算MET,LFT和XET

6. 尋找工作流結(jié)構(gòu)的根節(jié)點(diǎn)為{tentry}

7.for每個(gè)屬于{tentry}中的任務(wù)te

8.To_Provision←CheapesttaskVMMap(te)

//調(diào)用算法4

9. 生成類(lèi)型為T(mén)o_Provision的虛擬機(jī)ve

10. 在時(shí)間XST(te)時(shí)將te調(diào)度至ve

11. 更新虛擬資源池VM_Pool_Status

12.結(jié)束for循環(huán)

13.whileT中所有任務(wù)未完成

14. 發(fā)送調(diào)度任務(wù)至執(zhí)行管理器

15. 更新任務(wù)AST，XFT

16. 將任務(wù)ti的父任務(wù)集中被調(diào)度和正在運(yùn)行的任務(wù)組成任務(wù)集合to_be_scheduled

17. 在任務(wù)集to_be_scheduled上調(diào)用算法3

18.結(jié)束while循環(huán)

19.結(jié)束

20. 在MET_W以?xún)?nèi)修正截止時(shí)間

21.結(jié)束if

22.結(jié)束

3.1 任務(wù)預(yù)處理

為了降低任務(wù)運(yùn)行時(shí)開(kāi)銷(xiāo)，算法通過(guò)任務(wù)預(yù)處理過(guò)程將管道任務(wù)合并為單個(gè)任務(wù)執(zhí)行，如圖2所示。預(yù)處理可以節(jié)省任務(wù)間通信的數(shù)據(jù)傳輸時(shí)間，加快動(dòng)態(tài)調(diào)度方案的生成。圖3為預(yù)處理示例，任務(wù)t1和t2可合并為任務(wù)t1+t2，這使得t2可以在與t1相同的資源上執(zhí)行并在本地直接利用t1的執(zhí)行結(jié)果，避免t1與t2在不同資源上執(zhí)行時(shí)的數(shù)據(jù)傳輸時(shí)間，降低循環(huán)控制過(guò)程中的運(yùn)行開(kāi)銷(xiāo)。預(yù)處理步驟的執(zhí)行過(guò)程如算法2所示。

圖2 管道任務(wù)

圖3 合并管道任務(wù)

算法2Pre-processing(W)

輸入: 工作流W(T,E)

1. 開(kāi)始

2. 入口任務(wù){(diào)tentry}置入初始任務(wù)隊(duì)列tksqueue

3.while任務(wù)隊(duì)列tksqueue非空

4. 隊(duì)首任務(wù)賦予tp

5.tp的子任務(wù)置入Sc

6.ifSc的基數(shù)為1且tc僅有一個(gè)父任務(wù)tp

7. 合并tp和tc為tp+c

8. 設(shè)置tp+c為tc子任務(wù)的父任務(wù)

9. 新任務(wù)執(zhí)行時(shí)間ET(tp+c)

10. 添加合并任務(wù)tp+c至隊(duì)首

11.else

12. 添加tp的子任務(wù)至隊(duì)列tksqueue的隊(duì)尾

13.結(jié)束if

14.結(jié)束while循環(huán)

15.end

3.2 循環(huán)控制過(guò)程

預(yù)處理后，算法提供代價(jià)最低的可用資源(cheapestapplicable)用于執(zhí)行工作流入口任務(wù)，然后進(jìn)入循環(huán)控制過(guò)程。由于入口任務(wù)是第一個(gè)調(diào)度任務(wù)，故入口任務(wù)的期望開(kāi)始時(shí)間XST設(shè)置為期望VM獲取時(shí)間(expectedVMacquisitiontime)。在每次循環(huán)控制中，算法更新調(diào)度運(yùn)行任務(wù)的實(shí)際開(kāi)始時(shí)間AST，確定父節(jié)點(diǎn)已被調(diào)度的任務(wù)及將運(yùn)行(to-be-scheduled)的任務(wù)，然后利用PlanandSchedule算法作出合適的調(diào)度決策。循環(huán)控制過(guò)程直到所有工作流任務(wù)被調(diào)度時(shí)結(jié)束。在每一階段中，任務(wù)的cheapestapplicableVM類(lèi)型由CheapesttaskVMMap算法決定，若T時(shí)刻請(qǐng)求一個(gè)新的VM，則此時(shí)確保VM可用的expectedVMacquisitiontime也為T(mén)。

1) PlanandSchedule算法。PlanandSchedule算法接收一個(gè)任務(wù)集作為輸入，并將其調(diào)度至合適(appropriate)VM實(shí)例上。與CheapesttaskVMmap算法一致，該算法尋找最小代價(jià)且擁有最小數(shù)據(jù)傳輸時(shí)間的調(diào)度方案。算法試圖將一個(gè)任務(wù)調(diào)度至最后一個(gè)父節(jié)點(diǎn)(擁有最大期望完成時(shí)間XFT的父任務(wù))相同的資源上，以避免調(diào)度在不同資源時(shí)的數(shù)據(jù)傳輸。PlanandSchedule如算法3所示。

算法3PlanandSchedule算法

1. 將虛擬機(jī)池中的活躍虛擬機(jī)列表賦予Active_VMs

2.for任務(wù)列表中的每個(gè)任務(wù)t

3.vmmap←CheapesttaskVMMap(ti)

4. 尋找滿(mǎn)足約束條件的目標(biāo)虛擬機(jī)集合

5.if{vk}存在

6. 尋找XIST(vk)與XST(ti)差值最小的虛擬機(jī)vk

7. 在vk調(diào)度任務(wù)ti并更新XST(ti)

8. 更新虛擬機(jī)資源池VM_Pool_Status

9.else

10. 尋找滿(mǎn)足約束條件的目標(biāo)虛擬機(jī)集合

11.if{vj}存在

12. 尋找XIST(vj)與XST(ti)間差值最小的虛擬機(jī)vj

13. 在vj上調(diào)度任務(wù)ti并更新XST(ti)

14. 更新虛擬機(jī)資源池VM_Pool_Status

15.else

16. 生成新虛擬機(jī)

17. 按XST在v上調(diào)度任務(wù)ti

18. 更新虛擬機(jī)資源池VM_Pool_Status

19. 結(jié)束if

20.結(jié)束if

21.結(jié)束for循環(huán)

22. 撤銷(xiāo)關(guān)閉空閑虛擬機(jī)

23.返回

對(duì)于任務(wù)列表中的任務(wù)ti，PlanandSchedule算法調(diào)用CheapesttaskVMmap算法(即步驟3)得到調(diào)度ti的cheapestapplicableVM類(lèi)型vmmap。由于VM按完整的時(shí)間間隔Tintervals收取費(fèi)用，因此為了盡可能密集地利用VM，PlanandSchedule算法試圖決策是否ti能夠在當(dāng)前租用間隔CLI結(jié)束前調(diào)度于已經(jīng)租用的VM上。為了完成這個(gè)目標(biāo)，算法首先尋找與vmmap同類(lèi)型且滿(mǎn)足以下條件的活動(dòng)VMs {vk}：

(1) 若ti調(diào)度于vk，ti僅利用CLI(vk)的剩余時(shí)間部分；

(2)ti的期望完成時(shí)間小于或等于ti的最遲完成時(shí)間；

(3) 若ti調(diào)度于vk，不存在任一ti的子任務(wù)tc，使得tc的期望開(kāi)始時(shí)間大于tc的最遲開(kāi)始時(shí)間。

若該活動(dòng)VM集合存在，則從該集合中選擇擁有最小期望空閑開(kāi)始時(shí)間XIST與期望開(kāi)始時(shí)間之差的VMvk用于調(diào)度ti。XST(ti)與VM_Pool_Status通過(guò)步驟4-步驟8進(jìn)行更新；否則，PlanandSchedule算法試圖尋找活動(dòng)VMs{vj}，使得type(vj)≥vmmap且以下條件得到滿(mǎn)足：

(1) 若ti調(diào)度于vj，ti可在CLI(vj)的剩余時(shí)間內(nèi)完成；

(2)ti的期望完成時(shí)間小于或等于ti的最遲完成時(shí)間；

(3) 若ti調(diào)度于vj，不存在任一ti的子任務(wù)tc，使得tc的期望開(kāi)始時(shí)間大于tc的最遲開(kāi)始時(shí)間。

若該活動(dòng)VM集合存在，則從該集合中選擇擁有最小期望空閑開(kāi)始時(shí)間XIST與期望開(kāi)始時(shí)間之差的VMvj用于調(diào)度ti。XST(ti)與VM_Pool_Status通過(guò)步驟10-步驟14進(jìn)行更新；若不存在活動(dòng)VMs可利用于調(diào)度ti，則需要從云端生成新的VM類(lèi)型vmmap調(diào)度ti，即步驟16-步驟18。任務(wù)列表中的所有任務(wù)調(diào)度后，PlanandSchedule算法需要查證無(wú)任務(wù)調(diào)度的空閑VMs及已完成任務(wù)的VMs，即步驟22。

2) CheapesttaskVMmap算法。CheapesttaskVMmap算法接收一個(gè)任務(wù)t作為輸入，并返回其cheapestapplicable的VM類(lèi)型taskvmmap。盡管cheapestapplicable的VM類(lèi)型可以在任務(wù)的最遲完成時(shí)間內(nèi)完成任務(wù)，但可能不是最優(yōu)選擇，這是因?yàn)檫x擇代價(jià)最小的VM類(lèi)型并未考慮對(duì)其子任務(wù)的影響，即可能迫使子任務(wù)執(zhí)行于更快的VM而增加了總代價(jià)。因此，算法將任務(wù)的cheapestapplicable的VM類(lèi)型定義為代價(jià)最小類(lèi)型的單個(gè)VM，若利用該VM類(lèi)型調(diào)度關(guān)鍵路徑上從t開(kāi)始的所有任務(wù)，則可在截止時(shí)間D內(nèi)完成全部關(guān)鍵路徑任務(wù)的執(zhí)行，即所討論的目標(biāo)是利用最小的可能數(shù)據(jù)傳輸時(shí)間尋找最小代價(jià)的調(diào)度方案。因此，若任務(wù)t無(wú)需等待即可得到VM上一個(gè)空閑(免費(fèi))的時(shí)間間隔，則算法將確認(rèn)任務(wù)t是否能夠調(diào)度于其最后的父任務(wù)(擁有最大期望完成時(shí)間的父任務(wù))相同的VMvp上。若t調(diào)度于vp，XST(t)將被首次評(píng)估并與XIST(vp)比較。若XIST(vp)小于XST(t)(表明vp在t的期望開(kāi)始時(shí)間上是空閑的，可用于調(diào)度t)，調(diào)度于vp上可確保在截止時(shí)間D前完成執(zhí)行，然后可將taskvmmap設(shè)置為type(vp)，并更新XST(t)，即步驟4-步驟10。然后，PlanandSchedule算法將任務(wù)t調(diào)度于vp。否則，利用以下規(guī)則(步驟12-步驟18)更新XST(t)和對(duì)于t的taskvmmap：

(1) 確定VM類(lèi)型集合{VMk}，使得從t開(kāi)始的關(guān)鍵路徑若調(diào)度于類(lèi)型VMk的單個(gè)VM上，可以D內(nèi)完成執(zhí)行；

(2) 從集合{VMk}中確定VM類(lèi)型VMj，可使得該關(guān)鍵路徑的總執(zhí)行代價(jià)最小。

算法4CheapesttaskVMMap(t)算法

1. 開(kāi)始

2. 映射集合taskvmmap置空

3. ift不是入口任務(wù)

5. 將正在運(yùn)行最后一個(gè)父任務(wù)的虛擬機(jī)賦予vp

7. if((temp≥XIST(vp))且(temp+XET(t,type(vp)))≤D)

8.XST(t) ←temp

9.taskvmmap←type(vp)

10. 返回映射集合taskvmmap

11.else

13.結(jié)束if

14.else

15.XST(t) ←acquisitiondelay

16.結(jié)束if

17. 尋找滿(mǎn)足(XST(t)+XET(t,VMk))≤D的集合{VMk}

19. 將虛擬機(jī)VMj置入映射集合taskvmmap

20. 返回映射集合taskvmmap

3.3 算例說(shuō)明

本節(jié)通過(guò)一個(gè)算例說(shuō)明算法的執(zhí)行過(guò)程。以圖4作為工作流示例，包括9個(gè)任務(wù)t1-t9，邊上的數(shù)值表示任務(wù)間的數(shù)據(jù)傳輸時(shí)間。設(shè)有三種VM類(lèi)型{VMs,VMm,VMl}(s-small,m-medium,l-large)用于工作流任務(wù)的執(zhí)行。圖5是任務(wù)在各VM上的執(zhí)行時(shí)間矩陣和數(shù)據(jù)傳輸時(shí)間矩陣,圖6是合并管道任務(wù)后的工作流結(jié)構(gòu)。最小租用時(shí)間間隔設(shè)置為10 min，VM獲取延時(shí)acquisitiondelay設(shè)置為1 min，每個(gè)時(shí)間間隔的代價(jià)設(shè)置為：smalle類(lèi)型VM為＄0.01，medium類(lèi)型VM為＄0.02，large類(lèi)型VM為＄0.04，截止時(shí)間設(shè)置為50 min。

圖4 工作流示例

(a) 執(zhí)行時(shí)間矩陣 (b) 數(shù)據(jù)傳輸時(shí)間矩陣圖5 執(zhí)行時(shí)間矩陣和數(shù)據(jù)傳輸時(shí)間矩陣

圖6 預(yù)處理后的工作流結(jié)構(gòu)

算法首先需要通過(guò)式(2)、式(3)、式(4)計(jì)算每個(gè)任務(wù)的最小執(zhí)行時(shí)間MET、最早開(kāi)始時(shí)間EST和最遲完成時(shí)間EFT，計(jì)算結(jié)果如表2所示。然后，比較工作流的最小執(zhí)行時(shí)間MET_W(max(EFT(ti)=49))與截止時(shí)間D(D=50)，由于MET_W小于D，表明截止時(shí)間是可達(dá)的，算法需要繼續(xù)尋找調(diào)度方案。

表2 圖4中工作流各任務(wù)的MET、LFT和XET

首先，通過(guò)算法2進(jìn)行任務(wù)預(yù)處理。算法2通過(guò)合并管道任務(wù)t4、t7和t8、t9為單個(gè)任務(wù)t4+7和t8+9，預(yù)處理后的工作流結(jié)構(gòu)如圖6所示，預(yù)處理后的執(zhí)行時(shí)間矩陣和數(shù)據(jù)傳輸時(shí)間矩陣如圖7所示。

(a) 執(zhí)行時(shí)間矩陣 (b) 數(shù)據(jù)傳輸時(shí)間矩陣圖7 預(yù)處理后的矩陣

預(yù)處理后，WSCO算法通過(guò)式(2)、式(8)、式(10)計(jì)算每個(gè)任務(wù)的最小執(zhí)行時(shí)間MET、最遲完成時(shí)間LFT和期望執(zhí)行時(shí)間XET，結(jié)果如表3所示。

表3 圖6中各個(gè)任務(wù)的MET、LFT和XET(D=50)

然后，算法調(diào)用CheapesttaskVMmap算法尋找代價(jià)最低的VM類(lèi)型調(diào)度入口任務(wù)t1。CheapesttaskVMmap算法設(shè)置XST(t1)為acquisitiondelay，并尋找執(zhí)行代價(jià)最小的VM類(lèi)型。由于三種VM類(lèi)型中，XET(t1,VMm)和XET(t1,VMl)均小于D，算法比較在這兩種VM類(lèi)型上執(zhí)行從t1開(kāi)始的關(guān)鍵路徑得到的代價(jià)，并確定VMm為調(diào)度t1的cheapestapplicableVM。然后，算法獲得VMm類(lèi)型的一個(gè)VM進(jìn)行調(diào)度t1，并更新VM池狀態(tài)。算法在步驟13輸入while循環(huán)，并執(zhí)行循環(huán)過(guò)程直到所有任務(wù)調(diào)度完成。表4-表7列出了算法執(zhí)行過(guò)程中任務(wù)不同參數(shù)的取值變化。

表4 初始狀態(tài)

表5 第1次迭代結(jié)果

表6 第2次迭代結(jié)果

表7 第3次迭代結(jié)果

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

4.1 實(shí)驗(yàn)配置

利用WorkFlowSim[10]構(gòu)建仿真實(shí)驗(yàn)評(píng)估工作流調(diào)度算法性能，選取四種不同領(lǐng)域的現(xiàn)實(shí)科學(xué)工作流作為測(cè)試工作流結(jié)構(gòu)，包括：Montage、CyberShake、LIGO和Epigenomics工作流，不同工作流在執(zhí)行結(jié)構(gòu)和計(jì)算特征上均有所不同，具體可參見(jiàn)文獻(xiàn)[1]。每種工作流均配置三種規(guī)模的任務(wù)，小規(guī)模為30個(gè)任務(wù)，中規(guī)模為100個(gè)任務(wù)，大規(guī)模為1 000個(gè)任務(wù)。

云服務(wù)商提供五種類(lèi)型VM，其配置與處理能力參考Amazon EC2進(jìn)行設(shè)置[11]，具體見(jiàn)表8，其中，一個(gè)ECU等同于1.0～1.2 GHz的Xecon CPU計(jì)算能力，VM間的平均帶寬設(shè)置為20 Mbit/s，接近于Amazon web service的平均帶寬能力。VM的啟動(dòng)時(shí)間設(shè)置為97 s[12]，賬單間隔時(shí)間設(shè)置為10 min。

表8 VMs類(lèi)型配置

設(shè)置三種截止時(shí)間類(lèi)型評(píng)估算法性能，包括嚴(yán)格型、適度型和寬松型，截止時(shí)間D=(1+μ)×MET_W。對(duì)于嚴(yán)格型截止時(shí)間約束，0≤μ<1;對(duì)于適度型截止時(shí)間，1≤μ<2;對(duì)于寬松型截止時(shí)間，2≤μ≤3。且μ可視為約束因子，μ的變化步長(zhǎng)為0.25。選擇基于部分關(guān)鍵路徑算法IC-PCP[5]、健壯代價(jià)時(shí)間算法RCT[6]和健壯時(shí)間代價(jià)算法RTC[6]作為基準(zhǔn)算法進(jìn)行性能比較。

4.2 結(jié)果說(shuō)明

1) 截止時(shí)間約束的評(píng)估。表9給出了算法滿(mǎn)足截止時(shí)間比例的情況。對(duì)于嚴(yán)格型約束，IC-PCP在所有工作流中均無(wú)法滿(mǎn)足截止時(shí)間約束，RCT在四種工作流中按從高到低的滿(mǎn)足率分別為52.5%、47.5%、40%和37.5%，RTC則比RCT的約束滿(mǎn)足率更高，而WSCO是所有算法中對(duì)截止時(shí)間約束滿(mǎn)足最好的。對(duì)于適度型約束，IC-PCP的性能并未得到改善，RCT在先前的基礎(chǔ)上得到了輕微改善，RTC和WSCO則均達(dá)到了對(duì)截止時(shí)間100%的約束滿(mǎn)足。對(duì)于寬松型約束，IC-PCP性能不變，RCT繼續(xù)提高?？梢钥闯?，IC-PCP性能最差，這源于此算法并未預(yù)測(cè)VM的性能改變，且未考慮VM的啟動(dòng)時(shí)間，RCT和RTC基于資源選擇策略，一定程度上忽略了VMs的性能變化，WSCO同時(shí)考慮了以上因素，能夠估算單個(gè)任務(wù)的開(kāi)始時(shí)間和完成時(shí)間，可以盡可能地確保截止時(shí)間內(nèi)完成任務(wù)調(diào)度。

表9 截止時(shí)間滿(mǎn)足比例

續(xù)表9

2) 執(zhí)行時(shí)間與執(zhí)行代價(jià)評(píng)估。圖8同步觀察了平均執(zhí)行時(shí)間和平均執(zhí)行代價(jià)情況，由于為了產(chǎn)生更加經(jīng)濟(jì)的調(diào)度方案需要以更長(zhǎng)的調(diào)度時(shí)間作為代價(jià)，故需同步觀察這兩個(gè)性能表現(xiàn)?？梢钥吹?，IC-PCP產(chǎn)生了最便宜的調(diào)度方案，但其執(zhí)行時(shí)間長(zhǎng)于截止時(shí)間，無(wú)法滿(mǎn)足截止時(shí)間約束。由于算法設(shè)計(jì)的目標(biāo)是生成更高低價(jià)的調(diào)度且滿(mǎn)足截止時(shí)間，因此，以對(duì)截止時(shí)間違例得到的經(jīng)濟(jì)調(diào)度方案也是無(wú)效的。另外三種算法中，RCT在所有約束因子上均產(chǎn)生了最經(jīng)濟(jì)的調(diào)度方案，且調(diào)度時(shí)間也最長(zhǎng)，但約束滿(mǎn)足率平均僅為50%。對(duì)于0～0.25間的嚴(yán)格型約束，WSCO產(chǎn)生了最高代價(jià)調(diào)度但其調(diào)度時(shí)間最短，且其約束滿(mǎn)足率也高于其他算法，這是由于該算法通過(guò)適應(yīng)VM的性能變化能以可接受的代價(jià)降低截止時(shí)間的違例。同時(shí)，在同樣的條件下，RTC以最小的調(diào)度時(shí)間產(chǎn)生了最高代價(jià)的調(diào)度。比較來(lái)說(shuō)，隨著約束因子的增加，WSCO可以充分利用增加的VM空閑時(shí)間在滿(mǎn)足截止時(shí)間約束的同時(shí)得到最低價(jià)的調(diào)度。進(jìn)一步，對(duì)于所有的截止時(shí)間約束因子，平均來(lái)說(shuō)，WSCO相比RTC可以降低34%的代價(jià)和增加46%的調(diào)度時(shí)間，相比RCT可以降低28%的代價(jià)和降低16%的調(diào)度時(shí)間。因此，綜合評(píng)價(jià)，WSCO可以降低代價(jià)并滿(mǎn)足截止時(shí)間來(lái)交付，比對(duì)比算法有著更好的性能表現(xiàn)。對(duì)于嚴(yán)格型約束，算法可交付最高的約束滿(mǎn)意率，代價(jià)也更高。然而，隨著約束變得寬松，WSCO也可充分利用增加的空閑時(shí)槽進(jìn)而降低執(zhí)行代價(jià)。

(a) Montage工作流

(b)LIGO工作流

(c) CyberShake工作流

(d) Epigenomics工作流圖8 性能評(píng)估結(jié)果

5 結(jié) 語(yǔ)

為了解決滿(mǎn)足工作流截止時(shí)間約束的同時(shí)執(zhí)行代價(jià)最優(yōu)化問(wèn)題，提出了一種工作流調(diào)度算法WSCO。算法重點(diǎn)考慮了云資源異構(gòu)、虛擬機(jī)性能動(dòng)態(tài)可變等特征，通過(guò)迭代式的調(diào)度尋優(yōu)，最終得到滿(mǎn)足截止時(shí)間約束且代價(jià)最小化的工作流調(diào)度方案。實(shí)驗(yàn)結(jié)果證明了算法不僅擁有更高的約束滿(mǎn)意度，而且執(zhí)行時(shí)間更短，執(zhí)行代價(jià)更低。