面向高校教学云服务的虚拟机动态调度方法＊

王 菁，王 岗，高 晶，李 寒，马 倩

（1.北方工业大学云计算研究中心，北京100144；2.北方工业大学大规模流数据集成与分析技术北京市重点实验室，北京100144）

1 引言

伴随云计算技术的发展，高校逐步迈向云时代，校园云将成为高校重要的研究方向和信息化建设的主流。校园云能够为学生、教师以及科研人员提供安全可靠的计算和存储服务。它通过虚拟机的形式对用户提供服务，可以动态调度各种物理资源，从而高效地管理云平台中的资源［1］。

校园云平台包含教学、科研两类应用，为高校教师和学生提供教学及科研云服务。科研应用因其使用时间以及所需虚拟机数量不确定，呈现不可预知性、非周期性等特点，与传统应用类似。例如，Hadoop实验需要20台虚拟机，使用时间为两周。而教学应用具有周期性、可预测性、批量性等特点。例如，Java上机实验课需要为每个学生分配一台虚拟机，并且在第1～16周，每周一的1、2节课上课时间内使用。然而实际应用中资源利用率仍然较低。

分析原因可知，当前虚拟机调度机制为传统调度方法，而传统调度方法主要分为基于实时的调度与基于负载预测的调度两类。若采用基于实时的调度方法，当上课期间出现过载或过闲的情况时才会进行调度迁移，而迁移需要消耗较大的带宽资源、较多的能耗并且时间较长，势必会影响上课质量；若采用基于负载预测的调度方法，对于新申请的课程虚拟机资源，没有可参考的历史运行数据，无法对物理机负载进行正确预测。所以，核心问题在于当前的虚拟机调度机制未考虑高校教学应用负载的特征，不能量体裁衣，这样就会造成很多不必要的虚拟机迁移，以及由此带来负载不均和资源浪费。

综上所述，由于教学型应用的特殊性，面向教学需求的计算资源即虚拟机的调配这一关键问题又可进一步分解为以下两个子问题：

（1）虚拟机创建时的部署问题，即决定新创建的虚拟机部署在哪台物理机上；

（2）虚拟机使用时的动态调度问题，即根据物理机实际资源使用情况进行虚拟机的动态迁移。在前期工作［2］中针对第一个子问题进行了研究，定义了课程需求模型和物理机负载模型，提出了课程虚拟机部署算法。在此基础上对第二个子问题开展研究，提出了“先平衡，后节能”的动态调度原理，定义了吻合度、迁移优先值、负载判定值等算法判定参数，最终提出了课程虚拟机动态调度算法（CRS），以期解决物理集群资源浪费、负载不均衡问题，实现节能、环保、高效的目的。

2 相关工作

虚拟机优化调度是虚拟机管理的核心问题，针对这一问题，学术界和工业界都提出了相关解决方案，下面将从面向节能、面向负载均衡、面向负载均衡以及节能三方面进行讨论：

（1）面向节能方面，Mylavarapu S等人［3］将虚拟机的容量规划问题建模为随机优化问题，采用遗传算法与蒙特卡罗模拟相结合的方式加以解决。他们首先根据平均工作负载来分配虚拟机资源，部署虚拟机；此外，根据应用的服务等级协议SLA（Service－Level Agreement）在每台服务器上预留了空闲的资源池。这就避免了服务器过载、应用不能满足SLA 而带来的虚拟机迁移。该算法与传统的基于峰值工作负载的算法相比，所需服务器的数量较少，实现了节能。Goudarzi H 等人［4］提出了一种生成虚拟机备份的方法——基于动态优化、局部搜索的算法，该算法决定了每台服务器部署的虚拟机的数量。此外，还提出了节能虚拟机放置算法，该算法主要用来决定放置在不同物理机上的虚拟机副本数量。

（2）面向负载均衡方面，Chandakanna V R 等人［5］提出了一个适用于负载均衡集群的基于模型视图控制器的自适应调整集群框架。该框架可自动部署新的虚拟机，自动升级现有应用，并且保证集群的一致性。Hu J等人［6］提出了一种根据所采集的历史数据和系统当前状态利用遗传算法计算分配虚拟机资源后对系统的影响，从而找到最优分配方式的以负载均衡为目的的调度算法。

