張艮山 劉旭寧

(石家莊學(xué)院信息技術(shù)系 河北 石家莊 050035)

0 引 言

根據(jù)需求的不同，云計(jì)算可以動(dòng)態(tài)地將資源提供至用戶(hù)任務(wù)，實(shí)例租用方式是即付即用的，這與傳統(tǒng)計(jì)算模式不同，其更為靈活的特征給云計(jì)算作為處理科學(xué)工作流任務(wù)以及實(shí)施工作流調(diào)度帶來(lái)了極大的便利。大規(guī)模科學(xué)工作流應(yīng)用的常規(guī)建模形式是圖論中的有向無(wú)環(huán)圖DAG，圖中頂點(diǎn)代表工作流中大量相互依賴(lài)或相互獨(dú)立的任務(wù)集。這些任務(wù)間或存在著直接關(guān)聯(lián)(執(zhí)行先后有嚴(yán)格次序)，或無(wú)直接關(guān)聯(lián)可并行執(zhí)行。為了滿(mǎn)足云工作流的服務(wù)質(zhì)量，工作流調(diào)度需要在既定約束條件下搜索有效調(diào)度方案，將工作流結(jié)構(gòu)中的各個(gè)任務(wù)映射和調(diào)度至云資源實(shí)例上，并優(yōu)化目標(biāo)函數(shù)。

云計(jì)算按需提供和即付即用的資源使用方式使得目前的任務(wù)調(diào)度算法具有以下不足：1) 實(shí)例租用價(jià)格沒(méi)有利用更切合實(shí)際的商業(yè)云賬單模型；2) 實(shí)例利用時(shí)間相對(duì)固定；3) 在考慮多種約束條件的工作流調(diào)度問(wèn)題時(shí)，所使用的啟發(fā)式算法或搜索算法時(shí)間復(fù)雜度較高，實(shí)施成本太大。針對(duì)1)，本文在設(shè)計(jì)工作流調(diào)度算法中應(yīng)用Amazon EC2的實(shí)例賬單價(jià)格模型，同時(shí)在已經(jīng)支付的賬單周期中，前一任務(wù)的空閑賬單時(shí)間仍可被其他調(diào)度任務(wù)所利用，以此節(jié)省任務(wù)執(zhí)行代價(jià)。針對(duì)2)，本文所考慮的場(chǎng)景中一旦實(shí)例空閑即可釋放，資源獲取更加靈活，資源利用也更加充分。針對(duì)3)，本文不僅同步考慮預(yù)算和期限的雙重約束，還同步優(yōu)化執(zhí)行效率和代價(jià)，設(shè)計(jì)了更加高效復(fù)雜度更低的調(diào)度算法。

1 相關(guān)工作

