基于负载均值的云调度算法研究

邓先瑞，李春艳，齐 伟

（1. 唐山师范学院 计算机科学系，河北 唐山 063000；2. 唐山市先进仿真技术重点实验室，河北 唐山 063000；3. 北京交通大学 计算机与信息技术学院，北京 100044）

基于负载均值的云调度算法研究

邓先瑞1,2，李春艳1,3，齐 伟3

（1. 唐山师范学院 计算机科学系，河北 唐山 063000；2. 唐山市先进仿真技术重点实验室，河北 唐山 063000；3. 北京交通大学 计算机与信息技术学院，北京 100044）

在云计算环境中，由于调度算法的局限性而易造成某些节点负载过重，进而导致整个云计算平台负载不均衡和资源利用效率低下。针对此问题，在经典的Min-Min调度算法的基础上，提出了一种基于负载均值思想的任务调度算法。采用云计算模拟器CloudSim对算法进行仿真。仿真结果表明，改进的算法在实现了物理机和虚拟机层的负载均衡的同时，有效地提高了资源利用率。

Min-Min；负载均值；CloudSim；云计算

1 引言

云计算是网格计算的发展，在一定程度上，云计算的任务调度与网格计算具有相似性和可借鉴性，网格计算的任务调度和资源分配已得到广泛研究。云计算不同于网格计算，它所采用的商业理念、形式、成熟的虚拟化技术以及非标准化的规范，使得云计算环境下的任务调度呈现不同的特点[1]。

任务调度是一个NP完全问题。目前关于这个问题，国内外已经作了很多研究工作，出现了很多经典的任务调度算法。比如Hadoop默认FIFO[2]调度算法来进行任务调度，其有较好的调度效率，但不能保证小任务的及时执行。FaceBook针对此缺点开发了能够保证小任务得到迅速响应，大任务保证服务水平的公平调度算法[3]。Yahoo提出了计算能力调度算法即Capacity调度器[8]。Baomin Xu等基于伯格模型提出了公平调度算法。在任务与资源进行匹配时，以QoS参数的匹配作为依据，依据资源分配的公平性原则将最佳匹配的资源分配给任务[4]。

云环境下任务调度的本质是在任务和资源之间建立起一个映射，然后按照给定的映射关系将任务调度到合适的计算资源上执行。因此，云环境下任务调度的策略就是如何在任务和资源之间找到一个合适的映射关系，使得云环境下的任务调度在实现用户任务基本需求的基础上达到各个性能指标的优化。其中，考察云环境下的任务调度算法的主要指标之一就是负载均衡。即如果某些节点的负载超过其能够承受的负载阈值，平台的整体性能将受很大影响，并且会造成计算资源分配不均，导致资源的浪费。任务调度应该尽量将任务调度到负载较轻的节点运行以维持系统的负载均衡。由于云系统中的计算机数量非常庞大，组成复杂。使得目前云计算中负载均衡和最优跨度的实现成为具有挑战性的问题[5]。

本文在对经典的Min-Min算法[6]进行分析的基础上，针对云计算系统中可能因负载不均衡而造成的系统效率低下的问题，提出了一个改进的任务调度算法。该算法充分考虑任务分配过程中QoS[7]因素的影响，以节点的负载均值为标准，赋予任务不同的优先级，从优先级最高的(即对主机QoS要求最高)任务开始分配，从而获得较小的最优跨度（makespan）。

2 背景知识

2.1 任务调度问题

任务调度问题的实质就是在一个由m个需要调度的任务，n个可用的任务执行单元（集群中的节点）构成的分布运行环境下，把m个任务T={t1, t2, …, tm}以合理的方式调度到n个主机H={h1,h2,…, hn}上去，设法获得尽可能小的总执行时间。

假设每个任务在任意一台机器上的静态运行时间是预知的，任务的期望运行时间（Expected Time to Compute）可以由ETC矩阵来描述。m个任务在n个不同机器上的预测执行时间ETC是一个m×n的矩阵。矩阵的每一行代表某一个任务在n台机器上的不同执行时间，每一列代表在同一台机器上，m个不同任务的不同执行时间。

当一个任务ti被分配到一个机器时，其期望完成时间MCT(i,j)可定义为机器hj的期望就绪时间与任务ti在机器hj的期望执行时间之和，即

其中TASKSTART(j)为机器j的期望就绪时间。

2.2 经典Min-Min算法

Min-Min算法[8,9]是目前分布环境下比较经典的任务调度算法之一，该算法的主要思想如下：当需要调度的任务集合非空时，反复执行如下操作直至集合为空：

