陳黃科 祝江漢 朱曉敏 馬滿好 張振仕

(國(guó)防科學(xué)技術(shù)大學(xué)信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 長(zhǎng)沙 410073) (hkchen@nudt.edu.cn)

云計(jì)算中資源延遲感知的實(shí)時(shí)任務(wù)調(diào)度方法

陳黃科 祝江漢 朱曉敏 馬滿好 張振仕

(國(guó)防科學(xué)技術(shù)大學(xué)信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 長(zhǎng)沙 410073) (hkchen@nudt.edu.cn)

綠色云計(jì)算已經(jīng)成為一個(gè)研究焦點(diǎn)，動(dòng)態(tài)整合虛擬機(jī)和關(guān)閉空閑主機(jī)是極具潛力的途徑可降低云計(jì)算數(shù)據(jù)中心的能耗.當(dāng)云平臺(tái)的負(fù)載迅速增加時(shí)，系統(tǒng)需要啟動(dòng)更多的主機(jī)和創(chuàng)建更多的虛擬機(jī)來(lái)擴(kuò)展可用資源.然而，啟動(dòng)主機(jī)和創(chuàng)建虛擬機(jī)需要一定的時(shí)間開(kāi)銷，使得緊急任務(wù)難以及時(shí)開(kāi)始，從而延誤了截止期.為了解決以上問(wèn)題，首先提出具有機(jī)器啟動(dòng)時(shí)間感知的虛擬機(jī)擴(kuò)展策略，以緩解機(jī)器啟動(dòng)時(shí)間沖擊實(shí)時(shí)任務(wù)的時(shí)效性要求.基于該策略，設(shè)計(jì)算法STARS來(lái)調(diào)度實(shí)時(shí)任務(wù)和資源，以在保障任務(wù)時(shí)效性與節(jié)能2方面進(jìn)行權(quán)橫.最后，使用Google的負(fù)載數(shù)據(jù)進(jìn)行模擬實(shí)驗(yàn)，比較算法STARS與其他2個(gè)算法的性能.實(shí)驗(yàn)結(jié)果表明，在保障任務(wù)時(shí)效性、節(jié)能和資源利用率方面，算法STARS優(yōu)于對(duì)比算法.

云計(jì)算;虛擬化;調(diào)度;實(shí)時(shí)任務(wù);節(jié)能;機(jī)器啟動(dòng)時(shí)間

為了迎接急劇增長(zhǎng)的計(jì)算服務(wù)需求，云計(jì)算數(shù)據(jù)中心部署的主機(jī)規(guī)模急劇增長(zhǎng).一個(gè)數(shù)據(jù)中心的主機(jī)數(shù)量就高達(dá)幾萬(wàn)臺(tái)，甚至幾十萬(wàn)臺(tái)[1].運(yùn)行這些主機(jī)，云服務(wù)系統(tǒng)需要消耗大量的電能.據(jù)統(tǒng)計(jì)，從2005—2010年全球數(shù)據(jù)中心的能耗提高56%，占全球總能耗的1.5%[2].對(duì)企業(yè)而言，高能耗就意味著高成本.另外，高能耗對(duì)生態(tài)環(huán)境產(chǎn)生較大的負(fù)面影響，因?yàn)槭褂妹旱V發(fā)電會(huì)向空氣中釋放大量的廢氣[3].云計(jì)算數(shù)據(jù)中心的高能耗問(wèn)題已經(jīng)引起各界的極大關(guān)注，并成為學(xué)術(shù)界研究的熱點(diǎn).

大量的研究[4-6]表明，在云計(jì)算數(shù)據(jù)中心提高活躍主機(jī)的資源利用效率和減少電能消耗的有效途徑是：在云計(jì)算數(shù)據(jù)中心負(fù)載下降時(shí)，動(dòng)態(tài)整合虛擬機(jī)到盡可能少的主機(jī)上，然后關(guān)閉空閑的主機(jī)，以減少能量消耗.由于主機(jī)處于完全空閑的狀態(tài)，功耗仍然是它最大功耗的50%以上[6]，關(guān)閉空閑的主機(jī)就意味著節(jié)約大量的電能消耗.

但是，這類資源整合方法帶來(lái)了另一個(gè)挑戰(zhàn)性問(wèn)題：當(dāng)云計(jì)算數(shù)據(jù)中心的負(fù)載突增時(shí)，伸展虛擬機(jī)的過(guò)程中，創(chuàng)建新虛擬機(jī)或者先開(kāi)啟關(guān)閉的主機(jī)然后再創(chuàng)建虛擬機(jī)[4]都需要一定的時(shí)間開(kāi)銷，使得某些任務(wù)不能及時(shí)開(kāi)始，從而延誤了它們的截止期.例如，一個(gè)在0 s到達(dá)的新任務(wù)，它的執(zhí)行時(shí)間是5 s，假設(shè)它的截止期是執(zhí)行時(shí)間的5倍(即25 s).啟動(dòng)主機(jī)的時(shí)間大概為30 s，創(chuàng)建1臺(tái)虛擬機(jī)的時(shí)間近似于啟動(dòng)一個(gè)操作系統(tǒng)的時(shí)間，大概也是30 s.當(dāng)該任務(wù)到達(dá)后再創(chuàng)建新虛擬機(jī)，很明顯，該任務(wù)的截止期將被延誤.

為了解決以上問(wèn)題，本文首先提出了具有機(jī)器啟動(dòng)時(shí)間感知的虛擬機(jī)擴(kuò)展策略，該策略在每臺(tái)活躍主機(jī)上放置1臺(tái)應(yīng)急虛擬機(jī)，然后借助虛擬機(jī)CPU資源可以動(dòng)態(tài)伸縮的能力，當(dāng)某些實(shí)時(shí)任務(wù)的截止期得不到滿足時(shí)，動(dòng)態(tài)擴(kuò)大應(yīng)急虛擬機(jī)的CPU能力來(lái)服務(wù)這些任務(wù)，當(dāng)這些任務(wù)完成以后，應(yīng)急虛擬機(jī)將釋放CPU資源，以減少能耗.另外，本文將以上策略集成到滾動(dòng)優(yōu)化中，形成調(diào)度算法STARS，該算法在每個(gè)新任務(wù)到達(dá)時(shí)，為云計(jì)算數(shù)據(jù)中心生成新的任務(wù)和虛擬機(jī)調(diào)度方案.最后，通過(guò)仿真實(shí)驗(yàn)對(duì)本文的調(diào)度算法的有效性進(jìn)行驗(yàn)證.

1 相關(guān)工作

