云環境中一種多階段式工作流任務調度算法

張 揚 馬 飛

1(廣西工業職業技術學院 廣西 南寧 530003) 2(廣西大學計算機與電子信息學院 廣西 南寧 530004)

0 引 言

通常，云計算環境中的工作流可表示為有向無循環圖DAG的形式[1]。DAG中，節點即為待執行的任務，有向邊即為任務間的次序約束或任務間的通信關系。相互獨立的任務可分配至不同的虛擬機上同步執行，而相互依賴關系的任務則可以分配至同一虛擬機上執行以降低任務間的數據通信延時。調度問題即將DAG中的任務分配至一個虛擬機資源集合，并考慮改善系統的性能[2]。調度問題可以是靜態的，即任務執行前發生調度；也可以是動態的，即任務執行過程中發生調度。多數情況下，以實現調度時間或代價最優為目標的工作流形式的任務調度問題是NP問題。而大多數算法也僅集中于考慮執行時間最小化的任務調度問題，而忽略了云計算環境中的調度代價問題。

本文設計一種基于代價的工作流任務調度算法(簡稱ICTS)。算法由層次排序、確定任務優先級、虛擬機選擇三個階段組成。通過三階段式的任務調度過程，較好地均衡了調度長度和任務執行代價間的平衡問題，并且通過大規模隨機化生成的任務有向圖模型的仿真比較研究，證實了算法在調度長度和執行代價同步優化上的優勢。

1 相關研究

為了解決工作流調度這一NP問題，很多文獻提出了啟發式調度算法。文獻[3]提出兩種算法LOSS和GAIN分別用來優化預算約束下的時間和代價，但僅涉及單目標優化。文獻[4]討論了IaaS云環境中的代價和截止時間約束工作流調度，但所考慮的資源僅為同質資源模型。文獻[5]提出兩種云工作流調度算法：一階段算法IC-PCP和兩階段算法IC-PCPD2。兩種算法可以在多項式時間內得到截止時間約束下的代價最小調度方案。文獻[6]提出了在混合云中截止時間約束的代價最小化調度算法HEFT，利用子截止時間的概念進行資源的重調度，并實現了代價最小化。文獻[7]則實現了包任務在截止時間約束下的代價最小化調度，但僅適用于獨立任務調度。文獻[8]利用粒子群搜索方法求解了用戶截止時間約束下費用最小化的工作流調度方案。文獻[9-11]提出了一種截止時間與預算約束時工作流調度遺傳算法，但也僅是實現執行代價或執行時間的單一優化。文獻[12]提出一種工作流調度算法Hybrid，基于帕累托占優技術將任務調度至代價最小的虛擬機上，有效降低非關鍵路徑上任務的調度代價。但算法沒有考慮關鍵路徑上任務執行代價對于總體代價的關鍵影響，導致得到的最終代價并不一定是最優的。可以看出，以上啟發式或元啟式算法多數僅進行了壟斷和單一目標優化。

鑒于此，本文設計了一種同步考慮執行時間與代價的工作流調度算法，通過定義任務的調度優先級以及最優調度資源的選擇規則，實現工作流的均衡調度。

2 系統模型

表1給出與本文相關的所有符號含義說明。

表1 符號說明

表1 符號說明

2.1 工作流模型

科學工作流的常規建模方式即為有向無環圖模型DAG，將工作流表示為G=(V,E)，V表示任務v的集合，E表示邊e的集合也代表兩個任務間的通信代價。節點vi∈V表示任務的計算時間，該值取決于任務所分配的虛擬機的計算能力。邊(i,j)∈E的權重表示任務vi與任務vj間的通信時間，即任務間發送數據所需要的時間。若DAG中的一個任務不存在父節點(前驅節點)，則稱之為入口任務ventry，若一個任務不存在子節點(后繼節點)，則稱之為出口任務vexit。若DAG中擁有多個入口或出口任務節點，可分配一個總的入口或出口任務節點，并將其所有先前入口或出口任務相連，且該總入口或出口節點的權重取0，邊權重也取0。DAG的任務模型表明，一個任務只有在其所有父節點完成后，該任務才能開始執行。有向無環圖模型下的工作流模型優勢在于可以明確工作流各個子任務間的依賴關系，以及整個工作流的進出口位置，進而方便任務調度次序的選擇和任務完成時間的計算。

