黃志剛 劉 峰

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

0 引 言

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

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

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

1 系統(tǒng)模型

1.1 應(yīng)用模型

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

圖1 工作流示例

1.2 資源模型

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

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

1.3 問題定義

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

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

cheapesttask-VMmapping={(ti→VMv)}

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

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

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

Schedule={ti,vk,tstart,tend}

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

(1)

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

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

文中涉及的主要符號含義說明如表1所示。

表1 符號說明

續(xù)表1

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

(2)

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

(3)

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

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

(4)

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

(5)

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

(6)

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

(7)

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

(8)

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

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

(9)

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

(10)

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

(11)

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

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

(12)

3 算法設(shè)計

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

算法1WSCO算法

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

1.開始

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

3. 若D>MET_W

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

5. 計算MET,LFT和XET

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

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

8.To_Provision←CheapesttaskVMMap(te)

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

9. 生成類型為To_Provision的虛擬機ve

10. 在時間XST(te)時將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)度和正在運行的任務(wù)組成任務(wù)集合to_be_scheduled

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

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

19.結(jié)束

20. 在MET_W以內(nèi)修正截止時間

21.結(jié)束if

22.結(jié)束

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

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

圖2 管道任務(wù)

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

算法2Pre-processing(W)

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

1. 開始

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

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

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

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

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

7. 合并tp和tc為tp+c

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

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

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

11.else

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

13.結(jié)束if

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

15.end

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

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

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

算法3PlanandSchedule算法

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

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

3.vmmap←CheapesttaskVMMap(ti)

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

5.if{vk}存在

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

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

8. 更新虛擬機資源池VM_Pool_Status

9.else

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

11.if{vj}存在

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

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

14. 更新虛擬機資源池VM_Pool_Status

15.else

16. 生成新虛擬機

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

18. 更新虛擬機資源池VM_Pool_Status

19. 結(jié)束if

20.結(jié)束if

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

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

23.返回

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

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

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

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

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

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

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

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

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

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

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

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

算法4CheapesttaskVMMap(t)算法

1. 開始

2. 映射集合taskvmmap置空

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

5. 將正在運行最后一個父任務(wù)的虛擬機賦予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. 尋找滿足(XST(t)+XET(t,VMk))≤D的集合{VMk}

19. 將虛擬機VMj置入映射集合taskvmmap

20. 返回映射集合taskvmmap

3.3 算例說明

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

圖4 工作流示例

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

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

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

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

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

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

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

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

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

表4 初始狀態(tài)

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

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

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

4 仿真實驗

4.1 實驗配置

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

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

表8 VMs類型配置

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

4.2 結(jié)果說明

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

表9 截止時間滿足比例

續(xù)表9

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

(a) Montage工作流

(b)LIGO工作流

(c) CyberShake工作流

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

5 結(jié) 語

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