一种基于贪心策略的启发式云计算任务调度算法

孙凌宇，冷明，朱平



一种基于贪心策略的启发式云计算任务调度算法

*孙凌宇，冷 明，朱 平

（井冈山大学流域生态与地理环境监测国家测绘地理信息局重点实验室，江西，吉安 343009）

提出了一种基于贪心策略的启发式任务调度算法，用于优化云计算环境下任务调度中执行时间。首先，给出了云计算环境下任务调度问题的形式化描述及其最早完成时间的启发式优先分配原则；接着，基于最早完成时间的优先分配原则，采用贪心策略难易交错地分配任务求得任务调度的初始解；进而，引入了任务对交换的收益值概念，采用贪心策略选择收益值大的任务对交换优化任务调度初始解的执行时间；最后，在CloudSim云计算仿真实验平台下进行了顺序调度算法、Min-Min算法、Max-Min算法和本文算法的对比实验，实验数据对比充分验证了本文算法既能减少任务执行时间，又能使资源负载相对平衡。

任务调度；云计算；贪心策略；启发式算法

0 引言

云计算作为并行计算、分布式计算、网格计算等传统技术和分布式数据存储技术、网络编程模型、虚拟化技术等新型技术融合发展的产物，是引领未来信息产业创新的关键战略性技术和手段，对我国发展高新技术产业、冲出国外企业的技术壁垒具有重要的战略意义。云计算的核心思想是利用分布在各地闲散异构的大规模廉价物理资源，整合形成巨大的虚拟资源池，再通过网络将用户提交的计算和存储任务调度到不同的虚拟机上，使得人们能够以极低的成本投入提升计算能力及存储容量，获得较高的服务质量[1]。

任务调度作为云计算平台的重要组成部分，是将用户提交的任务进行合理高效地分配和调度，其实质就是将个相互独立的任务分配到个闲散异构的物理资源上，使得总任务完成时间最小并且可用资源得到充分利用[2]。任务调度的效率直接影响到云计算平台的整体性能和服务质量。

任务调度问题作为一个NP完全问题，在m个任务调度的解空间寻找近似最优解，使得总任务的执行时间和负截均衡度最小[2]。目前，云计算的任务调度机制还未形成统一的标准和规范[3]，但由于该问题的重要性，国内外研究者提出了大量的云计算任务调度算法来计算任务调度的近似最优解，既有传统网格计算中的Min-Min[4]、Max-Min[5]、动态规划[6]等启发式调度算法，也有基于遗传算法[7]、粒子群算法[8]、蚁群算法[3]、免疫算法[9]、差分进化算法[10]和禁忌搜索算法[11]等智能调度算法。其中，传统启发式调度算法以最早完成时间为目标进行调度，有着较好的负载均衡性能，但总任务的实际执行时间并非最少[6]；智能调度算法在进行海量任务调度过程中，易陷入局部最优解，在收敛速度和负载均衡方面的效果有待提高[10]。

本文提出了一种基于贪心策略的启发式任务调度算法。该算法运用贪心策略求解和优化任务调度的初始解，既采用贪心策略难易交错地分配任务求得任务调度的初始解，又采用贪心策略选择收益值大的任务对交换优化任务调度初始解的执行时间。该算法在CloudSim云计算仿真实验平台下对顺序调度算法、Min-Min算法、Max-Min算法进行了对比实验，实验数据对比充分验证了本文算法既能减少任务执行时间，又能使资源负载相对平衡。

1 云计算任务调度问题的形式化描述及优先分配原则[11]

定义1：假设云计算环境下，用户提交作业分解成个任务的集合，且任务之间相互独立，其调度不需要考虑任务间的数据关联与优先约束关系，定义任务集合，其中为分解后的任务数量，为分解成的第个任务，且的总指令长度为。

定义2：假设云计算环境下，有个虚拟资源参与任务调度，且虚拟资源为云计算集群平台的虚拟机。定义虚拟机集合，其中为虚拟机数量，为第个虚拟机资源，且的指令执行速度(每秒执行指令条数)为。

定义3：假设分解后的任务数量不小于虚拟机资源数量()，每个任务只能分配给一个虚拟机执行，且一个虚拟机在某一时间段只能执行一个任务。定义个不同的任务调度到个不同的虚拟机上的预期执行时间是一个的矩阵，其中表示第个任务在第个虚拟机上执行的时间，且。

定义4：对于某任务分配方案，定义虚拟机的负载为分配给第个虚拟机所有任务的预期完成时间。

定义5：对于个不同任务调度到个不同虚拟机的任务调度问题是寻找分配方案，使得该分配方案中虚拟机的任务最迟完成时间最早

