基于IaaS云中的任務(wù)調(diào)度分配算法的研究與實現(xiàn)

周水清， 陳 雯， 龔仕林

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

基于IaaS云中的任務(wù)調(diào)度分配算法的研究與實現(xiàn)

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

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

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

云計算；資源調(diào)度；負(fù)載均衡；DAG

0 引言

隨著近幾年互聯(lián)網(wǎng)的迅猛發(fā)展，網(wǎng)絡(luò)上的數(shù)據(jù)量呈現(xiàn)了爆發(fā)式的增長。面對如此龐大的數(shù)據(jù)量，搭建一個云計算資源管理平臺用于管理這些數(shù)據(jù)就顯得非常有必要[1-2]。

在平臺中，任務(wù)調(diào)度算法是提高平臺工作效率的關(guān)鍵之一。云計算任務(wù)調(diào)度的目標(biāo)就是將相互獨立的N項任務(wù)分配到M種異構(gòu)可用的資源上，使得任務(wù)的完成總時間最小且資源得到充分利用。在實際應(yīng)用中則是將不同的任務(wù)分配給不同的虛擬機執(zhí)行，以使得網(wǎng)絡(luò)帶寬占用率最小，得到最佳的任務(wù)執(zhí)行時間[3]。

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

盡管有很多分布式任務(wù)調(diào)度的研究取得了一定進(jìn)展，但是在以下幾方面仍然有進(jìn)一步研究和優(yōu)化的空間：

(1)只考慮了網(wǎng)絡(luò)情況良好、數(shù)據(jù)傳輸效率較高的情況；

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

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

1 算法模型

本文提出的算法在優(yōu)化后的Max-Min算法的基礎(chǔ)上[8]進(jìn)行了以下的改進(jìn)和優(yōu)化：

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

(2)引入了資源效益度，將資源的性能進(jìn)行量化，從而便于任務(wù)執(zhí)行節(jié)點的篩選；

(3)把任務(wù)直接分配到數(shù)據(jù)所在的資源節(jié)點上，而不是將數(shù)據(jù)和任務(wù)分配到篩選出的節(jié)點上，降低了網(wǎng)絡(luò)負(fù)載。

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

資源效益度不只是與任務(wù)完成時間、資源的負(fù)載有關(guān)，同時還與資源能耗、數(shù)據(jù)本地性有關(guān)。資源效益度值越高，則選擇該資源節(jié)點來完成任務(wù)的可能性也越高。

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

表1 特征量表

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

(1)

在特征量集中，由于有些特征量對于任務(wù)的執(zhí)行影響占據(jù)主導(dǎo)地位，有的則相對較弱，所以有必要對每個特征量取其權(quán)值。改變不同的權(quán)值用以應(yīng)對不同的情況。

(2)

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

(3)

另一方面，在實際的生產(chǎn)中，經(jīng)常出現(xiàn)的一種情況就是，所需要完成的任務(wù)的輸入值是其他任務(wù)完成之后的輸出值。在DAG中，任務(wù)之間具有關(guān)聯(lián)性，即必須在完成一個任務(wù)之后才能繼續(xù)執(zhí)行后續(xù)任務(wù)?；谶@種特征，本文使用DAG用以模擬此情況[10]。DAG的示例如圖1所示。

圖1 DAG任務(wù)示例圖

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

表2 常用元數(shù)據(jù)表

元數(shù)據(jù)對算法非常重要，比如數(shù)據(jù)能否在本地、數(shù)據(jù)的大小、數(shù)據(jù)的權(quán)限等。它無法像資源的效益度一樣進(jìn)行確切的量化分析，只能根據(jù)不同的情況在恰當(dāng)?shù)牡胤秸{(diào)用適合的元數(shù)據(jù)。

2 優(yōu)化算法

在系統(tǒng)的整體調(diào)度策略中，其策略核心是根據(jù)任務(wù)的元數(shù)據(jù)和資源的效益度執(zhí)行任務(wù)調(diào)度。本文所提出的DAG任務(wù)應(yīng)用分布式異構(gòu)系統(tǒng)的調(diào)度策略，其大致思想如下：

首先，選擇需要處理的任務(wù)。在一個DAG任務(wù)中，先對第一層任務(wù)進(jìn)行調(diào)度分配，即從DAG的入口開始。根據(jù)元數(shù)據(jù)，獲得需要處理數(shù)據(jù)的大小。需要處理數(shù)據(jù)量最大的任務(wù)擁有最高的優(yōu)先處理權(quán)。

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

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

(4)

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

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

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

圖2 算法流程圖

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

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

//判斷是否還有DAG層

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

//判斷該層是否還有任務(wù)

for all submitted tasks in layer of DAG;

//遍歷所有需要執(zhí)行的任務(wù)

for all metadata in tasks;

//確認(rèn)執(zhí)行任務(wù)的元數(shù)據(jù)

search task T which has maximum data

//找到數(shù)據(jù)量最大的任務(wù)，設(shè)為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;

//將運行任務(wù)的資源設(shè)定為busy狀態(tài)

}

}

