張 奕,程小輝,陳柳華

(1.桂林理工大學(xué) 信息科學(xué)與工程學(xué)院, 廣西 桂林 541004;2.廣西嵌入式技術(shù)與智能系統(tǒng)重點(diǎn)實(shí)驗(yàn)室(桂林理工大學(xué)), 廣西 桂林 541004;3.克萊姆森大學(xué) 電子與計(jì)算機(jī)工程系, 南卡羅來納州 克萊姆森市 29631, 美國) (*通信作者電子郵箱zywait@glut.edu.cn)

虛擬云下滿足多重約束的時限敏感任務(wù)調(diào)度算法

張 奕1,2*,程小輝1,2,陳柳華3

(1.桂林理工大學(xué) 信息科學(xué)與工程學(xué)院, 廣西 桂林 541004;2.廣西嵌入式技術(shù)與智能系統(tǒng)重點(diǎn)實(shí)驗(yàn)室(桂林理工大學(xué)), 廣西 桂林 541004;3.克萊姆森大學(xué) 電子與計(jì)算機(jī)工程系, 南卡羅來納州 克萊姆森市 29631, 美國) (*通信作者電子郵箱zywait@glut.edu.cn)

目前以虛擬云服務(wù)平臺作為強(qiáng)大計(jì)算平臺的虛擬云環(huán)境下，許多現(xiàn)存調(diào)度方法致力于合并虛擬機(jī)以減少物理機(jī)數(shù)目，從而達(dá)到減少能源消耗的目的，但會引入高額虛擬機(jī)遷移成本；此外，現(xiàn)存方法也沒有考慮導(dǎo)致用戶高額支付成本的成本因子影響。以減少云服務(wù)提供者能源消耗和云服務(wù)終端用戶支付成本為目標(biāo)，同時保障用戶任務(wù)的時限要求，提出一種能源與時限可感知的非遷移調(diào)度(EDA-NMS)算法。EDA-NMS利用任務(wù)時限的松弛度，延遲寬松時限任務(wù)的執(zhí)行從而無需喚醒新的物理機(jī)，更無需引入虛擬機(jī)動態(tài)遷移成本，以達(dá)到減少能源消耗的目的。多重?cái)U(kuò)展實(shí)驗(yàn)結(jié)果表明，EDA-NMS采用成本和能耗有效的虛擬機(jī)實(shí)例類型組合方案，與主動及響應(yīng)式調(diào)度(PRS)算法相比，在減少靜態(tài)能耗的同時，能更有效地滿足用戶關(guān)鍵任務(wù)的敏感時限并確保用戶支付成本最低。

虛擬云;實(shí)時任務(wù);調(diào)度;關(guān)鍵度;能源可感知

0 引言

成千上萬的物理主機(jī)所構(gòu)成的云數(shù)據(jù)中心消耗巨大的能源,為了提高能源的有效性,面向云應(yīng)用場景的綠色計(jì)算和能源保護(hù)獲得了大量關(guān)注[1]。其中,將應(yīng)用與底層復(fù)雜環(huán)境相隔離和抽象的虛擬化技術(shù),是近年來減少能源消耗方面最有發(fā)展前景的技術(shù)之一。以虛擬化技術(shù)支撐的虛擬云服務(wù)平臺作為強(qiáng)大的計(jì)算平臺,調(diào)度執(zhí)行不同用戶提交的任務(wù)集,能在一定程度上減少物理主機(jī)數(shù)量、提高能源利用的有效性。虛擬云服務(wù)平臺上大部分應(yīng)用是對結(jié)果的反應(yīng)時間具有時限約束的實(shí)時應(yīng)用程序[2],即組成此類應(yīng)用的任務(wù)具有嚴(yán)格時限需求且需要可預(yù)測性保證。此類任務(wù)的到達(dá)時間是動態(tài)的,任務(wù)的執(zhí)行周期預(yù)測是困難的甚至是不可能的[3]。在虛擬機(jī)資源集上調(diào)度從不同用戶提交的具有時限約束的任務(wù)集問題,是獲取能源有效性的關(guān)鍵。同時,如何達(dá)到最小化某個任務(wù)完成時間或系統(tǒng)總完成時間的目標(biāo),也是獲取高性能的關(guān)鍵因素。但能源消耗和系統(tǒng)性能之間存在固有矛盾,仍沒有一個解決方案可以在任務(wù)完成時間和能量消耗兩個目標(biāo)對象上同時取得最優(yōu)值。除此之外,虛擬云環(huán)境下用戶需租用云資源,同時需考慮經(jīng)濟(jì)成本因素[4]。