由文献[11]可得云计算任务调度的最早完成时间的优先分配原则：第个任务将分配给具有最早完成时间的虚拟机。

2 基于贪心策略的启发式云计算任务调度算法

2.1 传统的启发式云计算任务调度算法

传统的顺序调度策略的启发式云计算任务调度算法把一组任务顺序分配给一组虚拟机，尽量保证每个虚拟机运行相同数量的任务以平衡负载，但没有考虑任务的需求和虚拟机之间的差别[1]。

传统的Min-Min启发式云计算任务调度算法采用先易后难的策略，先执行完成时间短的任务，然后执行完成时间长的任务，并采取贪心策略把每个任务优先指派给执行它最早完成的计算资源。

传统的Max-Min启发式云计算任务调度算法则恰恰相反，采用先难后易和贪心策略，每次选取完成时间最长的任务，再执行完成时间短的任务，并采取贪心策略把每个任务优先指派给执行它最早完成的计算资源。

2.2 基于贪心策略的启发式云计算任务调度算法

定义6：对于某任务分配方案，假设为负载最大的虚拟机，为负载最小的虚拟机，即且；假设第个任务t被分配在虚拟机vm上执行，第个任务被分配在虚拟机vm上执行，即且。当任务t和任务进行交换，即任务t被交换至虚拟机vm上执行且任务被交换至虚拟机vm上执行，虚拟机vm交换前后的执行时间差称为该交换的收益值。

在文献[11]的基于最早完成时间的优先分配原则和定义6给出的收益值的基础上，本文提出了一种基于贪心策略的启发式云计算任务调度算法。该算法分为求解初始解和优化初始解两部分，其中求解初始解部分基于最早完成时间的优先分配原则，采用贪心策略难易交错地分配任务求得任务调度的初始解；优化初始解部分采用贪心策略，选择收益值大的任务对进行交换，从而优化任务调度初始解。该算法的基本步骤如下：

步骤1 计算预期执行时间矩阵：计算任务集合中个任务在虚拟机集合的个虚拟机上的预期执行时间，得到预期执行时间矩阵；

步骤2 初始化负载数组：初始化m个虚拟机的当前负载数组[1..]为零；

步骤3 求解初始解：从没有分配任何虚拟机的任务集合开始，交叉访问最大任务和最小任务t，执行下述步骤3.1、3.2和3.3，分配任务t到相应的虚拟机上；

步骤3.1 依据个虚拟机的当前负载数组和预期执行时间矩阵，计算出任务t分配至各个虚拟机相应的时间跨度；

步骤3.2 基于最早完成时间的启发式优先分配策略，找出时间跨度最小的虚拟机vm；

步骤3.3 分配任务t至虚拟机vm，更新vm虚拟机负载[]为[]+c；

步骤4 优化初始解：初始化循环计数器COUNT为0，执行下述步骤4.1、4.2、4.3、4.4和4.5 ，选择收益值大的任务对进行交换，直至循环计数器COUNT达到设定阈值；

步骤4.1 循环遍历每个任务：初始化个任务的禁忌数组[1..]为零，即允许所有的任务被交换；遍历每个任务，读取当前任务t的禁忌状态；如果当前任务t的禁忌标志为1，则表明其不允许被交换，跳过步骤4.2、4.3、4.4和4.5，继续循环执行步骤4.1；否则表明任务t允许被交换，修改任务t的禁忌标志[]=1，执行步骤4.2。

步骤4.2 产生被交换的候选任务对：读取当前任务t的状态，判断所分配虚拟机的负载vm是否大于平均负载；如果大于平均负载，则在个虚拟机的负载数组中，查找出负载最小的虚拟机vm；否则查找出负载最大的虚拟机vm；依据定义6计算出所有允许被交换的任务与当前任务交换之后的收益值。

步骤4.3 产生被交换的任务对：采用贪心原则选择交换收益值最大的候选对(t,t)，交换任务对(t,c)；

步骤4.4 交换任务对：交换任务对(t,t)，即任务t被交换至虚拟机vm上执行且任务t被交换至虚拟机vm上执行；修改任务t的禁忌标志[]=1；

步骤4.5 更新虚拟机负载：更新vm虚拟机负载[m]=[m]+ t-t；更新vm虚拟机负载[n]=[n]+ t-t；

2.3 时间复杂度分析

设任务调度的任务数为，虚拟机数为，且通常情况下任务调度测试基准满足>。本文任务调度优化算法的时间复杂度主要包括以下两部分。