（1）对集合T中每一个等待分配的任务ti，分别计算把该任务ti分配到n台机器上的最小完成时间MinTime(i)，可得到一个含有m个元素的一维数组MinTime；

（2）设MinTime中最小的元素为MinTime(k)，其中任务k对应的主机为h，则把任务k分配到机器h上；从任务集合中删除任务k，同时更新MCT矩阵。

理论上已经证明，在一般情况下，Min-Min算法能够获得较小的makespan，效率较高，但是这种方法存在着一个很大的缺点，即算法的负载平衡性能不高。其主要原因是Min-Min算法并没有考虑调度过程中涉及到的QoS的因素。不同计算资源能够提供不同的QoS，不同任务对于资源QoS的要求也不尽相同。忽视QoS因素的就会出现这样的情况，即对QoS要求比较低的任务占用了高QoS的资源，而对QoS要求较高的任务只有等待高QoS的资源空闲后才能够得到执行。这显然大大降低了效率及资源的利用率。

3 改进的Min-Min算法

3.1 预备知识

为了便于后面对算法进行描述，这里先介绍几个基本概念。

（1）离散型随机变量Si，其中i=1,2…m，它的取值为任务ti在各个计算节点上的期望执行时间，共有n个，分别为ETC(i,1)，ETC(i,2)…ETC(i,n)，同时任务ti分配到任何一个计算节点上的概率是相同的，为1/n。

（2）随机变量Si的数学期望ESi，其中i=1,2…m，它表示任务ti在n个计算节点上的期望执行时间的均值。故

（3）负载均值ES。每个任务ti在n个计算节点上期望执行时间的均值ESi可以理解为该任务给可用的计算节点提供执行时间为ESi的负载。最理想的情况，就是m个任务分配到n个计算节点上，实现了完全的负载平衡，定义ES为ESi（i=1，2，3…m）的平均值：

（4）集合T1。在改进的Min-Min算法中，所有的任务都要根据其对资源QoS的要求赋予优先级。以负载均值ES为标准，具体对某一任务来说，可能其在某些计算节点上的执行时间会超过ES。T1集合内的任务满足的条件是：其中一个任务在各个计算节点上的期待完成时间中超过负载均值的个数最多，也可以理解为该集合中的任务对资源QoS的要求最高。

3.2 算法描述

改进的Min-Min算法可分为两个阶段：第一阶段计算每个任务ti在各计算节点上的最小完成时间，得到一维数组MinTime，同时记录任务ti无效计算节点个数NUMi（无效计算节点是指任务在这些计算节点上的期望完成时间超过负载均值ES），得到集合T1；第二阶段，在任务集合T1上使用Min-Min算法分配一个任务。分配过的任务将从T中移走，然后清空任务集合T1。

算法的具体执行步骤为：

1. 根据ETC矩阵计算每个任务在n个虚拟机上执行时间的均值ESi和负载均值ES；

2. 将每台虚拟机的期望就绪时间TASKSTART(j)初始化为0，若T不为空，采用循环重复以下操作：

（1）初始化任务组T1为空；

（2）对于每个任务ti，计算它在每个虚拟机hj上的期待完成时间MCT(i,j)，将该任务的最小完成时间赋给一维数MinTime(i)；

（3）在步骤2的同时，比较ES和任务ti在各个虚拟机上期待完成时间MCT(i,j)的大小关系，根据任务ti的无效虚拟机的数目，将满足要求的任务添加到任务组T1；

（4）对任务组T1，利用传统Min-Min算法来分配一个任务，分配成功后修改相应的MCT矩阵。若T不为空回到步骤1。

4 实验与结果分析

4.1 实验环境

在这里使用云模拟器CloudSim[10,11]对实验算法进行仿真研究。CloudSim是2009年4月澳大利亚墨尔本大学的网格实验室和Gridbus项目宣布推出的云计算仿真软件。其首要目标是在云基础设施上对不同应用和服务模型的调度和分配策略的性能进行量化和比较，从而达到控制云计算资源使用的目的。在使用CloudSim时，研究者和开发者只需要关注特定系统的抽象层的算法、策略和协议的开发，无须关注与云基础设施和服务等底层相关的实现细节。

进行模拟实验时，CloudSim中采用5个不同的虚拟机，各个虚拟机的具体配置如表1所示。

表1 Cloudlet的资源配置

4.2 实验结果

实验中假定有10台机器，任务的预测执行时间矩阵ETC给定，我们根据任务数的不同分别作三组实验，每组的任务数分别为20、40、50个。在每一组实验中，我们随机使用4组ETC用例来查看实验结果，三组实验结果分别如表2、表3和表4所示。

表2 第一组实验结果（任务数为20个）

表3 第二组实验结果（任务数为40个）