滿足敏感時限、成本與能耗多重約束條件的調(diào)度問題是NP完全問題,無法找到最優(yōu)解,只能采用啟發(fā)式方法。到目前為止,以往各種啟發(fā)式方法不能同時滿足以上多重約束條件,不能直接重用。如何權(quán)衡系統(tǒng)性能與成本、能耗之間的關(guān)系,使用戶以最低的成本和能耗獲得最佳的系統(tǒng)性能,仍是目前虛擬云計(jì)算環(huán)境下的一個挑戰(zhàn)。針對以上挑戰(zhàn)和關(guān)鍵問題,本文提出一種啟發(fā)式任務(wù)調(diào)度算法——能源和時限可感知的非遷移調(diào)度(Energy and Deadline Aware with Non-Migration Scheduling, EDA-NMS)算法。EDA-NMS具有無需虛擬機(jī)遷移的特點(diǎn),且滿足能耗、成本與時限可感知多重約束。EDA-NMS在無需喚醒新的物理主機(jī)情況下,選擇成本有效的虛擬機(jī)實(shí)例,通過主動延后具有寬松時限條件的任務(wù)開始執(zhí)行時間,保障嚴(yán)格時限條件的任務(wù)完成時間,達(dá)到減少能源消耗的目的,同時避免了虛擬機(jī)動態(tài)遷移引入的遷移成本消耗。為了最大化滿足用戶不同優(yōu)先級任務(wù)時限需求,提出了實(shí)時關(guān)鍵度的概念。關(guān)鍵度是除了軟、硬實(shí)時之外的另一維度的任務(wù)特征,用于測量任務(wù)失敗對系統(tǒng)性能穩(wěn)定性的影響程度(任務(wù)失敗對系統(tǒng)穩(wěn)定性影響越大,任務(wù)的關(guān)鍵度越高)[5]。如果兩個任務(wù)時限相同,則優(yōu)先調(diào)度高關(guān)鍵度任務(wù),保障系統(tǒng)性能的穩(wěn)定性。

1 相關(guān)研究

大部分現(xiàn)存的云調(diào)度算法,如:Hadoop MapReduce的先進(jìn)先出(First In First Out, FIFO)調(diào)度[6],Facebook公平調(diào)度[7],Yahoo的性能調(diào)度等[8],不支持軟實(shí)時調(diào)度或服務(wù)質(zhì)量(Quality of Service, QoS)條件約束。文獻(xiàn)[9]提出的實(shí)時調(diào)度策略在任何時刻在每個虛擬機(jī)實(shí)例內(nèi)只允許執(zhí)行一個任務(wù),隨著任務(wù)數(shù)目增加,所需的虛擬機(jī)實(shí)例將大量增加而造成可觀的靜態(tài)能源消耗。文獻(xiàn)[3]實(shí)現(xiàn)的平行軟實(shí)時調(diào)度,雖然考慮了軟實(shí)時和同步問題,但沒有考慮最大化單臺物理機(jī)的資源利用率。文獻(xiàn)[4]提出的水平滾動優(yōu)化策略根據(jù)任務(wù)的時限不同將任務(wù)分配到不同的虛擬機(jī)實(shí)例,但此算法沒有充分考慮實(shí)時任務(wù)的其他特性(如:關(guān)鍵度)。文獻(xiàn)[10]提出的虛擬機(jī)調(diào)度算法關(guān)注提高到達(dá)任務(wù)的錄用率,卻忽略了在虛擬機(jī)上運(yùn)行的負(fù)載類型,從而影響調(diào)度算法的QoS保證率。因此,以上的研究成果均不能直接重用以滿足能源、成本和時限多重約束和優(yōu)化目標(biāo)。

