（计算机软件与理论专业论文）基于移动agent的网格资源调度研究.pdf

硕士学位论丈 m a s t e r st h e s i s 中文摘要 网格技术能够将分散在网络上的各种资源进行有机的整合，形成一个统一的整 体，为用户提供强大的计算能力和信息服务，被认为是继m t e m e t 之后一次重大的 科技进步。网格中的资源与传统的分布式系统资源相比具有分布性、动态性和异构 性的特征，这使得网格环境下的资源管理与分配变得相当复杂。 移动a g e n t 是一类特殊的软件a g e l l t ，它可以让程序在网络上从一台主机自主 地移动到另一台主机，代表用户完成指定的任务。我们将移动a g t 技术引入到网 格中，设计了一个基于移动a g e n t 的网格资源体系结构，构造了基于移动a g 铋t 的 网格层次资源监控模型，解决异构环境下的资源数据收集问题。 本文从网格资源的特点出发，探索一种更加合理的网格资源调度模型和更加有 效的调度策略。在分析了传统的调度模型的基础上，提出了基于a g e n t 的改进的层 次调度模型。调度模型分为全局调度层和局部调度层，不同的层次使用不同的调度 策略，从而使整个调度模型更加灵活有效。 好的资源调度算法能有效地协调和分配网格资源，并优化网格系统的性能。本 文根据网格环境下任务的时间相关性特点，对传统蚁群算法进行了改进，设计了一 种快速网格任务调度算法。该算法不仅解决了网格调度中多目标优化问题，而且依 据任务调度历史信息可以进行快速资源匹配。 使用网格模拟器酬d s i m 对f a c o 算法进行了仿真模拟。仿真结果表明f a c o 算法具有较高的求解速度，并且可以缩短任务的执行时间。 关键词：网格资源；资源调度；资源监控；移动a g e n t ：快速蚁群算法 a b s t r a c t w ec a ni n t e 翠a t ea l l 姑n d so fm er e s o 。c e sa c r o s st h en e n l e ti n t oau 1 1 i f o ms y s t e m c a l l e d 画ds y s t e m ，w m c hc 锄p r o v i d et l l eg i r du s e r sw i mp o w e r m ls e r v i c e ss u c h a s 廿l e s h 撕n go fi n f 0 珊a t i o na 1 1 dc o m p u t a t i o n a la b i l i 哆1 1 1 e 百r dt ec ：i 1 0 1 0 9 ) ，h a sb e e ns e e i l 嬲 姐h n p o r t a n ti n n o v a t i o ns 妣em ep o p u l a r i t yo fn 锄e t c o m p a 血g w i 也垃a d i t i o n a l d i s t r i b u t e ds v s t e i i l sr e s o u r c e ，1 er e s o u r c eo ft l l e 百r dh a s 廿1 ec h a r a c t e r i s t i c o f d i s 砸b u t i o n ，d y n a m i c ，h e t e r o g e n e i 劬s ot 1 1 er e s o u r c em 弛a g e m e n ta n dd i s t r i b u t i o ni n 舀r d s y s t e mi sm o r ec o m p l e x a f t e ra n a l y z e dt h et e c h n o l o g yo fm o b i l ea g 锄tt l l a tc o m dm o v e 白d mo n eh o s tt 0t l l e o t h e r 毹e l yi ni n t e m e t ，w ep r o p o s e da 撕e r a r c m c a lm o d e lo f 鲥dr e s 0 1 l r c e sm o i l i t o r i n g b a s e do nm o b i l ea g e l l t ，m a ts 0 l v et h ep r o b l e mo fc o u e c t i n gr e s o u r c ep 粗吼e t e rm h e t e r o g e n e o u s e 1 1 “r o n m e i l t t h em e s i si sl o o 虹n gf o ram o r er e a s o n a b l e 鲥dr e s o u r c es c h e d u l i n gm o d e la n d m o r ee f f i c i e n ts c h e d u l i n gp o l i c yb a s e do nm ec h 锄曲e r i s t i c so f 鲥dr e s o u r c e s a r e r d i s c u s s e dm et r a d i t i o n a ls c h e d u l i n p r o p o s e da i li m p r 0 v e dh e t e r o g e i l e o l l s 鲥dr e s o u r c e s c h e d u l i n gm o d e l ，w m c hw a sb a s e do nm o b i l ea g e n t 1 1 1 i sm o d e lc o m p o s e do f 舀o b a l s c h e d u l i n gl a y e ra n d 1 0 c a ls c h e d u l i n gl a y 既t h ed i f l 研e n tl a y e r s u s e dd i f i 研e i l t s c h e d u l i n gp o l i c i e st h a tm a d em i sm o d e lm o r ef l e x i b l ea l l dm o r e e f f i c i e n t o n e9 0 0 dr e s o u r c es c h e d u l i n ga l g o r i t 胁c o u l de 彘c t i v e l y 嬲s i 印t h e 鲥dr e s o u r c e a 1 1 di n l p r o v et h e 鲥ds y s t 锄p 加a 1 1 c e i nm i sp a p w ep r o p o s e da 酣ds c h e d u l e r u s i n gf a s ta n tc o l o n ya 1 9 0 棚瓶，w h i c hs a t i s f i e dt h em l 肌a l l y n n i c t i n g9 0 a l so f t l l e u s e r sa n dm er e s o u r c ep r o v i d 弱w e l l 的i m p r o v e dt l l ev e l o c i t ) ，o fm es c he d _ u 1 b y t a l ( i n ga d v a n t a g eo f1 l i s t o r i c a li i l f o 册a t i o no ns c h e d u l i n gt om a t c hr c s o u r c ef o rt a s k s q u i c k l y f i n a l l y ，s i n m l a t e dt 1 1 ef a c os c h e d u l i n ga l g o r i t h mi ng r i d s i m t h es i i l l u l a t i o nr e s u l t i n d i c a t e dt l l ef a c os c h e d u l i n ga l g o r i m mw a sm eb e s to n e i te r m a i l c e dm es p e c do f n l e a 1 9 0 r i t h ma s t r i n g e l l c ya 1 1 dr e d u c e d t h em a k e s p a l lo ff i m s h i n gm et a l s k s k e yw o r d s ：g i r dr e s o u e ；i 沁s o u r c es c h e d m i n g ；r e s o u r c em o i l i t o 血g ；m o b i l e a g e n t ；f a l s ta n tc 0 1 0 n ya l g o t h m 华中师范大学学位文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：鸯动两 日期：2 力吕年1 月z 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名：虏功丽 日期：劢必年多月z 日 导师 日期 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程”中的 规定享受相关权益。国童途塞握童后进卮i 旦圭生i 旦= 生；旦三生筮壶! 作者签名：痞劝厕 日期：劲纤月2 日 一吖弘厶 ：嗨 弛册 硕士学位论丈 m a s t e r st h e s i s 1 1 网格技术概述 第一章引言 1 1 1 网格的定义 网槲l 】技术出现于2 0 世纪9 0 年代，它代表了一种先进的技术和基础设施，是 近年来在学术界和产业界逐渐兴起的一个研究领域，也是继1 1 1 t e m e t 之后又一次重 大的科技进步。 那么究竟什么是网格呢? 全球网格研究的领军人物、美国阿岗( 吨o n n e ) 国家实 验室的资深科学家、g l o b u s 项目的领导人i a nf o s t e r 曾在1 9 9 8 年出版的网格：2 l 世纪信息技术基础设施的蓝图一书中这样描述网格：“网格是构筑在互联网上的 一组新兴技术，它将高速互联网、高性能计算机、大型数据库、传感器、远程设备 等融为一体，为科技人员和普通老百姓提供更多的资源、功能和交互性。互联网主 要为人们提供电子邮件、网页浏览等通信功能，而网格的功能则更多更强，它能让 人们透明地使用计算、存储等软硬件资源。 网格的发展经历了三个阶段：第一阶段是网格的萌芽阶段，开始于2 0 世纪9 0 年代早期，研究内容是关于千兆网试验床以及一些元计算方面的工作；第二阶段是 一些早期的试验，时间大概从2 0 世纪9 0 年代中期到晚期，出现了一些比较重要的 开创性和奠基性的研究项目，比如i w a y 、g 1 0 b u s 、l e 酉o n 等；目前处于网格的迅 速发展阶段，关于网格的研究、开发和应用项目大量出现，同时网格也不再仅仅局 限于科学研究，工业界与学术界联盟正致力于使网格在更广泛的领域得到推广和应 用。 网格代表了下一代的h l t e m e t 技术，它的最终目标是将地区间乃至国际间的网 格连接起来，实现计算资源、存储资源、数据资源、信息资源、知识资源、专家资 源等的全面共享。 1 1 2 网格的特点 网格技术的出现和快速发展，反映了社会对计算能力和资源共享的需求不断提 高。网格作为新兴的资源平台，能够将各种资源整合起来，转化成为一种随处可得 的、可靠的、标准的、经济的处理能力，具有自身的一些特剧1 】： ( 1 ) 分布性和异构性。组成网格的资源在地理位置上是分布的，这些资源可能 硕士学位论丈 m a s t e r st h e s i s 是计算资源、存储资源、数据资源、仪器资源等等，分布在地理位置不同的许多地 方。同时，组成网格的资源是异构的，比如计算资源，有不同类型的计算机，不同 的计算方式，不同的计算接口，不同的系统架构。同样对于存储资源和其它资源也 存在异构的问题； ( 2 ) 共享性和集成性。网格的最终目的就是资源共享，使任何网格用户都可以 非常方便的共享整个网格资源。同时，这种共享是深层次的，远远超出现在的因特 网的资源共享程度。网格可以实现多个共享资源的无缝集成，向用户提供统一的超 级计算环境，而且具有很强的集成性； ( 3 ) 自治性和动态性。网格上的资源首先是属于某一个人或者组织，网格资源 拥有者对资源具有最高级别的管理权限，网格应该允许资源拥有者对其资源有自主 的管理能力，因而具有自治性。也正因为网格资源拥有者对资源具有自治性，他们 可以决定资源加入或退出网格系统，从而使网格系统具有动态性的特征； ( 4 ) 抽象性与虚拟性。网格把实际的物理资源抽象为虚拟的逻辑网格资源，网 格用户或是网格的上层应用软件只需要遵循标准网格接口发出资源请求消息，就可 以获得符合该请求的资源，但用户得到的只是虚拟的逻辑资源，是物理资源的逻辑 抽象，用户和上层应用是看不到物理资源的。网格向用户屏蔽了物理资源的细节， 使得用户能够只关心“实现什么，而不必在意“如何实现”。 1 1 3 网格研究的意义 网格概念的提出从根本上改变人们对“计算”的看法，突破了以往强加在计算 资源之上的种种限制，给人们提供一种全新的更自由、更方便的方式使用资源，并 且它提供的处理能力是目前通过其它方式和途径所无法达到的【9 】。 ( 1 ) 突破计算能力大小的限制。以前大部分的用户无法得到足够的计算能力， 所以常用的是采取对模型以及算法进行简化的近似方法。而网格所提供的计算能力 要远远超过以前我们所能想象的程度，在这种计算能力的支持下，人们可以做许多 以前无法想象和无法完成的工作； ( 2 ) 突破地理位置的限制。资源是分布在各处的，有些资源是稀有或不可复制 的，有些资源甚至是无法和特定的地理位置分开的，这在很大程度上限制了这些资 源的使用。而网格把“资源所在的位置”对资源进行使用的限制打破了，使用者可 以异地远程使用这些资源： ( 3 ) 打破了传统共享和协作方面的限制。以前资源的共享往往停留在数据文件 传输的层次，而网格资源共享允许对其它资源进行直接的控制，而且共享资源的各 2 硕士学位论文 m a s t e r st h e s i s 方在协作时可以以多种方式进行更广泛地交流信息，充分利用网格提供的各种能 力。网格可以将不同地理位置、不同领域的专家、数据、设备等充分的结合在一起， 协同研究一个问题。 由于网格技术实现了更广、更深层面上的资源共享与协作，必将在人类探索自 然科学和改善社会生活方面发挥越来越重要的作用，对人们的生产、生活和学习等 方方面面产生日益深远的影响。 1 2 网格体系结构 网格体系结构是探讨网格技术时首先要回答的问题。因为网格体系结构给出了 网格基本组成部分与功能，描述网格各组成部分的关系以及各组成部分之间如何交 互集成。网格体系结构从最初的五层沙漏结构【2 1 ，演进到现在的w s r f 【3 1 ，代表了 网格技术发展的最新成果。 1 2 1 五层沙漏网格体系结构 以实现互操作为目的，基于协议和服务的网格五层体系结构包括：构造层、连 接层、资源层、汇聚层和应用层，结构如图1 1 所示。其中资源层和连接层共同组 成了瓶颈部分，使得该结构呈沙漏形状。其内在的含义就是各部分协议的数量是不 等的，对于其最核心的部分，要能够实现上层各种协议向核心协议的映射，同时实 现核心协议向下层各种协议的映射，核心协议在所有支持网格的地点都应该得到支 持，因此核心协议的数量不应该太多，这样核心协议就形成了协议层次结构中的一 个瓶颈。 ( 1 ) 构造层：控制局部资源，包括查询机制( 发现资源的结构和状态等信息) 、 控制服务质量的资源管理能力等，并向上提供访问这些资源的接口。构造层资源是 非常广泛的，可以是计算资源、存储系统、目录、网络资源以及传感器等等； ( 2 ) 连接层：基本功能是实现相互的通信。它定义了核心的通信和认证协议， 用于网格的网络事务处理。连接层的安全认证具有单点登录、代理、与局部安全方 法集成和基于用户的信任机制等特征； ( 3 ) 资源层：基本功能是实现对单个资源的共享。该层定义的协议包括安全初 始化、监视、控制单个资源的共享操作、审计以及付费等； ( 4 ) 汇聚层：基本功能是协调多种资源的共享。该层协议与服务描述的是资源 的共性，说明不同资源集合之间是如何相互作用的； ( 5 ) 应用层：这层是网格上用户的应用程序。应用程序通过各层的a p i 调用相 硕士学位论文 m a s t e r st h e s i s 应的服务，再通过服务调用网格上的资源来完成任务。 一应用 应用层 、瓣 汇聚层 资源与服务 的安全服务 资源层与连接层 蒸蠢 构造层 图1 l 五层网格体系结构 基于五层沙漏结构原理，g l o b u s 项目开发了网格计算领域应用非常广泛的模型 一g 1 0 b u st o o l 虹t s ，定义了构建计算网格的一组基本服务和功能。 五层沙漏体系结构影响十分广泛，它的特点就是简单，主要侧重于定性的描述 而不是具体的协议定义，容易从整体上进行理解。 1 2 2 基于w 曲服务的o g s a 网格体系结构 开放网格服务结构o g s a ( 0 i p e i l 嘶ds e 州c e 加c h i t e c t l l r e ) 是由全球网格论坛 ( g 1 0 b a lg r i df o r u m ，o g f ) 工作组于2 0 0 2 年制定的。 网格的五层沙漏结构是以协议为中心的“协议结构”，而o g s a 是基于w 曲 s e r v i c e 的“服务结构”。o g s a 中的服务包括各种计算资源、存储资源、网络、程 序、数据库等，简而言之，一切都是服务。 o g s a 有四个主要层次：物理与逻辑资源、w 曲服务与定义网格服务的o g s i 扩展、基于o g s a 架构的服务，以及网格应用程序，如图1 2 。 物理和逻辑资源层：资源的概念是o g s a 以及通常意义上的网格计算的中心部 分。它们通过虚拟化和聚合物理层的资源来提供额外的功能。通用的中间件，比如 文件系统、数据库管理员、目录和工作流管理人员，在物理网格之上提供这些抽象 服务。 w 曲服务层：o g s a 架构中的第二层是w 曲服务。这里有一条重要的o g s a 原则：所有网格资源( 逻辑的与物理的) 都被建模为服务。o g s i 规范定义了网格服务 并建立在标准w 曲服务技术之上。而且o g s i 进一步扩展了w 曲服务的定义，提 4 硕士学位论文 m a s t e r st h e s i s 供了动态的、有状态的和可管理的w 曲服务的能力。 毪罄誓。7 一 二j j j ；鲁毪鼍飞芦弘。：9 7 。? 。，j ：。7 。? j 譬? ? ；。母w 。， 网格应用程序 。 ，： 扩 、 “ ，4 影 “一基于0 g s a 构架的服务 i r 。绚 ，。：， o g s i 、7 莎j ，一一：”w e b 服务o ，j 。77 jj ，爹 ， ； 安全l | 工作流l | 数据l | 目录l 信息 i ， ， 7 服务器存储器 网络设备 之 豫。t 一? 。? ，| ? - 。i ，? j 。j 。_ j? ? 一，：。 图1 2 网格服务体系结构 基于o g s a 架构的网格服务层：包括四种类型的服务，即网格核心服务、网格 程序执行服务、网格数据服务、特定领域的服务。其中网格核心服务是基于o g s a 架构的服务层的主要构成部分。 网格应用程序层：随着基于网格架构的服务不断被开发出来，使用一个或多个 基于网格架构的服务的新网格应用程序亦将出现。这些应用程序构成了o g s a 架构 的第四个主要的层。 网格系统采用统一的w 曲服务框架，很自然就具备了原来w 曲服务的有利因 素：可以从服务描述中自动产生客户端与服务端的代码；将服务描述和互操作的网 络协议绑定在一起；与新出现的高级开放标准、服务和工具兼容；有广泛的工商业 支持等。 1 2 3w 曲服务资源框架 由于o g s i 规范过分强调网格服务和w 曲服务的差别，没有对资源和服务进行 区分，主要表现为网格服务和w 曲服务之间不能很好地融合，缺乏通用性，移植性 * z 工口 为了解决o g s i 和w 曲服务之间不能很好地融合的问题，2 0 0 4 年g l o b u s 联盟 和b i m 推出了w 曲服务资源框架( w 曲s e i c e sr e s o u r c ef r 锄e w o 咄w s r f ) 。w 曲 采用了与网格服务完全不同的定义：资源是有状态的，服务是无状态的。w s i 强的 规范是针对o g s i 规范的主要接口和操作而定义的，它保留了o g s i 中规定的所有 基本功能，只是改变了某些语法，并且使用了不同的术语进行表达。 作为o g s a 最新核心规范的w 曲服务资源框架w s i 强，它的提出加速了网格 硕士学位论丈 m a s t e r st h e s i s 和w 曲服务的融合，以及科研界和工业界的接轨。 o g s a 和w s i 强目前都处于不断的发展变化之中，对于w s r f 本身而言，由 于其提出不久，其规范还有待在实践中进一步检验，并逐步得到完善。 1 3 网格资源管理研究现状 目前，国际上关于网格资源管理方面的研究项目很多，代表性的项目主要有 g l o b u s 【5 1 、a p p l e s 【6 1 、n e t s 0 1 v e 【7 1 、n i m r o d g 等1 0 1 。 1 3 1g l o b 砒。i b o l k j t 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 锄g u a g e ，r s l ) 和网格资源分配管理器( g d d r e s o u r c ea 1 1 0 c a t i o nm a n a g g r a m ) 组成，它们之间的相互关系如图1 3 所示。 g r a m 位于g l o b u s 资源管理体系的底层，提供资源分配、创建进程、监控和 管理服务。g 删的下层是一些本地资源管理工具，目前g l o b u s 支持l s f 、p b s 、 c o n d o r 等“节点操作系统”，以及包含f i o r k 系统调用的u n 操作系统。g r a m 的 主要意义在于将所有异构的计算资源封装成同构的计算资源。 r s l 是描述g l o b u s 资源管理体系中各个模块之间资源请求的一种语言，它屏 蔽了各种平台在描述资源请求方面的差异，提供了一种标准的、对底层透明的资源 描述语言。 c o a 1 1 0 c a t o r 为分配给某个应用的资源集上提供映射、配置以及监控的功能。 g 1 0 b u s 工具包中设计了动态更新请求在线协同分配器( d ”锄i c a l l y - u p d a t er e q u e s t 0 1 1 l i n ec o a l l o c a t o r d u r o c ) 来实现这个功能。d u r o c 将抽取底层多重请求的每个 组成部分，去掉面向d u r o c 的部分，然后把请求提交给指定的g r a m 。d u r o c 可以对作业进行分块，并在g 洲之间进行协调。d u r o c 可以实现协同分配。提 交给d u r o c 的请求被分解为一个个的g r a m 请求，通过g r a ma p i 提交。 6 硕士学位论文 m a s t e r st h e s i s 田匣 亘 图l 一3g 1 0 b u s 资源管理系统 但是g 1 0 b u s 还需要进一步的改进，主要有： ( 1 ) 就g l o b u s 资源管理体系本身来说，g 1 0 b u s 并没有提供一个一般意义上的资 源代理( 资源调度器) ，而是提供了a p i 供各个网格项目设计自己的资源代理，因 此，从这个意义上讲，g 1 0 b u s 还停留在a p i 的层面上； ( 2 ) g 1 0 b u s 资源管理体系本身蕴含的调度机制呈现地是一个集中式的，至多是 一个层次式的结构。这种调度机制在一个局域范围内是有效的，但是随着网格系统 向广域的扩展，其性能会急剧下降。 1 3 2a p p l e s a 柙l e s ( a p p l i c a t i o nl “e ls c h e d u l i n g ) 是一个面向多用户分布式异构环境的高 性能调度器，如图1 4 所示。每个网格应用都通过自己的a p p l e s 来调度资源， a p p l e s 生成一个由该应用和目标计算网格所定制的调度方案并执行此方案。其中 网络气象服务( n e 研o r kw e a t h e rs e i c e ，n w s ) 负责动态收集系统的状态信息并预报 资源负载状况。 7 硕士学位论文 m a s t e r st h e s i s 图1 4a p p l e s 资源管理系统 a p p l e s 采用面向应用的调度策略。每当接收到一个作业时，系统为这个作业 产生一个a g e n t ，然后由这个a g e n t 根据作业和网格系统的动态和静态信息去最大 限度地挖掘系统的潜能以达到最小化运行时间的目标。 a p p l e s 采用了集中式的调度体系结构。 1 3 3n e t s o l v e n e t s o l v e 采用了基于a g e n t 的分布式调度体系结构，如图1 5 。n e t s o l v ea g e n t 担当了信息系统的责任，它记录了网络上可用的软硬件资源，每当一个新资源到达 网络时，这个新资源向某个n e t s 0 1 v ea g e n t 进行注册。n e t s o l v ea g e n t 还负责资源 发现和资源调度，用户的请求被传递到能确定最佳计算资源的a g e n t 上，并由此 a g e n t 在所选择的计算资源上发起计算并返回结果。在确定最佳资源和调度的过程 中，各个a g e n t 之间可以进行协作。 8 硕士学位论之 m a s t e r st h e s i s 图1 5n e t s o l v e 体系结构 1 3 4n i 脚帅d 【g n i m r o d g 的资源管理和调度遵循的是一种经济模式。n i l n r o 们是“计算资源 经济的网格框架( g r i dr e s o u r c e 心c h i t e c t l l r ef o rc o m p u t a t i o n a le c 0 n o m y ，g r a c e l 8 1 ) 中的一个组件，可以使用g r a c e 服务动态地与代表资源所有者的a g e n t 进行资源 贸易，以选择那些可以满足用户需求的、费用相对较低的资源。n i i l d d g 建立在 g l o b u s 环境上，因此可以利用g l o b u s 的功能定义作业的运行时间和代价等。 n i i t l r o d g 使用a g e n t 处理与管理相关的所有事件，包括资源发现、映射作业到合 适的资源、数据代码升级以及从多重结点收集结果等。 1 3 5 当前网格资源管理研究的不足之处 尽管g 1 0 b u s 等网格项目对网格应用提供了较好的支持，但是包括g l o b u s 在内 的很多网格系统在资源管理上仍存在以下问题【1 6 】【1 7 1 8 】： ( 1 ) 对多资源联合分配没有提供支持或支持很弱。这正是网格首要的问题，目 前已有的联合分配方法需要全局系统状态信息，通信开销较大，而且没有很好地解 决如何在分布自主的资源管理决策之间实现协调一致的资源调度问题，不能确保向 9 硕士学位论文 m a s t e r st h e s i s 应用提供相互匹配的服务，从而可能限制大规模的网格应用问题的解决； ( 2 ) 无法适应资源供需的动态变化。因为网格资源具有分布性和动态性的特点， 这使得资源在运行期间，性能可能会发生变化。然而现有的资源管理技术在考虑负 载变化的同时很少考虑资源能力的变化。所以在在设计开发新的网格资源管理系统 时，要求资源管理技术必须要实现对于资源供需动态变化的自适应，能够在线动态 调整资源管理策略； ( 3 ) 资源管理没有服务质量保证机制。已有的资源管理技术虽然都追求高服务 质量和资源利用率、尽量降低作业的平均响应时间，但是并不能保证作业的平均响 应时间能够低到某个具体的程度，也就是说没有具体的定量的标准来针对具体的应 用来衡量满足目标的程度，因而只能向用户提供“尽力而为 的服务，没有具体服 务质量保证机制。 1 4 本文研究重点及组织结构 1 4 1 本文研究重点 网格中的资源调度是网格研究中的一个核心问题，本文将移动a g e n t 技术引入 到网格系统中，并在此基础上提出了基于移动a g 锄t 的资源监控模型，在获得了调 度所需要资源数据之后，进一步提出了资源调度模型，并针对网格环境的特点，把 蚁群算法改进之后，引入到网格调度系统中来。论文主要从以下几个方面做了一定 的工作： ( 1 ) 设计基于移动a g e n t 的网格资源监控模型，为网格资源调度提供了及时有 效的资源信息。监控系统采用分层控制的方法，对全局监控和局部监控采取不同的 策略，提高监控系统的灵活性和监控的效率； ( 2 ) 改进的层次资源调度模型。根据局部调度和全局调度所要完成的不同的功 能，分别采取了不同的算法。把经过改进的蚁群算法引入到局部调度中，在提高算 法求解效率的同时，使它更适用于网格环境； ( 3 ) 负载平衡。因为网格资源具有动态性特征，在网格运行中可能会出现负载 不平衡问题。本文引入a b 角的方法来解决网格环境下的负载平衡问题； ( 4 ) 对经过改进的蚁群算法进行了模拟仿真和结果分析，进一步论证算法的可 靠性、高效性。 1 0 硕士学位论文 m a s t e r st h e s i s 1 4 2 论文组织结构 第章首先介绍了有关网格的基本知识和三个主要的网格体系结构，然后介绍 并分析了几个常见的网格项目中使用的网格资源管理系统，最后阐述了本文的研究 重点。 第二章对网格资源调度进行了深入分析，介绍了常见的调度算法，重点介绍了 本文使用的蚁群算法的基本原理。 第三章介绍了移动a g e n t 技术及其特点，把这一技术引入到网格资源监控中， 在此基础上提出了基于移动a g e n t 的网格资源监控模型，并对该模型进行了分析。 第四章提出了基于移动a g e n t 资源调度模型，在对蚁群算法做了改进之后，引 入到本模型中。而且针对网格资源的特点，改进了信息素的初始化及更新策略。 第五章介绍网格仿真工具g r i d s i m ，利用它对本文的调度算法进行了仿真分析。 第六章总结了文章所做的主要工作，另一方面也对进一步深入研究提出了新的 思路。 硕士学位论文 m a s t e r st h e s i s 第二章网格资源调度分析 网格的目的是使人们可以无缝地集成广域资源来合作解决问题，因此，在网格 环境里如何有效的调度资源成为影响网格发展是否成功的最主要的因素之一。同 时，由于网格的分布性、异构性、动态性和自治性，使得网格环境下的资源管理调 度变得十分复杂和具有挑战性。在网格资源调度的研究中，有两个重点内容：一是 资源管理的模型，它是研究资源调度的基础；另一个是调度算法，它是决定调度性 能的关键因素。本章在分析已有资源管理模型的基础上，提出了本文的资源管理模 型，并介绍分析了常用的调度算法。 2 1 网格资源调度概述 本文所讨论的网格资源调度问题基于以下定义：根据网格系统的状态信息和预 测信息，将互相独立的用户所提交的作业映射到适当的网格节点上并在适当的时刻 运行。 一 资资 作 任 资源代理 源源 一 用 1 业 务 分收 户 接 调 配集 度资源分配算法 器器 口一 器 甜 n可 网格资源目录 图2 - l 基本的网格资源管理和分配模型 在网格环境中，网格资源调度是网格资源管理系统的核心，如图2 1 。有效的 资源调度方案对优化资源的使用是非常重要的。资源调度负责接收用户发出的资源 共享请求，然后在资源和共享请求之间进行匹配，最后将符合共享请求的资源分配 给用户共享。 通常在进行资源和任务之间的匹配时，网格资源调度器需要考虑资源类型、资 源数量、资源性能以及各种资源的共享开销等因素，从而选择最符合用户任务请求 的共享资源。理想状态下，网格资源调度器在进行资源任务调度时只需搜索其资源 1 2 硕士学位论文 m a s t e r st h e s i s 数据库，根据用户提出的资源请求参数，如资源类型和性能来查找符合要求的资源。 但实际的网格系统大多具有异构性、分布性和动态性的特点，而且不同的网格资源 采取不同的共享策略，所以在一个大型的网格系统中，有效地定位共享资源或服务 是一项非常复杂的工作【2 1 。 如何确定网络环境对任务请求和资源调度的影响、当资源出现故障或退出时如 何及时调度其它资源，这些都要求资源管理系统具有探测资源当前工作状态的能 力，从而有效地调度符合用户要求的资源，同时在任务执行过程中出现异常时及时 做出调整。对资源进行监控是进行资源调度的基础，所以在第三章先对资源监控的 相关内容进行探讨。 2 2 网格资源调度模型研究 h 锄s c h e r 等人给出了3 个调度模型，分别是：集中式、层次式和分布式【z u l 。 集中式调度是指在网格系统中固定地指定一个或一些节点担任调度功能，系统 中所有的资源请求都发送到这些调度节点上，由这些节点控制和调度网格系统中所 有的资源请求节点和资源提供节点。集中式体系结构在逻辑上只有一个作业队列。 目前采用集中式调度的项目主要有a p p l e s 【2 1 1 、m s h n 【2 2 1 和n i m r o d g 【2 3 】。 在集中式调度方案中，因为所有任务都提交给网格调度者，网格调度者就必须 知道所有站点的信息。该调度方案就需要有一个高性能的中心结点，而且扩展性较 差，并且不适合于在不同站点使用不同优先级的调度。 层次式调度是指网格系统中的调度节点以层次方式组织起来，高层调度节点执 行粗粒度任务的调度，低层调度节点执行粒度较小的任务调度。逻辑上，每一层都 有各自的作业任务队列。可以把集中式调度视为只有一层的层次式调度。采用层次 式调度体系结构的有欧洲数据网格【2 4 1 、l e 西o n 和m o l 【2 7 1 。 在层次式调度方案中，所有任务仍然提交给网格调度者，然后由网格调度者将 任务发送给局部调度者。而且任务一旦发送给局部调度者，网格调度者就不能直接 干预任务的调度，即使该站点今后变得缓慢，也不能再转移到其他站点。 在分布式的网格资源调度系统中，没有指定某些固定的节点作为调度节点，网 格系统中每个节点都具有调度功能。逻辑上，网格中有多少个节点，就有多少个作 业队列。分布式调度又可以分为协作式和非协作式两类。协作式是指调度节点之间 进行协调以作出决策，非协作式指每个调度节点自己独立作出决策。采用分布式调 度体系结构的有n e t s o l v e 【2 8 1 、j a v e l i n 【2 9 1 等。 分布式调度方案除了在每个站点都有一个网格调度者，并且任务提交给各自站 硕士学位论文 m a s t e r st h e s i s 点上的网格调度者外，其他类似于层次式调度方案。分布式调度方案比层次式调度 方案的可扩展性好，但根据文献【4 1 的模拟结果，其性能比集中式与层次式调度方案 的性能差。 2 3 本文的资源管理模型 针对网格资源多样性和动态性的特点，我们采用树型拓朴结构【3 2 】来对所有结点 进行资源管理和任务分配，提出了如图2 2 所示的网格资源管理模型。树型结构的 一个主要优点是可扩展性好，新加入的结点可以插入系统中任意域中。为解决根结 点的瓶颈问题，根结点由若干个强连通结点组成，以避免节点单一失效。 本文所提出的树型模型分为两个层次：第一层是若干逻辑上的单元，称为局部 域，它是一个自治系统，拥有自己的本地资源信息服务代理，负责本域内资源的管 理；第二层是这些网格域相互连接构成的整个网格系统。多个局部域相互协作以服 务的形式提供整个环境中的全局资源供用户代理访问。每个局部域的内部结构对用 户来说都是透明的。 -_- 全局管理结点 管理结点 。 资源结点 管理结点 资源结点 图2 2 网格层次资源管理模型 全局管理结点功能：接收网格用户提交的任务、分析任务，获得任务的规模和 所需资源类型；获得各个域的权值和状态信息，为任务调度提供依据；执行调度算 法，将任务映射到合适的域；接收并整合执行结果，向用户提交结果。 局部管理结点功能：接收局部域内的网格用户提交的任务，进行域内调度；同 时也接收全局管理结点分配的任务：收集结点的负载信息，进行域内各结点的负载 平衡；接收各个执行结点执行结果，并向用户或全局管理结点提交执行结果。 本模型与层次式模型不同之处在于，层次模型中任务必须通过全局管理结点进 1 4 硕士学位论丈 m a s t e r st h e s i s 行一次调度，然后再由局部管理结点进行调度，这大大增加了任务调度的复杂性和 时间开销。在本模型中，局部域内的网格用户可以直接向局部管理结点提交任务， 由局部管理结点先进行局部调度，只有局部调度不成功时，才把该任务发送给全局 管理结点，由全局管理结点在整个网格系统内进行全局调度。对于较小的任务，如 果可以在局部域内调度成功，则可以大大减少调度和通信的开销。而且因为有一部 分任务调度可以不经过全局管理结点的干预，从而减少了全局管理节点的工作量， 因此本模型相比于层次模型更加灵活、有效。 而且该模型也和分布式模型不同，分布式调度在所有的节点上都有一个调度 器，而本模型只在管理结点上设置调度器，从而简化了调度过程，提高了调度效率。 因此该模型具有了层次式模型管理简单和分布式模型调度灵活的双重特点，同 时又抛弃了层次式模型中所有任务都要经过多层调度和分布式模型中效率过低的 缺点。 下面从扩展性、安全性和是否方便管理三个方面对本模型进行了分析： ( 1 ) 扩展性。网格系统规模随着研究和应用的深入将变得越来越大，异构性、 分布性、动态性特征更加明显。因此对于一个网格系统，拥有良好的可扩展性和自 适应性变得非常重要。本模型采用树形结构，树形结构本身的可扩展性使结点加入 和退出对整个系统的影响减少到最小，甚至可以忽略不计，从而使系统具有很好的 扩展性； ( 2 ) 安全性。将网格分割成多个域可以提高系统的安全性，单个域瘫痪或受到 攻击不会影响到其他的域，克服了集中式系统的单一管理所带来的问题； ( 3 ) 管理简单。复杂的网格资源管理工作，由两层多个管理结点共同承担，分 工明确，易于实现。 2 4 资源调度算法 2 4 1 常用调度算法分析 对于可用资源和不相关任务，资源调度的目的是寻找任务的最佳资源匹配，以 达到一个最优目标( 如执行时间最短、资源利用率最高和费用最低等) 。常用的方 法是使用启发式搜索程序寻找一个近似最优解。在网格环境中存在大量的任务和资 源，所以对于资源的调度算法的选择非常关键。常用的调度算法有： ( 1 ) 0 l b ( o p p o m l n i s t i cl o a db a l a n c i n g ) 【1 2 】：最简单的调度算法，称为随机负载均 衡。它只是简单地将任务分配到下一个即将空闲的计算资源上，若多个计算资源均 硕士学位论丈 m a s t e r st h e s i s 空闲，则随机选取一个。该算法可以实现负载均衡且实现简单，但由于没有考虑任 务执行时间和完成时间，难以得到较小的调度跨度。 ( 2 ) m i n m 洫和m a 】( m i n 【1 2 】算法：m i n _ m i l l 算法是首先将需要调度的任务组成 一个任务集合，然后计算出任务集合中每个任务的最短完成时间。调度是从任务集 合中选择有最短执行时间的那个任务分配到相应的资源上，同时从任务集合中删除 这个任务。然后开始新的调度，重复该过程直到任务集合为空。m a ) 【- m i l l 算法与 m i n m i n 算法相似，不同的是选择其中最长时间的那个任务进行调度，尽可能早地 完成执行时间长的任务。m i n 枷n 算法可能引发的负载不平衡，而m a ) 【幽算法的 不足之处在于它的运行时间较长。 ( 3 ) 遗传算法( g e i l e t i c 舢g o r i m l ，m ，g a ) 1 3 】：模拟生物在自然环境中的遗传和进化 过程而形成的一种自适应优化概率搜索算法。它将问题的