姜春茂，王凱旋

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

0 引言

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

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

1 相關(guān)工作

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

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

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

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

(1)

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

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

(2)

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

2 TQS算法

2.1 問題描述

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

表1 任務(wù)屬性Tab.1 Task properties

表2 虛擬機(jī)屬性Tab.2 Virtual machine properties

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

2.2 調(diào)度算法

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

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

圖1 緊急任務(wù)提交Fig.1 Emergency tasks submitted

圖2 正常任務(wù)提交Fig.2 Normal tasks submitted

圖3 松弛任務(wù)提交Fig.3 Relax tasks submitted

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

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

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

1) 首先提交緊急隊(duì)列中的任務(wù).

2) 處在正常隊(duì)列中的任務(wù)會(huì)一直等待，直到正常隊(duì)列中排序最前的任務(wù)的松弛時(shí)間小于5 s，將此任務(wù)移動(dòng)到緊急隊(duì)列中，再立即提交此任務(wù).

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

當(dāng)一個(gè)任務(wù)到達(dá)時(shí)，任務(wù)的松弛時(shí)間可以表示為

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

(3)

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

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

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

空閑虛擬機(jī)的能耗計(jì)算公式為

E(IVMi)=P20·Δv，

(4)

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

處在運(yùn)行狀態(tài)下的虛擬機(jī)的能耗計(jì)算公式為

(5)

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

算法具體步驟如下.

輸入：n個(gè)任務(wù)與m個(gè)虛擬機(jī)；輸出： 云計(jì)算總能耗.

Step1計(jì)算每個(gè)任務(wù)的松弛時(shí)間.

Step2按照松弛時(shí)間判斷任務(wù)，將任務(wù)分為三個(gè)隊(duì)列,Ti∈UQ,Ti∈NQ,Ti∈RQ.

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

Step4更新時(shí)間，檢查正常隊(duì)列中是否有任務(wù)的松弛時(shí)間小于5 s，如果有，就將任務(wù)移動(dòng)到緊急隊(duì)列,Ti∈UQ，再提交給虛擬機(jī).

Step5檢查是否有虛擬機(jī)K完成任務(wù)，如果完成，就將在松弛隊(duì)列中的第一個(gè)任務(wù)提交給虛擬機(jī)K運(yùn)行.

Step6所有任務(wù)提交完成后，按照能耗計(jì)算公式計(jì)算總能耗.

2.3 算法復(fù)雜度分析

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

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

表3 生成任務(wù)屬性Tab.3 Generate task properties s

2.4 算例說明

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

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

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

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

4) 在21 s時(shí)任務(wù)T3到達(dá)，T3(RT)=49 s，因?yàn)? s

5) 在28 s時(shí)任務(wù)T2到達(dá)，T2(RT)=58 s，因?yàn)? s

3 實(shí)驗(yàn)數(shù)據(jù)分析

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

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

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

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

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

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

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

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

從實(shí)驗(yàn)數(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個(gè)任務(wù)的實(shí)驗(yàn)結(jié)果可以看出，在較多任務(wù)情況下，ETC、MTC和ETC&MQS算法的能耗非常高，ESTC和ESTC&MQS算法的能耗相對(duì)較低， TQS算法的能耗為最優(yōu).

3.3 算法的能耗增長(zhǎng)趨勢(shì)測(cè)試

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

4 小結(jié)

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