總能源消耗包含兩部分:靜態(tài)能源消耗和動態(tài)能源消耗。靜態(tài)能耗是物理主機(jī)節(jié)點(diǎn)在空閑狀態(tài)下所消耗的能源;而動態(tài)能耗則是物理主機(jī)節(jié)點(diǎn)在繁忙狀態(tài)下所消耗的能源?；趧討B(tài)電壓頻率調(diào)整(Dynamic Voltage and Frequency Scaling， DVFS)的調(diào)度算法為任務(wù)提供最小的CPU利用率,達(dá)到最大限度減少動態(tài)能耗的目的[11-12]。文獻(xiàn)[13]提出的能源有效自適應(yīng)調(diào)度算法(Energy-Efficient Adaptive Scheduling Algorithm, EASA)能夠根據(jù)系統(tǒng)負(fù)載自適應(yīng)地調(diào)整所提供的電壓,有效地減少了動態(tài)能耗。以往大部分基于電壓調(diào)節(jié)的研究工作重點(diǎn)關(guān)注的是最大限度地減少動態(tài)能耗,然而即使運(yùn)行的是低速任務(wù),靜態(tài)能耗仍會持續(xù)很長的時間。部分能源可感知調(diào)度算法(如文獻(xiàn)[2,9-10,14-15]算法),試圖通過進(jìn)一步利用虛擬機(jī)動態(tài)遷移技術(shù)合并虛擬機(jī)以減少物理機(jī)數(shù)量,達(dá)到減少靜態(tài)能耗的目的,但卻會引入高額遷移成本消耗。本文提出的啟發(fā)式任務(wù)調(diào)度算法與以往研究不同的是:通過選擇不同計(jì)算性能的虛擬機(jī)實(shí)例來調(diào)節(jié)實(shí)時任務(wù)的執(zhí)行速度,而無需在物理主機(jī)節(jié)點(diǎn)之間動態(tài)遷移虛擬機(jī),能達(dá)到減少系統(tǒng)開銷并達(dá)到減少靜態(tài)能耗的目的。

2 系統(tǒng)模型與體系結(jié)構(gòu)

2.1 系統(tǒng)體系結(jié)構(gòu)

如圖1所示,虛擬云環(huán)境下的組合調(diào)度體系結(jié)構(gòu)由全局調(diào)度器(Global Scheduler, GS)與局部虛擬機(jī)服務(wù)供應(yīng)者集合(Local VM Providers, LP)兩個核心部件和一些子組件(性能監(jiān)控器,可調(diào)度性分析器和成本函數(shù))組成。

圖1 可組合調(diào)度體系結(jié)構(gòu)

云端服務(wù)供應(yīng)者(Cloud Service Provider, CSP)擁有大量數(shù)據(jù)中心和服務(wù)器集群,終端用戶通過分布式方式訪問CSP提供的服務(wù),并按規(guī)定付費(fèi)。CSP通過LP為終端用戶提供服務(wù),即LP負(fù)責(zé)給用戶任務(wù)分配云端資源:

LP={lp1,lp2,…,lpn}

(1)

某lpj與某用戶uj之間一一對應(yīng),即lpj綁定于特定用戶uj,并擁有物理主機(jī)集合PMj為uj提供所需的計(jì)算能力,存儲能力和滿足服務(wù)級協(xié)定(Service Level Agreement, SLA)的不同服務(wù)。

(2)

lpj管理和監(jiān)視在不同物理主機(jī)上啟動的屬于uj的虛擬機(jī)實(shí)例集合VMj,直至實(shí)例關(guān)閉。VMj給終端用戶uj提供服務(wù),保證用戶上下文安全性和私密性。

