（计算机应用技术专业论文）基于qos的蚁群优化在网格资源调度中的研究.pdf

摘要 网格能够整合网络中的异构资源，在动态的、多管理机制的虚拟组织中协 调资源共享，解决大规模计算的资源共享问题。资源调度问题是网格系统最核 心的部分，良好的资源调度策略可以实现尽可能多的任务被分配合适的资源， 大大提高资源的利用率和和总耗费量，使网格达到最佳性能。由于网格环境中 的资源具有异构性、动态性和自治性等特点，使网格资源调度比传统并行分布 式计算的资源调度更为复杂和困难，它已经被证实为是一个n p 难问题。蚁群 优化( a c o ) 算法几经成功解决了很多不同类型的调度问题，很多是针对n p 难问题，它具有并行性和较强的健壮性以及易于和其他方法结合的特点，并可 以很快取得高质量的解。因此，蚁群算法非常适合于解决网格系统的资源调度 问题。服务质量q o s 也是衡量网格性能的一个重要指标，在网格资源调度过程 中应充分考虑综合考虑用户任务的q o s 需求。 本文首先阐述了网格资源调度算法设计的前期准备工作，调度算法设计的 过程以及最后的算法性能测试对比。具体工作如下： ( 1 ) 通过对目前网格q o s 研究的学习和总结，提出了一个网格q o s 调度 模型，本文重点考虑了3 种q o s 约束，并对各个约束作了详细的说明及设置， 引入了评价函数，将q o s 约束转换为效用值来衡量。 ( 2 ) 学习并介绍了几种主要的网格资源调度算法，蚁群优化自身的并行性 特征较适合用于网格计算的资源调度，由于所有影响资源状态的因素都能由信 息素描述，调度程序能够非常简单、快速地获得结果。结合q o s 调度模型和蚁 群优化算法，给出了一种基于q o s 的蚁群优化调度算法( q o s a c o ) ，该算法 主要考虑时间、安全、可靠性这三种约束。为了综合考虑时间和代价，本文引 入了性价比的概念，将其作为蚁群算法的启发因子，在提高网格系统性能的前 提下，也考虑了资源处理能力和资源代价，较好的解决资源调度问题。 ( 3 ) 本文在g r i d s i m 工具箱的帮助下，实现了基于性价比的q o s - a c o 调 度算法在网格资源调度中的仿真，并与q o s a c o 做了比较，实验证明本文的算 法较q o s - a c o 在总效用值和性价比都有一定程度的提高。由于外部因素的限 制，本文提出的算法还没有应用到实际网格环境下，下一步可以尝试将该算法 应用到真实的网格环境来检测其可行性及性能。 关键词：网格计算，资源调度，q o s ，蚁群优化，性价比 a b s t r a c t n o w a d a y sg r i d h a sb e c o m eah o tt o p i ci nt h e w o r l d i tc a ni n t e g r a t et h e h e t e r o g e n e o u sn e t w o r kr e s o u i c e s ，c o o r d i n a t er e s o u r c es h a r i n gi nv i r t u a lo r g a n i z a t i o n t h a ti sd y n a m i ca n do fm u l t i - m a n a g e m e n tm e c h a n i s ma n df i n a l l ys o l v et h er e s o u r c e s h a r i n gp r o b l e mo fl a r g e - s c a l ec o m p u t i n g r e s o u r c es c h e d u l i n gi s t h ec o r eo ft h e g a ds y s t e m ，f i n i s h e st h em a p p i n gf r o mt h et a s ks e tt ot h er e s o u r c es e t ag o o d r e s o u r c es c h e d u l i n gs t r a t e g ) ，i se s s e n t i a lt ot h eg a ds y s t e m i tc a na s s i g nt h et a s k st h e f i g h tr e s o u r c e sa sm u c h 硒p o s s i b l e ，g r e a t l yi m p r o v er e s o u r c eu t i l i z a t i o na n dt o t a l c o s tt om a k et h eg a da c h i e v et h eb e s tp e r f o r m a n c e s i n c et h er e s o u r c eh a st h e c h a r a c t e r i s t i c so fh e t e r o g e n e o u s ，d y n a m i c sa n da u t o n o m y , r e s o u r c es c h e d u l i n gi n g a di sm o r ec o m p l e xa n dd i f f i c u l tt h a nt h a ti np a r a l l e la n dd i s t r i b u t e dc o m p u t i n g s y s t e m ，i th a sb e e np r o v e dt ob en p - c o m p l e t e a n tc o l o n yo p t i m i z a t i o na l g o r i t h m h a sr e s o l v e dal o to fs c h e d u l i n gp r o b l e m s ，f o rm a n ya l en p - h a r dp r o b l e m ，i th a s p a r a l l e l i s m , s t r o n gr o b u s t n e s sa n di se a s yt oc o m b i n e 、) r i lo t h e rm e t h o d s ，s ow ec a n g e tg o o ds o l u t i o n sb yt h i sw a y t h e r e f o r e ，a n tc o l o n yo p t i m i z a t i o ni sv e r ys u i t a b l e f o rs o l v i n gg a dr e s o u r c es c h e d u l i n g ，n l cq u a l i t yo fs e r v i c e ( q o s ) i sa l s oa n i m p o r t a n tm e a s u r eo ft h eg a d ，t h u s ，w es h o u l dc o n s i d e rt h eu s e r s r e q u i r e m e n to f q o si ns c h e d u l i n g f i r s td e s c r i b e st h ep r e p a r a t i o nf o rt h ed e s i g no ft h eg a dr e s o u r o es c h e d u l i n g a l g o r i t h m ，d e s i g np r o c e s sa n dt e s t i n ga b o u tn e wr e s o u r c es c h e d u l i n gp o l i c y n l e m e t h o d sa r ed i s c u s s e da sb e l o w ： ( 1 ) t h r o u g ht h es t u d ya n ds u m m a r yo fr e c e n tr e s e a r c ho fg a dq o s ，p r o p o s ea g a dq o ss c h e d u l i n gm o d e l i tf o c u so nt h r e ek i n d so fq o sc o n s t r a i n t s ，g i v e sa d e t a i l e dd e s c r i p t i o no ft h ev a r i o u sc o n s t r a i n t sa n ds e t t i n g s ，a n di n t r o d u c e st h e e v a l u a t i o nf u n c t i o nt oc o n v e r tt h eq o sc o n s t r a i n si n t oau t i l i t yv a l u et om e a s u r e ( 2 ) i n t r o d u c e s s o m eg a dr e s o u r c e s c h e d u l i n ga l g o r i t h m s ，a n tc o l o n y o p t i m i z a t i o nh a st h ec h a r a c t e ro fp a r a l l e l i s mi ss u i t a b l ef o rg a dc o m p u t i n g ，嬲a l lt h e f a c t o r st h a ta f f e c tr e s o u r c es t a t ec a nb ed e s c r i b e db yt h ep h e r o m o n e ，t h es c h e d u l e r c a na c c e s st op r e d i c tt h eo u t c o m es i m p l ea n df a s t i nc o n s i d e r a t i o no fq o sa n da n t c o l o n yo p t i m i z a t i o n , w ep r o p o s eaq o s - b a s e da n tc o l o n yo p t i m i z a t i o ns c h e d u l i n g a l g o r i t h m sa l g o r i t h mm a i n l yt a k e st h et i m e ，s e c u r i t ya n dr e l i a b i l i t yi n t oa c c o u n t i no r d e rt oc o n s i d e rt i m ea n dc o s t , t h i sp a p e ri n t r o d u c e st h ec o n c e p to fc o s t - e f f e c t i v e ， a n dm a k ei tb et h eh e u r i s t i ci n f o r m a t i o no f a n tc o l o n yo p t i m i z a t i o n o nt h ep r e m i s e o fi m p r o v et h ep e r f o r m a n c eo ft h eg a ds y s t e m , a n da l s ot a k i n gr e s o u r c ec o m p u t i n g a b i l i t ya n dc o s t ，t os o l v et h er e s o u r c es c h e d u l i n gp r o b l e mb e t t e r ( 3 ) w i t ht h eh e l po ft h eg r i d s i mt o o l b o x , w ea c h i e v ec o s t - e f f e c t i v eb a s e do n 专 q o s - a c os c h e d u l i n ga l g o r i t h mf o rr e s o u r c 圮s c h e d u | i n gi ng r i ds i m u l a t i o n , a tl a s t c o m p a r e dw i t hq o s - a c oi n t o t a lc o s tv a l u ea n dc o s t - e f f e c t i v e ，t h ea l g o r i t h m p r o p o s ei nt h i sp a p e rh a sb e t t e rr e s u l t d u et ot h ee x t e mf a c t o r s ，a l g o r i t h mp r o p o s e d i np a p e rh a sn o tb e e na p p l i e dt ot h er e a lg r i de n v i r o n m e n t , t h en e x ts t e pi st oa p p l y t h ea l g o r i t h mt ot h er e a lg r i de n v i r o n m e n tt ot e s tt h ef e a s i b i l i t ya n dp e r f o r m a n c e k e yw o r d s ：g r i dc o m p u t i n g ，r e s o u r c es c h e d u l i n g ，q o s ，a n tc o l o n yo p t i m i z a t i o n , c o s te f f e c t i v e 1 1 i ， ，譬 i j 黉 目录 第一章前言1 1 1 论文的研究背景及其意义。1 1 2 国内外研究现状2 1 2 1 网格的研究现状2 1 2 2 资源调度研究4 1 2 3 资源调度算法研究4 1 3 本文的工作和组织结构。4 第二章网格技术概述。6 2 1 网格的定义6 2 2 网格的分类6 2 3 网格的特点7 2 4 网格体系结构8 2 5 网格模拟工具简介1 l 2 5 1 网格模拟器的介绍1 1 2 5 2g r i d s i m 网格模拟器仿真1 2 2 5 3v i s u a lm o d e l e r ：图形化用户界面建模工具1 4 2 6 j 、结1 5 第三章网格资源调度1 6 3 1 网格资源调度概述1 6 3 1 1 网格资源调度特点1 7 3 1 2 网格资源调度过程1 8 3 2 网格资源调度的目标1 9 3 3 网格资源调度算法1 9 3 4 小结2 1 第四章网格q o s 调度模型2 2 4 1 网格q o s 的三层模型2 3 4 2q o s 参数的量化2 5 4 2 1 可量化参数2 6 ：1 7 ：1 7 2 8 2 9 调度中的应用3 0 3 0 。3 0 3 1 5 1 3 蚁群优化算法的应用情况3 2 5 2 蚁群优化在网格资源调度中的应用3 3 5 3 基于性价比的q o s a c o 网格资源调度算法3 4 5 3 1 基于q o s 的蚁群优化调度算法3 4 5 3 2 基于性价比的q o s a c o 资源调度算法一3 4 5 4 小结3 6 第六章仿真实验与性能评价3 7 6 1 实验环境搭建3 7 6 2 仿真实验3 8 6 2 1q o s 参数设置。3 8 6 2 2 实验结果与分析3 9 6 3d 、结4 0 第七章总结与展望4 1 参考文献4 2 致谢4 6 作者简介4 7 i i j_1， ii一 第一章前言 第一章前言 1 1 论文的研究背景及其意义 随着计算机技术和互联网技术的普及和迅猛发展，计算能力的需求与日俱增，尤其是 一些超大规模的应用所需的计算能力已经不可能在单一的计算机或者单一的计算机机群系 统上获得，这就要求将地理位置上分散的、异构的各种高性能计算资源、存储资源、数据 资源和其它特殊资源通过高速网络连接起来，形成对用户透明的虚拟的高性能计算环境， 这就形成了网格，它能构造动态的虚拟组织，并在其内部实现跨自治域的资源共享、联合 计算和协同工作，为用户提供各种基于网络的综合性服务，有效的满足面向互联网的复杂 应用对大规模计算能力和海量数据处理的要求，从而大幅度提升性能，高效的完成各项计 算任务，为用户提供高品质的服务。 网格是并行和分布处理技术的一个发展方向，但与传统的分布式计算相比较，网格是 非常新的内容，它定位于高性能计算，着重于大规模的资源共享、创新应用，现已经成为 一个重要领域。网格中的资源在地理上是广域分布的，由不同的组织拥有和操作，在网格 环境中允许不同站点使用不同的局部资源管理系统，因此各个站点在使用策略和安全机制 上各不相同。但是很多应用需要同时使用多个站点上的资源，站点自治性可能会导致分配 资源时出现故障，这时就需要一种特殊机制来管理不同站点上的异构资源。如何对网格计 算环境中的资源有效地管理是实现高性能计算和完成重大应用问题的关键。 网格资源调度是网格核心服务之一，良好的资源调度能有效地协调和分配网格资源， 有效降低网格计算的总执行时间和总耗费量，从而使网格达到最大的性能，它被证实为n p 难问题f l j 。传统的调度问题主要是解决提高任务并行度，缩短任务运行时间，提高系统利 用率的问题。网格系统的调度关心的主要问题是调度任务集到可用的计算资源上，从而在 最大限度提高网格资源利用率的同时，满足用户对工作流的约束以及提高用户对服务质量 的满意程度。在网格资源调度算法的研究方面，国内外都做了很多工作，已经产生了一些 优秀的经典网格资源调度算法，如m i n 。m i n 2 - r j ，m a x - m i n l 2 3 。】，m a x i i l 一，s u f f e r - a g e i s 算法等。另外b u y y a 提出了一种基于经济模型的优化调度模型【 ，v m c e n z o 介绍了一种 基于遗传算法的资源调度算法【1 2 】，a b r a h a m 等人介绍了模拟退火等进化算法在网格资源调 度中的应用【1 3 j 。但是这些算法也存在着一些不足之处，那就是没有考虑到网格环境中用户 对服务质量q o s ( q u a l i t yo f s e r v i c e ) 的要求，而仅仅是对传统分布并行调度算法的一些改 进。随着网格计算技术的不断发展，在调度问题研究中，又出现了许多新的特性，q o s 指 标越来越受到重视。因此，提出一种在最大限度提高网格资源利用率的同时，满足用户对 任务的各种约束以及对服务质量要求的高效合理的资源调度算法，对促进网格计算的发展 和提高网格计算的实用性都有十分重要的意义。 由于网格系统具有异构性和动态性，搭建真实的网格环境是非常复杂和困难的，因此， 南京信息工程大学硕士学位论文 在网格资源调度研究的过程中，通常采用网格模拟器来完成相关的研究工作。使用网格模 拟工具不需要构建真实的网格环境，它能够为用户提供一个可重复、可控制的实验环境， 选取合适的模拟器，往往可以取得事半功倍的效果。在这个模拟的实验环境中，通过配置 不同的参数，可以模拟网格环境中的应用场景，进行一些复杂问题的研究并可以探寻解决 方法，为研究者的算法、方案等研究提供了分析验证、系统性能评估的平台。 1 2 国内外研究现状 网格是近几年信息技术领域的热点研究课题，网格技术的研究和开发热潮吸引了大量 的人员和机构参加，发展网格被认定为是下一代i n t e r n e t 的核心任务之一。网格计算技术的 重要战略意义及其广阔的应用前景使国内外很多的研究机构和企业投入了相当的人力、物 力、财力进行网格计算技术的研究。继学术界之后，各国政府和商业界也分别启动了一系 列的研究项引1 4 1 。 1 2 1 网格的研究现状 近年来，网格迅速成为全球计算机界关注的热门技术之一，得到许多国家学术界、企 业界甚至政府部门的高度重视和支持。 到目前为止，国际上很多的组织机构都对网格资源调度进行了深入的研究，并将其成 果应用于各自的网格系统之中。较为有影响的网格项目如下： ( 1 ) g l o b u s e l 5 】g l o b u s 是美国阿贡国家实验室的研发项目，该工具软件已经在世界范 围内得到一定程度的使用，它对全球网格研究发展起到巨大的推动作用。该项目要开发一 个面向科学计算的基本软件基础设施，利用该设施，把地理位置上分布的计算资源和信息 资源集成起来。该项目研究网格计算的关键理论，开发支持网格计算的工具软件和网格应 用程序，帮助规划和组建大型的网格实验平台，其研究目标有两个：一是涉及资源管理、 安全、信息服务及数据管理等网格计算的关键理论；二是相应软件的开发和标准的制定， 它的目标是能在各种平台上运行，开发适合大型系统运行的应用程序。g l o b u s 着重处理了 资源发现和标识问题，对资源调度的支持很弱，提供资源调度模块，但不提供资源调度策 略。资源调度策略来自于服务层，g l o b u s 中也没有提供再调度的功能。 ( 2 ) l e g i o n i l 6 ll e g i o n 是始于1 9 9 3 年弗吉尼亚大学的一个基于对象的元系统软件项 目。它的目标是为用户提供单一、一致的虚拟机模型。其资源管理体系结构也是采用层次 模型：在任务调度方面采用分布式调度器、可预测价格模型、在线重调度方法、固定的面 向应用的调度策略等。 ( 3 ) n i m r o d g 1 7 n i m r o d - g 是一个网格资源代理，允许在计算网格中管理和操纵任 务。它使用了一个经济模型来完成资源管理和调度。n i m r o d - g 提供了网格节点的资源发现、 资源交易、调度和资源分段运输、结果收集以及最终的结果演示给用户。n i m r o d - g 在资源 管理上遵循的是分级和计算的市场模型。它使用网格中间件系统如g l o b u s 等提供的服务来 2 第一章前言 发现资源，并使用一个网络目录或者基于数据组织的对象模型。他通过g r a c e 架构提供 的计算经济服务支持资源预定和q o s 。用户可以指定q o s 要求，如完成期限( d e a d l i n e ) ， 预算( b u d g e t ) 和首选的最优策略等。 目前，n i m r o d 主要的算法为d e a d l i n ea n db u d g e tc o n s 砌n e d ( d b c ) s c h e d u l i n ga j g o f i t h m ， 其中能够根据任务完成时间以及花费预算进行资源调度，根据问题的侧重点不同，还有 d b ct i m eo p f m a 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 cc o s t - t i m eo p t i m i z a t i o n 三种分支。 ( 4 ) c o n d o r t l s lc o n d o r 是美国威斯康星麦迪逊大学的研究项目，它是一个专用的计 算密集型负载管理系统，可以提供队列机制、调度策略、优先级方案、资源监控、资源管 理等功能，可通过提供一个高吞吐量计算环境实现。用户向c o n d o r 提交任务，c o n d o r 可 以根据一定的策略，选择合适的时间在合适的资源上运行该任务。用户提交的任务可以是 串行的也可以是并行的。c o n d o r 被认为是具有平面组织的计算网格，它使用了具有混合命 名空间的可扩展体系，其缺点是不支持q o s 。 ( 5 ) a p p l e s t l 9 】a p p l e s ( 应用层调度) 是加利福尼亚大学计算机科学与工程系的网格 计算实验室进行的一个项目，研究对象是面向应用层的调度，着重研究和开发在计算网格 中调度单个应用的智能主体。它采用静态、动态应用和系统信息选择功能进行应用计算的 构造并预测其性能，与相关的资源管理系统交互完成应用任务。a p p l e s 智能主体嵌入到应 用中以在网格计算环境中进行资源调度，因而对应用而言将作业映射到资源的调度是集中 式的，但实际运行应用的各个任务则由本地的资源调度器负责。 ( 6 ) u n i c o r e 德国联邦教育和研究部的u n i c o r e 项目，主要合作者为德国的五 家研究机构。它的目的是提供一套软件，允许用户给远程高性能计算机提交自己的作业， 而不需要知道远程机器的操作系统、数据存储格式、管理策略和过程。它最大可能地使用 已有的万维网技术。用户接口语言用j a v a ，工具用浏览器，授权用户可以通过接口访问任 何地方的u n i c o r e 资源。它为终端用户和计算中心都提供了强大的运行网格的功能，具 体有：简单方便地作业创建和控制：支持多系统和多点作业；动态流控制；通过x 5 0 9 证 书集成安全；访问远程文件存储和档案；支持科研和商业应用。 我国在网格计算方面也做了大量基础性和前瞻性的研究，网格研究已经列入“8 6 3 计 划”。在北京举行的“网格战略讨论会”上，网格研究领域和应用领域的专家就网格研究方 面的问题展开了全面的讨论。大家一致认为，网格的研究、开发和应用将是未来的一个重 要方向。 中国科学院计算技术研究所从1 9 9 6 年开始了网格技术的研发工作。2 0 0 0 年开发了国 内8 个曙光计算中心的网格。2 0 0 1 年的织女星网格计划。2 0 0 2 年底，上海市宣布将投入两 个多亿，建设e i n s i t i t u t e ，其中网格是重点，把上海交大、复旦、华东理工等多所重点高校 用网格整合起来，共享资源，协同教学科研。教育部依托教育与科研网g e r n e t 和高校的 大量计算资源和信息资源，推出c h i n a g r i d 计划。l a g i i d 是中国清华大学计算机科学技术 系等单位和机构建成的e - l e a r n i n gg r i d 网格示范工程。在资源调度方面，它针对资源的分 布性和存取的普遍性，研究跨越多个自治域的资源管理体制，并在统一的调度框架下协调 写作群体行为，实现资源的动态分配，从而达到系统资源的整体优化。 3 南京信息工程大学硕士学位论文 1 2 2 资源调度研究 近年来，随着基础网格设施的不断完善和发展，资源调度算法研究得到广泛的关注。 目前在对网格资源调度的研究领域，大致集中在三个领域：采用经济市场模型资源管理和 调度的研究，基于信誉度的调度算法研究，基于q o s 的资源调度算法研究。其中目前大多 数关于q o s 的资源调度算法的研究是停留在单一q o s 约束基础之上的，所以多重q o s 约 束的网格资源调度算法的研究还具有进一步发掘和探索的空间。本文便是以多q o s 约束为 立足点进行的资源调度算法的研究。 参看其他的文献和研究成果，我们不难发现网格中的调度问题为n p 难问题，即我们 难以在有限代价之内获取问题的最优解。因此，以求近似最优解为目的的启发性算受到了 极大的重视。近年来，人们提出了很多启发性智能算法，例如神经网络、模拟退火、禁忌 搜索、遗传算法、蚁群算法等等，成为了解决n p 问题的最佳工具。 1 2 3 资源调度算法研究 在对传统并行分布式计算的广泛深入的研究过程中，已经产生了很多经典的结论。然 而随着网格计算的出现，产生了不同于分布式计算的新需求，这就迫切的要求有新的能够 满足网格计算需求的调度算法。传统的并行计算调度是将一个应用的子任务调度给多台并 行机，以减少执行时间；然而在网格环境中，调度是将来自不同用户的任务集合调度给一 个可用资源集，最大化资源利用率，并达到某种服务质罱需求。因此，网格资源调度要解 决两个问题，一是要解决应用的需求和可用的计算资源之间的匹配，二是要考虑服务质量 q o s 问题。 在资源调度算法的研究进展中，已经产生了一些优秀的经典网格资源调度算法，如 m i n - m i n 算法、m a x m i n 算法、s u f f e r a g e 算法等，它们都是基于调度目标最小化的思想提 出的，这三种算法成为了后来研究者研究调度算法的借鉴对象。但这些算法也存在着不足 之处，那就是没有考虑到网格环境中对服务质量q o s ( q u a l i t yo f s e r v i c e ) 的要求，而仅仅 是在传统分布并行调度算法的一些改进。基于q o s 的m i n - m i n 算法，虽然也考虑了q o s 要求，但它只是对网格资源中网络带宽的讨论，显然不能适用于解决复杂的实际网格应用 问题。本文将在第三章详细介绍网格资源调度的几种算法。 1 3 本文的工作和组织结构 本文首先分析了网格资源调度的主要内容，包括特点、过程、目标等，加之服务质量 q o s 指标在网格服务中受到越来越多的重视，如何保证网格资源调度过程中的服务质量 q o s 是网格发展道路上亟待解决的问题。在此基础上，本文将重点研究以下问题： ( 1 ) 通过对目前网格q o s 研究的学习和总结，提出了一个网格q o s 调度模型，本文 4 第一章前言 重点考虑了3 种q o s 约束，并对各个约束作了详细的说明及设置，引入了评价函数，将 q o s 约束转换为效用值来衡量。 ( 2 ) 通过对目前几种网格资源调度算法的研究和比较，发现蚁群算法的分布性和较好 的求解能力等特点，使得它非常适合于解决网格中的资源调度。结合q o s 调度模型，并将 资源处理速度和花费作为影响蚂蚁路径转移的启发因子，本文提出了一种基于性价比的 q o s 蚁群优化调度算法。 ( 3 ) 使用g d d s h ni 具进行了仿真实验。实验对基本的q o s 蚁群优化调度算法 ( q o s - a c o ) 和基于性价比的q o s 蚁群优化调度算法( 基于性价比的q o s - a c o ) 分别在 总效用和性价比两方面做了对比。实验结果表明，基于性价比的q o s - a c o 算法在系统总 效用值和性价比都有所提高。 文章的组织结构为： 第一章绪论，介绍了论文的研究背景、当前国内外的研究现状以及网格资源调度研究 的重要意义，然后介绍了国内外研究现状，包括科研项目、资源调度的研究以及算法的研 究。 第二章网格技术概述，阐述了网格计算的基础知识，包括网格的定义、分类、特点以 及目前主流的几种网格体系结构，另外介绍了网格模拟工具并重点介绍了本文中使用的模 拟工具g d d s h n 。 第三章网格资源调度，介绍了资源调度的基本内容和相关研究，资源调度是本文研究 的重点。资源是网格中的主要对象，网格的目的就是要调度好网格中的各种资源，为需要 资源的用户提供透明一致的访问接口。本章从网格资源调度的定义、特点、过程、目标， 详细描述了资源调度的相关概念，然后介绍了几种资源调度领域研究的算法。 第四章网格q o s 调度模型，首先介绍了q o s 的三层模型，并详细介绍了资源汇聚层七 种q o s 参数。接着针对本文研究的三类q o s 参数，时间性q o s 、可靠性q o s 、安全性q o s 给出了各自的评价函数，并引入了性价比这一重要概念，为后面提出的基于q o s 的蚁群优 化调度算法做了铺垫。 第五章基于q o s 的蚁群优化算法，首先介绍了蚁群优化算法的基本原理、研究进展以 及目前的应用状况，并详细说明了蚁群优化算法适合解决网格任务调度问题的原因。然后 将蚁群优化算法与上一章介绍的网格q o s 模型相结合，并加入了性价比这一因素，提出了 基于性价比的q o s - a c o 网格资源调度算法，并详细描述了算法的思想、流程等。 第六章：对本文提出的调度算法，使用g d d s h n 工具进行仿真，详细分析了实验结果 并和传统的q o s - a c o 算法进行了比较。 5 南京信息工程大学硕士学位论文 2 1 网格的定义 第二章网格技术概述 网格又称为网格计算，它起源于元计算，其核心思想是把整个因特网上的各种资源整 合成一台巨大的虚拟超级计算机，实现各种资源的全面共享，从而获得超级计算能力、数 据处理能力和信息处理能力。1 9 9 8 年，i a nf o s t e r 和c a r lk e s s e l m a n 在书t h eg r i d ：b l u e p r i n t f o ra n e wc o m p u t i n gi n f r a s t r u c t u r e 中首次给出了网格的定义：“计算网格是一个提供可靠的、 一致的、无所不在的便宜的硬件和软件基础结构，用来进行高端计算”【2 0 】。这个概念来自 于早期的网格，它主要用于互联美国各个实验室和大学之间的高性能设备。2 0 0 1 年，f o s t e r 、 k e s s e l m a n 和t u e c k e 又重新将网格定义为：“网格计算是构筑在互联网上的一组新兴技术， 它将高速互联网，高性能计算机、大型数据库、传感器、远程设备等融为一体，为科技人 员和普通老百姓提供更多的资源、功能和交互性。网格的功能性更为强大，它能让人们透 明的使用计算、存储、软硬件、数据等资源”。本文认为网格的成功之处就在于它打破了传 统计算资源的共享和协作方面的限制，如地理位置的限制、计算能力大小的限制以及共享 机制的限制等，允许网格用户直接使用资源且能够以多种方式更广泛地交流信息，来充分 的利用网格提供的各种功能。 网格研究起源于美国政府资助的高性能计算科研项目，为了支持大规模的科学协同工 作而出现的。这类研究的目标是将跨地域的多台高性能计算机、大型数据库、贵重科研设 备、通信设备等整合成一个巨大的超级计算机系统，支持科学计算和科学研究。目前一般 用于海量科学数据库的协同可视化，计算密集型数据分析的分布式计算，远程计算机、数 据和科学仪器的协同工作。不仅仅因为网格技术能够提高系统性能，而且因为网格技术是 构造可靠的、可扩展的、安全的分布式计算系统的解决方案。 2 2 网格的分类 网格由于其分布范围广、功能强、用户群数量巨大，功能也十分丰富，从不同的角度 出发，就会对网格有不同的分类方法。根据网格多共享的资源和所支持的应用，可以分为 四类1 2 l 】： ( 1 ) 计算网格计算网格能够利用广域网上分散的动态共享计算资源，用以进行科学 工程计算以解决各种研究问题。计算网格又可以分为分布式高性能计算、高吞吐量计算。 分布式高性能计算利用广域网上的计算资源使单个应用程序的执行时间最短。而高吞吐量 计算可以使整个网格系统的利用率达到最大。 ( 2 ) 抽取网格抽取网格从空闲的服务器和台式机上抽取c p u 时间片，以解决资源密 6 第二章网格技术概述 集型的任务计算。 ( 3 ) 数据网格：数据网格能够动态地共享分散在广域网上的数据资源，以解决海量存 储问题，如数字图书馆、数据仓库等。 ( 4 ) 服务网格：服务网格提供了任何单个机器都不能提供的服务，例如点播服务、协 作服务、多媒体网格等。协作服务提供了虚拟工作空间，使用户和程序实时交互。 2 3 网格的特点 网格具有分布性、动态性、异构性以及自治性四大特性阎，它能够吸纳包括计算机、 网络、数据、资料、仪器设备等在内的各种计算资源，并将它们转化为一种随处可得的、 可靠的、标准的同时还是经济的计算能力，不管用户身在何处，网格资源都能像电力、水 资源那样容易获得，并能按需提供人们所要的任何信息。作为一种新出现的重要的基础设 施，它有一些区别于其他计算系统的特性： ( 1 ) 分布与共享 分布性是网格的一个最主要的特点，如何解决分布资源的共享问题是网格的核心内容。 分布性首先是指网格系统中的资源是分布的，它们一般类型复杂，规模较大，跨越的地理 范围较广。它们具有一个共同特征就是充分共享性，任何网格使用者可以使用网格上的资 源。分布是网格硬件在物理上的特征，而共享是在网格软件下实现的逻辑上的特征。 ( 2 ) 相似性 网格的局部和整体之间存在着一定的相似性，即局部往往在许多地方具有全局的某些 特征。例如可以认为国家级网格是在省级网格基础上建立的，国家级和省级网格都会有各 自的计算中心，只不过在计算能力上有差异而己；它们也有各自的管理结点，只不过国家 级的管理结点管理功能需要更多、更强大。 ( 3 ) 动态性和多样性 网格中的资源不是固定的，随时会有新资源的加入和原有的资源的离开，网格资源的 可获得性、负载都是不确定的，随时间变化而变化。网格资源种类繁多，功能各异，访问 接口不尽相同，本地的管理系统存在差异性，共享规则各异。同样的计算资源可能所处的 操作系统不一样，或者版本不一样等等。因此，解决这些不同结构、不同资源之间的通信 和互操作问题是网格资源调度的前提。 ( 4 ) 自治性与管理的多重性 网格上的资源首先是属于某个组织或者个人，网格系统应该允许资源拥有者对他的资 源有自主的管理能力，这就是网格的自治性。同时网格中的资源也必须接受网格的统一管 理和合理调度，保证任务有序高效的进行。因此网格的管理具有多重性，一方面允许资源 拥有者具有自主管理的权限，另一方面又要求网格中的资源接受网格的统一管理。 7 南京信息工程大学硕士学位论文 2 4 网格体系结构 网格系统十分庞大，不仅建设者数量巨大，网格中的资源和用户数量也很庞大。因此， 必须要细心规划，建立合理的网格体系结构田】，并以此为标准进行建设，才能建成满足要 求的网格。网格体系结构就是关于如何构建网格的技术，它包括两个方面的内涵：一是对 网格系统基本组成部分和各部分的功能、目的和特点进行描述；二是对网格各组成部分之 间的关系以及他们的集成方式进行描述。可以说，网格体系结构是网格的骨架和灵魂，是 网格技术中最核心的部分。只有建立科学合理的网格体系结构，才能够建造满足需要的网 格，才能使网格有效地发挥自己的作用。 到目前为止，影响比较大的网格体系结构有三个，一个是l a nf o s t e r 等提出的五层沙漏 结构；第二个就是目前最重要的广泛认可的标准o g s a ( o p e ng r i ds e r v i c e a r c h i 咖) 第三个是由g l o b u s 联盟、m m 和肿于2 0 0 4 年初共同提出的w s r f t 2 0 1 ( w e bs e r v i c er e s o u r c e f r a m e w o r k ，w 曲服务资源框架) 。 ( 1 ) 五层沙漏结构 2 4 1 五层沙漏结构是一种影响非常广泛的结构，它的主要特点是结构简单、层次分明。该 结构最重要的思想是以“协议”为中心，突出协议在网格资源共享与互操作中的地位。它 定义了每一层的运行机制、接口、模式和协议等，支持资源提供者和用户之间通过协商建 立资源共享