多目標(biāo)工作流調(diào)度可劃分為兩種情形：?jiǎn)喂ぷ髁髡{(diào)度、多工作流調(diào)度。單工作流調(diào)度不適合云計(jì)算環(huán)境，與云計(jì)算的使用特征不符。單工作流調(diào)度目前主要體現(xiàn)在以下幾種類(lèi)型：1) 在期限約束下優(yōu)化執(zhí)行代價(jià)。文獻(xiàn)[1]基于任務(wù)副本方法設(shè)計(jì)了期限約束下的工作流調(diào)度代價(jià)最優(yōu)化算法。文獻(xiàn)[2]設(shè)計(jì)了期限約束的動(dòng)態(tài)代價(jià)啟發(fā)式調(diào)度算法，在公有云環(huán)境中進(jìn)行了單個(gè)工作流的調(diào)度優(yōu)化。文獻(xiàn)[3-4]分別采用無(wú)啟發(fā)式和搜索式方法進(jìn)行了工作流調(diào)度優(yōu)化。2) 在預(yù)算約束下優(yōu)化執(zhí)行時(shí)間。文獻(xiàn)[5-7]均設(shè)計(jì)了滿(mǎn)足預(yù)算約束的啟發(fā)式算法最小化執(zhí)行時(shí)間。文獻(xiàn)[8]設(shè)計(jì)的SABA算法是一種考慮安全與預(yù)算感知的工作流調(diào)度算法，在實(shí)現(xiàn)安全調(diào)度的同時(shí)提高了調(diào)度效率。以上兩種研究類(lèi)型均屬于單約束單目標(biāo)，此時(shí)調(diào)度方案的求解模型相對(duì)比較簡(jiǎn)單，但其缺陷在于僅在單方面從效率或代價(jià)方面進(jìn)行任務(wù)調(diào)度優(yōu)化，而云環(huán)境下的調(diào)度問(wèn)題中這兩個(gè)因素是并存的，必須同步考慮。3) 同步實(shí)現(xiàn)執(zhí)行時(shí)間和執(zhí)行代價(jià)最優(yōu)。部分研究試圖在工作流調(diào)度中實(shí)現(xiàn)時(shí)間和代價(jià)的平衡。文獻(xiàn)[9]根據(jù)Critical-Path-First機(jī)制，通過(guò)工作流的擴(kuò)展與壓縮來(lái)實(shí)現(xiàn)目標(biāo)優(yōu)化。文獻(xiàn)[10]則利用帕累托的概念實(shí)現(xiàn)兩個(gè)指標(biāo)優(yōu)化。同樣地，文獻(xiàn)[11]通過(guò)設(shè)計(jì)一種反映偏好的有效因子，實(shí)現(xiàn)了工作流執(zhí)行效率和代價(jià)優(yōu)化。但是以上工作多數(shù)為多約束下的單目標(biāo)指標(biāo)優(yōu)化或不做約束下同時(shí)優(yōu)化兩個(gè)指標(biāo)。4) 預(yù)算與期限多約束。文獻(xiàn)[12]利用搜索機(jī)制對(duì)任務(wù)重分配，實(shí)現(xiàn)了一種雙約束調(diào)度算法。文獻(xiàn)[13]以自適應(yīng)混合啟發(fā)式算法對(duì)混合云環(huán)境中的工作流調(diào)度問(wèn)題進(jìn)行求解。文獻(xiàn)[14]提出了宏觀(guān)多工作流調(diào)度和微觀(guān)單工作流調(diào)度算法。文獻(xiàn)[15]提出多個(gè)工作流結(jié)構(gòu)下?lián)碛薪刂箷r(shí)間約束的吞吐量?jī)?yōu)化調(diào)度算法，可以一定程度保證工作流的完成比例。文獻(xiàn)[16]則在資源分配過(guò)程中同樣采用了任務(wù)優(yōu)先級(jí)機(jī)制進(jìn)行多工作流調(diào)度。以上研究方法的問(wèn)題在于：(1) 考慮代價(jià)優(yōu)化時(shí)的資源定價(jià)多是固定定價(jià)，而非目前商業(yè)云所通用的云帳單模型，因此在進(jìn)行目標(biāo)優(yōu)化時(shí)得到的任務(wù)調(diào)度方案不一定能夠真正優(yōu)化調(diào)度代價(jià)；(2) 調(diào)度策略中所用的資源相對(duì)固定，無(wú)法反映云資源特有的彈性提供環(huán)境。

2 系統(tǒng)模型

工作流廣泛應(yīng)用于復(fù)雜分布式科學(xué)計(jì)算建模問(wèn)題，有向無(wú)環(huán)圖DAG是工作流的最常用抽象工具。利用DAG抽象，一個(gè)工作流可定義為G=(T,E)，T={t0,t1,…,tn}為頂點(diǎn)任務(wù)集，E={ei,j|ti,tj∈T}為邊集，即任務(wù)依賴(lài)。邊ei,j∈E(ti,tj∈T)代表兩個(gè)任務(wù)ti和tj之間的有向邊的偏序約束，此時(shí)，任務(wù)ti為tj的父親，任務(wù)tj為ti的子代任務(wù)。

本文考慮的場(chǎng)景為IaaS云服務(wù)模型，IaaS通過(guò)提供包括不同CPU、內(nèi)存、存儲(chǔ)、網(wǎng)絡(luò)帶寬的實(shí)際類(lèi)型來(lái)提供云服務(wù)，服務(wù)按照不同定價(jià)使用。本文在算法設(shè)計(jì)中考慮了Amazon EC2的云資源實(shí)例，以最小賬單時(shí)間租用，若實(shí)際使用時(shí)間小于賬單時(shí)間，仍按賬單時(shí)間付費(fèi)。令實(shí)例集合為P={p0,p1,…,pn}。

