基于IaaS云中的任務調度分配算法的研究與實現

周水清， 陳 雯， 龔仕林

(1.數字化紡織服裝技術教育部工程研究中心，上海 201620; 2.東華大學 信息科學與技術學院，上海 201620)

基于IaaS云中的任務調度分配算法的研究與實現

周水清1,2， 陳 雯1,2， 龔仕林1,2

(1.數字化紡織服裝技術教育部工程研究中心，上海 201620; 2.東華大學 信息科學與技術學院，上海 201620)

近年來，基于互聯網技術的云計算的應用日趨成熟，諸多開源的云平臺不斷出現。異構分布式環境中，在面對不同情況時，如何保障負載均衡已經成為云計算研究中的重要研究方向。本文提出了一種基于DAG(Directed Acyclic Graph)的異構分布式系統的任務調度策略。該算法通過資源效益度的競爭，從篩選后的資源池中選擇恰當的資源節點進行任務分配，以此提高系統的負載均衡能力。通過實驗表明，該任務調度算法可以有效降低通信開銷，提高資源利用率，提升負載均衡能力，為整個系統提供高效的性能。

云計算；資源調度；負載均衡；DAG

0 引言

隨著近幾年互聯網的迅猛發展，網絡上的數據量呈現了爆發式的增長。面對如此龐大的數據量，搭建一個云計算資源管理平臺用于管理這些數據就顯得非常有必要[1-2]。

在平臺中，任務調度算法是提高平臺工作效率的關鍵之一。云計算任務調度的目標就是將相互獨立的N項任務分配到M種異構可用的資源上，使得任務的完成總時間最小且資源得到充分利用。在實際應用中則是將不同的任務分配給不同的虛擬機執行，以使得網絡帶寬占用率最小，得到最佳的任務執行時間[3]。

目前，關于云計算平臺的任務調度算法逐漸成為研究熱點。Silvio Luiz Stanzani等人提出了MCA-HEFT(Multi-Cluster Allocation-HEFT)算法[4]，證明了多集群調度平行任務的可能性，不過沒有充分考慮到數據傳輸時造成的網絡負擔。Nitish Chopra等人提出了在公私混合云中進行調度的算法[5]，它著重考慮了任務調度運行中的用戶花費問題。通過多次調度，從公有云中借用資源達到了在規定時間內降低使用費用的目的。但是其缺點是從公有云中借用資源的步驟過于繁瑣復雜。O.M.Elzeki等人對最大最小任務調度算法進行了優化[6]。它克服原來最大最小算法的不足，當有大量較小任務的時候，最大最小任務調度算法的任務執行時間會顯著降低。但是，其缺點是沒有充分考慮到資源節點的可用性和穩定性。田國忠提出了基于異構資源的多DAG任務調度的BackFill算法，并且研究了用戶使用費用的優化問題[7]。

盡管有很多分布式任務調度的研究取得了一定進展，但是在以下幾方面仍然有進一步研究和優化的空間：

(1)只考慮了網絡情況良好、數據傳輸效率較高的情況；

(2)不同任務會對任務執行節點有不同的要求，需要引入一個靈活的變量用以量化任務執行節點；

(3)可以將DAG的概念引入算法。

1 算法模型

本文提出的算法在優化后的Max-Min算法的基礎上[8]進行了以下的改進和優化：

(1)引入了DAG任務的概念；

(2)引入了資源效益度，將資源的性能進行量化，從而便于任務執行節點的篩選；

(3)把任務直接分配到數據所在的資源節點上，而不是將數據和任務分配到篩選出的節點上，降低了網絡負載。

資源效益度(滿足程度)[9]：指的是在任務調度的過程中，資源對于任務所要求的條件滿足程度，對于第Ri個資源，其資源的效益程度用E(Ri)表示。

資源效益度不只是與任務完成時間、資源的負載有關，同時還與資源能耗、數據本地性有關。資源效益度值越高，則選擇該資源節點來完成任務的可能性也越高。

資源節點的效益度是由資源的特征參數構成的，這些特征參數可以使用一個集合來表示：C={c1,c2,c3,c4,c5,…}，集合中的每一個元素表示資源的一個特征量。常見的特征量如表1所示。此外，根據不同情況的需要，還可以靈活選擇特征量。