為了解決云數(shù)據(jù)中心的高能耗問(wèn)題，目前科研人員已經(jīng)提出大量能耗感知的調(diào)度方法.其中具有巨大潛在價(jià)值的是：將主機(jī)虛擬化成多個(gè)獨(dú)立的虛擬機(jī)來(lái)同時(shí)運(yùn)行多個(gè)任務(wù)，以提高主機(jī)的資源利用率和減少使用主機(jī)的數(shù)量；另外，當(dāng)數(shù)據(jù)中心的負(fù)載下降時(shí)，將虛擬機(jī)整合到盡可能少的主機(jī)上，然后關(guān)閉空閑的主機(jī)，以進(jìn)一步減少能量消耗.

比如，Li等人[7]針對(duì)目前大部分調(diào)度算法根據(jù)任務(wù)的平均運(yùn)行時(shí)間進(jìn)行調(diào)度，很難同時(shí)最小化任務(wù)的完成時(shí)間和能耗的不足，建立了隨機(jī)任務(wù)的運(yùn)行時(shí)間和能耗模型，并提出一個(gè)能耗感知的調(diào)度算法.Mei等人[8]針對(duì)異構(gòu)系統(tǒng)中基于任務(wù)復(fù)制的調(diào)度算法過(guò)度復(fù)制任務(wù)造成資源浪費(fèi)的問(wèn)題，提出了一個(gè)新的能耗感知調(diào)度算法來(lái)最小化任務(wù)的復(fù)制量，從而最小化應(yīng)用的完成時(shí)間和能量消耗.Ma等人[9]針對(duì)異構(gòu)系統(tǒng)的高能耗問(wèn)題，為帶截止期的獨(dú)立任務(wù)設(shè)計(jì)了能量高效的調(diào)度算法.Beloglazov等人[6]提出基于雙閾值的虛擬機(jī)動(dòng)態(tài)配置策略，根據(jù)主機(jī)的實(shí)時(shí)資源利用率對(duì)虛擬機(jī)進(jìn)行整合，并將空閑節(jié)點(diǎn)轉(zhuǎn)入睡眠模式.Zhu等人[4]提出了一種實(shí)時(shí)任務(wù)的節(jié)能調(diào)度算法EARH，同時(shí)提出了資源動(dòng)態(tài)增加與縮減策略.Xiao等人[10]設(shè)計(jì)了一個(gè)資源管理方法，借助虛擬化技術(shù)動(dòng)態(tài)分配數(shù)據(jù)中心的資源，同時(shí)優(yōu)化使用主機(jī)的數(shù)量，以支持綠色計(jì)算.馬艷等人[11]提出了網(wǎng)格依賴任務(wù)的能耗有效調(diào)度算法，來(lái)優(yōu)化應(yīng)用完成時(shí)間的同時(shí)降低能耗.魏亮等人[12]設(shè)計(jì)一種面向云計(jì)算基礎(chǔ)設(shè)施基于工作負(fù)載預(yù)測(cè)的整合調(diào)度算法，以減少主機(jī)使用量、虛擬機(jī)遷移次數(shù)和資源利用率.何炎祥等人[13]為提高資源和能源的有效利用率，提出了一種迭代式多目標(biāo)分配優(yōu)化方法，從能源消耗和資源的均衡使用度2個(gè)方面出發(fā)，利用可交換類指令重排優(yōu)化和寄存器重分配優(yōu)化，對(duì)總線和存儲(chǔ)系統(tǒng)的綠色指標(biāo)進(jìn)行改進(jìn).Hsu等人[14]提出一個(gè)能耗感知的任務(wù)整合方法來(lái)限制CPU的資源利用率低于預(yù)設(shè)的閾值，以最小化系統(tǒng)的能量消耗.周景才等人[15]基于用戶行為特征，動(dòng)態(tài)調(diào)整云計(jì)算系統(tǒng)的資源分配策略.Corradi等人[16]提出一種云管理平臺(tái)，以優(yōu)化虛擬機(jī)整合的3個(gè)性能：功耗、主機(jī)和網(wǎng)絡(luò)資源.丁有偉等人[17]針對(duì)異構(gòu)集群下IO密集型的大數(shù)據(jù)處理任務(wù)，提出一種新的能量高效算法，以減少各個(gè)節(jié)點(diǎn)因?yàn)榈却斐傻哪芰坷速M(fèi).李強(qiáng)等人[18]使用多目標(biāo)遺傳算法來(lái)求解虛擬機(jī)的放置方案.殷小龍等人[19]改進(jìn)NSGA II來(lái)求解虛擬機(jī)調(diào)度問(wèn)題，以均衡系統(tǒng)的負(fù)載、提高任務(wù)執(zhí)行效率和降低能耗.肖鵬等人[20]針對(duì)高性能計(jì)算領(lǐng)域的高能耗問(wèn)題，設(shè)計(jì)了一種“最小能耗路徑”的數(shù)據(jù)密集型工作流算法.Li等人[21]針對(duì)任務(wù)的執(zhí)行時(shí)間具有隨機(jī)性的特點(diǎn)，提出一個(gè)隨機(jī)任務(wù)調(diào)度算法，來(lái)同時(shí)滿足任務(wù)的時(shí)效性和能耗約束.

但是，這些調(diào)度方法存在如下問(wèn)題：當(dāng)云計(jì)算數(shù)據(jù)中心的負(fù)載突增時(shí)，在伸展虛擬機(jī)的過(guò)程中，啟動(dòng)主機(jī)和創(chuàng)建虛擬機(jī)需要一定的時(shí)間開(kāi)銷，使得某些任務(wù)不能及時(shí)開(kāi)始，從而延誤了截止期.本文針對(duì)該問(wèn)題，提出一種機(jī)器啟動(dòng)時(shí)間感知的虛擬機(jī)伸展策略，并將其集成到滾動(dòng)優(yōu)化中，以提高云計(jì)算數(shù)據(jù)中心保障實(shí)時(shí)任務(wù)時(shí)效性的能力，同時(shí)降低系統(tǒng)的能量消耗.

2 問(wèn)題描述

2.1 調(diào)度框架

每臺(tái)主機(jī)都可容納一個(gè)虛擬機(jī)集合VMj={vmj1,vmj2,…,vmjm′}∪{lvmj}，其中下標(biāo)m′表示主機(jī)hj上非應(yīng)急虛擬機(jī)的個(gè)數(shù)；主機(jī)hj上的第k臺(tái)虛擬機(jī)表示為vmj k∈VMj,1≤k≤m′；lvmj為主機(jī)hj上唯一的1臺(tái)應(yīng)急虛擬機(jī).對(duì)于每臺(tái)虛擬機(jī)vmj k，我們分別使用fj k，mj k，nj k表示分配給該虛擬機(jī)的CPU頻率、內(nèi)存和網(wǎng)絡(luò)帶寬.本文的調(diào)度模型如圖1所示.

