何 芳 何小東

1(湖南財(cái)經(jīng)工業(yè)職業(yè)技術(shù)學(xué)院電子信息系 湖南 衡陽(yáng) 421002) 2(中南林業(yè)科技大學(xué)計(jì)算機(jī)與信息工程學(xué)院 湖南 長(zhǎng)沙 410004)

0 引 言

云計(jì)算是分布式計(jì)算的新模式體現(xiàn)，云提供方可以向消費(fèi)者以即付即用模式按需分發(fā)服務(wù)，如應(yīng)用、平臺(tái)和計(jì)算資源等服務(wù)[1]。從消費(fèi)者角度看，云模型是代價(jià)有效模型，由于消費(fèi)者僅需按其實(shí)際使用云資源支付代價(jià)，且其服務(wù)是可擴(kuò)展的，消費(fèi)者對(duì)于資源的租用是不受限制的。這種特征使云計(jì)算在諸多領(lǐng)域得到了廣泛應(yīng)用[2-3]。這類應(yīng)用通常具有相互關(guān)聯(lián)的計(jì)算和數(shù)據(jù)傳輸類任務(wù)，由于任務(wù)間的依賴約束，任務(wù)間的大量空閑時(shí)槽將被虛擬機(jī)資源所浪費(fèi)，導(dǎo)致虛擬機(jī)資源整體利用率不高[4]。此外，云平臺(tái)較低的資源利用率也會(huì)浪費(fèi)大量代價(jià)，資源利用率的提升也是代價(jià)有效的整體調(diào)度手段。

有效的工作流任務(wù)調(diào)度算法是解決以上云平臺(tái)問(wèn)題的有效方法。然而，已有方法基本都是以準(zhǔn)確的任務(wù)執(zhí)行時(shí)間和任務(wù)間的通信時(shí)間信息為前提條件。而在實(shí)際的云環(huán)境中，任務(wù)執(zhí)行時(shí)間通常無(wú)法進(jìn)行準(zhǔn)確可靠估計(jì)，僅在任務(wù)完成后，任務(wù)的準(zhǔn)確執(zhí)行時(shí)間值才是可用的，主要原因在于：(1) 工作流任務(wù)通常在不同輸入下包含條件式指令，即特定應(yīng)用中的任務(wù)通常包含多種選擇和條件語(yǔ)句，其程序分支和循環(huán)不盡相同，使得任務(wù)的計(jì)算時(shí)間在不同的數(shù)據(jù)輸入下體現(xiàn)出極大的不同；(2) 云平臺(tái)中虛擬機(jī)的性能隨時(shí)間發(fā)生變化。以Xen和VMware等虛擬機(jī)技術(shù)為例，其多個(gè)虛擬機(jī)可以同步地分享相同的物理主機(jī)硬件資源，如CPU、I/O和網(wǎng)絡(luò)資源等。這種資源分享模式可能導(dǎo)致虛擬機(jī)的性能遭遇到虛擬機(jī)間資源干擾的影響而產(chǎn)生諸多的不確定性[5]。

由于云平臺(tái)的動(dòng)態(tài)性和不確定性，如可變的任務(wù)執(zhí)行時(shí)間、可變的虛擬機(jī)性能以及動(dòng)態(tài)的工作流的到達(dá)，均可能導(dǎo)致預(yù)定的調(diào)度方案無(wú)法有效地運(yùn)行于實(shí)際環(huán)境中。已有的工作流調(diào)度算法均忽略了這些動(dòng)態(tài)不確定性因素，為了解決這種不確定性，提高虛擬機(jī)資源利用率和降低執(zhí)行代價(jià)，本文將設(shè)計(jì)一種基于不確定性環(huán)境的云工作流調(diào)度算法，并對(duì)其有效性和可行性做出實(shí)驗(yàn)驗(yàn)證。

1 相關(guān)研究

已有的工作流調(diào)度算法可以劃分為表調(diào)度、聚類調(diào)度和元啟發(fā)式調(diào)度。文獻(xiàn)[6]設(shè)計(jì)了一種基于表調(diào)度的工作流調(diào)度算法MO-HEFT，可以均衡調(diào)度跨度與能耗。文獻(xiàn)[7]設(shè)計(jì)了兩階段調(diào)度方案，先生成確保執(zhí)行跨度最小的調(diào)度方案，然后進(jìn)一步最小化資源浪費(fèi)率得到更優(yōu)的調(diào)度方案。文獻(xiàn)[8]提出了一種基于局部關(guān)鍵路徑PCP的工作流調(diào)度算法，在確保工作流截止時(shí)間約束的同時(shí)最小化工作流執(zhí)行代價(jià)。文獻(xiàn)[9]在以上工作的基礎(chǔ)上，設(shè)計(jì)了IC-PCP工作流調(diào)度算法。另外，元啟發(fā)式方法也是求解工作流調(diào)度問(wèn)題的有效方法。文獻(xiàn)[10]設(shè)計(jì)了基于遺傳算法的工作流調(diào)度算法，利用賦予任務(wù)優(yōu)先級(jí)的方式，啟發(fā)式地將每個(gè)任務(wù)映射至處理器上執(zhí)行。文獻(xiàn)[11]提出了進(jìn)化多目標(biāo)優(yōu)化算法求解云工作流調(diào)度問(wèn)題。然而，以上方法均是針對(duì)單一工作流的調(diào)度環(huán)境，并且忽略了云平臺(tái)中任務(wù)執(zhí)行時(shí)間的不確定性和工作流應(yīng)用的動(dòng)態(tài)特征。

