武麗芬，嚴(yán)學(xué)勇

(1.晉中學(xué)院 信息技術(shù)與工程系，山西 晉中 030600；2.中國(guó)聯(lián)通晉中分公司 信息支撐中心，山西 晉中 030600)

0 引 言

云計(jì)算環(huán)境中，資源可根據(jù)應(yīng)用需求動(dòng)態(tài)地分配至用戶任務(wù)，而用戶對(duì)資源的支付方式是即付即用的，這極大地區(qū)別于傳統(tǒng)的網(wǎng)格等分布式計(jì)算環(huán)境。這種特有的使用特征使得云計(jì)算提供了對(duì)科學(xué)工作流調(diào)度的最好支持。每一種大規(guī)模的工作流應(yīng)用均可建模為有向無(wú)循環(huán)圖DAG結(jié)構(gòu)，其中包含大量相互依賴和相互獨(dú)立的任務(wù)，有些可同步執(zhí)行，有些則需按照先后次序執(zhí)行。為了滿足用戶應(yīng)用的QoS需求，云工作流調(diào)度需要尋找有效的調(diào)度方案，實(shí)現(xiàn)任務(wù)與多資源間的映射與執(zhí)行。

目前，云資源的使用特征導(dǎo)致已有調(diào)度算法擁有以下不足：①資源使用時(shí)間固定。本文中資源只要在空閑狀態(tài)即可釋放，資源獲取是任意的，這樣可節(jié)省資源使用代價(jià)；②資源定價(jià)未使用賬單模型。本文應(yīng)用Amazon EC2的資源賬單定價(jià)模型，在已付賬單中，先前任務(wù)的空閑時(shí)間片可被下一任務(wù)繼續(xù)利用，以節(jié)省代價(jià)；③涉及多QoS參數(shù)時(shí)，已有搜索或元啟發(fā)式算法復(fù)雜度過(guò)高。本文將設(shè)計(jì)時(shí)間復(fù)雜度更低的工作流調(diào)度算法，同步滿足截止時(shí)間和預(yù)算約束，尋找調(diào)度可行解。

1 相關(guān)研究

