（计算机应用技术专业论文）基于网格环境的任务调度算法研究.pdf

东南大学硕士学位论文 摘要 i n t e m e t 的流行使得人们信息通讯和协同工作变得容易，而网格可以帮助人们更进一步 的共享i n t e m e t 上汇聚的一切资源，包括计算资源、数据资源、c p u 、存储器、数据库、应 用软件、文件乃至硬件设备等。 任务调度是网格计算的关键技术之一。任务调度的作用是根据当前系统的负载情况，对 系统内的任务进行调度，它是网格能否高效使用资源和快速完成任务的关键要素。网格环境 中的任务调度与用户的利益切身相关，因此，任务的调度算法不仅从时间上考虑优化，而且 从费用上考虑优化。 本文的研究重点主要集中在网格环境中涉及的独立任务集调度算法方厩。作者在对网格 和网格计算的知识背景以及该领域的研究现状进行认真分析的基础上，提出了两个新的任务 调度算法。其一是根据网格环境中计算资源的q o s ( q u a l i t yo fs e r v i c e ) 属性提出的一个2 层 混合启发式算法，第一层采用o g m m ( q o sg u i d e dm i nm i n ) 算法对时间进行优化，第二 层在保持原有优化时间的前提下采用遗传算法的变异因子对费用进行优化。试验结果表明该 算法在时间比q o m m 和m i n - m i n 略优的情况下费用得到很大的优化。其二是基于m i n m i n 的极限下压算法。主要用到了模拟退火算法的原理和装箱理论。该算法侧重于时间的优化以 及提高系统平衡度。此外，本文设计并以j a v a 语言实现了一个网格仿真系统。该仿真系统 主要包括网格环境模拟模块、任务调度器模块和任务调度性能评价模块等。其中需要模拟的 i n t e r n c t 上的随机因素运用排队论相关知识构建，并在该仿真系统上对提出的两个算法进行 仿真实现和性能分析。 关键词：网格计算，任务调度，q o s ，遗传算法 东南大学硕士学位论文 a b s t r a c t t i l ep o p u l “l yo fi 玎t e m e tm a d ep e o p l ee a s yt oc o m m l i l l i c 砒ea n dc o o p e r a l e ，a n d 硎dw i l l h e l pp e o p l es 1 1 a 础辩u r c 髂i ni n , m e tb e t t e r t h e 姗u r c 嚣k l u d ec o m p u t m g 佗s o u f c ，d a t a r e s o u r c e 南c p u ，m 曲1 耐幅，d a t a b a s 铭，a p p l i a a t i o ，f i l e sa n dh a l d w 玳e q u i p m e n t s t h s ks c i 刷u “n gi so 鹏o ft i l cn l o s ti m p o r t a n tt e c l l l l i q l l e sj l l 鲥dc o m p l i t i n g n ef i 玎l c t i o no f t a s ks c h e d u l ei st o 站b e d u l et a s k sa c c o r d i n gt ot i i eb a l 卸c eo f s y s t e ma n dt oi i i i p r o v et l i e 硝丘c i 朗c y o fs y s t e m t a s k h e d u l i n gi i l 鲥dt i 勰ac l o 辩陀l a t i o m h i pw i t hu 靶r s b e n e f i t s s o ，b o t l ll l l e w 删o a db a l 锄a n dc o s ts h o e db et a l 【i i l gm a c c o u n t t h er 粼a r c ho f 躺p a p e rf b c l l s e s0 nm d e p e n d 如t 协s k ss c h 酣u l i n gi l l 面d b a s e do l i 岫 l 【i l o w l e d g e0 f 鲥d 柚d 卯dc o m p 埘n g ，t w on e wt a s k 辩h c d i l l i n g l e u r i s 蛞ca l 9 0 6 t h m sh a v eb e e n p 即s e , d 1 1 1 ef i r s ti sah y b r i d2 t i e rt i m e - c o s to p t i m i z i n gs c h e m aw h i c hi sb a s e do nq o so f c o m p i n g 化u r c e s h l 廿d sa l g o r i 吼q g m mi sa d o p 钯dj i it h et i mp h a s et oo b t a i na b c d u l e w 抽o p t i m i z e dm a k e s p 啦ag ao n l yw 曲m u t a t i o no i 增删甜i sr e e dt oo p t i m i z ec o s tn o t i 1 1 c r 瞄i n gm a k e s p 柏i l lt i l es e c o n dp h a s e e x p e r i l i l e m a l 啜u l 毽s h o wt h a tl l l ep r o p o s e d 印p m a c h c a l lg e tl o w e rc o s tt h a nt l 悖o t i l 盯t w ow i mt h ef l a n l ee o m p l 嘶o nt i m e 赫q g m m ，w h i c hi sb e t t e r t l l 柚t h a to f m i n - m m t h e 辩c o n di sa h y b r i da l 鲥m mb 鹞e do nm i n m i n s i i i l u l a t e da 皿e a l i n g h e u r i s t i ca n dp a c k i n ga 1 9 0 删m sh a v eb e e nu s e di l lt i i i sa l g 耐t l l m no p t i m i z e st l l em a k e s p a n 龃d s y s t e ml o a dh a j 卸f i i 坩l e 加。煽a 鲥ds i m 删o ns y s 咖i sd 豁i 鲷c d 彻di l | 1 p 】咖铷t 蚵j a v a l 柚g u a g e t h es i l n u l 缸i o ns y s t e mm e t u d e dg r i de n v i r o m c n ts i m u l 撕m o d u l e ，t a s ks c h e d i l l i n g m o d m ea n dr , e r f o r m a n c ee s t i m 蜘m o d u l e 1 1 1 ep m p o s e d 姆f i t h m sw 哪s i m u l a 伽a n dm c i r e 伍c i 曲c i 嚣h a v eb e a b 口d k e yw o r 凼：g 棚c o m p u n n g ；乜s k h e d u h g ；q o s ；g a 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文 的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档 的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借 阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东 南大学研究生院办理。 研究生签名：哇丝垒导师签名： 第一章绪论 1 1 研究背景 第一章绪论 i n t e r n e t 的流行使得人们信息通讯和协同工作变得更加容易，同时高性能计算机的利用 以及低消耗高速网络的发展也在改变人们的思想观念和使用计算机的方式。特别是近几十年 的计算机硬件和软件的迅猛发展，使得计算机网络成为单个统一强大的虚拟超级计算机的梦 想正在逐步成为现实。人们希望更进一步地共享i n t e m e t 上的汇聚的一切资源，包括数据资 源、c p u 、存储器、数据库、应用软件、文件乃至硬件设备等。而网格的思想就是把整个因 特网整合成一台巨大的“虚拟超级计算机”，实现各种资源的全面共享，同时将各种资源以 有效的方式动态的组织起来，隐藏其内部异构性和动态性，形成一个对用户相对透明的网格 环境，因此建立各种“网格”，诸如计算网格、信息网格、知识网格、服务网格等便是实现 人们更进一步共享资源愿望的途径。 i n t e m e t 中的各种资源存在着形态、性能以及使用和服务方式等各个方面的差异，这种 多层次的异构性和系统状态的不确定性造成了用户有效使用系统各种资源的巨大困难。此时 网格计算应运而生。网格【1 】1 2 1 是借鉴电力网( e l e c t r i c p o w e r g r i d ) 的概念提出的【3 】【4 】，它的最 终目的是希望用户在使用网格计算能力时如我们在生活中使用电力一样方便。我们在使用电 力时，并不需要知道电力是以何种方式产生，不管是风力发电还是核反应发电，最终用户使 用的都是统一的电能。网格也希望为最终的使用者提供的是与地理位置无关、与具体的计算 设施无关的通用的计算能力。但网格环境中的资源情况和用户要求都比电力网复杂得多。在 电力网中，只有统一的电能，而且用户的要求基本一致；而在网格环境中，资源多种多样， 而且分布共享、自治统一管理，此外资源的异构性和强动态性使得网格的性能和服务质量很 难满足用户存储容量、网络带宽和安全性稳定性等多方面的要求。 基于网格的问题求解称为网格计算p “卅。网格计算是构筑在i n t e m e t 之上的一种新兴 技术。在网格环境中的每一台计算机便是一个计算节点，而整个的计算环境便是由所有的计 算结点编织成的一张网格，也因此称之为网格计算。将整个网络整合而成的虚拟超级计算机 具有充分利用网上闲置资源因而价格低廉的特点，此外，它的超强计算能力也是足以令任何 高性能机望尘莫及的。 资源管理和任务调度是网格计算的关键技术。其中任务调度主要是根据当前系统的负载 情况，对系统内的任务进行动态调度，提高系统的运行效率。任务调度是并行和分布式计算 的一个主要部分，在这方面已经进行了大量的研究，并且有许多成果已经被普遍接受。然而， 随着网格计算的出现，为了解决网格环境中的新问题我们需要新的任务调度算法在网格环 境中的调度算法不再仅仅关注于一个计算节点或一个虚拟组织内的一个应用程序的予任务， 而是一个个相互独立没有联系的完整的任务。同时，资源提供者和资源用户有不同的目标和 策略，从资源用户角度来考虑，他不仅仅关注任务完成时间，而且应该以个体经济利益最大 化为目标来使用资源，所以在保证用户提交任务尽早完成的同时，对用户的费用进行优化。 即在复杂的网格环境中，需要以用户为中心的资源分配策略。为此设计的任务调度的主要目 标是将所有用户提交的独立的应用任务调度到可获得的计算资源，使得任务总的运行时间 ( m a k e s p ) 和费用( c t ) 最小并设法提高网格系统的总体吞吐率，实现最优调度。 东南大学硕士学位论文 1 1 1 研究现状 至今为止，网格主要沿着标准化、技术融合、大型化趋势而发展。目前，国外网格计算 【8 】的研究主要在美国和欧洲。美国政府用于网格技术基础研究经费己达5 亿美元。美国军 方正规划实施“全球信息网格( g l o b a li n f o r m a t i o nc - r i d ，g i g ) ”，预计2 0 2 0 年完成。其它应 用网格主要包括：美国国家航空和宇宙航行局供a s a ) 的i p g ( i n f o r m a t i o n p o w e r g r i d ) 嘲格项 目、美国能源部a s c i 网格、欧洲共嗣体的e u r o g r i d 和d a 诅g r i d 以及著名的网格计算研究 项目o l o b u s 。g l o b u s 是已经被科学和工程计算领域广泛接受的网格技术解决方案。它是一 种基于社团的、开放结构、开放源码的服务的集合，也是支持网格和网格应用的软件库。 o l o b u s 的目标是构建一个网格软件基础设施。研究内容包括资源管理、信息发现、数据访 问、应用开发、网格安全等，并开发出能在多种平台上运行的网格计算工具包软件- - o l o b u s t o o l k i t 。o l o b u s 工具包是g l o b u s 项目的最重要的实践成果，最新版本g t 4 0 基于o g s a 体 系结构且融和了w e bs e r v i c e 技术。2 0 0 1 年英国政府投资l 亿英镑，用以研发“英国国家网 格 6 kn a t i o n a lg r i d ) 。除此之外，欧洲还有u n i c o r e 、m o l 等网格研究项目正在展开。 随着网格研究在学术界的加速，i b m ，微软、s u n 、惠普、p l a t f o r m 等信息产业界公司都相 继启动了自己的网格研究和开发计划，并将其视为第三代i n t e r n e t 。 国内也相继开展了网格计算项目的研究，仅2 0 0 2 年公布的8 6 3 网格专项，就拨出3 亿 元资金用于c h i n a g r i d 相关研究。已经完成的网格研究项目主要有清华大学的先进计算基础 设施a c i ( a d v a n c e d c o m p u t a t i o n a lt n f r a s t r u c t u r e ) 和以中科院计算所为主的国家高性能计算环 境n h p c e ( n a t i o a a lh i g hp f o r m a n c ec o m p m i n ge n v i r o n m e n t ) 。还有8 6 3 计划支持的“中国网 格( c h i n a g r i d ) ”、“上海教育科研网格”、“仿真网格织女星网格”等网格项目也正在研究中。 另外，曙光公司将其超级计算机作为网格研究的主干节点以推动我国网格计算研究。 1 2 1 网格核心技术 如前所示。人们为了各个不同的领域应用构造了许多不同的网格，如计算网格、数据网 格、信息网格、知识网格和服务网格等。它们各自要解决的问题不同。因此侧重点有所不同， 甚至体系结构也不一样，只是符合网格的特性因此称之为网格，但它们还有一个共同的特性， 那就是所需要的关键技术相同。各种网格所涉及到的关键技术均包括：高性能调度技术、资 源管理技术、安全技术。 网格环境是一个资源异构的环境，在此环境下的任务调度的决策直接影响着应用程序的 运行性能。网格系统的创建就是为了最大限度的利用网格中的闲置资源，但这些资源都是地 理上分布而且异构的资源，如何离效的利用这些资源使得共享网格资源的应用能够获得最大 的性能昵? 这便是任务调度所需要考虑的问题。而且网格调度技术与传统的高性能计算中的 调度技术相比更为复杂，这是由网格资源的动态变化性，分布共享性，自治统一管理等特性 所决定的。而网格环境下的任务调度算法对一个网格的性能的好坏起着决定性的作用，因此 当翦对网格环境中任务调度算法的研究是一个热点。在本文所实现的任务调度器的网格仿真 环境中，任务调度器具有三种任务调度策略：传统的m i n - m i n 算法；考虑用户q o s 需求和 费用优化需求的2 层混合式启发式算法；基于m i n m i n 的极限下压算法，主要侧重于时间 的优化以及提高系统平衡度。 资源管理就是合理管理网格中的资源，使得资源请求者可以更好的使用网格中的资源。 它需要完成的功能有：将物理资源抽象为逻辑资源，隐藏资源使用的技术细节，为用户提供 透明的服务和访问资源的简单接口；在众多使用者申请使用统一资源时，根据资源拥有者的 2 第一章绪论 策略来决定由谁先后或同时共享该资源；管理资源的注册、资源的发现、资源的部署、资源 的代理、资源的使用以及资源注销等。网格资源管理的基本操作包括：资源信息收集、资源 信息更新、资源发现、资源分配、资源定位、资源迁移以及资源预约。 网格环境是基于i n t e r n c t 描建，但它对安全的要求比i n t e m e t 的安全要求更为复杂。除 了网络安全所包括的认证、授权、保证、记账，审计、完整性、机密性等等，由于网格环境 中的用户、资源数目庞大且动态可变，没有单一的身份管理机构使得网格环境中的用户访问、 认证和授权成为一个极大的挑战。此外资源同异构且管理策略也不同使得解决网格环境中的 安全问题成为一个难点。同时网格安全还必须包括支持网格计算环境中用户的单点登录，防 止主体假冒和数据泄密以及资源的迁移和委托管理等。随着越来越多的公司开始将网格视为 一种改进资源利用和计算能力的途径，多家行业组织开始研究网格安全问题。例如，g l o b u s 联盟正在研究多种网格相关技术和标准问题。g l o b u s 联盟由多家机构组成，包括a r g o n n e 国家试验室、芝加哥大学和南加州大学信息科学学院。该组织开发了g l o b u si 具包，这种 工具包设计用于实现网格环境中的安全通信、相互认证、单点登录和委托管理。 1 2 本文研究内容 ( 1 ) 任务调度算法研究 资源管理和任务调度是网格计算研究的核心问题。用户提交的任务能否在网格环境下正 确、快速和高效的完成与高效任务调度算法密不可分，因此本文的研究重点为任务调度算法。 网格环境下的任务调度为n p 一完全问题，寻找最优调度算法所需的执行时间随着任务数 和处理机数目的增加而呈指数级增长。由于启发式算法可以快速、有效的得到近似最优调度 方案，因此适合网格环境下的任务调度。而试验证明m i n - m i n 、遗传算法在多种启发式算法 中更为高效【9 】，因此，我们主要对m i n - m i n 算法和遗传算法加以研究改进，以及二者的有 效结合。仿真试验结栗表明，改进后的算法较之之前的算法具有更优的性能。 ( 2 ) 多种算法性能的比较 任务调度算法研究的目的就是寻找某一或某些方面性能有所提高的调度算法，但如何对 该算法的优劣进行评价，需要对算法进行形式化分析或者仿真的网格环境下的模拟比较。本 文对提出的两个算法以及m i n - m i n 等进行仿真比较，并对试验结果进行分析。 ( 3 ) 构建网格仿真环境 由于实际的网格环境中资源多种多样，因此要构建复杂的真实网格环境比较困难。而且 在实际的网格环境下对调度算法进行测试，会有一些实际的消耗，甚至可能给实际系统带来 一些难以预料的影响，所以网格环境下的任务调度算法在实际实施于i n t e r n e t 之前，都需要 迸行模拟和仿真因此网格仿真环境是进行网格性能研究的必须工具我们在研究了现有 的多种网格仿真环境的基础上用j a v a 设计了一种可扩展的网格任务调度仿真系统，其中主 要包括资源仿真模块，客户端模块、任务调度算法模块和性能模块。它对实际的网格计算环 境进行抽象，但是该仿真环境又涵盖了真实网格环境具备的各个功能，同时支持任务调度策 略的扩展，适合研究不同的网格环境的任务调度方法。 综上所述，本文的重点研究在于针对网格计算中任务调度问题，对已有调度算法进行改 进，设计一个简单有效的网格仿真环境，并利用改进的任务调度算法进行任务的调度，使得 网格的各个资源得到合理高效的利用。此外使任务得以快速的完成，达到整个网格系统的负 载均衡，为网格的进一步发展带来了巨大的推动。 3 东南大学硕士学位论文 1 3 技术路线 ( 1 ) 任务调度算法的提出和改进 计算任务调度算法是提高网格计算整体性能的关键，因此如何设计个满足网格资源的 异构性和动态性同时获得优化的时间费用优化算法将是本文的研究重点。因此，本文提出一 个基于q o s 测量的双层时间费用优化算法，希望可以将i n t e m e t 的特性考虑进去，并且在一 定程度上满足用户服务质量( q o s ) 上的需求。此外，基于m i n m i n 的极限下压算法则是从提 高系统的平衡度和提高效率两个方面考虑。 ( 2 ) 多种算法的性能比较 只有通过性能的比较才能说明某种算法的优劣性，因此本文将首先在自行设计的仿真系 统内对多种算法进行仿真模拟，然后在得到的模拟结果的基础上，对多种算法性能进行比较 和分析。 ( 3 ) 构建网格仿真环境 本文所设计的网格环境仿真系统以j a v a 语言开发，并运用排队论相关知识构建需要模 拟的i n t e r n e t 上的随机因素。网格仿真系统主要针对测试各种网格环境下的任务调度算法而 设计，因此，主要侧重在于资源仿真模块的模拟和可扩展的任务调度算法仿真模块。 设计的网格仿真环境的主要功能模块有： a ) 资源仿真模块，它包括对i n t e m e t 拓扑结构的仿真和对计算资源性能参数的仿真； b ) 客户端模块，用户可以指定需要资源的种类和q o s ，同时还可以指定使用的调度 算法。最后，任务的执行结果将被返回给用户。 c ) 任务调度算法仿真模块，可以在其中设置多种调度策略，根据用户提交的任务和 选定的调度策略，获得一组调度结果。 d ) 任务调度性能模块。它可以根据调度结果，算出任务计算总完成时间和总完成代价， 以及资源负载平衡程度。根据这些可以对基于该任务调度算法的网格性能优劣做出评价。 1 4 主要创新点 ( 1 ) 通过对已有启发式算法的研究和比较，设计实现了适用于网格任务调度的时间费用 优化算法。该算法采用的是任务分类调度机制，保证高优先级用户任务优先进行调 度，并且在快速完成任务的同时，使用遗传算法的变异算子对使用资源费用进行了 优化。 ( 2 ) 提出一种基于m i n - m i n 的极限下压方法，有助于快速任务调度和系统负载平衡。 它吸收了模拟退火算法逐步降温的思想，一步步的减少任务集的完成时间直到不能 再下压为止。在为任务合理分配资源的同时也提高了资源的负载平衡程度。 ( 3 ) 设计和开发了一种可扩展的网格仿真环境，支持不同的调度策略，有利于研究不同 任务调度策略对网格环境任务调度性能的影响。 1 5 论文组织结构 本文以介绍网格环境的概念和系统模型为起点，按照从理论到模型设计再到算法应用的 实现路线，根据现有网格中任务调度算法的不足，提出了两个改进的任务调度算法，并设计 了一个简要但功能完备的网格仿真系统。最后将提出的算法与传统算法在该网格仿真系统上 4 第一章绪论 进行任务调度，分析比较试验结果，验证了算法的有效性。论文的组织结构和章节安排如下： 第一章为绪论，介绍论文的选题背景，研究内容和技术路线，并对整个研究使用的方法 和漉程做一个简单的说明； 第二章为全文的理论基础，详细给出了网格的定义、特点和体系结构和实现方法，并介 绍了网格技术的反展现状； 第三章为网格环境下任务调度问题的介绍，描述了常见的几种任务调度算法，并对其进 行分析； 第四章对基于q o s 的时间费用优化算法的设计、实现以及试验结果进行了详细的介绍 和比较分析； 第五章对基于m i n - m i n 的极限下压算法的设计、实现以及试验结果进行了详细的介绍 和分析比较； 第六章为两格仿宾模型的设计和描述。 第七章为全文的总结和研究工作展望。 东南大学硕士学位论文 第二章网格的体系结构 瞬格( g r i d ) 是建立在互联网上的新一代的基础设施。在上世纪9 0 年代早期，网格计算开 始萌芽，在这个时期它主要用于建设千兆测试床以及进行元计算试验。9 0 ，平代中期到晚期 为网格计算的早期实验阶段。进入本世纪后，网格计算迅速发展。它不仅在学术界引起广泛 的关注，而且得到了来自产业界诸如m m 、m i c r o s o f t 、h p 、i n t e l 和s u n 等各大公司的鼎力 支持，并形成了具有相当规模的g g f ( g l o b a lg r i df o r u m ) 组织。 2 1 网格概述 2 1 1 弼格的概念 2 0 世纪9 0 年代，i n t e r n e t 蔓延到世界各地，成为人们沟通信息和协同工作的有效二具， 同时高性能计算机的利用以及低消耗高速网络的发展也在改变人们的思想观念和使用计算 祝的方式。人们开始思考如何将物理上互连的众多资源汇聚起来，联合提供服务，以便更迸 一步地共享i n t e x n e t 上的汇聚的一切资源，包括计算资源、数据资源、软件资源乃至各种硬 件设备等。而网格的思想就是把整个因特网整合成一台巨大的“虚拟超级计算机”，实现各 种资源的全面共享，同时将各种资源以有效的方式动态的组织起来，隐藏其内部异构性和动 态性，形成一个对用户相对透明的网格环境，因此建立各种“网格”。诸如计算网格、信息 网格、知识网格、服务网格等便是实现人们更进一步共享资源愿望的途径。 什么是网格? 美国计算网格项目的领导人l a n f o s t e r 曾这样描述：“网格是构筑在互联 网上的一组新兴技术，它将高速互联网、计算机、大型数据库、传感器、远程设备等融为一 体，为科技人员和普通老百姓提供更多的资源、功能和服务。互联网主要为人们提供电子邮 件、网页浏览等通信功能，而网格的功能则更多更强，它能让人们共享计算、存储和其它资 源。”他在2 0 0 2 年的什么是网格? 判断是否网格的三个标准一文中，限定网格必须满足 的三个条件是：( 1 ) 在非集中控制的环境中协同使用资源；( 2 ) 使用标准的、开放的和通用的 协议和接口；( 3 ) 提供非平凡的服务。这三个条件将p 2 p ( p e e r t op e e r ) 、c o n d e r 、e n t r o p i a 、 m u l t i c l u s t e x 等都被排除在网格之井。通俗一点对两格的理解就是将网格和电力网进行类比。 在我们的生活中都要用到电，但我们在使用电力的时候并不需要知道该电力是以何种方式产 生，通过哪个地方的发电站输送过来，我们使用的是统一形式的电能。而网格的最终目的给 用户提供的是与地理位置无关的、与具体的设施无关的通用的计算能力，使得人们可以像用 电一样方便简单的使用多种不同类型的嬲格终端设备上网，获取信息和知识以及电子商务和 计算等服务。与电力网相比，两格的结构更复杂，用户的要求更多样化，需要解决的问题更 多，但是它也会给我们带来更大的便利和帮助。同格与电力的形象比较如图2 - l 所示。 6 第二章网格的体系结构 图2 - 1 同格和电力同的比较 网格的概念起源于元计算【1 0 】【1 l 】，又称为网格计算。它的核心思想就是共享广域分布 的各种计算机资源，从而获得超级计算能力、数据处理能力和信息处理能力。因此，也可以 说网格以共享资源为目的。形成一个集成的计算与资源环境，或者说是一个计算资源池【1 2 】。 网格能够吸纳地理上分散的属于不同机构管理的各种异构的高性能计算机、服务器、数据存 储能力、处理系统和远程硬件设备等各种计算资源，并通过合理的组织充分利用起来，提供 给用户一种高可靠、高性能且经济的与地理位置无关的计算能力。 网格( g r i d ) 是建立在互联网上的新一代的基础设施，却不仅仅是互联网。如果认为网 格就是仅仅通过网络把人和计算机以及设备简单的连接以进行资源共享。那可就大错特错 了。它只看到了离散的两络资源，而没有将他们作为一个有机的统一整体。物理上离散的网 络资源结合网格的逻辑功能才能成为完成的网格系统。网格与互联网的主要不同在于：互联 网以信息发布和资源共享为主，而网格可以共享更深层次的资源，同时提供高性能计算应用 以及信息服务。网格将提供的功能如下：通用的资源共享平台，它提供包括计算资源、存储 资源、数据资源以及硬件设备等更为广泛的资源的共享；广域的高性能计算环境，它支持远 端高性能计算资源；一个对用户透明的统一资源环境，用户可以通过网格门户等技术透明的 使用整个网格上的资源。 综上所述，可以从三个方面来理解网格：一、网格是基础设施。它是综合了计算机、数 据、设备和服务等资源的基础设旌；二、网格的目标是资源共享和分布协同工作；三、网格 是一种技术。为了实现异构资源之间的分布共享和协同，网格必须制定相应的标准是解决多 个层次的资源共享和合作技术。 2 1 2 网格分类 网格始于大规模分布式计算，到如今已应用于许多领域。从不同的角度出发，对网格有 多种分类方法。 根据所关注的技术问题，网格可以被划分为计算网格，数据网格、信息网格、知识网格 及服务网格。计算网格是狭义上的网格，包括分布式超级计算、高性能计算，它把分散于各 个网络节点的计算资源整合起来以提供更高的计算能力；数据网格研究的内容主要有数据的 共享和管理、数据透明存储和访问以及数据共享的安全性等，它的核心是处理数据密集型问 题；信息网格使得用户可以更加有效的共享和管理信息资源，为用户提供透明的信息服务， 7 东南大学硕士学位论文 它比数据网格更偏重于信息的整合；知识网格集合了语义w e b 的研究，涉及本体、数据挖 掘等技术，通过知识网格用户可以更好的共享和管理知识资源：服务网格强调应用服务集成。 它不仅支持科学计算，还支持其它服务。包括通信服务、数据服务、信息服务、计算服务、 交易服务等等。 根据应用问题网格又可被归类为科学计算网格、商务计算网格和个人计算网格。科学计 算网格主要用于高性能计算、高能物理、生命科学以及地理系统等；而商业方面的应用包括 协同计算、生物制药和财务模型等。此外，根据网格资源所处的地理范围划分，还可以将网 格分为局域网格、地区网格和广域网格等。其实在实际的网格应用中，两格的类型并没有清 晰的界限，往往是多种类型网格的结合。 2 1 3 网格的特点 网格计算属于分布计算研究领域，但与传统分布计算相比，它的资源异构分布、动态性 强、分布共享，再加上资源的自治统一管理使褥网格具有以下特点： ( 1 ) 分布与资源共享：分布是网格最原始的特征，网格是通过集中分散的资源来完成计 算和其它服务的。资源的共享是一种集中资源的手段，通过网格解决资源的共享问 题便是网格的目的所在。 ( 2 ) 自相似：在大规模网格或小点规模的网格上有着相同或相似的规律。我们可以在一 个试验楼里建立一个小规模的试验网格，而整个学校的多个试验网格联系起来就形 成一个全校的校园网格，不同学校之间的校园网格就形成了一个全国性校园网格， 校园网格和科学计算网格、商业网格等组成统一的全国网格，各个国家的国家网格 汇聚成了全球网格联盟。在建立网格的各个阶段都可以看到网格的整体和部分之间 的相似性。 ( 3 ) 动态性和多样性：网格中的用户以及资源都是动态的，同时用户的需求也是动态变 化的，因此动态性是网格需要考虑的一个基本问题。网格中用户多种多样，需要的 服务也是各形各态，比起几种统一规格的电力需求可能要复杂得多，因此，网格需 要满足用户的多样性要求。 ( 4 ) 自治性与管理的多重性：网格的一个特点就是网格节点内部的自治和外部的受控整 合。网格资源是由分布在广域环境中的属于不同组织或者个人的资源构成的，资源 的所有者拥有对其资源的自治管理权力。而作为供用户使用一个统一整体的一部 分，网格资源在自治的同时还必须接收网格的统一管理，这便是网格自知性和管理 的多重性。 除了上述四大特点外，网格还具有高度抽象性。网格把所有资源以及计算力抽象成一个 用户可见的“网格接线板”，用户需要的时候插上“插头”即可，而其他的东西对用户透明， 使得用户可以简单方便的使用计算力和计算资源。 2 1 4 网格的应用领域 网格的应用范围非常广泛。它涉及人类生活的方方面面，从尖端科研到商业应用乃至日 常生活。在我国的许多行业如科研、气象气候、生物医学、能源、教育和水利等方面都非 常需要高性能计算网格。按照l 矾f o s t e r 和g l o b u s 项目组的观点，网格应用领域目前主要 有五类：分布式超级计算、分布式仪器系统、数据密集型计算、远程沉浸和信息集成a 分布式超级计算( d i s t r i b u t e ds u p e r c o m p u 恤g 卜它和以前的高性能计算的作用十分相 似，不同的是以前的高性能计算是集中式的，由某一个地方的一台或几台高性能计算机完成 3 第二章两格的体系结构 计算任务。而网格的分布共享能力可以把地理上分布的超级计算机和闲散资源集中起来组成 一台虚拟的超级计算，协同解决更复杂更大规模的问题，同时最大程度的提高现有计算资源 的利用率。比较典型的例子有美国国家科学基金会正在建立的“分布式兆兆级网格 ( t e r a g r i d ) ”，他们利用网格技术将几所大学的超级计算中心连接起来形成一个处理能力约为 每秒1 3 5 万亿次浮点操作，存储容量接近7 0 0 兆兆字节的可以供许多领域的研究机构使用 的“巨无霸”计算中心；此外比较著名的项目还有寻找外星生命的计划s e m i h o m e 。该项目 是通过互联两，利用互联网个人用户的闲置计算机，进行科学研究。从1 9 9 9 年至今有5 0 0 多万台个人计算机在闲置时参与了这项工作，而这些利用闲置时间所累计的计算总量相当于 2 0 台价值千万美元的超级计算机昼夜不停工作所能达到的工作极限。 分布式仪器系统( d i s t r i b u t e di n s t r u m e n t a t i o ns y s t e m 卜它利用网格管理分布在各地的 贵重仪器系统，提供远程访问仪器的手段，提高仪器的利用率，方便了用户的使用。在分布 式仪器系统中，两格需要综合各种技术，屏蔽各种平台的差异，将他们揉合在一起，同时还 需要管理各种设备，动态调度资源，提供海量数据的实时存储和检索服务，支持对远程仪器 的控制等。以方便远程使用科学仪器为目标，由美国能源部计划资助的x p o r t 项目能提供远 程仪器使用规划、仪器操作、数据获取、筛选和分析等功能。通过x p o r t ，科研工作者可以 远程提交任务，交互式控制任务的执行，接收和分析初步的运行结果，存储和管理产生的数 据，同时可以方便的与其他科研工作者共享研究成果等。可见x p o r t 不仅缩短研究时间，提 高设备的利用率而且提供了一个协同研究的平台。 数据密集型计算( d a t ai n t e n s i v ec o m p u t i n g 卜一对于数据密集型问题，数据采集地点、 数据处理地点、数据分析与结果存放地点、可视化设备设置地点等往往不在同一个地方，数 据密集型问题的求解往往同时会产生很大的通信和计算需求，因此数据密集型计算所对应的 数据网格 1 3 】相比于计算网格更侧重于数据的存储、传输和处理。数据密集型计算应用的研 究领域主要有高能物理实验、生物医学、地球观察和气象预测等。 远程沉浸( t e l e i m m e b i 卜近程沉浸是一种特殊的网络化虚拟现实环境。这个环境可 以是对现实或历史的逼真反映，可以是对高性能计算结果或数据库的可视化，也可以是个纯 粹虚构的空间。各地的参与者通过网络聚在同一个虚拟空间里，可以随意漫游，沟通，而且 还可以改变虚拟环境。远程沉浸可以广泛应用于可视化交互式科学、教育、艺术和娱乐等。 由伊利诺州大学芝加哥分校的电子可视化实验室e v l ( e l e c l n i cv i s u a l i z a t i o nl a b o r a t o r y ) 与 十几家合作伙伴一起开发的爱奥尼亚( s h a r e dm i l e t u s ) 项目让2 0 0 0 年前的希腊爱奥尼亚古城 复活，网络上进入的参观者可以在虚拟的城堡里畅游，还可以与其他游客交互。 信息集成( i n f o r m a t i o ni n t e g r a t i o n 卜信息集成要解决的核心问题有如何描述信息、存储 信息、发布信息和查找信息；如何充分利用现有网络技术，如h r r p 、x m l 、w s d l 、d d i ， s o a p 等来构成一个完整的服务链：如何保证信息的安全性等等。比较典型的项目有美国军 方的全球信息网格g i g ( g l o b a li n f o r m a t i o ng r i d ) ，它的目标是通过实时计算和通信完成信息 的收集、处理、存储和管理等。综合系统中的所有的信息和能力，提供单一的、集成的、安 全的信息系统，允许各地的用户访问共享数据和应用程序。 以上五个网格的应用领域的典型例子偏重于大规模的应用，事实上，网格也与我们的社 会生活息悫楣关。首先就商业而言，分布在世界各地的应用程序和各种信息，能够进行无缝 融合和沟通，从而形成崭新的商业机会；此外，网格本身可以提供更广泛的资源贸易闹 置的计算资源、贵重仪器、数据、信息等都可以在贸易的基础上实现广泛共享。其次，网格 技术可以整合和管理分散在政府各部门的信息化资源，实现各个政府部门之间数据的无缝交 换，消除信息孤岛，打破电子政务资源共享的瓶颈，网格虚拟环境下的协同办公也可以提亮 政府工作效率。再次，在个人娱乐方面，两格可以为游戏开发商和服务供应商提供可扩展的、 高弹性的基础设施以运行大型多人游戏。网格技术还使得虚拟现实有望走入平民生活。 9 东南大学硕士学位论文 网格技术在走向大规模应用时尚存在不少问题如各公司的技术标准不统一以及安全问 题等，但这并不能阻止网格前进和普及的脚步。相信随着网格技术的不断完善和应用领域的 不断扩展弼格可以在更多的领域得到应用，发挥更大的作用f 】4 】。 2 2 网格体系结构 两格体系结构从技术上描述了如何建造网格，它不仅给出了两格的基本组成和功能，还 清晰地描述出网格各组成部分的关系以及它们集成的方式，刻画了支持网格有效运转的机 制。目前主要的网格体系结构有两个：一个是l a nf o s t e r 早在2 0 0 1 年提出的五层沙漏结构 ( f i v e - l e v e l s a n d g l a s s a r c h i t e c t u r e ) 1 5 1 、其次就是【b m 和g l o b u s 基于f a nf o s t e r 等的五层沙 漏、结合w e bs e r v i c e 技术，在2 0 0 2 年2 月联合发布的开放厨格服务体系结构( o p e ng r i d s e r v i e e s a r c h i t e c t u r e ，o g s a ) 【1 6 】。l a n f o s t e r 将网格体系结构定义为“划分系统基本组件， 指定系统组件的目的与功能，说明组件之间如何相互作用的技术”。显然，网格体系结构是 网格的骨架和灵魂，只有建立合理的网格体系结构，才能设计和构建好网格，因此了解和学 习网格体系结构至关重要，下砸将逐一详细介绍上述两种两格的结构、功能模块和组成等。 2 2 1 五层沙漏结构 五层沙漏结构是最早由f a nf o s t e r 提出的具有代表性的网格体系结构，因此其影响非常 深远。五层沙漏体系结构是一种抽象层次结构。其基本思想是以协议为中心，强调服务与 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 ) 和s d k ( s o f t w a r ed e v e l o p m e n tk 她) 的重要性。这一标 准化的开放结构对网格的扩展行、互操作性，一致性以及代码共享都很有好处。五层沙漏体 系结构的经典结构图如图2 - 2 所示。 矾嘲 盛甩晨 髂 囊整 1 l 麟f 褒谨屡 与连整屡 斌 构造曩 图2 - 2 网格的五层沙漏结构 五层结构之所以形如沙漏，是由各部分协议数量的分布不均匀引起的。考虑到核心的移 植，升级的方便性，核心部分的协议数量相对比较少( 例如i n t e m e t 上的t c p 和h r r p ) ，因 为最核心的部分不仅要实现上层协议( 沙漏的顶层) 向核心协议的映射，同时要实现核心协 议向下层协议( 沙漏的底层) 的映射。按照定义。核心协议的数量不能太多，这样核心协议 就成了一个协议层次结构的瓶颈。在五层结构中，资源层和连接层共同组成这一核心的瓶颈 部分，它促进了单独的资源共享。 根据五层沙漏结构中各组成部分与共享资源的距离，将对共享资源进行操作、管理和使 l o 第二章网格的体系结构 用的功能分散在五个不同的层次，由下至上分别为构造层f f a b n 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 ) 。五层的功能特点【1 5 】分别为： 构造层( f 曲r i c 卜一构造层的基本功能为控制局部资源并向上提供访问资源的接1 2 1 。构 造层面对的是具体的物理或逻辑资源( 构造层资源可以包括计算资源、存储系统、目录、网 络资源等) 。它通过对这些局部资源的管理。向上层提供对这些资源的管理和控制界面。构 造层提高的功能越多则构造层资源可以支持的高级共享操作越多，例如如果资源层支持提前 预约功能，则容易在高层实现资源的协同调度服务而不需要很多额外的开销；但反过来说如 果构造层提供的功能较少，则网格结构的组织就可以比较简单，实现起来也相对容易。构造 层的基本功能包括：查询机制( 查询资源的状态、结构和可用性等) 、控制服务质量的资源 管理能力等。 连接层( c o n n e c t i