基于改进禁忌搜索的云任务负载均衡调度策略研究

陆佳炜，李 杰，张元鸣，肖 刚

(浙江工业大学 计算机科学与技术学院，杭州 310000)

1 引 言

云计算源于分布式计算、网格计算，是一种完全基于互联网的计算方式[1]，其遵循"按需付费"的模式为用户提供低成本、高可靠性、可伸缩的计算资源及服务.在云环境中，采用合理的任务调度算法可以有效的提高计算资源利用率、缩短总任务完成时间、降低云计算环境中的负载均衡.因此，任务调度已经成为云计算中的一个研究热点[2,3].

任务调度是指在一段时间内分配执行一组任务的资源[4].任务调度的目标之一是最小化任务的完成时间[5].通常来说，任务调度问题已被证明是一个NP-hard问题[6]，即随着问题规模的增加，总能找到一种较优的解决方案.良好的任务调度算法必须在满足用户服务质量的同时，降低负载均衡保证云环境的稳定性及节约能耗.

云环境中任务的处理单元称为虚拟机(VMs)，因此，减少虚拟机上任务的总体执行时间是用户的一个重要关注点[7].从业务的角度出发，虚拟机应尽可能早地并行执行任务.即任意时刻，单台虚拟机上的任务量不会过载，并且所有虚拟机都尽可能保持工作状态.因此，云任务负载均衡调度算法要尽可能保证资源利用的最大化，并能改善用户提交的云任务完成时间[8].

迄今为止，国内外研究者已经提出了许多启发式和元启发式算法用来解决任务调度问题，如文献[9,10]提出了尽可能将小任务分配到执行速度快的资源上运行的Min-Min算法；文献[11]提出了一种对时间贪心的Min-Max算法，其将小任务和大任务"捆绑"在一起执行调度，从而有效地解决了负载不均衡的问题；文献[1,12]将遗传算法运用到任务调度中，用于求解任务调度最优解；文献[13,14]考虑任务执行时间和负载均衡的优先级影响，提出一种粒子群优化算法提高任务调度效率；文献[7]提出了一种模拟蜜蜂采蜜机理的负载均衡策略，基于负载均衡评价模型进行任务交换以有效降低任务完成时间；文献[15]以最小化任务完成时间为目标给出了一种基于蚁群优化算法的云任务调度策略.

禁忌搜索[16]算法是一种启发式算法，具有智能记忆功能，求出的最优解优于传统算法，同时具有效率较高的搜索功能，在解决NP-hard问题时具有一定的优势.文献[17]将其运用于仓库调度多目标优化问题，建立了兼顾质量和路径的多目标优化模型，但其未完全克服禁忌搜索算法对任务初始解依赖性较强的缺点.文献[18]中提出了一种基于禁忌搜索的负载均衡任务调度算法，通过动态规划方法形式化推导出任务初始解，结合任务完成时间的收益值进行任务交换，在一定程度上降低了资源的负载均衡度，但其未考虑任务量较大时，可能会陷入局部最优的问题.

因此，本文提出了一种基于多因素优值和惩戒策略的禁忌搜索算法(Benefit Punishment Tabu，BP-Tabu)的云任务负载均衡策略，对任务调度进行多方面的综合优化.即通过综合考虑任务总体完成时间、虚拟资源负载均衡、虚拟机使用效益等多个因素的优值函数，作为衡量不同任务调度方案的优值，然后基于虚拟机随机分量函数提出一种跳出局部最优的惩戒策略，最后进行实验对比证明此算法在云任务调度中的可行性.

2 问题描述及数学建模

2.1 问题描述

由于云计算采用虚拟化技术实现资源的按需提供服务，资源可分为物理资源和虚拟资源.因此，云计算环境下的资源调度又分为虚拟资源层面的调度和物理资源层面的调度[19].图1为云计算中的资源调度模型.

图1 资源调度模型图Fig.1 Resource scheduling model

