滿足實(shí)時(shí)云任務(wù)需求的主動(dòng)響應(yīng)式工作流調(diào)度模型

王 旖 旎

(重慶商務(wù)職業(yè)學(xué)院 重慶 401331)

0 引 言

云計(jì)算是一種革新式的應(yīng)用，可以以即付即用的計(jì)算模式提供按需形式的應(yīng)用、平臺、基礎(chǔ)設(shè)施[1-3]。本質(zhì)上，云提供者需要部署大量的虛擬機(jī)以滿足廣泛分布的用戶需求，同步地為云提供方和用戶方降低運(yùn)營代價(jià)。此外，云提供方可以根據(jù)平臺負(fù)載動(dòng)態(tài)地調(diào)整可用的虛擬機(jī)資源，從而進(jìn)一步做到代價(jià)的節(jié)省。有賴于云計(jì)算低代價(jià)、彈性應(yīng)用、高可用性的特征，云計(jì)算平臺可執(zhí)行的應(yīng)用領(lǐng)域也越來越廣泛[4-6]。一種描述應(yīng)用過程的典型模式即為工作流，它由多數(shù)量的具有數(shù)據(jù)相關(guān)性的任務(wù)圖組成，通常以有向無環(huán)圖的形式描述[6-8]。對于云平臺而言，該類工作流應(yīng)用擁有實(shí)時(shí)性的特征，主要體現(xiàn)在兩個(gè)方面，一是廣泛分布的用戶的動(dòng)態(tài)發(fā)送請求，其到達(dá)時(shí)間是無法預(yù)知的；二是其需要邏輯上和臨時(shí)計(jì)算上的正確性，進(jìn)而確保工作流處理的時(shí)效要求。

目前，大量工作集中在云平臺上的工作流調(diào)度問題上。但是，多數(shù)已有工作流集中于單一工作流調(diào)度，且無法處理實(shí)時(shí)工作流調(diào)度問題。原因在于：首先，調(diào)度實(shí)時(shí)工作流任務(wù)時(shí)，由于工作流任務(wù)間的數(shù)據(jù)依賴性導(dǎo)致大量虛擬機(jī)的空閑時(shí)槽無法利用；其次，若按序調(diào)度實(shí)時(shí)工作流，通過合并不同資源上的工作流任務(wù)降低空閑時(shí)槽的方法可能增加算法的復(fù)雜性。更糟的是，合并工作流任務(wù)可能延遲任務(wù)的執(zhí)行時(shí)間，從而導(dǎo)致工作流執(zhí)行的截止時(shí)間無法得到保證。

如果來自不同工作流的任務(wù)可按序在相同虛擬機(jī)上執(zhí)行，則由于數(shù)據(jù)依賴導(dǎo)致的空閑時(shí)槽可被充分利用，進(jìn)而有助于改進(jìn)執(zhí)行代價(jià)和云平臺的資源利用率。基于此，本文主要研究如何以混合形式調(diào)度不同工作流任務(wù)，為了提高效率，著眼于如何擴(kuò)展和壓縮可用的虛擬機(jī)資源，實(shí)現(xiàn)代價(jià)更高效的工作流調(diào)度。

1 相關(guān)研究工作

工作流應(yīng)用是分布式計(jì)算環(huán)境中的普遍形式，如大數(shù)據(jù)分析應(yīng)用、圖像處理應(yīng)用、科學(xué)工作流應(yīng)用等，其中涉及大量相互依賴的任務(wù)執(zhí)行需求。近年來，工作流調(diào)度問題越來越受到關(guān)注，大量的工作流調(diào)度算法被提出，而已有算法可以劃分為三類：表調(diào)度算法、聚類調(diào)度算法、元啟發(fā)式調(diào)度算法。表調(diào)度算法是工作流調(diào)度的常用形式，其主要過程包括兩步：(1) 為每個(gè)工作流任務(wù)分配優(yōu)先級；(2) 基于任務(wù)優(yōu)先級調(diào)度工作流調(diào)度。例如：第一個(gè)基于表調(diào)度的工作流調(diào)度算法HEFT[9]，基于任務(wù)升秩值設(shè)置任務(wù)優(yōu)先級之后，再將其調(diào)度至完成時(shí)間最小的處理器上執(zhí)行。文獻(xiàn)[10]擴(kuò)展了HEFT算法，以改進(jìn)執(zhí)行跨度和能效為目標(biāo)尋找工作流調(diào)度的Pareto解集合。文獻(xiàn)[11]提出一種隨機(jī)等級調(diào)度算法以隨機(jī)運(yùn)行時(shí)間調(diào)度工作流任務(wù)。但是，以上方法僅關(guān)注于單一工作流的調(diào)度問題，在滿足截止時(shí)間下的云平臺中的多工作流調(diào)度問題上顯得效率較低。