圖1中，調(diào)度層的主要部件為：一個(gè)滾動(dòng)窗口(rolling horizon)、資源監(jiān)控器(resource monitor)、任務(wù)調(diào)度分析器(schedulability analyzer)和資源調(diào)配器(resource adjuster).滾動(dòng)窗口容納新到達(dá)任務(wù)和等待調(diào)度的任務(wù)；資源監(jiān)控器監(jiān)控系統(tǒng)的狀態(tài)，為任務(wù)調(diào)度提供底層資源的信息支撐；任務(wù)調(diào)度分析器負(fù)載調(diào)度滾動(dòng)窗口中的任務(wù)到虛擬機(jī)上；當(dāng)云計(jì)算數(shù)據(jù)中心的負(fù)載發(fā)生變化時(shí)，資源調(diào)配器將觸發(fā)來(lái)動(dòng)態(tài)伸縮資源，包括虛擬機(jī)(VM)和主機(jī)(host).另外，每個(gè)虛擬機(jī)上只放置一個(gè)正在執(zhí)行的任務(wù)(ET).

Fig. 1 The scheduling architecture圖1 調(diào)度架構(gòu)

2.2 任務(wù)模型

對(duì)于云服務(wù)系統(tǒng)，用戶提交的應(yīng)用具有高動(dòng)態(tài)和隨機(jī)性.本文針對(duì)的應(yīng)用是實(shí)時(shí)、非周期和獨(dú)立的任務(wù)，表示為T={t1,t2,…,tn}.這些任務(wù)的到達(dá)時(shí)間和截止期只有在任務(wù)到達(dá)之后才獲得.對(duì)于一個(gè)任務(wù)ti∈T,可以表示為ti=(ai,li,di)，這里ai，li，di分別表示任務(wù)ti的到達(dá)時(shí)間、長(zhǎng)度和截止期.由于虛擬機(jī)CPU處理能力的異構(gòu)性，假設(shè)eti,j k為任務(wù)ti在虛擬機(jī)vmj k上的執(zhí)行時(shí)間，如式(1)所示[4,22]：

eti,j k=lifj k.

(1)

2.3 主機(jī)的能耗模型

(2)

其中，vj和fj分別表示主機(jī)的電壓和頻率.

另外，由于CPU的電壓與頻率是線性關(guān)系，那么主機(jī)的活躍功率可表示為

(3)

(4)

假設(shè)執(zhí)行任務(wù)集合T的開(kāi)始時(shí)刻和結(jié)束時(shí)刻分別是st和et，主機(jī)hj的總能耗tecj表示為

(5)

那么，處理完任務(wù)集合T，云數(shù)據(jù)中心m臺(tái)主機(jī)的總能耗tec可以表示為

(6)

2.4 數(shù)學(xué)模型

根據(jù)以上描述，本文調(diào)度問(wèn)題的數(shù)學(xué)模型可以總結(jié)如下：

(7)

其中，xi,j k表示任務(wù)ti與虛擬機(jī)vmj k的映射關(guān)系，如果任務(wù)ti映射到虛擬機(jī)vmj k上，則xi,j k=1；否則，xi,j k=0.

該模型首先最大化任務(wù)的完成率，然后最小化數(shù)據(jù)中心的能量消耗.第1個(gè)約束條件表示任務(wù)需要在其截止期內(nèi)完成才滿足用戶要求的服務(wù)質(zhì)量；第2個(gè)約束條件表示任務(wù)是不可分割的，1個(gè)任務(wù)最多只能在1臺(tái)虛擬機(jī)上執(zhí)行.第3～5個(gè)約束分別表示在任何時(shí)刻主機(jī)分配給虛擬機(jī)的CPU能力、內(nèi)存和帶寬不能超過(guò)主機(jī)相應(yīng)的資源能力.

3 調(diào)度算法STARS

本節(jié)首先提出一個(gè)具有啟動(dòng)時(shí)間感知的虛擬機(jī)擴(kuò)展策略，這里的啟動(dòng)時(shí)間包括啟動(dòng)主機(jī)和創(chuàng)建虛擬機(jī)的時(shí)間，然后將以上策略集成到滾動(dòng)優(yōu)化中，形成算法STARS，用于調(diào)度實(shí)時(shí)任務(wù)、主機(jī)和虛擬機(jī).

3.1 機(jī)器啟動(dòng)時(shí)間感知的虛擬機(jī)擴(kuò)展策略

為了緩解啟動(dòng)主機(jī)和創(chuàng)建虛擬機(jī)的時(shí)間開(kāi)銷對(duì)任務(wù)截止期的影響，本節(jié)提出以下策略：在每臺(tái)活躍主機(jī)上放置1臺(tái)應(yīng)急虛擬機(jī)，該虛擬機(jī)處于完全空閑狀態(tài)時(shí)，占用主機(jī)少量的內(nèi)存(比如512 MB)和可以忽略不計(jì)的CPU資源.當(dāng)需要使用應(yīng)急虛擬機(jī)時(shí)，使用以下1個(gè)步驟增加應(yīng)急虛擬機(jī)的CPU能力.

步驟1. 如果活躍主機(jī)上剩余的CPU資源大于應(yīng)急虛擬機(jī)的資源需求，那么，增大主機(jī)的頻率，然后為應(yīng)急虛擬機(jī)配置CPU資源，如圖2所示.

如圖2①所示，在任務(wù)分配到應(yīng)急虛擬機(jī)(lash-up VM)之前，應(yīng)急虛擬機(jī)處于空閑狀態(tài)，占用主機(jī)很少的CPU資源，并且主機(jī)有足夠的剩余CPU資源；當(dāng)準(zhǔn)備分配任務(wù)到應(yīng)急虛擬機(jī)上時(shí)，如圖2②所示，迅速增大主機(jī)的工作頻率，為應(yīng)急虛擬機(jī)提供CPU資源；最后，當(dāng)應(yīng)急虛擬機(jī)完成任務(wù)后，應(yīng)急虛擬機(jī)釋放CPU資源，如圖2③所示.顯然，在主機(jī)有足夠空閑資源的情況下，步驟1能夠避免創(chuàng)建新虛擬機(jī)的時(shí)間開(kāi)銷對(duì)實(shí)時(shí)任務(wù)開(kāi)始時(shí)間的延遲，從而提高系統(tǒng)保證實(shí)時(shí)任務(wù)時(shí)效性的能力.

