论文研究-基于优先级的在线模式Min-Min任务调度算法 .pdf

所需积分/C币:36 2019-08-18 03:22:35 209KB .PDF
65
收藏 收藏
举报

基于优先级的在线模式Min-Min任务调度算法,范国昌,李旭,本文对网格计算中最经典的Min-Min任务调度算法进行了深入的研究与分析,指出了该算法在时间复杂度、负载均衡等方面所存在的不足,��
山国利技论文在线 http:/www.paperedu.cn 3.基于优先级的在线模式Min-Min算法 3.1算法思想 为了解决传统Min-Min所存在的诸多不足,对Min-Min算法作出如下的改进: (1)采用在线模式进行任务映射,在线模式算法是指一旦有仁务到达,任务调度器立 即进行映射 (2)建立一个任务队列,当有多个任务同时到达时把这些任务加入到任务队列中 (3)对每个仟务根据其紧急状况赋予一个初始的优先级,高优先级的仟务可以被优先 进行映射。 (4)每个任务的优先级可随等待的时间动态的变化,任务在任务队列中等待的时间越 长,它的优先级越高,就越有可能被映射 (5)对于参与调度的机器集合R中的任意一个机器r,限定其就绪时间为h1=0,此 时 ,即只靠虑当前空闲可用的杌器节点参与调度 (6)当有多个任务需要调度时,优先调度优先纵最高的任务;当优先级最高的任务不 唯一时,优先调度完成时间e最早的仟务。 改进后的算法描述如下: (1)当一个新任务t到达时,根据其重要性赋给一个初始的优先级P (2)如果任务队列为空,则立即对新到达的仟务t进行资源映射,映射机器为使仟务1 期望完成时间c最小的机器。其中r的就绪时间h,=0,即〃当前可用,本次映射结束 后从当前可用机器列表中删除机器r,直至t在它上面执行完毕,再重新把r;加入到可用机 器列表中供其它任务进行映射。 (3)如果任务队列不为空但是队列中所有任务的优先级都低于新到达任务的优先级 P1’则立即对任务t进行映射,映射策略同(2) (4)如果任务队列不为空且t的优先级p2不是最高,则把t加入到任务队列中等待被 映射。 (5)对于任务队列中所有未被映射的任务,每隔一定的时间间隔T就把它们各自的优 先级加1,使待它们可以尽快的待到资源映射 (6)当仼务队刎不为空时,选优取其中优先缴最高的任务进行映射;当优先缴最高的 任务不唯一时,选取其中期望完成时间C;最早的仟务进行映射;对于被选取进行映射的仟 务,其映射策略冋(2) (7)当任务队列不为空时,重复(3)-(6)直至队列为空。 (8)当仟务队列为空时,等待新仟务的到达。 重复以上算法直到所有的仟务都被调度完毕 该改进Min-Min算法的流程图如图1所小: 巾国科技论文在线 http://www.paper.edu.cn 新任务到达 任务队列为空? 优先级最高? 加入任务队列 任务队列为空? 高优先级任务优先 等待新仁务 同等优完级完成时间 最早的任务优先 任务-资源映射 图1基于优先级的在线模式Min-Min算法的流程图 32算法分析及比较 与传统的Min-Min算法相比,改进算法采用了在线模式进行任务-资源映射,当任务队 列为空或者新到达任务的优先级最高时可以立即对新任务进行资源映射,而在批模式 Min-Min调度算法中,新到任务必须等待统一映射事件的廾始,因此相比较传统的Min-Min 算法,改进算法节约了很多等待时间,当任务相玍独立并且到达时间比较分散时,改进算法 的这种优势更加的突出 改进算法中引入了调度的优先级策略,对于情况紧急的任务赋予较高的优先级,这样可 以缩短亡等待任务映射的时间,同时更倾向于分配到性能更好的机器資源,从而缩短任务的 执行时间。 改进算法中参与调度的机器集合限定机器的就绪时间h,=0,即只考虑当前可用的机 器节点进行映射,癌免了批处理 Min-Min算法中把多个任务映射到同一个札器上执行的情 况,有利于系统的负载均衡和资源利用率的提高。 依据上节对改进算法的描述,对于(2)(3)中新到达任务直接进行映射,只考虑该任 务的最早完成时间,所以映射每个任务的时间复杂度为Om),其中m为当前系统中可用的机 器资源。当有多个任务的优先级相等时,任务的调度顺序按它们的完成时间从早到晚排序, 最先完成的任务先映射,这样可以尽快释放它古用的资源为使它重新可用,提高系统的性能, 此时每个任务映射的时间复杂度为O(m) 巾国科技论文在线 http:/www.paper.edu.cn 当所有的任务同吋到达并且任务的优先缴都相同吋,此时的算法吋间复杂度同传统的 Min-Min算法相同,为Om2m),但是此时在等待时间和负载均衡性上改进算法具有更好的 性能。当任冬以随机时间等概率到达或者优先级没有重合时时间复杂度最好,最佳的时间复 杂度为O(mm) 通过以上分析,改进的基于优先级的在线模式Min-Min算法在时间复杂度、负载均衡、 等待时间等方面均有较大的改进和提高。 4.结论 本文对网格任务调度中经典的Min-Ⅵi算法进行了深入的分析,指出了该算法所存在 的缺点,并针对这些缺点提出了基于在线模式的支持仟务优先级的 Min-Min算法,该改进 算法具有更优的算法时间复杂度,避免了批模式中映射等待的问题,同时具有更好的负载均 衡特性,因此在性能上比传统的Min-Min算法只有很大的改进和提高。 参考文献 [l Foster I, Kesselman C. The grid: blueprint for a new computing infrastructure. Morgan Kaufmann, San Fransisco CA.1999 [2]朱福喜何炎祥.并行分布计算中的调度算法理论与设计[M武汉:武汉大学出版社,2003,5 [3]桂小林.格技术导论.北京:北京邮电大学出版社,2005 [4]徐志伟,祃白明,李伟.~格计算技术.北京:电子工业出版社,2004 [S]黄昌勤,栾翠菊,宋广华,魏贵义,陈启买.训算网格中的仼务管理研究及小范应用.北京:科学出版 社,2009 6都志辉,陈渝.刘鹏.网格计算.北京:清华大学出版社,2002 A Min-Min Grid Task Scheduling Algorithm Based On On-Line mode Fan Guochang Li Xu, Ma Xiaolei School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing PRC,(100876) Abstract In this paper. based on in-depth research and analysis of the most classical Min-Min grid task scheduling algorithm, some short comings of this algorithm was pointed out such as high time complexity, bad load balancing, etc. An improved Min-Min algorithm based on on-line model was proposed, which also support the task priority, the improved algorithm can save time because it dont wait for mapping took place as batch mode do, it also has better time complexity and load balancing features, so it has a better performance than the traditional min-min algorith Keywords: Grid! min-min algorichm on-line mode load balancing

...展开详情
试读 5P 论文研究-基于优先级的在线模式Min-Min任务调度算法 .pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-基于优先级的在线模式Min-Min任务调度算法 .pdf 36积分/C币 立即下载
1/5
论文研究-基于优先级的在线模式Min-Min任务调度算法 .pdf第1页

试读结束, 可继续读1页

36积分/C币 立即下载