(1) 任务调度初始解求解部分：步骤1，遍历每个任务，求解每个任务在个虚拟机上预期执行时间的值，时间复杂度为Ο(*)；步骤2，初始化大小为的虚拟机负载数组，时间复杂度为Ο() ；步骤3，遍历每个任务，基于最早完成时间的启发式优先分配原则，将该任务分配给时间跨度最小的虚拟机，时间复杂度为Ο(*)。因此，任务调度初始解求解部分的时间复杂度为Ο(*)。

(2) 任务调度初始解优化部分：步骤4.1，个任务禁忌状态的初始化，时间复杂度为Ο()；步骤4.3，基于贪心策略选择收益值大的任务对进行交换，其交换次数不大于，时间复杂度为Ο(2)。因此，任务调度初始解优化部分的时间复杂度为Ο(2)。

由于通常情况下>，因此本文算法的总时间复杂度为Ο(2)。

3 仿真对比实验与结果分析

3.1 对比实验模型

本文选用墨尔本大学网格实验室的Cloudsim云计算仿真平台[12]，具体的仿真对比实验步骤如下。

步骤1 初始化CloudSim包。对CloudSim的用户数量、日期和跟踪标志等参数进行初始化；

步骤2 创建数据中心。创建主机列表且设置每个主机的ID、内存等配置参数，创建PE列表且设置每个PE的ID、MIPS等配置参数，创建数据中心对象等；

步骤3 创建数据中心代理。通过对DataCenterBroker代理类扩展，在其内部分别实现顺序调度算法、Min-Min算法、Max-Min算法和基于贪心策略的启发式云计算任务调度算法(简称本文算法)；

步骤4 创建虚拟机。对虚拟机的ID、MIPS、CPU数量等参数进行设置并提交任务代理；

步骤5 创建云任务。创建指定参数的云任务，设定任务的用户ID并提交任务代理；

步骤6 调用任务调度算法。借助自定义的任务调度策略，分配任务并绑定到虚拟机；

步骤7 启动仿真；

步骤8 收集仿真实验数据。

对比实验中的参数设置如下：为了保证实验结果的可重复性和公正性，固定选用的随机数种子为1000；实验中设定虚拟机数量为5，虚拟机指令执行速度在[100,300] MIPS随机产生；五个对比实验分别设定任务数量为500、1000、1500、2000和2500，且每个任务指令长度在[1000,5000] MI随机产生。通过分析仿真实验数据并对比各算法的性能，验证本文算法在任务执行时间减少、资源负载相对均衡等方面的优点。

3.2 仿真对比实验的结果与分析

表1 不同数量任务下算法的最迟完成时间对比表

表1为不同数量任务下算法的最迟完成时间对比表，表明顺序调度算法作为Cloudsim中内嵌的一种简单的轮询调度，思路简单，因此所耗费时间远长于其它算法；本文算法与Max-Min算法、Min-Min算法相比，所需完成时间最短并接近于任务最优完成时间。

图1 不同数量任务下算法的完成时间可改进百分比对比图

定义7：对于个不同任务到个不同虚拟机的某分配方案，各虚拟机的任务最迟完成时间(最长处理时间)为，定义该分配方案的完成时间可改进百分比为与定义7的总任务最优完成时间百分比差，即。

图1曲线对比表明，本文算法的任务完成时间最接近于任务最优完成时间，其完成时间可改进百分比小于Min-Min算法、Max-Min算法和Tabu智能算法。

图2至图5为不同数量任务下各算法的资源负载平衡图，其中number代表一次调度的任务数量，分别为500、1000、1500、2000和2500，资源编号为5个虚拟机的编号。图2至图5对比表明，图3的Cloudsim顺序调度算法通过轮询调度分配任务，忽略了计算资源的负载均衡，因此其资源负载平衡能力最差；图4的Max-Min算法的资源负载平衡能力好于图3的Min-Min算法；图5的基于贪心策略的启发式云计算任务调度算法的资源负载平衡能力略好于图4的Max-Min算法和图3的Min-Min算法。

图2 不同数量任务下顺序调度算法资源负载平衡图

图3 不同数量任务下Min-Min算法资源负载平衡图

图4 不同数量任务下Max-Min算法资源负载平衡图

图5 不同数量任务下本文算法资源负载平衡图

定义8：对于个不同任务到个不同虚拟机的某分配方案，定义该分配方案的资源负载平衡因子为不同虚拟机任务完成时间的方差值，即

表2为不同数量任务的算法资源负载平衡因子对比表，表明Cloudsim中顺序调度算法的资源负载平衡能力最差，本文算法的资源负载平衡能力最好，与图1至图5的负载平衡对比结论一致。

表2 不同数量任务的算法资源负载平衡因子对比表

4 结束语

