虚拟机簇的双目标优化遗传迭代调度算法

祝衍军

(东莞职业技术学院 计算机工程系,广东 东莞　523808)

虚拟机簇的双目标优化遗传迭代调度算法

祝衍军

(东莞职业技术学院 计算机工程系,广东 东莞523808)

摘要:文章在遗传算法的基础上,构建了一种用于虚拟机簇部署的调度算法。此算法的核心是适应度函数的构建,构建的基础是2个优化目标:一个是结合CPU、内存、硬盘、带宽等参数的资源利用率,另一个是基于计算时间的处理效率。为了考察此算法的效果,选取启发式算法和GC(graph cut)算法作为比较算法。实验结果表明基于双目标优化的遗传迭代调度算法,具有更高的资源利用率和处理效率。

关键词:虚拟机簇;遗传算法;资源利用率;处理效率

虚拟化技术的出现,为云计算实现资源和硬件平台之间的松耦合连接创造了条件,使得云端的服务更加灵活、便利、高效[1]。云服务请求和执行被清晰地分割为2个阶段,根据任务需求调度虚拟机资源,再将虚拟机配置在最合理的物理主机之上[2]。

对于计算量小、任务单一的云服务请求,虚拟化技术较好地解决了实际问题[3]。研究者主要考虑单虚拟机在不同硬件平台上的调度和部署问题,如应用蚁群算法、多属性决策等优化技术,尽可能提升云服务过程中的资源利用效率[4-5]。随着大数据技术和云计算的发展,先前的针对单虚拟机的调度和部署算法已经很难满足实际需求。文献[6]认为,要解决大任务的最佳云服务问题,需要将大任务分解成多个子任务,进而设置多个优化目标来进行虚拟机资源的优化调度和部署。对于计算量较大的任务,往往需要多个虚拟机和多个物理主机来配合完成,虚拟机的调度问题则从单虚拟机调度转化为虚拟机的批量调度。为此,文献[7]对蚁群算法进行了改进,取得了较好的效果。文献[8]将多虚拟机部署问题,用虚拟机簇来描述,并构建了一种基于负载感知的调度方法,也取得了优于单虚拟机的部署效果。文献[9-10]提出了一种机器学习技术,能够对虚拟机和基于虚拟机的应用同时进行实时的自动化配置和再配置,并在此基础上提出一种基于强化学习方法虚拟机簇管理技术。

虚拟机簇的调度和配置问题,就是簇内多个虚拟机同时调度和配置的问题。因为虚拟机簇不仅包含了多个虚拟机,簇内各个虚拟机之间还存在一定的关联,这对于调度算法的要求就大大高于单个虚拟机的调度[11]。从现有的研究成果来看,虚拟机部署正在从单个虚拟机部署逐步演变为多虚拟机调度,也就是虚拟机簇的调度问题[12-13]。本文借助遗传算法和双目标优化的适应度函数,实现虚拟机簇的调度。

1基于双目标的遗传迭代算法框架

1.1虚拟机簇的染色体设置

假设云端同时要解决15个任务,并希望由4个虚拟机构成的虚拟机簇来完成任务。根据遗传迭代算法的基本设置需求,15即成为染色体的长度。分别用A、B、C、D来表征虚拟机簇中的4个虚拟机,可以构建一个染色体为:r=[C,B,D,A,A,C,B,C,A,D,D,D,A,B,C],根据此染色体中的基因排布,4个虚拟机分别承担了15个任务中不同数量的任务。

虚拟机A:完成4号、5号、9号、13号任务。

虚拟机B:完成2号、7号、14号任务。

虚拟机C:完成1号、6号、8号、15号任务。

虚拟机D:完成3号、10号、11号、12号任务。

所以,通过遗传算法确定一个具体的染色体,就可以实现虚拟机簇适应任务需要的合理调度。

1.2基于云端资源的初始种群生成

对于遗传算法设置中的初始种群,需要依托虚拟机簇的数量来实现,根据遗传算法的实际应用经验,初始种群的规模最好大于10。如果设定初始种群规模为20,就有20个虚拟机簇要参与任务调度算法的选择比较。染色体的长度根据任务数量进行设置,基因的可能出现情况取决于虚拟机簇中虚拟机的个数和配置标号。

1.3基于双目标优化的适应度函数构建