圖1為一個DAG模型示例。該DAG包括10個任務節點，節點v0為第一個執行任務，節點v1-v8僅能在任務v0完成關發送結果數據后才能開始執行，而節點v2-v4直到v1完成前也無法開始執行，節點v9是最后一個任務，該任務只有在其他所有任務均執行完成后才能開始執行。當兩個任務被分配至同一虛擬機資源時，邊上的通信代價值也可以忽略不計。

圖1 DAG示例

2.2 云資源模型

假設云計算環境擁有m個異構虛擬機資源組成的集合M，由于每個任務可在不同虛擬機上執行，令t(vi,mj)表示任務vi在虛擬機vj上的執行時間，并假設每個任務是DAG的一個個體而不再分割。DAG中的所有任務調度至虛擬機上執行后，DAG的調度長度makespan即為出口任務vexit的實際完成時間。令TES(vi,mj)、TEF(vi,mj)、TLF(vi,mj)分別表示任務vi在虛擬機mj上的最早開始時間、最早完成時間、最遲完成時間。TES(vi,mj)可表示為：

TES(vi,mj)=

(1)

若前驅任務vp調度至虛擬機mj，則ctvp,vi等于0。TEF(vi,mj)可表示為：

TEF(vi,mj)=TES(vi,mj)+t(vi,mj)

(2)

TLF(vi,mj)可表示為：

(3)

DAG的調度長度makespan定義為DAG的完成時間，等于出口任務vexit的實際完成時間，表示為：

MS=TAF(vexit)

(4)

云計算中，多個虛擬機均可以執行每個任務。則任務vi在虛擬機mj上的執行時間可表示為：

(5)

若現有n個虛擬同可執行任務vi，則vi的平均執行時間可表示為：

(6)

該資源模型利用異構的虛擬機集群建立了執行工作流任務的通用模型，使得不同處理能力和不同價格的虛擬機均是工作流任務的可選目標，這樣可以在調度算法設計上僅關注于任務與資源間滿足目標函數的匹配與映射求解問題。

2.3 價格模型

云計算擁有不同的價格模型，如Amazon EC2按照虛擬機的數量和類型收費，而Google App Engine則按照所請求的CPU周期數收費。本文利用后一種虛擬機的代價模型，其優勢在于在單個已付費周期的CPU租用過程中，若付費任務已經在單個CPU周期內完成，則后續繼續利用CPU的任務可以不支付費用，從而降低工作流整體的執行代價。價格越高，則表明虛擬機計算能力越強，反之亦然。令mc(vi,mj)表示任務vi在虛擬機mj上執行的代價：

(7)

3 算法設計

本文設計一種基于代價的工作流任務調度算法，目標是將DAG中的任務調度至虛擬機上執行，并確保得到最小化的調度長度和執行代價。算法基本流程如算法1所示。

算法1ICTS算法

輸入：DAG G(V,E)，虛擬機集合。

輸出：任務調度解，即任務與虛擬機間的映射關系。

1. partition G into levles according to tasks dependency

2. sort levels based on dependency order

3. for each level do

4. for each taskvido

5. computeRank(vi)

6. end for

7. end for

8. create new tasks list

9. sort all tasks in the new list in decreasing order of Rank(vi)

10. for each taskviin the task list do

11. for each VMmjin the VMs set do

12. compute MKCR(vi,mj)

13. end for

14. end for

15. assign taskvito the VMmjthat has the maximum value of MKCR(vi,mj)

