高性能计算平台中基于云计算的虚拟机优化调度研究

吴超越

（南京晓庄学院，江苏 南京 211171）

高性能计算平台中基于云计算的虚拟机优化调度研究

吴超越

（南京晓庄学院，江苏 南京 211171）

虚拟机资源在云计算环境的分配是云计算的重要技术环节，虚拟资源是否能被高效调用是制约是云计算效率的重要指标.本文提出一种引入蚂蚁相遇机制的改进蚁群算法，并将其应用到云计算虚拟机资源调度中.

云计算；虚拟机；蚁群算法

1 云计算概述

云计算是以虚拟化技术为基础，以网络为载体提供基础架构、平台、软件等服务为形式，整合大规模可扩展的计算、存储、数据、应用等分布式计算资源进行协同工作的超级计算模式.云系统的后台有大量的集群使用虚拟机的方式，通过高速的互联网互连，组成大型的虚拟资源池.这些资源池可自主管理和配置，用数据冗余的方式保证虚拟资源的高可用性.并具有分布式存储和计算、高扩展性、高可用性、用户良好性等特征.

2 优化的蚁群优化算法

2.1 蚁群算法与蚂蚁系统

蚁群算法能模拟真实蚂蚁搜索食物时相互间的反馈和群体分布协作行为，获得优化的行进路线，因此路径蚁群算法在诸如旅行查找等随机搜索方面具有广泛的应用.总结蚁群算法的运算过程，可概括出以下特点：(1)路径上各个节点的信息素浓度随着时间的推进按一定比例逐渐变化.到访蚂蚁根据周围节点信息素的浓度来计算周围各个节点的可能概率，择优选择概率最高的节点作为下一步的行进节点.(2)为避免蚂蚁陷入程序死循环，当前循环中已经访问的节点将被标记并禁止再次访问.(3)当走过某段路线后，根据该路线的长度信息，蚂蚁将会标记与其长度相适应的相应的信息素.因此，如果经过某路段蚂蚁数量较少，该路径所累积的信息素会随着时间按比例逐渐变少，表明该路线的成功率不高，后面蚂蚁选择的可能性也将慢慢减小.

2.2 改进蚂蚁系统

Map/Reduce是目前广泛使用的海量数据处理编程模型.它将一个较大的用户任务分割成几个较小任务量的子任务，通过虚拟资源分配机制将网络中的空闲节点资源调配到各个子任务.蚁群算法凭借其高稳定性和能分布式并行的优点，被应用到Map/Reduce模型下虚拟机资源的优化调度方面.在云计算环境中任何一个节点能同时运行多个任务，但如果根据每个节点的运行效率，尽量把用户任务分配给网络中效率较高的节点，将大大提高整个云计算网络的效率.基于这一思路，本文为每一个节点定义一个执行任务的预期时间阈值，如果任一节点执行任务的时间不超过该阈值，则判定该节点为有效节点，可供调配给新交的用户任务.

2.2.1 信息素.通过CPU数量及处理能力、内外存和带宽等硬件资源的容量来比较虚拟节点的信息素.CPU计算能力、内外存及带宽的信息素初始化分别为：

每个虚拟机节点上的信息素是各个硬件信息素的加权和，不同的硬件重要性具有不同的加权系数，具体如下式表示：

节点信息素=w1*CPU信息素+w2*内存信息素+w3*外在信息素+w4*带宽信息素

算法运行过程中需要对各信息素执行动态修改，当某个有效节点被分配给当新任务时，节点上CPU利用率会相应增加，相应地该该节点上的信息素将减小.

2.2.2 虚拟机资源调度算法.改进蚂蚁系统在云计算虚拟机资源优化调度方面的步骤主要包括有：（1）首先初始化Worker节点的信息素.（2）将交含有多个任务的用户作业先提交到Master节点，供其分发.（3）Master节点按顺序依次提取出存储队列中的作业，并按该作业的任务数调配相应的节点蚂蚁.如该节点作用有a个任务量，Master节点则为其分配a*b个蚂蚁进行路径探索，同时启动探索定时器.（4）每只蚂蚁预先设定的规则选择下一步的行进节点，并同时标记经过的节点是否是有效节点，如果是有效节点则拷贝有效节点的信息原路返回；否则，蚂蚁则继续判定和选择下一步的先进节点，直到找到有效节点为止，依次规律不断尝试.（5）如果在定时器计数完成前有蚂蚁向Master节点报告有效节点，表示当前有有效节点可用，则该节点会被分配给新接受的用户任务.（6）当某节点被调配给用户任务，或某节点已完成用户任务，则该节点上的信息素会被随之更新，以及时表示该节点是否被占用及可用性.（7）将步骤（3）到（6）一起重复，直到用户作业里的任务全部分配完毕.