云计算环境下任务调度问题是在mn个可能任务调度的解空间寻找近似最优解，使得总任务的执行时间最短。首先，本文阐述了当前国内外主流的云计算任务调度算法，其中有传统的Min-Min、Max-Min等启发式调度算法。接着，本文在云计算任务调度问题形式化描述的基础上，阐述了最早完成时间的启发式优先分配原则，进而提出了一种基于贪心策略的启发式任务调度算法。该算法基于最早完成时间的优先分配原则，采用贪心策略难易交错地分配任务求得任务调度的初始解；引入任务对交换的收益值概念，采用贪心策略选择收益值大的任务对进行交换，从而优化任务调度初始解的执行时间。本文还进行了顺序调度算法、Min-Min算法、Max-Min算法和本文算法的对比实验。实验数据对比充分验证了本文算法既能减少任务执行时间，又能使资源负载相对平衡。

参考文献：

[1] 白延敏,薛进,马维华. 云环境下弹性负载均衡方法的研究[J]. 小型微型计算机系统, 2014, 35(4): 814-816.

[2] 叶枫,王志坚,徐新坤,等. 一种基于QoS的云负载均衡机制的研究[J]. 小型微型计算机系统, 2012, 33(10): 2147-2152.

[3] 查英华,杨静丽. 改进蚁群算法在云计算任务调度中的应用[J]. 计算机工程与设计, 2013, 34(5): 1716-1816.

[4] 史少锋,刘宴兵. 基于动态规划的云计算任务调度研究[J]. 重庆邮电大学学报:自然科学版, 2012, 24(6): 687-692.

[5] 李建锋,彭舰. 云计算环境下基于改进遗传算法的任务调度算法[J]. 计算机应用, 2011, 31(1): 184-187.

[6] 封良良,张陶,贾振红,等. 云计算环境下基于改进粒子群的任务调度算法[J]. 计算机工程, 2013, 39(5): 183-188.

[7] 叶菁,陈国龙,阮一文. 异构环境下相关任务调度免疫遗传算法的研究[J].小型微型计算机系统,2011,32(10): 2124-2129.

[8] 董丽丽, 黄贲, 介军. 云计算中基于差分进化算法的任务调度研究[J]. 计算机工程与应用, 2014, 50(5): 90-95.

[9] 孙凌宇,冷明,朱平,等. 云计算环境下基于禁忌搜索的负载均衡任务调度优化算法[J]. 小型微型计算机系统, 2015, 36 (8): 2409-2414.

[10] Reuters T. CloudSim: a framework for modeling and simulation of cloud computing infrastructures and services introduction[EB/OL]. http://www.buyya.com/ gridbus/ cloudsim/.

RESEARCH ON THE HEURISTIC TASK SCHEDULING ALGORITHM BASED ON GREEDY STRATEGY IN CLOUD COMPUTING

*SUN Ling-yu，LENG Ming，ZHU Ping

（Key Laboratory of Watershed Ecology and Geographical Environment Monitoring of NASG, Jinggangshan University, Ji’an,Jiangxi 343009, China）

We propose the heuristic task scheduling algorithm based on greedy strategy in cloud computing to optimize the finish time of whole tasks. Firstly, the formal description of task scheduling problem in cloud computing is presented. We also present the heuristic principle of the earliest finish time (EFT) for task scheduling. Furthermore, the initial solution steps of task scheduling based on the EFT principle and the greedy strategy are given. Then, we propose the gain of task swap and adopt the greedy strategy to swap tasks to improve the task completing time of the initial solution. Finally, we carry out the comparative experiments among the sequential scheduling algorithm, Min-Min algorithm, Max-Min algorithm and the proposed algorithm based on CloudSim simulation platform of cloud computing. The experiment and analysis show the proposed algorithm has better performance in terms of the decreasing the task completing time and the improvement of resource load balancing.

task scheduling; cloud computing; greedy strategy; heuristic algorithm

1674-8085(2015)06-0056-06

TP391

A

10.3969/j.issn.1674-8085.2015.06.012

2015-08-03；修改日期：2015-10-23

国家自然科学基金项目(61363014,61163062）；江西省青年科学家培养对象计划(20153BCB23003)；江西省科技支撑计划项目(20132BBE50048)；江西省自然科学基金项目(20132BAB201035）；流域生态与地理环境监测国家测绘地理信息局重点实验室招标课题(WE2015012)

*孙凌宇(1976-)，女，江西永丰人，教授，硕士，主要从事云计算、任务调度化等研究(E-mail:lzylmsly@gmail.com);

冷 明(1975-)，男，江西高安人，副教授，博士，主要从事算法分析与设计、组合分析与优化等研究(E-mail:lengming@jgsu.edu.cn);

朱 平(1955-)，男，上海人，教授，硕士，主要从事算法分析与设计研究(E-mail:zhuping@jgsu.edu.cn).