云環(huán)境中一種多階段式工作流任務(wù)調(diào)度算法

張 揚(yáng) 馬 飛

1(廣西工業(yè)職業(yè)技術(shù)學(xué)院 廣西 南寧 530003) 2(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院 廣西 南寧 530004)

0 引 言

通常，云計(jì)算環(huán)境中的工作流可表示為有向無(wú)循環(huán)圖DAG的形式[1]。DAG中，節(jié)點(diǎn)即為待執(zhí)行的任務(wù)，有向邊即為任務(wù)間的次序約束或任務(wù)間的通信關(guān)系。相互獨(dú)立的任務(wù)可分配至不同的虛擬機(jī)上同步執(zhí)行，而相互依賴關(guān)系的任務(wù)則可以分配至同一虛擬機(jī)上執(zhí)行以降低任務(wù)間的數(shù)據(jù)通信延時(shí)。調(diào)度問(wèn)題即將DAG中的任務(wù)分配至一個(gè)虛擬機(jī)資源集合，并考慮改善系統(tǒng)的性能[2]。調(diào)度問(wèn)題可以是靜態(tài)的，即任務(wù)執(zhí)行前發(fā)生調(diào)度；也可以是動(dòng)態(tài)的，即任務(wù)執(zhí)行過(guò)程中發(fā)生調(diào)度。多數(shù)情況下，以實(shí)現(xiàn)調(diào)度時(shí)間或代價(jià)最優(yōu)為目標(biāo)的工作流形式的任務(wù)調(diào)度問(wèn)題是NP問(wèn)題。而大多數(shù)算法也僅集中于考慮執(zhí)行時(shí)間最小化的任務(wù)調(diào)度問(wèn)題，而忽略了云計(jì)算環(huán)境中的調(diào)度代價(jià)問(wèn)題。

本文設(shè)計(jì)一種基于代價(jià)的工作流任務(wù)調(diào)度算法(簡(jiǎn)稱ICTS)。算法由層次排序、確定任務(wù)優(yōu)先級(jí)、虛擬機(jī)選擇三個(gè)階段組成。通過(guò)三階段式的任務(wù)調(diào)度過(guò)程，較好地均衡了調(diào)度長(zhǎng)度和任務(wù)執(zhí)行代價(jià)間的平衡問(wèn)題，并且通過(guò)大規(guī)模隨機(jī)化生成的任務(wù)有向圖模型的仿真比較研究，證實(shí)了算法在調(diào)度長(zhǎng)度和執(zhí)行代價(jià)同步優(yōu)化上的優(yōu)勢(shì)。

1 相關(guān)研究

為了解決工作流調(diào)度這一NP問(wèn)題，很多文獻(xiàn)提出了啟發(fā)式調(diào)度算法。文獻(xiàn)[3]提出兩種算法LOSS和GAIN分別用來(lái)優(yōu)化預(yù)算約束下的時(shí)間和代價(jià)，但僅涉及單目標(biāo)優(yōu)化。文獻(xiàn)[4]討論了IaaS云環(huán)境中的代價(jià)和截止時(shí)間約束工作流調(diào)度，但所考慮的資源僅為同質(zhì)資源模型。文獻(xiàn)[5]提出兩種云工作流調(diào)度算法：一階段算法IC-PCP和兩階段算法IC-PCPD2。兩種算法可以在多項(xiàng)式時(shí)間內(nèi)得到截止時(shí)間約束下的代價(jià)最小調(diào)度方案。文獻(xiàn)[6]提出了在混合云中截止時(shí)間約束的代價(jià)最小化調(diào)度算法HEFT，利用子截止時(shí)間的概念進(jìn)行資源的重調(diào)度，并實(shí)現(xiàn)了代價(jià)最小化。文獻(xiàn)[7]則實(shí)現(xiàn)了包任務(wù)在截止時(shí)間約束下的代價(jià)最小化調(diào)度，但僅適用于獨(dú)立任務(wù)調(diào)度。文獻(xiàn)[8]利用粒子群搜索方法求解了用戶截止時(shí)間約束下費(fèi)用最小化的工作流調(diào)度方案。文獻(xiàn)[9-11]提出了一種截止時(shí)間與預(yù)算約束時(shí)工作流調(diào)度遺傳算法，但也僅是實(shí)現(xiàn)執(zhí)行代價(jià)或執(zhí)行時(shí)間的單一優(yōu)化。文獻(xiàn)[12]提出一種工作流調(diào)度算法Hybrid，基于帕累托占優(yōu)技術(shù)將任務(wù)調(diào)度至代價(jià)最小的虛擬機(jī)上，有效降低非關(guān)鍵路徑上任務(wù)的調(diào)度代價(jià)。但算法沒(méi)有考慮關(guān)鍵路徑上任務(wù)執(zhí)行代價(jià)對(duì)于總體代價(jià)的關(guān)鍵影響，導(dǎo)致得到的最終代價(jià)并不一定是最優(yōu)的?？梢钥闯觯陨蠁l(fā)式或元啟式算法多數(shù)僅進(jìn)行了壟斷和單一目標(biāo)優(yōu)化。

