基于低能耗的动态虚拟机调度

王悦

（华北电力大学，北京102206）

随着“大物云智移”技术的快速发展，加上高速率低时延的移动通信网络为超高密度的信息接入提供了便捷，数据中心产生了海量的数据被存储和操作的需求，数据中心是云计算基础设备的核心部分，在规模以及数量方面都呈现出爆发式增长态势，数据中心的能耗和效率问题亟待解决。根据报告显示，数据中心服务器的利用率仅为总容量的35%，其余的效用都被浪费了[1]。因此通过对虚拟机的整合优化来减少这些未充分利用的资源起着至关重要的作用，通过对虚拟机的整合优化，将虚拟机放在有限的服务器上，以提高数据中心的利用率和总体吞吐量成为了降低数据中心能源消耗的一种思路。

1 相关工作

数据中心的使用情况具有不确定性，不同时段数据中心的物理机利用率不同，不同应用对物理机上的资源喜好不同，因此物理机的负载情况也是具有随机性的。动态虚拟机迁移，就是在不停止对外提供服务的情况下，根据一定的策略，将虚拟机从一台物理机迁移到另一台虚拟机上。通过虚拟机的动态迁移来达到资源整合优化对改善数据中心能源消耗问题有着重要意义。目前对低能耗虚拟机调度已经有很多研究，文献[2]中，作者数据中心所有虚拟机的迁移频率和在物理机总体负载量设定随运行情况变化的阈值，有效的解决了静态阈值造成的一段是时间内虚拟机频繁迁移的问题，但对物理机各资源的利用情况未加以考虑资源，如某单一资源需求量高，可能会出现物理机资源利用不均衡导致的资源浪费的问题[2]。Paulraj 等人提出了一种通过复杂的算法预测未来一段时间内的负载情况来决定触发虚拟机迁移操作，虽然算法提高了预测的准确性，但是触发迁移时机的合理性完全依赖预测值[3]。文献[4]中提供了一种两级状态检测的方法，很好的解决了物理机负载的易变性导致的资源利用不稳的问题，但是并未考虑物理机负载过低的情况[4]。

在考虑迁移虚拟机的触发因素时，当物理机上某一或者某些资源被占用量过高以及物理机全部资源使用量过低都会出发虚拟机迁移操作。文献[5]中，根据建立虚拟机能耗模型，在迁出虚拟后保证物理机不过负载的前提下，选择虚拟机迁移代价最小的虚拟机进行迁出。虽然低了系统的能耗，但是算法复杂较高，也没有在目标物理机的需选择中体现节能[5]。L. Shi 等人提出的矢量箱包装算法算法首先根据服务器的利用率和容量对服务器进行排序，然后尝试将vm 从低容量服务器迁移到高容量服务器，以便在有限的机器上合并工作负载。但是，这可能会增加迁移的数量，从而对SLA 参数产生不良影响[6]。文献[7]在VMD_TES 的基础上，设计了4 种虚拟机选择算法，通过对比实验发现HLGP 充分兼顾SLA 违约和能耗两方面[7]。

虚拟机放置策略不在像以前一样只考虑单一要素，目前的研究都是基于多因素考虑，旨在得到一个性价比较高的调度策略。HALLAWI 等人将虚拟机放置问题做是一个多维装箱问题，将CPU 和内存看做二维资源，物理机看做箱子，通过建立最小化资源浪费模型，在箱子尽量少的前提下，放下最多的虚拟机，并利用遗传算法求解该模型[8]。Memaz 等人提出了同时兼顾完成时间和能耗的多目标混合遗传算法，提高了系统效率并降低了能耗[9]。J. Chen 等人通过降低迁移虚拟机数量来实现节能，因为VM迁移过程涉及额外的CPU-MIPS 开销和网络带宽，这会降低执行性能并导致违反SLA[10]。在上述的研究中都采用了智能启发算法，能够较好的多目标优化。但是基于负载平衡和低能耗的适应度函数易出现采样空间有限损失最优个体的问题。而NSGA-II 算法能够有效的解决这个问题。因此本文是在NSGA-II 算法上再次改进，旨在构建一个高效、节能、负载均衡的调度策略。

2 问题描述和模型介绍

虚拟机迁移主要是分为确定何时要进行虚拟机迁移、哪些虚拟机要从物理机中迁移出来以待迁移虚拟要迁移到哪台物理机。

2.1 问题描述

云计算数据中心是一个由计算节点、存数设备、网络设备构成的分布式网络，是云计算基础设备和资源的集合[11]。本文中假定数据中心拥有n 台异构台物理机PM= {PM1，PM2，PM1…PMm}，物理机i 上的资源集合由RSet（i）={Rcpu（i）、Rmem（i）、Rbro（i）…}表示，物理机i 上的虚拟机集合由VM={VM（i）1，VM（i）2，VM（i）3…VM（i）m}，包含CPU、内存、宽带、硬盘等。由于数据中心的任务不具备规律性，导致数据中心可能存在部分物理机负载较重，部分物理负载过低以及物理机上某种资源利用率很高，其他资源不能得到充分利用。

2.2 负载均衡

