基于改進蟻群算法的云計算任務(wù)調(diào)度模型

魏 赟,陳元元

(上海理工大學(xué)光電信息與計算機工程學(xué)院,上海200093)

基于改進蟻群算法的云計算任務(wù)調(diào)度模型

魏 赟,陳元元

(上海理工大學(xué)光電信息與計算機工程學(xué)院,上海200093)

為解決云環(huán)境下的資源調(diào)度問題,提出一種能改善任務(wù)并行性與兼顧任務(wù)串行關(guān)系的調(diào)度模型,將用戶提交的動態(tài)任務(wù)分割成具有制約關(guān)系的子任務(wù),按運行次序放到具有不同優(yōu)先級的調(diào)度隊列中。針對同一調(diào)度隊列中的子任務(wù),采用基于最短任務(wù)延遲時間的改進蟻群算法(DSFACO)進行調(diào)度,在兼顧調(diào)度公平性與效率的前提下,最大化縮短任務(wù)延遲時間,從而提高用戶滿意度。實驗結(jié)果表明,與任務(wù)調(diào)度增強蟻群算法相比,DSFACO算法在任務(wù)延遲時間、調(diào)度公平性及效率方面性能更好,能實現(xiàn)云計算環(huán)境下任務(wù)的最優(yōu)調(diào)度。

云計算;蟻群算法;任務(wù)調(diào)度;公平性;任務(wù)延遲時間

1 概述

云計算采用服務(wù)的方式為用戶提供動態(tài)虛擬化資源池[1],可以將用戶提交的任務(wù)分配給分布式計算機資源池進行合理調(diào)度。在云環(huán)境下采用何種任務(wù)管理和調(diào)度算法,使任務(wù)延遲時間最短、用戶滿意度最高,將會直接影響云平臺的效率與性能。云環(huán)境下的任務(wù)按照任務(wù)間有無輸入輸出關(guān)系分為2種:串行任務(wù)和并行任務(wù)。對于串行任務(wù)的調(diào)度,必須按照任務(wù)間的輸入輸出關(guān)系進行有序調(diào)度,文獻[2]提出一種基于路徑優(yōu)先級的任務(wù)調(diào)度算法,文獻[3]提出一種搶占式多有向無環(huán)圖(DAG)工作流動態(tài)調(diào)度策略來保證調(diào)度的公平性,但是它們都沒有對算法效率問題進行考慮。為提高云平臺上任務(wù)調(diào)度的效率,越來越多的智能優(yōu)化算法被應(yīng)用到并行任務(wù)的調(diào)度,蟻群優(yōu)化(Ant Colony Optimization, ACO)算法是一種動態(tài)的隨機搜索算法[4],特別是在動態(tài)環(huán)境中,可以表現(xiàn)出高靈活性和健壯性,用于解決許多系統(tǒng)組合優(yōu)化問題,因此,ACO算法非常適合于解決云環(huán)境下具有并行關(guān)系的任務(wù)調(diào)度問題。近年來很多學(xué)者用ACO算法來解決NP hard問題,如:旅行商問題,任務(wù)調(diào)度問題[5-6]和車輛路徑問題等。文獻[7]在云環(huán)境下提出基于Qos的作業(yè)調(diào)度算法,文獻[8]提出云環(huán)境下的最優(yōu)調(diào)度策略,文獻[9]提出云環(huán)境下實現(xiàn)最優(yōu)資源分配的方法,文獻[10]在云環(huán)境下提出基于改進蟻群算法的調(diào)度算法,文獻[11]在云環(huán)境下提出基于改進遺傳算法的調(diào)度算法,文獻[12]提出云環(huán)境下滿足Multi-QoS需求的調(diào)度算法,但是上述算法均沒有兼顧完成時間最短和用戶公平性問題。

本文基于云計算平臺和任務(wù)類型的特點,針對云環(huán)境下并行任務(wù)調(diào)度模型,將計算任務(wù)分割成小粒度子任務(wù),對于有串行制約關(guān)系的任務(wù),將其放入不同優(yōu)先級別的調(diào)度隊列中等待調(diào)度;對于可以并行運行的子任務(wù),提出一種基于最短任務(wù)延遲時間的改進蟻群算法(Delay Time Shortest and Fairness Ant Colony Optimization,DSFACO)。

2 云環(huán)境下的并行調(diào)度模型

