（计算机应用技术专业论文）无资源管理自协调网格计算模型及验证.pdf

摘要 摘要 网格计算的一个重要研究方向是利用i n t e r n e t 上大量的空闲计算资源解决 大规模的分布式问题，如参数扫描、地理信息处理等，但是因为i n t e r n e t 资源 的异构性和动态性，网格计算项目常常因为不能有效的解决资源调度、信息管理 等核心问题而无法进一步的扩大规模。本文主要研究如何解决i n t e r n e t 上的高 吞吐率计算环境的扩展性和动态性这两个问题，介绍了一个无资源管理自协调网 格计算模型，对模型所使用的资源调度算法、信息管理机制和动态性屏蔽等问题 进行了讨论，根据此模型设计与实现了一个完全分布式的网格计算原型系统，并 对此原型系统迸行了初步的实验和性能测试。本文的主要研究内容包括： 介绍了一种基于节点自治的完全分布式网格计算模型。该模型采用完全分布 的体系结构，整个系统采用自组织方式构成，具有良好的扩展性。在该模型中， 不存在任何全局或局部资源管理节点，所有节点地位相等，功能相同，各自管理 自己的资源，使用者可以方便地共享和使用计算资源。 此模型使用了一个简单的信息管理机制，通过对有限的邻居节点状态的维护 获得所需要的信息，并采用一个递归资源调度算法调度计算资源，不需要任何管 理节点，就能够合理的分配计算任务，而且可以有效地控制多个节点对资源的竞 争，为系统中每个用户提供一定范围内的计算资源。为了避免实时监控带来的巨 大消耗，模型采用有限任务复制算法调度任务，以此屏蔽环境的动态性，能够有 效的避免意外情况如节点失效等，保证服务的稳定性和有效性。 根据此网格计算模型，本文设计并实现了一个网格计算原型系统。此原型系 统采用模块化设计，使用j a v a 语言进行开发，在实现模块分别实现了模型中采 用的信息管理机制、递归资源调度算法和有限任务复制算法。 本文还针对此原型系统设计了在典型网络拓扑结构上的实验，通过的大合数 分解任务的测试，对其性能进行了初步分析和评价。实验结果显示该网格计算模 型负载分布合理，能够充分利用系统中计算资源提供的计算能力，对环境的动态 性有一定的适应能力，在高吞吐率计算领域可以有更大的发展。 关键词：网格计算，高吞吐率计算，网格计算模型，自治，递归资源调度，有限 任务复制，原型系统 a b s t r a c t o n eo ft h em o s ti m p o r t a n tr e s e a r c hf i e l d so fg r i dc o m p u t i n gi sh a r v e s t i n gt h ei d l e t i m eo fc o m p u t e r so ni n t e r n e tt or u nv e r yl a r g ed i s t r i b u t e da p p l i c a t i o n , s u c h 嬲 p a r a m e t e rs w e e p s ，g e o g r a p h i ci n f o r m a t i o np r o c e s s i n ge t c h o w e v e r , b e c a u s eo ft h e h e t e r o g e n e i t ya n dd y n a m i co ft h ei n t e m e t , t h es c a l eo f 鲥dc o m p u t i n gi su s u a l l y r e s t r i c t e d 。i nt h i sd i s s e r t a t i o n , t h ed i s p o s a lo ft h et w ok e y p r o b l e mo f h ig ht h r o u g h p u t c o m p u t a t i o n o ni n t e m e t ，t h es c a l a b i l i t ya n dd y n a m i c ，a r ep r e s e n t e d af u l l y d i s t r i b u t e d 班dc o m p u t a t i o n m o d e lb a s e do nn o d e a u t o n o m y , a s w e l la sa l l i n f o r m a t i o nm a n a g e m e n tm e c h a n i s m ，ar e s o u r c e ss c h e d u l ea l g o r i t h ma n das o l u t i o n f o rt h ed y n a m i co fe n v i r o n m e n tm a t c h e d ，i si n t r o d u c e di n t h i sd i s s e r t a t i o n a p r o t o t y p es y s t e mn a m e dn o m a n g r i db a s e do nt h i st h e o r yi sd e s i g n e da n dr e a l i z e d w i t ht h ep r i m a r ye x p e r i r n e n ta n da n a l y s e s t h em a i nc o n t e n t so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： a f u l l yd i s t r i b u t e d 鲥dc o m p u t a t i o nm o d e lb a s e do nn o d ea u t o n o m yi s i n t r o d u c e d t h ef u l l yd i s t r i b u t e da r c h i t e c t u r eo ft h em o d e le x t e n d st h es c a l e a st h e r e i s n ta n yc e n t r a lp r o x yi nt h em o d e la n dn o d e si nt h es y s t e mm a n a g er e s o u r c e sa l lb y t h e m s e l v e s ，t h i sm o d e li sn o tr e s t r i c t e dt oas t a t e ds i z eb u th a se n o r m o u se x p a n s i b i l i t y a s i m p l ei n f o r m a t i o nm a n a g e m e n tm e c h a n i s mi si n t r o d u c e dt ot h em o d e l b y m a i n t a i n i n gl i m i t e di n f o r m a t i o no fi t sn e i g h b o r i n gn o d e ，ar e c u r s i v er e s o u r c e s s c h e d u l ea l g o r i t h ms e n d st h et a s k st ot h en e a r e s ti d l e c o m p u t e r w i t h o u ta n y m a n a g e m e n tn o d e ，t h er e s o u r c e ss c h e d u l ea l g o r i t h m d i s t r i b u t e st h ec o m p u t i n g r e s o u r c e 嬲r e a s o n a b l ea sp o s s i b l e a tt h es a m et i m e ，c o m p e t i t i o nf o rt h ec o m p e t i t i o n f o rs h a r e dr e s o u r c e sb e t w e e nm u l t i u s e r si s d i s p o s e da n de v e r yu s e r c a n g e t a p p r o p r i a t ec o m p u t a t i o nr e s o u r c e s t os o l v et h ed y n a m i co fi n t e m e te n v i r o n m e n t w i t h o u tw a s t ec a u s e db yr e a l - t i m em o n i t o r i n g , al i m i t e dt a s k sr e p l i c a t i o na l g o r i t h mi s i n t r o d u c e dt ot h i sd i s s e r t a t i o n a sar e s u l to ft h el i m i t e dt a s k sr e p l i c a t i o na l g o r i t h m ， t h eg r i dc o m p u t a t i o nm o d e lc a l lp r o v i d eu s a b l ea n dd e p e n d a b l ec o m p u t a t i o na b i l i t yi n t h ed y n a m i ce n v i r o n m e n t b a s e do nt h i sm o d e l ，ap r o t o t y p es y s t e mo fg r i dc o m p u t i n gi sd e s i g n e da n d r e a l i z e d t h i sp r o t o t y p es y s t e mi sc o m p o s e do f4m o d u l e sa n dt h ec o d i n gl a n g u a g ei s j a v a t h ei n f o r m a t i o nm a n a g e m e n t m e c h a n i s m ，t h e f o r m a t i o n m a n a g e m e n t m e c h a n i s ma n dt h er e s o u r c e ss c h e d u l ea l g o r i t h ma r ea c h i e v e di nt h ep r o t o t y p es y s t e m t ot e s tt h ec o m p u t i n gc a p a b i l i t yo fn o m a n g r i d ，t h ev a l i d i t yo ft h ei n f o r m a t i o n m e c h a n i s ma n dt h ef e a s i b i l i t yo ft h et a s ks c h e d u l i n g , a l le x p e r i m e n to fc o m p o s i t e t l a b s t r a c t n u m b e rd e c o m p o s i t i o ni si n t r o d u c e d t h ee x p e r i m e n t a ld a t as h o w st h a tt h es y s t e m b a l a n c e st h en e t w o r kt r a f f i ca n dd i s t r i b u t e si tt oa l ln o d e se q u a l l y , w h i l ee n s u r i n gt h e e f f e c t i v et a s ks c h e d u l i n g ，s ot h a ta l lt h en o d e sa r ef u l l yu t i l i z e da n dt h et a s kl o a di s p r o p o r t i o n a lt ot h ec o m p u t i n gc a p a b i l i t y k e yw o r d s ：c o m p u t a t i o ng r i d ，h i 曲t h r o u g h p u tc o m p u t a t i o n ，g r i dc o m p u t a t i o n m o d e l ，a u t o n o m y , r e c u r s i v er e s o u r c es c h e d u l e ，l i m i t e d t a s k sr e p l i c a t i o n , p r o t o t y p es y s t e m i i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 伊吕年5 月够日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 同超 u d t 年5 月够e t 第一章引言 第一章引言 第一节网格的提出及发展 计算机在人类的科学研究领域中发挥着越来越重要的作用，在医学、天文学、 生物学、地理、核物理等研究中，都需要具有超大规模的计算和数据分析能力。 为了获得超大的计算能力，计算机科学家提出了高性能计算系统【1 1 、集群技术【2 】、 分布式计算技术【3 】等，但是这些技术的实现通常十分昂贵，而且使用领域有限， 只能帮助特定的用户使用一定范围的计算资源，所共享的资源也很有限。 与此同时，随着计算机技术的进步，个人p c 、小型服务器的计算能力不断 增强，i n t e m e t 的普及使得世界上任何一个角落的计算机都能够方便的获得网络 资源。i n t e r n e t 上聚集了大量的计算资源，包括个人电脑、工作站、集群系统、 超级计算机等各种计算资源，它们往往也通过一个或多个网关接入i n t e m e t ，和 直接连在i n t e r n e t 上的计算资源一起组成了一个物理上连接的超大规模网络，而 这些计算资源的利用率非常低，它们通常处于空闲状态，具有很多未用的内存、 磁盘空间 4 1 和计算能力。 网格计算研究的目的之一就是将i n t e r n e t 上的空闲资源整合成一个超大规 模的虚拟计算机，用以解决大规模的分布式计算问题，如药物筛选【5 1 、蒙特卡罗 【叼模拟、高能物理、生物信息、地球观测、全球变迁等。网格计算是由元计算【刀 的概念发展而来的，i w a y 项目中首次提出了网格计算q r i d 的概念【8 1 ，其最 初的目标是联合独立的超级计算机，为复杂大型科学计算问题提供统一的解决方 案，但随着i n t e r n e t 技术的发展和网络的普及，网格的概念和内涵发生了巨大 的变化。 网格计算最初的定义为：计算网格是一个硬件和软件的基础设施，它提供了 可靠的、一致的、普遍的和廉价的方法来获得高端的计算能力 9 】，该概念强调的 是地理上分布的资源之间的共享和协同；同时相关研究者也给出了网格定义的三 个标准：一是在非集中控制的环境中协同使用资源，二是使用标准的、开放的和 通用的协议和接口，三是提供非平凡的服务。 第一章引言 根据网格共享资源的目的，计算机科学家提出并实现了了多种网格，如以共 享计算资源为目标的计算网格、将网络上信息资源进行有效组织的信息网格、面 向广域网环境中数据的管理与传输的数据网格、为各种计算资源提供统一的服务 访问方式的服务网格等。目前网格正逐步向商业领域扩展，继以协议为中心的五 层沙漏结构之后一j ，i a nf o s t e r 结合w e bs e r v i c e 技术提出了以服务为中心的 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 ) 网格体系结构【l o i ，同时一些商业网 格也应运而生，如i b m 的按需计算、s u n 的s u n - o n e 1 1 】等，微软的n e t 等。 第二节网格计算在科学领域的应用 近年来，计算网格在科学研究中获得了很大的发展，其中最主要的应用是分 布式超级计算、高吞吐率计算和数据密集型计算。 ( 1 ) 分布式超级计算：利用聚集的多个分散的超级计算机解决由于c p u 速 度，内存大小等限制而无法在单一系统中解决的科学与工程计算问题。 ( 2 ) 高吞吐率计算：和分布式超级计算不同，高吞吐率计算关心的是更长时 间内完成的计算量。它用于调度大量松耦合或相互独立的任务，利用空闲的处理 器周期来执行这些任务。 ( 3 ) 数据密集型计算：在数据密集应用中，主要是从分布在各地数据仓库、 数字图书馆、数据库中的数据综合分析得到新的信息。这些分析过程通常会产生 很大的计算和通信需求。 分布式超级计算是计算网格最初的应用方向，但是分布式超级计算并没有在 计算网格上很好的实现，主要由于以下的原因：大部分计算问题不能很好的划分 为松耦合的任务，而任务之间的相互通信对网络的带宽、延迟等要求很高，网络 的延迟大大超过计算机的内部通信延迟，c a c t u s 模拟黑洞的试验中出现了利用 两台并行计算机得到的性能居然比四台还高的现象【1 2 】。受制于任务划分和网络延 迟的影响，计算网格很难扩大规模，无法充分利用资源。数据密集型计算同样对 网络的通信有比较高的要求，在i n t e r n e t 比较复杂的网络的环境下，网格计算 的服务质量无法得到保证。 高吞吐率计算关注于松耦合的大型任务，通常对网络的通信的带宽、延迟要 求不高，由于计算资源性价比的提高，部分用户关心的是计算网格系统在一段时 第一章引言 间内能够提供的服务或者完成任务的多少，而不是任务完成的时间。与此同时， i n t e t n e t 上的空闲计算资源具有不确定性，即计算资源随时可能被回收，而且通 信延迟可能变化，松耦合的任务更适合分散的计算资源进行计算，减少了任务之 间的通信，网格计算节点之间的通信瓶颈不再存在。因此计算网格可以在高吞吐 率计算中实现比较大的规模，获得更多的节点和计算资源，使用更少的网络资源。 c o n d o r ( c o n d o r - g ) t 1 3 1 和n i m r o d ( n i m r o d g ) 1 4 】是比较成功的高吞吐率计算环境。 本文主要研究适用于高吞吐率计算的计算网格，讨论对环境动态性具有自适 应能力的完全分布式体系结构和相关算法，设计并实现无资源管理自协调网格计 算的原型系统，并对此原型系统进行测试和讨论。 第三节网格计算研究中的关键问题 高吞吐率网格计算的研究主要关注以下几个方面的性能：扩展性、动态性、 和安全性。 ( 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 是一个异构的环境，包含各种各样的计算资源，这些 计算资源往往具有不同的c p u 类型、不同的操作系统等；要想共享多种异构的计 算资源，高吞吐率计算环境必须能够适应不同的平台，提供一个统一的资源访问 接口，使用户能够方便地使用远程计算资源。目前很多高吞吐率计算环境均采用 j a v a 作为编程语言，正是由于其良好的可移植性和跨平台特性。 在i n t e r n e t 环境中，由于i p v 4 的限制，很多企业、公司、校园网内的大量 计算资源无法拥有一个公有的i p 地址。通常采用方法是各个公司内部或校园网 内建立一个自己分配i p 地址( 私网地址) 的i n t r a n e t 网络，然后通过一个或多 个拥有公有i p 地址的服务器网关接入到i n t e r n e t ，使内部的计算机可以访问外 第一章引言 部具有公有地址的计算机，现有的i n t e r n e t 技术可以通过n a t ( n e t w o r ka d d r e s s t r a n s l a t i o n ) 1 5 】和n a p t ( n e t w o r ka d d r e s sp o r tt r a n s l a t i o n ) 1 6 1 很好的支持 这一点，但是外部的计算机主动与私网内的计算机通信，特别是某个私网内的计 算机与另一个私网内的机器的相互通信却非常困难，到目前为止没有一个很好的 解决方案。如果能解决这个问题，不仅能使高吞吐率环境容纳更大范围内的计算 资源，而且能够增加更多的应用范围，如企业之间、公司之间的计算资源共享， 多个校园网之间的资源共享等。 ( 2 ) 动态性 i n t e r n e t 是一个动态的环境。由于网络连接不稳定，网络中断时有发生， 计算资源也因为断电、异常等情况经常宕机；由于资源的共享，节点的处理能力、 网络带宽等经常发生变化；同时，在一个好的高吞吐率计算环境中，应该允许计 算资源自由地加入或离开系统，更为重要的是由于高吞吐率计算利用的是空闲资 源，当资源拥有者需要使用资源时，应允许资源拥有者回收资源而不影响他们对 资源的使用。在这样的动态环境中，一个良好的高吞吐率计算环境应能及时使用 新加入节点的计算能力，屏蔽环境的动态性，使之不因资源的动态变化而对网格 应用造成太大的影响，为用户提供持续、可靠的计算能力，保证系统的可用性。 ( 3 ) 安全性 对于基于i n t e r n e t 的高吞吐率计算环境来说，所有的资源都是连接在 i n t e r n e t 上，为所有用户服务，用户也是通过i n t e r n e t 将任务提交到不同的计 算资源上，一个良好的高吞吐率计算系统应能保证资源提供者和用户的安全。对 于资源提供者来说，系统不能破坏资源提供者的资源，不能泄漏其隐私，保证其 所提供的资源的绝对安全，这是资源提供者愿意加入系统的前提；而对于用户来 说，任务通过i n t e r n e t 发布到各个计算资源上，系统应保证用户的商业秘密不 被泄漏，这是用户愿意使用系统的前提。但由于基于i n t e r n e t 的高吞吐率环境 中资源和用户的大规模和动态性，其安全性比一般的网格计算系统更加难以保 证。 第一章引言 第四节网格计算目前的相关研究 网格计算为大运算量的复杂问题提供了新的解决方案，在世界范围内有许多 正在研究或已经投入使用的网格项目，如美国的g l o b u s 1 7 1 、l e g i o n 18 】等，欧洲 有e u r o g r i d 1 9 1 、e u r o p e a nd a t ag r i d m 和北方四国的n o r d u 硷1 3 等；日本有n i n f 径幻 等，我国有国家高性能计算环境( n h p c e ) 和中科院的织女星网格晗3 1 等研究项目。 高吞吐率计算领域也有一些网格系统，如共享局域范围内空闲资源的c o n d o r n 羽、 n i m r o d n 钔，共享i n t e r n e t 上空闲计算资源的s e t i h o m e 乜4 j 、d i s t r i b u t e d n e t 、 s u p e r w e b 、j a v e li n 、j a v e l i n + + 、b a y a n i h a n 、a n t h il l 、p a r a d r o p p e r 等。能够 共享i n t e r n e t 上空闲计算资源的高吞吐率系统被称为全球计算系统( g l o b a l c o m p u t i n gs y s t e m ，g c s ) 【2 5 1 ，由于共享资源大部分来自于自愿捐赠和大量普 通的桌面计算机，这些系统往往也被称作公用资源计算( p u b l i cr e s o u r c e c o m p u t i n g ) 2 6 1 、自愿计算( v o l u n t e e rc o m p u t i n g ) 2 7 1 、拾遗网格( s c a v e n g i n g g r i d ) 2 8 】等。 第五节本文的内容安排 目前基于i n t e r n e t 的高吞吐率计算网格的体系结构大致可以分为两类，一 类是集中式的体系结构，一类是分布式体系结构的p 2 p 网格；前者由于中心管理 的原因无法形成比较大的规模，后者则需要比较大的节点之间通信量，仍处于研 究阶段。 本文将根据无资源管理自协调网格计算模型，针对模型体系结构、任务调度 算法、动态性屏蔽问题进行研究和讨论，在此基础上设计并实现无资源管理自协 调网格计算原型系统n o m a ng r i d 原型系统，并对此原型系统的性能进行测试 和研究。 可扩展体系结构是n o m a n g r i d 网格计算模型的核心，本文第二章对其进行 了叙述，并重点介绍了系统中每个节点的功能，系统的信息管理机制和工作流程。 在没有中心管理节点存在的情况下，n o m a n - g r i d 资源调度算法将任务有效 调度到空闲节点运行，该算法将在本文第三章阐述，同时介绍如何控制多个用户 在系统中对共享资源的竞争。n o m a n - g r i d 采用简单的有限任务复制算法来屏蔽 i n t e r n e t 环境的动态性，第三章的后半部分重点介绍n o m a n g r i d 的有限任务复 第一章引言 制算法和相应的动态性解决方案。 本文依据n o m a n g r i d 网格计算模型开发了一个原型系统，并采在多种情况 下对系统进行t n 试和对系统的性能进行了初步的分析，本文第四章和第五章介 绍原型系统的设计与实现和对系统进行的性能分析过程。 本文最后一章对全文进行了总结并描述了未来的工作。 第二章无资源管理自协调网格计算模型 第二章无资源管理自协调网格计算模型 无资源管理自协调网格计算模型 2 9 】( 以下简称n o m a n - g r i d ) 采用基于节点自 治的完全分布式网络计算模型的体系结构，与之相适应的信息管理机制、资源调 度算法与动态性解决方案，使该模型在大规模、动态的i n t e r n e t 环境中，具有 良好的可扩展性、可靠性和可用性。 在此系统中，不存在任何资源管理节点，系统中的所有节点功能相同、地位 对等，每个节点都可以随时向系统中分布的计算资源提交运行任务请求，由多个 节点共同完成大规模计算任务，同时能够协调、监控各个子计算任务的运行情况。 本章阐述n o m a n g r i d 的体系结构和工作流程，重点介绍自治节点的模型以 及节点的信息管理机制，并简要介绍系统的资源调度方法和动态性屏蔽机制。 第一节无资源管理自协调网格计算模型体系结构 2 1 1 节点功能模型 n o m a n g r i d 系统采用自组织方式构成，完全由愿意共享自己的计算能力 的计算资源或需要额外计算能力用户所控制的计算资源相互连接而成，本文称系 统中共享的计算资源为节点。下面将简要介绍节点加入、计算组织互连等系统的 网络组织方法。图2 1 是一个包括环、分枝、直线的典型系统组织图： 。 图2 1 典型系统组织图 根据图2 1 ，我们来进行邻居节点概念的定义： 将整个网络拓扑看成一个无向图g ，如上图g = a ，b ，c ，d ，e ，f ，g ，n ，i ，j ，k 。 定义l ：与某个节点相连的节点称为该节点的邻居节点。记n e i g h b o r ( v ) 为 第二章无资源管理自协调网格计算模型 节点v 的邻居节点集合，n n e i g h b o r ( v ) 为邻居节点个数。如 n e i g h b o r ( a ) = b ，c ，d ，n n e i g h b o r ( v ) = 3 。 在n o m a n g r i d 系统中，所有节点地位相等，功能相同，参与系统的每个节 点都必须共享自己的计算能力，同时，在每个节点上用户都能提交任务( 本文中 将这样的节点称为任务源节点) ，利用系统所聚合的计算能力。和电网类似，节 点不需考虑计算资源来自于哪个节点，正如用户不需要考虑电力来自哪个发电 机，而且在n o m a n - g r i d 中，每个节点都可以提供计算资源。图2 2 是n o m a n g r i d 节点功能模型。 任务管理器 任务调度器 信息管理 本地资源管理器 应用层 核心层 亟亟亟匝圃资源层 图2 2节点功能模型 n o m a n g r i d 节点模型可按照功能不同划分为应用层、核心层和资源层，应 、用层是与用户进行交互的接口，处理用户提交的请求与计算任务，并将运算结果 返回给用户；任务管理器、任务调度器、信息管理和本地资源管理器属于核心层； 资源层负责与硬件交互和进行网络通信。下面是各层功能的简要介绍： 应用层：用户自己所在的节点上提交请求，将计算任务提交给n o m a n g r i d 系统，应用层将计算任务传递给核心层，同时实时显示本节点的运行状态，如系 统负载、邻接节点状态、任务运行状态等。 核心层：由任务管理器、任务调度器、信息管理和本地资源管理器组成， 核心层的功能和运行是本文研究的重点内容之一。任务管理器的功能是保存计算 任务，计算任务可以来自本节点，也可以由其它节点转发而来，任务管理器将任 务接受和保存，并在需要的时候将任务发送给任务调度器，当用户需要取消任务 第二章无资源管理自协调网格计算模型 的时候将计算任务删除；信息管理维护邻居节点信息，包含节点本身以及其所有 邻居节点的简单信息，节点信息包括节点能否提供计算资源、是否被控制等；任 务调度器从任务管理器中获取任务队列，根据任务调度规则选取计算任务放入执 行队列，并确认在本节点运行或是交由邻居节点运行；本地资源管理器负责管理 和监视计算运行情况，可以随时中断对计算资源的使用，并将资源的使用情况反 馈给应用层。 资源层：包括计算资源的操作系统、硬件和通信协议等，是n o m a n g r i d 的硬件和软件基础。 2 1 2 任务提交 n o m a n - g r i d 系统的用户通过用户界面将计算任务提交，目前的高吞吐率计算 要求任务之间不进行通信以减少网络通信负载，用户需要将大的计算任务分解成 为相对独立的子任务序列。 2 1 3 核心层功能 n o m a n - g r i d 的核心部分包括任务管理器、任务调度器、信息管理以及本地 资源管理器，各个功能模块负责系统的正常运转，保证在没有中心管理节点的情 况下合理的分配计算任务以及节点之间的协调，需要解决的几个关键问题： 如何为请求计算资源的用户提供一定范围的资源。 如何解决多个节点同时提出计算请求时的冲突。 如何屏蔽网络环境的动态性，为每个用户提供持续、可靠的计算资源。 任务管理器、任务调度器、信息管理和本地资源管理器四个模块之间的逻辑 关系如图2 3 所示。 第二章无资源管理自协调网格计算模型 图2 3核心层模块之间的逻辑关系 任务管理器接负责接收任务，计算任务可以来自本节点的提交或者是邻居节 点转发过来，所有任务都在任务队列进行排序，同时还负责将任务结果返回任务 的提交节点。n o m a n - g r i d 模型要求不能影响用户对本地资源的占有即优先本地 计算任务，从两方面保证，一是只有在节点计算资源空闲的时候才能接受其他节 点的任务发送，另一方面是一旦本地节点有任务提交，本地任务优先级最高，执 行完当前任务后立即执行本地计算任务。如果本节点是任务源节点( 即本节点需 要计算资源的使用) ，n o m a n - g r i d 通过一些机制保证本节点的计算任务不会被外 来任务中断，与此对应，如果本节点不是任务源节点，任务队列中也不会存在来 自于本节点提交的任务。 对于本节点是否是任务源节点，任务管理器的处理是不同的。如果本节点是 任务源节点，任务队列需要一直维护本地任务直到该任务的结果返回( 包括在本 地运行或者由其他节点完成) ，并将结果返回给用户；如果本节点不是任务源节 点，当某个任务被发送出去或者在本地被执行，该任务立刻被删除，不会重新调 度，详细算法将在本文第三章描述。 信息管理模块负责维护邻居节点信息表，其中包含所有己知邻居节点和本节 第二章无资源管理自协调网格计算模型 点的相关信息，不包括队列长度或者c p u 负载等比较复杂的信息，主要包括了两 方面的内容：从本节点看邻居节点的相对能力信息和多个任务源节点竞争资源的 控制信息，这些信息不需要节点之间的实时通信进行统，而是当任务调度、结 果返回、节点申请加入时，才有可能发生变化。采用简单信息管理机制可以避免 信息的协调和同步造成系统的性能瓶颈：一方面信息管理如果维护网络负载、队 列长度等动态信息，需要很大的代价，目前的网络不可能保证如此大的通信量都 是可靠和迅速的；另一方面，同步信息需要很大的开销，大量的资源被浪费在节 点信息的统一上，即使系统很长时间的没有任务运行；n o m a n g r i d 的信息管理 机制的目标是最大限度减少这两方面的消耗。 n o m a n g r i d 系统中不需要任何节点管理其他节点，因此系统中的节点只能 了解系统中局部的状态，如何保证系统资源的有效利用，如何控制多个节点对于 计算资源的竞争，是本文研究的重要内容。 邻居节点中保存本节点当前所有邻接节点的信息，当本节点有任务需要邻居 帮助运行时，任务调度器查询邻居节点表获得当前可用的邻居节点相关信息：包 括i p 和控制信息，之后将任务发送到这些邻居节点。在图2 1 中，假设d 节点 有任务发送到邻居节点运行，d 节点首先查询自己的邻居节点表，获得一系列可 用的计算资源，之后将任务发送到e ，a ，g ，f ，这样便形成了以d 节点为中心 的一个计算范围，而a 节点可能再继续将任务发送到b ，c 节点，再没有遭遇竞 争的情况下，d 节点占有的资源将逐步扩大。 n o m a n - g r i d 的特点是最大程度的利用空闲计算资源而不影响普通用户的正 常使用，因此当提供计算资源的节点需要回收资源的情况发生时，如c p u 占用率 过高时，正在运行的任务将被挂起或者终止。本地资源管理器负责监视本地资源 的运行状况，根据用户的设置，当n o m a n g r i d 占用的资源超过预设值，任务会 被中断，反之，当系统资源空闲下来，任务会被投入运行。 第二节信息管理 n o m a n g r i d 的信息管理保证了系统调度的合理性，每个节点负责管理自己邻 居节点的信息状态，即每一个节点都是n o m a n g r i d 的管理节点。在节点的邻居 节点表中保存两方面的信息：邻居节点能力信息和节点竞争资源的控制信息。 第二章无资源管理自协调网格计算模型 2 2 1 邻居节点能力信息 根据共享资源的使用频度和存在范围，网格中的资源分成两类：稀有资源和 一般资源。稀有资源只存在于个别节点，而一般资源可以有网格中的普通节点提 供，如计算资源。由于节点的情况不同，用统一的方式表达一般资源有比较大的 难度，n o m a n - g r i d 的目标是共享普遍存在的计算机的计算能力。i n t e r n e t 中计 算资源种类众多，从个人p c 到超级计算机，计算能力各不相同，有可能相差很 多数量级，使用统一的衡量标准必然造成使用上的难度，而且对于同一计算资源， 也可能不断变化，如果网格系统采用实时监视各个计算资源的变化，必须节点进 行频繁和大量的通信，不仅造成了网络资源的浪费，使用效率比较低，而且从原 理上限制了系统规模的扩大，无法利用更多的计算资源。 考虑到以上各个限制，n o m a n - g r id 抽象出计算能力，不量化计算能力的大 小和动态性，使用简单的概念衡量一个计算资源：有计算能力或者无计算能力。 当n o m a n - g r i d 中的节点正在运行一个计算任务，此节点的资源状态为无计算能 力，否则为有能力，这样达到了简化资源描述的目的。本文以1 表示有能力，以 0 表示无能力。 在邻居节点表中，n o m a n - g r i d 记录着与自己邻接的节点的计算能力状态， 即邻居节点能力信息，这是n o m a n - g r i d 任务调度的基础。当系统中一个节点进 行任务调度时，如果需要邻居节点的参与，则向有能力的节点进行调度。这里需 要说明有能力的定义，不是特指该邻居有能力，而是此邻居和其邻居节点表内所 有节点的合集中，只要有节点的能力状态是有能力，就是有能力节点。 n o m a n g r i d 使用相对能力信息表示邻居节点的能力状态，下文以r ( u ，v ) 表示从 节点u 的邻居节点v 的相对能力，即节点v 相对于节点u 的能力。 为了统一的表达和推理，n o m a n g r i d 中的节点将自身作为的一个邻居节点， 并放在邻居节点表的第一位。在图2 4 中，节点b 1 是节点b 在自己邻居节点表 中的表示，则r ( a ，b ) 是节点b 的所有邻居节点b 1 、c 、d 、e ( 不包含a ) 的本 地能力的或，只要其中一个节点的本地能力为有能力，则r ( a ，b ) 就是有能力， 否则，就是无能力。 第二章无资源管理自协调网格计算模型 图2 4相对能力示意图 相对能力是一个相对的概念，具有方向性即不对称性，即使从u 看v 的状态 为有能力，但从v 的其它邻居节点v 看却不一定有能力。如在图2 4 中，r ( a ，b ) 为从节点b 相对于节点a 的能力，只要节点b l 、c 、d 、e 中一个为有能力，在这 里我们假设只有节点c 是有能力的，a 、b 、d 、e 节点都是无能力的，则r ( a ，b ) = 1 ， 但从节点c 的方向来看，r ( c ，b ) = o ，b 为无能力，因为c 被排除。这样的机制 保证了系统调度的合理性，即任务可以及时的调度到有能力的节点，而且不会重 复调度到没有能力的节点，造成任务的堆积。 2 。2 。2 资源竞争控制信息 网格为系统中的众多用户提供服务，一旦多个用户同时申请同一资源的情况 发生，需要合适的管理机制协调多个申请之间的竞争，通常的解决方式是由一个 管理中心进行协调，为用户提供查找和统一的分配资源，如g l o b u s 的元计算目 录服务m d s ( m e t a c o m p u t i n gd i r e c t o r ys e r v i c e ) 【3 0 】和c o n d o r 的m a t c h m a k e r 【3 1 】 等。但是在n o m a n - g r i d 中，分布式的管理方式决定没有一个统一的控制中心， 在多个用户同时提交应用的时候，系统中存在多个任务源节点，每个任务源节点 都试图占有更多的节点为自己服务，以自己为中心形成一个势力范围，当两个势 力范围相遇时，会出现对计算资源的竞争。 在图2 5 中是一个资源竞争的普遍情况，节点a 和b 同时提交了应用申请， 并占据了周围的一系列节点，当a 占据了c 、e 、i 、f ，b 占据了d 、g 、h 的时候， 节点e 将试图将a 提交的任务发送到d ，而d 也将试图将b 的任务发送到e ，这 是就出现了冲突，n o m a n - g r i d 使用资源竞争机制解决这些冲突，使得节点d 和e 之间形成边界，在a 和b 运行任务的时候有各自的势力范围，互不影响，而当任 第二章无资源管理自协调网格计算模型 务运行结束之后，边界被解除，回到初始状态，资源竞争机制将在第三章详细描 述。 图2 5资源竞争和资源范围 n o m a n - g r i d 的资源竞争机制需要协调不同节点对于同一资源的竞争，在比 较简单的解决方法的前提下，还要保证每个任务提交节点都能获得一定范围的计 算资源，有效的完成计算任务。为达到这些目标，系统中的节点需要了解邻居节 点的资源控制状态，即邻居节点是否正在被其他节点使用，n o m a n g r i d 的信息 管理提出了一套管理机制并定义了资源竞争控制信息，标记本节点的所有邻居节 点的状态，该状态有三种可能：b o u n d a r y ( 边界) 、d o m i n a t e ( 控制) 、n o r m a l ( 正常) 。 “ 1 ) b o u n d a r y ：邻居节点的状态为边界，即邻居节点已经被其他节点占用， 不管是否有能力，都不能接受本节点的任务。 2 ) d o m