李菡薏,陳家琪

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

云計算環(huán)境下任務調度算法的研究

李菡薏,陳家琪

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

在云計算環(huán)境中存在龐大的任務數,為了能更加高效地完成任務請求,如何進行有效地任務調度是云計算環(huán)境下實現按需分配資源的關鍵。針對調度問題提出了一種基于蟻群優(yōu)化的任務調度算法,該算法能適應云計算環(huán)境下的動態(tài)特性,且集成了蟻群算法在處理NP-Hard問題時的優(yōu)點。該算法旨在減少任務調度完成時間。通過在CloudSim平臺進行仿真實驗,實驗結果表明,改進后的算法能減少任務平均完成時間、并能在云計算環(huán)境下有效提高調度效率。

云計算;任務調度;蟻群算法

如今,越來越多的計算任務和服務都被引入進了云端,云計算也變得越來越受歡迎。云計算是分布式計算、并行計算、網格計算、效用計算、虛擬化、網絡存儲等傳統(tǒng)計算機和網絡技術發(fā)展融合的商業(yè)實現。云計算可以對共享可配置的計算資源進行方便的按需訪問,并且根據實際情況來進行按需分配,同時管理這些資源只需要通過極小的代價來進行管理,是一種基于互聯網的新型計算服務模式。而云計算平臺的核心技術之一便是調度,目前關于調度問題的研究尚處于初級階段,而現有的調度算法均存在著一些不足之處。而在云計算環(huán)境中,任務調度是一個NP完全問題[1],蟻群算法作為智能優(yōu)化算法,適合于求解NP類問題。但就目前業(yè)界內的研究成果來看,蟻群算法雖然在解決云計算調度問題時取得了較好的效果,但仍存在不足。比如蟻群算法雖具有較好的尋優(yōu)能力,但由于初始階段信息素匾乏,初期收斂速度較慢。因此,本文從最小化完成時間的角度優(yōu)化云計算環(huán)境的任務調度問題,通過對現有的蟻群算法進行優(yōu)化,以建立一個較優(yōu)的任務調度策略。

1 問題描述

1.1 云計算調度的概念

迄今為止,針對云計算的任務調度問題仍屬于一個比較前沿的課題。云計算的核心思想是將計算任務分布在大量由計算機組成的資源池上,使用戶能夠按需獲取計算能力、存儲空間和信息服務,但云中擁有的資源與要處理的任務均是海量的,因此如何充分利用云中資源對任務進行高效調度是云計算中的重點與難點。

云計算的核心服務通?？煞譃橐韵?個子層:

(1)IaaS(Infrastructure as a Service)層。該層是云計算的基礎,IaaS層通過建立大規(guī)模數據中心為上層的云計算服務提供大量的硬件資源。同時,IaaS層可在虛擬化技術的支持下,提供個性化的基礎設施服務來實現硬件資源的按需配置。

(2)PaaS(Platform as a Service)層。該層作為3層核心服務的中間層,作為平臺即服務層既可為上層應用提供簡單、可靠的分布式編程框架,但由于底層系統(tǒng)具有一定的復雜性,所以又需要基于底層的資源信息來管理數據、調度作業(yè)。隨著數據密集型應用的普及和數據規(guī)模的日益龐大,PaaS層需要具備存儲與處理海量數據的能力。

(3)SaaS(Software as a Service)層。該層面向的是云計算終端用戶,作為軟件即服務層其提供基于互聯網的軟件應用服務。隨著Web服務、HTML5、Ajax、Mashup 等技術的成熟與標準化,SaaS應用近年來發(fā)展迅速。

雖然這3個云計算的核心服務層分別側重于不同的應用,但其仍存在著資源、任務調度問題。調度問題是云計算中的一個重要問題,直接影響到資源的使用效率、云服務的穩(wěn)定性、運營成本和用戶的滿意程度。因此云計算的研究一直側重于調度方面,無論是從理論技術還是實際應用方面都具有重要的研究價值[2]。

1.2 蟻群算法

云計算調度問題的研究重點就是性能,以調度性能作為最終目標,一般都以最短完成時間、系統(tǒng)效率等作為衡量算法優(yōu)劣的標準。目前研究和使用較為廣泛的算法包括Min-Min算法、Max-Min算法、遺傳算法(GA)、蟻群算法、貪婪算法和模擬退火算法等。IBM云計算平臺采用的是以性能為中心的調度策略[3]。李建峰等人提出了一種以作業(yè)平均完成時間為標準的、基于Map Reduce模型的雙適性遺傳算法(DFGA)[4],湯小春等人提出了一種基于元區(qū)間的分配決策算法[5];華夏渝等人提出一種基于蟻群優(yōu)化(Ant Colony Optimization)的資源分配算法[6]。

