论文部分内容阅读
网格计算是伴随着互联网技术的迅速发展而产生的一种新型分布式计算模式,以实现大规模分布式资源共享及协同问题求解为目标。任务调度是网格计算的一项核心技术,高效的任务调度算法可以充分利用网格资源,从而提高应用程序的性能。然而,网格资源的动态性、异构性、自治性等特性,使得网格环境下的任务调度极其复杂,因此如何开发出有效的任务调度算法是网格计算面临的一大挑战。任务调度已被证明是一个NP难问题,因而现有的任务调度算法多以启发式方法为主。本文在详细介绍网格计算中任务调度的概念、原理、目标等相关问题的基础上,集中对启发式元任务调度算法进行研究,主要工作如下：1.简要介绍了网格计算与任务调度的研究背景和研究现状,并对网格计算与任务调度的相关理论进行详细说明。2.深入研究了Min-Min与Sufferage算法的调度原理,并通过分析总结出,Min-Min算法能够获得较短的任务等待时间,但调度跨度不理想；Sufferage算法能获得较理想的调度跨度,但任务等待时间较长。因而当用户同时对调度跨度与任务等待时间存在需求时,这两个算法均不具备较强的可用性。3.针对Sufferage算法在多个任务竞争同一资源时,仅比较各任务的次小完成时间与最小完成时间差值的不充分性,本文设计并实现了MD-Sufferage算法。MD-Sufferage算法的执行流程为：首先对任务的所有完成时间按照升序排序,之后计算各完成时间与最小完成时间的差值；随后在发生资源竞争时,不单是比较各任务的次小完成时间与最小完成时间的差值,而是依次比较所有完成时间与最小完成时间的差值。4.为了在缩短调度跨度的同时保证较小的任务等待时间,本文设计并实现了WTMB(Waiting Time and Makespan Balance)算法。WTMB算法的执行流程为：考虑到任务执行时间波动性对调度性能的影响,首先计算所有任务的执行时间波动性；随后以执行时间波动性均值为标准将调度集合划分为高波动性集合与低波动性集合；最后,轮流调度高波动性集合与低波动性集合,直至所有任务均被调度。在每一轮对这两个子任务集合进行调度时,首先依据Min-Min算法的原理选取若干最小完成时间相对较小的任务构成候选任务集,之后采用MD-Sufferage算法对该候选任务集进行调度。5.对GridSim网格模拟工具进行了深入的研究,并采用GridSim对Min-Min、Sufferage、MD-Sufferage、WTMB算法进行仿真。仿真结果表明：MD-Sufferage算法获得的调度跨度略优于Sufferage算法；WTMB算法实现了调度跨度短与任务等待时间小的统一,因而综合性能要优于Min-Min、Sufferage、MD-Sufferage算法,并且具备更强的灵活性。