虚拟机簇任务调度算法的适应度函数应该体现在不同部署后云端的资源利用率和处理效率。虚拟机资源需求主要包括4个因素——CPU、内存、硬盘、带宽,下面从这4个角度来考虑虚拟机簇进行任务调度时的资源利用率。令M表示虚拟机簇,有M={m1,m2,…,mi,…};令T表示任务集合,有T={T1,T2,…,Tj,…}。资源利用率计算公式为:

(1)

从处理效率的角度看,虚拟机簇完成任务集合中的任务所花费的时间越少越好,这个时间的衡量,即虚拟机簇中每个虚拟机完成自身承担所有任务的最长时间,其计算公式为:

(2)

至此,代表资源利用率的R和处理效率的t就成为虚拟机簇任务调度时的2个优化目标,这2个目标也是遗传迭代中构建适应度函数的基础。考虑到2个优化目标,R越大越好、t越小越好,据此构建的适应度函数如(3)式所示。

(3)

根据这个适应度函数的构造关系,在遗传迭代的过程中,希望F(R,t)越小越好。

1.4遗传迭代过程中的关键操作

根据遗传算法的基本原理,种族中个体的诞生要经过2个个体的交叉繁殖,通过遗传和变异不断生成新的个体。通过初始化种群个体的数量以及控制繁殖的代数来确定总的个体个数,进而在遍历全部个体的过程中选出最优个体。对于本文而言,最优个体确定后,就可以根据这个个体的染色体来确定其基因排布,也就可以确定各个虚拟机上完成的具体任务了。

(1) 交叉繁殖。本文采用按序交叉模式,设第1代父辈的2个个体的染色体如下:

选取母个体r2中的基因串“ACAB”为交叉基因串,对父个体r1进行调整,诞生新个体的过程如图1所示。

(2) 变异繁殖。变异是个体染色体中某个基因发生突变的情况,变异发生的机率非常小,但对于种群进化起到非常重要的作用。在本文的算法中,用随机数和小概率函数乘积来模拟变异的情况,如(4)式所示。

Bit(r)=Bit{Random[p(eJ-1)]}

(4)

其中,Bit(r)代表染色体中的某一位。

(3) 最优个体选择。要选择整个种群中最优秀的染色体,除了依托适应度函数之外,还要根据遗传代数计算其被选择的累积概率。假设遗传迭代过程进行D代,则在第d代中,ri被选中的概率为:

(5)

其中,Z为种群中这一代所有染色体的数量。

在全部D代中,ri被选中的累积概率为:

(6)

p(D)最大的ri将会成为最优个体,也就是本文虚拟机簇调度的方案。

2实验结果与分析

为了验证本文方法的有效性,对基于双目标优化遗传迭代的虚拟机簇调度算法进行实验研究。实验验证平台和程序编制选择Matlab7.0,虚拟机数量设置为80～800个,每4个虚拟机为1个虚拟机簇,虚拟机簇个数则为20～200个。虚拟机簇的数目也就相当于个体种群的数量。任务的数量为15个,这些任务的4种资源需求见表1所列。

表1　各个任务的资源需求

所有虚拟机都可以承担至少1项任务,并且是表1中的最大任务。虚拟机资源配置最低的情况为:CPU 1 000 MIPS、内存2.0 GB、硬盘50 GB、带宽100 MB/s。资源配置高的虚拟机,则可以同时承载几项任务,对应着遗传迭代算法中染色体内某个基因反复出现几次。

实验中,染色体的长度设置与云计算要完成的任务数相同,都为15个。遗传迭代的适应度函数设置中,α1、α2、α3、α4都设置为0.25,β1、β2都设置为0.5。为了和本文方法对比,在虚拟机簇调度过程中,选择了另外2种方法作为比较方法,一个是启发式算法,另一个是GC(graph cut)算法。3种方法形成虚拟机簇部署后,资源利用率的对比结果如图2所示。

图2　资源利用率实验结果

从图2可以看出,当虚拟机簇的个数为20时,3种方法调度后承担任务的虚拟机簇的资源利用率都比较高,没有造成过多的资源浪费。随着虚拟机簇数目的增加,也就是种群规模的不断扩大,本文算法的优势逐渐显现,其调度后的虚拟机簇的资源利用率依然能维持在85%左右。GC算法则呈现比较稳定的下降趋势,启发式算法呈现波动性下降趋势,当虚拟机簇增加到200时,这2种算法的资源利用率都下降到50%以下。

时间效率实验结果如图3所示。

图3　时间效率实验结果

从图3可以看出,3种方法的调度时间有着明显的区别,GC算法的调度时间最长,启发式算法的调度时间次之,本文算法调度时间最短。随着虚拟机簇数目的增加,本文算法的调度时间优势逐渐加大。

