OpenStack环境下的虚拟机调度算法研究

陈昊 文成玉

摘 要：随着云数据中心的大规模应用，文章通过对当今主流的开源云平台OpenStack在虚拟机初始化放置机制的研究，针对OpenStack在创建虚拟机时初始化放置算法的不足，提出了基于虚拟机的综合优化放置算法作为OpenStack的虚拟机初始化放置算法，通过在仿真云平台CloudSim上仿真，结果表明，该算法性能更好，能更好地提高物理机的资源利用率。

关键词：OpenStack；虚拟机；调度算法

继个人计算机、互联网变革之后，2010年以来，云计算作为第三代IT浪潮的代表正在向我们走来，它将带来人类生活、生产方式和商业模式的根本改变，成为当前全社会关注的焦点。

随着云计算的蓬勃发展，基于云平台下的基础设施的规模也变得越来越大，数据中心上部署的物理服务器也越来越多，各种各样的服务和程序运行在这些物理服务节点上，怎样有效利用数据中心的共享资源，有效提高大规模的物理数据中心的资源利用率，具有重要意义。

现阶段，云平台的虚拟机初始化部署的研究主要分为传统的启发式算法和生物智能启发式算法两个方面。传统的启发式算法有首次匹配算法、最佳匹配算法等。生物智能启发式算法主要有蚁群算法、遗传算法等。上述算法在一定的情况下都能表现出较好的性能，但是在云平台这种没有环境限制下算法的性能会不稳定。本文针对OpenStack内置的算法的不足对传统算法的启发式的算法进行了改进，提出了综合优化放置算法。

1 0penStack虚拟机放置机制

1.1 0penStack虚拟机的创建流程

在OpenStack搭建的云环境中，分布着大量的性能不同的物理机，此时，当有用户在OpenStack的Web页面dashboard上请求创建虚拟机时，就面临着将虚拟机部署在哪个物理计算节点上的问题。OpenStack中，nova-scheduler（调度器）负责在资源池中筛选合适的物理服务器作为虚拟机实例的初始化部署节点。OpenStack中虚拟机的创建流程如图1所示。

1.2 0penStack中内置了两种初始虚拟机放置算法

1.2.1 即时服务放置算法

即时服务放置算法即如果当前的物理主机所剩余的内存等资源满足所申请创建的虚拟机的请求时，在满足条件的物理机列表中随机的选取一个物理主机做为虚拟机创建实例的初始化部署节点。

1.2.2 过滤称重算法

过滤称重算法如图2所示。

过滤称重算法主要是分为两个步骤，首先OpenStack计算服务Nova中的过滤调度器FilterScheduler使用配置的过滤器（Filter）对物理服务器进行过滤，筛选出符合要求的物理主机，然后对满足条件的主机进行权值排序，将获得剩余资源最多的主机最终作为放置虚拟机实例的节点。

1.3 0penStack虚拟机初始部署算法的不足

OpenStack在默认的情况下只是根據物理主机剩余的CPU进行权值的计算。因此，物理主机剩余的可利用的CPU越多，则该物理主机被选为最佳放置虚拟机主机的概率就越大。这种算法的优点是算法的实现相对比较简单。缺点是只是根据物理主机剩余的CPU大小来进行权值的排序，进而来选择物理主机作为放置虚拟机实例的目标主机，并不符合实际生产环境中云平台的使用要求。另外，只是单一地根据物理计算节点所剩余的CPU的大小来决定虚拟机的放置策略，使得云环境中各个物理主机的CPU的利用率都不高，因此，在实际的云生产环境中，需要综合考虑CPU、内存、带宽、磁盘等各个资源，最大限度地提高物理主机的资源利用率，避免资源的浪费。

2 0penStack综合优化放置算法

2.1 问题模型

虚拟机的初始化部署问题可以简化为一种装箱问题。即将m个w维的盒子装入n个w维的箱子。每个虚拟机可以看成是一个盒子，每个物理主机看作是一个箱子。盒子的重量是该虚拟机占用的资源。虚拟机的调度优化目标是将多个虚拟机放入物理主机中。保障用户的服务质量，同时，每个物理主机上虚拟机占用的资源总量不能超过物理主机所能提供的资源总量。并且，使虚拟机占用的物理主机的数量最少。达到节省能耗、提高资源利用率的目的。