鑒于此，本文設(shè)計(jì)了一種同步考慮執(zhí)行時(shí)間與代價(jià)的工作流調(diào)度算法，通過(guò)定義任務(wù)的調(diào)度優(yōu)先級(jí)以及最優(yōu)調(diào)度資源的選擇規(guī)則，實(shí)現(xiàn)工作流的均衡調(diào)度。

2 系統(tǒng)模型

表1給出與本文相關(guān)的所有符號(hào)含義說(shuō)明。

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

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

2.1 工作流模型

科學(xué)工作流的常規(guī)建模方式即為有向無(wú)環(huán)圖模型DAG，將工作流表示為G=(V,E)，V表示任務(wù)v的集合，E表示邊e的集合也代表兩個(gè)任務(wù)間的通信代價(jià)。節(jié)點(diǎn)vi∈V表示任務(wù)的計(jì)算時(shí)間，該值取決于任務(wù)所分配的虛擬機(jī)的計(jì)算能力。邊(i,j)∈E的權(quán)重表示任務(wù)vi與任務(wù)vj間的通信時(shí)間，即任務(wù)間發(fā)送數(shù)據(jù)所需要的時(shí)間。若DAG中的一個(gè)任務(wù)不存在父節(jié)點(diǎn)(前驅(qū)節(jié)點(diǎn))，則稱之為入口任務(wù)ventry，若一個(gè)任務(wù)不存在子節(jié)點(diǎn)(后繼節(jié)點(diǎn))，則稱之為出口任務(wù)vexit。若DAG中擁有多個(gè)入口或出口任務(wù)節(jié)點(diǎn)，可分配一個(gè)總的入口或出口任務(wù)節(jié)點(diǎn)，并將其所有先前入口或出口任務(wù)相連，且該總?cè)肟诨虺隹诠?jié)點(diǎn)的權(quán)重取0，邊權(quán)重也取0。DAG的任務(wù)模型表明，一個(gè)任務(wù)只有在其所有父節(jié)點(diǎn)完成后，該任務(wù)才能開(kāi)始執(zhí)行。有向無(wú)環(huán)圖模型下的工作流模型優(yōu)勢(shì)在于可以明確工作流各個(gè)子任務(wù)間的依賴關(guān)系，以及整個(gè)工作流的進(jìn)出口位置，進(jìn)而方便任務(wù)調(diào)度次序的選擇和任務(wù)完成時(shí)間的計(jì)算。

圖1為一個(gè)DAG模型示例。該DAG包括10個(gè)任務(wù)節(jié)點(diǎn)，節(jié)點(diǎn)v0為第一個(gè)執(zhí)行任務(wù)，節(jié)點(diǎn)v1-v8僅能在任務(wù)v0完成關(guān)發(fā)送結(jié)果數(shù)據(jù)后才能開(kāi)始執(zhí)行，而節(jié)點(diǎn)v2-v4直到v1完成前也無(wú)法開(kāi)始執(zhí)行，節(jié)點(diǎn)v9是最后一個(gè)任務(wù)，該任務(wù)只有在其他所有任務(wù)均執(zhí)行完成后才能開(kāi)始執(zhí)行。當(dāng)兩個(gè)任務(wù)被分配至同一虛擬機(jī)資源時(shí)，邊上的通信代價(jià)值也可以忽略不計(jì)。

