文档介绍：合肥工业大学
硕士学位论文
基于关键路径的网格任务调度算法研究
姓名:王霜
申请学位级别:硕士
专业:计算机软件与理论
指导教师:李心科
20090301
基于关键路径的网格任务调度算法研究摘要源节点的待执行任务序列,忽略了方案制定时和方案执行时资源能力的变化。随着网络技术的飞速发展,互联网上充斥着更多可以利用的廉价资源。利用此类资源的网格计算解决规模庞大、复杂问题具有重要的意义。网格资源具有规模庞大、分布异构和动态性等特点。实现高效的网格计算需要解决许多复杂的问题,任务调度问题就是其中的一个关键问题。网格资源动态性主要反应在资源能力衰减、增强以及新资源的加入和旧资源的退出。以往的很多调度算法主要关注调度方案制定,直接将任务加入到资若在方案制定时的资源能力在方案执行时衰减顺,使得高权限任务占有了低性能资源,造成任务执行时间增加,有可能增加整个应用的并行完成时间;若在方案制定时的资源能力在方案执行时增强,任务执行时间减小,有可能减小整个应用的;当新资源加入时,由于已经为任务分配资源,所以不影响任务执行时间和整个应用的。为了减小资源能力衰减引起应用增加的程度,以及增加能力出众的新加入资源对作业Ⅳ的影响,本算法根据调度执行开始时间将任务调度分为调度方案制定和调度方案执行两个阶段,定义了网格环境下的调度执行最晚开始时间、调度执行开始时间和任务优先图斜叩娜ㄖ担治隽巳挝裢级辰嵯鹾椭葱邢醵匀挝裢冀峁沟影响以及方案制定和方案执行时间的资源能力变化对调度准确性的影响。基于关键路径的调度算法衔#×刻崆叭挝裼畔韧脊丶肪吨每个任务的完成时间,就能缩短整个作业的,即关键路径上的任务具有更高的优先权。但是,与基于最早开始时间的调度算法冉戏现,最早开始时间同样影响着作业,且在一定条件下惴ㄓ庞惴ā当前大多数调度算法主要通过预防抢夺解决资源抢夺,即在任何情况下都不允许资源抢夺。本算法在关键路径算法的基础上,根据关键路径长度定义了任务优先权,并且考虑最早开始时间对作业的影响,允许未分配资源的任务抢夺已经被任务占有的资源。在此基础上定义了资源抢夺和调度最小图,分析了资源抢夺有可能出现的几种情况,以及对任务图和调度结果的影响,并且针对一种资源抢夺情况,提出了两个启发式原则用以决定是否允许资源抢夺。最后,提出了基于的允许资源抢夺的网格依赖任务调度算法。重点分析了网格模拟平台⒃诖似教ㄉ鲜迪諩算法、
惴ê虰惴ǎ匝榻峁⑾諦惴ㄓ庞谄渌街炙惴ǎ矣行У降低了网格动态性对调度结果的影响。关键词:网格;迹欢辰嵯酰坏鞫戎葱锌J际奔洌蛔试辞蓝
—..甅猵.,,甋猻,,.,瓺,,,,瑃,.,...
,’,:;籪籐;
籰沙漏形状的五层结构.⋯⋯⋯⋯⋯⋯⋯..⋯⋯⋯..用时间槽表示资源能力分配⋯⋯⋯⋯⋯⋯⋯⋯⋯..任务调度图..⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.⋯⋯⋯..任务优先图.⋯⋯⋯⋯⋯⋯⋯.⋯.⋯⋯⋯⋯⋯..任务调度流程图⋯⋯⋯⋯⋯⋯⋯.⋯⋯⋯⋯⋯..任务调度图⋯.⋯⋯.⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯调度最小图集合⋯⋯⋯⋯⋯.⋯⋯⋯...⋯⋯⋯⋯体系结构⋯⋯⋯⋯..⋯⋯⋯⋯⋯⋯⋯⋯模拟数据实验结果柱图模拟数据实验结果曲线图模拟数据实验结果柱图影响调度结果柱图⋯⋯⋯⋯⋯⋯⋯⋯⋯.⋯⋯.算法抢夺次数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.资源利用率图表清单架构..⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..⋯..任务优先图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..图图图图图图图图图图图图图图图表表表籰
婵醐:┳制窃饶攴滓签字日期:少旯逞学位论文者签名:乏独创性声明学位论文版权使用授权书金旦曼王些太堂金鲤至些太堂盒胆王些太堂本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知,除了文中特别加以标志和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。本学位论文作者完全了解有关保留、使用学位论文的规定,有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅或借阅。本人授权可以将学位论文的全部或部分论文内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。C艿难宦畚脑诮饷芎笫视帽臼谌ㄊ学位论文作者毕业后去向:工作单位:通讯地址:导师签名:
致谢毕业在即,三年的研究生学业生涯即将成为往事。首先,感谢我的导师李心科副教授。本文的研究工作是在李老师的精心指导和悉心关怀下完成的,在我的学业和论文的研究工作中无不倾注着导师辛勤的汗水和心血。李老师严谨的治学态度、渊博的知识、谦和的待人风范使我深受启迪。从尊敬的李老师身上,我不仅学到了扎实、宽广的专业知识,也