（计算机应用技术专业论文）基于复制与动态优先级网格任务调度算法研究.pdf

大连理工大学硕十学位论文 摘要 随着网格技术的深入研究与发展，地理上分布的异构资源可以通过高速互联网络连 接起来，构建成一个完整的计算平台，人们可以利用这些计算资源处理复杂的并行分布 式应用，而高效的网格任务调度则成为研究的热点和亟待解决的关键问题。 在网格任务调度中，通信延迟不仅会导致任务之间相互等待，而且还会造成处理器 结点空闲时间过多，是影响调度算法性能的一个至关重要的因素。除此之外，由于网格 是一个异构型的计算环境，相同的任务在不同的计算资源上的执行开销是不可能完全相 同的，随着调度过程的推进，任务结点的执行开销与通信开销都会变化，任务结点的权 值也会随之变动。然而，静态指定的任务优先级无法反应这种变化，导致指定的任务优 先级与实际优先级间存在误差。本文研究了网格环境下的静态任务调度策略，重点考虑 通信延迟与任务优先级对调度算法性能的影响。主要工作包括以下两个方面： 首先，结合表调度与基于复制的调度思想，提出了s t d h ( s e l e c t e dt a s k d u p l i c a t i o n f o rh e t e r o g e n e o u ss y s t e m ：异构环境下的选择性任务复制) 静态任务调度算法，通过冗 余调度前驱任务到处理器的空闲时间段来减少任务之间通信延迟。有利于保持任务的并 行性，提高处理器的利用率，从而缩短整个任务图的并行完成时间。实验结果表明了 s t d h 算法在减少通信延迟缩短任务完成时间方面的有效性。 其次，为确保每一步都能优先调度对整个任务完成时间影响最大的就绪任务，提出 一种采用动态任务优先级策略的任务调度算法，在任务调度过程中动态更新任务结点的 优先级，任务优先级计算过程与资源节点选取过程穿插进行，同时通过有效地利用处理 器的空闲时间来复制任务，以减少通信开销，从而缩短整个任务图的执行时间。大量实 验结果表明，本文算法优于h e f t 算法和基于动态决策路径的任务调度算法。 关键词：网格；任务调度；任务复制；动态任务优先级；调度长度 基于复制与动态优先级网格任务调度算法研究 d u p l i c a t i o na n dd y n a m i c p r i o r i t yb a s e ds c h e d u l i n ga l g o r i t h mi ng r i d c o m p u t i n gs y s t e m s a b s t r a c t w i t ht h ef l o u r i n go fg r i di nr e c e n ty e a r s ad i s t r i b u t e ds u i to fc o m p u t i n gm a c h i n e sw i t l l d i v e r s ec a p a b i l i t i e sc o n n e c tb yd i v e r s eh i g hs p e e dl i n k su t i l i z e dt oe x e c u t ep a r a l l e lp r o g r a m s h o w e v e r ，t h ep e r f o r m a n c eo ft h ep a r a l l e lp r o g r a me x e c u t i o ni ng d di sh i g h l yd e p e n d e n to n t h es c h e d u l i n go ft h ep a r a l l e lp r o g r a mt a s k so n t ot h e s em a c h i n e s i ng r i de n v i r o n m e n t ，t h ec o m m u n i c a t i o nd e l a yi sak e yi nd e g r a d i n gt h ep e r f o r m a n c eo f t h ep a r a l l e lp r o g r a me x e c u t i o n b u tl i s t b a s e ds c h e d u l i n ga l g o r i t h m sf a i lt oc o n s i d e rt h e c o m m u n i c a t i o nc o s t a n dac h i l dn o d ec a l l ts t a r tu n t i li t si m m e d i a t ep a r e n t sc o m p l e t ea n d s e n dt h em e s s a g et h ec h i l dt a s kn e e d 1 e a v i n gm a n yi d i et i m es l o t si nap r o c e s s o r i no r d e rt o d e a lw i t ht h i sp r o b l e m ，ag e n e r i cs c h e d u l i n gs t r a t e g y ，s t d h ( s e l e c t e dt a s k - d u p l i c a t i o nf o r h e t e r o g e n e o u ss y s t e m ) ，i sp r e s e n t e d ，w h i c hi m p r o v e st h ep e r f o r m a n c eo f l i s t - b a s e da l g o r i t h m 诚t ht h ed u p l i c a t i o n i ft h e r ei sap e r i o do fi d l et i m eo nt h ep r o c e s s o r ，s t d ha t t e m p t st oi n s e r t a l ls u i t a b l ei m m e d i a t ep a r e n tn o d e so ft h ec u r r e n ts e l e c t e dn o d e ，n o to n l yt h ec r i t i c a lp a r e n t ， s oa st or e d u c ei t sw a i t i n gt i m eo nt h ep r o c e s s o r ，w h i c hi sh e l p f u lt oa d v a n c i n gt h ee a r l i e s t s t a r t i n gt i m eo ft h i sc a n d i d a t et a s k o nt h eo n eh a n d t h ee a r l i e s ts t a r t i n gt i m eo fs o m et a s k s c o u l dm i n i m i z et h eo v e r a l lt i m eo ft h es c h e d u l i n g ，a n do nt h eo t h e rh a n d ，t h eu t i l i z a t i o no ft h e p r o c e s s o r sc o u l db er a i s e d t h ee x p e r i m e n t a lr e s u l t ss h o wt h a ts t d ho u t p e r f o r m sh e f ta n d h n d pi nt e r m so ff i n i s ht i m e b e s i d e s w h i l et h er a t i oo ft o t a lc o m m u n i c a t i o nc o s ta n dt o t a l c o m p u t a t i o nc o s to ft h et a s kg r a p hb e c o m e sl a r g e r ，s t d hb e c o m e s b e t t e rt h a nt h et w oo t h e r s t a k i n gi n t oa c c o u n tt h es y s t e mh e t e r o g e n e i t y ，t h es a m et a s kt a k ed i f f e r e n tr u nt i m eo n d i f f e r e n tp r o c e s s o r s ，t h ep r i o r i t yo fo n et a s km a yd y n a m i c a l l yc h a n g ei nt h es c h e d u l i n g p r o c e s sd u et ot h a tt h ep r o c e s s o rt oa s s i g nt h et a s kn o d ei sn o td e t e r m i n e d s os c h e d u l i n g s e q u e n c ed e t e r m i n es t a t i c a l l yi nt h el i s t i n gp h a s ei sn o tr e a s o n a b l eb e c a u s eo ft h es e q u e n c e c a nn o tc h a n g ei nt h es c h e d u l i n gp r o c e s s ，t h ep r i o r i t yc o m p u t e di nl i s t i n gp h a s em a yb e d i f f e r e n tf r o mt h er e a lp r i o r i t y i no r d e rt od e a lw i t ht h i sp r o b l e m t h ep r i o r i t yw a sd e t e r m i n e d d y n a m i c a l l yi nt h es c h e d u l i n gp r o c e s s ，i nt h i sw a y ，t h en o d e sw h i c hh a dt h eg r e a t e s ti n f l u e n c e t ot h es c h e d u l i n gl e n g t ho ft h et a s kg r a p hw o u l db es e l e c t e dt os c h e d u l ef i r s t i na d d i t i o n ，i f t h e r ew e r ei d i et i m es l o t si nt h ep r o c e s s o r s t h ep r e d e c e s s o r so fs e l e c t e dt a s k sw o u l db e d u p l i c a t e dt om i n i m i z et h ei n t r a p r o c e s s o rc o m m u n i c a t i o nc o s t t h ee x p e r i m e n t a lr e s u l t s i i 大连理工大学硕士学位论文 s h o wt h a tt h ea l g o r i t h mp r o p o s e di nt h i sp a p e ri sb e t t e rt h a nh e f ta n dd y n a m i cd e c i s i v e p a t ha l g o r i t h m k e yw o r d s ：g r i d ；t a s ks c h e d u l i n g ；t a s kd u p l i c a t i o n ；d y n a m i c p r i o r i t y ；s c h e d u l i n g l e n g t h h i ， 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：基王复剑当边查优先级圆整丝叠迥廑篡洼珏究 作者签名： 翻盥毛 日期：鲨! 年堕月j 日 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 茎查堕】兰丝叁丝弛墓趟丝堡兰至! 堕! 蜇缰丝复 日期： 日期： 年监月血日 年书一月以日 大连理工大学硕士学位论文 1绪论 1 1研究背景 传统的铁路、电话和电报、电力照明系统等基础设施给社会的发展带来了巨大社会 影响，没有这些基础设施，我们的生活是很难想象的。网格作为支持未来各类应用的新 的国家信息基础设施，也将像电网、铁路一样对人们的生活和工作方式产生巨大的影响。 任务调度问题是网格研究和应用必须解决的一个关键问题，直接影响网格系统的性 能。由于网格资源通常是分布式的，位于不同的地理位置，由不同的组织管理，加之计 算平台的异构型、资源结点的高度自治性、通信带宽不稳定及通信传输延迟大使得网格 环境中的任务调度成为一个非常复杂的问题，并进而成为网格计算的瓶颈问题之一。 因此，为了提高网格计算的性能，除了提高网格硬件设施的性能外，还必须提供一 个能够实现网格高性能的任务调度策略。 1 1 1 网格简介 网格的概念产生于2 0 世纪9 0 年代中期。它作为一种正在发展中的事物，有多种不 同的定义，其创始人i a nf o s t e r 和c a r lk e s s e l m a n 对网格的定义如下【1 1 ： 网格是一种新兴的基础设施，它将从根本上改变我们思考和使用计算机的方式。网 格这个词来源于可随时随地提供电能的电力网格，它向计算机和其他科技进步的产物一 样，对人类的能力和社会有着巨大的影响。人们相信通过使信息技术基础设施中的所有 成分，包括计算能力、数据库、传感器和人，灵活共享成为真正的协作工具，网格将会 有着类似的改造效果，导致新兴应用的出现。 网格是近年来兴起的新的技术研究热点，是继传统互联网、w e b 之后的第三次浪潮， 是第三代因特网应用。传统互联网实现了计算机系统的连通，w e b 实现了网页的连通， 而网格试图实现互联网上所有资源的全面连通，这些资源包括高速互联的异构计算机、 大型数据库、各种传感器、通信设备和超级计算机系统等。网格的目标就是将这些异构 计算资源重新整合成一台巨大的超级计算机系统，使得网格可以作为一个虚拟的整体使 用的地理上分散的异构计算资源，从而可以不必考虑地理、资源类型和操作系统之间的 差异，使总体性能真正超越各部分性能之和，来实现异构计算资源的全面共享和协同工 作。也就是说网格能够整合各种计算资源，并将他们转化为一种随处可得的、可靠的、 标准的同时还是经济的计算能力【2 】。 目前，网格技术已经成为一些国家研究与开发的竞争焦点，这主要表现在各个国家 大型网格研究项目不断启动。这些项目的目的在于为不同应用和研究团体创建网格、开 基于复制与动态优先级网格任务调度算法研究 发网格技术和技术框架。在国内，中国科技界已经向新一代互联网进军。从1 9 9 8 年国 家科技部的国家高技术研究发展计划( 8 6 3 ) 启动中国的“高性能计算环境”项目开始 至今，网格计算已经在中国发展了1 0 年。2 0 0 2 年“高性能计算机及其核心软件”重大 专项启动，本专项的实施，使我国在网格技术方面达到世界先进水平，大大提高了我国 的综合国力与国际竞争力；2 0 0 5 年国家自然科学基金启动了“以网络为基础的科学活动 环境研究”重大研究计划。在此基础上，2 0 0 7 年8 6 3 计划启动了“高效能计算机及网格 服务环境”重大项目；教育部通过的“c h i n ag r i d ”项目实力已经追上、甚至超越了某 些国外组织。在这些项目的资助下，我国的织女星网格、中国国家网格、上海网格、教 育网格等己经具有一定的知名度。 除此之外，美国已与2 0 0 5 年启动赛百基础架构( c y b e ri n f r a s t r u c t u r e ) 计划和t e r a g r i d ( d t f ) 二期计划。欧洲网格( e u r o p e a ng r i d ) 从网格基础设施、应用开发、基本 技术三个方面开展工作，其基本目标是建立一个为用户提供安全、简单、透明访问全欧 洲范围内的信息资源的平台，为欧洲的科学研究服务。另外，英国、法国、荷兰、日本 及韩国也都启动了国家网格计划，投入了大量研究资金，对网格的应用和发展都表现了 极大的兴趣。除政府外，i b m 、s u n 、h p 、p l a t f o r m 、m i c r o s o f t 、n e c 、n t i 等也都开 展了与网格计算相关的研究。 1 1 2 网格特点及应用 网格计算起源于科学计算中的分布式高性能计算，主要目的在于聚合基于因特网的 计算资源，解决大规模并行程序的计算问题。后来由于企业界的加入，网格计算逐步转 化为基于服务的计算。目前人们将计算网格( c o m p u t a t i o n a lg r i d ) 、信息网格( i n f o r m a t i o n g r i d ) 、数据网格( d a t ag r i d ) 、知识网格( k n o w l e d g eg r i d ) 以及p 2 p 计算、普适计 算( p e r v a s i v ec o m p u t i n g ) 等都归为网格计算范畴1 3 j 。 网格具有一些区别于其他计算系统的特性，下面将从几个方面来论述【9 】。 ( 1 ) 分布与共享 分布性是网格的一个最主要的特点。网格的分布性首先是指网格的资源是分布在各 地的计算能力不同的计算机、各种类型的数据库、电子图书馆以及其他的各种设备与资 源。这些设备和资源分布在地理位置不同的多个地方，而不是集中在一起的。这些资源 的类型复杂，规模较大，跨越的地理范围较广。这就决定了网格的计算定是分布式计 算而不是集中式计算。在网格这一分布式环境下，需要解决资源与任务的分配和调度问 题、安全传输与通信问题、实时性保障问题、人与系统以及人与人之间的交互问题等等。 网格资源虽然是分布的，但它们却是可以充分共享的。共享是网格的目的，没有共享便 大连理工大学硕士学位论文 没有网格。资源共享是网格的核心。分布是网格硬件在物理上的特征，而共享是在网格 软件支持下实现的逻辑上的特征，这两者对网格来说都是十分重要的。 ( 2 ) 动态性与异构性 网格并不是一成不变的。网格拥有的资源结点，在任何时刻都有可能会退出这个网 络或者出现故障，而原来没有的资源，可能随着时间的推移会不断加入进来。因此网格 的动态性表现在资源结点的动态增加和动态减少两个方面。除此之外网格资源是异构的 和多样的，它的异构型主要表现在两个方面：网络的异构型和结点的异构型。但是， t c p i p 的出现，使得采用不同技术的网络可以互联在一起，消除了网络的异构型。结点 的异构型是指网格环境中的资源可以是有不同体系结构、类别、配置以及软件系统，他 们的处理能力以及执行速度各不相同，因此网格系统必须能够解决这些不同结构、不同 类别资源之间的通信和互操作问题。 ( 3 )自相似性 网格的整体结构和局部之间存在着一定的相似性，局部往往在许多地方会表现出全 局的某些特征，而全局的特征在局部也有一定的体现。可以认为国家级网格是在省一级 的网格基础上建造起来的，国家级主干网要有更大的带宽，只有这样才能把不同省份的 子网格连接起来提供满意的通信服务，国家级和省级网格都会有各自的计算中心，只不 过在计算能力上有差异而已，他们也都需要有管理节点，只不过国家级的管理节点功能 更多更强大而已。 ( 4 ) 自治性与管理的多重性 网格的自治性主要表现在网格允许资源拥有者对他的资源有自主的管理能力，拥有 者对该资源拥有最高级别的管理权限。但是为了建立网格资源之间的相互联系，有效实 现共享和交互操作，网格资源也必须接受网格的统一管理，否则无法作为一个整体为更 多的用户提供服务。因此网格的管理具有多重性，一方面它允许网格资源拥有者对网格 资源具有自主性的管理，另一方面又要求网格资源接受网格的统一管理。 网格技术凭借其独特的计算力联合和分布式计算模式，在众多领域都拥有广泛的应 用前景，其应用领域归纳起来主要有以下几个方面【l o 】： ( 1 ) 分布式超级计算 分布式超级计算是指将分布在各地的超级计算机用高速互联网络连接起来，并通过 网格中间件整合在一起，形成比单台超级计算机强大得多的计算平台。在这个领域有两 个应用引人关注：第一个是军事仿真项目s fe x p r e s s ，它将大型军事仿真任务分解到各 个资源结点运行，在场景分发、资源配置、资源管理、信息服务、日志服务、监视和容 错等方面都利用了g l o b u st o o l k i t 的动态管理功能。第二个应用称作数字相对论，它利 基于复制与动态优先级网格任务调度算法研究 用网格求解爱因斯坦相对论方程并模拟出天体的运动规律。该项目使用了4 台超级计算 机，通过优化分布式计算的整体性能将运行效率由优化前的1 5 ，提升到了优化后的 6 3 。该项成就使得它在s c2 0 0 1 超级计算会议上获得了g o r d o nb e l l 奖。 ( 2 ) 分布式仪器系统 分布式仪器系统是指通过网格提供的功能远程访问分布在各地的贵重仪器系统，既 方便了用户的使用，又提高了仪器的利用率。在网格出现之前，软硬件环境及技术都不 够完善，人们只能通过网络访问一些仪器设备或仪器数据，实现一些低级应用，而网格 将分布式仪器系统变成了一个非常易于管理和有弹性的系统。 ( 3 ) 数据密集型计算 并行计算技术往往是由一些计算密集型应用推动着的，特别是一些带有重大挑战 ( g r a n dc h a l l e n g e ) 性质的应用，它们大大促进了对高性能并行体系结构、编程环境、 大规模可视化等领域的研究。但是，相比之下，数据密集型计算( d a t ai n t e n s i v e c o m p u t i n g ) 的应用好像要比计算密集型应用多得多。它对应的数据网格更侧重于数据 的存贮、传输和处理，而计算网格则更侧重于计算能力的提高，所以它们的侧重点和实 现技术是不同的。在这个领域独占鳌头的项目是欧洲原子能研究机构c e r n 所开展的数 据网格d a t ag r i d 项目。 ( 4 ) 远程沉浸 远程沉浸是一种特殊的网络化虚拟现实环境，通过对现实或者历史的逼真模拟，让 用户完全沉浸其中，在相同的虚拟空间沟通、交流，实现协同工作。这个环境既可以是 对高性能计算结果或数据库的可视化，也可以是个纯粹虚构的空间。远程沉浸可以广泛 应用于交互式科学可视化、教育、训练、艺术、娱乐、工业设计、信息可视化等许多领 域。目前，已经开发出几十个远程沉浸应用，包括：虚拟历史博物馆和协同学习环境等。 更重要的是，它将“人机交互”模式扩展成为“人机人协作”模式，不仅提供协同环境， 还将对数据库的实时访问、数据挖掘、高性能计算等集成了进来，为科技工作者提供了 一种崭新的协同研究模式。 ( 5 ) 信息集成 网格最早是作为异构计算平台出现的，接着进军分布式海量数据处理领域，自然而 然地在信息集成领域一展身手。所谓的信息网格，就是要通过统一的信息交换架构和大 量的中间件，向用户提供一种随手可得的服务。信息网格研究的中心问题有：如何描述 信息、存储信息、发布信息和查找信息；如何将异构平台、不同格式、不同表述方式的 信息进行转换，实现信息的无障碍交换；如何充分利用现有网络技术，如h t t p 、x m l 、 大连理工大学硕士学位论文 w s d l 、u d d i 、s o a p 等，构成一个完整的服务链；信息的语义表示，即如何赋予信息 以内涵，以及如何避免信息的二义性；如何对信息加密，防止信息泄露，等等。 不难看出，网格作为当今计算机科学领域的最新兴起的一项有很高学术价值和应用 价值的研究课题，正越来越广泛的应用于科学、工程和商业中。 1 2 研究现状 网格由大量分布共享的异构资源组成，这些资源协同提供了巨大的计算能力，随着 互联网的飞速发展，网格计算将成为解决复杂的并行分布式应用的必由之路。网格若想 实现资源共享，则有效的任务调度策略是网格研究中必须解决的一个问题，直接决定了 网格的性能。高效的任务调度策略和算法可以充分利用各种网格资源，提高网格应用程 序的性能。因此，引起了众多学者的关注，成为目前研究网格计算领域中的一个热点。 1 2 1网格任务调度概述 网格任务调度作为网格计算的关键技术之，长期以来得到了国内外研究者的广泛 重视，提出了多种调度算法，其中许多是由分布式算法发展而来的。但是由于网格计算 中资源在广域上分布、自主管理、本质上异构、负载动态变化等特征，使得网格环境下 的任务调度所面临的问题比传统分布式环境要复杂得多。因而，设计一种网格环境下的 高效合理的任务调度算法对促进网格计算的发展，提高网格计算的实用性具有十分重要 的意义。 网格任务调度算法按照不同的标准有很多种分类方法。根据任务调度策略产生的时 间，可以分为静态任务调度和动态任务调度。在整个任务执行之前，根据任务图所提供 的基本信息，可以计算出每个任务在各个处理器上的计算时间以及各个任务之间的数据 传输时间，同时采用非抢占式执行方式，称为静态调度；反之，称为动态调度。按照调 度算法产生的时间可以分为在线调度和离线调度。按照并行程序中各个任务之间的关 系，又可以分为独立任务和相关任务调度策略。独立任务调度来源于异构环境中的元任 务调度，独立任务调度在网格中应用的主要困难是资源的动态性和异构性。相关任务图 的调度策略一般用有向无环图( d a g ) ，这也是本文研究的重点，将在后面章节中给出 详细介绍。下面介绍几种具有代表性的算法： ( 1 ) 优先级调度：优先级调度策略是一种比较通用的策略。基于优先级的任务分 配与调度方法中，系统根据各种不同的参数为每个任务指派一个优先级，然后根据优先 级对任务进行排队，形成任务优先级队列，调度算法维护该任务优先级队列。在任务执 行过程中，一旦出现处理机空闲，则从任务队列中将准备就绪且具有最高优先级的任务 分配到该空闲处理机上去执行。这种方法中任务优先级的分配策略是关键。分配策略的 基于复制与动态优先级网格任务调度算法研究 好坏直接影响到分配与调度算法的效率。优先级策略经常与其他策略结合使用，例如 f i r s t f i t ，b a c k f i l l i n g 等等。 ( 2 ) 资源预留法【4 】：在f i r s t f i t 、b e s t f i t 、g r e e d y 等任务调度算法中，对资源需求 较大的任务长时间不能得到运行。为了避免这种问题，可以采取资源预留的策略，预留 该任务所需要的资源。也就是说，当一个任务在队列中等待的时间超过一个阈值时，只 要它所需要的资源有一部分处于可用状态，就不再把这些资源分配给其他任务，一直到 它所需要的所有资源都得到满足，才开始执行该任务。预留策略对于调度并行和串行混 合的任务队列非常有效。因为并行任务需要较多的处理机资源，它必须等到所需要的处 理机资源都空闲时才能运行。而此时空闲的处理机资源很容易被其他串行任务或需要资 源数目比较少的并行任务使用，使得需要资源数目较多的并行任务长时间得不到执行。 通过资源预留策略，就可以解决这个问题，但是它降低了系统资源的充分利用率，造成 了少量的资源空闲时间。 ( 3 ) 两阶段调度策吲5 】：在这种调度策略中，一个并行计算任务的计算范围会被 划分为l a n 内和l a n 间两个阶段，并在这两个阶段内设立全局的、集中的任务调度者， 以负责指定该阶段的任务调度方案和监控任务执行状况。因为两阶段任务调度策略在一 定程度上反映了网格的组成，所以为实施网络层次的其他调度算法提供一定的支持。但 是只将网格划分为两层是不准确的，所以两阶段调度策略还不能很好的描述网格的调 度，需要更深入的扩展。 ( 4 ) 基于市场供求关系的调度算法【6 】：模仿市场调控策略来对资源结点进行优化 组合。在这种调度算法中，每个资源结点都会被设定一个“价格”，该值由供需关系来 决定，即当供大于需，则价格会相应下调，相反价格会相应上升。当计算资源的价格被 设定后，对这些资源的分配过程就按照“先来先服务”的原则进行，统一地由调度者进 行调度。同一个计算资源的“价格”在实际的调度过程中可能会由于所选的策略和所处 的环境而不同，因此需要调度者进行策略级的全局优化。这种调度算法利用经济学理论 进行调度策略分析，为其他调度算法提供了一个新的思路。 1 2 2 网格任务调度的组织结构 网格任务调度中根据网格调度器的位置，可以将调度器的组织结构分为三种：集中 式调度、分布式调度及分层式调度。集中式调度是指网格中只有一个调度中心来负责网 格所有资源的调度。分布式调度是指网格环境中有多个调度中心，网格资源分为多个资 源集，每个资源集隶属不同的调度中心，各调度分中心只负责自己的资源调度。分层式 调度有中央调度者和本地调度者，中央调度者是本地调度者的上层。 大连理工大学硕十学位论文 ( 1 ) 集中式调度模式 在集中式调度环境中，一个中央机器扮演着资源管理者的角色，它将任务调度到其 它结点。这种调度模型适用于小型网格系统，因为在这种系统中，资源不是很庞大，调 度中心比较容易掌握所有的资源，能够产生高效的调度方案。 在这种调度模式中，首先将任务提交给中央调度器，调度器为该任务分配一个合适 的处理结点。那些不能在一个结点上启动的任务通常存放在中心任务队列中，以便随后 启动。集中式调度系统的优势之一是调度者能够给出更好的调度策略，因为它拥有关于 可用资源的所有必要的、最新的信息。然而，集中式调度显然不能与它所管理的不断增 长的环境匹配的很好。调度者本身可能成为一个瓶颈，必须保证其安全和可靠，以防止 单点失效，比如建立双调度器是解决单点失效的有效办法。 ( 2 ) 分布式调度模式 在分布式网络调度模型中，每个调度器仅维护本管理域的负载信息，没有中央调度 者负责管理所有的任务。一个调度者和其它调度者之间有两种通信方式：直接通信和间 接通信。分布式调度克服了集中式调度的可扩展性问题，而且它能够提供更好的容错能 力和可靠性。但是如果各个调度中心间的通信量比较大或者缺乏高效的吞吐时，不易于 管理和资源协同分配，为找到全局最优的资源分配方案增加了难度。 ( 3 ) 分层调度模式 分层调度实际上是分为两个阶段，外部调度和内部调度。外部调度是指，首先通过 网络资源信息服务寻找到当前满足任务需求的资源，然后通过某种策略从这些资源中选 择最佳的资源来执行任务。内部调度是指任务映射到本地服务资源以后，由服务资源本 地管理者予以调度。分层式调度模式就是指在外部调度采用集中式的调度，而在内部调 度中允许资源提供者使用自己的调度策略来进行任务调度。因此，这种模式是一种结合 式的方法。分层调度器易于实现扩展和容错，易于资源的协同分配，但不支持资源地域 自治和多种调度策略。 1 3 研究内容 任务调度策略是网格计算中一个至关重要的问题，其算法将直接影响到网格环境中 分布式应用任务的执行性能。用户通过向网格系统提交计算任务来共享网格资源，网格 调度程序再按照某种策略把这些任务分配给合适的资源。高效的调度算法可以充分利用 网格系统的处理能力，从而提高网格系统的性能。本文主要研究以性能为中心的任务调 度策略。主要包括以下几点： ( 1 ) 传统的任务调度算法在网格环境下的扩展 基于复制与动态优先级网格任务调度算法研究 当前网格任务调度的研究往往针对元任务或者批任务开展，忽视了任务之间的数据 关联与优先约束关系，不能反映网格任务的实际特征【7 1 。在并行处理领域中，通常以带 权值的d a g ( d i r e c t e da c y c l i cg r a p h ) 来表示有优先约束关系和数据关联的并行任务， 该任务图主要定义了各个任务之间的前驱后继关系和每个任务的执行开销。在早期的研 究中，它并没有包含每个任务之间的通信时间。除此之外，已有的很多典型调度算法仅 是考虑同构计算环境下的任务调度。而最近二十余年来，随着网络和处理器性能的迅速 提高，高性能计算领域进入了一个全新的阶段，并行调度不仅要考虑异构环境下任务之 间具有优先约束关系的情况还要考虑任务之间的通信代价，这些成果对于网格环境下的 任务调度具有重要借鉴意义。为此，本文引入并行处理领域的有向无环图d a g 来表示 网格任务，通过增加边的权值来表示任务之间的通信代价，增加任务执行时间矩阵来适 应网格环境的异构型，对传统的任务调度算法进行了扩展。 ( 2 ) 基于有限任务复制的d a g 图调度算法 当前，基于任务复制的调度已经成为研究热点，任务复制不仅能增强任务之间的并 行性，而且能够减少任务间的通信开销。一般来说，基于任务复制的调度绝对优于不是 基于任务复制的调度【8 】。但是由于传统的表调度模型没有考虑任务之间的通信代价，因 此造成了任务之间互相等待的现象及大量的处理器空闲时间段，不仅降低了任务之间的 并行性，而且降低了资源的利用率。本文针对处理器数目有限且处理器完全连接的异构 计算环境下的任务调度进行研究，结合了表调度与基于复制的调度思想。在任务调度过 程中，利用处理器的空闲时间，选择性复制能够提前当前任务开始执行时间的父任务， 减少任务之间通信延迟，使当前任务尽可能早的完成，以利于后续任务的及早调度，从 而缩短整个任务的并行完成时间。 ( 3 )网格环境下基于动态任务优先级的调度算法 基于优先级的任务分配与调度方法中，每个任务被指派一个优先级。在任务执行过 程中，一旦出现处理机空闲时，则从任务队列中将准备就绪且具有最高优先级的任务分 配到该空闲处理机上去执行。这种方法中任务优先级的分配策略是关键。分配策略的好 坏直接影响到分配与调度算法的效率。 在已有的静态任务调度策略中，大多数算法都是根据一定的分配策略，一次性为所 有任务指派优先级，在整个任务调度过程中不再变化。但是由于网格环境的异构性及任 务之间的通信代价使得随着任务调度过程的推进，任务的优先级也在不断发生变化，如 果依旧按照原来制定的任务优先级进行调度，则会影响到整个调度算法的效率。为此， 在本文中，任务优先级的计算与任务调度过程穿插进行，在整个调度过程中不断更新任 大连理工大学硕士学位论文 务的优先级，通过动态确定任务的优先级，精确定位当前对整个并行任务的完成时间影 响最深的就绪任务，有效缩短整个并行任务的完成时间。 1 4 文章的组织结构 论文主要分为绪论( 第一章) 、主体( 第二章到第五章) 、结论( 第六章) 、参考 文献、致谢及攻读硕士学位期间的主要研究成果等六个部分。 第一部分为绪论。本章介绍了本课题的研究背景，综述了网格及任务调度的研究现 状，介绍了本课题的主要内容及本论文的组织结构。 第二章深入分析了任务调度的特点、目标，综述了网格任务调度中一些基本概念和 技术，总结归纳了网格环境下的任务调度的相关理论和研究现状。 第三章为解决相关任务间存在的大量通信开销，提出了基于选择性复制前驱任务的 d a g 调度算法。 第四章主要研究一种基于动态任务优先级的任务调度算法，该算法在任务调度的过 程中，动态计算任务的优先级，有效缩短了任务调度的时间跨度。 第五章建立仿真环境进行性能分析，通过大量实验证明了本文算法在缩短并行任务 的时间跨度上的有效性。 第六章对本文工作的总结以及对未来研究工作的展望。 基于复制与动态优先级网格任务调度算法研究 2 网格环境下的任务调度研究 2 1任务调度的基本特点与主要目标 在网格系统中，任务调度策略是影响其系统性能的关键问题之一，它是根据用户提 交的任务信息采用适当的策略把不同的任务分配到相应的资源节点上去执行。为了最大 限度的提高系统资源利用率和减少任务调度的平均响应时间，必须采取有效的任务调度 策略，合理的分配子任务到各个工作结点上，保证总任务在最短的时间内完成，提高整 个网格系统的吞吐量。 2 1 1 任务调度的基本特点 网格调度的主要目的就是把任务与网格中所有可用资源进行匹配，找到最好最合理 的资源分配方式和资源调度策略，完成用户提交的任务，满足用户提出的要求。网格环 境下具有各种不同的应用，有信息计算方面的，也有高性能计算方面的，还有针对个性 消费的个性化应用需求，而且随着社会的发展，后者占的比例将越来越大。应用不同， 所侧重的目标也不同，因此网格的调度策略必须在传统分布式系统中的调度策略和技术 的基础上，充分结合网格的具体特征以及用户的需求，进一步增加网格调度的可行性。 具体的说，网格环境下任务调度系统具有以下几个特点【9 j ： ( 1 ) 任务调度是面向异构平台的。网格系统中的资源复杂多样，在规模最大的全 球性网络中，资源分布在全世界，包括各类主机、工作站甚至p c 机，它们是异构的， 可运行在u n i x 、w i n d o w s 等各种操作系统下，也可以是上述机型的机群系统、大型存 储设备、数据库或其他设备。由于资源的复杂多样，不同的资源会展示出不同的性能特 征，而且相同类型的资源由于共享等原因所展示的性能也会随时间而变化，因此网格系 统中的任务调度必须面向异构平台，需要建立随时间变化的性能预测模型，充分利用网 格的动态信息来表示网格性能的波动，并在这些平台上实现网格任务的调度。 ( 2 ) 任务调度是大规模的、非集中式的。由于网格系统其资源跨越多个管理域， 规模庞大，要实现一种全局的统集中的任务调度管理是根本不可能的。因此，网格系 统中的任务调度必须以分布、并行方式进行任务的管理与调度。 ( 3 ) 任务调度不干涉网格结点内部的调度策略。由于网格资源首先是属于资源的 拥有者，有自己本地的管理机构或处在本地管理机构的管理之下，具有本地自治能力。 网格资源中，除了一部分专用的网格资源是专门提供给网格用户使用的之外，大部分资 源都是资源拥有者自己使用的本地资源和作为网格用户可以使用的网格资源。网格调度 大连理工大学硕士学位论文 系统必须尊重本地管理策略，合理使用资源，不能损害资源拥有者和本地用户的利益。 因此在网格任务调度中，任务调度系统不应干预其结点内部的调度策略。 ( 4 ) 网格中要达到的调度目标很多，包括性能方面和经济方面，比如调度跨度最 短、可靠性最高、资源利用率最高、负载均衡等等，这些目标对各种资源的约束很多， 有些还相互矛盾，对于这种多目标多约束的问题找到满足所有约束和目标的全局最优解 是很困难的。 ( 5 ) 任务调度必须具有可扩展性。网格系统初期的计算规模较小，随着资源结点 的不断加入，系统的计算规模也必将随之扩大。因此，在网格系统资源规模不断扩大、 应用不断增长的情况下，网格系统的任务调度必须具有可扩展性，不会因应用规模的扩 大而导致网格系统性能的降低。 ( 6 ) 任务调度能够动态自适应。网格中的资源不但是异构的而且网格中的结构总 是不停地改变。随着时间的推移，有的资源结点因为出现故障而退出网络，有的新资源 要加入到网格中，有些资源重新开始工作等。网格资源的可使用性是随时间的变化而动 态变化的，一个网格资源的执行能力也会随时间的变化及自身的负载情况而动态变化。 总之网格的动态性是明显的，所以任务调度系统必须适应网格的这种动态性，重视网格 任务之间数据关联与优先约束关系、网格资源的动态变化、网格任务的q o s 需求等问题， 从可利用的资源中选取最佳资源为用户提供应用服务。 ( 7 ) 网格环境下的任务调度还必须考虑资源提供者与使用者之间所涉及到的经济 利益等因素。网格任务调度必须考虑到怎样协调网格用户和具体资源提供者之间的利 益，也就是使得用户所需要支付的开销最小且资源提供者获得的利益最大。 2 1 2 任务调度的主要目标 在网格系统中任务调度系统是其重要的组成部分，也是影响其性能的关键因素。用 户提交的并行分布式应用会依据一定的原则划分为具有约束关系的各个子任务，任务调 度系统将各个子任务依据一定的原则分配到相应的资源结点，努力实现最优调度。简单 的说，任务调度目标就是对用户提交的任务实现最优调度，并设法提高网格系统的总体 吞吐率。主要可分为以性能为中心的任务调度策略和以经济目标为中心的任务调度策 略，前者主要包括：最优跨度( o p t i m a lm a k e s p a n ) 、服务质量q o s ( q u a l i t yo f s e r v i c e ) 和负载均衡( l o a db a l a n c i n g ) 等u o ，l 。 ( 1 ) 最优跨度 跨度是任务调度最常见、最主要的调度目标。它指的是完成一个用户的所有任务所 需要的时间，也就是说从执行第一个任务开始，到所有任务执行完成所花的时间的总和。 基于复制与动态优先级网格任务调度算法研究 对于网格环境下的任务调度来说，最主要的目的就是将用户提交的并行应用快速、正确 的执行并计算出结果，时间跨度的长短，直接反映了任务调度策略的性能。因此，时间 跨度越短，证明该调度算法越好。从节约时间、充分利用资源的角度来考虑，以最优跨 度为目标是大多数资源拥有者和用户的共同目标。在这一目标中包括两部分，一是任务 的执行时间，二是结点之间的通信时间。在任务调度过程中，要尽量减少这两部分时间。 一个用户所有任务的完成时间就是衡量相应网格任务调度算法性