圖1 DAG示例

2.2 云資源模型

假設(shè)云計(jì)算環(huán)境擁有m個(gè)異構(gòu)虛擬機(jī)資源組成的集合M，由于每個(gè)任務(wù)可在不同虛擬機(jī)上執(zhí)行，令t(vi,mj)表示任務(wù)vi在虛擬機(jī)vj上的執(zhí)行時(shí)間，并假設(shè)每個(gè)任務(wù)是DAG的一個(gè)個(gè)體而不再分割。DAG中的所有任務(wù)調(diào)度至虛擬機(jī)上執(zhí)行后，DAG的調(diào)度長(zhǎng)度makespan即為出口任務(wù)vexit的實(shí)際完成時(shí)間。令TES(vi,mj)、TEF(vi,mj)、TLF(vi,mj)分別表示任務(wù)vi在虛擬機(jī)mj上的最早開(kāi)始時(shí)間、最早完成時(shí)間、最遲完成時(shí)間。TES(vi,mj)可表示為：

TES(vi,mj)=

(1)

若前驅(qū)任務(wù)vp調(diào)度至虛擬機(jī)mj，則ctvp,vi等于0。TEF(vi,mj)可表示為：

TEF(vi,mj)=TES(vi,mj)+t(vi,mj)

(2)

TLF(vi,mj)可表示為：

(3)

DAG的調(diào)度長(zhǎng)度makespan定義為DAG的完成時(shí)間，等于出口任務(wù)vexit的實(shí)際完成時(shí)間，表示為：

MS=TAF(vexit)

(4)

云計(jì)算中，多個(gè)虛擬機(jī)均可以執(zhí)行每個(gè)任務(wù)。則任務(wù)vi在虛擬機(jī)mj上的執(zhí)行時(shí)間可表示為：

(5)

若現(xiàn)有n個(gè)虛擬同可執(zhí)行任務(wù)vi，則vi的平均執(zhí)行時(shí)間可表示為：

(6)

該資源模型利用異構(gòu)的虛擬機(jī)集群建立了執(zhí)行工作流任務(wù)的通用模型，使得不同處理能力和不同價(jià)格的虛擬機(jī)均是工作流任務(wù)的可選目標(biāo)，這樣可以在調(diào)度算法設(shè)計(jì)上僅關(guān)注于任務(wù)與資源間滿足目標(biāo)函數(shù)的匹配與映射求解問(wèn)題。

2.3 價(jià)格模型

云計(jì)算擁有不同的價(jià)格模型，如Amazon EC2按照虛擬機(jī)的數(shù)量和類型收費(fèi)，而Google App Engine則按照所請(qǐng)求的CPU周期數(shù)收費(fèi)。本文利用后一種虛擬機(jī)的代價(jià)模型，其優(yōu)勢(shì)在于在單個(gè)已付費(fèi)周期的CPU租用過(guò)程中，若付費(fèi)任務(wù)已經(jīng)在單個(gè)CPU周期內(nèi)完成，則后續(xù)繼續(xù)利用CPU的任務(wù)可以不支付費(fèi)用，從而降低工作流整體的執(zhí)行代價(jià)。價(jià)格越高，則表明虛擬機(jī)計(jì)算能力越強(qiáng)，反之亦然。令mc(vi,mj)表示任務(wù)vi在虛擬機(jī)mj上執(zhí)行的代價(jià)：

(7)

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

本文設(shè)計(jì)一種基于代價(jià)的工作流任務(wù)調(diào)度算法，目標(biāo)是將DAG中的任務(wù)調(diào)度至虛擬機(jī)上執(zhí)行，并確保得到最小化的調(diào)度長(zhǎng)度和執(zhí)行代價(jià)。算法基本流程如算法1所示。

算法1ICTS算法

輸入：DAG G(V,E)，虛擬機(jī)集合。

輸出：任務(wù)調(diào)度解，即任務(wù)與虛擬機(jī)間的映射關(guān)系。

1. partition G into levles according to tasks dependency

2. sort levels based on dependency order

3. for each level do

4. for each taskvido

5. computeRank(vi)

6. end for

7. end for

8. create new tasks list

