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

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

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

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

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

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

云計算;虛擬化;調(diào)度;實時任務(wù);節(jié)能;機器啟動時間

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

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

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

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

1 相關(guān)工作

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

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

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

2 問題描述

2.1 調(diào)度框架

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

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

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

2.2 任務(wù)模型

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

eti,j k=lifj k.

(1)

2.3 主機的能耗模型

(2)

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

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

(3)

(4)

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

(5)

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

(6)

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

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

(7)

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

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

3 調(diào)度算法STARS

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

3.1 機器啟動時間感知的虛擬機擴展策略

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

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

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

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

如圖3①所示，主機的CPU資源大部分已經(jīng)被分配給虛擬機1(VM1)和虛擬機2(VM2)，主機沒有足夠的CPU資源供應(yīng)急虛擬機使用.假設(shè)虛擬機2上的執(zhí)行任務(wù)和等待任務(wù)能夠忍受應(yīng)急虛擬機執(zhí)行任務(wù)造成的延遲，如圖3②所示，將虛擬機2的CPU資源轉(zhuǎn)移給應(yīng)急虛擬機.待應(yīng)急虛擬機完成任務(wù)以后，把CPU資源返還給虛擬機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個步驟都不可行，并且主機上存在某些虛擬機，能夠忍受啟動主機后遷移它們到其他主機的時間延遲，那么，把這些虛擬機的CPU資源轉(zhuǎn)移給應(yīng)急虛擬機使用.同時開啟1臺關(guān)閉的主機，待關(guān)閉主機開啟后，再將那些能夠容忍延遲的虛擬機，遷移到剛啟動的主機上，然后恢復(fù)它們的CPU資源供給.圖4為步驟3的示意圖.

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

3.2 算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證畢.

4 算法STARS的性能評估

為了檢驗算法STARS的有效性，本節(jié)通過仿真實驗，將算法STARS的性能與其他2個算法進行比較，對比算法是EARH[4]和Lowest-DVFS[22].

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

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

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

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

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

4.1 實驗設(shè)置

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

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

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

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

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

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

(8)

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

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

μi,j k=cifj k.

(9)

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

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

(10)

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

本文針對虛擬機擴展過程中，啟動主機和創(chuàng)建虛擬機的時間開銷影響實時任務(wù)時效性的問題，提出了啟動時間感知的虛擬機擴展策略，借助單個虛擬機CPU頻率可以動態(tài)調(diào)整的能力，將機器啟動時間對新到達實時任務(wù)的影響轉(zhuǎn)移到其他能夠容忍該延遲的任務(wù).然后，將以上策略集成到滾動優(yōu)化中，實現(xiàn)對實時任務(wù)和資源的動態(tài)調(diào)度，降低機器啟動時間對實時任務(wù)時效性的影響.最后，將本文的算法STARS部署到CloudSim模擬平臺中.實驗結(jié)果顯示，算法STARS能夠有效提高虛擬化云保障實時任務(wù)時效性的能力，減少云服務(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)(馬艷, 龔斌, 鄒立達. 網(wǎng)格環(huán)境下基于復(fù)制的能耗有效依賴任務(wù)調(diào)度研究[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)(魏亮, 黃韜, 陳建亞, 等. 基于工作負載預(yù)測的虛擬機整合算法[J]. 電子與信息學(xué)報, 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]. 計算機研究與發(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)(周景才, 張滬寅, 查文亮, 等. 云計算環(huán)境下基于用戶行為特征的資源分配策略[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]. 計算機研究與發(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)(李強, 郝沁汾, 肖利民, 等. 云計算中虛擬機放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J]. 計算機學(xué)報, 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)(殷小龍, 李君, 萬明祥. 云環(huán)境下基于改進 NSGA II 的虛擬機調(diào)度算法[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é)報, 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

國家自然科學(xué)基金項目(61572511, 71271213)；國防科學(xué)技術(shù)大學(xué)科研計劃項目(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