云环境下一种基于负载均衡的任务调度策略

葛君伟，葛 兵，方义秋

(重庆邮电大学 通信与信息工程学院，重庆 400065)

云环境下一种基于负载均衡的任务调度策略

葛君伟，葛 兵，方义秋

(重庆邮电大学 通信与信息工程学院，重庆 400065)

针对云计算环境下大量并行计算节点容易产生计算节点之间的负载不均问题，提出了一种基于任务类型匹配的负载均衡方案。该方案针对任务集中的多种不同长度的子任务类型情况进行判定，并对当前主流的Max-Min和Min-Min两种启发式负载均衡算法进行分析，综合其优缺点，并针对任务集的类型采用不同的算法进行任务调度。实验结果表明在该负载均衡的策略下，提出的方案具有比单一应用Max-Min或者Min-Min算法具有更好的负载均衡特性和更短的完成时间。

云计算；任务调度；负载均衡；Max-Min；Min-Min

云计算是一种新型的商业计算模式，它将计算任务分布在大量异构的计算机构建成的资源池上，使得各种应用系统能够根据需求获取可用的计算资源、数据资源以及存储资源等资源服务[1]。云计算的一个典型特征是具有伸缩性，所以一个云系统也被称为弹性云。

近年来关于云计算中的负载均衡问题是一个研究热点，如今已经有许多的负载均衡算法被提出以满足不同的优化目标。

最大最小算法(Max-Min)和最小最小算法(Max-Min)是一种启发式的调度算法，他们以任务的总执行时间最短为优化目标，Max-Min算法的核心思想是每次先计算任务在各个资源上的预计算时间，然后对最大最早完成时间的任务进行调度。对于元任务集合中长任务少短任务多的情况下，算法的执行效果较好。但是如果具体应用条件发生了变化，Max-Min算法的优势可能就不存在了[2]。

Max-Min 算法和Max-Min算法却正好相反，它是先计算出任务在资源上的预计执行时间，再将最小且是最早完成时间的任务调度到资源节点上，这样会使任务的处理速度较快，任务完成时间短，但是由于每次都是把任务分配给执行最快的资源，这样很容易造成负载的严重不均，甚至一些服务器空载[3]。

基于此，本文提出了一种基于云环境下针对任务类型匹配的资源调度算法，该算法针对任务集中长短任务的不同分布情况来采取不同的调度算法，通过云仿真软件CloudSim 3.0验证了该调度策略良好的调度效果。

1 相关工作

云计算环境下，有大量的负载均衡算法用于将任务调度到相应的计算资源上执行，根据优化的目标不同，算法各有优缺点。当前有国内外学者都相继提出了针对Max-Min算法和Max-Min的缺点的改进算法，Mao等人提出了利用任务状态表预测虚拟机实时负载和任务预计完成时间来动态调度任务[1]，这种方法虽然能够实现较好的负载均衡，但是由于需要维持任务状态表的实时更新，所以会使得开销比较大，任务响应时间偏长。Santhosh B等人提出了一种改进的Max-Min算法[4]，每次将任务集中的和平均任务长度最接近的任务分配给完成时间最短的任务。Upendra Bhoi等人提出一种增强型的Max-Min任务调度算法[5]，针对元任务集中大任务数很少而小任务很多的情况，提出了一种将最大任务优先调度到执行速度最慢的资源上。O.M.Elzeki等人提出一种改进 Max-Min算法[6]，针对小型云计算环境下，将最大执行时间的任务分配给最小完成时间的任务。郑莉等人提出一种基于用户优先级的负载均衡算法[7]，该算法针对Min-Min算法进行改进，一开始用Min-Min算法进行任务分配处理，然后选择负载较重的资源进行资源的重新分配，观察负载重资源上的最短任务，并计算它在其他资源上的完成时间，如果小于任务跨度，那么将此任务从最终负载上移除，用其他资源进行处理。

上述介绍的种种算法，虽然在原有算法的基础上做出了一些改进，但是由于大都在特定的仿真环境下，比如说增强的Max-Min算法，作者给出的实验数据是长任务很少，而短任务很多的情形，所以所得结果会比原有算法性能更优，但是考虑到云环境下任务的动态特点，所以这些算法没有较强的适应能力。基于现有算法的局限性，提出了一种基于任务类型匹配的资源调度策略(TTM)，在此调度策略下通过与用单一使用Max-Min或者Min-Min算法相比较，验证了此算法在任务动态环境下具有较好的效果。

