（通信与信息系统专业论文）基于改进遗传算法的网格任务调度研究.pdf

武汉理工大学硕士学位论文 摘要 网格是当前并行与分布式计算技术的一个重要发展方向，其目标是实现对 地理上广泛分布的大量异构资源进行共享。由于网格中的资源具有分布性，共 享性，自相似性，动态性，多样性，自治性与管理的多重性等特点，因此为了 使网格能够达到最好的性能，有效减少网格任务的完成时间以及其它目标，网 格研究者研究出了多种网格任务调度算法，如遗传算法，m i n m i n 算法，模拟退 火算法等。同时，现在网格仿真工具己经越来越多的被用来帮助网格系统的设 计者验证设计方案及测试网格系统性能，特别是其中模拟任务调度部分的仿真 工具更成为研究的热点。 本文在介绍网格和网格任务调度的基本概念，特点的基础上。详细研究了 基于p a c e 网格性能预报系统的t i t a n 网格体系结构，讨论了目前典型的网格 技术与资源管理系统，并且在现有的遗传算法设计框架下，对遗传算法的初始 种群生成方式提出了一些改进，以达到减少遗传算法运行迭代次数，并提高遗 传算法的运行速度的目的，同时，通过对任务总执行时间跨度，资源空闲时间， 和用户完成期限时间的考虑，提出了带有参数的适应度函数，以满足调度算法 对这些需要的适应程度。由于在网格任务调度的研究中，没有必要使用实际系 统来对算法的正确性和性能进行验证，所以仿真器就用来完成这一工作。本文 详细介绍了g r i d s i m 这一网格建模与仿真工具箱和网格模拟器的体系结构，建模 仿真机制和仿真过程以及各个模块的实现方法。最后，本文在g r i d s i m 工具箱的 帮助下，使用j a v a 语言实现了改进的网格任务遗传调度算法仿真。实验结果表 明，本文提出的改进遗传调度算法是可行的，在传统遗传算法的基础上，提高 了调度的性能。 当然，本文的研究只是网格改进遗传任务调度算法的一个初步尝试，在研 究中没有考虑网格实际情况下的任务问通信，资源间通信，以及支持网格运作 的网络状况这些方面的因素影响。另外在网格环境中，如何将各种指标进行分 类、如何选择合适的调度频率以达到优化的目的、如何在实际的网格系统中应 用算法等，仍然需要作进一步的研究。 关键词：网格，遗传调度算法，性能预报系统，g r i d s i m ，仿真 武汉理工大学硕士学位论文 a b s t r a c t 而口g r i dc o m p u t i n ga i m st op r o v i d ea l li n t e g r a t e dc o m p u t e rp l a t f o r ma m o n g l a r g en u m b e ro fh e t e r o g e n i cr e s o u r c e s ，a n dh a sb e c o m i n ga ni m p o r t a n td e v e l o p m e n t t r e n df o r p a r a l l e l a n dd i s t r i b u t e dc o m p u t i n gt e c h n o l o g y ，a st h e c h a r a c t e r s o f d i s t r i b u t e da n ds h a r e d ，s e l f - r e s e m b l i n g ，d y n a m i ca n dd i v e r s e ，a u t o n o m o u sa n d m a n i f o l dm a n a g e m e n to fag r i d ，s o m et a s k ss c h e d u l i n ga l g o r i t h m ss u c ha sg e n e t i c a l g o r i t h m ，m i n m i n ，s i m u l a t e da n n e a l i n ge t ch a v eb e e np r e s e n t e dt oi m p r o v et h e p e r f o r m a n c eo ft h eg r i d ，r e d u c et h ee x e c u t i o nt i m ea n dt h ec o n s u m p t i o no ft h e 鲥d c o m p u t a t i o n m e a n t i m e ，n e wg r i ds i m u l a t i o nt o o l sa r eg r a d u a l l yb e i n gu s e dt oh e l p t h ed e s i g n e r so ft h eg r i ds y s t e m st ov a l i d a t et h es c h e m ea n dt e s tt h ep e r f o r m a n c eo f t h eg r i ds y s t e m ，a n du s i n gs i m u l a t i o nt o o l sf o rt h ep a r to ft a s k ss c h e d u l i n gh a s b e c o m i n gt h ek e yp o i n to ft h er e s e a r c hi nt h i sf i e l d i nt h i sp a p e r ，b a s e do nt h ei n t r o d u c t i o no ft h eb a s i cc o n c e p t s ，c h a r a c t e r sb o t hi n f i e l d so f 酊da n dt h et a s k ss c h e d u l i n g ，t h et i t a ng r i ds t r u c t u r ew i t h i nap a c e p e r f o r m a n c ep r e d i c t i o ns y s t e mi sp r e s e n t e d t h e n ，s e v e r a lt y p i c a lg r i dt e c h n o l o g i e s a n dr e s o u r c em a n a g e m e n ts y s t e m sa l ed i s c u s s e d f u r t h e r m o r e ，ai m p r o v e dg e n e t i c a l g o r i t h m ( i g a ) i sp r o p o s e d 1 1 1 ed i s t i n c t i v ef e a t u r eo ft h ea p p r o a c h i st h a tt h ei g a n e e d st oe x e c u t eo n l yv e r yf e wg e n e r a t i o n st oc o m eu pw i t hg o o ds o l u t i o n s ，m a k i n gi t s u i t a b l et ob eu s e di ni n t e n s et a s k se n v i r o n m e n t af i t n e s sf u n c t i o n 、析t 1 1t h r e ew e i g h t s u s e dt op r i o r i t i z ea n yp a r t i c u l a rc o m p o n e n ti na c c o r d a n c ew i t ht h en e e d so ft h ej o b s 0 rt h eu s e r so rt h er e s o u r c ep r o v i d e ri sa l s od e s i g n e dt om i n i m i z em a k e s p a n ，i d l et i m e o f 也ea v a i l a b l ec o m p u t a t i o n a lr e s o u r c e s ，a n dt h es p e c i f i e dd e a d l i n e sp r o v i d e db y u s e r s i ti su n n e c e s s a r yt ou s er e a ls y s t e m st oe v a l u a t et h ep e r f o r m a n c ea n da c c u r a c y o ft h e s ea l g o r i t h m s ，s o ，e m u l a t o r sa r eu s e dt oh a n d l ew i t ht h i sk i n do fw o r k ，i nt h i s p a p e r ，ag d dm o d e l i n ga n ds i m u l a t i o nt o o l k i tn a m e d g r i d s i mi si n t r o d u c e di nd e t a i l s f i n a l l y ，g r i d s i mi su s e dt om a k et h es i m u l a t i o no ft h ei g a ，t h r o u g hw h i c h ，t h e f e a s i b i l i t yo ft h ea l g o r i t h mi sp r o v e d i t i ss t i l laf i r s ta t t e m p tt os u p p o r ti g ai ng r i dt a s k ss c h e d u l i n g t h er e s e a r c h 武汉理工大学硕士学位论文 c o v e r e ds e v e r a la s p e c t sw i t h o u tc o n c e r n i n gt h ei m p a c t sf r o mt h ei n t e r c o m m u n i c a t i o n c o s tb e t w e e nt a s k sa n dt h er e s o u r c e s ，e v e nt h ea c t u a ls t a t u so ft h e u n d e r l y i n g n e t w o r k s w h a t sm o r e ，t h es c h e d u l i n g 行e q u e n c ya sw e l la sa d a p tt h ea l g o r i t h mt o g r i df i e l d ，s t i l ln e e d sm o r ed e l i b e r a t i o n k e y w o r d s ：g r i dc o m p u t i n g ；g e n e t i ca l g o r i t h m ；p e r f o r m a n c ep r e d i c t i o ns y s t e m ； g r i d s i m ；s i m u l a t e i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：叠勿盘冶 导师签名： 、 武汉理工大学硕士学位论文 1 1 研究背景 第1 章绪论 网格技术是继传统互联网之后的第三大浪潮，可以称之为第三代互联网。 传统互联网实现了计算机系统互联，实现了网页的连通，而网格试图实现互联 网上所有资源的全面连通f 1 1 1 2 。g l o b u s 项目【3 】开发组的领导者i a nf o s t e r 在文献【4 】 中指出网格计算关心的是在动态、异构的虚拟组织中协调资源共享和协同解决 问题。在网格环境中，资源的共享必须被高度控制，资源提供者和消费者要清 晰和详细地定义哪些资源可被共享，谁可享用这些资源，以及共享发生的条件。 用这样的共享规则定义的一组资源和机构，称之为虚拟组织。网格能解决在动 态、异构的虚拟组织中的协同资源共享问题，具有如下特性： ( 1 ) 分布与共享 分布性是网格一个最重要的特点。网格的分布性，首先是指网格的资源是 分布的。组成网格的资源包含分布在地理位置互不相同的异构计算机，各种类 型的数据库，以及各种设备，涉及的资源类型复杂，规模较大，跨越的地理范 围较广。网格资源虽然是分布的，但是它们却可以被充分共享。网格上的任何 资源都可以提供给网格上的任何用户。分布是网格硬件在物理上的特征，而共 享则是在网格软件支持下实现的逻辑上的特征，对网格来说二者都十分重要。 ( 2 ) 自相似性 自相似性在自然和社会现象中大量存在，一些复杂的系统都具有这种特征， 网格也是这样。可以认为国家级的网格是在省一级的网格基础上建造起来的， 国家级的主干网要有更宽大的带宽，只有这样才可以将不同省份的子网格连接 起来提供满意的通信服务。它们都有各自的计算中心，只是在计算能力上有差 异。它们也都需要管理节点，只是国家级网格的管理节点功能更多、更强大。 ( 3 ) 动态性与多样性 网格并非一成不变，原来拥有的资源和功能，在下一时刻可能就会出现故 障或者不可用。而原来没有的资源，可能随着时间的推移会不断的加入。网格 的动态性包括动态扩展和动态减少两方面的含义。在设计和实现上，网格能支 持新资源的加入，并且可以和原有的资源融合在一起，共同发挥作用。网格的 武汉理工大学硕士学位论文 扩展性还集中体现在规模、能力和兼容性等几个方面，它能够允许对自身进行 多种形式的扩展。对于网格资源的动态减少或者资源出现故障的情况，网格能 及时采取措施，实现任务自动迁移，做到对高层用户透明或者尽可能减少用户 的损失。网格资源是异构和多样的，在网格环境中可以有不同体系结构的计算 机系统和不同类型的资源，网格系统能够实现在这些资源之间的通信和互操作。 ( 4 ) 自治性与管理的多重性 网格资源首先是属于某个组织或者个人的，因此网格资源的拥有者对该资 源具有最高级别的管理权限，网格允许资源拥有者对它的资源有自主的管理能 力，这就是网格的自治性。网格资源也必须接受网格的统一管理，以便在不同 资源之间建立联系，实现共享和互操作，并作为一个整体为更多的用户提供方 便的服务。因此网格的管理具有多重性。一方面，它允许网格资源的拥有者对 网格资源具有自主的管理能力。另一方面，又要求网格资源必须接受网格的统 一管理。 ( 5 ) 安全性 网格系统的安全性问题必须引起足够的重视。与单一组织范围的分布式环 境不同，网格系统的安全必须支持高度灵活的共享关系和对共享资源的高级控 制，以满足细粒度访问控制和单点登录等安全需求。在帮助用户和服务相互确 定对方是否可信赖等方面，网格环境扮演着关键的角色。 基于以上特点，网格较以往分布式系统具有以下的优势1 5 j ： ( 1 ) 协调非集中控制资源。网格能够整合各种资源，协调各种使用者对这些 资源的使用，并且使使用者在不同控制域中能够解决在分布式环境中出现的安 全策略和使用费用等问题。 ( 2 ) 使用标准、开放、通用的协议和界面。网格系统中包含很多协议，这些 协议可以解决认证、授权、资源发现和资源存取等方面的基本问题。 ( 3 ) 获取匹配的服务质量。网格允许资源被协同使用，从而获取多种服务质 量，以满足不同使用者的需求。 在网格计算中，任务管理、任务调度和资源管理是网格系统必须具备的三 个基本功能。用户通过任务管理系统向网格提交任务、为任务指定所需资源、 删除任务并监测任务的运行状态。用户提交的任务由任务调度系统按照任务的 类型、所需资源、可用资源等情况安排运行日程和策略。而资源管理系统监测 网格资源状况，收集任务运行时的资源占用数据等。 2 武汉理工大学硕士学位论文 任务调度系统是网格中很重要的一个组成部分，它要根据任务信息采用适 当的策略把不同的任务分配到相应的资源节点上去运行。由于网格系统的异构 性和动态性，以及运行于网格系统之中的应用程序对于资源的不同需求，使得 任务调度变得极其复杂，不好的任务分配策略，将会增加任务的执行时间、降 低整个网格系统的吞吐量。 由于网格计算任务调度面临的是一个n p 完全问题，它引起了众多学者的关 注，成为目前网格计算研究领域的一个焦点。 1 2 网格任务调度算法设计面临的问题 调度算法在传统的并行分布式系统中已经作为一个基本的问题被深入的学 习和研究。但这些算法都是与并行分布式系统的结构相联系在一起的。尽管可 以从以前的研究中得到一些启示，但传统的调度模型在实际中很难产生较满意 的网格调度。这是因为传统的系统都作了如下的假设1 6 j ： ( 1 ) 所有的资源都属于一个管理层管理。 ( 2 ) 调度器控制所有的资源，且资源池是不变的。 ( 3 ) 调度器可以通过一些策略处理好由多个任务引起的竞争。所以竞争对节 点能提供给每个任务的性能影响是可以很好的进行预测的。 ( 4 ) 运行计算是一个高可预测的过程，从资源的预定到目的地的预定，这些 过程都可以作为常量开销。 以上的所有假设在网格环境中都不能成立。在网格环境中，许多独特的特 性使调度算法的设计变得很有挑战性。网格调度算法的设计需要考虑的实际问 题有： ( 1 ) 异构性和自治性 尽管异构性对于调度算法来说已不再是新的问题了。但它仍没有被完全的 决解。对于调度算法的设计和分析来说，它还是一个很大的挑战。在计算网格 中，资源是分布在多个地域中的。异构性不仅体现在计算和存储节点上，还体 现在底层的网络连接上。异构产生了对任务处理和数据接入上的不同性能。传 统的并行分布式系统中，计算资源通常由单一的控制节点管理。调度器不仅可 以看到所有正在运行和暂停运行的任务以及资源利用率方面的信息，还可以管 理任务队列和资源池。所以在传统的并行分布式系统中，可以很容易的预测资 源的行为，而且能根据特定性能的需求将任务分配到资源上去。在网格环境中， 武汉理工大学硕士学位论文 资源具有自治性，且网格调度器不能完全的控制资源。同时因为网格调度器不 能违反本地的资源调度策略。这就使它很难估算出一个任务在不同节点上的确 切开销。自治性还体现在本地资源管理和接入控制策略的多样性上。比如，对 于不同应用的优先级设定和资源的预留方法上。这样，网格调度器就需要有自 适应的能力。本论文就尝试通过对调度算法参数的控制，达到使算法能有自适 应性的目的。在网格用户一边的异构性和自治性体现在不同的参数上，包括应 用类型，资源的需求，性能的建模和优化目标上。基于应用层的调度和网格经 济模型【7 j ，以及受自然启发的调度算法就被提了出来，以应用到网格调度当中。 本论文的遗传调度算法就是一种受自然启发的调度算法。 ( 2 ) 性能的动态性 合适的调度通常依赖于对候选资源所能提供的性能估计。特别是对于静态 算法。网格调度器工作在可用资源的性能在不断变化的动态环境中。变化来自 于节点的自治性和应用任务对资源的竞争上。由于资源的自治性，通常的网格 资源都不是用来提供专门的网格服务的。比如，一个远程提交到某计算机簇的 网格任务可能会因为簇内优先级更高的内部任务而中断。能提供更好服务的新 资源可能会加入进来。或者其它的资源会变得不可用。同样的情况也会发生在 连接资源的网络上。可用的带宽会被与网格任务没有任何关系的网络数据流严 重的影响。对于网格应用来说，这种竞争就导致了性能的下降。这就使经典性 能模型很难估计出网格调度的性能。从任务调度的角度看，性能的衰退可能是 网格与传统系统比较最重要的特征。一个有效的调度算法应该是能够适应这种 动态行为的变化的。还有其它的方法可以减少这些问题的影响。如，q o s 协商， 资源预留和重调度1 8 j 。本论文也将针对性能的动态性特点，研究一种基于性能预 报的网格任务调度框架。 ( 3 ) 资源选择与计算数据的分离 在传统的系统中，应用的可执行代码和输入，输出数据通常是在同一节点 上。或者在应用提交前，相关的输入资源和输出目的地就已经确定了。这样， 对于数据分级的消耗可以作为常量，也可以不用考虑。但在由大量异构的计算 节点和存储节点，通过广域网组成的网格中。一个应用任务的计算节点通常是 网格调度器根据资源状态和特定性能模型选择出来的。另外，在网格中，网络 的通信带宽是受限的，并且要和主机上的其它负载共享。所以，内部领域的通 信消耗也要参与计算考虑。许多网格应用都是大数据量的。所以数据分级的成 4 武汉理工大学硕士学位论文 本也不能忽略。这就产生了计算数据分离的问题。即选择一个低成本的计算资 源的优势可能会被其高成本接入存储节点而中和掉。 1 3 网格任务调度的研究现状 目前存在的网格任务调度相关研究中，大致可以分为网格资源管理与调度 系统的研究以及任务调度算法的研究，本文对这两方面分别进行了详细的分析。 目前正在开发和研究的网格调度项目分别有： n i m r o d g 咿j 网格资源代理。n i m r o d g 允许在计算网格中管理和操纵任务。 它使用了一个经济模型来完成资源管理与调度。用户可以使用一种参数声明建 模语言或运行在网格中的g u i ( g r a p h i c a lu s e ri n t e r f a c e ) 接口来系统化参数。 n i m r o d g 提供了网格节点的资源发现，资源交易，调度和资源分段运输，结果 收集，以及最终的结果演示给用户。n i m r o d g 使用了g r a c e ( g r i da r c h i t e c t u r e f o rc o m p u t a t i o n a le c o n o m y ) 服务来动态地与资源拥有者代理交易，选出合适的 资源。g r a c e 使得n i m r o d g 被用来在w w g ( w o r l dw i d eg n d ) 中测试网上调 度参数扫描型应用任务。 n i m r o d g 在资源管理上遵循的是分级的和计算的市场模型。它使用网格中 间件系统，如g l o b u s 等提供的服务来发现资源，并使用一个网络目录或者基于 数据组织的对象模型。它通过g r a c e 架构提供的计算经济服务支持资源预定和 q o s 。用户可以指定q o s 要求，如完成期限( d e a d l i l l e ) ，预算( b u d g e t ) 和首选的最 优策略等。网格资源能力的估计是通过启发式和历史负载档案实现的。调度策 略是面向应用程序的，并且是按照用户定义的要求如d e a d l i n e ，b u d g e t 的限制来 驱动负载完成周期性的调度工作。 g l o b u s 1 0 1 网格计算工具箱。g l o b u s 提供了一个软件架构，使得应用程序可 以把分散的异类计算资源视为一个单个的虚拟机。g l o b u s 项目是一个美国的多 协会共同的研究工作，目的是为了建立计算网格。当前，g l o b u s 的研究者们正 与h i 曲e n e r g yp h y s i c s 和c l i m a t em o d e l i n gc o m m u n i t y 一起建造一个数据网格。 g l o b u s 系统中一个关键的元素就是g l o b u s 工具箱，它定义了构建计算网格的基 本服务和功能的实现架构。工具箱由一系列组件构成来实现基本服务，如安全， 资源定位，资源管理，数据管理，资源预定以及通信等。使用特定工具的开发 者或应用程序可以从中选择能够满足他们特定需要的服务。g l o b u s 是一个典型 的分层网格体系，高层的服务可以调用低层的核心服务来开发。它的重点在于 武汉理工大学硕士学位论文 分级的集合网格组件和服务，鼓励使用低级的服务来开发高级的服务过程。 g l o b u s 中的资源和状态信息是由一个叫做m d s ( m o n i t o r i n ga n dd i s c o v e r y s e r v i c e s ) 的基于l d a p 的网络目录提供的。m d s 由两个组件构成：g i i s ( g r i d i n d e xi n f o r m a t i o ns e r v i c e ) 和g r j s ( g r i dr e s o u r c ei n f o r m a t i o ns e r v i c e ) 。g r i s 通 过一个统一的接口来查询网格中的资源提供者的当前状态，能力和配置信息。 g i i s 把信息从众多的g r i s 服务中取出并集成到一个连贯的资源信息数据库中。 资源信息提供者使用一个p u s h 协议来更新g r i s 。m d s 遵循p u s h 和p u l l 协议 来分布资源。高层次的协议，如资源代理可以通过使用l d a p 协议查询m d s 来 发现资源。m d s 的命名空间是一个树状结构组织起来的形式。g l o b u s 以资源预 定的形式提供了q o s 。g l o b u s 提供了调度组件作为工具箱的一部分，但是并没 有提供调度策略。g l o b u s 服务已被用来开发许多全局调度程序，包括n i m r o d g ， l e g i o n ，a p p l e s 和c o n d o r g 等。 同时，c e r n ( e u r o p e a no r g a n i z a t i o nf o r n u c l e a rr e s e a r c h ) 和高能物理协会建 立了一个国际数据网格项目d a t ag r i d l l l l ，目的是为了将这项工作应用到别的科 学协会，比如e a r t h o b s e r v a t i o na n db i o i n f o r m a t i c s 。这个项目的目标是建立一个 研究网络，开发数据网格技术，通过大范围真实世界里的端到端应用试验的部 署，论证数据网格的有效性，并且证明使用低成本组件，构造，连接，管理大 量通用的，数据集中型的计算机集群的能力。 d a t ag r i d 项目集中在开发中间件服务来处理分布式的物理数据。其中核心 的中间件系统是扩展了数据网格能力的g l o b u st o o l k i t 。d a t ag r i d 项目有一个分 等级的机器组织，越低等级的机器，存储越少的数据。c e r n 是0 级，存储了几 乎所有与l 级相关的数据，而这些1 级的地区中心位于意大利，法国，英国， 美国和日本，它们存储了更少量的数据。此外，d a t ag r i d 有一个将资源模型置 于分等级的命名组织之上的可扩展体系。它并不支持任何的q o s ，所有资源的 信息存储在基于l d a p 的网络目录上。资源的分发是批量式的，并周期性的分 到网格的其他部分中。资源发现是分散式的和基于查询的。因而该调度程序使 用的是一个分级组织，并具有可扩展的调度策略。 在调度算法的研究方面，出现了以自然和人类社会的特征为基础的非传统 网格调度算法的研究，比如网格经济模型调度算法等【l 到，非传统网格调度算法 的分类如图1 1 。 6 武汉理工大学硕士学位论文 非传统网格 调度模型 考虑成本收益 的经济模型 网格经济模型一 不考虑成本收益 的经济模型 自然启发模型 图1 1非传统网格调度算法的分类 遗传算法 模拟退火算法 禁忌搜索算法 基于市场供求关系的调度算法f l3 1 ，仿照日用品买卖市场调控策略来对计算 资源进行优化组合。具体的说，计算资源的“价格”被设定为介于资源的需求和提 供之间，当计算资源的“价格”确定后，对它们的分配过程就按照“先来先服务” 的原则进行，统一地由调度者进行调度。对于同一个计算资源，在实际的调度 过程中可能会由于所选的策略和所处的环境不同而被标上不同的“价格”，因而， 需要调度者进行策略级的全局优化。基于市场供求关系的调度算法利用了经济 学理论进行调度策略的分析，为其他调度算法提供了新颖的思路。 除此之外，还有一些算法思路比较新颖并且也具有较高的参考价值。如两 阶段( 2 - p h a s e ) 调度策略i l 引，是将一个计算任务的计算范围依次划分为l a n 间和l a n 内两个阶段，并分别在l a n 间阶段和l a n 内阶段设立全局的、 集中的任务调度者，以负责制定该阶段的任务调度方案和监督任务执行情况。 2 - p h a s e 式的调度策略，的确在某种程度上反映了计算网格的网络组成，也为实 施网络层次的其他调度算法提供一定的支持。但是，由于仅用涉及l a n 的两 层结构来刻画计算网格是不准确的，所以，2 - p h a s e 调度策略还不日 匕匕, ，z t k e l 好地描述 计算网格的调度，需要更深入的扩展。 国内外许多学者对网格任务调度的算法做了大量的研究工作，但是在网格计 算环境中，已有的任何调度模型、策略、调度目标函数和算法都不可能适宜一 切应用和环境；同一套调度机制在不同的条件下其表现性能不一定相同，因而， 武汉理工大学硕士学位论文 产生的许多研究成果是近似的或者仅是具有启发性的方法。为了找到适宜的调 度方案，许多技术如图论，数学规划，排队论，遗传理论等等被用来解决这个 问题。人们在该领域进行了许多的研究，也取得了一些成果，但是要解决网格 环境的任务调度还需要进行大量的研究工作。 1 4 本文的主要工作 本文所做的主要工作有： ( 1 ) 在深入分析和研究了网格任务调度问题的基础上，对多层次可以提供性 能预报的基于代理的网格任务调度框架作了剖析。 ( 2 ) 就目前网格任务调度算法存在的问题，提出了一种改进遗传算法的调度 方案，以提高遗传算法的执行速度。同时，通过建立合理的适应度函数和参数 的控制，以改善用户和资源提供者间对调度质量的不同要求的平衡。 ( 3 ) 用g r i d s i m 模拟器进行了一系列实验，通过与传统调度算法的比较，证 实了改进遗传算法在问题解决上的有效性。 1 5 本文的组织结构和安排 本文以介绍网格环境的概念和系统模型为起点，按照从理论到模型设计再 到算法应用的实现路线，根据现有网格中遗传调度算法的不足，提出了一个改 进的思路，并使用了g r i d s i m 网格仿真工具，将现有的传统遗传调度算法同本文 改进的算法进行了比较，通过分析实验结果，验证了算法的有效性。按照研究 工作完成的顺序，本论文的组织结构和章节安排如下： 第一章绪论，介绍本文的选题背景，研究工作的基础，并对整个研究中所 做的工作进行了说明。 第二章网格计算任务调度的研究，主要介绍了网格的体系结构，并详细给 出了任务调度仿真模型的设计思路，以及设计网格任务调度算法要遇到的困难， 同时对遗传算法原理进行了总结，包括遗传算法的背景和思想，以及相关的基 本操作原理。 第三章对基于性能预报的网格任务调度进行了整体研究，分析了网格任务 调度对体系结构的需要，网格性能预测机制的实现，并介绍了基于g l o b u s 的信 息服务。 第四章针对传统遗传算法提出了一种改进的遗传算法，对改进的思路进行 武汉理工大学硕士学位论文 了详细的说明，并详述了改进遗传算法各部分的具体设计。 第五章利用g r i d s i m 仿真环境，对本文提出的改进算法进行了仿真实验，并 在结果上与传统的遗传算法进行了对比。 第六章对全文进行了总结，并提出了下一步的相关工作重点。 9 武汉理工大学硕士学位论文 第2 章网格计算中的任务调度 2 1 任务调度的定义 在计算网格中，一个程序可以看作是一个任务集，这些任务可以串行或并 行地执行。任务之间一般是有优先次序约束的。调度问题的目标是要在满足一 定的性能指标和优先约束关系的前提下，将可并行执行的任务按适当分配策略 确定一种分派和执行顺序，合理分配到各处理机上有序地执行，以达到减少总 的执行时间的目的【1 5 】。 性能和效率是评价调度系统的两个基本特征。我们应以任务分派( 调度) 的质 量和调度算法( 调度程序本身) 的效率为基础来评价调度系统。调度质量以产生的 优化调度的性能为基础来衡量；调度算法的效率以时间复杂度为基础来衡量。例 如，如果以优化一个程序的完成时间来衡量，显然完成时间越短越好。如果两 个调度算法产生相同的调度质量，则调度算法越简单越好。 任务调度的相关定义如下【1 6 】： 在有m 个处理单元和任务图g = ( t ，e ) 之上的调度是一个函数厂，厂将每个 任务以某个特定的开始时间映射到某个处理单元。 从形式上，一个调度可描述为： f ：t - - - ) 1 ，2 ，3 ，m x 【o ，】 如果存在_ i ，t ，f ( v ) = ( f ，) ，则表示任务，被调度到处理单元p 上，且从时间 t 开始执行。 函数厂可以表示成如下定义的g a n t t 图。 g a n t t 图用于直观地表示所有任务的开始时间和完成时间。在一个g a n t t 图中， 有一个分布式系统的处理单元表，表中的每个处理单元都有一个任务分配表， 即将分配到这个处理单元的所有任务按执行时间排列成表，其中包括开始时间 和结束时间，分别用s t ( t j , p ) 和f t ( t ，只) 表示。， 实际上，g a n t t 图是一个四元表： g a n t t ( p _ f ，f ，s t ( t ，) ，f t ( i j , ) ) 其中， 只( 扛1 , 2 ，3 ，m ) 为处理单元； 1 0 武汉理工大学硕士学位论文 ( = 1 , 2 ，3 ，刀) 为分配到只上的任务； s t ( t ，只) 为t j 在只上的开始时间； f r ( t ，只) 为在只上的结束时间； 一个任务调度系统的最大调度长度s l ( s c h e d u l el e n g t h ) 定义为所有处理机 只中的： m 即一) ) 调度的目标就是要将任务适当分配到处理机并协调任务之间的执行顺序， 使得并行执行时满足并行任务之间的优先约束关系，而且s l 最小。 任务调度问题属于n p 完全问题，没有最优解f 1 7 1 。任务调度问题的最常见的 目标函数就是完成时间c o ( m a k e s p a n ) 。 基本上每个调度算法都需要估计系统中每个任务所需要的执行时间t 。可以 把执行时间t 分成两部分疋和，这里，是经过网络发送数据到计算机m 的 时间加上从计算机m 上接受结果的时间，是在计算机m 上计算所用的时间。 时间瓦可以通过下列计算参数得到： ( 1 ) 任务长度的大小； ( 2 ) 返回结果的大小。 时间需要计算下列参数： ( 1 ) 任务的规模； ( 2 ) 使用算法的复杂度； ( 3 ) 执行任务的计算机m 的性能，主要取决于m 的负载和计算速度。 2 2 网格调度的过程和组件 网格是一个由应用，中间件组件，和资源所组成的一个高多样性的系统， 但从功能的角度来看，仍然可以找到网格任务调度的逻辑结构【”】。可以将任务 调度过程一般化为三个阶段：资源的发现和筛选，为达到某种目标而进行的资 源选择和调度，以及任务的提交1 1 9 1 。本文主要集中于第二阶段的研究。图2 1 显 示了由资源和应用信息流以及任务调度命令流连接的网格调度系统功能组件的 模型。 网格调度器g s ( g r i ds c h e d u l e r ) 从网格使用者那里接受到应用任务，然后 武汉理工大学硕士学位论文 根据从网格信息服务模块提供的所需信息来选择合适的网格资源来执行这些应 用任务。并最终产生从应用任务到对应执行资源的映射，同时网格调度器还需 要通过特定的目标函数和对资源性能的预测信息来做出任务的分配。网格调度 器不像在传统的并行分布式系统那样能直接控制网格中的资源i z 训。它是以代理 的角色，或者作为应用层调度方案提出来的【2 1 1 。调度器可以和资源不在同一个 地域范围内。图2 1 只显示了一个网格调度器，在实际中，多个调度器可以同时 被部署起来，根据不同的考虑因素，如性能和可扩展性方面，组织成诸如集中 式，分层式和非集中式的结构【2 2 1 。调度组件是充分发挥网格资源潜力的关键。 本论文对调度算法的讨论是建立在假设已存在网格调度器的基础上的。 一 地域1地域n 图2 1由资源和应用信息流以及任务调度命令流连接的逻辑网格调度结构 当考虑网格的异构和动态特性时，可用资源的状态信息对于网格调度器作 出正确的调度显得尤为重要。网格信息服务g i s ( g r i di n f o r m a t i o ns e r v i c e ) 担当着 向网格调度器提供信息的角色。g i s 负责收集和预测像c p u 能力，内存大小， 网络带宽，软件可用度以及特定时段内的节点负载这样的资源状态信息。它不 仅可以提供资源信息，也可以将信息“推送”给信息的订阅者。基于g l o b u s 的网 格监视和发现系统m d s ( m o n i t o r i n ga n dd i s c o v e r ys y s t e m ) 2 3 就属于g i s 。 另外，对于g i s 提供的原始资源信息中的应用属性和资源的性能也是作出 正确调度的重要参考因素。应用仿形a p ( a p p l i c a t i o np r o f i l i n g ) 可以提取应用的精 1 2 武汉理工大学硕士学位论文 确属性。同时，类推基准测试a b ( a n a l o g i c a lb e n c h m a r k i n g ) 用来衡量一个资源对 于一个服务所能提供的服务质量的好坏【2 4 】【2 5 】。利用a p 和a b ，同时结合特定的 性能模型【2 6 1 ，就能够计算出候选调度策略的成本。这样，调度器就根据计算出 的数据选择最优的调度策略以达到优化目标函数的目的。 发送和监视l m ( l a u n c h i n ga n dm o n i t o r i n g ) 模块通过将任务提交给选定的 资源，实现了最后的调度决策。它可以管理和对数据分级，如果需要，也可以 监视应用的执行。网格资源分配和管理系统g r a m ( g r i dr e s o u r c ea l l o c a t i o na n d m a n a g e m e n t ) 是l m 的具体实现【z 。 一个本地资源管理器l r m ( l o c a lr e s o u r c em a n a g e r ) 主要负责两项事务：在 一个资源地域内的本地调度，这不仅要处理外来网格用户的数据，还要处理地 域内本地用户的数据。同时l r m 还要将资源信息报告给g i s 。在一个地域内， 一个或多个本地调度器都运行在逻辑上特定的资源管理策略上，现有的本地调 度器包括o p e n p b s l 2 引和c o n d o r l 2 9 j 。一个l r m 也可以通过网络天气服务系统 ( n w s ) t 3 0 1 ，h a w k e z e 3 1 1 和g a n g l i a l 3 2 j 等工具收集本地的资源信息，同时向g i s 报 告资源状态信息。 2 3 网格任务调度中的遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ) 是通过模拟达尔文的进化论而创建的，遗传 算法( g e n e t i ca l g o r i t h m s ，g a ) 最早由美国m i c h i g a n 大学的h o l l a n d 提出，它模 拟生物遗传进化的过程，引入了选择、复制、交叉重组和变异等方法，并将进 化论中的“物竞天择，适者生存”的概念引入到算法中【3 3 】【3 4 】。由于遗传算法具有 全局寻优能力、适用于离散和连续变量问题、无须先验知识等特点，因此得到 了普遍的应用。遗传算法历史上的经典著作自然和人工系统中的适应性， 系统阐述了遗传算法的基本理论和方法，并提出了模式定理( s c h e m a t at h e o r e m ) ， 证明在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距离以及平均 适应度高于群体平均适应度的模式在子代中将以指数级增长，这里的模式是某 一类字符串，其某些位置有相似性。 遗传算法是从代表问题可能潜在的一个种群( p o p u l a t i o n ) 开始的，而一个 种群则由经过基因编码( e n c o d i n g ) 的一定数目的个体组成。每个个体实际上就 是一个带有特征的染色体( c h r o m o s o m e ) 实体。染色体作为遗传物质的主要载 体，即多个基因的组合，其内部表现是某种基因组合，它决定了个体的性状的 武汉理工大学硕士学位论文 外部表现。因此，在一开始需要实现从表现型到基因型的映射，即编码工作。 由于仿照基因编码的工作很复杂，往往需要进行简化，如二进制编码。初代种 群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近 似解。在每一代( g e n e r a t i o n ) ，根据问题域中个体的适应度( f i t n e s s ) 大小挑选 个体，并借助于自然遗传学的遗传算子进行组合交叉( c r o s s o v e r ) 和变异 ( m u t a t i o n ) ，产生出代表新的解集的群体。这个过程将导致种群像自然进化一 样的后生代种群比前代更加适应环境，末代种群中的最优个体经过解码，可以 作为问题近似最优解。 遗传算法采纳了自然进化模型，如选择、交叉、变异等等。