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

　?。?.數(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)提供高效的性能。

　　關(guān)鍵詞：云計算；資源調(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ù)分配給不同的虛擬機(jī)執(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)度運(yùn)行中的用戶花費問題。通過多次調(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)化的空間：

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

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

　?。?）可以將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特征量表類型參數(shù)CPUCPU數(shù)量CPU處理速率CPU利用率內(nèi)存空閑物理內(nèi)存空閑虛擬內(nèi)存硬盤磁盤利用率磁盤轉(zhuǎn)速I/O訪問速度其他Flag標(biāo)識在計算資源效益度時，首先要對特征參量進(jìn)行量化和歸一化處理，從而使得Ci∈［0,1］。 然后根據(jù)歸一化之后的特征量計算資源的效益度。

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

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

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

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

元數(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。為此，有必要把效益度公式再次修改為：

　　擁有任務(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所示。

　　從流程圖中可以看出，算法會首先考慮當(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;

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

　　}

　　}

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

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

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

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

　　實驗中搭建了一個數(shù)據(jù)中心用以模擬云計算集群。該集群擁有五臺虛擬機(jī)作為資源節(jié)點，分別稱之為Vm0，Vm1，Vm2，Vm3，Vm4。詳細(xì)數(shù)據(jù)如表3所示。因為集群中每臺計算機(jī)的性能指標(biāo)復(fù)雜繁多，所以本次實驗中僅僅考慮與任務(wù)處理速度相關(guān)的兩個主要性能指標(biāo)：MIPS（Million Instructions Per Second）和Ram。這兩項指標(biāo)是任務(wù)處理中的關(guān)鍵指標(biāo)。此外，所有的虛擬機(jī)都假定是單核處理器。在CloudSim中的具體實現(xiàn)則是從CondorVM類中分別實例化5個Vm，在實例化的過程中指定相應(yīng)的性能參數(shù)。

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

　　在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é)果如下：

　?。?）在網(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可以看出，優(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算法的完成時間相同。

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

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

　　對于FCFS算法，它將大量的任務(wù)分配到了運(yùn)算能力低下的節(jié)點Vm0和Vm1上。而能力相對強(qiáng)大的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)度策略的研究提出了新的解決思路。

參考文獻(xiàn)

　　［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.

　?。?］ 梁鋼, 茅秋吟. 云計算IaaS平臺的信息安全和運(yùn)維服務(wù)設(shè)計［J］. 電子技術(shù)應(yīng)用, 2013, 39(7):6364.

　?。?］ 徐忠勝,沈蘇彬.一種云計算資源的多目標(biāo)優(yōu)化的調(diào)度方法［J］.微型機(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.

　?。?］ 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.

　?。?］ 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.

　?。?］ 田國忠. 多 DAG 共享資源調(diào)度的若干問題研究［D］. 北京: 北京工業(yè)大學(xué), 2014.

　?。?］ 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.

　?。?］ 程春玲, 張登銀, 徐玉,等. 一種面向云計算的分態(tài)式自適應(yīng)負(fù)載均衡策略［J］. 南京郵電大學(xué)學(xué)報：自然科學(xué)版, 2012(4):5358.

　?。?0］ 唐一韜, 黃晶, 肖球. 一種基于DAG的MapReduce任務(wù)調(diào)度算法［J］. 計算機(jī)科學(xué), 2014, 41(S1):4246.