針對(duì)隨機(jī)計(jì)算環(huán)境下的工作流調(diào)度問(wèn)題，文獻(xiàn)[12]通過(guò)任務(wù)復(fù)制的方法減輕工作流調(diào)度時(shí)資源性能變化對(duì)于工作流截止時(shí)間的影響。文獻(xiàn)[13]設(shè)計(jì)了基于隨機(jī)啟發(fā)式方法的工作流調(diào)度算法最小化工作流執(zhí)行跨度。文獻(xiàn)[14]基于蒙特卡羅方法處理工作流任務(wù)執(zhí)行時(shí)間的不確定性。文獻(xiàn)[15]則側(cè)重于虛擬機(jī)的性能變化，設(shè)計(jì)了基于粒子群優(yōu)化的工作流調(diào)度算法，可以在確保截止時(shí)間條件的同時(shí)最小化全局工作流執(zhí)行代價(jià)。然而，以上算法也是相對(duì)于單一工作流調(diào)度環(huán)境設(shè)計(jì)的調(diào)度算法，不適用于動(dòng)態(tài)的云計(jì)算平臺(tái)，也無(wú)法有效處理多工作流的提交環(huán)境。

2 問(wèn)題描述

2.1 云虛擬機(jī)模型

云計(jì)算可提供多種類型的虛擬機(jī)服務(wù)，定義為：V={v1,v2,…,vm}，每種虛擬機(jī)類型vi均具有特定性能配置和使用代價(jià)，i∈{1,2,…,m}。不同虛擬機(jī)類型配置擁有不同的CPU性能、內(nèi)存、存儲(chǔ)和網(wǎng)絡(luò)帶寬等性能。令P(vi)代表虛擬機(jī)vi的使用代價(jià)，以單位時(shí)間收費(fèi)。不滿單位時(shí)間的虛擬機(jī)租用依然按一個(gè)時(shí)間單位收費(fèi)。令VMk,vi代表虛擬機(jī)類型vi的第k個(gè)虛擬機(jī)，令WBkh代表虛擬機(jī)VMk,vi與虛擬機(jī)VMh,vj間的網(wǎng)絡(luò)帶寬，并忽略網(wǎng)絡(luò)通信之間可能產(chǎn)生的網(wǎng)絡(luò)擁塞，以簡(jiǎn)化任務(wù)調(diào)度模型。

2.2 工作流任務(wù)模型

云平臺(tái)下的工作流應(yīng)用可被用戶連續(xù)提交執(zhí)行需求，將這類工作流應(yīng)用定義為：W={w1,w2,…,wm}。某一特定工作流應(yīng)用wi∈W可定義為wi={ATi,Di,Gi}，ATi為工作流的到達(dá)時(shí)間，Di為工作流完成的截止時(shí)間，Gi為工作流的結(jié)構(gòu)模型。工作流wi的結(jié)構(gòu)Gi可建立為無(wú)向無(wú)環(huán)圖DAG模型，表示為Gi=(Ti,Ei)，Ti={t1,i,t2,i,…,ti,|Ti|}代表有向圖中的頂點(diǎn)集合，表示任務(wù)節(jié)點(diǎn)，ti,j代表工作流wi中的任務(wù)j，Ei?Ti×Ti代表任務(wù)節(jié)點(diǎn)間的有向邊集合。有向邊eipj∈Ei若存在于有向圖中，即表明任務(wù)tip與任務(wù)tij之間存在依賴約束關(guān)系，而任務(wù)tip可稱為任務(wù)tij的直接后繼任務(wù)。有向邊eipj的權(quán)重值w(eipj)代表任務(wù)tip與任務(wù)tij之間傳輸數(shù)據(jù)量。由于有向圖中的某個(gè)任務(wù)可能存在多個(gè)前驅(qū)任務(wù)或后繼任務(wù)，令pred(tij)表示任務(wù)tij的前驅(qū)任務(wù)集合，succ(tij)表示任務(wù)tij的后繼任務(wù)集合。對(duì)于不確定性環(huán)境而言，由于云虛擬機(jī)資源性能的變化以及系統(tǒng)負(fù)載的不確定性，任務(wù)的準(zhǔn)確執(zhí)行時(shí)間是無(wú)法提前預(yù)知的，因此任務(wù)執(zhí)行時(shí)間可理解為一個(gè)隨機(jī)變量，并具有獨(dú)立性，服從正態(tài)分布。

