王 旖 旎

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

0 引 言

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

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

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

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

工作流應(yīng)用是分布式計算環(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) 為每個工作流任務(wù)分配優(yōu)先級；(2) 基于任務(wù)優(yōu)先級調(diào)度工作流調(diào)度。例如：第一個基于表調(diào)度的工作流調(diào)度算法HEFT[9]，基于任務(wù)升秩值設(shè)置任務(wù)優(yōu)先級之后，再將其調(diào)度至完成時間最小的處理器上執(zhí)行。文獻(xiàn)[10]擴(kuò)展了HEFT算法，以改進(jìn)執(zhí)行跨度和能效為目標(biāo)尋找工作流調(diào)度的Pareto解集合。文獻(xiàn)[11]提出一種隨機等級調(diào)度算法以隨機運行時間調(diào)度工作流任務(wù)。但是，以上方法僅關(guān)注于單一工作流的調(diào)度問題，在滿足截止時間下的云平臺中的多工作流調(diào)度問題上顯得效率較低。

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

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

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

2 問題描述

云平臺下的工作流可建立模型為WS={w1,w2,…,wn}。對于每一個工作流wi∈WS又可以建立為一個三元組模型wi={Gi,ai,Di}，Gi代表工作流wi的任務(wù)結(jié)構(gòu)，ai代表工作流的到達(dá)時間，Di代表工作流完成的截止時間。工作流的結(jié)構(gòu)Gi可以建立模型為有向無循環(huán)圖結(jié)構(gòu)，表示為DAGGi=(Ti,Ei)，其中：Ti={t1,i,t2,i,…,ti,|Ti|}代表有向圖中的頂點集合，表示任務(wù)節(jié)點，ti,j代表工作流wi中的任務(wù)j；|Ti|代表集合Ti中的頂點數(shù)，即任務(wù)數(shù)；Ei?Ti×Ti代表任務(wù)節(jié)點間的有向邊集合。一條有向邊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ù)量的虛擬機VM服務(wù)，令m代表云平臺中可用的虛擬機類型的數(shù)量，u∈{1,2,…,m}代表VM類型的標(biāo)識號，每種虛擬機類型對應(yīng)一個使用代價p(u)，則VMu,k代表類型為u的第k個虛擬機，再令ck,l代表虛擬機su,k與虛擬機su′,h間的通信帶寬。

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

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

(1)

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

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

(2)

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

FTi≤Di?wi∈WS

(3)

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

(4)

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

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

(5)

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

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

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

3.1 調(diào)度模型

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

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

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

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

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

(6)

(7)

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

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

(8)

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

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

LFTi,j=LSTi,j+METi,j

(9)

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

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

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

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

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

(10)

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

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

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

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

4 性能評測

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

4.1 實驗搭建

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

表1 虛擬機配置

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

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

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

(11)

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

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

Di=ai+β×MF

(12)

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

表2 參數(shù)配置

4.2 結(jié)果對比

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

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

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

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

圖4是工作流數(shù)量對性能的影響。圖4(a)顯示，六種算法的執(zhí)行代價隨工作流數(shù)量呈線性遞增，原因是越多的工作流帶來越多虛擬機上越長的等待時間，進(jìn)而影響到越高的執(zhí)行代價。本文算法的代價要小于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í)行代價方面具有預(yù)期的優(yōu)勢。

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

5 結(jié) 語

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