pred(ti)={tj|(tj,ti)∈E}

(1)

任務(wù)ti的所有直接子任務(wù)可表示為：

succ(ti)={tj|(ti,tj)∈E}

(2)

如圖1所示的工作流結(jié)構(gòu)中，任務(wù)t8的父親任務(wù)為t5、t6和t7，任務(wù)t1的子任務(wù)為t2、t3和t4。若一個(gè)任務(wù)沒(méi)有父親任務(wù)則為工作流的入口任務(wù)，若一個(gè)任務(wù)沒(méi)有子任務(wù)則為工作流的出口任務(wù)。圖中，任務(wù)t1為工作流的入口任務(wù)，任務(wù)t9為工作流的出口任務(wù)。換言之：

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

pred(tentry)=?

(3)

succ(texit)=?

(4)

工作流的完成時(shí)間稱(chēng)為調(diào)度長(zhǎng)度或makespan，表示為L(zhǎng)ms。由于出口texit是整個(gè)工作流執(zhí)行的最后一個(gè)任務(wù)，可以認(rèn)為該任務(wù)的最終完成時(shí)間即為工作流的調(diào)度長(zhǎng)度。因此，其可以表述如下：

Lms=FT(texit)

(5)

式中：FT(texit)為工作流最后一個(gè)任務(wù)texit的完成時(shí)間。

工作流結(jié)構(gòu)是目前科學(xué)計(jì)算領(lǐng)域中最常用的任務(wù)結(jié)構(gòu)形式，它定義了任務(wù)的觸發(fā)順序和觸發(fā)條件，直接關(guān)聯(lián)的任務(wù)間必須按照先后次序進(jìn)行部署，無(wú)直接關(guān)聯(lián)的任務(wù)則可以并行執(zhí)行。而作為最常用的工作流結(jié)構(gòu)表示模型，本文采用的有向無(wú)環(huán)圖DAG結(jié)構(gòu)則較為明確的定義的了工作流的結(jié)構(gòu)特征，其開(kāi)始任務(wù)和結(jié)束任務(wù)均可以在DAG中明確表示。在設(shè)計(jì)工作流任務(wù)調(diào)度算法過(guò)程中，有向無(wú)環(huán)圖DAG的存儲(chǔ)方式和編程表達(dá)也比較有利于進(jìn)行實(shí)驗(yàn)環(huán)境的搭建和性能測(cè)試。

令Ci,j表示任務(wù)ti和tj之間數(shù)據(jù)傳輸?shù)臅r(shí)間：

(6)

如果兩個(gè)任務(wù)ti和tj調(diào)度到相同的實(shí)例上(即pi=pj)，則任務(wù)間的數(shù)據(jù)傳輸發(fā)生在本地機(jī)器上，通信代價(jià)基本為0。否則，通信時(shí)間為數(shù)據(jù)傳輸量data與數(shù)據(jù)中心平均帶寬β間的比值。

ti的最早開(kāi)始時(shí)間EST計(jì)算為：

(7)

式中：wtj表示任務(wù)tj在最快實(shí)例上的執(zhí)行時(shí)間。任務(wù)ti在實(shí)例pj上的執(zhí)行代價(jià)為：

(8)

式中：cj表示在單個(gè)時(shí)間周期里任務(wù)執(zhí)行時(shí)租用實(shí)例pj的代價(jià)；Nt表示租用實(shí)例的時(shí)間周期數(shù)量。工作流中所有任務(wù)的執(zhí)行總代價(jià)可表示為：

(9)

該代價(jià)模型應(yīng)用了Amazon EC2的實(shí)例賬單價(jià)格模型，同時(shí)在已經(jīng)支付的賬單周期中，前一任務(wù)的空閑賬單時(shí)間仍可被其他調(diào)度任務(wù)所利用(取式(8)中上限整數(shù)部分)，以此節(jié)省任務(wù)的總體執(zhí)行代價(jià)。

3 預(yù)算/期限感知調(diào)度算法