目前,云環(huán)境下的任務(wù)調(diào)度大多采用Google提出的MapReduce分布式計算編程模型,如文獻[13]中在云環(huán)境下提出一種改進型MapReduce模型。將用戶所提交的任務(wù)劃分成多個Map任務(wù)和多個Reduce任務(wù)并行處理,大致分為2個階段:Map階段和Reduce階段。在Map階段,把用戶所提交的任務(wù)分成M片,并將其分給多個計算節(jié)點并行執(zhí)行,然后將處理后的文件輸出。在Reduce階段,對Map階段輸出的結(jié)果進一步匯總處理,輸出最后的處理結(jié)果并提交給用戶。因為云環(huán)境中任務(wù)具有大規(guī)模性和動態(tài)性等特點,任務(wù)和計算資源的數(shù)量是非常大的,系統(tǒng)每時每刻都要對海量用戶所提交的任務(wù)進行處理,所以在MapReduce分布式計算編程模型下,如何對大量任務(wù)進行合理高效調(diào)度是決定云計算效率的重點和難點,不恰當(dāng)?shù)娜蝿?wù)調(diào)度方法將會增加任務(wù)執(zhí)行時間,降低整個云的性能和用戶滿意度。

2.1 模型定義

在云環(huán)境中,當(dāng)用戶所提交申請計算資源的任務(wù)非常緊急,而云計算資源管理平臺不能盡快向其分配計算資源,逐漸將會導(dǎo)致云計算資源利用率降低、用戶滿意度下降,因此本文主要研究對用戶所提交的緊急任務(wù)劃分和調(diào)度。

任務(wù)集合和調(diào)度集合定義如下:用戶提交的任務(wù)集合記為T={T1,T2,…,TM},調(diào)度等待隊列集合記為Q={Q1,Q2,…,QN},對任務(wù)進行MapReduce處理后,子任務(wù)定義為tijk,其中,i為任務(wù)編號,1≤i≤M;j為調(diào)度隊列編號,1≤j≤N;k為可并行子任務(wù)編號,k=1,2,…。對于調(diào)度次序為ti1的調(diào)度優(yōu)先級高于ti2,對于同一個調(diào)度隊列中的任務(wù)tij1,tij2,…,tijk可并行調(diào)度。

2.2 調(diào)度模型基本原理

調(diào)度步驟具體如下:

Step 1將用戶提交的任務(wù)運用MapReduce模型劃分為更小的子任務(wù),將具有制約或并行關(guān)系的子任務(wù)放入具有不同優(yōu)先級的調(diào)度隊列中,如圖1所示。

圖1 調(diào)度次序劃分

Step 2從優(yōu)先級最高的調(diào)度隊列開始調(diào)度,當(dāng)隊列中所有子任務(wù)調(diào)度完畢后,依次調(diào)度后續(xù)任務(wù)隊列,以保證子任務(wù)之間的制約關(guān)系。對于同一隊列中的子任務(wù),按本文所設(shè)計的DSFACO算法選擇調(diào)度對象。

Step 3任務(wù)的所有子任務(wù)全部調(diào)度完畢后,結(jié)束該任務(wù)并將結(jié)果返回給用戶。

由于相同調(diào)度隊列中的子任務(wù)相互獨立,且云計算資源可采用相同的調(diào)度算法對每個隊列進行調(diào)度,因此本文以任務(wù)延遲時間最短為目標,對ACO算法進行改進,主要研究如何對調(diào)度等待隊列中的子任務(wù)進行高效調(diào)度,最大限度提高云平臺效率及用戶的滿意度。

3 基于改進蟻群優(yōu)化算法的子任務(wù)調(diào)度

標準蟻群優(yōu)化算法是受生物進化的啟發(fā),對自然界真實蟻群進行模擬后所提出的一種仿生優(yōu)化算法,具有并行性、魯棒性和正反饋性等優(yōu)點,但該算法的隨機性很大,在解決大規(guī)模優(yōu)化問題時很容易陷入局部最優(yōu),導(dǎo)致算法效率很低。因此,考慮到實際應(yīng)用中的效率與公平問題對ACO算法進行如下改進:以任務(wù)延遲時間最短為目標建立數(shù)學(xué)函數(shù)來解決效率問題;將向計算資源提出請求的用戶參數(shù)作為公平因子引入到ACO算法中來解決任務(wù)分配公平性問題,并對任務(wù)被選擇概率進行改進。

3.1 改進蟻群算法的設(shè)計

為便于計算,重新對調(diào)度等待隊列Qk中的子任務(wù)進行標記Qk={q1,q2,…,qm},云計算資源集合表示為A={a1,a2,…,an},任務(wù)qi的預(yù)開始處理時間和實際開始處理時間分別記為EDT(qi),ADT(qi),任務(wù)調(diào)度時間窗為st。