部分工作通過對工作流任務(wù)進(jìn)行聚類的方式實(shí)現(xiàn)工作流調(diào)度。文獻(xiàn)[12]設(shè)計(jì)一種局部關(guān)鍵路徑算法PCP進(jìn)行網(wǎng)格中的工作流調(diào)度，可以實(shí)現(xiàn)滿足截止時(shí)間下的代價(jià)最優(yōu)。PCP算法的兩個(gè)關(guān)鍵步驟是：首先進(jìn)行截止時(shí)間的分配，即將總體截止時(shí)間在每個(gè)工作流任務(wù)間進(jìn)行子劃分；然后為調(diào)度階段，即分配每個(gè)任務(wù)至滿足子截止時(shí)間下執(zhí)行代價(jià)最小的實(shí)例上。文獻(xiàn)[13]擴(kuò)展PCP算法得到了兩種新的算法IC-PCP和IC-PCP2，實(shí)現(xiàn)了云環(huán)境中的工作流調(diào)度。文獻(xiàn)[14]設(shè)計(jì)了云工作流調(diào)度算法RCT，主要步驟是：首先根據(jù)任務(wù)相關(guān)性將工作流任務(wù)聚類為多個(gè)局部關(guān)鍵路徑，然后在滿足時(shí)間和代價(jià)約束的基礎(chǔ)上為每條關(guān)鍵路徑生成一個(gè)可行調(diào)度解集合，最后對解集合進(jìn)行優(yōu)化，選擇最優(yōu)解。但是，以上方法沒有云環(huán)境提供資源的動(dòng)態(tài)性，對于調(diào)度實(shí)時(shí)工作流的效率顯然不高。

元啟發(fā)式調(diào)度算法是解決工作流調(diào)度的另一有效方法。文獻(xiàn)[15]利用PSO降低了工作流調(diào)度的執(zhí)行代價(jià)，同時(shí)可以確保時(shí)間約束。文獻(xiàn)[16]同樣利用PSO增強(qiáng)了調(diào)度的負(fù)載能力。文獻(xiàn)[17]利用GA得到了云工作流調(diào)度的Pareto解集，在執(zhí)行跨度和能效上均得到了優(yōu)化。文獻(xiàn)[18]設(shè)計(jì)了基于蜂群的工作流調(diào)度算法JDS-BC，同步降低了執(zhí)行跨度和數(shù)據(jù)傳輸時(shí)間。文獻(xiàn)[19]利用GA對工作流進(jìn)行了分級，然后通過啟發(fā)式方法對任務(wù)進(jìn)行映射。文獻(xiàn)[20]結(jié)合啟發(fā)式方法和進(jìn)化搜索方法求解了工作流調(diào)度問題。文獻(xiàn)[21]設(shè)計(jì)了新的進(jìn)化搜索方法對單一工作流調(diào)度的時(shí)間和代價(jià)進(jìn)行均衡。文獻(xiàn)[22]利用種群協(xié)作機(jī)制同步優(yōu)化執(zhí)行跨度、代價(jià)和調(diào)度能耗。但是，以上隨機(jī)化搜索算法通常具有較高的時(shí)間復(fù)雜度，應(yīng)用在云環(huán)境中的工作流調(diào)度問題上擁有諸多限制。

在已有的多工作流調(diào)度研究中，文獻(xiàn)[23]設(shè)計(jì)了一種收益感知算法，在滿足預(yù)算和時(shí)間約束的情況下可以提高工作流調(diào)度的收益。文獻(xiàn)[24]在公平和優(yōu)先原則的基礎(chǔ)上設(shè)計(jì)了一種均衡策略，可以確保工作流調(diào)度的截止期限。文獻(xiàn)[25]在考慮時(shí)間和費(fèi)用約束的基礎(chǔ)上實(shí)現(xiàn)了并行任務(wù)的完成率提升。文獻(xiàn)[26]則充分利用虛擬機(jī)之間的空閑時(shí)槽降低工作流執(zhí)行代價(jià)。但是，以上方法沒有不同工作流中并行任務(wù)的到達(dá)，沒有充分利用計(jì)算資源的空閑時(shí)間。

2 問題描述

云平臺下的工作流可建立模型為WS={w1,w2,…,wn}。對于每一個(gè)工作流wi∈WS又可以建立為一個(gè)三元組模型wi={Gi,ai,Di}，Gi代表工作流wi的任務(wù)結(jié)構(gòu)，ai代表工作流的到達(dá)時(shí)間，Di代表工作流完成的截止時(shí)間。工作流的結(jié)構(gòu)Gi可以建立模型為有向無循環(huán)圖結(jié)構(gòu)，表示為DAGGi=(Ti,Ei)，其中：Ti={t1,i,t2,i,…,ti,|Ti|}代表有向圖中的頂點(diǎn)集合，表示任務(wù)節(jié)點(diǎn)，ti,j代表工作流wi中的任務(wù)j；|Ti|代表集合Ti中的頂點(diǎn)數(shù)，即任務(wù)數(shù)；Ei?Ti×Ti代表任務(wù)節(jié)點(diǎn)間的有向邊集合。一條有向邊ei,p,j∈Ei代表任務(wù)ti,j開始執(zhí)行取決于執(zhí)行任務(wù)ti,p的輸出數(shù)據(jù)，而ti,p是任務(wù)ti,j的直接前驅(qū)任務(wù)之一，ti,j是任務(wù)ti,p的直接后繼任務(wù)之一。集合pred(ti,j)代表所有ti,j的直接前驅(qū)任務(wù)組成的集合，succ(ti,j)代表所有ti,j的直接后繼任務(wù)組成的集合。

