论文部分内容阅读
网络的高速发展,使得分散的、异构的计算机资源有机的结合到一起,并且使其形成一个巨大的网格成为可能。相应地,网格中的任务调度也成为一个非常重要的问题。任务调度算法的研究,直接关系到网格环境中调度的速度和质量,在网格计算技术的研究中,起着举足轻重的作用。作为启发式算法中的经典算法,Min-Min算法总是先执行具有最短完成时间的任务,有着思路简单、总完成时间较短的特点,是网格任务调度算法研究中倍受关注的一个算法,但是Min-Min算法存在负载不均的缺陷。网格计算中,一个好的任务调度算法不但要考虑所有任务的最终完成时间Makespan要尽量小,同时要考虑到整个系统机器间的负载均衡问题。本文的主要研究工作包括：(1)针对Min-Min算法负载不均的缺陷,本文提出了一种改进的算法K-M-I,该算法将Max-Int算法中时间损失度的思想引入Min-Min算法中。改进的算法K-M-I中设置了一个可调节的参数k,k的取值是一个百分数,代表从所有任务中挑选出计算时间损失度的任务数占总任务数的比值。利用实验测试了k的取值,得出k的取值为何值时,K-M-I算法具有更小的时间跨度Makespan,并将算法K-M-I与Min-Min算法和Max-Int算法进行了比较,得出改进的算法与Min-Min算法相比,有更小的时间跨度和更好的负载均衡,在负载均衡方面,改进算法也优于Max-Int算法。(2)针对Min-Min算法未考虑服务质量QoS要求的缺陷,本文参照QoS guided Min-Min算法改进Min-Min算法的思路,提出了一种考虑QoS要求的改进算法QoS guided K-M-I算法。利用实验仿真,将改进算法QoS guided K-M-I算法与Min-Min算法和QoS guided Min-Min算法进行了比较,得出改进的算法与Min-Min算法相比,达到了更小的时间跨度与更好的负载均衡的综合性能的统一,同时在负载均衡方面,改进算法QoS guided K-M-I也优于QoS guided Min-Min算法。