葛君偉，葛 兵，方義秋

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

云環(huán)境下一種基于負載均衡的任務(wù)調(diào)度策略

葛君偉，葛 兵，方義秋

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

針對云計算環(huán)境下大量并行計算節(jié)點容易產(chǎn)生計算節(jié)點之間的負載不均問題，提出了一種基于任務(wù)類型匹配的負載均衡方案。該方案針對任務(wù)集中的多種不同長度的子任務(wù)類型情況進行判定，并對當(dāng)前主流的Max-Min和Min-Min兩種啟發(fā)式負載均衡算法進行分析，綜合其優(yōu)缺點，并針對任務(wù)集的類型采用不同的算法進行任務(wù)調(diào)度。實驗結(jié)果表明在該負載均衡的策略下，提出的方案具有比單一應(yīng)用Max-Min或者Min-Min算法具有更好的負載均衡特性和更短的完成時間。

云計算；任務(wù)調(diào)度；負載均衡；Max-Min；Min-Min

云計算是一種新型的商業(yè)計算模式，它將計算任務(wù)分布在大量異構(gòu)的計算機構(gòu)建成的資源池上，使得各種應(yīng)用系統(tǒng)能夠根據(jù)需求獲取可用的計算資源、數(shù)據(jù)資源以及存儲資源等資源服務(wù)[1]。云計算的一個典型特征是具有伸縮性，所以一個云系統(tǒng)也被稱為彈性云。

近年來關(guān)于云計算中的負載均衡問題是一個研究熱點，如今已經(jīng)有許多的負載均衡算法被提出以滿足不同的優(yōu)化目標(biāo)。

最大最小算法(Max-Min)和最小最小算法(Max-Min)是一種啟發(fā)式的調(diào)度算法，他們以任務(wù)的總執(zhí)行時間最短為優(yōu)化目標(biāo)，Max-Min算法的核心思想是每次先計算任務(wù)在各個資源上的預(yù)計算時間，然后對最大最早完成時間的任務(wù)進行調(diào)度。對于元任務(wù)集合中長任務(wù)少短任務(wù)多的情況下，算法的執(zhí)行效果較好。但是如果具體應(yīng)用條件發(fā)生了變化，Max-Min算法的優(yōu)勢可能就不存在了[2]。

Max-Min 算法和Max-Min算法卻正好相反，它是先計算出任務(wù)在資源上的預(yù)計執(zhí)行時間，再將最小且是最早完成時間的任務(wù)調(diào)度到資源節(jié)點上，這樣會使任務(wù)的處理速度較快，任務(wù)完成時間短，但是由于每次都是把任務(wù)分配給執(zhí)行最快的資源，這樣很容易造成負載的嚴(yán)重不均，甚至一些服務(wù)器空載[3]。

基于此，本文提出了一種基于云環(huán)境下針對任務(wù)類型匹配的資源調(diào)度算法，該算法針對任務(wù)集中長短任務(wù)的不同分布情況來采取不同的調(diào)度算法，通過云仿真軟件CloudSim 3.0驗證了該調(diào)度策略良好的調(diào)度效果。

1 相關(guān)工作

