• 学业杂志社官网
当前位置: 主页 > 收录文章 > >详细介绍
资讯信息

一种用于云计算任务调度的策略

时间:2020-06-09 来源:《学业》杂志 作者:admin 点击:

  摘要:云计算环境下,任务的高效调度是云计算平台要解决的关键问题之一。目前,针对任务调度算法的研究中,通常只针对某一个评判任务调度算法好坏的因素进行研究,经常会出现改进后的算法以较高的任务完成成本作为代价换取较短的任务完成时间。因此提出了一种考虑任务完成时间和成本约束的遗传算法,此算法的调度结果可以取得较短的任务完成时间,同时成本也较小。实验结果表明,该算法能够有效平衡任务完成时间和成本。

  关键词:任务调度;云计算;时间;成本

  0 引言

  云计算任务调度的目标就是按照某种调度策略,达到运行时间最短,成本最低,同时充分利用系统资源。如何把众多Map-Reduce任务进行调度是一个NP完全问题。启发式算法是解决此问题的最佳选择,其中遗传算法是具有良好收敛性的优化算法。

  1 云计算的任务调度模型

  对于内部的大规模计算,云计算一般采用数据分割的计算方式,将较大的任务分割成许多子任务,然后分配给若干个虚拟资源节点并行执行,最后返回运行结果。为了使云计算系统高效快速的完成任务,将各个子任务按照一定的调度策略分配给虚拟资源进行处理,这就是云计算的任务调度。

  任务调度最主要的目标之一就是缩短任务的完成时间,为了解决这个问题,文献[1]提出了一种基于总任务完成时间和任务的平均完成时间的双适应度的遗传算法,此算法不但能找到总任务完成时间较短的调度结果, 而且此调度结果的任务平均完成时间也较短。而文献[2]则提出了一种基于模板遗传算法的任务调度方法,此方法能得到总任务完成时间较短的调度结果。这两种算法都很好的解决了任务的完成时间,可是对于用户而言,任务的完成成本也同样的重要,所以本文提出了一种基于时间和成本的遗传算法的任务调度方法。

  2 基于遗传算法的任务调度

  2.1染色体编码与解码

  染色体编码有很多种方式,可以采用直接编码,也可以采用间接编码,本文采用简单直观的资源-任务间接编码方式。在这种编码方式中,染色体的长度为子任务的数量,染色体中每个基因的取值为该位置对应的子任务分配到资源上的资源编号。

  通过解码后的序列和ETC矩阵就可以计算出每个资源执行完该资源上的所有子任务所需要的时间,由于云计算任务调度的并发性,各个资源上执行任务的最长时间就是完成所有任务的总时间:

  (1)

  (2)

  2.2初始群体生成

  取种群规模为S,资源数为R,子任务数为N,则初始化描述为由系统随机产生S条染色体,染色体长度为N,基因取值为[1,R]之间的随机数。

  2.3适应度函数

  适应度函数的选取对遗传算法至关重要,直接影响到遗传算法的收敛速度与最优解的查找。总任务的完成时间是云计算任务调度的一个重要目标,所以定义时间适应度函数为:

  (3)

  对于用户来说,完成所有任务的成本也是一个重要的因素,因此定义成本适应度函数为:

  (4)

  (5)

  本文既考虑了任务的执行时间,也考虑了任务执行的成本,所以定义的适应度函数为:

  (6)

  其中,α∈[0,1] ,β∈[0,1],α+β=1,取α=0,β=1时,算法调度的结果为完成所有子任务成本最小的调度;取α=1,β=0时,算法调度的结果为完成所有子任务时间最小的调度。

  2.4遗传操作

  2.4.1 选择操作

  选择操作是为了在种群中选择适应度高的个体,即优良个体,优良个体的基因会遗传到下一代,使得群体中的个体的适应度值不断接近最优解。本算法采用轮盘赌选择作为选择操作算子,根据适应度计算公式(6),则个体i被选择的概率为:

  (7)

  2.4.2 交叉与变异操作

  交叉操作是遗传算法中最主要的搜索算子,它决定了遗传算法的全局搜索能力,将原有的优良基因遗传给下一代,并生产包含更优良基因结构的新个体。变异操作可以拓展新的搜索空间,在种群局部收敛时,变异可以保持种群的多样性,避免出现早熟现象。本算法采用随机交换基因对的方法,若个体P1和P2进行交叉,随机选取某一基因座之后的位置作为交叉点,将P1和P2上的等位基因进行对换,产生新的个体。

  3 算法仿真结果与分析

  本文采用Cloudsim模拟云计算环境,在相同的环境条件下,将本文算法与TGA、CGA进行对比。

  算法的初始条件:种群规模S=50,资源数量R=5, 根据资源i的MIPS的大小来决定,资源的处理能力越大,费用也就越高。

  算法的终止条件:考虑到遗传算法对任务调度自身的运行开销,达到一定的进化代数,算法终止。从最后一代的个体中选取适应度值最大的染色体,作为最佳调度方案。

  TGA的调度结果可以取得最短的总任务完成时间,而对任务完成成本的优化作用不明显;CGA的调度结果可以取得最小的总任务完成成本,而对任务完成时间的优化作用不明显;本文算法同时对任务完成时间和成本进行优化,故得到的调度结果能够较好的平衡任务的完成时间和成本。

  4 结语

  任务调度一般以任务的完成时间作为标准来衡量调度方案的质量,本文加入了任务的完成成本约束,该算法基于时间和成本的适应度函数。实验结果表明,该算法在云计算环境实现了较为理想的任务调度。

  在未来的工作中,可以考虑任务调度的负载均衡,而且可以加入任务的优先级,产生更为理想的任务调度。

  参考文献

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

  [2] 盛小东, 李强, 刘昭昭. 云环境下基于模板遗传算法的任务调度方法[J]. 计算机应用, 2016, 36(3):633-636.

《学业》杂志是由学业出版社主办、神州杂志社协办、学业杂志社编辑出版 ISSN刊号:2305-7599   国内刊号:CN 11-4461/I   邮发代号:2-871
学业杂志社版权所有@未经本刊授权,不得转载本站资料