基于三支隊列的實時云任務節(jié)能調(diào)度算法

姜春茂，王凱旋

(哈爾濱師范大學 計算機科學與信息工程學院 黑龍江 哈爾濱 150080)

0 引言

云計算是一種新型的信息服務模式，通?；谔摂M化和分布式計算技術.在云計算過程中，資源的虛擬化利用率較低，但同時又有著較高的能耗.文獻[1]研究表明，閑置資源的能耗可以達到總能耗的60%或者更多，所以提高云環(huán)境中的資源使用率和降低云能耗變得非常重要.文獻[2]研究表明，當云環(huán)境中的虛擬機在資源利用率超過70%時，能耗會急劇上升.為了更合理地節(jié)約能耗，采用了云計算中一項能夠有效降低云能耗的技術——任務合并[3-5].任務合并是一個為了最大化資源利用率和最小化能耗，而將一個任務(服務請求)集合分配到一個云計算資源集合的過程，它能夠按照設定好的調(diào)度策略將任務分配給最適合的虛擬機來執(zhí)行.

借鑒三支決策的基本思想[6-8]，本文提出了基于三支隊列的實時云任務節(jié)能調(diào)度算法(簡記為TQS算法).當用戶提交一個實時任務給云平臺以后，首先會利用其截止時間進行松弛時間的計算，之后按照松弛時間將任務放入緊急調(diào)度隊列、正常調(diào)度隊列和松弛調(diào)度隊列.結合虛擬機的實際負載情況，對三個隊列提交任務進行調(diào)度.結果表明，在滿足任務實時性需求的情況下，TQS算法能夠有效降低云能耗.

1 相關工作

三支決策的基本思想是通過一對閾值(α,β)將全集U劃分成三個獨立的部分，然后針對各個區(qū)域開發(fā)相應的策略.三支決策的唯一特征是使用三支方法進行問題的解決和信息的處理.三支是基本的出發(fā)點，決策是應用之一.

三支決策[3]作為一種有效的粒度計算方法，內(nèi)在地切合了云平臺的諸多特點，如云任務可以按照任務的類型(計算密集型、存儲密集型、通信密集型)、作業(yè)的長短(長、中、短)等進行分類；虛擬機則涉及合并、遷移、關閉.本文結合三支決策的基本思想對實時云任務的松弛時間進行“三分”，不同的隊列采取不同的任務合并策略進行調(diào)度執(zhí)行.

文獻[2]提出了ETC (energy-aware task consolidation)算法：當虛擬機在資源利用率超過70%時，能耗會急劇上升.因此，ETC算法認為將每個虛擬機利用率的上限限制在70%為最優(yōu).在云計算中調(diào)度器調(diào)度任務時，會按照一定的調(diào)度順序提交任務給虛擬機運行(例如先到先服務、最短作業(yè)時間優(yōu)先等策略)，每次提交的虛擬機都不會超過70%的使用率，如果所有虛擬機的利用率都超過了70%，那么就尋找當前資源利用率最低的虛擬機來運行這個任務.文獻[9]提出了ESTC (energy saving task consolidation)算法：調(diào)度器會優(yōu)先將任務提交給空閑的虛擬機，這樣就極大降低了云環(huán)境中虛擬機的空閑率，減少了能耗，如果最后沒有空閑的虛擬機，就找一個利用率最低的虛擬機來運行提交的任務.文獻[10]提出了MTC (multi-criteria based task consolidation)算法：給每個時刻同時到達的任務計算一個適應值，調(diào)度器按照適應值的升序來調(diào)度任務，適應值低的優(yōu)先提交，越高的會越晚提交，適應值F的計算公式為

F=λ·NT+(1-λ)·NU，

(1)

式中：0<λ<1；NT表示規(guī)格化運行時間，即當前任務的運行時間除以同時到達任務中的最大運行時間；NU為規(guī)格化利用率.之后按照適應值從大到小進行排序，調(diào)度器依次提交任務給虛擬機執(zhí)行.文獻 [11]提出了MQS (multi queue scheduling)算法：MQS算法是一種多隊列調(diào)度算法，在調(diào)度之前，調(diào)度器會按照任務的突發(fā)時間對任務進行升序排序，這里的突發(fā)時間是指任務從到達到任務開始所需要的時間，可以表示為