云平臺可以提供不同類型不同數(shù)量的虛擬機(jī)VM服務(wù)，令m代表云平臺中可用的虛擬機(jī)類型的數(shù)量，u∈{1,2,…,m}代表VM類型的標(biāo)識號，每種虛擬機(jī)類型對應(yīng)一個(gè)使用代價(jià)p(u)，則VMu,k代表類型為u的第k個(gè)虛擬機(jī)，再令ck,l代表虛擬機(jī)su,k與虛擬機(jī)su′,h間的通信帶寬。

云平臺下的虛擬機(jī)可在任意時(shí)刻進(jìn)行租用和釋放，本文假設(shè)當(dāng)一臺虛擬機(jī)空閑時(shí)，即該虛擬機(jī)已經(jīng)完成所有映射任務(wù)和數(shù)據(jù)傳輸后，即可被釋放。進(jìn)一步，虛擬機(jī)按其租用的時(shí)間單位按整數(shù)進(jìn)行付費(fèi)，單位時(shí)間內(nèi)的部分時(shí)間租用也按整數(shù)單位時(shí)間付費(fèi)，即若付費(fèi)時(shí)間單位為1小時(shí)，若虛擬機(jī)租用時(shí)間為1小時(shí)1分鐘，也將按2小時(shí)付費(fèi)。由于任務(wù)只有在接收完其所有前驅(qū)任務(wù)的數(shù)據(jù)后才能開始執(zhí)行，則存在如下約束：

FTi,p,k+TTi,p,j≤STi,j,k

(1)

式中：FTi,p,k代表任務(wù)ti,p在虛擬機(jī)VMu,k上的完成時(shí)間；TTi,p,j代表任務(wù)ti,p與ti,j間的數(shù)據(jù)傳輸時(shí)間；STi,j,k為任務(wù)ti,j在虛擬機(jī)VMu,k上的開始時(shí)間。

在工作流wi的所有任務(wù)被調(diào)度至虛擬機(jī)執(zhí)行后，wi的完成時(shí)間FTi可定義為所有任務(wù)中的最大完成時(shí)間，即：

(2)

為了確保工作流執(zhí)行的截止時(shí)間，工作流wi中的所有任務(wù)必須在其期限D(zhuǎn)i內(nèi)完成，即存在以下約束：

FTi≤Di?wi∈WS

(3)

結(jié)合式(1)的數(shù)據(jù)依賴約束和式(3)的截止時(shí)間約束，云平臺下的多工作流調(diào)度問題的第一個(gè)目標(biāo)是降低完成工作流集WS的總體執(zhí)行代價(jià)TC，可形式化為：

(4)

式中:|VM|代表處理工作流集合WS時(shí)租用的虛擬機(jī)量；Pk代表租用虛擬機(jī)VMu,k的時(shí)間單位數(shù)量。

對于云資源提供方而言，其目標(biāo)是追求盡量高的資源利用率AU。虛擬機(jī)資源的利用率定義為虛擬機(jī)執(zhí)行工作流任務(wù)的有效工作時(shí)間與虛擬機(jī)完整運(yùn)行時(shí)間的比例，虛擬機(jī)完整運(yùn)行時(shí)間包括虛擬機(jī)有效工作時(shí)間和無任務(wù)執(zhí)行空閑時(shí)的等待時(shí)間。基于此，多工作流調(diào)度問題的另一個(gè)目標(biāo)是最大化虛擬機(jī)的平均資源利用率，可形式化為：

(5)

式中：wtk代表處理工作流WS時(shí)虛擬機(jī)VMu,k的有效工作時(shí)間；TTk代表虛擬機(jī)VMu,k的完整運(yùn)行時(shí)間，包括工作時(shí)間和空閑等待時(shí)間。

為了便于云計(jì)算環(huán)境中的工作流任務(wù)調(diào)度仿真，本文將應(yīng)用工作流仿真平臺WorkFlowSim實(shí)現(xiàn)算法仿真。該平臺在既有云任務(wù)仿真平臺CloudSim的基礎(chǔ)上擴(kuò)展而來，支持本文所構(gòu)建的有向無環(huán)圖模型的工作流調(diào)度。同時(shí)，為了實(shí)現(xiàn)多工作流調(diào)度模型，平臺中可通過觸發(fā)器生成多類型不同結(jié)構(gòu)的工作流，支持實(shí)時(shí)多工作流調(diào)度需求。而為了統(tǒng)計(jì)調(diào)度算法優(yōu)化目標(biāo)中的任務(wù)總體執(zhí)行代價(jià)和虛擬機(jī)資源利用率，實(shí)驗(yàn)過程中調(diào)度器會實(shí)時(shí)統(tǒng)計(jì)運(yùn)行狀態(tài)的虛擬機(jī)資源量、虛擬機(jī)被租用的時(shí)間單位數(shù)量、虛擬機(jī)的完整運(yùn)行時(shí)間，以便衡量工作流調(diào)度算法的執(zhí)行效果。

