一種基于優(yōu)先級的云工作流動態(tài)調(diào)度方法

范貴生,陳興鵬,虞慧群

1(華東理工大學(xué) 信息科學(xué)與工程系,上海 200237) 2(上海市計算機軟件測評重點實驗室,上海 201112)

1 引 言

隨著云計算和云基礎(chǔ)設(shè)施的快速發(fā)展,越來越多的工作流應(yīng)用正在從傳統(tǒng)的分布式平臺向云端過渡.工作流調(diào)度是一個眾所周知的NP難題[1],其旨在為工作流中的每個任務(wù)分配計算資源以滿足如時間、能耗和成本等性能指標(biāo).一個工作流可以通過一個有向無環(huán)圖來表示,其中節(jié)點代表工作流的每個任務(wù),邊代表任務(wù)之間的依賴關(guān)系.用戶對應(yīng)用的請求被描述為一個工作流,應(yīng)用服務(wù)器將工作流中的每個任務(wù)分發(fā)到相應(yīng)的云服務(wù)進行執(zhí)行,以優(yōu)化任務(wù)執(zhí)行周期[2].

當(dāng)現(xiàn)有服務(wù)實例不能滿足工作流的性能要求時,通過創(chuàng)建新的服務(wù)實例以實現(xiàn)執(zhí)行成本和系統(tǒng)性能之間的折衷[3].云提供商提供具有不同處理能力和租賃成本的服務(wù)資源,用戶根據(jù)需求選擇不同的服務(wù)類型和服務(wù)數(shù)量,以滿足應(yīng)用工作流的時間約束和執(zhí)行成本.當(dāng)用戶面臨服務(wù)選擇時,一般的方法是在滿足工作流的最后期限的同時,最小化工作流的執(zhí)行成本,有兩大類方法可以解決這個問題:局部啟發(fā)式和元啟發(fā)式.目前,無論啟發(fā)式算法還是元啟發(fā)式算法,主要關(guān)注的是調(diào)度方案是否能夠滿足工作流的一個整體時間約束,而不是具體到是否滿足工作流的每個任務(wù)的子截止時間.而且,在任務(wù)調(diào)度過程中基本上是基于工作流任務(wù)優(yōu)先級的靜態(tài)調(diào)度,并沒有根據(jù)云中服務(wù)資源的可變性,動態(tài)調(diào)整工作流任務(wù)調(diào)度優(yōu)先級.

基于以上問題,本文提出了一種基于優(yōu)先級的動態(tài)調(diào)度算法(Priority-based and Dynamic Scheduling,Pbads)來解決滿足時間約束的工作流任務(wù)調(diào)度問題.主要工作如下:

1)根據(jù)工作流任務(wù)之間的依賴性,將相關(guān)聯(lián)的多任務(wù)合并為單任務(wù),以降低在調(diào)度過程中不同服務(wù)之間的數(shù)據(jù)傳輸成本.其次,根據(jù)用戶工作流的時間約束,為每個任務(wù)分配其子截止期限,并基于任務(wù)的子截止期限和計算任務(wù)的緊急程度,也即調(diào)度優(yōu)先級.根據(jù)任務(wù)的優(yōu)先級對工作流中的任務(wù)進行排序,生成調(diào)度隊列.

2)在任務(wù)調(diào)度過程中,Pbads基于時間約束動態(tài)調(diào)整任務(wù)調(diào)度優(yōu)先級和子父任務(wù)調(diào)度決策,為每個任務(wù)分配一個成本增量最小的服務(wù).對于每一個服務(wù),每當(dāng)分配一個新的任務(wù)時,Pbads會遍歷該服務(wù)的執(zhí)行隊列的每個可插入位置,可以是隊列的頭部、隊列的尾部以及每個任務(wù)的前后位置,判斷當(dāng)前執(zhí)行位置是否為可以滿足任務(wù)子期限和依賴約束,并在可行位置中選擇一個任務(wù)執(zhí)行成本最小的位置.

3)在實驗中,本文將Pbads方法與現(xiàn)有方法(ProLiS[4]、L-ACO[4]、COHA[5]、CPDE[6]和IC-PCP[7])使用4種數(shù)據(jù)集進行實驗比較.結(jié)果表明,Pbads算法在執(zhí)行成本和滿足工作流時間約束方面具有更好的表現(xiàn).

本文的其余部分安排如下:第2節(jié)介紹了工作流調(diào)度的相關(guān)工作.第3節(jié)是工作流調(diào)度的成本優(yōu)化問題模型.第4節(jié)提出了云中工作流動態(tài)調(diào)度方法.最終的實驗結(jié)果在第5部分.第6節(jié)是對當(dāng)前工作的總結(jié)和未來工作的展望.

2 相關(guān)工作

傳統(tǒng)的分布式系統(tǒng)中,工作流調(diào)度工作關(guān)注如何最小化工作流的執(zhí)行時間,而云環(huán)境中工作流的執(zhí)行成本也是一個不可忽視的因素,因此如何權(quán)衡工作流的執(zhí)行時間和執(zhí)行成本尤為重要.