2.3 調(diào)度模型

具有不確定性的云平臺(tái)中的工作流調(diào)度模型如圖1所示。平臺(tái)由用戶層、調(diào)度層和資源層三個(gè)部分構(gòu)成。云調(diào)度平臺(tái)中，用戶負(fù)責(zé)向資源提供方發(fā)送工作流應(yīng)用執(zhí)行需求，調(diào)度層負(fù)責(zé)依據(jù)制定的調(diào)度策略，并根據(jù)確定的目標(biāo)函數(shù)和資源性能狀況，生成每個(gè)工作流任務(wù)與虛擬機(jī)資源間的映射關(guān)系，資源層由大規(guī)模的異構(gòu)虛擬機(jī)資源構(gòu)成，而這些虛擬機(jī)的性能可以動(dòng)態(tài)的縮放以滿足不同需求的用戶任務(wù)。

圖1 調(diào)度模型

調(diào)度層主要由工作流任務(wù)集模塊、調(diào)度分析模塊、資源調(diào)節(jié)控制模塊及任務(wù)分配控制模塊組成。工作流任務(wù)集模塊負(fù)責(zé)接收等待的工作流任務(wù)，調(diào)度分析模塊負(fù)責(zé)生成計(jì)算資源的擴(kuò)展性能和等待任務(wù)與虛擬機(jī)資源間的映射關(guān)系，計(jì)算資源的擴(kuò)展調(diào)節(jié)包括何時(shí)添加或刪除不同類型虛擬機(jī)資源的數(shù)量，并由資源調(diào)節(jié)控制模塊對(duì)其執(zhí)行。任務(wù)分配控制模塊負(fù)責(zé)動(dòng)態(tài)地根據(jù)任務(wù)與虛擬機(jī)間的映射關(guān)系將等待的工作流任務(wù)分配至對(duì)應(yīng)的虛擬機(jī)上執(zhí)行。該調(diào)度模型的主要特征是多數(shù)的等待任務(wù)均會(huì)在工作流任務(wù)集模塊中處于等待狀態(tài)，而不是直接處于虛擬機(jī)的等待隊(duì)列中，而僅有一個(gè)就緒任務(wù)被直接映射至虛擬機(jī)上，即每臺(tái)虛擬機(jī)僅允許一個(gè)任務(wù)等待。

2.4 最優(yōu)化模型

定義變量xi,j,k用于表示任務(wù)ti,j與虛擬機(jī)VMk,vh間的映射關(guān)系，并滿足以下條件：

(1)

令r(ti,j)表示任務(wù)ti,j映射的虛擬機(jī)的序號(hào)。由于工作流任務(wù)的執(zhí)行時(shí)間是隨機(jī)變量，利用其α分位數(shù)表示執(zhí)行時(shí)間的近似值。令ETα,ijk表示任務(wù)tij在虛擬機(jī)VMk,vh上執(zhí)行時(shí)間的α分位數(shù)。令PSTij,k表示任務(wù)tij在虛擬機(jī)VMk,vh上的估計(jì)開(kāi)始時(shí)間，PFTij,k表示任務(wù)tij在虛擬機(jī)VMk,vh上的估計(jì)完成時(shí)間。估計(jì)開(kāi)始時(shí)間計(jì)算方式如下：

(2)

式中：PFTlh,k表示虛擬機(jī)VMk,vh上最后一個(gè)任務(wù)tlh的估計(jì)完成時(shí)間；r(tip)表示任務(wù)tip調(diào)度的虛擬機(jī)的序號(hào)；TTipj表示任務(wù)間的有向邊eipj上的數(shù)據(jù)傳輸時(shí)間。

工作流wi的所有任務(wù)調(diào)度后，其估計(jì)完成時(shí)間可定義為：

(3)

任務(wù)完成后，其實(shí)際開(kāi)始時(shí)間、執(zhí)行時(shí)間和完成時(shí)間將是準(zhǔn)確可知的。令RSTijk、RETijk和RFTijk分別表示任務(wù)tij在虛擬機(jī)VMk,vh上的實(shí)際開(kāi)始時(shí)間、實(shí)際執(zhí)行時(shí)間和實(shí)際完成時(shí)間。因此，工作流wi的實(shí)際完成時(shí)間可定義為：

(4)

不確定性的調(diào)度環(huán)境中，工作流wi的實(shí)際完成時(shí)間RFTi決定了任務(wù)的執(zhí)行時(shí)間需求是否可以確保。因此，以下約束條件需要?jiǎng)?wù)必滿足：

(5)

由于工作流應(yīng)用中任務(wù)間存在順序約束，一個(gè)任務(wù)僅能在其所有前驅(qū)任務(wù)完成后才能被執(zhí)行，因此需要滿足以下約束：

RSTijk≥RFTip,r(tip)+TTipj?eipj∈Ei

(6)

結(jié)合以上的兩個(gè)約束條件，工作流集合W調(diào)度的第一個(gè)目標(biāo)是最小化總體執(zhí)行代價(jià)，即：

