（计算机应用技术专业论文）nomangrid：一种无资源管理自协调网格.pdf

摘要 摘要 网格系统具有动态性强、异构性复杂和节点数量庞大的特点，在这样的环 境下正确并高效的完成应用就必须解决动态性屏蔽、异构性屏蔽和系统扩展性 等问题。当前的网格项目能够做到动态性和异构性的屏蔽，但是在系统扩展性 上很难达至i i m e m e t 计算的节点数量级，这是因为资源管理和数据传输等重要问 题的解决还存在困难。本文介绍的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 基于无资源管理自协调网格计算模型实现，该模型整体组织形 式上采用自组织方式构成，系统中没有中心资源管理节点也没有任何节点具有 全局知识，所有节点的地位、功能都相同。节点只管理自身的资源，只需将需 要计算的任务根据给定的算法传递给相邻的节点。系统中每个节点只需遵守一 定的相对简单的算法对任务及自身资源进行管理，整个系统全局即形成了无中 心管理的自治网格系统。 n o m a n g r i d 提出了一系列算法来保障系统的动态性和扩展性。完全分布式 的任务调度算法，系统中的每个节点在没有全局知识的情况下能够将任务发送 到相邻的节点，任务负载分布会遵循压力传递分布模式，算法保证任务可以传 达到系统的所有节点。在系统中存在多个任务源节点的情况下，会出现多个应 用争用计算资源的现象，对于这种情况可以使用资源竞争算法判定并分配被竞 争的计算资源。根据边界解除算法及时释放已经不再需要的资源以供其它用户 的应用使用，可以提高系统内资源利用率。针对应用环境的动态性n o m a n - g r i d 提出了有限任务复制算法，此算法能够屏蔽动态性保证用户提交的应用正确完 成。 对于无资源管理自协调网格计算模型和各种算法的验证需要建立一个原型 系统g 1 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 的特性是否符合设计的初衷。原型系统根据无资源管理自协 摘要 调网格计算模型设计并实现，开发环境使用j a v a 开发平台，在开发过程中采用了 模块化的设计思想。 设计了两组实验验证n o m a n g r i d 系统的两个主要特性：任务负载分布符合 压力传递分布模式和资源管理成本不随系统规模扩大而上升。根据实验数据结 果分析说明n o m a n - g r i d 适用于节点数量庞大的系统环境。 关键词：计算网格压力传递分布模式自治网格计算模型 a b s t r a c t ab s t r a c t g r i ds y s t e me n v i r o n m e n th a ss e v e r a lc h a r a c t e r i s t i c s ，s u c ha ss t r o n gd y n a m i c ， c o m p l e xh e t e r o g e n e o u sa n dh u g en u m b e ro fn o d e s t of i n i s ha p p l i c a t i o ne f f i c i e n t l y i ns u c ha ne n v i r o n m e n t ，t h e s et h r e ek e yp r o b l e m sm u s tb ed i s p o s a l s o m eg r i d p r o j e c t sc a ns o l v et h ed y n a m i ca n dh e t e r o g e n e o u sp r o b l e m , b u tt h es c a l a b i l i t yc a i ln o t r e a c ht h es c a l eo ft h ei n t e r n e t ，t h i si sb e c a u s et h ec o r ei s s u e s ，s u c ha sr e s o u r c e m a n a g e m e n ta n dd a t at r a n s m i s s i o n ，a l es t i l ln o tr e s o l v e d t h i sd i s s e r t a t i o nd e s c r i b e s t h en o m a n g r i ds y s t e md e s i g nf o rt h el a r g e - s c a l ee n v i r o n m e n t ，w h i c hw i t h o u t r e s o u r c em a n a g e m e n tb o t t l e n e c ki nl a r g e s c a l es y s t e m t h i sd i s s e r t a t i o nc o v e r st h em a i nr e s e a r c hn o m a n - g r i da r c h i t e c t u r e ，a l g o r i t h m s ， ap r o t o t y p es y s t e m ，a n da n a l y s i sa n dd e s i g ne x p e r i m e n t sf o rt h em a i nc h a r a c t e r i s t i c s o ft h en o m a n g r i d n o m a n - g r i di st h ep r o t o t y p es y s t e mo ft h e 伽l yd i s t r i b u t e dg r i dc o m p u t a t i o n m o d e lb a s e do nn o d ea u t o n o m y n o m a n - g r i di sas e l f - o r g a n i z a t i o ns y s t e m ，a n dt h e r e i sn on o d ew i t hg l o b a lk n o w l e d g e ，a l ln o d e sh a v es a m es t a t u sa n df u n c t i o n t h e t h i n g so n en o d et od oi sm a n a g i n gl o c a lr e s o u r c e sa n dd i s t r i b u t et a s kt oi t sn e i g h b o r n o d ea c c o r d i n gt oa l g o r i t h m n o m a n g r i da d d r e s s e sas e r i e so fa l g o r i t h m st os o l v et h ed y n a m i ca n d s c a l a b i l i t yp r o b l e m f u l l yd i s t r i b u t e dt a s ks c h e d u l i n ga l g o r i t h m ，s e n dt a s kt on e i g h b o r n o d e ，t h et a s kd i s t r i b u t i o nw i l lf o l l o wt h ed i s t r i b u t i o no fp r e s s u r et r a n s m i s s i o nm o d e ， t h ea l g o r i t h mt oe n s u r et h a tt a s k sc a nb es e n tt oe v e r y w h e r eo ft h es y s t e m i nt h e s y s t e mt h e r ew i l lb em u l t i p l ea p p l i c a t i o n sc o m p e t ef o rt h ec o m p u t i n gr e s o u r c e s ， r e s o u r c e sc o m p e t i t i v ea l g o r i t h mi st os o l v et h i s p r o b l e m b o u n d a r yb r e a k i n g a l g o r i t h mi st or e l e a s er e s o u r c ew h i c hi sn ol o n g e rn e e df o ro n ea p p l i c a t i o n t os o l v e t h ed y n a m i co fg l o b a lc o m p u t i n ge n v i r o n m e n tw i t h o u tw a s t ec a u s e db yr e a l - t i m e m 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 si n t r o d u c e dt ot h i sd i s s e r t a t i o n t ov e r i f yt h ef u l l yd i s t r i b u t e dg r i dc o m p u t a t i o nm o d e la n di t sa l g o r i t h m sw e d e s i g n s e v e r a l e x p e r i m e n t a lp r o g r a m s o nn o m a n - g r i d t h en o m a n - g r i di s i i i a b s t r a c t d e v e l o p e db yj a v ap r o g r a m m i n gl a n g u a g e n o m a n - g r i ds y s t e mh a st w om a i nc h a r a c t e r i s t i c s ，t a s kl o a dd i s t r i b u t i o np a t t e r n s a n dt h es c a l a b i l i t yo fr e s o u r c e m a n a g e m e n t i n t h i sd i s s e r t a t i o nt h e s et o c h a r a c t e r i s t i c sa r ea n a l y z e da n da r ev e r i f l e db ye x p e r i m e n t a ld a t a k e y w o r d s ：c o m p u t a t i o n a l g r i dt a s kl o a dd i s t r i b u t i o n a u t o n o m y g r i d c o m p u t a t i o nm o d e l i v 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外：本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年 月日 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法。我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h u n 。 本人承诺；本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩； 提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 2 0 年月日 南开大学研究生学位论文作者信息 论文题目 姓名 学号 答辩日期年月 日 论文类别博士口学历硕士口硕士专业学位口高校教师口同等学力硕士口 院，系，所专业 联系电话e m a i l 通信地址( m g 编) ： 备注：是否批准为非公开论文 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 第一章引言 第一章引言 第一节网格的发展及其应用 计算机的强大计算能力和基于计算机网络的资源共享为人们的生活、生产 和科学研究等领域提供了极大的方便。随着人类发展，各个领域对计算能力和 资源共享的需求也越来越高。另一方面，计算机的普及使很多人拥有了较充裕 的数据处理能力，而连接这些计算机的网络通信能力的提高，使利用这些闲余 计算资源去完成高计算量的工作成为可能。管理这些网络上的海量闲余的计算 资源或者能力，并使之虚拟成为具有强大的计算能力的计算支持环境，为用户 提供计算服务，是网格产生的初衷。这不论是在降低计算成本，还是节约社会 资源上，都是一个有益的思路。网格的另一个早期目标是支持用户从自己的联 网终端上，直接、方便地访问虚拟计算环境，即“像使用电力资源一样从电力 网上获取资源 。于上世纪9 0 年代初，人们提出了网格的概念，这一阶段的网格 是指集合地理上分布的各种资源，满足用户提出的资源使用要求。此处的资源 包括设备、数据和计算能力。 网格至今已经发展了十余年，形成了很多研究成果，包括标准、协议、网 格应用项目、中间件和网格平台。网格初期从基于超级计算机的元计算模型发 展而来人们称这段时期的网格为第一代网格。第一代网格的代表是在9 5 年 s u p e r c o m p u t i n g 会议上展示的实验性项目i - w a y ( i n f o r m a t i o nw i d e a r e ay e a r ) i 。 i - w a y 之后网格的研究成为热点，从上世纪9 0 年代末开始，网格进入了第二代， 这期间出现了很多网格项目，如：g l o b u s l 2 1 、l e g i o n 3 1 、c o n d o r t 4 1 j g a p p l e s i 5 1 等 项目。g l o b u s 和l e g i o n 面向的是构建系统级的网格基础架构。c o n d o r 和a p p l e s 分别具有高吞吐率和高运算性能的调度算法。这些项目中最具代表性和应用范 围最广的是g l o b u s 项目，g l o b u s 工具包提供了一组网格中间件，开发者可以基于 其开发出具体的网格应用。 在很多国家上述网格项目已经被应用在生命科学、工程学、数据挖掘、物 理学等领域【6 】。当前的网格项目整合的计算资源所能提供的计算力还是远远不能 满足人们的计算需求。如果能够将i n t e m e t 上海量空闲计算资源加以利用则能够 满足人们对计算资源的需求。 第一章引言 当前网格系统的资源管理方法大多属于中心制的管理方法，随着系统内节 点数量的增加管理成本也会增长中心制下的管理节点就会形成瓶颈。如果想在 一个网格系统中控制并管理大量节点采用中心制的管理方法无法从根本上解决 瓶颈问题，必须走无中心管理的道鲥7 1 。 网格的发展和主要研究方向有计算网格、数据网格，此外还有其他一些研 究方向如协同工作、信息网格、知识网格、语义网格，本文中论述内容主要涉 及计算网格方向。 第二节当前网格继续发展的障碍 一个网格系统规模越大其集成的资源越多，网格也就能服务更多的用户和 更大规模的计算应用。随着人们的应用问题的扩大，其所需的计算量也在不断 提高，人们迫切需要能提供海量计算资源的网格系统。网格研究从上世纪9 0 年 代中期到现在的十几年中，网格系统的规模在逐渐扩大，但随着系统规模的扩 大有一些关键问题还没有好的解决方法所以限制了网格规模的进一步扩大，下 面对这些问题一一解释。 1 2 1 资源管理瓶颈 一个网格系统的节点数量可能从区区几个节点增长到海量节点( 极端情况 下，全球的计算设施都会加入网格系统) 。随着网格规模的增长潜在的问题就是 由于管理成本越来越高导致整体效率会降低。系统中具有海量资源时资源管理 成本将会大幅增加，若采用中心制全局统一的资源调度将使得资源管理中心的 负担过重。资源管理需要存储资源的基本信息和使用状态等信息，并且要结合 任务的要求调度资源以完成任务。当系统内有海量资源时，需要资源管理中心 有极高的吞吐率，这就导致资源调度管理中心必须具有极高性能。但是资源管 理中心的性能越高其制造成本和使用成本也会越高，而且资源管理中心的性能 也不能无限制提高，这就限制了中心制资源管理网格系统的规模不能无限扩大。 虽然当前有些方法( 如建立资源索引目录) 能够一定程度上减轻资源管理中心 的负担，但并不是从根本上解决了资源管理瓶颈问题。 2 第一章引言 1 2 2 数据传输瓶颈 当系统规模扩大时，其内部节点的平均距离也将越来越远，数据传输所需 平均时间也会增大。其结果导致用户设计应用时必须考虑到访问数据资源的延 迟问题。随着c p u 速度的变快和存储容量增加，这两项指标已经不是影响系统运 行效率的关键问题，影响效率的关键就是数据所在地和计算资源的距离。用户 提交的数据密集型应用需要并行处理海量数据，而用户提交的数据要从任务源 节点分割并分布到网格中的节点上，这将耗费大量时间，数据在远距离节点间 的移动将成为瓶颈峭】。从i n t e m e t 上的节点传输数据到本地的速度和从本地磁盘读 取数据速度的差别巨大，因此数据传输速度会很大程度上影响应用的完成时间。 网格为了达到更大的规模数据必须被分布在很多计算机上，并且计算任务需要 被安排在尽量离数据存放节点较近的地方以降低通信成本。 第三节本文的内容安排 当资源管理中心制的网格系统规模逐渐扩大时，其系统内部就会形成资源 管理瓶颈。为了提供更多的计算资源，必须继续扩大网格系统规模，就必须解 决资源管理的瓶颈问题。 无资源管理自协调网格计算模型【9 】( 以下简称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 的体系结构，一方面是 系统的总体组织结构，另一方面是节点的功能模型。在介绍了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 的主要算法包括：任务调度算法、资 源竞争算法、边界解除算法和有限任务复制算法，这些算法解决了任务负载分 布、资源竞争和动态性屏蔽的问题。第四章介绍了n o m a n g r i d 实现的系统结构， 并分别说明了每个子系统的实现方式。第五章用实验数据证明了n o m a n g r i d 的 两个典型特征：任务负载符合压力传递分布模式和资源管理成本不随系统规模 扩大而上升，并说明了具备这两种典型特征的网格系统的适合的应用环境。第 3 第一章引言 六章对本文的主要研究内容进行了总结并提出了下一步工作可能的研究方向。 4 第二章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 体系结构 一个设计合理的体系结构是系统具有各种优良特性的基础。n o m a n - g r i d 系 统体系结构可以从两个层面进行理解，即从全局观察的系统组织结构和从微观 观察的系统中每个节点的功能模型。本节将首先从全局介绍n o m a n g r i d 的组织 结构，然后再从每个节点的角度介绍节点功能模型。 2 1 1 全局组织结构 n o m a n - c n 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 组织的情况，无论那种情况n o m a n - g r i d 都只需简单的操作就能达到 目的。对于前者只需两个组织内有节点互相建立邻居节点关系，而对于后者只 要两个组织之间的邻居节点关系都断开即可。 在图2 1 中，有已经存在的n o m a n g r i d 系统，新的节点l 希望加入其中，在 获得了节点j 和k 的消息后，和二者建立了邻居关系，则节点l 成为新的节点，他 的邻居节点是j 和k ，与此同时，j 和k 在邻居节点表中增加一项l ，各项信息初始 化，图中用虚线表示新的邻居关系。 o 图2 1节点l 加入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 系统，有可能出现两b n o m a n g r i d 系统需要融合的情况：当一个小 5 第二章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 网格系统，构 造方式是一样的，只需要两个系统中的任意两个节点将对方设置为邻居，就将 两个n o m a n g r i d 合并成一个新的系统，而所有共享的计算资源可以为新的系统 内的所有节点服务。 ：一一兰苎氅鬯一一：一一! 竺氅譬一一： 图2 2 计算组织互连 图2 2 展示了两 f 、 n o m a n - g r i d 系统间的互联，节点b 和节点f 之间建立邻居关 系，产生了一个更大规模的n o m a n g r i d 系统。这种简单的结合方式适合系统的 规模扩大，不需要更多的修改系统结合带来的组织管理工作，消耗仅相当于一 个新的节点加入系统。 ：| 2 1 2 节点功能模型 n o m a n g r i d 中没有特殊地位和特殊功能的节点，所有节点都可以贡献和利 用计算资源，所有节点遵守相同的功能模型，如图2 3 。 6 第二章n o m a n g r i d 体系结构及特性 图2 3n o m a n - g r i d 节点功能模型 节点功能分为任务管理、信息管理、任务调度、本地资源管理、任务发送 五个模块。 这里需要先对邻居节点进行定义，图2 4 是一个包含了环、分枝、直线的典 型系统组织图。邻居节点的定义是：将整个网络拓扑看作无向图g ，贝i j g = a ，b ， c ，d ，e ，f ，1 3 ih ，i ，j ，k 。 图2 4 典型系统组织图 定义l ：在图2 4 中有连线的节点互为邻居节点。记n e i g h b o r ( v ) 为节点v 的邻 居节点集合，n n e r g h b o r ( v ) 为邻居节点个数。如n e i g h b o “d ) = 八e ，f ，g ， 7 第二章n o m a n g r i d 体系结构及特性 n n e i g h b o r ( d ) = 4 。 下面对节点功能模型中每个模块的具体功能进行解释： 任务管理模块：接受本地节点提交的任务和来自邻居节点的任务，并组织 成任务队列。接受任务结果，若此任务是本地任务则将相应任务从任务队列中 移除，若是非本地任务则将结果返回任务源节点； 信息管理模块：维护邻居节点表，保存与本地节点相邻节点的基本信息、 能力信息和控制信息； 任务调度模块：根据任务调度算法和邻居节点表的信息将任务调度到某个 邻居节点处理或本地运行，并在调度过程中更新邻居节点表的信息； 本地资源管理模块：监视本地资源运行状况，并根据监测结果控制调度到 本地节点运行的任务的创建、挂起、运行和中止，一旦资源的使用超过资源提 供者设置的条件，则将正在运行的任务挂起，反之则唤醒挂起的任务，使之继 续运行。 任务发送模块：在动态的网络环境下将任务发送到指定的邻居节点。 任务队列是任务管理模块的输出又是任务调度模块的输入，任务队列遵守 先入先出原则。若在系统运行期间本地节点提交任务( 即本地节点成为任务源 节点) ，则任务管理模块不再将任何邻居节点的任务加进任务队列，这体现了本 地任务优先运行的原则。任务调度模块对于任务队列的任务会有两种处理：转 发其他邻居节点或本地运行。若任务来自邻居节点，无论进行了哪种处理，都 会在处理后将该任务从任务队列中删除；若任务来自本地节点，则不删除该任 务，要等到从本地或其它节点处收到该任务的运行结果才删除该任务。 每个节点的信息管理模块管理了n o m a n g r i d 中局部的资源信息，管理范围 是与本地节点相邻的节点，管理的信息包括邻居节点的相对能力信息和资源竞 争控制信息。 在n o m a n g r i d 中邻居节点能力信息代表的是一个节点的计算资源当前是否 可用。能力信息只用简单的0 、1 代表节点当前是否能够提供计算资源，而对于 一个节点的计算能力的多少并不给予衡量。在网格系统环境下节点能力相差巨 大，如果节点计算能力建立统一衡量机制，对计算资源的统计和管理将耗费大 量资源，而且建立了衡量机制后还需要对计算资源的变化及时反映，若要对网 络资源采取实时监控的办法将会浪费大量资源造成效率降低。基于以上原因， n o m a n - g l i d 中将节点计算资源抽象成为计算能力，不量化计算能力的大小和动 8 第二章n o m a n g r i d 体系结构及特性 态性，使用简单的概念衡量计算资源：有计算能力和无计算能力。当一个节点 正在运行任务时此节点的计算能力信息为o ，否则记其计算能力为1 。此处要说 明一个节点的某个邻居节点的相对能力信息不只是代表那个邻居节点本地的能 力信息而是代表此邻居节点后所有节点的是否还有可用计算资源，下面是本地 能力和邻居节点相对能力的定义。 定义2 ( 本地能力) ：如果节点v 正在为网格运行任务，则本地无能力，否则本 地有能力，记l ( v ，v ) 为节点v 的本地能力。 定义3 ( 邻居节点相对能力) ：记r ( u ，v ) 为节点u 的邻居节点v 相对于节点u 的相对能力。 资源竞争控制信息记录了系统中存在多个应用时每个计算资源所属的应用 服务的相关信息。在一般的网格系统中提出了一些集中式的资源分配方法，如 g l o b u s 的监控和发现服务( m d s ) 、c o n d o r 的m a c t h m a k e r 。在n o m a n - g r i d 中没有 一个中心的负责资源管理及分配的节点，在没有资源全局知识的条件下合理分 配资源是一个难题，针对这一问题n o m a n g r i d 提出了资源竞争算法。系统中存 在多个任务源节点时，相邻较近的应用可能会争用计算资源，此时，遵循资源 竞争算法对争用的计算资源进行分配。采用的资源竞争算法需要简单，而且要 保证每个应用尽可能多获取计算资源，所以需要记录本地节点的邻居节点的资 源竞争控制信息( 即记录节点是否被其它节点占用) 。资源竞争控制信息c ， v ) 用来标记邻居节点v 在资源竞争中相对于节点u 的状态。控制信息包括三种状 态：b o u n d a r y 、d o m i n a t e 和n o r m a l 。 b o u n d a r y 该节点属于另一个资源范围，本地节点不能向其调度任务， 称该节点为本地节点的边界节点。 d o m i n a t e ：本地节点优先为来自于该节点的任务服务，称该节点为本地 节点的控制节点。 n o r m a l ：如果不是上面两种状态，就标记为n o r m a l 。 当多个应用争用同一个计算资源时，遵循先来先服务( f i r s t - c o m e f i r s t s e r v e d ，f c f s ) 策略，即先向本地节点发出任务的节点会成为本地节点的控 制节点。当一个节点被占用后，其就全部计算资源就被控制节点占用，不在接 收其它应用的任务，此节点相对于其它应用来说就是一个边界节点。 在初始情况下所有的邻居节点都是n o r m a l 状态，当接收到邻居节点发送来 任务时，本地节点会查看自身是否已经有控制节点，若没有则将该邻居节点设 9 第二章n o m a n g r i d 体系结构及特性 置为本地的控制节点，若有控制节点则还要判断此任务是否来自控制节点，若 是来自控制节点则接收并运行任务，否则拒绝该任务并标记该邻居节点状态为 边界节点。 信息管理模块所管理的信息都记录在邻居节点表中，在此表中记录了本地 节点所有邻居节点的能力信息和资源竞争控制信息。在n o m a n g r i d 中将本地节 点也抽象成一个邻居节点存储在邻居节点表的第一项，这样能够保证在任务调 度时优先为本地节点分配任务。邻居节点表存储四项信息：编号、i p 地址、相对 能力信息、资源竞争控制信息。编号代表一个节点在n o m a n g r i d 中的唯一标示， 规定第一条记录的节点是本地节点，由于任务调度时是顺序扫描邻居节点表进 行任务分配，所以编号较小的节点接收任务的概率较大。i p 地址记录了相应编号 邻居节点的i p 地址，以备任务发送时使用。表2 1 是邻居节点表的简单示例。 表2 1 邻居节点表 节点i d相对能力资源竞争控制信息 4od o m i n a t e 5on o r m a l 60n o r m a l 1 61n o r m a l 1 90 b o u n d a r y 在表2 1 中本地节点即为任务源节点，当前时刻本地节点正在运行任务，编 号5 、6 的节点已经运行本地节点发送过去的任务，但是本地节点并不能从5 、6 号节点的n o r m a l 信息中得知其已经被本地节点控制，也就是说本地节点无需知 道哪些节点正在为其服务，只需得到哪些节点当前可用，这样既保证信息的全 面有效又能节省通信量。1 6 号节点的相对能力是1 ，说明可以将任务调度到此节 点运行。1 9 号节点的资源竞争控制信息是b o u n d a r y 说明此节点已为其它应用运算 任务。为了防止“乒乓效应”，当邻居节点的资源竞争控制信息是d o m i n a t e 时， 必须将其相对能力设置为0 ，这样能够保证不会在任务调度时将任务回调给本地 节点的控制节点。邻居节点表的信息改变会在下面三种情况下发生：任务调度 给某邻居节点、任务源节点接收到任务结果、新邻居节点加入。以上三种情况 只有在系统有应用运行时才发生，这样能保证系统在没有应用时不会为维护邻 居节点信息产生大量无用的网络通信从而减少维护系统的开销。 l o 第二章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 基于无资源管理自协调网格计算模型，采用此模型的网格系统 由多个计算资源( 本文称单个计算资源为一个节点) 互连而成，逻辑上相连的节点 互称为邻居节点。网格系统环境的特点有：海量节点、节点差异大、网络动态 性强，针对这些特点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 的用户无需购买大型计算 机或集群即可获得大量计算资源。在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 采用自组织方式构成，没有统一的目录服务。当有节点希望加入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 系统。 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 的节点都要贡献自己的空闲计算资源，还可以提交应 用到系统中利用计算资源。提交任务的节点称为任务源节点，在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 中的节点根据任务调度算法将任务调度到符合条件的邻居节点 运行。任务是由任务源节点向四周传递出去的，在全系统中任务负载符合压力 传递分布模式1 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 体系结构及特性 部任务。网格系统一般包含了多种异构资源，而且这些资源大多分布在全球各 地的不同组织机构中。加入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 必须解决跨平台运行问题，这里所说跨平台是指在不同操作系统甚 至硬件结构下运行n o m a n - g r i d 。所以在选择开发技术时n o m a n - g r i d 采用了j a v a 平台。j a v a 是j a v a 程序设计语言和j a v a 平台的总称。在硬件或操作系统平台上安 装一个j a v a 平台之后，j a v a 应用程序就可运行。j a v a 平台已经支持大多数操作系 统，具体列表可以在s u nm i c r o s y s t e m s 公司的技术支持网站查看。这样j a v a 程序 可以只编译一次，就可以在各种系统环境中运行。 传统的动态性屏蔽策略有心跳检测和检查点，这两种方法在目前的高可靠 性集群中应用很广泛。心跳检测是指每隔一段时间都要向外广播自身的状态。 在进行心跳检测时，心跳检测的时间和时间间隔是关键问题，如果心跳检测的 太频繁，将会影响系统的正常运行，占用系统资源；如果间隔时间太长，则检 测就比较迟钝，影响检测的及时性。检查点又称为主动检测，就是每隔一段时 间周期，就会对被检测对象进行一次检测，如果在给定的时间内，被检测对象 没有响应，则认为检测对象失效。与心跳检测相同，检测点也受到检测周期的 影响，如果检测周期太短，虽然能够及时发现故障，但是给系统造成很大的开 销；如果检测周期太长，则无法及时的发现故障。对于网格系统环境下网络异 常和节点的频繁加入、退出等事件，n o m a n g r i d 采用了有限任务复制算法以达 到动态性屏蔽的目的。有限任务复制算法相对于传统的心跳检测和检查点方法 降低了网络通信量并节省网络带宽和系统资源，在第三章的第四节将讨论有限 任务复制算法。 综上，n o m a n g r i d 是具有自组织系统、无资源管理、多点任务注入、任务 负载服从压力传递分布模式、异构性屏蔽和动态性屏蔽等多种特性的网格系统。 其中无资源管理和任务负载服从压力传递分布模式两个特性使得n o m a n - c j r i d 适 合应用在节点数量庞大的系统环境下。在本文的第五章会对n o m a n g r i d 的任务 负载服从压力传递分布模式和无资源管理模型的扩展性两个主要特性给予实 验，并根据实验数据分析n o m a n - g r i d 的扩展性。 1 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 节点间的组织结构采用自组织的方式生成， 在系统中并没有特殊地为的节点，没有一个节点具有全局资源索引。每个节点 在系统内的地位是相同的功能也是相同的，所有节点具有相同的功能模型。节 点功能分为任务管理、信息管理、任务调度、本地资源管理、任务发送五个模 块。在本章对五个功能模块进行了详细介绍。合理的体系结构导致n o m a n g r i d 系统具有很多优良特性，包括：自组织系统、无资源管理模型、多点任务注入、 任务负载服从压力传递分布模式、异构性屏蔽和动态性屏蔽。其中任务负载符 合压力传递分布模式和无资源管理模型两个特性有利于网格系统具有更高的扩 展性。本文的第五章将针对这两个特性进行两组实验，并根据实验数据分析 n o m a n g r i d 的扩展性。 1 3 第三章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 需要应用在动态性强而且节点数量庞大的环境下，为了正确并 高效的完成用户提交的应用n o m a n - g r i d 提出了一系列算法，包括：任务调度算 法、资源竞争算法、边界解除算法和有限任务复制算法。这些算法从任务分配、 资源划分和动态性屏蔽等方面保证了n o m a n - g r i d f l 皂够在动态性强而且节点数量 庞大的环境下高效的运行。本章将对上述算法进行详细介绍。 第一节任务调度算法 n o m a n g r i d 采用了完全分布式的任务调度算法，系统中的每个节点在没有 全局知识的情况下能够将任务发送到相邻的节点，任务分配会遵循压力传递分 布模式，算法保证任务可以传达到系统的所有节点。在系统中的所有节点处理 能力相差不大的情况下，任务的压力传递分布模式会使得任务源节点完成的任 务数最多，而邻居节点会随着与任务源节点的距离增加完成的任务数逐渐减少。 资源调度过程实质上就是根据信息管理模块中邻居节点表的相对能力信息。， 和资源竞争控制信息进行合理的任务调度的过程。通过任务调度模块、任务管 理模块、信息管理模块的合作才能完成任务调度功能，任务调度模块从任务管 理模块取出待调度任务，从信息管理模块获知哪些邻居节点当前有能力，然后 将任务发送到该邻居节点，并更新邻居节点表。在任务调度时需要遵守如下几 条原则： 原则1 ：每个节点同时只能运行一个任务； 原贝l j 2 ：任务源节点提交的任务优先在本地运行； 原n 3 ：节点向有相对计算能力的邻居节点依次发送任务； 原贝l j 4 ：出现资源竞争时，遵循给定的资源竞争算法调度任务。 为了屏蔽异构型和动态性而规定了原则l ，n o m a n g r i d 应用的环境无法时刻 监测所有节点中任务的运行情况，所以规定每个节点在同时只能运行一个任务。 对于有强大计算资源的节点，相对普通节点能够提前完成任务，在这种方法下 也不会浪费其计算资源，因为完成任务后此节点会主动表达其已经有能力了， 在调度任务时会再次为其分配任务。 1 4 第三章n o m a n g r i d 算法设计 原则2 保证了任务尽可能在本地运行以减少通信量。这一条保证了应用的任 务每次调度都先检查本地节点的能力信息，能够尽量减少向外发送任务的概率， 完全符合任务的压力传递分布模型。 原则3 保证任务只发送到有相对