（计算机软件与理论专业论文）基于计算网格的任务调度算法研究.pdf

摘要高速网络的发展使得将分散的、异构的计算资源有机地整合到一起形成计算网格成为可能。计算网格为解决科学和工程领域一些大规模计算问题提供了理想的平台。由于网格所具有的广域性、动态性、异构性的特点，如何对任务进行调度以满足用户的需求是一个极具挑战性的问题。a p p l e sp a r a m e t e rs w e e pt e m p l a t e 是套用于布置和执行大规模p a r a m e t e rs w e e pa p p l i c a t i o n 的用户级中间件，它的设计目的就是要使应用的布置、调度和执行变得简单易行而且有效。它使用一种自适应的任务调度算法，并且在这个算法中针对p a r a m e t e rs w e e pa p p l i c a t i o n 中任务共享输入文件的特点，在s u f f e r a g eh e u r s i t i c 的基础上提出了x s u f f e r a g eh e u r i s t i c 来进行任务调度。为了减少调度开销，算法在进行任务调度步骤之前要先进行任务子集的选择，这样就使得原任务集中的任务在调度过程中产生了先后次序。但是，在存在大量输入文件共享以及使用x s u f f e r a g e 进行调度的前提条件下，不同的任务子集调度次序会对调度结果产生不同的影响。算法中采用随机选取的方法来选择任务子集，这不能保证对后面的调度产生有利的影响。本文针对算法的这种不足，提出了一种任务子集选择方法，通过s i m g r i d 平台进行模拟实验，实验结果说明加入了任务子集选择方法的算法比原算法在性能上有进一步提高。随着网格的飞速发展，服务质量( q o s ) 成为网格任务调度过程中必须要考虑的一个重要因素。有些任务需要在能够提供一定q o s 的计算资源上运行，而有些任务对计算资源没有q o s 方面的要求。在这种情况下，一些传统的任务调度算法不能很好满足用户的需求。因此，有人在传统的m i n m i nh e u r i s t i c 的基础上提出了q o sg u i d e dm i n - m i nh e u r i s t i c ，但是，以上算法都是以“批模式”运行的，缺乏灵活性，易造成资源的浪费，本文在原算法的基础上进行了一些扩展，引进任务申请机制，提出了e x t e n d e dq o sg u i d e dm i n m i nh e u r i s t i c ，并通过模拟实验表明，扩展后的算法比原算法性能更高、稳定性更好；最后，本文对容错技术在网格任务调度领域的应用进行了一些探讨，并在现有的一种基于备份技术的网格容错调度策略的基础上引入可用性的概念，提出一种新的容错调度策略。关键词：计算网格：任务调度：服务质量；p a r a m e t e rs w e e pt e m p l a t e ；容错a b s t r a c ti nr e c e n ty e a r s ，t h eh i g h s p e e dn e t w o r k sd e v e l o pv e r yf a s t ，w h i c hm a k e si tp o s s i b l et oi n t e g r a t et h ed i s t r i b u t e da n dh e t e r o g e n e o u sc o m p u t i n gr e s o u r c e si n t oc o m p u t a t i o n a lg r i d i tp r o v i d e sa ni d e a lp l a t f o r mt os o l v el a r g e 。s c a l ec o m p u t i n gp r o b l e m si ns c i e n t i f i ca n de n g i n e e r i n ga r e a b e c a u s et h er e s o u r c e si ng r i da r ed i s t r i b u t e d ，h e t e r o g e n e o u sa n dd y n a m i c ，h o wt os c h e d u l et a s k si ng r i dt om e e tu s e r s r e q u i r e m e n t si sac h a l l e n g i n gp r o b l e m i na p p l e sp a r a m e t e rs w e e pt e m p l a t e ，a na d a p t i v es c h e d u l i n ga l g o r i t h mi su s e df o rt a s ks c h e d u l i n g i nt h ea l g o r i t h m ，x s u f f e r a g eh e u r i s t i cb a s e do us u f f e r a g eh e u r i s t i ci sp r o p o s e df o rt h ef a c tt h a tt a s k si np s aa l w a y ss h a r ei n p u tf i l e s i no r d e rt or e d u c es c h e d u l i n go v e r h e a d ，t h ea l g o r i t h mw i l lp i c kas u b s e to ft a s k sf r o mt h ew h o l et a s ks e tb e f o r es c h e d u l i n g ，w h i c hm a k e ss o m et a s k ss c h e d u l e de a r l ya n dt h eo t h e r ss c h e d u l e dl a t e i ft h e r ea r em a n yi n p u tf i l e ss h a r e da n dt h ea l g o r i t h mu s e sx s u f f e r a g ef o rs c h e d u l i n g ，d i f f e r e n ts e q u e n c ef o rt a s k st ob es c h e d u l e dc a np r o d u c ed i f f e r e n tr e s u l t s i no r d e rt oi m p r o v et h ep e r f o r m a n c eo fa l g o r i t h m ，am e t h o df o rt a s ks u b s e ts e l e c t i o ni sp r o p o s e d as i m u l a t i o ne x p e r i m e n tb a s e do ns i m g r i dp l a t f o r mi sm a d ea n dt h ec o m p a r i s o nb e t w e e nt h eo r i g i n a la l g o r i t h ma n dt h ea l g o r i t h mw i t ht a s ks e l e c t i o ns h o w st h a tt h el a t t e ri sb e t t e r w i t ht h ep r o l i f e r a t i o no ft h eg r i d ，q u a l i t yo fs e r v i c e ( o o s ) h a sb e c o m ea ni m p o r t a n tf a c t o rt h a tn e e d e dt ob cc o n s i d e r e di nt h ep r o c e d u r eo fs c h e d u l i n g i nt h i ss i t u a t i o n ，q o sg u i d e dm i n m i nh e u r i s t i cb a s e do nm i n - m i nh e u r i s t i ci sp r o p o s e d b u tt h eh e u r i s t i ci sr u n n i n go nb a t c hm o d e ，w h i c hm a k e si tp o s s i b l et oc a u s ew a s t eo fc o m p u t i n gr e s o u r c e s i no r d e rt oo v e r c o m et h i ss h o r t c o m i n g ，e x t e n d e dq o sg u i d e dm i n m i nh e u r i s t i ci sp r o p o s e db yi m p o r t “b i d d i n g - f o r t a s k ”p o l i c y t h er e s u l to fs i m u l a t i o ne x p e r i m e n ts h o w st h a tt h ee x t e n d e dh e u r i s t i ci sb e t t e r a tt h ee n d ，w ed i s c u s st h ea p p l i c a t i o no ff a u l tt o l e r a n c ei ng r i dt a s ks c h e d u l i n g o nt h eb a s i so fae x i s t i n gg r i df a u l t - t o l e r a n ts c h e d u l i n gp o l i c y ，w ei m p o r tt h ec o n c e p to f “a v a i l a b i l i t y ”a n dp r o p o s ean e wp o l i c y k e yw o r d s ：c o m p u t a t i o n a lg r i d ；t a s ks c h e d u l i n g ；o o s ；p a r a m e t e rs w e e pt e m p l a t ef a u l tt o l e r a n c e插图索引2 1 计算网格的五层沙漏形体系结构模型82 2n i m r o d g 任务调度框架123 1a p p l e s 应用框架l33 2a p p l e sp a r a m e t e rs w e e pt e m p l a t e 框架153 3p s a 应用模型1 63 4 计算网格模型1 73 5g a n t t 表实例1 83 6s c h e d u l e ( ) 的具体步骤1 83 7 应用不同h e u r i s i c 时的运行结果2 13 8s c h e d u l e ( ) 改进前后性能比较2 34 1m i n m i n 算法的调度结果2 84 2q o sg u i d e dm i n m i n 算法的调度结果3 04 3 三种算法在三种情况下的运行结果3 34 4 不同调度周期下三种算法的运行结果比较3 45 1 网格模型3 8图图图图图图图图图图图匿图图图表4 1表4 2表4 3表4 4表4 5表5 1附表索引任务在相应主机上的预计运行时间2 8两种算法在三种情况下的运行结果3 1两种算法在三种调度周期下的运行结果3 1三种算法在三种情况下的运行结果3 3不同调度周期下三种算法的运行结果比较3 3传统分布式计算系统和网格系统上的容错机制3 7湖南大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：关媛日期：加o ；年年月z 妒日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1 、保密口，在年解密后适用本授权书。2 、不保密团。( 请在以上相应方框内打“”)作者签名导师签名关饭飞坳日期：加p s 年4 月上g 日醐：扣产f 月暗鼍1 1 研究背景第1 章绪论当前，i n t e r n e t 飞速发展，网络速度成倍增长，主干网的带宽从原来的5 6 k b s发展到十兆、百兆甚至千兆：另一方面，各种计算资源的能力越来越强大。这一切使得一种新的网络计算模式一一网格计算( g r i dc o m p u t i n g ) 的出现成为可能。网格计算是指在动态的、异构的、广域的虚拟组织( v i r t u a lo r g a n i z a t i o i l ，v o )中进行的协同资源共享和问题求解f l l 。随着人们求解问题领域的不断拓展，所遇到的问题也越来越复杂，而且规模越来越大，解决这些问题所需要的计算能力也在大幅度提高。比如在天文学研究中，天文望远镜每年所产生的数据不少于1 0p e t a b y t e s ，处理如此大的数据量，即使是计算能力强大的超级计算机也不能胜任，因此，必须使用广大的分布资源，将它们集中起来协同解决问题。另一方面，随着信息技术的快速发展，各个地理分部的组织部署了相当多的信息处理设备，而其中相当多的资源在大部分时间内没有被充分利用；其次，在信息技术飞速发展的过程中，各个地理分部的组织积累了大量的信息资源，但是它们却处于分立的状态，构成了一个个的信息孤岛。基于i n t c r n c t 的网格计算技术以解决这些问题为目标，成为当前的一个研究热点。1 1 1 网格简介在开始阶段，网格计算更多地被称为“元计算”( m e t a c o m p u t i n g ) 1 2 1 ，过去对元计算的研究可以认为是网格计算的初级阶段。直到2 0 世纪9 0 年代中期，网格( g r i d ) 一词才出现，在1 9 9 5 年的i w a y 项目中明确提出了网格计算的概念1 3 j 。网格就是把整个国际互联网集成为一台巨大的超级计算机，实现全球范围的计算资源、存储资源、数据资源、信息资源、知识资源、专家资源、设备资源的全面共享。当然，网格并不一定非要这么大，我们也可以构造地区性的网格、企事业内部网格、局域网网格、甚至家庭网格和个人网格。网格的根本特征是资源共享，消除资源孤岛，它的规模并不是主要因素【4 j 。网格是一个集成的计算与资源环境，它能够吸纳各种包括计算机、网络、数据资料、仪器设备等在内的计算资源，并将它们转化成为一种随处可得的、可靠的、标准的同时还是经济的计算能力，它具有一些区别于其他计算系统的特性，下面将从几个方面来论述。1 ) 分布与共享共存分布性是网格的一个最主要的特点，首先网格涉及的资源是分布的，它们一般类型复杂，规模较大。跨越的地理范围较广：由于这个原因，基于网格的计算也是分布式的，这就产生了资源与任务的分配和调度、安全传输与通信等一系列需要解决的问题。虽然网格资源是分布的，但它们是充分共享的，可以提供给网格上的任何使用者。共享是网格的目的，如何解决分布资源的共享问题，是网格的核心内容。分布是网格硬件在物理上的特征，而共享是在网格软件支持下实现的逻辑上的特征，这两者在网格系统中同时存在。2 ) 相似性网格的局部和整体之间存在着一定的自相似性，局部往往在许多地方具有全局的某些特征，而全局的特征在局部也有一定的体现。3 ) 动态性和多样性对于瞬格来说，决不能假设它是一成不变的，原来拥有的资源或者功能，在下一时刻可能会出现故障或者不可用；而原来没有的资源，可能随着时间的推移会不断地加入进来。这就对网格系统的容错性以及可扩展性提出了更高的要求。网格资源是异构和多样的。在网格系统中可以有不同体系结构的计算机系统和类别不同的资源，因此网格系统必须能够解决这些不同结构、不同类别资源之间的通信和互操作问题。4 ) 自治性与管理的多重性网格上的资源首先是属于某一个组织或者个人，因此网格资源的拥有者对该资源有最高级别的管理权限，网格在统一管理这些资源的同时，也应该允许资源拥有者对他的资源有自主的管理能力。因此网格的管理具有多重性，一方面允许网格资源的拥有者具有自主性的管理，另一方面又要求网格资源必须接受网格的统一管理。以上就是网格的一些特性，也提出了网格需要解决的问题。为解决不同领域中的不同问题，人们以网络互连为基础构造了不同的网格，如信息网格、天文网格、科学计算网格、生物信息网格等。1 1 2 国内外的网格计算项目简介网格计算技术的巨大应用前景促使国内外很多的研究机构和企业投入了相当大的人力、物力和财力进行网格计算技术的研究。当前，网格计算研究已经获得了很大的发展，取得了很多有重要价值的成果，国内外有很多网格计算项目，其中许多项目都是由政府资助的国家级项目。t e r a g r i 驴1 。该项目由美国国家科学基金于2 0 0 1 年8 月发起，当时用5 3 0 0 万美元资助四个超级计算中心，构建计算网格，目标是为开放的科学研究建立和部署一个世界最大的、最全面的分布式计算基础设施。当前，该项目聚集了分布在9 个地点的计算和存储资源，提供了2 0 t e r a f l o p s 的聚合计算能力，也开发了大量的网格计算工具。2 0 0 3 年9 月该项目宣称将增加更多的科学设备、大规模数据集、计算资源和存储资源。该项目使用了g l o b u st o o l k i t 、c o n d e r g 6 j 、m p i c h g 2 t n等面向计算网格环境的软件，使得登陆到该计算网格环境的用户可以透明的使用其中的计算、存储资源，进行大规模科学计算和数据处理。i p g ( i n f o r m a t i o np o w e rg r i d ) 1 8 】。美国n a s a 构建了该网格计算实验床，它可以将n a s a 分布在各地的计算和存储资源通过网络( 包括无线网络) 连接起来，解决n a s a 目前无法解决的科学与工程计算和数据管理等问题。p a c i ( p a r t n e r s h i pf o ra 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 c s a l 9 j 和n p a c i 1 0 ) 。目标是通过将学术界、政府部门和工业界的计算基础设旌联合起来，建立一个网格计算基础设施的伙伴联盟，促进科学发现、知识创新和工程开发。a c c e s sg r i d t l , 。该项目由美国a r g o n n e 国家实验室发起，吸引了多所大学和研究机构加入，汇集的资源包括计算资源、多媒体显示、表现和交互式环境，提供对网格中间件和可视化环境的访问接口，特别适用于组对组的通信交互。e u r o g r i d a 2 ；。该项目是由欧盟资助的研究和技术开发计划，目标是使用网格技术为科学和工业群体提供一个信息处理环境。d a t a g r i d l l 3 。由欧洲原子能研究组织领导，欧盟资助，目标是建立一个数据密集的计算网格来管理和分析科学实验中产生的大量实验数据【1 4 1 ，对数据管理和处理提出了极大的挑战，该网格项目就是针对这一需求而建立的。还有许多国家和地区也设立了网格计算研究项目，如英国的e s c i e n c e 计划1 1 5 1 、日本的n i n f l l 6 ) 、n a r e g i t l n 、荷兰的p o l d e r m e t a c o m p u t e r i l b l 、法国的a c i g r i d i gj等等。网格被认为是2 1 实际的信息基础设施，被越来越多的国家和组织所重视。在国内，网格计算也快速发展，主要的项目有：中国国家网格项目( c n g r i d ) 。“十五”期间，国家“8 6 3 ”高技术研究发展计划资助了该项目。旨在建立面向企业、高校、科研机构、政府部门的国家高性能计算环境。主要任务包括：1 ) 建设中国国家网格实验床：2 ) 建立具有4 万亿次以上计算能力的网格主节点；3 ) 开发支持网格应用以及维护网格系统运行的网格软件；4 ) 开发具有代表性的网格生产性应用。教育部的中国教育科研网格项目( c h i n a g r i d ) 。该项目是“十五”国家“2 1 1工程”公共服务体系“c e r n e t ( 中国教育科研网) 高速地区网和重点学科信息服务体系建设”项目中的重要建设内容，目标是在2 0 0 5 年建立聚合计算能力超过1 5 万亿次量级的教育科研网络，形成世界上最大的超级网格之一，并争取在网格计算的基础研究和应用研究方面走在世界前列。另外，国内还有一些行业应用网格和地区性网格研发项目，如中国气象网格、空间信息网格、上海城市网格等。国内多个大学、科研单位也已经开始了网格计算技术的研究，中国科学院计算所研究开发了v e g a 网格【2 0 i ，清华大学、国防科技大学、华中科技大学等单位在网格技术研究中都取得了一定的成果。这些项目围绕网格中间件、网格调度、网格性能监测和预报、网格资源选择、网格编程环境、网格门户、网格环境下的数据管理和服务等方面开展了丰富的研究，也构建了多个网格计算实验床1 2 l 】。另外还有很多网格计算研究项目针对网格计算领域的某一研究方向开展了研究。包括，以核心中间件和工具包开发为目标的项目，如著名的g l o b u s 项目、l e g i o n项目、n m i 计划1 2 2 】等：还有以研究网格应用调度和作业管理为目标的项目，如计算网格应用调度软件包a p p l e s f 2 3 1 、c o n d o r g t e j 等等。1 2 研究内容1 2 1 网格任务调度简介从本质上来讲，网格就是一个基于广域网构建的分布式计算系统，它与传统的分布式系统的主要区别在于它具有广域性、异构性、动态性三个特点。它主要应用于解决科学、工程、商业领域中规模庞大、计算复杂、需要使用多种异构资源的计算问题，这样的问题大量存在，而且在任何一个单一的超级计算机上都无法解决。由于网格资源所具有的这些特点以及网格应用的复杂性，以前针对传统的分布式计算的调度方法已经不适用于网格环境中的任务调度。在传统的并行和分布式调度问题中，所涉及的计算资源是同构的，因此不必关心资源所具有的属性以及资源能否满足用户所提交的任务的需要，而且，计算资源通常在地理上是集中的，因此不用关心系统在运行过程中通信所花费的开销。网格任务调度的目的就是将“合适”的任务分配到“合适”的资源上去运行。因此，不同的网格任务调度系统就可能有不同的调度日标，有的是为了增大系统的计算吞吐率，有的是为了使系统的利用率最大化，有的则是为了以最经济、最节省的方式使用户的需求得到满足。教育部的中国教育科研网格项目( c h i n a g r i d ) 。该项目是“十五”国家“2 1 1工程”公共服务体系“c e r n e t ( 中国教育科研网) 高速地区网和重点学科信息服务体系建设”项目中的重要建设内容，目标是在2 0 0 5 年建立聚合计算能力超过1 5 万亿次量级的教育科研网络，形成世界上晟大的超级网格之一，并争取在网格计算的基础研究和应用研究方面走在世界前列。另外，国内还有一些行业应用网格和地区性网格研发项目，如中国气象网格、空间信息网格、上海城市网格等。国内多个大学、科研单位也已经开始了网格计算技术的研究，中国科学院计算所研究开发了v e g a 网格i ，清华大学、国防科技大学、华中科技大学等单位在网格技术研究中都取得了一定的成果。这些项目围绕网格中间件、网格调度、网格性能监测和预报、网格资源选择、网格编程环境、网格门户、网格环境下的数据管理和服务等方面开展了丰富的研究，也构建了多个网格计算实验床m 】。另外还有很多网格计算研究项目针对网格计算领域的某一研究方向开展了研究。包括，以核心中问件和工具包开发为目标的项目，如著名的g l o b u s 项目、l e g i o n项目、n m i 计划m 1 等；还有以研究网格应用调度和作业管理为目标的项目，如计算网格应用调度软件包a p p l g s l 2 ，l 、c o n d o r g i s i 等等。1 2 研究内容1 2 1 网格任务调度简介从本质上来讲，网格就是一个基于广域网构建的分布式计算系统，它与传统的分布式系统的主要区别在于它具有广域性、异构性、动态性三个特点。它主要应用于解决科学、工程、商业领域中规模庞大、计算复杂、需要使用多种异构资源的计算问题，这样的问题大量存在，而且在任伺一个单一的超级计算机上都无法解决。由于网格资源所具有的这些特点以及刚格应用的复杂性，以前针埘传统的分布式计算的调度方法已经不适用于网格环境中的任务调度。存传统的并行和分布式调度| 、口j 题中，所涉及的计算资源是同构的，因此不必关心资源所具有的属性以及资源能否满足用户所提交的任务的需要，而月，计算资源通常在地理上是集中的，冈此不用关心系统在运行过程巾通信所花费的开销。网格任务侧度的目的就是将“合适”的任务分配到“合适”的资源上去运行。因此，不同的网格任务调度系统就可能有不同的调度日标，有的是为了增大系统的计算吞r 率，有的是为了使系统的利用率最人化，有的则是为了以最经济、虽节省的方式使用户的需求得到满足。省的方式使用户的需求得到满足。目前，网格计算已经在许多方面进行了应用，针对不同的应用，有许多网格任务调度模型和算法被提出。本文对其中一些模型和算法进行了研究，并做了相关工作。1 2 2 研究现状网格的出现，对分布式任务调度研究提出了新的挑战。目前，已有许多科研组织对网格任务调度进行了研究。下面简单介绍了当前网格计算中几个主要的调度模型以及相关的调度算法。c o n d o rc o n d o r 系统是面向高吞吐率计算( h i g l lt h r o u g h p u tc o m p u t i n g ) 计算而设计的，它的主要目的就是利用网络中工作站的空闲时间来为用户服务。针对这种应用，c o n d o r 使用的调度方法就相对简单一些。它定义了一套半结构化的数据模型- - c 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 i n g ) 和声明( c l a i m i n g ) ，在匹配阶段，m a t c h m a k e r 在可获得资源中找到最适合任务的资源，然后通知用户和服务提供者，随后用户和服务提供者再进行声明，以此确立两者之间消费与服务的关系。n i m r o d由于网格的异构性，其资源可能被不同的个人或者组织拥有，从而具有不同的管理策略、访问成本以及动态变化的性能。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 tc 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 ，此算法根据用户任务对于完成时间以及花费预算的要求对任务进行调度。其中，根据算法的侧重点不同，此算法又有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 cc o s t t i m eo p t i m i z a t i o n 三种分支。a p p l e sa p p l e s 是a p p l i c a t i o nl e v e ls c h e d u l i n g 的简称，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 pa 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 提 h 了一个自适应的任务调度算法，在这个算法中，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 rs w e e pa p p l i c a t i o n 中存在任务共享输入文件的情况，c a s a n o v a 等人在s u f f e r a g e 算法的基础上进行改进后提出一个新的调度策略- - x s u f f e r a g e ，实验证明，共享文件越大，x s u f f e r a g e的优越性越明显。随着网格的不断发展，在任务调度领域不断有新的挑战出现。在一些网格应用中，有些应用要求在能够提供一定的q o s 的资源上运行，而有些应用则在资源能提供的q o s 方面没有要求。在这种新的调度模型下，一种新的以q o s 为指向的启发式算法一q o sg u i d e d m i n m i nh e u r i s t i c 被提出来，它是在m i n m i nh e u r i s t i c的基础上改进而来。 3 本文的主要工作本文所做的主要工作如下：a p p l e sp a r a m e t e rs w e e pt e m p l a t e 为了提高p a r a m e t e rs w e e pa p p i c a t i o n 的执行效率，使甩了一个自适应的任务调度算法。此算法包含有若干步骤，其中一个步骤是将待调度的任务集合中的任务分配到相应的主机上运行。在这一步骤中，算法可以使用包括w o r k q u e u e 、m i n m i n 、m i n m a x 、s u f f e r a g e 在内的调度策略来进行调度。而针对p a r a m e t e rs w e e pa p p l i c a t i o n 中存在任务共享输入文件的情况，在s u f f e r a g e 算法的基础上进行改进后提出一个新的调度策略- - x s u f f e r a g e ，实验证明，共享文件越大，x s u f f e r a g e 相对于其他调度策略的优越性越明显。而在对任务集合进行调度之前，为了减少调度开销，算法要在整个任务集合中选择出一个任务子集。这样就使得任务的调度产生了先后次序。当在大量文件共享，并用x s u f f e r a g e 来进行调度的情况下，不同的调度次序可能会带来不同的调度结果。原算法中使用的是随机选择的办法，因此，给调度带来的影响也具有很大的随机性。本文对p a r a m e t e rs w e e pa p p l i c a t i o n 以及计算网格模型的特性进行了研究，提出了一种任务子集的选择方式，并通过s i m g r i d f 州平台进行了模拟实验，实验表明，在使用x s u f f e r a g e 进行调度的条件下，当共享文件越多时，算法性能提高幅度越大。网格的不断发展使得服务质量( q o s ) 成为在任务调度中需要考虑的一个重要因素。在某些应用中，一些任务对于资源所能够提供的q o s 有要求，而另一些任务则没有；一些高端资源能够提供较高的q o s ，而一些低端资源则不能。在这种情况下，传统的任务调度算法不能满足任务调度的需要。因此，有人在m i n m i nh e u r i s t i c 的基础上提出了q o sg u i d e dm i n m i nh e u r i s t i c 。但是此算法是周期性运行的，周期的长短对于调度有一定的影响。如果周期太短，则调度开销势必会增大；如果周期太长，则可能造成计算资源的浪费。因此，本文对原算法进行了一些扩展，使得算法更加灵活。然后通过模拟实验表明，扩展算法与原算法相比在性能上有一定的提高。最后，本文对容错技术在网格任务调度领域的应用进行了一此探讨，并在现有的一种基于备份技术的网格容错调度策略的基石j | i 上引入可用性的概念，提出一种新的容错调度策略。全文包含五个章节，分别安排如下：第一章是“绪论”，包括研究背景、研究内容和本文所做的主要工作；第二章是“网格体系结构以及g l o b u s 网格中间件”，简单介绍了现在网格研究领域中两种主要的体系结构以及g l o b u s 网格中间件，以及基于g l o b u s 的网格任务调度框架：第三章是“基于p s t 的网格任务调度算法及其改进”，主要包括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 的网格任务调度算法，针对算法的不足进行的一些分析和改进，以及相应的模拟实验和结果对比；第四章是“q o sg u i d e dm i n m i nh e u r i s t i c 及其扩展”，包括对q o sg u i d e dm i n m i nh e u r i s t i c 的介绍，对于可以进一步提高算法性能的可能性分析，以及模拟实验和结果对比：第五章是“容错技术在网格任务调度中的应用”，包括对相关容错技术的介绍，对将可用性概念和备份技术应用于网格任务调度的可能性的探讨以及相应的网格任务调度过程的描述；最后总结全文。第2 章网格体系结构以及g l o b u s 网格中间件2 1 网格体系结构网格体系结构是划分网格系统基本组件、指定系统组件的目的与功能、以及说明组件之间如何相互作用的技术。在当前，比较重要的网格体系结构有两个，一个是f o s t e r 等人在早些时候提出的五层沙漏结构n i 另一个是在考虑到w e b 技术的发展和影响后，结合w e bs e r v i c e 提出的开放网格服务结构o g s a ( o p e n g r i ds e r v i c ea r c h i t e c t u r e ) 。2 1 1 五层沙漏结构这里简要介绍一下五层沙漏结构的网格体系结构模型，它是以协议为中心的层次结构，以沙漏模型的原则刻画了计算网格的体系结构。五层沙漏结构如图2 1所示：应用层+l 汇聚层r资源层连接层图2 1 计算网格的五层沙漏形体系结构模型1 2 6 i各层的功能特点如下：( 1 ) 构造层( f a b r i c ) ：局部控制的乔面。网格构造层的基本功能就是控制局部的资源，向上提供访问这些资源的接口。构造层的资源是非常广泛的，可以是计算资源，存储系统，目录，网络资源和传感器。构造层网格组件实现对本地特定资源的访问，向上提供访问这些资源的接口。因此在构造层各种功能实现卜- ，有耄紧密和互相依赖的联系，还有对共享的支持。构造层实现的基本功能包括查询机制、控制服务质量的资源管理能力等。( 2 ) 连接层( c o n n e c t i v i t y )支持便利安全的通信。连接层的基本功能是保证构造层的资源实体间相互通信的便利和安全，在这一层，网格定义了核心的网络事务处理所需要的通信和认证协议。通信协议允许在构造层资源之间交换数据，建立在通信服务上的认证协议提供加密的安全机制，用于识别用户和资源。通信的必要条件包括传输，路由和命名等功能。在实际上，通信协议大部分是从t c p i p 协议栈中抽出的。比如i n t e r n e t 体系结构的i n t e r n e t 层( i p 与i c m p ) ，传输层( t c p 与u d p ) ，和应用层( d n s 、o s p f 、r s v p 等)( 3 ) 资源层( r e s o u r c e )共享单一的资源。资源层建立在连接层的通信和认证协议之上，定义的协议包括安全的连接、初始化、监视和控制、审计、计费等。资源层的协议实现调用构造层的功能以访问和控制本地资源。资源层的最重要的两个协议是信息协议和管理协议，前者用于获得关于资源结构和状态的信息，后者用来协商对共享资源的访问。( 4 ) 汇聚层( c o l l e c t i v e )协调各种资源。汇聚层的基本功能是协调多个资源的共享，实现虚拟组织。汇聚层组件建立在资源层和连接层形成的协议瓶颈之上，它们能够在不对资源强加新的要求的情况下实现广泛的和多样化的共享行为，如目录服务，协同分配，调度和代理服务等。( 5 ) 应用层( a p p l i c a t i o n )虚拟组织中的所有用户应用构成了网格的应用层，它调用下一层次中的服务来构造网格应用。从网格应用开发者的角度来看，下面各个层次的协议和服务都提供了相应的a p i 和s d k ，使得用户可以很容易的构建网格应用。可见，以资源共享协议和资源问的通信协议为核心，网格环境实现了广域范围内的资源共享和协同工作，将面向i n t e r n e t 的计算推进到了一个新的阶段。计算网格体系结构中的连接层、资源层和汇聚层的功能需要由架构在资源层之上、应用层之下的网格中间件实现。2 1 2 开放网格服务体系结构开放网格服务结构o g s a ( o p e ng r i ds e r v i c e sa r c h i t e c t u r e ) 是g l o b a lg r i df o r u m4 的重要标准建议，是继五层沙漏结构之后最重要的一种网格体系结构。它与五层沙漏结构最大区别在于，它不时i 柚沙漏结构一样以协议为巾心，而是以服务为中心的。这里的服务是指具有特定功能的网络化实体，包括各种计算资源、存储资源、网络、程序、数据库等等。在o g s a 中，实现的不再是对资源的共享，而是对服务的共享。从资源到服务，这种抽象将资源、信息、数据等统一起来，有利于灵活的、一致的、动态的共享机制的实现。2 2g l o b u s 网格中间件在网格计算研究领域，研究、开发高质量的网格中间件是一个很重要的课题。网格中间件一般被认为是在操作系统和应用之间的软件层，它可以屏蔽网格资源的异构性，为上层应用提供一个统一的资源视图，使得在开发、布置网格应用的时候不需要考虑底层异构网格资源的特性，只需调用网格中间件提供的各种标准接口，对网格应用的开发、执行因此变得简单易行而且可靠有效。目前，许多网格研究项目几乎都是着力于开发能够集成现有的异构资源和服务的中间件。典型的计算网格中间件研究项目如g l o b u s t 2 a i 和l e g i o n l 2 9 1 ，其中g l o b u s 项目中开发的g l o b u s 工具包已经在许多网格项目中得到了广泛的应用。g l o b u s 项目是目前国际上具有影响的网格计算研究项目，g l o b u s 工具包已经成为构建网格环境的事实上的标准。g l o b u s 是美国a r g o n n e 国家实验室的研发项目，在初始阶段，全美有十多所大学和科研机构参与了该项目的研究工作。g l o b u s对信息安全、资源管理、信息服务、数据管理以及应用开发环境等网格计算的关键技术进行了广泛的研究，开发出了能在多种平台上运行的网格计算工具包软件( g l o b u st o o l k i t m ) ，可以用来帮助规划和构建大型的网格实验和应用平台，开发适合大型网格系统运行的网格应用。目前，g l o b u s 工具包已在n a s a 网格( n a s ai p g ) 、欧洲数据网格( d a t ag r i d ) 、美国国家技术网格( n t g ) 等众多项目中得到应用。为了有效地支持网格计算环境，g l o b u s 工具包主要实现了以下四个方面的功能：1 ) 资源管理功能网格计算中涉及到大量的、异构的、甚至是不同类的资源，因此，g l o b u s 工具包应当能够提供一套统一的、可扩展的管理机制来管理远程系统中的计算和通信资源，并使得它们在并行和分布式计算过程中能协同合作。2 ) 数据管理和访问功能在一些分布式的科学和工程应用中，往往需要访问大量的数据，因此，如何管理数据使得对数据的访问简易、有效是g l o b u s 工具包必须要解决的一个问题。3 ) 信息服务功能在分布式环境下的高性能计算往往得益于对计算机、网络等资源以及适合于具体应用的协议、算法的选择和配置，这都需要有相关资源最新的、精确的信息来支持，因此，g l o b u s 工具包必须能够提供高质量的信息服务。4 ) 安全功能网格是一个广域的分布式系统，安全问题是用户最关心的问题之一。它常常包含许多不同域的计算资源，每一个域都有各自的安全策略，所以，g l o b u s工具包必须能够提供一套可以处理这种复杂情况的安全机制。为了实现以上提到的四方面功能，面向计算网格的g l o b u s 工具包主要组成部分包括- ：1 ) 安全基础设施( g r i ds e c u r i t yi n f r a s t r u c t u r e ，g s i )负责在广域网络下的安全认证和加密通信，提供单点登录功能、远地身份鉴别功能、数据传输加密功能等；2 ) g l o b u s 资源分配管理( g l o b u sr e s o u r c ea l l o c a t i o nm a n a g e r ，g r a m )负责远程应用的资源请求处理、远程任务调度处理、远程任务管理等工作，是阚格计算环境中的任务执行中心；3 ) 元计算目录服务( m e t a c o m p u t i n gd i r e c t o r ys e r