(7)

式中：|VM|為執(zhí)行工作流集合W的虛擬機(jī)總量；Wk為虛擬機(jī)VMk,vh的工作時(shí)間。

資源利用率最大化是調(diào)度算法的第二個(gè)目標(biāo)，可定義為：

(8)

式中：WTk和TTk分別為工作流集合W執(zhí)行時(shí)虛擬機(jī)VMk,vh的工作時(shí)間和總活躍時(shí)間(包括工作時(shí)間和空閑時(shí)間)。

在不確定性環(huán)境下，另一個(gè)需要優(yōu)化的目標(biāo)是最小化方差代價(jià)函數(shù)，定義為工作流的估計(jì)完成時(shí)間與實(shí)際完成時(shí)間絕對(duì)差的權(quán)重之和的均值，表示為：

(9)

式中：τi為估計(jì)完成時(shí)間與實(shí)際完成時(shí)間的時(shí)間差的邊界代價(jià)。

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

由于工作流任務(wù)的執(zhí)行指令與虛擬機(jī)性能的變化，任務(wù)的準(zhǔn)確執(zhí)行時(shí)間在調(diào)度前通常無(wú)法準(zhǔn)確估算。因此，工作流任務(wù)的執(zhí)行時(shí)間和完成時(shí)間是具有不確定性的。調(diào)度任務(wù)時(shí)，如果執(zhí)行任務(wù)的預(yù)留時(shí)間過(guò)短，任務(wù)的實(shí)際完成時(shí)間將大于其期望完成時(shí)間，進(jìn)而會(huì)導(dǎo)致其他任務(wù)執(zhí)行的延遲，并違背任務(wù)執(zhí)行的截止時(shí)間約束。因此，本文設(shè)計(jì)了一種主動(dòng)式調(diào)度策略用于建立工作流的底線調(diào)度方案，該方案利用了工作流的最差執(zhí)行時(shí)間。本文中，當(dāng)α遠(yuǎn)大于0.5或小于1時(shí)，算法將任務(wù)執(zhí)行時(shí)間的α分位數(shù)考慮為最差執(zhí)行時(shí)間。但是，工作流任務(wù)在多數(shù)情況下的執(zhí)行時(shí)間會(huì)小于最差執(zhí)行時(shí)間。因此主動(dòng)式工作流調(diào)度策略會(huì)浪費(fèi)大量資源性能。為了處理這種影響，任務(wù)執(zhí)行期間，需要設(shè)計(jì)一種基于響應(yīng)式的工作流調(diào)度策略，能夠動(dòng)態(tài)調(diào)度等待任務(wù)以充分利用剩余資源性能。

將以上主動(dòng)式調(diào)度和響應(yīng)式調(diào)度劃分為兩類事件的發(fā)生：一是新的工作流到達(dá)時(shí)進(jìn)行主動(dòng)式調(diào)度，二是當(dāng)虛擬機(jī)完成一個(gè)任務(wù)時(shí)進(jìn)行響應(yīng)式調(diào)度。

3.1 基于任務(wù)執(zhí)行時(shí)間不確定性的任務(wù)分級(jí)

工作流任務(wù)集合中的所有任務(wù)依據(jù)其估計(jì)最遲開(kāi)始時(shí)間PLSTij進(jìn)行分級(jí)，任務(wù)tij的估計(jì)最遲開(kāi)始時(shí)間PLSTij定義為任務(wù)開(kāi)始執(zhí)行后，工作流wi的估計(jì)完成時(shí)間PFTi將大于其截止時(shí)間Di的最遲時(shí)間，定義為：

(10)

式中：succ(tij)為任務(wù)tij的直接后繼任務(wù)集合；METα,ij為任務(wù)tij的執(zhí)行時(shí)間的α分位數(shù)的最小值。

則任務(wù)tij的估計(jì)最遲完成時(shí)間PLFTij可計(jì)算為：

PLFTij=PLSTij+METα,ij

(11)

3.2 調(diào)度算法設(shè)計(jì)

一個(gè)任務(wù)視為就緒任務(wù)，當(dāng)其不存在任一前驅(qū)任務(wù)，即pred(tij)=null，或其所有前驅(qū)任務(wù)已被映射至虛擬機(jī)上，且至少一個(gè)前驅(qū)任務(wù)已經(jīng)完成。傳統(tǒng)的工作流調(diào)度方法中，一旦新的工作流到達(dá)，其所有任務(wù)被直接調(diào)度至虛擬機(jī)的本地隊(duì)列中。本文的調(diào)度策略不同，將多數(shù)等待任務(wù)放入工作流任務(wù)集合中，僅有一個(gè)就緒任務(wù)被調(diào)度和分配至虛擬機(jī)。在整個(gè)云平臺(tái)的實(shí)際執(zhí)行過(guò)程中，工作流任務(wù)集合中的等待任務(wù)的新的映射方案將連續(xù)生成。算法1為執(zhí)行當(dāng)新的工作流到達(dá)時(shí)的主動(dòng)式工作流調(diào)度策略。