對(duì)于工作流調(diào)度多目標(biāo)優(yōu)化問(wèn)題，本文將調(diào)度算法分為兩種類型：?jiǎn)喂ぷ髁髡{(diào)度和多工作流調(diào)度。單工作流調(diào)度僅涉及一次從入口任務(wù)至出口任務(wù)的執(zhí)行過(guò)程，而多工作流調(diào)度涉及入口任務(wù)與出口任務(wù)間的多次執(zhí)行過(guò)程。目前多集中于單工作流調(diào)度，但多數(shù)不適用于云環(huán)境，原因在于云計(jì)算具有即付即用和按需提供的特征，這與傳統(tǒng)資源提供方式具有極大不同。

單工作流調(diào)度的目標(biāo)是尋找任務(wù)與資源間的合適映射以滿足目標(biāo)函數(shù)優(yōu)化，具體包括：①代價(jià)最優(yōu)，截止時(shí)間約束。文獻(xiàn)[1]提出代價(jià)最優(yōu)化算法，利用任務(wù)復(fù)制機(jī)制增加滿足約束概率。文獻(xiàn)[2]提出動(dòng)態(tài)代價(jià)有效截止時(shí)間約束調(diào)度算法，實(shí)現(xiàn)單一工作流調(diào)度。除了以上啟發(fā)式算法，文獻(xiàn)[3,4]利用搜索和元啟發(fā)式算法優(yōu)化相同的目標(biāo)；②時(shí)間最優(yōu)，預(yù)算約束。文獻(xiàn)[5-7]提出啟發(fā)式算法最小化執(zhí)行時(shí)間，同時(shí)滿足預(yù)算約束。文獻(xiàn)[8]提出安全與預(yù)算感知調(diào)度算法SABA，可在滿足安全級(jí)的同時(shí)降低執(zhí)行時(shí)間；③時(shí)間最優(yōu)，代價(jià)最優(yōu)。很多文獻(xiàn)嘗試均衡最小化時(shí)間和代價(jià)兩種QoS。文獻(xiàn)[9]提出關(guān)鍵路徑優(yōu)先算法，利用工作流的擴(kuò)展與壓縮機(jī)制優(yōu)化時(shí)間和代價(jià)。文獻(xiàn)[10]提出Pareto最優(yōu)的代價(jià)-時(shí)間最優(yōu)調(diào)度算法。同樣地，利用Pareto最優(yōu)，文獻(xiàn)[11]通過(guò)設(shè)置反映用戶對(duì)于時(shí)間和代價(jià)偏好的代價(jià)有效因子，提出執(zhí)行時(shí)間和代價(jià)最小化調(diào)度算法；④截止時(shí)間約束，預(yù)算約束。文獻(xiàn)[12]提出雙約束健壯啟發(fā)式算法實(shí)現(xiàn)調(diào)度優(yōu)化，算法利用搜索策略對(duì)調(diào)度任務(wù)進(jìn)行重分配，以滿足時(shí)間和代價(jià)參數(shù)。以上工作的問(wèn)題在于：采用的資源定價(jià)模型不同于當(dāng)前云的帳單模型；調(diào)度過(guò)程中資源數(shù)量固定，不適應(yīng)于云環(huán)境；VM資源沒(méi)有設(shè)置釋放/獲取時(shí)間戳。

相比單工作流調(diào)度，多工作流調(diào)度研究相對(duì)較少。文獻(xiàn)[13]提出兩種分級(jí)工作流調(diào)度算法：宏觀多工作流調(diào)度和微觀單工作流調(diào)度。工作流基于QoS需求劃分為時(shí)間敏感型和代價(jià)敏感型，算法采有不同的調(diào)度策略可保證對(duì)于每種工作流類型的時(shí)間QoS和代價(jià)QoS的滿足。文獻(xiàn)[14]提出多DAG最大化吞吐量調(diào)度算法MTMD，可保證多個(gè)DAG在截止時(shí)間內(nèi)的完成比例。文獻(xiàn)[15]提出在線多工作流調(diào)度算法OMPHC-PCPR和OPHC-TR，兩種算法的不同在于資源分配的任務(wù)優(yōu)先級(jí)機(jī)制。

2 系統(tǒng)模型

2.1 應(yīng)用模型

工作流的建模方式為有向無(wú)循環(huán)圖DAG，以三元組G=表示工作流應(yīng)用DAG，T={t1,t2,…,tn}為有限任務(wù)集，n為工作流任務(wù)數(shù)量。邊集E為任務(wù)間的依賴關(guān)系，該依賴關(guān)系確保只有所有父任務(wù)完成并發(fā)送需要的輸入數(shù)據(jù)后，其子任務(wù)才開(kāi)始執(zhí)行。data表示數(shù)據(jù)傳輸量的n×n矩陣，data(ti,tj)表示tj執(zhí)行前ti需要向tj發(fā)送的數(shù)據(jù)量。Tavg(ti,tj)表示ti與tj間的平均傳輸時(shí)間，其值取決于所有資源對(duì)間的平均帶寬和延遲。對(duì)于給定的DAG，無(wú)前驅(qū)任務(wù)(父任務(wù))的任務(wù)稱為入口任務(wù)tentry，無(wú)后繼任務(wù)(子任務(wù))的任務(wù)稱為出口任務(wù)texit。

2.2 資源模型

云環(huán)境由m個(gè)異構(gòu)資源R={∪mj=1rj|rj∈VMtype}組成，可提供不同能力和代價(jià)的服務(wù)資源。假設(shè)所有計(jì)算和存儲(chǔ)資源處于同一數(shù)據(jù)中心，資源間的平均帶寬是相等的。執(zhí)行于同一VM上的兩個(gè)任務(wù)的傳輸時(shí)間為0。每個(gè)VM類型在其CPU能力、內(nèi)存容量和代價(jià)方面擁有自身配置。假設(shè)工作流應(yīng)用使用的資源VMs數(shù)量是不受限制的，且為了合理初始化以便于用戶使用，租用VM時(shí)需要一個(gè)初始的啟動(dòng)時(shí)間boot_time。同時(shí)，資源定價(jià)是基于VM的間隔時(shí)間(interval time)數(shù)量的即付即用賬單模型，用戶將根據(jù)interval time的執(zhí)行數(shù)量付費(fèi)。

對(duì)于特定資源rj，其平均性能以每秒進(jìn)行的浮點(diǎn)操作次數(shù)GFLOPs度量，其單位小時(shí)價(jià)格是已知的。表1給出了實(shí)驗(yàn)中使用的Amazon EC2所提供的4種VM資源類型的相關(guān)參數(shù)。

表1 Amazon EC2資源參數(shù)

令VMr/a表示每個(gè)VM在調(diào)度中更新的釋放/獲取時(shí)間戳排列，VMr/a={(S1,F1),(S2,F2),…}，(S,F)為目標(biāo)VM連續(xù)執(zhí)行的開(kāi)始時(shí)間和完成時(shí)間。該時(shí)間戳在任務(wù)調(diào)度至目標(biāo)VM時(shí)計(jì)算。

在為當(dāng)前任務(wù)tcurr選擇適當(dāng)資源rsel之后，如果該任務(wù)無(wú)法從資源rsel的上一執(zhí)行任務(wù)上降低其執(zhí)行代價(jià)，即：使用資源rsel上的之前最后任務(wù)的剩余時(shí)間間隔，資源rsel的VMr/a則通過(guò)以下方式更新：①最后調(diào)度任務(wù)執(zhí)行完后增加釋放時(shí)間；②根據(jù)tcurr的開(kāi)始時(shí)間增加獲取時(shí)間。否則，資源rsel的釋放時(shí)間將根據(jù)當(dāng)前任務(wù)的完成時(shí)間進(jìn)行更新。此外，令schedrj={ti|AR(ti)=rj}為資源rj上的調(diào)度任務(wù)集，AR(ti)為執(zhí)行ti的分配資源。每個(gè)schedrj集合基于其任務(wù)完成時(shí)間進(jìn)行排序。

2.3 問(wèn)題定義

工作流調(diào)度即為尋找任務(wù)與資源間的映射關(guān)系，以滿足用戶定義的QoS參數(shù)。本文所討論的調(diào)度問(wèn)題的QoS參數(shù)主要包括工作流的總執(zhí)行時(shí)間makespan和經(jīng)濟(jì)代價(jià)。

(1)執(zhí)行時(shí)間makespan

為了計(jì)算給定工作流的執(zhí)行時(shí)間，定義ti在資源rj上的處理時(shí)間TR為ti在資源rj上的執(zhí)行時(shí)間ET(ti,rj)與其任意父任務(wù)tp∈pred(ri)傳輸?shù)淖畲筝斎霑r(shí)間的要求時(shí)間之和，表示為