步驟2. 如果步驟1不可行，并且主機(jī)上存在某些虛擬機(jī)的執(zhí)行任務(wù)和等待任務(wù)可以忍受應(yīng)急虛擬機(jī)完成任務(wù)造成的延遲，那么把那些可以忍受延遲的虛擬機(jī)的CPU資源暫時(shí)轉(zhuǎn)移給應(yīng)急虛擬機(jī)使用，待應(yīng)急虛擬機(jī)完成任務(wù)后，釋放應(yīng)急虛擬機(jī)的CPU資源，并返還給其他虛擬機(jī).圖3為步驟2的示意圖.

如圖3①所示，主機(jī)的CPU資源大部分已經(jīng)被分配給虛擬機(jī)1(VM1)和虛擬機(jī)2(VM2)，主機(jī)沒(méi)有足夠的CPU資源供應(yīng)急虛擬機(jī)使用.假設(shè)虛擬機(jī)2上的執(zhí)行任務(wù)和等待任務(wù)能夠忍受應(yīng)急虛擬機(jī)執(zhí)行任務(wù)造成的延遲，如圖3②所示，將虛擬機(jī)2的CPU資源轉(zhuǎn)移給應(yīng)急虛擬機(jī).待應(yīng)急虛擬機(jī)完成任務(wù)以后，把CPU資源返還給虛擬機(jī)2，如圖3③所示.

Fig. 2 An example of Step1圖2 步驟1的示意圖

Fig. 3 An example of Step2圖3 步驟2的示意圖

Fig. 4 An example of Step3圖4 步驟3的示意圖

步驟3. 如果以上2個(gè)步驟都不可行，并且主機(jī)上存在某些虛擬機(jī)，能夠忍受啟動(dòng)主機(jī)后遷移它們到其他主機(jī)的時(shí)間延遲，那么，把這些虛擬機(jī)的CPU資源轉(zhuǎn)移給應(yīng)急虛擬機(jī)使用.同時(shí)開(kāi)啟1臺(tái)關(guān)閉的主機(jī)，待關(guān)閉主機(jī)開(kāi)啟后，再將那些能夠容忍延遲的虛擬機(jī)，遷移到剛啟動(dòng)的主機(jī)上，然后恢復(fù)它們的CPU資源供給.圖4為步驟3的示意圖.

如圖4①所示，主機(jī)1沒(méi)有足夠的剩余資源給應(yīng)急虛擬機(jī)1使用，同時(shí)，應(yīng)急虛擬機(jī)1需要運(yùn)行的時(shí)間比較長(zhǎng)，主機(jī)1上的其他虛擬機(jī)都不能忍受運(yùn)行應(yīng)急虛擬機(jī)帶來(lái)的延遲.如果虛擬機(jī)2能夠忍受啟動(dòng)主機(jī)和遷移虛擬機(jī)的時(shí)間開(kāi)銷，那么把虛擬機(jī)2的CPU資源轉(zhuǎn)移給應(yīng)急虛擬機(jī)1使用，同時(shí)開(kāi)啟1臺(tái)關(guān)閉的主機(jī)，如圖4②所示.待關(guān)閉的主機(jī)啟動(dòng)后，把虛擬機(jī)2從主機(jī)1遷移到主機(jī)2，如圖4③所示；待虛擬機(jī)2成功遷移到主機(jī)2后，主機(jī)2為虛擬機(jī)2供給CPU資源，同時(shí)在主機(jī)2上創(chuàng)建1臺(tái)應(yīng)急虛擬機(jī)，如圖4④所示.

3.2 算法設(shè)計(jì)

本節(jié)將啟動(dòng)時(shí)間感知的擴(kuò)展策略集成到滾動(dòng)優(yōu)化，形成具有啟動(dòng)時(shí)間感知能力的調(diào)度算法STARS，來(lái)實(shí)現(xiàn)實(shí)時(shí)任務(wù)和資源的調(diào)度.在算法STARS中，所有未開(kāi)始執(zhí)行的任務(wù)都在滾動(dòng)窗口RH中等待，直到準(zhǔn)備被執(zhí)行時(shí)，才被從RH中傳輸?shù)教摂M機(jī).當(dāng)新任務(wù)到達(dá)時(shí)，算法STARS將重新調(diào)度滾動(dòng)窗口中的所有等待任務(wù)和新到達(dá)任務(wù)，如算法1所示.

算法1. STARS:啟動(dòng)時(shí)間感知的調(diào)度算法.

算法1中，當(dāng)新任務(wù)到達(dá)時(shí)，滾動(dòng)窗口中所有任務(wù)的調(diào)度方案將被刪除，并且更新系統(tǒng)中每臺(tái)虛擬機(jī)的就緒時(shí)間(算法1中行③)，就緒時(shí)間是指虛擬機(jī)完成所有分配給它的任務(wù)的時(shí)間；然后，把新到達(dá)的任務(wù)加入到滾動(dòng)窗口RH(行④)；接著，對(duì)滾動(dòng)窗口中所有任務(wù)按照它們截止期進(jìn)行非降序排序(行⑤)；最后，調(diào)用函數(shù)ScheduleTask()為滾動(dòng)窗口中的每個(gè)任務(wù)生成調(diào)度方案(行⑥～⑧).

函數(shù)ScheduleTask()的偽代碼如算法2所示.

算法2. 函數(shù)ScheduleTask().

如算法2所示，函數(shù)使用3個(gè)遞進(jìn)的步驟把任務(wù)映射虛擬機(jī)上.步驟1：在已經(jīng)開(kāi)啟的虛擬機(jī)中為該任務(wù)尋找1臺(tái)目標(biāo)虛擬機(jī)(算法2中行②～⑦)，該目標(biāo)虛擬機(jī)能夠滿足任務(wù)的時(shí)效性要求，并且使得任務(wù)的完成時(shí)間最小(行④).如果步驟1不能夠成功調(diào)度任務(wù)，那么轉(zhuǎn)入步驟2：調(diào)用虛擬機(jī)伸展策略(即函數(shù)ScaleUpResource()，算法4)為任務(wù)增加新虛擬機(jī)(行⑩).如果以上2個(gè)步驟都不能成功調(diào)度任務(wù)，那么執(zhí)行步驟3：調(diào)用函數(shù)FindLash-UpVM()來(lái)為該任務(wù)尋找1臺(tái)應(yīng)急虛擬機(jī)(行).如果存在應(yīng)急虛擬機(jī)能夠滿足該任務(wù)的時(shí)效性要求(行)，那么將該任務(wù)放置到應(yīng)急虛擬機(jī)上執(zhí)行(行)，否則，拒絕執(zhí)行該任務(wù)(行).