9. sort all tasks in the new list in decreasing order of Rank(vi)

10. for each taskviin the task list do

11. for each VMmjin the VMs set do

12. compute MKCR(vi,mj)

13. end for

14. end for

15. assign taskvito the VMmjthat has the maximum value of MKCR(vi,mj)

16. end

ICTS算法由三個(gè)階段組成：層次排序階段(工作流任務(wù)分級(jí))、確定任務(wù)優(yōu)先級(jí)階段、虛擬機(jī)選擇階段。第一階段的目標(biāo)是盡可能提高任務(wù)并行執(zhí)行度，具體方式是以自頂向下的方式遍歷工作流結(jié)構(gòu)的有向無(wú)環(huán)圖，以拓?fù)渑判虻男问綄⑻幱谕粚哟蔚南嗷オ?dú)立的任務(wù)劃分為群組。分組后的任務(wù)將形成任務(wù)包的形式，在同一任務(wù)包中的任務(wù)不具備相關(guān)性，從而提高任務(wù)的并行執(zhí)行程度。第二階段中，算法根據(jù)每個(gè)任務(wù)的秩值，對(duì)每個(gè)層次中的任務(wù)進(jìn)行排序，任務(wù)vi的秩值計(jì)算方式為：

(8)

(9)

Rank(vexit)=MCP(vexit)

(10)

由此可見(jiàn)，第二階段計(jì)算任務(wù)的秩值決定了任務(wù)被調(diào)度的優(yōu)先級(jí)次序，且任務(wù)秩值需要以遞歸方式從出口任務(wù)往入口任務(wù)進(jìn)行計(jì)算。

最后，在虛擬機(jī)選擇階段，任務(wù)vi在虛擬機(jī)mj上的調(diào)度長(zhǎng)度/代價(jià)比率MKCR(vi,mj)計(jì)算為：

MKCR(vi,mj)=[(1-β)×Min_Cost(vi)/

Cost(vi,mj)]+[β×Min_TEF(vi)/TEF(vi,mj)]

(11)

式中：β表示代價(jià)因子，用于描述用戶對(duì)于調(diào)度長(zhǎng)度與執(zhí)行代價(jià)間的偏好；Cost(vi)表示任務(wù)vi在虛擬機(jī)mj上的執(zhí)行代價(jià)。

第三階段使得每個(gè)任務(wù)將被調(diào)度至擁有最大MKCR(vi,mj)值的虛擬機(jī)上，該策略可以充分利用在每個(gè)虛擬機(jī)上相鄰兩個(gè)調(diào)度任務(wù)間的空閑時(shí)間槽，不僅最小化整個(gè)DAG的完成時(shí)間，并且可以通過(guò)目標(biāo)虛擬機(jī)的選擇時(shí)參考調(diào)度長(zhǎng)度/代價(jià)比率MKCR的方式均衡任務(wù)執(zhí)行的時(shí)間和代價(jià)。

算法時(shí)間復(fù)雜度分析。ICTS算法的時(shí)間復(fù)雜度與傳統(tǒng)的HEFT算法是相似的，同為O(e×m)，其中：e表示DAG中有向邊的數(shù)量，m表示虛擬機(jī)數(shù)量。若有向邊的數(shù)量正比于v2(v為任務(wù)數(shù)量)，則算法時(shí)間復(fù)雜度可達(dá)到O(v2×m)。

圖2展示了以圖1為例的任務(wù)DAG利用混合算法Hybrid[12]和本文算法ICTS得到的調(diào)度結(jié)果。算例的場(chǎng)景中擁有3個(gè)虛擬機(jī)資源，任務(wù)在虛擬機(jī)上的執(zhí)行時(shí)間和執(zhí)行代價(jià)如表2和表3所示。圖2(a)顯示混合算法的調(diào)度長(zhǎng)度為1 000.94 s，調(diào)度代價(jià)為822＄。圖2(b)顯示ICTS算法的調(diào)度長(zhǎng)度為874.19 s，調(diào)度代價(jià)為793＄。本文提出的算法降低了約12.66%的調(diào)度長(zhǎng)度，調(diào)度代價(jià)約節(jié)省了3.52%。

圖2 調(diào)度結(jié)果對(duì)比