(3)

(4)

2.2 任務(wù)模型及特性

2.3 任務(wù)靜態(tài)松弛度模型

(5)

其中:tc表示當(dāng)前時間。

2.4 任務(wù)完成時間預(yù)測模型

圖2 實(shí)時任務(wù)插入

(6)

(7)

(8)

(9)

全局調(diào)度器首先將屬于某用戶uj的任務(wù)分配到局部虛擬機(jī)服務(wù)供應(yīng)者lpj。當(dāng)圖3所示的情景2(圖3(a))或情景3(圖3(b))出現(xiàn)時,lpj將任務(wù)傳遞到性能更高虛擬機(jī)實(shí)例。如果任務(wù)的時限仍不能得到滿足,將啟動更多的虛擬機(jī)實(shí)例直到情景2或情景3不再出現(xiàn)。

2.5 能源消耗模型

(10)

(12)

(13)

圖3 不同γ值下的總能源消耗

只要系統(tǒng)存在較高的靜態(tài)能耗,僅僅減少動態(tài)能耗并不能降低總能耗。以往研究集中于合并虛擬機(jī)來減輕靜態(tài)能耗,然而依賴于網(wǎng)絡(luò)架構(gòu)的移植過程引入了高開銷。除此之外,源局部虛擬機(jī)服務(wù)供應(yīng)者花費(fèi)更多計(jì)算能力在動態(tài)遷移間隔瞬間,可能導(dǎo)致違反SLA。為了解決這個問題,本文提出一種任務(wù)調(diào)度策略:在保證滿足大多數(shù)任務(wù)時限的同時盡可能啟動虛擬機(jī)實(shí)例越少越好,達(dá)到提高CPU資源利用率、減少靜態(tài)能耗的目的。

3 時限保障調(diào)度策略

文獻(xiàn)[2]只允許一個任務(wù)在虛擬機(jī)實(shí)例中排隊(duì)等待執(zhí)行。當(dāng)任務(wù)數(shù)目龐大時,導(dǎo)致大量任務(wù)滯留在全局等待隊(duì)列中成為性能瓶頸,引起大量任務(wù)錯過其時限。此外,由于排序操作時間依賴于RTQ隊(duì)列長度,因此增加了調(diào)度算法的時間復(fù)雜度。本文利用局部等待隊(duì)列構(gòu)建的調(diào)度體系結(jié)構(gòu),避免了上述對調(diào)度算法所造成的大量任務(wù)錯過其時限和時間復(fù)雜度增加的問題。EDA-NMS算法詳細(xì)偽代碼如下所示。

算法1 EDA-NMS算法。

RTQ←NULL;

NRTQ←NULL;

ELSE

END IF

WHILERTQ!= NULL DO

RTQ隊(duì)列中的任務(wù)按松弛度升序排序;

END IF

執(zhí)行LRTS算法(算法2);

END WHILE

WHILERTQ==NULL amp;amp;NRTQ!= NULL DO

END FOR

END WHILE

END FOR

算法2 LRTS算法。

END WHILE

END WHILE

ELSE

END IF

4 調(diào)度性能評價

4.1 環(huán)境設(shè)置

本文利用CloudSim仿真器執(zhí)行擴(kuò)展實(shí)驗(yàn)評價EDA-NMS算法的有效性[25]。通過以下性能度量指標(biāo)和詳細(xì)參數(shù)設(shè)置,將EDA-NMS與主動及響應(yīng)式調(diào)度(Proactive and Reactive Scheduling, PRS)算法[2]進(jìn)行定量比較,來證明EDA-NMS獲得的性能提升。

1)時限錯過率:完成時間晚于時限的任務(wù)數(shù)和總?cè)蝿?wù)數(shù)的比率。

2)響應(yīng)性:反應(yīng)時間間隔,例如,實(shí)時任務(wù)完成時間與時限的延遲間隔。

