（计算机应用技术专业论文）元计算实现机制和资源管理的研究.pdf

华 中 科 技 大 学 硕 士 学 位 论 文 摘要 随着科学计算规模的不断扩大， 大规模计算在各行业也日 益得到广泛应用。 人们 对计算能力的 需求是无限的，尽管微处理器的速度以 摩尔定律每 i s个月 增长一 倍的速度发展， 但一些大规模计算问 题依然不能在适当的时间内由 一台单一的p c计 算完成。 超级计算机造价昂贵， 通常属于某大学或大公司所专有，普通用户没有机会 使用。普通机构或个人为满足自 身的 计算需求而购买高 端的计算设备是不经济的。 i n t e rn e t 上连接的包括超级计算机在内的计算机数目的极大增长及大部分计算机远远 都未充分利用的现实引出了元计算的概念。 元计算是指通过网络连接地理上分布的 各类计算机( 包括机群) 、数据库和其它设 备，形成对用户透明的虚拟高性能计算环境，实现广域范围的资源共享和协同工作， 它的应用包括科学与工程计算、信息服务、协同工程等。 本文针对元计算在信息服务和科学工程计算中应用的实现机制做了研究。 在信息 服务方面， 以 面向服务的观点， 提出了一个w e b 服务的通用集成模型， 为集成现有的 we b 服务实现元计算提供了一种可选机制。 在科学与工程计算方面， 则是借用其它方 的计算设备来运行用户特定的应用， 实现计算资源共享。 为了 应对元计算中资源管理 和任务调度的挑战， 借鉴已 有的相关研究成果， 给出了一个改进的基于市场的资源管 理模型， 这一模型不仅能更好的调节计算资源的供求关系， 而且可以刺激更多的计算 节点加入到元计算系统中 提供计算力， 促进元计算系统的良 性循环发展。 为任务调度 设计了一种蚂蚁算法， 本算法在动态变化的元计算环境中可得到较好的响应时间和较 高的系统利用率。 最后根据给出的资源管理模型设计了一个元计算系统， 并对其原型 实现中的难点做了详细研究。 关键词: 元计算，信息服务，资源管理，任务调度，市场模型 华 中 科 技 大 学 硕 士 学 位 论 文 ab s t r a c t wi t h t h e c o n s t a n t e n l a r g e m e n t o f t h e s c i e n t i f i c c a l c u l a t i o n s c a l e ，l a r g e s c a l e c o m p u t a t i o n i s a l s o a p p l i e d m o r e a n d m o r e i n a l l k i n d s o f b u s in e s s . p e o p l e s d e m a n d f o r c o m p u t i n g c a p a c i t y i s in f i n i t e , a l t h o u g h t h e r a t e o f c p u i n c r e a s e d r a p i d l y a c c o r d i n g t o mo o r e s l a w一 d o u b l e e v e r y 1 8 m o n t h s , s o m e l a r g e s c a l e c o m p u t a t i o n p r o b l e m s c a n n o t b e c o m p l e t e d b y a p c i n a r e a s o n a b l e a m o u n t o f t i m e . s u p e r c o m p u t e r s a r e v e ry e x p e n s i v e , a n d t h e y a r e u s u a l l y o w n e d e x c lu s i v e l y b y s o m e u n i v e r s i t y o r la r g e c o r p o r a t i o n , o r d i n a ry u s e r s u s u a l l y h a v e n o c h a n c e t o u s e t h e s u p e r c o m p u t e r s . i t i s n o t e c o n o m i c a l f o r o r d i n a r y o r g a n i z a t i o n o r p e r s o n t o p u r c h a s e a d v a n c e d c o m p u t a t i o n a l e q u ip m e n t t o m e e t i t s d e m a n d f o r c o m p u t a t i o n . t h e n u m b e r o f c o m p u t e r s t h a t a r e c o n n e c t e d t o i n t e rne t i n c l u d i n g s u p e r c o m p u t e r s i n c r e a s e d g r e a t l y， a n d m o s t o f t h e c o m p u t e r s a r e m u c h u n d e r u t i l i z e d d u r i n g m o s t t i m e , t h e c o n c e p t o f m e t a c o m p u t i n g i s i n t r o d u c e d . me t a c o m p u t i n g i s a l s o k n o w n a s g r i d c o m p u t i n g , i t i s a n e t w o r k t h a t c o n n e c t s a l l k i n d s o f g e o g r a p h i c a l l y d i s t r i b u t e d c o m p u t e r s ( i n c l u d i n g c lu s t e r s ) , d a t a b a s e a n d o t h e r e q u ip m e n t s , w h i c h p r o v i d e s a t r a n s p a r e n t v i r tu a l h i g h - p e r f o r m a n c e c o m p u t i n g e n v i r o n m e n t t o u s e s . b y m e t a c o m p u t i n g , r e s o u r c e s h a r i n g in a l a r g e a r e a a n d c o o p e r a t i v e w o r k a r e r e a l iz e d , t h e a p p li c a t i o n o f m e t a c o m p u t i n g i n c lu d e s s c i e n t i f i c a n d e n g i n e e r i n g c o m p u t a t i o n , i n f o r m a t i o n s e r v i c e a n d c o o p e r a t i v e e n g i n e e r i n g , e t c . t h i s d i s s e r t a t i o n s r e s e a r c h f o c u s e s o n t h e i m p l e m e n t a t i o n m e c h a n i s m s i n t h e a p p l i c a t i o n fi e l d o f i n f o r m a t i o n s e r v i c e a n d s c i e n t i f i c c o m p u t i n g . i n t h e in f o r m a t i o n s e r v i c e fi e l d , fr o m a s e r v i c e - o r i e n t e d v i e w p o i n t ， a g e n e r a l i n t e g r a t i o n m o d e l o f we b s e r v i c e i s p r e s e n t e d w h i c h m a k e u s e o f e x i s t i n g b as i c w e b s e r v i c e s , a n d t h e m o d e l p r o v i d e a a lt e rn a t i v e i m p l e m e n t a t i o n m e c h a n i s m f o r m e t a c o m p u t i n g . i n t h e f i e l d o f s c i e n t i fi c c o m p u t i n g , s h a r in g o f c o m p u t i n g r e s o u r c e i s r e a l i z e d b y u s i n g o t h e r s c o m p u t i n g e q u i p m e n t s t o r u n o n e o w n a p p l ic a t i o n . t o t a k e t h e c h a l l e n g e o f r e s o u r c e m a n a g e m e n t a n d t a s k s c h e d u l in g i n m e t a c o m p u t i n g , u s i n g e x i s t i n g r e l a t e d r e s e a r c h a c h i e v e m e n t s f o r r e f e r e n c e , a n i m p r o v e d m o d e l o f r e s o u r c e m a n a g e m e n t b a s e d o n m a r k e t i s p r e s e n t e d w h i c h c a n n o t o n l y r e g u l a t e t h e s u p p l y a n d d e m a n d o f c o m p u t i n g r e s o u r c e , b u t a l s o s t i m u l a t e m o r e c o m p u t i n g n o d e s t o e n r o l l in t h e m e t a c o m p u t i n g t o c o n t r ib u t e t h e i r c o m p u t i n g p o w e r , r 华 中 科 技 大 学 硕 士 学 位 论 文 le a d i n g t h e b e n i g n d e v o l e p m e n t o f m e t a c o m p u t in g r o t a t i v e l y . a k i n d o f a n t a l g o r it h m f o r t a s k s c h e d u l i n g i s d e s i g n e d t o g e t b e tt e r r e s p o n s e t i m e a n d h i g h e r u t i l i z a t i o n o f s y s t e m i n m e t a c o m p u t i n g . f i n a l l y , m e t a c o m p u t i n g s y t e m b a s e d o n t h e p r e s e n t e d r e s o u r c e m a n a g e m e n t m o d e l i s d e s i g n e d , s o m e d i f f i c u lt p o i n t s o f i t s p r o t o t y p e i s g i v e n d e t a i l e d r e a s e a r c h . k e y w o r d s : m e t a c o m p u t i n g , i n f o r m a t i o n s e r v i c e , r e s o u r c e m a n a g e m e n t , t a s k s c h e d u l i n g , ma r k e t mo d e l 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学 位 论 文 作 者 签 名 : + 3 勇 日 期 : - d l* 件 月 飞 。 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即:学校有 权保留并向国家有关部门 或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在_年解密后适用本授权书。 本论文属于 不 保 密 s r . ( 请在以上方框内打 “-1 1 1 ) 学 位 论 文 作 者 、iq d * 日 期 : l午 月 ; o f l 指 导 教 师 签 名 : 术 、 0 rv 日 期 : ” ， 件 华 月; 。 日 华 中 科 技 大 学 硕 士 学 位 论 文 1 绪论 1 . 1 课题背景 基于i n t e r n e t 的 元计算( m e t a c o m p u t i n g ) 的 概念 越来越流行，它 又称网 格计算， 其 主要思想是使用通过i n t e rne t 互连的、 在地理上分布的计算机来解决大规模复杂问题。 “ 元” 是共享、 协调行动的意思。 元计算指各计算机共享资源，协调运行， 从而共同 解决某个问 题。元计算通过网络给用户提供一个透明使用计算资源的环境。 为什么需要元计算?简单的说是我们的计算需求是无限的，而我们自己的计算资 源 却是有限的，于是可以 利用网 络连接 起来的 众多的闲 置计算资 源。 w w w ( 万维网 ) 的流行使i n t e rn e t 上的主机数目 有了极大的增长， 上千万台计算机连上了i n t e rn e t ， 这 些互相连接的处理器构成了一个拥有不可思议的计算能力的超级计算机， 这些机器中 的大部分只是用来执行一些小型的交互式程序，例如阅读电子邮件、编辑文件或只是 浏览网页， 利用率不到2 5 ， 它们中的大部分在许多时间里都是空闲的， 只是在运行 屏幕保护程序，因此使用这些巨大的计算资源来解决密码学、 数学、计算科学中的问 题是可行的。 理想的元计算环境应该是注册各类共享资源， 用户只需提交服务请求或任务，各 节点就能协调计算，发送结果， 人只需要很少的参与，就象人们只用开关就能使用电 力那样容易。为了跨组织共享各自 治异构资源，实现理想的元计算， 应该遵循以下一 般原则:不干扰现有的计算节点的管理和自 治性;不损害现有节点及用户的安全性; 不必改变现有的操作系统、网络协议及相关服务; 允许计算节点自由的加入或退出元 计 算环 境; 提供可靠的 和容错的 基础 构架; 对异构 部件的 支持 i .i 为了 使网格计算的应用领域不局限于科学计算， 加速与企业界w e b 服务技术的融 合，网 格计算权威 i r a n f o s t e : 博士继五层砂漏结构后提出了 开放网格服务体系结构 o g s a ( o p e n g r i d s e r v i c e a r c h i t e c t u r e ) ， 它被称为是下一代的网格体系结构。 o g s a 就是以 服务为中心的体系结构，它定义了“ 网格服务”的概念，网格服务是一种w e b s e r v i c e l2 l . w e b s e r v i c e s 是一种新的分布式计算的模式，它描述了一些操作的接口， 通过标准化的x ml消息传递机制，可以通过网络访问这些操作。we b 服务履行一项 特定的任务或一组任务， 它可以单独或同其他w e b 服务集成起来用于实现复杂的商业 交易。随着电子商务的 迅速发展， b 2 b ( b u s i n e s s - t o - b u s i n e s s ) 应用模式的不断普及，如 华 中 科 技 大 学 硕 士 学 位 论 文 何将w e b 服务高效集成起来， 从而实现大范围的跨企业实体的商务应用系统对接成为 一个急待解决的问 题侧 。 元计算与传统的并行计算的关键区别在于每个计算节点的行为。元计算环境是由 若干计算节点组成的动态集合， 其中的任一节点可以自由的加入或退出这个集合， 各 节点是独立的机器;而并行计算的各计算节点通常不是独立的。 在元计算系统中管理处理器、内存、网络、存储器和其它部件是很重要的，总的 目 标是有效并高效地调度需要使用元计算环境资源的各类应用程序。资源管理和调度 对用户而言应该是几乎透明的，用户只需提交应用程序而已， 这给资源管理和任务调 度提出了极大的挑战。 1 .2 国内外研究概况 当前关于w e b 服务集成的研究较少，已 有的研究例如ws f l , x l a n g等，主要 是为w e b 服务技术制定 基于x m l 的 标准，为w e b 服务集成定义原语 ( p r i m i t i v e ) 并 使各 we b服务间自 动协作，然而这些研究并没有直接解决 we b服务间的异构问题， 也未给松散藕合的we b 服务的集成提供好的事务支持。 使用空闲的计算节点来帮助处理某些科学计算己不是什么新思想了。 在参考文献 4 中 提到了 一 个大规 模并行计算的 例子， 这个实验 使用了 大约4 0 0 台 机器来分 解一 个 r s a加密算法使用的1 0 0 位整数， 每个节点通过电 子邮件收到了一些将要独立计算的 多项式， 每个任务的计算结果也将通过电子邮件送给某一服务器， 它将协调任务流与 关 系流。 在1 9 9 4 年4 月， 著名的1 2 9 位r s a 密 码被 该项目 使用 平方过0( q u a d r a t i c s ie v e ) 算法破解了。 根据r s a发明者( r o n r i v e s t , a d i s h a m i r , l e n a d l e m a n ) 的说法， 这个 密 码需要4 0 x 1 0 2 4 年刁 能分解。 在1 9 %年4 月， 一 个1 3 0 位的 数也被成功分解了 ， 这 次 他们使用的是实数域过滤算法，该项目 现在的目 标是r s a - 1 5 5 e 1 9 9 7 年， 人 们 宣 布了 一个 叫 作s e t i h o m e 的 方 案， 它 将 试图 使 用i n te rn e t 上p c 机的空闲 计算能 力来寻找地球外的 智能 ( s e t i ) 。 该 程序将作为 一个 特殊的 屏 幕保护 程 序而执行，分析一些世界上最大的射电望远镜获得的数据。在 1 9 9 7 年 9 月， 有超过 3 5 0 0 0 的 人 加入了s e t i h o m e 邮 件列 表。 总之，现在己经有了一些很好的在 i n t e rn e t 上执行数据处理程序的例子，这些例 子说明 成千上万台i n t e r n e t 上的计算机可以作为一台超级计算机来解决需要长时间 运 行的问题，仅仅需要利用他们的空闲c p u时间而已。 一 些 典 型 的 元 计 算 系 统 诸 如g l o b u s ls 和l e g i o n fb 等 主 要 是 对高 端 计 算 资 源 超 一门一一甲一. ， . . . . .， 月 . . . . . . . 月 . . . . . . . .目 . . 目 目. . 户 ， 一. 一一一 一，. . . . . . . . . 2 华 中 科 技 大 学 硕 士 学 位 论 文 级计算机和以队列系统管理的机群的使用，为分布式高级应用提供了一个计算平台。 1 . 2 . 1 国内外类似系统概况 i . gl o b u s g l o b u s 7 1 基于己存在组件集合提供了一个工具箱， 利用这个工具箱可以 构造一个 元计算系统。 通过 g l o b u s 这一架构，应用程序处理分布式的异构资源时就像一台虚 拟的 机器一 样。 g r a m ( g l o b u s r e s o u r c e a l l o c a t i o n m a n a g e ) 是g l o b u s 结构的 最低层。 g r a m允许任务远程执行，并为任务的提交、监控和终止提供了a p i . g r a m 提供 了用于资源管理的本地部件， 该部件负责在本地统一的分配策略下的资源管理。 这一 分配策略可以 用本地的资源管理软件包实现，例如 l s f , c o d in e或 c o n d o r . g r a m 的职责如下: ( 1 ) 解析并执行用r s l ( r e s o u r c e s p e c i f i c a t i o n l a n g u a g e ) 描述的 任务请求。 这些 请求详细说明了资源选择、任务进程生成及任务控制等情况。g r a m或者拒绝请求， 或者生成一个或多个进程来满足该请求。r s l是一种结构化语言，用户可以用 r s l 定义资源需求和参数。 ( 2 )对己经生成的任务的远程监控和管理。 ( 3 )用与其管理的资源相关的可用性等信息更新md s o 2 . l e g i o n l e g io n 8 1 是 美国 弗 吉 尼亚 大学 开 发的 基于 对象 的 元 计 算系 统， l e g io n 从已 有 部 件 和新部件抽象出一高层次的统一对象模型。 主机对象代表处理器， 每一计算节点上可 运 行多 个主 机对象。 主 机对象为 活跃的l e g i o n 对象生成 和管理进程。 为 激活主 机对象 代表的计算节点上的实例， c l a s s e s 调用这些对象的 成员函数。 在l e g i o n中，资 源所 有者可以 初始化、 管理、 控制和终止系统对其资源的使用。 l e g i o n 的调度模块包括以 下三个部分: ( 1 ) 资源状态信息数据库( c o l l e c t i o n ) . c o l l e c t i o n 与资源对象交互收集描述系统 的状态信息。 ( 2 ) 将请求映 射到资 源的 模块( s c h e d u l e r ) . s c h e d u l e : 查 询c o l l e c t i o n 以 决定匹 配要求的可用资源集合，一旦作出调度决定，s c h e d u l e r 就将该调度决定交给e n a c t o r 执行。 ( 3 )负责实现调度决定的代理( e n a c t o r ) o e n a c t o r预定使用每种资源，并向 s c h e d u l e : 报告结果， 一旦得到s c h e d u l e r 的批准， e n a c t o r 就在计算节点上生成相应对 象，并监控它们的状态。为满足用户需求，主机对象可以适应不同的环境。 例如主机 3 华 中 科 技 大 学 硕 士 学 位 论 文 对象可以提供与l s f , c o d i n e 或c o n d o r 等资源管理系统的接口。 l e g io n 的 面向 对 象的 特性 有 数 据 抽 象、 封 装、 继 承 和多 态等 优点， 但也带 来了 一 些问 题。 如何封装消息传递或分布式共享内 存等非面向 对象的 编程范式最好至今仍无 定论， 并 且现实中的 大多数计 算服务 都是过 程性接口 ， 因 而为了 能与l e g i o n 更好的 对 接， 有必要生成面向 对象的w r a p p e r . 3 . we b f l o w w e b f l o w i9 1 是 w e b模型的 计算扩展， 为 广域网的分布式计算提供了 一个框架。 w e b f l o w的主要设计目 标是为在 we b上发布和重用计算模块构建一个无缝的框架， 从而用户通过浏览器就能参与到创建分布式应用的过程中来。we b f l o w 的基于 j a v a 的 三层结 构可以 看作是一个可视化的 数据流系统。 前端使用a p p l e t 实现对环境的修改、 可视化和控制。 w e b f l o w使用基于s e r v l e t 的中间 件层来管理用于数据库或高性能仿真 的遗留代码等后端模块并与之交互。 w e b f l o w的结构特点决定了它只能安装在支持 s e r v l e t 的w e b 服务 器上。 元计算需要的硬件和软件基础设施应该能提供对高性能计算机等计算资源的可 靠的、一致的、普遍的使用 ; 1 。 在理想的元计算中，用户可以一种无缝的方式使用 元计算中的可用资源， 这需要元计算在设计时要注意以下问题: 管理层次， 通信服务， 信 息 服务， 命 名服 务， 资 源 管 理与 任务 调 度， 安 全 和授 权等 1 1 1 ,12。 资 源管 理的 总 体 目 标是高效调 度任务使用元计算中的可用资源， 将各个不同的异构环境组合成一个虚 拟的同构环境，这带来了两个重要的挑战: i . 扩展性 元计算可能包括许多组织机构， 元计算中的每一组织都有自己的功能、 资源和环境， 这些组织不一定能协调地共同 工作， 不同的组织可能位于不同的地点并 且并不知道彼此的存在。 2 . 适应性 元计算是一个动态的环境， 各个的组成部分的位置、 类型、性能都可 能 在经常地改 变。 例如某一计算节点可能随时地加入或退出计算环境。 元计算中的某 节点很可能不是为元计算所专用的，它能贡献给元计算的计算力随时间是改变的。 元计算的资源管理必须应对扩展性和适应性挑战。 典型的元计算系统， 如g l o b u s , w e b f l o w , l e g i o n 等， 都没 有在资 源管理中 使 用经济学方 法。 但是， 在计 算机系统的 资源管理中使用经济学方法， 特别是使用经济学方法解决分布式系统的负载平衡问 题，却是近 2 0年来非常活跃的一个研究领域，相关的研究论文和原型系统为数众多 t 3 一 ， 5 。 上述工作的 基本思想是: 使用价格信号反映资源的忙闲 程度， 通过使用最便宜 的资源执行新到的用户作业，实现整个系统的负载平衡。 . . . . . ， . ， . . . . . . . . . . ， . ， ， . . . . . . . 4 华 中 科 技 大 学 硕 士 学 位 论 文 这些研究成果不能直接用于计算网 格的 资源管理， 其原因 在于: 首先它们的 着眼 点主要是负载平衡，因而对于服务质量保证的支持很弱; 其次，需要一个中央市场或 是公告牌，因而算法的可扩展性不好; 再有，资源分配的对象是具体的任务， 粒度小 导致开销大; 一部分工作基本没有考虑计算网 格的广域特点。 1 .2 .2 主要关键技术 w e b 服务的集成，元计算资源管理模型及其原型实现主要涉及以下关键技术: 1 . ws d l ( we b s e r v i c e s d e s c r i p t i o n l a n g u a g e ) ws d l 3 是用于描述w e b服务的一种 x m l语言。 它将 w e b服务描述为一组对 消息进行操作的网络端点。一个 ws d l服务描述包含对一组操作和消息的一个抽象 定义，绑定到这些操作和消息的一个具体协议，和这个绑定的一个网络端点规范。 ws d l抽象描述访问的操作和访问时使用的请求/ 响应消息，将其绑定到具体的传输 协议和消息格式。 相关的具体部署的服务访问点通过组合就成为抽象的we b 服务。 描 述 服务的 主要 元素 有t y p e s , m e s s a g e , o p e r a t i o n , p o rt 乃 p e , b i n d i n g , p o rt , s e r v i c e . 业务之间将通过交换 ws d l文件来理解对方的服务， ws d l 包括面向文档的( 消息) 和面向r p c型的两种有效载荷。 2 .计算网格资源管理 计算网格资源管理系统的基本功能是接受来自 计算网格范围内的机器的资源请 求， 并且把特定的资源分配给资源请求者。 合理地调度相应的资源， 使请求资源的作 业 得以 运行。 为实现上述功能， 一般而言， 计算网 格的资源管理系统应提供三个基本 的 服务 1 16 ,1 7 1 : 即 资 源分 发、 资 源发 现 和资 源的 调 度 ( 或任务 调 度 ) 。 资 源发 现 和资 源分 发提供相互补充的功能。 资源分发由资源启动且提供有关机器资源的信息或一个源信 息资源的指针并试图去发现能够利用该资源的合适的应用。 而资源发现由网络应用启 动并在网 格范围内 发现适于本应用的资源。 通常通过使用一个资源信息协议来发布计 算网格环境中的资源信息， 而资源信息协议由资源和分发功能所实现。 资源分发和资 源发现是资源调度的前提条件，资源调度实施把所需资源分配到相应的请求上去， 包 括通过不同结点资源的协作分配。 资源管理系统的有效性和可接受性在很大程度上依赖于所实现的资源调度系 统! 1 8 1 ， 也与机器的组织结构密切相关。 计算网 格系统的资源是地理上分布的并属于几 个不同的组织和拥有者， 而大多数的本地机器都有不同的调度策略， 并且在大的计算 网格系统中常遭受任意时间资源加入或退出的频繁的变化。 计算网格的动态性和异构 性决定了资源调度系统的复杂性。 5 华 中 科 技 大 学 硕 士 学 位 论 文 目 前没有一种管理模式能够处理所有的网格应用需求， 大量的网格项目 试图提供 一 个合 适的 资 源管 理 方 法 【 19 -2 1 1， 一 般可 分 为 集中 式、 分 布 式以 及层次 式的 和计 算 经 济 的资源管理模型。 在集中式的环境中， 所有的资源由 一个中央调度程序调度， 所有可 用系统的有关的状态信息被聚集在该中 心机上。 从概念上讲这种调度模式是非常有用 的， 例如在计算中心，因为所有的资源在相同的目 标之下被使用。 在这种情况下，即 使缺乏网络带宽也可以被忽略。 但它形成了一个瓶颈， 使得当计算网格的大小规模扩 充时是很困难的。在分布式的系统中， 分布式的调度程序交互作用并且提交作业到远 程系统中， 没有一个中央调度程序负责作业的调度， 所有系统的状态信息也没有被集 中在单个的结点上，因此消除了集中式调度的通讯瓶瓶。同样单个组件的失效将不会 影响整个的计算网 格系统， 容错和可靠性更高。 但由于一个并行程序的所有部分可能 被分配在不同 域的资源上，因此在相同的时间必须是活跃的， 所以不同的调度程序必 须同步作业并且保证同时运行， 这使得调度系统的优化相当困 难。 在层次式的调度模 型中，有一个集中式的调度程序， 作业被提交到该集中的调度程序，而每一个机器资 源使用一个独立的调度程序用于本地的调度。 这种结构的主要优点是不同的策略能够 被使用来用于本地和全局的作业调度。 如g l o b u s 中的资源管理子系统g r a m根据用 户的请求在网格范围内寻找最符合用户要求的一个或一组机器， 然后实现资源的定位 及分配， 最后由本地资源的调度系统如l o a d l e v e l e r 等与用户进行交互。 基于计算经济 的 调 度 模型的 优越 性是 可 调节 供 需 矛 盾 2 2 1 3 . 蚂蚁式调度算法 元计算要实现i n t e rn e t 上的资源共享， 在通常情况下节点间的通信开销是很高的， 因而在元计算中通常考虑的是粗粒度的任务并且任务间的通信很少。 蚂蚁式的调度算 法是一种启发式的算法，很适合于元计算环境的动态变化的特点。 蚂蚁算法基于现实世界中蚂蚁的行为。 蚂蚁是一种无视力的昆 虫，当它到处寻找 食物的时候， 它都会在自己经过的路上留 下信息素， 于是较短路径上的信息素会迅速 的增长，每一条通往食物的路径上的信息素的数量会影响到其它蚂蚁对路径的选择， 最终所有蚂蚁都会找到最短路径。 蚂蚁式算法已经被用来成功的解决了许多n p问 题， 例如t s p 分配问题和染图问 题12 3 1蚂蚁式算法很适合于元计算中的任务调度， 所有影响计算资源状态的因素可用 “ 信息素”来描述。 要设 计出 切实可 行的 算 法， 还要 将 模型 进一步 精确， 如要 考虑信息素的 挥发 ( 即 信 息素的浓度将随时间而逐步降低等等) 。 用蚂蚁算法求最短程的一般过程如下: 6 华 中 科 技 大 学 硕 士 学 位 论 文 ( 1 )一群蚂蚁随机从出发点出发，遇到食物，衔住食物，沿原路返回。 ( 2 )蚂蚁在往返途中，在路上留下信息素标志。 ( 3 ) 信息素将随时间逐渐挥发( 一般可用负指数函数来描述， 即乘上某因子e 一 a ) o ( 4 )由 蚁穴出发的蚂蚁， 其选择路径的 概率与各路径上的信息素浓度成正比。 4 .智能体技术 智能 体 i ( a g e n t) , 其含义 是 按 照 他人 的 意 愿 或 利益 发 生 作用的 人， 在 计 算 机 领 域中，智能体技术起源于人工智能，其概念在 6 0年代就已提出。智能体技术地真正 发展是在上个世纪 9 0年代，现在正向计算机领域的各方面渗透。智能体是指按照用 户意愿，能够自 主执行的软件模块， 亦称软件智能体。 在复杂环境中，智能体是具有 智能的人工助手，它可以根据需要，自 觉地行使其职责，它还可以通过创建、复制、 组装、 销毁等手段对自 身进行改造，以 适应复杂的任务。 典型的软件智能体结构主要 由感知输入和内部状态记录器，自 身的规则、 方法、 承诺、知识库和推理机组成。 智 能体有自己的变量和推理规则， 推理机以感知到的内容作为输入， 将产生的结果输出 到操作器。操作器根据推理机的结果执行相应的 操作。 智能体的特性如下: ( 1 )自治性 智能体能够在没有人或其它外界因素的干预下运行，即它从用户那 里得到了一定程度的自治。 ( 2 ) 协作性 对于某些任务， 仅靠单个智能体很难完成， 这时需通过多智能体的 协调与合作才能完成。 ( 3 )反应能力 智能体可以感知环境并及时地作出反应。 ( 4 )主动性 智能体可以主动地采取行动达到目 标。 ( 5 ) 适应性 智能体可以适应环境的变化。 智能体的以上特性使它特别适合于元计算环境中的应用。 5 .对象序列化 对象序列化即将对象的状态信息存储到文件中， 以后又能将它们读到内存中或使 用s o c k e t 通过网络发送对象。在j a v a 语言的 对象序列化中， 要序列化的对象必须是 实 现了j a v a .i o . s e r i a l i z a b l e 接口的j a v a 对象。 如果没有实现， 则对象不能被序列化。 注意， s e r i a l iz a b l e 接口 没有任何方法， 它只是提醒j a v a 虚拟机将要序列化对象。 6 .多态 多态性是面向 对象的一个重要特征。 c + 十 中实现运行时绑定是通过将父类中的方法 声明为v ir t u a l ， 缺省情况下是编译时 绑定。 在j a v a 中除非显式的说明为f i n a l , 所有的 方法绑定都是运行时绑定。当通过超类句柄调用一个覆盖方法时， j a v a 虚拟机根据调 一一一一一一一目 . . ，叫 . . . . . . 一一一一-一-一 7 华 中 科 技 大 学 硕 士 学 位 论 文 用发生时引用的实际对象类型来决定执行哪个版本的方法， 这个决定是在运行期做出 课题主要研究工作 在本文的 论述中， 将元计算和网格计算作为两个可以互换的词语。网格( g r i d ) 通 吮l.3 过网络连接地理上分布的各类计算机( 包括机群) 、 数据库、各类设备， 形成对用户相 对透明的虚拟高性能计算环境， 实现广域范围的高性能资源共享和协同工作， 其应用 包括了科学与工程计算、 信息服务、 协同工程等。 网格计算结构己 发展成为连接和统 一各类不同 远程资源的一种基础结构2 5 1 本文针对元计算在信息服务和科学工程计算中应用的实现机制做了研究。 在信息 服务方面，以面向服务的观点， 利用现有的基本的w e b s e r v i c e ， 提出了w e b 服务的一 个通用集成模型。 在科学计算方面，借鉴相关的研究成果，给出了一个改进的基于市 场的资源管理模型， 本模型能更好地调节计算网格资源的 供求， 促进元计算系统的良 性循环发展。 1 . 通用的we b 服务集成模型 根据最新的网格计算中， 面向服务” 的思想，提出了一种 w e b服务集成的通用模 型g i m w s ( g e n e r a l i n t e g r a t io n m o d e l o f w e b s e r v i c e s ) 2 6 ， 为 集 成 现 有w e b 服 务 实 现 元计算提供了一种可选机制。 2 . 基于市场的资源管理模型 从资源共享的角度来看， 元计算可以是小型的家庭用的网络系统， 也可以是大规 模的网络计算系统， 从理论上讲也可以扩大到整个因特网。 正象市场上的的买主和卖 主一样， 元计算市场上也有两方: 请求资源的用户和资源提供者。 经济制度已经被证 明是调节市场供给与需求的最好机制， 市场模型很适合于描述计算网格的动态和异构 特征， 而已 有的 元计 算系统g l o b u s , l e g i o n 和w e b fl o w都未曾 采用经济制度， 为 此 本文将借鉴己 有的相关研究成果f2 7 -2 9 1 ，给出一种改进的基于市场的资 源管理模型 m r m m ( m a r k e t - b a s e d r e s o u r c e m a n a g e m e n t m o d e l ) , m r m m模型 不 仅能 更 好的 调 节 计算资源的供给和需求， 而且可以刺激更多的计算节点加入到元计算系统中提供计算 力，促进元计算系统的良性发展。 3 .元计算系统mr mm的设计与其原型实现 根据给出的模型将设计一个元计算系统m r m m。首先分析元计算系统的一般设 计要求，将元计算与传统的集群作了比较，指出设计中的难点问题;然后将设计 8 华 中 科 技 大 学 硕 士 学 位 论 文 m r mm 的体系结构和各模块的功能，并为其中的 任务调度单元设计一种蚂蚁算法; 最后给出m r mm系统的原型实现并列举了两种典型应用。 本文的章节安排如下: 第 1 章为绪论，介绍了 课题的背景、国内外研究发展概况及主要研究内容; 第2 章对集成现有的w e b 服务实现元计算作了研究; 第3 章给出基于市场的资源管理模型m r mm，并详细阐述了其结构; 第4 章依据m r mm模型设计元计算系统并对其原型实现作了研究。 第5 章介绍元计算系统m r m m原型的使用环境和实例测试; 第6 章对所做工作进行总结，列出一些创新点和继续研究的方向。 1 . 4 小结 本章首先介绍了课题的背景， 然后回顾了国内外研究发展概况，列举了本文主要 涉及的关键技术，最后介绍了课题的主要研究内容。 . . . . . . . . . . . ， ， 叫 ， . ， . . . . . . ， . ， . 月 . . . . . . 户 . . . . 曰 . . . . . . . . . . 叫 9 华 中 科 技 大 学 硕 士 学 位 论 文 2 集成现有的we b 服务实现元计算 本 章提出 了 一 种w e b 服务 集成的 通 用模 型g i m w s ( g e n e r a l i n t e g r a t i o n m o d e l o f w e b s e r v i c e s ) ， 为 集成现有的w e b 服务实 现元计算 作了 研究。 g i m w s 模型 有 效地 解 决了we b 服务集成中的异构问题，其中的聚合层屏蔽