(1)

考慮到任務(wù)間的數(shù)據(jù)傳輸時(shí)間的存在性，對(duì)于每個(gè)在rj上執(zhí)行的ti，資源rj需要在ti開(kāi)始接收父任務(wù)傳輸數(shù)據(jù)之前進(jìn)行部署，且僅在其完成和數(shù)據(jù)已傳送至其子任務(wù)之后進(jìn)行釋放。令avail(tj)表示不考慮其父任務(wù)時(shí)ti在rj上的最早開(kāi)始時(shí)間

(2)

其中，tl表示資源rj上的任務(wù)調(diào)度排序表schedrj中的最后一個(gè)任務(wù)，F(xiàn)T(tl,rj)表示tl在rj上的完成時(shí)間?；赼vail(rj)，定義rj的釋放時(shí)間RT(rj)為資源上最后調(diào)度任務(wù)的最后租用小時(shí)數(shù)

(3)

圖1是簡(jiǎn)單調(diào)度，圖1中t1、t2和t3已調(diào)度，t4是當(dāng)前被選待調(diào)度任務(wù)。由式(3)及在3個(gè)資源上最后調(diào)度任務(wù)所使用的最后interval time可計(jì)算資源釋放時(shí)間，此時(shí)，t4未被調(diào)度但已分配至目標(biāo)資源。

