基于动态资源预测的遗传算法网格任务调度方案研究 hadoop任务调度

　　[摘要]网格计算可以为应用服务提供强大的计算能力,而其中最为重要的就是任务调度机制,在改进过去的调度算法的基础上,提出基于动态资源的网格任务调度方案,实验证明该方案可以有效地加强网格的任务调度效率。
　　[关键词]动态资源遗传算法任务调度网格
　　中图分类号:TP3文献标识码:A文章编号:1671-7597(2009)1110086-01
　　
　　一、引言
　　
　　网格计算是在Internet上的一组新兴技术,利用共享网络提供强大的计算能力,任务调度系统是其重要的组成部分,它根据任务信息采用适当的策略把不同的任务分配到相应的资源节点上运行。由于网格系统的异构性和动态性,使得任务调度变得极其复杂。
　　在过去学者已经成功地把各个人工智能算法应用到网格任务调度系统中,如神经网络、蚁群算法、min-min算法等,并取得了巨大的成果,但由于系统通常不会处于以单一状态中以人们所期望的状态发展,从而导致了任务调度的复杂性,服务器由于工作任务的不确定导致在网格任务的运行过程当中,可能会因为其他原因导致网格任务执行的失败,同时也会导致服务器的运行错误。对于这种情况,过去的任务调度算法并没有考虑,所以本文结合支持向量机(SVM)与遗传算法对动态资源进行预测,从而达到自适应的目的。
　　支持向量机可以成功地处理回归问题和模式识别等问题。支持向量机将向量映射到一个更高维的空间里,在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。建立方向合适的分隔超平面使两个与之平行的超平面间的距离最大化。其中支持向量机的关键是核函数的选取,本论文为了得到精确的数据,选用径向基(RBF)核函数来进行。
　　在任务的分配方案中,本论文选择了遗传算法进行任务调度,遗传算法(Genetic Algorithm)是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群开始的,而一个种群则由经过基因编码的一定数目的个体组成。初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度大小选择个体,并借助于自然遗传学的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。在本论文中就是利用遗传算法的这一特性来对任务进行调度分配。
　　
　　二、基于性能预测机制的遗传算法任务调度总体框架
　　
　　在调度框架中,为了使调度算法可以先对重要任务或资源紧急的任务进行快速处理,所以引入了QoS机制,对每个任务进行QoS计算,对QoS进行排序,把QoS最高的任务首先输入调度系统,优先执行。
　　1.对初始任务的QoS进行排序,然后按顺序输入到任务调度系统的任务群中。
　　2.在得到排序后的任务群后,利用以往的网格节点状态数据进行SVM的分类预测,估计服务器的运行情况,以调整遗传算法的系统参数。
　　3.利用遗传算法对任务进行调度。
　　4.调度任务运行,并且记录实际结果,不断调度任务,直至任务队列为空。
　　
　　三、基于支持向量机的网格节点性能预测模型
　　
　　本文讨论的网格框架作为一个纯计算网格的框架,显然网格节点需要要比其他服务器拥有更快的速度、更大的内存,在通常条件下这些服务器都用在商业或科研环境下,而并非私人使用,所以服务器负载具有十分明显的周期性。
　　经过实验证明,该模型可以对网格节点负载进行有效预测。
　　
　　四、基于遗传算法的任务调度算法
　　
　　在网格计算中,任务调度的实质是将n个相互独立的任务分配到m个异构可用资源上,使得总任务的完成时间最小以及资源得到充分的利用。具体描述如下:
　　1.J是n个需要调度的任务集合,表示第个任务。
　　2.R是m个可用资源集合,表示第i个资源。
　　3.n个任务m个不同资源上的执行时间 是一个 的矩阵。
　　表示第i个任务在第j个资源上的执行时间。
　　4.把任务i所需要的数据从存储系统传输到资源j的传输时间为
　　 。
　　5.所有任务都执行完成的时间为时间跨度(),即
　　 由于网格任务调度的目标是时间跨度尽可能的短,因此适应度函数可以定义为:
　　
　　而染色体的编码则用二进制编码方式来完成,把一个任务调度矩阵转化为一个一维的二进制数列。
　　
　　五、网格调度实验
　　
　　在实验中,任务的CPU时间为0到100的随机数,内存为0到900的随机数。在代表程序运行之前,最大等待时间以70步长的时间随机递增,以提供一系列的任务。网格节点CPU最大时间为1000到3000的随机数,总体内存为4000到12000的随机数。
　　从上表可知,在10次的试验中,遗传算法整体上任务调度性能比min-min算法优越,其中遗传算法的运行时间均比min-min算法的运行时间少,而且在任务的丢弃方面,遗传算法的任务丢弃数量也比min-min算法的任务丢弃少。从而表明遗传算法比min-min算法有着更优秀的执行效率。
　　
　　六、结论
　　
　　本论文对基于动态资源预测的遗传算法进行研究,实验验证了该算法作为调度函数的网格任务调度模型性能更加优越,不仅缩短了任务的调度时间,也增加了任务调度可靠性,整体上优于基于min-min算法网格任务调度模型。
　　
　　参考文献:
　　[1]张颖峰、李毓麟,基于进化算法的网格计算资源管理调度系统[J].计算机工程,2003,29(15):110-111.
　　[2]Carretero J,Xhafa F.Use of Genetic Algorithms for Scheduling Jobs in Large Scale Grid Applications[J].ūKIO TECHNOLOGINIS IR EKONOMINIS VYSTYMAS.2006,12(1):11-17.
　　[3]Abraham A,Buyya R,Nath B.Nature"s heuristics for scheduling jobs on computational grids[C].2000.
　　[4]Yan H,Shen X Q,Li X,et al.An improved ant algorithm for job scheduling in grid computing[C].2005.
　　[5]Foster I,Kesselman C.The grid:blueprint for a new computing infrastructure[M].Morgan Kaufmann,2004.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文