基于改進蟻群算法的云計算任務調度模型

魏 赟,陳元元

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

基于改進蟻群算法的云計算任務調度模型

魏 赟,陳元元

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

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

云計算;蟻群算法;任務調度;公平性;任務延遲時間

1 概述

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

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

2 云環境下的并行調度模型

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

2.1 模型定義

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

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

2.2 調度模型基本原理

調度步驟具體如下:

Step 1將用戶提交的任務運用MapReduce模型劃分為更小的子任務,將具有制約或并行關系的子任務放入具有不同優先級的調度隊列中,如圖1所示。

圖1 調度次序劃分

Step 2從優先級最高的調度隊列開始調度,當隊列中所有子任務調度完畢后,依次調度后續任務隊列,以保證子任務之間的制約關系。對于同一隊列中的子任務,按本文所設計的DSFACO算法選擇調度對象。

Step 3任務的所有子任務全部調度完畢后,結束該任務并將結果返回給用戶。

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

3 基于改進蟻群優化算法的子任務調度

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

3.1 改進蟻群算法的設計

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

(1)目標函數建立

為實現調度隊列中的子任務高效調度,使得任務延遲時間最短,建立以下目標函數:

(2)啟發式因子設置

將任務處理時間與任務完成時間作為2個啟發式因子。

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

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

其中,K1為一固定常數,用于調節客戶公平因子的大小。

(4)任務啟發式因子更新

當任務qi被選擇安排計算資源后,該任務所屬用戶ci的任務啟發式因子更新為:

(5)任務被選擇的概率

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

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

(6)信息素更新

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

3.2 改進蟻群算法的實現步驟

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

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

Step 2單次迭代外層循環:次序x累加,當x＞s時,結束本層循環,表示已全部將所有計算資源的可用時間分配給各項任務,執行Step6;否則執行Step3。

Step 3單次迭代內層循環:計算資源aj→aj+1依次執行,每個計算資源依次處理滿足條件的各類任務,當j＞l1+l2+…+ln時,執行Step2;否則執行Step4。

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

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

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

Step 7迭代,終止條件:NI→NI+1,當NI＞NI_MAX,且任務完成時間連續60次無變化,跳出循環。

4 仿真實驗結果與分析

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

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

當調度任務數為50時,用戶被安排調度任務數量如表1所示。

表1 用戶調度的任務數量(Task=50)

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

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

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

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

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

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

圖5 算法任務延遲時間對比

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

5 結束語

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

[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] 祝家鈺,肖 丹.云環境下基于路徑優先級的任務調度算法[J].計算機工程與設計,2013,34(10): 3511-3515.

[3] 孫 月,于 炯,朱建波.云計算中一種多DAG工作流可搶占式調度策略[J].計算機科學,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] 查華英,楊靜麗.改進蟻群算法在云計算任務調度中的應用[J].計算機工程與設計,2013,34(5): 1716-1726.

[11] 李建峰,彭 艦.云計算環境下基于改進遺傳算法的任務調度算法[J].計算機應用,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] 李 震,杜中軍.云計算環境下的改進型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

魏 赟,陳元元.基于改進蟻群算法的云計算任務調度模型[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

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

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

2014-05-27

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