3 調(diào)度模型與算法設(shè)計(jì)

3.1 調(diào)度模型

本節(jié)設(shè)計(jì)了云平臺下的響應(yīng)式工作流調(diào)度模型，如圖1所示。調(diào)度模型由三個(gè)部分構(gòu)成：用戶方、調(diào)度器、云資源提供方。云平臺可向廣泛分布的用戶提供服務(wù)，用戶方則可以在任意時(shí)間向云平臺發(fā)送其工作流任務(wù)的執(zhí)行請求。調(diào)度器作為用戶方與資源方的連接橋梁，可以動(dòng)態(tài)地將工作流執(zhí)行請求調(diào)度至虛擬機(jī)資源上，并根據(jù)云平臺的負(fù)載狀況動(dòng)態(tài)調(diào)整資源方所提供的可用虛擬機(jī)資源，形成可擴(kuò)展可收縮的資源池。

圖1 響應(yīng)式工作流調(diào)度模型

任務(wù)就緒狀態(tài)。若一個(gè)任務(wù)的所有前驅(qū)任務(wù)均已在虛擬機(jī)上完成，或任務(wù)不存在任一前驅(qū)任務(wù)，即pred(ti,j)=?，則該工作流任務(wù)視為就緒狀態(tài)。

為了以混合方式調(diào)度來自不同工作流的任務(wù)，每臺虛擬機(jī)至多僅有一個(gè)等待任務(wù)，而其他等待任務(wù)將臨時(shí)放置在工作流任務(wù)隊(duì)列中。當(dāng)工作流任務(wù)就緒后，它們將被移動(dòng)至就緒任務(wù)隊(duì)列。由于就緒任務(wù)隊(duì)列中的就緒任務(wù)來自于不同的工作流，且它們之間不存在數(shù)據(jù)依賴關(guān)系，調(diào)度這些就緒任務(wù)可以改進(jìn)代價(jià)和資源利用率。調(diào)度算法的主要目標(biāo)是生成適應(yīng)于可用數(shù)量虛擬機(jī)資源的調(diào)度策略，并調(diào)度工作流任務(wù)隊(duì)列中的等待任務(wù)至虛擬機(jī)上執(zhí)行。調(diào)度算法部分包括三個(gè)對工作流的調(diào)度響應(yīng)策略：1) 新到達(dá)工作流的響應(yīng)調(diào)度策略；2) 任務(wù)完成的響應(yīng)策略；3) 緊迫任務(wù)的響應(yīng)調(diào)度策略。調(diào)度響應(yīng)策略不僅可以滿足多工作流的執(zhí)行需求，而且可以實(shí)時(shí)響應(yīng)緊迫型工作流任務(wù)的執(zhí)行需求，充分利用虛擬機(jī)資源的空閑時(shí)槽和更大化的任務(wù)并行程度，以混合形式調(diào)度來自不同工作流的任務(wù)，在確保截止期限約束的同時(shí)，有效滿足實(shí)時(shí)云任務(wù)的調(diào)度需求。

當(dāng)進(jìn)行工作流調(diào)度時(shí)，若某些工作流在隊(duì)列中的等待時(shí)間過長，則會導(dǎo)致無法滿足工作流的截止時(shí)間約束。為了解決這一問題，需要定義每個(gè)任務(wù)的最遲開始時(shí)間LSTi,j，必須使每個(gè)工作流任務(wù)在該時(shí)間前開始執(zhí)行，如此，工作流wi的完成時(shí)間即可在其截止時(shí)間之前。由于云平臺下的虛擬機(jī)資源是異構(gòu)的，當(dāng)任務(wù)調(diào)度至不同虛擬機(jī)時(shí)得到的任務(wù)運(yùn)行時(shí)間也是不一樣的。類似地，工作流任務(wù)間的數(shù)據(jù)傳輸時(shí)間同樣取決于所調(diào)度的虛擬機(jī)之間的帶寬。因此，對于任務(wù)ti,j而言，無法準(zhǔn)確計(jì)算其最遲開始時(shí)間LSTi,j。本文中，在調(diào)度工作流之前需要利用最小執(zhí)行時(shí)間。定義任務(wù)的最小執(zhí)行時(shí)間為METi,j，數(shù)據(jù)依賴ei,p,j的最小數(shù)據(jù)傳輸時(shí)間為MTTi,p,j，并定義如下：

(6)

(7)

式中：VM代表云平臺中的虛擬機(jī)集合；ETi,j,k代表任務(wù)ti,j在虛擬機(jī)VMu,k上的執(zhí)行時(shí)間；r(ti,j)代表任務(wù)ti,j所選的虛擬機(jī)索引。

結(jié)合以上定義，工作流任務(wù)ti,j的最遲開始時(shí)間可定義為：

(8)

式中：succ(ti,j)代表任務(wù)ti,j的所有直接后繼任務(wù)集合；DTvm代表部署一臺新虛擬機(jī)的延時(shí)。

則任務(wù)ti,j的最遲完成時(shí)間LFTi,j可定義為：

LFTi,j=LSTi,j+METi,j

(9)

3.2 算法詳細(xì)設(shè)計(jì)

