何 芳 何小東

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

0 引 言

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

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

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

1 相關(guān)研究

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

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

2 問題描述

2.1 云虛擬機模型

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

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

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

2.3 調(diào)度模型

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

圖1 調(diào)度模型

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

2.4 最優(yōu)化模型

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

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

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

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

(6)

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

(7)

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

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

(8)

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

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

(9)

式中：τi為估計完成時間與實際完成時間的時間差的邊界代價。

3 算法設(shè)計

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

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

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

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

(10)

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

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

PLFTij=PLSTij+METα,ij

(11)

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

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

算法1新工作流到達時的主動式工作流調(diào)度策略

1.taskSet←null

2.foreach new workflowwiarrivesdo

3. 通過式(11)和式(12)計算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到達時，算法1通過步驟3計算工作流中每個任務(wù)的估計最遲開始時間和估計最遲完成時間。步驟4將工作流中的所有就緒任務(wù)放入就緒任務(wù)集合中，并在步驟5中根據(jù)任務(wù)的分級值的遞增排序?qū)途w任務(wù)進行排列。最后，在步驟6-步驟8中，通過調(diào)用算法3將這些就緒任務(wù)調(diào)度至虛擬機上執(zhí)行。步驟9則將新工作流中的所有的非就緒任務(wù)添加至工作流任務(wù)集合中。

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

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

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

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

(12)

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

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

1.minCost←∞,targetVM←null

2.foreachVMVMk,vithe systemdo

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

4 性能評估

4.1 實驗搭建和參數(shù)配置

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

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

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

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

BETij,k=BETij×f

(13)

式中：k為虛擬機的類型序號，對應(yīng)于擴展因子f的虛擬機。

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

μ=BETij,k

δ=BETij,k×var

(14)

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

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

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

(15)

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

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

Di=ATi+u×MF

(16)

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

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

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

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

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

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

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

(a) 截止時間因子對執(zhí)行代價的影響

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

(c) 截止時間因子對方差代價的影響圖3 截止時間因子對性能的影響

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

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

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

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

5 結(jié) 語

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