(1)目標函數(shù)建立

為實現(xiàn)調(diào)度隊列中的子任務(wù)高效調(diào)度,使得任務(wù)延遲時間最短,建立以下目標函數(shù):

(2)啟發(fā)式因子設(shè)置

將任務(wù)處理時間與任務(wù)完成時間作為2個啟發(fā)式因子。

(3)客戶公平因子的引入

將向計算資源提出請求的用戶參數(shù)引入到ACO算法中,用N(ci)表示用戶ci的待處理任務(wù)數(shù)量;η3(qi)表示任務(wù)qi的公平因子;F(ci)表示任務(wù)qi所屬用戶ci的公平因子;β3表示啟發(fā)函數(shù)η3(qi)相對重要性的期望啟發(fā)式因子,β3越大,公平因子對任務(wù)被選中概率的影響越大。

其中,K1為一固定常數(shù),用于調(diào)節(jié)客戶公平因子的大小。

(4)任務(wù)啟發(fā)式因子更新

當(dāng)任務(wù)qi被選擇安排計算資源后,該任務(wù)所屬用戶ci的任務(wù)啟發(fā)式因子更新為:

(5)任務(wù)被選擇的概率

在本次迭代中若任務(wù)qi所屬用戶已經(jīng)被分配計算資源,則此用戶ci其他任務(wù)的公平因子應(yīng)該按比例降低,這樣可以對其他用戶的任務(wù)進行分配計算資源:

其中,x表示調(diào)度隊列中任務(wù)的被調(diào)度次序;τix為表示信息素的參數(shù);allowed表示目前尚未分配處理的任務(wù)集合中與計算資源類型匹配的所有任務(wù)。

(6)信息素更新

式(7)表示任務(wù)在本次調(diào)度中剩余的信息素,K2為信息素增強系數(shù),式(8)表示每次qi更新信息素時的積累方式。

3.2 改進蟻群算法的實現(xiàn)步驟

改進蟻群算法的具體步驟如下:

Step 1變量初始化:對輸入?yún)?shù)進行初始化,云計算資源集合A,調(diào)度等待隊列Qk,最大迭代次數(shù)NI_MAX,信息啟發(fā)式因子α,期望啟發(fā)式因子β1,β2,信息素的揮發(fā)系數(shù)ρ,信息素的增強系數(shù)Q,時間窗的長度st。

Step 2單次迭代外層循環(huán):次序x累加,當(dāng)x＞s時,結(jié)束本層循環(huán),表示已全部將所有計算資源的可用時間分配給各項任務(wù),執(zhí)行Step6;否則執(zhí)行Step3。

Step 3單次迭代內(nèi)層循環(huán):計算資源aj→aj+1依次執(zhí)行,每個計算資源依次處理滿足條件的各類任務(wù),當(dāng)j＞l1+l2+…+ln時,執(zhí)行Step2;否則執(zhí)行Step4。

Step 4根據(jù)式(6)計算任務(wù)被選擇的概率。

Step 5調(diào)度隊列的修改:調(diào)度隊列為n行、s列的矩陣,計算資源每次選擇完畢后即對調(diào)度隊列進行修改,然后執(zhí)行Step3。

Step 6根據(jù)式(7)、式(8)進行信息素更新,更新后繼續(xù)執(zhí)行Step7。

Step 7迭代,終止條件:NI→NI+1,當(dāng)NI＞NI_MAX,且任務(wù)完成時間連續(xù)60次無變化,跳出循環(huán)。

4 仿真實驗結(jié)果與分析

為評價和分析本文DSFACO算法的性能,在云計算模擬平臺CloudSim中,通過改寫Datacenter-Broker類中的bindCloudletToVm方法,添加基于DSFACO的調(diào)度算法,并且使用Ant工具對平臺進行重新編譯,從而將基于DSFACO的任務(wù)調(diào)度算法加入到模擬平臺的任務(wù)單元調(diào)度中,進行模擬實驗。同理,對文獻[10]中的增強蟻群算法TS-EACO進行相同的環(huán)境配置。

根據(jù)參數(shù)調(diào)整原則和大量數(shù)據(jù)實驗,確定DSFACO的參數(shù)設(shè)置如下:α=10,β1=10,β2=0.5,β3=10,ρ=0.01,NI_MAX=500,st=40 min,計算資源的計算能力和任務(wù)數(shù)量用Matlab隨機產(chǎn)生,且假設(shè)子任務(wù)編號為0～9之間的隨機數(shù),其中,0～2為調(diào)度級別1;3～6為調(diào)度級別2;7～9為調(diào)度級別3。在此實驗數(shù)據(jù)條件下,分別仿真待調(diào)度任務(wù)數(shù)Task=50,100,200 3種情況。最后對DSFACO與TS-EACO算法的調(diào)度結(jié)果進行對比分析。