結(jié)合前文給出的工作流調(diào)度模型，本節(jié)設(shè)計(jì)一種啟發(fā)式算法，整合三種響應(yīng)調(diào)度策略，以較小的計(jì)算開銷獲取最優(yōu)的調(diào)度方案。引入兩種約束：1) 一旦一臺虛擬機(jī)上的執(zhí)行任務(wù)完成，且其所有前驅(qū)任務(wù)也已完成，則該虛擬機(jī)上的等待任務(wù)立即開始執(zhí)行。2) 當(dāng)滿足以下兩個(gè)條件時(shí)，一臺虛擬機(jī)可被釋放：(1) 為空閑虛擬機(jī)，即該虛擬機(jī)已經(jīng)完成映射至其上的所有任務(wù)以及數(shù)據(jù)傳輸任務(wù)；(2) 該虛擬機(jī)的租用時(shí)間為整數(shù)個(gè)時(shí)間單位。

已有調(diào)度算法當(dāng)有新的工作流到達(dá)時(shí)，所有工作流任務(wù)將被直接調(diào)度至虛擬機(jī)。不同于這種方法，本文算法保留部分等待任務(wù)在工作流任務(wù)隊(duì)列中，僅有就緒任務(wù)被映射至虛擬機(jī)上執(zhí)行。隨著時(shí)間的推移，對于等待任務(wù)的新的調(diào)度方案隨之生成，同時(shí)調(diào)整可用虛擬機(jī)資源應(yīng)對新的任務(wù)調(diào)度。主動(dòng)響應(yīng)工作流調(diào)度算法的主要步驟如算法1所示。

算法1主動(dòng)響應(yīng)工作流調(diào)度算法

1. WTQ←?

2. RTQ←?

3.fornewwiarrivesdo

4.foreachti,j∈wido

5.computeLSTi,jandLFTi,jforti,j

6.ifpred(ti,j)=?

7.ifLSTi,j-ct<△t

8.callAlgorithm2toscheduleti,jtoaVM

9.else

10. RTQ←RTQ∪{ti,j}

11.endif

12.else

13. WTQ←WTQ∪{ti,j}

14.endif

15.endfor

16.sortRTQbytask’sLSTinanincreasingorder

17.endfor

算法1中，WTQ和RTQ分別代表工作流任務(wù)隊(duì)列和就緒任務(wù)隊(duì)列，步驟1-步驟2將兩個(gè)隊(duì)列初始化為空集。一旦新的工作流wi到達(dá)后，算法立即計(jì)算工作流中所有任務(wù)的最遲開始時(shí)間LSTi,j和最遲完成時(shí)間LFTi,j，如步驟5。然后，所有工作流任務(wù)被劃分為就緒任務(wù)和非就緒任務(wù)，如步驟6-步驟14。參數(shù)ct和△t分別代表當(dāng)前時(shí)間和預(yù)設(shè)時(shí)間閾值，而△t可設(shè)置為新的虛擬機(jī)的開始時(shí)間。對于就緒的工作流任務(wù)，若任務(wù)為緊迫類任務(wù)，即其LSTi,j小于△t對應(yīng)的當(dāng)前時(shí)間(步驟7)，則通過步驟8中的緊迫任務(wù)調(diào)度功能算法2將其調(diào)度至虛擬機(jī)上。若任務(wù)為非緊迫任務(wù)，則在步驟10中將其添加至就緒任務(wù)隊(duì)列中。對于在新工作流wi中的所有非就緒任務(wù)，它們將在工作流任務(wù)隊(duì)列WTQ中等待，即步驟13。最后，步驟16對RTQ中的所有就緒任務(wù)按照最遲開始時(shí)間的遞增方式進(jìn)行排序。任務(wù)ti,j在虛擬機(jī)VMu,k上的執(zhí)行代價(jià)ci,j,k為：

ci,j,k=p(u)×(FTi,j,k-rtk)

(10)

式中：rtk代表對于任務(wù)ti,j虛擬機(jī)su,k的就緒時(shí)間。rtk計(jì)算方法如下：1) 如果虛擬機(jī)VMu,k為空閑，即其執(zhí)行和等待任務(wù)均為空，則rtk為當(dāng)前時(shí)間；2) 如果虛擬機(jī)VMu,k為非空閑狀態(tài)，其rtk為虛擬機(jī)VMu,k上最后一個(gè)任務(wù)的完成時(shí)間；3) 如果虛擬機(jī)VMu,k才被租用，則其rtk為租用的開始時(shí)間。

當(dāng)算法調(diào)度緊迫工作流任務(wù)ti,j時(shí)，算法將選擇擁有最小執(zhí)行代價(jià)的虛擬機(jī)，同時(shí)確保其最遲完成時(shí)間。緊迫任務(wù)調(diào)度功能的具體過程如算法2所示。

算法2緊迫任務(wù)調(diào)度策略

1. minCost←∞

2. selectedVM←?

3. for each availableVMu,kdo

4. ifwtk=? do

5. computeFTi,j,kofti,jonVMu,k

6. compute the costci,j,kofti,jonVMu,k

7. ifFTi,j,k≤LFTi,jandci,j,k