算法1新工作流到達(dá)時(shí)的主動(dòng)式工作流調(diào)度策略

1.taskSet←null

2.foreach new workflowwiarrivesdo

3. 通過(guò)式(11)和式(12)計(jì)算PLSTijandPLFTijfor eachtijinwi

4.readyTasks←get all the ready tasks in workflowwi

5. sortreadyTasksby tasks’ ranks in an increasing order

6.foreach ready tasktijinreadyTasksdo

7. scheduletijby Algorithm 3

8.endfor

9. add all the non-ready tasks inwiinto settaskSet

10.endfor

步驟1首先將工作流任務(wù)集合置為空集。當(dāng)新的工作流wi到達(dá)時(shí)，算法1通過(guò)步驟3計(jì)算工作流中每個(gè)任務(wù)的估計(jì)最遲開(kāi)始時(shí)間和估計(jì)最遲完成時(shí)間。步驟4將工作流中的所有就緒任務(wù)放入就緒任務(wù)集合中，并在步驟5中根據(jù)任務(wù)的分級(jí)值的遞增排序?qū)途w任務(wù)進(jìn)行排列。最后，在步驟6-步驟8中，通過(guò)調(diào)用算法3將這些就緒任務(wù)調(diào)度至虛擬機(jī)上執(zhí)行。步驟9則將新工作流中的所有的非就緒任務(wù)添加至工作流任務(wù)集合中。

由于任務(wù)在一個(gè)虛擬機(jī)上的完成時(shí)間是隨機(jī)的，將一臺(tái)虛擬機(jī)上的一個(gè)任務(wù)的完成事件視為一個(gè)突發(fā)事件。當(dāng)突發(fā)事件發(fā)生時(shí)，如果虛擬機(jī)上存在等待任務(wù)，則第一個(gè)等待任務(wù)立即開(kāi)始執(zhí)行(其所有前驅(qū)任務(wù)已經(jīng)完成)。此外，當(dāng)一個(gè)任務(wù)完成時(shí)，其后繼任務(wù)變?yōu)榫途w任務(wù)，此時(shí)將觸發(fā)算法1對(duì)就緒任務(wù)進(jìn)行主動(dòng)式調(diào)度。算法2執(zhí)行當(dāng)虛擬機(jī)完成一個(gè)任務(wù)時(shí)的響應(yīng)式調(diào)度。

算法2虛擬機(jī)完成一個(gè)任務(wù)時(shí)的響應(yīng)式調(diào)度

1.ifthere exist waiting tasks onVMVMk,vithen

2. start to execute the first waiting task onVMVMk,vi

3.endif

4.readyTasks←null

5.fortis∈succ(tij)do

6.iftasktisis readythen

7. readyTasks←(readyTasks+tis)

8.endif

9.endfor

10.taskSet←(taskSet-readyTasks)

11. sortreadyTasksby their ranksPLSTijin an increasing order

12.foreach readytasktij∈readyTasksdo

13. schedule tasktijby Algorithm 3

14.endfor

在步驟1～步驟3中，當(dāng)虛擬機(jī)VMk,vi完成其執(zhí)行的任務(wù)后，如果其等待任務(wù)隊(duì)列wtkk為非空，則立即開(kāi)始執(zhí)行該隊(duì)列中第一個(gè)等待任務(wù)。然后，選擇處于就緒狀態(tài)的任務(wù)tij的后繼任務(wù)，即步驟4-步驟9。具體地，步驟4首先將就緒任務(wù)隊(duì)列置為空，然后在步驟5-步驟9中遍歷當(dāng)前就緒任務(wù)tij的所有后繼任務(wù)，在步驟6中判斷該后繼任務(wù)是否為就緒狀態(tài)，若為就緒狀態(tài)，則更新當(dāng)前就緒任務(wù)隊(duì)列readyTasks。步驟10將以上就緒任務(wù)從工作流任務(wù)集合taskSet中移除。步驟11中，算法根據(jù)估計(jì)最遲開(kāi)始時(shí)間PLSTij對(duì)就緒任務(wù)進(jìn)行遞增排序并更新就緒任務(wù)隊(duì)列。根據(jù)式(11)定義可知，按照最遲開(kāi)始時(shí)間遞增排序后按序調(diào)度就緒隊(duì)列中的任務(wù)，可以確保工作流任務(wù)間的執(zhí)行順序約束。最后，對(duì)于所有處于就緒任務(wù)集合中的任務(wù)，通過(guò)算法3將就緒任務(wù)調(diào)度至虛擬機(jī)上執(zhí)行，即步驟12-步驟14。

任務(wù)tij在虛擬機(jī)VMk,vi上的估計(jì)代價(jià)為：

Pcij,k=P(VMk,vi)×(PFTij,k-PRTk)

(12)