（3）兼顾节能以及负载均衡方面，Chang Y C等人［7］提出了一个基于学习算法的神经网络模型。集群内的每台服务器上部署了资源管理器用以预测云服务器的工作负载，从而高效地对资源进行分配，在提高服务器性能的同时降低能耗。

但是，目前的研究一般针对传统的云数据中心，当然也有少数面向特定应用领域的，比如面向感知数据托管平台［8］、电子 政务基础架构云［9］、可对云资源进行综合管理的清华云平台［10］。但是，尚没有针对高校教学应用的虚拟机动态调度机制，没有考虑到教学云服务负载的特征，未能对症下药，利用周期性、可预测性、批量性进行有效的管理调度。

3 动态调度算法

3.1 问题定义

设校园云平台的数据中心有n台物理服务器，通过虚拟机动态调度使：

（1）活跃的物理机数量尽可能少。

（2）各活跃物理机的资源利用率尽可能均衡。

为了便于上述问题求解，本文作了如表1所示的定义。

Table 1 Definition of related symbols表1 相关符号定义

结合上述的相关问题可以定义：

3.2 调度原理

为了达到3.1节的目标，调度原理采用了“先平衡，后节能”的策略。对于实际负载较高的物理机进行虚拟机动态迁移操作，从而消除高负载的物理机，实现负载均衡。然后对于负载较低的物理机，选择合适的物理机对低负载上的虚拟机进行动态迁移，从而关闭物理机，实现节能目的。

具体的调度原理如图1所示。

Figure 1 Dynamic scheduling diagram of virtual machine图1 虚拟机动态调度原理图

在具体调度过程中，首先根据课程虚拟机运行时物理机实际资源使用情况对物理机进行分组；然后对于实际负载较高且已影响虚拟机正常运行的物理机，对综合资源使用率较高的虚拟机进行迁移，目标主机根据待迁移虚拟机与正常物理机的相似程度及资源使用情况确定，从而消除高负载的物理机，动态迁移完成后更新物理机负载；当调度域内无过载物理机时，对于实际负载较低的物理机，进行虚拟机迁移操作，全部迁移完成之后，即可关闭该物理机，实现节能目的。

3.3 相关定义

定义1（课程虚拟机模型） 课程虚拟机模型可以定义为一个五元组：CVm＝（VMName，IWeek，FWeek，Resource，LSet），其中：

（1）VMName表示课程虚拟机名称类，是课程虚拟机唯一性的标识。

（2）IWeek表示课程的起始周数，FWeek表示课程的结束周数。

（3）Resource表示课程虚拟机被分配的虚拟资源，每个元素可以表示为一个二元组Resource＝（Cpu，Memory），其中：Cpu表示被分配的虚拟CPU 数量；Memory表示被分配的虚拟内存大小。

（4）LSet表示课程具体的课时集，可表示为一个三元组：LSet＝（LSection，LDay，LWeek），其中，LSection表示课程在某一天具体上课的节数；LDay表示一周具体上课的时间，即课程所在的星期几；LWeek表示课程所在的单双周类，LWeek＝（SWeek，DWeek），其中，DWeek为1 表示双周有课，SWeek为1表示单周有课，否则为0。

定义2（物理机负载模型） 物理机上所部署的课程虚拟机负载情况可定义为一个二元组：Cijk＝（PName，UResource）。其中：

（1）Cijk表示在第k周，星期j，i节课的物理机负载，其中1≤i≤5，1≤j≤5，1≤k≤16；

（2）PName＝ ｛VMName1，VMName2，…，VMNamew｝，其中w表示为第k周、星期j、i节课时间段所要同时进行的课程虚拟机的数目，VMNamew为第w个课程虚拟机的名称；

（3）UResource表示物理机上已消耗的虚拟资源，可以表示为一个二元组UResource＝（Cpu，Memory），其中：Cpu表示已消耗的虚拟CPU 数量，Memory表示已消耗虚拟内存大小。

定义3（吻合度） 待迁移虚拟机与物理机负载相对应元之间的重合度高低。公式定义如下：

其中，Numoverlap表示待迁移虚拟机一共进行的课程次数，Numall表示与物理机负载相重合的课程数。