當(dāng)調(diào)度任務(wù)數(shù)為50時,用戶被安排調(diào)度任務(wù)數(shù)量如表1所示。

表1 用戶調(diào)度的任務(wù)數(shù)量(Task=50)

可以看出,TS-EACO調(diào)度結(jié)果中,用戶d的任務(wù)調(diào)度數(shù)量為0,說明資源管理平臺并沒有向其分配計算資源,從而其緊急任務(wù)無法及時被調(diào)度,導(dǎo)致任務(wù)調(diào)度不公平、用戶滿意度急劇下降。本文所設(shè)計的DSFACO算法的調(diào)度任務(wù)數(shù)量不會出現(xiàn)上述情況,每個用戶都相對公平地得到任務(wù)處理機會。任務(wù)最短延遲時間對比如圖2所示,通過TS-EACO計算后,任務(wù)的延遲時間約為280 min,迭代次數(shù)為25次左右;而DSFACO的任務(wù)延遲時間約為250 min,迭代次數(shù)50次左右,從結(jié)果可知,雖然DSACO的任務(wù)延遲時間僅略小于TS-EACO,但DSACO其在保證公平性的前提下在效率方面要好于TS-EACO算法,延遲時間優(yōu)化了大約30 min。

圖2 任務(wù)延遲時間(Task=50)

當(dāng)被調(diào)度任務(wù)數(shù)增多到100時,DSFACO和TSEACO的任務(wù)延遲時間對比如圖3所示,可以看出TS-EACO算法的收斂速度很快,但是其任務(wù)延遲時間比DSFACO算法多了大約50 min,相比于任務(wù)數(shù)為50的任務(wù)延遲時間(30 min)又多了20 min。當(dāng)被調(diào)度任務(wù)數(shù)量繼續(xù)增加到200時,從圖4可以看出,2種算法所得調(diào)度結(jié)果的任務(wù)延遲時間差距達到110 min。隨著被調(diào)度數(shù)量的增加,本文所設(shè)計的DSFACO算法進行的任務(wù)調(diào)度得到了任務(wù)延遲時間更小的調(diào)度結(jié)果,該算法能充分利用云計算資源進行更加合理的資源調(diào)度,獲得更高的資源利用率,提高了任務(wù)調(diào)度的效率。

圖3 任務(wù)延遲時間(Task=100)

圖4 任務(wù)延遲時間(Task=200)

通過圖5可知,使用DSFACO算法在云環(huán)境中對用戶提交的任務(wù)進行調(diào)度,在保證任務(wù)調(diào)度公平性的前提下,有效縮短了任務(wù)延遲時間,提高了用戶滿意度,而且隨著調(diào)度任務(wù)數(shù)量的增加,其綜合調(diào)度優(yōu)勢越來越明顯,任務(wù)延遲時間差距越來越大。

圖5 算法任務(wù)延遲時間對比

從以上實驗結(jié)果可知,雖然TS-EACO算法的任務(wù)延遲時間能達到較短,但本文所設(shè)計的DSFACO算法不但能保證任務(wù)分配的公平性,而且其任務(wù)完成時間、效率、用戶滿意度等方面都優(yōu)于TS-EACO算法,進一步驗證DSFACO算法能有效解決云環(huán)境下的調(diào)度問題。

5 結(jié)束語

本文提出一種基于改進蟻群算法的并行任務(wù)調(diào)度模型。將用戶提交的動態(tài)任務(wù)分割成具有相互制約關(guān)系的子任務(wù),并將其按運行次序放入具有不同優(yōu)先級的調(diào)度隊列中。采用基于最短任務(wù)延遲時間和任務(wù)分配公平的改進蟻群算法DSFACO,對同一個調(diào)度隊列中的子任務(wù)進行調(diào)度。DSFACO算法以縮短任務(wù)延遲時間為目標研究子任務(wù)的調(diào)度問題。通過Cloudsim平臺對比分析了DSFACO算法與TSEACO算法,實驗結(jié)果表明DSFACO算法綜合性能優(yōu)于TS-EACO算法,更加適應(yīng)云計算環(huán)境。下一步工作的重點是在保證DSFACO算法具有最短任務(wù)延遲時間的同時降低總計算成本。

