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

基于关键路径的网格任务调度算法研究 摘要 随着网络技术的飞速发展，互联网上充斥着更多可以利用的廉价资源。利 用此类资源的网格计算解决规模庞大、复杂问题具有重要的意义。网格资源具 有规模庞大、分布异构和动态性等特点。实现高效的网格计算需要解决许多复 杂的问题，任务调度问题就是其中的一个关键问题。 网格资源动态性主要反应在资源能力衰减、增强以及新资源的加入和旧资 源的退出。以往的很多调度算法主要关注调度方案制定，直接将任务加入到资 源节点的待执行任务序列，忽略了方案制定时和方案执行时资源能力的变化。 若在方案制定时的资源能力在方案执行时衰减( 退出) ，使得高权限任务占有 了低性能资源，造成任务执行时间增加，有可能增加整个应用的并行完成时间 ( m a k e s p a n ) ；若在方案制定时的资源能力在方案执行时增强，任务执行时间 减小，有可能减小整个应用的m a k e s p a n ；当新资源加入时，由于已经为任务 分配资源，所以不影响任务执行时间和整个应用的m a k e s p a n 。 为了减小资源能力衰减引起应用m a k e s p a n 增加的程度，以及增加能力出 众的新加入资源对作业l a k e s p a n 的影响，本算法根据调度执行开始时间 ( b t ) 将任务调度分为调度方案制定( t s p f ) 和调度方案执行( t s p e ) 两个阶 段，定义了网格环境下的调度执行最晚开始时间、调度执行开始时间和任务优 先图( d a g ) 中边的权值，分析了任务图冻结消减和执行消减对任务图结构的 影响以及方案制定和方案执行时间的资源能力变化对调度准确性的影响。 基于关键路径的调度算法( c p a ) 认为，尽量提前任务优先图关键路径中 每个任务的完成时间，就能缩短整个作业的m a k e s p a n ，即关键路径上的任务 具有更高的优先权。但是，与基于最早开始时间的调度算法( e t f ) 比较发 现，最早开始时间同样影响着作业m a k e s p a n ，且在一定条件下e t f 算法优于 c p a 算法。 当前大多数调度算法主要通过预防抢夺解决资源抢夺，即在任何情况下都 不允许资源抢夺。本算法在关键路径算法的基础上，根据关键路径长度( c p ) 定义了任务优先权，并且考虑最早开始时间对作业m a k e s p a n 的影响，允许未 分配资源的任务抢夺已经被任务占有的资源。在此基础上定义了资源抢夺和调 度最小图，分析了资源抢夺有可能出现的几种情况，以及对任务图和调度结果 的影响，并且针对一种资源抢夺情况，提出了两个启发式原则用以决定是否允 许资源抢夺。 最后，提出了基于b t 的允许资源抢夺的网格依赖任务调度算法 ( b t t s ) 。重点分析了网格模拟平台g r i d s i m ，并在此平台上实现e t f 算法、 c p a 算法和b t t s 算法，试验结果发现b t t s 算法优于其它两种算法，且有效地 降低了网格动态性对调度结果的影响。 关键词：网格；d a g 图；冻结消减；调度执行开始时间；资源抢夺 t h er e s e a r c ho fg r i dt a s ks c h e d u l i n ga l g o r i t h mb a s e do n c r i t i c a lp a t h 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 ft h en e t w o r kt e c h n o l o g i e s ，t h ei n t e r n e tc a nb e f i l l e dw i t hm o r ea v a i l a b l ec h e a pr e s o u r c e s s o l v i n gl a r g e s c a l e ，c o m p l e xp r o b l e m s i s i m p o r t a n t t ou s es u c hr e s o u r c e s g r i d s y s t e m c o n s i s t so faw i d e o f g e o g r a p h i c a l l y d i s t r i b u t e dr e s o u r c e sa n dt h e s er e s o u r c e sa r eh e t e r o g e n e o u s ， g e o g r a p h i c a l l yd i s t r i b u t e da n dd y n a m i c a l l ya v a i l a b l e m a n yc o m p l e xp r o b l e m s n e e dt ob ea d d r e s s e dt oi m p l e m e n te f f e c t i v eg r i dc o m p u t i n g ，w h e r et a s ks c h e d u l i n g i sac r i t i c a lp r o b l e mt ob es o l v e d r e s o u r c e s d y n a m i c c o n c l u d e st h ei n c r e a s eo rd e c r e a s eo ft h er e s o u r c e c a p a c i t y ，a n dj o i n i n go rw i t h d r a w i n go f t h er e s o u r c e b a s i n go nt h ea n a l y s i so ft h e v a r i o u st a s ks c h e d u l i n ga l g o r i t h m sf i n dt h a tm a n yp r e v i o u ss c h e d u l i n ga l g o r i t h m s a l w a y sp a ya t t e n t i o nt ot s p f ，a n dd i r e c t l yi n s e r tt h et a s ki n t ot h et a s ks e q u e n c eo f t h er e s o u r c e ，b u tn e g l e c tw h e t h e ri tc a nb ei m p l e m e n t e d d e c l i n i n go ft h er e s o u r c e c a p a c i t yf r o mt h et s p ft i m et o t h et s p et i m e ，m a k e st h et a s kh i g hp r i o r i t y o c c u p i e s al o w p e r f o r m a n c er e s o u r c e ，i n c r e a s e st h et a s ke x e c u t i o nt i m e ，a n d m a y b ed e l a y st h em a k e s p a n o nt h ec o n t r a r y , e n h a n c e m e n t o ft h er e s o u r c e c a p a c i t yf r o mt h et s p ft i m et ot h et s p et i m e ，d e c r e a s e st h et a s ke x e c u t i o nt i m e ， m a y b ea d v a n c e st h em a k e s p a n b e c a u s et h et a s kh a so c c u p i e dar e s o u r c e ，t h eo n e w i l ln o te a s i l yg i v eu pt h eo l dr e s o u r c ea n dc a t c han e w ，t h en e wr e s o u r c e sw i l ln o t i n f l u e n c et h em a k e s p a n i no r d e rt oa b a t et h ei n f l u e n c eo fd e c r e a s eo ft h er e s o u r c ec a p a c i t yo nt a s k s c h e d u l i n g ，a n di n c r e a s et h ei n f l u e n c eo fn e we x c e l l e n tr e s o u r c e so nt h em a k e s p a n ， t h et a s ks c h e d u l i n gi sd i v i d e di n t ot w os t a g e sa c c o r d i n gt ob t t s p fa n dt s p ei n t h i sd i s s e r t a t i o n ag r o u po ff e a t u r e s ，w h i c hi n c l u d el a t e s tb e g i nt i m e ( l b t ) ， b e g i nt i m e ( b t ) a n dt h ee d g ew e i g h ti n ad a g , a r ed e f i n e di nt h i sd i s s e r t a t i o n w ea n a l y z et h e i m p a c t o nd a gb yf r e e z i n ge l i m i n a t i o na n di m p l e m e n t i n g e l i m i n a t i o na n dt a s ks c h e d u l i n ga c c u r a c yb yt h eg a pb e t w e e nt s p ft i m ea n dt s p e t i m e c r i t i c a lp a t ha l g o r i t h m s ( c p a ) h o l d st h a tc o m p l e t i o nt i m eo fe a c ht a s ki na d a gc r i t i c a lp a t hs h o u l db ea d v a n c e da sm u c ha sp o s s i b l e ，t h u sm a k e s p a nc a nb e s h o r t e n ，i e t a s k so nc r i t i c a lp a t hh a v et h eh i g h e s tp r i o r i t y b u tc o m p a r e dt oe t f ， 1 1 1 i ti sf o u n dt h a tt h ee a r l i e s tb e g i nt i m ea l s oi n f l u e n c e sm a k e s p a na n de t fs u r p a s s e s c p au n d e rc e r t a i nc o n d i t i o n s c u r r e n t l ym o s ts c h e d u l i n ga l g o r i t h m sm a i n l y a d d r e s sr e s o u r c e sr o bb y p r e v e n t i n gf r o mr o b b i n g ，i e r e s o u r c e sr o bi sn o ta l l o w e di na n yc a s e t h eb t t s d e f i n e st a s kp r i o r i t y , c o n s i d e r st h ee a r l i e s tb e g i nt i m e si n f l u e n c eo nm a k e s p a na n d a l l o w st h a tt a s k sw h i c hh a sn o ta s s i g n e df o rr e s o u r c e sr o bt h er e s o u r c e sh e l db y o t h e r t a s k sa c c o r d i n gt ot h el e n g t ho fc r i t i c a lp a t h ( c p ) o nt h eb a s i so fc p a r e s o u r c e sr o ba n dm i n da ga t ed e f i n e d ，s e v e r a lc o n d i t i o n st h a tr e s o u r c e sr o b m a yo c c u rt h ei n f l u e n c e so nd a ga n ds c h e d u l i n gr e s u l t s a r ea n a l y z e da n dt w o h e u r i s t i cp r i n c i p l e st od e c i d ew h e t h e rr e s o u r c e sr o bi s a l l o w e df o rak i n do f r e s o u r c e sr o bs i t u a t i o n f i n a l l y ，t h eb t t sa l g o r i t h mi sp r o p o s e d f o c u s e do na n a l y z i n gat o o l k i tf o r m o d e l i n ga n ds i m u l a t i n gg r i de n v i r o n m e n t - - g r i d s i m ，t h ee t fa l g o r i t h m ，c p a a l g o r i t h ma n db t t sa l g o r i t h ma r ei m p l e m e n t e do nt h ep l a t f o r m b yc o m p a r i s o n w i t he t fa l g o r i t h ma n dc p aa l g o r i t h m ，t h eb t t sa l g o r i t h mi s b e t t e rt h a nt h e o t h e r s ，a n dr e d u c e st h ei m p a c to nt h er e s u l to ft a s ks c h e d u l i n gb yr e s o u r c e s d y n a m i c k e y w o r d s ：g r i d ；d a g ；f r e e z i n ge l i m i n a t i o n ；l a t e s tb e g i nt i m e ；r e s o u r c e sr o b 1 v 图表清单 2 一l 沙漏形状的五层结构10 2 2o g s a 架构1 l 3 1 用时间槽表示资源能力分配2 0 3 2 任务调度图2l 4 1 任务优先图2 3 4 2 任务调度流程图2 5 4 3 任务调度图2 6 4 4 任务优先图2 7 4 5 调度最小图集合2 8 5 一lg rid si m 体系结构3 2 5 2 模拟数据实验结果柱图( g e = o 1 ) 3 7 5 3 模拟数据实验结果曲线图( g e = o 1 ) 3 7 5 4 模拟数据实验结果柱图( g e = o 8 ) 3 7 5 5 模拟数据实验结果曲线图( g e = o 8 ) 3 8 5 6g e 影响调度结果柱图3 8 5 1b t t s 算法抢夺次数3 8 5 2 资源利用率( g e = o 1 ) 3 9 5 3 资源利用率( g e = o 8 ) 3 9图图图图图图图图图图图图图图图表表表 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 金旦曼王些太堂 或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签字z 蓊签字魄匀年纷伊 学位论文版权使用授权书 本学位论文作者完全了解金鲤至些太堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权盒胆王些太堂可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：乏 签字日期：少7 年钩循 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 婵醐：7 咖 | 致谢 毕业在即，三年的研究生学业生涯即将成为往事。首先，感谢我的导师李 心科副教授。本文的研究工作是在李老师的精心指导和悉心关怀下完成的，在 我的学业和论文的研究工作中无不倾注着导师辛勤的汗水和心血。李老师严谨 的治学态度、渊博的知识、谦和的待人风范使我深受启迪。从尊敬的李老师身 上，我不仅学到了扎实、宽广的专业知识，也学到了做人的道理。在此，再次 向李老师致以最衷心的感谢和深深的敬意。 其次要感谢的是王钊副教授、邵垄副教授，两位老师理论功底扎实，思路 镇密，在我的学业生涯中给予了重要的帮助和指导；在我写作论文的过程中给 了我许多灵感与启发，提出了许多改进的意见。 还要感谢软件工程实验室的金元杰、周东星、杨晓辉等同学以及师弟师妹 们，和他们在一起工作和学习使我受益匪浅，大家在一起学习和讨论的日子使 我终生难忘。 特别要感谢我的父母，是他们含辛茹苦抚养我成人，给我以人生指导，给 我学业以物质和精神支持，没有他们的支持与赞赏，我不可能走到现在。谢谢 你们! 在此，谨以此文向以上关怀和帮助过我的所有老师、同学、朋友、亲人表 示衷心的感谢! 第一章绪论 1 1 课题来源 本论文受国家创新基金计划项目“安徽省中小企业综合服务平台”( 项目 编号0 7 c 2 6 1 4 3 4 0 1 4 7 7 ) 和安徽省科技厅科技计划项目“面向科技服务体系基 于b i 技术的决策支持系统的研究及应用”( 项目编号0 6 0 12 0 21 a ) 资助。 1 2 本文的目的和意义 随着商业计算越来越复杂，人们越来越需要数据处理能力更强大的计算 机。另一方面，计算机技术和通讯技术的迅速发展使得利用互联网把分散在不 同地理位置的电脑组织成一个“虚拟的超级计算机”变为可行。于是，网格技 术应运而生，满足不同的信息化使用者对计算机技术的需求。 网格计算最早的推动力来自学术界，尤其是涉及高能物理、分子生物、海 洋科学、气象分析等需要极强运算能力的高性能计算领域。另一个推动网格计 算的动力来自产业界，主要是那些需要很强计算和协作力的能特殊行业，包括 生物技术、制药行业等。随着技术的发展与网格概念的延伸，网格系统己不再 是一个封闭的、集中于计算的平台，而是一个开放的，集计算、信息、事务处 理和服务于一体的分布与协同的综合平台。它将各种信息资源，例如数据库、 软件以及各种信息获取设备都连接成一个整体，向每个用户提供包括计算能 力、数据存储能力以及各种应用工具等一体化透明的服务。与此相对应，其应 用领域也不断拓宽。 科学研究需要网格。 科学领域中的数值计算问题存在于许多学科中，这类应用对计算能力的需 求似乎没有止境。物理学中大规模微分方程组的求解问题就是一个例证；计算 化学的出现使化学这一试验学科有了新的研究工具；在生物学领域，基因序列 的测序与分析需要很强的计算能力，目前任何超级计算机也无法完全满足这一 需求：在天文、地质( 石油勘探) 和天气预报等领域有着类似的需求。这些科研 人员不但需要超强的计算能力，而且为了科研的方便和直观性的要求，大量的 计算结果需要进行可视化处理。对于这些应用需求，现有的信息技术难以完 成：一方面，超级计算机昂贵的价格使得它很难进入普通人的工作领域；另外 一方面，有些工作所需的计算能力并非目前的单独一台计算机能够提供。这就 需要新的计算技术来完成这些需求。 工业界需要网格。 工业界的信息化需求是网格技术的又一个主要的推动力量。现在，跨国企 业在数量和规模上都在不断增长，这些公司的分支机构遍布全球，它们需要共 享资源和协同工作，从n c s a 到i b m 都已经认识到这种需求的紧迫性，已经开 始了相应的研究工作，并取得了初步的成果。例如，制药企业开发一种新的合 成药物，需要联合多家企业和研究单位，在研究过程中需要彼此分享研究成 果，共同研究试验方案，并将结果可视化的表示出来，网格技术可以很好的解 决这一问题。 教育界需要网格。 教育界同样需要网格技术来提高教育和培训的质量，同时降低教育的成 本。虽然发达国家的教育事业比较发达，但他们同样需要网格技术来实现教育 资源的增值；发展中国家的教育资源本来就较臣乏，网格技术可以将有限的资 源放大，使更多的人受益于信息化。同时，还可以将发达国家的教育资源通过 网格技术输送到发展中国家，这种方式可以有效地降低教育的直接费用。大学 通过网格技术可以有效地联合处于不同地理位置的其它大学，以很小的成本做 到资源共享、优势互补。中小学和其它教育机构也有着类似的需求。 服务业需要网格。 服务业一直是信息技术的推动力量之一，随着服务业的快速发展，服务机 构遍布社会的各个方面。对数据资源的共享尤为迫切，为了完善服务也需要集 成大量的数据。例如，银行业在这方面的需求比较具有代表性，随着银行对客 户提供服务的不断完善，大量的服务网点需要资源进行共享和互操作。 由于网格资源具有分布性、异构多样性、动态变化性等特点，因此网格的 研究具有极大的挑战性。其中任务管理是网格的核心与难点，同时也是网格计 算中具有研究价值的一个方面，己成为网格技术中的热点研究方向。网格任务 管理器结构、任务调度策略和资源信息服务是网格任务管理中的三个重要问 题。网格任务管理器为用户提供任务提交、任务调度、查询及监控等功能：任 务调度策略根据任务的资源需求和网格资源的状态，为任务寻找合适的资源， 以完成用户提交的任务，并实现对网格资源的优化使用；网格资源信息服务主 要完成对网格环境中资源的发现、注册、查询等工作，为任务调度提供必要的 资源信息，以更有效的使用各种资源。 1 3 网格计算与任务调度研究概况 1 3 1 网格计算研究概况 网格一词最早出现在2 0 世纪9 0 年代中期，而网格计算的概念在1 9 9 5 年 的i w a y 项目中被提出。网格概念是在问题和应用的推动下不断发展、丰富和 完善的。网格的发展到目前为止基本上可以划分为以下几个阶段： 萌芽阶段：在9 0 年代早期，主要是千兆网的测试床，以及一些元计算 的试验； 早期试验阶段：在9 0 年代中期到晚期，如i w a y 项目，还包括一些学 术性的软件项目，如g i o b u s ，l e g i o h t ，以及一些应用试验； 迅速发展阶段：2 0 0 2 年以来，出现了大量的计算服务网格研究和应用 项目，出现了影响很大的组织一一全球网格论坛g g f ( g i o b a lg r i df o r u m ) ，致 力于制定全球网格计算的标准和规范。同时，网格计算也不再仅仅局限于科学 研究，工业界与学术界联盟正致力于网格计算在更广泛的科学、工程和商业领 域得到推广和应用。 在网格计算领域的研究工作主要集中于网格计算环境中的基础研究和建立 专用应用网格两条线路，前者主要被国外以g i o b u s 同腽为代表的研究组织所领 导，而对于后者，在国外主要集中在美国和欧洲。如英国政府己投资1 亿英 镑，用来研制“英国国家网格( u kn a ti o n a lg r i d ) 。美国军方正规划实施 一个宏大的网格计划，叫做“全球信息网格( g l o b a l i n f o r m a ti o n g r i d ) ，预计在2 0 2 0 年完成。作为该计划的一部分，美国海军陆战部队己 启动了个耗资1 6 0 亿美元历时8 年的项目，包括系统的研制、建设、维护和 升级。在我国国内，网格研究项目主要有清华大学的先进计算基础设施a c i ( a 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 h p c e ( n a t i o n a lh i g hp e r f o r m a n c ec o m p u t i n ge n v i r o n m e n t ) 、教 育部“十五2 1 1 建设 重点项目“中国教育科研网格计c h in ag r id ”和中科院 领衔主持的“织女星网格”项目。 1 3 2 网格任务调度研究概况 将网格作业分解为多个子任务，每个子任务有各自的资源需求，然后提交 到网格调度系统执行调度，是目前网格调度系统采用的通用方法。网格应用模 型对于网格调度和任务分配产生重要的影响，不同类型应用的约束条件不一 样，尤其是网格环境中由于没有完全集中的控制，在资源的分配和调度上对不 同的应用模型的任务的处理方式是不一样的。主要有两种不同类型的任务，相 互之间独立的任务，即m e t a t a s k s ；另外是相互之间存在依赖和时序关系、因 果关系的任务。 调度中预期任务运行时间是一个关键部分，可以通过两种方法计算：短 期预测模型：在调度的第一轮，调度器进行初步猜测所有任务的执行时间。当 任务完成后，调度器使用观测的执行时间提高预测算法的准确性。长期预测 模型：用来在非专用计算环境预测任务执行时间。 目前在网格调度算法研究中，引入并行处理方面的研究成果，其目标主要 是增加吞吐率，增加系统的使用率，满足用户的经济需求和约束条件。实现在 整个系统中网格应用任务的完成时间最小，即m a k e s p a n 最小，找到一个这样的 m a k e s p a n 是n p 完全问题。 任务调度算法主要分为静态调度和动态调度两大类。静态调度算法假设任 务图和处理单元相关的信息在程序执行前可以精确获取，调度好的任务节点不 能迁移，也称为编译时间调度算法；反之，则称为动态调度算法，也称为实时 调度算法n 1 。由于调度问题本身是一种n p 完全问题，国内外的研究者提出了 很多启发式算法，这些算法分为表调度算法雎6 7 1 5 ，1 6 ，5 5 3 、基于复制的调度算 法、基于任务聚类的调度算法2 2 1 、基于随机搜索技术盥4 2 引的调度算法等等。 表调度算法的思想是，首先从任务列表中选取一个合适的任务进行调度，其次 为这个任务分配一个最优的资源节点心1 。 1 4 本文研究内容 本文研究了网格中较为重要的问题，包括网格体系结构、资源管理、资源 抢夺、任务调度以及网格模拟器等。重点研究了资源管理模型、资源抢夺以及 任务调度等问题，实验操作环节选取澳大利亚墨尔本大学开发的模拟器 g r i d s i m 作为算法比较模拟平台。 资源管理模型：网格计算的本质是通过共享地理上分布在多个自治系统中 的资源来协同完成某个任务。因此，如何对网格计算环境的资源进行管理是实 现高性能联合计算，共同完成重大应用问题的关键。目前网格资源管理系统模 型主要分为三类：分层模型、抽象所有者模型和计算经济模型。在分析了三个 模型基础上，本文采用分层模型管理网格资源。 资源抢夺：以往的大多数静态调度算法认为资源被任务占有后不允许其它 任务抢夺，或者将允许资源抢夺的调度算法一概而论的划入到动态任务调度算 法中。此时有可能出现两种情况：任务已经开始在资源节点上执行和任务虽然 占有资源但还没有执行。第一种情况下动态调度算法可以要求低权限任务为高 权限任务放弃已经占有的资源，但是静态调度算法却对此无能为力。第二种情 况下由于任务还没有在资源上执行，所以认为此时未分配资源的低权限任务可 以抢夺高权限任务已经占有的资源。本文在基于时间槽的资源能力管理的基础 上，提出了“资源抢夺”。并且，分析了资源抢可能出现的各种情况，针对其 中一种抢夺情况提出了启发式原则1 和启发式原则2 用以解决是否允许资源抢 夺。 任务调度：本文分析了多个调度算法发现，采用遗传算法比钔和模拟退火 技术的任务调度算法，不仅需要输入一些控制参数，而且算法的调度成本和时 间复杂度很高；采用树形结构描述任务关系的调度算法1 和实际复杂任务关系 想取甚远。本文主要研究了基于d a g 图描述任务关系的任务调度算法，并且重 新定义了d a g 图边的权值。当调度开始时，大多数调度算法n ，引根据当前获得的 网格资源信息，为任务分配合适的资源，并且立即执行此次分配结果，将任务 调度到资源上。但是，这时可能出现两种情况：第一，由于资源上已经积压了 很多任务还没有运行，资源需要很久才能为任务提供服务；第二，资源可以短 时间内为任务提供服务。网格动态性决定了网格中资源和资源的性能将随着时 间变化，如果出现第一种情况，由于任务在资源上开始运行时间与调度算法为 任务分配资源的时间距离较长，造成资源信息准确性降低，从而引发调度准确 性降低，即距离时间与准确性成反比，以及能力优秀的新资源加入并没有减小 作业执行的m a k e s p a n 。为了解决这一问题，本文根据任务调度开始时间( b t ) 将任务调度分为( 任务调度) 方案制定和( 任务调度) 方案执行两个阶段。针 对网格动态性，任务执行还需经过方案复审一步，防止方案陈旧造成调度不准 确。 网格模拟器：分析多个网格模拟器，考虑到f r e e b s d 操作系统和跨平台性 的前提下，选择澳大利亚墨尔本大学开发的模拟器g r id s i m h 6 5 引。实验时，为 了进一步测试算法在不同情况的效率，提出网格熵( g e ) 概念用以描述网格的 动态性。 1 5 本文主要工作及组织结构 本文工作主要分为以下四方面： 为了更加适应网格的动态性，将任务调度分为方案制定和方案执行两阶段， 提出了在方案执行前必须进行方案复审，进一步提高了调度的准确性，并且根据任 务的调度完成更新任务图。 分析了资源抢夺可能出现的各种情况，针对其中的一种抢夺情况，提出决定 是否允许资源抢夺的启发式原则。 比较分析了e t f 和c p a 等多种网格任务调度算法，提出了允许资源抢夺的基 于b t 的关键路径任务调度算法b t t s 。 比较分析了各种网格模拟器，并且为了更加准确的描述网格的动态性，提出 了网格熵( g e ) 的概念。以g r i d s i m 作为本算法模拟器进行实验分析，结果表明 b t t s 算法能较好地适应网格的动态性变化。 全文共分六章。 第一章绪论。介绍了本文所涉及课题的来源、目的和意义、国内外研究 概况、作者的研究内容以及本文主要工作和整个文章的章节安排。 第二章网格和网格任务调度。介绍了网格和网格计算、网格体系结构和 网格任务调度。 第三章网格的资源管理和抢夺。在介绍了网格资源管理模型和网格资源 能力管理相关知识后，提出了“资源抢夺”。 第四章基于b t 的网格任务调度。研究了基于d a g 图的任务调度的基础 上，将任务调度划分为方案制定和方案执行，并且讨论了任务调度对任务的影 响( 任务图消减) ，以及基于d a g 图的资源抢夺，最终提出了基于b t 的任务调 度算法思想。 第五章算法实现及结果分析。在介绍了多个算法仿真平台的基础上，选 择g r id s i m 作为本算法的仿真平台，实现了本算法，以及和多个算法的比较分 析。 第六章总结和展望，总结了本论文创新点，提出了下一步的研究方向。 第二章网格与网格任务调度 2 1 网格及网格计算 网格( g r i d ) 是一个集成的计算和资源环境，或者说是一种计算资源池。 网格能够充分吸纳各种计算资源，并将它们转化为一种随处可得的、可靠的、 标准的，同时还是经济的计算能力。除了各种类型的计算机，这里的计算资源 还包括网络通信能力、数据资料、仪器设备、甚至是人等各种相关的资源。 网格是借鉴电力网( e 1e c t r i cp o w e rg r id ) 的概念提出来的，其最终目 的是希望用户在使用网格计算能力时，就如同现在使用电力一样方便。在使用 电力时，不需要知道它是从哪个发电站输送出来，也不需知道该电力是通过什 么样的发电机产生，用户使用的是一种统一形式的“电能”。网格也希望给最 终的使用者提供的是与地理位置无关、与具体的计算设施无关的通用的计算能 力。因此，对于网格提供的计算能力有四个基本的要求：可靠性、标准化、易 访问性和价格低廉。 网格作为一种新出现的重要的基础性设施，和其它的系统相比，具有如下 一些特点： 分布性和共享性。网格分布性体现在网格资源是分布的。网格中涉及 的各种资源分布在地理位置互不相同的多个地方。因此需要解决资源和任务的 分配和调度问题。网格资源虽是分布的，却是可以充分共享的，共享是网格的 目的。 自相似性。网格的自相似性主要体现在网格局部往往在许多地方具有 全局的某些特征，而全局的特征在局部也有一定的体现。网格的自相似性在网 格的建造和研究过程中有重要的意义。 异构和多样性。网格的异构和多样性主要体现在网格资源的异构、多 样性以及动态变化等方面。因此网格资源管理必须充分考虑资源的增加、减 少，不同结构、不同类别资源之间的通信和互操作问题，才能解决网格的健壮 性、可扩展性以及可成长性问题。 自治性与管理的多重性。网格的自治性与管理的多重性主要体现指在 网格应该允许资源拥有者对他的资源有自主的管理能力，但是同时也必须接受 网格的统一管理，否则无法实现共享和互操作。 网格计算( g r i dc o m p u t i n g ) 是目前网络计算的一个具有重要创新思想和 巨大发展潜力的技术实践，其从最初希望能够将超级计算机连接成为一个可远 程控制的元计算机系统( m e t a c o m p u t e r s ) ，至试图提供种能够聚集网络上 的各种高性能计算机、服务器、p c 、信息系统、海量数据存储和处理系统、应 用模拟系统、仪器设备和信息获取设备等广泛分布的各种资源，进行大规模计 算和数据处理的通用基础支撑结构，为各种应用开发提供底层技术支撑， 将 i n t e r n e t 变成为一个功能强大、无处不在的计算设施。 网格计算是伴随着互联网技术而迅速发展起来的，专门针对复杂科学计算 的新型计算模式。这种计算模式是利用互联网把分散在不同地理位置的电脑组 织成一个“虚拟的超级计算机 ，其中每一台参与计算的计算机就是一个“节 点”，而整个计算是由成千上万个“节点”组成的“一张网格”，所以这种计 算方式叫网格计算。这样组织起来的“虚拟的超级计算机 有两个优势，一个 是数据处理能力超强；另一个是能充分利用网上的闲置处理能力。简单地讲， 网格是把整个网络整合成一台巨大的超级计算机，实现计算资源、存储资源、 数据资源、信息资源、知识资源、专家资源的全面共享。网格计算可以从三个 方面来理解。 从概念上，网格计算的目标是资源共享和分布协同工作。网格计算的 这种概念可以清晰地指导行业和企业中各个部门的资源进行行业或企业整体上 的统一规划、部署、整合和共享，而不仅仅是行业或大企业中的各个部门自己 规划、占有和使用资源，这种思想的沟通和认同对行业和企业是至关重要的， 它的实施是一个根本性的系统决策，将提升或改变整个系统的规划部署、运行 和管理机制。 网格计算是一种技术。为了达到多种类型的分布资源共享和协作，网 格计算技术必须解决多个层次的资源共享和合作技术，制定网格的标准，将 i n t e r n e t 从通讯和信息交互的平台提升为资源共享的平台。但是目前并行计 算、分布计算、中间件等现行技术研究目标和网格计算技术目标有较大的差 别，远远没有解决多组织之间资源的共享问题，以及广域范围的多系统之间联 合处理和计算等网格计算所面临的关键问题，因此，网格计算技术研究是具有 独特性、紧迫性和挑战性的。 网格是基础设施，是通过各种网络综合计算机、数据、设备和服务等 资源的基础设施；随着网格技术逐步成熟，建立地理分布的遍布全国或世界的 大型资源结点，集成网络上的多个资源，联合向全社会按需提供全方位的信息 服务。这种设施的建立，将使用户如同今天我们按需使用电力一样，无需再为 用户端配套大量的全套计算机系统和复杂软件，就可以简便地使用网格提供的 服务。由基础设施提供存储、计算的能力，有时称为u t i l i t yc o m p u t i n g ( 公 用计算) 。 2 2 网格体系结构 到目前为止，主流的网格体系结构主要有三个：第一个是伊安福斯特等 人在早些时候提出的五层沙漏结构 ( f i v e l e v e ls a n d g l a s s a r c h it e c t u r e ) ；第二个是在以i b m 为代表的工业界的影响下，考虑到w e b 技 术的发展与影响后，伊安福斯特等结合五层沙漏结构和w e bs e r v ic e 提出的 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 u s 联盟、i b m 和h p 于2 0 0 4 年初共同提出的w s r f ( w e bs e r v ic e r e s o u r c ef r a m e w o r k ，w e b 服务资源框架) ，w s r fv 1 2 规范已于2 0 0 6 年4 月 3 日被批准为o a s i s ( o r g a n iz a t i o nf o r t h ea d v a n c e m e n to fs t r u c t u r e d i n f o r m a t i o ns t a n d a r d s ，结构化信息标准促进组织) 标准。 2 2 1 五层沙漏结构 五层沙漏结构23 根据该结构中各组成部分与共享资源的距离，将对共享 资源进行操作、管理和使用的功能分散在五个不同的层次，由下至上分别为构 造层( f a b r i c ) 、连接层( c o n n e c t i v i t y ) 、资源层( r e s o u r c e ) 、汇聚层 ( c o lle c t i v e ) 和应用层( a p p lic a t i o n ) ，如图2 一l 所示。 构造层 构造层的基本功能就是控制局部的资源，包括查询机制( 发现资源的结构 和状态等信息) 、控制服务质量的资源管理能力等，并向上提供访问这些资源 的接口。构造层资源是非常广泛的，可以是计算资源、存储系统、目录、网络 资源以及传感器等等。构造层资源提供的功能越丰富，则构造层资源可以支持 的高级共享操作就越多，例如如果资源层支持提前预约功能，则很容易在高层 实现资源的协同调度服务，否则在高层实现这样的服务就会有较大的额外开 销。 连接层 连接层的基本功能就是实现相互的通信。它定义了核心的通信和认证协 议，用于网格的网络事务处理。通信协议允许在构造层资源之间交换数据，要 求包括传输、路由、命名等功能。在实际中这些协议大部分是从t c p i p 协议 栈中抽取出的。认证协议建立在通信服务之上，提供的功能包括：单一登录、 代理、与局部安全方法的集成、基于用户的信任机制。 资源层 资源层的主要功能就是实现对单个资源的共享。资源层定义的协议包括安 全初始化、监视、控制单个资源的共享操作、审计以及付费等。它忽略了全局 状态和跨越分布资源集合的原子操作。 汇聚层 汇聚层的主要功能是协调多种资源的共享。汇聚层协议与服务描述的是资 源的共性，包括目录服务、协同分配和调度以及代理服务、监控和诊断服务、 数据复制服务、网格支持下的编程系统、负载管理系统与协同分配工作框架、 软件发现服务、协作服务等。它们说明了不同资源集合之间是如何相互作用 的，但不涉及到资源的具体特征。 应用层 应用层是在虚拟组织环境中存在的。应用可以根据任一层次上定义的服务 来构造。每一层都定义了相应的协议， 括资源管理、数据存取、资源发现等。 以提供对相关服务的访问，这些服务包 在每一层，可以将a p i 定义为与执行特 定活动的服务交换协议信息的具体实现。 工具与应用 应用层 瓣 汇聚层 ， 1 资源与服务 资源层 的安全访阿 与连接层 夕 构造层 图2 - 1 沙漏形状的五层结构 2 2 2 开放式网格服务体系结构( o g s a ) o g s a ( 如图2 - 2 所示) 最基本的思想就是以“服务”为中心。在o g s a 框 架中，将一切抽象为服务，包括各种计算资源、存储资源、网络、程序、数据 库等等，简而言之，一切都是服务。这种观念，有利于通过统一的标准接口来