虚拟资源层面的调度又称为任务调度，即用户需求(Client requirements)提交后，被分解成一组互相独立的子任务集合(Task)，每个子任务都是一个执行特定功能的单元，并且是任务调度的最小粒度，这些子任务调度至合适虚拟机(VM)进行执行的过程称为虚拟资源层面的调度[20]；物理资源层面的调度指虚拟机选择合适的物理主机(host)上运行的过程.本文重点研究虚拟资源层面的调度，即任务调度.在数学建模之前，我们先归纳需要使用的术语，如表1所示.

表1 符号和参数定义Table 1 Symbol and parameter definitions

2.2 数学建模

假设给定一个任务集合Tasks={t1,t2,…,tn}，包含n个待分配的任务，任务ti的总指令长度为MIi.云环境中存在一组工作中的虚拟机集合VMs={vm1,vm2,…，vmm}，虚拟机vmj的指令执行速度为MIPSj.假设所有虚拟机都是互不干扰，并行执行的，任务之间相互独立，互不抢占资源.任务ti在虚拟机vmj上执行的预期完成时间为ctij，定义如下：

(1)

2.2.1 虚拟机负载

对于某任务分配方案P，假设虚拟机vmj上已经完成了前k-1个任务分配，定义虚拟机vmj的当前负载vlj为分配给虚拟机vmj的所有任务所需执行时间：

(2)

同一时刻，对于任务tk，定义其在虚拟机vmj上的时间跨度为makespankj，即任务tk在vmj上执行的最早完成时间.根据公式(1)、公式(2)，makespankj为虚拟机vmj当前负载vlj与任务tk在vmj上的预期完成时间的和值：

makespankj=vlj+ctkj

(3)

最终定义虚拟机的负载VLj为分配给第j个虚拟机vmj所有任务的预期完成时间.VLj越大，说明虚拟机vmj负载越高.

(4)

2.2.2 负载均衡度

(5)

对于任务调度方案P，结合公式(4)、(5)，给出虚拟机总的负载均衡度定义如下：

(6)

若方案P的负载均衡度LBp越小，说明该任务调度方案下，云环境的任务负载越均衡.

2.2.3 多因素优值函数

针对任务调度方案集合η中的不同调度方案，本文给出优值函数用于衡量该任务调度方案的优值，最终选择优值高的调度方案完成任务集合Tasks的调度.

首先根据虚拟机处理能力MIPS、指令的执行成本α以及延迟成本DP，定义虚拟机利用效益函数VMUj，用于衡量虚拟机的使用效益.则虚拟机vmj当前状态下VMUj为虚拟机vmj的利用效益，表示如下：

VMUj=vmu(α,DP,MIPSj)

(7)

结合公式(6)、公式(7)，给出用于衡量任务调度方案P的优值函数Bp定义：

(8)

其中w1，w2为权重值.优值函数Bp越高，说明此任务调度方案越优.

2.2.4 惩戒策略

由于原始Tabu搜索算法的藐视准则无法保证搜索陷入局部最优时一定能够跳出，本文在此基础上提出了惩戒策略，其基本思想是：对修改禁忌表tabuList中禁忌对象的次数进行记录，其记录次数用pt表示，初始值为0.当禁忌对象进入禁忌表时，pt加1，当连续h次tabuList集没有更新时，即pt=h时，将会启动惩戒策略.

定义虚拟机随机分量函数P*(h)如下：

P*(h)=P(h)+w×h

(9)

其中P(h)为当前最小虚拟机的索引量，w为随机惩戒常量，h为记录次数阈值.

虚拟机分量函数的增加会对任务负载VLmin最小的虚拟机VMmin的选择产生影响，VMmin的索引量P(h)会偏移，根据最新的P(h)选择相应的虚拟机代替VMmin，最终引导搜索跳出局部最优.

3 BP-Tabu搜索算法

3.1 算法思想

云计算环境下，各个任务调度方法都存在着一定的不足，例如Min-Min[9,10]、Min-Max[11]等启发式算法重点考虑任务完成时间，而未考虑到云资源利用率的最大化及虚拟资源的负载情况；遗传算法[1,12]、粒子群算法[13]等元启发式算法在大任务量情况下易陷入局部最优的困境.本文提出的BP-Tabu搜索算法适用于云任务调度，能够克服现有云环境下任务分配不均衡、单台虚拟机资源负载过大或者空闲较多的问题.