例如，一个待迁移虚拟机属于C＋＋课程，该课程CVm＝（"C＋＋"，1，16，（2，4），｛（4，2，（1，1）），（5，1，（1，1））｝），可以得到该虚拟机一共进行了32次课程。若对于一台物理机存在课程Java，课程虚拟机参数为CVm＝（"Java"，1，16，（2，4），（4，2，（1，1））），该物理机有Java课程虚拟机4台，则该物理机与待迁移虚拟机的重合课程数为64，则吻合度GOFit＝16/64＝0.25。

定义4（判决周期T） 为了避免负载抖动的虚拟机进行迁移，本文统计λ倍的平均虚拟机迁移消耗时间Δt作为物理机状态的判决周期，即T＝λ·Δt，通常λ大于5。

定义5（高负载物理机） 在判决周期T内，若某一物理机Pj（1≤j≤m，m为集群中物理机个数）某一资源维度上的资源利用率不小于Hi，则称此物理机为高负载物理机。

定义6（低负载物理机） 在判决周期T内，若某一物理机Pj（1≤j≤m，m为集群中物理机个数）某一资源维度上的资源利用率不大于Li，则称此物理机为低负载物理机。

定义7（负载判定值De） 该值用来对物理机的负载进行一个综合度量，更加量化地显示出过载与过闲的程度，通常用以下公式表示：

其中，RPi为T内物理机在资源维度i上的平均使用大小，TPi为物理机资源i的总量。De越小则负载越高，越大则负载越低。

文献［11］只考虑了CPU 维度，但通常情况下，还要考虑内存、存储等资源的维度。因此，本文通过对CPU、内存两个维度的资源监控，更准确地度量了物理机负载。

定义8（迁移优先值） 该值用来对虚拟机的资源使用情况进行综合评定，用以选出待迁移虚拟机，如上只考虑CPU、内存维度，所以用公式migrateValue＝wcpu·RVcpu＋wmemory·RVmemory计算，其中RVcpu为T 内虚拟机平均活动CPU 大小，RVmemory为T内虚拟机平均使用内存大小。

3.4 算法描述

当所部署的课程虚拟机正常运行时，虚拟机的负载会随时间发生变化。因此，需要实时监控物理机、虚拟机负载情况，从而做出正确的优化调度。首先需要获取集群中所有物理机的性能监控数据，根据De判断物理机所处的队列是高负载、低负载还是正常队列。然后选取最高负载物理机，计算其上虚拟机的迁移优先值，选取待迁移的虚拟机后，根据当前物理机资源使用情况以及吻合度，选定目标主机，实施迁移操作。通过迁移即可消除高负载物理机，达到负载均衡的目的。最后对于最低负载物理机，对其上的虚拟机进行迁移，从而消除低负载物理机，关闭空闲物理机，实现节能目标。这样通过对负载值的调节，可以同时兼顾负载均衡以及节能的目标。调度算法描述如下：

算法1 课程虚拟机动态调度算法（CRS算法）

输入：集群内虚拟机和物理机的监控数据。

输出：虚拟机和物理机迁移映射关系。

算法描述：

上述算法的输出结果是迁移映射关系，根据该映射关系，执行迁移操作。需要注意的是，一个物理机同一时间只能进行一次迁移操作，避免因同时大规模迁移带来集群的震荡。迁移完成之后，更新平均虚拟机迁移消耗时间Δt，并调整监控数据获取的周期T。

4 校园云平台动态调度机制实现

4.1 调度系统架构

为实现上述面向高校教学云服务的虚拟机动态调度方法，本节提出了调度系统架构，架构图如图2所示。并且在以开源OpenStack Icehouse版本为基础的校园云平台上实现了面向教学需求的虚拟机动态调度系统。

Figure 2 Scheduling system architecture diagram图2 调度系统架构图

下面将对系统架构进行详细阐述：

该系统的最底层为计算资源、存储资源等物理资源；之上为通过服务器虚拟化技术形成的虚拟机资源，即虚拟化层，由于本系统是基于OpenStack这一开源虚拟化平台管理工具，所以该层为Open－Stack虚拟化平台；再往上则是本系统的核心部分，主要由数据存储模块、虚拟机调度模块、虚拟机控制模块组成。