函數(shù)FindLashUpVM()的偽代碼如算法3所示.

算法3. 函數(shù)FindLashUpVM().

如算法3所示，函數(shù)FindLashUpVM()使用了3.1節(jié)中的3個(gè)策略為緊急任務(wù)快速擴(kuò)展虛擬機(jī).策略1：如果存在某臺(tái)活躍主機(jī)上剩余的CPU資源大于應(yīng)急虛擬機(jī)的資源需求，那么，增大主機(jī)的頻率，然后為應(yīng)急虛擬機(jī)配置CPU資源來(lái)完成該任務(wù)(算法3中行②～⑦).如果策略1不可行，轉(zhuǎn)入策略2：如果存在某臺(tái)主機(jī)，它的虛擬機(jī)集合中存在某些虛擬機(jī)的執(zhí)行任務(wù)和等待任務(wù)可以忍受應(yīng)急虛擬機(jī)完成該任務(wù)造成的延遲，那么，把那些可以忍受延遲的虛擬機(jī)的CPU資源暫時(shí)轉(zhuǎn)移給應(yīng)急虛擬機(jī)完成該任務(wù)(行⑧～).如果之前2個(gè)策略都不可行，轉(zhuǎn)入策略3：如果存在某臺(tái)主機(jī)，它的虛擬機(jī)集合中存在某些虛擬機(jī)，能夠忍受啟動(dòng)主機(jī)然后遷移它們到其他主機(jī)的時(shí)間延遲，那么，把這些虛擬機(jī)的CPU資源轉(zhuǎn)移給應(yīng)急虛擬機(jī)來(lái)完成應(yīng)急任務(wù).同時(shí)開(kāi)啟1臺(tái)關(guān)閉的主機(jī)，待關(guān)閉主機(jī)開(kāi)啟后，再將那些能夠容忍延遲的虛擬機(jī)，遷移到剛啟動(dòng)的主機(jī)上，然后恢復(fù)它們的CPU資源供給(行～).

函數(shù)ScaleUpResource()的偽代碼如算法4所示.

算法4. 函數(shù)ScaleUpResource().

如算法4所示，函數(shù)ScaleUpResource()使用了2個(gè)策略，來(lái)為云服務(wù)系統(tǒng)增加新的虛擬機(jī).策略1是在活躍主機(jī)上創(chuàng)建新虛擬機(jī)(算法4中行①～⑨).如果策略1可行，那么在目標(biāo)主機(jī)上創(chuàng)建新虛擬機(jī)(行⑤～⑧).否則，轉(zhuǎn)入策略2，該策略開(kāi)啟1臺(tái)關(guān)閉的主機(jī)，然后創(chuàng)建新虛擬機(jī)(行⑩～).策略2的具體流程如下:首先，選擇1個(gè)能夠在任務(wù)截止期內(nèi)完成該任務(wù)的虛擬機(jī)模板，同時(shí)考慮開(kāi)啟主機(jī)和創(chuàng)建虛擬機(jī)對(duì)該任務(wù)截止期的影響;然后，從關(guān)閉主機(jī)的隊(duì)列中，選出1臺(tái)能夠容納該虛擬機(jī)模板的主機(jī)(行～)，來(lái)創(chuàng)建虛擬機(jī).

當(dāng)云服務(wù)系統(tǒng)中負(fù)載下降，并且存在某些虛擬機(jī)長(zhǎng)時(shí)間空閑時(shí)，本文使用文獻(xiàn)[4]中的資源收縮策略來(lái)收縮虛擬機(jī)和主機(jī)的規(guī)模，以減少系統(tǒng)的能耗.

3.3 時(shí)間復(fù)雜度分析

定理1. 算法STARS調(diào)度一個(gè)任務(wù)集合T的時(shí)間復(fù)雜度為O(|T|×Nw×(Nvm+NH))，其中，|T|表示任務(wù)集合T中的任務(wù)數(shù)量；Nw表示等待任務(wù)的數(shù)量；Nvm和NH分別表示虛擬機(jī)和主機(jī)的數(shù)量.

證明. 計(jì)算1個(gè)任務(wù)在所有虛擬機(jī)上的開(kāi)始和結(jié)束時(shí)間的時(shí)間復(fù)雜度為O(Nvm)(見(jiàn)算法2中行②～⑦).算法2中調(diào)用函數(shù)ScaleUpResource()增加1臺(tái)虛擬機(jī)的時(shí)間復(fù)雜度為O(NH).分析如下，在算法4中，為虛擬機(jī)模板尋找1臺(tái)合適的啟動(dòng)主機(jī)的時(shí)間復(fù)雜度為O(Na)(見(jiàn)算法4中行①～⑨)，其中Na表示啟動(dòng)主機(jī)的數(shù)量；為虛擬機(jī)模板尋找1臺(tái)關(guān)閉的主機(jī)的時(shí)間復(fù)雜度為O(No)(見(jiàn)算法4中行⑩～)，其中No表示關(guān)閉主機(jī)的數(shù)量.那么，算法4的時(shí)間復(fù)雜度為O(Na+No)=O(NH)，即函數(shù)ScaleUpResource()的時(shí)間復(fù)雜度為O(NH).另外，算法2調(diào)用函數(shù)FindLashUpVM()為任務(wù)尋找1臺(tái)應(yīng)急虛擬機(jī)的時(shí)間復(fù)雜度為O(Na).那么，算法STARS調(diào)用函數(shù)ScheduleTask()調(diào)度1個(gè)任務(wù)的時(shí)間復(fù)雜度為O(Nvm+NH+Na)=O(Nvm+NH)，由于Na≤NH.因此，算法STARS調(diào)度任務(wù)集合的時(shí)間復(fù)雜度為O(|T|)O(Nw)O(Nvm+NH)=O(|T|Nw(Nvm+NH)).

證畢.

4 算法STARS的性能評(píng)估

為了檢驗(yàn)算法STARS的有效性，本節(jié)通過(guò)仿真實(shí)驗(yàn)，將算法STARS的性能與其他2個(gè)算法進(jìn)行比較，對(duì)比算法是EARH[4]和Lowest-DVFS[22].