3.2 初始解构造

基于时间贪心算法，定义任务集合Tasks根据MI的大小进行降序排列后得到的结果集为STasks；定义虚拟机集合VMs根据MIPS的大小进行升序排列后得到的结果集为SVMs.根据公式(1)，结合排序之后的STasks和SVMs生成预期完成时间矩阵CT.从行号h=1开始，每次都将任务th自CT矩阵最后一列对应的虚拟机vmm往前分配，依次计算任务th分配给各虚拟机后的时间跨度makespanhj(公式(3))，选择使makespanhj最优的虚拟机vmj完成分配，若存在多个分配方案，挑选任务运行数最少的虚拟机资源进行分配，实现初步的负载均衡.待所有任务均完成分配，则结束算法(图2)，整个初始解构造伪代码如图2所示.

图2 初始解构造伪代码Fig.2 Initial solution algorithm

3.3 BP-Tabu搜索算法设计

在给出通过时间贪心求得的任务调度初始解(3.2节)、多因素优值函数(2.2.3节)以及惩戒策略(2.2.4节)的基础上，本文提出了一种改进的基于BP-Tabu搜索的云任务负载均衡算法，其设计流程如图3所示.

图3 基于BP-Tabu搜索的云任务负载均衡算法流程图Fig.3 BP-Tabu flow diagram

下面给出BP-Tabu搜索算法的具体步骤：

1) 初始化设置.定义禁忌数组tabuList[1,2,…,n]，其中数组的各元素初始值均为1，用于标识该任务可以被交换；设置虚拟机随机分量函数P*(h)，初始化记录次数阈值h、随机惩戒常量w以及记录次数pt=0；

VMmax=max{VLj|j∈m,j=1,2,…,m}

(10)

VMmin=min{VLj|j∈m,j=1,2,…,m}

(11)

判断记录次数pt是否达到记录次数阈值h，若是，触发惩戒策略，根据虚拟机随机分量函数P*(h)(公式(9))重新选择VMmin；

Ifh≤pt,VMmin=VMp*(h)%m

(12)

3) 任务交换.选择虚拟机VMmax上可被用于交换的任务tk，设置其禁忌值tabuList[k]=0；若VMmax上的任务均被标记为不可交换，则完成任务分配，结束算法；否则，定义TVMmin为分配在虚拟机VMmin上的任务集合，并计算得出任务交换函数MBT(k,l)(公式(13))，其中Bkl、Blk分别表示未交换及交换状态下的优值函数值(公式(8)).

MBT(k,l)=max{Blk-Bkl|l∈TVMmin,l=1,2,…,m}

(13)

图4 BP-Tabu搜索算法伪代码Fig.4 BP-Tabu algorithm

如果存在任务l使任务交换函数MBT(k,l)大于0，则进行任务交换，定义A↔B为A和B值的互换，设置禁忌值tabuList[l]=0；否则，设置记录次数pt=pt+1.BP-Tabu搜索算法的伪代码如图4所示.

在一个有n个任务和m个虚拟机资源的云环境中，假设任务数量n不小于虚拟机资源数量m(n≥m)，本文的算法时间复杂度主要分为两部分：

2)BP-Tabu搜索算法中使用禁忌数组及优值交换的策略，计算可得时间复杂度为O(n2).

由此可得，BP-Tabu搜索算法总时间复杂度为O(n2).

4 实验分析

4.1 实验设置

4.1.1 实验工具与算法实现

本文实验使用CloudSim云计算仿真工具，它是一个用于云计算基础设施和服务建模的仿真框架[21].由于BP-Tabu搜索算法添加了工作负载、多因素优值函数和惩戒策略等特性，因此对工具包CloudSim进行扩展以满足模拟实验要求.

