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

周水清， 陳 雯， 龔仕林

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

1 算法模型

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

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

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

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

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

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

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

表1 特征量表

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

(1)

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

(2)

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

(3)

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

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

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

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

元數(shù)據(jù)對(duì)算法非常重要，比如數(shù)據(jù)能否在本地、數(shù)據(jù)的大小、數(shù)據(jù)的權(quán)限等。它無(wú)法像資源的效益度一樣進(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ù)。在一個(gè)DAG任務(wù)中，先對(duì)第一層任務(wù)進(jìn)行調(diào)度分配，即從DAG的入口開(kāi)始。根據(jù)元數(shù)據(jù)，獲得需要處理數(shù)據(jù)的大小。需要處理數(shù)據(jù)量最大的任務(wù)擁有最高的優(yōu)先處理權(quán)。

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

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

(4)

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

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

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

圖2 算法流程圖

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

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 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)相關(guān)條件

實(shí)驗(yàn)使用的仿真平臺(tái)是CloudSim。它是一款由澳大利亞墨爾本大學(xué)的實(shí)驗(yàn)室與Gridbus項(xiàng)目所宣布推出的云計(jì)算仿真軟件。

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

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

表3 資源信息表(次)

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

圖3 實(shí)驗(yàn)任務(wù)完成時(shí)間比較圖

(2)由圖3可以看出，優(yōu)化后的算法平均任務(wù)完成時(shí)間為217.35 ms，Max-Min算法為205.21 ms， FCFS算法為210.04 ms。新算法的完成時(shí)間比Max-min算法的完成時(shí)間延長(zhǎng)了5.91%。這是因?yàn)樾滤惴ㄏ啾仍镜乃惴ㄔ黾恿讼拗茥l件，從而造成任務(wù)完成時(shí)間的延長(zhǎng)。不過(guò)，任務(wù)完成時(shí)間的增量在可以接受的范圍之內(nèi)。如果處理的任務(wù)量不是非常大，那么可以近似認(rèn)為新算法和Max-min算法的完成時(shí)間相同。

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

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

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

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

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

4 總結(jié)

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

實(shí)驗(yàn)結(jié)果表明，新算法可以顯著降低網(wǎng)絡(luò)負(fù)載，并且在輸入DAG任務(wù)規(guī)模不太大的時(shí)候，通過(guò)犧牲部分任務(wù)完成時(shí)間顯著提高了云計(jì)算系統(tǒng)的任務(wù)負(fù)載均衡能力。為云計(jì)算環(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] 梁鋼, 茅秋吟. 云計(jì)算IaaS平臺(tái)的信息安全和運(yùn)維服務(wù)設(shè)計(jì)[J]. 電子技術(shù)應(yīng)用, 2013, 39(7):63-64.

[3] 徐忠勝,沈蘇彬.一種云計(jì)算資源的多目標(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.

[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] 田國(guó)忠. 多 DAG 共享資源調(diào)度的若干問(wèn)題研究[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] 程春玲, 張登銀, 徐玉,等. 一種面向云計(jì)算的分態(tài)式自適應(yīng)負(fù)載均衡策略[J]. 南京郵電大學(xué)學(xué)報(bào)：自然科學(xué)版, 2012(4):53-58.

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

2015-11-05)

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

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

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