算法EARH與算法STARS的區(qū)別在于：1)EARH在任務(wù)調(diào)度算法中沒(méi)有啟動(dòng)時(shí)間感知的策略；2)EARH考慮運(yùn)行主機(jī)在最優(yōu)頻率上進(jìn)行節(jié)能.

算法Lowest-DVFS在滿足實(shí)時(shí)任務(wù)截止期要求的條件下，把主機(jī)的工作頻率調(diào)整到最低.該算法沒(méi)有使用虛擬機(jī)整合策略來(lái)節(jié)能.

另外，本節(jié)選用以下2個(gè)性能指標(biāo)來(lái)比較不同算法的性能.

1) 任務(wù)完成率(guarantee ratio, GR).任務(wù)在截止期內(nèi)完成的比例.

2) 總能量消耗(total energy consumption，TEC).執(zhí)行完一個(gè)任務(wù)集合，云服務(wù)系統(tǒng)中所有主機(jī)消耗的總能量.

4.1 實(shí)驗(yàn)設(shè)置

在本文的實(shí)驗(yàn)中，CloudSim[23]仿真平臺(tái)被選來(lái)模擬云服務(wù)系統(tǒng)中的基礎(chǔ)設(shè)施.為了模擬云服務(wù)系統(tǒng)中的主機(jī)參數(shù)，本文使用以下5種真實(shí)主機(jī)的參數(shù)①http://www.spec.org/power_ssj2008/results：PowerEdge R730，Sugon I620-G20，RH2288H V2，Altos R360，Express5800.每種主機(jī)的數(shù)量都設(shè)為2 000臺(tái).假設(shè)啟動(dòng)主機(jī)的時(shí)間為30 s.

另外，假設(shè)云服務(wù)系統(tǒng)中有6個(gè)虛擬機(jī)模板，虛擬機(jī)模板對(duì)主機(jī)的CPU頻率的需求分別有1.0，1.5，2.0，2.5，3.0，3.5(單位GHz).使用虛擬機(jī)模板創(chuàng)建虛擬機(jī)的時(shí)間為30 s.

本節(jié)將根據(jù)Google云服務(wù)系統(tǒng)中真實(shí)任務(wù)的執(zhí)行數(shù)據(jù)②http://code.google.com/p/googleclusterdata/wiki/ClusterData2011_1來(lái)模擬隨機(jī)任務(wù).本組實(shí)驗(yàn)選擇從timestamp=1 468 890到timestamp=1 559 030，共計(jì)955 626個(gè)任務(wù)的執(zhí)行數(shù)據(jù).

由于任務(wù)執(zhí)行數(shù)據(jù)中沒(méi)有包含任務(wù)周期(cycle)和截止期的詳細(xì)信息，類似于文獻(xiàn)[24]，本節(jié)使用以下方式設(shè)置以上2個(gè)參數(shù).

對(duì)于任務(wù)的周期，本文將使用Google云服務(wù)系統(tǒng)中關(guān)于任務(wù)開(kāi)始時(shí)間、結(jié)束時(shí)間和主機(jī)CPU的平均利用率的數(shù)據(jù)來(lái)計(jì)算，如式(8)所示：

ci=(tsfinish-tsschedule)×Uavg×CCPU，

(8)

其中，tsfinish和tsschedule分別表示任務(wù)開(kāi)始和結(jié)束的時(shí)間戳；Uavg表示執(zhí)行該任務(wù)時(shí)，主機(jī)CPU的平均利用率.以上3個(gè)參數(shù)可以從Google公開(kāi)的數(shù)據(jù)獲取.CCPU表示主機(jī)CPU的處理能力，類似于本文其他實(shí)驗(yàn)中主機(jī)的參數(shù)，假設(shè)CCPU=4.0 GHz.

類似于文獻(xiàn)[4]，假設(shè)任務(wù)在虛擬機(jī)上的執(zhí)行時(shí)間為任務(wù)的周期與虛擬機(jī)CPU頻率的比值，如式(9)所示：

μi,j k=cifj k.

(9)

本節(jié)使用截止期基準(zhǔn)(deadlineBase)來(lái)控制任務(wù)的截止期，任務(wù)ti的截止期di的計(jì)算公式如式(10)所示：

di=ai+(tsfinsh-tsschedule)×deadlineBase.

(10)

4.2 任務(wù)截止期對(duì)性能的影響

為了測(cè)試任務(wù)截止期對(duì)算法性能的影響，本組實(shí)驗(yàn)選取任務(wù)集中的350 000個(gè)任務(wù)，并將它們的參數(shù)deadlineBase從1.1遞增到3.6，步長(zhǎng)為0.5.對(duì)于任務(wù)完成率(GR)和總能耗(TEC)，算法STARS，EARH，Lowest-DVFS的實(shí)驗(yàn)結(jié)果如圖5所示：

Fig. 5 Performance impact of task deadlines圖5 任務(wù)截止期對(duì)性能的影響

從圖5(a)中可以觀察到，隨著deadlineBase的增加，3個(gè)算法的任務(wù)完成率也隨之上升.這可以解釋為：隨著deadlineBase的增加，任務(wù)的截止期被延長(zhǎng)，任務(wù)的時(shí)效性要求降低，從而使得更多的任務(wù)能夠在截止期內(nèi)完成.另外，算法STARS的任務(wù)完成率平均比EARH高13.48%，比Lowest-DVFS高19.10%.然而，所有算法的任務(wù)完成率還是達(dá)不到100%.這是由于在Google的任務(wù)集中，存在執(zhí)行時(shí)間很短的任務(wù)，即使deadlineBase很大，這些任務(wù)的截止期也很小，不能夠忍受啟動(dòng)主機(jī)和創(chuàng)建虛擬機(jī)造成的延遲.在Google任務(wù)集中，執(zhí)行時(shí)間小于10 s的任務(wù)占總?cè)蝿?wù)的10%左右，對(duì)于這些執(zhí)行任務(wù)很短的任務(wù)而言，即使deadlineBase達(dá)到3.6時(shí)，它們的截止期也小于36 s.很明顯這些任務(wù)的截止期小于啟動(dòng)主機(jī)和創(chuàng)建虛擬機(jī)的時(shí)間.而算法STARS中的應(yīng)急虛擬機(jī)可以及時(shí)開(kāi)始執(zhí)行這些任務(wù)，從而能夠保障所有任務(wù)的截止期.本組實(shí)驗(yàn)結(jié)果表明，具有機(jī)器啟動(dòng)時(shí)間感知能力的算法STARS在保障實(shí)時(shí)任務(wù)時(shí)效性方面具有優(yōu)異的性能.