下面将逐一介绍核心模块的功能及其接口：

（1）数据存储模块。

存储物理机预测负载：将根据虚拟机的课程详情计算得到的的物理机预测负载存储写入到Mysql数据库中；

存储监控数据：将通过监控软件获得的物理机、虚拟机的实时资源（cpu、内存等）使用情况存储到Mysql数据库中；

存储映射关系表：将服务器与虚拟机的放置映射关系存储到Mysql数据库中。

（2）虚拟机调度模块。

吻合度计算：根据待迁移课程虚拟机课程信息和物理机负载计算物理机的吻合度大小；

物理机状态判断：根据监控所得数据、高低阈值判定物理机所处状态；

负载判定值计算：根据物理机监控数据更加量化地计算物理机综合资源使用情况；

迁移优先值计算：对于过载或过闲物理机上的虚拟机，根据监测数据对虚拟机的资源使用情况进行综合判定；

动态调度：根据物理机状态、负载判定值、迁移优先值、吻合度对虚拟机按照调度规则进行动态调度，生成迁移映射关系。

4.2 OpenStack动态调度机制扩展

由于OpenStack不支持虚拟机的动态在线迁移，因此，首先需要结合Ganglia监控软件来获取监控数据，实现物理机集群和虚拟机集群的实时监控。具体步骤如下：（1）通过UDP 协议将监控数据封装为xml文件，被监控节点的监控信息汇聚到监控节点，从而将监控数据以xml文件形式存储在监控节点；（2）由于Ganglia通过8651端口进行监控数据传输，所以等间隔地去读取物理服务器端8651端口，获得xml树状结构的数据；（3）通过SAXReader接口对xml数据进行解析，然后将获得解析的监控数据实时地存入Mysql数据库中。

其次，OpenStack热迁移通过搭建分布式存储Sheepdog实现共享存储。Sheepdog是为kvm 虚拟化量身定做的分布式文件系统，相比共享SAN存储，Sheepdog不存在单点故障，并且是开源的，没有SAN 的价格昂贵。同时，Sheepdog也可作为Cinder、Glance和Swift的后端存储，每台服务器安装Sheepdog后即是计算节点也是存储节点。

最后，使用Python语言编写课程虚拟机动态调度算法（CRS算法）并通过调用OpenStack Nova API中的live＿migration接口进行虚拟机在线迁移。

5 实验验证

该实验使用8台服务器构建的集群上搭建了OpenStack平台，具体服务器配置如表2所示。

Table 2 Server configuration表2 服务器配置

如表2所示，sigsit.openstack.controller为控制节 点，computenode1、computenode2、computenode3、computenode4、computenode5、computenode6、computenode7为计算节点。

为了验证课程虚拟机动态调度算法（CRS）的效果，本文从物理机负载监控值比较本算法与其他调度算法的优劣。首先通过表3的所有课程请求采用CRD 算法部署课程虚拟机，其中所有课程虚拟机的CPU 核数为1，内存为2GB。

Table 3 Details of the courses on request表3 课程请求详情

其次，在所有课程虚拟机部署完成后，通过对不同动态调度策略的比较来验证CRS 算法的优势，调度策略采用目前使用较为广泛的OpenStack开源软件提供的SimpleSchedule（SS）以及贪心算法First Fit（FF）。另外，动态调度过程需要设定相关参数，若高阈值设定过高，容易造成虚拟机服务质量下降也无法得到迁移；而设置过低，会导致资源利用率不足的问题。若低阈值设定过高，当有新的虚拟机迁入时，容易成为高负载物理机，引起二次迁移；若设定过低，则会造成一定的资源浪费。Srikantaiah S等人［12］的研究表明，当CPU 利用率超过70%的时候虚拟机性能明显下降，本文将相关值设定如下：Hcpu＝70%，Lcpu＝10%，Hmemory＝90%，Lmemory＝30%，T＝30s。

从图3、图4 可看出，在该课程首次上课时间段内，经本文提出的CRS算法动态调度之后，集群内CPU、内存基本达到负载均衡。而经其他两种算法调度之后，可以消除高负载物理机，但是集群内资源严重不均衡，CPU 利用率差距大于25%，内存利用率差距大于60%。这样虽然消除了高负载物理机，但是存在资源浪费。