表1 特征量表

在計算資源效益度時，首先要對特征參量進行量化和歸一化處理，從而使得Ci∈[0,1]。 然后根據歸一化之后的特征量計算資源的效益度。

(1)

在特征量集中，由于有些特征量對于任務的執行影響占據主導地位，有的則相對較弱，所以有必要對每個特征量取其權值。改變不同的權值用以應對不同的情況。

(2)

此外，在效益度中，設置了變量Flag，它是一個布爾值。當資源空閑、沒有任務需要處理時，將其置為1。如果有任務正在處理時，則將其置為0。因此，將效益度的公式修改為：

(3)

另一方面，在實際的生產中，經常出現的一種情況就是，所需要完成的任務的輸入值是其他任務完成之后的輸出值。在DAG中，任務之間具有關聯性，即必須在完成一個任務之后才能繼續執行后續任務。基于這種特征，本文使用DAG用以模擬此情況[10]。DAG的示例如圖1所示。

圖1 DAG任務示例圖

在任務調度的過程中，按照任務層對任務進行歸類。在每一層中，得到任務所要處理數據的元數據(metadata)。和資源的特征量類似，元數據也是一個集合，其內部常用的元素如表2所示。

表2 常用元數據表

元數據對算法非常重要，比如數據能否在本地、數據的大小、數據的權限等。它無法像資源的效益度一樣進行確切的量化分析，只能根據不同的情況在恰當的地方調用適合的元數據。

2 優化算法

在系統的整體調度策略中，其策略核心是根據任務的元數據和資源的效益度執行任務調度。本文所提出的DAG任務應用分布式異構系統的調度策略，其大致思想如下：

首先，選擇需要處理的任務。在一個DAG任務中，先對第一層任務進行調度分配，即從DAG的入口開始。根據元數據，獲得需要處理數據的大小。需要處理數據量最大的任務擁有最高的優先處理權。

在分布式系統中，同一份數據會在不同的資源上擁有備份，因此根據元數據獲取需要處理的任務數據的路徑。

此外，判斷數據是否在本地資源上的變量是一個布爾值，記為L。為此，有必要把效益度公式再次修改為：

(4)

擁有任務所需要數據的資源的集合，稱為資源候選池。從上式可以知道，當本地資源沒有所需要的數據，或者當資源正在處理其他任務時，資源的效益度會設為0，也就是最低。這樣這個資源在資源候選池中就沒有了競爭力，這樣任務就會分配到其他候選資源上。

在對資源進行篩選后，剩下的資源會繼續通過效益度競爭，并且仍然由效益度較高的資源獲得任務執行權。在獲得執行權后，將資源節點的Flag置為0，并在任務執行完畢之后將Flag重新置1，以此迭代，完成一層DAG任務。

在DAG任務的第一層執行完畢后，執行第二層的任務集合。處理方法與第一層任務執行程序一樣。原則是將需要處理的最大數據分配給處于空閑狀態并且效益度最高的擁有本地數據的資源上，依次迭代。當最后一層的任務完成之后，到達DAG的出口，整個DAG任務則完成。算法流程圖如圖2所示。

圖2 算法流程圖

從流程圖中可以看出，算法會首先考慮當前DAG層是否還有任務需要執行。如果有尚未完成的任務，則獲取任務的元數據。通過元數據比較該層全部任務所擁有的優先級，選擇優先級最高的任務，通過效益度計算公式選擇效益度最高的資源節點，使用該節點執行任務。在完成任務之后，繼續考慮當前層有無任務需要執行，依次迭代，最后完成整個DAG層。在所有的DAG層都完成以后，該DAG任務完成。下面給出算法的偽代碼。

while (layer.size() != 0){

//判斷是否還有DAG層

while (task.size() != 0){

//判斷該層是否還有任務

for all submitted tasks in layer of DAG;

//遍歷所有需要執行的任務

for all metadata in tasks;

//確認執行任務的元數據

search task T which has maximum data

//找到數據量最大的任務，設為T

for all resource;

assign Ti to the resource Rj which has maximum performance with local data in leisure;

set Flag of resource Rj to busy;

//將運行任務的資源設定為busy狀態

}

}

