任務執行時間不確定性條件下實時云工作流的可靠調度研究

何 芳 何小東

1(湖南財經工業職業技術學院電子信息系 湖南 衡陽 421002) 2(中南林業科技大學計算機與信息工程學院 湖南 長沙 410004)

0 引 言

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

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

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

1 相關研究

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

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

2 問題描述

2.1 云虛擬機模型

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

2.2 工作流任務模型

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

2.3 調度模型

具有不確定性的云平臺中的工作流調度模型如圖1所示。平臺由用戶層、調度層和資源層三個部分構成。云調度平臺中，用戶負責向資源提供方發送工作流應用執行需求，調度層負責依據制定的調度策略，并根據確定的目標函數和資源性能狀況，生成每個工作流任務與虛擬機資源間的映射關系，資源層由大規模的異構虛擬機資源構成，而這些虛擬機的性能可以動態的縮放以滿足不同需求的用戶任務。

圖1 調度模型

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

2.4 最優化模型

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

(1)

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

(2)

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

工作流wi的所有任務調度后，其估計完成時間可定義為：

(3)

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

(4)

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

(5)

由于工作流應用中任務間存在順序約束，一個任務僅能在其所有前驅任務完成后才能被執行，因此需要滿足以下約束：

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

(6)

結合以上的兩個約束條件，工作流集合W調度的第一個目標是最小化總體執行代價，即：

(7)

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

資源利用率最大化是調度算法的第二個目標，可定義為：

(8)

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

在不確定性環境下，另一個需要優化的目標是最小化方差代價函數，定義為工作流的估計完成時間與實際完成時間絕對差的權重之和的均值，表示為：

(9)

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

3 算法設計

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

將以上主動式調度和響應式調度劃分為兩類事件的發生：一是新的工作流到達時進行主動式調度，二是當虛擬機完成一個任務時進行響應式調度。

3.1 基于任務執行時間不確定性的任務分級

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

(10)

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

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

PLFTij=PLSTij+METα,ij

(11)

3.2 調度算法設計

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

算法1新工作流到達時的主動式工作流調度策略

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首先將工作流任務集合置為空集。當新的工作流wi到達時，算法1通過步驟3計算工作流中每個任務的估計最遲開始時間和估計最遲完成時間。步驟4將工作流中的所有就緒任務放入就緒任務集合中，并在步驟5中根據任務的分級值的遞增排序對就緒任務進行排列。最后，在步驟6-步驟8中，通過調用算法3將這些就緒任務調度至虛擬機上執行。步驟9則將新工作流中的所有的非就緒任務添加至工作流任務集合中。

由于任務在一個虛擬機上的完成時間是隨機的，將一臺虛擬機上的一個任務的完成事件視為一個突發事件。當突發事件發生時，如果虛擬機上存在等待任務，則第一個等待任務立即開始執行(其所有前驅任務已經完成)。此外，當一個任務完成時，其后繼任務變為就緒任務，此時將觸發算法1對就緒任務進行主動式調度。算法2執行當虛擬機完成一個任務時的響應式調度。

算法2虛擬機完成一個任務時的響應式調度

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

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

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

(12)

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

算法3調度處于就緒狀態的任務

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

4 性能評估

4.1 實驗搭建和參數配置

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

表1 虛擬機配置參數

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

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

BETij,k=BETij×f

(13)

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

將每個任務的執行時間建立為正態分布，即ETij,k=N(μ,δ)，任務基準執行時間均值為μ，相對任務執行時間標準方差為δ：

μ=BETij,k

δ=BETij,k×var

(14)

式中：var為任務執行時間的變化。

實驗中，任務的實現執行時間為：

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

(15)

式中：r_N(μ,δ2)表示隨機數生成器，用于生成均值為BETij,k和標準方差為(BETij,k×var)的正態分布值。

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

Di=ATi+u×MF

(16)

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

4.2 結論分析與比較

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

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

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

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

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

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

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

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

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

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

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

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

5 結 語

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