為了解決基于截止期限的工作流調(diào)度問題,文獻[4]提出了一種啟發(fā)式算法ProLiS和一種元啟發(fā)式算法L-ACO.ProLiS算法為每個工作流任務(wù)分配子截止期限,根據(jù)任務(wù)的緊急程度建立了一個有序的任務(wù)列表,并將每個任務(wù)分配給滿足其子截止期限且成本增量最少的服務(wù).L-ACO算法是基于蟻群算法來解決時間約束的成本優(yōu)化問題:螞蟻通過更新信息素軌跡,查找全局最優(yōu)解.然后每只螞蟻都為問題建立一個解決方案,存儲局部最優(yōu)的解決方案,然后更新信息素軌跡,整個過程不斷重復(fù),直到返回全局最優(yōu)解.文獻[5]設(shè)計了一種任務(wù)拆分算法COHA,該算法將無法滿足子截止期限的工作流任務(wù)拆分為兩個子任務(wù),為其分配子截止期限,并添加到任務(wù)隊列中進行重新調(diào)度,以此來確保所有的任務(wù)都能按時完成.文獻[6]基于關(guān)鍵路徑提出了一種的成本預(yù)測算法CPDE,該算法通過使用現(xiàn)存虛擬機和創(chuàng)建新虛擬機兩種方式來滿足工作流截止期限約束,并通過預(yù)測每個任務(wù)調(diào)度成本以此來確定工作流整體調(diào)度成本最低的方案.文獻[7]基于工作流部分關(guān)鍵路徑提出一種的啟發(fā)式算法IC-PCP,該算法通過遞歸的方式,從已分配的任務(wù)出發(fā)構(gòu)造局部關(guān)鍵路徑,每個關(guān)鍵路徑上的任務(wù)被安排到成本最低且滿足子截止期限約束的虛擬機上.文獻[8]提出了一種主動響應(yīng)式工作流調(diào)度算法,當(dāng)新工作流到達時,該算法僅將當(dāng)前所有工作流的就緒任務(wù)進行混合調(diào)度,在滿足截止期限的約束下選擇執(zhí)行成本最小的虛擬機.文獻[9]提出了一種時間預(yù)算雙重約束的調(diào)度算法BDAS,該算法對工作流結(jié)構(gòu)進行分層,將工作流任務(wù)劃分為若干無關(guān)聯(lián)性的包任務(wù),以增大調(diào)度過程中的并行程度.文獻[10]考慮到私有云有限的資源以及隱私暴露的風(fēng)險,提出了一種在混合云環(huán)境下,成本與隱私感知的調(diào)度算法CPHC,該算法在滿足工作流截止期限和隱私保護需求的前提下,盡可能多的將工作流任務(wù)調(diào)度到私有云環(huán)境,以此來最小化工作流執(zhí)行成本.文獻[11]改進了基于遺傳算法的批處理工作流任務(wù)的調(diào)度算法BIGA,基于獨立任務(wù)和非獨立任務(wù)兩種任務(wù)類型,進行調(diào)度成本優(yōu)化.文獻[12]基于已知的HEFT算法,提出了一種預(yù)算和期限約束算法BDSD,該算法基于工作流任務(wù)的子截止期限定義任務(wù)的調(diào)度優(yōu)先級,并考慮預(yù)算和期限雙重約束下的調(diào)度成功率.文獻[13]提出了一種多約束的工作流調(diào)度算法,該算法基于最慢執(zhí)行效率的虛擬機計算工作流可用預(yù)算,以此來構(gòu)建可用虛擬機集合,并定義了一個平衡因子,針對每個工作流任務(wù)開發(fā)了一種資源選擇方法,以滿足工作流任務(wù)的時間約束的前提下最小化其執(zhí)行成本.文獻[14]提出了EIPR算法,該算法利用預(yù)分配資源的空閑時間和預(yù)算盈余來復(fù)制任務(wù),隨著可用于復(fù)制的預(yù)算增加,同時也增加了滿足工作流最后期限的可能性,減少了應(yīng)用程序的總執(zhí)行時間.文獻[15]提出了一種截止期限感知的啟發(fā)式算法DCEDA,該算法通過工作流最短執(zhí)行時間來確定其截止期限,通過實時監(jiān)控資源池,動態(tài)為工作流任務(wù)分配執(zhí)行成本最低的虛擬機.文獻[16]提出了一種分而治之的調(diào)度算法DQWS,該算法首先為工作流關(guān)鍵路徑上的任務(wù)選擇滿足截止期限并且執(zhí)行成本最低的資源,然后將關(guān)鍵路徑上的任務(wù)從工作流中移除,工作流分為若干子工作流,針對每個子工作流重復(fù)上述過程直到全部任務(wù)分配完成.