2.3 改进蚁群算法

本文提出一种对蚂蚁系统模型的改进措施，并在此基础上，设计一种改进的蚁群算法.

2.3.1 蚂蚁相遇机制.根据蚂蚁在节点网络中的行进方向，将人工蚂蚁分为前向蚂蚁和反向蚂蚁两种.前向蚂蚁搜索云计算环境中的有效虚拟资源节点；当有效虚拟机节点被前身蚂蚁搜索到后，算法产生反向蚂蚁向Master节点报告发现.反向蚂蚁按原路程返回,在返回途中经过节点时标记其中可用资源的信息素及任务预期时间等.初始时，系统为每个节点分配存储区，用于存储反向蚂蚁所携带的节点信息，同时开户定时器.如果前向蚂蚁在计时器预设时间到来之前行进到该节点，算法判定此时有两只蚂蚁在此节点相遇.而定时器归零后系统自动清除节点上所登记的信息，以准备更新可能的新信息.同一个节点在不同时刻可能会有不止一个反向蚂蚁到访，这些不同的反向蚂蚁源自于多个被发现的有效节点，因此算法需要判别每一只反向蚂蚁由中哪一个有效节点生成.

2.3.2 前向蚂蚁行进规则.前向蚂蚁在考虑下一步行进节点时需要考虑两种情形，一种情形是前向蚂蚁在行进过程中还没有遇到返回的反向蚂蚁；另一种情形是前向蚂蚁在选择下一步行进节点时遇到了反向蚂蚁，此时需要参考反向蚂蚁所报告的信息，以提高选择下一步节点的有效性.据此，前向蚂蚁需要根据不同的情形选择不同的下一步行进节点.前向蚂蚁如果在行进过程中没有与反射蚂蚁相遇，则根据以下公式计算各节点概率，并选择概率最大的节点为行进方向.

从节点i到节点j概率=

假设前向蚂蚁在某节点与反射蚂蚁相遇，则在选择下一步行进节点时需按两种情况进行分析：（1）若前向蚂蚁和反向蚂蚁在某节点相遇，而该相遇节点仅登记唯一一个反向蚂蚁标记的信息，且该相遇节点的相邻节点也同样登记了来自反向蚂蚁的信息，此时需要逐一计算选择某候选节点的概率，并将此概率与其该相邻节点的概率进行比较，择优选择有效概率最大的节点作为下一步行进的节点.（2）若前向蚂蚁和反向蚂蚁在某节点相遇，且相遇节点已登记了来自多个反向蚂蚁的信息，此时需要在所有被反向蚂蚁标记过的节点集合和候选节点集合中择优选择有效概率最大的节点作为下一步行进的节点.

3 实验结果与分析

实验中信息素及任务预期时间在调度中的的权重分别以α、β表示；蚂蚁数量以n表示.α，β和n的优化组合需要通过实验获得.本文中涉及的比例因子均为0.2.本实验将虚拟机节点数量设定为150，每个虚拟机具有约500MIPS的双核计算能力；内存容量设定为200兆；带宽为2兆每秒；外存容量为1G.实验中提交一个可被分割成20个任务量的用户作业，将其向云计算中心反复提交10次，并分别使用基于改进蚂蚁系统模型和基于改进蚁群算法的虚拟机优化调度算法进行资源的分配.实验首先需要得到α，β和n的最优组合，该最优组合可通过多次尝试试验得到(如表1所示).

表1 实验数据

由表1实验数据得出，当α=1，β=2，n=2.5时组合达到最优.以此组合为参数，实验用基于改进蚂蚁系统模型和基于改进蚁群算法调度方法处理具有20个任务量的作业，实验结果如表2：

表2 实验结果

可见，由于增加了蚂蚁相遇机制，借助反向蚂蚁标记的节有效资源节点信息，前向蚂蚁搜索虚拟机资源效率得以提高，因此基于改进蚁群算法在任务分配时间方面明显要优于基于改进蚂蚁系统模型.

〔1〕吴吉义，平玲娣，潘学增，等.云计算:从概念到平台[J].电信科学，2009(12)：23-30.

〔2〕陈全，邓倩妮.云计算及其关键技术[J].计算机应用，2009 (9)：2562-2567.

TP393

A

1673-260X（2014）09-0024-02