3)任務(wù)平均執(zhí)行時間:

其中Nt是總?cè)蝿?wù)數(shù)。

4)通過間隔數(shù)計(jì)算任務(wù)時限:

其中:U[0,500]s定義為均勻分布在0 s～500 s的變量,由此變量控制任務(wù)時限的松緊度。

6)任務(wù)到達(dá)服從到達(dá)速率為λ的泊松分布(Poisson(λ)),λ=4。

4.2 可變工作負(fù)載類型下的性能分析

本組實(shí)驗(yàn)測試針對不同類型(計(jì)算密集型與混合類型)工作負(fù)載算法的調(diào)度性能。對于計(jì)算密集型負(fù)載,主要性能瓶頸是CPU計(jì)算能力。因此,忽略其他資源(例如,內(nèi)存、磁盤和網(wǎng)絡(luò)I/O)對調(diào)度策略的影響。針對混合類型工作負(fù)載,仿真三種類型工作負(fù)載(計(jì)算密集型、I/O密集型和混合型)。同時按亞馬遜 AWS EC2標(biāo)準(zhǔn)仿真三種虛擬機(jī)實(shí)例類型(通用型、高端CPU型和高端內(nèi)存型)。不同類型工作負(fù)載在不同類型虛擬機(jī)實(shí)例上的單位執(zhí)行時間與運(yùn)行成本如表1所示。

表1 混合類型工作負(fù)載單位執(zhí)行成本與時間

分別產(chǎn)生3組不同任務(wù)數(shù)計(jì)算密集型負(fù)載與混合類型負(fù)載追蹤算法性能。實(shí)驗(yàn)產(chǎn)生的結(jié)果:實(shí)時任務(wù)數(shù)nrt、拒絕的任務(wù)數(shù)nrj、拒絕任務(wù)的低中高三種關(guān)鍵度的任務(wù)數(shù)分別為nK1、nK2、nK3,如表2所示。

表2 計(jì)算密集型負(fù)載/混合類型負(fù)載部分運(yùn)行結(jié)果

不同關(guān)鍵度任務(wù)對系統(tǒng)穩(wěn)定性的影響不同,通過調(diào)整實(shí)時任務(wù)時限的松緊度,比較當(dāng)某些實(shí)時任務(wù)錯過其時限時系統(tǒng)的穩(wěn)定性。從表2結(jié)果中可以發(fā)現(xiàn)EDA-NMS算法拒絕的任務(wù)的關(guān)鍵度低于PRS算法,即EDA-NMS算法具有更高的系統(tǒng)穩(wěn)定性。

同時,表2結(jié)果表明EDA-NMS保持較低的時限錯過率。為了進(jìn)一步研究任務(wù)的執(zhí)行時間,通過累積分布函數(shù)(Cumulative Distribution Function, CDF)表示任務(wù)響應(yīng)的快慢程度(即：任務(wù)時限與任務(wù)實(shí)際完成時間之間的差值)，如圖4所示。

從圖4所示的實(shí)驗(yàn)結(jié)果可看出：在計(jì)算密集型和混合型兩種工作負(fù)載情況下，EDA-NMS算法在各種不同任務(wù)數(shù)情況下，任務(wù)反應(yīng)時間間隔均大于PRS算法，意味著EDA-NMS算法任務(wù)的實(shí)際完成時間與時限之間的差值更大，即具有更短的任務(wù)完成時間，響應(yīng)更快，效率更高。

4.3 計(jì)算成本比較

設(shè)置任務(wù)數(shù)從1 000變化到10 000,利用表1中給出的成本單價,比較EDA-NMS和PRS兩種算法針對實(shí)時任務(wù)的平均計(jì)算成本(例如,支付成本)。圖5中的實(shí)驗(yàn)結(jié)果表明,在計(jì)算密集型和混合類型工作負(fù)載情況下,EDA-NMS算法具有更低的平均計(jì)算成本。