為了解決基于預(yù)算約束的大規(guī)模多任務(wù)工作流調(diào)度問題,文獻[17]提出了一種預(yù)算敏感的調(diào)度算法ScaleStar,該算法將當(dāng)前需要分配的任務(wù)分配給更好的計算資源執(zhí)行,有效平衡了工作流的執(zhí)行時間和成本.文獻[18]提出了一種公平預(yù)算約束的調(diào)度算法FBCWA,該算法通過對工作流任務(wù)進行分類,通過調(diào)整成本時間因素,為每個工作流任務(wù)提供一種公平的預(yù)算約束調(diào)度算法.文獻[19]提出了一種異構(gòu)預(yù)算約束調(diào)度算法HBCS,旨在在用戶定義的執(zhí)行成本下最小化工作流任務(wù)的執(zhí)行時間,其主要貢獻在于該算法實現(xiàn)了更低的時間復(fù)雜度.文獻[20]提出了一種基于任務(wù)復(fù)制的調(diào)度算法TDSA,該算法回收已分配工作流任務(wù)未使用的預(yù)算資源并進行重新分配,利用資源上的空閑時間槽選擇性地復(fù)制任務(wù)的前驅(qū)任務(wù),從而在保證工作流任務(wù)的子預(yù)算約束的同時減少任務(wù)的完成時間.文獻[21]基于云的計算資源構(gòu)建工作流的性能分析模型,并提出了一種臨界貪婪算法,以在云預(yù)算約束下實現(xiàn)科學(xué)工作流的最小端到端延遲.文獻[22]根據(jù)工作流任務(wù)優(yōu)先級為其分配預(yù)算約束,并且優(yōu)先保證工作流關(guān)鍵路徑任務(wù)分配至最佳虛擬機,其他任務(wù)按照更新的預(yù)算成本選擇合適的虛擬機.文獻[23]等擴展了經(jīng)典的異構(gòu)最早完成時間算法并提出了BHEFT,它決定是否使用用戶設(shè)置的特定約束,并在截止日期和預(yù)算約束的前提下工作.文獻[24]提出了一種資源分配機制和工作流調(diào)度算法GRP-HEFT,旨在現(xiàn)代IaaS云小時成本模型中最小化給定工作流的完成時間,提出了一種貪心算法,通過服務(wù)實例的效率列出實例類型,并在預(yù)算約束下選擇效率最高的實例.

總之,無論是基于成本約束還是時間約束的工作流調(diào)度,都在優(yōu)化性能方面做了很多努力.但是很多工作是基于整個工作流維度的,而不是特定于工作流中的每個任務(wù).而且在調(diào)度過程中,沒有考慮到云中資源的可變性,任務(wù)的調(diào)度順序是靜態(tài)的,不會隨著調(diào)度過程而變化.因此,本文試圖從工作流任務(wù)維度入手,考慮到云服務(wù)的異構(gòu)性和任務(wù)之間的依賴性,動態(tài)調(diào)整任務(wù)的優(yōu)先級以及調(diào)度策略.

3 工作流調(diào)度模型

3.1 系統(tǒng)模型

當(dāng)用戶向應(yīng)用程序發(fā)出請求時,應(yīng)用程序會將請求以工作流的形式在云端執(zhí)行.工作流可以用一個有向無環(huán)圖表示,WF=(Nodes,Edges),其中Nodes表示工作流任務(wù)的集合{t1,t2,…,tn},任務(wù)之間相互獨立,并且具有不同工作負載twi;Edges則是不同任務(wù)之間的依賴關(guān)系的集合,edgei=(ti,tj)表示任務(wù)ti和tj之間的依賴關(guān)系或優(yōu)先級,只有當(dāng)ti完成后,tj才能開始執(zhí)行.datai,j表示ti到tj之間的數(shù)據(jù)傳輸量,因此只有當(dāng)ti執(zhí)行完成并且數(shù)據(jù)傳輸完成后,tj才能開始執(zhí)行.為了形象地描述一個工作流,方便后續(xù)工作的開展,為每個工作流添加兩個工作負載為零的任務(wù)tentry和texit,將這兩個任務(wù)作為工作流的入口任務(wù)和出口任務(wù).具體工作流示例如圖1所示.

圖1 工作流結(jié)構(gòu)圖Fig.1 Workflow structure diagram

云中存在一組具有不同處理能力和不同租賃成本的服務(wù)集合Service={sl},工作流的執(zhí)行成本按照在工作流執(zhí)行期間租用云中服務(wù)的租金來表示.本文根據(jù)按需定價模型計算工作流的執(zhí)行成本,工作流執(zhí)行成本根據(jù)工作流使用云中服務(wù)的時間間隔數(shù)進行計算,例如小于一個時間間隔會按照一個時間間隔計算.使用TI表示一個時間間隔,對于服務(wù)sl,使用Calc(sl)表示服務(wù)的處理能力,使用Cost(sl)表示服務(wù)在一個時間段內(nèi)的租用成本.