云計算環(huán)境下，有大量的負載均衡算法用于將任務(wù)調(diào)度到相應(yīng)的計算資源上執(zhí)行，根據(jù)優(yōu)化的目標(biāo)不同，算法各有優(yōu)缺點。當(dāng)前有國內(nèi)外學(xué)者都相繼提出了針對Max-Min算法和Max-Min的缺點的改進算法，Mao等人提出了利用任務(wù)狀態(tài)表預(yù)測虛擬機實時負載和任務(wù)預(yù)計完成時間來動態(tài)調(diào)度任務(wù)[1]，這種方法雖然能夠?qū)崿F(xiàn)較好的負載均衡，但是由于需要維持任務(wù)狀態(tài)表的實時更新，所以會使得開銷比較大，任務(wù)響應(yīng)時間偏長。Santhosh B等人提出了一種改進的Max-Min算法[4]，每次將任務(wù)集中的和平均任務(wù)長度最接近的任務(wù)分配給完成時間最短的任務(wù)。Upendra Bhoi等人提出一種增強型的Max-Min任務(wù)調(diào)度算法[5]，針對元任務(wù)集中大任務(wù)數(shù)很少而小任務(wù)很多的情況，提出了一種將最大任務(wù)優(yōu)先調(diào)度到執(zhí)行速度最慢的資源上。O.M.Elzeki等人提出一種改進 Max-Min算法[6]，針對小型云計算環(huán)境下，將最大執(zhí)行時間的任務(wù)分配給最小完成時間的任務(wù)。鄭莉等人提出一種基于用戶優(yōu)先級的負載均衡算法[7]，該算法針對Min-Min算法進行改進，一開始用Min-Min算法進行任務(wù)分配處理，然后選擇負載較重的資源進行資源的重新分配，觀察負載重資源上的最短任務(wù)，并計算它在其他資源上的完成時間，如果小于任務(wù)跨度，那么將此任務(wù)從最終負載上移除，用其他資源進行處理。

上述介紹的種種算法，雖然在原有算法的基礎(chǔ)上做出了一些改進，但是由于大都在特定的仿真環(huán)境下，比如說增強的Max-Min算法，作者給出的實驗數(shù)據(jù)是長任務(wù)很少，而短任務(wù)很多的情形，所以所得結(jié)果會比原有算法性能更優(yōu)，但是考慮到云環(huán)境下任務(wù)的動態(tài)特點，所以這些算法沒有較強的適應(yīng)能力?；诂F(xiàn)有算法的局限性，提出了一種基于任務(wù)類型匹配的資源調(diào)度策略(TTM)，在此調(diào)度策略下通過與用單一使用Max-Min或者Min-Min算法相比較，驗證了此算法在任務(wù)動態(tài)環(huán)境下具有較好的效果。

2 云環(huán)境下負載調(diào)度模型

2.1 負載均衡任務(wù)調(diào)度模型

負載均衡是云計算的主要問題之一，負載可以是內(nèi)存、CPU處理能力、網(wǎng)絡(luò)或者是時延負載[8]。它需要在不同的節(jié)點之間共享工作負載，從而提高資源利用率和系統(tǒng)的性能。本文通過深入分析了Max-Min算法和Max-Min 算法的優(yōu)缺點和所使用的場景，設(shè)計了一個新的調(diào)度策略，根據(jù)任務(wù)集中的任務(wù)長度分布情況來調(diào)用相應(yīng)的算法，調(diào)度模型如圖1所示。

圖1 負載均衡調(diào)度模型

此調(diào)度過程為，首先用戶提交任務(wù)，通過作業(yè)管理器管理用戶提交的任務(wù)，計算任務(wù)所需要的性能要求和其他的一些因素限制，運用不同的負載均衡算法將任務(wù)分配給不同的虛擬機去執(zhí)行，當(dāng)然這里的虛擬機是在物理服務(wù)器中創(chuàng)建的，所以考慮的是物理服務(wù)器的負載。

2.2 任務(wù)類型匹配負載均衡算法設(shè)計

云計算環(huán)境下由于任務(wù)的大小不一，云計算數(shù)據(jù)中心各節(jié)點的處理能力也不同，所以負載的的定義很復(fù)雜[9]，為了簡化起見，做了2點假設(shè)。

1)各任務(wù)之間是獨立的，互相之間沒有依賴關(guān)系；

2)虛擬機的處理能力只考慮他的執(zhí)行速度(MIPS)，沒有考慮帶寬和內(nèi)存等其他因素。為了描述模型的方便，先做一些相關(guān)定義。

定義1：任務(wù)執(zhí)行時間(TET)。

任務(wù)執(zhí)行時間是一個任務(wù)在某個資源節(jié)點上的處理時間，假設(shè)任務(wù)i的長度為lengthi，虛擬機j的執(zhí)行速度為MIPSj，那么任務(wù)i在虛擬機j上的執(zhí)行時間為

Tij=lengthi/MIPSj

(1)