Fig. 6 Performance impact of task count圖6 任務(wù)量對(duì)性能的影響

從圖5(b)中可以觀察到，隨著deadlineBase的增加，Lowest-DVFS減少，EARH基本不變，STARS先增后降.另外，算法STARS消耗的能量平均比算法EARH少15.23%，比算法Lowest-DVFS少24.47%.本組實(shí)驗(yàn)結(jié)果表明，本文的虛擬機(jī)伸縮算法具有高效的節(jié)能能力.

4.3 任務(wù)數(shù)量對(duì)性能的影響

本組實(shí)驗(yàn)的目的是測(cè)試在不同任務(wù)規(guī)模下不同的算法的性能.本組實(shí)驗(yàn)將任務(wù)量從350 000遞增到950 000，步長(zhǎng)為200 000，設(shè)deadlineBase=2.1，實(shí)驗(yàn)結(jié)果如圖6所示.

如圖6(a)所示，不管任務(wù)規(guī)模如何變化，算法STARS，EARH，Lowest-DVFS的任務(wù)完成率分別穩(wěn)定在99.01%，88.66%，82.06%.這是由于擴(kuò)展虛擬機(jī)的過(guò)程中，啟動(dòng)主機(jī)和創(chuàng)建虛擬機(jī)的時(shí)間開(kāi)銷，延誤了一些截止期較短的任務(wù)的截止期.另外，算法STARS的任務(wù)完成率平均比算法EARH優(yōu)11.67%，比算法Lowest-DVFS優(yōu)20.65%.更多的解釋類似于圖5(a).

如圖6(b)所示，3個(gè)算法的能耗都隨著任務(wù)數(shù)量線性增長(zhǎng).這由于在本組試驗(yàn)中，3個(gè)算法的任務(wù)完成率都基本保持不變?nèi)鐖D6(a)，當(dāng)總?cè)蝿?wù)量增長(zhǎng)時(shí)，云服務(wù)系統(tǒng)完成的任務(wù)數(shù)量也隨之線性增長(zhǎng)，云服務(wù)系統(tǒng)的能耗與它的工作量也是正比關(guān)系.另外，算法STARS消耗的能量比算法EARH少14.98%，比算法Lowest-DVFS少24.22%.

5 結(jié)束語(yǔ)

本文針對(duì)虛擬機(jī)擴(kuò)展過(guò)程中，啟動(dòng)主機(jī)和創(chuàng)建虛擬機(jī)的時(shí)間開(kāi)銷影響實(shí)時(shí)任務(wù)時(shí)效性的問(wèn)題，提出了啟動(dòng)時(shí)間感知的虛擬機(jī)擴(kuò)展策略，借助單個(gè)虛擬機(jī)CPU頻率可以動(dòng)態(tài)調(diào)整的能力，將機(jī)器啟動(dòng)時(shí)間對(duì)新到達(dá)實(shí)時(shí)任務(wù)的影響轉(zhuǎn)移到其他能夠容忍該延遲的任務(wù).然后，將以上策略集成到滾動(dòng)優(yōu)化中，實(shí)現(xiàn)對(duì)實(shí)時(shí)任務(wù)和資源的動(dòng)態(tài)調(diào)度，降低機(jī)器啟動(dòng)時(shí)間對(duì)實(shí)時(shí)任務(wù)時(shí)效性的影響.最后，將本文的算法STARS部署到CloudSim模擬平臺(tái)中.實(shí)驗(yàn)結(jié)果顯示，算法STARS能夠有效提高虛擬化云保障實(shí)時(shí)任務(wù)時(shí)效性的能力，減少云服務(wù)系統(tǒng)的能量消耗.

[1]Chen H, Zhu X, Guo H, et al. Towards energy-efficient scheduling for real-time tasks under uncertain cloud computing environment[J]. Journal of Systems and Software, 2015 (99): 20-35

[2]Koomey J. Growth in data center electricity use 2005 to 2010[OL]. [2016-08-01]. http://www.missioncriticalmagazine.com/ext/resources/MC/Home/Files/PDFs/Koomey_Data_Center.pdf

[3]Pettey C. Gartner estimates ICT industry accounts for 2 percent of global CO2 emissions[OL]. [2016-08-01]. https://www.gartner.com/newsroom/id/503867,2007,14:2013

[4]Zhu X, Yang L T, Chen H, et al. Real-time tasks oriented energy-aware scheduling in virtualized clouds[J]. IEEE Trans on Cloud Computing, 2014, 2(2): 168-180

[5]Hermenier F, Lorca X, Menaud J M, et al. Entropy: a consolidation manager for clusters[C] //Proc of ACM SIGPLAN/SIGOPS Int Conf on Virtual Execution Environments. New York: ACM, 2009: 41-50

[6]Beloglazov A, Abawajy J, Buyya R. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[J]. Future Generation Computer Systems, 2012, 28(5): 755-768

[7]Li K, Tang X, Li K. Energy-efficient stochastic task scheduling on heterogeneous computing systems[J]. IEEE Trans on Parallel and Distributed Systems, 2014, 25(11): 2867-2876

[8]Mei J, Li K, Li K. Energy-aware task scheduling in heterogeneous computing environments[J]. Cluster Computing, 2014, 17(2): 537-550

[9]Ma Y, Gong B, Sugihara R, et al. Energy-efficient deadline scheduling for heterogeneous systems[J]. Journal of Parallel and Distributed Computing, 2012, 72(12): 1725-1740

[10]Xiao Z, Song W, Chen Q. Dynamic resource allocation using virtual machines for cloud computing environment[J]. IEEE Trans on Parallel and Distributed Systems, 2013, 24(6): 1107-1117

[11]Ma Yan, Gong Bin, Zou Lida. Duplication based energy efficient scheduling for dependent tasks in grid environment[J]. Journal of Computer Research and Development, 2013, 50(2): 420-429 (in Chinese)(馬艷, 龔斌, 鄒立達(dá). 網(wǎng)格環(huán)境下基于復(fù)制的能耗有效依賴任務(wù)調(diào)度研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(2): 420-429)

[12]Wei Liang, Huang Tao, Chen Jianya, et al. Workload prediction-based algorithm for consolidation of virtual machines[J]. Journal of Electronics & Information Technology, 2013, 35(6): 1271-1276 (in Chinese)(魏亮, 黃韜, 陳建亞, 等. 基于工作負(fù)載預(yù)測(cè)的虛擬機(jī)整合算法[J]. 電子與信息學(xué)報(bào), 2013, 35(6): 1271-1276)