2 云环境下负载调度模型

2.1 负载均衡任务调度模型

负载均衡是云计算的主要问题之一，负载可以是内存、CPU处理能力、网络或者是时延负载[8]。它需要在不同的节点之间共享工作负载，从而提高资源利用率和系统的性能。本文通过深入分析了Max-Min算法和Max-Min 算法的优缺点和所使用的场景，设计了一个新的调度策略，根据任务集中的任务长度分布情况来调用相应的算法，调度模型如图1所示。

图1 负载均衡调度模型

此调度过程为，首先用户提交任务，通过作业管理器管理用户提交的任务，计算任务所需要的性能要求和其他的一些因素限制，运用不同的负载均衡算法将任务分配给不同的虚拟机去执行，当然这里的虚拟机是在物理服务器中创建的，所以考虑的是物理服务器的负载。

2.2 任务类型匹配负载均衡算法设计

云计算环境下由于任务的大小不一，云计算数据中心各节点的处理能力也不同，所以负载的的定义很复杂[9]，为了简化起见，做了2点假设。

1)各任务之间是独立的，互相之间没有依赖关系；

2)虚拟机的处理能力只考虑他的执行速度(MIPS)，没有考虑带宽和内存等其他因素。为了描述模型的方便，先做一些相关定义。

定义1：任务执行时间(TET)。

任务执行时间是一个任务在某个资源节点上的处理时间，假设任务i的长度为lengthi，虚拟机j的执行速度为MIPSj，那么任务i在虚拟机j上的执行时间为

Tij=lengthi/MIPSj

(1)

定义2：任务预期完成时间(TCT)。

任务预期完成时间是任务在考虑分配给哪个虚拟机时要考虑的问题，看看任务在哪个虚拟机上能最快处理完成，即为准备时间，放在处理能力最强的虚拟机上完成时间不一定短，这个和执行时间不同。它等于开始执行的时间BETij加上Tij。

TCTij=BETij+Tij

(2)

定义3：平均资源利用率和时间跨度。

资源利用率表示为所有虚拟机在整个任务处理过程中的资源平均利用率

(3)

(4)

Makespan=max(TCTij)

(5)

定义4：集中任务预期完成时间标准差。

由于各个任务之间是独立的，所以标准差计算公式为

(6)

定义5：负载均衡度。

负载均衡度定义为各个虚拟机之间负载量的差别程度，用β表示

(7)

(8)

式中：m表示虚拟机的个数；S表示资源利用率的标准方差，当S越小是表明负载均衡度越高。

2.3 策略执行过程

对于到达的一批假设任务集为T{t1,t2,t3,…，tm},他们的长度分别为length1,length2，…，lengthn，首先将到达的任务集中的任务按照长度进行升序或者降序排列，为了讨论方便假设为降序，在排好序的任务中找到连续几个值大于SD的地方，通过此方法可以找到任务长度明显变化的地方，记为Po，所以对于任务集中的任务分布可能有如下3种情形：

1)情形1，即如果Po

2)情形2，即如果Po>S/2,那么说明短任务数小于长任务数，此时应用Min-Min算法效果比较好些。

3)情形3，即如果任务长度间的差值没有大于SD,说明任务之间的长度都差不多，此时选择Min-Min算法处理下个任务，算法流程图如图2所示。

3 实验仿真结果及分析

为了验证本算法的有效性，采用CloudSim 3.0软件进行仿真实验，这是一款由澳大利亚墨尔本大学开发的云计算仿真工具，主要考察两个指标：任务总执行时间(Makespan)和负载均衡度(Load Balancing Level)，实验表明提出的算法优于单一采用Max-Min算法和Min-Min算法。

针对上述3种情形进行仿真实验，仿真中将资源数定位取10，一批任务的数量为1 000，刚开始任务是长度随机排列的，任务到达由泊松随机过程建模。仿真结果如图3、图4所示。

通过图3中的3种情形得比较可以看出，提出的算法在3种情形下均具有较短的时间跨度，情形1中由于有许多的段任务，而长任务量很少，多虚拟机并发执行的时间短，所以用Max-Min 算法耗时比较长，而此时用Max-Min

图2 任务类型匹配负载均衡调度算法

图3 总执行时间