综上所述，本文提出的虚拟机动态调度算法（CRS），可在保证教学应用需求的同时，达到兼顾节能以及负载均衡多目标优化的目的。

Figure 3 CPU utilization of the cluster图3 集 群CPU 利 用 率

Figure 4 Memory utilization of the cluster图4 集群内存利用率

6 结束语

本文提出了面向高校教学云服务的虚拟机调度方法及系统，提出了“先平衡，后节能”的动态调度原理，提出了课程虚拟机动态调度算法（CRS），以期解决物理集群资源浪费、负载不均衡问题，实现节能、环保、高效的目的。但是，本文在资源维度的选取方面，只考虑了CPU 和内存这两个维度，具有一定的局限性。为了更接近于真实的复杂环境，在日后的研究中可以考虑增加网络带宽、硬盘容量等维度，使得考量指标更丰富、更真实。

［1］ Nathuji R，Schwan K.Virtual power：Coordinated power management in virtualized enterprise systems［C］∥Proc of ACM Symposium on Operating Systems Principles（SOSP’07），2007：256－278.

［2］ Qian Ma，Jing Wang，Gang Wang.A deployment scheme of virtual machines for campus cloud platform［C］∥Proc of the 2014International Conference on Service Sciences，2014：187－192.

［3］ Mylayarapu S，Sukthankar V，Banerjee P.An optimized capacity planning approach for virtual infrastructure exhibiting stochastic workload［C］∥Proc of ACM Symposium on Applied Computing（SAC），2010：386－390.

［4］ Goudarzi H，Pedram M.Energy－efficient virtual machine replication and placement in a cloud computing system［C］∥Proc of 2012IEEE 5th International Conference on Cloud Computing（CLOUD），2012：750－757.

［5］ Chandakanna V－R，Vatsavayi V－K.A model view controller based self－adjusting clustering framework［J］.Journal of Systems and Software，2013，29（4）：581－589.

［6］ Hu J，Gu J，Sun G，et al.A scheduling strategy on load balancing of virtual machine resources in cloud computing environment［C］∥Proc of 2010 3rd International Symposium on Parallel Architectures， Algorithms and Programming（PAAP），2010：89－96.

［7］ Chang Y－C，Chang R－S，Chuang F－W.A predictive method for workload forecasting in the cloud environment［M］∥Advanced Technologies，Embedded and Multimedia for Humancentric Computing. Netherlands：Springer Netherlands，2014：577－585.

［8］ Li X，Jiang Y.A sensory－data－hosting oriented scheduling strategy on virtual machine［C］∥Proc of 2013IEEE and Internet of Things （iThings/CPSCom），IEEE International－Conference on Green Computing and Communications（GreenCom），and IEEE Cybe，Physical and Social Computing，2013：2029－2036.

［9］ Zhao Hong－wei，Shi Bo－le.On capacity planning for E－government cloud computing infrastructure［J］.Computer Applications and Software，2014，31（11）：118－121.（in Chinese）

［10］ Zhao Shao－ka，Li Li－yao，Ling Xiao，et al.Architecture and scheduling scheme design of TsinghuaCloud based on Open－Stack［J］.Journal of Computer Applications，2013，33（12）：3335－3338.（in Chinese）

［11］ Beloglazov A，Buyya R.Energy efficient allocation of virtual machines in cloud data centers［C］∥Proc of the 10th IEEE/ACM International Conference on Cluster，Cloud and Grid Computing（CCGrif’10），2010：577－578.

［12］ Srikantaish S，Kansal A，Zhao F.Energy aware consolidation for cloud computing［C］∥Proc of the 2008Conference on Power Aware Computing and System，2008：10.

附中文参考文献：

［9］ 赵宏卫，施伯乐.电子政务基础架构云的容量规划方法研究［J］.计算机应用与软件，2014，31（11）：118－121.

［10］ 赵少卡，李立耀，凌晓，等.基于OpenStack的清华云平台构建与调度方案设计［J］.计算机应用，2013，33（12）：3335－3338.