物理机的负载不均衡主要体现以下两个方面，对负失衡的原因分析，提出相应解决办法，就能将负载均衡的思路运用到虚拟机放置策略中。

（1）物理机得资源利用率不均衡

物理机出现资源浪费的原因就是虚拟随机分配到物理机上，就可能出现物理机上的虚拟机集合对某一资源利用率较高，而其他资源不能被充分的利用。本文根据物理机的是实际资源拥有量，为每一个资源设定负载阈值，超出这个阈值就需要对虚拟机进行迁移。

其中Rcpu（i）j，Rcpu（i）j，Rcpu（i）j分别表示物理机i 上的第j个虚拟机的CPU、内存、带宽的使用量，Rcpu（i），Rcpu（i），Rcpu（i）分别表示物理机i 的CPU、内存、带宽的使用量。

（2）物理机负载不均衡

数据中心接到任务后虚拟机被放置到能够满足要求的物理机上运行，并不会考虑对物理机的充分利用，就会存在数据中心有空闲和低负载的物理机在运行, 维持这些物理机运行也会产生资源浪费。因此根据物理机的总资源量，为物理机设定一个高负载阈值和低负载阈值，在这里我们设定总资源量的0.8倍为高阈值，总资源量的0.2 倍为低阈值。超过高阈值就会触发接下来的对各项资源负载阈值的判断决定被迁出的虚拟。对于低于负载阈值的物理机上的虚拟机需要全部被迁出。

其中mi表示物理机上有mi台虚拟机，VMload （i）j 表示物理机i 上第j 个虚拟机的负载Pload（i）表示第i 个物理机的总负载量。

2.3 改进的NSGA-II 算法

多目标优化算法是为了解决有两个或两个以上的目标函数的优化问题。NSGA-II 算法是在的NSGA 的基础上为了解决多目标优化问题改进而产生的，对解决多目标问题有很好的能力。算法流程如下：

（1）编码：对染色体编码时采取分组编码的方式，编码时每台物理机都代表着染色体上的一个基因位，物理机上的虚拟机编号后就是该基因位的值。然后随机产生初始种群P。

（2） 适 应 度 计 算 ： 根 据 适 应 度 函 数f=A*LoadRate+B*ResourceRate+C*VMMigrate 对种群进行适应性评估，其中VMMigrate 为虚拟机迁移数量，A、B、C 为权重系数且和为1。若满足优化标准，输出最最优解，结束循环，如不满足，进行步骤（3）。

（3）交叉：在生成的初始种群中，采取随机选择策略随机选择两个个体进行交叉，形成新的个体。在进行交叉时每个基因位的交叉概率相等。

（4）变异：在算法的变异阶段，采取非均匀变异的方式进行变异步骤，对每个基因位以相同概率进行一次随机扰动，产生新个体。

（5）非支配排序：对种群的解进行非支配排序，在种群P 和Q 中，进行三次非支配排序，得到三个不同等级的非支配解集。

（6）拥挤距离排序：对得到的非支配解集按照适应度大小进行拥挤距离排序，按适应度降序排列，取前N 个解作为初始种群P。

重复（2）（3）（4）直至结果收敛。

3 调度过程

虚拟机的调度过程是由虚拟机检测器、虚拟管理器、虚拟机调度完成。根据每台物理机所拥用的总资源设定物理机总体阈值PMUlow，PMUhigh，物理机中各项资源CPU、内存、宽带的高负载阈值根据各自的利用率决定。

图1 算法流程图

通过对该物理机监测器实现对物理机的负载情况进行检测，负载过高过低都会触发迁移操作，当物理机总量超负载时，在对物理机资源进行二级检测确定物理机的负载类型，根据HLGP 算法对超负载的资源进行排序将占用该资源量最大和最小的虚拟机迁出到待迁移虚拟机队列，直至物理机处于正常负载，若物理机负载低于低阈值将物理机上的所以虚拟机迁到待迁移虚拟机队列。虚拟机调度器根据虚拟机反馈的信息，通过改进NSGA-II 算法得到一个调度方案，既满足负载均衡，又满足能耗较低。最后对得到的调度方案由管理器来实施。（图1）

4 仿真设计及结果

数据中心的运行情况较复杂，数据量很大，如果要完全复现数据中心的真是实运行环境比较困难且会耗费不必要的社会资源。CloudSim 能够较真实的仿真云数据中新的运行情况，能够有效的简化云平台的建设与测试，同时可实现跨平台运行。因此在数据中心资源调度的研究中被广泛运用。为了在对本文的虚拟机调度策略的有效性进行验证，也采用了CloudSIM平台。在实验中数据中心的任务是采用的数据集为BitBrainstorm 公司提供的公开数据集，数据集包含本实验所涉及的CPU、内存、带宽三种类型的资源记录，数据中心异构物理机数量为800 台，虚拟机的数量根据任务变化。评价指数是根据论文[11]中的提出的评价指标对CloudSim 的能耗函数进行改进，通过与传统的LBES 算法和PDT 算法进行对比实验发现本文提出的算法能够减少虚拟的迁移次数，提高物理机的资源利用率，降低能耗。