云計算中任務(wù)調(diào)度優(yōu)化策略的研究

全 ,

(長沙理工大學(xué) 計算機與通信工程學(xué)院,長沙 410114)

0 概述

云計算是互聯(lián)網(wǎng)計算發(fā)展的新革命,相比于分布式計算其具有更突出的優(yōu)勢,它是一種高效率的多功能計算系統(tǒng)[1],大規(guī)模的計算資源確保了云服務(wù)的高效性。云計算中需要處理的任務(wù)被調(diào)度分配到在各個計算資源中,用戶可以通過云計算按照需求獲取計算與信息服務(wù),以及高效的存儲服務(wù)[2]。任務(wù)調(diào)度作為云計算的核心技術(shù),在云計算處理任務(wù)的過程中,任務(wù)調(diào)度是不可避免的重要環(huán)節(jié)之一,因此,優(yōu)化任務(wù)調(diào)度機制是強化云計算綜合性能的重要方法。

為了更有效地改善云計算的服務(wù)性能,有學(xué)者針對云計算中的任務(wù)調(diào)度機制所遇到的問題展開了研究。文獻[3]以提高云計算服務(wù)質(zhì)量為基礎(chǔ),通過對蜂群算法的改進,能夠在一定程度上提高算法的全局搜索能力,并且能夠有效地滿足QoS需求;文獻[4]引入局部搜索算子對蜂群算法進行優(yōu)化,能夠有效地縮短任務(wù)的完成時間;文獻[5]利用蟻群算法對云計算任務(wù)調(diào)度系統(tǒng)進行改善,能夠較好地在多個方面提高系統(tǒng)性能;文獻[6]針對任務(wù)調(diào)度過程中虛擬機負載的問題,利用蟻群算法較好的反饋機制提出蟻群優(yōu)化算法,能夠較好地改善資源利用率;文獻[7]利用遺傳算法較好的搜索能力能夠有效地改善任務(wù)調(diào)度的性能,使虛擬機達到負載均衡;文獻[8]利用遺傳算法前期搜索能力強的優(yōu)勢與蟻群算法的信息反饋的特點,將2種算法相結(jié)合來彌補各自的問題,該算法在改善收斂速度的同時滿足用戶所要求的服務(wù)質(zhì)量;文獻[9]對遺傳算法中的交叉和變異的概率公式進行優(yōu)化,提高了全局搜索能力;文獻[10]針對云計算中任務(wù)調(diào)度需要多個目標(biāo)優(yōu)化的問題,提出了改進的Memetic算法,該算法能夠較快地找到全局最優(yōu)解,提高了計算效率。

本文針對蟻群算法收斂速度慢與任務(wù)分配不均的問題,結(jié)合調(diào)度機制的特點對算法中信息素更新方法進行優(yōu)化,通過對信息素增量賦予權(quán)值,改進算法的計算效率,并采用揮發(fā)系數(shù)動態(tài)調(diào)整的方法,提高算法的搜索能力,在進行局部信息素更新時,加入衡量虛擬機工作負載的權(quán)重系數(shù),保證虛擬機的負載均衡。

1 任務(wù)調(diào)度模型

云計算在處理任務(wù)時,任務(wù)需要被合理地分配到各個計算資源中,其任務(wù)調(diào)度機制可以表示為:通過任務(wù)調(diào)度策略將需要處理的任務(wù)分配到異構(gòu)的資源上,使全部任務(wù)在被執(zhí)行完成之后所需時間最少并滿足負載均衡。本文考慮的問題是將N個相互獨立、不同大小的任務(wù)根據(jù)任務(wù)調(diào)度算法分配到M個性能不同的虛擬機進行并行計算,根據(jù)虛擬機處理任務(wù)時的性能指標(biāo)得出實驗結(jié)果。

在云計算調(diào)度模型中需要處理的作業(yè)為N個互不關(guān)聯(lián)的任務(wù),N個任務(wù)集合表示為:Task={t1,t2,…,tn},MI表示任務(wù)的指令長度,其中MIi表示任務(wù)ti的指令長度[11]。處理任務(wù)的異構(gòu)資源為M個虛擬機,虛擬機集合表示為VM={v1,v2,…,vm},MIPS表示虛擬機的執(zhí)行速度,其中MIPSj表示虛擬機vj的執(zhí)行速度[12]。

為計算每個任務(wù)在不同虛擬機上所需要的處理時間,定義執(zhí)行時間矩陣為:

其中,timeij表示表示虛擬機vj處理任務(wù)ti所需要的執(zhí)行時間,并且timeij=MIi/MIPSj。

根據(jù)虛擬機與任務(wù)的匹配關(guān)系建立矩陣x[i][j],表示任務(wù)ti是否分配給虛擬機vj,定義為:

2 云計算任務(wù)調(diào)度策略

2.1 基于蟻群算法的調(diào)度模型