為了同時(shí)滿(mǎn)足預(yù)算和期限約束，并在調(diào)度長(zhǎng)度和調(diào)度代價(jià)上取得同步優(yōu)化的效果，BDAS算法將劃分為五個(gè)階段實(shí)行。1) 工作流結(jié)構(gòu)分層：將工作流劃分為若干不具有相關(guān)性的包任務(wù)，稱(chēng)之為層次level；2) 預(yù)算分配：利用某種策略將總體預(yù)算B分配至每個(gè)level中；3) 期限分配：將總體截止時(shí)間D分割并在不同level間進(jìn)行分配，每個(gè)level得到層次期限；4) 任務(wù)選擇：根據(jù)就緒隊(duì)列中待執(zhí)行任務(wù)的優(yōu)先級(jí)，選擇調(diào)度任務(wù)；5) 實(shí)例選擇：以時(shí)間和代價(jià)的均衡性作為參考，選擇最優(yōu)實(shí)例。

3.1 工作流分層

由于工作流結(jié)構(gòu)中的任務(wù)或者具有直接相關(guān)性，或者不具備直接關(guān)聯(lián)。那么，工作流分層的目的就是通過(guò)分離或?qū)θ蝿?wù)進(jìn)行劃分，使得在同一個(gè)層次中的任務(wù)不具有相關(guān)性，以此盡可能最大化任務(wù)執(zhí)行的可并行程度，以此節(jié)省任務(wù)調(diào)度的時(shí)間，而具有直接關(guān)聯(lián)的任務(wù)則必須依據(jù)先后關(guān)系執(zhí)行。這樣，每個(gè)層次即可考慮為一個(gè)包括若干不相關(guān)任務(wù)的包任務(wù)。本文利用一種期限底部分層的方法將任務(wù)劃分至不同的層次中。將任務(wù)ti的層次描述為從ti至texit間路徑邊的最大值。那么，任務(wù)texit的層次將總為1。而其他任務(wù)則有：

(10)

所有任務(wù)根據(jù)其分層可劃分至任務(wù)分層集合TLS中，則：

TLS(l)={ti|L(ti)=l}

(11)

式中：l表示層次，l∈{1,2,…,L(tentry)}。

3.2 預(yù)算分配

預(yù)算分配的思想是將全局預(yù)算B在不同層次中進(jìn)行分配，在考慮分配至一個(gè)層次的可用子預(yù)算subB(l)的情況下將任務(wù)調(diào)度至實(shí)例上，其優(yōu)勢(shì)是可以將除去已經(jīng)使用后的全部預(yù)算按層次全部預(yù)留至下層任務(wù)。先將預(yù)算B全部分配給tentry，tentry調(diào)度完成后將剩余預(yù)算分配至下一層任務(wù)。將分配至一個(gè)層次上的子預(yù)算稱(chēng)為層次預(yù)算，預(yù)算分配策略是將預(yù)算分配至最早的層次上，然后將未使用的剩余預(yù)算繼續(xù)分配至下一層次上，表示如下：

(12)

式中：TaskCostti由式(8)定義。將剩余預(yù)算定義為調(diào)度層次l中的所有任務(wù)后的剩余費(fèi)用值。

3.3 期限分配

期限分配階段的目標(biāo)是將初始定義的整體截止時(shí)間在劃分后的工作流不同層次上進(jìn)行分配，即將整體的截止時(shí)間約束分割成不同層次間的子截止時(shí)間的約束。換言之，若在所分配的子期限內(nèi)層次中的所有任務(wù)可以保證完成，則整體截止時(shí)間同樣可以得到滿(mǎn)足。策略需要考慮每個(gè)層次的執(zhí)行時(shí)間以及層次中任務(wù)的數(shù)量，從而得到更低的代價(jià)。一旦任務(wù)被劃分入各自層次后，每個(gè)層次中的任務(wù)即可按比例從整體期限D(zhuǎn)中分配相應(yīng)子期限。令subD(l)表示層次期限，即分配至每個(gè)層次l的子期限。為了滿(mǎn)足整體期限，需要確保每個(gè)層次中的每個(gè)任務(wù)在其分配的子期限內(nèi)完成。每個(gè)層次l的初始估計(jì)期限計(jì)算為：

(13)

式中：ECT(ti)表示在所有資源間ti的最早完成時(shí)間，定義為：

(14)