當(dāng)任務(wù)ti分配給服務(wù)sl進行執(zhí)行時,ti的工作負載為twi,sl的處理能力為Calc(sl),因此ti的執(zhí)行時間可以計算為:

ET(i,l)=twi/Calc(sl)

(1)

假設(shè)云中所有的服務(wù)資源都在同一個區(qū)域內(nèi),因此不同服務(wù)之間的帶寬bw大致相等,同一服務(wù)中的傳輸延遲為零.因此,不同任務(wù)之間的數(shù)據(jù)傳輸時間取決于任務(wù)所分配的服務(wù)以及任務(wù)之間的數(shù)據(jù)傳輸量.ts(ti)表示任務(wù)ti所分配到的服務(wù),數(shù)據(jù)傳輸時間TT(i,j)可以通過以下方式計算:

(2)

如果將任務(wù)ti分配給服務(wù)sl進行執(zhí)行,RT(i,l)表示服務(wù)sl可以執(zhí)行ti的最早開始時間.那么任務(wù)ti的開始執(zhí)行時間ST(i,l)和完成時間FT(i,l)可以計算為:

(3)

FT(i,l)=ST(i,l)+ET(i,l)

(4)

服務(wù)的總租賃時間可以通過服務(wù)租賃開始時間RSTl和租賃結(jié)束時間RETl來計算,并將服務(wù)總租賃時間轉(zhuǎn)換為時間間隔數(shù)來計算服務(wù)的使用成本MSC(sl).那么MSC(sl)可以通過以下方式計算:

MSC(sl)=「(RETl-RSTl)/TI?×Cost(sl)

(5)

此外,云中服務(wù)sl的租用時間從部署在sl上的第一個任務(wù)ti接收其父任務(wù)數(shù)據(jù)開始,到部署在sl上的最后一個任務(wù)tj執(zhí)行完成且數(shù)據(jù)傳輸完成時結(jié)束:

(6)

(7)

3.2 問題描述

工作流旨在將每個任務(wù)分配給相應(yīng)的服務(wù)進行執(zhí)行以滿足用戶的需求.因此任務(wù)調(diào)度可以用來表示.R={s1,s2,…,sn}表示一組已分配的服務(wù)資源,每個服務(wù)的處理能力和運行成本也不同.M由一組任務(wù)資源映射組成,每個m=表示任務(wù)ti被分配到服務(wù)sl執(zhí)行,任務(wù)ti開始執(zhí)行時間為ST(i,l),完成時間為FT(i,l).因此整個工作流的執(zhí)行時間WFT(R,M)可以通過以下方式計算:

(8)

工作流執(zhí)行總成本W(wǎng)FC(R,M)可以通過以下方式獲得:

(9)

使用D表示用戶指定的工作流的截止期限.因此滿足時間約束的云工作流成本優(yōu)化問題定義為:

(10)

4 基于優(yōu)先級的動態(tài)調(diào)度算法

圖2 工作流調(diào)度模型Fig.2 Workflow scheduling model

4.1 任務(wù)預(yù)處理階段

1)任務(wù)合并.為了減少工作流調(diào)度過程中的不同服務(wù)之間的數(shù)據(jù)傳輸開銷,將多個相關(guān)聯(lián)的工作流任務(wù)被合并為單個任務(wù)(圖3).這不僅降低了多個任務(wù)之間的數(shù)據(jù)傳輸成本,而且還減少了循環(huán)監(jiān)控調(diào)度信息時產(chǎn)生的時間開銷.工作流任務(wù)合并條件如下:任務(wù)ti是任務(wù)tj的父任務(wù),當(dāng)ti有唯一的子任務(wù)tj,且tj有唯一的父任務(wù)ti時,ti和tj合并為ti+j.當(dāng)ti和tj被分配到不同的服務(wù)上執(zhí)行,就會產(chǎn)生任務(wù)之間的數(shù)據(jù)傳輸成本,而任務(wù)合并就會避免成本的產(chǎn)生.算法1規(guī)定了任務(wù)合并的具體步驟.注意:ti為除出口任務(wù)texit以外的所有工作流任務(wù),其中任務(wù)下標(biāo)索引i的變化范圍為[0,n-1),n為當(dāng)前工作流任務(wù)總數(shù).

圖3 任務(wù)合并示例圖Fig.3 Task merge example diagram

2)任務(wù)截止期限分配.在本文中,依據(jù)文獻[4]中的所提出的方法為工作流中的每個任務(wù)分配子截止期限.任務(wù)ti的子截止期限tdli由其任務(wù)等級tri決定的.任務(wù)等級的含義類似于工作流的關(guān)鍵路徑,即從任務(wù)ti到出口任務(wù)texit的預(yù)期執(zhí)行時間的長度.任務(wù)等級是通過從出口任務(wù)texit向前遍歷來計算得到的,并為每個任務(wù)選擇最快的服務(wù)s*計算任務(wù)執(zhí)行時間,其原因是考慮到調(diào)度問題的第一個目標(biāo)是滿足截止期限約束.因此任務(wù)等級tri可以通過以下方式獲得:

(11)

dj表示是否考慮任務(wù)的數(shù)據(jù)傳輸延遲[4].ccrj是任務(wù)tj的執(zhí)行時間與任務(wù)通信的比率,即(twj/Calc(ms*))/(datai,j/bw),rand()是一個隨機函數(shù),用于返回[0,1]中的隨機數(shù),o是一個大于1的參數(shù):

(12)

通過入口任務(wù)到當(dāng)前任務(wù)的最長路徑,按比例的為工作流中的每一個任務(wù)設(shè)置一個子截止期限tdli.

(13)

3)任務(wù)排序.為每個工作流添加兩個執(zhí)行時間為零、傳輸時間為零的任務(wù)tentry和texit,并將這兩個任務(wù)作為工作流的入口和出口.此外,根據(jù)任務(wù)緊迫性對工作流任務(wù)進行排序,任務(wù)緊迫性ui可以通過以下方式獲得.

(14)

其中tdli表示任務(wù)的子截止期限,ni表示從任務(wù)ti到任務(wù)texit的關(guān)鍵路徑上的任務(wù)數(shù)量.因此,當(dāng)任務(wù)的子截止期限越小,到任務(wù)texit的關(guān)鍵路徑上的任務(wù)越多,即u值越小,任務(wù)的緊急度越高.

依托在中國、亞洲、澳洲、歐洲、美洲成立的五大研發(fā)中心，聚力斐雪派克、GE Appliances、海爾、卡薩帝、統(tǒng)帥五大頂級廚電品牌，相信未來海爾會推出更多行業(yè)領(lǐng)先的廚電產(chǎn)品，滿足不同用戶的個性化、多樣化需求，創(chuàng)造出更加舒適、更加健康的廚房環(huán)境。

算法1.任務(wù)合并算法

輸入:由n個任務(wù)組成的工作流WF=(Nodes,Edges)

輸出:任務(wù)合并完成后的工作流WF=(Nodes,Edges)

1.通過入口任務(wù)tentry生成任務(wù)隊列Queue;

2.foreach 任務(wù)tiinQueuedo

3.ifti有唯一子任務(wù)tjthen

4.iftj有唯一父任務(wù)tithen

5. 更新任務(wù)tj的工作負載twj=twi+twj;

6. 更新任務(wù)tj的父任務(wù)集合;

7. 更新任務(wù)ti的父任務(wù)的子任務(wù)集合;

8.end

9.end

10.將ti從任務(wù)隊列Queue移除;

11.end

4.2 任務(wù)調(diào)度階段

工作流任務(wù)調(diào)度的主要過程如算法2所示.首先,根據(jù)任務(wù)之間的依賴關(guān)系將多個任務(wù)合并為單任務(wù),并為每個合并后的任務(wù)分配子截止期限.然后,根據(jù)每個任務(wù)的子截止期限和該任務(wù)到出口任務(wù)關(guān)鍵路徑的任務(wù)數(shù)計算該任務(wù)的調(diào)度優(yōu)先級.最后,根據(jù)任務(wù)調(diào)度優(yōu)先級對工作流任務(wù)進行排序生成任務(wù)隊列,并根據(jù)任務(wù)隊列依次對任務(wù)進行調(diào)度分配.

算法2.任務(wù)調(diào)度算法

輸入:R←?,M←?

輸出:任務(wù)資源映射結(jié)果

1.調(diào)用任務(wù)合并算法進行工作流任務(wù)合并;

2.Queue=基于任務(wù)優(yōu)先級初始化任務(wù)調(diào)度隊列;

3.foreach 任務(wù)tiinQueuedo

4.listp=任務(wù)ti及其已調(diào)度的直接父任務(wù)集合;

5.collectionc=listc的調(diào)度序列的集合;

6.listmin=collectionc中滿足任務(wù)時間約束和依賴關(guān)系,且執(zhí)行成本最低的序列;

7. for each 任務(wù)tpinlistmindo

8. 調(diào)用服務(wù)選擇算法選擇執(zhí)行成本最小的服務(wù)sp;

9.if服務(wù)sp屬于已分配的服務(wù)資源Rthen

10. 將服務(wù)sp添加到R中;

11.end

12. 計算任務(wù)tp在服務(wù)sp上執(zhí)行的開始時間ST(tp,sp)和完成時間FT(tp,sp);

13. 更新M←;

14.listt=分配給服務(wù)sp的任務(wù)隊列;

15.foreach 可插入位置piinlisttdo

16. 將任務(wù)tp插入到pi位置進行隊列重排序;

17.if重排序后的隊列調(diào)度順序滿足每個任務(wù)的子截止期限和依賴關(guān)系then

18.計算該隊列調(diào)度的執(zhí)行成本;

19.end

20. 將tp插入到一個執(zhí)行成本最低的位置;

21.end

22.end