图5为CloudSim仿真数据流图.在仿真开始前，每个数据中心(DataCenter)实体会在云信息服务(CloudInformationService)注册表中注册.仿真开始时，数据中心代理类(DataCenterBroker)通过云信息服务中注册的数据中心，获取数据中心特征信息，为用户提供合适的资源列表.之后在匹配的数据中心中创建虚拟资源进行任务调度.任务完成之后，销毁虚拟资源.

其中DataCenterBroker为数据中心代理的功能实现类，作为云环境下数据中心和云任务共同协作的中介者.本文算法的实现主要通过对DataCenterBroker类进行二次开发来完成，读者可下载和运行BP-Tabu算法相关程序代码(https://github.com/viivan/BP-Tabu-for-cloudsim)进行深入了解.

图5 CloudSim仿真数据流图Fig.5 CloudSim simulation data flow

4.1.2 案例背景及CloudSim参数设置

有限元分析是指工程项目借助于计算机完成，建立计算模型并进行分析计算，一个完整的有限元分析过程包括前处理、计算和后处理三个过程.其中，计算过程是有限元分析过程中最重要的一部分，但由于有限元分析计算量极大，对服务器性能要求较高，因此，提升有限元求解的计算效率是当前有限元分析领域的研究热点之一[22].

班主任制度下的PDCA学风管理模式是以班级为单位，以学生为主体，以班主任为主导的学习质量控制体系。其中，班级整体学风建设是大的PD-CA循环，每个学生个体学习质量提升是小的PDCA循环，班级整体学风建设要依靠学生个体学习质量提升作为动力和检验指标。

本文以有限元分析在云环境下的任务调度为案例展开研究.由于工程项目中，有限元分析的计算任务都较为复杂，因此在使用云计算仿真框架CloudSim对有限元子任务进行模拟之前，我们采用EBE[23]方法先将有限元计算任务拆解为互不干涉的子任务.每个有限元分析计算子任务需要各自计算单元刚度矩阵、单元载荷向量并进行边界条件处理，然后计算各子任务的位移和应力，最终整合得到计算任务的总体节点位移和应力.

我们首先使用有限元分析软件对一个划分成10万个网格节点的机械结构进行单机分析，多次计算后得出平均求解时间计为δ≈170s.然后，根据真实的有限元分析过程选择参数进行，仿真实验设定实验的任务总数为100～4000，每个任务的指令长度MI由随机数产生且各不相同，近似代表了每个网格节点数的计算量，取值范围在[1000,5000]；设定实验中有10个虚拟机资源，每个虚拟机的处理能力MIPS由随机数产生且各不相同，取值范围在[200,400].在以上条件设定下，模拟环境中一台MIPS为300的虚拟机处理MI总量为10万的任务所消耗的时间可与δ近似.具体参数设置如表2所示.

表2 参数设置表Table 2 Parameter setting

4.2 仿真实验结果分析

为了验证本文提出的BP-Tabu搜索算法的性能及有效性，以有限元分析在云环境下的任务调度为应用背景，与常见的任务调度算法进行比较，包括有限元分析中的默认轮询算法RR[24]、融入贪心策略的Min-Max调度算法[11]、基于蚁群优化任务调度算法ACO[15]、基于禁忌搜索的负载均衡任务调度优化算法[18](以下简称Tabu).为了保证对比的公平性，实验环境均为：Mac OS X 10.11.3 EI Capitan系统平台、主频2.7Hz、内存8GB，编程及调试环境MyEclipse 2014.

本文主要用来验证的评价指标如下：

1) 任务总体完成时间；

2) 负载均衡度；

3) 资源利用率；

4.2.1 任务总体完成时间

本节实验侧重任务总体完成时间的比较，因此设置在任务总数分别为1000、2000、3000和4000的情况下，使用RR算法、Min-Max算法、ACO算法、Tabu算法和BP-Tabu算法这5种不同的任务调度算法进行实验对比，五种算法的任务总体完成时间如图6所示.

图6 5种算法的任务总体完成时间Fig.6 Makespan of the five algorithms

