云計算環(huán)境下任務(wù)調(diào)度算法的研究

李菡薏,陳家琪

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

云計算環(huán)境下任務(wù)調(diào)度算法的研究

李菡薏,陳家琪

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

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

云計算;任務(wù)調(diào)度;蟻群算法

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

1 問題描述

1.1 云計算調(diào)度的概念

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

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

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

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

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

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

1.2 蟻群算法

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

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

2 算法描述

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

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

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

τ0=m×p

(1)

其中,m是虛擬機(jī)的個數(shù);p是表示CPU的速度。

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

(2)

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

0,else

(3)

(4)

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

(5)

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

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

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

(6)

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

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

(7)

2.2 算法流程

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

ProcedureJS-ACO

Begin

初始化參數(shù)

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

每個螞蟻開始活動

While(當(dāng)每只螞蟻都完成構(gòu)建解時停止)do

For每只螞蟻do

根據(jù)狀態(tài)轉(zhuǎn)移概率公式選擇下個虛擬機(jī);

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

Endfor

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

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

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

Endwhile

Endwhile

End

3 實驗與分析

3.1CloudSim

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

3.2 仿真環(huán)境

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

CloudSim采用分層設(shè)計特征及體系結(jié)構(gòu),圖1所示為分層的CloudSim體系結(jié)構(gòu)圖。

圖1 分層的CloudSim體系結(jié)構(gòu)圖

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

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

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

圖2 CloudSim的仿真流程

3.3 算法仿真

算法的調(diào)度參數(shù)列表如表1、表2所示。

表2 調(diào)度參數(shù)列表

表3 參數(shù)列表

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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

[6] 華夏渝,鄭駿,胡文心.基于云計算環(huán)境的蟻群優(yōu)化計算資源分配算法[J].華東師范大學(xué)學(xué)報:自然科學(xué)版,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)化算法的服務(wù)網(wǎng)格的作業(yè)調(diào)度[J].計算機(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—),女,碩士研究生。研究方向:計算機(jī)網(wǎng)絡(luò)。E-mail:zitengyekuki@163.com。陳家琪(1957—),男,教授。研究方向:網(wǎng)絡(luò)計算等。

10.16180/j.cnki.issn1007-7820.2015.11.012

TP301.6

A

1007-7820(2015)11-043-05