（计算机应用技术专业论文）网格环境中一种改进的蚁群任务调度算法.pdf

a ni m p r o v e da n tc o l o n y a l g o r i t h mf o rt a s ks c h e d u l i n gi ng r i d b y h u a n g y a n g at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g c o m p u t e ra p p l i c a t i o n i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rl ik e n l i n o v e m b e r ，2 0 10 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。， 作者签名：蒜痞 日期：# o l o 年i 月j 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名： 导师签名： 螽、舡 为之 日期：w d 年l z - 月j 日 日期：汐f 。年f2 ，月j 日 网格环境中一种改进的蚁群任务调度算法 摘要 网格计算环境日益成为一种不受地域限制的廉价的超级计算环境，它试图聚 合分布在世界各地的计算、存储、知识、通信和信息等各类资源，以服务大众为 目的，实现资源共享与协同工作。但由于网格资源具有异构性、动态性、自治性 以及分布性等特点，网格环境下进行任务调度是一个很具挑战性的问题。网格任 务调度算法直接关系到任务执行的速度，在网格技术研究中起着重要作用。 5 0 年代中期仿生学应运而生，人们不断地从生物进化的机理中得到启发，提 出了许多用于解决复杂优化问题的新方法，比如遗传算法、神经网络、模拟退火 算法等，并成功应用于解决实际问题。近年来，许多学者将蚁群算法应用于网格 任务调度技术，并取得了不错的效果。但是目前研究者较少考虑仿生算法初始参 数设置对算法收敛性能的影响。在蚁群算法中存在的信息启发因子a 、期望因子 鼻、信息素强度因子q 、信息素挥发因子p 共四个参数中，a 反应了蚂蚁受其它 蚂蚁经过网格资源节点时留下的信息素影响程度，其值越大，蚂蚁越倾向于选择 其他蚂蚁选择过的资源节点，1 3 反应了蚂蚁受资源的固有属性的影响程度，其值 越大，蚂蚁越倾向于选择条件好的资源，这两个参数的值越大，蚁群算法极易陷 入局部最优。q 能够加强正反馈，使搜索朝有利于寻找最优解的方向进行，p 能 够避免信息素无限积累，从而扩大搜索范围，以提高求解的效率。本文提出了一 种新的改进蚁群算法n a c a ( n e wa n tc o l o n ya l g o r i t h m ) ，先对蚁群算法中的四个参 数进行随机编码，产生染色体，利用蚁群算法得到一组较优解；再利用遗传算法 的优点对这组值进行交叉、变异，选择产生更优的解；最后将这组值作为蚁群算 法下一轮探索的原始值，进行最大次数的循环迭代直至停止，即求得参数组合的 近似最优解。n a c a 利用遗传算法快速随机的全局搜索能力，以探索出蚁群算法 中的四个参数a 、鼻、p 、q 的优化组合，将它应用于网格系统任务调度中，系 统的性能得到了明显的改善。 利用网格模拟器g r i d s i m 对所提出的算法进行了仿真模拟，结果表明所提出 的算法具有更短的调度长度和更宽的适应性，当任务已知时，执行时间约缩短了 2 1 7 ，能有效缩短任务的执行时间，且负载变化时对网格中各处理器资源的影 响大大减小。然而当任务未知和系统规模很大时，算法需要进一步完善。 关键词：网格；任务调度；蚁群算法；g r i d s i m 高校教师硕士学位论文 a b s t r a c t g r i d c o m p u t i n g e n v i r o n m e n th a s i n c r e a s i n g l yg r o w n a v e r y c h e a p s u p e r c o m p u t i n ge n v i r o n m e n tb e y o n da r e a l i m i t i t g a t h e r sc o m p u t a t i o nr e s o u r c e s ， s t o r a g er e s o u r c e ，k n o w l e d g er e s o u r c e ，c o m m u n i c a t i o nr e s o u r c e ，a n di n f o r m a t i o n r e s o u r c ee t c t o g e t h e rf r o ma l lo v e rt h ew o r l d ，a i m sa ts e r v i n gp u b f i ea n dr e a l i z i n g r e s o u r c e ss h a r i n ga n d c o o p e r a t i v ew o r k i n g h o w e v e r , d u e t ot h e h e t e r o g e n e o u s d y n a m i c ，a u t o n o m o u s ，a n dd i s t r i b u t i o na n do t h e rc h a r a c t e r i s t i c si ng r i dr e s o u r c e s ， t a s k s c h e d u l i n gi ng r i d e n v i r o n m e n ti sac h a l l e n g i n gp r o b l e m t a s k s c h e d u l i n g a l g o r i t h mf o rg r i ds c h e d u l i n gi sd i r e c t l yr e l a t e dt ot h es p e e d ，q u a l i t ya n de t c i tp l a y s a ni m p o r t a n tr o l ei nt h eg r i ds t u d y s i n c eb i o n i c sw a sc r e a t e di nm i d d l ep e r i o do f19 5 0 s ，p e o p l eh a v eb e i n gi n s p i r e d f r o mt h em e c h a n i s mo ft h eb i o l o g i c a le v o l u t i o nc o n s t a n t l y m a n yn e wm e t h o d sh a d b e e na p p l i e dt os o l v et h ec o m p l i c a t e do p t i m i z a t i o np r o b l e m sa r ep r o p o s e d s u c ha s n e u r a ln e t w o r k ，g e n e t i ca l g o r i t h m ，s i m u l a t e da n n e a l i n g ，a n de v o l u t i o nc o m p u t a t i o n t h e s en e wm e t h o d sh a db e e ns u c c e s s f u l l ya p p l i e dt os o l v et h ep r a c t i c ep r o b l e m s m a n ys c h o l a r sr e s e a r c ht h et a s ks c h e d u l i n ga l g o r i t h mf o rt h eg r i dt e c h n o l o g y ，a n dh a s a c h i e v e sg o o dr e s u l t si nr e c e n ty e a r s b u tt h e yd o n tt a k ep a r a m e t e ro p t i m i z a t i o ni n t o a c c o u n ta n dv a l u ei n s p i r i n gi n f o r m a t i o np a r a m e t e ra ，t h ee x p e c t a t i o n sf a c t o r1 3 ，t h e p h e r o m o n es t r e n g t hq a n dt h ei n f o r m a t i o nv o l a t i l ef a c t o rpa c c o r d i n gt ot h ep r e v i o u s e x p e r i m e n t i nf a c t ，t h ec o n v e r g e n c ep e r f o r m a n c ea n dc o m p u t a t i o n a le f f i c i e n c yo fa n t c o l o n y a r es e n s i t i v et oi t a na n t s y s t e mb a s e de x p l o r a t i o n e x p l o i t a t i o n f o r r e i n f o r c e m e n tl e a r n i n g d u r i n gt h ef o u rp a r a m e t e r s ，ar e f l e c t st h ei m p a c to ft h e p h e r o m o n eb yt h eo t h e ra n t sl e f tb e h i n da f t e rag r i dr e s o u r c en o d e s t ot h ea n t s t h e g r e a t e rt h ev a l u e ，i ti sm o r ep o s s i b l ef o rt h ea n tt oc h o o s et h es a m er e s o u r c e so ft h e o t h e ra n t s t h ep a r a m e t e rpr e f l e c t st h ei n h e r e n tp r o p e r t i e so fa n t sb yt h ei m p a c to f r e s o u r c el e v e l t h eg r e a t e rt h et w op a r a m e t e r s ，i ti sm o r ee a s yf o ra n tc o l o n y a l g o r i t h mt of a l l i n t ol o c a lo p t i m u m t h ep a r a m e t e rqc a ne n h a n c et h ep o s i t i v e f e e d b a c k ，s ot h a tt h es e a r c hd i r e c t i o nt h a ti sc o n d u c i v et ot h ed i r e c t i o no ff i n d i n gt h e o p t i m a ls o l u t i o n t h ep a r a m e t e rpt oa v o i du n l i m i t e da c c u m u l a t i o no fp h e r o m o n e ， t h e r e b ye x p a n d i n gt h es e a r c hs c o p et oi m p r o v et h es o l u t i o ne f f i c i e n c y t h i sp a p e r p r e s e n t sa ni m p r o v e da n tc o l o n ya l g o r i t h mn a c a ( n e wa n tc o l o n ya l g o r i t h m ) f i r s t l y ， w em a k et h ef o u rp a r a m e t e r so ft h ea n tc o l o n ya l g o r i t h mc o d i n gr a n d o m l ya n dg e tt h e i i i 网格环境中一种改进的蚁群任务调度算法 c h r o m o s o m e s ，as e to fo p t i m u ms o l u t i o n sc o u l db eg a i n e db yu s i n gt h ea n tc o l o n y a l g o r i t h m t h e nt h e yc r o s s o v e r 、m u t a t ea n ds e l e c tb yu s i n gt h ea d v a n t a g e so fg e n e t i c a l g o r i t h m s f i n a l l y ，t a k et h ev a l u eo ft h i sg r o u pt oe x p l o r et h en e x tr o u n da st h ea n t c o l o n y so r i g i n a lv a l u e ，r u n st h em a x i m u mn u m b e ro fl o o pi t e r a t i o n su n t i li ts t o p s n a c am a k ef u l lu s eo ff a s tg l o b a ls e a r c hr a n d o m l yo fg e n e t i ca l g o r i t h ma n de x p l o r e s o p t i m i z a t i o no f f o u rp a r a m e t e r sa 、p 、p 、o ，t h ep e r f o r m a n c eo ft h es y s t e mh a sb e e n s i g n i f i c a n t l yi m p r o v e dw h n ei tw a sa p p l i e dt ot h eg r i dt a s ks c h e d u l i n gs y s t e m s a ne x t e n s i v es i m u l a t i o ns t u d yi ng r i d s i ms i m u l a t i o np l a t f o r mw a sc o n d u c t e dt o e v a l u a t ea n dc o m p a r et h ep e r f o r m a n c eo ft h ea l g o r i t h m si nt h el a t e rc h a p t e r so ft h i s p a p e r t h eo b t a i n e dr e s u l t ss h o wt h a tt h ea l g o r i t h mh a so p t i m a lp e r f o r m a n c ea n d a d a p t ew i d e l y g r i d s i mu s i n gg r i ds i m u l a t o ro ft h ep r o p o s e da l g o r i t h ms 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 ds c h e d u l i n ga l g o r i t h mh a sas h o r t e rl e n g t ha n dw i d e r a d a p t a b i l i t y w h e nt h et a s ki sk n o w n e x e c u t i o nt i m ec o u l db er e d u c e da b o u t21 7 t h ee x e c u t i o nt i m eo ft h et a s ki ss h o r t e ng r e a t l y i ti m p a c tl e s st ot h ep r o c e s s o r r e s o u r c e sw h e nt h el o a do nt h eg r i dc h a n g e s h o w e v e r ，w h e nt h et a s ki su n k n o w na n d t h es y s t e mi sl a r g e ，t h ea l g o r i t h mn e e df u r t h e ri m p r o v e d k e yw o r d s ：g r i d ；t a s ks c h e d u l i n g ；a n tc o l o n ya l g o r i t h m ；g r i d s i m i v 高校教师硕j 二学位论文 目录 学位论文原创性声明和学位论文版权使用授权书j i 摘要i i a b s t r a c t i l l 插图索引一v i i 附表索引v i i i 第1 章绪论1 1 1 本文的研究背景1 1 2 研究现状一2 1 3 本文的主要工作3 1 4 论文结构4 第2 章网格中的任务调度模型5 2 1 网格计算任务调度的特点和主要目标5 2 2 网格中任务调度算法的研究7 2 2 1 简单的任务调度启发式算法7 2 2 2m i n m i n 类型的启发式任务调度算法一8 2 2 3 遗传模拟类的启发式调度算法8 2 3 网格任务调度的困难性一1 0 2 4 小结11 第3 章蚁群算法与遗传算法基本原理一1 2 3 1 蚁群算法的基本原理1 2 3 2 蚁群算法的数学模型1 3 3 3 蚁群算法特点。1 6 3 4 基本遗传算法一l6 3 4 1 遗传算法16 3 4 2 遗传算法基本特点1 7 3 5 蚁群算法与遗传算法的混合的基本方法1 7 3 5 1 混合的基本思想18 3 5 2 变异操作18 3 5 3 交叉操作1 9 3 5 4 遗传蚁群算法1 9 3 5 5 算法测试2 0 v 网格环境中一种改进的蚁群任务调度算法 3 6 小结2 1 第4 章一种改进的蚁群网格任务调度算法n a c a 2 2 4 1n a c a 算法描述2 2 4 2 蚁群算法中参数设置的重要性与盲目性2 2 4 3 利用遗传算法对蚁群算法中的参数进行优化2 3 4 4 网格任务调度相关2 5 4 4 1 网格调度2 5 4 4 2 网格资源的负载平衡2 5 4 5n a c a 实现2 5 4 5 1n a c a 基本思想一2 6 4 5 2 初始定义及假设条件2 6 4 5 3 网格计算环境中n a c a 的设计2 7 4 6 j 、结31 第5 章仿真实验设计与分析3 2 5 1 网络仿真工具3 2 5 2g r i d s i m 模拟器介绍3 2 5 2 1g r i d s i m 与其他仿真工具的比较3 3 5 3g r i d s i m 仿真实验环境的搭建3 4 5 4 仿真实验3 5 5 5 小结3 8 总结与展望3 9 参考文献4 1 致j 射4 6 附录a 攻读学位期间所发表的学术论文目录：4 7 v i 高校教师硕十学位论文 插图索引 图3 1 蚁群系统示意图1 2 图3 2 蚁群算法的一般步骤1 5 图4 1n a c a 算法的基本框图3 0 图5 1g r i d s i m 体系结构3 2 图5 2 调试g r i d s i m 3 5 图5 3 时间与任务节点图3 6 图5 4 负载平衡比较3 7 v i i 网格环境中种改进的蚁群任务调度算法 附表索引 表3 1 几种算法测试结果一2 0 表4 1 各参数意义一览表一2 3 表5 1 网络中间件的模拟3 3 表5 2 网络模拟器的使用特性3 4 表5 3 资源性能参数表3 5 表5 4a c a 与n a c a 执行情况对照表3 6 表5 5 资源负载平衡的比较一3 7 i i 高校教师硕上学位论文 1 1 本文的研究背景 第1 章绪论 所谓网格，即是将分布在世界各地的计算、存储、知识和通信等资源融合 起来形成一个功能强大的虚拟计算机。网格的这个想法始于电力网。在2 0 世纪 9 0 年代中期，网格一词首次被用来描述用于科学和工程分布式计算的基础设施。 这种基础设施把计算资源、数据和软件、存储设施、广域网络、仪器设备等连成 有机的整体，它是一种硬件和软件的综合体系结构，能够将网络、通信、计算和 信息等集合成一体，把整个因特网整合成一个巨大的超级虚拟计算机，方便用户 使用这个基础设施中的任何资源。网格从广义上说是一个集成的计算和资源环境 嵋。j 。它希望人们在使用网格的计算能力等功能时就像使用电力网一样方便，无需 考虑资源在什么地方以及这个资源的配置方法作为一个分布式计算平台，网格能 够解决科学、工程和经济中的大规模计算问题和数据密集型问题，能够实现地理 上广泛分布的高性能计算资源、信息资源、应用系统、服务系统、组织、人员等 各种资源的共享与聚合。它逐步成为一种新的技术和基础设施，可以充分利用集 成的资源形成一个大规模的计算池，其目的是为了在分布、异构、自治的网络资 源环境上构造动态的虚拟组织，并在其内部实现跨自治域的资源共享与资源协作， 有效地满足面向互联网的复杂应用对大规模计算能力和海量数据处理的需求。在 网格计算技术中，网格系统软件起着关键的作用，他提供单一系统映像、透明性、 可靠性、负载平衡和资源共享等功能。网格系统软件中的网格操作系统层提供网 格的底层管理功能，编程和使用环境可提供用户接口，从而使一般应用和专门为 网格开发的应用能方便和有效地利用网格资源。许多行业和领域，如能源、交通、 气象、水利、农林、教育、环保等，以及涉及科研、开发、教育的诸多部门、单 位和企业，对高性能计算网格以信息网格的需求是非常巨大的。 网格计算t s l ( g r i dc o m p u t i n g ) 是伴随着互联网技术而迅速发展起来的，专门针 对复杂科学计算的新型计算模式。在这种计算模式下，利用互联网把空间上分散 的计算机组织成一个“虚拟的超级计算机”，其中每一台参与计算的计算机就相当 于一个“一个节点 ，整个计算网格由成千上万个这样的“节点”组成“一张网格”， 因此将这种计算方式称之为网格计算。它有两个优点：一是数据处理能力极强； 二是能充分利用计算机的闲置处理能力。简单地讲，网格是把整个网络整合成一 台巨大的超级计算机，实现计算资源、存储资源、数据资源、信息资源、知识资 源和专家资源的全面共享【3 】。而网格的动态性和异构性等特征使得网格任务调度 网格环境中一种改进的蚁群任务调度算法 具有一些这样的特点【9 儿1 0 】【1 1 1 。其一，它必须面向异构平台，屏蔽一些底层差异。 其二，它具有分布式的特点，虽然网格任务调度不会影响资源节点内部的调度策 略，但是网格资源分布在世界各地，不可能存在一个任务调度器负责完成网格中 所有任务的调度。更为重要的是，网格任务调度必须具备动态适应性和可扩展性， 才能应对随机出现的资源增加，退出和发生故障等突发情况。网格任务调度这些 特点使得网格任务调度这个组合问题变得异常复杂。一方面，它要求用户提交的 任务实现最优跨度，负载均衡和提高系统的吞吐率；另一方面，它还希望这个调 度符合经济原则并能提高好的服务质量，提高用户的满意度，推进网格的应用与 发展。传统的任务调度策略很少需要考虑资源的异构性、动态性和可扩展性等特 点，以及运行于网格系统之中的应用程序对于资源的不同需求，使得任务调度变 得极其复杂，不好的任务分配策略，将会增加任务的执行时间、降低整个网格系 统的吞吐量。因而，设计一种高效的网格任务调度方法对于网格整体性能的提高 有着重要的意义。网格任务调度问题已经被证明n p 难问题【4 】，因此，网格调度 引起了众多学者的关注，成为目前网格研究领域的一个热点，研究出适合于网格 环境下的任务调度的策略，应对诸如n p 难等问题，意义重大。对此，国内外展 开了广泛的研究并取得一定的成果。 1 2 研究现状 目前，国内外在网格任务调度方面做了大量的研究工作，并提出了一些有效 的算法。 按照子任务之间是否存在依赖关系，可分为独立任务调度算法和依赖任务调 度算法，独立任务调度算法是依赖任务调度算法的基础。就调度策略而言，网格 任务调度策略还可以分为静态调度策略和动态调度策略。静态调度策略指用户提 交任务后，并不立即执行，而是将一个时间段中的任务集中起来，当任务映射事 件到来时集中映射，该算法缺乏灵活性，一旦资源状态发生变化，原先消耗不少 时间计算出来的任务调度列表需要重新计算，增加了用户的响应时间。动态调度 策略却不同，用户提交任务后便马上映射，它能够随着网格环境的变化而变化， 具有较好的适应性和灵活性。常见比较传统的静态调度策略有：m a x m i n 引， m i n m i n e 3 1 ，s u f f r a g e 4 】等；常见的动态调度算法比如蚁群算法【5 1 ，免疫遗传算法【6 l ， 模拟退火算法【_ 7 j 等。蚁群算法和模拟退火算法等启发式智能算法应用于网格任务 调度且达到了预期效果，这些算法毫无争议地成为解决网格任务调度问题的锐利 工具。 作为网格核心服务之一的网格任务调度技术负责完成网格资源的调度工作， 既要体现“鼓励一部分人先富裕起来 又要保证“共同富裕”，充分利用网格资源。 一个好的调度策略能高效地协调和分配网格资源，有效降低网格任务调度的总执 高校教师硕士学位论文 行时间和平衡负载，以提高网格性能。 本文在仔细分析启发式智能化算法蚁群算法和遗传算法基本原理和特性的基 础上，提出蚁群遗传算法n a c a ，将该算法用于解决网格计算环境下的任务调度 问题，减少用户交互付时间，提高用户满意度，最终促进网格的推广与应用。 1 3 本文的主要工作 根据网格的特性，研究适合网格的实用性强、可靠性高、更接近实际网格的 调度算法是当今网格基础研究中急需解决的问题。本课题的主要研究目标是网格 任务调度，网格任务调度考虑的是最早完成时间，即最优跨度。而任务优化是考 虑在网格中如何静态的分配资源给由相互通信的子任务组成的请求。这样分配的 目标是网格环境下最快请求执行时任务。其中，要解决的关键问题就是子任务分 配问题。其目的在考虑最优跨度最小和时间开销消耗最小。 主要研究工作及创新性体现在以下几个方面。 ( 1 ) 对典型的网格任务调度算法的研究和分析。 典型的网格任务调度算法有m i n m i n 和m a x m i n 算法、禁忌算法、遗传算法、 模拟退火算法等。这些算法都有一定的优越性，但是对于网格任务调度这类n p 问题，使用模拟生物进化的遗传算法是最好的选择。 ( 2 ) 基于网格能量和最优跨度提出基于遗传算法的网格任务调度算法。 本文提出了基于遗传算法的网格任务调度算法，该算法综合了网格能量和用 户q o s 里的最优跨度，在满足最优跨度的同时，最小化网格能量消耗，从而在网 格任务最优调度下最大的节约了网格能量消耗。 ( 3 ) 对网格仿真软件的研究及算法仿真。 网格系统的设计是一个非常复杂的系统工程，它需要考虑由于广域共享所引 起的许多问题，比如资源的异构性、动态性以及性能等问题。网格模拟器为帮助 网格系统的设计者验证设计方案、测试设计性能提供了极大的便利。目前常用的 网格仿真工具较多，这些仿真工具各自具备不同的特点，并且适用于不同的体系 结构和操作平台，因此如何选择一种适合于本研究环境的仿真工具也成为本文需 要考虑的问题。本文选择了g r i d s i m 作为仿真工具，介绍了仿真流程和方法，同 时对基于遗传算法的网格任务调度算法进行了仿真分析。 在阅读国内外关于网格任务调度相关文献后，提出了适应网格计算环境，提 高网格任务调度效率的网格任务调度策略n a c a 。论文主要内容包括： ( 1 ) 解析网格环境下，任务调度特征及当前面临的问题，是本文进行理论研 究的前提条件。 ( 2 ) 分析比较仿生优化算法中的蚁群算法和遗传算法的特点，是本文进行理 论研究的现实基础。 网格环境中一种改进的蚁群任务调度算法 ( 3 ) 将蚁群算法和遗传算法融合后的蚁群遗传算法应用于网格任务调度并进 行了必要的仿真，验证该算法合理性和可行性。 1 4 论文结构 本文以介绍网格环境的概念为起点，按照从理论到模型设计再到算法应用的 实现路线，根据现有网格中任务调度算法的不足，首先对传统算法的优缺点进行 阐述以及网格环境中固有特点进行分析，接着提出适用于网格的n a c a 调度算 法，并在仿真平台上进行建模仿真，最后与传统算法进行比较，分析实验结果，验 证了算法的有效性。论文的组织结构和章节安排如下：第一章为绪论，介绍本文 的选题背景，国内外研究动态，并对整个研究的内容和意义做出了说明。第二章 为网格中的任务调度研究，剖析蚁群算法和遗传算法的基本原理及特点，为本文 的研究奠定理论基础。提出适用于网格环境下的任务调度策略蚁群遗传算法 n a c a 在第三章中做出了介绍。第四章首先介绍网格计算环境对任务调度的影 响，然后介绍算法设计思想，仿真实验及分析。仿真结果表明文中对n a c a 调度 算法的扩展在异构网格环境中具有较优的性能和广泛的适应性。第五章总结与展 望。本章节对本文的研究工作进行回顾和总结，并提出了值得进一步探索的问题。 高校教师硕f ：学位论文 第2 章网格中的任务调度模型 2 1 网格计算任务调度的特点和主要目标 网络是把地理上分散的计算机系统通过网络设备连接在一起，相互独立的计 算机系统之间在遵循一定的通信协议的基础上实现资源共享。现代网络大致经历 了三次发展过程，从基于简单设备的相连，到基于w e b 的资源共享，再到更大 范围内实现资源的共享( 即网格技术) 。通过网格这种基础设施，用户不需要了解 网格环境的具体资源细节，就可以在网格环境中使用各种资源提供的计算能力， 完成相关的计算任务【l 引。在网格系统中，任务调度系统是其重要的组成部分，它 要根据用户提交的任务信息采用适当的策略把不同的任务分配到相应的资源节点 上去运行。由于网格系统的异构性和动态性，以及运行于网格系统之中的应用程 序对于资源的不同需求，使得任务调度变得极其复杂，不好的任务分配策略，将 会增加任务的执行时间、降低整个网格系统的吞吐量。网格的目标是资源的共享 与协作，要让加入到网格中的用户能够容易地访问网格资源。在这种网格平台上， 用户不需要使用远程登录( t e l n e t ) 、文件传输协议( f t p ) 等工具就可以使用远 程节点计算资源【l3 1 。现在这些计算资源主要是指一些p c 的资源节点、计算机集 群环境、高性能计算机节点和各种高性能的服务器。 在网格环境中，任务和资源的数目都比较大，任务和资源之间的匹配关系也 比较复杂。任务与任务、任务与资源、资源与资源之间的相互关系最终都会影响 任务的调度顺序和任务与资源之间的匹配。 网格计算任务调度具有以下几个特点【1 4 】： ( 1 ) 任务调度是面向异构平台的。由于网格系统是地理上分布的各类资源组 成，在规模最大的全球性网格中，资源分布在全世界，包括各类主机、工作站甚 至p c 机，它们是异构的，可运行在u n i x 、w i n d o w s 等各种操作系统下，也可以 是上述机型的机群系统、大型存储设备、数据库或其他设备。因此网格系统中的 任务调度必须面向异构平台【l5 】6 。，并在这些平台上实现网格任务的调度； ( 2 ) 任务调度是大规模的、非集中式的。由于网格系统其资源跨越多个管理 域，规模庞大，要实现一种全局的统一集中的任务调度管理是根本不可能的。因 此，网格的任务调度必须以分布、并行方式进行任务的管理与调度； ( 3 ) 任务调度不干涉网格节点内部的调度策略。在网格系统中，各网格节点 的内部调度策略是自治的，网格任务调度系统干预其内部的调度策略是没有必要 的，也是不可能的； 网格环境中一种改进的蚁群任务调度算法 ( 4 ) 任务调度必须具有可扩展性。网格系统初期的计算规模较小，随着超级 计算机系统的不断加入，系统的计算规模也必将随之扩大【1 7 】。因此，在网格资源 规模不断扩大、应用不断增长的情况下，网格系统的任务调度必须具有可扩展性， 不致降低网格系统的性能； ( 5 ) 任务调度能够动态自适应【1 8 】。网格中的资源不但是异构的而且网格的 结构总是不停地改变。有的资源出现了故障，有的新资源要加入到网格中，有些 资源重新开始工作等。 总之网格的动态性是明显的，所以任务调度系统必须适应网格的这种动态性， 从可利用的资源中选取最佳资源为用户提供应用服务。 网格调度的主要目的【l9 】就是：为了完成用户提交的任务和满足用户对任务运 行的要求，把网格中所有可用资源，如计算资源、存储资源和网络资源等与任务 进行匹配，。找到最好最合理的资源配置方式和资源调度策略。在网格系统中，有 大量的应用在运行，有高性能计算方面的应用，也有针对个性消费的个性化应用 需求( 不需要强大的计算能力和存储能力) ，而且随着商业化趋势的加强，后者占 的比例将增加。另外，随着网格技术向商业领域的逐渐延伸，网格服务市场的形 成，网格的调度应充分考虑经济因素，即要引入市场经济的规律。因此网格的调 度设计必须在传统高性能计算和分布式系统中的调度策略和技术的基础上，结合 网格的具体特征。 调度问题一般可分为两大步： s t e p l ：是在空间上对计算和数据进行分配，包括选取给定任务所需要的资源 组，将任务交给这些资源去执行，并分配相关的数据和计算等； s t e p 2 ：就是在时间上和空间上为计算和通信进行排序，包括在计算资源上为 不同的任务进行排序，同时为不同任务之间的通信进行排序。 具体的目标【2 0 】包括：最优跨度( o p t i m a lm a k e s p a n ) 、服务质量q o s t 2 1 】【2 2 】 ( q u a l i t yo fs e r v i c e ) 、负载均衡( l o a db a l a n c i n g ) 、经济原则( e c o n o m i cp r i n c i p l e s ) 在蕾 守o ( 1 ) 最优跨度 跨度是一个最主要、最常见的目标，指的是调度的长度，也就是从第一个任 务开始运行到最后一个任务运行完毕所经历的时间。跨度越小说明调度策略越好。 当用户向网格系统提交任务后，最大的愿望是网格系统尽快完成自己的任务。可 见，实现最优跨度是用户和网格系统的共同目标。 ( 2 ) 服务质量 网格系统要为用户提供计算和存储服务时，用户对资源需求情况是通过服务 质量的形式反映出来的。任务管理与调度系统在进行分配调度任务时，必然需要 保障网格应用的服务质量。 高校教师硕上学位论文 ( 3 ) 负载均衡 在开发并行和分布式计算应用时，负载平衡是一个关键问题。网格系统的发 展更加突出了这个问题。网格任务调度是涉及交叉域和大规模应用的调度，解决 好系统的负载均衡势在必行。 ( 4 ) 经济原则 网格环境中的资源在空间上很分散，而且每个资源都归属于不同的组织，都 有各自的资源管理机制和政策。根据现实生活中的市场经济原则，不同资源的使 用费用也是不尽相同的。市场经济驱动的资源管理与任务调度必须保证消费双方 ( 资源使用者和资源提供者) 互惠互利，才能使网格系统持久地发展下去，因此， 任务调度还需要考虑网格运行成本。 本文算法研究涉及的目标包括时间跨度、负载均衡。时间跨度成为仿真实验 结果比较的重要指标。 2 2 网格中任务调度算法的研究 网格调度定义为将网格任务映射到多管理域的资源上的过程【2 3 1 ，就是将待处 理的任务按照用户指定的某种成本函数如性能或费用，或者按照网格系统性能指 标进行最优化映射到特定的物理资源上。这是一个n p 完全问题，可以使用不同 的算法来得到最优或近似最优解。网格中的任务调度算法可以根据调度任务的属 性分为两类【2 4 1 。第一类是任务相互之间不存在依赖关系，这种任务的集合成为元 任务，将在这一节进行讨论；第二类任务相互间存在依赖关系，如任务b 必须在 任务a 执行完成以后才能开始执行，这类任务之间的关系可以用有向无环图表示， 将在下一节中讨论。 如上所述，元任务是一组没有数据依赖的相互独立的任务集合。这里讨论的 静态任务模型【2 5 】【2 6 1 基于以下假设：( 1 ) 任务集中的任务都是元任务；( 2 ) 每台机 器在一个时刻只能执行一个任务，机器执行任务的顺序是按照任务到来的先后顺 序进行的；( 3 ) 异构计算环境中的机器数量m ，待调度的任务集合的元素个数n 以及机器执行任务的快慢均为已知。我们将对三种类型的启