表4 第三组实验结果（任务数为50个）

三组实验结果表明，在任务调度过程中，本文提出的改进算法得到的makespan同传统Min-Min算法取得的makespan相比明显减少，可以提高系统的有效性。

5 结束语

本文在经典的Min-Min调度算法的基础上，引入QoS因素，提出了一种基于负载均值思想的改进策略，并且在CloudSim中对改进的算法进行了仿真验证。仿真结果表明，改进算法达到了既能够在云计算环境下安全高效地执行任务，又能够实现系统中负载基本均衡的目标。

[1] 刘美林.云计算中基于博弈论的任务调度算法研究[D].北京:北京工业大学,2014:18-19.

[2] Kamal Kc, Kemafor Anyanwu. Scheduling hadoop jobs to meet deadlines[C]. Indianapolis, Indiana, USA: IEEE Second International Conference on Cloud Computing Technology and Science (CloudCom), 2010: 388-392.

[3] http://hadoop.apache.org/docs/r1.2.1/fair_scheduler.html.

[4] Randles, Martin, David Lamb, A Taleb-Bendiab. A com-parative study into distributed load balancing algorithms for cloud computing[C]. 24th IEEE International Conference on Advanced Information Networking and Applications Workshops (WAINA), Perth, Australia, 2010: 551-556.

[5] Baomin Xu, Chunyan Zhao, Enzhao Hu, et al. Job scheduling algorithm based on Berger model in cloud environment[J]. Advances in Engineering Software, 2011, 42(7): 419-425.

[6] Xiaoshan He, Xianhe Sun, Gregor Von Laszewski. QoS guided min-min heuristic for grid task scheduling[J]. Journal of Computer Science and Technology, 2003, 18(4): 442-451. [7] B. Sabata, S. Chatterjee, M. Davis, et al. Taxonomy for QoS specifications[C]. Newport Beach, CA: Workshop on Object-Oriented Real-Time Dependable Systems, 1997: 100-107.

[8] X Ma, Y Wang, and X Pei. A Scalable and Reliable Matching Service for Content-Based Publish/Subscribe Systems[J]. IEEE Transactions on Cloud Computing, 2014, 3(1):1-13.

[9] L Heilig, S Voss. A Scientometric Analysis of Cloud Computing Literature[J]. IEEE Transactions on Cloud Computing, 2014, 2(3):266-278.

[10] Rodrigo N. Calheiros, Rajiv Ranjan, Anton Beloglazov, 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.

[11] 邓见光.云计算任务调度策略研究[D].广州:华南理工大学, 2014:22-25.

（责任编辑、校对：赵光峰）

中国学术期刊影响因子年报（人文社会科学•2014版）

编号：CST-JIFR 2014 TSSF

期刊名称：唐山师范学院学报

主办单位：唐山师范学院

学科类目：综合性人文、社会科学 研究层次：理论研究

CN/ISSN：CN 13-1301/G ISSN 1009-9115

影响因子种类 即年指标 影响因子 他引影响因子5年影响因子 他引5年影响因子 影响因子学科排序复合JIF 0.033 0.223 0.209 0.264 0.257 395/631期刊综合JIF 0.029 0.082 0.068 0.077 0.070 466/631人文社科JIF 0.022 0.071 0.057 0.057 0.050 446/631

来源：中国学术期刊（光盘版）杂志社

中国科学文献计量评价研究中心

2014-12-05

The Research on Cloud Scheduling Algorithm Based on Load Average

DENG Xian-Rui1,2, LI Chun-Yan1,3, QI Wei3

(1. Department of Computer Science, Tangshan Normal University, Tangshan 063000, China; 2. Tangshan Advanced Simulation Technology Key Laboratory, Tangshan 063000, China; 3. School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China)

A task scheduling algorithm based on load average is presented in this paper, which is developed from the classical Min-Min task scheduling algorithm. The proposed algorithm is used for Cloud Computing, in which the loads of some nodes get too heavy that the load of the whole Cloud Computing platform becomes imbalanced and the utilization of resources becomes low because of the limitation of scheduling algorithms. The simulation of the proposed algorithm was done by using Cloud Computing Simulator (CloudSim). The result shows the improved algorithm can achieve load balancing between physical machines and virtual machines and it can promote the utilization of resources.

Min-Min; load average; CloudSim; Cloud Computing

TP393.09

A

1009-9115(2015)02-0038-04

10.3969/j.issn.1009-9115.2015.02.012

河北省科技计划项目（13220319D），唐山师范学院博士基金项目（07A01）

2014-08-31

邓先瑞（1973-），女，四川成都人，博士，副教授，研究方向为计算机算法。

计算机科学与技术