云环境下的基于Min-Max的节能资源调度算法的研究

徐京明 王 珺 李成星

(南京邮电大学通信与信息工程学院 江苏 南京 210003)

0 引 言

随着云计算数据中心规模的不断扩大，数据中心消耗的能量也在不断增加。近年来，数据中心产生的高能耗现象逐渐受到各界的关注[1]。据美国相关机构统计[2]：2012年，全世界IT行业的能量消耗占总比例的40%，排放的二氧化碳占全球的2%。2014年数据中心的基础设施和能源成本占总成本的75%，而基础设施成本仅占其中的25%。预计到2020年，云计算能耗在全世界将接近2万亿千瓦时。因此，迫切需要研究云环境中的节能资源调度算法和策略。

根据相关机构的调查结果可知，数据中心能量消耗过高的原因主要有两个：一方面是资源调度算法设计不合理造成的[3]；另一方面是当物理资源处于空闲状态时，没能及时转换成休眠或者关机等状态造成的[4]。本文针对第一个问题展开研究。

1 相关工作

云计算的资源调度有无限可能的发展前景，因此，资源调度算法是当前研究的一个热点。资源调度就是将资源池中的资源根据算法或者策略的规则分配给用户的过程。目前为止，已经有很多学者在这方面提出了很多的算法，比如：文献[7]中提出了一种优化的Min-Min算法，该算法不仅基于Min-Min算法，而且基于三个约束。三个约束分别是服务质量、动态优先级模型和服务成本，使用Cloudsim软件来运行模拟实验。与传统的Min-Min算法相比，它可以在合理的时间内执行完长度较大的任务，不仅提高了资源利用率，而且提高了用户的QoS。文献[8]中提出了贪心算法[18]的优化，该算法在贪心算法基础上增加了优先级机制，将云任务根据任务指令条数(单位为MI)的大小按照递减的顺序排列。资源根据处理器速度(单位为MIPS)的大小按照递增的顺序排列。该算法以最小任务完成时间为调度目标，它总是能建立当前最佳的任务到物理资源的映射关系。文献[9]提出了一种基于Max-Min的调度算法，调度过程中的任务状态表用于预测虚拟资源的实时负载和任务的预期完成时间，该算法实现了负载均衡但是没有考虑任务的完成时间。文献[10]提出了Min-Max算法，调度过程中，首先根据Max-Min算法和Min-Min算法分别选出长度最大和最小的任务，根据计算得出各自在物理机执行的完成时间，分别选出最小任务完成时间的物理资源，最后将这两个任务分别放在对应的物理机上执行。该算法既提高了系统整体的资源利用率，又实现了负载均衡。当然，还有其他的调度算法，比如粒子群算法、蚁群算法等，但是这些算法大多都只考虑了性能、可靠性以及安全性等问题，而忽略了能量消耗的问题。

近年来，越来越多的人开始关注能耗问题，研究者也提出了一些关于节能的资源调度的算法。文献[11]中提出一种面向异构机群的低功耗调度算法，在经典的Min-Min算法的基础上，将休眠状态控制策略应用于异构集群的各个节点，实现了性能和能耗的平衡。然而，睡眠唤醒机制会增加任务准备时间，减少任务有效性。文献[11]中的算法考虑了休眠和空闲状态下如何通过状态转换实现节能，本文提出的算法考虑了通过调度算法进行能耗优化，实现工作状态下的节能。当然，如何在睡眠和空闲状态下节约能量也是未来需要考虑的问题。在文献[6]中，针对绿色节能，提出了一种云环境下的资源调度算法。该算法利用了遗传算法找到最优调度策略，建立两级调度模型，采用能耗估算模型，该模型考虑了休眠、空闲以及工作三种物理机状态。相较于GA，该算法减少了任务完成时间和能量消耗，但是文中的能耗估算模型忽略了物理机进行状态转换时的能耗损失。本文和文献[6]采用的都是ECEM能耗估算模型，但本文考虑的是计算密集型任务在工作状态下的能耗，因此，该模型不考虑状态转换期间消耗的能量，对本文没有影响。在文献[12]中，提出了一种基于Min-Min的节能资源调度算法，在原有算法的基础上增加了能量估计机制。首先，根据Min-Min算法找到最小长度任务。然后，根据用户对任务的期望时间将物理资源分为两类：满足时间期望和不满足时间期望。该算法实现了节能的目标而忽略了负载均衡问题，还需要进一步完善。相比于文献[12]提出的调度算法，本文的ESSAMM算法实现了负载均衡，并且本文采用的是文献[6]中的ECEM能耗估算模型，而文献[12]中使用了MSEM能耗估算模型，两个模型能耗的计算方式和物理机状态不同。通过分析，本文将后者作为ESSAMM节能算法能耗估算模型。最后，本文只考虑计算密集型任务在工作状态下产生的能耗，而文献[12]研究了多种任务在多种状态下的不同能耗，内容不限于资源调度。在文献[13]中，研究了云计算环境下的能源效率问题。首先，该文研究了能耗模型，将计算资源分为CPU、内存、存储和网络四大类，并针对不同的组件设计了不同的调控策略。在此基础上，提出了一种动态资源调度算法，最后的仿真结果也证明了该算法的有效性。但是该算法由于数据收集的不完善，无法在云环境下普遍使用，需要进一步修改和完善。