將任務與資源按照一定的原則進行映射就是任務調度。云計算是指通過虛擬化技術將用戶的任務通過虛擬機處理,同時將資源以虛擬機的形式體現,這樣可簡化資源與任務的匹配,從而將分配資源的過程封裝為分配虛擬機的過程[7]。一個良好的任務調度算法,應根據環(huán)境或任務類型的變化來調整其調度策略[8]。在云計算中,優(yōu)秀的任務調度算法就是要求使用最少的寬帶需求、最小完成時間將任務分配給虛擬機。因此,像蟻群算法(ACO)這種動態(tài)的任務調度算法,更加適合解決云計算環(huán)境下的動態(tài)任務調度問題。ACO算法是一種隨機搜索算法[9],該算法使用了一種正反饋機制來模擬自然界螞蟻尋找食物的方法,當螞蟻在尋找食物時,每只螞蟻都會在其經過的路上分泌一種信息素(Pheromone),螞蟻群體之間通過這種信息素來達到互相進行交流、協作,最終在覓食過程中傾向尋找較短路徑。本文從最小化完成時間的角度提出基于蟻群算法的任務調度優(yōu)化算法JS-ACO,利用蟻群算法的自適應性等特點將其應用到云計算環(huán)境的任務調度中,通過為作業(yè)尋找最合適的從結點來減少網絡寬帶的消耗,能提高整個系統(tǒng)的吞吐量,較大程度地提高云計算環(huán)境的效率和性能。

2 算法描述

2.1 基于蟻群的作業(yè)調度算法

基于蟻群的作業(yè)調度算法具體描述如下:

步驟1 信息素參數初始化。將每條路徑上的信息素參數根據式(1)初始化

τ0=m×p

(1)

其中,m是虛擬機的個數;p是表示CPU的速度。

步驟2 任務轉移規(guī)則。為了構造一個完整的解決方案,螞蟻帶著未調度的任務將按照狀態(tài)轉移規(guī)則選擇下一步移動的位置,從而使一群螞蟻并行異步地訪問鄰近虛擬機。在t時刻螞蟻會根據式(2)和式(3),從當前的虛擬機i選擇下一個虛擬機m。

(2)

其中,τim(t)為t時刻從虛擬機i到虛擬機m的信息素強度;q是分布在[0,1]的隨機數;q0是一個參數(0≤q0≤1)。avoidk是螞蟻k的回避列表,S在t時刻根據式(3)狀態(tài)轉移概率選擇鄰近虛擬機

0,else

(3)

(4)

其中,ETjm(K+1)表示作業(yè)j到達虛擬機m的預測執(zhí)行時間[10];K+1表示作業(yè)執(zhí)行次數;ETjm(K)表示上次執(zhí)行作業(yè)的預測執(zhí)行時間;RTjm(K)表示上次執(zhí)行作業(yè)的實際執(zhí)行時間;ξ是一個經驗參數(0<ξ<1),表示上次作業(yè)的預測執(zhí)行時間和實際執(zhí)行時間對下一次預測作業(yè)執(zhí)行的影響度,用來調節(jié)在云計算中經驗值與預測值的比重

(5)

式中,TTjm表示作業(yè)j到達虛擬機m時的預測傳輸時間,其中Sj表示作業(yè)j的大小,bandwidthm表示虛擬機m的可用帶寬。

步驟3 局部信息素更新。當螞蟻k選擇了一個虛擬機之后,為衰減被選中路徑的信息素濃度,使螞蟻們對其他路徑的選擇以擴大搜索范圍避免了過早收斂,必須根據式(6)對信息素進行更新

τim=(1-ρ)×τim+ρτ0

(6)

其中,ρ(0<ρ<1)是一個參數,表示信息素蒸發(fā)因子。

步驟4 全局信息素更新。當所有螞蟻都已完成一次遍歷,按照式(7)更新本次遍歷中最佳路徑上的信息素

(7)

2.2 算法流程

基于蟻群優(yōu)化的云計算任務調度算法JS-ACO如下

ProcedureJS-ACO

Begin