3 實驗與結果分析

3.1 實驗相關條件

實驗使用的仿真平臺是CloudSim。它是一款由澳大利亞墨爾本大學的實驗室與Gridbus項目所宣布推出的云計算仿真軟件。

CloudSim的功能可以分為兩大類：第一類是虛擬化引擎，其目的是在數據中建立和管理獨立的、協同的、多重的虛擬化服務。第二類是虛擬化服務分配處理核心，使其可以在時間共享和空間共享之間靈活地進行切換。

實驗中搭建了一個數據中心用以模擬云計算集群。該集群擁有五臺虛擬機作為資源節點，分別稱之為Vm0，Vm1，Vm2，Vm3，Vm4。詳細數據如表3所示。

表3 資源信息表(次)

因為集群中每臺計算機的性能指標復雜繁多，所以本次實驗中僅僅考慮與任務處理速度相關的兩個主要性能指標：MIPS(Million Instructions Per Second)和Ram。這兩項指標是任務處理中的關鍵指標。此外，所有的虛擬機都假定是單核處理器。在CloudSim中的具體實現則是從CondorVM類中分別實例化5個Vm，在實例化的過程中指定相應的性能參數。

任務的輸入是DAG任務，有50個任務，分為9層。每層的任務數量如表4所示。

表4 每層任務數量表

在CloudSim中，DAG任務是通過一個xml文件引入的。利用Java的File類對文件進行解析，從而實現任務的輸入。

另外，在比較資源效益度方面，因為CondorVM類繼承自VM類，所以可以使用VM類中的方法getCloudletMips()和getCloudletRAM()獲得本次試驗所需的資源節點的性能指標。每次分配任務時，算法都會自動刷新這些指標，把得到的最新性能指標代入上文所推出的節點效益度公式(4)，從而實時地為算法提供每個節點的效益度指標。

3.2 實驗結果

經過多次試驗，并對結果進行統計后，將其與FCFS(First Come First Server)算法以及Max-min算法進行比較。FCFS算法是一種對DAG任務中的每一個任務逐個依次進行執行的經典算法。得到的試驗結果如下：

(1)在網絡負載使用方面，因為優化后的算法是把任務分配到資源上，所以其對網絡環境的要求較低。而另外兩個算法則是把任務需要的數據傳輸到任務節點上，因此當網絡環境惡劣或者需要傳輸數據量非常大的時候，這兩個算法的性能會大幅下降，所以兩者對網絡環境的要求較高。

圖3 實驗任務完成時間比較圖

(2)由圖3可以看出，優化后的算法平均任務完成時間為217.35 ms，Max-Min算法為205.21 ms， FCFS算法為210.04 ms。新算法的完成時間比Max-min算法的完成時間延長了5.91%。這是因為新算法相比原本的算法增加了限制條件，從而造成任務完成時間的延長。不過，任務完成時間的增量在可以接受的范圍之內。如果處理的任務量不是非常大，那么可以近似認為新算法和Max-min算法的完成時間相同。

(3)在負載均衡能力方面，由于處理的DAG任務大多分布于第3層，所以主要從第3層分析算法的負載均衡能力。負載均衡能力主要觀察是否每個節點都被平均地分配到了任務。如果各個節點之間所獲得的任務數量相近，那么就可以認為算法的負載均衡能力較好。

如圖4所示，在所有28個任務中，原來的Max-min算法主要是把任務分配到了運算能力較為強大的Vm3和Vm4上，Vm0和Vm1所分配到的任務個數顯然偏少，算法的負載均衡能力不好。

圖4 負載均稀能力比較圖

對于FCFS算法，它將大量的任務分配到了運算能力低下的節點Vm0和Vm1上。而能力相對強大的Vm3和Vm4的幾個節點相對而言幾乎沒有分配到任務，因此，該算法的負載均衡能力也不好。

