（计算机应用技术专业论文）网格环境下资源管理与调度方法的研究与应用.pdf

武汉理工大学硕士学位论文 摘要 网格是近年来迅速兴起的一个新的研究领域，它的出现标志着网络技术进 入了一个崭新的时代。网格的实质是共享与协作，即在动态的、可扩充的虚拟 组织中可控且平等地使用和共享资源。如何充分利用网格中的共享资源是决定 一个网格系统好坏的关键因素，资源管理和作业调度则是解决这一问题的主要 技术手段。资源管理和作业调度是网格的核心和关键内容之一，为了提高网格 系统的计算效率，必须不断加强对资源管理和作业调度的研究。 本文在理论与实践相结合的基础上，对网格资源管理和调度的相关问题进 行了系统的分析与研究，其主要研究工作和贡献可以体现在以下几个方面： 首先系统地分析了网格的内涵、特征、分类以及相应的体系结构，归纳和 比较了目前一些主要的网格研究项目的特点。通过仔细分析网格资源的特征， 归纳和总结了网格资源管理调度的目标、特点、组成以及相应的结构模型。 针对网格调度中容易出现的群集行为，本文在详细分析d 随机选择算法和 非统一性随机选择算法的基础上，结合网格环境的特点，提出了一种改进的随 机选择算法一二次随机选择算法，该算法融合了d 随机选择方法和非统一性 随机选择算法的思想，并弥补了非统一性随机选择算法不适合于网格调度这方 面的不足。 本文分别在理论和实践上将提出的二次随机选择算法同d 随机选择算法进 行分析和对比，发现在系统负载信息不准确和不真实的情况下，二次随机选择 算法在负载平衡方面确实优于d 随机选择算法，从两更好地解决了群集行为。 另外，本文在借鉴现有网格技术的基础上，通过利用s i m o r i d 工具包中的 g r a s 机制，设计和实现了一个基于二次随机选择算法的网格调度系统原型，并 通过模拟和仿真，发现在该原型基础上。相对于d 随机选择方法来说，二次随 机选择算法确实能够带来更好的负载平衡，同时也没有带来过多的额外开销。 论文工作对网格的资源管理和调度研究具有较大的理论意义和使用价值。 关键词：网格，资源管理，群集行为，随机选择算法 武汉理工大学硕士学位论文 a b s t r a c t g r i di sai l e wf i e l do fr e s e a r c hr a p i dd e v e l o p i n gi nr e c e n ty e a r s ，t h ee m e r g e n c eo f w h i c hr e p r e s e n t st h a tn e t w o r kt e c h n o l o g yh a se n t e r e dan e we p o c h g r i di st h e 伪s 伽l c eo fs h a r i n ga n dc o l l a b o r a t i o n , t h a ti s ，c o n t r o l l a b l ea n de q u i t a b l el 娣a n d s h a r i n go fr e s o u r c e si nt h ed y n a m i c , s e a l a b l ev i r t u a lo r g a n i z a t i o n h o wt om a k ef u l l u s eo ft h es h a r e dr e s o u r i 满i st h ek e yf a c t o ro fd e t e r m i n i n gt h ep e r f o r m a n c eo fg r i d s y s t e m , w h i c h co u l db ed e a l tw i t hb yr e s o u r c em a n a g e m e n ta n dj o bs e h e a u l i n g t h e l e s o u r c em a n a g e m e n ta n dj o bs c h e a u l i n gi so n eo ft h ec e n t e ra n dk e yd e m e n t so f g r i ds y s t e m t h e r e f o r e , i no r d e rt oi m p r o v e 鲥dc o m p u t i n ge f f i c i e n c y , w em u s t c o n t i n u et os t r e n g t h e nt h es t u d yo fr e s o u r c em a n a g e m e n ta n dj o bs c h e d u l i n g c o m b i n i n gt h e o r y w i t h p r a c t i c e , t h i s d i s s e r t a t i o ns y s t e m a t i c a l l ys t u d i e st h e t e c h n o l o g i e so fg r i dr e s o u r c em a n a g e m e n ta n ds c h e d u l e t h em a j o rr e s e a r c hw o r k a n dc o n t r i b u t i o n si nt h i sd i s s e r t a t i o na r ea sf o l l o w s t h i st h e s i ss y s t e m a t i c a l l ya n a l y z e st h ec o n c e p t i o n , c h a r a c t e r i s t i c s , c l a s s i f i c a t i o n a n da r c h i t e c t u r eo ft h eg r i d s u m m a r i z e sa n dc o m p a r e st h ec h a r a c t e r i s t i c so fc u r r e n t g r i ds , r o j e e t s w i t ht h ec a r e f u la n a l y s i so ft h ec h a r a c t e r i s t i c s o fg r i dl - e s o u r c e s ， s u m m a r i z e sa n ds u m s 印t h eg o a l ，c h a r a c t e r i s t i c sa n dc o m p o n e n to fg r i d 坞s 嘴 m a n a g e m e n ta n ds e h e , t u l i n ga n dc o r r e s p o n d i n gs m l c t u r em o d e l i no r d e rt oa v o i dt h eh e r db e h a v i o re a s i l yr a i s e di ng r i c li e s o u l r c a ：m a n a g e m e n ta n d s c h e d u l i n g , b a s e do nt h ea n a l y s i so ld - r a n d o ms e l e c t i o nm e t h o da n dn o n - u n i f o r m i t y r a n d o ms e l e c t i o na l g o r i t h m , c o m b i n e d 谢t l lt h ec h a r a c t e r i s t i c so fg r i de n v i r o n m e n t , w ep r o p o s ea ni m p r o v e dr a n d o ms e l e c t i o na l g o r i t h m - - t w i c er a n d o ms e l e c t i o n a l g o r i t h m , w h i e l ai n t e g r a t e s t h oi d e ao fd - r a n d o ms e l e c t i o nm e t h o da n d n o n - u n i f o r m i t yr a n d o ms e l o e t i o na l g o r i t h m , a n dm a k e su pt h ed e f i c i e n c yt h a tt h e n o n - u n i f o r m i t yr a n d o ms e l e c t i o na l g o r i t h m d o e sn o t a d a p tt o 班ds c h e d u l i n g w i t ht h et h e o r e t i c a la n a l y s i sa n dp r a c t i c a lv a l i d a t i o n , 骶p r o v ot h a tt h et w i c e r a n d o ms e l e c t i o na l g o r i t h mi si n d e e ds u p e r i o rt o d - r a n d o ms e l e c t i o na l g o r i t h mi n l o a db a l a n c i n g , w h e nt h el o a di n f o r m a t i o no fs y s t e mi sn o tl a u ea n da u t h e n t i c 武汉理工大学硕士学位论文 t h e r e f o r e , t h et w i c er a n d o ms e l e c t i o na l g o r i t h mc a nd e a lw i t ht h eh e r db e h a v i o r b e t t e r i na d d i t i o n , b a s e do i lr e c e n tg r i dt e c h n o l o g i e s ，诵mu s i n gt h eg r a sm e c h a n i s mi n s i m c , r i d , w ed e s i g na n di m p l e m e n tas y s t e mp r o t o t y p eo f g r i db a s e do nt w i c er a n d o m s e l e c t i o na l g o r i t h m , a n df o u n db ys i m u l a t i o na n de m l u a t o rt h a to nt h eb a s i so ft h e p r o t o t y p e , t h et w i c er a n d o ms e l e c t i o na l g o r i t h mc o m p a r e dt ot h ed r a n d o ms e l e c t i o n a l g o r i t h r a a c h i e v e st h eb e t t e rl o a db a l a n c ew i t h o u tb r i n g i n ga b o u tt o om u c h a d d i t i o n a lo v e r h e a d t h es t u d yi nt h i sd i s s e r t a t i o ni ss i g n i f i c a n ti nt h e o r ya n dp r a c t i c et ot h er e s e a r c ho f r e s o u r c em a n a g e m e n ta n dj o bs c h e d u l i n go fg r i d k e y w o r d s ：g r i d ，r e s o u r c em a n a g e m e n t , h e r db e h a v i o r r a n d o ms e l e c t i o na l g o r i t h m m 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论交中作了明确的说明并表示了谢意。 研究生签名：主! 1 2 窆荜： 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，1 1 1 学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部内容， 可以采用影印、缩印或其他复制手段保存论文 ( 保密的论文在解密后应遵守此规定) 研究生签名：越导师签名：墨蚴日期曼：! 垒：三：童 武汉理工大学硕士学位论文 第1 章引言 随着i n t e r n e t 规模的不断扩大和应用的日益普及，网络成为了人们信息交流 和协同工作的重要平台，在该平台上汇集了越来越多的计算资源、数据资源以 及各种软、硬件资源，它们共同构成了传播和使用知识的重要载体。然而在 i n t e r n e t 这个大型的网络中，由于资源的封闭性，使得大量的资源被闲置，系统 的使用率低下，据有关资料统计，系统资源平均使用率仅为3 0 左右，有的空 闲率竞达9 1 ；与此同时，人们需要解决的问题越来越复杂，对计算机处理能 力的要求也越来越高，有些问题甚至是现存的任何一台超级计算机在有限的时 间内都难以解决的。在这种情况下，若能将i n t e m e t 中闲置的大量资源利用起来， 组成一个“虚拟的超级计算机 ，这对于解决复杂问题、有效利用资源都具有重 大的现实意义。网格技术就是在这样的环境下应运而生的。 网格是近年来迅速兴起的一个新的研究领域，它的出现标志着网络技术进 入了一个崭新的时代。网格的实质是共享与协作，即在动态的、可扩充的虚拟 组织中可控且平等地使用和共享资源。如何充分利用网格中的共享资源是决定 一个网格系统好坏的关键因素，资源管理和作业调度则是解决这一问题的主要 技术手段。为了提高网格系统的计算效率，必须不断加强对资源管理和调度的 研究。 1 1 网格概述 1 1 1 网格定义及特点 网格【1 】【2 】是构筑在i n t e m e t 上的一组新技术，它将高速互联网、高性能计算 机、大型数据库、传感器、远程设备等融为一体，提供更多的资源、功能和交 互性，能够实现广域网范围内的动态的、多个机构的虚拟组织内的协同资源共 享和问题求解。 网格计算是作为分布式计算的一个分支出现的，但它却不等同于分布式计 算，有其自身的特点。网格系统的特征主要表现在以下几个方面： 武汉理工大学硕士学位论文 1 ) 资源共享 资源共享是网格系统的本质，网格中的资源共享不仅仅是交换文件信息， 而是对分布在不同地理位置的计算机、软件、数据以及其他各种资源进行访问 和操作。这种共享必须是被高度控制的，一方面既要满足用户的要求，另一方 面又必须遵从资源提供者的权利( 包括什么才能被共享、谁才有权利共享等) 。 2 ) 站点自治与多重管理 网格资源通常属于不同的机构或组织，因此网格资源的拥有者对该资源拥 有自主的管理能力；同时，网格资源必须接受网格的统一管理。网格通过各个 机构或组织共同参与“虚拟组织一来解决多级管理域的问题。 3 ) 异构性与多样性 网格中的资源可以跨越地理分布的多个管理域，而构成网格资源的计算机 在体系结构、操作系统及应用软件等多个层次上都可能具有不同的结构，这就 决定了网格资源的异构性；同时，网格中的资源并不仅仅只是计算机或者数据， 它涉及到计算机、软件、数据、大容量存储设备等各种资源，因而它是多种多 样的。 4 ) 动态性 对于网格来说，决不能假设它是一成不变的。原来拥有的资源或者功能， 在下一时刻可能就会出现故障或者不可用；而原来没有的资源，可能会随着时 间的推移不断地加入进来。 5 ) 自相似性 网格的自相似性是指网格的局部和整体之间存在一定的相似性，局部往往 在许多地方具有全局的某些特征，而全局的特征在局部也有一定的体现。 1 1 2 网格体系结构 网格体系结构就是关于如何建造网格的技术。它给出了网格的基本组成与 功能，描述了网格各组成部分的关系以及它们集成的方式或方法，刻画了支持 网格有效运转的机制。 1 ) 五层沙漏模型 五层沙漏结构【l 】用于描述网格中的协议分层结构。类似于i n t e r n e t 中的 t c p i p 体系结构，五层沙漏模型同样将网格环境中的协议划分为五层，分别是： 2 武汉理工大学硕士学位论文 构造层( f a b r i c ) 、连接层( c o n n e c t i v i t y ) 、资源层( r e s o u r c e ) 、汇聚层( c o l l e c t i v e ) 和应用层( a p p l i c a t i o n ) 。五层沙漏结构和i n t o n e r 体系结构对照关系如图1 1 所 不 应用层( a p p l i c a t i o n ) + 汇集层( c o l l e c t i v e ) 1r 资源层( r e s o u r c e ) 1r 连接层( c o n n e c t i v i t y ) 图1 1 网格和i n t e m e t 体系结构对照图 五层沙漏结构主要从协议的角度对网格各层功能进行了划分，本质上它是 一个在虚拟组织组件之间进行互操作的协议体系结构。在这五层结构中，资源 层和连接层组成沙漏的瓶颈部分，是整个结构的核心部分，起到了承上启下的 作用。各层功能分别如下【l 】： 构造层实现对本地特定资源的访问和控制，向高层提供这些资源的共享访 问接口。构造层的资源非常广泛，可以是处理能力、存储系统、目录、分布式 文件系统、分布式计算机池、计算机集群等。因此构造层的实现依赖于特定的 实现。 连接层定义了网格特有的网络交互过程中的核心的通信和认证协议，通信 功能实现网格构造层资源之间的数据交换，在此基础上，认证协议提供了对用 户和资源的身份的加密安全验证机制。 资源层实现对单个资源的共享，反映了抽象的局部资源特征。资源层建立 在连接层的通信和认证协议之上，定义的协议包括安全的初始化、监视、控制 单个资源的共享操作、审计以及付费等。资源层协议考虑的完全是单个的局韶 资源，因此忽略了全局状态和跨越分布资源集合的原子操作。 3 蚕 武汉理工大学硕士学位论文 汇聚层建立在资源层之上，为了对来自应用的共享进行管理和控制，汇集 层提供目录服务、资源分配、日程安排、资源代理、资源监测诊断、网格启动、 负荷控制、账户管理等多种功能。 应用层存在于网格用户的应用环境中，用户的应用程序通过各层的a p i 调 用相应的服务，再通过服务调用网格上的资源来完成任务。 2 ) 开放网格服务体系结构 ， 开放网格服务体系结构o g s a ( o p e ng r i ds e r v i c ea r c h i t e c t u r e ) 2 】【3 】是g l o b u s 小组和m m 于2 0 0 2 年初提出的一个面向服务的网格结构，是将w e b 服务同五 层体系结构相结合的产物。 o g s a 的核心思想是以服务为中心。o g s a 在定义过程中，强调不同资源响 应协议消息的服务的本质，网格被看作是一个可扩展的网格服务集，网格中“一 切都是服务一，这里的服务是指具有特定功能的网络化实体。在五层沙漏结构中， 强调的是被共享的物理资源，或者是这些资源所支持的服务，而在o g s a 提出 时，服务所指的概念变得更广，包括计算机设备、应用程序、数据，也包括仪 器、设备等也抽象成为服务。简而言之，就是把一切抽象为服务，这样有利于 通过统一的标准接口来管理和共享网格上功能各异的资源【2 】 o g s a 通过将各种网格资源对看作是具有特定功能的遵循标准接口和相关 访问协议的网格服务，实现了对所有网格资源的虚拟化，通过各种网格资源的 组合，可以形成层次化的网格服务体系，并最终实现资源共享和协同问题求解。 另外，通过将已有的网格技术和w e bs e r v i c e 技术的结合，增强了企业对网格技 术研发和应用的投入和支持，使网格应用能够快速的从科研领域进入到商业应 用领域，对网格的发展和广泛应用有很好的推动作用。 1 2 研究目的及意义 在网格环境下研究其资源管理和调度技术有着重大而深远的意义，这主要 体现在： 1 ) 资源管理和调度技术是网格技术的核心研究内容之一 网格的目的是满足分布在不同地域的用户共享资源和协同工作的需求。在网 格系统中，大量的上层应用共享着网格的各种资源。如何有效地管理和调度这 些资源，以便尽可能提高网格系统的性能，这就是网格调度所要解决的问题。 4 武汉理工大学硕士学位论文 良好的调度是实现高效使用共享资源的重要环节。通过调度，可以把应用所需 的计算隐藏于网格中，降低了上层应用的复杂性，使用户不必关心任务所需的 计算放到什么地方去执行，从而把更多的精力投入到业务本身的开发中。 2 ) 网格中的调度技术比其他系统中的调度技术更复杂 在网格系统中，其资源的动态变化性、资源类型的异构性和多样性就决定 了网格调度技术比传统高性能计算中的调度技术更复杂；同时在网格调度中， 还需要考虑移植性、扩展性、效率、可重复性以及网格调度和本地调度的结合 等一系列问题。 3 ) 网格资源管理和调度是网格实用化的关键【4 】 当前，大多数的网格系统主要集中于科研领域，现在还没有一个真正可以用 于商业的网格系统。也就是说，目前网格系统还处于研究实验阶段，没有实用 化。其原因在于现在的网格系统没有很好地解决网格资源调度所面临的主要问 题这些问题主要有：如何有效处理由每个随时可能加入和退出网格的资源节 点所组成的动态变化的网格资源池；如何处理每个网格节点的自治性问题；如 何对多个用户同时使用的资源的性能进行准确地预测；如何根据不同的预测结 果采用不同的调度方案；如何根据资源动态变化的状态信息对正在运行的任务 进行重调度；如何进行资源预留等等。因此，网格资源调度还需要进行深入研 究，只有解决好这些问题，才可以使网格系统实用化、普及化。 1 3 论文的主要研究工作及贡献 针对网格环境复杂性的特点，本文对网格环境下的资源管理和调度技术进 行了研究和探讨，主要的研究工作包括： 1 ) 系统地分析了网格资源调度的目标、模型、流程，并对现有的一些网格 调度系统进行了研究。 2 ) 基于解决网格资源管理和作业调度中的群集行为这个目的，通过对 b a l l s - a n d b i n s 模型和d 随机选择算法的详细分析，结合非统一性随机选择算法 的思想，针对网格环境的特点，提出了一种改进的随机选择算法一二次随机 选择算法。 3 ) 分别在理论和实践上将二次随机选择算法同d 随机选择算法进行分析 和对比，发现二次随机选择算法在负载平衡方面确实优于d 随机选择算法，并 5 武汉理工大学硕士学位论文 且相对于后者来说，前者并没有带来过多的额外开销。 4 ) 根据二次随机选择算法的特点，通过将现有网格技术融合起来，设计了 一个适合于二次随机选择算法的网格系统原型，并利用s i m g r i d 的g r a s 机制 模拟了该调度原型。 1 4 论文组织结构 本文共分为5 章，各章结构和主要内容如下： 第l 章介绍了网格的含义、特征以及体系结构，说明了网格资源管理的研 究目的和意义，并给出了本文的研究工作和章节安排。 第2 章综述了资源管理调度的含义、模型以及流程，分析和比较了目前一 些主要网格调度项目的特点及体系结构，并指出了网格调度中出现的问题以及 本文的研究重点。 第3 章首先介绍了群集问题的模型，然后详细描述了二次随机选择算法， 并从理论上分析了该算法的性能；同时，借鉴现有的一些网格系统中的相关技 术，设计了并实现了一个基于二次随机选择算法的系统原型。 第4 章通过模拟和仿真，对几种算法的性能进行比较和分析。 第5 章总结了本文工作，并对今后的研究作出了展望。 6 武汉理工大学硕士学位论文 第2 章网格资源调度研究综述 本章综述了网格资源管理和任务调度的概念、流程、目的和目标，并研究 了一些现有的网格调度系统。通过分析网格调度的特点和现有一些调度系统的 调度方法，指出了网格调度中可能出现的问题群集行为，并提出了相应的 解决办法。 2 1 调度问题 文献【4 】中给出了基本的调度模型，如图2 1 所示。 i l 数 寥 j l j 2 弘 弘 图2 1 面向系统和面向作业的甘特图 假定系统中有n 个作业需要处理，记为：j = j l ，j 2 ，j 3 ， ：同时，系统 中存在t 个机器能够处理这些作业，记为：m = m i ，m 2 ，m 3 ，m t ) 。那么对于 每个作业而言，调度则是将一个或者多个机器上的一个或多个时间间隔分配给 该作业的过程。 7 武汉理工大学硕士学位论文 2 2 网格资源管理和调度 在网格中，资源管理和调度系统是其核心组成部分，它要根据当前系统的状 况信息和预测信息，对系统内的作业进行动态调度。资源调度主要研究如何在 同构或异构的网格计算系统中屏蔽底层计算资源，在网格系统范围内为用户提 供一种统一的资源视图，在任务与资源之间寻找最佳的匹配策略，管理和调度 任务的并行执行，使系统资源得以合理利用，最终使系统计算资源的利用率得 到提高。 2 2 1 网格资源调度的目标 简单地说，网格资源调度的目标就是如何最大限度地提高网格系统效率， 同时又能够尽快地完成用户提交的任务。具体来讲，可以体现在以下几个方面【5 】： 1 ) 最优跨度( o p t i m a lm a k e s p a n ) 跨度是一个最主要、最常见的目标，指的是调度的长度，就是在实现网格 资源管理调度时，从第一个任务开始运行到最后一个任务运行完毕所经历的时 间。跨度越短，说明调度策略越好。对于用户来讲，其最大的愿望就是希望在 向网格系统提交任务后，网格系统能够尽快完成自己的任务。可见，实现最优 跨度是用户和网格系统的共同目标。 2 ) 负载均衡( l o a db a l a n c i n g ) 在开发并行和分布式计算应用时，负载平衡是一个关键问题。网格系统更 进一步扩展了这个问题。网格任务调度是涉及交叉域和大规模应用的调度。解 决好系统的负载均衡是一个非常重要的问题。本文的研究重点也集中在这个方 面。 3 ) 服务质量( q u a t i t yo fs e r v i c e ) 在网格系统为用户提供计算和存储服务对，用户对资源需求情况是通过服 务质量q o s 形式反映出来的。任务管理与调度系统在进行分配调度任务时，保 障网格应用的q o s 是相当重要的。 4 ) 经济原则( e c o n o m i cp r i n c i p l e s ) 网格中的资源在地理上是广泛分布的，而且每个资源都隶属于不同的组织， 都有各自的资源管理机制和政策。根据现实生活中的市场经济原则，不同资源 3 武汉理工大学硕士学位论文 的使用费用也应该是不相同的。市场经济驱动的资源管理与任务调度必须使消 费双方( 资源使用者和资源提供者) 互惠互利，才能使网格系统长久地发展下 去。 2 2 2 网格调度的特点 网格任务调度具有以下几个特点【5 1 1 6 1 ： 1 ) 任务调度是面向异构平台的 由于网格系统是由分布在互联网上的各类资源组成的，包括各类主机、工 作站甚至p c 机，它们是异构的，可运行在u n i x ，w m d o w sn t 等各种操作系 统下，也可以是上述机型的机群系统、大型存储设备、数据库或其他设备。因 此网格系统中的任务调度必须面向异构平台，并在这些平台上实现网格任务的 调度。 2 ) 任务调度必须具有可扩展性 网格系统初期的计算规模较小，随着超级计算机系统的不断加入，系统的 计算规模也必将随之扩大。因此，在网格资源规模不断扩大、应用不断增长的 情况下，网格系统的任务调度必须具有可扩展性，不致降低网格系统的性能。 3 ) 任务调度是大规模的、非集中式的 由于网格系统是一个大到整个i n t c m e t 的分布式系统，要实现一种全局的统 一集中的任务调度管理是根本不可能的。因此，网格的任务调度必须以分布、 并行方式进行任务的管理与调度。 4 ) 任务调度能够动态自适应 ， 网格中不仅其资源是异构的，而且网格本身的结构也总是不停地改变，有 的资源可能会因为故障而退出，有的新资源要加入到网格中，有些资源重新开 始工作等。总之网格的动态性是明显的，所以任务调度系统必须适应网格的这 种动态性，从可利用的资源中选取最佳资源为用户提供应用服务。 2 2 3 网格资源调度的分类 网格资源调度方式可以采用以下几种方式进行分类 4 1 1 7 1 ： 1 ) 调度器体系结构 9 武汉理工大学硕士学位论文 网格调度系统根据其体系结构可以分为集中式、分层结构和分布式三种 集中式调度是指在网格系统中固定地指定一个或一些节点担任调度功能，系 统中所有的资源请求都发送到这些调度节点上，由这些节点控制和调度网格系 统中所有的资源请求节点和资源提供节点。集中式调度的优点是易于实施和管 理，易于实现资源的协同分配，缺点就是维护代价高，难以实现容错。 分层式调度是指网格系统中的调度节点以层次结构组织起来，高层调度节点 执行粗粒度任务的调度，低层调度节点执行粒度较小的任务调度。逻辑上，每 一层都有各自的作必任务队列。可以把集中式调度视为只有一层的层次式调度。 分层式调度易于实现扩展和容错，易于资源的协同分配，但不支持资源地域自 治和多种调度策略。 在分布式的网格资源调度系统中，没有指定某些固定的节点作为调度节点， 网格系统中每个节点都具有调度功能。逻辑上，网格中有多少个节点，就有多 少个作业队列。分布式调度又可以分为协作式和非协作式两类。协作式是指调 度节点相互之间进行协调来做出决策，而非协作式则是每个调度节点自己独立 地做出决策。分布式调度易于扩展和容错，支持资源自治和多种调度策略结合 使用，但不易于管理和资源协同分配。 2 ) 调度策略 调度策略是网格调度器在调度过程中所遵循的策略。根据调度策略本身在 调度过程中是否改变，可以将调度分为固定的( f i x e d ) 调度策略和可扩展 ( e x t e n s i b l e ) 的调度策略。 固定式调度又可以分为面向系统的和面向应用程序的，前者的调度目标是 最大化系统吞吐量，后者的调度目标是最优化应用程序完成时间。可扩展调度 策略又分为a d - h o c 类型和结构化类型，前者执行固定调度策略，但允许系统外 部实体修改调度结果，而后者允许外部代理修改系统任务调度策略。从系统状 态估计的支持上，可将网格任务调度分成有状态预测和无状态预测两类，预测 方法包括启发式方法、基于经济模型的方法和机器学习方法。无预测的方法包 括启发式方法和概率分布方法。 3 ) 调度方式 根据是否实时地处理用户的作业请求，网格调度系统的调度方式有两类： 在线式和批处理式【4 】。在线式调度是指每当收到一个用户作业请求时，网格调度 系统立即对该作业进行调度。批处理式调度中，调度行为只在“调度事件一发 1 0 武汉理工大学硕士学位论文 生时进行。调度事件的发生可以是周期性的，也可以是事件驱动的。调度事件 发生时等待调度的所有互相独立的用户作业所组成的集合称为一个“元任务 ( m e t a t a s k ) 一。一个元任务包括从最后一个调度事件发生后接收到的所有作业请 求以及在上一次调度中还没有开始执行的作业。以n j 表示第j 个作业，a j 表示n j 的到达时刻，b j 表示n i 的开始被调度的时刻，以m i 表示在第i 个调度事件发生 时被调度的元任务，t i 表示m i 被调度的时刻，其中i 0 。则初始元任务m o 由所 有在时刻t o 之前提交的作业组成，即m o f f i n j l a j to ) 。元任务m k ( 踟) 由那些 在第k - 1 个调度事件发生后提交的所有作业以及在第k - 1 个调度事件发生时已经 被调度但是还没有开始执行的作业组成，即m k = n j 睦 a j t o u n j l a j t k - ) 在线式调度和批处理式调度各有所长。在线式调度主要适用于单位时间内 接收的用户作业比较少的系统，这样，每个作业都能够得到及时的调度。批处 理式调度适用于系统负载比较重，单位时间接收的用户作业比较多的情况，系 统以元任务为调度单位，可以综合考虑元任务中各个作业的特点进行适当的调 度，从而提高系统的利用率，缩短作业的平均运行时间。 4 ) 抢占方式 根据作业执行时资源是否可以被抢占，可将调度分为抢占式和非抢占式。 抢占式则指可以中断已经运行在网格节点上的任务。目前绝大多数的关于网格 调度方面的研究工作都集中在非抢占式调度。 2 2 4 网格资源管理调度流程 根据j e n i l i f e rm s c h o p f 8 1 的观点，可以将网格资源调度流程分为资源发现、 系统选择和作业执行三个阶段，如图2 2 所示。 武汉理工大学硕士学位论文 图2 2 资源管理和调度流程 1 ) 资源发现 资源发现阶段主要是为用户搜索一个满足其最小需求的资源集合，以供下 一阶段使用，资源发现主要由三个步骤来实现： ( 1 ) 授权过滤( a u t h o r i z a t i o nf i l t e r i n g ) 授权过滤的主要任务是将用户拥有访问权限的资源搜集起来，形成一个资 源列表。从原理上来看，网格中的授权过滤与远程提交一个作业到某一单一站 点类似：没有权限就不能运行作业。这一步结束以后，用户会得到一个自己具 有访问权限的资源集合。 ( 2 ) 应用需求定义( a p p l i c a t i o nr e q u i r e m e n td e f i n i t i o n ) 对于自己的应用，用户通常都能够以某种方式给出运行的最低资源要求， 这些需求将用来在下一步过滤资源。 作业需求集合可能会非常广泛，并且作业间的差别也会很大。它既可能包 含静态的条件( 如操作系统、或者硬件的类型、或者具体的体系结构等) ，也可 能包含动态的条件，如内存的容量、存储空间的大小等。这一项包含了所有保 证作业能够运行的那些可以映射到资源属性的指定条件。 ( 3 ) 最小需求过滤( m i b r e q u i r e m e n tf i l t e r i n g ) 1 2 武汉理工大学硕士学位论文 在得到用户具有访问权限的资源集合以及用户提交作业的最小资源需求之 后，这一步的主要工作就是根据用户提交作业的最小资源需求，过滤所得到的 资源，将不满足作业需求的资源去掉，剩下的留给下一步使用。 2 ) 系统选择 系统选择阶段的主要工作就是在一组满足作业运行条件的资源( 资源发现 阶段所搜集到的) 中，为作业选择一个合适的资源，这一阶段是本论文研究的 重点。这个选择的过程一般可分为两步： ( 1 ) 信息收集( i n f o r m a t i o ng a t h e r i n g ) 为了做出最佳的作业和资源之间的匹配，用户需要收集资源的动态信息。 根据应用和资源的情况，可能需要收集不同的信息。动态信息收集通常涉及两 个方面：有哪些可用的资源和用户如何能够获得访问权。 例如，假设需要找到一个最佳的资源来运行一个作业。为此，用户就可能 需要知道不同机器的负载、队列情况；另外，一些物理特性和软件需求可能也 会起作用资源上是否有所需的编译器，磁盘空间是否够大等等；然后还有 位置连接性能的因素机器与数据源是否够近呢? ( 2 ) 系统选择( s y s t e ms e l e c t i o n ) 在上一步收集的资源的基础上，这一步主要完成的任务就是根据某种标准 为作业选择一个最佳的资源运行。 3 ) 作业执行 网格调度的第三个阶段就是提交运行作业。它包括许多步骤，其中的一些 在资源间还没有统一的定义： ( 1 ) 提前预留( a d v a n c er e s e r v a t i o n ) 为了充分利用资源，有的时候还需将部分资源提前预留出来。根据资源的 不同状况，提前预留做起来有可能简单，也有可能比较复杂。此外，预留资源 也有可能需要额外的花费。 ( 2 ) 作业提交( j 0 bs u b m i s s i o n ) 一旦资源被选中后，就可以将作业提交给该资源。作业提交可以通过运行 一个简单的命令，或者一系列复杂的脚本来完成。网格系统中，如果缺乏一定 的作业提交标准，那么作业提交这个简单的过程也有可能因此会变得相当复杂。 ( 3 ) 准备任务( p r e p a r a t i o nt a s k s ) 准备任务阶段涉及到安装，分段传输、声明预留以及其他一些准备工作。 1 3 武汉理工大学硕士学位论文 有的时候，在作业运行之前，还需要运行一些额外的进程来进行一些分段传输 和清除的工作。 ( 4 ) 运行监控( m o n i t o r i n gp r o g r e s s ) 根据不同的应用及它们的运行时间，用户可以监控应用的运行进程，需要 时，甚至可能改变应用运行的位置或运行方式。目前实现这个步骤时，比较典 型的一种方法就是不停地重复查询资源的状态信息。 ( 5 ) 作业完成 当作业运行完成后，需要有一种机制去通知用户。例如，在并行机器上运 行作业时，提交脚本中会包含一个e - m a i l 参数去通知用户。然而，由于容错机 制的原因，这个通知过程实现起来会相当困难。 ( 6 ) 任务清除( c l e a n - u pt a s k s ) 作业运行完毕后，用户可能需要取回一些文件用来做数据分析，然后删除 一些临时设置，恢复原来的机器环境等。 2 3 网格资源管理调度的研究现状 针对网格资源调度的并行性和复杂性，在考虑资源调度的效率上一般要选 择好的调度算法，现阶段对资源调度的研究也主要集中在对调度算法的比较和 改进上。其目标主要是为了增加吞吐率和系统的使用效率。目前，国际上关于 网格资源调度方面的研究很多，下面我们介绍一些比较有代表性的研究成果。 1 ) g l o b u s g l o b u s 9 - 1 4 】是目前网格技术的旗舰产品，是g l o b u s 联盟的网格产品，它是由 a r g o n n e 国家实验室、南加州大学信息科学院、芝加哥大学联合开发的一个项目， g l o b u st o o l k i t 1 心是g l o b u s 项目最重要的成果。 g l o b u s 是一个分层式的体系结构，主要由资源代理( b r o k e r ) 、资源协同分 配器( c o - a l l o c a t o r ) 、资源规范语言( r e s o u r c es p e c i f i c a t i o nl a n g u a g e ，r s l ) 和 网格资源分配管理器( g r i dr e s o u r c ea l l o c a t i o nm a n a g e r , g r a m ) 组成，其体系 结构如图2 3 所示u 4 1 。 1 4 武汉理工大学硕士学位论文 图2 3g l o b u st o o l k i t 资源管理体系结构 g l o b u s 中的资源管理模块又称为网格资源分配管理器( g r i dr e s o u r c e a l l o c a t i o nm a n a g e r , g r a m ) 【1 3 】【1 4 1 ，位于g l o b u s 资源管理体系的底层，提供资 源分配、创建进程、监控和管理服务。g r a m 的下层是一些本地资源管理工具， 目前g l o b u s 支持l s f 、p b s 、c o n d o r 等“节点操作系统 以及包含f o r k 系统调 用的u n i x 操作系统。g r a m 的主要意义在于将所有异构的计算资源封装成同 构的计算资源。 g l o b u s 目前已经成为一种事实上的标准，其成功之处在于：( 1 ) 提供了一 个管理和调度计算资源可行的框架，并提供了良好的a p i 以设计资源调度器；( 2 ) g r a m 较好地解决了把各种异构计算资源封装成同构的、虚拟的计算资源；( 3 ) 通过r s l 语言较好地描述了对计算资源的资源请求；( 4 ) 初步解决了大规模数 据传输和对数据复制管理的问题；( 5 ) 初步探讨了网格资源管理中的协同分配、 q o s 等问题。 但就g l o b u s 项目本身而言，它只是一个可行的管理和调度计算资源的框架。 g l o b u st o o l k i t 也只是作为一个开源的工具包出现，它提供了一些a p i 来设计网 格调度器，现在许多关于网格调度的项目都使用了g l o b u s 提供的a p i 来设计它 们的网格调度器。因此从这个意义上来说，g l o b u s 并没有提供一个一般意义上 的网格资源调度器，也即它并没有涉及到具体的调度方法，同时它也没有考虑 负载均衡的问题。 1 5 武汉理工大学硕士学位论文 2 ) c o n d o r - g c o n d o r - g i s l 是g l o b u s 与c o n d o 一1 6 】合作开发的一个网格系统，它将g l o b u s t o o l k i t 的局域的( i n t e r - d o m a i n ) 资源管理协议同c o n d o r 的广域的( i n t r a - d o m a i n ) 的资源管理方法结合起来，使得用户在处