（计算机科学与技术专业论文）基于多经济智能主体的计算网格资源管理.pdf

国防科学技术大学研究生院学位论文 摘要 计算网格是当前并行和分布处理技术的一个发展方向。资源管理是计算网 格的关键技术之一。它对于开发计算网格系统具有重大的理论意义和实用价值。 因为计算网格中的资源是分布的、自治的、异构的、动态的和需要协调一 致的，所以计算网格资源管理是一个具有挑战性的问题。本文深入地分析了计 算网格资源管理的研究现状，指出了当前各种实际使用的资源管理技术用于计 算网格系统的不足之处。在此基础上： 1 本文讨论了使用经济学方法和多智能主体技术实施计算网格资源管理的合理 性，进而首创计算网格资源管理的g r a m m e a ( g rj dr e s o u r c ea 1 l o c a t i o na n d m a n a g e m e n tb a s e do nm u l t i e c o n o m i c a g e n t s ) 体系结构。与已有的计算网格 资源管理体系结构相比，g r a m m e a 体系结构具有坚实的经济理论基础，可扩展 性好，可以提供服务质量保证，具有自适应性。 2 本文为g r a m m e a 体系结构建立了经济学模型。本文定义了资源和服务分配的 均衡状态，证明了均衡状态的最优性、公平性和存在性三个定理。这些定理作 为g r a 删e a 体系结构的理论基础，为使用g r a m m e a 实施有效和公平的计算网格 资源管理提供了理论保证。 3 本文设计了g r a m m e a 体系结构中的三个交易协议：资源交易协议、服务交易 协议和信息交易协议。这三个交易协议是经济智能主体之间发生联系和经济智 能主体与外部环境发生联系的纽带。每个交易协议包括交易协议语言和交易协 议过程两部分：前者规定了交易语句的语法规则；后者规定了交易语句的语用 规则。 4 本文为g r a e a 提出了两组算法。一组是资源和服务分配算法，它们通过使 用迭代、搜寻、最优化等技术实现了资源和服务分配遥近经济学模型中的均衡 状态。另一组是服务质量保证算法，它们通过面向负荷的准入控制和任务投放、 基于虚时钟的任务组调度等技术提供了一定程度的服务质量保证。 通过以上工作，本文认为：基于多经济智能主体的计算网格资源管理 ( g r a m m e a ) 体系结构以均衡状态的最优性、公平性和存在性为理论依据，通过 三个市场的交易协议实现经济智能主体之间以及经济智能主体与外部环境的交 互，通过一系列关键算法实现经济智能主体内部的规划和决策，为解决计算网 格资源管理问题提供了一种有效的技术途径。 国防科学技术大学研究生院学位论文 i i 国防科学技术大学研究生院学位论文 a b s t r a c t c o m p u t a t i o n a lg r i d i sad e v e l o p m e n td i r e c t i o no fd i s t rj b u t e da n d d a r a l l e lp r o c e s s i n gt e c h n o l o g y r e s o u r c em a n a g e m e n ti s o n eo ft h ek e y t e c h n i q u e s o fc o m p u t a t i o n a lg r i d i t h a sm a g n i t u d et h e o r e t i c a l s i g n i f i c a n c ea n da p p l t e dv a l u et od e v e l o pc o m p u t a t i o n a l g r i d - r e s o u r c em a n a g e m e n to fc o m p u t a t i o n a lg i r di sac h a l l e n g i n gq u e s t j o l 3 b e c a u s et h a tr e s o u r c ei nc o m p u t a t i o n a lg r i di sd i s t r i b u t e d ，i sa u t o n o m o u s ， ish e t e r o g e n e o u s ，i sd y n a m i c ，a n di sn e e do fc o o r d i n a t i o n t h i sp a p e rg o e s i n t ot h er e s e a r c h i n gs t a t u so f h i sq u e s t i o na n dp o i n t so u tm e a g e r n e s s o fa p p l y i n gv a r i o u sr e s o u r c em a n a g e m e n tt e c h n i q u e s i nu s i n gn o wi n t o c 0 1 i 】p u t a t i o n a lg r i d f i r s t l y ，h i st h e s i s d i s c u s s e st h er a t i o n a l i t yo fu s i n ge c o n o m i c m e t h o da n da g e n tt e c h n o l o g yt om a n a g e rg r i dr e s o u r c e a n dt h e nl n lt i a t e s g r i dr e s o u r c ea l l o c a t i o na n dm a n a g e m e n ta r c h i t e c t u r eb a s e d0 nm u l t i e c o n o m i c - a g e n t s c o m p a r e dw i t ho t h e rw o r k s ，g r a i v l m e an o to n l yh a se c o n o m l c b a s i ci nt h e o r y ，b u ta l s oi ss c a l a b l ea n da d a p t i v ei np r a c t i c e a tt h e s a m et i m e ，i ts u p p o r t sq u a l i t yo fs e r v i c ei nac e r t a i ne x t e n t s e c o n d l y ，t h i st h e s i sf o u n d st h ee c o n o m i cm o d e lo fg r a m m e a i td e f i n e s t h ee q u i l i b r i u ms t a t e o f r e s o u r c ea l l o c a t i o na n dt h a to fs e r v i c e a l l o c a t i o n ，a n dp r o v e st h et h e o r e m sa b o u to p t i m i z a t i o n 、 f a i r n e s sa n d e x i s t e n c eo ft h ee q u i l i b r i u ms t a t e ，w h i c ha r et h et h e o r e t i c a lb a s i co f g r a m m e aa r c h i t e c t u r ea n da s s u r et h a tg r a m e ac a nm a n a g e rg r i dr e s o u r c e f a i r l y a n de f f i c i e n t l y t h i r d l y ，t h ist h e s i sc o n s t r u c t st h r e et r a d i n gp r o t o c o l s ，w h i c ha r e t h er e s o u r c et r a d i n gp r o t o c o l 、t h es e r v i c et r a d i n gp r o t o c o l a n dt h e i n f o r m a t i o nt r a d i n gp r o t o c 0 1 t h e s et r a d i n gp r o t o c o l sd e f i n et h ei n t e r a c t r u l e so fe c o n o m i ca g e n t s e v e r yt r a d i n gp r o t o c o lc o n s i t u t e st w op a r t s ： o d ei st h et r a d i n gp r o t o c o ll a n g u a g ea n dt h ee t h e ri st h et r a d i n gp r o t o c o l p r o c e s s t h ef o r m e rs p e c i f i e st h eg r a m m a t i c a lr u l e so ft r a d i n gs e n t e n c e ， a n dt h el a t e rs p e c i f i e st h ep r a g m a t i e sr u l e so ft r a d i n gs e n t e n c e a tl a s t ，t h i st h e s i sp u t sf o r w a r dt w og r o u p so fa l g o r i t h m s t h ef i r s t g r o u po fa l g o r i t h m si sa b o u tr e s o u r c ea n ds e r v 5c ea l l o c a t i o n ，w h i c hm a k e s i i i 国防科学技术大学研究生院学位论文 a l l o c a t i o ns c h e m ec l o s e dt ot h ee q u i l i b r i u ms t a t ei nt h ee c o n o m i cm o d e l t h es e c o n dg r o u po fa l g o r i t h m si sa b l et og u a r a n t e eq u a l i t yo fs e r v i c e i nac e r t a i ne x t e n tb yu s i n gw o r k l o a d - o r i e n t e da d m i s s i o nc o n t r o l 、 w o r k l o a d - o r i e n t e dt a s kl o a d i n g 、t a s kg r o u ps c h e d u l i n gb a s e do nv i r t u a l c l o c ka n ds oo n i nc o n c l u s i o n ，h a i l e do ne c o n o m i cm o d e l sg r a m m e aw i t ht h r e et r a dm g p r o t o c o l sa n dt w og r o u p so fa l g o r i t h m sp r o v i d e sa ne f f e c t i v ea p p r o a c ht o m a n a g e l g r i dr e s o u r c e k e y w o r d s ：c o m p u t a t i o n a lg r i d ，r e s o u r c em a n a g e m e n t ，a g e n t m o d e l ， e q u i l i b r i u m ，p a r e t oo p t i m a l ，q u a l i t y e 0 0 n f ) ! n l t o is e r v i c e 国防科学技术火学研究生院学位论文 第一章绪论 1 1 本文的研究对象、目标和意义 从终端主机模式到客户机服务器模式，从基于l a n 的文件服务器到基于 i n t e r n e t 的w e b 应用，技术的进步一直在不断地改变着计算机系统的使用方式。 近年来，i n t e r n e t 技术、高性能计算机技术和高速网络技术都得到了长足的发 展。这些技术使得把地理分布的各种异构计算资源作为一个统一的计算系统来 使用成为了可能。这里的异构计算资源可以是各种各样的计算机、外设、数据 源、科学仪器，例如超级计算机、高性能工作站、磁盘阵列、数据库、电子显 微镜、粒子加速器、遥感仪等等。由它们构成的统一的计算系统被称为计算网 格( 简称网格) ，这种计算系统的使用方式叫做网格计算。本文的第二章会对计 算网格的一般原理和关键技术给以简要介绍。 计算网格的思想可以上溯到八十年代末期美国对于吉比特高速网络的研究 项目，c a s a 1 ( 一个吉比特网路测试床项目) 的研究人员首先提出了元计算和 元计算机的概念。他们认为元计算就是网路环境下用户透明的计算资源使用方 式，元计算机就是网络虚拟超级计算机。在1 9 9 7 年1 0 月美国国家基金( n s f ) 宣布了面向2 1 世纪的“计算科学联盟”重大基金项目g r i d 。该项目计划以美 国全国范围内的网格计算为目标，历时五年时间，联合六十余所大学、科研机 构和公司，集中力量在全国范围内建立一个高级计算的基础底层结构，以实现 大区域的高性能并行与分布式计算，在大范围内由高速网络把分布在各地的计 算资源和数据资源连接在一起，达到t e r a f l o p s 规模的计算能力，形成新的科 学计算和信息应用结构，并在上面集成各种系统和开展各种应用研究，解决宇 宙学、生物化学工程、流体力学、材料、神经等重大科学应用领域的计算问题。 经过四五年的艰辛探索，计算网格的研究已经出现了一批阶段性的工作成 果，如g l o b u s 2 元计算工具集合。当前，计算网格的研究工作已经大大超出 了g r i d 计划最初的设想。计算网格的目标已经不仅限于为解决广域科学计算提 供充足的计算能力。我们认为：计算网格就是通过计算资源在广域跨组织范围 下的合理配置和高效使用解决目前的分布和并行计算系统解决不了、解决不好 或是虽能解决但成本太高的高性能计算问题；计算网格的技术手段是组织和联 合地理分布的各种异构的计算系统、数据库和科学仪器使之构成一个统一的虚 拟计算环境，计算网格的本质是一种信息处理基础设施。 本文的研究对象就是计算网格的资源管理问题。具体而言，又可以进一步 将计算网格的资源管理问题分为两个子问题： 第1 页 国防科学技术大学研究生院学位论文 一一是计算网格的资源分配问题， 源分配的公平； 二是计算网格的资源使用问题， 务质量的保证。 研究目标是实现资源分配的效率和资 研究目标是实现资源使用的高效和服 资源管理是计算网格最重要的基本服务之一。从微观角度而言，资源管理 体系结构和应用调度机制会对计算网格应用执行的效果产生重要影响。从宏观 角度而言，资源管理问题的有效全面解决是计算网格走向实际运用的一个关键 因素。因此，对于计算网格资源管理问题的研究，对当前和未来计算网格的发 展和应用。都将具有重要的理论意义和巨大的实践价值。 1 2 当前计算网格资源管理研究的不足之处 目前对于计算网格资源管理的研究可以分为两类：一类是理论上的计算网 格资源管理体系结构和模型研究，以网格论坛调度和资源管理工作组的“稻草 人”系列提议为代表；另一类是实践上的计算网格资源管理软件包的设计实现， 以g l o b u s 元计算工具集合的g r a m 库程序为代表。本文的第三章会对这些研究 工作给以简要介绍。 对于已有的计算网格资源管理研究工作的不足之处以及这些不足对应的计 算网格资源管理需要进一步解决的具体课题，可总结如下： 一是资源管理没有服务质量保证机制。固然，已有的资源管理技术都追求 高的服务质量和高的资源利用率。例如所有的调度技术都想方设法降低作业的 平均响应时间，但是系统并不能确保作业的平均响应事件能够低到某个具体的 程度。至于对于个别的作业，其响应时间就更加不可预测了。换言之，这些已 有的资源管理技术只能够向用户提供尽力而为的服务。这种没有服务质量保证 机制的计算服务对于计算网格常常是不可接受的，其原因有三。从用户的角度 而言，许多用户对于计算网格应用的运行有明确的服务质量要求。例如视频点 播、股市信息发布、虚拟现实等应用通常有实时的要求，至少也有软实时的要 求；科学计算类计算网格应用通常有完成时限要求。从系统的角度而言，计算 网格应用常需要多个自治的计算资源同时提供服务，而这些计算资源的服务质 量的不匹配会造成极大的资源浪费。从记帐的角度而言，服务质量保证机制也 为公平地分担计算资源的运行费用提供了基本依据。由此可见，实现一定的服 务质量保证机制是计算网格资源管理技术需要解决的第一个重要课题。 二是资源管理没有考虑用户需求的异构性这一重要因素。由于已有的资源 管理技术在进行资源分配时没有考虑这种异构性，常常会导致资源分配的无效 和不公。无效指的是资源分配的结果不是经济的，即没有把资源分配给最需要 第2 页 国防科学技术大学研究生院学位论文 资源的、会产生最大效益的计算网格应用。不公指的是资源分配的结果是不公 平的，一个常见的现象是特定的资源分配方法总是优待和照顾特定负载特性的 应用。固然，通过赋予优先级的方法，通过轮询的方法，通过在资源分配中考 虑负载特性( 如并行应用的平均并行度) 的方法，这些资源管理技术也在一定 程度上试图接近效率和公平的目标；但是对于计算网格的资源管理而言，这些 是远远不够的。由此可见，定义公平和效率的概念，进而通过一定技术达到资 源分配的效率和公平，是计算网格资源管理技术需要解决的第二个重要课题。 三是资源管理以用户作业为基本对象。换言之，已有的资源管理技术都是 非层次的技术。与非层次的技术随之而来的问题就是系统运行的开销大、系统 的可扩展性差。常常是资源管理者需要为每一个作业要保存一份调度信息，在 进行资源管理和实施调度时又必须处理许多份这样的调度信息，这势必导致资 源管理的开销大。而资源管理的开销越大，该资源管理技术的可扩展性也就越 差。而计算网格恰恰是广域的、大规模的，因此对资源管理技术的可扩展性要 求也就高。因此，如何降低资源管理的代价，改善系统的可扩展性，是计算网 格资源管理技术需要解决的第三个重要课题。 四是没有对多资源联合分配提供支持或者支持很弱。如上一节所述，计算 网格的资源分配是通过分布的自主决策实现的。已有的资源管理技术没有很好 地解决如何在这些分布自主决策之间实现协调一致的问题。例如某个计算网格 应用需要使用一个计算资源和一个通信资源，那么在这些资源管理技术中还没 有哪种机制能够使得确保分布自主的资源管理决策的结果是两个资源向应用提 供相互匹配的服务质量。由此可见，提供一种简单有效的协调机制，支持多资 源的联合分配，并实现协调一致，是计算网格资源管理技术需要解决的第四个 重要课题。 五是无法适应计算网格资源供需的动态变化。已有的资源管理技术在考虑 负载变化的同时很少甚至几乎不考虑资源能力的变化，而计算网格恰好不仅存 在而且经常发生资源能力变化的情况。实现对于计算网格资源供需变化的自适 应，在线动态调整资源管理策略是计算网格资源管理技术需要解决的第五个重 要课题。 以上这些不足之处及其对应的需要进一步解决的具体课题正是本文工作的 出发点和突破口。 1 3 本文的解决方案和主要创新点 根据当前计算网格资源管理相关研究的长处和不足，本文提出的解决方案 是使用基于多经济智能主体的计算网格资源管理技术途径，其基本思想是： 第3 页 国防科学技术大学研究生院学位论文 使用智能主体技术作为计算网格资源管理逻辑抽象和物理实现的工 具。具体而言就是：将计算网格中的资源、作业、任务等实体抽象为 智能主体，进而将计算网格看成一个由多类经济智能主体构成的多智 能主体系统，从而在实现中使用现成的智能主体语言、环境和工具。 使用模糊聚类算法对组成计算网格应用的任务进行分类，即将负载特 性相近的任务归并为一类。在此基础上分层实施资源管理高层资源 管理的对象是任务类别，低层资源管理的对象是同一任务类别的若干 任务。这样做的优点有两个：一是资源的分配开销小、可扩展性好； 二是资源的使用规则，便于支持一定程度的服务质量确保。 在任务聚类的基础之上通过使用准入控制技术和多级调度技术实现在 一定程度的服务质量确保。具体而言：任务的准入控制使用面向负荷 的早期随机检测算法；任务的高调使用面向负荷的任务投放算法；任 务的中调使用基于虚时钟的任务组调度算法；任务的低调由各个本地 资源管理器负责。由于同一任务类别的任务负载特性相近，所以上述 方法可以很好地提供服务质量的支持。 根据经济学原理，严格地定义计算网格资源分配的效率和公平的概念。 效率的定义以经济学中的社会福利函数为理论基础，公平的定义以经 济学中的帕累托优化和平等为理论基础。与此同时，通过在资源分配 中引入基于分布自主决策的市场竞争方法，尽可能逼近最有效率同时 又最公平的计算网格资源和服务分配的均衡状态。 通过价格机制实现协调的多资源联合分配和资源管理对于资源供需变 化的自适应。对协调的多资源联合分配而言就是：当一类任务的执行 需要使用多个或者多类资源时必然要考虑在这些资源之间取得性能价 格的平衡和匹配：与此同时，当一个应用由多个任务或者多类任务组 成时也必然要考虑在投入这些任务的资金和获得的服务质量之间的平 衡和匹配。对自动适应资源供需变化而言就是：资源供需状况变化导 致资源价格变化，资源价格变化导致资源的分配结果和使用方式变化， 资源的分配结果和使用方式变化导致新的均衡状态。 本文的主要创新之处有： 1 - 本文在分析计算网格资源管理的特点和现有资源管理技术应用于计算网格 环境的不足的基础之上，讨论了使用经济学方法和多智能主体技术实施计 算网格资源管理的合理性，进而首创计算网格资源管理的g r a m m e a 体系结 构。与已有的计算网格资源管理体系结构相比，g r a m m e a 体系结构具有坚 实的经济理论基础、可扩展性好、可以提供服务质量保证、具有自适应性。 2 本文为g r a m m e a 体系结构建立了经济学模型。本文定义了资源和服务分配 的均衡状态，证明了均衡状态的最优性、公平性和存在性三个定理。这些 第4 页 国防科学技术大学研究生院学位论文 定理作为g r a m m e a 体系结构的理论基础，为使用g r a m m e a 实施有效和公平 的计算网格资源管理提供了理论保证。 3 本文设计了g r a m m e a 中的三个交易协议。这三个交易协议是经济智能主体 之间发生联系和经济智能主体与外部环境发生联系的纽带。每个交易协议 包括交易协议语言和交易协议过程两部分：前者规定了交易语句的语法规 则；后者规定了交易语句的语用规则。 4 本文为g r a m m e a 提出了两组算法。一组是资源和服务分配算法，它们通过 使用迭代、搜寻、最优化等技术实现了资源和服务分配逼近经济学模型中 的均衡状态。另一组是服务质量保证算法，它们通过面向负荷的准入控制 和任务投放、基于虚时钟的任务组调度等技术实现了定程度的服务质量 保证。 1 4 论文结构 本文共分九章，各章安排如下： 第一章绪论 第二章研究背景 第三章相关研究 第四章g r a m m e a 体系结构 第五章g r a m m e a 中的经济学模型 第六章g r a 删卧中的交易协议 第七章g r a m m e a 中的关键算法 第八章模拟实验 第九章结束语 各章之间的联系如图1 1 所示。 第5 页 国防科学技术大学研究生院学位论文 图1 1 论文各章的联系 第6 页 国防科学技术大学研究生院学位论文 第二章研究背景 2 1 并行和分布计算的发展趋势 2 1 _ 1 技术迸步 一方面微处理器已经由3 2 位跃进至6 4 位，主频已经超过1 g h z ，而且仍在 遵循摩尔定律飞速发展，桌面机、工作站、服务器等都具有相当高的计算性能； 另一方面网络通信技术和光纤技术迅猛发展，建立高速和高通信质量的网络已 势在必行；特别是i n t e r n e t 的商业化宣布了以网络为中心的信息时代已经到 来。在未来几年我们可以看到高速网络的广泛建立，例如i n t e r n e t 2 ，美国d r e n 网、n s f 的v b n s 网络等都是以高速为主要目标。以美国n s f 的v b n s 网络为例， 2 0 0 2 年广域网的带宽将会达到3 8 4 g b 秒。一旦如此高速的网络建成，人们便 能够快速访问远程计算资源，从而更加方便地通讯和交互。 2 1 2 高性能需求应用的增加 技术的进步和人类需求的发展推动了许多应用要求得到高性能计算资源的 支持，例如在核模拟与仿真、经济模型的构造、全球天气预报、医学、生物工 程学、宇宙学等都需要高性能计算的支持。有些应用不仅希望能够得到m p p 技 术的支持，还要求能在桌面机上访问到远程多种类别和功能的高性能计算资源， 并能够操纵计算过程；有些应用需要的计算能力远远超出了本组织能够提供的 计算能力；还有些应用必须访问远程的数据资源。凡此种种，都需要新的计算 基础设施提供支持。 2 1 3 空闲资源的有待利用 据统计网络上的大量高性能p c 、工作站和服务器的资源的利用率不超过3 0 ，剩下的7 0 空闲处理机时间未得到充分利用。即使是美国能源部的超级计 算机的利用率也只是在3 0 3 07 0 之间。资源的闲置和稀缺形成鲜明对比。这些 闲置的计算资源应当采用各种技术加以利用。应当注意的是，不仅仅是硬件资 源需要充分利用，大量的软件资源和信息资源也应当被共享而提高利用率。 2 1 4 计算结果的大范围共享 大量的计算结果和信息数据都存在大范围、异地共享的需求，这是一些大 型科学应用的要求，也是大型复杂的合作计算的要求。重要的是能够使各类研 究学者能够跨地域的相互交流，访问异地仪器设备、共享数据和计算资源，在 所处地域不同的条件下合作进行科学研究，共同解决科学问题。 2 1 5 解决问题的新技术和新工具 科学计算已经成为人们解决科学的重要手段，可视化技术、虚拟虚实技术、 第7 页 国防科学技术大学研究生院学位论文 计算机仿真模拟等都为解决科学问题提供了新的、良好的方法，而这些都需要 能够更易、更快地访问各种计算资源和共享数据。 正是以上各个方面的因素使得并行与分布计算技术朝着基丁高速网络的大 区域高性能的方向发展。于是计算网格也就成为计算机工作者近年来在分布和 并行计算领域的一个研究热点。 2 2 计算网格的特点 计算网格不同予传统的分布式系统和并行系统。一方面，计算网格高性能 的要求导致网格计算的程序设计模型和接口不同于分布式系统，应用程序往往 希望精确地安排通讯和计算，以满足高性能的需求，这正是并行系统的特点而 非分布式系统所具有的；另一方面，计算网格的异构特性、动态特性和广域特 性又限制了并行计算的工具和技术在其中的应用，这又和分布式系统相类似。 因此不妨认为计算网格结合了分布式系统和并行系统的若干特性。 下面我们具体介绍计算网格的主要特点。 2 2 1 可扩充性和可选择性 计算网格首先必须保证系统的可扩充性。广域范围内的并行与分布式计 算，拥有庞大的计算机资源，可扩充性是一个基本的特点。任何应用都可以根 据自己在连接特性、开销、安全和可靠性等方面的要求选择适合的计算资源完 成计算。 2 2 2 多层次上的异构性 构成计算网格的计算资源和网络连接常常是高度异构的，这种异构特性表 现在各个层次上，从硬件设备、系统软件到调度策略、安全策略、使用策略等 等都具有异构性。这是由计算网格所面临的现实环境决定的。 2 2 3 不可预测的结构 传统上，高性能应用一般在单独一类系统上开发，很多特性是固定、可知 的。然而，计算网格的应用要求执行在较广泛的环境中，这种环境是由适合资 源动态构成的。这就导致了执行系统的结构和特性很难确定，动态变化，无法 进行预测，同时地理上的分布和网络等的复杂性更加剧了这一点。 2 2 4 动态的，不可预测的行为 传统的高性能应用系统经常使用空分共享或者组调度的调度策略，可以预 测其对处理机和网络的访问，而在计算网格中，资源特别是网络链路很可能是 共享的，其结果是系统行为和性能随时间而变化。此外大规模的计算网格也可 能会遇到资源和网络的失效，以致无法保证基本的服务质量要求，这又会导致 第8 页 国防科学技术大学研究生院学位论文 应用系统的行为无法预测。 2 2 5 多个管理区域 计算网格应用所使用的资源通常不是只被一个组织拥有和管理，而是由多 个组织的管理实体管理自身的计算资源。不同组织的管理实体可能采用不同的 管理机制，不同的验证机制、授权机制和访问机制，这使得本已令人头疼的网 络安全问题更加复杂，这也要求计算网格要解决用户代码的远程执行问题、资 源的协作分配问题以及分布和并发调度问题。 2 3 计算网格的分层模型 上一节归纳的计算网格的特点使得计算网格具有比传统分布和并行系统更 复杂的内部结构。为了刻划描述的清晰和设计实现的简明，计算网格的研究一 般采用图2 1 所示的分层模型，由底向上的四个层次依次为：网格纤维层、网 格中间件层、网格工具层和网格应用层。从功能划分的角度又可以把这四个层 次合并成两个子网格：底下两层组成了资源子网格，它为网格用户提供了几乎 是不受限的计算资源、数据资源以及各种各样的科学仪器和设备；顶上两层组 成了访问子网格，它为网格用户提供了一个可实施协作的、虚拟的应用环境及 应用开发环境。 2 3 1 网格纤维 如表2 1 所示，网格纤维包括了所有地理分布的跨越组织的联网资源以及 它们的本地资源管理器。 2 3 2 网格中间件 网格中间件为网格计算提供了一系列的基本服务，它们包括通信服务、名 字服务、信息和注册服务、安全和认证服务、远程进程管理服务、协作资源分 配服务、全局数据访问服务、分布式文件系统和协作式高速缓存服务、协同资 源分配服务、服务质量保证服务等。网格中间件是计算网格的核心层次。 2 3 3 网格开发环境和工具 语言、库和调试工具为程序设计人员提供了网格应用的开发平台；应用代 理软件实现了两组功能：一组功能是为特定领域特定规模的应用确定其资源需 求，并使用网格中间件提供的服务将应用的资源需求映射为一组具体的资源集 合；另一个功能是启动应用执行、实施应用级的资源调度、监视应用的执行情 况以及收集计算结果。嵌入h t t p 服务器的w e b 工具为用户访问应用代理提供了 一致的界面。 第9 页 国防科学技术大学研究生院学位论文 2 3 4 网格应用和网格端口 使用网格工具层提供的语言和库，如整合了网格计算支持的h p c + + 、m p i 等软件，可以开发出各个领域的网格应用。典型的网格应用有参元分析、密码 破译、气候模拟、宇宙起源研究等，它们通常需要本组织和本管理域无法满足 的计算能力、远程数据的访问以及特殊科学仪器的使用。此外，网格端口提供 了w e b 使能的应用服务。例如用户可以通过w e b 浏览器在一个具有几乎足无限 多资源的虚拟机房里完成自己的计算任务一提交作业、监视执行和收集结果。 使用w e b 界面的好处是用户友好，并且能使用户专注于网格应用的开发和运行， 尽量少关心具体计算资源的细节。这一点对于计算网格的地理分布、广域大范 围的异构环境尤其重要。 图2 1 计算网格的分层模型 第1 0 页 国防科学技术大学研究生院学位论文 i i1 表2 1 网格纤维 资源类型资源示例本地资源管理嚣 计算瓷源 单一计算系统超级计算机、高性能工操作系统，如各种u n i x 、w i n d o w sn t 等 作站、微机 分布和并行系统机群排队系统，如d 0 s ； 负载平衡系统，如l s f ： 空闲能力采集利用系统，如c o n d o r ： 等 数据资源物理数据资源磁盘阵列、存贮局域网设备的专用操作系统 s n 逻辑数据资源数据库、数据仓库 数据库管理系统 科学仪器如射电望远镜、电子显微镜、遥感仪、粒子加速器等 2 4 计算网格的基本服务 计算网格不仅要能够连接资源集合，隐蔽网络和机器的异构性，还要能够 提供计算所需的一系列基本服务，从而支持和简化包括计算密集、数据密集和 通讯密集等各种类型的应用和工具的开发，支持各种高级服务策略在基本服务 上的有效实现。如何提供这些基本服务是计算网格非常关键和重要的技术。这 些基本服务包括通信服务、名字和信息服务、安全服务、数据访问服务、资源 管理和应用调度服务、远程执行服务、容错服务等等。限于篇幅，下面只对相 对更重要的前五个基本服务作逐一的考察。 2 4 1 通信服务 计算网格应用对于通信的需求非常广泛：从点到点通信到组播和广播通 信；从不可靠的无连接的通信到可靠的面向连接的通信；从流数据通信到块传 输通信，有时还同时使用多种通信模式。此外，由于计算网格具有地理分布的 广域特性，通信的安全和服务质量需求也高于传统的分布和并行系统。 由于以上特点，一个可行的网格计算通信解决方案应当提供多通信方法的 支持。g l o b u s 元计算工具集合的n e x u s 3 多线程通信库所使用的通信链接远 程服务请求通信模式就是一个典型的例子。该通信模式能够映象为多种不同的 通信方法，这些通信方法又可以具有不同的性能特点。通信方法不仅包括通信 协议，而且还包括通信的其它方面，例如安全性，可靠性和服务质量等。通过 将通信链接的属性与一个特定的起点或终点相联系，应用程序就可以控制位于 这个链接之上的通信方法。例如，如果在一个应用中有些通信必须是可靠的， 第1 1 页 国防科学技术大学研究生院学位论文 而其它一些通信则要求低延迟，则可以在两进程问建立两个通信链接，其中一 个配置成可靠的、延迟较高的通信，而另一个则可配置成低延迟、不可靠的通 信。通过分别在两个通信链接上执行远程服务请求，就可以得到不同种类的通 信服务。 2 4 2 名字服务和信息服务 类似其它分布式系统，名字被用来作为各种资源、服务和数据对象的引用。 名字服务为整个计算网格的提供了一个统一名字空间。典型的名字服务协议有 i s o 的x 5 0 0 和i n t e r n e t 的d n s ，两者都可以在计算网格中得到应用。 计算网格是一个动态的计算平台，其服务的类型和位置始终在不断地发生 着变化。计算资源对于网格用户的位置透明性是计算网格的一个重要设计目标。 信息服务使得网格用户能够方便、快速和准确地获取地理分布的各种动态信息。 计算网格对于名字和信息服务的基本要求有三点：大规模两性能低开销、信 息的一致性和系统规模的可伸缩性。此时轻权目录访问协议l d a p 是一个较好的 选择。 表2 2 对于主要的名字服务和信息服务技术与工具进行了简明的对比。 2 4 3 安全服务 在广域网络上进行计算，安全保证是至关重要的。安全服务的好坏常常是 计算网格成败的一个关键因素。安全服务将提供基本的安全保护验证机制，以 验证合法的用户和资源，并为其它安全服务如授权和数据安全等提供接口，允 许用户选择不同的安全策略、安全级别和加密方法等。 在计算网格中常用的安全技术有：安全套接层s s l 、x 5 0 9 授权标准、 k e r b e r o s 认证协议和r s a 加密解密算法。 2 4 4 数据访问服务 数据访问服务通过对i o 的抽象提供一个远程i o 接口，以支持网格计算 应用对数据的高速远程访问。分布式文件系统是计算网格实现数据访问服务 的通常途径。大多数的网格计算应用都要访问远程数据，这些数据常常又是分 布在多个物理位置。这时从用户的观点而言，一个方便而高效的分布式文件系 统对于应用开发和执行的效率会是至关重要的。用户对于分布和并行文件系统 的基本要求有：一个统一的、全计算网格范围的文件空间、一组语义清晰、语 法简单的文件输入输出原语及对应的数据访问协议、文件输入输出性能优化的 工具和途径( 例如协作式高速缓存) 、尽可能避免至少是减少源程序的修改。 分布式文件系统的一个重要标准是m p i i o 4 。m p i - i o 定义了基于消息传 递语义的并行i o 应用程序接口。由于和消息传递接口标准m p i 的密切联系， m p i i o 已经得到了广泛的应用。 第1 2 页 国防科学技术大学研究生院学位论文 计算网格中使用的典型分布式文件系统有g a s s 、w e b f s 、p v f s 等等。 表2 2 主要的名字服务和信息服务技术与工具 技术与工具能力与特点 0 s 命令，如u n e 和s y s i n f o 供某台机器的重要信息，但不支持远程访问 网络信息服务n i s支持远程访伺，但开销太、可伸缩性弱 并行计算环境，如p v m 、p 4 和m p i高性能，但可伸缩性弱、对远程访问的支持弱 x5 0 0 标准定义了一个目录服务满足各种功能上的要求，但是非常复杂，又需要 i s o 协议支持，使用a s n 1 数据编码，因此使用不广泛 i n t e r n e t 域名服务d n s提供了分布的、可伸缩的服务来解决网络名字地址变换问题其修改 策略仅支持很少和很小的变化。 轻权目录访问协议l d a p x 5 0 0 目录服务的轻权版本，抛开了对i s o 协议栈的需求，直接在i p 协议上定义了一个标准：简化了x5 0 0 的数据编码技术和指令系统 同时定义了一个目录访问的标准a p i ：功能和性能得到了一定程度的 折中。 2 4 5 资源管理和应用调度服务 显然，资源管理体系结构和应用调度机制会对计算网格应用执行的效果产 生重要影响。从系统的观点而言，处理机时间、内存和外存空间、网络带宽需 求及其它计算资源在应用之间的合理配置和高效使用是资源管理和应用调度服 务的最终目标。从用户的观点而言，资源管理和应用调度服务最好是透明的， 用户只需说明应用的负载特性和服务质量需求，系统根据这些信息和当前系统 状态确定适合的资源集合并在适合的时机调度应用执行。用户并不关心也无需 了解具体计算资源及其局部资源管理器的各种细节。 资源管理和应用调度服务是本文研究的核心问题。第三章将用一节的篇幅 讨论计算网格资源管理的研究现状和存在问题，此处不再赘述。 2 5 计算网格应用 在核科学和核武库维护、宇宙学、环境和水文学、生物学、医药学、流体 力学、化学、材料科学、微电子学、军事学等等众多的领域存在着计算网格应 用的广阔天地。根据应用特性的不同，可以将这些领域中主要的计算网格应用 划分为如下几类。 第1 3 页 国防科学技术大学研究生院学位论文 2 6 1 分布式超级计算应用 该种应用无法由单一系统来解决，它需要由多种机器，多个系统甚至多个 科学仪器设备来共同完成。它是一种计算密集型应用，网络带宽、延迟、调度、 容错是其关键技术。主要的应用领域有大型分布式可交互仿真、复杂物理过程 的精确仿真等等。例如美国s f _ e x p r e s s 工程就曾经基于g l o b u s 系统提供的服 务，使用了横跨七个时区的九个地方的先进计算机，进行了十万辆独立机载物 的军事模拟。 2 5 2 高吞吐率计算应用 这类应用通常由大量松散耦合的、独立任务组成，主要目标是调度大量的 松散耦合的独立任务，利用网络上空闲的计算资源完成多个任务的计算，从而 完成整个应用。这种应用常常利用空闲的计算系统，例如a m d 公司的k 6 、k 7 芯 片设计就采用了几千台计算机利用空闲时间进行计算，一些加密算法问题也采 用了此类技术。 2 5 3 按需求计算的应用 这种应用往往要求一些局部无法解决和满足的计算资源提供短时间的服 务，这些资源可以是计算机、软件、数据和特殊仪器等，它们又常常以性能价 格比作为最主要的因素。例如：远程医学仪器使用和远程教育等。这类应用根 据需要要求局部自己无法解决的计算资源在适当的时间提供支持。 2 5 4 数据密集计算的应用 该类应用要求从地理上分布的数据库和数据仓库中的数据中综合出信息。 这种综合过程往往是计算密集和通讯密集的过程。例如未来的高能物理实验每 天将产生万亿字节量数据，每年将达千万亿字节量数据，需要使用复杂的查询 方法才能访问如此巨大的数据集合，从而抽取组织有效信息。访问这些数据的 科学工作者往往处在不同的地理位置，需要对数据进行共享和不同的计算处理， 因此，这类应用希望系统能够支持分布存储和管理，并提供良好的并行查询、 提取等操作。 2 5 5 合作计算的应用 合作计算的应用主要关心如何允许和加强人们之间的交互行为和合作以协 同完成任务。这种应用通常是根据虚共享空间构造的，允许共享使用计算资源， 能够进行远地的实时交互，完成一个共同的任务。 2 6 计算网格研究项目 计算网格是当前分布和并行计算领域的一个研究热点。世界各国正在实施 第1 4 页 国防科学技术大学研究生院学位论文 着数十个计算网格的研究项目，表2 3 列举了一些主要项目的i n t e r n e 网址。 从系统框架到应用测试床，从协作环境到资源管理模型，这些研究基本含盖了 计算网格研究的各个侧面和各个层次。限于篇幅，本文仅讨论三个具有代表性 的项目：g l o b u s 、l e g i o n 和w e b f l o w 。 表2 3 主要计算网格研究项目的i n t e n e t 网址 g l o b u s型坠上且生坐出 l e 9 1 0 n l e r i o nv i r r i n i ae d u a p p l e s w