初始化參數

While(未找到最優(yōu)解的停止條件)do

每個螞蟻開始活動

While(當每只螞蟻都完成構建解時停止)do

For每只螞蟻do

根據狀態(tài)轉移概率公式選擇下個虛擬機;

根據式(6)進行局部信息素更新;

Endfor

記錄此次迭代的最優(yōu)解;

對最優(yōu)解進行局部搜索;

根據式(7)進行全局信息素更新;

Endwhile

Endwhile

End

3 實驗與分析

3.1CloudSim

C1oudSim是墨爾本大學RajkumarBuyya教授領導的網格實驗室與Girdbus項目推出的云計算仿真平臺,用于云計算基礎設施和應用服務的建模、仿真和實驗,CloudSim的首要目標是在軟件、硬件、服務等云基礎設施上,對不同應用和服務模型的調度和分配策略的性能進行量化和比較,最終模擬云計算中資源[11]。在GridSim模型基礎上發(fā)展而來的C1oudSim能根據云計算的特性,模擬云計算環(huán)境下的資源管理和調度模擬。云計算的特點之一是虛擬化技術中資源,將這些資源虛擬化為資源池,打包對外向用戶提供服務。C1oudSim能恰好符合這個特點,其提供的擴展部分可對接口進行實現,能提供基于數據中心的虛擬化技術、虛擬化云的建模和仿真功能。在基于CloudSim云計算仿真器中用戶能夠反復測試自身的程序,在部署服務之前調節(jié)性能瓶頸,既能節(jié)約大量時間,又可以給開發(fā)工作帶來較大的便利。

3.2 仿真環(huán)境

表1 算法的仿真實驗環(huán)境

CloudSim采用分層設計特征及體系結構,圖1所示為分層的CloudSim體系結構圖。

圖1 分層的CloudSim體系結構圖

CloudSim的頂層是用戶代碼層,該層提供如主機、用戶、虛擬機、應用等一些基本實體,同時提供代理調度策略。通過擴展這些實體可使開發(fā)者在用戶代碼層開發(fā)各種應用調度技術,并執(zhí)行CloudSim支持的云配置的魯棒性測試。CloudSim的下層是為云計算的虛擬數據中心環(huán)境所設置的仿真層、并為仿真提供各種相應的接口。例如:虛擬機分配、CPU分配、內存分配、存儲空間分配及寬帶分配。下層的仿真層主要用于主機與虛擬機之間資源分配方面的策略研究,并通過擴展核心的虛擬機調度函數實現。

當開始一個仿真時,首先數據中心(DataCenter)創(chuàng)建資源后通過CIS(Cloud Information Service)注冊服務,然后CIS提供相關服務的匹配決策,由數據中心代理(DataCenterBroker)管理信息的交互過程。

C1oudSim提供了良好的云計算調度算法仿真平臺,C1oudSim中提供的bindCloudletToVm(int cloudletId,int vmId),DataCenterBroker類,通過對該類進行擴展,云應用開發(fā)人員可將任務分配到指定的虛擬機上執(zhí)行,實現自定義的調度策略,完成對自定義的調度算法進行模擬和測試。通過配置特定的環(huán)境來進行模擬云計算,最終達到模擬云計算環(huán)境下的開發(fā)測試目的。

圖2 CloudSim的仿真流程

3.3 算法仿真

算法的調度參數列表如表1、表2所示。

表2 調度參數列表

表3 參數列表

在實驗中α、β參數值的選取至關重要,參數與蟻群算法的性能是相掛鉤的,本次實驗設置α的初值為0.1,而β的值設置為2.0。信息素蒸發(fā)因子ρ取0.1,ants螞蟻的數量為20。由于蟻群算法是一個啟發(fā)式算法,為保證實驗結果的公平性,取10次實驗結果的平均值來與其他算法相比較,實驗結果如圖3所示。

圖3 任務執(zhí)行時間比較圖

在其他條件不變的情況下,將短任務改為長任務,任務執(zhí)行時間如圖4所示。

圖4 任務執(zhí)行時間比較圖

從實驗結果中可看出,JS-ACO算法的平均完成時間小于其他兩種算法,任務執(zhí)行的時間比傳統(tǒng)的Min-Min算法短,隨著任務數量的增加,算法的執(zhí)行時間差越來越大,優(yōu)化性能的提升越發(fā)明顯。究其原因,主要是因為改進后的蟻群算法可動態(tài)的跟蹤虛擬機的狀態(tài)。