式中：pred(ti)為ti的父任務(wù)集;wti為ti的最小執(zhí)行時(shí)間;l為父任務(wù)ti的層次。tentry沒(méi)有父親任務(wù)，故其ECT=0。

計(jì)算層次期限值后，需要根據(jù)截止時(shí)間的比例和每個(gè)層次中任務(wù)的數(shù)量將期限在所有任務(wù)間進(jìn)行非均勻分配。引入一個(gè)比例單元∝deadline定義為：

(15)

式中：|subD(l)|表示層次l的期限長(zhǎng)度；|TSL(l)|表示每個(gè)層次中的任務(wù)數(shù)量。

定義期限因子DF為：

(16)

式中：subD(1)表示包括出口任務(wù)的層次。式(16)的分子部分表示剩余的期限，即總體截止時(shí)間與出口任務(wù)所在層次子期限之差值。

將每個(gè)層次的期限的長(zhǎng)度更新為期限因子DF的函數(shù)：

subD(l)=DF×|subD(l)|×|TSL(l)|+subD(l)

(17)

可見(jiàn)，擁有越長(zhǎng)任務(wù)執(zhí)行時(shí)間和越多任務(wù)數(shù)量的層次，將獲得更多的截止時(shí)間分配。

3.4 任務(wù)選擇

由于處于相同層次中的任務(wù)間不具有相關(guān)性，所有這部分任務(wù)可以并行同步執(zhí)行。算法執(zhí)行過(guò)程中，待執(zhí)行的就緒任務(wù)將被置入就緒隊(duì)列中，而從就緒隊(duì)列中選擇執(zhí)行任務(wù)的依據(jù)是最早開(kāi)始時(shí)間EST?；谌蝿?wù)的最早開(kāi)始時(shí)間對(duì)任務(wù)進(jìn)行調(diào)度次序選擇，可以確保盡可能短的工作流任務(wù)完成時(shí)間，從而提高任務(wù)調(diào)度效率。BDAS算法中，任務(wù)將按層次執(zhí)行，這表明只有在前一層次中的所有任務(wù)得到調(diào)度后，其下層次中的任務(wù)才可以開(kāi)始執(zhí)行。

對(duì)于某個(gè)任務(wù)是否為就緒任務(wù)的判斷依據(jù)為是否其所有父親任務(wù)已完成并已接收所有數(shù)據(jù)，若滿(mǎn)足該條件，該任務(wù)即可進(jìn)入就緒隊(duì)列。同一層中的任務(wù)由于任務(wù)間均沒(méi)有依賴(lài)性，故可以同步并行執(zhí)行。而選擇任務(wù)的依據(jù)是根據(jù)就緒隊(duì)列中的任務(wù)的優(yōu)先級(jí)來(lái)決定，此時(shí)優(yōu)先級(jí)的定義依據(jù)為最早開(kāi)始時(shí)間EST。ti的最早開(kāi)始時(shí)間EST計(jì)算為：

因此，調(diào)度算法需要首先計(jì)算每個(gè)任務(wù)在實(shí)例上的EST，而最先開(kāi)始執(zhí)行的任務(wù)也擁有最高的選擇優(yōu)先級(jí)，該任務(wù)也將被選為執(zhí)行的候選任務(wù)(該任務(wù)擁有最高的優(yōu)先級(jí))。

3.5 實(shí)例選擇

處于以下?tīng)顩r時(shí)需要進(jìn)行實(shí)例選擇：1) 每個(gè)任務(wù)已被分配至一個(gè)層次中；2) 每個(gè)層次的預(yù)算和期限已被分配；3) 每個(gè)就緒任務(wù)的優(yōu)先級(jí)已被分配。實(shí)例選擇過(guò)程中，需要均衡任務(wù)的執(zhí)行時(shí)間和執(zhí)行代價(jià)。本文算法在進(jìn)行實(shí)例選擇時(shí)將兼顧考慮到任務(wù)的執(zhí)行時(shí)間和執(zhí)行代價(jià)，通過(guò)設(shè)計(jì)的均衡函數(shù)選擇最佳的任務(wù)執(zhí)行實(shí)例，確保在截止時(shí)間和預(yù)算兩個(gè)不同的約束狀況下都能夠完成對(duì)任務(wù)的有效調(diào)度。