问题定义：将数据中心的n个物理主机定义为集合P={P₁，…，P_n}，将需要放置的m个虚拟机定义为集合V={v₁，…，v_m），物理主机上虚拟机的放置向量为H={h_i1，h_i2，…，h_im）。h_ij=1表示虚拟机v_j放在物理主机p_i上。定义每个物理节点上的资源为w维。因为物理服务器节点的资源主要有CPU、内存、网络带宽和磁盘存储，所以简化定义物理服务器资源向量为四维向量P_i=（SC_i，SM_i，SM_i，SH_i）相应的虚拟机的资源定义为v_j=sc_i，sm_i，sn_i，sh_i）。

虚拟机的部署问题可以描述如下：

公式组（1）中第一个公式表示虚拟机只能部署在一台物理机上。后面4个公式为约束条件分别表示某个物理机上虚拟机占用的CPU、内存、带宽、磁盘存储的资源总数不能超过物理机提供的总的资源总量。n表示物理主机的总数，m表示虚拟机的总数。目标函数（2）为云平台所使用的物理机最少，即云平台的资源利用率最高。

F=min（P_used）

（2）

2.2 基于启发式算法改进的虚拟机综合优化放置算法

虚拟机的初始化部署问题可以看成是n维装箱问题，对于多维问题，通常选择降维的方法将多维问题转化成一维问题来解决。本文选择的是利用欧氏距离将虚拟机的CPU、内存、带宽、磁盘存储四维向量转化成一维问题。

算法的流程如下。

（1）输入虚拟机的集合V，物理服务器集合P，根据公式（3）分别计算每个虚拟机对应的欧氏距离d_ij，并将对应的虚拟机按照各自的欧氏距离的大小进行升序排序。

（2）将虚拟机队列中第一个放置物理机pl中，并将队列首部的虚拟机从集合中移除，判断队列末尾的虚拟机能否放入物理机pl中，如果能，则将队列末尾的虚拟机放入物理机pl中，并将队列末尾的虚拟机从队列中移除。如果不能，则重新开启一台物理主机。

（3）从虚拟机集合中检索第一个能放入物理主机中的虚拟机，如果能找到，则将该虚拟机放入物理主机Pi中，如果不能找到，则新开启一台物理主机，将该虚拟机放入到物理主机p_i中。

（4）不断重复步骤3，直到所有的虚拟机都放入物理主机中。

（5）输出物理服务器所用的数量。

3 仿真结果分析

为了验证本文提出的综合优化虚拟机初始放置算法对在实际的云平台上的效果，通过在CloudSim仿真云平台上的仿真与OpenStack内置的虚拟机初始化部署算法做对比来验证本文提出的算法的有效性。

实验中参与的模拟的物理服务器的规模为200个，每个服务器的配置为CPU2.1 GHz，内存的大小为8 GMB，磁盘的大小为2 000 GB，网络带宽为1 000 Mbps。虚拟机总共有10种不同的配置。虚拟机的配置如表1所示。

试验中，每10个虚拟机一组，每次增加一组总共测得20组数据，实验结果如图3所示。

由图3可以看出，本文提出的基于启发式算法改进的虚拟机综合优化初始化部署算法，随着虚拟机创建数量的增多，相对于OpenStack内置算法的性能优势越来越明显。以此说明了该算法的有效性。

4 结语

本文通过研究虚拟机的创建的流程，并通过对OpenStack内置的虚拟机资源调度算法的分析，针对内置算法的不足，对基于启发式虚拟机资源调度算法进行了改进，并提出了综合负载优化调度算法，并通过在CloudSim云仿真平台上进行了算法的仿真，仿真结果表明该算法减少了物理服务器的使用数量，提高了资源利用率，减少了平台的能耗。本文的下一步重点将放在虚拟机的动态迁移策略上。

[参考文献]

[1]赛迪顾问有限公司中國云计算产业发展白皮书[J]中国信息通信研究院，2010 （1）：3-4.

[2]孙春玲，陈智斌，李建平.装箱问题的一种新的近似算法[J].云南大学学报，2004 （5）：392-396.

[3]杨星，马自堂，孙磊.云环境下基于改进蚁群算法的虚拟机批量部署研究[J]计算机科学，2012（9）：33-37