虛擬云下滿足多重約束的時限敏感任務調度算法

張 奕,程小輝,陳柳華

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

虛擬云下滿足多重約束的時限敏感任務調度算法

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

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

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

虛擬云;實時任務;調度;關鍵度;能源可感知

0 引言

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

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

1 相關研究

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

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

2 系統模型與體系結構

2.1 系統體系結構

如圖1所示,虛擬云環境下的組合調度體系結構由全局調度器(Global Scheduler, GS)與局部虛擬機服務供應者集合(Local VM Providers, LP)兩個核心部件和一些子組件(性能監控器,可調度性分析器和成本函數)組成。

圖1 可組合調度體系結構

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

LP={lp1,lp2,…,lpn}

(1)

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

(2)

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

(3)

(4)

2.2 任務模型及特性

2.3 任務靜態松弛度模型

(5)

其中:tc表示當前時間。

2.4 任務完成時間預測模型

圖2 實時任務插入

(6)

(7)

(8)

(9)

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

2.5 能源消耗模型

(10)

(12)

(13)

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

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

3 時限保障調度策略

文獻[2]只允許一個任務在虛擬機實例中排隊等待執行。當任務數目龐大時,導致大量任務滯留在全局等待隊列中成為性能瓶頸,引起大量任務錯過其時限。此外,由于排序操作時間依賴于RTQ隊列長度,因此增加了調度算法的時間復雜度。本文利用局部等待隊列構建的調度體系結構,避免了上述對調度算法所造成的大量任務錯過其時限和時間復雜度增加的問題。EDA-NMS算法詳細偽代碼如下所示。

算法1 EDA-NMS算法。

RTQ←NULL;

NRTQ←NULL;

ELSE

END IF

WHILERTQ!= NULL DO

RTQ隊列中的任務按松弛度升序排序;

END IF

執行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 調度性能評價

4.1 環境設置

本文利用CloudSim仿真器執行擴展實驗評價EDA-NMS算法的有效性[25]。通過以下性能度量指標和詳細參數設置,將EDA-NMS與主動及響應式調度(Proactive and Reactive Scheduling, PRS)算法[2]進行定量比較,來證明EDA-NMS獲得的性能提升。

1)時限錯過率:完成時間晚于時限的任務數和總任務數的比率。

2)響應性:反應時間間隔,例如,實時任務完成時間與時限的延遲間隔。

3)任務平均執行時間:

其中Nt是總任務數。

4)通過間隔數計算任務時限:

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

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

4.2 可變工作負載類型下的性能分析

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

表1 混合類型工作負載單位執行成本與時間

分別產生3組不同任務數計算密集型負載與混合類型負載追蹤算法性能。實驗產生的結果:實時任務數nrt、拒絕的任務數nrj、拒絕任務的低中高三種關鍵度的任務數分別為nK1、nK2、nK3,如表2所示。

表2 計算密集型負載/混合類型負載部分運行結果

不同關鍵度任務對系統穩定性的影響不同,通過調整實時任務時限的松緊度,比較當某些實時任務錯過其時限時系統的穩定性。從表2結果中可以發現EDA-NMS算法拒絕的任務的關鍵度低于PRS算法,即EDA-NMS算法具有更高的系統穩定性。

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

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

4.3 計算成本比較

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

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

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

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

圖4 任務響應性

圖5 實時任務的平均計算成本

5 結語

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

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。

國家自然科學基金資助項目(61662017);高等學校科學技術研究項目(2013YB113);廣西重點實驗室嵌入式技術和智能系統基金資助項目(桂林理工大學)。

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

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.