對(duì)于當(dāng)前任務(wù)ti，其在實(shí)例pj上的最早執(zhí)行時(shí)間表示為ECT(ti|pj)，該時(shí)間是任務(wù)在實(shí)例上完成的最早時(shí)間，由式(14)定義?；诖?，可以計(jì)算當(dāng)前任務(wù)的估計(jì)層次期限與任務(wù)在實(shí)例pj上的最早完成時(shí)間的差異：

(18)

式中：subDlti表示分配給包括任務(wù)ti所在層次的子期限；ECTmin表示在所有實(shí)例中得到的任務(wù)最小執(zhí)行時(shí)間。

(19)

式中：subBlti表示分配給包括任務(wù)ti所在層次的子預(yù)算；TaskCostmin表示ti在所有實(shí)例上執(zhí)行的最小代價(jià)(最優(yōu)代價(jià))。

為了尋找最優(yōu)實(shí)例，算法利用Cost/Time均衡因子CTTF實(shí)現(xiàn)執(zhí)行代價(jià)與執(zhí)行時(shí)間的均衡。CTTF值可以調(diào)整當(dāng)前任務(wù)在所有實(shí)例上的Time值和Cost值。為了代價(jià)最小化，目前已有的算法會(huì)將任務(wù)調(diào)度至最便宜可用的實(shí)例上(最慢實(shí)例)，從而滿(mǎn)足其分配的子期限。然而，在這種策略下，任務(wù)執(zhí)行將花費(fèi)更多時(shí)間，進(jìn)而導(dǎo)致其子任務(wù)的EST出現(xiàn)延時(shí)。為了避免這種情況，在滿(mǎn)足期限的同時(shí)較貴的實(shí)例是更好的選擇，但又可能導(dǎo)致超過(guò)預(yù)算。因此，CTTF的作用即是在時(shí)間和代價(jià)間取得均衡。

利用式(18)和式(19)計(jì)算任務(wù)的Time和Cost值時(shí)，會(huì)出現(xiàn)以下四種不同的情況：

1)Cost>0，Time>0。此情況為最優(yōu)情形，其表明可以得到充足的預(yù)算進(jìn)行工作流調(diào)度，同時(shí)，截止時(shí)間也相對(duì)寬松。當(dāng)分配預(yù)算和期限時(shí)，每個(gè)層次可以得到相對(duì)大的份額。因此，任務(wù)所在層次的子預(yù)算和子期限均較為充足，故Cost和Time值均為正值。

2)Cost≤0，Time>0。層次l分配的預(yù)算已被支付(subBlti=0)，因此，無(wú)法啟動(dòng)新的實(shí)例，由于此時(shí)已無(wú)預(yù)算。另外一個(gè)可能的情形是當(dāng)前任務(wù)ti在實(shí)例pj上的代價(jià)高于剩余子預(yù)算(式(19)的分子)。若滿(mǎn)足以上兩種情況之一，則式(19)的值小于或等于0。

3)Cost>0，Time≤0。此時(shí)為較緊密的期限情形(實(shí)例計(jì)算能力較低，無(wú)法滿(mǎn)足任務(wù)層次分割的子期限)，導(dǎo)致式(18)中的ECT值大于或等于任務(wù)層次的子期限。若滿(mǎn)足此情況，式(18)的值變?yōu)樨?fù)值或0。

4)Cost≤0，Time≤0。此時(shí)為較緊密的期限和預(yù)算，即當(dāng)前的子預(yù)算和子期限分別小于TaskCost和ECT。對(duì)于任務(wù)ti，式(19)和式(18)均小于或等于0。均衡函數(shù)定義為：

(20)

具有最大CTTF值的實(shí)例將被選擇為執(zhí)行任務(wù)ti的實(shí)例。

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

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