从图6得出：在任务数量的不断增长的情况下，任务总体完成时间呈线性增长；在相同任务总数的情况下，BP-Tabu算法的任务总体完成时间最优，且各类算法都优于有限元分析默认的轮询RR算法.

同时，为了评估本文提出的惩戒策略的有效性，在相同实验条件下，本文将BP-Tabu算法与其未添加惩戒策略的情况下(称为B-Tabu)进行实验对比，实验结果如图7所示.

从图7可以得出：任务量较小时，BP-Tabu算法与B-Tabu算法的任务总体完成时间大致趋于一致，当任务量逐渐增大时，拥有惩戒策略的BP-Tabu算法的任务总体完成时间渐渐优于B-Tabu算法.由此可以得出，任务量较大时，B-Tabu算法容易陷入局部最优的局面，本文的惩戒策略在局部最优问题上具有一定程度的优化效果.

图7 BP-Tabu与B-Tabu的任务总体完成时间Fig.7 Makespan of BP-Tabu and B-Tabu

4.2.2 负载均衡度

本节实验侧重负载均衡度的比较，因此根据任务数量大小分别设置两组实验进行对比，第一组实验任务数量分别为100、200、300、400，第二组实验任务数量分别为1000、2000、3000、4000.使用RR算法、Min-Max算法、ACO算法、Tabu算法和BP-Tabu算法这5种不同的任务调度算法进行实验对比.其中，对于某一任务调度方案P，其负载均衡为LBp(公式(6)).两组实验的负载均衡度如图8、图9所示.

图8 任务量较小时五种算法的负载均衡度Fig.8 Load balancing of the five algorithm with small tasks

图9 任务量较大时五种算法的负载均衡度Fig.9 Load balancing of the five algorithm with large tasks

从图8可以得出：有限元分析默认的RR算法未考虑到计算资源的负载均衡，因此其负载均衡度最差；Min-Max算法通过大小任务"捆绑"的方式，一定程度上起到了负载均衡的作用，因此其负载均衡度优于RR算法，但与Tabu、ACO和BP-Tabu三种算法相比，后三者的负载均衡度均更优.从图9可以得出，随着任务量的不断增大，基于多因素优值函数的BP-Tabu算法的负载均衡度较低，云环境下的虚拟机负载较均衡.

4.2.3 资源利用率

本节实验侧重资源利用率的比较，因此设置在任务总数分别为1000、2000、3000和4000的情况下，使用RR算法、Max-Min算法、ACO算法、Tabu算法和BP-Tabu算法这五种不同的任务调度算法进行实验对比，5种算法的资源利用率如图10所示.

从图10得出,RR算法未考虑到资源利用率情况，因此利用率最低；Min-Max和ACO算法资源利用率低于Tabu、BP-Tabu算法；而BP-Tabu相较Tabu算法，增加了包含虚拟机利用率的多因素优值函数，因此资源利用率优于Tabu算法.

图10 系统整体资源利用率Fig.10 Utilization rate of entire system

5 结束语

本文提出了一种基于BP-Tabu的云任务负载均衡调度策略，适用于云环境下任务调度的负载均衡方面，能够克服现有云资源任务调度方法陷入任务分配不均衡、单台虚拟机资源负载过大或者空闲较多的问题.该策略综合考虑任务总完成时间及虚拟机负载均衡度，首先通过时间贪心求得策略初始解，进而结合多因素优值函数的Tabu算法优化任务调度的负载均衡，再进一步提出惩戒策略帮助BP-Tabu算法跳出局部最优.并以有限元分析在云环境下的任务调度为应用背景，通过CloudSim进行仿真实验，证明此算法不仅缩短了复杂有限元任务执行的总体完成时间，同时优化了虚拟资源负载均衡度，可见云任务调度技术在优化传统行业的复杂工程计算任务方面，具有一定的研究价值和现实意义.但本文的工作默认任务是相互独立的，未考虑用户QoS因素对任务调度的影响，因此在下一步研究中还需加入任务优先级等QoS因素来改进此算法.