23.listc=任務(wù)ti的未調(diào)度的直接子任務(wù)集合;

24.collectionc=listc的調(diào)度序列的集合;

25.foreach 序列qiincollectioncdo

26. if 序列qi滿足任務(wù)的子截止期限和依賴關(guān)系then

27. 計算當(dāng)前調(diào)度序列qi的執(zhí)行成本;

28.end

29. 選擇執(zhí)行成本最低的調(diào)度序列更新Queue

30.end

31.end

32.返回

考慮到父任務(wù)與子任務(wù)在不用服務(wù)之間的所產(chǎn)生的數(shù)據(jù)傳輸成本,因此當(dāng)一個新的任務(wù)被調(diào)度時,會獲取當(dāng)前任務(wù)且已經(jīng)調(diào)度完成的父任務(wù)集合,并與當(dāng)前任務(wù)形成一個局部調(diào)度隊列,動態(tài)調(diào)整任務(wù)的調(diào)度策略以實現(xiàn)當(dāng)前調(diào)度成本增量最小化.具體過程如下:首先遍歷局部調(diào)度隊列,為每個任務(wù)選擇一個全局成本增量最小的服務(wù)(第6行),具體過程見算法3.然后更新任務(wù)的開始執(zhí)行時間和完成時間,并得到任務(wù)ti所分配的服務(wù)sl的當(dāng)前任務(wù)隊列.遍歷服務(wù)任務(wù)隊列的所有可插入位置,如任務(wù)隊列的第一個位置,任務(wù)隊列中每個任務(wù)后面的位置,以及任務(wù)隊列的末端.判斷將當(dāng)前任務(wù)ti插入到該位置后,服務(wù)任務(wù)隊列是否滿足任務(wù)之間的依賴關(guān)系以及任務(wù)的子截止期限約束,并計算所有可行的服務(wù)任務(wù)隊列的執(zhí)行成本.通過比較執(zhí)行成本,選擇一個成本最低的插入位置(第13～20行).

每當(dāng)一個任務(wù)調(diào)度完成后,獲取該任務(wù)的未調(diào)度的子任務(wù)集合,根據(jù)當(dāng)前的調(diào)度信息動態(tài)調(diào)整子任務(wù)集合中每個任務(wù)的的調(diào)度優(yōu)先級,生成一個執(zhí)行成本增量最小的局部調(diào)度序列,并以此修改任務(wù)隊列的整體調(diào)度順序,從而達到動態(tài)調(diào)整任務(wù)優(yōu)先級的目的(第21～31行).

算法3主要目的是為任務(wù)選擇一個執(zhí)行成本增量最小的服務(wù),具體過程如下:首先,從已分配服務(wù)資源池中選擇一個滿足任務(wù)子截止期限約束且執(zhí)行成本增量最小的的服.注意,該處的成本增量的計算方法是添加任務(wù)ti后服務(wù)sl的執(zhí)行成本減去添加ti前的服務(wù)執(zhí)行成本.如果服務(wù)資源池中不存在既滿足任務(wù)子截止期限,且服務(wù)執(zhí)行成本增量最少的的服務(wù),那么則從服務(wù)資源池中選擇任務(wù)執(zhí)行時間最短的服務(wù).此外,若所選擇的服務(wù)不是處理效率最快的服務(wù)類型,那么將其更新為最快的服務(wù)類型.服務(wù)候選者包括解決方案(即M)中已經(jīng)使用的所有服務(wù),以及那些尚未使用但可以隨時添加到M中的服務(wù).

算法3.服務(wù)選擇算法

輸入:任務(wù)ti

輸出:服務(wù)sl

1.TTmax=任務(wù)ti與其子任務(wù)之間最大的數(shù)據(jù)傳輸時延;

2.Pool=正在執(zhí)行任務(wù)的的服務(wù)資源池;

3.foreach 服務(wù)slinPooldo

4. 計算任務(wù)ti在服務(wù)sl上執(zhí)行的開始時間ST(ti,sj)和完成時間FT(ti,sl);

5.ifFT(ti,sl)

6. 計算任務(wù)ti在服務(wù)sl上執(zhí)行的成本;

7.end

8. 選擇一個滿足任務(wù)子截止期限且執(zhí)行成本最低的服務(wù)sl;

9.end

10.ifPool不存在滿足上述條件約束的服務(wù)then

11.sl=服務(wù)資源池中執(zhí)行任務(wù)ti時間最少的服務(wù);

12. 計算任務(wù)ti在服務(wù)sl上執(zhí)行的開始時間ST(ti,sl)和完成時間FT(ti,sl);

13.ifFT(ti,sl)>tdli且服務(wù)sl不是處理速度最快的服務(wù)then

14. 將sl更新為處理速度最快的服務(wù);

15.end

16.end

17.返回服務(wù)sl

4.3 算法復(fù)雜度分析