最后，對于本文提出的新算法，各節點獲得的任務數量較為平均，相對于另外兩個算法，負載均衡能力明顯有了提升。這是因為優化后的算法采用的策略是將任務放在本地數據上進行處理，即把任務分配到了數據所在資源上，而不是把數據傳輸到效益度較高的資源上進行處理。

4 總結

本文提出了資源效益度概念，用于量化系統中各個資源節點，以此作為選擇任務分配時的重要依據。對于資源效益度，用戶可以根據不同的任務情況，隨時改變它的量化標準，從而靈活調整任務分配的策略。文章通過DAG模擬了日常生產中所遇到的輸入任務情況，并提出了基于DAG任務的調度算法。通過加入效益度函數對原有算法進行了優化。

實驗結果表明，新算法可以顯著降低網絡負載，并且在輸入DAG任務規模不太大的時候，通過犧牲部分任務完成時間顯著提高了云計算系統的任務負載均衡能力。為云計算環境下DAG任務調度策略的研究提出了新的解決思路。

[1] ARMBRUST M, FOX O, GRIFFITH R, et al. Above the clouds: a view of cloud computing[J]. Eecs Department University of California Berkeley, 2009, 53(4):50-58.

[2] 梁鋼, 茅秋吟. 云計算IaaS平臺的信息安全和運維服務設計[J]. 電子技術應用, 2013, 39(7):63-64.

[3] 徐忠勝,沈蘇彬.一種云計算資源的多目標優化的調度方法[J].微型機與應用,2015,34(13):17-20.

[4] STANZANI S L, SATO L M, NETTO M A S. Scheduling workflows in multi-cluster environments[C].Advanced Information Networking and Applications Workshops (WAINA), 2013 27th International Conference on. IEEE, 2013: 560-565.

[5] CHOPRA N, SINGH S. HEFT based workflow scheduling algorithm for cost optimization within deadline in hybrid clouds[C].2013 Fourth International Conference on Computing, Communications and Networking Technologies (ICCCNT). IEEE, 2013: 1-6.

[6] ELZEKI O M, RESHAD M Z, ELSOUD M A. Improved max-min algorithm in cloud computing[J]. International Journal of Computer Applications, 2012, 50(12): 22-27.

[7] 田國忠. 多 DAG 共享資源調度的若干問題研究[D]. 北京: 北京工業大學, 2014.

[8] KOKILAVANI T, GEORGE AMALARETHNAM D I. Load balanced Min-Min algorithm for static Meta-task scheduling in grid computing[J]. International Journal of Computer Applications, 2011,20(2):43-49.

[9] 程春玲, 張登銀, 徐玉,等. 一種面向云計算的分態式自適應負載均衡策略[J]. 南京郵電大學學報：自然科學版, 2012(4):53-58.

[10] 唐一韜, 黃晶, 肖球. 一種基于DAG的MapReduce任務調度算法[J]. 計算機科學, 2014, 41(S1):42-46.

Research and implement of task scheduling algorithm based on IaaS cloud platform

Zhou Shuiqing1,2, Chen Wen1,2, Gong Shiling1,2

(1.Engineering Research Center of Digitized Textile & Apparel Technology, Ministry of Education, Shanghai 201620, China;2. College of Information Science and Technology, Donghua University, Shanghai 201620, China)

In recent years, with the developing of Internet technology, many open source platform occurs. In heterogeneous distributed system, face to different condition, how to guarantee the payload balance became a important issue. In this paper, a task scheduling algorithm based on DAG’s heterogeneous distributed system is proposed. After selecting source nodes by their performance, the algorithm reselects node from the pool of source to balance the system. The experiment results show that the algorithm can ensure system balance, improve source efficiency and reduce cost of communication.

cloud computing, task scheduling, load balancing, DAG

TP393

A

1674-7720(2016)05-0022-04

周水清，陳雯，龔仕林. 基于IaaS云中的任務調度分配算法的研究與實現[J].微型機與應用，2016,35(5)：22-25.

2015-11-05)

周水清(1989-)，男，碩士研究生，主要研究方向：云計算和計算機仿真。

陳雯(1977-)，女，博士，副教授，主要研究方向：網絡通信和計算機仿真。

龔仕林(1990-)，男，碩士研究生，主要研究方向：云計算和仿真。