资源描述：
《基于min-min改进后的网格调度算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第25卷第5期计算机应用Vol.25No.52005年5月ComputerApplicationsMay2005文章编号:1001-9081(2005)05-1190-03基于Min2Min改进后的网格调度算法魏天宇,曾文华,黄宝边(厦门大学计算机科学系,福建厦门361005)(skyspace001@163.com)摘要:在对网格计算中现有的任务调度算法的研究基础上,仔细分析了调度算法中最经典的Min2Min算法,指出了该算法中所存在的负载不平衡的缺点,并在该算法的基础上提出了一个改进模型来有效的平衡负载,
2、同时给出了相应的Balance2Min2Min算法。最后采用SimGrid工具包对所提出的算法进行仿真,验证了算法的合理性和高效性。关键词:网格;调度;Min2Min;Balance2Min2Min;SimGrid中图分类号:TP393文献标识码:ASchedulingalgorithmbasedonmodifiedMin2MiningridWEITian2yu,ZENGWen2hua,HUANGBao2bian(DepartmentofComputerScience,XiamenUniversity,Xia
3、menFujian361005,China)Abstract:Basedontheresearchofexistingschedulingalgorithms,aparticularanalysisofthemostclassicalMin2Minwasmadeanditpointedoutthatthisalgorithmcanleadtoabadqualityofloadbalancing.Amodifiedmodulewhichcouldbalancetheloadeffectivelyanddevel
4、opacorrespondingschedulingalgorithmBalance2Min2Minwasdrawnout.AtlastthisalgorithmwassimulatedwiththeaidofSimGridtoolkitandwasprovedreasonableandefficient.Keywords:grid;Schedule;Min2Min;Balance2Min2Min;SimGrid务可分为高质量任务和低质量任务两类;而机器异构中在同0引言一台机器上不同类型任务的执行时间是不同的
5、,机器也可分[1]为高性能机和低性能机两类。网格(Grid)技术是当今计算机领域的研究热点之一。在网格技术飞速发展的同时,网格计算中的任务调度问题也任务调度问题的实质就是在一个由m个需要调度的任变得越来越重要。任务调度的目的是在包含大量不同计算机务,n个可用的任务执行单元(主机或集群),k个数据储存单的网格环境中,同时考虑各网格节点的计算性能、节点之间的元构成的网格环境下,把m个任务T={t1,t2,⋯,tm}以合理通讯性能等参数,把不同的任务以最合理的方式分配到相应的方式调度到n个主机H={h1,h2,⋯,
6、hn}上去,目的是得到尽可能小的总执行时间(makespan)。我们把每个执行单元的网格结点去完成。任务调度也称为任务映射。由于在网格广义的当作一台主机来看待,把k个数据储存单元当成一个环境中各处理器的运行速度、主机的负载、网络通讯的时间等存储系统整体来看待。是动态变化的,因此任务调度问题同时也是一个非常困难的m个任务在n个不同机器上的预测执行时间ETCNP完全问题。(ExpectedTimetoCompute)是一个m×n的矩阵。矩阵中的每目前,围绕着网格计算中的任务调度算法,国内外已经做一行代表某一个任务
7、在n台机器上的不同执行时间,每一列了大量的研究工作,先后提出了各种静态和动态的调度算法。[2]代表在同一台机器上m个任务的不同执行时间。本文对网格调度中的Min2Min、Max2Min等最基础的启发式记第i个任务在第j台机器上的预测最小完成时间算法进行了认真的分析和研究,指出这些算法所存在的缺陷,(MinimumCompletionTime)为MCT(i,j),则m个任务在n个并提出了一个改进的算法。仿真试验表明改进后的算法比传不同机器上的预测最小完成时间也是一个m×n的矩阵。统的算法更加合理高效。MCT(i
8、,j)主要由以下几个因素决定:1问题分析(1)任务i在机器j上的预测执行时间ETC(i,j);(2)机器j的最早可用时间TASKSTART(j);通常在网格环境下主要考虑的是一组相互独立、任务之(3)任务i运行时所需数据在存储系统上的最早可取时[3]间没有通讯和数据依赖的元任务(metatask)映射。现有的间DATASTART(i);任务调度算法可以分为在线模式(on2line)和批模式(batc