蟻群算法作為一種全局優(yōu)化算法,一般被用來解決路徑優(yōu)化的問題,該算法具有分布性、隨機性、反饋性等特點,在云環(huán)境中利用蟻群算法的特點能夠有效地處理任務(wù)調(diào)度機制所遇到的問題。

(3)

在完成一次迭代之后,根據(jù)虛擬機與任務(wù)的配對情況,對信息素τij(t)進行更新,表達式為:

τij(t+1)=ρ·τij(t)+Δτij(t)

(4)

2.2 任務(wù)調(diào)度算法的優(yōu)化

蟻群算法在解決任務(wù)分配的問題時,對任務(wù)的分配采用隨機選擇的方法,影響了算法的搜索能力,使算法需要更多的迭代才能得到最優(yōu)分配方案,因此,會出現(xiàn)收斂速度變慢的問題,雖然通過正反饋機制可以強化較優(yōu)的解,但會導(dǎo)致停滯現(xiàn)象。針對這些問題,本文通過對信息素增量Δτij(t)賦予權(quán)值的方法,改變?nèi)中畔⑺氐母乱?guī)則,并依據(jù)迭代次數(shù)的增加更新?lián)]發(fā)系數(shù)ρ的參數(shù)值,改善了算法的綜合性能。

2.2.1 信息素的更新

為了更好地利用最優(yōu)解的信息,使算法得到較好的性能,在每次迭代完成之后,將每只螞蟻所形成的解按照從小到大排序,表示為F1(t)≤F2(t)≤…≤Fm(t),利用解的大小對信息素增量賦予不同的權(quán)值,最優(yōu)解的權(quán)值最大。最優(yōu)解的權(quán)值大小為a,當(dāng)全部的螞蟻進行完一次迭代之后,利用賦予信息素增量權(quán)值的方法對信息素做全局更新:

(6)

負載均衡是衡量任務(wù)調(diào)度算法的重要指標(biāo),針對負載均衡的問題,在信息素的更新規(guī)則中,通過加入局部信息素的更新方法來保障任務(wù)調(diào)度的負載均衡。局部信息素的更新方法定義為:每完成一次任務(wù)與虛擬機的配對之后,將引入局部信息素,并依據(jù)虛擬機的運行時間對其進行更新,更新規(guī)則為:

2.2.2 自適應(yīng)調(diào)整策略

信息素揮發(fā)系數(shù)ρ的數(shù)值設(shè)定是否合理將會影響算法選找最優(yōu)分配方案的搜索能力與計算效率[16],通過動態(tài)地改變ρ的值,從而能自適應(yīng)地調(diào)整信息素的大小,因此,可以有效地加強算法前期的搜索能力,豐富解的多樣性,并隨著迭代次數(shù)的增加,最優(yōu)分配方案的概率得到提高,保證了算法的綜合性能,揮發(fā)系數(shù)ρ的調(diào)整策略為:

ρa(t)=1-ln(t)/ln(t+c)

(9)

其中,C為常數(shù),揮發(fā)系數(shù)ρ的大小限制在[ρmin,ρmax],使ρ的值不會因為過大或過小,而導(dǎo)致求解效率變慢或者搜索能力變?nèi)?保證了算法的綜合性能。

2.3 算法的實現(xiàn)過程

算法實現(xiàn)過程如下:

1)初始化啟發(fā)函數(shù)ηij(t)、信息素τij(t)、最大迭代次數(shù)tmax、螞蟻數(shù)量n。

3)更新螞蟻k的任務(wù)禁忌表tabuk,如果螞蟻k將任務(wù)ti分配給虛擬機vj,則將任務(wù)ti加入禁忌表tabuk,更新任務(wù)集合Ek,如果任務(wù)集合Ek為空,則執(zhí)行下一步,否則將跳轉(zhuǎn)到第2步。

5)全局信息素的更新,根據(jù)式(5)對全局最優(yōu)解進行更新,判斷是否為最大迭代次數(shù),如果t≥tmax,則結(jié)束算法,否則t++、k=1并跳轉(zhuǎn)到第2步。

算法偽代碼如下:

1.initialize ηij(t),τij(t),tmax,n,t←1;

2.while t≤tmax

3.initialize k←1,tabuk,Ek;

5.if k≤n

6.while Ek≠φ

8.update tabuk,Ek;

9.end while

10.update τij(t) by式(7);

11.calculate Fk(t);

13.k++;

14.end if

15.update τij(t) by式(6);

17.update Fbestby式(5);

18.t++;

19.end while

3 實驗結(jié)果與分析

實驗選擇云計算仿真器CloudSim對任務(wù)調(diào)度實驗進行仿真,CloudSim是一種可擴展、通用的仿真框架,能夠?qū)υ朴嬎闳蝿?wù)調(diào)度實驗進行模型建立和仿真模擬。實驗對本文設(shè)計的改進蟻群算法與Min-Min算法、基本蟻群算法進行仿真,并比較3種不同算法的實驗結(jié)果。

1)Min-Min算法