圖1 調(diào)度示例

ti在資源rj上的開(kāi)始時(shí)間ST和完成時(shí)間FT可表示為

(4)

FT(ti,rj)=λ(ti,rj)+ST(ti,rj)+TR(ti,rj)

(5)

其中，λ(ti,rj)為資源rj的啟動(dòng)時(shí)間。如果ti可在rj的最后interval time上開(kāi)始，則任務(wù)完成時(shí)不考慮啟動(dòng)時(shí)間；否則，需要啟動(dòng)目標(biāo)資源rj，并將其啟動(dòng)時(shí)間考慮至任務(wù)完成時(shí)間中。例如，圖1中，僅當(dāng)t4調(diào)度至VM3時(shí)，啟動(dòng)時(shí)間才考慮至完成時(shí)間中，由于t4在VM3的當(dāng)前釋放時(shí)間之后才執(zhí)行。λ(ti,rj)計(jì)算為

(6)

其中，boot_timerj表示VM的啟動(dòng)時(shí)間，實(shí)驗(yàn)中設(shè)置為97 s[16]。

工作流總執(zhí)行時(shí)間makespan可定義為最后執(zhí)行完成的任務(wù)(出口任務(wù))的完成時(shí)間，即

DAGmakespan=FT(texit)

(7)

(2)執(zhí)行代價(jià)cost

ti在資源rj上的執(zhí)行代價(jià)根據(jù)任務(wù)完成的總資源使用時(shí)間計(jì)算，包括數(shù)據(jù)傳輸時(shí)間、執(zhí)行時(shí)間和資源使用價(jià)格。對(duì)于Amazon EC2實(shí)例而言，不足一小時(shí)的資源使用仍支付整數(shù)小時(shí)代價(jià)，因此，如果任務(wù)能在已支付時(shí)間間隔內(nèi)完成，則該任務(wù)無(wú)需支付費(fèi)用。定義ti的總使用時(shí)間為需要支付的周期時(shí)間

(8)

如果ti在rj的當(dāng)前釋放時(shí)間RT(rj)之前開(kāi)始且在其之后完成，則出現(xiàn)第3種情況。此時(shí)，RT(rj)之前的時(shí)間片需由之前的任務(wù)支付，且無(wú)需考慮在ti的當(dāng)前使用時(shí)間之內(nèi)。

對(duì)于第二種情況，如果任務(wù)在之前的支付時(shí)間間隔內(nèi)執(zhí)行(未完全利用)且未支付額外代價(jià)，則Ptime(ti,rj)=0。例如，圖1中，如果當(dāng)前t4被調(diào)度至資源VM2，則Ptime(t4,VM2)=0。通過(guò)式(8)，VM1的支付時(shí)間為Ptime(t4,VM1)=FT(t4,VM1)-RT(VM1)，對(duì)于VM3有Ptime(t4,VM3)=FT(t4,VM3)-ST(t4,VM3)。同時(shí)，通過(guò)式(5)，VM3的啟動(dòng)時(shí)間boot_time已考慮在FT(t4,VM3)內(nèi)。

對(duì)于Ptime>0，任務(wù)ti在資源rj上的執(zhí)行代價(jià)為

(9)