8. selectedVM←VMu,k

9. minCost←ci,j,k

10. end if

11. end if

12. end for

13.u←null

14. for each availableVMtypel∈{1,2,…,m} do

15. computeFTi,j,kofti,jon a newVMl,kwith typel

16. computeci,j,kofti,jon a newVMl,kwith typel

17. ifFTi,j≤LFTi,jandci,j,k

18.u←l

19. minCost←ci,j,k

20. end if

21. end for

22. ifu!=? then

23. rent a newVMwith typeuand scheduleti,jto thisVM

24. call Algorithm 3 to search a waiting task for newVM

25. else

26. scheduleti,jto the selectedVMselectedVM

27. end if

該算法接收任務(wù)ti,j作為輸入，執(zhí)行目標(biāo)是為其尋找擁有最小執(zhí)行代價(jià)，且在其最遲完成時(shí)間LFTi,j以內(nèi)完成任務(wù)的虛擬機(jī)。首先，算法將檢測云平臺中等待任務(wù)wtk為空的所有可用虛擬機(jī)，即步驟3-步驟12。擁有最小執(zhí)行代價(jià)且能在LFTi,j之前完成任務(wù)ti,j的虛擬機(jī)得以選擇，即步驟7-步驟10。然后，所有可用虛擬機(jī)類型被檢測(步驟13-步驟21)，以尋找一種虛擬機(jī)類型，使得該類型的新的虛擬機(jī)能夠產(chǎn)生更低的執(zhí)行代價(jià)，且能夠滿足任務(wù)的最遲完成時(shí)間，即步驟17-步驟20。之后，如果所選虛擬機(jī)類型為空(步驟22)，則表明租用所選類型的新的虛擬機(jī)可以產(chǎn)生最小執(zhí)行代價(jià)，新的虛擬機(jī)將被租用以執(zhí)行該緊迫任務(wù)，即步驟23。最后，第三種響應(yīng)調(diào)度策略將尋找等待任務(wù)，即步驟24中調(diào)用算法3。如果所選虛擬機(jī)類型為空，則緊迫任務(wù)將被調(diào)度至相應(yīng)可用虛擬機(jī)上執(zhí)行，即步驟26。

當(dāng)一個(gè)任務(wù)在虛擬機(jī)上完成或一個(gè)新的虛擬機(jī)被租用時(shí)，算法中的第三種響應(yīng)調(diào)度策略將被觸發(fā)，其過程如算法3所示。

算法3搜索新虛擬機(jī)的等待任務(wù)

1. for eachti,s∈succ(ti,j) do

2. ifti,sis ready then

3.ti,s→RTQ

4. end if

5. end for

6. sort all tasks inRTQbyLSTin a non-descending order

7.ti,j←get the task at the head inRTQ

8. whileti,j!=? do

9. computeFTi,jofti,jonVMu,k

10. ifFTi,j≤LFTi,jthen

11. scheduleti,jtoVMu,k

12. break

13. else

14.ti,j←get the next task inRTQ

15. end if

16. end while

當(dāng)一個(gè)任務(wù)完成時(shí)，根據(jù)算法1，其后繼任務(wù)可能變?yōu)榫途w狀態(tài)。令ti,j為虛擬機(jī)VMu,k剛剛完成的任務(wù)。如算法3所示，第三種響應(yīng)策略首先尋找所有剛剛變?yōu)榫途w狀態(tài)的任務(wù)，然后將這些就緒任務(wù)添加至就緒任務(wù)隊(duì)列RTQ中，即步驟1-步驟5。步驟6對RTQ中的所有任務(wù)按照其最遲開始時(shí)間進(jìn)行非降序排列。步驟7獲取隊(duì)列RTQ中隊(duì)首的任務(wù)。步驟9計(jì)算該任務(wù)在虛擬機(jī)VMu,k上的完成時(shí)間。步驟10比較該時(shí)間與任務(wù)的最遲完成時(shí)間的大小關(guān)系，若滿足小于，則進(jìn)行任務(wù)調(diào)度。需要注意的是，若策略被算法2調(diào)用以為虛擬機(jī)尋找新的等待任務(wù)(算法2中的步驟24)，則此時(shí)步驟1-步驟6將被拋棄不予執(zhí)行。擁有較小的最近開始時(shí)間LSTi,j的任務(wù)將被優(yōu)先考慮為確保為最遲完成時(shí)間而尋找調(diào)度虛擬機(jī)的任務(wù)，即步驟7-步驟16。

4 性能評測