式中：PRTk代表虛擬機(jī)VMk,vi對(duì)于任務(wù)tij可用的估計(jì)時(shí)間。算法3用于對(duì)處于就緒狀態(tài)的任務(wù)進(jìn)行調(diào)度。

算法3調(diào)度處于就緒狀態(tài)的任務(wù)

1.minCost←∞,targetVM←null

2.foreachVMVMk,vithe systemdo

3.通過(guò)式(3)和式(13)計(jì)算PFTij,kandPcij,kfor tasktijonVMVMk,vi

4.ifPFTij,k≤PLFTijandPcij,k

5.targetVM←VMk,vi,minCost←Pcij,k

6.endif

7.endfor

8.iftargetVM!=nullthen

9.schedule tasktijto thetargetVM

10.else

11.lease a newVMVMk,viwith the minimalPcij,kwhile satisfyingPFTij,k≤PLFTij

12.schedule tasktijtoVMVMk,viafter it has been initiated

13.endif

步驟1對(duì)算法得到的最小執(zhí)行代價(jià)和調(diào)度目標(biāo)虛擬機(jī)進(jìn)行置空初始化。算法利用了兩種方式將一個(gè)就緒任務(wù)調(diào)度至虛擬機(jī)上。方法一對(duì)于能夠在其估計(jì)最遲完成時(shí)間PLFTij以內(nèi)且以最小的估計(jì)代價(jià)Pcij,k完成任務(wù)的初始化的虛擬機(jī)(步驟4-步驟6)，將選擇為完成該就緒任務(wù)的虛擬機(jī)，即步驟2-步驟7所示。如果該方法不能為就緒任務(wù)找到合適的虛擬機(jī)，方法二將租用一個(gè)生成最小估計(jì)代價(jià)Pcij,k，且在其估計(jì)最遲完成時(shí)間PLFTij以內(nèi)完成該任務(wù)的新的虛擬機(jī)進(jìn)行任務(wù)調(diào)度，即步驟10-步驟13。

4 性能評(píng)估

4.1 實(shí)驗(yàn)搭建和參數(shù)配置

利用CloudSim云計(jì)算仿真平臺(tái)實(shí)現(xiàn)云平臺(tái)中工作流任務(wù)調(diào)度問(wèn)題的仿真。為云平臺(tái)配置六種不同類型的虛擬機(jī)，每種類型的虛擬機(jī)配置數(shù)量不受限制。表1給出以上虛擬機(jī)的具體配置，具體包括虛擬機(jī)類型名稱、使用代價(jià)、CPU的內(nèi)核數(shù)量及擴(kuò)展因子，該配置參考了亞馬遜的彈性計(jì)算云EC2的配置參數(shù)，具備很好的代表性。此外，虛擬機(jī)的租用時(shí)間單位為一小時(shí)，虛擬機(jī)之間的網(wǎng)絡(luò)帶寬設(shè)置為1 Gbit/s。

表1 虛擬機(jī)配置參數(shù)

利用四種現(xiàn)實(shí)工作流模型進(jìn)行算法的仿真測(cè)試，包括Montage工作流、SIPHT工作流、CyberShake工作流和LIGO工作流，這些工作流模塊集合中包括多種描述元素，具體參考文獻(xiàn)[16]。設(shè)置三種不同規(guī)模的工作流任務(wù)模型，30個(gè)任務(wù)組成小規(guī)模工作流執(zhí)行模型，50個(gè)任務(wù)組成中等規(guī)模工作流執(zhí)行模型，100個(gè)任務(wù)組成大規(guī)模工作流執(zhí)行模型。另外，為了實(shí)現(xiàn)云平臺(tái)中工作流執(zhí)行的動(dòng)態(tài)特征，工作流模塊在固定的時(shí)間間隔內(nèi)進(jìn)行隨機(jī)選取，并發(fā)送至調(diào)度器上。兩個(gè)連續(xù)工作流的時(shí)間間隔為一個(gè)變量，令其服務(wù)1/λ=100 s的泊松分布。

由于虛擬機(jī)類型不盡相同，導(dǎo)致任務(wù)的基準(zhǔn)執(zhí)行時(shí)間不同類型的虛擬機(jī)上也是不相同的。利用擴(kuò)展因子f描述以上不確定性特征。任務(wù)tij在不同虛擬機(jī)類型上的基準(zhǔn)執(zhí)行時(shí)間計(jì)算為：

BETij,k=BETij×f

(13)

式中：k為虛擬機(jī)的類型序號(hào)，對(duì)應(yīng)于擴(kuò)展因子f的虛擬機(jī)。

將每個(gè)任務(wù)的執(zhí)行時(shí)間建立為正態(tài)分布，即ETij,k=N(μ,δ)，任務(wù)基準(zhǔn)執(zhí)行時(shí)間均值為μ，相對(duì)任務(wù)執(zhí)行時(shí)間標(biāo)準(zhǔn)方差為δ：

μ=BETij,k

δ=BETij,k×var

(14)

式中：var為任務(wù)執(zhí)行時(shí)間的變化。