定義2：任務(wù)預(yù)期完成時間(TCT)。

任務(wù)預(yù)期完成時間是任務(wù)在考慮分配給哪個虛擬機時要考慮的問題，看看任務(wù)在哪個虛擬機上能最快處理完成，即為準(zhǔn)備時間，放在處理能力最強的虛擬機上完成時間不一定短，這個和執(zhí)行時間不同。它等于開始執(zhí)行的時間BETij加上Tij。

TCTij=BETij+Tij

(2)

定義3：平均資源利用率和時間跨度。

資源利用率表示為所有虛擬機在整個任務(wù)處理過程中的資源平均利用率

(3)

(4)

Makespan=max(TCTij)

(5)

定義4：集中任務(wù)預(yù)期完成時間標(biāo)準(zhǔn)差。

由于各個任務(wù)之間是獨立的，所以標(biāo)準(zhǔn)差計算公式為

(6)

定義5：負載均衡度。

負載均衡度定義為各個虛擬機之間負載量的差別程度，用β表示

(7)

(8)

式中：m表示虛擬機的個數(shù)；S表示資源利用率的標(biāo)準(zhǔn)方差，當(dāng)S越小是表明負載均衡度越高。

2.3 策略執(zhí)行過程

對于到達的一批假設(shè)任務(wù)集為T{t1,t2,t3,…，tm},他們的長度分別為length1,length2，…，lengthn，首先將到達的任務(wù)集中的任務(wù)按照長度進行升序或者降序排列，為了討論方便假設(shè)為降序，在排好序的任務(wù)中找到連續(xù)幾個值大于SD的地方，通過此方法可以找到任務(wù)長度明顯變化的地方，記為Po，所以對于任務(wù)集中的任務(wù)分布可能有如下3種情形：

1)情形1，即如果Po

2)情形2，即如果Po>S/2,那么說明短任務(wù)數(shù)小于長任務(wù)數(shù)，此時應(yīng)用Min-Min算法效果比較好些。

3)情形3，即如果任務(wù)長度間的差值沒有大于SD,說明任務(wù)之間的長度都差不多，此時選擇Min-Min算法處理下個任務(wù)，算法流程圖如圖2所示。

3 實驗仿真結(jié)果及分析

為了驗證本算法的有效性，采用CloudSim 3.0軟件進行仿真實驗，這是一款由澳大利亞墨爾本大學(xué)開發(fā)的云計算仿真工具，主要考察兩個指標(biāo)：任務(wù)總執(zhí)行時間(Makespan)和負載均衡度(Load Balancing Level)，實驗表明提出的算法優(yōu)于單一采用Max-Min算法和Min-Min算法。

針對上述3種情形進行仿真實驗，仿真中將資源數(shù)定位取10，一批任務(wù)的數(shù)量為1 000，剛開始任務(wù)是長度隨機排列的，任務(wù)到達由泊松隨機過程建模。仿真結(jié)果如圖3、圖4所示。

通過圖3中的3種情形得比較可以看出，提出的算法在3種情形下均具有較短的時間跨度，情形1中由于有許多的段任務(wù)，而長任務(wù)量很少，多虛擬機并發(fā)執(zhí)行的時間短，所以用Max-Min 算法耗時比較長，而此時用Max-Min

圖2 任務(wù)類型匹配負載均衡調(diào)度算法

圖3 總執(zhí)行時間

圖4 負載均衡度β

算法效果比較好。情形2恰好相反，短任務(wù)很少，長任務(wù)多，此時應(yīng)用 Max-Min 算法就沒有什么優(yōu)勢。情形3中子任務(wù)之間的長度差別很小，所以用Max-Min 算法執(zhí)行時間也較短。

同樣以上3種仿真情形中使用TTM算法均具有較好的負載均衡效果，由于Max-Min算法的負載均衡效果本身要優(yōu)于Min-Min算法，特別是當(dāng)短任務(wù)很少、長任務(wù)多的情形。因此對于以上3種情形的負載均衡水平采用TTM算法會具有較好的性能。

4 結(jié)束語