在工作流仿真平臺WorkFlowSim[27]下進(jìn)行仿真實(shí)驗(yàn)對算法性能進(jìn)行評測。選擇五種工作流調(diào)度算法進(jìn)行性能比較，包括：WSMT算法[26]，MER算法[28]，OMWSA算法[29]，IC-PCPD2算法[13]和HEFT算法[9]。WSMT算法是一種在線調(diào)度算法，當(dāng)有新工作流到達(dá)時(shí)，該算法首先按計(jì)算資源的非升序?qū)μ摂M機(jī)進(jìn)行排列；然后，為了降低任務(wù)執(zhí)行代價(jià)，算法將工作流任務(wù)插入虛擬機(jī)的時(shí)間槽。若無法執(zhí)行以上步驟，則再應(yīng)用最小完成時(shí)間策略進(jìn)行調(diào)度。MER算法首先利用最早完成時(shí)間策略生成工作流任務(wù)的基準(zhǔn)調(diào)度方案；然后，通過合并輕型負(fù)載資源上的任務(wù)以填充至其他資源上的空閑時(shí)間槽來進(jìn)一步優(yōu)化調(diào)度方案。OMWSA算法在有新工作流到達(dá)時(shí)，為每個(gè)任務(wù)分配一個(gè)等級，然后根據(jù)等級對任務(wù)進(jìn)行排序。當(dāng)調(diào)度一個(gè)任務(wù)時(shí)，能夠在任務(wù)最遲完成時(shí)間內(nèi)完成的虛擬機(jī)被選擇為目標(biāo)。若無法找到以上步驟的可行解，算法將租用新的具有最小執(zhí)行代價(jià)的虛擬機(jī)，并在其最遲完成時(shí)間內(nèi)完成任務(wù)。IC-PCPD2算法的執(zhí)行分為截止時(shí)間分配和調(diào)度兩個(gè)階段。第一階段分配給每個(gè)任務(wù)一個(gè)子期限，然后將任務(wù)調(diào)度至代價(jià)最小的虛擬機(jī)上，并滿足該子期限。算法評測指標(biāo)上選擇式(4)的總體執(zhí)行代價(jià)和式(5)的資源利用率進(jìn)行性能比較。

4.1 實(shí)驗(yàn)搭建

選擇四種類型的虛擬機(jī)進(jìn)行實(shí)驗(yàn)，每種類型的虛擬機(jī)數(shù)量可以擴(kuò)展，虛擬機(jī)的主要參數(shù)包括使用代價(jià)、CPU內(nèi)核數(shù)、內(nèi)存量和類型因子，具體如表1所示。由于每個(gè)任務(wù)在不同類型的虛擬機(jī)上擁有不同的運(yùn)行時(shí)間，類型因子參數(shù)Type(u)用于描述該不同。若該類型虛擬機(jī)擁有最強(qiáng)的計(jì)算能力，能最小化任務(wù)的執(zhí)行時(shí)間，則類型u的Type(u)等于1。對于虛擬機(jī)類型u，其參數(shù)Type(u)定義為任務(wù)在該類型虛擬機(jī)上的執(zhí)行時(shí)間與任務(wù)的最小執(zhí)行時(shí)間之比。

表1 虛擬機(jī)配置

選取四種經(jīng)典科學(xué)工作流結(jié)構(gòu)Montage、SIPHT、CyberShake和LIGO工作流[5]作為實(shí)時(shí)工作流應(yīng)用進(jìn)行仿真測試。每種工作流設(shè)置不同的規(guī)模：小規(guī)模為30個(gè)任務(wù)組成，中等規(guī)模為100個(gè)任務(wù)組成，大規(guī)模為500個(gè)任務(wù)組成。同時(shí)，為了仿真云平臺下工作流應(yīng)用的動(dòng)態(tài)屬性，假設(shè)工作流的到達(dá)服從λ的泊松分布，1/λ為兩個(gè)連接工作流到達(dá)的平均時(shí)間長度。

考慮到多種可用的虛擬機(jī)類型，工作流任務(wù)在不同類型的虛擬機(jī)上的執(zhí)行時(shí)間是不同的。對于任務(wù)ti,j，其在類型為u的虛擬機(jī)上的執(zhí)行時(shí)間計(jì)算為：

ETi,j,k=METi,j×Type(u)

(11)

式中：k代表虛擬機(jī)的索引；u代表虛擬機(jī)類型的索引。

令基準(zhǔn)調(diào)度方案為將每個(gè)任務(wù)調(diào)度至能力最強(qiáng)的虛擬機(jī)上執(zhí)行得到的方案，此時(shí)虛擬機(jī)間的最大帶寬可用于計(jì)算數(shù)據(jù)傳輸時(shí)間。參數(shù)MF代表該基準(zhǔn)方案下工作流的執(zhí)行跨度。設(shè)置參數(shù)β用于控制工作流的截止時(shí)間的縮放范圍，表示截止時(shí)間因子，工作流wi的截止時(shí)間設(shè)置為：

Di=ai+β×MF

(12)

實(shí)驗(yàn)中將分析截止時(shí)間因子β、工作流到達(dá)率λ和工作流數(shù)量對性能的影響。分析一個(gè)參數(shù)的影響時(shí)，另兩個(gè)參數(shù)固定。具體如表2所示。

表2 參數(shù)配置

4.2 結(jié)果對比