16. end

ICTS算法由三個階段組成：層次排序階段(工作流任務分級)、確定任務優先級階段、虛擬機選擇階段。第一階段的目標是盡可能提高任務并行執行度，具體方式是以自頂向下的方式遍歷工作流結構的有向無環圖，以拓撲排序的形式將處于同一層次的相互獨立的任務劃分為群組。分組后的任務將形成任務包的形式，在同一任務包中的任務不具備相關性，從而提高任務的并行執行程度。第二階段中，算法根據每個任務的秩值，對每個層次中的任務進行排序，任務vi的秩值計算方式為：

(8)

(9)

Rank(vexit)=MCP(vexit)

(10)

由此可見，第二階段計算任務的秩值決定了任務被調度的優先級次序，且任務秩值需要以遞歸方式從出口任務往入口任務進行計算。

最后，在虛擬機選擇階段，任務vi在虛擬機mj上的調度長度/代價比率MKCR(vi,mj)計算為：

MKCR(vi,mj)=[(1-β)×Min_Cost(vi)/

Cost(vi,mj)]+[β×Min_TEF(vi)/TEF(vi,mj)]

(11)

式中：β表示代價因子，用于描述用戶對于調度長度與執行代價間的偏好；Cost(vi)表示任務vi在虛擬機mj上的執行代價。

第三階段使得每個任務將被調度至擁有最大MKCR(vi,mj)值的虛擬機上，該策略可以充分利用在每個虛擬機上相鄰兩個調度任務間的空閑時間槽，不僅最小化整個DAG的完成時間，并且可以通過目標虛擬機的選擇時參考調度長度/代價比率MKCR的方式均衡任務執行的時間和代價。

算法時間復雜度分析。ICTS算法的時間復雜度與傳統的HEFT算法是相似的，同為O(e×m)，其中：e表示DAG中有向邊的數量，m表示虛擬機數量。若有向邊的數量正比于v2(v為任務數量)，則算法時間復雜度可達到O(v2×m)。

圖2展示了以圖1為例的任務DAG利用混合算法Hybrid[12]和本文算法ICTS得到的調度結果。算例的場景中擁有3個虛擬機資源，任務在虛擬機上的執行時間和執行代價如表2和表3所示。圖2(a)顯示混合算法的調度長度為1 000.94 s，調度代價為822＄。圖2(b)顯示ICTS算法的調度長度為874.19 s，調度代價為793＄。本文提出的算法降低了約12.66%的調度長度，調度代價約節省了3.52%。

圖2 調度結果對比

任務VM0VM1VM2v0191.98132.6499.31v1220.01152.01113.81v2177.37122.5591.75v3270.97187.22140.18v4204.71141.44105.90

續表2 s

表3 任務在不同虛擬機上的執行代價 ＄

4 仿真實驗

利用WorkFlowSim平臺[13]進行云環境中工作流調度的仿真實驗，并利用一種特定的工作流結構類型Montage作為云工作流的拓撲結構進行測試，Montage工作流是一種應用于天文學領域的科學工作流結構，其任務組成以I/O密集型為主，對CPU處理能力要求相對較低，串行任務較少，其結構如圖3所示。表4是實驗中的相關參數配置情況。

圖3 Montage工作流結構

表4 參數配置

4.1 性能指標

1) 調度長度比率和代價比率。系統調度效率可以通過標準化的調度長度和代價進行衡量，即調度長度比率SLR和代價比率MCR，分別定義為：

(12)

(13)

式(12)的分母部分表示處于關鍵路徑CP上的任務的最小執行時間之和，式(13)的分母部分表示處于關鍵路徑CP上的任務的最小執行代價之和。