實(shí)驗(yàn)中，任務(wù)的實(shí)現(xiàn)執(zhí)行時(shí)間為：

RETij,k=r_N(BETij,k,(BETij,k×var)2)

(15)

式中：r_N(μ,δ2)表示隨機(jī)數(shù)生成器，用于生成均值為BETij,k和標(biāo)準(zhǔn)方差為(BETij,k×var)的正態(tài)分布值。

為了給每個(gè)工作流分配截止時(shí)間，定義最快調(diào)度方案為將每個(gè)工作流任務(wù)調(diào)度至最快的虛擬機(jī)(即表1中的M2.xlarge虛擬機(jī))上執(zhí)行得到的調(diào)度結(jié)果，參數(shù)MF定義為一個(gè)工作流的最快調(diào)度方案下得到的執(zhí)行跨度。令u表示截止時(shí)間因子，將工作流的截止時(shí)間設(shè)置為：

Di=ATi+u×MF

(16)

選擇IC-PCP工作流調(diào)度算法[9]和WSTR工作流調(diào)度算法作為對(duì)比算法[12]，保留兩種算法的調(diào)度思路，并在仿真實(shí)驗(yàn)環(huán)境中將其擴(kuò)展為可調(diào)度多工作流的調(diào)度模型。

4.2 結(jié)論分析與比較

首先分析不確定性的任務(wù)執(zhí)行時(shí)間對(duì)性能的影響，改變?nèi)蝿?wù)執(zhí)行時(shí)間變化參數(shù)var的值，將其設(shè)置在0.1至0.5之間，并以步長(zhǎng)0.1進(jìn)行遞增。圖2為該參數(shù)對(duì)于工作流執(zhí)行代價(jià)、資源利用率和方差代價(jià)的影響。圖2(a)顯示，隨機(jī)該參數(shù)的增加，工作流執(zhí)行代價(jià)在不同算法間以不同的遞增速率增加，兩種對(duì)比算法的增加趨勢(shì)比本文算法更加明顯。這是由于兩種對(duì)比算法均未采用任何響應(yīng)式調(diào)度策略控制任務(wù)執(zhí)行時(shí)間的不確定性和云平臺(tái)中資源性能的動(dòng)態(tài)性，而僅是以基準(zhǔn)調(diào)度方案進(jìn)行任務(wù)執(zhí)行。本文算法相較兩種對(duì)比算法IC-PCP和WSTR算法分別降低了65%和48%左右的執(zhí)行代價(jià)，這表明本文算法可以降低云提供方的代價(jià)，且不受任務(wù)時(shí)間可變和不確定性的影響。圖2(b)表明本文算法得到的資源利用率始終處于較高的水平，遠(yuǎn)遠(yuǎn)高于另外兩種對(duì)比算法。原因在于：(1) 當(dāng)?shù)却蝿?wù)處于就緒時(shí)，本文算法動(dòng)態(tài)將就緒任務(wù)調(diào)度至虛擬機(jī)上，使得每個(gè)虛擬機(jī)上的空閑時(shí)槽被大大壓縮。(2) 兩種對(duì)比算法中執(zhí)行時(shí)間變量的增加導(dǎo)致任務(wù)的估計(jì)完成時(shí)間與實(shí)際完成時(shí)間之差變得更大，這大大地浪費(fèi)了調(diào)度時(shí)間，同時(shí)導(dǎo)致了更低的虛擬機(jī)資源利用率。圖2(c)表明，隨著執(zhí)行時(shí)間參數(shù)的增加，三種算法的方差代價(jià)均有所增加，這是由于該參數(shù)的增加使得估計(jì)完成時(shí)間和實(shí)際完成時(shí)間之差變大。此外，本文算法的方差代價(jià)要低于對(duì)比算法，由于它們并沒(méi)有控制等待任務(wù)的不確定性。

(a) 任務(wù)執(zhí)行時(shí)間變化對(duì)執(zhí)行代價(jià)的影響

(b) 任務(wù)執(zhí)行時(shí)間變化對(duì)資源利用率的影響

(c) 任務(wù)執(zhí)行時(shí)間變化對(duì)方差代價(jià)的影響圖2 任務(wù)執(zhí)行時(shí)間變化對(duì)性能的影響