4 結束語

由于任務調度是典型的NP-Hard問題,而蟻群算法成功解決了其他的NP問題,本文旨在優(yōu)化云計算環(huán)境下的任務調度問題,從最小化完成時間出發(fā)提出了改進后的ACO算法。該算法利用了蟻群算法的獨特性與云環(huán)境的特殊性,應用蟻群算法的正反饋機制來求得全局的近似最優(yōu)解,而不會像其他搜索算法那樣容易陷入局部最優(yōu)解。與此同時,應用信息素的揮發(fā)機制,通過更新信息素來指導螞蟻進行狀態(tài)轉移,對每次迭代產生的最優(yōu)解再進行局部搜索,最終得到合理的解決方案。實驗結果表明:通過改進后的算法可減少完成時間,提高系統(tǒng)效率。本文算法只考慮了任務調度過程中的任務數量,而在實際應用中情況比較復雜,還有更多因素需要考慮,比如對本文提出的蟻群算法進行其他的可能性測試如:任務數量繼續(xù)增多、數據中心不止一個等,再通過實驗結果分析本文實現的蟻群算法是否還存在其他的不足。另外還可考慮與其他算法結合,繼續(xù)優(yōu)化蟻群算法的性能。

[1]ThusooA,ShaoZ,AnthonyS,etal.Datawarehousingandanalyticsinfrastructureatfacebook[C].Indianapolis,Indiana:SIGMOD’10,ACM,2010.

[2] 左利云,曹志波.云計算中調度問題研究綜述[J].計算機應用研究,2012(11):4023-4027.

[3] 田文洪,趙勇.云計算:資源調度管理[M].北京:國防工業(yè)出版社,2011.

[4] 李劍鋒,彭艦.云計算環(huán)境下基于改進遺傳算法的任務調度算法[J].計算機應用,2011,31(1):184-186.

[5] 湯小春,劉健.基于元區(qū)間的云計算基礎設施服務的資源分配算法研究[J].計算機工程與應用,2010,46(34):237-241.

[6] 華夏渝,鄭駿,胡文心.基于云計算環(huán)境的蟻群優(yōu)化計算資源分配算法[J].華東師范大學學報:自然科學版,2010(1):127-134.

[7]RodrigoNCalheiros,RajivRanjan,CesarAFDeRose,etal.CloudSim:Anovelframeworkformodelingandsimulationofcloudcomputinginfrastructuresandservices[R].Australia:UniversityofMelbourne,2009.

[8]ChangF,RenJ,ViswanathanR.Optimalresourceallocationinclouds[C].WashingtonDC,USA:CLOUD’10,2010.

[9]DorigoM,BlumC.Antcolonyoptimizationtheory:Asurvey[J].TheoreticalComputerScience,2005,344(2-3):243-278.

[10]張曉杰,孟慶春,曲衛(wèi)芬.基于蟻群優(yōu)化算法的服務網格的作業(yè)調度[J].計算機工程,2006,32(8):216-218.

[11]BuyyaR,RanjanR,CalheirosRN.Modelingandsimulationofscalablecloudcomputingenvironmentsandthecloudsimtoolkit:challengesandopportunities[C].Kochi,India:InternationalConferenceonHighPerformanceComputing&Simulation,2009.

Research on Task Scheduling Algorithm In Cloud Computing Environment

LI Hanyi,CHEN Jiaqi

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)

There are large number of tasks in cloud computing environment,and how to conduct effective task scheduling is the key to allocate resources by need in cloud computing environment in order to be more efficient completion of task request.This paper proposes a task scheduling algorithm based on the ant colony optimization which an adapt to the dynamic characteristics of the cloud computing environment coupled with the advantages of ant colony optimization in the treatment of NP-Hard.The algorithm is designed to minimize task completion time during scheduling.Simulation on the CloudSim platform shows that this algorithm can effectively improve the task scheduling time under cloud computing environment.

cloud computing;job scheduling;ant colony optimization

2015- 04- 16

上海市教委科研創(chuàng)新基金資助項目(12zz146)

李菡薏(1991—),女,碩士研究生。研究方向:計算機網絡。E-mail:zitengyekuki@163.com。陳家琪(1957—),男,教授。研究方向:網絡計算等。

10.16180/j.cnki.issn1007-7820.2015.11.012

TP301.6

A

1007-7820(2015)11-043-05