（计算机应用技术专业论文）基于拍卖机制的网格作业调度遗传算法研究.pdf

太原理工大学硕士研究生学位论文 基于拍卖机制的网格作业调度遗传算法研究 摘要 网格计算属于分布式计算的一种，但是由于网格资源在广域上分布、 本质上异构、归属不同的人和组织拥有、相异的存取和花费模式、负载和 可用性动态变化，因此网格计算环境远比传统的分布式计算环境复杂。这 就使得针对传统的分布式计算环境设计的资源调度策略在网格环境中并不 理想。这主要表现为不能很好的预测网格环境中动态的资源变化，不能全 面考虑网格环境对作业或者资源所设的限制，没有充分考虑网格环境中资 源耗费对网格资源调度的影响等一系列问题。 本文提出了基于拍卖机制的在线信誉网格资源管理模型，是基于计算 经济网格的资源管理模型，为资源提供者提供了贡献与共享资源的动机， 吸引更多更好的资源加入网格，实现资源优化分配。保证交易双方均获取 最大利益，有利于网格资源的市场管理及供需均衡。 本文设计了基于遗传算法( g e n e t i ca l g o r i t h m ) 的网格作业全局调度策 略。在算法中，引入了时间和花费两方面经济因素，用户可以设置不同的 影响因子，将两个因素综合考虑进去，根据用户需求得到最优化的资源分 派策略，从而提高网格系统的总体性能。 基于g r i d s i m 工具包构建网格仿真环境，该仿真环境已经包含了通常 的网格环境中所需的所有基本因素。并将本文提出的算法纳入g r i d s i m 模 拟器进行系统测试，测试算法的性能。 太原理工大学硕士研究生学位论文 经测试表明，本文设计的基于遗传算法的网格作业全局调度策略能降 低用户作业的总执行时间和总花费，从而提高网格系统的利用率和性价比。 关键字：网格，拍卖模型，遗传算法，g r i d s i m 模拟器，作业调度 太原理工大学硕士研究生学位论文 r e s e a r c ho ng e n e t i ca l g o r i t h mo fj o b s c h e d u l i n gi ng l u db a s e do na u c t i o nm e c h a n i s m a b s t r a c t g r i dc o m p u t i n gi sak i n do fd i s t r i b u t e dc o m p u t i n g b u tt h ee n v i r o n m e n to f g r i dc o m p u t i n gi sm o r ec o m p l e xt h a nt h ee n v i r o n m e n to fd i s t r i b u t e dc o m p u t i n g , s ot h er e s o u r c es c h e d u l i n g p o l i c yw h i c hd e s i g no nd i s t r i b u t e dc o m p u t i n g u n s u i t a b l et h ee n v i r o n m e n to f g r i dc o m p u t i n g f o re x a m p l e ，t r a d i t i o n a lp o l i c y u n a b l ef o r e c a s t r e s o u r c e s d y n a m i cc h a r g e ，t h i n k o v e rt h ec o n f i n e so f r e s o u r c e s j o b s ，t h ec o s to ff i n i s ht h ej o b sa n ds o m eo t h e rp r o b l e m si ng r i d c o m p u t i n g t h i sp a p e rp r e s e n ta l lo n l i n er e p u t a t i o ng r i dr e s o u r c em a n a g e m e n tm o d e l b a s e do na u c t i o nm e c h a n i s m t h i sr e s o u r c em a n a g e m e n tm o d e li sb a s e do nt h e g r i da r c h i t e c t u r ef o rc o m p u t a t i o n a le c o n o m y i tp r o v i d e st h em o t i v a t i o no f r e s o u r c e sc o n t r i b u t i o na n ds h a r ef o rr e s o u r c ep r o v i d e r s ，a n da t t r a c t sm o r eb e t t e r r e s o u r c e st oj o i nf o ra c h i e v i n gt h er e s o u r c eo p t i m a la l l o c a t i o n t h er e s o u r c e m a n a g e m e n tm o d e lg u a r a n t e e sm a x i m u mb e n e f i t sf o rb o t ht r a n s a c t i o ns i d e s ，s o i tc o n t r i b u t e st ot h em a r k e tm a n a g e m e n to f g r i dr e s o u r c ea n db a l a n c eb e t w e e n 1 1 1 太原理工大学硕士研究生学位论文 s u p p l ya n dd e m a n d t h i sp a p e rd i s c u s s e st h ed e s i g nt h eg l o b a ls c h e d u l i n gs t r a t e g yo fg r i dj o b s b a s e do nt h eg e n e t i ca l g o r i t h m i nt h ea l g o r i t h r n , w ei n t r o d u c et w oe c o n o m y f a c t o r sw h i c ha r et i m ea n dc o s t t h ed i f f e r e n ti n f l u e n t i a lf a c t o r sa r es e tb yu s e r , t h e nt h em a t h e m a t i c a lr e l a t i o nb e t w e e nt h et w oe c o n o m yf a c t o r si sd e d u c e d t h r o u g hr e s e a r c h i n gt w of a c t o r s t h ea l g o r i t h mc a na c h i e v et h eo p t i m i z e d r e s o u r c ea l l o c a t i o n s t r a t e g y o nu s e rd e m a n d , t h u si m p r o v et h e s y s t e m s p e r f o r m a n c e ac o n c r e t e g r i d e n v i r o n m e n ti ss i m u l a t e d b yg r i d s i mt o o l k i t s t h e s i m u l a t i o ne n v i r o n m e n th a sc o n t a i n e da l lb a s i cf a c t o r sw h i c ha r en e e d e di n g e n e r a lg r i de n v i r o n m e n t t h eg l o b a ls c h e d u l i n gs t r a t e g yo fg r i dj o bb a s e do n g e n e t i c a l g o r i t h m i st e s t e do nt h es i m u l a t o rg r i d s i mt oe s t i m a t et h e p e r f o r m a c eo fa l g o r i t h m , t h er e s u l t ss h o wt h a tt h eg l o b a ls c h e d u l i n gs t r a t e g yo f g r i dj o bb a s e do n g e n e t i ca l g o r i t h mc a nr e d u c et o t a lp r o c e s s i n gt i m ea n dt o t a l c o s to fl a s e r j o be f f e c t i v e l y , t h e r e b y t h eu t i l i z a t i o n r a t i oa n d p e r f o r m a n c e - t o - p r i c er a t i oo fg r i ds y s t e ma r ei m p r o v e d k e y w o r d s ：g r i d , a u c t i o nm o d e l ，g e n e t i ca l g o r i t h m , g r i d s i ms i m u l a t o r , j o b s c h e d u l i n g i v 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下。 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：二型雾虹日期：址 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定。其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) o 签名：骜监玺 导师签名：垒亟盈 日期：2 迦z 。z 五 日期：趁2 ：( 1 匕 太原理工大学硕士研究生学位论文 1 1 网格概述 1 1 1 网格的概念 第一章引言 网格概念是借鉴电力网提出来的，网格的最终目标是希望用户在使用网格时，就 如同现在使用电力一样方便。最初，网格计算研究的目标是希望将超级计算机连接成 为一个可远程控制的元计算机系统( m e t a c o m p u t e r s ) ；现在这一目标已经深化为建立 大规模计算和数据处理的通用基础支撑结构，将网络上的各种高性能计算机、服务器、 p c 、信息系统、海量数据存储和处理系统、应用模拟系统、虚拟现实系统、仪器设备 和信息获取设备( 如传感器) 集成在一起，为各种应用开发提供底层技术支撑，将i n t e m e t 变为一个功能强大、无处不在的计算设施。它的目标是实现网络虚拟环境下的高性能 资源共享和协同工作，消除信息孤岛和资源孤岛，解决诸如虚拟核爆炸、新药研制、 气象预报和环境等重大科学研究和技术应用领域的问题，而且还能使人们共享和充分 利用网络中的各种资源。 与它相关的技术包括：实时企业信息系统、网络化虚拟设计环境、因特网技术、 知识管理、x m l 技术、a s p 技术、万维网服务( w 曲s e r v i c e ) 、语义网( s e m a n t i cw e b ) 、 高性能计算等。计算网格构想的提出和当前全世界j 下在兴起的有关计算网格的研究， 越来越清楚地使我们感受到一种信息社会的新的基础设施正在出现。它的出现不仅仅 可能带来信息资源的获取、分布、传输和有效利用的革命性的、结构性的巨大变化， 而且将根本改变我们的研究方式、教育方式、生活方式与生产活动的方式。人们普遍 认为“网格最终应该是一种公共事业，- 由网格应用服务商提供服务，这种服务与电话、 电力、水、煤气并列，被称为“第五公用设施”，网格将是继i n t e r n e t 、网页之后的更大 科技进步。 全球网格研究的领军人物、美国阿( a r g o n n e ) 家实验室的资深科学家、美国 太原理工大学硕士研究生学位论文 g l o b u s 项目的领导人i a n f o s t e r 曾在1 9 9 8 年出版的网格：2 1 世纪信息技术基础设 施的蓝图一书中这样描述网格：“网格是构筑在互联网上的一组新兴技术，它将高速 互联网、高性能计算机、大型数据库、传感器、远程设备等融为一体，为科技人员和 普通老百姓提供更多的资源、功能和交互性。互联网主要为人们提供电子邮件、网页 浏览等通信功能，而网格功能则更多更强，让人们透明地使用计算、存储等其他资源。”i l 】 2 0 0 0 年，i a nf o s t e r 在网格的剖析这篇论文中把网格进一步描述为“在动态变 化的多个虚拟组织间共享资源和协同解决问题。”1 2 j 2 0 0 2 年7 月，i a nf o s t e r 在什么是网格? 判断是否网格的三个标准一文中， 限定网格必须同时满足三个条件：( 1 ) 在非集中控制的环境中协同使用资源；( 2 ) 使 用标准的、开放的和通用的协议和接口( i a af o s t e r 认为目前只有g l o b u s 才算得上标准 协议) ；( 3 ) 提供非平凡的服务。这三个条件非常严格，如p 2 p 、s u ng r i de n g i n e 、c o n d o r 、 e n t r o p i a 、m u l t i c l u s t e r 等都被排除在网格之外。 但并不是所有人都同意他的观点，有许多人赞同广义的网格概念，它称作巨大全 球网格g g g ( g r e a tg l o b a lg r i d ) ，它不仅包括计算网格、数据网格、信息网格、知识 网格、商业网格，还包括一些已有的网络计算模式，例如对等计算p 2 p ( p e e rt op e e r ) 、 寄生计算等。i a nf o s t e r 赞成的是一种狭义的“网格观”，而g g g 是一种广义的“网 格观”。虽然人们对网格的认识有待统一，但越来越清晰地认识到网格就是下一代软件 技术，具有全方位的互联互通，强烈地表现出网格整体属性。网格是“虚拟组织”的 实现，是未来的社会信息基础设施，人们未来依赖网格就象现在依赖水电一样。简单 地讲，传统因特网实现了计算机硬件的连通，w 曲实现了网页的连通，而网格试图实 现互联网上应用层面的互联互通，这就意味着所有资源的全面连通，包括计算资源、 存储资源、通信资源、软件资源、信息资源、知识资源等等。 1 1 2 网格的目的和意义 今天的计算机系统效率很低。用户只用到计算机软件的功能的5 ，大部分应用常 常只能得到5 甚至1 以下的利用率。同时，一个趋势是：“人们对性能价格比”的 重视j 下在向“总拥有性能价格比”( t o t a lp e r f o r m a n c e c o s to f o w n e r s h i p ) 过渡，与性能 表面上看起来无关的因素越来越重要( 如互操作性、可移植性、安全性、好用性、易 管理性、高可用性、易部署性) 。网格带来的另一个趋势是：除了速度、响应时间、吞 2 太原理工大学硕士研究生学位论文 吐率等传统指标外，人们正在提出和使用更靠近用户的服务协议等级 ( s e r v i c el e v e l a g r e e m e n t ) 、生产力( p r o d u c t i v i t y ) 、用户价值( v a l u e ) 等新指标。 网格将根本地改变人们对“计算机应用”的看法，这是一种全新的、更方便的计 算方式，能轻松解决现今解决不了的更加复杂的问题： ( 1 ) 突破计算能力的限制：网格可以联合并放大全社会的计算能力，这是目前无 法想象的； ( 2 ) 打破地理物理位置的限制：网格计算能把“全社会的计算能力”送到你的手 中： ( 3 ) 节约资源，现今的计算机资源利用率远不充分，然而很多应用又缺乏资源； ( 4 ) 网格打破了传统共享与协作方面的限制，网格以“虚拟组织”的方法，实现 了全社会范围的资源共享与服务协作。 1 1 3 网格技术发展 发展网格被认为是下一代i n t e r n e t 的核心任务之一，它已经成为各国的研究热点， 例如美国有g l o b u s 、l e g i o n 、c o n d o r 、i p g 等，欧洲有c e r nd a t a g r i d 、u n i c o r e 、 m o l 等，澳大利亚有n i m r o d g 、e c o g d d 等，日本有n i n f b r i c k s 等，中国有国家网 格、上海网格等网格研究项目。 网格技术发展的必然趋势是全球范围内的标准化、技术融合和大型化。 ( 1 ) 标准化趋势2 0 0 4 年1 月，w e bs e r v i c e 标准与o g s a 标准的融合w s r f 框架被提出，将发展成为未来的网格新标准。 ( 2 ) 技术融合趋势g l o b u s 项目组看到了w e bs e r v i c e s 的巨大潜力，在2 0 0 2 年迅 速将g l o b u st o o l k i t 的开发转向了w e bs e r v i c e s 平台，试图用o g s a 在网格世界一统 天下。基于o g s a 之后，网格的一切对外功能都以网格服务( g r i ds e r v i c e ) 来体现，并 借助一些现成的、与平台无关的技术，如x m l 、s o a p ( s i m p l eo b j e c ta c c e s sp r o t o c o l ， 简单对象访问协议) 、w s d l ( w e bs e r v i c ed e s c r i p t i o n l a n g u a g e ，网络服务描述语言) 、 u d d i ( u n i v e r s a ld e s c r i p t i o nd i s c o v e r ya n di m e g r a t i o n ，统一描述发现和集成) 等来实 现这些服务的描述、查找、访问和信息传输等功能。这样，一切平台及所使用技术的 异构性都被屏蔽。用户访问网格服务时，根本就无需关心该服务是c o r b a 提供的， 还是n e t 提供的。 太原理工大学硕士研究生学位论文 ( 3 ) 大型化趋势美国政府单在网格技术的基础研究上，每年投入的经费就高达5 亿美元。i b m 在2 0 0 1 年8 月宣布，将投入4 0 多亿美元进行“网格计算创新计划( g 咖 c o m p u t i n gi n i t i a t i v e ) ”，全面支持网格计算。i b m 成为g l o b u s 的首席合作伙伴，还是 o g s a 标准的制定者之一。英国政府宣布投资1 亿英镑，用以研发“英国国家网格”( u k n a t i o n a lg r i d ) 。我国也拨出了上亿元的资金用于c h i n a g r i d 相关的研究。 2 0 0 0 年w e bs e r v i c e 标准一经提出，就因其广泛的w e b 工业基础，立刻受到在科 研领域网格研究最成功的g i o b u s 项目关注，结合为o g s a 标准，并逐步演化重构，并 于2 0 0 4 年初提出网格资源框架w s r f ，目前基于其上的研究工作正如火如荼地在全球 范围内开展起来。 政府对网格研究的支持继续升温，其中美国最为积极。其现有的网格研究有 d i s t r i b u t e dt e r a s c a l ef a e i l i t y ( d t f ) 、e t f 、m i d d l e w a r ei n i t i a t i v e 等。欧洲方面最积极的是英 国( e s c i e n c e ) 。荷兰、意大利与德国也有相当投入。法国也启动了一个称为a c l g r i d ( a c t i o nc o n c e r t ei n c i d a t i v e ) 的国家网格计划，牵头单位是 i n r i a ( m i c h a e l c o s n a r d i n r i a f r ) 。这个三年计划的经费不到1 0 0 0 万美元，但不包括人员和 设备投入( 另有经费支持) 。日本与韩国的网格计划已经启动，并各自成立了全国网格 论坛。 工业界已在大力开发网格产品和服务，这方面的领头公司是i b m 与微软，其次是 p l a t f o r m 、l i p 、s u n 、l r r t e l 与b e a 等公司。这些公司基本上都认为网格与w e bs e r v i c e 本质上是一回事。但在产品推动的具体操作上，公司的主要力量在w e bs e r v i c e ，这与 学术界注重计算网格、数据网格有所不同。 在我国，已经完成的网格研究项目主要有清华大学的先进计算基础设施 a c l ( a d v a n c e dc o m p u t a t i o n a li n f r a s t r u c t u r e ) 和以中科院计算为主的国家高性能计算环 境n h p c e ( n a t i o n a lh i g hp e r f o r m a n c ec o m p u t i n ge n v i r o n m e n t ) 。 目前我国正在进行的网格研究项目有：“中国网格( c h i n a g r i d ) ”建设，8 6 3 计划 支持有多家单位参加；。上海教育科研网格”，多所上海的大学参加；“仿真网格”的研 究，由航天二院和清华大学共同开展；“织女星网格”，由中科院计算所领衔开发。 1 1 4 网格的应用领域 按照i a nf o s t e r 和g l o b u s 项目组的观点，网格应用领域目前主要有四类：分布式超 4 太原理工大学硕士研究生学位论文 级计算、分布式仪器系统、数据密集型计算和远程沉浸及网格信息集成应用【3 】。 1 、分布式超级计算 分布式超级计算( d i s t r i b u t e ds u p e r c o m p u t i n g ) 是指将分布在不同地点的超级计算 机用高速网络连接起来，并用网格中间件软件“粘合”起来，形成比单台超级计算机 强大得多的计算平台。目前典型的分布式超级计算应用有两个：第一个是军事仿真项 目s fe x p r e s s ，它将大型军事仿真任务分解到分布式环境中运行，从而在规模上创下了 该领域的世界纪录；第二个应用称作数字相对论，它利用网格求解爱因斯坦相对论方 程并模拟出天体的运动规律。 2 、分布式仪器系统 分布式仪器系统( d i s t r i b u t e di n s t r u m e n t a t i o ns y s t e m ) 是指用网格管理分布在各地 的贵重仪器系统，提供远程访问仪器设备的手段，提高仪器的利用率，大大方便用户 的使用。在网格出现之前，人们就试图通过网络访问一些仪器设备或仪器数据，但当 时的软硬件环境都不成熟，只能实现一些低要求应用罢了，而网格将分布式仪器系统 变成了一个非常易于管理和有弹性的系统。 3 、数据密集型计算 并行计算技术往往是由一些计算密集型应用推动着的，特别是一些带有重大挑战 ( g r a n dc h a l l e n g e ) 性质的应用，它们大大促进了对高性能并行体系结构、编程环境、 大规模可视化等领域的研究。但是，相比之下，数据密集型计算( d a t ai n t e n s i v e c o m p u t i n g ) 的应用好像要比计算密集型应用多得多。它对应的数据网格更侧重于数据 的存贮、传输和处理，而计算网格则更侧重于计算能力的提高，所以它们的侧重点和 实现技术是不同的。 4 、远程沉浸 远程沉浸是一种特殊的网络化虚拟现实环境。这个环境可以是对现实或历史的逼 真反映，可以是对高性能计算结果或数据库的可视化，也可以是个纯粹虚构的空间。“沉 浸”的意思是人可以完全融入其中：各地的参与者通过网络聚在同一个虚拟空间罩， 既可以随意漫游，又可以相互沟通，还可以与虚拟环境交互，使之发生改变。打个比 方，远程沉浸是一部观众可以进入其中的科幻电影。远程沉浸可以广泛应用于交互式 科学可视化、教育、训练、艺术、娱乐、工业设计、信息可视化等许多领域。 5 、信息集成 太原理工大学硕士研究生学位论文 早在网格兴起之前。人们已经意识到了信息集成的重要性，网格最早以集成异构 计算平台的身份出现，接着跨入分布处理海量数据的领域，自然而然地，网格将在信 息集成领域一展身手。所谓的信息网格，就是要建立一个体系结构并开发相应的中间 件，向用户提供信息在你指尖”( i n f o r m a t i o na ty o u rf i n g e r t i p ) 式的服务。信息网格研 究的中心问题有：如何描述信息、存储信息、发布信息和查找信息；如何充分利用现 有网络技术，如h r t p 、x m l 、w s d l 、u d d i 、s o a p 等，构成一个完整的服务链； 信息的语义表示，即如何赋予信息以内涵，以及如何避免信息的二性；如何对信息加 密，防止信息泄露等等。 1 2 网格的特点 研究网格特点可以更好地认识与把握网格的开发应用。网格具有分布共享性、自 相似及整体性、动态多样性以及自治虚拟性等特点。 l 、分布与共享 网格设备( 具有唯一i p 网络地址的硬件) 是地理上分布的，网格资源( 可以网格 寻址的抽象) 也是分布在不同的网格设备上的，因此只能是分布式的计算模式。虽然 网格资源存在分布性，但网格资源也是可以充分共享的，即网格上的任何资源可以提 供给网格上的任何用户。分布式网格资源的共享问题是网格的核心问题。通过网络服 务协作实现了物理上分布的网格资源的全局共享，这是网格的本质特征。 2 、自相似性与整体性 网格系统的局部与整体具有一定的相似性，网格局部也是网格，局部组合成整体 时，功能与性能超线性增加，体现出“整体远远大于部分和”的特性。 3 、动态多样性 网格的动态性是指：局部网格设备的增加与减少，不影响网格其它部分的功能与 性能，网格可以自动把相关资源或服务迁徙到其它部分，不影响网格的应用性能。网 格设备具有多样异构性，网格资源的多样异构性，是网格的本质特征。解决异构资源 的集成正是网格的吸引力所在。 4 、自治性 网格资源是属于资源所有者的，所有者有权决定资源是否向网格开放以及向谁、 6 太原理工大学硕士研究生学位论文 怎么公开。网格资源是否为网格接受并被用户租用，要取决于网格及其用户，用户有 权决定自己使用谁的网格资源。 1 3 网格作业调度算法 1 3 1 网格作业调度 网格作业调度是使用网格资源的一种形式，它根据用户确定的流程，为用户提供 使用资源的功能。网格作业一般都是在远程节点上运行，作业提交者对远程设备的控 制能力是非常有限的，为了有效管理作业的运行，就需要网格作业管理机制，管理整 个网格作业的运行过程。 作业是用户代码、数据及其相应资源描述信息的集合。作业管理需要信息服务、 资源管理、数据管理、安全通信的支持，它是网格中不可或缺的功能，尤其是在计算 网格中，它是保证网格用户合理有序地使用网格环境下的计算资源的基础，应该做到 每个用户提交的作业都能在合适的资源上执行。 网格作业调度应把用户付出的代价尽可能降到最低。在一批候选资源中自动选择 一个或多个资源来运行用户提交的作业，应把用户的利益最大化作为管理的基本功能。 作业调度是作业提交者和计算资源之间的中介，从资源的角度要求作业调度做到负载 均衡，从用户的角度要求最大限度地保护用户的利益。同一个作业在不同的计算资源 上运行需要用户付出的代价也会存在差异，即使用户没有明确指定自己所能承受的代 价是多少，作业调度也应该选择用户付出代价最小的资源。这里的代价是指综合付出， 付出的时间、用户的劳动、付出的费用等都是代价的主要因素。 1 3 2 研究现状 在网格作业管理方面，目前已经出现了一些网格作业管理系统，这些软件提供的 功能彼此之间存在差异，使用界面也各有特点。典型的几个有：( 1 ) 欧洲数据网格的 作业提交接口，是通过g l o b u s 工具包实现的，因此与g l o b u s 所提供的接口和功能非常 密切。( 2 ) s u n 网格引擎s g e ( s u ng r i de n g i n e ) 将网格定义为执行作业的计算资源的集 合，对用户而言，网格是一个大系统，它提供单个a t 3 点，从该入口点可以访问网格 7 太原理工大学硕士研究生学位论文 中强大而分散的资源，用户只需要将网格看作单个计算资源，资源管理软件接收由用 户提交的作业，并根据资源管理策略调度作业的执行，用户不必考虑它们在何处执行。 ( 3 ) 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 r ) ，它也有作业管理器的功能。g r a m 和本地管理器相互作用，把作业按照不同类型，提交给作业管理器。g r a m 的后端是 本地作业管理系统，如p b s ( p o r t a b l eb a t c hs y s t e m ) ，l s f ( l o a ds h a r i n gf a c i l i t y ) 等。 用户和作业之间的交互是通过g r a m 实现的。 1 3 3 网格作业调度算法 网格作业调度是一个n p 完全且难问题，人们在该领域进行了许多研究，也取得了 一些成果，但是要解决网格环境下的作业调度问题还需要进行大量的研究工作。 在网格作业和元任务调度研究中，出现了很多算法，如先来先服务( f c f s ) 、短时 间作业优先( s p t ) 、f i r s t f i t 、随机调度算法( r a n d o m ) 、b e s t f i t 、贪心算法、优先级 调度、资源预留算法、遗传算法( g e n e t i c d g o r i t h m ) 等。 本文采用的是基于遗传算法的网格作业全局调度策略。遗传算法是建立一个调度 的集合并从其中找出优化的调度，将这种特性遗传给下一代。遗传算法利用固定的大 量数据和随机的挑选，通过适应函数交叉和重组得出最优的调度。这是一种迭代的算 法，它的优点是在它不断进化的过程中吸收系统的改变，能够适应动态变化的网格系 统，比如增加或删除任务，节点速度和状态的改变。 1 4 课题目的和意义 网格资源是异构和多样的，网格环境中可以有不同体系结构的计算机系统和类别 不同的资源，网格系统必须能够解决这些不同结构，不同类别资源之间的通信和互操 作问题。因此网格资源的高效管理和作业的有效调度已成为网格研究的重要内容之一。 使用经济方法对网格资源进行管理分配，利用经济学中的竞争理念，构造优胜劣 汰的自然环境，形成一个平等健壮的交易市场，可以充分保障网格中大部分用户( 包 括资源消费者和资源提供者) 的利益。因此引入经济因素进行网格资源分配有以下好 处： ( 1 ) 经济活动中的市场是一种基于分布自主决策的资源分配机制，即每个参与方 太原理工大学硕士研究生学位论文 根据市场价格和自身偏好自主决策，而计算网格的资源分配恰好需要实现类似的分布 自主决策； ( 2 ) 关于市场机制的经济学理论给出了计算网格资源分配效率的精确刻画。计算 网格通常强调用户需求的异构性，此时以经济理论为基础的市场效率观点对于计算网 格的资源分配非常重要； ( 3 ) 市场机制通过价格浮动反映资源供需状况的动态变化，通过供需均衡实现优 化分配。这种动态协调的资源分配机制恰恰适合计算网格的动态特性。 因此合理的将经济因素引入计算网格的资源分配和任务调度中，可以保证资源提 供者更好的提供服务，保障资源提供者和资源消费者的利益，同时也可以激励更多的 资源拥有者加入到网格系统的建设中来。 本课题主要通过研究已有的作业调度模型和算法，提出了一种基于拍卖机制的在 线信誉网格资源管理模型，吸引更多更好的资源加入网格，实现资源优化分配，保证 交易双方均获取最大利益，有利于网格资源的市场管理及供需均衡。并在其基础上提 出了基于遗传算法的网格作业全局调度策略，对己提出的启发性较好的遗传算法进行 改进，引入时间和花费两方面经济因素，提高计算效率和获取最优代价值。努力为网 格资源实现最优调度做一些工作。 1 5 本文所做的工作 本文旨在对网格计算的核心之一网格作业调度进行深入研究。但是考虑到网 格作业调度算法的实施设计的其他技术环节众多，特别是网格资源的管理模型、调度 之后调度成果的性能评价等。鉴于此，本文的研究内容主要包括以下几点： ( 1 ) 网格资源管理模型 计算网格的基石是众多的计算资源，但是由于计算网格的根本特性是随机的共享， 所以众多的计算资源存在着种类繁多、服务不确定，能力不统一等性质，因此设计一 个网格资源管理模型基于拍卖机制的在线信誉网格资源管理模型，更有效地管理 计算资源及更好的为用户服务是本文研究的重点之一。 ( 2 ) 网格作业调度算法研究 一个运算量巨大的任务能否在网格环境下正确、快速的运行并能运行成功，与高 9 太原理工大学硕士研究生学位论文 效的作业调度算法密不可分，因此本文重点对作业调度算法进行研究，提出基于遗传 算法的网格作业全局调度策略。并对提出的算法进行形式化分析及仿真网络环境下的 模拟测试。 ( 3 ) 搭建仿真环境 通过g r i d s i m 模拟器，搭建网格仿真环境，为算法评测提供试验平台。 ( 4 ) 性能评价 在g r i d s i m 仿真环境下，对本文提出的作业调度算法和其他算法进行比较，评价 算法的优劣。 1 6 本文的组织结构 本文共分为六章 第一章“引言”，简要介绍计算网格技术背景，特点、应用、发展状况及网格作 业调度算法的基本知识，并且介绍了本文的主旨。 第二章“网格体系结构”，对计算网格的两种主流体系进行了分析比较，并对w s r f 规范进行剖析。 第三章。网格环境下的资源管理模型”，介绍了目前基本的网格资源管理模型，并 对其做出了相应的评价；详细分析了计算经济模型的具体类型及特点。 第四章“基于拍卖机制的在线信誉网格资源管理模型”，描述了基于拍卖机制的在 线信誉网格资源管理模型的设计思想、结构框图、主要部分的工作机理及相应的信任 模型。 第五章。基于遗传算法的网格作业全局调度算法”，设计了基于遗传算法的网格作 业全局调度策略，目标是通过更合理的资源分配降低网格用户的总花费及执行时间。并 利用网格模拟器g r i d s i m 进行仿真测试。 第六章“结束语”，总结了本文提出的“基于拍卖机制的在线信誉网格资源管理模 型”及“基于遗传算法的作业全局调度算法”，并对进一步研究的方向提出了建议。 1 0 太原理工大学硕士研究生学位论文 第二章网格体系结构 2 1 网格体系结构的意义和功能 建立网格的首要任务是建立科学，合理的网格体系结构。网格以现有的互联网为 基础，在其上建立一个满足人们对资源更高需求的计算平台。网格是在国际互联网基 础之上建立的一个全新的计算平台，管理跨组织、跨管理域，为网格应用提供全面的 资源共享接口，实现分布式资源的有效集成，提供共享各种资源的手段，提高资源利 用率，满足人们对广域网内各种资源的共享需求。请求使用网格资源时，用户首先向 网格发出请求使用资源的消息，网格接收请求并做出响应。这是一个典型的客户端驱 动模型，它与现在的万维网工作方式有诸多相似之处，但仍存在明显的区别： ( 1 ) 在网格环境下，一个客户请求能同时驱动多个资源工作，同时连接到多个 服务器上；在万维网上，一个客户端可以先后访问多个服务器，但同时只能访问一个 服务器。 ( 2 ) 在网格环境下，运行某个客户程序的资源也可以被其他客户请求作为资源 使用，客户端和服务端不存在明显的界限。 ( 3 ) 在网格环境下，浏览器仍然是一种客户端，但不是客户端的唯一形式，客 户端将更加多样化。 ( 4 ) 网页仍然是网格中的一种资源，但网格资源的种类将扩大到计算设备、存 储设备、软件资源等。资源的功能将更丰富，提供信息、加工信息、执行作业、实现 操作的功能都可以由不同的资源完成。 网格的多方参与特性要求有一个指导原则规范多方的行为，这个指导原则的具体 实现就是网格体系结构。网格的多方参与特性体现在以下几个方面： ( 1 ) 网格中的资源分别属于不同机构或不同的管理域，不同资源的拥有者不同， 参与网格的方式和可以被网格用户共享使用的方式也各不相同。 ( 2 ) 网格中资源的种类繁多，数量巨大，不同资源提供的功能多样，不同资源 太原理工大学硕士研究生学位论文 具有的物理接口也各不相同，提供相同功能的多个资源可能具有不同的物理接口，具 有相同的物理接口的资源可能提供不同的功能。 ( 3 )网格的建设需要多方参与，协同开发，建立网格体系结构后，可以将整体 功能按照逻辑关系的相互独立性和功能的相对完整性划分成多个模块，不同的模块可 以由不同的人开发。 ( 4 ) 网格上的用户数量巨大，来源各异，背景差异也很大，网格用户使用的母 语有很多种，访问网络的输入输出设备也千差万别，需要网格提供的功能存在很大差 别。 ( 5 ) 一个网格用户需要在网格中的多个资源上进行活动，以便利用不同的资源 提供的特有功能和合理集成多个分布式资源之后的整体功能。 2 2 五层沙漏结构 五层沙漏结构是一个影响十分广泛的结构，它的主要特点就是简单，主要侧重于 定性的描述而不是具体的协议定义。五层沙漏结构根据该结构中各个组成部分与共享 资源的距离，将对资源进行的操作、管理和使用功能分散在五个不同的层次，越向下 层就越接近于物理的共享资源。 、工具与应用, 应用层 n 诊星霉基 汇聚层 资源与服务 的安全访问 资源与连接层 各种资源如： 计算机、存储介质、心 构造层 网络、传感器等、& 图2 - 1 沙漏形状的五层结构l q f i g u r e 2 1t h ef i v el e v e l sh o t w g l a s sm o d e la r c h i t e c t u r e 由图2 - 1 清晰显示出五层沙漏结构的一个重要的特点就是其沙漏形状，其内在的含 义是：因为各部分协议的数量是不同的，对于其最核心的部分，要能够实现上层各种 协议向核心协议的映射，同时实现核心协议向下层其他各种协议的映射。核心协议在 所有支持网格计算的地点都应该得到支持。因此，核心协议的数量不应该太多，这样 1 2 太原理工大学硕士研究生学位论文 核心协议就成了协议层次结构中的一个瓶颈。 五层沙漏结构中，各层的功能： ( 1 ) 构造层：面对的是具体的物理资源。它通过对局部资源的管理，向上层提供 对这些资源的管理和控制界面。构造层组件实现了基于底层特定资源的高层共享操作。 在构造层实现的功能有紧密的相互依赖性，它们支撑着上层可共享的功能。构造层功 能越丰富，就越能更好地实现上层功能的共享。减少构造层的组成元素，网格的基础 构造配置则相应简化。 ( 2 ) 连接层：主要为下层的物理资源提供安全的数据通信能力。连接层为各个孤 立的单个资源之间建立了联系，这是资源之间进行互操作的前提。该层定义了网格中 网络处理的核心通信协议和认证协议。通信协议使构造层的资源间的数据转换成为可 能。认证协议基于通信服务提供确认用户和资源身份的安全机制。 ( 3 ) 资源层：反映抽象的局部资源特征。资源层建立在连接层的通信和认证协议 之上，定义了关于安全协商，共享计费，监控等方面的协议。资源层通过调用构造层 的功能访问和控制本地资源。资源层与连接层构成沙漏模型的瓶颈，协议必须符合跨 多种不同资源的基本共享机制，同时不能明显限制高层协议的种类和性能。 ( 4 ) 汇聚层：将下层以单个资源形式表现出来的资源集中起来，协调解决多个资 源之间的问题。 ( 5 ) 应用层：决定把什么样的资源分配给下层的虚拟组织，解决不同虚拟组织的 具体问题。 2 3 开放网格服务体系结构( o g s a ) 开放网格服务体系结构( o g s ao p e ng r i ds e r v i c ea r c h i t e c t u r e ) i s 【6 】是g g f ( g l o b a l g r i df o r u m ) 的重要协议标准，是继五层沙漏结构之后最重要的一种网格体系结构。 o g s a 把g l o b u s 标准与面向商业应用的w e bs e r v i c e 结合起来，把网格计算从科学工 程计算应用扩展到更广泛的以分布式系统服务集成为主要特征的商业应用领域。o g s a 以服务为中心，把一切都抽象为服务，利用新兴的w e b 服务定义语言( w 曲s e r v i c e s d e f i n i t i o nl a n g u a g e ) 接1 3 确保异构系统间的互操作性，这样不同类型的系统就可以进 行通信、共享信息。 太原理工大学硕士研究生学位论文 如果说五层沙漏结构是以协议为中心的协议结构的话，o g s a 就是以服务为中心 的体系结构。这里的服务是指具有特定功能的网络化实体。在五层沙漏结构中强调的 是被共享的物理资源( 或者这些资源提供的服务) ；在o g s a 中服务的概念更广，包括 各种计算资源，存储资源，网络，程序，数据