本文主要針對云計算環(huán)境中的負載均衡問題進行了研究，在深入分析當(dāng)前的兩種經(jīng)典的啟發(fā)式負載均衡算法基礎(chǔ)上，通過比較他們的優(yōu)缺點，提出一種基于任務(wù)類型匹配的負載均衡算法，并通過CloudSim 云仿真環(huán)境驗證了此算法的可行性，提出的算法不僅加快了系統(tǒng)響應(yīng)時間而且有效地平衡了虛擬機之間的負載，提高了用戶的服務(wù)質(zhì)量。由于研究工作是在已有的負載均衡算法上做的調(diào)度策略創(chuàng)新，而不是在原有的算法上做的改進，而且對于任務(wù)調(diào)度有較多因素沒有考慮，比如通信的開銷、執(zhí)行任務(wù)的花費等，所以這也會是下一步的研究工作。

[1] MAO Y，CHEN X，LI X. Max-min task scheduling algorithm for load balance in cloud computing[C]//Proc. International Conference on Computer Science and Information Technology.[S.l.]：Springer India，2014：457-465.

[2] KANAKALA R, REDDY V K. Performance analysis of load balancing techniques in cloud computing environment[J]. Telkomnika Indonesian Journal of Electrical Engineerin，2015，13(3)：568 - 573.

[3] 蘇淑霞. 面向云計算的任務(wù)調(diào)度算法研究[J]. 安徽大學(xué)學(xué)報：自然科學(xué)版，2014，38(5)：24-30.

[4] SANTHOSH B. MANJAIAH D H.An improved task scheduling algorithm based on Max-Min for cloud computing[C]//Proc. International Conference on Advances in Computer & Communication Engineering. Bengaluru，India： IJIRCCE，2014：84-88.

[5] BHOI U, RAMANUJ P N. Enhanced Max-Min task scheduling algorithm in cloud computing[J]. International Journal of Application or Innovation in Engineering & Management (IJAIEM)，2013，2(4)： 259-264.

[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] 鄭莉.云計算環(huán)境下資源調(diào)度關(guān)鍵技術(shù)研究[D]. 北京：北京郵電大學(xué)，2014.

[8] KHERANI F, VANIA J. Load balancing in cloud computing[J]. International Journal of Engineering Development and Research(IJEDR)，2014，12(1)：907-912.

[9] 郭平，李濤，李琪. 一種云計算環(huán)境下的負載調(diào)度算法[J]. 系統(tǒng)工程理論實踐，2014，34(S1)：269-275.

葛 兵(1991— )，碩士，主研云計算、負載均衡；

方義秋(1963— )，女，副教授，主要研究方向為云計算、軟件工程等。

責(zé)任編輯：許 盈

Task Scheduling Strategy Based on Load Balancing in Cloud Computing Environment

GE Junwei,GE Bing ,FANG Yiqiu

(CollegeofCommunicationandInformationEngineering，ChongqingUniversityofPostsandTelecommunications，Chongqing400065，China)

According to the load imbalance problem of a large number of parallel computing nodes under the cloud computing environment, in this paper, a novel load balance scheme based on task type matching is proposed .This scheme focus on the judgement of task type among multiple different lengths of the subtasks, and an analysis is done on the advantages and disadvantages of two kinds of heuristic load balancing algorithms named Max-Min and Min-Min. Then, task scheduling with different algorithm is executed according to the type of the task set. The experimental results show that the proposed scheme has better load balancing features and shorter completion time than only using the algorithm of Max-Min or Min-Min

cloud computing; task scheduling; load balancing; Max-Min; Min-Min

重慶市教委科學(xué)技術(shù)研究項目(KJ130533)

TP391.1

A

10.16280/j.videoe.2015.19.011

葛君偉(1961— )，教授，博士，主要研究方向為云計算、 軟件體系結(jié)構(gòu)、電信管理網(wǎng)等；

2015-04-27

【本文獻信息】葛君偉，葛兵，方義秋.云環(huán)境下一種基于負載均衡的任務(wù)調(diào)度策略[J].電視技術(shù),2015，39(19).