利用科學(xué)工作流調(diào)度仿真平臺(tái)WorkFloSim[13]進(jìn)行仿真，所構(gòu)成的數(shù)據(jù)中心包括六種實(shí)例類(lèi)型，實(shí)例類(lèi)型的相關(guān)參數(shù)如表1所示。將不同實(shí)例類(lèi)型間任務(wù)進(jìn)行數(shù)據(jù)傳輸?shù)膸捲O(shè)為20 MB/s，實(shí)例的處理能力以MFLOPS計(jì)算度量，即資源每秒鐘可進(jìn)行的百萬(wàn)浮點(diǎn)操作數(shù)。此外，在實(shí)例租用價(jià)格方面，本文參考Amazon EC2的云資源實(shí)例定價(jià)機(jī)制，其定價(jià)利用以小時(shí)為單位的賬單機(jī)制。

表1 實(shí)例類(lèi)型以及能力參數(shù)

選擇四種具有代表性且性能較被認(rèn)可的云環(huán)境中的工作流調(diào)度算法與本文的BDAS算法進(jìn)行性能比較，包括Hybrid算法[11]、MTCT算法[18]、CWFT算法[19]、SABA算法[8]。為了測(cè)試算法在處理不同類(lèi)型的工作流結(jié)構(gòu)上的優(yōu)勢(shì)以體現(xiàn)算法的適應(yīng)性，選擇不同科學(xué)領(lǐng)域中的工作流結(jié)構(gòu)進(jìn)行測(cè)試[20]，包括CyberShake工作流、EPIGENOMIC工作流、LIGO工作流、Montage工作流。其中：CyberShake和LIGO兩種工作流的特點(diǎn)是存儲(chǔ)需求較大，前者是地震科學(xué)中仿真工作流應(yīng)用類(lèi)型，后者為物理學(xué)中引力波的工作流應(yīng)用類(lèi)型；Epigenomic工作流屬于計(jì)算密集型，是生物信息學(xué)中的工作流應(yīng)用類(lèi)型；Montage工作流屬于輸入/輸出密集型，是天文學(xué)中的工作流應(yīng)用類(lèi)型。此外，CyberShake工作流也是數(shù)據(jù)密集型。為了表現(xiàn)不同規(guī)模的工作流，仿真過(guò)程中分別配置200、400和800個(gè)工作流任務(wù)進(jìn)行測(cè)試。

為了測(cè)試算法對(duì)工作流執(zhí)行預(yù)算和期限的滿(mǎn)足程度，以一種靈活方式生成工作流的整體預(yù)算和期限值。具體方式如下：

D=minD+αD×(maxD-minD)

(21)

B=minB+αB×(maxB-minB)

(22)

式中：minD為所有任務(wù)均調(diào)度至處理能力最差(代價(jià)相應(yīng)最小)的實(shí)例上執(zhí)行算法得到的調(diào)度長(zhǎng)度；maxB為此時(shí)算法得到的對(duì)應(yīng)調(diào)度代價(jià)；maxD為所有任務(wù)均調(diào)度至處理能力最強(qiáng)(代價(jià)相應(yīng)最大)的實(shí)例上執(zhí)行算法得到的調(diào)度長(zhǎng)度；minB為此時(shí)算法得到的對(duì)應(yīng)調(diào)度代價(jià)；αD和αB分別表示處于0至1之間的期限因子和預(yù)算因子。通過(guò)式(21)和式(22)中設(shè)置期限和預(yù)算約束，可以確保算法尋求調(diào)度解時(shí)滿(mǎn)足此時(shí)給出的約束條件。實(shí)驗(yàn)中分別設(shè)置αD、αB的取值為{0.1,0.3,0.5}進(jìn)行測(cè)試，以此觀(guān)察算法在不同的期限和預(yù)算緊密程度下算法的適應(yīng)性。而在理論上，兩個(gè)因子取值增加，成功調(diào)度工作流概率應(yīng)用是有所提高的。

4.2 性能指標(biāo)

為了測(cè)試算法的性能，以下指標(biāo)被選取進(jìn)行性能比較，包括：調(diào)度成功率、時(shí)間比率和代價(jià)比率。

調(diào)度成功率SR：該指標(biāo)表示滿(mǎn)足預(yù)算和期限兩個(gè)約束條件時(shí)成功執(zhí)行的實(shí)驗(yàn)次數(shù)與總仿真次數(shù)(nTot)的比值：

(23)

時(shí)間比率TR：該指標(biāo)表示整體期限D(zhuǎn)與工作流調(diào)度的實(shí)際時(shí)間的比值：

(24)