3结束语

针对虚拟机簇的调度问题,本文依托遗传迭代算法构建了一种全新的调度算法。在此算法中,根据虚拟机和所承担任务的关系构建个体的染色体,根据任务数量初始化种群规模,基于资源利用率和处理效率构建适应度函数,依据按序模式完成个体的交叉运算,根据累积概率选择最优个体,进而解码出虚拟机簇的调度结果。实验结果表明,本文构建的方法较好地完成了虚拟机簇的调度,调度结果具有更高的资源利用率和处理效率。

[参考文献]

[1]Rana S,Jasola S,Kumar R.A hybrid sequential approach for data clustering using K-Means and particle swarm optimization algorithm [J].International Journal of Engineering,Science and Technology,2010,2(6): 167-176.

[2]Calheiros R.N,Ranjan R,Beloglazov A,et al.CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms [J].Software: Practice and Experience,2011,41(1): 23-50.

[3]Jayasinghe D,Pu C,Eilam T.Improving performance and availability of services hosted on IaaS clouds with structural constraint-aware virtual machine placement[C]//2011 IEEE International Conference on Services Computing.Piscataway: IEEE,2011: 72-79.

[4]温少君,陈俊杰,郭涛.一种云平台中优化的虚拟机部署机制[J].计算机工程,2012,38(11): 17-19.

[5]庄威,桂小林,林建材,等.云环境下基于多属性层次分析的虚拟机部署与调度策略[J].西安交通大学学报,2013,47(2): 28-32.

[6]李强,郝沁汾,肖利民,等.云计算中虚拟机放置的自适应管理与多目标优化[J].计算机学报,2011,34(12):2253-2264.

[7]杨星,马自堂,孙磊.云环境下基于改进蚁群算法的虚拟机批量部署研究[J].计算机科学,2012,39(9): 33-37.

[8]王光波,马自堂,孙磊,等.基于架构负载感知的虚拟机聚簇部署算法[J].计算机应用,2013,33(5): 1271-1275.

[9]Xu Chengzhong,Rao Jia,Bu Xiangping.URL: a unified reinforcement learning approach for autonomic cloud management [J].Journal of Parallel and Distributed Computing,2012,72(2): 95-105.

[10]Rao Jia,Bu Xiangping,Xu Chengzhong,et al.VCONF: a reinforcement learning approach to virtual machines auto-configuration[C]//Proceedings of International Conference on Autonomic Computing and Communications.New York:ACM,2009: 137-146.

[11]Kim C,Jeon C,Lee W,et al.A parallel migration scheme for fast virtual machine relocation on a cloud cluster [J].Journal of Supercomputing,2015,71(12):4623-4645.

[12]Yang C T,Liu J C,Huang K L,et al.A method for managing green power of a virtual machine cluster in cloud [J].Future Generation Computer Systems,2014,37: 26-36.

[13]李晨,刘博,李云.云环境下基于碎片影响度的提前预定资源调度策略[J].合肥工业大学学报:自然科学版,2015,38(7): 914-917,991.

(责任编辑张淑艳)

Genetic iterative scheduling cluster algorithm for virtual machine based on double objective optimization

ZHU Yan-jun

(Dept. of Computer Engineering, Dongguan Polytechnic, Dongguan 523808, China)

Abstract:Based on the genetic algorithm, a scheduling algorithm for the virtual machine cluster was developed. The core of this algorithm is the construction of fitness function, and its basis is two optimization objectives: one is resource utility with four parameters of CPU, RAM, hardware and bandwidth; the other is processing efficiency based on computing time. In order to investigate the effect of this algorithm, heuristic algorithm and graph cut(GC) algorithm are selected as the comparison algorithm. The experimental results show that the genetic iterative scheduling algorithm based on double objective optimization has higher resource utility and processing efficiency.

Key words:virtual machine cluster; genetic algorithm; resource utility; processing efficiency

收稿日期：2015-07-01；修回日期：2016-03-10

基金项目：广东省省级科技计划资助项目(2014A010103002);东莞市高等院校、科研机构科技计划一般资助项目(2014106101037;2014106101033) 和东莞职业技术学院政校行企合作开展科研与服务资助项目(ZXHQ2014d010)

作者简介：祝衍军(1982-),男,湖南邵阳人,东莞职业技术学院工程师.

doi:10.3969/j.issn.1003-5060.2016.05.012

中图分类号:TP393.01

文献标识码：A

文章编号：1003-5060(2016)05-0632-04