為了進(jìn)一步評價算法性能,假設(shè)能提前獲知工作負(fù)載類型并將其分配到最適合的虛擬機(jī)實(shí)例上執(zhí)行(例如,針對計(jì)算密集型負(fù)載將其分配到高端CPU型虛擬機(jī)實(shí)例執(zhí)行)。在此假設(shè)前提下,引入一種虛擬機(jī)實(shí)例的最優(yōu)組合作為比較標(biāo)準(zhǔn)進(jìn)行性能評價。由于不可能提前知道工作負(fù)載的類型,因此最優(yōu)組合在現(xiàn)實(shí)生活中不可能實(shí)現(xiàn),僅作為評價標(biāo)準(zhǔn)。各種組合啟動的虛擬機(jī)實(shí)例類型如表3所示,每種組合實(shí)驗(yàn)都仿真運(yùn)行10 000個未知工作負(fù)載類型的任務(wù)。

運(yùn)行后的結(jié)果如表3所示,組合1、組合2和組合3這三種方案分別比最優(yōu)組合方案運(yùn)行成本高出58%、23%和17%。EDA-NMS算法采用的組合3這種虛擬機(jī)組合方案最接近最優(yōu)組合方案的成本,因此用戶的支付成本比其他兩種組合方案更低。雖然最優(yōu)組合方案可以獲得最低的成本,但其需啟動的虛擬機(jī)實(shí)例臺數(shù)更多,其靜態(tài)能耗是其他三種組合方案的1.5倍。綜合比較,EDA-NMS算法采用的組合3方案是成本和能耗有效的解決方案。

表3 不同組合的總成本比較

圖4 任務(wù)響應(yīng)性

圖5 實(shí)時任務(wù)的平均計(jì)算成本

5 結(jié)語

云數(shù)據(jù)中心中現(xiàn)存的調(diào)度方法試圖通過虛擬機(jī)動態(tài)遷移技術(shù)合并虛擬機(jī),最小化物理機(jī)數(shù)量,達(dá)到減少靜態(tài)能源消耗的目的;然而卻不可避免高額的遷移成本。本文提出的啟發(fā)式任務(wù)調(diào)度算法——EDA-NMS,通過利用某些任務(wù)具有相對松散時限的特性,主動推遲這些任務(wù)的執(zhí)行而不喚醒新的物理機(jī),可達(dá)到進(jìn)一步減少靜態(tài)能源消耗的目的。算法根據(jù)用戶指定的時限、估計(jì)的完成時間和物理主機(jī)的資源利用率,漸進(jìn)地為任務(wù)提供云服務(wù)。擴(kuò)展實(shí)驗(yàn)結(jié)果表明,本文提出的啟發(fā)式任務(wù)調(diào)度策略不僅減少了系統(tǒng)能源消耗,也減少了實(shí)時任務(wù)的完成時間，在無需引入虛擬機(jī)動態(tài)遷移開支的情況下,保證了任務(wù)時限的滿足。

References)

[1] POP F, DOBRE C, CRISTEA V, et al. Deadline scheduling for aperiodic tasks in inter-cloud environments: a new approach to resource management[J]. Journal of Supercomputing, 2015, 71(5): 1754-1765.

[2] 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 amp; Software, 2015, 99(2): 20-35.

[3] BOSSCHE R V D, VANMECHELEN K, BROECKHOVE J. Cost-optimal scheduling in hybrid IaaS clouds for deadline constrained workloads[C]// Proceedings of the 2010 IEEE 3rd International Conference on Cloud Computing. Washington, DC: IEEE Computer Society, 2010: 228-235.

[4] LONG T, VARGHESE B, BARKER A. Task scheduling on the cloud with hard constraints[C]// Proceedings of the IEEE 11th World Congress on Services. Piscataway, NJ: IEEE, 2015: 95-102.

[5] MALL R. Real-time Systems: Theory and Practice[M]. Upper Saddle River, NJ: Prentice Hall Press, 2009.