[1] Armbmst M,Fox A,Griffith R,et al.Above the Clouds: A Berkeley View of Cloud Computing[R].University of California,Berkeley,Technical Report:UCB/EECS-2009-28,2009.

[2] 祝家鈺,肖 丹.云環(huán)境下基于路徑優(yōu)先級的任務(wù)調(diào)度算法[J].計算機工程與設(shè)計,2013,34(10): 3511-3515.

[3] 孫 月,于 炯,朱建波.云計算中一種多DAG工作流可搶占式調(diào)度策略[J].計算機科學(xué),2014,41(3): 145-148.

[4] Dorigo M,Blum C.Ant Colony Optimization Theory:A Survey[J].TheoreticalComputerScience,2005, 344(2/3):243-278.

[5] Gao Y.A Multi-objective Ant Colony System Algorithm for Virtual Machine Placement in Cloud Computing[J]. Journal of Computer and System Sciences,2013,79(8): 1230-1242.

[6] Dorigo M,BirattariM,StutzelT.AntColony Optimization[J].IEEEComputationalIntelligence Magazine,2006,1(4):28-39.

[7] Huang Qiyi,HuangTinglei.AnOptimisticJob Scheduling Strategy Based on QoS for Cloud Computing[C]//Proceedings of 2010 IEEE International Conference on Intelligent Computing and Integrated Systems.[S.l.]:IEEE Press,2010:673-675.

[8] Sanyal M G.Survey and Analysis of Optimal Scheduling Strategies in Cloud Environment[C]//Proceedings of IEEEInternationalConferenceonInformationand Communication Technologies.[S.l.]:IEEE Press, 2012:789-792.

[9] Chang F,Ren J,Viswanathan R.Optimal Resource Allocation in Clouds[C]//Proceedings of the 3rd International Conference on Cloud Computing.[S.l.]: IEEE Press,2010:418-425.

[10] 查華英,楊靜麗.改進蟻群算法在云計算任務(wù)調(diào)度中的應(yīng)用[J].計算機工程與設(shè)計,2013,34(5): 1716-1726.

[11] 李建峰,彭 艦.云計算環(huán)境下基于改進遺傳算法的任務(wù)調(diào)度算法[J].計算機應(yīng)用,2011,31(1):184-186.

[12] Dutta D,Joshi R C.A Genetic:Algorithm Approach to Cost-basedMulti-QoSJobSchedulinginCloud Computing Environment[C]//Proceedings of International Conference and Workshop on Emerging Trends in Technology.Mumbai,India:ACMPress,2011: 422-427.

[13] 李 震,杜中軍.云計算環(huán)境下的改進型Map-Reduce模型[J].計算機工程,2012,38(11):27-29,37.

編輯 陸燕菲

Cloud Computing Task Scheduling Model Based on Improved Ant Colony Algorithm

WEI Yun,CHEN Yuanyuan
(School of Optical-electrical and Computer Engineering, University of Shanghai for Science and Technology,Shanghai 200093,China)

To solve the problem of resource scheduling problem in cloud computing,a parallel scheduling model is proposed,which can improve the task parallelism while maintaining the serial relationships between tasks.Dynamic tasks submitted by users are divided into sub-tasks in some serial sequences,and it puts into scheduling queue with different priorities according to running order.For these tasks in the same priority scheduling queue,an improved Delay Time Shortest and Fairness Ant Colony Optimization(DSFACO)algorithm is applied to schedule.Considering both fairness and efficiency,DSFACO algorithm applies to subtask scheduling problem to realize shortest delay time,thus improves the user satisfaction.Experimental results show DSFACO algorithm is better than the TS-EACO algorithm in fairness, efficiency and task delay time,and it can realize the optimal scheduling in cloud computing.

cloud computing;ant colony algorithm;task scheduling;fairness;task delay time

魏 赟,陳元元.基于改進蟻群算法的云計算任務(wù)調(diào)度模型[J].計算機工程,2015,41(2):12-16.

英文引用格式:Wei Yun,Chen Yuanyuan.Cloud Computing Task Scheduling Model Based on Improved Ant Colony Algorithm[J].Computer Engineering,2015,41(2):12-16.

1000-3428(2015)02-0012-05

:A

:TP393

10.3969/j.issn.1000-3428.2015.02.003

國家自然科學(xué)基金資助項目(61170277);上海市教委科研創(chuàng)新基金資助項目(12YZ094)。

魏 赟(1976-),女,副教授、博士,主研方向:云計算,智能交通控制,分布式系統(tǒng);陳元元(通訊作者),碩士。

2014-05-27

:2014-07-26E-mail:chenyuanyuanzhang@163.com