采用Min-Min算法處理任務(wù)調(diào)度的過程為:通過計算每個虛擬機處理不同任務(wù)時所需要的完成時間,選出每個任務(wù)所需完成時間的最小值,根據(jù)最小值的大小將任務(wù)進行排序,按照由小到大的順序依次分配任務(wù),因為Min-Min算法只考慮任務(wù)被完成的時間為優(yōu)化目標(biāo),所以會導(dǎo)致任務(wù)分配不合理的問題。

2)蟻群算法

在應(yīng)用蟻群算法解決任務(wù)調(diào)度問題的過程中,首先根據(jù)虛擬機對每個任務(wù)的處理能力,計算任務(wù)與虛擬機的配對概率,由螞蟻根據(jù)配對概率對任務(wù)進行分配,完成一次迭代之后,更新目標(biāo)解與信息素,在算法完成收斂時得到目標(biāo)解。由于隨機選擇的方法與反饋機制的原因,因此會導(dǎo)致收斂速度變慢與早熟現(xiàn)象。

參數(shù)設(shè)置:需要處理的任務(wù)個數(shù)分別設(shè)為40、60、80、100和120,任務(wù)的指令長度為5 000 MI～50 000 MI,虛擬機數(shù)量為8,執(zhí)行速度為1 000 MIPS～2 000 MIPS。根據(jù)文獻[6,17],并通過多次實驗進行測試仿真,對算法參數(shù)進行設(shè)置,算法參數(shù)如表1所示。

表1 任務(wù)調(diào)度算法參數(shù)

為了驗證改進蟻群算法應(yīng)用于云任務(wù)調(diào)度時的收斂速度,實驗方案設(shè)置為:對于不相同的任務(wù)個數(shù),分別計算改進蟻群算法與基本蟻群算法2種方案,找到最優(yōu)解時的迭代次數(shù),虛擬機的個數(shù)為8。每組數(shù)據(jù)為10次實驗的平均值,實驗結(jié)果如圖1所示。

圖1 算法的迭代次數(shù)

圖1的仿真結(jié)果表明:改進蟻群算法完成收斂所需的迭代次數(shù)低于基本蟻群算法,因為本文通過結(jié)合調(diào)度機制的特點對信息素的更新規(guī)則進行優(yōu)化,通過對信息素增量Δτij(t)賦予權(quán)值的方法,加快算法的求解速度,并對揮發(fā)系數(shù)的值進行動態(tài)更新,隨著迭代次數(shù)的增加,提高最優(yōu)目標(biāo)解的概率,進一步加快算法的計算效率,收斂速度得到提高,因此改進蟻群算法相比于基本蟻群算法能夠更快地找到最優(yōu)解,算法性能得到較好地改善。

圖2為在任務(wù)個數(shù)不相同的情況下,基于3種不同調(diào)度算法虛擬機完成任務(wù)所需要的總執(zhí)行時間的對比。

圖2 不同算法的任務(wù)完成時間

通過對3種算法的對比,改進蟻群算法根據(jù)解的大小作為信息素更新時的權(quán)值,并依據(jù)迭代次數(shù)的大小計算揮發(fā)系數(shù),使算法的全局搜索能力得到加強,豐富解的多樣性,最終解的大小更優(yōu),因此,總執(zhí)行時間更快,與Min-Min算法、基本蟻群算法相比分別減少了16%～29%、10%～17%。

圖3 不同算法的負載均衡情況

由于Min-Min算法只把總執(zhí)行時間作為優(yōu)化目標(biāo),因此負載均衡度最差,本文設(shè)計的改進蟻群算法根據(jù)虛擬機的運行情況對局部信息素進行更新,優(yōu)化了虛擬機處理任務(wù)時的負載均衡,對比基本蟻群算法,虛擬機工作的負載均衡效果更好。

4 結(jié)束語

通過蟻群算法處理云計算中的任務(wù)時,會遇到求解速度慢和負載不均衡的問題,本文通過添加權(quán)值的方法對信息素更新規(guī)則進行改進,利用每只螞蟻所生成的解作為信息素增量的權(quán)重,加快算法在選擇匹配方案時的求解效率,并采用動態(tài)更新?lián)]發(fā)系數(shù)的方法,根據(jù)迭代次數(shù)自適應(yīng)地對權(quán)值進行更新調(diào)整,提高算法的全局搜索能力,豐富解的多樣性,改善了算法的收斂性,保證算法的綜合性能。在對局部信息素更新時,加入衡量虛擬機負載的權(quán)重系數(shù),使任務(wù)得到合理分配。實驗結(jié)果表明,本文設(shè)計的改進算法能夠較快地得到最優(yōu)解,與Min-Min算法和基本蟻群算法相比,任務(wù)的總執(zhí)行時間與負載問題得到了改善。為了更好地提高調(diào)度機制的綜合性能,下一步將研究具有關(guān)聯(lián)性的云任務(wù)調(diào)度與能耗優(yōu)化問題。