（计算机软件与理论专业论文）基于统计思想的层次化网格负载平衡调度算法.pdf

华北电力入学硕十学何论文摘要 摘要 随着网格技术的飞速发展，有关资源分配与任务调度的研究面临着新的机遇 和挑战。这些新的技术、概念和方法提供了更新的环境来研究和发展面向负载平 衡的作业调度系统。针对层次化网格模型结构，运用统计思想提出了一种新的资 源分配与任务调度算法，不仅能够提高资源的利用率和系统的吞吐率，而且能够 实现网格系统内部的负载平衡。算法对负载信息预测、负载平衡收益和丌销、作 业分配以及性能标准做了详细的阐述。在解释了方案中各功能部件的作用及其相 互之问关系的基础上，给出了相应的算法伪码，仿真实验表明，该算法是有效的。 关键词：网格计算，层次化，任务调度，负载平衡 a b s t r a c t a sg r i dt e c h n o l o g i e se v o l v eq u i c k i yo ni n t e t l l e t ，l o a db a l a n c er e s e a r c ha n d d e v e l o p m e n tf a c en e wo p p o n u n j t i e sa n dc h a l l e n g e s t h e s en e wt e c h n o l o g i e s ，i d e a s a n d a p p r o a c h e sp r o v i d e an e we n v i r o n m e n tf 6 rr e s e a r c h i n ga n dd e v e l o p i n g 1 0 a d b a l a n c i n gs y s t e m a i m i n ga t t h ed i s i r i b u i e dl a y e r e dt a s ks c h e d u l i n gm o d e l d e s c r i b e di n t h i s p a p e r ， b yr e s e a r c h i n gt h i ss c h e d u l i n gm o d e l ， a c o m p u t a t i o n a l r e s o u r c es e l e c t i o na l g o r i t h mb a s e do nd o u b l eg o a l sm e a s u r e m e n tf u n c t i o nw a s p r o p o s e d t h ea l g o “t h mm a d ead e t a i lt oe l a b o r a t en i sp a p e re x p l a i n e dt h ef u n c t i o n s a n dt h er e l a t i o n s h i p sb e t w e e nt h ed i f f e r e n tp a r t s0 ft h em o d e la n dg i v et h ea l g o r i t h mo f t h em o d e l t h ep a p e ru s e sg r i d s i ms i m u l a t i o nt o o lt ov a l i d a t e dt h i sm o d e l ，s i m u l a t i o n r e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mp e r f b n t l sb e t t e rl h a n o t h e rs c h e d u l i n g a l g o “t h mi nh e t e r o g e n e o u s 伊i d h o n g b i nz h a n g ( c o m p u t e rs o f t w a r ea n dt h e o r y ) d i r e c t e db yv i c ep r o f b i nl u k e yw o r d s ： g r i dc o m p u t i n g ，h i e r a r c h i c a i ， t a s k s c h e d u i i n g ， l o a d b a l a n c i n g 华北电力入学硕十学何论文摘要 摘要 随着网格技术的飞速发展，有关资源分配与任务调度的研究面临着新的机遇 和挑战。这些新的技术、概念和方法提供了更新的环境来研究和发展面向负载平 衡的作业调度系统。针对层次化网格模型结构，运用统计思想提出了一种新的资 源分配与任务调度算法，不仅能够提高资源的利用率和系统的吞吐率，而且能够 实现网格系统内部的负载平衡。算法对负载信息预测、负载平衡收益和丌销、作 业分配以及性能标准做了详细的阐述。在解释了方案中各功能部件的作用及其相 互之问关系的基础上，给出了相应的算法伪码，仿真实验表明，该算法是有效的。 关键词：网格计算，层次化，任务调度，负载平衡 a b s t r a c t a sg r i dt e c h n o l o g i e se v o l v eq u i c k i yo ni n t e t l l e t ，l o a db a l a n c er e s e a r c ha n d d e v e l o p m e n tf a c en e wo p p o n u n j t i e sa n dc h a l l e n g e s t h e s en e wt e c h n o l o g i e s ，i d e a s a n d a p p r o a c h e sp r o v i d e an e we n v i r o n m e n tf 6 rr e s e a r c h i n ga n dd e v e l o p i n g 1 0 a d b a l a n c i n gs y s t e m a i m i n ga t t h ed i s i r i b u i e dl a y e r e dt a s ks c h e d u l i n gm o d e l d e s c r i b e di n t h i s p a p e r ， b yr e s e a r c h i n gt h i ss c h e d u l i n gm o d e l ， a c o m p u t a t i o n a l r e s o u r c es e l e c t i o na l g o r i t h mb a s e do nd o u b l eg o a l sm e a s u r e m e n tf u n c t i o nw a s p r o p o s e d t h ea l g o “t h mm a d ead e t a i lt oe l a b o r a t en i sp a p e re x p l a i n e dt h ef u n c t i o n s a n dt h er e l a t i o n s h i p sb e t w e e nt h ed i f f e r e n tp a r t s0 ft h em o d e la n dg i v et h ea l g o r i t h mo f t h em o d e l t h ep a p e ru s e sg r i d s i ms i m u l a t i o nt o o lt ov a l i d a t e dt h i sm o d e l ，s i m u l a t i o n r e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mp e r f b n t l sb e t t e rl h a n o t h e rs c h e d u l i n g a l g o “t h mi nh e t e r o g e n e o u s 伊i d h o n g b i nz h a n g ( c o m p u t e rs o f t w a r ea n dt h e o r y ) d i r e c t e db yv i c ep r o f b i nl u k e yw o r d s ： g r i dc o m p u t i n g ，h i e r a r c h i c a i ， t a s k s c h e d u i i n g ， l o a d b a l a n c i n g 声明户叫 本人郑重声明：此处所提交的硕士学位论文基于统计思想的层次化网格负 载平衡调度算法，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行 的研究工作和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得华北电 力大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：日 期： 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有 权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩 印或其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅； 学校可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方 式在不同媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名： 日期： 导师签名： 日期： 华北电力人学硕+ 学位论文 1 1 研究背景 第一章引言 网格技术是近年来迅速兴起的一门新技术，它的出现掀起了下一波互连网技术 的浪潮。计算网格作为网格技术最早也是最主要的应用，目前己成为国内外研究的 热点。它最初的目标是通过互连网将超级计算机联合起来，解决复杂大型科学计算 问题；现在，这一目标已演变为通过互连网将分布在各地的各种不同类型的计算机 以合理的方式“粘合”起来，形成高度集成的有机整体，向普通用户提供强大的计 算能力，将i n t e r n e t 变为一个功能强大、无处不在的计算设施，使人们在使用网 格计算能力时就像现在使用电力一样方便。 网格计算是伴随着互联网技术而迅速发展起来的，最初它只是专门针对复杂科学计 算的新型计算模式。这种计算模式是利用互联网把分散在不同地理位置的计算机组织成 一个“虚拟的超级计算机”其中每一台参与计算的计算机就是一个“节点”，而整个计 算是由成千上万个“节点”组成的“一张网格”，所以这种计算方式叫网格计算。这样 组织起来的“虚拟的超级计算机”有两个优势，一个是数据处理能力超强：另一个是能 充分利用网上的闲置处理能力。简单地讲，网格是把整个网络整合成一台巨大的超级计 算机，实现计算资源、存储资源、数据资源、信息资源、知识资源、专家资源的全面共 享。同时，随着网格技术的推广，网格服务市场逐渐形成，计算网格提供的计算能 力演变为一种像电视、电信、供水、供电这样的资源服务，人们在使用网格提供的 计算能力时必须购买。然而，在网格环境中，有大量不同需求的应用和大量广域分 布的计算资源，这些资源没有全局的控制中心和统一的价格机制，且动态变化。这 样，网格调度就不仅要考虑如何按时完成用户的应用，同时还要考虑如何协调资源 提供者和需求者之间的利益比1 。 随着网格计算的出现，由于网格资源是地理上分布的、异构的、隶属于不同的 机构或个人各类计算资源，作业调度者没有直接分配资源的能力，此时，需要一些 新的作业调度模式和调度算法来对网格中的任务进行调度。由于网格中的资源是动 态变化的，包括资源的动态加入或者退出，资源提供者不同时间对资源的要求不同， 都会引起资源的不断变化，网格作业调度应该适应网格中的资源特性。目前的调度 算法大多都是基于作业的历史运行信息来作为作业调度的一个衡量指标，而且大多 数作业调度算法并不考虑资源的动念变化。由于网格系统是个大规模系统，资源管 理都是由资源提供者本身来操作的，很容易由于不可预测的原因导致资源不可用， 此时，如果有作业在不可用资源上运行，需要对这些作业进行迁移。在网格中作业 运行常常会遇到的问题有： 华北电力人学硕+ 学位论文 ( 1 ) 由于资源的不断变化而引起的负载不均衡问题。 ( 2 ) 由于资源的不可用、资源不足、资源退出而引起的作业迁移问题。 研究这些问题对网格的作业调度具有非常重要的意义。 1 2 网格的研究现状 目前网格的研究主要集中在美国和欧洲。英国政府己投资l 亿英镑，用来研制 “英国国家网格( u kn a t i o n a lg r i d ) ”。欧洲的d a t ag r i d 涉及到欧盟的2 0 几个 国家，是一种典型的“大科学”应用平台。目前美国和欧洲在美国政府用于网格技 术基础研究经费则已达5 亿美元。美国军方j 下规划实施一个宏大的网格计划，叫做 “全球信息网格( g l o b a li n f o r m a t i o ng r i d ) ”，预计在2 0 2 0 年完成。美国政府电 子信息技术协会的一位负责人预测，到2 0 0 6 年，g i g 有可能成为五角大楼的最大投 资项目。作为这个计划的一部分，美国海军和海军陆战队己启动了一个耗资1 6 0 亿 美元历时8 年的项目，包括系统的研制、建设、维护和升级。除了上述国家级的项 目和系统外，很多世界著名的公司也都非常关注网格的发展。惠普、i b m 、微软、 s u n 等公司最近取得共识，支持x m l 、s o a p 、u d d i 等标准，从而更有利于丌发新一 代的网络应用，即网格服务。其目的是将互联网上的资源和信息汇聚在一起，组合 成企业和消费者所需要的服务。惠普推出了e s p e a k 服务平台；i b m 用它的 w e b s p h e r e 平台和一系列中间件实现力维网服务；微软的路线是通过其n e t 计划和 c # 语言实现；s u n 则通过o p e nn e t w o r ke n v i r o n m e n t ( s u no n e ) 计划和j a v a 平台 来实现它。另外，i b m 己经宣布将投资4 0 亿美元，启动一个“网格计算创新计划”， 而s u n 则在2 0 0 0 年9 月就公布了其网格引擎软件。 在国内，网格研究f 在迅速展开，主要有中科院牵头的“国家高性能计算环境 n h p c e ”项目、由教育部支持的重点项目“先进计算基础设施北京上海试点工程”、 8 6 3 计划支持的“中国网格( c h i n ag r i d ) ”、“上海教育科研网格”、由航天二院和 清华大学共同丌展“仿真网格 的研究、由中科院计算所领衔丌发“织女星网格”。 在调度方面，较典型的是中科院计算所在实际网格项目提出的系列调度方法。 然而，由于网格技术本身不成熟，这些研究还处于发展阶段，比较随意，缺乏 系统的理论研究和客观实用的评价标准，因此还需要更多的机构和个人加入研究来 推动网格调度应用的发展。 网内的网格计算尚处于研究阶段，主要集中于中科院计算所、国防科大、江南 计算所、清华大学、山东大学等几家在高性能计算方面有较强实力的研究单位。目 前，我国已启动了五个网格项目，科技部负责的中国国家国格( c n g r i d ) 、教育部负 责的中国教育科研网格技术( c h i n a g r i d ) 、国家自然科学基金委负责的e s c i e n c e 网格研究计划、上海信息网格、中国空间信息网格。其中，中国国家网格( c n g r i d ) 2 华北电力火学硕+ 学位论文 由国家8 6 3 高技术研究发展计划资助，旨在建立面向企业、高等院校、科研机构、 政府部门的国家高性能计算环境。中国教育科研网格项目是“c e r n e t 高速地区网 和重点学科信息服务体系建设 项目中的重要建设内容，是迄今为止由政府推出的 最宏大的网格工程。c h i n a g r i d 的目标是在2 0 0 5 年建立聚合能力超过1 5 万亿次量 级的教育科研网格，形成世界上最大的超级网格之一，并争取在网格计算的基础研 究和应用研究方面走在世界前列。分析目前的研究和应用现状，网格计算应在以下 几个方面重点丌展工作： ( 1 ) 网格安全由于可扩展性的要求，性能和异构是任何分布式系统的奋斗目 标，但网格计算的特点导致了在分布式系统中已有的安全技术尚不能解决的问题。 网格应用所涉及的大量资料和计算内容在各组织之间是否能安全共享，内部系统环 境中一些常常被忽略掉的问题，如安全和可靠性等，在任何分布式环境下都必须得 到解决。 ( 2 ) 资源监视确定并监测网格资源状况，收集任务运行时的资源占用数据。 用户提交的任务要由系统来分配资源并控制其运行，包括要将其分配到哪些主机上 运行、调用哪些数据、启动何种应用程序、何时丌始运行等。 ( 3 ) 资源管理为了使网格的性能达到最佳，需要管理信息在网格中分配的方 式。如何分配工作、工作传输的频率、以及它分配给每一个客户机的方式都会影响 服务器的负载、网络的负载，并最终影响网格的性能。通过精心管理，如控制工作 单元分配、在代理端保持记录以及分析每一个客户机的性能，应当可以使网格的性 能达到最大化。通过管理服务器( 将作业提交给网格的工作代理) 和客户机( 所需 资源的提供者) 的带宽，应当能够使网格环境的性能达到最大化，同时防止过度使 用网络、c p u 和其他资源。 ( 4 ) 任务调度在网格系统中，大量的上层应用共享着网格的各种资源。如 何使得这些应用获得最大的性能以及使得整个网格系统的效率达到最高( 例如最大 吞吐率等) ，这就是网格调度所要解决的问题。良好的调度是实现高效使用共享资 源的重要环节。通过调度，可以把应用所需的计算隐藏于网格中，降低了上层应用 的复杂性，使用户不必关心任务所需的计算放在什么地方去执行从而把更多的精力 投入到业务本身的开发中。 综上所述，网格计算方面进行研究和探索的内容是极其丰富和具有挑战性的， 资源管理是网格的核心服务层技术，包括网格资源管理和分配、网格资源信息服务、 网格资源发现与监视、网格资源需求描述等方面n 1 。 3 华北电力人学硕十学位论文 1 3 网格的特点 网格是在网络的高速发展的基础上出现的，但网格不是网络，两者之间是有 区别的。网格是在网络之上运行的软件基础设施，是连接、集成不同硬件系统、软 件系统、应用系统的纽带和粘接剂：网络是网格的物理基础，没有高性能网络，网 格的形态也较难体现：网格对网络的发展有推动作用。网络和网格是不同层次的事 物，网格是直接支撑应用的，而网络主要实现系统问的高效灵活的数据传输，二者 不是相互取代的关系。从另一个角度看网格是网络基础上的高级应用：网络解决的 是信息传输的问题，而网格则是解决信息处理的问题：网格的实质，就是共享与协 作，即在多个机构动态形成的虚拟组织中共享资源和协同解决问题。通俗一点讲就 是处在网格环境中的所有计算机硬件资源与软件资源的共享，硬件与软件的动态协 作，完成一个共同的目标。网格的主要特点如下： ( 1 ) 分布与共享分布性是网格的一个重要的特点。网格的分布性首先指网格的 资源是分饰的。组成网格的计算能力不同的计算机，各种类型不同的数据库乃至电 子图书馆，以及其它的各种设备及资源，是分布在地理位置互不相同的多个地方， 而不是集中在一起的。因为网格资源是分布的，所以基于网格的计算一定是分布式 计算而不是集中式计算。在网格这一分布式环境下，需要解决资源和任务的分配和 调度问题，安全传输和通信问题，实时性保障问题，人与系统以及人与人之问的交 互问题。网格资源虽然是分布的，但它们却是可以充分共享的。即网格上的任何资 源都可以提供给网格上的任何一个使用者。共享是网格的目的，没有共享就没有网 格，解决分布资源共享问题，是网格的核心问题。 ( 2 ) 异构性( h e t e r o g e n e i y t ) ：网格可以包含多种异构资源，包括跨越地理分布 的多个管理域。构成网格计算系统的超级计算机有多种类型，不同类型的超级计算 机在体系结构、操作系统及应用软件等多个层次上可能具有不同的结构。 ( 3 ) 动态性和多样性对网格来说，绝对不能将它看作一成不变的。原来拥有的 资源或者功能，在下一时刻有可能出现故障或者不可用：而原来没有的资源，可能 会随着时间的推移不断地加入进来。网格的动态性即资源的动态加入和退出。 网格资源的动态变化特点要求网格管理必须考虑并解决好这一问题，对于网格 中的资源故障或者动态减少的情况，要求网格能够及时采取措施，实现任务的自动 迁移，做到对高层用户透明或者尽量减少损失。 网格资源的动态增加需要提高网格的扩展性问题，也就是说在网格的设计与实 现时，必须考虑到新的资源能否自然的加入到网格中来，并且可以和原来的资源融 合在一起，共同发挥作用。网格扩展要求体现在规模、能力、兼容性等几个方面。 网格资源是异构和多样的。在网格环境中可以有不同体系结构的计算机系统和 类别不同的资源，因此网格系统必须能够解决这些不同结构，不同类别资源的通信 4 华北电力人学硕十学位论文 和互操作问题。正是异构型和多样性的存在，为网格软件的设计提出了更大的挑战， 只有解决好这个问题，才会使网格更具有吸引力。 ( 4 ) 可扩展性( s c a l a b i l i y t ) ：网格可以从最初包含少数的资源发展到具有成千 上万资源的大网格。由此可能带来的一个问题是随着网格资源的增加而引起的性能 下降以及网格延迟，网格必须能适应规模的变化。 ( 5 ) 可适应性( a d a p t a b i1 i t y ) ：在网格中，具有很多资源，资源发生故障的概 率很高。网格的资源管理或应用必须能动态适应这些情况，调用网格中可用的资源 和服务来取得最大的性能。 ( 6 ) 结构的不可预测性：动态和不可预测的系统行为。在传统的高性能算系统 中，计算资源是独占的，因此系统的行为是可以预测的。而在网格算系统中，由于 资源的共享造成系统行为和系统性能经常变化。 ( 7 ) 自治性和管理多重性 网格上的资源，首先是属于某一个组织或者个人的， 因此网格资源的拥有者对该资源具有最高级别的管理权限，网格应该允许资源拥有 者对他的资源有自主的管理能力，这就是网格的自主性。 但是网格的资源也必须接受网格的统一管理，否则不同的资源就无法建立相互 间的联系，无法实现共享和互操作，无法作为一个整体为更多的用户提供方便的服 务。 ( 8 ) 多级管理域由于构成网格计算系统的超级计算机资源通常属于不同的机构 或组织并且使用不同的安全机制，因此需要各个机构或组织共同参解决多级管理域 的问题。 1 4 网格的基本要求 从i a n f o s t e r 等对网格的定义来看，网格作为一个大型的系统，其基本要求主 要有以下几点： ( 1 ) 可靠性：网格的可靠性是指网格提供的计算能力必须保证是持续、稳定和 安全的，不应该因为网格内部个别资源的变化而对网格应用造成影响，即网格内部 局部资源的变动对网格应用应该是透明的。 ( 2 ) 标准化：标准化的一方面是指网格资源之问应该有一个统一的可以相互访 问标准化的接口或者协议标准。标准化是共享的前提。另一方面是网格对用户提供 的计算能力应满足一定的标准，有一种比较统一的形式，从而便于以一种统一的方 式进行访问。 ( 3 ) 易访问：网格的易访问性是指用户可以在任何时间、任何地点、以自己习 惯的统一的方式访问和使用各种资源。 ( 4 ) 低廉性：网格费用的低廉性是网格能够被普遍接受的前提。网格技术通过 5 华北电力火学硕+ 学位论文 将资源共享，最大限度的发挥资源的使用价值，不仅可以将原来闲置和浪费的资源 收集起来供用户使用，而且可以减少以前由于地理位置限制所带来的各种额外丌 销。 1 5 本文的研究意义 网格技术是现代高科技发展的必然产物，从生物领域的后基因组计划的解读： 到高性能物理领域更深层次物理结构的研究：再到哈勃望远镜所获取的大量宇宙数 据：再到气象、地震预报预测。这些重大科学领域的计算问题促成科学家要利用分 布在世界各地的计算机资源，通过高速网络连接起来，共同完成计算问题。网格技 术已经引起了欧美乃至世界上大部分国家科学界的极大兴趣，各行各业都在积极参 与到网格技术的丌发应用中。由此可见对于网格的研究仍是未来几年的热点。 网格计算不仅仅是一种暂新的计算模式和理念，网格计算所依托的网格概念可 以说是一个新型平台。在网格计算平台上，原先只能使用超级计算机或者集群才可 以解决的高性能计算问题可以通过普通的p c 机来解决。 由于网格系统中的资源不断变化，被映射到资源中的作业在运行的过程中难免 会出现负载不均衡，如果能够提供动态负载平衡，将能够改善网格系统的资源利用 率，提高系统的吞吐率。当网格中的资源提供者希望退出网格系统的或者资源出现 不可用的时候，此时，如果能够提供作业的动态迁移，就不需要作业重新提交，提 高系统的透明性和容错性。因此对网格中动态负载平衡和作业迁移将是非常具有意 义的事情。 1 6 文章结构 本文的总体结构大体分为三个部分：第一部分理论研究，主要包括第一至第三 章：第二部分系统实现，主要为第四至第六章；最后第七章，总结全文。具体的内 容安排如下： 第一章首先简单介绍了网格计算的应用和研究背景；讨论了当前的网格的研究 现状和存在的问题；接着阐述了本文要研究和解决的问题以及采用的研究策略。 然后重点针对计算资源管理模型、计算任务调度算法代表系统这几个计算网格 的关键技术， 第二章概述了基于网格技术的基础包括网格作业管理、任务调度、的资源发现 管理模型，然后针对其核心模块进行了详细的说明，最后定性地论述了该模型的优 点。 第三章为提出了重载、适度负载和轻载的定义，比较了各种负载平衡策略的优 缺点，提出一种层级式动态负载平衡系统，并且详细介绍了它的组成结构和工作流 6 华北电力人学硕十学位论文 程，最后，对层次化模型进行定量的分析。 第四章为本文的重点和核心。结合层级式动态负载平衡系统的架构模式和相关 技术，设计出更科学的动态双阈值负载平衡系统的算法的实现模型，并对其运行结 构、体系结构、组成部件进行说明，随后介绍了网格模拟器g r i d s i m 。 第五章在作业的运行过程中难免会出现资源不可用，此时需要对作业进行迁 移。对作业迁移条件及问题作业迁移时的选择策略、性能评价进行了研究。 第六章本文提出算法在网格模拟器g r i d s i m 中进行了仿真实验，并与m i n m i n 算法进行了性能比较，模拟实验结果表明，在网格异构环境下，该算法优于其它算 法 第七章对整篇论文进行总结，并对未来工作进行展望。 7 华北电力人学硕十学位论文 2 1 网格体系结构 第二章网格理论基础技术研究 网格体系结构就是关于如何建造网格的技术。它给出了网格的基本组成与功 能，描述了网格各组成部分的关系以及它们集成的方式或方法，刻画了支持网格有 效运转的机制。 网格体系结构可以说是一个“分与“合”的统一体。网格是一个整体的概念， 网格体系结构的作用在一定程度上就是对于网格的剖析。所谓的”分”是指网格体 系结构必须能够标识出网格的基本组成成分，能够清楚地说明网格整体是由哪些关 键部分结合在一起而形成的，还能够对各部分的功能、目的和特点等进行清晰地描 述。在“分”的基础上，网格体系结构还要进一步描述“合”的功能，即在充分了 解网格的各个部分的作用机理、作用方式的基础上，将这些部分按照一定的方式进 行组织和集成，形成一个具有特定功能的整体，对外提供服务。 到目前为止，比较重要的网格体系结构有两种，一种是f o s t e r 等在早些时候 提出的五层沙漏结构：另一种是以i b m 为代表的工业界的影响下，在考虑到w e b 技 术的发展与影响后，f o s t e r 等结合w e bs e r v i c e 提出的开放网格服务结构( o p e n g r i ds e r v i c e sa r c h i t e c t u r e ) 。下面将分别加以介绍。 2 1 1 五层沙漏模型 ( 1 ) 五层划分 五层沙漏结构并不提供严格的规范，它不是对全部所需协议的完整罗列，而是 对该结构中各部分组件的通用要求进行定义。将这些组件形成一定的层次关系，每 一层的组件具有相同的特征，上层组件可以在任何一个底层组件的基础上建造。图 2 1 为五层沙漏结构 图2 一l 五层结构及其与t c p i p 网络协议的对比 在五层沙漏结构中，最底层是构造层。构造层面对的是一个个具体的物理( 也 8 回回 华北电力人学硕十学位论文 可以是逻辑的) 资源，它通过对这些局部资源的管理，向上层提供对这些资源的管 理和控制界面。构造层的上面是连接层，主要是为下层的物理资源提供安全的数据 通信能力，这是资源之间进行互操作的前提，连接层使得孤立的单个资源之间建立 了联系。连接层的上面是资源层，它反映的是抽象的局部资源特征。资源层的上面 是汇聚层，它的功能是将下面以单个资源形式表现出来的资源集中起来，协调处理 多个资源。最上面的应用层和资源的距离最远，它关心的是有什么样的资源可以由 下面提供给虚拟组织，解决不同虚拟组织的具体问题。 ( 2 ) 沙漏形状 五层结构另外一个重要特点是沙漏形状。其内在含义就是因为各部分协议的数 量是不同的。对于其最核心的部分，要能够实现上层各种协议向核心协议的映射， 同时实现核心协议向下层其它各种协议的映射。核心协议在所有支持网格计算的地 点都应该得到支持，因此核心协议的数量不应该太多，这样核心协议就形成了协议 层次结构中的一个瓶颈。在五层结构中，资源层和连接层共同组成这一核心的瓶颈 部分，如图2 2 所示。 图2 2 沙漏形状的五层结构 沙漏的核心思想可以和微内核的操作系统进行类比，即操作系统只实现一些关 键的基本功能，而把大量与特定设备有关和应用相关的部分交给其它部分来完成。 一个小的核心是有利于移植的，也可以比较容易地实现和得到支持饰1 。 2 1 20 g s a 的架构 o g s a 的系统架构，从下到上，0 g s a 框架可分成四层 ( 1 ) 资源。物理和逻辑资源层资源的概念是o g s a 的中心部分。构成网格能力 的资源并不仅限于处理器。物理资源还包括服务器、存储器和网络等等。物理资源 之上是逻辑资源。它们通过虚拟化和聚合物理层的资源来提供额外的功能。通用的 中间件，比如文件系统、数据库管理员、目录和工作流管理人员，在物理网格之上 提供这些抽象服务。 ( 2 ) w e b 服务。在o g s a 中，所有网格资源( 逻辑的与物理的) 都被建模为服务。 o g s i 规范定义了网格服务并建立在标准w e b 服务技术之上。o g s i 利用诸如x m l 与 w s d l 等w e b 服务机制，为所有网格资源指定标准的接口、行为与交互。o g s i 进一 q 华北电力人学硕十学位论文 步扩展了w e b 服务的定义，提供了动念的、有状态的和可管理的w e b 服务的能力， 这在对网格资源进行建模时都是必需的。 ( 3 ) 基于o g s a 架构的网格服务。w e b 服务层及其o g s i 扩展为基于架构的网格 服各提供了基础设施，g g f 目前正在致力于在诸如程序执行、数据服务和核心服务 等领域中定义基于网格架构的服务。随着这些新架构的服务开始出现，0 g s a 已变成 更加有用的面向服务的架构( s o a ) 。 ( 4 ) 网格应用程序层。丰富的基于网格架构的服务正在不断被丌发出来，使 用一个或多个基于网格架构的服务的新网格应用程序办将出现。这些应用程序构成 了o g s a 架构的第四层。 在o g s a 的结构中，o g s a 的两个主要逻辑组件是w e b 服务加上0 g s l0 p e ng r i d s e r v i c ei n f r a s t r u c t u r e ) 层和基于o g s a 架构的服务层1 。 相对于前面的五层沙漏结构，o g s a 更侧重从网格提供服务出低到高对网格进 行层次分解，体现了其s o a 的特性。但在其具体实现中，0 g s a 要利用五层沙漏结构 提供的协议分层来对功能进行划分，提供更好的代码重用和服务接口等特性。事实 上，每一层都需要协议来提供对相关服务的访问，包括资源管理，数据存取，资源 发现等。 2 2 网格作业管理 作业方式是使用网格资源的一种形式，它根据用户确定的流程，为用户提供使 用资源的功能。网格作业一般都是在远端节点上运行，作业提交者对远程设备的控 制能力是非常有限的，为了有效的管理作业的运行，就需要网格作业管理机制，管 理整个作业的运行过程。在网格计算平台下，作业管理机构还要具备作业迁移管理、 作业任务分解等一些特殊功能。 2 2 1 作业描述 作业描述是为网格作业管理机构提供完成作业请求的必要信息。在网格环境 下，一个作业的构成部分可能分散在不同的节点上，为了在作业运行过程中顺利的 找到需要的文件、程序等，需要有统一的描述方式。描述可以有填写表格和编写作 业描述文件等不同方式，但是都需要支持描述的介质。最早具有这种功能的描述是 批处理系统的作业描述。 作业描述语言 1 c 1 a s s a d s c 1 a s s a d s ( c l a s s i f i e da d v e r t i s e m e n t s ) 是c o n d o r 的一种描述语言，该描述语 言可以描述作业、工作站和其他资源。调度作业时，c o n d o r 的不同部分之间交换 c l a s s a d s 信息。该语言的基本表示形式是属性名到表达式的一个映射。最简单的情 l o 华北电力人学硕十学位论文 况，表达式是一个常数，包括整数、浮点数、字符串等。复杂表达式可以表示为更 复杂的含义。一个c 1 a s s a d s 文档就是一个属性列表。c 1 a s s a d s 的语法允许动态更 新限制，比如，在没有可用的大存储器、c p u 的情况下，可以降低要求：一个作业 如果需要等待更长时间才能够执行，可以增加等待执行的时间。c l a s s a d s 的语法提 供了大量必须或者可选属性。下面是个作业描述的例子： m y t y p e = “m a c h i n e ， t a r g e t t y p e = “j o b n a m e = “l x l j l u e d u c n ” m a c h i n e = “l x l j l u e d u c n ” a r c h = “i n t e l u i d d o m a i n = j l u e d u c n 0 p s y s = “w i n d o w sx p ” d is k = 6 0 g v i r t u a lm e m o r y = 1 8 3 4 6 4 m i p s = 2 0 1 r e q uir e m e n t = t a r g e t o w n e r = = “1xl ”l o a d a v g 1 5 木6 0 作业分配是个复杂过程，需要把提交者的资源需求和资源提供者的资源进行动 态匹配，匹配过程根据具体情况可能很快，也可能很慢。c 1 a s s a d s 支持诸如机器名 字等永久资源和c p u 速度、类型等半永久资源及空闲存储空间等变化资源的描述。 2 作业描述语言j d l 欧洲数据网格采用作业描述语言( j o bd e s c r i p t i o nl a n g u a g e ) 描述作业。j d l 采用c 1 a s s a d s 属性表的形式来描述作业，其中每个属性都是通过该属性的值或者 简单表达式定义的。该语言有丰富的时间功能、字符串处理功能和一些数学功能。 作业描述语言包含资源属性和作业属性两种信息。资源属性指存储器、c p u 时间、 本地资源管理类型( c o n d o r ，p b s ，) 等盯3 ；作业属性包括执行文件、输入沙箱、输 出沙箱、输入数据、副本目录等。下面是个简单的j d l 文件： ( e x e c u t a b l e = a o u t ) ( dir e ct o r y = h o m e n o b o d y ) ( a r g u m e n t s = a r 9 1 ”a r 9 2 ”) ( c o u n t = 1 ) ( p h y sic a l m e m o r y 12 8 ) ( m i p s 1 5 ) ( e x p e c t e d r u n t i m e = 5 0 0 ) 这个作业描述语言描述了一个作业的基本信息，这个作业的可执行文件是 a o u t ，存在的目录是h o m e n o b o d y ，这个作业需要a r 9 1 ，a r 9 2 参数，需要的物理 内存大于1 2 8 m ，c p u 的要求是大于1 5 m i p s ，预计运行的时间是5 0 0 秒。 1 1 华北电力人学硕十学位论文 2 2 2 作业调度 作业调度是作业管理器的主要功能之一，作业管理器管理作业的不同状态，负 责作业在不同状态之问的调度。由于网格资源具有自治特性，网格作业调度不能剥 夺资源本地对作业的管理权力，它与资源本地的作业调度要协同工作，共同完成网 格用户提交的网格作业的调度，为网格用户充分利用计算资源提供方便。在网格环 境下，满足某个作业要求的计算资源可能不止一个，但是该作业在这些资源上执行 获得的性能、付出的代价可能不一样。同样都是满足条件的资源，但提供给使用者 的服务质量会存在差异，有时这种差异会很大。作业调度首先要根据作业的需求， 发现满足条件的计算资源；然后从满足条件的计算资源中根据主要因素或者选择策 略选择一个合适的资源，分配给该作业；作业获得满足条件的资源之后，可以在这 个资源上运行，并在资源本地的作业管理机制的管理之下：作业在资源执行结束之 后，把占用的资源还给网格管理机构，网格作业管理模块把作业执行结果和有关信 息告诉作业提交者1 。网格作业调度需要排队管理机制，用户提交的作业进入等待 调度的作业队列，用户很快就得到了响应，具体的调度在等待的作业队列上进行。 一个等待队列中的不同作业对资源的需求情况可能不同，等待队列中排在前面的作 业，目前可能没有满足条件的空闲资源可用，需要继续等待；但是排在等待队列中 后面的作业有可能有了可用空闲资源，可能需要从等待队列中移出。作业调度机构 要从等待调度的作业队列中选择合适作业进行调度。 2 2 2 1 网格计算中调度的目的 虽然现有的网格项目在体系结构和需要解决的问题类型等方面不尽相同，但它 们的本质内容都是共享与协作，基本上都需要一些共同的关键技术，例如网格调度 技术。在网格系统中，大量的上层应用共享着网格的各种资源。如何使得这些应用 获得最大的性能以及使得整个网格系统的效率达到最高( 例如最大吞吐率等) ，这 就是网格调度所要解决的问题。良好的调度是实现高效使用共享资源的重要环节。 通过调度，可以把应用所需的计算隐藏于网格中，降低了上层应用的复杂性，使用 户不必关心任务所需的计算放在什么地方去执行从而把更多的精力投入到业务本 身的开发中。对于一个调度系统，从应用的角度来说，用户关注的是它给应用带来 的等待时间、执行时间等指标；而从系统的角度来说，管理员关注的则是它导致的 系统吞吐率、负载平衡等指标。这两方面的指标有时候并不能达到完全一致，这就 给网格调度带来了多种可能性，出现了种类繁多的调度系统。网格调度技术比传统 高性能计算中的调度技术更复杂，这主要是因为网格具有一些独有的特征，例如， 网格资源的动态变化性、资源的类型异构性和多样性、调度器的分布和局部管理性 等。在网格调度中，还需要考虑移植性、扩展性、效率、可重复性以及网格调度和 1 2 华北电力人学硕十学位论文 本地调度的结合等一系列问题。 2 2 2 2 作业调度种类 由于网格资源可提供的本地作业管理机制不同，网格作业调度器向本地作业管 理器提交作业的种类： ( 1 ) 独占型资源，该资源接受一个作业运行完成之后，再从网格作业管理器 那旱接收新的作业。这种情况不支持多个作业的分时共享，资源本地不需要维护网 格作业队列，但网格作业调度器需要为该资源维护一个作业队列，把提交给该资源 的网格作业排在队列中。该资源上的作业完成顺序由网格作业调度器决定。 ( 2 ) 一个资源一次可以最多接收不超过规定数目的n 个网格作业。在这种情 况下，资源本地需要维护一个不超过n 的网格作业队列，如果分配给该资源的作业 数目不超过规定的数目n ，所有分配给该资源的作业都进入本地维护的作业队列。 但是，如果分配给该资源的作业超过了规定数目n ，网格作业管理器就要为该资源 维护一个网格作业队列，把不能进入本地网格作业队列的其它网格作业维护在网格 作业调度器的队列中呻1 。网格作业管理器和资源本地的作业管理器都需要在自己的 队列上进行调度。 ( 3 ) 一个资源可接受的作业数目不受限制，资源本地的作业管理器需要维护 一个足够长的作业队列，需要容纳下提交给该资源的所有作业，网格作业管理器不 需要为该资源维护作业队列。该资源上作业完成先后顺序基本上取决于资源本地的 作业管理器的调度策略。 用户把作业提交给网格作业管理器之后，作业进入网格作业管理机构维护的作 业队列。网格作业调度模块从作业队列中选择合适的作业分配到合适的资源上运 行。在网格作业的整个生命周期中，作业要经历不同的作业状念。网格作业可能离 丌一个队列，然后进入另外一个队列，由于某种事件的发生，作业状念从一种状态 转变为另外一种状态，作业调度模块负责管理作业从一种状态改变成另外一种状 态。 2 2 2 3 作业调度策略 作业调度包含两个组成部分，一个是等待队列中某个作业找到合适计算资源的 调度，称为匹配调度；另一个是从等待队列中选择一个合适的作业首先进行处理的 调度，称为次序调度。匹配调度是处理一个作业与多个资源的关系，次序调度是处 理多个作业之间的关系0 i 。次序调度是从多个作业中选择谁先谁后的调度，有了次 序调度，网格作业得到服务的顺序就不一定与作业提交的顺序一致。 (