[6] XIE J, YIN S, RUAN X, et al. Improving MapReduce performance through data placement in heterogeneous Hadoop clusters[C]// Proceedings of the 2010 IEEE International Symposium on Parallel amp; Distributed Processing, Workshops and Phd Forum. Piscataway, NJ: IEEE, 2011: 1-9.

[7] ROSS C, ORR E S, SISIC M, et al. Personality and motivations associated with Facebook use[J]. Computers in Human Behavior, 2009, 5(2): 578-586.

[8] COOPER B F, RAMAKRISHNAN R, SRIVASTAVA U, et al. PNUTS: Yahoo!’s hosted data serving platform[J]. Proceedings of the VLDB Endowment, 2008, 1(2): 1277-1288.

[9] ZHU X, YANG L T, CHEN H, et al. Real-time tasks oriented energy-aware scheduling in virtualized clouds[J]. IEEE Transactions on Cloud Computing, 2014, 2(2): 168-180.

[10] QIU M, SHA H M. Cost minimization while satisfying hard/soft timing constraints for heterogeneous embedded systems[J]. ACM Transactions on Design Automation of Electronic Systems, 2009, 14(2): 1-30.

[11] TANG Z, QI L, CHENG Z, et al. An energy-efficient task scheduling algorithm in DVFS-enabled cloud environment[J]. Journal of Grid Computing, 2016, 14(1): 55-74.

[12] CALHEIROS R N, BUYYA R. Energy-efficient scheduling of urgent bag-of-tasks applications in clouds through DVFS[C]// CLOUDCOM 2014: Proceedings of the 2014 IEEE 6th International Conference on Cloud Computing Technology and Science. Washington, DC: IEEE Computer Society, 2014: 342-349.

[13] HE C, ZHU X, GUO H, et al. Rolling-horizon scheduling for energy constrained distributed real-time embedded systems[J]. Journal of Systems and Software, 2012, 85(4): 780-794,.

[14] HOSSEINIMOTLAGH S, KHUNJUSH F, SAMADZADEH R. SEATS: smart energy-aware task scheduling in real-time cloud computing[J]. Journal of Supercomputing, 2015, 71(1): 45-66.

[15] WANG W J, CHANG Y S, LO W T, et al. Adaptive scheduling for parallel tasks with QoS satisfaction for hybrid cloud environments[J]. Journal of Supercomputing, 2013, 66(2): 783-811.

[16] HOSSEINIMOTLAGH S, KHUNJUSH F, HOSSEINIMOTLAGH S. Migration-less energy-aware task scheduling policies in cloud environments[C]// Proceedings of the 2014 28th International Conference on Advanced Information Networking and Applications Workshops. Washington, DC: IEEE Computer Society, 2014: 391-397.

[17] GAO Y, WANG Y, GUPTA S K, et al. An energy and deadline aware resource provisioning, scheduling and optimization framework for cloud systems[C]// Proceedings of the 2013 International Conference on Hardware/Software Codesign and System Synthesis. Piscataway, NJ: IEEE, 2013: 1-10.

[18] BERRAL J L, GAVALDA R, TORRES J. Adaptive scheduling on power-aware managed data-centers using machine learning[C]// Proceedings of the 2011 12th IEEE/ACM International Conference on Grid Computing. Washington, DC: IEEE Computer Society, 2011: 66-73.

[19] SENGUPTA A, PAL T K. Fuzzy Preference Ordering of Interval Numbers in Decision Problems[M]. Berlin: Springer, 2009.

[20] BARUAH S, LI H, STOUGIE L. Towards the design of certifiable mixed-criticality systems[C]// Proceedings of the 2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium. Washington, DC: IEEE Computer Society, 2010: 13-22.

[21] DU G, HE H, MENG Q. Energy-efficient scheduling for tasks with deadline in virtualized environments[J]. Mathematical Problems in Engineering, 2014(2014), Article ID 496843.