2) 代價因子β。為了度量SLR和MCR，需要使用不同的代價因子β取值。圖4為針對不同的代價因子取值在不同的DAG規模下得到SLR和MCR取值情況。圖中，x軸代表代價因子，y軸同時代表SLR和MCR，即標準化的調度長度和代價。DAG中的任務數量隨機生成于80～400個任務之間。圖4表明，代價因子與MCR成正比，而與SLR成反比。對于較小的代價因子β，如β=0.1、0.2、0.3，MCR和SLR的變化比例略小于β>0.3的變化。總體來看，在β<0.4的情況下，算法在兩個指標上能夠擁有較好的性能表現。而β>0.4后，SLR的變化比例較慢，而MCR變化較快。因此，在后續仿真測試中代價因子β可取值為0.1、0.2和0.3。

圖4 不同規模不同代價因子對性能的影響

4.2 結果分析

本節對ICTS算法和對比算法Hybrid進行實驗對比分析，利用前文引入的標準化調度長度比率和標準化代價比率作為性能指標。在相同的虛擬機資源配置下，利用不同的DAG規模(不同的任務數量)進行實驗仿真。圖4為在不同的任務數量和CCR取值情況下兩個指標的性能比較情況，其中，柱狀圖的取值對應于左側縱坐標值，折線圖的取值對應于右側坐標值。算法的SLR指標均會隨著任務數量和CCR取值的增加而增加，而ICTS算法在不同DAG規模下也可以得到更優的SLR性能。表5給出本文算法ICTS對比Hybrid算法在任務調度長度和代價上得到的增益比例(即在調度長度和代價上的節省程度)，在確定的任務規模下，ICTS算法在選擇目標虛擬機時有效參考了調度效率與代價的均衡，使得兩個指標均得到改善。

表5 ICTS算法比較對比算法Hybrid得到的增益

圖5和圖6顯示了在不同的DAG任務規模下算法得到的SLR和MCR指標性能情況。可以看到，ICTS算法在兩項指標上是優于Hybrid算法的，這是因為ICTS算法考慮了任務父節點與自身的通信時間以及任務子節點與自身的通信時間(如式(8)所示)。因此，在DAG中最復雜任務將處于分級隊列的隊首而被優先進行調度。而Hybrid算法在計算每個任務的分級時僅僅考慮了任務與其后繼之間的通信時間。

圖5 不同任務組成(CCR度量)及不同任務數量對SLR的影響

圖6 不同任務組成(CCR度量)及不同任務數量對MCR的影響

利用式(11)選擇任務調度的虛擬機，ICTS算法同時考慮了Min_Cost(vi)和Min_TEF(vi)。此外，還可以看到，改變工作流中任務的通信/計算比率(改變計算密集型和通信密集型任務的比例)的情況下，ICTS算法在SLR指標上依然具有較好的適應性，仿真結果并沒有出現反轉式的結果，而僅僅是指標值出現比較緩和的增加。

對于算法而言，MCR指標會隨著任務數量和CCR取值的增加而增加。圖6結果表明ICTS算法在不同的任務規模下提供了比Hybrid算法更好的MCR性能。另一方面，Hybrid算法過多依賴于時間與代價的比例，這些比例在選取調度任務時僅考慮了執行代價與執行時間的最小值和最大值，而本文算法對相關參數的依賴性則遠弱于Hybrid算法，使其在不同規模和不同任務組成的情況下依然可能得到比較穩定的性能表現。

5 結 語

為了實現云計算環境中的工作流任務調度，本文以最小化調度長度和執行代價為目標，提出一種基于代價的工作流調度算法。通過任務分級排序、確定任務優先級以及虛擬機資源選擇三個階段的優化，實現了不同規模任務下對工作流調度長度和執行代價的同步優化。仿真實驗結果表明，對于選取的SLR和MCR兩個性能指標，本文算法均表現出比對比算法更好的性能。下一步可選擇將云資源提供方的能耗問題考慮到優化目標中，即在執行效率與執行能效之間取得更好的平衡，以此為目標設計工作流調度算法。