云计算环境下的资源调度过程需要平衡好性能和能耗这两个方面。由表1知，Min-Max算法的任务完成时间介于Min-Min算法和Max-Min算法之间，但是其资源利用率最大。因此本文选择Min-Max算法进行改进。三个算法都没有考虑能量消耗，所以本文在Min-Max算法的基础上考虑了能量消耗因素，并且将用户对于任务的期望完成时间也考虑进去(时间QoS)，即本文所提出的ESSAMM算法。仿真实验表明：ESSAMM算法不仅实现了负载均衡，而且减少了能量消耗。

表1 三种算法性能对比

2 参考模型

2.1 云计算环境下的两级资源调度模型

根据虚拟化技术在云计算中的应用，将云计算系统中的所有资源集成到一个巨大的资源池中[14]，将云用户提交的任务划分为几个小任务，先实现资源池中信息的有效输入和输出，然后建立任务与资源之间的有效映射关系。云中的资源分为两类：虚拟资源和物理资源。因此，云环境中的资源调度可以分为两个层次：第一个层次在虚拟资源层；第二个层次在物理资源层。具体的调度模型如图1所示。

图1 云环境的两级资源调度模型

第1级映射关系可以表示为S1={T,V,f1}，其中T={T1,T2，…，Tm}表示有m个任务的集合；V={V1,V2，…，Vm}表示与任务列表一一对应的m个虚拟机的集合；f1表示任务到虚拟机的映射关系。第2级映射关系可以表示为S2={V,H,f2}。其中H={H1,H2，…，Hn}表示有n个物理机的集合。f2表示虚拟机到物理机的映射。

在第一级映射关系中，云任务和虚拟机是一一对应的关系，根据任务的属性以及要求，在资源池中匹配到相应的虚拟资源，建立任务到虚拟机的映射关系。在第二级映射关系中，一台物理机可以对应一个或者多个虚拟机，根据上一级匹配到的虚拟资源的配置信息，以最小能耗和时间QoS为调度目标，选择最佳的物理资源并建立虚拟机到物理机的映射关系。其中，第二级映射关系是本文的研究重点。通过上述云环境下的两级资源调度模型，本文可以建立从任务到物理机的有效映射关系。相较于采用多任务和超线程技术，虚拟化的两级资源调度模型的优势是一个物理资源可以同时运行多个虚拟资源，执行多个任务，结合优化的调度算法可以减少很多相关开销、提高数据传输速率和性能。

2.2 ECEM能耗估算模型

本文使用的能耗模型是文献[6]中提到的ECEM能耗估算模型。ECEM能耗估算模型将总能耗分为休眠能耗、空闲能耗和工作能耗之和[15]。工作能耗分为计算能耗、存储能耗以及通信能耗三类。任务类型分为计算密集型、能量密集型以及通信密集型三类，其中计算密集型任务工作过程中产生的能耗成为计算能耗，计算能耗主要和CPU利用率有关。能量密集型任务工作过程中产生的能耗成为存储能耗，存储能耗主要和磁盘读写的字节数有关。通信密集型任务工作过程中产生的能耗成为通信能耗，通信能耗主要和传输的字节数有关。研究表明，能耗的主要来源是物理机的CPU，主要因素是CPU利用率，一般情况下，每个物理机的CPU利用率基本不同。所以本文只考虑计算密集型任务在工作状态下产生的计算能耗，采用CPU利用率不同的物理机去执行任务。以下本文所说的能耗都指的是计算能耗。设在物理机Hj上执行任务Ti产生的执行时间用RTij表示；在物理主机Hj上执行任务Ti产生的能耗用CECij表示：