基于由n個任務(wù)組成的工作流進行算法時間復(fù)雜度分析.Pbads算法,工作流任務(wù)的最大依賴為n(n-1)/2,故截止期限分配階段的時間復(fù)雜度為O(n2),基于優(yōu)先級進行任務(wù)排序的時間復(fù)雜度為O(nlogn),任務(wù)調(diào)度階段,服務(wù)候選者數(shù)量的上限是n+s,其中s是服務(wù)類型的集合,在任務(wù)循環(huán)調(diào)度過程中,遍歷候選服務(wù)的時間復(fù)雜度為O(n(n+s)).考慮當(dāng)前任務(wù)的父任務(wù)調(diào)度決策和子任務(wù)優(yōu)先級動態(tài)調(diào)整,并且當(dāng)新任務(wù)到達服務(wù)時進行插入重排,分配給每個服務(wù)的最大任務(wù)數(shù)為n,因此任務(wù)調(diào)度階段的時間復(fù)雜度為O(n2(n+s));因此Pbads算法時間的復(fù)雜度為O(n2(n+s)).

ProLiS算法,為每個工作流任務(wù)分配子截止期限的時間復(fù)雜度為O(n2);候選服務(wù)數(shù)量上限為n+s,因此ProLiS算法的時間復(fù)雜度為O(n(n+s)).L-ACO算法,大小為colSize的蟻群迭代maxNo次,共構(gòu)建colSize×maxNo個解,基于ProLiS算法的工作流任務(wù)調(diào)度過程,L-ACO算法的時間復(fù)雜度為O(colSize×maxNo×n(n+s)).COHA算法,將n個任務(wù)組成的工作流拆分后最大任務(wù)數(shù)為2n;候選服務(wù)數(shù)量上限為2n+s,因此COHA算法的時間復(fù)雜度為O(2n(2n+s)).CPDE算法,有s種虛擬機類型,候選虛擬機數(shù)量上限為n+s,因此CPDE算法任務(wù)調(diào)度過程的時間復(fù)雜度為O(n(n+s)).IC-PCP算法,對n個任務(wù)組成的工作流構(gòu)造局部關(guān)鍵路徑,最大可用資源數(shù)為n+s,因此IC-PCP算法的時間復(fù)雜度為O(n(n+s)).

在任務(wù)數(shù)量為n,可用資源數(shù)量為n+s的情況下,ProLiS算法、CPDE算法、IC-PCP算法和COHA算法每調(diào)度一個任務(wù)需要遍歷一遍可用資源,而COHA算法任務(wù)拆分后任務(wù)數(shù)量最大為2n,可用資源數(shù)量為2n+s,因此COHA算法復(fù)雜度大于其余3種算法.而Pbads算法在調(diào)度完任務(wù)后需要遍歷可用資源上已分配任務(wù),因此Pbads算法復(fù)雜度大于上述4種算法.L-ACO算法需構(gòu)建colSize×maxNo個解,每個求解過程復(fù)雜度為O(n(n+s)).綜上所述,本文提到的6種算法的復(fù)雜度對比如下:L-ACO算法>Pbads算法>COHA算法>ProLiS算法、CPDE算法、IC-PCP算法.

5 實驗與分析

本節(jié)詳細闡述了實驗設(shè)置和實驗指標(biāo),進行了模擬實驗,并將實驗結(jié)果與現(xiàn)有方法進行比較.

5.1 實驗設(shè)置

基于模擬實驗,使用4種不同科學(xué)工作流(CyberShake,LIGO,Montage和SIPHT)來評估所提出的Pbads方法.這4種工作流應(yīng)用在結(jié)構(gòu)、依賴關(guān)系和通信數(shù)據(jù)等方面各不相同,圖4描述了每種應(yīng)用的一個簡單工作流結(jié)構(gòu).

圖4 4種科學(xué)工作流結(jié)構(gòu)示例Fig.4 Example of four realistic scientific workflows

圖4(a)CyberShake工作流應(yīng)用于地震科學(xué),通過生成地震分布圖來描述一個地區(qū)的地震嚴(yán)重程度,它可以被歸類為數(shù)據(jù)密集型的工作流,對服務(wù)內(nèi)存和CPU有很大的要求;圖4(b)LIGO工作流應(yīng)用在引力物理學(xué)中,檢測宇宙中各種事物產(chǎn)生的引力波,這個工作流任務(wù)是CPU密集型任務(wù),需要消耗大量內(nèi)存;圖4(c)Montage是一個天文學(xué)應(yīng)用,用于生成天空的自定義馬賽克,其大部分任務(wù)是I/O密集型,不需要太多的CPU性能;圖4(d)SIPHT用于自動搜索NCBI數(shù)據(jù)庫中細菌復(fù)制子的非翻譯RNA.關(guān)于以上4種工作流的詳細信息,可以參考文獻[25]進行了解和學(xué)習(xí).從每個工作流選擇4種規(guī)模,分別是50、100、200和300個任務(wù),此外對于每種規(guī)模都使用了20個服務(wù)實例.