圖3分析了截止時(shí)間因子的設(shè)置對(duì)于算法性能的影響，不同的截止時(shí)間因子可以生成不同大小的工作流截止時(shí)間。由圖3(a)可以看到，三種算法的執(zhí)行代價(jià)會(huì)隨著截止時(shí)間因子的增加(即工作流的截止時(shí)間變得更加寬松)而輕微下降，這表明截止時(shí)間延長(zhǎng)時(shí)，可以使工作流在時(shí)間約束內(nèi)更遲完成。相應(yīng)地，更多的工作流中的并行任務(wù)(任務(wù)間不具有執(zhí)行順序依賴關(guān)系)可以執(zhí)行在相同的虛擬機(jī)上，使得更少量的虛擬機(jī)被利用，資源利用率得以提高。此外，本文算法的執(zhí)行代價(jià)對(duì)兩種對(duì)比算法的代價(jià)平均低44%和76%，該結(jié)果表明融合了主動(dòng)式調(diào)度策略和響應(yīng)式調(diào)度策略的本文算法在降低執(zhí)行代價(jià)方面是有效可行的。由圖3(b)可以看到，當(dāng)截止時(shí)間因增加時(shí)，三種算法的資源利用率會(huì)相應(yīng)增加，這是由于工作流執(zhí)行的截止時(shí)間變長(zhǎng)時(shí)，其執(zhí)行跨度在不違背截止時(shí)間約束的同時(shí)也會(huì)變長(zhǎng)，進(jìn)而使得虛擬機(jī)資源的空閑時(shí)槽大大壓縮和減少。本文算法得到的資源利用率平均來(lái)說(shuō)要分別高于對(duì)比算法30%和40%，本文算法得到極高的資源利用率是由于算法僅在任務(wù)變?yōu)榫途w狀態(tài)時(shí)就直接動(dòng)態(tài)地調(diào)度至虛擬機(jī)上執(zhí)行，使得虛擬機(jī)的空閑時(shí)槽被大大減少。圖3(c)的結(jié)果表明，隨著截止時(shí)間因子的增加，本文算法和WSTR算法的方差代價(jià)輕微增加，而IC-PCP算法則基本保持不變。此外，本文算法的方差代價(jià)平均來(lái)說(shuō)低于兩種對(duì)比算法，原因在于兩種對(duì)比算法在一旦有新的工作流到達(dá)時(shí)就立即調(diào)度其所有任務(wù)至虛擬機(jī)上，導(dǎo)致任務(wù)執(zhí)行時(shí)間不確定性對(duì)性能造成了較大的影響。圖3結(jié)果表明本文算法在處理調(diào)度不確定性時(shí)具有很好的控制功能。

(a) 截止時(shí)間因子對(duì)執(zhí)行代價(jià)的影響

(b) 截止時(shí)間因子對(duì)資源利用率的影響

(c) 截止時(shí)間因子對(duì)方差代價(jià)的影響圖3 截止時(shí)間因子對(duì)性能的影響

實(shí)驗(yàn)最后觀察執(zhí)行工作流的規(guī)模對(duì)于系統(tǒng)性能的影響，如圖4所示。由圖4(a)可見(jiàn)，三種算法的總體執(zhí)行代價(jià)會(huì)隨著工作流執(zhí)行數(shù)量的增加而得到增進(jìn)。很明顯，執(zhí)行的工作流數(shù)量越多，越需要更多的虛擬機(jī)工作時(shí)間，導(dǎo)致了更高的執(zhí)行代價(jià)。而本文算法的執(zhí)行代價(jià)依然比兩種對(duì)比算法分別低54%和71%。圖4(b)表明，工作流執(zhí)行數(shù)量增加時(shí)，三種算法的資源利用率基本會(huì)穩(wěn)定在77%、50%和45%左右。該結(jié)果表明工作流執(zhí)行數(shù)量的增加對(duì)于云平臺(tái)下的資源利用率的影響比較有限。圖4(c)的結(jié)果表明，三種算法的方差代價(jià)分別為0.055、0.15和0.3，這表明工作流執(zhí)行數(shù)量的增加對(duì)基準(zhǔn)調(diào)度的影響甚少。本文算法得到較低的方差代價(jià)是由于能夠通過(guò)主動(dòng)式和響應(yīng)式調(diào)度策略將任務(wù)執(zhí)行時(shí)間不確定性降低至最小，從而得到與實(shí)際調(diào)度情形更加接近的工作流調(diào)度解。

(a) 執(zhí)行工作流的數(shù)量對(duì)執(zhí)行代價(jià)的影響

(b) 執(zhí)行工作流的數(shù)量對(duì)資源利用率的影響

(c) 執(zhí)行工作流的數(shù)量對(duì)方差代價(jià)的影響圖4 執(zhí)行工作流的數(shù)量對(duì)性能的影響

5 結(jié) 語(yǔ)

為了改善云平臺(tái)下多工作流的執(zhí)行代價(jià)和資源利用率，提出一種不確定性感知的工作流可靠調(diào)度算法。該算法利用主動(dòng)式和響應(yīng)式的調(diào)度策略，可以實(shí)時(shí)觸發(fā)新工作流的調(diào)度請(qǐng)求和響應(yīng)虛擬機(jī)完成任務(wù)后的任務(wù)調(diào)度請(qǐng)求，并滿足多工作流的執(zhí)行環(huán)境。在現(xiàn)實(shí)工作流模型的測(cè)試表明新的工作流調(diào)度算法可以在確保滿足截止時(shí)間約束的同時(shí)，極大降低工作流執(zhí)行代價(jià)和提高虛擬機(jī)資源利用率，并將不確定性影響降至最低。