Ti(BT)=Ti(ST)-Ti(AT).

(2)

本文提出了TQS算法，其基本思想是按照突發(fā)時間排序，將任務分成三個隊列，之后將三個隊列通過一定的算法分為兩個隊列進行提交運行.TQS是一種基于實時任務的松弛時間進行任務的三支劃分，然后合并調(diào)度的機制，即將提交的任務按照松弛時間進行三支隊列排序，之后按照不同的隊列順序?qū)θ蝿者M行調(diào)度執(zhí)行.

2 TQS算法

2.1 問題描述

一個具有n個實時云任務的集合T={T1,T2,…,Tn}，Ti是一個六元組{AT,ST,UT,PT,FT,DL}，任務屬性含義如表1所示，m個虛擬機的集合V={V1,V2,…,Vm}，其屬性如表2所示.

表1 任務屬性Tab.1 Task properties

表2 虛擬機屬性Tab.2 Virtual machine properties

每一個任務都會被調(diào)度器分配到一臺合適的虛擬機上運行，每一臺虛擬機又都具有一定的屬性，虛擬機的利用率與能耗呈線性增長關系.為了降低云計算中的能耗，需要設計一個調(diào)度算法來降低虛擬機在運行任務時的利用率，從而達到降低能耗的目的.在降低能耗的同時，也需要考慮任務的違約率，如果違約率過高，將會極大地影響到用戶體驗.

2.2 調(diào)度算法

TQS算法是一種任務合并調(diào)度算法，算法除了考慮到節(jié)約云環(huán)境能耗，還考慮了任務的SLA違約問題.SLA違約問題是指用戶提交任務后，任務完成的時間超過了任務的截止時間.在云環(huán)境中虛擬機利用率越高，單位時間內(nèi)能耗就越多.TQS算法的主要思想就是減少虛擬機運行在高利用率的時間，讓不緊急的任務盡可能得晚，但是又在不違約的情況下提交給虛擬機運行，從而減少能耗.緊急任務(UrgentTask)提交如圖1所示，其中LocalTask為已經(jīng)運行在虛擬機上的任務，如果此時將UrgentTask立即提交，重疊時間為4.2 s，在此期間，虛擬機運行的利用率為20%.

正常任務(NormalTask)提交如圖2所示，如果到達的任務按照松弛時間判斷為NormalTask，那么可以等候一段時間再提交，此時的重疊時間為3.2 s，這就證明在任務延后提交后，虛擬機在利用率為20%時運行了3.2 s，比UrgentTask提交時減少了1 s.

圖1 緊急任務提交Fig.1 Emergency tasks submitted

圖2 正常任務提交Fig.2 Normal tasks submitted

圖3 松弛任務提交Fig.3 Relax tasks submitted

松弛任務(RelaxTask)提交如圖3所示，此任務可以等待整個云環(huán)境中最先完成任務而空閑下來的虛擬機再進行提交運行.從圖中可以看到，兩個任務沒有重疊時間，所以虛擬機沒有達到過20%的利用率，這樣就使虛擬機一直運行在較低的利用率水平，從而達到節(jié)省能耗的目的.

松弛時間(RelaxTime)代表了一個任務需要處理的緊急程度.通過對松弛時間的判定，將任務分為緊急任務、正常任務和松弛任務，分別將其放入三個相對應的調(diào)度隊列，即緊急隊列(UrgentQuene)、正常隊列(NormalQuene)和松弛隊列(RelaxQuene).

當調(diào)度器開始調(diào)度時，具體步驟如下：

1) 首先提交緊急隊列中的任務.

2) 處在正常隊列中的任務會一直等待，直到正常隊列中排序最前的任務的松弛時間小于5 s，將此任務移動到緊急隊列中，再立即提交此任務.

3) 對松弛隊列中的任務，可以一直等到云環(huán)境中最早完成任務的虛擬機完成正在運行的任務后，再將松弛隊列中的第一個任務提交給虛擬機運行，之后每1 s刷新一次隊列狀態(tài).

當一個任務到達時，任務的松弛時間可以表示為

Ti(RT)=Ti(DL)-(CT+Ti(PT))，

(3)

