（计算机软件与理论专业论文）网格资源三层调度模型与算法研究.pdf

摘要 计算网格作为网格技术最早也是最主要的应用，目前已成为国内 外研究的热点。它最初的目标是通过互连网将超级计算机联合起来， 解决复杂大型科学计算问题；现在，这一目标已演变为通过互连网将 分布在各地的各种不同类型的计算机以合理的方式“粘合刀起来，形 成高度集成的有机整体，向普通用户提供强大的计算能力，将 i n t e r n e t 变为一个功能强大、无处不在的计算设施，使人们在使用网 格计算能力时就像现在使用电力一样方便。网格由大量的异构资源组 成，具有复杂性、动态性和自治性特点。高效的网格调度算法可以充 分利用网格系统资源，提高网格处理应用程序的能力。 本文在分析现有的资源调度方案及模型的基础上，设计出一种网 格资源三层调度系统模型，它由主调度器、次级调度器和资源站点组 成。主调度器根据任务的性质和需求，并参考下层次级调度器的执行 情况，将任务分发到各次级调度器上，实现了主调度器与次级调度器 之间的并行工作。基于该模型设计出反馈调度算法( h b f s ) 。实验结果 表明，h b f s 算法不但可以有效减少不必要的延迟，而且在任务响应时 间的平滑性、任务的吞吐率及任务在调度器等待调度的时间方面比随 机调度等传统算法要好。 关键词资源调度，三层调度模型，任务分发，调度算法 a bs t r a c t c o m p u t a t i o n 酊do r i g i n a l l ya i m e d t oc o m b i n e s u p e r c o m p u t e r st h r o u g h i n t e r n e ts oa st os o l v ec o m p l e xa n dl a r g e s c a l ec o m p u t i n gp r o b l e m s a t p r e s e n t , t h ea i mh a se v o l v e d i n t oc o m b i n i n gv a r i o u st y p e so f c o m p u t e r si n d i f f e r e n ta r e a si nar e a s o n a b l ew a ya n dt h eh i g h l yi n t e g r a t e do r g a n i cu n i t y c a ns u p p l yp o w e r f u lc o m p u t i n ga b i l i t i e st oc o m m o nu s e r s g r i ds y s t e m c o n s i s t so fa 诹d e v a r i e t yo fg e o g r a p h i c a l l yd i s t r i b u t e dr e s o u r c e sa n dt h e s e r e s o u r c e sa r eh e t e r o g e n e o u s ，g e o g r a p h i c a l l yd i s t r i b u t e da n d d y n a m i c a l l y a v a i l a b l e 。h i g he f f i c i e n ts c h e d u l i n ga l g o r i t h mw o u l db ea b l et oi n c r e a s e t h r o u g h p u t ，m a x i m i z es y s t e mu t i l i z a t i o n ，a n df u l f i l le c o n o m i c a ls y s t e m a n du s e rc o n s t r a i n t s t h i sp a p e ra n a l y s e se x i s t i n gr e s o u r c es c h e d u l i n gs t r a t e g y ar e s o u r c e s c h e d u l i n gs y s t e mm o d e lb a s e do nh i e r a r c h i cw i t ht h r e e l e v e lf o rg r i d c o m p u t i n gi sd e s i g n e d ，w h i c hc o n s i s t so fm a i ns c h e d u l e r ，l o w - l e v e l s c h e d u l e ra n dc o m p u t i n gn o d e t h em a i ns c h e d u l e r d i s p a t c h e sap o r t i o n o ft a s k st ot h el o w - l e v e ls c h e d u l e r sa c c o r d i n gt ot h er e q u e s t so ft a s k sa n d t h ee x e c u t i o np e r f o r m a n c eo fl o w - l e v e ls c h e d u l e r s ，w h i c ha c t u a l i z e st h e p a r a l l e l i s mo ft a s ks c h e d u l i n g i nt h i sp a p e r , ah i e r a r c h i cw i t ht h r e e l e v e l b a s e df e e d b a c k 西ds c h e d u l i n g ( h b f s ) a p p r o a c hi sp r e s e n t e d e x p e r i m e n t a l r e s u l t sd e m o n s t r a t et h a tt h i sa p p r o a c hd i m i n i s h e sl a t e n c ya n dc o n t r i b u t e s t ot h eo v e r a l l 鲥dl o a db a l a n c i n g ，w h i c hs i g n i f i c a n t l yi m p r o v e sr e s o u r c e u t i l i z a t i o na n d r e s p o n s et i m eo f t a s k s k e yw o r d sr e s o u r c es c h e d u l i n g ，t h r e e - l e v e ls c h e d u l i n gm o d e l ， t a s kd i s t r i b u t i n g ，s c h e d u l i n ga l g o r i t h m i l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特另j d r i 以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：趁丝日期：丝竺年上月堑日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 硕士学位论文第一章绪论 1 1 研究的背景和意义 第一章绪论 网格【l 】技术是近年来迅速兴起的一门新技术，它的出现掀起了下一波互连网 技术的浪潮。计算网格作为网格技术最早也是最主要的应用，目前已成为国内外 研究的热点。它最初的目标是通过互连网将超级计算机联合起来，解决复杂大型 科学计算问题；现在，这一目标已演变为通过互连网将分布在各地的各种不同类 型的计算机以合理的方式“粘合 起来，形成高度集成的有机整体，向普通用户 提供强大的计算能力，将i n t e m e t 变为一个功能强大、无处不在的计算设施，使 人们在使用网格计算能力时就像现在使用电力一样方便。 同时，随着网格技术的推广，网格服务市场逐渐形成，计算网格提供的计算 能力演变为一种像电视、电信、供水、供电这样的资源服务，人们在使用网格提 供的计算能力时必须购买。然而，在网格环境中，有大量不同需求的应用和大量 广域分布的计算资源，这些资源没有全局的控制中心和统一的价格机制，且动态 变化，这样，网格调度就不仅要考虑如何按时完成用户的应用，同时还要考虑如 何来协调资源提供者和需求者之间的利益。 “关于计算网格调度模型的研究这一课题就是在这种背景下确立的，旨在 尝试探索一种能够适应计算网格环境并能较好协调各方利益的调度模型。这一课 题跨度很大，既要求对网格相关的理论有一个清晰的了解，还要求对分布式系统 的设计、网络计算、并行设计、代理技术、数据库系统等相关知识有较强的把握。 通过这一课题的实施，对传统分布式系统和网格系统的调度器进行了总结，同时 提出了一个基于代理的计算网格调度系统模型，笔者认为本课题的确立和完成将 在网格调度领域做出一些有益的探索。 1 2 网格的研究现状 目前网格的研究主要集中在美国和欧洲。英国政府已投资l 亿英镑，用来研 制英国国家网格( u kn a t i o n a lg r i d ) 一。欧洲的d a t a g r i d 2 1 涉及到欧盟的2 0 几个国家，是一种典型的“大科学”应用平台。目前美国和欧洲在美国政府用于 硕士学位论文第一章绪论 网格技术基础研究经费则己达5 亿美元。美国军方芷瓶划实施一个宏大的两格计 划，叫做“全球信息网格( g l o b a li n f o r m a t i o ng r i d ) 3 1 ，预计在2 0 2 0 年完成。 美国政府电子信息技术协会的一位负责入预测，到2 0 0 6 年，g i g 有爵能成为五 角大楼的最大投资项目。作为这个计划的一部分，美国海军和海军陆战队己启动 了一个耗资1 6 0 亿美元历时8 年的项曩，包括系统的研制、建设、维护窝舞级。 除了上述国家级的项目和系统外，很多世界著名的公司也都非常关注网格的 发展。惠普、i b m 、微软、s u n 等公司最近取得共识，支持x m l 4 1 、s o a p 5 1 、 u d d i 6 等标准，从而更有利于开发新一代的网络应用，即网格服务。其目的是 将互联网上的资源和信息汇聚在一起，组合成企业和消费考所需要的服务。惠普 推出了e s p e a k 服务平台；m m 用它的w e bs p h e r e 平台和一系列中间件实现万维 网服务；微软的路线是通过其n e t 计划和c 撑语言实现；s u n 则通过o p e nn e t w o r k e n v i r o n m e n t ( s u n 饼咂) 计划和j a v a 平台来实现它。另外，i b m 已经宣布将投 资4 0 亿美元，启动一个“网格计算创新计划，丽s u n 则在2 0 0 0 年9 月就公布 了其网格引擎软件。 翻前在国外的网格计算研究项目中，一些通用的网格技术研究和项目有： a c c e s sc , r i d t 霸， c o n d o r s l ，e c o g r i d t 9 ，g l o b u s 1 0 1 ，l e g i o n t 吲，n m i 计划；一些 网格应用和库有：n e o s ，n e t s o l v e 1 2 1 ，n i m r o d g t l 3 】，p u n c h ；还有一些商业界 在网格计算方面的努力，包括p 2 p 工作组，a v a k i ，e n t r o p i a ，g r i d w a r e ，i n s o r s 。 在日本的网格项目有n i “1 4 1 。 网内的网格计算尚处于研究阶段，主要集中于中科院计算所、国防科大、江 南计算所、清华大学、山东大学等几家在高性能计算方面有较强实力的研究单位。 目前，我国已启动了五个阏格项霉，科技部负责的中匡国家国格( c n g r i d ) 、 教育部负责的中国教育科研网格技术( c h i n a g r i d ) 、国家自然科学基金委负责 的e s c i e n c e 网格研究计划、上海信息网格、中国空间信息网格。其中，中国国 家网格( c n 硎d ) 由国家8 6 3 高技术研究发展计划资助，旨在建立面向企业、 高等院校、科研机构、政府部 j 的国家高性能计算环境。中国教育科研网格项霉 是“c e r n e t 高速地区网和重点学科信息服务体系建设 项目中的重要建设内 容，是迄今为止由政府推出的最宏大的瞒格工程。c h i n a g r i d 的蜀标是在2 0 0 5 年 建立聚合能力超过1 5 万亿次量级的教育科研网格，形成世界上最大的超级网格 之一，并争取在网格计算的基础研究和应用研究方面走在世界前列。 2 硕士学位论文 第一章绪论 1 3 本文的主要研究内容 本论文的研究目标是：在众多不确定因素的网格环境中，高效率的调度具有 自治性和动态性的网格资源以完成用户提交的各种任务。高效率指两个方面，一 是在调度时尽可能地缩短总的任务完成时间和任务平均完成时间；二是在尽可能 满足用户的q o s 要求。 本文的主要工作： ( 1 ) 详细分析了网格资源调度的过程，提出并设计了网格资源三层调度系统 模型。 ( 2 ) 在该模型中提出并采用了一种新的“上访下察 资源收集策略。 ( 3 ) 提出基于该模型的任务分发策略。 ( 4 ) 基于该调度模型设计出相关的资源调度算法。资源选择算法能有效进行 资源调度，即将任务提交到性能较优的资源站点上，而避免将任务调度 到负载较高或已经失效的资源站点上。 ( 5 ) 对该模型及算法进行了详细设计，并在网格调度模拟器中加以检验，实 验结果说明该调度模型及调度算法在各方面都优于集中式随机调度方 法。 1 4 本文章节安排 全文共分七章。 第一章是绪论，介绍本文所涉及课题的研究背景和意义、国内外研究现状、 作者的主要工作以及整个文章的章节安排。 第二章介绍目前网格调度方面的相关研究：包括网格资源的含义、特点，资 源调度的特点、调度目标等。 第三章详细介绍了当前常用的网格调度模型及算法。 第四章详细介绍了网格资源三层调度系统模型。包括总体结构，工作流程、 详细设计、基于该模型的任务分发策略等。 第五章详细介绍了三层调度系统模型中所涉及的一些主要调度算法。 第六章是利用流行的网格调度模拟器进行模拟实验及结果分析。 第七章是全文总结。 硕士学位论文 第二章网格调度相关研究 第二章网格调度相关研究 任务调度系统是网格资源管理系统的核心组件，它负责接收用户的任务请 求，并选择适当的资源运行用户任务。任务调度算法用来决定采用何种调度策略 进行资源一任务匹配。它是个n p 完全问题。本章介绍网格调度的相关研究，主 要包括阙格资源的特点、资源调度的特点及主要翳标、现有的调度策略与算法。 2 。1 网格资源 嬲格调度涉及到任务及资源两个方面，即将用户的任务提交到各资源节点上 执行，因此网格资源对调度来说是一个非常重要的概念。本节将介绍网格资源的 含义及特点。 2 i 1 网格资源的含义 “资源 通常被定义为系统中的可参与计算的元素，包含硬件计算资源和软 件计算资源等等。硬 睾资源主要是处理器、存储器等。软傅资源包括各种应惩程 序、文件、数据、代码等。 本文依据o g s a 关于“一切都是服务的观点，把计算资源抽象热计算服 务，将对计算资源的访问限制到一组定义良好的操作，是一种网格服务( g r i d s e r v i c e ) 。对计算资源的共享体现为对计算服务的共享，多今计算资源协同鳃决 问题也体现为多个基本的计算服务协作来提供更高级别的满足协同要求的服务。 概括地说，资源是一种能够提供服务的实体。 2 1 2 网格资源的特点 无论是简单的计算机系统还是复杂的集群系统、并行系统、分布式系统都存 在着不同的资源，但是那些资源无论是种类的多样性还是功能的多样性方面，都 不能和网格系统相比。网格中的资源具备了以往系统中的资源所不具备的特点， 网格资源具体有如下特点： ( 1 ) 分布与共享分布性是指网格的资源是分布在地理位置互不相同的地 硕士学位论文第二章网格调度相关研究 方，而不是集中在一起，它决定了基于网格的计算一定是分布式计算而不是集中 式计算。共享是指网格上的任何资源都可以提供给任何使用者。共享是网格的目 的，解决分布资源的共享问题是网格的核心内容。网格资源共享的方式也不同于 传统的共享，传统的共享往往停留在文件传输的层次，而网格资源的共享允许直 接控制其他资源。 ( 2 ) 多样性是指网格资源是异构和多样的，即在网格环境中可以有不同体 系结构的计算机系统和类别不同的资源，因此网格系统必须要能够解决这些不同 结构、不同类别资源之间的通信和互操作问题。 ( 3 ) 资源具有动态性 资源可以自由地加入网格和离开网格系统，网格资源的可获得性以及一个网 格资源提供给用户使用的能力是随时间的变化而动态变化的，网格资源的负载也 是动态变化的。 ( 4 ) 资源既是私有的又是可共用的资源是由资源拥有者提供的，资源的拥有 者对该资源有最高的使用权限，但是该资源又是网格中的资源要被网格用户共 享。 ( 5 ) 自治性与管理的多重性 网格上的资源首先是属于某一个组织或者个 人的，因此网格资源的拥有者对该资源具有最高级别的管理权限和自主的管理能 力，这就是网格的自治性。管理的多重性是指资源不仅可以被拥有者自主管理网 格，也必须接受网格的统一管理，才能实现共享和互操作。 2 2 网格资源调度的特点及主要目标 网格的资源调度不同于其他的调度，它有其自身的特点和目标，本节介绍网 格资源调度的特点及主要目标。 2 2 1 网格资源调度的特点 网格计算资源调度系统具有以下几个特点： ( 1 ) 资源调度是面向异构平台的。由于网格系统是由分布在i n t e m e t 上的各 类资源组成的，包括各类主机、工作站甚至p c 机，它们是异构的，可运行在 u ni x ，w i n d o w sn t 等各种操作系统下，也可以是上述机型的机群系统、大型 存储设备、数据库或其他设备。因此网格系统中的任务调度必须面向异构平台， 硕士学位论文第二章网格调度相关研究 并在这些平台上实现网格任务的调度。 ( 2 ) 资源调度是大规模的、非集中式的。由于网格系统是一个大到整个 i n t e m 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 d b 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 ) 等【i 5 1 。 ( 1 ) 最优跨度。跨度是一个最主要、最常见的西标，指的是调度的长度，也 就是从第一个任务开始运行到最后一个任务运行完毕所经历的时间。跨度越短说 明调度策略越好。当用户向网格系统提交任务后，磺大的愿望是网格系统尽快完 成自己的任务。可见，实现最优跨度是用户和网格系统的共同目标。 ( 2 ) 服务质量q o s 。网格系统要为用户提供计算和存储服务时，用户对资源 需求情况是通过q o s 形式反映出来的。任务管理与调度系统在进行分配调度任 务时，保障网格应用的q o s 是完全应当的。 ( 3 ) 负载均衡。在歼发并行和分布计算应用时，负载平衡是一个关键问题。 网格系统更进一步扩展了这个阀题。网格任务调度是涉及交叉域和大规模应用盼 调度。解决好系统的负载均衡是个非常重要的问题。 6 硕士学位论文 第二章网格调度相关研究 ( 4 ) 经济原则。网格环境中的资源在地理上是广泛分布的，而且每个资源都 归属于不同的组织，都有各自的资源管理机制和政策。根据现实生活中的市场经 济原则，不同资源的使用费用也应是不相同的。市场经济驱动的资源管理与任务 调度必须使消费双方( 资源使用者和资源提供者) 互惠互利，才能使网格系统长 久地发展下去。 7 硕士学位论文第三章网格环境下现有调度模型及算法 第三章网格环境下现有调度模型及算法 本章首先对网格调度模型及调度过程进行描述和分析，然后就当前三种具体 的调度模型进行比较，分析它们的优点和不足之处。接下来分析了现有的调度算 法的优缺点，最后通过小结提出了一种改进的基于层次式的三层调度模型。 3 1 调度系统的总体框架 在网格环境下，任务调度的目的是得到尽可能小的总执行时间。对于用户来 说，他不关心其请求具体由哪些资源完成，丽只关心他的请求是否能够尽快返回。 对于网格调度器，它负责查找信息服务、获取服务信息，并调度合适的资源来完 成用户的请求。调度模型的总体框架如图3 1 【1 q 所示。 璎3 - 1 调度累统的总体框架 从用户角度来看，任务的响应时间包括用户提交任务给调度器的时间、调度 器与信怠服务器通信所导致的时阂、任务提交绘资源节点到资源节点执行完任务 返回结果的时间等。因此，网格环境下一个任务在理想情况下的响应时间可以定 义为f 1 7 1 t r = t ”+ r 矽+ 丁g 缁+ r 撂+ r g s + r s + r e公式( 4 1 ) 8 硕士学位论文第三章网格环境下现有调度模型及算法 下面就上述公式中的各个分量做详细解释与分析。公式中，g 代表网格调度 器，四代表信息服务器，s 代表执行任务的远程资源，r 。代表用户请求提交到 调度器的时间以及处理结果从调度器返回给用户的时间之和，丁矿是指任务在调 度器上的等待时间，丁g + + 俗表示网格调度器与信息服务器通信所花费的时间，丁腰 表示在信息服务器上寻找合适的远处资源所花费的时间，r g 郴表示网格调度器 提交任务到远程资源以及任务在资源上执行完后返回结果给调度器所花费的往 返通信时间，丁s 一矿表示任务在资源的任务队列上等待调度的时间，而丁e 表示任 务在资源上的执行时间。 实际上，由于网格中的资源具有自治性和动态性【l 引，如果碰到资源忙或资 源失效的情况，那么调度器需要重新调度。换言之，并非所有的任务都能一次就 能调度成功。一次成功的调度可能包含多个不成功的调度，因此可在上述公式的 一些分量上乘以一个系数。修改后符合调度实际情况的任务响应时间公式如下： t r = t 。+ 丁矿+ c t ( t g ”腰+ 丁四) + f l ( t g 付s + t s - w ) + r e 公式( 4 2 ) 其中，a 、b 表示不同的系数。 3 2 现有调度模型的比较 网格调度模型主要是指图3 1 中网格调度器的内部组织结构【1 9 】。目前，网格 计算环境下资源调度的模型主要有三种：集中式、层次式与分布式调度【2 0 】。 在集中式调度模型中，只有一个网格调度器，网格调度的所有工作均在该调 度器上执行，网格调度器直接向资源站点提交要执行的任务。网格调度器知道所 有站点的信息，并且负责调度网格中的所有资源，所有任务都提交给网格调度器。 该调度模型的优点是易于实施和管理，易于实现资源的协同分配。而缺点是维护 代价高，难于实现容错。而且该调度方案扩展性较差，当网络比较大时，调度 系统很难掌握所有的资源，调度系统便会成为瓶颈【2 。比如由于错误使得调度 系统出现故障，就会影响整个网格系统。 在分布式调度模型中，网格调度系统有多个调度器，各调度器之间是平等的。 它的优点是可扩展性较好，可靠性比较高，易于容错，支持资源自治和多种调度 策略结合使用，但不易于管理和资源协同分配【2 2 j 。缺点是各调度器之间的通信量 很大，也不能掌握网格中所有资源，因而很难找到全局最优的资源分配方式。 在层次式调度模型中，设置一个任务主分发器，它负责将任务提交给下级调 9 硕士学位论文第三章网格环境下现有调度模型及算法 度器进行调度1 2 引。同时在任务主分发器下再设置一个任务分发器受其控制，该 任务分发器负责从主分发器接受任务，再将任务提交给它管辖的下级调度器。 层次式调度模型可扩展性和容错性较好，在任务分发器下还可再设置第三级 任务分发器。由于在任务主分发器下又设置了任务分发器，因此该方案适合于一 类包含大量任务的用户应用，使系统能响应更多的请求，一定程度上缓解了一些 任务长时间等待而得不到系统响应的矛盾。虽然该方案纵向扩展性较好，但由于 涉及到的层次越多，各层次间通信量越大，而且调度系统很难监控底层的调度情 况，也不利于出现各种差错的及时反馈。 3 3 现有的调度算法 围绕着网格中的任务调度，国内外已做了许多研究工作，先后提出了各种调 度算法。 这些算法按照调度策略可以分为动态调度( d y n a m i cs c h e d u l i n g ) 和静态调度 ( s t a t i cs c h e d u l i n g ) 两种 2 4 1 。动态调度是任务一到来就加以映射；而静态调度则是 把任务收集起来，等映射事件到来后才对这些任务进行集中映射。按网格调度的 度量依据主要有基于时间、经济【2 习以及其他度量指标( 如公平性、稳定性、健 壮性等) 的调度。此外，还有将多种调度准则综合在一起的调度方法，如q o s ( q u a l i t yo f s e r v i c e ) 2 5 - 3 0 1 等。根据调度算法所应用于任务调度的阶段，调度算法 可分为应用于预处理阶段的算法和调度及重调度阶段算法。 静态调度算法主要有f i f o ，m i n - m i n t 3 1 3 4 1 ，m a x m i n t 3 2 - 3 4 ，g r e e d y ， s u f f r a g e 3 1 1 ，x s u f f r a g e 3 5 1 ，p r i o r i t y ，t c r ( t r a n s f e rc o m p u t a t i o nr a t i o ) 【3 6 】，u d a ， b a c k f i l l i n g 等。 静态调度算法需要花费大量时间计算任务调度表，算法缺少灵活性。任何变 化，如任务添加、删除或任务特征变化，都需要重新计算调度表。而且静态调度 算法每隔一定周期进行一次调度，因此，越早到达的任务等待的时间越长，从而 使得任务的响应时间过长。总之，静态调度的主要特点是实现简单，但调度质量 不佳。 常见的动态调度算法有m e t ( m i n i m u me x e c u t i o nt i m e ) 3 2 】，m c t ( m i n i m u m c o m p l e t i o nt i m e ) 3 2 】，d l s ，s a ( s w i t c h i n ga l g o r i t h m ) 【3 2 ，3 6 1 ，k p b ( k - p e r c e n tb e s t ) ， o l b ( o p p o r t u n i s t i cl o a db a l a n c i n g ) 1 3 4 】，r e s e r v a t i o n 。 1 0 硕士学位论文第三章网格环境下现有调度模型及算法 与静态调度算法相比，动态调度算法的环境适应性好，在多种环境下操作性 能良好，算法灵活。动态调度的主要特点是能充分发挥各资源节点的处理能力， 但实现起来比较复杂，可能由于任务的动态调整影响个别任务的执行效率。尽管 如此，动态调度算法还是更适合于网格环境。许多网格中间件，如c h i n a g r i d 支 撑平台c g s p ( c h i n a g r i ds u p p o r tp l a t f o r m ) ，v e g a u ，c r o w n ( c h i n ar e s e a r c h a n dd e v e l o p m e n te n v i r o n m e n to v e rw i d e r a r e an e t w o r k ) 3 s j ，g l o b u st o o l k i t 等，也 采用的是一种动态调度模式。 除了以上的算法之外还有启发式调度算法，主要包括遗传算法【3 8 】、模拟退 火算、法【3 9 1 、蚁群算法 4 0 l 等。 下面介绍当前主要的一些调度算法。 ( 1 ) 先进先出调度算法( f i r s tc o m ef i r s ts e r v e ) 先进先出调度算法是任务到达的顺序即是任务执行的顺序，每次挑出资源中 最快的机器分配给任务来执行。缺点是该算法没有考虑任务的优先级别，用户提 交任务是定义的最终完成期限，也没有考虑任务的长短给任务执行时间带来的影 响。当网格中主机的数量增加时，该算法的复杂性将呈指数增长。 ( 2 ) 遗传算法( g e n e t i ca l g o r i t h m ) 遗传算法是建立一个调度的集合并从其中找出优化的调度，将这种特性遗传 给下一代。遗传算法利用固定的大量数据和随机的挑选，通过适应函数交叉和重 组得出最优的调度。这是一种迭代的算法，它的优点是在它不断进化的过程中吸 收系统的改变，能够适应动态变化的网格系统，比如增加或删除任务，节点速度 和状态的改变。但该算法的缺点是“早熟现象和慢速收敛性，需要根据网格的 具体调度环境来调整选择和变异策略，也未能很好地解决负载平衡等一些问题。 ( 3 ) m n m i n 和m a x m i n 算法 m i l l m i i l 算法是一种实现起来很简单的算法，算法的执行时间也很快。该算 法的目的是将大量的任务指派给不仅完成它最早，而且执行它最快的机器。算法 的思想是首先映射小的任务，并且映射到执行快的机器上。执行过程为：计算要 参与映射事件的任务集中每个任务在各个机器上的期望完成时间，找到每个任务 的最早完成时间及其对应的机器；从中找出具有最小最早完成时间的任务，将该 任务指派给获得它的机器；指派完成后，更新机器期望就绪时间并将已完成映射 的任务从任务集合中删除。重复上面的过程，直到所有的任务都被映射完。m i n - r a i n 算法完成一次映射事件的时间复杂度为o ( n 2 m ) ，其中n 为一次映射事件需 硕士学位论文第三章网格环境下现有调度模型及算法 要完成映射的任务总数，m 为可用的机器总数。 m a x m i i l 启发算法非常类似于上面提到的m m m i i l 启发算法。同样要计算 每一任务在任一可用机器上的最早完成时间。不同的是m a x m i n 算法首先调度 大任务。任务到资源的映射是选择最早完成时间最大的任务映射到所对应的机器 上。时间复杂度同m i n - m i n 一样也为o ( n 2 m ) ，其中n 为一次映射事件需要完成 映射的任务总数，m 为可用的机器总数。 ( 4 ) 蚁群算法是1 9 9 2 年由意大利学者d o r i g om 等人首先提出的。它是对自 然界蚂蚁寻径进行模拟而得出的一种模拟进化算法。该算法不依赖于具体问题的 数学描述，具有很强的全局优化能力和本质上的并行性，是解决n p 完全问题的 有效方法。蚁群算法具有正反馈性和协同性的特点。它具有本质的并行性，易于 并行实现。具有较强的鲁棒性，为求解复杂的组合优化问题提供了新的思路。此 外，它还容易与其它算法结合，以改进其性能。然而，基本蚁群算法的计算时间 较长，易出现停滞现象，易陷入局部最优解，而找不到全局最优解。基本蚁群算 法中各参数的选取有一定的难度，只能靠经验或实验值取得，而没有合适的理论 依据。 ( 5 ) 神经网络算法 神经网络由于其非线性处理能力强，性能稳定等特点得到了广泛应用和研 究。主要应用于模式识别、信号处理、知识工程、专家系统、优化组合、机器人 控制等。神经网络中使用最为广泛的就是前馈神经网络。其网络权值学习算法中 影响最大的就是误差反向传播算法( b a c k - p r o p a g a t i o n 简称b p 算法) 。b p 算法 存在局部极小点，收敛速度慢等缺点，所以各种改进的b p 算法纷纷出现。如可 变的学习速率，以提高算法的收敛速度，对于局部极小点问题，很多研究重点是 神经网络与进化算法结合。 网格任务调度与负载平衡是提高网格计算环境可用性和效率的关键问题， n i m r o d g 、a p p l e s 和c o n d o r - g 【4 1 】等网格任务调度器都基于特定的调度策略， 适用于特定情况的任务调度。g l o b u s 任务调度方法基本是轮循方式的；n i m r o d g 采用应用程序级的基于微观经济模型的调度方法，适用于各个资源的定价机 制都很完整的情况；a p p l e s 采用应用程序级的调度方法，用网络气象服务监测 资源性能的动态改变情况作为任务调度的依据，信息维护代价较高，且要求各节 点间的连接都具有监测机制；c o n d o r g 要求每个资源代理周期性广播其可提供 1 2 硕士学位论文第三章网格环境下现有调度模型及算法 的服务，客户代理广播其需求，匹配器执行集中式的任务到资源之间的匹配调度。 3 4 小结 本章着重分析了当前常用的网格调度的模型及算法，但目前的调度模型及算 法在如下几个方面未作有效考虑： 首先，目前的调度算法均要求能够控制网格节点，这在网格环境下是很难做 到的；其次，网格调度器在进行任务调度时假设资源的状态如性能、可用性等不 作改变，这一点并不符合网格的实际情况。实际上，网格资源的性能与可用性均 处于变化之中：第三，假设在调度过程中可用资源一成不变，不考虑资源的退出 或完全失效与新的可用资源的加入，这也不符合网格的实际情况；最后，大多数 网格调度算法未考虑网络通信延迟。 这些因素使得目前的网格调度算法在调度时效性和适用性方面存在一定的 缺陷。针对目前网格调度机制存在的这几个问题，本文提出了一种改进的基于层 次式的网格调度模型网格资源三层调度模型。 硕士学位论文 第四章网格资源三层调度模型 第四章网格资源三层调度模型 在一定q o s 条件下，使任务的响应时间尽可能地短是调度系统的一个重要 目标。为此，本文提出了一种改进的基于层次式的网格资源三层调度模型。本章 将具体介绍该模型的基本目标、总体结构、组成、功能设计以及在该模型中所需 的任务分发策略等。 4 1 模型概述 本节介绍网格资源三层调度模型的基本目标、总体结构、工作流程和消息传 递机制。 4 1 1 模型的基本目标 本文提出的三层调度模型所要达到的目标主要是： ( 1 ) 为资源选择提供准确、可靠和快捷的查询服务，避免将任务调度到性能 较差甚至完全失效的资源上； ( 2 ) 尽可能地缩短任务在调度器中的等待时间以及总的任务响应时间； ( 3 ) 支持各种任务调度算法和资源选择算法； ( 4 ) 支持重调度机制； ( 5 ) 具有一定的容错性。 4 1 2 模型的总体结构 三层调度系统模型结构如图4 - 1 所示，第一层是一个主调度器：第二层由若 干个次级调度器组成，主调度器并不负责直接调度任务，而是将任务分发给各次 级调度器；第三层是底层的资源站点，具体负责完成分配的任务，并返回结果。 由于网格计算的规模很大，第二层的次级调度器不能太少也不能太多。次级 调度器分别分布在与主调度器不同的机器上。而且如果某个次级调度器出现故 障。主调度器可以重新调度。这样增强了整个系统的容错性，使其更加健壮、可 靠，同时该模型大大减轻了调度策略的负载。 1 4 硕士学位论文第四章网格资源三层调度模型 图4 - 1 三层调度系统模型总体框架 主调度器的主要功能是： 乱接受用户应用请求，访问g i s 获取和存储网格； b 监控次级调度器当前的状况，根据q o s 要求执行任务分发策略，将任务 分发给适当的次级调度器； c 监控执行情况，接收执行结果，对于未能完成的任务依据策略考虑是否 重新分发和调度； d 向用户提交执行结果。 次级调度器的主要功能有： a 接收主调度器分发的任务，分析各个任务的资源请求类型及任务之间的 耦合关系，把所有的任务进行解析和分解，降低任务之间的耦合度，减少通信开 销： b 请求系统信息服务，匹配资源请求，定位资源并进行调度； c 监控任务执行状况，接收执行结果； d 向主调度器提交执行结果，将未能完成的任务返回给主调度器重新调度； e 将资源状况反馈给主调度器。 1 5 硕士学位论文 第四章网格资源三层调度模型 4 1 3 调度系统的工作流程 调度系统工作流程是： ( 1 )用户通过任务提交p o r t a l 来提交任务给调度系统。 ( 2 )主调度器接收到任务后将任务信息存储到任务及资源信息数据库。 ( 3 )主调度器接启动一个线程不断地访问g i s 来获取网格信息。 ( 4 )主调度器将获取到的网格资源信息进行整理和筛选并存入或更新任务及 资源信息数据库。 ( 5 )主调度器启动另外一个线程根据一定的目标如q o s 要求执行任务分发策 略，将接收到的任务分发给各个次级调度器。 ( 6 ) 各次级调度器对接收到的任务进行解析并分解成一组可执行的相互独立 的子任务。 ( 7 ) 分解后的子任务被次级调度器置入一个等待队列准备调度。 ( 8 )次级调度器从等待队列中提取一个任务，并访问主调度器中的任务及资源 信息数据库，从中选择最佳的资源并将该任务提交给这个资源。 ( 9 )若次级调度器中的等待队列还有尚未调度的任务，则重复上一步骤。 ( 1 0 ) 各次级调度器等待资源节点返回任务执行结果。 ( 1 1 ) 一旦有结果返回给次级调度器后，该次级调度器便根据这次返回的结果， 将返回结果的资源的信息及时反馈给主调度器，主调度器将该资源节点的 信息存入任务及资源信息数据库中，以供所有的次级调度器今后访问。另 一方面，如果某次级调度器当前最先调度的任务经过一定时间后尚未返回 结果，则启动重调度机制，将该资源节点上的任务队列中的所有任务进行 重新调度。并且反馈该资源节点的信息给主调度器。主调度器便将该资源 节点不可用的信息存入任务及资源信息数据库，这样其它的次级调度器今 后一段时间内不会将任务提交给该资源节点。 1 6 硕士学位论文第四章网格资源三层调度模型 为了更直观地描述，图4 2 是调度系统工作流程图。 用户提交任务 收集任务信息并存入数据库 主调度器分发任务 主调度器访问g i s 获取并处理网格信息 将资源相关信息存入数据库 次级调度器接收任务并置入接收队列 接收队列 是否为宅? f 次级调度器解析任务并置入调度队列 y 调度队列 是否为它? in 次级调度器访问数据库，荻取可用资源 次级调度器执行调度算法进行任务调度 资源站点返回结果给次级调度器 次级调度器将结果返 回给主调度器 主调度器整理结果并 返回给用户 次级调度器分析结果返回时 间，荻取并反馈资源状况 调度器将反馈信息加以 整理并存入数据库 图4 - 2 调度系统工作流程图 1 7 硕学位论文 第四章网格资源三层调度模型 4 。 。4 调度系统的消息传递枧制 在已有的调度策略中，资源站点的负载信息是由调度器主动去收集，这增加 了调度器的负载。三层调度系统模型改进了这一方式，第三层资源站点定时收集 自身的负载及所需传递的数据等信息发送给相应的次级调度器，次级调度器及时 对相关消息进行处理，并传递给主调度器。主调度器接收到相关信息后，随之进 行相应的调整。 由于各次级调度器对从用户接收来的任务经过了一定的解析和分解，但不能 完全消除任务之间的耦合关系，所以需要各任务之间有时需要进行通信获取相关 数据。 因此，调度系统模型的消息处理机制比较重要，需要考虑跨组通信的情况。 如果资源菇点反馈的信息其磊的地不在本组内，则该次级调度器应把该消息转发 给主调度器。主调度器根据消息的目的地选择适当的次级调度器，然后把消息发 给这个次级调度器，由它进行处理。 4 。2 三层调度模型的设计 本节将具体介绍三层调度模型的设计，主要包括模型的组成、模型的功能设 计和数据库设计。 4 。2 模型的缓成 在上一节中已经介绍了该模型的总体框架，本节将详细介绍模型中的各组成 部分及详细架构。模型中主调度器与次级调度器上的的详细架构如图4 3 所示。 主调度器由任务接收器、信息采集器、任务分发器、饪务队列、任务与资源 信息数据库组成。 次级调度器由任务接收器、任务解析器、信息采集器、任务调度器、任务接 收队列、任务调度队列组成。 1 8 硕士学位论文 第四章网格资源三层调度模型 主 调 度 器 次 级 调 度 器 图4 3 三层调度系统模型架构( 只画出一个次级调度器) 4 2 2 模型的功能设计 ( 一) 任务提交p o r t a