3 實驗與結(jié)果分析

3.1 實驗相關(guān)條件

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

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

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

表3 資源信息表(次)

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

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

表4 每層任務(wù)數(shù)量表

在CloudSim中，DAG任務(wù)是通過一個xml文件引入的。利用Java的File類對文件進(jìn)行解析，從而實現(xiàn)任務(wù)的輸入。

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

3.2 實驗結(jié)果

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

(1)在網(wǎng)絡(luò)負(fù)載使用方面，因為優(yōu)化后的算法是把任務(wù)分配到資源上，所以其對網(wǎng)絡(luò)環(huán)境的要求較低。而另外兩個算法則是把任務(wù)需要的數(shù)據(jù)傳輸?shù)饺蝿?wù)節(jié)點上，因此當(dāng)網(wǎng)絡(luò)環(huán)境惡劣或者需要傳輸數(shù)據(jù)量非常大的時候，這兩個算法的性能會大幅下降，所以兩者對網(wǎng)絡(luò)環(huán)境的要求較高。

圖3 實驗任務(wù)完成時間比較圖

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

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

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

圖4 負(fù)載均稀能力比較圖

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

最后，對于本文提出的新算法，各節(jié)點獲得的任務(wù)數(shù)量較為平均，相對于另外兩個算法，負(fù)載均衡能力明顯有了提升。這是因為優(yōu)化后的算法采用的策略是將任務(wù)放在本地數(shù)據(jù)上進(jìn)行處理，即把任務(wù)分配到了數(shù)據(jù)所在資源上，而不是把數(shù)據(jù)傳輸?shù)叫б娑容^高的資源上進(jìn)行處理。

4 總結(jié)

本文提出了資源效益度概念，用于量化系統(tǒng)中各個資源節(jié)點，以此作為選擇任務(wù)分配時的重要依據(jù)。對于資源效益度，用戶可以根據(jù)不同的任務(wù)情況，隨時改變它的量化標(biāo)準(zhǔn)，從而靈活調(diào)整任務(wù)分配的策略。文章通過DAG模擬了日常生產(chǎn)中所遇到的輸入任務(wù)情況，并提出了基于DAG任務(wù)的調(diào)度算法。通過加入效益度函數(shù)對原有算法進(jìn)行了優(yōu)化。

實驗結(jié)果表明，新算法可以顯著降低網(wǎng)絡(luò)負(fù)載，并且在輸入DAG任務(wù)規(guī)模不太大的時候，通過犧牲部分任務(wù)完成時間顯著提高了云計算系統(tǒng)的任務(wù)負(fù)載均衡能力。為云計算環(huán)境下DAG任務(wù)調(diào)度策略的研究提出了新的解決思路。

[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平臺的信息安全和運維服務(wù)設(shè)計[J]. 電子技術(shù)應(yīng)用, 2013, 39(7):63-64.

[3] 徐忠勝,沈蘇彬.一種云計算資源的多目標(biāo)優(yōu)化的調(diào)度方法[J].微型機與應(yīng)用,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 共享資源調(diào)度的若干問題研究[D]. 北京: 北京工業(yè)大學(xué), 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] 程春玲, 張登銀, 徐玉,等. 一種面向云計算的分態(tài)式自適應(yīng)負(fù)載均衡策略[J]. 南京郵電大學(xué)學(xué)報：自然科學(xué)版, 2012(4):53-58.

[10] 唐一韜, 黃晶, 肖球. 一種基于DAG的MapReduce任務(wù)調(diào)度算法[J]. 計算機科學(xué), 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云中的任務(wù)調(diào)度分配算法的研究與實現(xiàn)[J].微型機與應(yīng)用，2016,35(5)：22-25.

2015-11-05)

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

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

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