式中：RT(RelaxTime)為松弛時間；DL(DeadLine)為任務的截止時間；CT(CurrentTime)為當前系統(tǒng)的運行時間；PT(PeriodTime)為任務的運行時間.

如果任務Ti的RT小于5 s并且大于0，則Ti為緊急任務，將其加入緊急隊列；如果任務Ti的RT大于5 s,但是小于云環(huán)境中所有虛擬機的最小任務完成時間(意味著此任務無法等到有空閑虛擬機出現(xiàn))，那么Ti為正常任務，將其添加到正常隊列；如果任務Ti的RT大于云環(huán)境中所有虛擬機的最小任務完成時間(意味著此任務可以等到一臺空閑虛擬機的出現(xiàn))，那么將其添加到松弛隊列.

假定一個虛擬機集合V={V1,V2,V3}，其中Vi={TUi，UUi，RUi，TLi，MTi}，虛擬機屬性如表2所示.設置一個任務集合T={T1,T2,T3}，其中Ti={ATi，STi，UTi，PTi，F(xiàn)Ti，DLi}，任務屬性如表1所示.云計算中空閑虛擬機與處在工作狀態(tài)中的虛擬機的能耗計算方法是不同的.

空閑虛擬機的能耗計算公式為

E(IVMi)=P20·Δv，

(4)

式中：E(IVMi)為VMi在空閑時的能耗；P20為虛擬機在利用率為20%時的能耗；Δv=vmax-vmin，為虛擬機開機時間減去虛擬機關機時間，即虛擬機持續(xù)運行的時間.

處在運行狀態(tài)下的虛擬機的能耗計算公式為

(5)

式中：E(NVM2(X))為VM2在利用率為X時的能耗；%為取余運算符.

算法具體步驟如下.

輸入：n個任務與m個虛擬機；輸出： 云計算總能耗.

Step1計算每個任務的松弛時間.

Step2按照松弛時間判斷任務，將任務分為三個隊列,Ti∈UQ,Ti∈NQ,Ti∈RQ.

Step3首先提交緊急隊列中的任務，如果有空閑虛擬機，優(yōu)先使用空閑虛擬機，如果虛擬機全為運行狀態(tài)，就挑選當前利用率最低的虛擬機進行提交.

Step4更新時間，檢查正常隊列中是否有任務的松弛時間小于5 s，如果有，就將任務移動到緊急隊列,Ti∈UQ，再提交給虛擬機.

Step5檢查是否有虛擬機K完成任務，如果完成，就將在松弛隊列中的第一個任務提交給虛擬機K運行.

Step6所有任務提交完成后，按照能耗計算公式計算總能耗.

2.3 算法復雜度分析

TQS算法的時間復雜度主要集中在調(diào)度步驟，設提交的任務總數(shù)為n，執(zhí)行任務的虛擬機總數(shù)為m，虛擬機最早完成任務的時間為k.在調(diào)度過程中，遍歷兩次任務總數(shù)n，遍歷搜索一次虛擬機總數(shù)m，迭代次數(shù)為O(n2×m)，所以TQS算法的時間復雜度為O(n3).

TQS算法中建有任務鏈表、虛擬機鏈表，建有緊急隊列、正常隊列、松弛隊列，每個隊列內(nèi)部對象均為可數(shù)，即TQS算法的空間復雜度為O(n).

表3 生成任務屬性Tab.3 Generate task properties s

2.4 算例說明

給出一個算例，提交5個實時任務，生成任務屬性如表3所示.云環(huán)境中有兩臺虛擬機VM1和VM2，初始狀態(tài)如下：TU為100%，UU為0，RU為100%，TL為Null，MT為0.

1) 從表3中可以看出，最先到達的為T5，根據(jù)式(3)計算其松弛時間為：T5(RT)=35 s，但是因為此時虛擬機沒有運行任務，所以將T5提交給VM1直接運行，此時VM1的MT為T5的開始時間(ST)加上運行時間(PT)，為55 s.

2) 表3中第二個到達的任務為T1，根據(jù)式(3)計算其松弛時間為：T1(RT)=0 s，此時VM2上并沒有運行任務，所以將T1提交給VM2運行，此時VM2的MT為T1的開始時間(ST)加上運行時間(PT)，為168 s.