代價(jià)比率CR：該指標(biāo)表示整體預(yù)算B與工作流調(diào)度的實(shí)際代價(jià)間的比值：

(25)

顯然，TR和CR的取值若小于1，則說(shuō)明算法得到的工作流調(diào)度沒(méi)有滿(mǎn)足期限和預(yù)算的約束條件。

4.3 實(shí)驗(yàn)分析

圖2-圖5展示了五種算法得到的調(diào)度結(jié)果中的平均調(diào)度成功率SR?？梢悦黠@地看出，本文算法相較其他四種對(duì)比算法在所有四種類(lèi)型的工作流結(jié)構(gòu)中均得到了更高的調(diào)度成功率。換言之，BDAS算法得到的同時(shí)滿(mǎn)足預(yù)算和期限的調(diào)度結(jié)果次數(shù)是最多的。由于四種工作流的任務(wù)類(lèi)型和結(jié)構(gòu)特征也有所差異，所有算法得到的平均調(diào)度成功率也不同。BDAS算法通過(guò)分層后的任務(wù)以及預(yù)算和期限的子分割機(jī)制，可以有效解決雙約束時(shí)的工作流調(diào)度問(wèn)題，同時(shí)同步降低工作流的執(zhí)行時(shí)間和執(zhí)行代價(jià)。此外，還可以看到，若增加預(yù)算因子αB，工作流的各層次將擁有更多的可用預(yù)算，從而使得BDAS算法的平均調(diào)度成功率SR會(huì)進(jìn)一步得到增加。對(duì)于αD=0.1所表達(dá)的較為緊密的截止時(shí)間，在四種工作流的多數(shù)實(shí)驗(yàn)情形中，僅本文算法實(shí)現(xiàn)成功調(diào)度的可能性最大。

圖2 CyberShake工作流

圖3 Epigenomic工作流

圖4 LIGO工作流

圖5 Montage工作流

圖6是改變預(yù)算因子得到的時(shí)間比率TR指標(biāo)情況，圖7是改變期限因子得到的代價(jià)比率CR指標(biāo)情況。如指標(biāo)的定義可知，如果TR大于1，則表明算法得到的工作流調(diào)度解的執(zhí)行時(shí)間Makespan是小于整體期限約束的，反之亦然。同樣對(duì)于代價(jià)比率也有同樣的結(jié)果。圖6表明，本文算法得到的工作流調(diào)度方案的執(zhí)行時(shí)間對(duì)于不同程度的預(yù)算因子，總可以滿(mǎn)足期限約束。然而，根據(jù)圖7的CR指標(biāo)，若降低αD，本文算法的代價(jià)將超過(guò)預(yù)算。圖2-圖5給出的SR指標(biāo)的含義是在算法同時(shí)滿(mǎn)足期限約束和預(yù)算約束時(shí)成功調(diào)度的工作流的比例大小。圖7所示的CWFT算法雖然在降低執(zhí)行代價(jià)方面表現(xiàn)不錯(cuò)，但在圖6所示的TR指標(biāo)結(jié)構(gòu)中卻無(wú)法滿(mǎn)足期限約束，其SR指標(biāo)性能是所有算法中表現(xiàn)最差的。多數(shù)情況下，SABA算法均無(wú)法得到成功調(diào)度，即無(wú)法同時(shí)滿(mǎn)足兩個(gè)條件的約束，原因在于SABA算法進(jìn)行任務(wù)調(diào)度并未控制執(zhí)行代價(jià)，雖然該算法在總體執(zhí)行時(shí)間優(yōu)化上性能是最好的，但其代價(jià)性能是最差的。

圖6 時(shí)間比率指標(biāo)

圖7 代價(jià)比率指標(biāo)

5 結(jié) 語(yǔ)

為了求解在期限和預(yù)算雙重約束條件上的云工作流調(diào)度解，本文提出了一種新的調(diào)度算法。算法將工作流調(diào)度過(guò)程劃分為五個(gè)子階段，通過(guò)科學(xué)工作流結(jié)構(gòu)的仿真實(shí)驗(yàn)，證明了算法在調(diào)度成功率和執(zhí)行時(shí)間與執(zhí)行代價(jià)的同步優(yōu)化上較同類(lèi)型算法的性能更優(yōu)。