（计算机软件与理论专业论文）网格环境下多维qos指导的任务调度研究.pdf

摘要 网格计算是近年来得到快速发展的广域网络计算技术。网格计算环境相对于一 般网络计算环境来说有着更为复杂的特征，如存在多管理域和站点自治，系统的动 态性、异构性和通信延迟的不确定性等问题。 网格调度负责资源的协调与任务的调度，在网格环境里如何有效地实现任务调 度是影响网格计算成功的最重要的因素之一。近年来，网格环境下服务质量( q o s ) 问题渐渐受到关注，提供非平凡的( n o n t r i v i a l ) 服务质量成为网格的一大特征。调 度问题的实质，一方面是尽量满足用户q o s 需求，另一方面则要尽力优化系统吞吐 率、资源利用率等系统性能指标。因此，在网格任务调度中提供q o s 支持就成为网 格系统是否能够提供非平凡服务质量的关键。 本文围绕在网格任务调度中提供q o s 支持这一问题，开展了以下研究工作：首先 介绍了论文的研究背景，包括网格计算的概念、网格资源管理的概念以及网格任务 调度在网格资源管理中的地位等；然后，较系统地综述了网格的体系结构及网格环 境下的任务调度机制。其中，总结了网格任务调度的特点及目标；根据现有的研究 状况对网格任务调度机制进行了分析；介绍了已有的调度系统；并指出在网格任务 调度中引入q o s 支持的意义。 为了解决任务调度中多维服务质量要求的问题，本文提出了一种描述多维q o s 的模型，并基于这一模犁针对批调度提出了多维q o s 指导的任务调度算法，该算法 在优化系统性能的同时兼顾了用户多维o o s 需求。模拟结果表明，多维q o s 指导的 批调度算法相对于传统m i n - m i n 算法，系统吞吐率损失可以忽略不计，而用户满意 度则平均提升了大约1 1 在本文的最后，为了验证新算法在性能上的改善，采用了g r i d s i m 工具包对所 提出的算法进行实验仿真，通过与传统m i n - m i n 调度算法的进行比较，表明这一算 法在考虑多维服务质量的同时可以达到较好的系统吞吐量和用户满意度。 关键字：网格计算；任务调度；服务质量；资源管理 a b s t r a c t r e c e n t l y , g r i dh a sb e e nw i d e l yp a y i n ga t t e n t i o n ，w h i c hi sc o n s i d e r e da sah o tt o p i c i nt h er e s e a r c ho fc o m p u t e rs c i e n c e t h et a s ks c h e d u l i n gi saf u n d a m e n t a li s s u ei n a c h i e v i n gh i g hp e r f o r m a n c ei ng r i dc o m p u t i n gs y s t e m sa n dp l a y sa ni m p o r t a n tr o l e t h e r ei sag r e a ts i g n i f i c a n c ei ns c h e d u l i n gt a s k sc r o s sd i f f e r e n tp r o c e s s o r se f f e c t i v e l ya n d e f f i c i e n t l yw i t h i nt h ew h o l eg r i ds y s t e m ，b o t hf o rt h e o r e t i c a la n dp r a c t i c a la p p l i c a t i o n i t h a sb e e np r o v e dt h a tt h eg r i dt a s ks c h e d u l i n gi san p c o m p l e t ep r o b l e m ，a n di ti sh a r dt o f i n da l lo p t i m a ls o l u t i o ni np o l y n o m i a lb yu s i n gt r a d i t i o n a ls e a r c h i n gm e t h o d s ot h e m o d e mh e u r i s t i c sa l g o r i t h mi si n t r o d u c e dt oa p p r o a c ht h eo p t i m a ls o l u t i o n i nt h i s g r a d u a lp r o c e s s ，q u a l i t yo fs e r v i c e ( q o s ) s h o u l dn o tb ei g n o r e d g r i ds c h e d u l i n gs y s t e mi sr e s p o n s i b l ef o rr e s o u r c ec o o r d i n a t e da n dt a s ks c h e d u l i n g i ng r i de n v i r o n m e n t ，t h ee f f i c i e n c yo ft a s ks c h e d u l i n gi st h ek e yf a c t o rt h a ta f f e c t st h e e f f i c i e n c yo fg r i ds y s t e m d u r i n gt h e s ey e a r s ，m o r ea n dm o r ea t t e n t i o n sh a v eb e e np a i d t oq o s ( q u a l i t yo fs e r v i c e ) i ng r i de n v i r o n m e n t ，a n dt h ea b i l i t yt od e l i v e rn o n t r i v i a lq o s b e c a m eo n eo ft h ek e yc h a r a c t e r so fg r i ds y s t e m u s u a l l y , t a s ks c h e d u l i n gm e a n st r y i n g t os a t i s f yu s e r sq o sr e q u i r e m e n ta n dt r y i n gt oo p t i m i z es y s t e mp e r f o r m a n c e ，s u c ha s s y s t e mt h r o u g h p u ta n d r e s o u r c eu t i l i z a t i o n o b v i o u s l y , s u p p o r t i n gq o si ng r i dt a s k s c h e d u l i n gi st h ek e y i s s u ea f f e c t st h eg r i ds y s t e md e l i v e r i e sn o n t r i v i a lq o s f o c u s i n go nt h ep r o b l e mo fs u p p o r t i n gm u l t i p l eq o si n 鲥dt a s ks c h e d u l i n g , t h i s t h e s i sc a r r i e so u tr e s e a r c h e sa sf o l l o w s ： f i r s t l y , t h i st h e s i si n t r o d u c e st h eb a c k g r o u n do fr e s e a r c h ，i n c l u d e st h ec o n c e p to f g r i d ，t h ec o n c e p to f g r i dr e s o u r c em a n a g e m e n t ，a n dt h er o l et a s ks c h e d u l i n ga c t si ng r i d r e s o u r c em a n a g e m e n t s e c o n d l y , t h i st h e s i ss u m m a r i z e st h em e c h a n i s mo ft a s ks c h e d u l i n gi n g r i d e n v i r o n m e n t ，w h i c hi n c l u d e st h es u m m a r i z e sf o rt h ec h a r a c t e r i s t i c sa n dg o a l so fg r i d t a s ks c h e d u l i n g ，t h ea n a l y s i sf o rg r i dt a s ks c h e d u l i n gm e c h a n i s ma c c o r d i n gt ot h e r e s e a r c hu pt od a t e ，t h ei n t r o d u c t i o no f g r i ds c h e d u l i n gs y s t e m s ，a n dt h ee m p h a s i so nt h e p r o b l e mo fs u p p o r t i n gq o si ng r i dt a s ks c h e d u l i n g m o r e o v e r , i no r d e rt os o l v em u l t i p l eq o sr e q u i r e m e n t ，an o v e lm a t h e m a t i c a lm o d e l f o rm u l t i d i m e n s i o n a lq o sa n dah e u r i s t i ca l g o r i t h mb a s e do nt h i sm o d e li sp r o p o s e d t h e h e u r i s t i cf o rb a t c hs c h e d u l i n ge n a b l e st h ec o n s i d e r a t i o nf o ru s e r sq o sr e q u i r e m e n t s w h i l ea i m i n gt oo p t i m i z es y s t e mp e r f o r m a n c e t h es i m u l a t i o nr e s u l t sf r o mg r i d s i m d e m o n s t r a t et h a t ，f o rt h em u l t i q o ss u p p o r t i n gb a t c hs c h e d u l i n gh e u r i s t i c ，c o m p a r e dt o t r a d i t i o n a lm i n - m i nh e u r i s t i c i t s m a k e s p a nh a sa l m o s tn o d e c r e a s ew h i l ei t su s e r s a t i s f a c t i o ni m p r o v e s17 i na v e r a g e a tl a s t ，t h ea l g o r i t h mi se v a l u a t e dw i t h i nas i m u l a t e dg r i d s i me n v i r o n m e n t t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h en e wm u l t i q o sg u i d e dm i n - m i n h e u r i s t i cc a nl e a dt o s i g n i f i c a n tp e r f o r m a n c eg a i nf o rav a r i e t yo fa p p l i c a t i o n s k e yw o r d s ：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 ，o o s ，r e s o u r c em a n a g e m e n t 致谢 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文 中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义 上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或 成果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：獭山 日期：夕嵋年乡月7 2 日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本 人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单 位仍然为青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密矾 ( 请在以上方框内打“ ) 论文作者签名：莲沲c f l日期：加厶i ，年f 月fq 导师签名： 祈2l 二 日期：沙亏年f 月l 饵 ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使用) 第一章绪论 第一章绪论弟一早三：百了匕 因特网的出现使得人们能够大范围地共享各种信息，也使得人们比以往任何时 候都更加渴望能够更广泛地共享各种资源。使用凶特网作为底层，研究人员可以将 很大范围上地理分布的异构计算机系统集合在一起形成一个大规模的计算平台。该 领域的研究产生了一个新的软件体系结构，我们称之为网格( g r i d ) 1 1 。网格计算( g r i d c o m p u t i n g ) 的概念来源于电网( e l e c t r i c a lp o w e rg r i d ) ，人们试图实现一种方式，就像 家用电器能够极为方便的从电网中使用电力资源，计算应用也能够便利地从一个大 范围的分布的资源池中获取所需的各种计算资源。 近年来，国内外众多科研人员在网格计算方面开展了许多相关的研究工作，研 究结果表明网格计算确实是一个可行的高性能广域分布式计算模型，同时这些结果 也展示了许多急需解决的挑战性问题，其中，如何有效地管理网格资源、调度任务， 如何向网格用户提供确保质量的服务都足影响网格计算是否成功的重要因素。 1 1 网格计算的概念及演变 网格计算是近年来得到迅速发展的网络计算技术，人们试图将很大范围上地理 分布的异构计算机系统集合在一起形成一个大规模的计算平台。逐渐地，这一目标 深化为建立大规模计算和数据处理的通用基础支撑架构，将网络上的各种高性能计 算机、服务器、信息系统、海量数据存储和处理系统、应用模拟系统、虚拟现实系 统、仪器设备和信息获取设备( 如传感器) 等大型基础设施集成在一起，为各种相关 应用开发提供底层技术支撑，构造一个功能强大、无处不在的计算设施。 网格计算是由最初的元计算发展而来【3 】【6 】，目前为止，网格计算还没有一个十 分精确的定义。i a nf o s t e r 曾先后三次尝试给网格下定义。1 9 9 9 年，i a nf o s t e r 在与 c a r lk e s s e l n r a n 合编的著作【l 】里认为：计算网格是用以提供可靠、一致、普遍而且便 宜的高端计算能力的软硬件基本设施。那时候网格的研究范围还主要局限于计算网 格，而这也是网格的渊源所在。2 0 0 1 年，文献1 2 】从更加宽广的范围，在更为抽象的 层次上给出定义，认为网格主要涉及到动态、多机构的虚拟组织协调的资源共享和 问题解决，关键的概念是在一组参与者( 提供者和消费者) 之间协商资源共享的安排 并利用所得资源实现特定日标的能力。这时候的定义己经跳出了计算网格的范围。 并且指出了网格的本质和根本目的是资源犬享。2 0 0 2 年，i a nf o s t e r 在为g r i d t o d a y 7 1 撰写的特稿上给出了判断网格系统的三点标准，认为网格应该能够： 青岛大学硕士学化论文 ( 1 ) 协调不服从于中央控制的资源： ( 2 ) 使用标准、开放和通用的协议和接1 2 1 ； ( 3 ) 提供非平凡的( n o n t r i v i a l ) ) ) l 艮务质量。 这个标准是在o g s a ( o p e ng r i ds e r v i c e s a r c h i t e c t u r e ) t 8 j 的背景下提出来的，强 调的是实现资源共享的协议和服务。继o g s a 网格体系结构之后，在g l o b u s t o o l k i t 4 【8 】中，义提出了一种新型的w e b 服务框架，即w s r f 框架，它通过尽可能多的使 用现有w e b 服务标准以降低服务本身的复杂性，g l o b u s 项目希望w s r f 能够成为 网格服务的新标准。然而，w s r f 较o g s a 并没有本质的变化，最大的不同在于面 向服务的体系结构。这说明网格与w e b 服务的整合趋势，也说明网格学术界希望 网格在工业界逐渐拓展商业作用。 可见，网格还没有一个公认的、明确的定义，而且其内涵和外延也在不断的演 变。下面是一个较为通用意义上的定义：网格的核心问题是资源共享，网格就是在 缺少中央控制、没有全知者( o m n i s c i e n c e ) 以及强的信任关系的情况下对于地理分布 的各种大型基础设施的协同使用。 1 2 网格资源管理 网格计算环境相对于一般网络计算环境有着更为复杂的特征，如存在多管理域 和站点自治、系统的动态性、异构性和通信延迟的不确定性更高，硬件和软件两个 层次上都存在异构性等等。因此，实现有效的网格计算有很多需要解决的问题，具 体包括资源管理、任务调度、系统安全、编程模式、性能评测和数据存取等。 1 2 1 网格资源管理的概念 网格资源是指网络上能够被共享和利用的任何能力 9 1 ，包括传统意义上的物理 资源，如计算资源、带宽资源、存储资源、传感器、特殊仪器等，也包括虚拟的服 务，如数据库、数据传输、仿真等软件应用。 网格资源管理是网格的核心组件，其核心功能是识别资源需求，匹配和分配资 源，调度和临视资源，从而尽可能高效地利用资源【1 0 1 。网格资源管理侧重于控制网 格资源如何提供能力及可用服务给其它请求者，并不关心资源的功能，而是该功能 t 作的方式。 2 第一章绪论 1 2 2 网格资源管理的特点及要求 传统计算系统的资源管理已经得到了充分的研究，如批调度器、工作流引擎和 操作系统。网格资源管理与传统资源管理的目标都是高效、合理地利用资源，且都 具有并发性、共享性和随机性的特点。但他们之间有着很大的不同，他们的根本区 别在于网格资源具有广域分布性、异构性和动态性。 传统的资源管理系统在单台计算机或小规模局域网范围内上运作，对资源能够 完全控制，故可在与外界隔离的情况下实现高效的管理机制和调度策略。网格资源 管理的应用背景是开放的广域网，它对资源不能够完全控制，对资源的状态变化不 可预料，而异构的资源也使得资源管理任务更加地复杂化。这些问题使得传统的资 源管理工具无法胜任网格系统的资源管理与调度任务。 网格系统的特点及其对网格资源管理系统g r m s ( g i r dr e s o u r c em a n a g e m e n t s y s t e m ) 的要求体现为以下几个方面： 资源的分布自治性。资源跨多个管理域，地理上分布、自治，规模庞大， g r m s 需要提供资源、用户的全局命名空间。资源的共享与私有并存，不 同的管理域有不同的本地资源管理系统l r m ( l o c a lr e s o u r c e m a n a g e m e n t ) ，g r m s 对资源的没有完全的信息和控制，需要与l r m 交互， 协同使用资源。 资源的异构性。资源的种类繁多，有不同的类型和不同的性能特征，相对 于传统的资源管理系统，其异构性更强。g r m s 要解决异构环境下对相似 资源的配置和管理，定义标准的资源管理协议。 技术的多样性。资源属于不同的机构，不同的机构对资源有不同的使用、 调度策略和安全机制。g r m s 需要通过一种标准机制对资源和用户需求进 行描述：并且，资源管理框架要足够的灵活，易于扩展，以支持新的策略和 机制。 参与者目标的不一致性。参与者众多，资源使用者与资源提供者往往有不 一致甚至矛盾的目标、策略和需求模式。g r m s 需要提供相关机制实现他 们之间的协商及不同目标的平衡。 动态性与自适应性。用户需求和资源状态动态变化：资源提供者与资源消 费者的身份、需求可能发生变化，资源信息具有不确定性，资源的配置和 能力也在动态变化。g r m s 需要具有一定的自适应性，有效且高效地利用 资源，并具备一定的容错处理能力。 3 青岛大学硕士学位论文 资源的协同性。很多网格任务需要跨域协同分配、使用多个资源口【7 1 。g r m s 需完成跨域的资源协同分配，这需要了解不同域的安全机制、资源特征， 进行任务的跟踪，并处理各种形式的错误。 综上所述，网格环境的特殊性为网格资源管理带来了诸多新的挑战，需要进一 步对资源管理系统的相关机制进行研究。 1 2 3 网格任务调度问题 在网格系统中，任务调度是资源管理的核心组成部分。任务调度的实质就是按 照一定的策略为任务寻找合适资源的过程。网格任务调度可以定义为将网格作业映 射到各管理域的网格资源的过程，而调度通常是以整个执行时间( 吞吐率) 、资源利 用率及使用者和应用需求等指标为优化目标。一个典型的调度器在网格环境中的应 用示例如图i i 所示。 图1 1 调度器在网格环境中应用示例 一个网格系统的有效性在很大程度上取决于它的调度执行的有效性和效率。由 于网格作业本身的异构及需求的不同，其所需资源在广域上分布、本质上异构、由 不同的个人或组织拥有、有不同的存取和花费模式、负载和可用性动态变化，这些 复杂特征使得网格环境下的任务调度机制研究更具复杂性和挑战性，也使得任务调 4 第一章绪论 度成为网格研究中的一个热点与难点问题。 1 3 提供服务质量支持的网格任务调度研究 1 3 1 网格服务质量问题的提出 网格计算的初衷，是人们希望能够实现廉价、普遍的高性能计算，能够合作存 取各种数据信息，能够提供广域多媒体应用等。随着对网格计算的进一步认识，人 们发现，网格计算环境相对于一般网络计算环境有着更为复杂的特征，如存在多管 理域和站点自治，系统的动态性、异构性和通信延迟的不确定性更高，硬件和软件 两个层次上都存在异构性等。这些复杂性给网格系统的具体实现带来了很大的困难， 尤其是在多个服务协作使用资源时，性能和效率也容易造成降级，因此，网格系统 的服务质量难以得到保障。 随着网格应用的深入，人们不再满足于目前基于“尽最大努力 的网格基础设 施，渐渐地，人们希望网格系统能够提供可靠的服务质量，因此，网格q o s 问题应 运而生。在近年来的网格研究工作中，o g s a ( o p e ng r i ds e r v i c e sa r c h i t e c t u r e ) ! j ， o g s l ( o p e ng r i ds e r v i c e si n f r a s t r u c t u r e ) 1 2 j 以及w e b 服务资源框架( w s r e s o u r c e f r a m e w o r k ，简称w s e d 7 ) t 1 3 都要求所有的网格服务能够交付无缝的q o s 。 但是，目前的网格q o s 研究尚处于起步阶段，其基本的问题定义、具体描述、 参数量化等尚不清晰。 1 3 2 任务调度中提供服务质量支持的意义 在网格环境里如何有效地实现任务调度是影响网格计算是否成功的最重要囚素 之一。由于网格作业本身的异构及需求的不同，其所需资源在广域上分布、本质上 异构、由不同的个人或组织拥有、有不同的存取和花费模式、负载和可用性动态变 化。这些复杂特征使得嘲格环境下的任务调度机制研究更具复杂性和挑战性。与此 同时，随着网格应用需求的扩展以及网格面向服务架构的提出，如何在网格系统中 为用户提供服务质量支持也成为当前网格研究中的一个热点问题。 在嘲格的应用场景下，从用户的角度而言，：提交作业的过程总是伴随着对某些 服务质量的期望( 例如：最基本的，用户往往希望尽快得到作业执行结果) ；同时， 从系统的角度而言，处理作业的过程总是希望最大化系统吞吐率、最大化资源利用 率，网格系统的一大特征是提供非平凡的服务质量，网格调度系统承担了协调资源、 青岛大学硕士学位论文 调度作业的任务，它是网格系统是否能够提供非平凡服务质量的关键。因此，研究 在网格任务调度中如何提供服务质量支持就具有了非常重要的意义。 1 4 本文的主要工作 基于上述考虑，本文主要研究网格环境卜提供服务质量支持的任务调度问题， 主要工作介绍如下： ( 1 ) 较系统地综述了网格的体系结构及网格环境下的仃务调度机制。其中，总结 了网格任务调度的特点及目标；根据现有的研究状况从凋度的组织模式、应用模型、 状态估计、任务调度算法几个方面对网格调度机制进行了分析；介绍了已有的调度 系统；并指出网格任务调度中引入o o s 支持的意义。 ( 2 ) 较全面地综述了网格环境卜服务质量的概念与描述，并利用数学知识对网格 的多维服务质量问题进行分析，建立了多维服务质量的数学模型。 ( 3 ) 基于所建立的模型针对批调度提出了网格环境f 多维服务质量指导的任务 调度算法。该算法在优化系统性能的同时兼顾了用户多维o o s 需求。模拟结果表明， 多维o o s 指导的批调度算法相对于传统m i n - m i n 算法，在系统吞吐率损失可以忽略 不计，而用户满意度则平均提升了儿。 ( 4 ) 学习并掌握了使用g r i d s i m 进行模拟仿真的方法，在建立了相关的资源和用 户模型后，对所提出的算法进行了实验仿真，通过与传统m i n - m i n 调度算法的进行 比较，表明这一算法在考虑多维服务质量的同时可以达到较好的系统吞吐量和用户 满意度。 1 5 本文的组织结构 本文共分六章，组织结构如下： 第一章为绪论。主要介绍本文工作的背景和问题的提出。首先阐明网格的概念： 然后概括性介绍网格环境下的资源管理、任务调度问题，并指出网格服务质量以及 提供服务质量支持的任务调度问题的重要意义；最后，概括介绍本文的工作内容和 组织结构。 第二章从网格计算系统的早期体系结构模型及五层渗漏模型开始介绍，然后介 绍了g g f 提出的开放网格服务体系结构( o p e nc r r i ds e r v i c e sa r c h i t e c t u r e ) 。 第二二章重点介绍网格环境下的任务调度机制。首先介绍网格任务调度的特点和 目标，然后介绍现有的网格任务调度模型以及已有的调度系统，最后指出在任务调 度中引入服务质量支持的意义。 第一章绪论 第四章研究了网格服务质量的的概念与描述问题，首先区分性地介绍网格服务 质量与网络服务质量。并具体描述网格应用的服务质量需求。 第五章基于前一章对网格服务质量的描述，建立了多维服务质量的数学模型， 并针对批调度提出了基于这一数学模型的任务调度算法。 第六章详细介绍了g r i d s i m 网格模拟器的设计与实现。首先，介绍了常见的网 格模拟工具，然后通过体系结构、具体实现细节对该模拟器进行详细介绍，并使用 g r i d s i m 工具包对所提出的算法进行了模拟和验证。最后通过实验结果表明，本文提 出的调度算法相对于传统调度算法能够更优地适应用户和系统的需求。 第七章总结全文，并对将来继续进行的工作进行展望。 7 青岛大学硕士学似论文 第二章网格的体系结构 无论是计算机还是因特网，都有自己内在的体系结构，网格汁算系统也不例外。 一般认为，网格体系结构足关于如何建造网格的技术，包括对网格基本组成部分和 各部分功能的定义及描述、网格各部分相互关系与集成方法的规定、网格有效运行 秽【锘0 的亥0 画。 2 1 网格体系结构的概念 目前有四种常见的网格体系结构，这些体系结构可以归纳为4 中形式：抽象层 次结构、积木块结构、概念空问结构和混合模式结构。 1 抽象层次结构， 在抽象层次结构中，最具代表性的是伊恩一福斯特( i a nf o s t e r ) 等人在1 9 9 8 年 提出的五层沙漏结构模型。该结构足以“协议”为中心的，强调协议在网格资源共 享和互操作中的地位。但是，并1 i 是所有的服务或者应用都可以分解为标准而底层 的协议，而且很多时候，人们会本能地按照积木块结构的思想来思考问题，于是就 提出了计算网格的积木块体系结构。 2 积木块结构 积木块结构实际上是一种组件结构，它强调的是计算网格中不同的功能模块相 对独立，又相瓦联系的关系。在积木式网格系统中，整个系统的各个部件采用积木 式模块方式构建，具有很强的伸缩性。 3 概念空间结构 计算网格中存在着一系列的概念，如元数据、目录、资源、服务、协议、实体 和对象等，这些概念构成了计算网格的概念空问，根据这些概念之间的关系形成的 网格体系结构，称谓概念空间结构。与上面两种体系结构相比，概念空间体系结构 的层次特征不够清晰，它强调的是各部分在概念上的关联。这一方法已在元计算系 统和数据网格i 1 得到应用，代理技术和面向对象技术是实现概念关联的主要方法。 4 混合模式结构 混合模式结构就是以上各种结构的有机组合。开放网格服务结构( o g s a ) 就 是一种具有代表性的混合结构。它是在以i b m 为代表的t 业界的影响下，基于五层 沙漏模型，在考虑到w e b 技术的发展与影响后，结合w e bs e r v i c e s 而提出的，是目 前得到广泛流行和支持的一种混合体系结构。 8 第二章网格的体系结构 2 2 五层沙漏模型 五层沙漏结构的主要特点是结构简单、层次清楚。该结构侧重于定性的描述而 不是具体的协议定义。五层沙漏结构并不提供严格的规范，不是对全部所需协议的 完整罗列，而是对该结构中各部分组建的通用要求进行定义，结果是一个开放的、 可扩展的体系结构提供虚拟组织的解决方案。该结构将组件形成一定的层次关系， 每一层的组件具有相同的特征，上层组件可以在任何一个底层组件的基础之上建造。 应用层 传输层 网络层 二匦e 囤 图2 1 五层沙漏结构与i n t e r n e t 协议的对比 五层沙漏结构是从g l o b u s 系统中抽象出来的，对网格的初步影响十分广泛。尹 恩一福斯特等人使用图2 1 描述了g l o b u s 的五层沙漏模型结构，并把它与i n t e m e t 协 议模型进行了比较。五层沙漏结构的一个重要思想就是以“协议”为中心，同时强 调服务和a p i 、s d k 等的重要性。它类似于传统的t c p i p 网络协议栈，将网格分 成五个互相关联而不均等的层次。在五个层次中，资源层和汇聚层大大地拓展了网 格应用层的功能，对传统网络中的许多应用层问题进行了封装，因而功能进一步强 大，并为用户提供更加透明的使用手段。 2 2 1 各层的功能 五层沙漏模型按照模型中各个组件与其共享资源的距离远近，将对共享资源进 行操作、管理和使用的功能分散在五个不同的层次中，越向下层就越接近物理的共 享资源，与特定资源相关的成分就比较多；越向下层就越感觉4 i 到共享资源的细节 特征，也就是说上层是共享资源的更加抽象表示，因此就不需要关心与底层资源相 关的具体实现问题。为了便于理解，该结构还将这五层与t c p i p 网络协议进行了粗 略的对比。该模型在网格底层( 即构造层) 和网格高层( 即应用层) 对网格行为和 q 青岛大学硕士学位论文 状态作了将少规定，从而形成了沙漏的两端；然而在它的中间层( 即资源层和连接 层) ，则作了比较严格的规定和限制，形成了沙漏的中间部分。 五层沙漏结构的五层由下至上分别为：构造层、连接层、资源层、汇聚层和应 用层。下面对这五层的功能分别进行描述。 1 构造层 网格构造层的基本功能是控制局部的资源，向上提供访问这些资源的接口。构 造层资源可以是计算资源、存储系统、目录、网络资源以及传感器等。广域分布的 计算机、工作站、机群、w e b 服务器、数据库服务器和超级计算机系统是构造层的 物理资源，他们本身附带的文件系统、通信系统构成了构造层的逻辑资源。 构造层应该实现的基本功能包括查询机制( 用来发现资源的结构和状态等信 息) 、i , n i i 务质量的本地资源管理能力等。 2 连接层 连接层的基本功能就是实现资源问的相互通信。它定义了核心的通信和认证协 议，用丁网格的网络事务处理之中。 通信协议允许在构造层资源之间交换数据，包括传输、路由、命名等功能。建 立在通信服务之上的认证协议提供加密的安全机制，用于识别用户和资源。 3 资源层 资源层的主要功能就是实现对单个组织内的资源共享。资源层建立在连接层的 通信和认证协议之上，定义的协议包括安全初始化、监视、控制单个资源的共享操 作、审计及付费等。资源层协议只考虑单个的局部资源，忽略了全局状态和跨越分 布资源集合的原子操作。 资源与连接协议形成了沙漏模型的瓶颈部分，因此这个协议集合要小，而且尽 量标准化。这些协议要集中涵盖不同资源类型的基本共享机制，但是又不能对高层 协议的类型和性能有太多的约束。 4 汇聚层 汇聚层的主要功能是协调多个资源组织间的资源的共享，而资源层的主要功能 则是实现“单个虚拟组织”的资源交互共享。汇聚层协议与服务描述的是资源的共 性，并不涉及资源的具体特征，只是说明不同资源集合之间是如何相互作用的。 由于汇聚层协议在资源层通用目的的协议的基础上实现更高级的应用，因此资 源层协议必须是通用的，而且可以广泛应用。 5 应用层 应用层是在虚拟组织环境中存在的。从应用程序员的观点看网格结构，应用是 根据在任意层次上定义的服务来构造的。在每一层都定义了协议，以提供对相关服 务的访问，这些服务包括资源管理、数据存取、资源发现等。在每一层，可以将a p i 1 n 第二章网格的体系结构 定义为与执行特定活动的服务交换协议信息的具体实现。应用层的应用可以提供更 高级的框架和库调用。 2 2 2 模型的特点 1 共享 传统的共享只是局限在交换文件，而这里则更强调对计算机、软机、数据及其 他资源的直接访问。这种需求在工业、科学以及工程等许多领域都会遇到。而且这 种共享还必须是高度受控制的，需要在资源控制者和使用者之间定义什么是可以共 享的，那些人可以共享，在什么条件下可以共享。而“虚拟组织”就足基于这样的 一些共享规则，它是由一些入或者团体形成的集合体。共享是一种随时间变化的动 态的共享，而不是静态的共享。网格具有动态的特点，网格资源的共享也必然满足 动态性的要求。 因此，在五层沙漏结构中的共享，是深层次的、广泛的、动态的、具有多种多 样形式的有条件受控制的共享。 2 互操作 互操作也就是对资源的直接访问，从而实现资源的共享。这种共享关系需要在 任意的组织、团体之间在一开始就建立了，也可以动态增加新的成员，并且可以跨 越不同的平台、语言和编稗环境，在这样的情况下，如果不能提供一种互操作机制， 使得可以跨越不同的组织边界、使用策略以及资源类型，就不能达到共享的目的。 没有互操作机制的保证，动态虚拟组织的形成是不可能的，而且可以形成的虚拟组 织的类型是非常有限的。 3 协议 协议是指为了实现特定的操作而定义的分布式系统元素之间交互的方式，以及 交互过程中交换的信息结构。它侧重于外部行为而不是内部特征。共享需要互操作， 而互操作有需要定义协议，因此五层沙漏结构特别重视协议的定义。如同w e b 通过 提供统一的协议和语法来进行信息共享，在网格中也需要标准化的协议和语法用于 通用的资源共享。 4 服务 服务是由它使用的协议和实现的行为定义的，标准协议使得定义标准服务更加 容易。标准服务( 如对计算机的访问、存取数据、资源发现、协同调度、数据复用 等) 的定义抽象了资源的相关细节，所以非常有利于虚拟组织的应用开发。 5 a p i s d k 在五层沙漏结构中，同时还提供a p i ( a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e ) 和s d k 青岛大学硕士学位论文 ( s o f t w a r ed e v e l o p m e n tk i t s ) ，使得在建立网格应用时可以在抽象的基础上提高编 稃的级别。因为有更多的应用是针对虚拟组织的，而不是针对底层的互操作、协议 或者服务。开发者要能够在复杂、动态执行的环境中开发高级的应用，借助于a p i 、 s d k 就可以加速代码开发，实现代码共享，以及增强应用的可移植性。a p i 和s d k 是附属于协议的，而不是协议的替代。 6 沙漏彤状 该模型之所以称为沙漏结构，是因为各部分协议的数量是不同的，对于其核心 的部分，要能够实现上层各种协议向核心协议的映射，同时实现核心协议向下层其 他各种协议的映射，核心协议在所有支持网格计算的地点都应该得到支持，因此核 心协议的数量不应该太多，这样核心协议就形成了协议层次结构中的一个瓶颈，在 五层结构中，资源层和连接层共同组成这一核心的瓶颈部分。 沙漏核心的思想可以和微内核的操作系统进行类比。微内核操作系统只实现一 些关键的基本功能而把大量与特定设备有关和与应用有关的部分交给其他部分完 成。一个小的核心是有助于移植的，也可以比较容易地实现和得到支持。资源是多 种多样的，应j h 需求更是复杂多变的。因此，核心部分是非常重要的。 1 2 第三章网格环境下的任务调度机制 第三章网格环境下的任务调度机制 网格环境下的任务调度机制是影响网格计算成功的最重要因素之一。区别于本 地调度，网格任务调度的对象往往跨越多个管理域，各管理域隶属于不同的组织， 采用不同的策略操作其资源，而调度中涉及的网格用户和网格资源提供方的目的也 可能不一致甚至相互抵触。由于网格任务调度面临的是一个n p 完全问题，它引起 了众多学者的关注，成为目前网格计算研究领域的个焦点。本章将介绍网格环境 下的任务调度机制。 3 1 网格任务调度的特点及目标 在网格系统中。任务调度系统是其重要的组成部分，它要根据任务信息采用适 当的策略把不同的任务分配到相应的资源节点上去运行。由于网格系统的异构性和 动态性，以及运行于网格系统之中的应用程序对于资源的不同需求，因此，网格任 务调度相比本地调度更加复杂。 3 1 1 网格环境下任务调度的特点 网格任务调度系统具有以下几个特点： 任务调度是面向异构平台的。网格系统是由分布在i n t e m e t 的各类资源组成 的，包括各类主机、工作站甚至p c 机。它们是异构的，可运行在u n i x 、 w i n d o w s n t 等各种操作系统下，也可以是上述机型的机群系统、大型存储 设备、数据库或其它设备。因此网格系统中的任务调度必须面向异构平台， 并在这些平台上实现网格任务的调度。 任务调度不干涉网格节点内部的调度策略。在网格系统中，各网格节点的 内部调度策略是自治的，网格任务调度系统干预其内部的调度策略是没有 必要的，也是不可能的。 任务调度必须具有可扩展性。网格系统初期的计算规模较小，随着超级计 算机系统的不断加入，系统的计算规模也必将随之扩大。因此，在网格资 源规模不断扩大、应用不断增长的情况下，网格系统的任务调度必须具有 可扩展性，不致降低网格系统的性能， 7 。” 任务调度能够动态自适应。网格中的资源不但异构而且网格的结构总是不 停地改变：有的资源出现了故障，有的新资源要加入到网格中，有些资源 重新开始工作等。总之网格的动态性明显，因此任务调度系统必须适应网 青岛大学硕士学化论文 格的这利动态性，从可利用的资源中选取最佳资源为用户提供应用服务。 3 1 2 网格环境下任务调度的目标 简单地说，网格仟务调度的目标就是要对用户提交的任务实现最优调度，并设 法提高网格系统的总体吞吐率。具体的目标包括：最优跨度( o p t i m a lm 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 ) 、经济原i 贝l j ( e c o n o m i c p r i n c i p l e s ) - 等。 1 1 最优跨度。跨度是一个最主要、最常见的目标，指的是调度的长度，也就 是从第一个任务开始运行到最后一个任务运行完毕所经历的时间。它也常 常作为衡量系统吞吐率的指标。跨度越短说明调度策略越好。当用户向网 格系统提交任务后，最大的愿望是网格系统尽快完成自己的任务。可见， 实现最优跨度足用户和网格系统的共同目标。 2 ) 服务质量q o s 。网格系统要为用户提供计算和存储服务时。用户对资源需 求情况是通过服务质量的形式反映出米的。任务管理与调度系统在进行分 配调度任务时，保障网格应用的服务质量是完全应当的。 3 ) 负载均衡。在开发并行和分布计算应用时，负载均衡是一个关键问题。网 格系统更进一步扩展了这个问题。网格任务调度是涉及交叉域和大规模应 用的调度。解决好系统的负载均衡是一个非常重要的问题。 4 ) 经济原则。网格环境中的资源在地理上是广泛分布的，而且每个资源都归 属丁f 、：同的组织，都有各自的资源管理机制和政策。根据现实生活中