實驗中,假設(shè)云服務(wù)提供商提供5種不同類型的服務(wù),每種服務(wù)都有不同的處理能力和執(zhí)行成本,具體信息如表1所示.每一種服務(wù)的配置及其處理能力是基于EC2云服務(wù)的性能分析[26].服務(wù)的定價是基于亞馬遜EC2的現(xiàn)行定價方案.參考文獻[27]中的設(shè)置,將不同服務(wù)之間的平均帶寬設(shè)置為20MBps,這是亞馬遜網(wǎng)絡(luò)服務(wù)中提供的近似平均帶寬,并計費間隔TI設(shè)置為一小時.

表1 不同服務(wù)類型的處理速度和成本表Table 1 Processing speed and cost table for different service types

此外,引入松弛系數(shù)λ來表示截止期限的寬松程度,MF和MC表示工作流分別在效率最快的服務(wù)和成本最低的服務(wù)上執(zhí)行的成本,工作流的截止期限可以通過以下方式確定.

D=MF+(MC-MF)×λ

(15)

對于任務(wù)等級定義中的參數(shù)o,參考文獻[4]中的方法,分別使用1、1.5、2、4、8、10這6個值測試了Pbads在4種不同工作流程中的表現(xiàn),λ取值從0到0.2,步長為0.02.結(jié)果表明,Pbads在o取值為1.5時表現(xiàn)最好,因此在下面的實驗中,o設(shè)置為1.5.

5.2 度量指標(biāo)

將本文方法Pbads與ProLiS、L-ACO、COHA、CPDE、和IC-PCP 進行比較,對于每個工作流,使用上述6種算法來計算其執(zhí)行成本.但是每一種算法,都會存在不滿足最后期限約束的解決方案,因此只比較每種算法解決方案的執(zhí)行成本是不全面的.針對上述問題,引入算法成功率的概念,即每種算法成功調(diào)度的工作流數(shù)量與總調(diào)度的數(shù)量的比率.通過比較算法成功率和其解決方案的執(zhí)行成本來綜合評估算法的有效性.

5.3 結(jié)果分析

在實驗過程中,按照步長為0.005,將松弛系數(shù)λ從0.005遞增到0.05,以此評估上述6種算法方法在滿足任務(wù)截止期限約束的前提下執(zhí)行工作流的有效性(成功率)和執(zhí)行效率(執(zhí)行成本).圖5描述了6種算法基于松弛系數(shù)由小到大的過程中,平均成功率的變化折線圖.由圖5可以發(fā)現(xiàn),λ值越大,即工作流截止期限越靠后,算法的總體成功率越高.本文提出的Pbads算法在CyberShake數(shù)據(jù)集中略遜于L-ACO算法,在其余3種數(shù)據(jù)集中成功率表現(xiàn)最優(yōu).

圖5 λ在0.005至0.05變化情況下,每種算法的成功率Fig.5 Success percentage of each approach with λ varying from 0.005 to 0.05

圖6描述了在不同的松散系數(shù)λ下,6種算法的標(biāo)準(zhǔn)化成本.由圖6可以發(fā)現(xiàn),隨著松散系數(shù)值越大,工作流的執(zhí)行成本越低.對比其余4種算法,在LIGO、Montage和SIPHT這3種工作流數(shù)據(jù)集中,無論截止期限因子λ變化如何,Pbads算法整體的執(zhí)行成本都小于其他5種算法.

圖6 λ在0.005至0.05變化情況下,每種算法的執(zhí)行成本Fig.6 Normalized cost of each approach with λ varying from 0.005 to 0.05

圖7描述了6種算法在不同任務(wù)數(shù)下工作流調(diào)度的時間開銷情況.可以看出,隨著任務(wù)數(shù)的增加,工作流調(diào)度所消耗的時間隨著增加.ProLis、COHA、CPDE和ICPCP算法所花費的調(diào)度時間開銷較低,隨著任務(wù)數(shù)的增加,時間開銷變化并不明顯.本文提出的Pbads算法和L-ACO算法時間復(fù)雜度較高,因此隨著任務(wù)數(shù)的增加,所需要的時間開銷明顯上升,這也是后續(xù)工作需要改進的地方.

圖7 5種算法的工作流任務(wù)調(diào)度時間Fig.7 Workflow task scheduling time of five algorithms

6 結(jié) 論

本文提出了一種基于優(yōu)先級的云工作流動態(tài)調(diào)度算法Pbads,該算法在滿足任務(wù)期限的前提下,最大程度地降低執(zhí)行成本.在截止期限的松弛系數(shù)從小到大變化的情況下,Pbads在執(zhí)行成本和滿足工作流截止期限約束方面都具有更好的表現(xiàn).在未來的工作中,將研究在滿足任務(wù)期限的前提下,如何實現(xiàn)從任務(wù)到服務(wù)、服務(wù)到虛擬機的多層映射,以降低工作流任務(wù)的執(zhí)行成本以及工作流調(diào)度的時間開銷.