图4 负载均衡度β

算法效果比较好。情形2恰好相反，短任务很少，长任务多，此时应用 Max-Min 算法就没有什么优势。情形3中子任务之间的长度差别很小，所以用Max-Min 算法执行时间也较短。

同样以上3种仿真情形中使用TTM算法均具有较好的负载均衡效果，由于Max-Min算法的负载均衡效果本身要优于Min-Min算法，特别是当短任务很少、长任务多的情形。因此对于以上3种情形的负载均衡水平采用TTM算法会具有较好的性能。

4 结束语

本文主要针对云计算环境中的负载均衡问题进行了研究，在深入分析当前的两种经典的启发式负载均衡算法基础上，通过比较他们的优缺点，提出一种基于任务类型匹配的负载均衡算法，并通过CloudSim 云仿真环境验证了此算法的可行性，提出的算法不仅加快了系统响应时间而且有效地平衡了虚拟机之间的负载，提高了用户的服务质量。由于研究工作是在已有的负载均衡算法上做的调度策略创新，而不是在原有的算法上做的改进，而且对于任务调度有较多因素没有考虑，比如通信的开销、执行任务的花费等，所以这也会是下一步的研究工作。

[1] MAO Y，CHEN X，LI X. Max-min task scheduling algorithm for load balance in cloud computing[C]//Proc. International Conference on Computer Science and Information Technology.[S.l.]：Springer India，2014：457-465.

[2] KANAKALA R, REDDY V K. Performance analysis of load balancing techniques in cloud computing environment[J]. Telkomnika Indonesian Journal of Electrical Engineerin，2015，13(3)：568 - 573.

[3] 苏淑霞. 面向云计算的任务调度算法研究[J]. 安徽大学学报：自然科学版，2014，38(5)：24-30.

[4] SANTHOSH B. MANJAIAH D H.An improved task scheduling algorithm based on Max-Min for cloud computing[C]//Proc. International Conference on Advances in Computer & Communication Engineering. Bengaluru，India： IJIRCCE，2014：84-88.

[5] BHOI U, RAMANUJ P N. Enhanced Max-Min task scheduling algorithm in cloud computing[J]. International Journal of Application or Innovation in Engineering & Management (IJAIEM)，2013，2(4)： 259-264.

[6] ELZEKI O M，RESHAD M Z，ELSOUD M A. Improved Max-Min algorithm in cloud computing[J]. International Journal of Computer Applications，2012，50(12)：22-27.

[7] 郑莉.云计算环境下资源调度关键技术研究[D]. 北京：北京邮电大学，2014.

[8] KHERANI F, VANIA J. Load balancing in cloud computing[J]. International Journal of Engineering Development and Research(IJEDR)，2014，12(1)：907-912.

[9] 郭平，李涛，李琪. 一种云计算环境下的负载调度算法[J]. 系统工程理论实践，2014，34(S1)：269-275.

葛 兵(1991— )，硕士，主研云计算、负载均衡；

方义秋(1963— )，女，副教授，主要研究方向为云计算、软件工程等。

责任编辑：许 盈

Task Scheduling Strategy Based on Load Balancing in Cloud Computing Environment

GE Junwei,GE Bing ,FANG Yiqiu

(CollegeofCommunicationandInformationEngineering，ChongqingUniversityofPostsandTelecommunications，Chongqing400065，China)

According to the load imbalance problem of a large number of parallel computing nodes under the cloud computing environment, in this paper, a novel load balance scheme based on task type matching is proposed .This scheme focus on the judgement of task type among multiple different lengths of the subtasks, and an analysis is done on the advantages and disadvantages of two kinds of heuristic load balancing algorithms named Max-Min and Min-Min. Then, task scheduling with different algorithm is executed according to the type of the task set. The experimental results show that the proposed scheme has better load balancing features and shorter completion time than only using the algorithm of Max-Min or Min-Min

cloud computing; task scheduling; load balancing; Max-Min; Min-Min

重庆市教委科学技术研究项目(KJ130533)

TP391.1

A

10.16280/j.videoe.2015.19.011

葛君伟(1961— )，教授，博士，主要研究方向为云计算、 软件体系结构、电信管理网等；

2015-04-27

【本文献信息】葛君伟，葛兵，方义秋.云环境下一种基于负载均衡的任务调度策略[J].电视技术,2015，39(19).