任務(wù)VM0VM1VM2v0191.98132.6499.31v1220.01152.01113.81v2177.37122.5591.75v3270.97187.22140.18v4204.71141.44105.90

續(xù)表2 s

表3 任務(wù)在不同虛擬機(jī)上的執(zhí)行代價(jià) ＄

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

利用WorkFlowSim平臺(tái)[13]進(jìn)行云環(huán)境中工作流調(diào)度的仿真實(shí)驗(yàn)，并利用一種特定的工作流結(jié)構(gòu)類型Montage作為云工作流的拓?fù)浣Y(jié)構(gòu)進(jìn)行測(cè)試，Montage工作流是一種應(yīng)用于天文學(xué)領(lǐng)域的科學(xué)工作流結(jié)構(gòu)，其任務(wù)組成以I/O密集型為主，對(duì)CPU處理能力要求相對(duì)較低，串行任務(wù)較少，其結(jié)構(gòu)如圖3所示。表4是實(shí)驗(yàn)中的相關(guān)參數(shù)配置情況。

圖3 Montage工作流結(jié)構(gòu)

表4 參數(shù)配置

4.1 性能指標(biāo)

1) 調(diào)度長(zhǎng)度比率和代價(jià)比率。系統(tǒng)調(diào)度效率可以通過(guò)標(biāo)準(zhǔn)化的調(diào)度長(zhǎng)度和代價(jià)進(jìn)行衡量，即調(diào)度長(zhǎng)度比率SLR和代價(jià)比率MCR，分別定義為：

(12)

(13)

式(12)的分母部分表示處于關(guān)鍵路徑CP上的任務(wù)的最小執(zhí)行時(shí)間之和，式(13)的分母部分表示處于關(guān)鍵路徑CP上的任務(wù)的最小執(zhí)行代價(jià)之和。

2) 代價(jià)因子β。為了度量SLR和MCR，需要使用不同的代價(jià)因子β取值。圖4為針對(duì)不同的代價(jià)因子取值在不同的DAG規(guī)模下得到SLR和MCR取值情況。圖中，x軸代表代價(jià)因子，y軸同時(shí)代表SLR和MCR，即標(biāo)準(zhǔn)化的調(diào)度長(zhǎng)度和代價(jià)。DAG中的任務(wù)數(shù)量隨機(jī)生成于80～400個(gè)任務(wù)之間。圖4表明，代價(jià)因子與MCR成正比，而與SLR成反比。對(duì)于較小的代價(jià)因子β，如β=0.1、0.2、0.3，MCR和SLR的變化比例略小于β>0.3的變化?？傮w來(lái)看，在β<0.4的情況下，算法在兩個(gè)指標(biāo)上能夠擁有較好的性能表現(xiàn)。而β>0.4后，SLR的變化比例較慢，而MCR變化較快。因此，在后續(xù)仿真測(cè)試中代價(jià)因子β可取值為0.1、0.2和0.3。

圖4 不同規(guī)模不同代價(jià)因子對(duì)性能的影響

4.2 結(jié)果分析

本節(jié)對(duì)ICTS算法和對(duì)比算法Hybrid進(jìn)行實(shí)驗(yàn)對(duì)比分析，利用前文引入的標(biāo)準(zhǔn)化調(diào)度長(zhǎng)度比率和標(biāo)準(zhǔn)化代價(jià)比率作為性能指標(biāo)。在相同的虛擬機(jī)資源配置下，利用不同的DAG規(guī)模(不同的任務(wù)數(shù)量)進(jìn)行實(shí)驗(yàn)仿真。圖4為在不同的任務(wù)數(shù)量和CCR取值情況下兩個(gè)指標(biāo)的性能比較情況，其中，柱狀圖的取值對(duì)應(yīng)于左側(cè)縱坐標(biāo)值，折線圖的取值對(duì)應(yīng)于右側(cè)坐標(biāo)值。算法的SLR指標(biāo)均會(huì)隨著任務(wù)數(shù)量和CCR取值的增加而增加，而ICTS算法在不同DAG規(guī)模下也可以得到更優(yōu)的SLR性能。表5給出本文算法ICTS對(duì)比Hybrid算法在任務(wù)調(diào)度長(zhǎng)度和代價(jià)上得到的增益比例(即在調(diào)度長(zhǎng)度和代價(jià)上的節(jié)省程度)，在確定的任務(wù)規(guī)模下，ICTS算法在選擇目標(biāo)虛擬機(jī)時(shí)有效參考了調(diào)度效率與代價(jià)的均衡，使得兩個(gè)指標(biāo)均得到改善。

