（计算机应用技术专业论文）基于dcg3a的网格任务调度研究.pdf

摘要 网格环境强调资源的共享和协作给用户带来了便利，同时也对任务调度技术提出了 很高的要求。一个良好的任务调度策略要能高效地协调和分配网格资源，有效降低网格 计算的总执行时间和总耗费，从而使网格达到最佳的性能，网格环境下的任务调度问题 现在是网格计算的研究热点之一。 目前存在的网格任务调度算法，如基于遗传算法、蚂蚁算法、模拟退火算法、禁忌 搜索算法等的启发式智能调度算法，虽各有优点，但都不能单独实现对网格任务的最优 调度，而且没有将遗传算法和蚂蚁算法结合在一起来解决网格任务调度问题的策略。 本文的研究思路是对遗传算法和蚂蚁算法进行改进使其应用于网格环境中的任务 调度，采用理论与仿真实验相结合的方法，围绕网格任务调度的相关问题，展开探索， 具体工作如下： 在综述网格任务调度的研究内容、意义及研究现状的基础上，分析网格任务调 度目前存在的主要问题； 对启发式智能化方法进行研究，提出兼顾遗传算法和蚂蚁算法优点的动态融合 的遗传蚂蚁算法( d y n a m i cc o m b i n a t i o no fg e n e t i ca l g o r i t h ma n da n ta l g o r i t h m ， d c g 3 舢，并用马尔可夫理论分析该算法的收敛性；根据网格计算对任务调度 的要求，对d c g 3 a 进行改进，设计应用于网格环境的任务调度策略： 研究网格系统的负载平衡问题，提出动态负载平衡因子，并将其引入算法中， 以提高系统的负载平衡； 对g r i d s i m 进行深入研究，提出基于g r i d s i m 工具的分模块的任务调度模拟实 现方法，并在此基础上构建本文的任务调度算法模拟平台； 在构建的模拟平台上对本文所提出的网格任务调度算法进行仿真，验证该算法 的可行性和高效性。 关键词：网格环境；任务调度；遗传算法；蚂蚁算法；仿真 a b s t r a c t g r i de n v i r o n m e n te m p h a s i sr e s o u r c e ss h a r i n ga n dc o o p e r a t i o n , t h a tb r i n g sg r e a tn o to n l y a d v a n t a g e sb u ta l s ot a s ks c h e d u l i n gp r o b l e m s b yh a r m o n i z i n ga n dd i s t r i b u t i n gt h eg r i d r e s o u r c e se f f i c i e n t l y , a na d v a n c e dt a s ks c h e d u l i n gs t r a t e g yc a nr e d u c et o t a lr u nt i m ea n dt o t a l e x p e n s eg r e a t l ya n db r i n g a n o p t i m a lp e r f o r m a n c e s ot a s ks c h e d u l i n gu n d e rg r i d e n v i r o n m e n t si so n eo ft h ek e yr e s e a r c hf i e l d so f g r i ds y s t e m s a tp r e s e n t ，an u m b e ro fg r i dt a s k ss c h e d u l i n ga l g o r i t h m s ，s u c ha sg e n e t i ca l g o r i t h m ( g a ) ， a n ta l g o r i t h m ( a a ) ，s i m u l a t e d a n n e a l i n ga l g o r i t h ma n ds u f f e r a g ea l g o r i t h me t c ，h a v e a d v a n t a g e sa n dd i s a d v a n t a g e so b v i o u s l y , w h i c hc a nn o t f i n i s ho p t i m i z i n gt h et a s ks c h e d u l i n g b yh s e l fa n das t r a t e g yt h a tc o m b i n e sg aa n da ai sn o tb r o u g h tf o r w a r d t h er e s e a r c ht h o u g h to ft h i st h e s i si sm o d i f i e dg aa n da ai no r d e rt ou t i l i z et h e mi n t o t h et a s ks c h e d u l i n go fg r i de n v i r o n m e n t ，m a k i n gt h ef o l l o w i n gc o n t r i b u t i o no ns o m er e l a t e d r e p u t a t i o np r o b l e m sb ym e a n so ft h e o r e t i c a la n a l y s i sa n ds i m u l a t i o ne x p e r i m e n t ： t h e p r o b l e m so fg r i dt a s ks c h e d u l i n ga r ea n a l y z e dt h r o u g hs u m m a r i z i n gr e s e a r c h c o n t e n ta n ds i g n i f i c a n c eo fg r i dt a s ks c h e d u l i n ga n dr e s e a r c ha c t u a l i t y ； a c c o r d i n gt ot h er e s e a r c ho fh e u r i s t i ca l g o r i t h m s ，ad y n a m i cc o m b i n a t i o no f g e n e t i ca l g o r i t h ma n da n ta l g o r i t h mi sp r o p o s e d ，w h i c hh a sb o t ht h ea d v a n t a g e so f g aa n da a a n dc o n s i d e r i n gt h et a s ks c h e d u l i n gr e q u e s to fg r i d c o m p u t i n g e n v i r o n m e n t ，d e s i g nan e wg r i dt a s ks c h e d u l i n gs t r a t e g yb a s e do nt h ea l g o r i t h m ； p r e s e n t i n gt h el o a db a l a n c ef a c t o ri nt h ea l g o r i t h m , s ot h eb a l a n c eo fs y s t e mi s i n c r e a s e d ； t h e d e v e l o p m e n ta p p r o a c ho fs c h e d u l i n gs i m u l a t i o nb a s e do ng r i d s i mi sp r e s e n t e d a n dt h es i m u l a t i o np l a t f o r mo f t h ed c g 3 ai ss e tu p d o i n gap r o t o t y p ee x p e r i m e n to ft h ea l g o r i t h m so nt h es i m u l a t i o np l a t f o r ma n d e x p e r i m e n t a lr e s u l t ss h o wt h e i rf e a s i b i l i t ya n ds u p e r i o r i t y ； k e yw o r d s ：g r i de n v i r o n m e n t ；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 ；a n ta l g o r i t h m ； s i m u l a t i o n i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：寸l 观罕 日期：叼年j 月以e t 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名： 寸阢学 日期：叫年月也日 导师签名： 醐。1 引朋砌 1 1 研究背景 第一章概述 在现代科学研究和应用领域中，科研工作者需要访问和处理庞大的数据来解决科学 问题。这些问题不仅计算复杂而且计算量大，许多数据分析需要千亿次甚至万亿次计算。 但现有的数据管理体系结构、方法和技术已经不能满足人们对高性能、大容量分布存储 和分布处理能力的要求。在这种背景下，人们提出网格( g r i d ) 的构想，试图通过共享、 选择和集中地理上分布的异构资源来解决广域上的科学、工程和商业问题【1 。简单的说， 网格是一个集成的计算与资源环境，或者说是一个计算资源池，它将分布的计算机无缝 的组织起来协同解决复杂的计算问题。网格计算是当今计算机科学领域最新兴起的一项 高学术价值和应用价值的研究课题圈。 网格环境强调资源的共享和协作，这给用户带来了便利，但同时也对任务调度技术 提出了更高的要求【3 1 。用户通过向网格系统提交计算任务来共享网格资源，网格调度程 序再按照某种策略把这些任务分配给合适的资源。高效的调度策略或算法可以充分利用 网格系统的处理能力，从而提高应用程序的性能。然而网格的异构性和动态性，以及运 行于网格系统之中的应用程序对于资源的不同需求，使得任务调度变得极其复杂，不好 的任务分配策略，会增加任务的执行时间，降低整个网格系统的吞吐量。由此可见，调 度问题的有效全面解决是网格走向实际运用的一个关键因素。因此，网格任务调度问题 的研究，对当前和未来网格的发展和应用都将有重要的理论意义和巨大的实践价值【4 】。 1 1 1 网格的概念 随着网格技术的不断发展，“网格”吸引了越来越多的人的关注。当更多的人投入到 网格研究中来的时候，很多的困惑也随之产生了。一些初学者还不知道网格究竟是什么， 究竟具有什么优点使之受到如此的重视。 “网格 是借鉴电力网的概念提出来的，希望成熟的网格如同电网一样，用户只要 把设备的插头插入网格的“插座”，就可以使用网格中的资源，而不需要知道具体供应 方( 高性能计算机和其他信息资源) 。显然，网格将从根本上改变了计算机( 尤其是超 级计算机) 使用的模式和概念【5 】。图1 1 是对电力网和网格组成的简单对比。 全球网格研究的领军人物、美国阿岗( a r g o n n e ) 国家实验室的资深科学家、美国 g l o b u s 项目的领导人i a nf o s t e r 在网格：一种新的计算基础设施蓝图中这样描述网格： “网格是构筑在互联网上的一组新兴技术，它将高速互联网、高性能计算机、大型数据 库、传感器、远程设备等融为一体，为科技人员和普通百姓提供更多的资源、功能和交 互性。互联网主要为人们提供电子邮件、网页浏览等通信功能，而网格的功能则更强， 它能让人们透明的使用计算、存储等其他资源f 6 】。” 2 0 0 0 年，i a nf o s t e r 把网格进一步描述为：“在动态变化的多个虚拟机构间共享资源 和协同解决问题【7 l 。 2 0 0 2 年7 月，i a nf o y e r 在什么是网格? 判断是否网格的三个标准 一文中，限定网格必须同时满足三个条件【s 】：( 1 ) 在非集中控制的环境中协同使用资源； ( 2 ) 使用标准的、开放的和通用的协议和接口( i a nf o y e r 认为目前只有g l o b u s 才算得 上标准协议) ；( 3 ) 提供非平凡的服务。 清华大学李三立院士将网格与信息高速公路做了比较，他认为：“将先进计算基础 设施( 网格) 与信息高速公路相比较，可以说信息高速公路是信息传输和获取的信息基 础设施；而先进计算基础设施则是信息处理的信息基础设施。虽然，国内外都有不断扩 充信息高速公路频带宽度、改进路由器性能的计划；但是，国外专家认为：真j 下的下一 代信息基础设施是先进计算基础设施。它将使以计算机为主体的信息处理发生根本性的 变化【9 】。 中科院计算所李国杰院士认为：“网格不同于国外正在搞的i n t e m e t 2 或下一代i n t e m e t ( n g i ) ，网格可以称作是第三代i n t e m e t ，其主要特点是不仅仅包括计算机和网页，而 且包括各种信息资源，例如数据库、软件及各种信息获取设备等，它们都连接成一个整 体，整个网络如同一台巨大无比的计算机，向每个用户提供一体化的服务n o ，。” 电力网构成示意图 网格组成示意图 图1 1 电力网与网格组成的对比 2 圈 圉 从上述定义可得出网格有四个方面的特点： 分布性与共享性 网格的分布性是指网格资源的分布性，即组成网格计算能力不同的计算机，各种类 型的数据库乃至电子图书馆，以及其它的各种设备与资源，是分布在地理位置互不相同 的多个地方，而不是集中在一起。分布的网格一般涉及的资源类型复杂，规模较大，跨 越的地理范围较广。图1 2 展示了网格的分布特性。 图1 2 网格的分布性 网格资源虽然是分布的，但却是可以充分共享的。即网格上的任何资源都可以提供 给网格的使用者。共享是网格的目的，没有共享便没有网格，解决分布资源的共享问题， 是网格的核心任务。分布是网格硬件在物理上的特征，而共享是在网格软件下实现的逻 辑上的特征。 自相似性 分形模型有个非常重要的特征就是自相似性。自相似性在许多自然和社会现象中都 大量存在，一些复杂系统现在都具有这种特征，网格就是这样。网格的局部和整体之间 存在着一定的相似性，局部往往在许多地方具有全局的某些特征，而全局的特征在局部 也有一定的体现。 动态性与多样性 网格具有动态性，原来拥有的资源或者功能，在下一时刻可能会出现故障或者不可 用；而原来没有的资源，可能随着时间的推移不断地加入进来。网格的动态性包括动态 增加和动态减少两个方面的含义。 网格资源是异构和多样的。在网格环境中可以有不同体系结构的计算机系统和类别 不同的资源，因此网格系统必须解决这些不同结构、不同类型资源之间的通信和互操作 问题。 自治性与管理的多重性 网格上的资源属于某一个组织或者个人，其对该资源具有最高级别的管理权限，网 格应该允许资源拥有者对他的资源有自主的管理能力，这就是网格的自治性。但网格资 源也必须接受网格的统一管理，否则不同的资源就无法建立相互之间的联系，无法实现 共享和互操作，无法作为一个整体为更多的用户提供服务。因此网格的管理具有多重性， 方面允许网格资源的拥有者对网格资源具有自主性的管理，另一方面又要求网格资源 必须接受网格的统一管理。 1 1 2 网格的发展及其任务调度 网格计算一开始更多地被称为元计算，从2 0 世纪9 0 年代中期出现的元计算系统开 始，网格的发展过程可以分为三个阶段【i l 】。 萌芽阶段：在2 0 世纪9 0 年代早期，网格被称为元计算环境( m e t a c o m p u t i n g e n v i r o n m e n t ) ，通常用来连接超级计算机为要求高性能的应用提供计算资源，典型的 系统有i w a y 。 早期实验阶段：在2 0 世纪9 0 年代中期，异构、分布的资源共享问题得到了重视， 这个阶段各种计算网格的研究项目相继出现，如i w a s 项目1 1 3 1 ，以及一些学术性的软 件项目，如：g l o b u s 、l e g i o n 等，在此基础上还派生出一些应用实验研究项目。 迅速发展阶段：人类进入2 1 世纪以来，网格计算出现大量的应用实体和项目，工 业界对网格计算的兴趣也不断增长。如：i b m 、p l a t f o r m 、m i c r o s o f t 、s u n 和c o m p a q 等公司，对网格计算技术均给予了极大的关注，并成立相应的全球网格论坛( g g f ) 组织， 该组织现己涵盖了2 0 多个国家。在这一阶段中，面向服务的模型和元数据是最关键的概 念，二者构成了o g s a ( o p e ng r i ds e r v i c ea r c h i t e c t u r e ) 的核心思想 t 2 1 。 随着网格技术的飞速发展，人们逐渐认识到从尖端的科研到同常生活，不同的国家 乃至世界都需要网格，与此同时人们对网格的性能要求也越来越高。因此，网格技术的 研究受到了人们极大的关注。网格技术的研究内容十分丰富，其中包括：网格基础研究、 网格体系结构、网格性能分析、网格资源管理、网格任务调度、网格数据管理、网格信 息服务及网格安全等方面 1 3 1 。 网格任务调度是网格的核心技术，可以描述为合理解决计算任务在地理分布的各种 资源之间的动态调度。任务调度是并行分布计算中最具挑战的问题之一，同时也是一个 n p 完全问题【h 1 ，所以成为了分布式计算研究领域的焦点。随着网格的出现，任务调度中 出现了很多新的特征，网格平台对任务调度提出了新的要求。网格有大量分布共享的异 构资源组成，这些资源协同提供了巨大的计算能力。但由于网格计算中资源在广域上分 布、自主管理、本质上异构、负载动态变化等特性，使得网格环境下的任务调度面临的 问题比传统分布式环境要复杂得多。 随着对网格研究的日趋深入，人们逐渐认识到任务调度在网格系统中的重要作用 【”】。图1 3 描述了任务调度模型与计算网格原型系统的相互关系。首先，任务调度是提高 网格计算性能的一项非常关键的技术，它能通过改善任务划分和处理器的分配，以及适 量的任务复s u ( u p 在不同节点上执行相同的任务) 达到隐藏通信时延的效果。其次，采用 适宜的任务调度策略可以提高资源的利用率和任务吞吐量，充分利用节点问的计算资 源，使用负载平衡技术以改善系统的性能。因此，网格研究的侧重点由对网格的体系结 构的建立以及网格在某些专门领域的应用方面的研究向以分布式并行算法和通信为重 要内容的网格计算资源管理和任务调度的研究转变c 佑】。综上所述，设计一种网格环境下 的合理、高效的任务调度算法对促进网格计算的发展和提高网格的实用性具有十分重要 4 的意义。 网格c l i e n t网格c l i e n t 网格c l i e n t 、 一 、 g i r dp o r t a l w e bs e r v e r 扩展的信息服 r e q u e s t 。返回作业状况、结务( e x t e n d e d m d s ) y 网格中间件( 计算代理) 任务调度子系统r 网格计算中间件基 卜_ 一础功能 网格节点网格节点网格节点网格节点 ( w i n 3 2n o d e )( l i n u xn o d e )( c l u s t e rn o d e )( o t h e rn o d e ) 甲甲甲甲 资源采集模块 图1 3 任务调度模型与计算网格原型系统的关系 事实上，将网格调度的研究内容缩小到以任务调度为主，其研究内涵已经缩小了很 多，但要进行真正意义上的网格任务调度研究，还必须解决以下几方面的问题： 资源发现和管理模型的建立； 任务调度模型的设计； 高效任务调度算法的研究； 多种算法的性能比较； 仿真系统的实现。 要解决这些问题，目前的研究工作还有待进一步的深入。为设计一种高效、实用的 网格任务调度策略，作者通过概括已有的研究工作，提出一种新的启发式智能调度策略， 用于网格环境的任务调度。 1 2 网格任务调度的研究现状 网格的出现，对分布式调度研究提出了新的挑战。目前对于网格任务调度的研究主 要集中在改进调度算法上。但根据网格计算任务调度系统的特点，传统的调度算法不能 很好的适应网格资源的要求，因此寻找一种更适合网格环境的任务调度算法一直是众多 网格研究者努力的方向【1 7 l 。 1 2 1 国外研究现状 目前，国外已有许多科研组织对网格任务调度进行了研究。 g l o b u s t 8 1 项目是目前国际上最有影响的与网格计算相关的项目之一，它的前身是当 初美国建立的一个试验环境i w a y ( i n f o r m a t i o nw i d ea r e ay e a r ) ，它把位于美国1 7 个 不同地点的6 0 多个组织的超级计算机和资源通过高性能网络联系起来，进行大规模科学 模拟、协同工程、并行计算等科学研究。作为目前网格计算事实上的标准，g l o b u s 没有 专门的任务调度器，g l o b u s 资源分配管理g l o b u sr e s o u r c e a l l o c a t i o nm a n a g e r ( g r a m ) 是网格计算环境中的任务执行中心，负责远程应用的资源请求处理、远程任务调度处理、 远程任务管理等工作，负责对r e s o u r c es p e c i f i c a t i o nl a n g u a g e ( r s l ) 信息的解析和处理 工作，g r a m 的结构如图1 4 。其中任务的提交和调度算法都不是很完善，任务的提交采 用命令行手动方式，任务调度采用轮循方法，容错性差，没有考虑负载平衡。 图1 4g r a m 的结构图 a p p l e s j ( a p p l i c a t i o nl e v e ls c h e d u l i n g ) ，由加利福尼亚大学圣迭戈分校开发，是 适用于多用户、分布式异构环境的高性能调度系统。它着重研究和开发在网格中调度单 个应用的职能主体。a p p l e s 智能主体嵌入到应用中，每个网格应用程序都由自己的 a p p l e s 系统进行调度。对应用而言将任务映射到资源的调度是集中式的，但实际运行 应用的各个任务则由本地的调度器负责。p a r a m e t e rs w e e pt e m p l a t e 是a p p l e s 项目中一套 用户级的中间件，它针对的主要应用是p a r a m e t e rs w e e p a p p l i c a t i o n 。它的主要目标就是 将任务以最有效的方式调度到资源上去运行，使得应用以比较高的效率被完成。为了实 现这个目标p a r a m e t e rs w e e pt e m p l a t e 提出了一个自适应的任务调度算法，在这个算法 中，w o r k q u e u e 、m i n - m i n 、m a x - m i n 、s u f f e r a g e 等调度策略都可以被使用。而针对p a r a m e t e r s w e e pa p p l i c a t i o n q b 存在任务共享输入文件的情况。c a s a n o v a 等 2 0 1 在s u f f e r a g e 算法基础上 6 改进后提出一个新的调度策略_ x s u f f e r a g e ，实验证明，共享文件越大，x s u f f e r a g e 的优 越性越明显。 n i m r o d g t 烈) 是由澳大利亚的m o n t h 大学开发的针对参量研究用来管理资源和调度 应用自动执行的网格资源代理。它由四个关键构件组成：任务管理引擎、调度器、分派 器和职能主体。n i m r o d 系统的主要目的就是在保证用户需求得到满足的条件下为用户提 供最经济的计算模式。为了达到这个目的，n i m r o d 系统中采用了d e a d l i n ea n db u d g e t c o n s t r a i n e d ( d b c ) s c h e d u l i n ga l g o r i t h m ，此算法根据用户任务对完成时间以及花费预算 的要求对任务进行调度，遵循层次的、分布式的调度模型，模型如图1 5 所示。其中， 根据算法的侧重点不同，此算法又有d b ct i m eo p t i m i z a t i o n 、d b cc o s to p t i m i z a t i o n 和d b c c o s t t i m eo p t i m i z a t i o n _ 三_ 种分支【2 2 1 。n i m r o d g 相关的研究成果还包括一个称为g r i d s i m 的工 具集，提供复杂的设置及支持网格任务调度的建模与模拟，可用于评估调度算法的性能。 ab 金s q u r 金d q m a i n 图1 5n i m r o d 网格资源管理与调度模型 c o n d 0 1 4 2 3 1 是一个批处理调度系统，通过分布式环境支持高吞吐率计算，利用分布式 环境的空闲资源处理长周期、大数据量应用，体系结构如图1 6 所示。针对这种应用， c o n d o r 使用的调度方法就相对简单一些。它定义了一套半结构化的数据模型 叫l a s s i f i e da d v e r t i s e m e n t ，用于描述资源的特性和表达用户的需求。它的调度分为两 部分匹配和声明，在匹配阶段，m a t c h m a k e r 在获得资源中找到最合适任务的资源， 然后通知用户和服务提供者，随后用户和服务提供者再进行声明，以此确立两者之间消 费与服务的关系。 7 图1 6c o n d o r 体系结构 c o n d o r 的网格调度器是集中式的，用户向c o n d o r 系统提交一个任务，通过调度器 找到一个可用资源并将任务调度到资源上运行，一旦由于某些原因资源变成不可用，系 统会将任务迁移到其他可用资源上继续执行。集中式调度易于管理、部署和协调分配资 源，但是其调度器是一个单点故障和性能的瓶颈，限制了可伸缩性和容错性，用于支持 网格计算环境中的动态调度服务发现仍有其局限性。 b o n d 2 4 1 由美国普渡大学开发的面向对象的网格计算中间件系统。在任务调度方面采 用分布式调度器、可预测价格模型、在线重调度方法、固定的面向应用的调度策略等。 其资源管理体系结构是采用层次模型。 l e g i o n v s 堤：一个面向对象技术在网格领域应用的重要实例，由维吉尼亚大学开发。 它支持透明的调度、数据管理、容错、站点自治和各项安全选项，并且提供了资源预约 的能力，允许应用层调度器执行周期性调度或批调度。l e g i o n 资源管理架构是层次型的， 使分布式调度策略，它支持缺省的面向系统的调度策略，但是也允许通过资源代理扩展 策略。 除以上几个对任务调度研究较多的项目外，j a v a l i n d 拍) 、n e t s o l v e t m 、d a t a 研i d 【冽、 t e r a g r i d v 9 1 、u n i c o r e 、s e t i h o m e 、e s c i e n e 等也对网格任务调度进行了相关的研 究。 综上所述，就现有项目而言，面向系统的调度( 女h c o n d o r g ) 与面向服务的调度 ( a p p l e s 、n e t s o l v e 等) 主要调度对象是面向科学计算任务的处理器、存储器和网络等 硬件资源，面向用户提供的接口也是针对批处理作业提交设计的接口。它们的调度目标 比较单一，主要是实现计算节点的负载平衡。表1 1 简要比较了几个网格项目对任务调度 的支持情况： 8 表1 1 部分网格系统对任务调度的支持对比表 网格系统调度组织任务类型调度策略调度方式调度自适应性 在线调度 a p p l e s 集中式单一任务用户自定义是 ( o n l i n e ) 单一任务总完成时间最短批处理 n e t s o l v e分布式否 任务池任务队列优化 ( b a t c h ) 单一任务任务资源匹配在线调度 c o n d o r 集中式否 并行任务系统利用率最大 n i m r o d 分布式任务池成本或时间最优批处理是 l e g i o n 层次式单一任务取决于系统在线调度 否 1 2 2 国内研究现状 国内网格研究发展也很迅速，在任务调度方面，较典型的是中科院计算所在实际网 格项目中提出的系列调度方法，如织女星项目中基于网格资源空间及s l a ( s e r v i c el e v e l a g r e e m e n t ) 的作业管理等【3 0 】。除科研机构外，很多学者也对其进行了相关研究。 启发式智能任务调度 启发式智能调度【3 l ，是我国近年来研究的热点，马学彬等【，：】提出一种改进的遗传算法， 用以解决网格的任务调度问题。该算法所处理的任务不仅可以包含多个有前后约束关系 的子任务，并且每个子任务可以需要多种资源。刘洋等 3 3 1 针对遗传算法存在的问题并受到 遗传算法的新研究进展的启发，提出一种进化算法和禁忌搜索相结合的新型混合调度算 法。李宗勇等 3 4 1 利用图论的思想将任务间依赖关系描述为满足一定条件的有向无环图 ( d a g ) ，通过d a g 图精确描述任务的优先级，并根据任务间的约束关系，调整蚁群算 法获得的元任务分配结果，从而解决参数相关任务的调度问题。陈廷伟等1 3 5 1 提出一种任 务调度机制，将任务集合到资源集合的映射关系表示为一个称作任务资源分配图的有 向无环图，把网格任务调度问题转化为任务资源分配图优化选取问题，并将免疫遗传 算法应用于任务资源分配图优化选取。李季等1 3 6 1 对网格任务调度问题进行了模糊化，以 a i s 的克隆选择算法为基础，提出基于人工免疫系统的网格任务调度算法。王敏等 3 7 1 提出一种基于改进微粒群算法的网格任务调度方法，通过预测任务执行时间，自适应地 进行任务调度，实现网格资源的优化调度和分配。 基于a g e n t 的任务调度 a g e n t 技术源自于人工智能，其概念在6 0 年代就已提出来，真正的发展在9 0 年代， 9 现在正向计算机领域的各方面渗透。张颖峰等f 3 8 】提出基于a g e n t 的网格任务调度，调度问 题被简化成如何在各a g e n t 之间分配计算任务并随时根据a g e n t 的变化情况进行调整，以 及在各a g e n t 内如何进行子任务的继续分配。这样的层次结构具有高度的可扩展性，便于 在网格这样的庞大异构环境中运用。图1 7 描绘了它的调度模型。李春林等 3 9 1 提出一种基 于a g e n t 的计算网格( a g e n tb a s e dc o m p u t a t i o n a lg r i d ，a c g ) 任务管理方案，给出了网 格资源的描述，并设计了实现网格资源管理的三个网格协议原型：服务登记协议，服务发 现协议和服务访问协议。描述了它们的构成要件及功能作用。该a c g 资源管理方案可为 网格的计算资源和服务提供一个统一的高层管理框架。 w e b 用户 图1 7 多a g e n t 网格任务调度模型 基于p e t r i 网的任务调度 p e t r i 网作为模拟与分析具有并发、异步、动态等特点的信息处理系统的有力工具， 在调度中得到大量应用 4 0 l 。韩耀军等 4 1 1 提出一个可用于网格计算任务调度的高级时间 p e t r i 网fe x t e n d e dh i g hl e v e lt i m e dp e t r in e t ，e h l t p n ) 模型。在该模型中，分配给转移 的点火时间是输入库所t o k e n s 的函数，并利用e h l t p n 构造了一个网格计算的任务调度 的简单模型，并定义一个e h l t p n 的可达调度图( r e a c h a b l e s c h e d u l i n gg r a p h ，r s g ) 用来 分析任务调度的时间特性。胡志刚等 4 2 1 用有色p e t r i 网对各层次的资源调度进行建模， 利用共享合成技术得到整个系统资源调度的p e t r i 网模型。张绍华等 4 3 1 将动态建模语言 d p e t r in e t 应用到网格调度中。图1 8 为采用c p nt o o l1 4 为网格调度系统建立的c p n 抽 象模型。 图1 8 网格调度系统c p n l o 基于计算经济的任务调度 随着网格调度研究的深入，经济模型【钳l 越来越受到相关学者的青睐。朱春玲等t s 1 在 经济原则的基础上为调度问题引入了成本( c o s t ) 概念，并为此设计了网络通信成本函 数、c p u 成本函数、存储器成本函数。当一个新任务到达后，分别计算相应的成本函数为 该任务选择一个成本最低的主机进行调度。游新冬等1 4 6 1 针对网格环境中的动态性特点， 特别是用户o o s 要求的动态变化性，提出一种基于效益函数的网格任务调度算法，该调 度算法在代价上优于基于时间优化的调度算法；而花费相同预算的情况下，在时间上优 于基于代价优化的调度算法。 除上述调度算法外，还有很多其他的算法。王伟铮，提出一种基于信任机制的任务 调度模型，利用b a y e s 方法对可信度进行评估，将节点的可信度并入d l s 算法【4 8 】得到可信 动态级调度算法；周维等【4 9 】提出了一种以策略为机制的网格任务调度模型；王兴红等【划 提出一种新的元任务调度算法，该算法根据网格中当前可用的计算资源、存储资源和元 任务对这些资源的不同需求，选择一些任务预先分配到其中的一种资源上。再根据运行 时资源的可用情况，调整预分配任务运行顺序和给未预分配的任务分配资源，平衡计算 资源和存储资源的负载并使元任务的完成时问趋向最短。 1 2 3 目前本项研究存在的问题 到目前为止人们提出了很多网格系统的调度技术和算法。但是不少调度算法缺乏完= 整的理论依据，一些调度技术的结论还仅源于仿真结果，至今未形成网格计算的任务调 度理论。因此该领域的研究还有待进一步发展和完善。通过上文对网格任务调度现状的 分析，目前网格任务调度的研究主要还存在着以下几点不足： 缺少有效的资源发现和管理模型以提供智能化的宏观调控手段和资源信息更新 变动等快速反映能力。虽然集中式、分布式、层次式和基于多a g e n t 式等四种资源发现 和管理模型为我们提供了多种形态的发现和管理资源的策略，但是却没有为我们提供一 种对智能化宏观调控、快速响应资源变动等需求的整合。 现有任务调度算法无法适应网格平台的特点。尽管启发式智能算法为网格计算 任务调度的研究提供了新的方向，但其中也存在着诸多不足，如遗传算法收敛速度慢， 求解过程所耗时间太长，容易找到局部最优解；蚂蚁算法初期信息素匮乏，各蚂蚁分工 单一，求解速度慢，他们都不太适合快速多变的网格环境。 网格任务调度系统在安全机制方面存在漏洞。网格坏境的复杂性、动态性和开 放性使得分配到远程计算节点的任务可能会因为节点的物理故障或者受到攻击而无法 完成，而目前的调度策略都没有考虑到这个问题。因此会导致任务被分配到安全性较低 的计算节点上去执行，使计算任务特别是长计算任务很容易因为计算节点的失效而被中 断，降低了网格系统的效率和服务质量。也就是说，安全任务调度技术有待进一步研究。 缺少统一的底层支撑实现模型。目前国内外对网格计算底层支撑系统的研究还 处于初级阶段。人们虽然已经对网格计算底层支撑系统做出了一定的研究，但是由于系 统自身的庞大性和涉及技术的多样性，使人们还有很多探索和研究需要继续，如任务的 划分目前还是一个n p 问题，目前不少算法研究的资源和任务还是粗粒度的。 尚未找到对网格系统及应用状态进行精确预测的方法。这种预测是从其历史信 息中获得的，然而准确评估任务执行时间和通信延迟是困难的。例如在编译期估计通信 延迟是不可行的，因为运行期有网络争用延迟。 1 3 本文的主要工作及组织结构 1 3 1 本文的主要内容 由于时间和水平有限，对于以上存在的问题，本文只对网格计算的核心之一一网格 任务调度算法进行探索，以推进网格任务调度系统的研究。考虑到网格环境中任务调度 算法实施、设计的其他技术环节众多，特别是调度之前的计算资源发现管理、调度之后 调度成果的性能评价等因素。本文的研究工作主要从以下几个方面展开： 解析网格计算环境，归纳网格计算环境下任务调度的特点 由于网格计算环境的复杂性及网格计算的特点，网格环境下的任务调度与其它分布 式计算中的任务调度有很大的区别，因此需要研究网格计算环境的特点，在整体上把握 网格计算环境对任务调度的要求，为后文设计基于遗传算法和蚂蚁算法的网格任务调度 策略提供参考。 研究遗传算法和蚂蚁算法的机理，提出d c g 3 a 算法 深刻理解遗传算法和蚂蚁算法的优缺点，以及两者的内在联系，提出兼顾遗传算法 和蚂蚁算法优点的动态融合的遗传蚂蚁算法，并用马尔可夫理论分析该算法的收敛性， 为后面设计网格环境下的任务调度奠定基础。 根据网格任务调度特点，提出基于d c g 3 a 的网格任务调度策略 根据遗传算法和蚂蚁算法在网格任务调度这类组合问题寻优的搜索特点，利用两者 的优势，克服其劣势，设计出动态融合的调度算法。目标就是通过更合理的分配任务降 低网格系统总的执行时间和耗费，从而提高网格系统的总体性能。 研究网格系统的负载平衡问题，提出动态负载平衡因子 网格环境中，一个好的任务调度算法不但要考虑所有任务的m a k e s p a n ，使其尽量小， 同样要考虑整个系统机器间的负载平衡问题。因此本文通过计算任务迁移、任务交换后 的资源负载平衡量差值，提出动态负载平衡因子的概念，并将其引入到算法中，以提高 系统的负载平衡。 调度系统的仿真与分析 仔细研究g r i d s i m 这一网格仿真软件，提出基于g r i d s i m 工具的分模块任务调度模 拟开发方法，并按照这种方法构建本文所提出的任务调度算法模拟平台，并针对真实网 1 2 格环境的特点，给出自己设计的模拟程序，进而对本文所提出的任务调度算法进行仿真 与分析。 1 3 2 本文的组织结构 论文的各章节结构安排如下：第一章介绍网格当前发展情况和任务调度研究现状并 指出目前网格任务调度存在的问题及本文所做的工作；第二章对网格环境下任务调度的 模型、特点、目标及已有调度算法等方面进行分析，为以后章节的研究奠定理论基础； 第三章提出动态融合的遗传蚂蚁算法，并对该算法的收敛性进行证明；最后对该算法进 行改进，使其应用于网格环境中的任务调度；第四章提出基于g r i d s i m 工具的分模块的 任务调度模拟实现方法，并在所构建的模拟平台上对本文的算法进行对比实验；收集实 验所得数据，对结果进行分析。在全文的结尾部分总结本文所做工作并提出进一步的工 作。 第二章网格环境中的任务调度问题 网格是一个分布式的异构环境，主要由网格中间件系统与在i n t e m e t 上的各个分布式 共享资源组成。网格环境中的任务调度问题，就是根据一定的规则和策略，将构成网格 应用程序的一组任务映射到网格计算环境的多个结点上去执行，以取得较好的系统性 能，实现系统的负载平衡。下面分别对网格环境下任务调度的定义、特点、模型及已有 调度算法进行分析，为下一步研究奠定理论基础。 2 1 网格任务调度概述 任务调度主要是根据当前系统的负载情况，对系统内的任务进行动态调度，提高系 统的运行效率，任务调度的相关定义如下【s l 】 在有r n 个处理单元和任务图g = ( t ，e ) 之上的调度是一个函数厂，厂将每个任务 以某个特定的开始时间映射到某个处理单元。 形式上，一个调度可以描述为： f ：t 专 1 ，2 ，l ，聊) 【o ，0 0 】 如果存在v t ，f ( v ) = ( f ，f ) ，则表示任务y 被调度到处理单元p ，上，且从时间t 开 始执行。 函数厂可以表示成如下定义的g a n t t 图。 g a n t t 图用于直观地表示所有任务的开始时间和完成时间。在一个g a n t t 图中，有 一个分布式系统的处理单元表，对于表中每个处理单元都有一个任务分配表，即将分配 到这个处理单元的所有任务按执行时间排列成表，其中包括开始时间和结束时间，分别 为s t ( t , ，p ，) 和f t ( t f ，p j ) 表示。 实际上，函数厂的g a n t t 图是一个四元表：g a n t t ( t ，乃，s t ( t i ，乃) ，刀( ，所) ) 其中 t j ( i = 1 ，2 ，n ) 为分配到p j 上的任务； p j ( j = l ，2 ，刀) 为处理单元； s t ( t j ，马) t , 毛e m a x ) - - f t ( t , ，乃) ) 上的开始时间；