虚拟云下满足多重约束的时限敏感任务调度算法

张 奕,程小辉,陈柳华

(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.