其中，Prj表示每個(gè)使用間隔中資源rj的使用代價(jià)，即表1中的價(jià)格。因此，工作流總執(zhí)行代價(jià)可表示為

(10)

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

本節(jié)設(shè)計(jì)截止時(shí)間與預(yù)算雙QoS約束云工作流調(diào)度算法DBWS(deadline-budget constraint workflow scheduling)，旨在尋找滿足雙QoS約束的調(diào)度可行解。在滿足截止時(shí)間約束的同時(shí)，如果執(zhí)行代價(jià)也滿足預(yù)算，則視為一種成功的可行調(diào)度，否則，視為調(diào)度失效。算法通過(guò)調(diào)度成功率進(jìn)行評(píng)估。

為了便于算法描述，以下給出相關(guān)符號(hào)說(shuō)明：

tcurr：表示當(dāng)前調(diào)度任務(wù)，即所有就緒任務(wù)中在任務(wù)選擇階段中選擇的目標(biāo)任務(wù)；

rsel：表示執(zhí)行任務(wù)tcurr的目標(biāo)資源；

FTmin(tcurr)和FTmax(tcurr)：表示當(dāng)前任務(wù)tcurr在所有測(cè)試資源上的最小和最大完成時(shí)間；

l(ti)：表示ti的分級(jí)，即從入口任務(wù)至ti間路徑邊的最大值。對(duì)于入口任務(wù)，其分級(jí)l(tentry)=1，對(duì)于其它任務(wù)

(11)

Costmin(tcurr)和Costmax(tcurr)：表示當(dāng)前任務(wù)tcurr在所有測(cè)試資源上的最小和最大執(zhí)行代價(jià)；

Costhigh(DAG)和Costlow(DAG)：表示將工作流調(diào)度至所有資源類型中代價(jià)最高和最低的異構(gòu)VMs集合上的總執(zhí)行代價(jià)。

算法分為兩個(gè)階段：任務(wù)選擇階段和資源選擇階段。

3.1 任務(wù)選擇階段

任務(wù)根據(jù)優(yōu)先級(jí)進(jìn)行選擇。利用任務(wù)在工作流中的自頂向下分級(jí)值ranku賦予優(yōu)先級(jí)，即：對(duì)于ti，其分級(jí)值為ti至出口任務(wù)texit間的最長(zhǎng)路徑的長(zhǎng)度，包括ti的計(jì)算時(shí)間，表示為

ranku(tchild)}

(12)

其中，ETavg(ti)表示ti在所有資源上的平均執(zhí)行時(shí)間，Tavg(ti,tchild)表示ti與其子任務(wù)tchild間的平均傳輸時(shí)間，succ(ti)表示ti的直接后繼(子)任務(wù)集。對(duì)于出口任務(wù)則有：ranku(texit)=ETavg(texit)。

3.2 資源選擇階段

對(duì)于執(zhí)行當(dāng)前任務(wù)的目標(biāo)VM資源的選擇需要在雙QoS的約束下同時(shí)考慮代價(jià)與時(shí)間的因素。為了選擇最優(yōu)資源，需要均衡時(shí)間與代價(jià)。定義SDL作為時(shí)間約束，表示總截止時(shí)間在每個(gè)任務(wù)的截止時(shí)間子分配。

首先，將任務(wù)根據(jù)其在工作流DAG中的深度進(jìn)行不同的分級(jí)，定義Levelexe為對(duì)應(yīng)分級(jí)中所有任務(wù)的最大執(zhí)行長(zhǎng)度

(13)

其中，ETmax(ti)表示ti在所有VM類型VMtype中的最大執(zhí)行時(shí)間。

(14)

對(duì)于第一級(jí)，式(14)的前半部分為0。

最后，所有屬于同一級(jí)的任務(wù)擁有相等子截止時(shí)間

(15)