(1)

(2)

式中：CECij表示计算能耗，RTij表示任务Ti在物理机Hj上的执行时间(单位为s)，CIi(单位为MI)表示任务指令条数，CSj表示物理机的处理器速度(单位为MIPS)，PCj表示在物理机Hj上执行任务的计算功耗(单位为W)。

2.3 算法变量以及时间QoS的说明

1) 在说明ESSAMM算法之前，有如下定义：

任务集合表示为T={T1,T2，…，Tm}，虚拟机集合表示为V={V1,V2，…，Vm}，物理机集合表示为H={H1,H2，…，Hn}。长度最大的任务Tp和长度最小的任务Tq。

(1)RTij表示任务Ti在物理资源Hj上的执行时间。

(2)WTij表示任务Ti在被调度之前的等待时间。

(3)CTij表示任务Ti在物理资源Hj上的完成时间，且满足CTij=RTij+WTij。

(4)TQoS(i)表示任务Ti的时间服务质量即时间QoS。

(5)Eij表示任务Ti在物理资源Hj上的消耗的能量值。

(6) 矩阵ECT表示任务完成时间矩阵，矩阵中的元素为CTij。

(7) 矩阵ECE表示能量消耗矩阵，矩阵中的元素为Eij。

2) 因每个任务在物理机上的完成时间是已知的，当用户输入时间QoS时，系统会提示用户当前任务在各物理机上执行的最小和最大的完成时间，且限定输入的时间QoS范围必须在最小和最大的完成时间之间。本文的时间QoS也指用户期望任务的完成时间。

3 ESSAMM节能调度算法

3.1 算法描述

针对ECEM能耗模型中的第二级调度，ESSAMM算法以系统总能耗最小为优化目标，以满足任务的时间QoS为约束条件。ESSAMM算法在Min-Max调度算法基础上考虑了时间QoS和能耗，节省了大量能耗，提高了用户满意度，使得整个系统处于负载均衡的状态。ESSAMM算法总共分为三个阶段：第一个阶段是计算任务完成时间；第二个阶段是根据用户设定的时间QoS，将满足时间需求的物理资源选择出来；第三个阶段是根据能耗实现资源调度。

1) 第一阶段：计算任务完成时间。

(1) 计算出任务集合T在物理机集合H上的完成时间。

(2) 根据(1)中的任务完成时间，选择物理机上最大完成时间对应的任务和最小的完成时间对应的任务来组成任务对(同一个物理机上的任务完成时间越长，任务的长度就越大，可以根据完成时间来判断任务长度)，即当前任务集合中长度最大的任务Tp和长度最小的任务Tq，并确定两个任务在各物理资源Hp和Hq上的完成时间。

2) 第二阶段：根据用户设定的时间QoS，筛选出满足用户时间需求的物理资源。

在满足用户设定的时间QoS前提下，将任务Tp分别在n个物理机上执行的完成时间(CTP1，CTP2，…，CTpn)和设定的TQoS(p)进行比较，如果CTp>TQoS(p)，则将该资源标为无效且删除，若反之，则留下并等待第三阶段的调度选择。对于任务Tq同理之。

3) 第三阶段：根据能耗实现资源调度。

(1) 采用式(2)计算Tp和Tq在各物理资源Hj执行产生的能耗值。

(2) 比较任务Tp在各物理资源上的能耗值，取最小能耗值对应的物理资源Hp，将Tp放在Hp上执行，建立任务Tp到物理机Hp的最佳映射关系；对任务Tq，将Tq放在能耗值最小的物理资源Hq上执行，建立任务Tq到物理机Hq的最佳映射关系。

3.2 算法流程

步骤1初始化。初始化任务的等待时间WTij= 0，执行时间RTij=0，完成时间CTij=0，能耗值Eij=0，设定TQoS(i)。

步骤2建立完成时间矩阵ECT。计算每个任务Ti在不同物理机Hj上的完成时间CTij，确定一个M行N列的完成时间矩阵ECT，CTij为ECT矩阵中的元素。

步骤3确定当前任务列表中长度最大和长度最小的任务。根据ECT矩阵，找出每个任务的最小完成时间，并且比较出每个任务的最小完成时间，找出最大值和最小值即为长度最大的任务Tp和长度最小的任务Tq。