[22] MAO M, LI J, HUMPHREY M. Cloud auto-scaling with deadline and budget constraints[C]// Proceedings of the 2010 11th IEEE/ACM International Conference on Grid Computing. Piscataway, NJ: IEEE, 2010: 41-48.

[23] LEI H, ZHANG T, LIU Y, et al. SGEESS: smart green energy-efficient scheduling strategy with dynamic electricity price for data center[J]. Journal of Systems amp; Software, 2015, 108: 23-38.

[24] VENI T, MARY S B S. A survey on dynamic energy management at virtualization level in cloud data centers[EB/OL]. [2017- 01- 10]. http://airccj.org/CSCP/vol3/csit3511.pdf.

[25] 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 amp; Experience, 2011, 41(1): 23-50.

[26] BELOGLAZOV A, BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[J]. Concurrency amp; Computation Practice amp; Experience, 2012, 24(13): 1397-1420.

Multi-constraintsdeadline-awaretaskschedulingheuristicinvirtualclouds

ZHANG Yi1,2*, CHENG Xiaohui1,2, CHEN Liuhua3

(1.SchoolofInformationScienceandEngineering,GuilinUniversityofTechnology,GuilinGuangxi541004,China;2.GuangxiKeyLaboratoryofEmbeddedTechnologyandIntelligentSystems(GuilinUniversityofTechnology),GuilinGuangxi541004,China;3.SchoolofElectricalandComputerEngineering,ClemsonUniversity,Clamson,SouthCarolina29631,USA)

Many existing scheduling approaches in cloud data centers try to consolidate Virtual Machines (VMs) by VM live migration technique to minimize the number of Physical Machines (PMs) and hence minimize the energy consumption, however, it introduces high migration overhead; furthermore, the cost factor that leads to high payment cost for cloud users is usually not taken into account. Aiming at energy reduction for cloud providers and payment saving for cloud users, as well as guaranteeing the deadline of user tasks, a heuristic task scheduling algorithm called Energy and Deadline-Aware with Non-Migration Scheduling (EDA-NMS) was proposed. The execution of the tasks that have loose deadlines was postponed to avoid waking up new PMs and migration overhead, thus reducing the energy consumption. The results of extensive experiments show that compared with Proactive and Reactive Scheduling (PRS) algorithm, by selecting a smart VM combination scheme, EDA-NMS can reduce the static energy consumption and ensure the lowest payment with meeting the deadline requirement for key user tasks.

virtual cloud; real-time task; scheduling; criticality; energy-aware

2017- 04- 17;

2017- 07- 10。

國家自然科學(xué)基金資助項(xiàng)目(61662017);高等學(xué)?？茖W(xué)技術(shù)研究項(xiàng)目(2013YB113);廣西重點(diǎn)實(shí)驗(yàn)室嵌入式技術(shù)和智能系統(tǒng)基金資助項(xiàng)目(桂林理工大學(xué))。

張奕(1977—),女,江西九江人,副教授,博士,CCF會員,主要研究方向:面向服務(wù)的計(jì)算、實(shí)時計(jì)算; 程小輝(1961—),男,江西樟樹人,教授,博士研究生,CCF會員,主要研究方向:物聯(lián)網(wǎng); 陳柳華(1987—),男,廣東湛江人,博士,主要研究方向:分布式計(jì)算。

1001- 9081(2017)10- 2754- 06

10.11772/j.issn.1001- 9081.2017.10.2754

TP391.41

A

This work is partially supported by the National Natural Science Foundation of China (61662017), the Scientific and Technological Research Program for Guangxi Educational Commission (2013YB113), the Guangxi Key Laboratory Fund of Embedded Technology and Intelligent Systems (Guilin University of Technology).

ZHANGYi, born in 1977, Ph. D., associate professor. Her research interests include service oriented computing, real-time computing.

CHENGXiaohui, born in 1961, Ph. D. candidate, professor. His research interests include Internet of things.

CHENLiuhua, born in 1987, Ph. D. His research interests include distributed computing.