需要說(shuō)明的是，如果當(dāng)前任務(wù)無(wú)法找到滿足其子截止時(shí)間約束的執(zhí)行資源，則選擇能夠最早完成該任務(wù)的資源執(zhí)行。

為了在時(shí)間和代價(jià)同步最小上取得均衡，資源選擇階段需要考慮時(shí)間和代價(jià)兩個(gè)QoS。定義TimeQ和CostQ分別為當(dāng)前任務(wù)tcurr的時(shí)間質(zhì)量和代價(jià)質(zhì)量，對(duì)于資源rj∈R∪R’上的當(dāng)前任務(wù)tcurr，R為調(diào)度前一步中使用的資源集，R’表示來(lái)自于可用VMtype中的一個(gè)臨時(shí)資源集。在為任務(wù)tcurr選擇了合適資源rsel之后的每一步中，R通過(guò)R={R∪rsel|rsel?R}的方式進(jìn)行更新。

通過(guò)式(16)和式(17)對(duì)時(shí)間質(zhì)量和代價(jià)質(zhì)量進(jìn)行標(biāo)準(zhǔn)化處理

(16)

(17)

其中

(18)

TimeQ用來(lái)度量當(dāng)前任務(wù)在rj上的完成時(shí)間與任務(wù)子截止時(shí)間SDL的接近程度。子截止時(shí)間定義了任務(wù)完成時(shí)間的最大限度。通常，資源的TimeQ值越高，則完成時(shí)間與子截止時(shí)間距離越大，該資源被選擇的概率也越大。如果當(dāng)前任務(wù)在rj上的完成時(shí)間高于其子截止時(shí)間，則rj的TimeQ值為負(fù)值，表明降低了該資源被選擇的概率。類似地，CostQ用來(lái)度量當(dāng)前任務(wù)在rj上的實(shí)際執(zhí)行代價(jià)與最大執(zhí)行代價(jià)的相差程度。

如果沒(méi)有任一資源可確保當(dāng)前任務(wù)的子截止時(shí)間SDL(tcurr)，則對(duì)于所有資源CostQ=0，對(duì)于每個(gè)rj的TimeQ值為負(fù)值，表明在rj上得到的相對(duì)完成時(shí)間，即：更低的完成時(shí)間導(dǎo)致更小負(fù)值。同時(shí)，資源的TimeQ值越高，被選概率也越大。

最后，為了選擇最優(yōu)目標(biāo)資源，將兩種QoS質(zhì)量綜合考慮，資源rj的質(zhì)量Q表示為

Q(tcurr,rj)=TimeQ(tcurr,rj)×(1-CF)+CostQ(tcurr,rj)×CF

(19)

其中，CF表示代價(jià)均衡因子，定義為

(20)

可以看出，CF越低，表明用戶越傾向于更快的執(zhí)行工作流，時(shí)間質(zhì)量TimeQ將在資源質(zhì)量Q中占更大比重。同理，CF越高，表明用戶可用預(yù)算更接近于最低執(zhí)行代價(jià)，因此，時(shí)間質(zhì)量TimeQ將被相對(duì)忽視，而代價(jià)質(zhì)量CostQ將成為主要影響因素，并允許選擇更低價(jià)的資源為執(zhí)行tcurr確保更低的執(zhí)行代價(jià)。

3.3 算法流程與時(shí)間復(fù)雜度

算法1給出DBWS算法的執(zhí)行流程。

Input: workflow DAG with two QoS parameters,DuserandBuser

Output: schedule mapping

(1)compute and sort all tasks based on their upward rank

(2) compute schedule cost on the resources with cheapest (Costlow) and most expensive (Costhigh) cost fromVMtype

(3) ifBuser

(4) return no possible schedule map

(5) else ifBuser>Costhigh(DAG)

(6) return PEFT scheduled map on most expen-siveVMtype

(7) end if

(8) compute the Sub-Deadline value (SDL) for each task

(9) while there is an unscheduled task do

(10)tcurr=the next ready task with highestrankuvalue

