（计算机应用技术专业论文）网格环境下调度机制的研究.pdf

、 、 r 备 0 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期：一矽，口年7 月，日 导师签名： 曩匆卅乞 j 签字同期：伽i o 年 月日 ， 中图分类号：t p 3 1 5 u d c ：6 2 l 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 作者姓名：王欣 导师姓名：罗四维 学位类别：工学 网格环境下调度机制的研究 r e s e a r c ho ng r i ds c h e d u l i n g 学号：0 8 1 2 0 5 3 2 职称：教授 学位级别：硕士 学科专业：计算机应用技术研究方向：计算机网络与体系结构 北京交通大学 2 0 10 年6 月 、nll0 ； 致谢 本论文的工作是在我的导师罗四维教授的悉心指导下完成的。罗四维教授严 肃的科学态度，严谨的治学精神，精益求精的工作作风，深深地感染和激励着我。 从课题的选择到最终完成，罗老师都给予了我大量的鼓励和指导。两年来，罗老 师不仅在课题研究上培养我严谨的态度，在生活中也教给我许多做人的道理，这 些都让我受益匪浅。在此，向我的导师罗四维教授致以崇高的敬意和衷心的感谢。 在此，我还要感谢实验室的其他同学，在这两年的科研生活中他们和我一起 。度过，一起进步，并对我的论文撰写提供了许多宝贵的意见。特别要感谢丁丁老 师，对我的课题研究工作提供了很多技术上的帮助。 另外也感谢我的家人，正是因为他们的理解和支持，我才能够专心完成我的 学业。 上cij 一 摘要 网格是构建在i n t e r n c t 上的一组新兴技术，其目标是在动态变化的、广域分布 的异构虚拟组织间实现资源协同共享。在网格系统中，任务调度是其重要的组成 部分，它根据任务信息采用适当的策略把任务分配到相应的资源节点上运行。由 于网格系统的异构性和动态性，以及运行于网格系统之上的应用程序对于资源的 不同需求，使得任务调度变得极其复杂。考虑不周全的任务调度策略，将会增加 任务的执行时间、降低整个网格系统的吞吐量。 本文介绍和总结了网格计算中的关键技术任务调度。网格任务调度实质 是在网格环境下将m 个需要调度的任务合理分配到万个资源上，高效的调度策略 可以充分利用网格系统的处理能力。网格的规模决定了m 和n 的数值比较庞大， 要在有限的时间里找到最优的资源分配方案比较困难，所以网格任务调度一般采 用启发式调度，目的是尽可能得到较小的任务完成时间。本文将用户提出的任务 紧迫性作为一维q o s 需求，同时考虑了任务相对忍耐度，结合m i n m i n 算法和 s u f f e r a g e 算法的优点，在s u f f e r a g e 算法基础上提出了基于任务紧迫性的网格调度 算法。在任务调度时，根据任务排序结果选出对服务质量影响最大的任务，并将 该任务映射到完成时间最早的资源。实验采用g l i d s i m 工具包仿真。结果证明， 与m i n m i n 算法和s u f f c r a g e 算法相比，该算法在任务完成时间、服务质量方面有 其自身的优点。 同时，本文就面向q o s 的任务调度，提出了一个以任务的硬性指标和弹性指 标相结合的q o s 管理和任务调度的模型体系。通过该体系结构，详细分析了基于 q o s 的网格任务调度过程，并设计了一个基于模糊贴近度的任务资源弹性参数匹 配算法，该算法考虑了多维q o s 需求，在很大程度上适应了网格应用的需求和方 向。同时将该算法与两个常见的启发式算法比较，结果表明，该算法在资源匹配 成功率等性能指标上有了明显地改善。 限于网格任务调度的适用局限性，本文对未来的工作进行了进一步地展望并 提出了一些有待增强的方面。 关键词：网格；任务调度；调度机制；调度算法；q o s 分类号：t p 3 1 5 一 j a b s t r a c t g r i dw a sb u i l ta san e w t e c h n o l o g yb a s e do ni n t e m e t i ta i m e da tc o o r d i n a t i n gt h e r e s o u r c e ss h a r i n gw i t he a c ho t h e rb e t w e e nd y n a m i c ，h e t e r o g e n e o u sv i r t u a lo r g a n i z a t i o n s t h et a s ks c h e d u l i n gw a sak e yp a r to f t h e 鲥ds y s t e m ，w h i c ha s s i g n e da l lt h et a s k st o t h e r i g h tr e s o u r c e sa c c o r d i n gt ot h et a s ki n f o r m a t i o n t h ei m p l e m e n t a t i o no ft a s k s c h e d u l i n gw a sv e r yc o m p l i c a t e db e c a u s eo ft h eh e t e r o g e n e o u sa n dd y n a m i co fg r i d ，t h e d i f f e r e n tr e q u i r e m e n tf o r r c s o u r c e sf r o ma l lt h e 酣da p p l i c a t i o n s t h ew o r s es c h e d u l i n g s t r a t e g i e sw o u l db r i n gt h ew o r s er e s u l t ，s u c ha sl o n g e re x e c u t i o nt i m e ，l o w e rt h r o u g h p u t o f g r i ds y s t e m t h i sp a p e ri n t r o d u c e da n ds u m m e du pt h ec r u c i a lt e c h n i q u e - - - t a s ks c h e d u l i n g t h e e s s e n t i a lf u n c t i o no f s c h e d u l i n gw a sa s s i g n i n gr e a s o n a b l ym t a s k st onr e s o u r c e su n d e r t h eg r i d t h es c h e d u l i n gs t r a t e g i e sw i t hh i g he f f i c i e n c yc a ng i v ef u l lp l a yt oi n i t i a t i v eo f g r i d i tw a sd i f f i c u l tt of i n dt h eb e s ts o l u t i o nf o ra l l o c a t i n gr e s o u r c e s ，b e c a u s et h ema n d nw e r ev e r yl a r g ei ng r i ds y s t e m t h a t st h er e a s o nw h yr e s e a r c h e r sc h o s et h eh e u r i s t i c a l g o r i t h m t h i sp a p e rp r o p o s e das t r a t e g yb a s e do nt h et a s ku r g e n c yr e q m r e m e n t ，w h i c h c o m b i n e dt h em i n m i na l g o r i t h mw i t hs u f f e r a g ea l g o r i t h m ，s e tt h et a s ks u f f e r a g eb a s e d o nt h em e a ne x e c u t i o nt i m ec o n s i d e r i n gq o sa n dt a s ku r g e n c ya st h ep a r a m e t e r si nt h e t a s ko r d e r i n gm e c h a n i s m t h i ss t r a t e g yp i c k e du pt h et a s kw i t h 芦e a t e s ti n f l u e n c eo nt h e q o sa c c o r d i n gt ot h er e s u l ta f t e ro r d e r i n g ，a n dt h e nm a p p e di tt ot h er e s o u r c ew i t ht h e e a r l i e s tc o m p l e t i o nt i m e f u r t h e r m o r e ，t h i sp a p e rp r o p o s e dam o d e lo fq o sm a n a g e m e n ta n dt a s ks c h e d u l i n g c o m b i n i n gt h er i g i da n de l a s t i cp a r a m e t e r s t h e na l la l g o r i t h mw i t hm u l t i d i m e n s i o n q o sr e q u i r e m e n tb a s e do nf u z z yn e a r n e s sb e t w e e nt a s k sa n dr e s o u r c e sw a sd e s i g n e d c o m p a r e dw i t ht h et w oe l d e rh e u r i s t i ca l g o r i t h m s ，i ti m p r o v e dt h ep e r f o r m a n c ei nt h e s u c c e s sr a t eo fm a t c h ，t h ea v e r a g ee x e c u t i o nt i m e ，a n ds oo n a l s o ，t h i sp a p e rm a d eaf u t u r eo u t l o o ka n dg a v es o m ef i e l d sn e e dt ob ei m p r o v e d ， b e c a u s et h ea l g o r i t h m si nt h ep a p e rh a dt h e i ro w nl i m i t a t i o n s k e y w o r d s ：g r i d ；t a s ks c h e d u l i n g ；s c h e d u l i n gm e c h a n i s m ；s c h e d u l i n ga l g o r i t h m ； q o s c l a s s n o ：t p 3 15 目录 摘要i i i a b s t r a c t i v 1 引言1 1 1 论文背景：j 。l 1 2国内外研究现状“2 1 3论文研究内容。7 1 3 1 论文主要工作7 1 3 2 论文组织7 2网格任务调度9 2 1概述9 2 1 1 调度过程9 2 1 2 调度特点1 0 2 2调度模型1 2 2 3调度策略1 4 2 3 1 形式化描述1 4 2 3 2 一般调度策略1 5 2 3 3 基于q o s 的调度策略1 7 2 4调度评价18 2 5调度仿真19 2 5 1 常见的网格仿真器。2 0 2 5 2g r i d s i m 工具包2 1 2 5 3 调度仿真过程2 4 2 6本章小结2 6 3基于任务紧迫性的调度策略2 7 3 1 调度模型2 7 3 2问题描述2 7 3 3算法描述2 8 3 3 1 参数定义2 8 3 3 2 算法流程图3 0 3 3 3 算法实现31 v 3 4实验结果及分析3 2 3 5本章小结3 7 4基于模糊贴近度的调度策略3 8 4 1任务管理3 8 4 1 1 概述3 8 4 1 2 任务管理器3 9 4 1 3 任务的执行流程4 1 4 2q o s 管理。：4 2 。4 2 1 q o s 参数模型。4 2 4 2 2 q o s 体系结构4 3 4 2 3 算法描述4 5 4 2 4 实验结果及分析4 7 4 3本章小结一4 9 5 结论一5 0 5 1研究工作总结5 0 5 2进一步工作5 0 参考文献。5 2 作者简历5 4 独创性声明5 5 学位论文数据集5 6 1 引言 1 1论文背景 计算机网格系统是利用互联网把地理上广泛分布的各种异构的计算资源、存 储资源、数据资源等连成一个逻辑整体，就像一台超级计算机一样，为用户提供 一体化信息和应用服务( 计算、存储、访问等) ，最终实现在这个虚拟环境下的资 源共享和协同工作。 ： 网格的最终目的是实现对网格资源的优化使用，完成用户提交的任务，同时 保证用户获得更好的服务质量。在实现过程中，网格系统必须根据任务的资源需 求以及网格资源的实时状态，对任务所要求的资源进行选择和分配，并进行任务 的调度。由此可见，网格任务调度对于网格系统来说是最基本也是最重要的部分 之一。 网格任务调度【i 】的基本功能是根据网格任务的需求，从众多的可用资源中，选 择满足任务需求的资源，将任务分配到该资源上执行，同时能够使该资源的某种 评价标准最大化。在计算机操作系统中，我们已经熟悉了任务调度的概念。常见 的根据时间片轮转的任务调度机制本质上就是轮流获得使用处理器资源的权利； 当然还包括其它的任务调度策略。但是网格中的任务调度不同于以往的调度，原 因在于网格本身的特性。 首先，网格具有分布性。网格资源包括计算资源、存储资源、数据资源、仪 器资源等，它们可以分布在不同的国家、城市和地区。在这种环境下，需要解决 网格任务的分配和调度问题，传输与通信、网格应用的自动执行和协作等问题。 其次，网格具有异构性。组成网格的资源是异构的。对于计算资源，有不同 类型的计算机、计算接口或者系统架构。同样，对于存储资源和其它资源，也会 面临这样的问题。因此，网格既要具有利用资源的异构特点进行处理问题的能力， 也要具有提供资源一致管理的能力。 第三，网格资源具有自治性。网格上的资源首先是属于某一个人或者组织的。 在根据一定的约束和规则接受网格系统统一管理的同时，本地的资源拥有者具有 最高级别的管理权限。网格应该允许本地用户对自己的资源有自主的管理能力。 这使得网格管理比一般的分布式系统更为复杂，具有管理的多重性。 最后，是网格的动态性。由于网格中的资源具有自治性，因此网格资源就存 在动态地加入或者退出的情况，也可能会有个别节点出现故障而导致不可用。另 外，资源的性能情况也会随时出现变化，这就势必会导致网格系统要动态地放弃 已分配的资源，选择其它资源继续完成任务。由于网格没有集中控制能力，因此， 需要有一种机制来保障网格应用的运行不会遭受比较大的影响。除了以上几点， 网格中往往还有非网格的任务，即网格中的资源竞争包括网格任务之间的竞争及 网格任务和非网格任务之间的竞争，这种复杂的竞争使得资源状态难以预测，而 对资源的状态预测是任务调度的主要依据之一。 出于以上几点原因，网格环境下的任务调度困难性可见一斑。同时，基于网 格应用本身的需求，网格系统必须具有非凡的服务质量。这也是2 0 0 2 年i a nf o s t e r 2 】 提出的网格必须满足的三个条件之一。因此，服务质量已经成为检验网格性能好 坏的标准之一。但是，正因为网格具有分布性、异构性、自治性和动态性的特点， 导致网格应用中服务质量( q u a l i t yo fs e r v i c e ，q o s ) 的保证成为了一项非常复杂和具 有挑战性的工作，服务质量的好坏、效率的高低也直接关系到网格系统的性能。 同时，网格用户关心的服务质量不只是单一的时限、花费等因素，还包括很多其 它重要因素，如可靠性、安全性保障等。对于不同的服务要求，网格系统的行为 ( 如调度策略的选择) 也需要随之变化。因此，本项目对于网格环境下基于q o s 的任务调度研究不仅有助于丰富网格计算环境中基于q o s 任务调度的策略，也有 利于为今后的相关研究和实际的网格调度系统实现提供理论基础。 1 2国内外研究现状 网格技术【3 】起源于大型科学计算，是在动态变化的多个虚拟机构之间共享资源 和协同解决某种问题。其中最为核心的是为各种网络上的资源提供一种安全高效 的共享机制，使得各种异构资源能够以一个整体为用户提供各种计算和信息服务。 近年来，随着计算机计算能力的迅速增长，互联网络的普及和高速网络成本的大 幅度降低，各个国家对网格相关技术的研究投以越来越多的关注。目前，网格的 研究已经从美国和欧洲推广到了世界各大洲，各个国家和地区都投入了大量的资 金进行网格技术研究和网格基础设施建设，这导致建设网格的理论与技术得到了 飞速发展。 网格分布的范围广并且用户相当多，因此网格的功能也就比较丰富。国内外 研究者从不同的角度出发，对网格进行了分类【1 1 。按网格客体分类；将网格分为 资源网格，信息网格和知识网格三个从低到高的层次。资源网格为上层应用提供 数据层面的联通和共享。信息网格为上层应用提供信息的无缝共享。知识网格主 要从底层的数据和信息中发掘、处理和应用知识。按网格主体分类；把网格用 户按照领域的不同分成不同的类。常见的应用网格有科学研究网格、游戏网格、 2 访问网格和制造网格等。 伴随着网格研究的深入，出现了一系列与网格有关的相关组织。比如全球网 格论坛。该论坛是一个网格技术论坛的国际组织，是由网格论坛和欧洲网格论坛 以及亚太网格社区合并而成的，它主要负责通过发布指南、标准、代码等推动和 发展网格技术和应用。其次还有万维网联盟。该联盟是一个国际性组织，它通过 开发保证互操作性的通用协议来推动万维网的发展。除此之外还有国际互联网工 程任务组等相关组织。 同时，网格体系结构也经历了由五层沙漏模型向开放网格服务体系结构( o p e n g r i ds e r v i c e sa r c h i t e c t u r e ，o g s a ) 的发展。五层沙漏结构是一种早期的抽象层次结 构，主要特点是以“协议”为中心，强调协议在网格的资源共享和互操作中的地 位，其结构简单，层次清楚。通过协议实现一种机制，使得虚拟组织的用户和资 源之间可以进行资源使用的协商，建立共享关系，并且可以进一步管理和开发新 的共享关系。网格技术的发展和现实世界中的应用需求是分不开的。2 0 0 2 年6 月， 网格研发的先行者美国a r g o n n e 国家实验室的i a nf o s t e r 等人结合w e bs e r v i c e 技术提出开放网格服务体系结构o g s a 。在o g s a 中，一切都是服务，计算资源、 存储资源、程序、数据库等都用服务来表达，从而使网格技术的共享特性在o g s a 中表现为对服务的共享。这种抽象将各种各样的广义资源统一起来，有利于灵活、 一致、动态的共享机制的实现，使得网格环境中的分布系统管理有了标准的接口 和行为。 网格技术的出现以及迅猛的发展致使许多行业具有挑战性的问题可以在新的 计算平台上完成和实现，比如金融业、汽车设计业、生命科学和其它行业。各国 的政府、研究结构和商业机构已经意识到网格的重要性，导致了网格研究的不断 升温。 1 国外网格研究 网格技术研究发源于美国。网格的研究最初是从科研机构开始的，美国的多 家研究机构开展了与网格相关的研究工作，诸如c o n d o r 、g l o b u s 等比较有影响的 网格项目。 g l o b u st o o l k i t 【4 】是由g l o b u s 联盟开发的一个软件工具箱。利用这个工具箱， 我们可以创建网格系统。它已经在世界范围内得到了一定程度的使用。该工具箱 主要包含了许多可以用来创建网格应用的高层服务，这些服务实际上可以满足 o g s a 提出的绝大部分抽象需求，它对全球的网格研究开发工作起到了巨大的推 动作用，成了网格领域关注的焦点。由于这些类型的服务接口的标准化工作正在 由全球网格论坛( g g f ) 的工作组开展，虽然目i j i 还不能将g t 4 看成是o g s a 的一 个实现，不过可以将其看作是o g s a 需求和网格社区的一系列事实标准的实现， 而g g f 正致力于所有不同服务的标准化。它的目标是能够在各种平台上运行。除 了g l o b u s 之外，美国还有许多项目与网格研究和开发工作密切相关。 l e g i o n t 5 】是弗吉尼亚大学于1 9 9 3 年开始研究的一个基于对象的元系统软件项 目。在l e g i o n 内，所有的网格组件、资源和服务都使用一个对象表示。每个对象 由它的类对象定义和管理，类对象的作用相当于管理者，它除了定义实例之外， 还制定管理策略。l e g i o n 允许应用开发者选择和定义系统级的责任，其目标是为 用户提供单一的、一致的虚拟机器模型。l e g i o n 支持透明调度、数据管理、容错、 站点自治和多种安全机制。 c o n d o r 是威斯康星二一麦迪逊大学的研究项目，它是个专用的计算密集型 负载管理系统，具备选优能力，提供队列机制、调度策略、优先级方案、资源监 控、资源管理等功能。用户向c o n d o r 提交自己的作业后( 可以是串行作业，也可 以是并行作业) ，c o n d o r 把作业放在队列中，并根据某种策略，选择合适的时间在 合适的节点上运行用户提交的作业。作业运行过程中，它监控作业的运行过程； 作业运行结束时，它通知提交作业的用户。 n a s ai p g ：美国的n a s a ( n a t i o n a la e r o n a u t i c sa n d s p a c ea d m i n i s t r a t i o n ) 正在 构造一个网格计算试验床，称为i p g ( i n f o r m a t i o np o w e rg r i d ) ，使用i p g 中间件， 网格用户就可以从任何地方访问广泛分布的异构性资源。其主要目标是建立一个 网格环境原型，提供统一的资源访问，主要适用的应用领域为：高性能计算、高 能物理和海量数据存储等。 美国已经有不少的商业公司加入到网格研究的行列，多家大公司都纷纷宣布 了各自的网格战略计划。i b m 和g l o b u s 提出的开放网格服务结构正在赢得大家的 认可，对未来网格的研究将产生重大的影响。 在各国政府部门的大力支持下，亚洲的中国、日本、韩国等国都先后举办了 网格方面的高级国际论坛或研讨会，网格的研究和应用已经在亚洲许多国家和地 区开展起来。亚太网格式亚洲和太平洋地区网格研究的基础设施，它把重点放在 资源共享、网格技术开发、网格技术推广等方面，它不局限于很少的几个发达国 家，也不局限于特定网格，更不对研究组织进行限制。它也是亚洲和太平洋地区 各国研究人员进行技术交流、信息交换的场所。它作为亚太地区的代表参加了全 球网格论坛组织以及与网格研究有关的其它活动。 日本是亚洲开展网格研究比较早的国家之一，已经进行了多个项目的研发。 n i n f 是同本j 下在实施的全球计算基础设施项目，它允许用户访问包括硬件、软件 和数据在内的、分布在广域网上的资源。b r i c k s 是r 本的另一个研究项目，它是一 个性能评价系统，允许在典型的高性能全球计算环境上分析和评价不同的调度策 略，它能模拟不同的全球计算系统的不同行为，尤其是网络的行为和资源调度算 4 法的行为。 韩国的情报和通信部与韩国科学技术情报研究院于2 0 0 1 年5 月开展了国家网 格基本计划，促进了国内的网格研究活动，加强了与国际网格研究组织和项目之 间的交流，建立了韩国网格论坛，推动了网格技术的发展。n g r i d 是韩国情报和 通信部支持的一个项目，目标是要建立韩国国家网格，该项目包括计算网格、数 据网格、访问网格和应用网格四个部分。它将韩国的超级计算机和高性能集群连 接在一起，建立了应用试验床及应用门户，开发了具体的应用程序。泰国网格计 划将重点放在资源共享、增加资源利用率、提高合作能力方面。初步的工作在于 开发几个使用网格的应用。在应用开发过程中，需要研究开发一个中间件，实现 和底层应用程序接口的绘画，例如资源查询、资源分配等服务的调度。用户通过 访问网格提交一个作业，为了透明地共享数据，需要构建数据网格应用程序接口。 2 国内网格研究 对于网格计算，我国政府给予了高度重视。在我国，网格研究已列入“8 6 3 计 划”。开展的项目主要有：中国国家网格、中国空间信息网格、教育科研网格、中 国气象应用网格等。网格计算研究主要集中在中科院计算所、清华大学等几家在 高性能计算方面有较强实力的研究单位。在8 6 3 计划的支持下，我国的多项网格 研究已经取得了突破。 国家高性能计算环境是国家级高性能计算和信息服务的战略性基础设施。该 项目的目标是建立一个计算资源广域分布、支持异构特性的计算网格示范系统， 它把我国的八个高性能计算中心通过i n t e m e t 连接起来进行统一的资源管理，并在 此基础上开发了多个需要高性能计算能力的网格应用系统，已经取得了一系列研 究成果。 中国空间信息网格是国家投资2 0 0 0 万建立的又一大型网格项目。空间信息网 格是一种汇集和共享地理上分布的海量空间信息资源，对其进行一体化组织与处 理，从而具有按需服务能力的、强大的空间数据管理和信息处理能力的空间信息 基础设施。空间信息网格是一个创新性的体系框架，它为空间信息用户对空间数 据进行信息获取、共享、访问、分析和处理等各种需求提供了实用可行的解决思 路和实施方案。 中国教育科研网格是教育部“十五 2 1 1 工程公共服务体系建设的重大专项， 项目第一期投资1 2 0 0 万。该网格主要由生物信息学网格、图像处理网格、远程教 育网格、流体力学网格和海量信息处理网格这五大专业应用网格构成。它将充分 利用中国教育科研网和高校的大量计算资源和信息资源，开发相应的网格软件， 配合网络计算机的使用，将分布在c e r n e t 上自治的分布异构的海量信息资源集 成起来，实现c e r n e t 环境下资源的有效共享，消除信息孤岛，提供有效的服务 5 器，形成高水平、低成本的计算服务平台。 中国气象应用网格，其目标是以“十五”国家科技攻关项目“中国气象数值 预报系统技术创新研究”的研究成果为基础，研制基于网格技术的数值天气预报 软件及其支持软件；利用中国气象局已有的卫星气象通讯网络和高性能计算资源 深入研究数值预报工作流管理、防火墙突破等技术。 网格作为广域环境下的信息基础设施，其目标令人鼓舞，但是随着研究的深 入，面临的挑战性问题越来越多，任务调度便是其中之一，因而成为研究热点。 国外一些重大网格项目中的调度研究有： g l o b u s 4 】：由美国a r g o n n e 国家实验室实施的研究项目。该项目的主要研究计 划是网格技术的研究和相应软件的开发标准制定。目前g l o b u s 被认为是计算网格 技术的典型代表和事实上的规范。其资源管理体系结构采用典型的层次模型，实 现了层次模型的大部分被动组件和主动组件；资源描述与访问采用可扩展模式模 型、层次式名空间、软q o s 、l d a p 网络目录存储、分布式查询发现、周期性推送 分发等；在任务调度方面，提供较低级的服务，支持上层资源分配或者协同分配， 提供高级工具执行调度等。 l s f 由加拿大平台计算机公司研制和开发，从t o r o n t o 大学开发的u t o p i a 系 统发展而来。l s f 是一个成熟的集群作业管理系统，资源管理采用集中式模型， 在任务调度方面的主要特点是提供抢占式调度；保证紧急任务的调度；可通过逻 辑表达式创建任务依赖图，提供对依赖性任务的支持；提供了多种调度策略，其 中包括r e s e r v a t i o n 和b a c k f i l l 等。 b o n d 6 】：由美国p u r d u e 大学探索基于证券市场的经济方法建立网格环境的一 个项目。其资源管理体系结构采用层次模型；资源描述与访问采用可扩展对象模 型、图式名空间、硬q o s 、基于语言的对象存储与通讯、基于代理的发现、周期 性推送分发；在任务调度方面采用分布式调度、可预测价格模型、在线重调度方 法、固定的面向应用的调度策略等。 n i m r o d g 7 】：由澳大利亚m o n a s h 大学开发的一个专门用来模拟参数学习的网 格项目。其资源管理体系结构采用典型的经济市场模型；资源描述与访问使用由 底层g l o b u s 中间件服务所提供的资源模型、依赖于计算节点的可用性、提供软q o s 和硬q o s 等；在任务调度中引入经济方法，采用由计算经济和截止期限所驱动的 应用级调度策略，遵循层次、分布式调度模型等。 g c o m m e r c e ：由美国t e n n e s s e e 大学实施的研究项目，此项目使用市场经济 学在网格中进行动态资源分配。研究指出了资源的相对价值是根据供需变化而改 变的，给出了c p u 资源和磁盘资源的价格公式，并讨论了关于价格调整的问题。 6 1 3 论文研究内容 1 3 1论文主要工作 1 介绍了网格任务调度的过程、特点以及调度评价指标。从网格调度模型和 策略两方面来系统地描述网格环境下任务的调度机制。介绍了常见的调度 策略和以q o s 为出发点的调度策略。 2 提出了以任务紧迫性为一维q o s 需求的网格调度算法，在s u f f e r a g e 中结 合m i n m i n 算法，将任务紧迫性参数和任务平均执行忍耐度作为启发知 识，重新构建了启发式规则，并将其与经典调度算法比较，利用g r i d s i m 工具包进行多次实验，验证了该算法在服务性能上的提升。 3 提出了一个任务管理器的模型，着重介绍q o s 管理模块，并在此基础上 设计了一个基于模糊贴近度的网格任务调度策略，该策略考虑了多维q o s 需求，并将其分为硬性参数和弹性参数两部分，对于资源任务的弹性参 数采用模糊贴近匹配。实验结果证明，该算法较常见的基于q o s 的调度 算法在某些性能指标上有了提高。 1 3 2论文组织 本论文详细介绍了网格技术以及任务调度的研究现状和发展，并对任务调度 中的关键问题提出了自己的看法和观点，全文主要分为五个章节。 每一章首先介绍了本论文的研究背景、国内外研究现状和发展趋势，对论文 所研究的项目意义做了简单的概括和描述； 第二章为了从整体上把握论文的研究内容和方法，主要介绍了网格任务调度 的基础知识，分别从调度特点、调度过程、调度模型、调度策略以及调度评价五 个方面进行描述，并针对调度策略中的一般调度策略和基于q o s 的调度策略作了 研究，给出了常用了评价标准以及计算公式。最后就本论文的实验平台一一 g r i d s i m 网格仿真工具作了详细介绍。 第三章和第四章是本论文的核心。在第三章中，本文以第二章介绍的相关知 识为基础，结合了m i n m i n 算法和s u f f e r a g e 算法的优点，将任务紧迫性作为一维 q o s 需求，并考虑任务的平均执行忍耐度，提出了基于任务紧迫性的网格调度策 略，并对该策略进行了验证；根据第三章中策略的验证结果，证明了基于q o s 调 度策略的有效性。第四章以此为基础，首先设计了一个任务管理器架构，进而提 出了一个以任务的硬性指标和弹性指标相结合的q o s 管理和任务调度的模型体 7 系，考虑多维q o s 需求，设计了基于模糊贴近度的调度策略，并将其与传统的启 发式算法进行对比，验证其性能的提高。 第五章针对本文所作的研究工作做出了总结，并就论文不足的地方提出了未 来改进的方向。 2 网格任务调度 2 1概述 网格的能力体现在应用程序的运行性能上。为了获得较高的运行性能，首先 需要仔细分析应用的特性，可用的网格节点类型、处理器数量、存储能力、网络 带宽和延迟，以及输入输出的数据位置等等。其次就是在应用和网格资源之间做 出合理匹配，并在运行过程中不断地调整和优化，这就是网格任务调度。 在资源众多、用户众多的情况下，资源分配和任务调度是一个极其繁琐和复 杂的问题，调度的基本原则就是保障资源顺利完成用户提交的任务，能有效地避 免和解除死锁，同时要考虑资源在空间和时间上的合理搭配，以期达到更好的效 果。更为复杂的调度算法还会考虑应用的优先级、资源预留、自动调度等问题。 2 1 1调度过程 在网格环境下，当网格用户提出某个任务之后，网格资源中满足其所需要的 资源可能有多个，而且该任务在这些符合需要的资源上执行时所获得的服务性能、 付出的费用、代价可能也不一样a 同样都是满足条件的资源，但提供给使用者的 服务质量( q o s ) 会存在一定的差异，有时这种差异会很大。如何根据任务的q o s 需求选择合理的资源便是网格任务调度算法要考虑的问题。 网格系统会根据下列步骤来完成对任务的调度： 1 从接口获得资源和任务的信息资料，经过挑选和提取建立任务集和原始资 源集； 2 进行调度预处理，根据任务的需求和资源所具备的属性，根据筛选策略进 行筛选，获得可用的资源集； 3 然后从满足条件的资源节点集合中根据主要因素或选择策略选择一个合 适的资源，将其分配给该任务； 4 任务获得满足条件的资源后，便可以在该资源上运行，同时并接受资源本 地的任务管理机制的管理； 5 任务在资源上执行结束后，把占用的资源还给网格管理机构： 6 反馈任务执行结果和有关信息给任务提交者： 7 调度结束。 由上可以总结出，网格任务调度的核心是：针对网格模型和任务模型，建立 9 适宜的调度模型、算法，在调度策略和目标函数的作用下进行调度。为了提高调 度的性能，往往会有调度评价与之结合。典型的网格任务调度组成如图2 i 所示： 网格软件系统架构有效网 调度策略 目标函数 网格资源组成结构格资源 调 ，、 3 调度模型 度 网格模犁 调度算法 结 应用软 任务属性 果 性能指标 4 启动模拟 g r i d s i m s t a r t g r i d s i m u l a t i o n 0 ； 5 模拟结束，输出任务完成情况，对结果进行分析。 p r i v a t es t a t i cv o i dp r i n t o u t p u t ( g r i d l e t ) 代码略 2 6 本章小结 本章系统地介绍了网格任务调度的相关知识，从调度过程、调度特点、调度 模型方面对网格环境下的任务调度作了描述；其次，介绍了在线模式和批模式下 的经典调度策略，以及基于q o s 考虑的任务调度策略( q o sg u i d e dm i n - m i n 等) ； 第三，针对现有的调度策略给出几种性能评价标准，并给出了相应的计算公式； 最后，给出了网格仿真器g r i d s i m 的仿真原理和仿真过程，为本论文中所提出的 调度策略的验证工作提供了基础保障。 基于任务紧迫性的调度策略 在第二章所介绍的几种批模式下的调度策略中，多数以计算资源( 主机性能) 或计算量( 时间) 为调度依据，但对用户而言，仅仅考虑这些参数是不够的。比 如在市场经济环境下，计算费用等是用户必需考虑的问题，并且不同等级的用户 应该得到相应等级的服务，而这些参数在上述策略中是没有体现的。 本章针对这种问题，提出了以任务紧迫性为需求的网格调度策略，在s u f f e r a g e 中结合m i n - m i n 算法，将用户的任务紧迫性作为一维的q o s 需求来考虑，并且将 任务平均执行忍耐度问题作为启发知识之一，将网格环境下不同类型的任务执行 时间相差较大的因素考虑在内，综合两种体现服务质量的参数，重新构造了启发 式规则，优先调度那些任务紧迫性高并且等待时间相对于执行时间较大的任务。 并利用g r i d s i m 工具包进行调度算法仿真，实验结果表明，基于紧迫性的调度策 略在加入了紧迫性参数之后，随着任务数的逐渐增加，任务的服务质量得到了稳 定地提高。 3 1调度模型 本文假设用户提交的任务是网格调度器处理的基本单位，它们之间相互独立， 并且无需跨节点执行。任务集合t = 亿，瓦，疋7 是m 个相互独立的任务集合，任 务的输入和输出都以文件的形式呈现。r = 皿，尺，一，r7 是由 个计算资源组成的 资源集合。这些资源可以是个人主机、超级计算机或者集群等。本文假设执行该 任务所需要的数据正好在所分配的资源上，那么在用户提交一个任务直至得到结 果的时间中没有包括数据从其它节点传输到执行节点的时间。 3 2问题描述 本调度策略是针对异构网格环境下，用户提交任务包含紧迫性需求的情况进 行研究。对于某种计费资源，资源申请者付出的费用与其从资源提供者得到的服 务成证比，即将资源申请者等级制，高级别的用户应当得到高质量的服务。在这 罩，资源申请者的级别定义为任务紧迫性参数，参数值越高，表明该用户级别越 高，其所提交的任务应该更快地予以执行，反之，任务可以相对延后。 如前所述，s u f f e r a g e 算法以任务的忍耐度作为任务调度的主要依据，然而在 实际的网格环境下，由于不同的任务性质，不同的任务种类，一些任务的执行时 2 7 间相对于另外一些任务来说数量级会相差很大，导致任务的忍耐度也存在着很大 的差异。例如表3 1 中的乃，乏： 表3 - 1 执行时间差异示例( s ) t a b l e 3 - 1s a m p l eo fe x e c u t i o nt i m eg a p ( s ) 资源节点 任务 r lr 2r 3 凡 t l + 0 10 20 3 ：0 4 t 2 5 0 6 07 08 0 如表所示，正为简单的查询任务，执行时间较短，在所有的资源节点上都为 零点几秒，而乃是大规模的计算任务，在相应的资源节点上执行时间较长，都为 几十秒。两个任务最早执行时间的资源节点都为r ，按照s u f f e r a g e 算法的出发点， 任务的忍耐度来进行调度，显然，由于l 的忍耐度大于乃，乃会在r ，上运行，而乃 则会被调度到忌上。但是对于正来说，调度到尺，上执行意味着它的执行时间变为 0 2 秒，相对于最短运行时间0 1 秒来说，它得到的服务质量减少了一半。但是如 果我们先把乃映射到r 上，那么乃也会被映射到r ，上。最终正得到了