表5 ICTS算法比較對(duì)比算法Hybrid得到的增益

圖5和圖6顯示了在不同的DAG任務(wù)規(guī)模下算法得到的SLR和MCR指標(biāo)性能情況?？梢钥吹?，ICTS算法在兩項(xiàng)指標(biāo)上是優(yōu)于Hybrid算法的，這是因?yàn)镮CTS算法考慮了任務(wù)父節(jié)點(diǎn)與自身的通信時(shí)間以及任務(wù)子節(jié)點(diǎn)與自身的通信時(shí)間(如式(8)所示)。因此，在DAG中最復(fù)雜任務(wù)將處于分級(jí)隊(duì)列的隊(duì)首而被優(yōu)先進(jìn)行調(diào)度。而Hybrid算法在計(jì)算每個(gè)任務(wù)的分級(jí)時(shí)僅僅考慮了任務(wù)與其后繼之間的通信時(shí)間。

圖5 不同任務(wù)組成(CCR度量)及不同任務(wù)數(shù)量對(duì)SLR的影響

圖6 不同任務(wù)組成(CCR度量)及不同任務(wù)數(shù)量對(duì)MCR的影響

利用式(11)選擇任務(wù)調(diào)度的虛擬機(jī)，ICTS算法同時(shí)考慮了Min_Cost(vi)和Min_TEF(vi)。此外，還可以看到，改變工作流中任務(wù)的通信/計(jì)算比率(改變計(jì)算密集型和通信密集型任務(wù)的比例)的情況下，ICTS算法在SLR指標(biāo)上依然具有較好的適應(yīng)性，仿真結(jié)果并沒(méi)有出現(xiàn)反轉(zhuǎn)式的結(jié)果，而僅僅是指標(biāo)值出現(xiàn)比較緩和的增加。

對(duì)于算法而言，MCR指標(biāo)會(huì)隨著任務(wù)數(shù)量和CCR取值的增加而增加。圖6結(jié)果表明ICTS算法在不同的任務(wù)規(guī)模下提供了比Hybrid算法更好的MCR性能。另一方面，Hybrid算法過(guò)多依賴于時(shí)間與代價(jià)的比例，這些比例在選取調(diào)度任務(wù)時(shí)僅考慮了執(zhí)行代價(jià)與執(zhí)行時(shí)間的最小值和最大值，而本文算法對(duì)相關(guān)參數(shù)的依賴性則遠(yuǎn)弱于Hybrid算法，使其在不同規(guī)模和不同任務(wù)組成的情況下依然可能得到比較穩(wěn)定的性能表現(xiàn)。

5 結(jié) 語(yǔ)

為了實(shí)現(xiàn)云計(jì)算環(huán)境中的工作流任務(wù)調(diào)度，本文以最小化調(diào)度長(zhǎng)度和執(zhí)行代價(jià)為目標(biāo)，提出一種基于代價(jià)的工作流調(diào)度算法。通過(guò)任務(wù)分級(jí)排序、確定任務(wù)優(yōu)先級(jí)以及虛擬機(jī)資源選擇三個(gè)階段的優(yōu)化，實(shí)現(xiàn)了不同規(guī)模任務(wù)下對(duì)工作流調(diào)度長(zhǎng)度和執(zhí)行代價(jià)的同步優(yōu)化。仿真實(shí)驗(yàn)結(jié)果表明，對(duì)于選取的SLR和MCR兩個(gè)性能指標(biāo)，本文算法均表現(xiàn)出比對(duì)比算法更好的性能。下一步可選擇將云資源提供方的能耗問(wèn)題考慮到優(yōu)化目標(biāo)中，即在執(zhí)行效率與執(zhí)行能效之間取得更好的平衡，以此為目標(biāo)設(shè)計(jì)工作流調(diào)度算法。