步骤4确定满足时间QoS的物理资源。将任务Tp对应的每个物理资源的完成时间和步骤1中设定的TQoS(p)作比较，若大于TQoS(p)则将该物理资源标为无效；对于任务Tq同理之。

步骤5建立能量消耗矩阵ECE。采用式(2)分别计算出任务Tp和Tq在各物理资源上的能量消耗值，能耗值表示为Eij，确定一个M行N列的能量消耗矩阵ECE。

步骤6建立最佳映射关系。对于任务Tp，比较步骤5中的能耗值，选择最小值Ep对应的物理资源Hp，将任务Tp放在Hp上执行，建立最佳映射关系；对于任务Tq，比较步骤5中的能耗值，选择最小值Eq对应的物理资源Hq，将任务Tq放在Hq上执行，建立最佳映射关系。

步骤7将已经执行的任务Tp和Tq从云任务列表T中删除，然后更新任务列表T，更新完成时间矩阵ECT和能量消耗矩阵ECE。重复上述步骤3，直到任务列表为空，退出循环。

由2.2节中ECEM能量估算模型式(1)、式(2)可知，物理机的计算能耗与任务完成时间和物理机的功耗有关，而物理机的计算功耗与其CPU的利用率有关，因此，在CPU利用率不同的物理机上执行相同任务产生的能耗是不同的。ESSAMM算法以最小能耗为调度目标，通过选择最小能耗对应的物理机执行该任务，以此来节省系统总能量消耗，而Min-Max算法并未考虑能耗因素，造成能源的浪费。此外，ESSAMM算法在Min-Max算法的基础上提高了资源利用率，由于Min-Max算法在调度过程中并未根据任务的属性和用户的需求考虑了每一个物理资源的分配，导致资源利用率较低。另一方面，由于ESSAMM算法的复杂度比Min-Max算法的复杂度更高，所以，在调度过程中ESSAMM算法的任务总完成时间略长一些。相比于Min-Max算法，本文提出的ESSAMM算法实现降低系统总能耗、提高系统整体资源利用率及用户满意度等调度目标。

4 仿真与结果分析

仿真实验从任务总完成时间、系统资整体源利用率以及系统总能耗几个方面，分别对ESSAMM算法、Min-Max算法以及Min-Min算法进行比较。其中，任务总完成时间代表了资源调度算法的执行效率，系统的整体资源利用率代表了算法的负载均衡性能，系统总能耗代表了算法的节能效果。任务数量从1到1 000，物理机数量从1到100。

4.1 主要参数设置

实验环境：CPU 主频 2.40 GHz，硬盘：150 GB，内存：4 GB，操作系统：Windows10 64位。

开发环境：开发平台为Eclipse，开发语言为Java，仿真环境为Cloudsim3.0.3。

实验的参数配置如表2所示，虚拟机的配置与云任务的一致。

表2 实验参数设置

4.2 仿真结果对比分析

(1) 物理机的数量为100，任务数量从100递增到1 000。

首先，本文仿真了当任务数从100到1 000递增时，ESSAMM算法、Min-Max算法以及Min-Min算法的总任务完成时间，结果如图2所示。

图2 三种算法的总任务完成时间

如图2所示，当任务数量从100到1 000递增时，三种算法的任务总完成时间均在增加，其中Min-Min算法的任务总完成时间最小，Min-Max算法的任务总完成时间介于其他两个算法之间。原因如下：ESSAMM算法在调度过程中既考虑了任务总完成时间，又考虑了时间QoS和能量消耗两个因素，相较于另外两个算法，调度过程更加复杂一些，从而使得该算法的任务总完成时间略长一些。而Min-Min算法以最小完成时间为调度目标，它总是优先调度长度较小的任务，使得大任务的等待时间变少，从而使得总完成时间减少。Min-Max算法既调度大任务又调度小任务，以负载均衡和总任务完成时间作为调度目标，所以完成时间介于其他两个算法之间。

当任务数从100到1 000递增时，将ESSAMM算法、Min-Max算法以及Min-Min算法的整体资源利用率进行仿真，结果如图3所示。

图3 三种算法的整体资源利用率