圖2是期限因子β對性能的影響。圖2(a)顯示，隨著β的增加，六種算法的總體執(zhí)行代價(jià)有輕微下降的趨勢，原因是處于長截止時(shí)間可以使得工作流的時(shí)效需求更加寬松，使得更多的并行任務(wù)可以調(diào)度至同一虛擬機(jī)上執(zhí)行，從而減少虛擬機(jī)使用量。此外，更多低代價(jià)的虛擬機(jī)可以滿足截止時(shí)間約束需求，也進(jìn)一步降低了執(zhí)行代價(jià)。本文算法相比WSMT、MER、OMWSA、IC-PCPD2和HEFT分別降低了8.1%、10.5%、16.8%、17.9%和24.1%的代價(jià)。原因是：首先，本文算法僅在任務(wù)就緒時(shí)才調(diào)度至虛擬機(jī)上，大量壓縮上虛擬機(jī)的等待時(shí)間；其次，由算法1可知，當(dāng)虛擬機(jī)執(zhí)行其他任務(wù)時(shí)，虛擬機(jī)上的等待任務(wù)可以接收其前驅(qū)任務(wù)的數(shù)據(jù)，這樣可以使等待任務(wù)直接開始執(zhí)行而進(jìn)一步降低虛擬機(jī)的空閑時(shí)槽和租用時(shí)間，也有助于降低執(zhí)行代價(jià)。圖2(b)顯示，資源利用率在β增加時(shí)具有明顯上升的趨勢，原因是越大的β值則有越長的截止時(shí)間，這有助于在相同虛擬機(jī)資源上執(zhí)行并行任務(wù)，盡可能避免虛擬機(jī)空閑時(shí)間。本文算法相比WSMT、MER、OMWSA、IC-PCPD2和HEFT分別提高了7.3百分點(diǎn)、14.1百分點(diǎn)、19.1百分點(diǎn)、30百分點(diǎn)和35.7百分點(diǎn)的資源利用率。原因在于，本文算法在調(diào)度就緒任務(wù)時(shí)不存在數(shù)據(jù)依賴，這些任務(wù)可以混合方式分配至虛擬機(jī)上執(zhí)行，因此壓縮了虛擬機(jī)的空閑時(shí)間。而其他五種算法在有新的工作流到達(dá)時(shí)即調(diào)度至虛擬機(jī)。

(a) 對執(zhí)行代價(jià)的影響

圖3是工作流到達(dá)率對性能的影響。圖3(a)顯示，本文算法和WSMT算法的總體執(zhí)行代價(jià)隨著到達(dá)率λ的增加而輕微下降，其他四種算法基本保持不變。工作流越高的到達(dá)率表明越多的任務(wù)在工作流任務(wù)隊(duì)列中等待，尤其在就緒任務(wù)隊(duì)列中會更多等待。當(dāng)就緒任務(wù)增多時(shí)，對于虛擬機(jī)而言尋找等待任務(wù)更加容易，虛擬機(jī)的空閑時(shí)間也將進(jìn)一步降低。因此，本文算法在增加到達(dá)率時(shí)代價(jià)更小。MER、IC-PCPD2和HEFT三種算法涉及單一工作流的調(diào)度，是輪流調(diào)度方式，并無先前工作流調(diào)度帶來的空閑時(shí)槽問題。因此，基本維持不變的代價(jià)。WSMT將任務(wù)插入虛擬機(jī)的時(shí)槽中，高到達(dá)率也有利于增加任務(wù)插入的成功率。圖3(b)顯示，到達(dá)率從0.01增加至0.1，本文算法的資源利用率從78%增加至87%，而MER、IC-PCPD2和HEFT則僅有66%、53%和49%左右，原因同上。

(a) 對執(zhí)行代價(jià)的影響

圖4是工作流數(shù)量對性能的影響。圖4(a)顯示，六種算法的執(zhí)行代價(jià)隨工作流數(shù)量呈線性遞增，原因是越多的工作流帶來越多虛擬機(jī)上越長的等待時(shí)間，進(jìn)而影響到越高的執(zhí)行代價(jià)。本文算法的代價(jià)要小于WSMT、MER、OMWSA、IC-PCPD2和HEFT算法約8.6%、9.3%、14.3%、20.2%和28.4%。圖4(b)顯示，本文算法、WSMT、MER、OMWSA、IC-PCPD2和HEFT算法的資源利用率分別穩(wěn)定在78.4%、72.2%、66.1%、62.9%、53.5%和49.8%，與工作流到達(dá)量無關(guān)。這些結(jié)果充分地展示出本文算法在改善資源利用率和降低執(zhí)行代價(jià)方面具有預(yù)期的優(yōu)勢。

(a) 對執(zhí)行代價(jià)的影響

5 結(jié) 語

云平臺下的工作流調(diào)度問題必須同步地注重資源提供方的資源利用率提升和資源使用方進(jìn)行任務(wù)調(diào)度的代價(jià)優(yōu)化問題。為了改善云平臺下多工作流的執(zhí)行代價(jià)和資源利用率，提出一種代價(jià)有效的工作流調(diào)度算法。該算法可以充分利用虛擬機(jī)資源的空閑時(shí)槽，以混合形式調(diào)度來自不同工作流的任務(wù)，在確保截止期限約束的同時(shí)，降低任務(wù)執(zhí)行代價(jià)，并提高資源利用率。仿真實(shí)驗(yàn)結(jié)果表明，與其他幾種工作流調(diào)度算法相比，本文的調(diào)度方法可以達(dá)到更好的預(yù)期效果。