云計算中任務調度優化策略的研究

全 ,

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

0 概述

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

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

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

1 任務調度模型

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

在云計算調度模型中需要處理的作業為N個互不關聯的任務,N個任務集合表示為:Task={t1,t2,…,tn},MI表示任務的指令長度,其中MIi表示任務ti的指令長度[11]。處理任務的異構資源為M個虛擬機,虛擬機集合表示為VM={v1,v2,…,vm},MIPS表示虛擬機的執行速度,其中MIPSj表示虛擬機vj的執行速度[12]。

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

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

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

2 云計算任務調度策略

2.1 基于蟻群算法的調度模型

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

(3)

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

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

(4)

2.2 任務調度算法的優化

蟻群算法在解決任務分配的問題時,對任務的分配采用隨機選擇的方法,影響了算法的搜索能力,使算法需要更多的迭代才能得到最優分配方案,因此,會出現收斂速度變慢的問題,雖然通過正反饋機制可以強化較優的解,但會導致停滯現象。針對這些問題,本文通過對信息素增量Δτij(t)賦予權值的方法,改變全局信息素的更新規則,并依據迭代次數的增加更新揮發系數ρ的參數值,改善了算法的綜合性能。

2.2.1 信息素的更新

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

(6)

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

2.2.2 自適應調整策略

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

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

(9)

其中,C為常數,揮發系數ρ的大小限制在[ρmin,ρmax],使ρ的值不會因為過大或過小,而導致求解效率變慢或者搜索能力變弱,保證了算法的綜合性能。

2.3 算法的實現過程

算法實現過程如下:

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

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

5)全局信息素的更新,根據式(5)對全局最優解進行更新,判斷是否為最大迭代次數,如果t≥tmax,則結束算法,否則t++、k=1并跳轉到第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 實驗結果與分析

實驗選擇云計算仿真器CloudSim對任務調度實驗進行仿真,CloudSim是一種可擴展、通用的仿真框架,能夠對云計算任務調度實驗進行模型建立和仿真模擬。實驗對本文設計的改進蟻群算法與Min-Min算法、基本蟻群算法進行仿真,并比較3種不同算法的實驗結果。

1)Min-Min算法

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

2)蟻群算法

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

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

表1 任務調度算法參數

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

圖1 算法的迭代次數

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

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

圖2 不同算法的任務完成時間

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

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

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

4 結束語

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