如图3所示，当任务数量从100到1 000递增时，三个算法的整体资源利用率均在增加，Min-Min算法的整体资源利用率一直处于最低状态，ESSAMM算法的整体资源利用率最高且均在90%左右，Min-Min算法的资源利用率略低于ESSAMM算法，但也保持在85%以上。原因如下：Min-Min算法总是优先将小任务放在CPU处理速度快的物理机上执行，导致处理速度慢的物理资源处于空闲状态，不能很好地利用所有资源，所以它的资源利用率较低。而Min-Max算法和ESSAMM算法在调度过程中都考虑了负载均衡的因素，此外，ESSAMM算法在调度过程中又以能耗因素将任务调度到不同物理机上执行，而不仅仅是以CPU处理速度的快慢作为标准。所以，ESSAMM算法的整体资源利用率最高，其次是Min-Max算法，最低是Min-Min算法。

当任务数从100到1 000递增时，将ESSAMM算法、Min-Max算法以及Min-Min算法的总能量消耗进行仿真，结果如图4所示。

图4 三种算法的总能量消耗

如图4所示，当任务数量从100到1 000递增时，三种算法的总能量消耗值也逐渐上升，但是ESSAMM算法的总能量消耗一直处于最低值，且增长趋势较为平缓；Min-Max算法的总能量消耗最高，Min-Min算法的总能量消耗值处于两者之间。原因如下：Min-Min算法以任务完成时间作为调度目标，Min-Max算法以任务完成时间和负载均衡作为目标进行调度，这两个算法在资源调度过程中都没有考虑能量消耗的因素，而ESSAMM算法在Min-Max算法的基础上考虑了能耗因素，在满足时间QoS的前提下，取能耗最小值对应的物理资源执行该任务，即以能耗最低为目标进行资源调度。所以ESSAMM算法的总能耗值最低，其次是Min-Min算法，Min-Max算法的总能耗值最高。

(2) 任务数量为1 000，物理机数量从10递增到100。

当物理机的数量从10递增到100时，将ESSAMM算法、Min-Max算法以及Min-Min算法的总任务完成时间进行仿真，结果如图5所示。

图5 三种算法的总任务完成时间

如图5所示，随着物理机数量的增加，三个算法的总任务完成时间均在不断减小，且下降趋势较为平缓，其中Min-Min算法的总任务完成时间最小，Min-Max算法的总任务完成时间介于ESSAMM算法和Min-Min算法之间。原因如下：Min-Min算法是以最小任务完成时间为目标，调度过程较简单；Min-Max算法是以负载均衡为目标，调度过程中将当前任务中长度最大和最小的任务“捆绑”执行，且将任务的等待时间考虑进去，充分利用各物理资源，达到优化的目标；而ESSAMM算法既考虑了负载均衡的因素，又考虑了能量消耗的因素，相较于前面两个算法，考虑的更加全面一些，所以任务的完成时间略长一点。

当物理机的数量从10递增到100时，将ESSAMM算法、Min-Max算法以及Min-Min算法的整体资源利用率进行仿真，结果如图6所示。

图6 三种算法的整体资源利用率

如图6所示，随着物理机数量的增加，三个算法的整体资源利用率均在逐渐增加，其中ESSAMM算法的整体资源利用率最高，Min-Max算法的整体资源利用率略低于ESSAMM算法，而Min-Min算法的整体资源利用率最低。原因如下：ESSAMM算法和Min-Max算法在调度过程中均考虑了负载均衡的因素，而Min-Min算法只以最小任务完成时间为调度目标。

5 结 语

本文以节省能量消耗为调度目标，提出了一种新的节能调度算法(ESSAMM)。面向云环境，本文建立了两级的资源调度模型，利用时间QoS对每个任务的物理资源进行筛选，将符合时间QoS的物理资源保留，然后根据ECEM能耗估算模型计算出任务在物理机上的执行能耗，比较出最小值，最后建立了最佳映射关系。仿真结果表明， ESSAMM节能调度算法与Min-Max算法和Min-Min算法相比，节能效果最好；ESSAMM算法和Min-Max算法的任务总完成时间基本相同，其中Min-Min算法的任务总完成时间最小；ESSAMM算法的整体资源利用率最高，而Min-Min算法的整体资源利用率最低。目前，本文只考虑了计算密集型任务，并没有考虑其他类型的任务，所以细化任务类型是下一步工作内容之一。另外，本文提出的算法只考虑了工作过程中的能耗优化，下一步的工作重点是将空闲状态以及休眠状态下的节能方案也考虑进来，完善整个节能系统。