（计算机应用技术专业论文）qos约束下的网格任务调度算法研究.pdf

已。i 。：j f g r i dt a s ks c h e d u l i n g a l g o r i t h mw i t hq o s c o n s t r a i n t s s p e c i a l t y ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y m a s t e rd e g r e ec a n d i d a t e ：z h o n g y i n g z i ， s u p e r v i s o r ：p r o f y a n gc h a n g x i n g s c h o o lo fi n f o r m a t i o ns c i e n c e & e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h ah u n a n p r c 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 簋生墓望日期：j 丑旦_ 年上月盟日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：鲐墓姿 导师签名日期：骅月兰日 摘要 网格是继i n t e r n e t 和w e b 技术之后又一次重大的科技变革。在网 格计算环境中，任务调度是影响系统性能和服务质量的关键问题之 一，已经被证明是一个n p 完全问题，所以它引起了众多学者的关注， 成为一个研究的热点。 目前，很多网格任务调度算法是针对元任务的调度问题而提出来 的，但是，许多领域的网格应用，如生物信息学和天文学等，都需要 考虑任务间的依赖关系。在资源异构、广域互连的网格计算环境中， 任务间的依赖关系对传统的调度算法提出了新的挑战。任务调度的主 要工作是确定任务的执行次序以及为任务分配合适的资源。可以用一 个有向无环图( d a g ) 来描述任务间的先后执行约束关系。 而另一方面，蚁群算法是一种新兴的有效地求解n p 类问题的智 能启发式优化算法。它具有较强的正反馈效应、鲁棒性和内在的分布 并行性，且易于和其他方法相结合。但蚁群算法初期信息素匮乏，求 解速度较慢。 本文在考虑时间和花费两项用户q o s 需求的基础上，提出了 g c a a 和g t a a 两个网格任务调度算法。先采用g c ( g r e e d yc o s t t i m ed i s t r i b u t i o n ) 算法或g t ( g r e e d yt i m e c o s td i s t r i b u t i o n ) 算法求 解，将所得解转化为蚁群算法的初始信息素分布，然后利用蚁群算法 获得调度解。模拟实验结果表明：在网格环境下，本文提出的调度算 法具有明显的优势。 关键词蚁群算法，网格计算，任务调度，g r i d s i m a b s t r a c t g r i di sa n o t h e rg r e a tt e c h n o l o g i c a lr e v o l u t i o na f t e rt h ei n t e r n e ta n d w e b t a s ks c h e d u l i n gi so n eo fk e yf a c t o r so fs y s t e mp e r f o r m a n c ea n d s e r v i c eq u a l i t yi ng r i dc o m p u t i n ge n v i r o n m e n ta n di t h a sb e e np r o v e dt o b ean p - c o m p l e t ep r o b l e m t h e r e f o r e ，i t 。a t t r a c t e dt h ea t t e n t i o no fm a n y s c h o l a r sa n dt u r n e dt ob ear e s e a r c hh o t s p o t a tp r e s e n t ，m a n yg r i dt a s ks c h e d u l i n g a l g o r i t h m sa s s u m et h e s c h e d u l e dt a s ki sm e t a - t a s k ，b u tm a n yg r i da p p l i c a t i o n si na r e a ss u c ha s b i o i n f o r m a t i c sa n da s t r o n o m ya r er e q u i r e dt oc o n s i d e rt h ed e p e n d e n c i e s a m o n g t a s k s i nt h e g r i dc o m p u t i n ge n v i r o n m e n t ，r e s o u r c e s a r e h e t e r o g e n e o u sa n di n t e r c o n n e c t e do v e rt h ew o r l d ，s ot h ed e p e n d e n c i e s a m o n gt a s k sp r e s e n t e dn e wc h a l l e n g e s t ot h et r a d i t i o n a ls c h e d u l i n g a l g o r i t h m s t h em a i nw o r ko fs c h e d u l i n gi st od e t e r m i n et h ee x e c u t i o n o r d e rf o rt h et a s k so fa na p p l i c a t i o na n da s s i g nt h et a s k st os u i t a b l e r e s o u r c e s w ec a n u s ed i r e c t e d a c y c l i cg r a p h s t od e s c r i b et h e d e p e n d e n c i e sa m o n gt a s k s o nt h eo t h e rh a n d ，a n ta l g o r i t h mi san e wk i n do fi n t e l l i g e n t h e u r i s t i co p t i m i z a t i o na l g o r i t h mt os o l v et h en pp r o b l e me f f e c t i v e l y i t h a st h ec h a r a c t e r i s t i c so f s t r o n gp o s i t i v ef e e d b a c k ，s t a b i l i t y a n d p a r a l l e l i s m ，a n di se a s i l yc o m b i n e dt oo t h e rm e t h o d s h o w e v e r , t h ei n i t i a l p h e r o m o n eo fa n ta l g o r i t h mi sl a c k e d ，s oi ts o l v e ss l o w l y i nt h i sp a p e r , c o n s i d e r i n gt h eu s e r s q o sr e q u i r e m e n t s ( t i m ea n d c o s t ) ，w ep r o p o s e dt w og r i dt a s ks c h e d u l i n ga l g o r i t h m s ：g c a aa n d g t a a a tf i r s t ，g c ( g r e e d yc o s t t i m ed i s t r i b u t i o n ) a l g o r i t h mo rg t ( g r e e d yt i m e - c o s td i s t r i b u t i o n ) a l g o r i t h mp r o d u c e das o l u t i o nw h i c h w a st r a n s f o r m e di n t ot h ei n i t i a lp h e r o m o n eo fa n ta l g o r i t h m t h e n ，a n t c o l o n ya l g o r i t h mc o n v e r g e do ng l o b a l b e s ts o l u t i o n s i m u l a t i o nr e s u l t s s h o wt h a t ：i nt h eg r i de n v i r o n m e n t ，t h ep r o p o s e ds c h e d u l i n ga l g o r i t h m s p e r f o r mb e t t e r t h a no t h e r s c h e d u l i n ga l g o r i t h m so b v i o u s l y i n g r i d e n v i r o n m e n t k e yw o r d sa n ta l g o r i t h m ，g r i dc o m p u t i n g ，t a s ks c h e d u l i n g ，g r i d s i m i l 目录 摘要i a b s t r a c t i i e jj 录i i i 第一章绪论1 1 1 研究背景“1 1 2 网格计算研究现状2 1 - 3 网格任务调度算法研究现状3 1 3 1 启发性智能任务调度3 1 3 2 基于a g e n t 的任务调度5 1 3 3 基于p e t r i 网的任务调度5 1 3 4 其他启发式任务调度算法5 1 4 本文的主要工作6 1 5 本文的组织结构和安排一6 第二章网格计算及其任务调度综述一8 2 1 网格的概念8 2 2 网格计算任务调度的特点和主要目标l o 2 2 1 网格计算任务调度的特点一1l 2 2 2 网格计算任务调度的主要目标1 1 2 3 网格计算任务调度过程1 2 2 4 本章小结1 3 第三章蚁群算法原理1 4 3 1 组合优化问题和n p 完全问题简介1 4 3 1 1 组合优化问题1 4 3 1 2n p 完全问题1 4 3 2 元启发式算法概述15 3 3 蚁群算法原理16 3 3 1 自然界中蚁群行为描述1 6 3 3 2 基本蚁群算法的数学模型一1 7 3 3 3 基本蚁群算法的实现步骤1 9 3 3 4 蚁群算法的特点2 l 3 4 蚁群算法的应用2 2 i i i 3 4 1 在静态组合优化问题中的应用2 2 3 4 2 在动态组合优化问题中的应用2 3 3 5 本章小结2 4 第四章基于蚁群算法的网格任务调度算法2 5 4 1 问题描述j 2 5 4 2 算法简介2 7 4 3g c 算法2 7 4 4g t 算法：- 2 8 4 5 改进蚁群算法2 8 4 5 1 目标函数2 8 4 5 2 高度分层排序2 9 4 5 3 蚁群系统3 0 4 6 算法总体描述3 2 4 6 1g c a a 算法总体描述3 2 4 6 2g t a a 算法总体描述。3 4 4 7 本章小结3 6 第五章仿真实验及结果分析3 7 5 1 网格模拟工具3 7 5 2g r i d s i m 简介3 8 5 2 1g r i d s i m 的特征3 9 5 2 2g r i d s i m 的体系结构4 0 5 3 实验结果与分析4 1 5 3 1g c a a 算法4 1 5 3 2g m 蛆算法4 3 5 4 本章小结4 4 第六章总结与展望4 5 6 1 总结4 5 6 2 展望4 5 参考文献4 7 致 射5 2 攻读学位期间主要的研究成果5 3 i v 硕七学位论文第一章绪论 1 1 研究背景 第一章绪论 网格( g r i d ) 这一新兴的r r 技术是继传统互联网之后又一次重大的科技变 革。传统互联网仅仅实现了计算机系统互联和网页的连通，而网格试图实现互联 网上所有资源( 如计算资源、存储资源、网络资源、数据资源、信息资源、设备 资源等等) 的全面共享【l 】，把分散在不同地理位置的各种资源整合成一台“虚拟 的超级计算机 ，处理来自用户的请求，为解决复杂计算问题提供了一种新型计 算模式。在文献 2 】中，i a nf o s t e r ，g l o b u s 项目开发组的领导者，指出网格必须 能够解决在动态、异构的虚拟组织中实现协作式资源共享和问题求解。 网格具有如下几个特性【3 】： ( 1 ) 分布性与共享性； ( 2 ) 自相似性； ( 3 ) 动态性与多样性； ( 4 ) 自治性与管理的多重性； ( 5 ) 安全性。 基于上述几个特性，与传统分布式系统相比，网格具有如下几大优势【4 】： ( 1 ) 网格系统中包含许多可以解决认证、授权、资源发现和资源存取等基本 问题的标准、开放和通用的协议。 ( 2 ) 网格能够融合各种异构资源，协调各种用户对这些资源的使用，并且使 用户在不同控制域中能够解决出现在分布式环境中的使用费用和安全策略等问 题。 ( 3 ) 网格系统中，能够允许资源被协同使用，从而满足不同用户的不同服务 质量需求。 可以说，网格从根本上改变了我们思考和使用计算的方式，对人类的能力和 社会有着巨大的影响【5 l 。 在网格计算中，必需具备的三个基本功能有【6 】：任务管理、资源管理和任务 调度。其中，网格任务管理系统供给用户向网格提交任务、给任务指定所需资源、 监控任务的运行状态并且删除任务的功能；网格资源管理系统提供监控网格资源 的状况、收集任务运行时的网格资源占用情况的数据等功能；而网格任务调度系 统按照任务的类型、所需资源和可用资源等情况为用户提交的任务安排运行日程 硕士学位论文第一章绪论 和策略。 任务调度系统是网格系统中非常重要的组成部分【7 1 ，它需要采取适当的算法 或策略并且根据任务和资源的信息把各个任务分配到相应的资源结点上去执行。 由于网格系统的动态性和异构性，再加上运行在网格系统中的应用程序对于资源 的需求也各不相同，使得任务调度变得十分复杂。不好的任务调度算法或策略， 将很难满足用户任务的服务质量需求、会降低整个网格系统的吞吐量；而良好的 任务调度算法或策略，将能够充分利用系统资源的并行分布式处理能力【s 】，保障 用户任务的服务质量需求。 在动态、异构的网格计算环境中，任务调度是一个公认的n p h a r d 问题，它 引起了国内外众多研究者的关注，成为当前网格计算领域中的一个焦点。 1 2 网格计算研究现状 网格能够为人们提供大量全新的解决问题的方法和策略，1 9 9 8 年，i a nf o s t e r 提出了网格的几个主要应用【9 】： ( 1 ) 分布式大规模计算； ( 2 ) 分布式仪器系统； ( 3 ) 数据密集型应用； ( 4 ) 远程沉浸。 虽然上面所述反映的是1 9 9 8 年的应用前景和现状，但是大部分内容仍然经 得起时间考验，仍然能够提供有价值的参考。除了上述几个应用之后，目前，网 格的应用还有【5 】： ( 1 ) 可预测的维护：分布式飞行器引擎诊断； ( 2 ) 分布式遥现：地震工程学与n e e s g r i d 的协作； ( 3 ) 科学数据联盟：全球天文望远镜； ( 4 ) 医学数据联盟：生物医学信息学科研网； ( 5 ) 知识集成：生物信息学中的i ns i l i c o 实验； ( 6 ) 分布式数据分析：用于高能物理的联合计算； ( 7 ) 大规模分布式计算：基于桌面计算机网格的虚拟筛选； ( 8 ) 企业资源管理：科研和工业中的应用； ( 9 ) 可扩展的互动性：多人游戏基础设施； ( 1 0 ) 服务虚拟化：基础设施和应用； ( 11 ) 群体协作：访问网格协作系统； ( 1 2 ) 协作式科学：天体物理学需求与经验。 2 硕士学位论文第一章绪论 目前，虽然在网格研究领域中，美国、欧洲和同本等发达国家处于领先地位， 但在中国，网格技术研究工作和网格基础设施建设也取得了不错的成就，如先进 计算基础设施( a d v a n c e dc o m p u t a t i o n a lh 觚t r u c t u r e ，a c i ) 、国家高性能计算 环境( n a t i o n a lh i 【g hp e r f o r m a n c ec o m p u t i n ge n v i r o n m e n t ，n h p c e ) 、中国网格 ( c h i n a g r i d ) 、上海教育科研网格、航天二院和清华大学共同研究的“仿真网格”、 织女星网格等等【l0 1 。 1 3 网格任务调度算法研究现状 目前，一些网格研究项目已经成功地设计出各自的网格系统【1 1 1 。许多网格系 统的任务管理和调度模块主要都是基于g l o b u s 中间件所提供的相关组件的，如 c o n d o r - g 1 2 】( 由威斯康星麦迪逊大学开发) ，a p p l e s 1 3 】( a p p l i c a t i o nl e v e l s c h e d u l i n g ，由加利福尼亚大学圣迭亚戈分校开发) 和n i m r o d g t l 4 】( 由澳大利亚 m o n a s h 大学开发) 等等。 除了上面提到的一些基于g l o b u s 设计的网格系统之外，还有很多的网格系 统是独立于g l o b u s 而设计的，如l e g i o n t l5 1 、n e t s o l v e g r i d s o l v e t l 6 】和j a v a l i n t l 7 】 等等。 在网格计算中，任务调度的实质就是把“合适的任务分配到“合适的资 源上去执行，因此不同的任务调度算法有不同的调度目标。网格计算中的任务 调度是一个n p 完全问题【1 8 】，虽然采用穷举法可以求解n p 问题，但是算法的复 杂度将会是十分巨大的，因此，以求近似最优解为目的的启发式算法就受到了极 大地重视。 1 3 1 启发性智能任务调度 近年来，人们提出了许多启发性智能优化算法，如遗传算法【1 9 】、蚁群算法 2 0 】、 神经网络、模拟退火【2 1 1 、禁忌搜索等等。 ( 1 ) 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是美国j h o l l a n d 首次提出来的，它从 一组随机产生的初始解开始搜索过程。这组随机产生的初始解称为一个种群 ( p o p u l a t i o n ) ，也称为个体群。种群中每个个体是问题的一个解，表示成染色体 ( c h r o m o s o m e ) 。将染色体置于问题的环境中，根据优胜劣汰、适者生存的原则， 从中选择出适应环境的染色体进行复制，通过交叉、变异等操作产生出新一代更 适应环境的种群，这样一代代地不断进化，最终收敛到一个最适合环境的染色体 硕十学位论文 第一章绪论 上，从而求得问题的最优解【2 2 1 。 标准的遗传算法有下述三个基本成分： 1 ) 种群； 2 ) 适应度函数； 3 ) 遗传操作。 肖青等在文献 2 3 】中提出了一个基于遗传算法的网格任务调度算法。 。( 2 ) 蚁群算法 蚁群算法( a n t a l g o r i t h m ，a a ) 。是一个基于蚂蚁觅食行为的新兴启发式智能- 优化算法。每只蚂蚁在寻找食物的时候，都会在它经过的路径上释放出一些信息 素，而其它蚂蚁选择这条路径的概率由该路径上信息素的数量决定。那么，较短 路径上的信息素会增加得很快，而较长路径上的信息素增加得很慢。最终，所有 的蚂蚁将选择最短的路径。由于蚁群算法具有较强的正反馈效应、鲁棒性和内在 的分布并行性，且易于和其他方法相结合等优点，使得它非常适合于网格计算中 的任务调度。 文献 2 4 】设计了一个基于蚁群算法的网格任务调度算法。 ( 3 ) 遗传算法与蚁群算法的融合 虽然遗传算法具有比较强的全局搜索能力【2 5 粕】，但无法利用系统中的反馈信 息，求解到一定范围时往往做大量无为的冗余迭代，求精确解效率低，比较适合 前期搜索在大范围内寻找一组粗略解；而蚁群算法采用信息正反馈原理，具有局 部搜索能力强和收敛速度比较快等优点，但初始信息素匮乏，比较适合后期搜索 快速寻找最优解。 文献 1 8 】提出了一个基于融合进化计算的网格任务调度算法，前期采用遗传 算法求解，后期再采用蚁群算法求精确解。 ( 4 ) 人工神经网络 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 用计算机仿真的方法，从 物理结构上模拟人脑，从而使系统具有人脑的某些功能。目前，多层前馈神经网 络模型是应用得最为广泛的人工神经网络模型。 ( 5 ) 模拟退火 模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 是一个建立在金属退火机理之上的全 局最优化方法。它具有较强的局部搜索能力，但它与一般的局部搜索算法不同， 它以一定的概率选择领域中费用值大的状态，从而使搜索过程能够避免陷入局部 最优解。 4 硕士学位论文 第一章绪论 1 3 2 基于a g e n t 的任务调度 上世纪6 0 年代就已经提出了a g e n t 的概念，但是直到上世纪9 0 年代才真正 地发展起来，目前，a g e n t 技术已经渗透到计算机领域的各个方面。 在基于a g e n t 的任务调度中，把网格系统中每个资源结点( 如一个机群) 都 封装成一个a g e n t ，把网格系统看成是一种多层次系统的集合。这样，网格计算 中的任务调度问题就变成如何在各a g e n t 之间分配网格任务并随时根据a g e n t 的变化情况进行调整，以及如何在各a g e n t 内继续分配子任务。由此可见，面向 a g e n t 技术具有良好的可扩展性，非常适合于复杂、分布、异构的网格计算环境 中。 在文献 2 7 】中，作者提出了一种基于a g e n t 的计算网格资源管理算法。 1 3 3 基于p e t r i 网的任务调度 p e t r i 网是德国c a r la d a mp e t r i 首次提出来的，它是一个描述和分析离散事件 动态系统的模拟工具，尤其适合于描述和分析工作流系统等模型。由于网格应用 可以分解为在网格资源上执行的任务的组合，与工作流系统非常类似，所以也常 常使用p e t r i 网来描述和分析网格应用。 1 3 4 其他启发式任务调度算法 除了上面提到的几个网格任务调度算法之外，还有几个常见的经典启发式任 务调度算法，如m i n m i n 算法( 最小最小算法) 、m a x m i n 算法( 最大最小算法) 、 f a s t - g r e e d y 算法( 快速贪吃算法) 和s u f f e r a g e 算法等等。下面我们分别简单地 介绍： ( 1 ) m i n m i n 算法 m i n m i n 算法【2 8 】实现起来非常简单，而且算法的执行速度也很快。该算法的 执行步骤简单描述如下： 1 ) 计算每个未分配任务在各个资源上的期望完成时间，找出每个任务的最 早完成时间以及和它对应的资源； 2 ) 把具有最小最早完成时间的任务分配给相应的资源； 3 ) 分配完成后，更新资源的就绪时间，并将已分配的任务从未分配任务集 合中删除掉； 4 ) 重复执行上面几个步骤，直到分配完所有的任务。 5 硕士学位论文 第一章绪论 令n 为任务总数，m 为可用的资源总数，则m i n m i n 算法的时间复杂度为 o ( ，z 2 研) 。 ( 2 ) m a x m i n 算法 m a x m i n 算法非常类似于上面提到的m i n m i i l 算法。唯一不同的是，m m m i l l 算法是把具有最小最早完成时间的任务分配给相应的资源，而m a x m i i l 算法是 把具有最大最早完成时间的任务分配给相应的资源。显然，m a x m i n 算法和 m i n m i n 算法的时间复杂度相同，也是o ( n 2 ，1 1 。 ( 3 ) f a s tg r e e d y 算法 f a s tg r e e d y 算法是以一种随机的顺序把每个任务分配给对该任务具有最早 完成时间的资源。 ( 4 ) s u f f e r a g e 算法 s u f f e r a g e 算法将已分配到某一个资源的最后一个任务与当前要分配的任务 的忍耐值( s u f f e r a g ev a l u e ) 进行比较，然后优先分配忍耐值大的任务。其中， 任务的次早预期完成时间与最早完成时间的差值称为忍耐值，它表示任务分配与 否对任务期望完成时间造成的影响。 1 4 本文的主要工作 本文的主要工作如下： ( 1 ) 深入分析和研究了网格计算、网格计算中的任务调度算法以及蚁群算法 的原理，为本文的算法奠定了基础。 ( 2 ) 在考虑了时间和费用两项用户q o s 需求的基础上，提出了g c a a 和 g t a a 两个基于改进蚁群算法的网格任务调度算法。 ( 3 ) 用g r i d s i m 实现了本文提出的任务调度算法并进行了一系列对比实验， 验证了本文提出的算法的有效性。 1 5 本文的组织结构和安排 本文的组织结构和章节安排如下： 第一章是绪论，介绍了本文的研究背景、网格计算的研究现状以及网格任务 调度算法的研究现状，接下来对本文的主要工作、本文的组织结构和安排进行了 说明。 第二章首先介绍了网格的概念，然后分析了网格计算中任务调度的特点和主 要目标，最后阐述了网格计算任务调度的过程。 6 硕士学位论文第一章绪论 第三章详细阐述了蚁群算法的原理，然后介绍了蚁群算法在静态和动态组合 优化问题中的应用。 第四章在考虑了时间和费用两项用户q o s 需求的基础上，提出了g c a a 和 g t a a 两个基于改进蚁群算法的网格任务调度算法。 第五章首先简单介绍了五个网格模拟工具，并从不同方面对这几个网格模拟 工具进行了对比，然后重点介绍了g r i d s i m t o o l k i t ，编程实现了第四章提出的任 务调度算法，并进行了一系列对比实验，最后分析了实验结果。 第六章对全文进行了总结，并指出了下一步的研究方向。 7 硕士学位论文 第二章网格计算及其任务调度综述 第二章网格计算及其任务调度综述 2 1 网格的概念 网格的概念是在2 0 世纪9 0 年代中期提出来的，用来表述一种适用于高端科 学与工程的分布式计算体系结构。这种环境下的应用包括满足数据分析等计算需 求的分布式计算( 如构建计算能力和存储资源池等等) 、各种分布式数据集的联 合、大量科学数据的协同可视化( 如构建专家知识库等等) 、科学仪器与远程计 算机和档案库的联合【5 1 。 目前，商业环境中也愈来愈明显地显示出了相似的需求。网格不仅仅用于科 学与工程计算应用中，也用于分布式商业计算应用中，它包括企业内应用的整合、 b 2 b 商业伙伴间的网上合作等等。就像万维网最初是为科研协作而提出的概念和 相关技术、而后来又应用于电子商务中一样，我们可以看到网格技术也正在走着 同样的发展轨迹。 因此，可以断定，不管是科学界还是工业界，都将从网格技术上获益。r r 技 术及其基础设施的根本目的是让我们处理日常事务变得更加有效。在某种程度 上，这些事务的完成依赖于与其他人的协作。网格不只是一种应运而生的技术， 更是我们的基础设施必须发展的方向。 目前，还没有一个关于网格的普遍接受的定义。在文献 1 q u ，i a nf o s t e r 对 网格是这样定义的： 网格是架构在i n t e r n e t 之上的一组新型技术，它融合了高性能计算机、大型 数据库、高速互联网、传感器和远程设备等等，为人们提供更多的资源、功能和 交互性。网格提供比i n t e r n e t 更多更强的功能，它不仅仅为人们提供网页浏览、 电子邮件等等通信功能，还让人们透明地使用计算、存储、网络和各种仪器等其 他资源。 后来，在文献 2 1 q u ，i a n f o s t e r 对网格进一步定义为： 在多个机构组成的动态虚拟组织间实现协作式资源共享和问题求解。 接下来，在文献【2 9 】中，i a nf o s t e r 又对网格提出了新的要求，如下所述： ( 1 ) 网格必须使用标准、开放和通用的接e l 和协议； ( 2 ) 网格必须满足在非集中控制的环境中协同使用资源； ( 3 ) 网格必须提供非平凡的服务。 由于网格必须同时满足上述几个要求，所以像m u l t ic l u s t e r 和p 2 p 等都不再 8 硕士学位论文第二章网格计算及其任务调度综述 属于网格的范畴了【3 0 1 。 关于网格，不同的研究者从不同的角度和侧重点还提出了许多不同的定义， 这里就不再一一细述了。 网格这个概念来源于可随时随地提供电能的电力网格( e l e c t r i cp o w e rg r i d ) 。 人们在使用电能的时候，根本不需要知道电能是从哪个发电厂输送出来的，也不 需要知道这是通过水力、火力、风力还是核反应发电的，人们只要插上插头、打 开开关就能够源源不断地使用电能。这些都是因为电力网使用输电网络把全国的 发电厂、输电站和变电站等整合成一个整体，然后供给人们按需访问，如图2 1 所示。 囹囹豳 电站 豳固敷 煤矿水坝油井 图2 - 1 电力网 网格借鉴电力网，使用互联网络把分散在不同地理位置的资源也整合成为一 个整体，实现计算资源、存储资源、通信资源、数据资源、信息资源、软件资源、 知识资源和专家资源等等的全面共享。这样，人们在使用网格资源的时候就可以 像使用电能一样方便、按需访问了，如图2 2 所示。 9 硕士学位论文第二章网格计算及其任务调度综述 图2 - 2 像用电一样接需访问网格 电力网和网格的详细对比如表2 1 所示。 表2 - i 电力网和网格的对比 电力网网格 发电机 发电厂 水能、风能、火能、核能 电能 输电线 电力调配系统 动力电、照明电、家用电器等 各种电器 高性能计算机、服务器 高性能计算中心、信息中心 数据库、传感器等数据源 信息、知识、交易 l a n 、m a n 、w a n 网格系统软件、中间件 科学计算、电子商务、信息服务等网格应用 网格终端设备 2 2 网格计算任务调度的特点和主要目标 在网格系统中，任务调度系统是其重要的组成部分，它要根据任务信息采用 适当的策略把不同的任务分配到相应的资源节点上去运行。由于网格系统的异构 性和动态性，以及运行于网格系统之中的应用程序对于资源的不同需求，使得任 务调度变得极其复杂，不好的任务分配策略，将会增加任务的执行时间、降低整 个网格系统的吞吐量。 1 0 鼍。辔荔臻一， *掳脯；屠蕊珊娜善*儡强搿缀缓谬 ， ，f f f爹；，#r 硕士学位论文第二章网格计算及其任务调度综述 2 2 1 网格计算任务调度的特点 网格计算任务调度系统具有以下几个特点【6 】： ( 1 ) 任务调度是面向异构平台的。由于网格系统是由分布在i n t e m e t 上的各 类资源组成的，包括各类主机、工作站甚至p c 机，它们是异构的，可运行在 u n i x 、w i n d o w sn t 等各种操作系统下，也可以是上述机型的机群系统、大型存 储设备、数据库或其他设备。因此网格系统中的任务调度必须面向异构平台，并 在这些平台上实现网格任务的调度。 ( 2 ) 任务调度是大规模的、非集中式的。由于网格系统是一个大到整个 i n t e r n e t 的分布式巨系统。要实现一种全局的统一集中的任务调度管理是根本不 可能的。因此，网格的任务调度必须以分布的、并行的方式进行任务的管理与调 度。 ( 3 ) 任务调度不干涉网格节点内部的调度策略。在网格系统中，各网格节点 的内部调度策略是自治的，网格任务调度系统干预其内部的调度策略是没有必要 的，也是不可能的。 ( 4 ) 任务调度必须具有可扩展性。网格系统初期的计算规模较小，随着超级 计算机系统的不断加入，系统的计算规模也必将随之扩大。因此，在网格资源规 模不断扩大、应用不断增长的情况下，网格系统的任务调度必须具有可扩展性， 不致降低网格系统的性能。 ( 5 ) 任务调度能够动态自适应。网格中的资源不但是异构的而且网格的结构 总是不停地改变：有的资源出现了故障，有的新资源要加入到网格中，有些资源 重新开始工作等。总之网格的动态性是明显的，所以任务调度系统必须适应网格 的这种动态性，从可利用的资源中选取最佳资源为用户提供应用服务。 2 2 2 网格计算任务调度的主要目标 简单地说，网格计算任务调度的目标就是要对用户提交的任务实现最优调 度，并设法提高网格系统的总体吞吐率。具体的目标包括：最优跨度( o p t i m a l m a k e s p a n ) 、服务质量q o s ( q u a l i t yo fs e r v i c e ) 、负载均衡( l o a db a l a n c i n g ) 、 经济原则( e c o n o m i cp r i n c i p l e s ) 等【6 j 。 ( 1 ) 最优跨度。跨度是一个最主要、最常见的目标，指的是调度的长度，也 就是从第一个任务开始运行到最后一个任务运行完毕所经历的时间。跨度越短说 明调度策略越好。当用户向网格系统提交任务后，最大的愿望是网格系统尽快完 成自己的任务。可见，实现最优跨度是用户和网格系统的共同目标。 硕士学位论文第二章网格计算及其任务调度综述 ( 2 ) 服务质量q o s 。网格系统要为用户提供计算和存储服务时，用户对资源 需求情况是通过q o s 形式反映出来的。任务管理与调度系统在进行分配调度任 务时，保障网格应用的q o s 是完全应当的。 ( 3 ) 负载均衡。在开发并行和分布计算应用时，负载平衡是一个关键问题。 网格系统更进一步扩展了这个问题。网格任务调度是涉及交叉域和大规模应用的 调度。解决好系统的负载均衡是一个非常重要的问题。 ( 4 ) 经济原则。网格环境中的资源在地理上是广泛分布的，而且每个资源都 归属于不同的组织，都有各自的资源管理机制和政策。根据现实生活中的市场经 济原则，不同资源的使用费用也应是不相同的。市场经济驱动的资源管理与任务 调度必须使消费双方( 资源使用者和资源提供者) 互惠互利，才能使网格系统长 久地发展下去。 2 3 网格计算任务调度过程 一个典型的网格调度至少应包括作业提交、收集可用资源静态信息、资源预 约、资源动态信息查询、制订调度计划和资源初始化以及作业运行时监控等几个 过程【3 1 3 3 1 。 ( 1 ) 作业提交 用户作业的执行通常会涉及到分布式数据、网络资源、存储资源和软件资源 等，另外用户可能对服务的质量有一定的要求，如任务必须在什么时间之前完成。 这些资源需求可以通过脚本语言描述( 如r s l ) 提交给网格调度系统。 用户或应用定义需求后被提交给网格调度服务，网格调度服务负责根据这一 需求找到合适的资源。作业需求描述脚本包含了必要的信息足以判断资源是否能 够满足这一需求。作业描述脚本应该包含三个方面的信息，一是作业本身的属性， 如可以分成几个部分，相互之间的先后关系，一般被并行化理论抽象为d a g 图 的形式；第二是作业的约束条件，如作业完成的时间限制、服务质量等，可能还 有在网格经济模型中的“费用 、“代价 的概念；第三是对实际静态资源的需求， 如要求程序运行的操作系统、最小的内存要求、网络带宽等的要求。 ( 2 ) 收集可用资源静态信息 网格调度系统负责为用户提交的“需求清单 找到合适的资源，包括为作业 进行资源调度、资源预约。无论是系统进行资源自动选择还是由用户参与的交换 选择，都需要考虑到用户和资源拥有者两方面的要求，在满足用户需求的条件下 节约资源的使用。 这一过程主要是发现潜在资源的静态信息。即为用户的作业需求找到匹配的 1 2 硕士学位论文 第二章网格计算及其任务调度综述 资源组合。调度器接收到用户作业的需求报告后将其中的内容解析出来。之后， 网格调度系统通过网格信息服务收集网络上可用的网格资源。此时，调度系统仅 仅进行简单匹配，并不判断这些资源是否处于可用状态。 ( 3 ) 资源预选 经过资源发现阶段可能会得到针对一个作业的许多合适的网格资源，资源预 选的任务就是进行进一步的筛选，使得只有一部分合适的资源能够进一步的进行 匹配。这一过程可以通过许多启发式原则进行自动筛选或者在用户的干预下进 行。例如，用户可能需要在满足任务运行条件的网格资源中选择费用最小的资源 等。 ( 4 ) 资源动态信息查询 作业运行时调度系统需要收集当前的资源信息并依次进行资源使用情况的 预测。如当前资源是否是可用状态，否则预测什么时候可用。如果当前考查的资 源不满足条件，则需要返回上一步对候选的下一个资源组合进行考查。 ( 5 ) 制定调度计划，资源预约初始化 基于资源可用情况、网络带宽和数据准备情祝，调度服务判断哪个资源组合 对作业来说是合适的。这一步骤需要用到一些评价模型来决定资源组合，制订调 度策略，发出资源预约请求。当某一个资源预约过程失败，那么调度器会选择后 备的服务继续这一预约过程。 ( 6 ) 作业运行时监控 复杂的作业运行时间一般比较长，用户应该有权利在任务提交后到执行完毕 的时间内查询任务的运行状态。这是通过作业运行时监控服务来管理的，监控服