(11) for allrj∈R∪R’

(12) calculate QualityQ(tcurr,rj) by Eq.(19)

(13) end for

(14)rsel=resourcerjwith highest Quality (Q)

(15) assign current tasktcurrto resourcersel

(16) updateR={R∪rsel|rsel?R}

(17) updateVMr/a(rsel)

(18) end while

(19) return schedule map

算法詳細(xì)說(shuō)明：步驟(1)、步驟(2)進(jìn)行初始化，步驟(3)檢測(cè)是否存在預(yù)算約束內(nèi)的調(diào)度映射解。步驟(8)通過(guò)式(15)計(jì)算每個(gè)任務(wù)的子截止時(shí)間，然后，通過(guò)重復(fù)執(zhí)行步驟(9)～步驟(18)映射工作流任務(wù)。步驟(10)中，選擇所有就緒任務(wù)中擁有最高優(yōu)先級(jí)(ranku)的任務(wù)作為當(dāng)前調(diào)度任務(wù)tcurr。步驟(11)～步驟(13)中，計(jì)算tcurr的調(diào)度資源rj的質(zhì)量Q(tcurr,rj)。此時(shí)，首先計(jì)算當(dāng)前任務(wù)的完成時(shí)間FT和執(zhí)行代價(jià)，然后計(jì)算所有資源的質(zhì)量，步驟(14)選擇所有資源中擁有最高質(zhì)量的作為被選資源rsel。最后，分配當(dāng)前任務(wù)至所選資源后，更新資源rsel的釋放/獲取時(shí)間戳。

時(shí)間復(fù)雜度分析。DBWS算法需要計(jì)算每個(gè)任務(wù)的自頂向下分級(jí)ranku和子截止時(shí)間SDL，該步驟的時(shí)間復(fù)雜度為O(n×p)，其中，p為可用資源數(shù)量，n為任務(wù)數(shù)量。在資源選擇階段，為了給當(dāng)前任務(wù)尋找和分配資源，在所有資源間計(jì)算當(dāng)前任務(wù)的ST和FT的時(shí)間復(fù)雜度為O(n×p)，計(jì)算資源質(zhì)量的時(shí)間復(fù)雜度為O(p)，則總時(shí)間復(fù)雜度為O(n×p+n×(n×p+p))=O(n2×p)。

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

本節(jié)通過(guò)WorkflowSim的仿真實(shí)驗(yàn)評(píng)估算法性能，選擇4種調(diào)度算法進(jìn)行性能比較，包括：HYBIRD算法[11]、MTCT算法[17]、CWFT算法[18]和SABA算法[8]。選擇4種常見(jiàn)科學(xué)工作流作為測(cè)試數(shù)據(jù)結(jié)構(gòu)[19]，包括：CyberShake、Epigenomic、LIGO和Montage，CyberShake和LIGO存儲(chǔ)需求更大，Epigenomic屬于CPU-bound型工作流，Montage屬于I/O-bound型工作流，同時(shí)CyberShake還屬于數(shù)據(jù)密集型工作流。基于數(shù)據(jù)多樣性，為每種工作流隨機(jī)產(chǎn)生100個(gè)工作流DAG，每種工作流的任務(wù)數(shù)量設(shè)置為100、200和300。

4.1 截止時(shí)間和預(yù)算約束設(shè)置

定義截止時(shí)間和預(yù)算為

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

(21)

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

(22)

其中，minD和maxD分別表示將工作流調(diào)度至代價(jià)最小和最大的資源集合上執(zhí)行時(shí)得到的總執(zhí)行時(shí)間makespan，而此時(shí)對(duì)應(yīng)的工作流執(zhí)行代價(jià)則分別為maxB和minB。通過(guò)這種設(shè)置截止時(shí)間和預(yù)算的上下限方式，可以確保兩種QoS約束的實(shí)際可行。