3) 在13 s時任務T4到達，T4(RT)=1 s，所以將T4放入緊急隊列，并且同時立即提交，此時兩個虛擬機都被占用，選擇利用率為12%的VM1來執(zhí)行T4，此時VM1的最大任務完成時間為T4的完成時間，為58 s.

4) 在21 s時任務T3到達，T3(RT)=49 s，因為5 s

5) 在28 s時任務T2到達，T2(RT)=58 s，因為5 s

3 實驗數(shù)據(jù)分析

測試的主機CPU均為四核，主RAM為16 GB，硬盤容量為1 TB，帶寬1 Gbit/s，實驗所需虛擬機在利用率為1%～20%、21%～30%、31%～40%、41%～50%、51%～60%、61%～70%、71%～80%、81%～90%、91%～100%時的能耗分別為78.5、83、85、88、93、102、109、122、136 W[3].

3.1 在少量任務情況下的實驗數(shù)據(jù)分析

在模擬環(huán)境中隨機生成了三個任務，屬性見表3中的T1、T2、T3，其中任務到達時間(AT)服從泊松分布，運行時間(PT)服從指數(shù)分布.主機上運行三臺虛擬機用作云任務處理機，實驗共運行10次.三個任務在三臺虛擬機上分別使用ETC、ESTC、MTC、ETC&MQS、ESTC&MQS和TQS算法，在少量任務情況下不同時間的能耗如表4所示.

通過實驗數(shù)據(jù)可以計算得出ETC、ESTC、MTC、ETC&MQS、ESTC&MQS和TQS算法的總能耗分別為46 937、34 547、43 910、48 624、34 547、31 721 W.可以看出，在較少任務數(shù)量的實驗中，ETC、MTC和ETC&MQS算法的能耗較高，ESTC和ESTC&MQS算法的能耗相對較低，TQS算法的能耗為最優(yōu).

表4 在少量任務情況下不同時間的能耗Tab.4 Energy consumptions under a small amount of tasks at different time W

3.2 在較多任務情況下的實驗數(shù)據(jù)分析

在較多任務測試的情況下，實驗自動生成了500個任務，其中任務到達時間(AT)服從泊松分布，運行時間(PT)服從指數(shù)分布，經(jīng)過10次實驗，取平均值得出6種算法在較多任務情況下不同時間的能耗，結果如表5所示.

表5 在較多任務情況下不同時間的能耗Tab.5 Energy consumptions under more tasks at different time 103 W

從實驗數(shù)據(jù)可以得出ETC、ESTC、MTC、ETC&MQS、ESTC&MQS和TQS算法的總能耗分別為2.3×107、4.39×106、2.29×107、2.44×107、4.39×106、4.08×106W.從500個任務的實驗結果可以看出，在較多任務情況下，ETC、MTC和ETC&MQS算法的能耗非常高，ESTC和ESTC&MQS算法的能耗相對較低， TQS算法的能耗為最優(yōu).

3.3 算法的能耗增長趨勢測試

系統(tǒng)分別隨機生成5、10、15、20、25、30、35、40、45個任務，其中任務到達時間(AT)服從泊松分布，運行時間(PT)服從指數(shù)分布，系統(tǒng)相應地自動生成5、10、15、20、25、30、35、40、45個虛擬機，共進行了10次實驗.結果表明，在少量任務時，6種算法的能耗都較低，但在任務數(shù)超過25個時，ETC、ETC&MQS和MTC算法的能耗開始急劇增長，而在較多任務情況下，TQS算法仍然保持著較低的能耗水平.實驗結果驗證了TQS算法能夠在保證違約率的同時減少在云計算中的能耗.

4 小結

本文提出了基于三支隊列的實時云任務節(jié)能調(diào)度算法，在不違約的情況下能更加合理地調(diào)度任務，將每個任務的截止時間利用得更好，盡可能地減少云環(huán)境中虛擬機運行在高利用率的時間.實驗結果表明，無論TQS算法在少量任務或者較多任務的情況下，能耗都優(yōu)于其他5種算法，尤其是ETC算法.基于實時任務的松弛時間進行任務的合并調(diào)度算法，確實能夠有效降低在云環(huán)境中的能耗.下一步將在算法的優(yōu)化和面向容器的能耗優(yōu)化中，更多地使用多粒度三支決策的思想進行任務的調(diào)度、容器的合并等.