[13]He Yanxiang, Yu Tao, Chen Yong, et al. Green demands oriented data allocation for embedded systems[J]. Journal of Computer Research and Development, 2015, 52(1): 94-104 (in Chinese)(何炎祥, 喻濤, 陳勇, 等. 面向嵌入式系統(tǒng)綠色需求的數(shù)據(jù)分配方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(1): 94-104)

[14]Hsu C H, Slagter K D, Chen S C, et al. Optimizing energy consumption with task consolidation in clouds[J]. Information Sciences, 2014, 258: 452-462

[15]Zhou Jingcai, Zhang Huyin, Zha Wenliang, et al. User-aware resource provision policy for cloud computing[J]. Journal of Computer Research and Development, 2014, 51(5): 1108-1119 (in Chinese)(周景才, 張滬寅, 查文亮, 等. 云計(jì)算環(huán)境下基于用戶行為特征的資源分配策略[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(5): 1108-1119)

[16]Corradi A, Fanelli M, Foschini L. VM consolidation: A real case based on openStack cloud[J]. Future Generation Computer Systems, 2014 (32): 118-127

[17]Ding Youwei, Qin Xiaolin, Liu Liang, et al. An energy efficient algorithm for big data processing in heterogeneous cluster[J]. Journal of Computer Research and Development, 2015, 52(2): 377-390 (in Chinese)(丁有偉, 秦小麟, 劉亮, 等. 一種異構(gòu)集群中能量高效的大數(shù)據(jù)處理算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(2): 377-390)

[18]Li Qiang, Hao Qinfen, Xiao Limin, et al. Adaptive management and multi-objective optimization for virtual machine placement in cloud computing[J]. Chinese Journal of Computers, 2011, 34(12): 2253-2264 (in Chinese)(李強(qiáng), 郝沁汾, 肖利民, 等. 云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(12): 2253-2264)

[19]Yin Xiaolong, Li Jun, Wan Mingxiang. Virtual machines scheduling algorithm based on improved NSGA II in cloud environment[J]. Computer Technology and Development, 2014, 24(8): 71-75 (in Chinese)(殷小龍, 李君, 萬(wàn)明祥. 云環(huán)境下基于改進(jìn) NSGA II 的虛擬機(jī)調(diào)度算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2014, 24(8): 71-75)

[20]Xiao Peng, Hu Zhigang, Qu Xilong. Energy-aware scheduling policy for data-intensive workflow[J]. Journal on Communications, 2015, 36(1): 1-10 (in Chinese)(肖鵬, 胡志剛, 屈喜龍. 面向數(shù)據(jù)密集型工作流的能耗感知調(diào)度策略[J]. 通信學(xué)報(bào), 2015, 36(1): 1-10)

[21]Li K, Tang X, Yin Q. Energy-aware scheduling algorithm for task execution cycles with normal distribution on heterogeneous computing systems[C] //Proc of the 41st Int Conf on Parallel Processing (ICPP). Piscataway, NJ: IEEE, 2012: 40-47

[22]Kim K H, Beloglazov A, Buyya R. Power-aware provisioning of cloud resources for real-time services[C] //Proc of the 7th ACM Int Workshop on Middleware for Grids, Clouds and e-Science. New York: ACM, 2009: 1-7

[23]Calheiros R N, Ranjan R, Beloglazov A, et al. CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software: Practice and Experience, 2011, 41(1): 23-50

[24]Moreno I S, Garraghan P, Townend P, et al. An approach for characterizing workloads in Google cloud to derive realistic resource utilization models[C] //Proc of the 7th IEEE Int Symp on Service Oriented System Engineering (SOSE). Piscataway, NJ: IEEE, 2013: 49-60

Chen Huangke, born in 1990. Received his BSc and MSc degrees from the College of Information and System Management at National University of Defense Technology(NUDT), China, in 2012 and 2014, respectively. Currently, he is PhD candidate at the same college and university. His main research interests include scheduling, resource management and data security in cloud computing.

Zhu Jianghan, born in 1972. Received his MSc and PhD degrees in management science and technology from NUDT, China, in 2000 and 2004, respectively. His main research interests include combinatorial optimization, cloud services, space-based information systems, and satellite application information link.

Zhu Xiaomin, born in 1979. Received his PhD degree in computer science from Fudan University, Shanghai, China, in 2009. He is currently associate professor in the College of Information Systems and Management at NUDT, China. His main research interests include scheduling and resource management in distributed systems.

Ma Manhao, born in 1974. Received his MSc and PhD degrees in management science and technology from NUDT, China, in 2004 and 2008, respectively. He is currently associate professor in the School of Information Systems and Management at NUDT. His main research interests include combinatorial optimization, and space-based information systems.

Zhang Zhenshi, born in 1979. Received his MSc degree from NUDT, China, in 2010. His main research interests include cognitive computing and decision neuro-science, planning & scheduling, and multiple satellites.

Resource-Delay-Aware Scheduling for Real-Time Tasks in Clouds

Chen Huangke, Zhu Jianghan, Zhu Xiaomin, Ma Manhao, and Zhang Zhenshi

(ScienceandTechnologyonInformationSystemsEngineeringLaboratory,NationalUniversityofDefenseTechnology,Changsha410073)

Green cloud computing has become a central issue, and dynamical consolidation of virtual machines (VMs) and turning off the idle hosts show promising ways to reduce the energy consumption for cloud data centers. When the workload of the cloud platform increases rapidly, more hosts will be started on and more VMs will be deployed to provide more available resources. However, the time overheads of turning on hosts and starting VMs will delay the start time of tasks, which may violate the deadlines of real-time tasks. To address this issue, three novel startup-time-aware policies are developed to mitigate the impact of machine startup time on timing requirements of real-time tasks. Based on the startup-time-aware policies, we propose an algorithm called STARS to schedule real-time tasks and resources, such making a good trade-off between the schedulibility of real-time tasks and energy saving. Lastly, we conduct simulation experiments to compare STARS with two existing algorithms in the context of Google’s workload trace, and the experimental results show that STARS outperforms those algorithms with respect to guarantee ratio, energy saving and resource utilization.

cloud computing; virtualization; scheduling; real-time tasks; energy-efficient; startup time

2015-12-21；

2016-09-06

國(guó)家自然科學(xué)基金項(xiàng)目(61572511, 71271213)；國(guó)防科學(xué)技術(shù)大學(xué)科研計(jì)劃項(xiàng)目(ZK16-03-09) This work was supported by the National Natural Science Foundation of China (61572511, 71271213) and the Scientific Research Project of National University of Defense Technology (ZK16-03-09).

TP393