（计算机应用技术专业论文）基于遗传模拟退火算法的网格任务调度研究.pdf

一 嬲燃 内蒙古科技大学硕士学位论文 论文题目：基于萼佧幽警冬笋滓的| _ 何何爹塑f 芝矽f 窖 作者： 阴：振江 指导教师： 堂丛生丝丝单位：笪：垦：兰狸堂堕 协助指导教师：王赴：j ：刨邀拯单位：笪：垦：兰：壁堂堕 论文提交日期：2 0 1 0 年钐月协日 学位授予单位：内蒙古科技大学 研岁芒：l 姓名：陈振江 指导教帅姓名：谭跃生 内蒙占科技大学信息学院 包头0 1 4 0 1 0 ，中国 c a n d i d a t e ：c h e nz h e n - j i a n g s u p e r v i s o r ：t a ny u e s h e n g s c h o o lo fi n f o r m a t i o ne n g i n e e r i n g i n n e rm o n g o l i au n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y b a o t o u0 14 0 10 ，p r c h n a 内蒙古科投人学顺i j 学位论文 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导f 进行的研究一i ：作及 取得研究成果。尽我所知，除了文中特别加以标注和敛谢的地办外，论文中 小包含其他人已经发农或撰t 拍，j 研究成果，也不包含为获得内蒙占科技人学 或其他教育机构的学位或证书所使用过的材料。与我一同： 作的同志对本研 究所做的任何贡献均已在沦义中做了明确的说明并表示，谢意。 签名：翠豆及扛f j 期：扬丞：岳： 关于论文使用授权的说明 本人完全了解内蒙古科技大学有关保留、使用学位论文的规定，即：学 校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文 的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵循此规定) 签名：佴耻导师签名：互陋f 1 期：o 蛔砬仙 一 内蒙占科技人学f ! i j 学位论义 摘要 网格计算是近年来的研究热点之一。它可将高速互联网、电脑、大型资料库、传 感器、远端改箭等融为一体，实现它们的全而共享与协同+ i ：作。h 懈f e 务调嫂是网格 计算研究的骸心内容之一，如何合胖地将仟务分配给不n 可资源，使整个阳挤系统达剑 最佳的性能，这是任务调度需要解决的问题。由于网格自身的分和性、异构性、动念 性和自治性，使得传统的渊度算法t f ds 临新的挑战。冈此，如何在现有调度算法的基础 上改进优化，尽t 叮能提高网格系统的吞吐量，是一个重要而现实的问题。 遗传算法g a ( g e n e tica lg o r it h m ) 和模拟退火算法s a ( s i m u l a t e da n n e a li n g ) 是目 自玎解决网格任务凋度比较有效的算法。两种算法都是模拟自然界的某螋现象进行人规 模优化问题求解的随机性方法，都不要求目标函数的连续性、可微性和凸性。g a 有较 强的全局搜索性能，但它的爬山能力弱，在实际应用中容易产生早熟收敛的i 、u j 题，在 进化后期搜索效率较低。而s a 却具有摆脱局部最优解的能力，能抑制遗传算法的早熟 现象，f e l 它的进化速度慢。 针对g a 早熟收敛和s a 进化速度慢的问题，本文结合两算法的各自特点进行改进 并设计了一种遗传模拟退火算法g s a a ( o e n e t i cs i m u l a t e da n n e a lin ga 1 9 0 t i t h m ) 。 g s a a 基本思想是首先充分利用g a 的群体性、全局收敛性、随机性、快速搜索等优势 生成初始解，即通过g a 的遗传操作产生初始解；随后采用s a ，对生成的初始解，利 用s a 的m e t r o p o l i s 准则跳变特性决定是否接受由交叉和变异操作产生的新个体，使 得在接受优质解的同时，也有限度的接受劣质解，保证了种群的多样性；采用了自适 应交义和变异概率：适当地改进了遗传操作。通过g s a a 来求取网格任务调度的最优解。 本文深入研究了g a 和s a 的壤本原理，根据嗍格任务调度的特点，本文在g a 和 s a 基础上改进并设计了g s a a 的各个组成部分。在g r i d s i m 网格模拟器中，对g s a a 进 行了仿真实现，并与g a 和s a 进行了对比，结果表明本义提出的g s a a 具有更好的搜索 能力和收敛速度。 关键字：网格计算；任务调度：遗传算法( g a ) ；模拟退火( s a ) 算法；g r i d s i m 厂二二二= 三二二二 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n di n t e r n e t ，t h e r ea r eal a r g e n u m b e ro fd i f f e r e n tt y p e so fa v a i l a b l er e s o u r c e sw h i c hi sg e n e r a t e do nt h ew e b g r i dt a s k s c h e d u l i n gi so n eo ft h ec o r er e s e a r c h i n gi t e m s o n eo ft h ec o r et a s k si sh o wt or a t i o n a ll y a l l o c a t et h et a s kt od if f e r e n tr e s o u r c e st om a k et h ee n t i r eg r i ds y s t e mt op e r f o r mp e r f e c t l y b u th e t e r o g e n e o u s ，d y n a m i ca n da u t o n o m yo ft h eg r i di t s e l fm a k et h et r a d i t i o n a ls c h e d u l i n g a l g o r i t h mf a c i n gn e wc h a l l e n g e s t h e r e f o r e ，h o wt oo p t i m i z et h es c h e d u l i n ga l g o r i t h m b a s e do nt h ee x i s t i n go n et om a x i m i z et h et h r o u g h p u to ft h eg r i ds y s t e mi sa ni m p o r t a n ta n d p r a c t i c a li s s u e r e c e n t l y , g e n e t i ca l g o r i t h mg a ( g e n e t i ca l g o r i t h m ) a n ds i m u l a t e da n n e a l i n ga l g o r i t h m s a ( s i m u l a t e da n n e a l i n g ) a r er e l a t i v e l ye f f e c t i v et os o l v et h e 鲥dt a s ko fs c h e d u l i n g a l g o r i t h m b o t ht w oa l g o r i t h m sa r es i m u l a t e ds o m ep h e n o m e n ao fn a t u r et oo p t i m i z e m e t h o d sf o rs o l v i n gp r o b l e m si nal a r g e s c a l e a l s o ，n e i t h e ro ft h e mr e q u i r e st h ec o n t i n u i t y a n dc o n v e x i t yo ft h eo b j e c t i v ef u n c t i o n g ah a ss t r o n gg l o b a ls e a r c hp e r f o r m a n c e ，b u ti t s c l i m b i n ga b i l i t yi sw e a ka n dp r o n et ot h ep r e m a t u r ec o n v e r g e n c ep r o b l e mi np r a c t i c a l a p p l i c a t i o n ，a n dh a sl o w e re f f i c i e n c yi nt h el a t e rs t a g eo fe v o l u t i o n t h es ai sa b l et oc a s t o f fl o c a lo p t i m a ls o l u t i o na n dt oi n h i b i tp r e m a t u r ec o n v e r g e n c eo fg e n e t i ca l g o r i t h m s ，b u ti t s e v o l u t i o ni ss l o w s i n c et h ep r e m a t u r ec o n v e r g e n c ea n ds l o we v o l u t i o no fg a ，t h ep a p e rc o m b i n e dt w o a l g o r i t h m s c h a r a c t e r i s t i c st oi m p r o v ea n dd e s i g nas i m u l a t e da n n e a l i n gg e n e t i ca l g o r i t h m g s a a ( g e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h m ) t h eb a s i ci d e ao fg s a ai st om a k ef u l l u s eo ft h eg r o u po fg a ，g l o b a lc o n v e r g e n c e ，r a n d o m ，q u i c ks e a r c ha n do t h e ra d v a n t a g e so f g e n e r a t i n gt h ei n i t i a ls o l u t i o nf i r s t l y , w h i c hi sp r o d u c e di n i t i a ls o l u t i o nb yt h eg e n e t i c o p e r a t i o no fg a ；t h e nu s et h ei n i t i a ls o l u t i o no fs am e t r o p o l i sc r i t e r i at od e c i d ew h e t h e rt o a c c e p tt r a n s i t i o nc h a r a c t e r i s t i c so ft h ec r o s s o v e ra n dm u t a t i o nt og e n e r a t en e wi n d i v i d u a l s ， t oa c c e p tt h eh i g h - q u a l i t ys o l u t i o n sw h i l ea c c e p t i n gi n f e r i o rs o l u t i o n s p r o p e r l y , t oe n s u r et h e d i v e r s i t yo fp o p u l a t i o n t h eg s a a u s e sa d a p t i v ec r o s s o v e ra n dm u t a t i o np r o b a b i l i t y ； p r o p e r l yi m p r o v e dg e n e t i co p e r a t i o n s t oo b t a i nt h eo p t i m a ls o l u t i o no fg r i dt a s ks c h e d u l i n g b yg s a a i sw o r k a b l e t h i sp a p e ra n a l y s i st h eb a s i cp r i n c i p l e so ft h eg e n e t i ca l g o r i t h ma n ds i m u l a t e da n n e a l i n g a l g o r i t h ms a ( s i m u l a t e da n n e a l i n g ) t h o r o u g h l y a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fg d d t a s ks c h e d u l i n g ，t h ep a p e rd e s i g n st h eh y b r i dg e n e t i ca l g o r i t h mi nv a r i o u sc o m p o n e n t s ，a n d s i m u l a t ea c h i e v e dt h eg s a ai ng r i d s i mg r i ds i m u l a t o rs t i l l ，a f t e rc o m p a r i n gw i t hg aa n d s a ，t h er e s u l t ss h o wt h a tt h ep r o p o s e dg e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h mh a sb e t t e r s e a r c ha b i l i t y k e y w o r d s ：g r i dc o m p u t i n g ；t a s ks c h e d u l i n g ；g e n e t i ca l g o r i t h m ( g a ) ；s i m u l a t e d a n n e a l i n g ( s a ) a l g o r i t h m ；g r i d s i m 内蒙古科技人学顺卜位论文 目录 摘要一i a b s t r a c t i i 第一章绪论1 1 1nf 告臻小期以1 1 1 1m 恪的丛 i 慨念l 1 1 1 1 起源与研究动机l 1 1 1 2 州格的辏本特征2 1 2 网恪f ，j 体系结f ；j 3 1 2 1 嘲洛的基本功能模块3 1 2 2 两种典蚕! 的网格体系结构4 1 3 本文的研究内容7 1 3 1 课题的提出7 1 3 2 本文研究的主要内容8 1 4 奉文各章节结构8 第：二章网格资源和网格任务调度1 0 2 1 网格资源l o 2 1 1 网格资源的定义- 1 0 2 1 2 刚格资源的分类1 l 2 1 3 网格资源的特点1 1 2 2 网格中的任务调度概述1 2 2 2 1 网格任务调度的特点1 2 2 2 2 网格任务的调度过程1 3 2 2 3 网格任务调度评价标准1 4 2 3 资源调度模型研究1 5 2 3 1 集中式资源调度模型1 5 2 3 2 分布式资源调度模型15 2 3 3 层次化资源调度模型1 5 2 4 网格任务调度算法1 6 2 5 本章小结。1 9 第：三章遗传算法和模拟退火算法2 0 3 1 遗传算法介绍2 0 3 1 1 遗传算法的基本原理2 0 3 1 2 遗传算法的实现过程2 1 内蒙吉科投人学硕l j 学位论文 3 1 2 1 染色体编码2 l 3 1 2 2 初始化种群2 2 3 1 2 3 适应度函数2 2 3 1 2 4 遗传操作一2 2 3 1 2 5 进化俘i l ：“e 删1 i l l 天运 j ：参数2 4 3 1 3 越传算i 2 a , j 优点与缺陷2 5 3 2 模拟退火算法简介2 5 3 2 1 模拟j 娃火算法的堆奉思怨2 5 3 2 2 模拟退火的参数选择问题2 7 3 3 遗传并法改进的具体实现2 8 3 3 1 算法改进的基本思想2 8 3 3 2 遗传模拟退火算法的设计2 9 3 3 2 1 自适应交叉和变异概率一2 9 3 3 2 2 对遗传操作的适当改进一3 0 3 3 2 3 遗传模拟退火算法的基本流程3 0 3 4 本章小结3 2 第四章基二f 遗传模拟退火算法的网格任务调度一3 3 4 1 网格任务调度系统模型3 3 4 2 任务调度问题的定义3 4 4 3 遗传模拟退火算法各部分实现过程3 5 4 3 1 染色体的设计3 6 4 3 2 种群的初始化3 6 4 3 3 适应度函数3 7 4 3 4 选择操作3 7 4 3 5 交叉操作3 8 4 3 6 变异操作3 9 4 3 7 自适应交叉和变异概率4 l 4 3 8 降温函数4 l 4 3 9 进化终止条件4 1 4 4 算法执行流程4 2 4 5 本章小结4 3 第五章基于g r i d s i m 的仿真4 4 5 1 网格模拟器g r i d s i m 一4 4 5 1 1g r i d s i m 的关键特征4 4 5 3 仿真与结果分析5 l 5 3 1 实验参数一5 1 5 3 2 仿f 结果与分析5 2 5 4 本章小结5 4 第六章总结与展望5 5 参考文献5 6 攻馥颁： ：学位期l 自j 发表的文章5 9 致谢6 0 顺i ：学位论义 1 1 网格基本知识 1 1 1 网格的基本概念 1 1 1 1 起源与研究动机 绪论 算的核一i i , 。本章闸述了网格的发展及其在 景+ j 现状，并介窒f j 了本文的t 要：i ：作与伞 “网淅”一词最早于2 0 世纪9 0 年代巾期提i 叶j ，用于表述在先进科学和工程计算 中的一种分们式计算体系结构。在最初戍用网格概念和技术的科学协作中，分命在各 地的不同组织和机构不但共享数据，而且还要求灵活共享软件和计算资源，甚至包括 昂贵的专用科学仪器，如天文望远镜和电子湿微镜等。针对这一类型的需求 n 脱了大 量的网格应用，包括对计算能力要求很高的用于实验数据分析的分御式计算；异构分 布式数据集合的邦联：海量科学数据的协作式可视化：科学仪器的耦合：对实验数据 的远程访问等。 这些应用中的共享不局限于文件共享，它更强调对于计算机、软件、数据和服务 非常直接的存取。这一共享是高度受控的，允许资源的提供者和使用者清楚地定义共 享的实体、限制以及条件。由这些共享规则定义的人和组织组成了虚拟组织( v ir t u a l o r g a n i z a t i o n ，v o ) 。v o 在规模、范围、存在的时间、结构、分布和功能上是各不相 同的。v o 的例子包括：为了完成。一个计算任务而涉及到的应用服务提供者、存储服务 提供者、计算服务提供者等；为紧急情况制定预案所需的仿真系统和数据库系统；大 型围际化物理研究合作中的各个成员等。尽管v 0 的应用背景不同，但其中大量需要解 决的问题足柑同的。v ( ) 中需要建立高度灵活、能够表达成员之间协作关系的共享关系： 需要对共享资源进行复杂的高层控制，包括存取控制授权、本地和全局策略的实施等； 还需要有对各种资源进行发现、并提供和管理的基础机制。这样j 能支持不同模式协 作下对时间和性能提出的要求，解决诸如o o s 、调度、协同分配、审计等问题。网格 研究的目的即是为了支持v o 巾资源的灵活共享和协作，即“动态、多机构组织巾的协 同式资源共享和问题求解” 尽管网格研究的仞衷足为了解决科学研究中对计算能力和资源共享的需求，但已 有越来越多的企业意i = 到了网格技术的广泛应用前景，并j r 始进行网格的研究和应用。 希：人黾的商业坏境中，包括企q k i , v 用集成、按需服务、b 2 b 等，同样涉及全u 与f ：述应 内蒙占科技人学倾i j 学位论文 用类似的动念、多机构合作中协同式资源共享和| 、u 】题求解。【j 于具有分布、动态和短 暂的( e p h e m e r a l ) 特性，v o 的概念【i _ = i 】样也适用f 这些合作，i f 如i 司w e b 丌始时作为科 学协作技术f 现、然后用于电子商务一样，网格技术的发展也逐渐呈现出类似的轨迹 i 存众多f f _ jj ：科学研究的人型h 恪喊j f j j 顷t - tf i ，比较典型 ， ，j 钉炎酬s f 资助的f f jj ： 地震研究的x e e s 项肖上、美幽n a s a 川于航犬科技研究的i n t 。o r m a jo np o w e rg r i d 项 目网、以及欧盟刚：f 高能物理研究的e ud a t ag r i d 项目等。荚l 1 4 军疗也提出了全球信 息网格( ( ；l o b a li n f o r m a t i o i l ( ；r i d ，g i g ) 的概念_ 1 ，以信息战为7 亍景对网格技术展丌 研究。在州格标准和系统软件的研究方面，美困a r g o n n e 阉家实验审的( ；1 b u s 项目。 的提出的丌放网格服务体系结构( x ；s a 被公认为目自玎网格体系结构的标准，而其发行的 g 1 0 b u s t o o lkit 4 0 则是o g s a 目i 订最通用的实现。h p 、i b l 、m i c r o s o f t 、s u n 等犬公刮 也陆续j f ：始往网格及其相关领域内投资和研发。在我国，由中科院计算所等f 几家科 研单位共州承担的“8 6 3 ”重点项目一国家高性能计算环境( n h p m e ) 是我幽第一个网格 雏形，2 0 0 2 年，国家“8 6 3 ”计划启动了新一轮网格研究项目一中困困家网格( c h i n a n a t i o n a lg r i d ) ，突出了网格在地质、气象、药物、航空等领域的应用。 1 1 1 2 网格的基本特征 随着网格研究的深入和应用需求的r 益丰富，人们希望l 叫格支持包括计算能力、 数据、信息、知识和服务等在内越来越广泛资源的灵活、高效的共享。因此网格一词 的内涵越来越丰富，所涵盖的范畴也越来越大，网格研究中也逐渐提出了数据网格、 信息网格、知识网格、服务网格等各种各样的网格名称。其中，数据网格( d a t a g r i d ) 用于解决现代科学研究和商业应用领域中产生的t b 至p b 级分和数据的存储、访问、 传输、处理与分析等问题；信息网格( i n f o r m a t i o ng r i d ) 的根本出发点在于使用灵活 资源集成与共享技术解决信息系统建设中广泛存在的信息“孤岛”问题，实现信息的 高效处理、共享与利用；知识网格( k n o w l e d g eg r i d ) 则着眼于知谚 的获墩、产生和灵 活的管理与共享；服务网格( s e r v i c eg r i d ) 通过使用面向消息的服务接1 1 将能够通过 消息交换为客户提供某种功能的实体封装为服务，并提供统一的服务访问方式，实现 灵活高效的服务集成的目的。 总的来说，计算网格和数据网格是网格的基础，为上层应用提供强大的计算能力 与数据处理能力；信息网格和知谚 网格则可视为网格技术在计算和数据之上更高层次 的应用，试图提供远远超出当d 订i n t e r n e t 信息处理技术与能力的。体化信息基础设 施；服务嗍格则在体系结构方面强调以“服务”为中心，突出了网格构造中异构资源 集成的特点与新手段，代表了例格在系统构造方面的发展趋势。 为把例格和一般的分命式系统f x 分) 1 i ，h 格研究的先驱、( ；l o h s 项门的负责人i a n 内蒙古科技人学颁t j 学f t 论义 f o s t e r 提了网格的3 条削断标准引： 1 ) 协调非集中控制的资源：网格整合各种资源，协调各种使用者，这止莹资源和使 用者处于彳i 同的管理域。网格应该解决在这种分佰式环境中的安全、资源管理策略、 使用费用和1 成员权限等问题： 2 ) 使j | j 卡，j 讲、j l ：放和通川的 j j _ 义和接ii ：h 恪建：z 企多助能的阱议和接【1 之l ： 这廿鼍协议和接【j 刚f 解决认址、授权、资源发现属l 资源存取等鉴本i u j 题： 3 ) 提供非平凡的( n o n t r i v i a l ) 服务：网格允许协调使用资源，以得剑多种服务质 量，满足不h 使用者需求，如系统响应时| n j ，流通跫、有效性、安伞性等。 文献+ - - 总结了理想情况f ，网格所具有的t 要特点： 1 ) 大觇模：体现在集成的资源数黾和资源之i 日j 的物理距离方面； 2 ) 地理分自】 3 ) 异构：网格中资源的形式和槿性仃很人差异； 4 ) 资源共享； 5 ) 跨越多个管理域； 6 ) 资源的协调使用； 7 ) 对资源透明的访问； 8 ) 可靠的服务质鼍； 9 ) 一致的资源访问方式，即m 格必须具有标准的协议、接口以屏蔽异构性，并保 证可伸缩性； 1 0 ) 对资源无处不在的访问，即网格资源的访问应该适应动态、大规模的环境，并 考虑资源失效的处理。 1 2 网格的体系结构 网格体系结构足关于如何建造网格的技术，它描述了网格的基本组成和功能，以 及各个组成部分之间的相瓦关系和网格的运行机制。网格是一个整体的概念，网格体 系结构的作f j 在一定程度上就是对网格的解剖。网格体系结构不仪耍能够标识出网格 的基本组成成分，能够清楚地说明网格整体足l l i 哪些关键部分结合在一起形成的，而 且还要进一步描述如何将这些部分按照一定的方式进行组织和集成，形成一个具有特 定功能的整体对外提供服务。 1 2 1 网格的基本功能模块 网格中的各个模块的设置和模块i h j 的相互助能的分配要以实现i 叫格功能为目标。 尤其是肇本模块的没霄受是紧密结合m 格的目的来确定的。j l 自那哆电实现阀格功能所 必须的模块彳成为网格的基本模块。网格町以划分出下列基本功能模块。 内蒙古科找人学坝i j 学位论文 1 界面管理模块：负责用户和网格之m 信息的转换和表示。 2 信息锊理模块：为网格活动提供依据，如哪廿鬯资源是可供用户使用的。 3 资源管理模块：负责资源的查找、分配等。 4 数掘管理模块：负责把远程节点的数据传输剑汁算程序运i j ：的节点l 。 5 作、蚴专：刖模块：便。j ：f f j ，1 了解f 二 l 二作、i t 的运”陌况。支持j f j 广t 订引。算资源l ：运 行自己的代码。 6 公共管理模块：包括用户的管理、网格的临控、计费等功能。 7 通信勺安今= 管理模块：保证网格 = 的活动合法，通信安全。 模块j 1 | j 关系如图1 1 所示。 图1 1 网格基本功能模块间关系 1 2 2 两种典型的网格体系结构 随着分布式计算等其它计算技术的发展和相关标准的提出和完善，以及人们对网 格认识的进一步深化，网格体系结构也在逐步的演进。五层沙漏模型足l a nf o r s t e r 等在网格发展的早期阶段提i j j 来的一种网格体系结构。后来，在以i b m 为代表的工业 界的影响一f ，在网格体系结构中引入了w e bs e r v i c e 技术，提出了日自订j “泛流i r 的丌 放网格服务体系结构( o g s a ，o p e n ( 衍i ds e r v i c e sa r c h i t e c t u r e ) 。o g s a 在较高的层 次上对网格的整体结构和服务进行了抽象的定义，为网格的构建绘制了一幅蓝图。 1 五层沙漏结构 五层沙漏模型n 3 是一种以协议为中心的协议结构，强调“协议”的重要性如图1 2 所示，在血层沙漏结构中，最底层是构造层，构造层面对的是一个个具体的物王里( 也 可以是逻辑的) 资源，它通过对这些局部资源的管理，向上层提供对这些资源的管理 利挖书0 界面。构造层的上l f i f 足连接层，主要是为f 层的物理资源提供安全的数据通信 能力，这是资源之l 开j 进行厅：操作的自，j 提，连接层使得孤立的单个资源之i f j j 建立了联系。 内蒙古科技人学硕i 。学位论j ：= 连接层的上面是资源层，它反映的是抽象的局部资源的特征，f 而资源层i i 面的汇聚层 完成的功能是如何将下面以单个资源形式表现出来的资源集l j 起术，协调解决多个资 源之f n j 的问题。最j 二面的应用层和资源的距离最远，它关心的是有什么样的资源可以 卜h 下而提供给慌拟针i 织，解决不同啦拟纤【织的具体问题。 7 ij 二；多斛1 j 的，j 外一个霞要特点就恐沙漏形状，其内存禽义就恐i q 为各部分m 议的 数量足f i 川的。时于其敲核心的鄢分，要能够实现【：层各种阱议阳核，心的映射，州时 实现核心向下层其他协议的映射，核心协议在所有支持网挤计算的地点都应该得到支 持，冈此核心协议的数嚣不f 够该太多，这样核心协议就形成了伪议层次结构中的。个 瓶颈，存“层结构中，资源层和连接层共同组成了沙漏的瓶颈，是该模型的核心协议 部分，起到了承f 【：启下的作用。 图1 2 五层沙漏模型 2 o g s a g l o b u s 小组和i b m 于2 0 0 2 年初提出了一个新的网格结构，该结构是要将当时网 格领域最热门的两个技术计算网格和w e bs e r v i c e 结合起来，把原来按照两条路 线进行的研究活动1 纳到条主线e 来。o g s a 是一个由i 向服务的系统结构，主要突出 从网格用户的角度看上去的网格系统足什么样子。这是继缸层沙漏结构之后最重要， 也是目自仃最新的一种网格体系结构，被称为足下一代的网格结构。 如果说血层沙漏结构是以协议为中心的“协议结构”，则o ( ；s a 就足以服务为中心 的“服务结构”。这艰的服务是指具有特定功能的网络化实体。在五层沙漏结构中，强 调的是被其享的物理资源( 或者足这些资源技术的服务) ，在o g s a 中，服务所指的概 念更广，包括各种计算资源、存储资源、网络、程序、数据库等等，简而吉之，切 都是服务。“层模型试图实现的是对资源的芪享，而在o ( ；s a 中，实现的将足对服务的 共享。从资源到服务，这种抽象，将资源、信息、数扼等统一起来，f j 分有利于灵活 内蒙古科技人学顺i ：学位论义 的、一致的、动念的共享机制的实现，使得分布式系统管理有了标准的接i - i 和 j 二为。 为了使服务的思想更加明确和具体，o g s a 定义了“刚格服务”一。的概念。 网格服务是一一种w e bs e r v i c e ，该服务提供了一组接门，这些接r j 的定义 j 确并 f - i 遵守特定的啊滞0 ，解决 j 2 务发现、动念服务创建、! l 命刷期管理、通知等| u j 题。舀： ( x ；s ai - l ，将切部石。作足f t q 隆j j t ：务，l j i l d l l , d ： 姚是i 叮扩展的h 洛服务的凭合 ! i j 洛 = ：网恪服务：。州恪服务u r 以 ：川的方式聚集，延术满足虚拟组纵的需婴，虚拟纠1 彩：f - i 身 也可以部分地根掂它们操作嗣i 足享的服务术定义。 个w e bs e r v i c o 就是个可以被l i l 谚 别的软件应i i j 。它的接口霹嘲：j t 使厂h 町 扩腱标记语高( x m i 。，x t e n si b l em a r k u pl a n g u a g e ) 描述和发现，并1 1 可以通过鉴于 i n t e r n e t 的协议直接支持和其它堆于x 4 1 消息的软件应用的交互。w e bs e r v i c o 描述 了一种新f ：现的、晕嘤的分前j 式计算范弋，和d e c ，c o r b a ，j a v ar m i 等方法小川，它 更强凋肇j ：t 弘个i n t e r n e t 标准来解决异构分布汁算的i 、u j 题。 w e bs e l 、ic e 定义了一种技术，用j 二描述被访问的软件组件、访问组i 件的方法以 及找到相关服务提供者的发现方法。 o ( ；s a 符合标准的w e bs e r v i c e 框架。w e bs e r v i c e 解决了发现和激发永久服务的 l u j 题。但是在i 硼格中，大量的是临时服务。因此o g s a 对w e bs e r v i c e 进行了扩展，提 出了网格服务的概念，用丁解决服务发现、动态服务创建、服务卜命周期管理等与临 时j j 技务有关的问题，并且能够动态创建和删除。o ( ；n a 定义了如图1 ：；所，j ；的服务“。 内蒙古科技人学硕i ：学位论文 ：i 1 0 ，：、o 生 g n u se i c e f 1 1 硇s e r v i c e da t a ：蜘；- 嘣毋- j 、 4 j ， 0f u s e t t e n u i n a t i 砒) a t a i 2 甲h i - 一唆笆i j 州鼍f i tl 。 d es t r o v ? 鼍e i ? 0j ，卜 no t i 丘c a 乜。斌o w c e s u b s c n b e t o t l o t q f i c a t l o n t o p , , ： ：+ f 。：。 u l 正j u b s c r l b e t o n o a f i c a t t o n t o p l c 羁ti 囱；1 屯 na t i f i c a 乜o i 豸l n kd e l i v e r no t t f i c a a o n 对：0 踅! 薹i f j ，u r e g , l ：, 走t yr e 孕斌e f s e r v l c e ：，；t ：? 一_ ，6 毛二j ；、幽、i u n r e 昏g t e r s e l c e 墩；m ；+ 艇 fa c t o l yc t e a t e ) e t , n c e 辽ji 。c ? 一2 j 乃j 、p ； p n m m y k e y f i f 虻4 b y p r n 铽 y k e y 九涟魄 r 找j 一 烈殄i i j 曩 d e 嫩o y b y p n m a i y k e y 手盔迄玎l 救；：t 一 峰 ：强碜；l q h a z m g e l 4 a pf i t m t b y h a t l | c g e r 0 ； 嚣 1 1 q 1 ；口 ； ) ：j 、 ? l 1 3 本文的研究内容 1 3 1 课题的提出 图1 3o g s a 定义的接口 随着互联网及计算机技术的飞速发展，i n t e r n e t 上产生了大量不同性质的可利用 资源。研究人员试图将大范围的异构计算机系统组合起来，形成一个巨大的资源共享 平台，我们称之为网格( g r i d ) 。用户通过网格可以方便、快捷的访问到自己需要的资 源，而不必关心其中的细节。网格系统除了向用户提供强大的计算能力以外，还提供 共享各种数据资源、存储空间、网络服务等等。然而，由十网格资源具有分布性、异 构性、动态性、自治性等特点，使得阀格环境f 对资源的管理成为影响网格系统的重 要防l 索之一。 网格资源管理包括：资源发现、资源调度和资源监控，其叶1 资源任务调度是网格 资源管理的核心。计算网格系统实现了不同地理分自珀勺异构资源的共享、选择和聚合， 以解决在科研、工程、经济学等领域大规模的计算问题。随着大规模工程的计算应用 需求，资源调度问题已经变得二 e 常一蓖要。 刚格资源的异构性和地理分仃性使得在大规模分钿环境中的任务凋度成为一个复 杂的问题，而任务调度算法性能的好坏直接决定詹m 格系统性能优劣。鉴于实际。：i ：程 优化i 口j 题的复杂性、大型化、多极值和建模难等特点，网格计算任务调皮基本是n p 问题，寻求一种适用丁大觑模并行n 具有智能特性的通用性较强的全局优化方法已成 为h 格仃务渊| ! ：的个研究热点。 内蒙i i 亍科技人学坝卜学位论文 网格环境f ，如何大范闭地进行资源共享，提高资源的利f j 率，成为提高网格系 统r e 能的一个突出问题。而任务凋度算法是优化系统、提高系统性能的关键，合理有 效的算法能够平衡各个节点的调度负载，以允分发挥节点的作j 丰 ，充分合理地利用各 种资源。 遗f 簟舛法和髓拟退火鳍；上砬| | i | 】 u - ，| j 牛r l 决f t q 浒f t 务凋度伞片6 优化题比较订效的算 法。两种算法鄙是模拟f i 然界的桀些现琢进行大规模优化i u 邀求解的随机性方法，都 不要求 j 标函数的连续性、町微性及凸。阽，而且算法简单，易j ：实现。遗传算法有较 强的全局搜索陀能，仉它的爬i i 能力弱，在实际应瑚巾容易j t - 早熟收敛的问题，在 进化