（计算机应用技术专业论文）基于petri网模型的网格资源调度的研究.pdf

摘要 网格计算是解决科学计算和工程计算等大规模计算的非常具有潜力的下代 计算平台。网格核心服务是网格的重要组成部分，是连接网格底层和高层功能的 纽带，是协调整个网格系统的有效中枢，而网格的资源调度技术是网格的核心服 务之一。为了使网格达到最大的性能，有效降低网格计算的执行时间和耗费，需 要一个良好的资源调度策略来有效的分配网格资源。由于网格中的资源具有分布 与共享、自相似性、动态性和多样性、自治性与管理的多重性等特点，网格的资 源调度具有一定的难度。因而调度算法的研究既是研究的重点也是研究的难点。 p e t r i 网是一个描述异步并发的图形工具，具有可达树、可达图、关联矩阵等 多种分析方法，并且可以通过数学方法来证明其正确性；它与网格有很多相似的 特性，故可以把它同网格计算结合起来，作为研究网格的工具。 论文主要阐述了资源调度设计的准备工作，算法的改进以及仿真实验，本文的 主要工作如下： 介绍了网格的基本概念，特点以及网格的体系结构，然后介绍了p e t r i 网的基 础理论知识，重点阐述了工作流的化简技术。 利用扩展高级时间p e t r i 网为资源调度建立了模型描述，并提出了一个改进的 模型，利用改进的模型把任务集按照q o s 进行了划分，然后把它同改进的m i n m i n 算法结合起来，可以简化算法的复杂度，提高它的负载度。 利用g r i d s i m 仿真器进行算法的模拟，分析了影响调度性能的因素。实验结果 表明改进的算法是合理的，可以一定程度上提高网格系统的利用率和性价比。 关键字： 网格计算；资源调度；p e t r i 网：m i n - m i n ：6 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 gi st h ep o t e n t i a lo ft h en e x tg e n e r a t i o no fp l a t f o r m ，w h i c hw i l lb e u s e di nf i e l do fs c i e n c ec o m p u t i n g ，e n g i n e e r i n gc o m p u t i n ga n ds o m eo t h e rl a r g e s c a l e c o m p u t i n g g r i dc o r es e r v i c ei sa ni m p o r t a n tc o m p o n e n to ft h eg r i dc o m p u t i n g a sa c e n t r u mo fe n t i r e g r i dc o m p u t i n g ，g r i dc o r e s e r v i c ec o n n e c t sg r i du n d e r s t r a t u m g r o u p w a r et ot o pg r o u p w a r ea n dc o o r d i n a t ee n t i r eg r i ds y s t e mt ow o r ke f f e c t i v e l y , s oi t i sv e r yi m p o r t a n ta n du s e f u lt or e s e a r c hg r i dc o r es e r v i c et e c h n o l o g y g r i d sr e s o u r c e s c h e d u l i n gt e c h n o l o g yi sap a r to fg r i dc o r es e r v i c et e c h n o l o g y ag o o ds t r a t e g yo fg r i d r e s o u r c es c h e d u l i n g ，w h i c hi si no r d e rt og e tt h eb e s tp e r f o r m a n c ea n dr e d u c et o t a l r u n n i n gt i m ea n dt o t a le x p e n s ei ng r i dc o m p u t i n g ，i sn e e d e dt oa l l o c a t eg r i dr e s o u r c e h o w e v e r , a st h ec h a r a c t e r so fg r i dr e s o u r c ea r ed 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 dm a n i f o l da n ds oo n ，r e s o u r c em a n a g e m e n ta n d s c h e d u l i n gu n d e re n v i r o n m e n t si so n eo ft h ek e yr e s e a r c hf i e l d so fg r i ds y s t e m p e t r in e ti sak i n do fg o o dt o o lt od e s c r i b ec o n c u r r e n ta n da s y n c h r o n o u ss y s t e m ， t h e r ea r em a n ym e t h o d st o a n a l y z ep e t r in e t ，s u c ha sr e a c h a b i l i t yg r a p h ，r e a c h a b i l i t y t r e e ，i n c i d e n c em a t r i x a n ds o o n h o w e v e r , i t sc o r r e c t n e s sc a nb ep r o v e db y m a t h e m a t i c sm e t h o d c o m p a r e dw i t ht h ec h a r a c t e r so fg i r d ，i ti sc o n v e n i e n c et ou s e p e t r in e tt od e s c r i b eg r i d t h ep a p e rm o s t l ye x p a t i a t et h ep r e p a r a t i o n ，d e s i g np r o c e s sa n dt e s t i n ga b o u tt h e r e s o u r c es c h e d u l i n gm e t h o dw h i c hb a s e do ni m p r o v e dm i n - m i na l g o r i t h m t h em a j o r w o r ki sd i s c u s s e da sb e l o w ： t h eb a s i cc o n c e p t ，c h a r a c t e r sa n da r c h i t e c t u r eo fg r i dc o m p u t i n ga r ei n t r o d u c e d ； t h e nt h eb a s i ct h e o r e t i co fp e t r in e ti si n t r o d u c e d ，w h e r ew o r k f l o wt e c h n o l o g yi s e x p a t i a t e do nf o c u s am o d e lo fg r i dc o m p u t i n gi ss e tu p ，w h e r eu s i n ge x t e n d e dh i g hl e v e lt i m e p e t r in e t t h e na ni m p r o v e dm o d e li sp u tf o r w a r d ，w h i c hd i v i d e st h et a s k si n t ot w o p a r t sa c c o r d i n gt oq u a l i t yo fs e r v i c e s t h ei m p r o v e dm o d e li s u s e di ni m p r o v e d m i n m i na l g o r i t h m ，w h i c hc o u l ds i m p l i f yt h ea l g o r i t h ma n da l s oi m p r o v el o a d t h ea l g o r i t h mi ss i m u l a t e db yg r i d s i m ，a n dt h ef a c t o ro ns c h e d u l i n ga l g o r i t h mi s a n a l y z e d t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h em o d i f i e da l g o r i t h mi nt h i sp a p e ri s f e a s i b l e i tc o u l di m p r o v et h es c h e d u l i n gp e r f o r m a n c ei nac e r t a i ne x t e n t k e yw o r d s ：g r i dc o m p u t i n g ；r e s o u r c es c h e d u l i n g ；p e t r in e t ；m i n - m i n ； g r i d s i m ；s i m u l a t i n g i l 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 彦章哀日期：埘年5 月矸日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 厍索束日期：刎年5 月互午日 导师签名：占、吻没 日期：加6 年，月日 第一章绪论1 帚一早三百了匕 1 1 课题的研究背景及意义 i n t e r n e t 的产生与发展，对人们的思维方式、工作模式以及生活理念都产生 了巨大的影响与冲击，可以把i n t e r n e t 的发展分成三个阶段：第一代i n t e r n e t 以e - m a i l 为主，把遍布于世界各地的计算机用t c p i p 协议联系在一起；第二代 i n t e r n e t 则通过w e b 信息浏览及电子商务等信息服务，实现了全球网页的连通： 第三代i n t e r n e t 将“试图实现互联网上所有资源的全面连接，包括计算资源、通 信资源、软件资源、信息资源、知识资源等”，这就是网格计算【1 】( g r i dc o m p u t i n g ) 。 网格计算是建立在i n t e r n e t 上的一组新兴技术，其基础设施是基于i p 协议的 宽带数字通信网络，利用互联网把分散在不同地理位置的计算机组织成一个“虚 拟的超级计算机”，其中每一台参与计算的计算机就是一个节点，而整个计算是 由成千上万个节点组成的一张网格，所以这种计算方式叫网格计算| 2 l 。这样组织 起来的“虚拟的超级计算机”具有两个优势：一个是数据处理能力强；另一个是 能充分的利用网上的闲置处理能力。它将会改变传统的c i i e n t s e r v e r 和 c 1 l e n t c l u s t e r 结构，形成新的r e s o u r c e g r i d 体系结构，这种体系结构将使得 用户把整个网络视为一个巨大的计算机，并从中享受一体化的、动态变化的、可 灵活控制的、智能的、协作式信息服务。 实际上j 网格计算是分布式计算( d i s t r i b u t e dc o m p u t i n g ) 的一种【3 】f4 1 ，如 果我们说某项工作是分布式的，那么，参与这项工作的一定不是一台计算机，而 是一个计算机网络，显然这种“蚂蚁搬山”的方式将具有很强的数据处理能力。 目前，网格计算不仅在学术界、研究领域进行着深入的研究与实验，同时也得 到了来自产业界诸如i b m 、h p 、m i c r o s o f t 、n t t 、i n t e l 、s g i 和s u n 等各大公司 的巨资支持与商业应用开发。g l o b u s 项目是目前国际上最有影响的与网格计算相 关的项目之一f 1 1 。它发起于九十年代中期，其最初的目的是希望把美国境内的各 个高性能计算中心通过高性能网络连接起来，方便美国的大学和研究机构使用， 提高高性能计算机的使用效率。当时在美国建立了一个实验环境i w a y ，它把 位于美国1 7 个不同地点的6 0 多个组织的超级计算机和资源通过高性能网络联系 起来，进行大规模科学模拟、协同工作、并行计算等科学研究，这实际上是g l o b u s 项目的前身。随着对g 1 0 b u s 项目的深入研究，针对它的目标也进一步扩展，希望 通过g l o b u s 项目可方便对地理上分布的研究人员建立虚拟组织，进行跨学科的虚 拟合作。目前，g l o b u s 项目把在商业计算领域中w e bs e r v i c e 技术结合在一起， 希望不仅仅局限于科学计算领域，而且能够对各种商业应用进行广泛的、基础性 的网格环境支持，实现更方便的信息共享和互操作，从而对商业模式、人的工作 方式和生活方式产生深远的影响。 p e t r i 网是二十世纪六十年代，德国研究员c a r l a d a mp e t r i 在他的博士论文用 自动机通信中首次使用网络结构模拟通信系统1 5 j ，而提出的一种新的数学建模 工具：p e t r i 网是从实际的物理模型出发，构造描述系统的模型，因而它一产生就 受到大家的青睐，使得p e t r i 网的发展非常迅速，它从最初应用于通信系统，然后 推广到计算机、通信、自动控制、柔性制造( f m s ) 、人工智能等领域【6 】。自1 9 8 0 年以来，每年一次的p e t r i 网理论和应用的国际研讨会，推动、促进了p e t r i 网理 论和应用技术的发展，使得p e t r i 网技术日益完善和充实。国内的各科研院校、工 业界也进行了广泛的研究，并在中国计算机学会中专门设立了p e t r i 网专业委员会， 每逢奇数年召开全国的p e t r i 网技术研讨会，对p e t r i 网的发展和对外交流起了推 动作用。p e t r i 网既具有直观、易懂、图形化的特点，同时又具有数学化的分析方 法，它不仅能用图形表示系统的静态结构和动态结构，还能用关联矩阵、不变量 和可达树等来计算、描述推理过程i7 1 。用p e t r i 网描述系统具有以下优点：1 ) 善 于表达系统静态结构和动态行为；2 ) 可以把复杂的问题用直观的图形模型来表示， 便于理解；3 ) 系统动态过程可用矩阵来描述，不需要在庞大的解空间中搜索最优 解；4 ) 可以并行求解，同时得到多个求解路径。因此p e t r i 网是研究和模拟系统 并行发生、次序发生或循环发生的理想工具。 网格资源调度问题从特征上分析具有并行性和异步性，采用p e t r i 网描述网格 资源调度问题具有相当的优势，所以p e t r i 网在网格资源调度的研究有相当的应用 价值。用p e t r i 网描述调度问题，然后采用关联矩阵描述各个资源的状态，根据状 态矩阵的初始状态采用启发式算法优化调度模型。上述技术的关键步骤在于如何 解决p e t r i 网节点过多的问题。 1 2 本课题采取的研究方法以及可行性分析 p e t r i 网是非常适合描述同步和异步的建模工具，而网格资源调度问题正好具 备这种特性，因而利用p e t r i 网可以非常恰当的描述调度问题的动态过程。参考文 献 8 9 1 0 1 1 都是利用p e t r i 网给网格系统建模，然后再利用相应的算法求解。 事实上p e t r i 网是一个可以扩充的系统，根据实际的应用可以增加一些特殊的功能， 考虑有优先级的调度问题中，可以引进抑制弧，即可以对调度任务进行优先级排 序。在实际的情况中还可以做相应的扩充。 对于网格调度问题来说，它们的表述形式可以看成是将m 个资源分配到n 个处 理机上，如何得到合理的优化结果。在本文中拟对网格资源进行研究，计划采用 以下步骤： ( 1 )对网格资源调度建立p e t r i 网模型，分析网格的行为过程； ( 2 )分析m i n m i n 算法，引入改进的m i n m i n 算法； ( 3 ) 把改进的m i n m i n 算法与p e t r i 网的可达图分析结合起来，给算法一个 形象的图形的描述； ( 4 ) 利用仿真工具g r i d s i m ，把改进的算法作为g r i d s i m 中第一级b r o k e r ， 进行仿真实验。 1 2 1 网格资源的建模 建模的关键在于确定p e t r i 网中的库所( p l a c e ) 和变迁( t r a n s i t i o n ) 。在网格 资源中，拟订以调度的任务作为库所，而把处理机作为变迁，如图1 1 描述了一 组有优先级和没有优先级的调度过程。 p 】 t n p 抵o 呻如 p 我 图1 1 ( a ) 有优先级的调度图1 1 ( b ) 无优先级的调度 实际的调度模型就是将上面的基本元素组合而来的复杂模型；由于实际的系统 是一个复杂的模型，因而引进p e t r i 网简化技术。 1 2 2 简化p e t ri 网模型 初始建立的p e t r i 网模型由于过度注重了细节的描述，因而节点过于庞大，必 须对初始模型进行化简，否则不能体现p e t r i 网模型的优点。 目前有很多关于p e t r i 网模型简化的技术，层次模拟和抽象是比较成熟的技术。 把同一个应用问题从使用基本网系统到使用p t 系统，再到使用高级网系统就是 层次模拟：抽象就是忽略细节，在同一层次上忽略细节以减少节剧”。高级网系 统有p r ，t - 系统，自控网系统等，抽象技术主要是与u m l 相结合的技术。在本文 中对p e t r i 网理论的应用主要有两个方面：第一个是描述网格系统时，为了减少节 点，引进着色p e t r i 网，把具有相同性质的节点抽象成一个节点，这并不改变p e t r i 网的活性，然后再利用工作流分析的方法，进一步对模型进行简化，当然这个模 型只是为了描述网格系统更为方便，根据不同的需要，我们可以做出不同的抽象 模型，描述不同层次的模型；第二个应用是在求解调度模型时，由于网格调度问 题实际上一个n p c 问题，不管如何改进算法，算法的复杂度是不会降低的，为了 能加速求解过程，把问题进行分而治之的求解方法，在理论上是能加快求解的速 度的。本文中采用的算法是改进的m i n m i n 算法，把任务分成了有优先级要求的 两部分，然后在对每部分进行求解，在此是利用p e t r i 网来划分任务，对网络的结 构进行分解，仅与网络的拓扑结构有关，具有易形式化等特点，将规模大的网分 解成小规模子网，对子网进行求解，可以降低计算的复杂性，并且不会改变p e t r i 网 的畅通性。 1 2 3 模型的求解 对分解后的任务按照改进的m i n m i n 算法进行求解，得到满足要求的解。 1 2 4 仿真实现 对上面的算法进行编程，然后在g r i d s i m 仿真器下进行实验。 1 3 论文的研究内容 本文在广泛阅读国内外相关的参考文献后，为网格资源建立p e t r i 网模型，采 用了改进的m i n m i n 算法，并将其作为核心调度策略来分配网格资源。论文的主 要研究内容包括以下几个方面： ( 1 ) 解析网格计算环境，归纳网格计算环境下资源调度的特征 由于网格计算环境的复杂性及网格计算的特点，网格计算环境下的资源调度与 其他分布式计算中的资源调度有很大的区别，因此需要研究网格计算环境的特点， 在整体上把握网格计算环境对资源调度的要求，为后面建立p e t r i 网模型以及设计 m i n m i n 算法的网格资源调度策略提供参考。 ( 2 ) 建立p e t r i 网模型 在深刻理解网格计算环境下的资源调度的情况下，为它建立p e t r i 网模型，并 针对其中的缺点提出了改进的p e t r i 网模型。 ( 3 ) 设计基于m i n m i n 算法的网格资源调度策略 根据改进的p e t r i 网模型，设计基于m i n m i n 算法的网格计算环境下的资源调 度策略，目标是通过更合理的分配资源降低网格系统的总执行时间和总消耗，从 而提高网格系统的总体性能，并在仿真平台g r i d s i m 上进行仿真研究。 1 4 论文的创新点 ( 1 ) 根据网格计算的特点，为它建立了p e t r i 网模拟，根据的初始模型的缺点 提出了改进的模型，也就是引入q o s 的要求，对任务集进行了划分，减少了每次 载入的任务的空间复杂度，然后把它同改进的m i n m i n 算法结合，进行任务集的 调度。 ( 2 ) 利用工作流的化简规则对抽象层次的模型进行进一步的化简，给出了一 个忽略细节的网格计算调度模型。 1 5 本论文的结构安排 第二章介绍了网格概念、特点以及体系结构，然后总结了资源调度的研究现状 及其面临的难题。 第三章本章主要介绍了p e t r i 网的基本理论，介绍了工作流的知识，然后详细 描述了工作流的相关知识，及6 个化简规则。 第四章是全文的重点，描述了调度问题的基本过程，然后利用e h l t p n 给网 格资源调度建立了一个模型，针对每次没有调度的任务又返回了初始的任务集当 中，在进行下一次调度时又要进行一次o o s 的判断，加大了时间和空间的开销这 个缺点，提出了改进的调度模型，即把它的任务集划分为高优先级和低优先级的 任务，可以减小了每次载入的任务集，减少空间和时间的复杂性，然后引入了改 进的m i n m i n 算法，并把它同改进的改进的模型结合起来，进行任务的调度，可 以得到更好的调度效果。最后还给出忽略细节的网格计算调度模型 第五章是介绍了几种相关的网格仿真器，解释为什么选择g r i d s i m 作为仿真 器。详细介绍了g r i d s i m 的工作机制，为下一步仿真做好准备。分析了影响资源 调度的因素，通过v i s u a lm o d e l e r 这个工具随机产生资源和用户，然后调用本文 设计的算法来解决调度问题。 第六章是j 滇实验的结论。 第七章是总结和展望，对全文进行了总结，并提出了进一步的研究工作和方向。 最后是参考文献，致谢和发表的论文。 第二章网格计算及其资源调度 2 1 网格计算的基本概念 2 1 1 网格的概念 网格就是一个集成的计算与资源环境，或者说是一个计算资源池。 网格能够充分吸纳各种计算资源，并将它们转化成一种随处可得的、可靠的、 标准的同时还是经济的计算能力。除了各种类型的计算机，这里的计算资源还包 括网络通信能力、数据资料、仪器设备、甚至是人等各种相关的资源。 基于网格的问题求解就是网格计算。 这里给出的网格和网格计算的概念是相对抽象的，而且是广义的定义，狭义网 格定义中的网格资源主要是指分布的计算机资源，而网格计算就是指将分布的计 算机组织起来协同解决复杂的科学与工程计算问题。狭义的网格一般被称为计算 网格( c o m p u t i n gg r i d ) ，即主要用于解决科学与工程计算问题的网格。 根据求解问题的特点，人们又提出了多种名称的网格，比如以解决科学问题为 的核心的科学网格【”】，以全球地球系统模型问题求解为主要目的的地球系统网格 【1 3 】等等，此外还有地震网格【1 4 】等行业网格。 图2 1 网格资源、网格管理与网格环境间的关系 那种认为网格就是仅仅通过网络把计算机、人、仪器、数据等连接起来的观点 是过时的，它过分强调了物理的网络和离散的网格资源，而没有将它们作为一个 有机的统一整体来看待。另外一种观点就是把网格看作中问件系统，这种观点也 是不全面的。中间件的确在网格中占有很重要的地位，但是网格决不仅仅只是中 间件。这两种观点都存在一定的片面性，第一种观点是过分强调网格物理上的资 源组成，第二种观点过分强调网格逻辑上的功能，只有将两者结合起来才是完整 的网格系统。物理资源本身和对资源的管理与逻辑上的功能都是十分重要的，而 且两者也是密不可分的，它们是网格环境的两大核心组成要素( 如图2 1 所示) 。 2 1 2 网格的目的 网格是借鉴电力网( e l e c t r i cp o w e rg r i d ) 的概念提出来的【1 】【2 1 ，网格的最终目 的是希望用户在使用网格计算能力时，就如同现在使用电力一样方便。网格也希 望给最终的使用者提供的是与地理位置无关、与具体的计算设旋无关的通用的“计 算能”。如图2 2 是对电力网和网格组成的简单对比示意图。 电力网构成示意图 网格组成示意图 图2 2 电力网与网格组成对比示意图 与电力网相比，网格的结构更复杂，需要解决的问题也更多，但是它也给我们 带来更大的便利和帮助。 2 1 3 网格的基本要求 对于网格提供的计算能力，有四个基本的要求，它们分别是可靠性要求，标准 化要求，易访问性要求和价格低廉的要求1 1 ”。 网格的可靠性是指网格提供的计算能力必须保证是持续、稳定和安全的，不应 该由于网格内部个别资源的变化而对网格应用造成影响，即网格内部局部资源的 变动对网格应用应该是透明的。网格还应该满足各种形式的安全要求，比如数据 传输的加密，权限的认证，避免非法入侵和非法使用等，如果没有安全性保障， 这种先进的计算服务就不能得到广泛的推广。 网格的标准化要求：一方面网格资源之间应该有一个统一的可以相互访问的接 口或者协议标准，因为只有这样才能够实现网格资源的互操作，从而实现充分的 蓼 翱蚕 擎 虱磊 资源共享，标准化是共享的前提；另一方面是指网格对用户提供的计算能力应该 满足一定的标准，有_ 种比较统一的形式，从而便于以统一的方式进行访问，对 于访问者来说，不能因为时间、地点、具体的访问系统等的不同而要求不断改变 访问形式，访问形式应该有一致性，当然一致性的前提是网格必须提供给用户一 个相对稳定的标准化接口。 网格的易访问性要求是指用户可以在任何时间，任何地点，以自己习惯的形式 访问和使用各种网格资源。网格计算能力可以通过网格系统输送到任何角落，随 处可得。也就是说在网格上是没有资源处在什么位置的概念，只有“在网格上” 和“不在网格上”的区别。人们以前在解决特定问题时或许不得不到特定的地点 来进行，比如到某一个单位去登记和使用特殊的仪器设备等，但是在网格上解决 问题时，不应该因为访问者或者资源所在的位置不同受到限制。 网格费用的低廉性要求是网格能够被普遍接受和推广的前提，不管网格的优点 如何，如果大多数的使用者无法承受其费用，网格就不会得到普及，它的各种优 势也就根本无法得到体现。网格技术通过将资源充分共享，最大限度发挥资源的 使用价值，可以将原来闲置和浪费的资源收集起来供网格用户使用，而且可以避 免以前由于地理位置限制所带来的各种额外开销。 以上的要求，都是网格需要解决的问题，也就是网格技术发挥作用的地方。网 格作为一种新型而重要的基础设施，不是一下子就能够奇迹般地出现的，需要各 个方面联合起来，共同努力才可以实现。 2 1 4 网格的特点 网格作为一种新出现的重要的基础性设施，与其它的系统相比有如下特点： 1 分布与共享 分布性是网格的一个最主要的特点。网格的分布性首先是指网格的资源是分布 的。分布的网格一般涉及的资源类型复杂，规模较大，跨越的地理范围较广。所 以基于网格的计算一定是分布式计算的。如图2 3 展示了一个问题的求解需要从a 和b 两个不同的地方获得数据，然后将这些数据传送到专门的机构c 进行数据的 分析和处理，对于处理后的结果，需要进一步在d 处通过实验进行验证，并利用 e 处的高级可视化设备进行结果显示，而问题最终得到的结果可能是在f 处进行 公布。这个问题的求解过程分别涉及到了a 、b 、c 、d 、e 、f 六个不同的地方， 这说明了网格的分布性特征。 图2 3 网格的分布性 网格资源是分布的，但是它们却是可以充分共享的。即网格上的任何资源都可 以提供给网格上的任何使用者。共享是网格的目的，没有共享就谈不上网格，解 决分布资源的共享问题是网格的核心内容。 分布是网格硬件在物理上的特征，而共享是在网格软件支持下实现的逻辑上的 特征，这两者对于网格来说都是十分重要的。 2 自相似性 网格的局部和整体之间存在一定的自相似性，局部往往在许多地方具有全局的 某些特征，而全局的特征也跟局部有定的联系。 可以认为国家级别的网格是在省一级的网格基础之上建造起来的，国家级主干 网有更大的带宽；国家级和省级网格都有各自的计算中心，只不过在计算能力上 有差异而己；它们也都必须有自己的管理节点，只是说国家级的管理节点管理功 能更多、更强大而已。 国家网格 国 家 实 验 室 国 家 计 算 中 心 省 级 子 网 格 国 家 主 干 网 国 家 管 理 结 占 其 它 省 级 实 验 室 省 级 计 算 中 心 市 县 级 子 网 格铫 其 它 图2 4 网格的自相1 i ；【性 3 动态性与多样性 对于网格来说，绝不能假设它是一成不变的。原来拥有的资源或者功能，在下 一时刻可能会出现故障或者不可用；而原来没有的资源可能随着时间的推移会不 断地加入进来。网格的动态性包括动态增加和动态减少两个方面的含义。 网格资源的动态增加需要提高网格的扩展性，也就是说在网格的设计与实现 时，必须考虑到新的资源能否很自然地加入到网格中来，并且可以和原来的资源 融合在一起，共同发挥作用。网格扩展性要求体现在规模，能力、兼容性等几个 方面。网格应该能够允许对自身进行多种形式的扩展，网格规模扩展后网格的相 应管理软件也应该能够满足扩展性的要求，网格软件的升级要能够向下兼容。 网格资源的异构和多样性为网格软件的设计提出了更大的挑战，只有解决好这 问题才能使网格更加有吸引力。 4 自治性与管理的多重性 网格上的资源，首先是属于某一组织或者个人的，因此网格资源的拥有者对该 资源具有最高级别的管理权限，网格应该允许资源拥有者对他的资源有自主的管 理能力，这就是网格的自治性。 但是网格资源必须接受网格的统一管理，否则不同的资源就无法建立相互之间 的联系，无法实现共享和互操作性，无法作为一个整体为更多的用户提供服务。 因此网格的管理具有多重性，一方面它允许网格资源的拥有者对网格资源具有 自主性的管理，另一方面又要求网格资源必须接受网格的统一管理。 2 1 5 网格的体系结构 网格体系结构就是关于如何建造网格的技术。它给出了网格的基本组成与功 能，描述了网格各组成部分的关系以及它们集成的方法或方式，说明网格的有效 运行机制。 f o s t e r 将网格体系结构定义为“划分系统基本组件，指定系统组件的目的与功 能，说明组件之间如何互相作用的技术”1 2 】。到目前为止，比较重要的体系结构 有两个【1 1 ，一个是f o s t e r 等在早些时候提出的五层沙漏结构，然后就是以i b m 为 代表的工业界的影响下，在考虑到w e b 技术的发展与影响后，f o s t e r 等结合w e b s e r v i c e 提出的开放网格服务结构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 ) 。 1 五层沙漏结构 五层沙漏结构并不提供严格的规范，它不是对全部所需协议的完整罗列，而是 对该结构中各个部分组件的通用要求进行定义，而且将这些组件形成一定的层次 关系，每一层的组件具有相同的特征，上层组件可以在任何一个底层组件的基础 之上建造i “。 铤 l 量亟 t 连接层 二】匿二 网 i 网络层i 厩磊翮 图25 五层结构及其与t o p i p 网络协议的对比 1 0 如上图所示，五层沙漏结构的五层从上到下依次是应用层、汇聚层、资源层、连 接层以及构造层。 ( 1 )构造层：局部控制的界面 网格构造层的基本功能就是控制局部的资源，向上提供访问这些资源的接口。 构造层的资源是非常广泛的。可以是计算资源、存储系统、目录、网络资源以及 传感器等。构造层应该实现的基本功能包括：查询机制( 发现资源的结构和状态 等信息) 、控制服务质量的资源管理能力等。 ( 2 )连接层：支持便利安全的通信 连接层的基本功能就是实现互相通信。它定义了核心的通信和认证协议，用 于网格事务处理之中。通信协议允许在构造层资源之间交换数据，要求包括传输、 路由、命名等功能。在实际中这些协议大部分是从t c p i p 协议栈中抽出的，比如 网络层( i p 、i c m p ) ，传输层( t c p 、u d p ) 和应用层( d n s ) 。建立在通信服务 之上的认证协议提供加密的安全机制，用于识别用户和资源。 在网格环境中，连接层的安全认证需要解决的问题或者说应该具备的特征如 表2 1 所示： 表2 1 连接层安全认证特性 特点描述 用户只需登陆一次，就可以以该身份访问不同的构造层网格资源，不 单一登陆点 需要对不同的资源多次重复登陆，也不需要用户的进一步介入。 用户必须让程序以自己身份运行的能力，因此程序就能够访问用户认 代理证的不同的资源。该程序还能够有条件地将它的部分权限授予另一个 程序( 受限制的代理) 。 不同的资源可以使用其局部的安全方案，但是网格安全方案必须能够 与局部安全方 与那些局部的方案进行互操作。不要求网格安全方案完全替代局部安 法的集成 全方案，但是它必须能够实现向局部的映射。 用户可以使用多个提供的资源，但并不要求资源提供者在安全环境中 基于用户的信协同操作或者互操作。即如果一个用户有权使用地点a 和b 的资源，用 任机制户就能够将a 和b 资源结合起来使用，并不要求a 和b 的安全管理相互作 用 ( 3 )资源层：共享单一资源 资源层的主要功能就是实现对单个资源的共享。资源层建立在连接层的通信 和认证协议之上，定义的协议包括安全初始化、监视、控制单个资源的共享操作、 审计以及付费等。值得注意的是，资源层的协议考虑的安全是单个的局部资源， 因此忽略了全局状态和跨越分布资源集合的原子操作( 这些问题是由汇聚层考虑 的) 。 表2 2 资源层的协议类型及描述 协议类型 描述 信息协议得到资源的结构和状态信息，如配置，当前负载，使用策略等 通过谈判访问共享资源，指出资源需求以及将执行的操作。初始化共享 管理协议关系，保证要求的协议操作与底层共享策略一致。还要考虑记账和付费 问题，协议还可能需要具有监控操作的状态并控制某些操作的功能 资源与连接协议形成了沙漏模型的瓶颈部分，因此协议集合要小，而且尽量 标准化。这些协议要能够抓住涵盖不同资源类型的基本共享机制，但是不应该约 束高层协议的类型和性能。 ( 4 ) 汇聚层：协调各种资源 汇聚层的协议与服务描述的是资源的共性，并不涉及资源的具体特征，说明 不同资源集合之间是如何相互作用的。 表2 3 ；1 - 聚层服务和协议 服务与功能名称 描述 允许虚拟组织参加者发现存在的资源或者是存在资源的特性，允 目录服务 许用户根据名字或者属性来查询资源 协同分配，调度以及允许虚拟组织参加者申请分配一个或者更多的资源，并且在相应 代理服务的资源上进行任务调度 监控和诊断服务用于监视虚拟组织资源的失败，恶意攻击，入侵检查，过载等 支持虚拟组织存储、网络与计算的管理，按照响应时间、可靠性、 数据复制服务 费用等标准优化数据访问的性能 网络支持下的编程可以在网格中提供熟悉的编程模型，使用不同的网格服务解决资 系统 源发现、安全、资源分配以及其它的问题 负载管理系统与协 同分配工作框架 提供描述、使用以及管理多步、异步以及多组建工作流 软件发现服务求解问题的参数发现和选择最好的软件实现与执行平台 用于潜在较大的用户社团内的协同交换信息，包括同步与异步两 协作服务 种方式 ( 5 )应用层 应用层是在虚拟组织环境中存在的。从应用程序员的观点看网格结构，应用 层是根据在任一层次上定义的服务来构造的。在每一层都定义了协议，以提供对 相关服务的访问，这些服务包括资源管理，数据存取，资源发现等。在每一层， 可以将a p i 定义为与执行特定活动的服务交换协议信息的具体实现。这里的应用 可以调用更高级的框架。这些框架自身可以定义协议、服务和a p i ，这里只是提 出网格中要求的基本服务与协议。 五层结构的另一个重要特点就是沙漏形状。其内在含义就是因为各部分协议的 数量是不同的，对于最核心的部分，要能够实现上层各种协议向核心协议的映射， 同时实现核心协议向下层其它各种协议的映射，核心协议在所有支持网格计算的 地点都应得到支持，因此核心协议的数量不应太多，这样核心协议就形成了协议 层次结构中的一个瓶颈，在五层结构中，资源层和连接层共同组成这一核心的瓶 颈部分，如图2 6 所示： 工具与应用 应用层 诊晶蔫篮藿等 汇聚层 ) 磊：| 霎茎鬈蒿( 资源与 连接层 “? 鬻公 构造层 图2 6 沙漏形状的五层结构 沙漏的核心思想可以和微内核的操作系统进行类比，即操作系统只实现一些关 键的基本功能，而把大量与特定设备有关和与应用有关的部分交给其它部分来完 成。一个小的核心是有利于移植的，也可以比较容易地实现和得到支持。资源是 多种多样的，应用需求更是复杂多变，因此定义好这样一个核心部分的意义是很 大的。 2 开放网格服务结构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 ) 开放网格服务结构是g l o b a lg r i df o r u m4 的重要标准建议，是继五层沙漏结 构之后最重要，也是目前最新的一种网格体系结构，被称为是下一代的网格结构。 如果说五层沙漏结构是以协议为中心的“协议结构”，则o g s a 就是以服务为中 心的“服务结构”。 这里的服务是指具有特定功能的网络化实体。在五层沙漏结构中，强调的是被 共享的物理资源( 或者是这些资源所支持的服务) ，在o g s a 中，服务所指的概 念更广，包括各种计算资源、存储资源、网络、程序、数据库等等，简而言之， 一切都是服务。五层模型试图实现的是对资源的共享，而在o g s a 中，实现的将 是对服务的共享。从资源到服务，这种抽象，将资源、信息、数据等统一起来， 十分有利于灵活的、一致的、动态的共享机制的实现，使得分布式系统管理有了 标准的接口和行为。如下图所示： 服务数据的访问 g r i d s e r v i c e 导式撤销 ( 必需的) 软状态申明周期 绑定特性 一可靠激活 一认证 猢-( 可选的) 1 标准接口： 一通知 一授权 一服务创建 一服务注册 一管理 一并发 + 面向特别应 用的接口 2 7 网格示意图 简单地说，网格服务= 接口行为+ 服务数据【2 j 。 下面介绍一下建造o g s a 的两大支撑技术： ( 1 ) g l o b u s 是一种基于社团的、开放结构、并发源码的服务集合，也是支持 网络与网格应用的软件库，该工具包解决了安全，信息发现，资源管理，数据管 理，通信，错误检测以及可移植等问题。g l o b u s 工具包在世界上的许多网格项目， 包括几百个地点被使用。关于g l o b u s 的详细介绍请参见文献【1 】和1 2 】。 和o g s a 关系密切的g l o b u s 组件是g r a m ( 网格资源分配与管理协议) 和门 卫服务，它们提供了安全可靠的服务创建和管理功能，元目录服务通过软件状态 注册、数据模型以及局部注册来提供信息发现功能，g s l 支持单一登录点、代理 和信任映射。这些功能提供了面向服务结构的必要元素，但是比o g s a 中的通用 性要小。 为了对比五层结构各部分和g l o b u s 功能的对应关系给出表2 4 ： 表2 4 五层结构各部分与gl o b u s 功能对应关系 五层结构对应g l o b u s 的功能与特点 1 实现现有的构造层组件，包括卖方支持的协议与界面； 构造层2 如果卖方不提供必要的构造层行为，g l o b u s 将提供缺省的功能； 3 g a r a ( g e n e r a l - p u r p o s ea r c h i t e c t u r ef o rr e s e r v a t i o na n da l l o c a t i o n ) ，通 过提供插槽管理，为不支持这一能力的资源提供实现资源预约的功能 1 g l o b u s 使用基于公钥的g s i ( g r i ds e c u r i t yi n f r a s t r u c t u r e ) 协议用于认证、 通信保护以及授权；支持与不同安全方案的集成，使