公式中，αD和αB分別表示截止時(shí)間因子和預(yù)算因子，αD、αB∈[0,1]。為了觀察算法尋找有效調(diào)度解的性能，設(shè)置αD、αB為{0.1,0.3,0.5}進(jìn)行了測(cè)試。

4.2 性能指標(biāo)

選擇調(diào)度成功率SR作為指標(biāo)，該指標(biāo)給出實(shí)驗(yàn)中算法進(jìn)行有效調(diào)度的百分比，成功調(diào)度的衡量方式為同時(shí)滿足截止時(shí)間與預(yù)算約束的一次工作流調(diào)度過(guò)程

(23)

此外，分別選擇截止時(shí)間與完成時(shí)間makespan的比例、預(yù)算與工作流調(diào)度代價(jià)的比例作為另一性能指標(biāo)，分別表示為

NM=Duser/DAGmakespan

(24)

NB=Buser/DAGcost

(25)

NM和NB比較1越小，則表明調(diào)度方案越無(wú)法滿足約束。

4.3 結(jié)果分析

圖2～圖5是算法的平均調(diào)度成功率結(jié)果。DBWS比較其它算法得到更高的成功率。同時(shí)，通過(guò)增加預(yù)算因子αB，對(duì)于工作流將擁有更多的可用預(yù)算，導(dǎo)致DBWS的平均SR會(huì)進(jìn)一步增加。而在較短的截止時(shí)間內(nèi)(αD=0.1)，在4種工作流的大多數(shù)情況中，僅有DBWS可以完成調(diào)度工作流(圖3～圖5)。

圖2 CyberShake工作流

圖3 Epigenomic工作流

圖4 LIGO工作流

圖5 Montage工作流

圖6和圖7是算法的NM和NB情況。如果NM>1，表明算法可以得到makespan低于截止時(shí)間的調(diào)度解，反之亦然。NB也是同理。圖6中，DBWS得到的調(diào)度解makespan在所有預(yù)算因子下總可以滿足截止時(shí)間約束。然而，對(duì)于圖7中的總執(zhí)行代價(jià)，通過(guò)降低截止時(shí)間因子，DBWS的調(diào)度解執(zhí)行代價(jià)會(huì)高于預(yù)算約束。圖2～圖5中的SR指標(biāo)所表示的是同時(shí)滿足時(shí)間和代價(jià)約束的調(diào)度工作流的比例。例如：盡管圖7中的CWFT算法極大降低了執(zhí)行代價(jià)，但在圖6中卻無(wú)法滿足截止時(shí)間約束，其SR指標(biāo)是所有算法中最差的。SABA的SR指標(biāo)上則在大多數(shù)情況下均無(wú)法得到成功調(diào)度。主要是該算法沒(méi)有考慮執(zhí)行代價(jià)的控制，因此，圖6～圖7顯示出SABA算法在降低總執(zhí)行時(shí)間上擁有最好的性能，而代價(jià)方面則是最差的。

圖6 NM指標(biāo)

圖7 NB指標(biāo)

5 結(jié)束語(yǔ)

為了滿足截止時(shí)間和預(yù)算的雙QoS約束，提出了一種云工作流調(diào)度算法DBWS。算法將工作流調(diào)度劃分為任務(wù)選擇和資源選擇兩個(gè)階段。任務(wù)選擇階段中利用任務(wù)的自項(xiàng)向下分級(jí)值為任務(wù)分配調(diào)度優(yōu)先級(jí)。然后，在資源選擇階段中，將用戶定義的截止時(shí)間在不同分級(jí)任務(wù)上進(jìn)行子截止時(shí)間分配，并通過(guò)時(shí)間質(zhì)量和代價(jià)質(zhì)量尋找最優(yōu)的目標(biāo)資源。實(shí)驗(yàn)結(jié)果表明，DBWS算法在調(diào)度成功率和同步滿足兩種QoS約束上性能是更優(yōu)的。