（通信与信息系统专业论文）网格环境下minmin调度算法改进与实现.pdf

武汉理工大学硕士学位论文 摘要 网络的高速发展，使得分散的、异构的计算资源有机地结合到一起，并且 使其形成一个巨大的网格成为可能。相应的，网格中的作业调度也渐渐成为一 个重要的问题。作业调度算法的研究，直接关系到网格环境中调度的速度和质 量，在网格计算技术的研究中，起着举足轻重的作用。 作为启发式算法中的经典算法，m i n m i n 算法总是先执行具有最短完成时间 的作业，有着算法思路简单、总完成时间短的特点，是网格作业调度算法研究 中倍受关注的一个算法。但是现有的网格系统大多是为了一些学术研究目的而 开发的，在这些系统中强调资源的共享和协同工作，却没有考虑到资源的价格 因素。在实际应用中，大量的资源并不是无偿使用的。在这种情况下，m i n m i n 算法已经不能满足调度的需求了，需要在算法中将资源费用的要求考虑进去。 基于此，本文主要的研究工作包括： + 在了解网格作业调度目标、网格作业调度算法和作业调度算法模拟器的基 础上，对m i n m i n 算法进行了改进研究。一是把m i n m i n 算法的最短完成时间 概念扩大，使其完成总花费最小，花费中既包括任务完成时间，也包括任务在 c p u 上的运行费用；二是定义性价比函数，将m i n m i n 算法中的“将各个任务 分配到完成它时间最短的机器上”改为“将各个任务分配到完成它性价比最高 的机器上 。 用程序模拟m i n m i n 算法、q o sg u i d e dm i n m i n 算法及改进后的两种算法， 通过几组对比实验，对这四种算法从多角度进行分析和比较。证明改进后的 m i l l 一m i n 算法比其他两种算法拥有更少的总花费，同时网格负载更加均衡，更加 适用于网格环境。 关键词：网格，作业调度，m i n m i n 算法，总花费，算法模拟 武汉理工大学硕士学位论文 a b s t r a c t t h er a p i dd e v e l o p i n gn e t w o r km a k e si tp o s s i b l et oi n t e g r a t et h eg e o g r a p h i c a l l y d 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 ot r e m e n d o u sg r i d s ot h e t a s k ss c h e d u l i n gi ng r i dh a sb e c o m ea ni m p o r t a n tp r o b l e m a n dt h er e s e a r c ho f s c h e d u l ea l g o r i t h m s ，w h i c hd i r e c t l yr e l a t e dt ot h es p e e da n d q u a l i t y , p l a y sad e c i s i v e r o l ei nt h er e s e a r c ho fc o m p u t i n gg r i d m i n - m i n a l g o r i t h m ，ac l a s s i c sa l g o r i t h mi nh e u r i s t i ca l g o r i t h m ，w h i c ha l w a y s c o m p l e t e st h es h o r t e s tt o t a lc o m p l e t i o nt i m et a s kf i r s t ，h a st h ec h a r a c t e r i s t i co f s i m p l e a n ds h o r t e s tc o m p l e t i o nt i m e s oi tc a t c h e sal o to fc l o s ea t t e n t i o n si nt h ef i e l d o f s t u d y i n gf o rt a s k ss c h e d u l i n ga l g o r i t h m si ng r i d b u tm o s to ft h ee x i s t i n gg r i d s y s t e m sa r ed e v e l o p e df o r t h ep u r p o s eo fl e a m i n gr e s e a r c h ，t h e s es y s t e m se m p h a s i z e t h es h a r ea n dc o o p e r a t ew o r kw i t hr e s o u r c e s ，t h ep r i c eo fr e s o u r c ei sn o tc o n s i d e r e d m o s to ft h er e s o u r c e sa r en o tv o l u n t e e ri nt h ea c t u a la p p l i c a t i o n i nr e s u l to ft h e p r o b l e mm e n t i o n e dj u s tn o w , t h em i n - m i na l g o r i t h ma l r e a d yc a nn o ts a t i s f yt h en e e d f o rs c h e d u l i n g s ow es h o u l dc o n s i d e rn e wa l g o r i t h m st h a tt a k et h et a s k s d e m a n d s f o rp r i c eo fr e s o u r c e si na c c o u n t b a s e do nt h i s ，t h i sp a p e rf o c u s e so nt h ef o l l o w i n gr e s e a r c h e s ： a f t e rw ek n o wt h er e s e a r c hs t a t u sf o rt a s ks c h e d u l i n go b j e c t s ，a l g o r i t h m s ，a n d s i m u l a t o r s o ft a s ks c h e d u l i n ga l g o r i t h m s ，t h e nm o d i f yt h em i n m i na l g o r i t h m f i r s t l y , w ee x p a n d st h ec o n c e p to fs h o r t e s tf i n i s ht i m ei nm i n - m i n a l g o r i t h m s ，a n dm a k e st h e j o bf i n i s ha tt h el e a s tc o s t ，w h i c hn o to n l yi n c l u d ec o m p l e t i o nt i m eb u ta l s ot h e e x p e n s e so fc p u s e c o n d l y , w ed e f i n ep e r f o r m a n c ep r i c er a t i of u n c t i o n ，t h e nw ec a n c h a n g e d i s t r i b u t ee v e r yj o b st ot h ec o m p u t e r sw h i c hf i n i s ht h e mi nt h es h o r t e s tt i m e i nm i n m i na l g o r i t h mt o “d i s t r i b u t ee v e r y j o b st ot h ec o m p u t e r sw h i c hf i n i s ht h e mi n t h eb e s tp e r f o r m a n c ep r i c er a t i o ” w es i m u l a t em i n - m i na l g o r i t h m 、q o sg u i d e dm i n - m i na l g o r i t h ma n dt h et w o m o d i f i e da l g o r i t h m si np r o g r a m a n a l y z e sa n dc o m p a r e st h ea b o v ef o u ra l g o r i t h m s f r o mm u f t i a s p e c t st h r o u g hs e v e r a ls e t so fc o n t r a s t i n ge x p e r i m e n t s a tl a s t ，i ti s i i 武汉理工大学硕士学位论文 p r o v e dt h a tt h em o d i f i e dm i n m i na l g o r i t h mh a ss h o r t e rt o t a lc o s tt h a nt h eo t h e rt w o a l g o r i t h m s ，a tt h es a m et i m e ，t h eg r i dr e s o u r c e sa lem o r eb a l a n c e d s ow ec a n c o n c l u d et h e yf i tf o rt h eg r i de n v i r o n m e n tb e t t e rt h a nt h eo t h e rt w oa l g o r i t h m s k e y w o r d s ：g r i d ，t a s ks c h e d u l i n g ，m i n - m i na l g o r i t h m ，t o t a lc o s t ， a l g o r i t h ms i m u l a t i n g i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 签名：迸i i 氢日期：2 竺壁：13 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保 留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：拯i i 垂3导师签名：日期：咝j7 武汉理工大学硕士学位论文 第1 章绪论 随着互联网技术的迅速发展和应用，以及对广域分布的资源之间的共享和 协同需求的增加，单台高性能计算机已经不能胜任一些大规模应用问题的解决。 这就需要将地理上分布、系统上异构的多种计算资源通过高速网络连接起来， 共同解决大型应用问题【1 1 ，这就是网格技术【2 捌。 一个简单的网格模型主要有网格用户，资源管理中心，网格资源三类实体。 网格用户是资源的消费者，网格资源是资源的提供者，而资源管理中心的功能 是如何把网格用户提交的作业合理地配置到网格资源上，如图1 1 所示。资源 管理中心具有调度功能。由于作业是由一些具有不可分解性的任务组成，因此 资源管理中心的主要功能是如何把作业中的任务合理有效地映射到资源上，并 使得性能最优【4 】。针对不同的目标，人们设计了各种资源管理系统。而一个好的 管理系统，最重要的就是有好的算法来调度用户递交的任务，以达到合理而经 济地利用资源的目的p ，6 j 。 网格用户 资源管理中心 二囿囡 网格资源 图1 1 简单网格模型 由于在科学计算中，并行程序总是由若干个并行的任务组成，网格计算的 资源管理系统就要为这个程序的各个任务分配计算资源，将任务恰当地指派给 各个计算机来完成。调度算法的好坏，直接影响一个程序的运行时间和所耗费 用。现在多数调度算法处理的问题均假定用户递交的各个任务是独立的，即它 们之间既没有拓扑排序关系，也不存在通讯。虽然在很多科学计算的并行程序 中，各个任务之间经常发生通讯以交换中间信息，但在“相互独立 的假定下， 喧回 刁豳阂阂阴矽仁画雕_ 武汉理工大学硕士学位论文 上述调度算法仍可以应用于很多科学计算问题，例如定积分、蒙特卡罗模拟、 生物上的d n a 等。所以，研究相互独立的任务调度有很大价值。当然，涉及通 讯的任务调度的研究较少的另一个原因是，当各个任务不独立时，通讯中的相 互等待、任务的拓扑序关系等将为我们带来很多复杂的、难以处理的情况，以 至很难有较好的解决方法1 7 j 。 由于网格的异构性，其资源可能被不同的个人或者组织拥有，从而具有不 同的管理策略、访问成本以及动态变化的性能。n i m r o d g 系统，是利用经济模 型【8 - 1 1 1 ，来管理任务的调度，其中任务的执行费用也作为是一个很重要q o s 参数 而被考虑进来。n i m r o d - g 系统的主要目的就是在保证用户需求得到满足的条件 下为用户提供最经济的计算模式。n i m r o d g 有两个最重要的q o s 参数，分别是 任务的执行时间和执行费用。该系统中为任务的调度提供了一套调度策略 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 t l l 】，这套策略中主要包括3 个调度算法：时间优 化算法，费用优化算法，费用时间优化算法，用户可以按照自己的需求选择合 适的策略进行调度。 因此，原m i n m i n 经典调度算法可以说是上述调度策略中的时间优化算法， 并未考虑费用因素。本文在m i n m i n 调度算法上运用经济学原理来对相互独立 的任务调度进行改进。在本文的模型中，将根据用户对运行时间和执行费用约 束的要求分配最优的调度方案，这里的“最优 兼顾了任务所耗的时间和c p u 费用。用户对调度最终完成的时间和费用存在某个边界要求，本文对m i n m i n 算法的改进要使任务在用户规定的时间内完成，并且所耗费用不能超过用户的 最大预算。总之，本文的算法要把用户提交的各个任务指派到合适的计算机上 运行，以达到耗时和费用兼顾的最优，也可以定义为性价比最优，这种调度策 略与现实生活中的商品经济模型类似，必将有助于该算法在计算网格调度中的 应用。 1 1 项目来源 本课题来源于国家自然科学基金国际合作与交流项目“以网络为基础的数 字制造环境的新理论和新技术研究( 5 0 6 2 0 1 3 0 4 4 1 ) 。本项目的目标是利用网 络技术将地理上位置不同的制造设施、计算与存储设备、控制与检测仪器仪表 等集成在一起，建立面向网络制造服务的通用基础支撑环境，实现i n t e r n e t 上 2 武汉理工大学硕士学位论文 产品全生命周期的制造资源、设计资源和服务资源的有效聚合和广泛共享，从 而建立一个能够实现设计区域或全球合作和协作的虚拟制造科研和实验环境， 支持以区域网络制造和全球网络制造为特征的数字制造活动。 1 2 本课题的研究背景、目的及意义 目前，已有许多科研组织对网格任务调度进行了研究，其中包括将传统的 分布式计算中的任务调度算法应用到网格计算中来，常用的调度算法包括 m i n m i n 算法、m a x m i n 算法、s u f f e r a g e 算法【1 2 】、x s u f f e r a g e 算法【1 3 】、贪婪算 法、遗传算法、蚂蚁算法等。网格中几个常用的调度模型有c o n d o r - g 1 4 】，a p p l e 1 5 j 和n i m r o d g 【1 6 1 。 不管是一个商品公共网格还是一个计算网格，网格的关键价值常常是依据 它在业务上的优点和用户各自的满意程度来衡量的。其中，用户的满意程度是 根据网格提供的服务质量来衡量的，而运行时间( m a k e s p a n ) 和所耗费用( c o s t ) 又是决定网格服务质量的主要因素。以往的调度算法，只是考虑到任务的执行 时间、通常没有考虑到调度中的价格因素。 网格中的资源属于不同的机构和个人，分布在世界各地，因此需要一个性 能较好的管理系统。用户不需要知道这些资源在哪里，更不需要知道如何去选 择哪些资源来完成他们的任务一这些工作应该由管理系统完成。资源管理系统的 核心是合理而有效的将用户提交的任务映射到合适的资源上，这就需要有好的 算法来调度用户递交的任务，以达到合理而经济地利用资源的目的。 当一个用户递交了拟运行的任务之后，网格计算的资源管理系统( 网格调 度器g s ) 就要为这个任务寻找计算资源，恰当地指派给各个计算资源站点来完 成，任务的调度模型如图1 2 所示。调度算法的好坏，直接影响一个程序的运 行时间( m a k e s p a n ) 和所耗费用( c o s t ) 。迄今为止己存在很多网格任务调度算 法，但是大量的算法和协议都假定参加者被动地执行事先设计的算法，而不存 在自己的个人意愿。然而，对于基于i n t e m e t 的网格计算平台，该假设在很大程 度上不成立。参加者都是具有理性的自由个体，追求自己利益的最大化，因而 认为所有的参与者都尽力实现自己的利益更为合理。 武汉理工大学硕士学位论文 篓萎h 任器愕搿卜繁源i 鬻器 网格调度器g s 计算资源站 点( 本地调度 器) 计算资源站 点( 本地调度 器) 图1 2 任务调度模型 随着网格计算的发展，现在多数情况下用户递交的均为含q o s 要求的任务。 因此本文介绍的是一种含q o s ( 服务质量，q u a l i t yo fs e r v i c e s ) 要求的调度独立 任务的算法。例如用户要求一些任务要在特定时间内完成，及各任务的总费用 不能超过预算上限。针对这一点，本文将提出一个基于性价比的m i n m i n 任务 调度算法，该算法综合考虑了时间和费用两个因素，从用户的角度出发，以任 务调度的剩余完成时间与执行费用的比值作为性价比，以该性价比作为启发信 息对任务进行分配，并通过实验验证了该算法的有效性。 本文提出的m i n m i n 改进算法就是在该背景下提出的，旨在探索一种能够 很好的协调各方利益的网格任务调度策略。通过对这一课题的实施，对计算网 格环境下m i n m i n 基本调度算法进行了分析，同时提出了一个基于性价比的 m i n m i n 网格任务调度算法，根据用户的q o s 要求为其提供合理有效的调度。 笔者认为本课题的确立和完成将在网格调度领域做出一些有益的探索。 1 3 网格调度算法研究现状 高效的任务调度算法可以提高整个网格的计算效率，因此作为网格关键技 术之一的任务调度算法，历来都受到国内外网格研究者的重视和关注。在众多 的任务调度算法中，以下几种算法思路比较新颖并且具有较高的参考价值【3 9 1 。 ( 1 ) 两阶段( 2 p h a s e ) 调度策略1 4 0 j ：将一个计算任务的计算范围依次划分 为l a n 间和l a n 内两个阶段，并分别在l a n 间阶段和l a n 内阶段设立全局的、 集中的任务调度者，以负责制定该阶段的任务调度方案和监督任务执行情况。 2 - p h a s e 式的调度策略，的确在某种程度上反映了网格的网络组成，也为实施网 络层次的其他调度算法提供一定的支持。但是，由于仅用涉及l a n 的两层结构 4 武汉理工大学硕士学位论文 来刻画计算网格是不准确的，所以，2 - p h a s e 调度策略还不能很好地描述网格的 调度，需要更深入的扩展。 ( 2 ) 基于优先级和b e s tf i t 机制的c o r s p b ，c o r s b f ，c o r s b f r 调度 算法【4 l 】，首先提出了“联合预留”( c o r e s e r v a t i o n ) 的思想，即当计算请求被 提出时，应用和网格系统之间将签订一个资源预留协议，只有当q o s 的要求发 生冲突时，调度者才会检查计算请求，同时如果在整个计算请求中有一个需要 的资源不可得，那么整个计算请求将被全部抛弃。在此思想上，该算法提出了 “基于优先级利益的联合预留调度算法( c o r s p b ) 、“基于尽力服务的联合 预留调度算法”( c o r s b f ) 和“基于尽力和优先级的联合预留调度算法 ( c o r s b f r ) ”。其中，c o r s p b 具有较高总体调度效益，c o r s b f 具有较低 的请求拒绝量，而c o r s b f r 则是上述二者的折衷。 ( 3 ) 基于市场供求关系的调度算法【4 2 】：仿照日用品买卖市场调控策略来对 计算资源进行优化组合。具体的，计算资源的“价格”被设定为介于资源的需 求和提供之间，当计算资源的“价格 确定后，对它们的分配过程就按照“先 来先服务 的原则进行，统一地由调度者进行调度。对于同一个计算资源，在 实际的调度过程中可能会由于所选的策略和所处的环境不同而被标上不同的 “价格”，因而需要调度者进行策略级的全局优化。基于市场供求关系的调度算 法利用经济学理论进行调度策略的分析，为其他调度算法提供了新颖的思路。 由于在网格调度过程中网格资源映射到本地资源后，将由本地服务资源管 理者进行调度，而且允许本地资源管理者使用自己的调度策略。因此，就需要 一个高效的、可靠的调度算法对已经映射到本地的任务进行调度。 首先介绍调度算法中常见的n p 问题： 对于任务调度，除少数小规模问题存在p 算法外，大量调度问题属于n p 问 题，国际数学界研究n p 问题的历史开始于2 0 世纪7 0 年代。1 9 7 1 年，c o o l 找 到了第一个n p 完全问题，寻求标准布尔方程解的问题( s 问题) ，开创了n p 完 全问题研究的历史。到目前为止，大约有几千个问题己被证明是n p 完全问题。 在网格计算中，当网格中有n 个任务和能够满足n 个任务的m 个资源时， 运用一个合适的任务调度策略可以在n 个任务和m 个资源之间进行匹配，使得 总任务的完成时间最小以及资源得到充分利用。定义f i 为任务i 的最后完成时 间( 即后面提到的f t ( v ，p ) ) ，定义跨度为f m a x = m a x f i ，i = l ，n ) ，则调度任 务就是在2 m 个可能的资源子集空间中寻找最优集合使得跨度f m a x 和f i 最小。 武汉理工大学硕士学位论文 网格作业调度算法本身就是一个n p 难问题，围绕作业调度算法，国内外都 做了大量的研究，提出了一些比较成熟的调度算法【3 3 1 ，如下所示： ( 1 ) 模拟退火算法 模拟退火算法是广泛使用的解决组合优化问题的算法之一。它模拟机械工 业上的金属冷却过程，它的最大优点是能避免问题的解落入局部最小。模拟退 火算法采用循环搜索来寻找问题的优化解，循环刚开始时，算法以一定的可能 性接受相对较差的解决方案以获得有可能更好的问题解搜索空间。随着算法的 不断进行，较差的解决方案被接受的可能性越来越小，最后输出的是较好的解 决方案。 ( 2 ) 禁忌搜索算法 这是一种循环搜索技术，但它在问题的解空间里记录了已经搜索过的空间 以避免重复搜索临近区域。对于每个解决方案s x ，s 是s 的一个可能的小 的改动，例如其中两个任务相互交换，他们组成了s 的邻居。在这些邻居中，算 法求解局部最优问题，然后这个局部最优问题搜索的映射被加入到一个t a b o o 列表中，t a b o o 列表记录了已经搜索过的空间。算法重新产生一个映射，如果这 个映射和t a b o o 列表中的元素基本相同，这个映射就被称为是禁忌的，算法将会 重新选择映射。 ( 3 ) a 木算法 a 幸算法在许多任务分配问题都有应用。它是一种启发树式搜索算法，根结 点是一个空结点，而中间的结点是部分的解决方案。它在广度有限搜索的基础 上增加了一个函数f ( x ) = g ( x ) + h ( x ) ，其中g ( x ) 是达到某个状态时 已经花费的开销，h ( x ) 是一个构造函数，表示从该状态开始到达目的状态的 开销的估计值，从而加快了搜索速度。 ( 4 ) g a ( t h eg e n e t i ca l g o r i t h m ) ：遗传算法是用来寻找比较大的解决方 案的一个算法，它是对已给问题的染色体进行操作，而最初的染色体是随机产 生的一个染色体可以由任何一个算法产生，当它由m i n m i i l 算法产生，它就被 称之为以m i l l m i n “播种”。 ( 5 ) m i n m i n ：在该算法中，先要算出每一个作业在每个机器上的最短完 成时间。所有作业中，拥有最小完成时间的作业将被选出来，分配到对应的机 器执行，将这个作业删除，重复上述工作，直至所有作业都被分配。 ( 6 ) m a x m i n - m a x m i n 算法与m i n m i n 算法类似，还是要先算出每一个 6 武汉理工大学硕士学位论文 作业在每个机器上的最短完成时间。在所有作业中，拥有最大完成时间的作业 将被选出来，分配到对应的机器执行，将这个作业删除，重复上述工作，直至 所有作业都被分配。 在第4 至第6 个算法中，m i n m i n 算法是最快的算法，g a 算法比m i n m i n 要慢，a + 是最慢的。对一个1 6 个资源，5 1 2 个作业的网格环境，m i n m i n 算法 的执行时间差不多是l s ，g a 算法的执行时间是3 0 s ，而斛算法的执行时间要 1 2 0 0 s 。 m i n m i n 算法是一个简单、快速的算法，并且性能比较好。g a 算法使用 m i n - m i n 算法来播种染色体，也是因为它有比较好的性能。m i n m i n 算法的缺点 是只考虑到完成时间方面的要求，在算法目标的其它方面几乎没有考虑，因此 这种算法只是在理论情况下是比较好的，对于执行时间长的大任务就无法保证 服务质量。因为大任务通常由于算法的关系被排到最后完成，这样就不适合在 网格的环境下进行任务调度。这种算法只是在理论情况下是比较好的。在文献 3 4 】 中，考虑到q o s ( 主要指带宽) 的情况下，算法显然不能合理地安排作业的调 度，因此在文献 3 4 3 中提出了q o sg u i d e dm i n m i n 算法，在网格作业调度过程 中，引入了q o s 这个评判标准，使得在考虑算法m a k e s p a n 的同时，也要兼顾到 带宽( o o s 的一个方面) 的影响。但是文献 3 4 】中考虑的q o s 单指带宽这一方面， 本文在此基础之上，扩展了原算法对q o s 的要求，从费用的角度将原算法进行 评估，使得该改进算法更加适用于实际的网格环境。实验结果表明，优化后的 算法的性能在考虑到费用约束时比m i n m i n 算法及q o sg u i d e dm i n m i n 性能有 很大提高，负载更加均衡，更加适用于实际的网格环境。 1 4 本论文主要研究内容与结构安排 1 4 1 本文主要研究内容 本文从理论和实践方面对网格环境下m i n m i n 作业调度算法进行了较为深 入的研究。论文的主要工作如下： ( 1 ) 了解网格环境下作业调度的相关概念，并且分析了主要的作业调度算 法和作业调度目标，研究了启发式和经济模型两种算法，并对网格环境下作业 调度算法的模拟器进行了分析和比较。 7 武汉理工大学硕士学位论文 ( 2 ) 对网格作业调度算法的经典算法m i n m i n 算法进行了研究，重点分析 了h ex i a o s h a n 提出的q o sg u i d e dm i n m i n 算法，指出了m i n m i n 和q o s g u i d e dm i n m i n 算法的不足。在此基础之上对m i n m i n 算法进行改进。 ( 3 ) 基于m i n m i n 算法的改进思想，使用j a v a 语言对m i n m i n 算法、q o s g u i d e dm i n m i n 算法和改进后的m i n m i n 算法进行模拟。从不同任务数量和资 源数量两个方面对上述四种算法进行评估。验证了改进后算法的可行性及优越 性。 1 4 2 本文结构安排 全文共分为5 章： 第1 章对本课题的提出和选题背景与研究意义进行了阐述。 第2 章是网格作业调度及调度算法研究。介绍了作业调度的相关概念及调 度目标。同时介绍了调度算法的分类及评价尺度。最后对较为常用的网格模拟 器g r i d s i m 进行了介绍。 第3 章是m i n m i n 调度算法分析。本章详细分析了m i n m i n 及q o sg u i d e d m i n m i n 算法，分析了这两种算法的不足，提出了m i n m i n 算法改进的方法及 算法思想，并举例说明了改进算法的优点。 第4 章是改进m i l l m i i l 调度算法模块设计与实现。根据m i n m i n 算法及改 进算法的思想，设计了算法实现模块，通过程序实现了算法，采用调度界面进 行各个算法的调度，我们把采集到的调度结果进行了详细的对比及性能分析， 指出了算法的适用性及优点，同时也指出了改进算法存在的问题。 第5 章对本文的主要工作进行总结并提出下一步的研究工作展望。 8 武汉理工大学硕士学位论文 第2 章网格作业调度及调度算法研究 在网格系统中，作业调度是其重要的组成部分，它采用适当的作业调度算 法把不同的作业分配到相应的资源节点上去运行。由于网格系统的异构性和动 态性，以及运行于网格系统之中的应用程序对于资源的不同需求，使得作业调 度变得极其复杂，但是某一个作业调度算法并不可能适用于所有的环境，也不 可能存在一个绝对好的作业调度算法。因此针对不同的要求、不同的环境，需 要有不同的作业调度算法与之相对应。本章将介绍网格环境中作业调度的目标 以及目前研究比较多的算法，并对现有的网格调度算法模拟器进行分析和比较。 首先需要了解网格调度和传统分布式调度系统的主要区别： ( 1 ) 操作对象不同 传统调度系统面对的是组织内部的，执行实际任务的计算单元、存储单元。 而网格调度面对的是不同系统之间的调度实例，本身不涉及具体的资源。因此， 网格调度器又被称为是元调度器，它是建立在现有的调度系统之上的一层中间 层，任务是为不同系统之间的调度实例的协同工作提供标准的系统服务和协议。 ( 2 ) 有效范围不同 网格调度器的有效范围是i n t e m e t 网格环境下资源状态对调度系统而言是 不确定的，对一般分布式系统而言，对负责的调度模块可见。 ( 3 ) 标准的开放性不同 由于不同的系统之间需要通过网格调度系统来进行通信，因此要求通信协 议的标准性和开放性，如o g s a ，w e bs e r v i c e s ，x m l 等。对于系统内部的调度 器，可以根据自身的需要，综合考虑性能等多方面的因素，定制自己的通信协 议。 支持自主系统之间交互的高层调度服务( s c h e d u l i n gs e r v i c e ) 是进行网格调 度技术的关键。同时，网格调度系统设计的基本原则之一就是调度系统需要根 据批处理作业或实时作业定义不同的调度策略以满足q o s 。对网格资源的访问 通常需要遵循资源管理者定义的访问权限、记账、优先级和安全机制，这些机 制是由资源所在的不同系统进行自主管理。 9 武汉理工大学硕士学位论文 2 1 网格中作业调度的特点 网格计算作业调度系统具有以下几个特剧”】： ( 1 ) 任务调度是面向异构平台的。由于网格系统是地理上分布的各类资源 组成，在规模最大的全球性网格中，资源分布在全世界，包括各类主机、工作 站甚至p c 机，它们是异构的，可运行在u n i x 、w i n d o w s 等各种操作系统下， 也可以是上述机型的机群系统、大型存储设备、数据库或其他设备。因此网格 系统中的任务调度必须面向异构平台，并在这些平台上实现网格任务的调度； ( 2 ) 任务调度是大规模的、非集中式的。由于网格系统其资源跨越多个管 理域，规模庞大，要实现一种全局的统一集中的任务调度管理是根本不可能的。 因此，网格的任务调度必须以分布、并行方式进行任务的管理与调度； ( 3 ) 任务调度不干涉网格节点内部的调度策略。在网格系统中，各网格节 点的内部调度策略是自治的，网格任务调度系统干预其内部的调度策略是没有 必要的，也是不可能的； ( 4 ) 任务调度必须具有可扩展性。网格系统初期的计算规模较小，随着超 级计算机系统的不断加入，系统的计算规模也必将随之扩大。因此，在网格资 源规模不断扩大、应用不断增长的情况下，网格系统的任务调度必须具有可扩 展性，不致降低网格系统的性能； ( 5 ) 任务调度能够动态自适应。网格中的资源不但是异构的而且网格的结 构总是不停地改变：有的资源出现了故障，有的新资源要加入到网格中，有些 资源重新开始工作等。 总之网格的动态性是明显的，所以作业调度系统必须适应网格的这种动态 性，从可利用的资源中选取最佳资源为用户提供应用服务。 网格中任务调度主要由任务调度器来控制，任务调度器的结构如图2 1 所 示： 1 0 武汉理工大学硕士学位论文 用户应用 授权认证模任务分配控 块 制 + 任务输入控调度分配算 登 制法 记 0 服 务 资源查询模块 器 图2 1 任务调度器结构 任务调度器的主要组件包括：授权认证模块、任务的输入控制、资源查询、 调度分配算法、任务的分配等。任务调度器接受用户的工作任务，通过授权认 证模块对输入工作任务的用户进行身份验证后，送到任务输入模块。任务输入 模块通过资源查询模块向登记服务器查询各节点所能供服务的性质，包括服务 名、服务类型、服务提供的截止时间、节点主机名等等，获得资源状态，然后 运行调度分配算法，调度分配算法根据工作任务的性质和节点提供服务的属性 来对用户的任务分解。例如，a 节点能提供较强的计算能力，b 节点能提供较大 存储，任务分配控制模块把需要较快运算能力的任务分配给a 节点处理，需要 大的存储的任务分配给b 节点处理，由服务提供者进行处理，井将结果返回给 用户。达到合理的分配任务，提高了资源的利用率。 总结一下，网格调度的特点具体如下： ( 1 ) 任何一个网格调度器都无法面对所有的网格资源进行管理，而只能是 针对一定范围内的网格资源。 ( 2 ) 网格资源动态变化，资源信息的采集和组织对调度影响很大。 ( 3 ) 网格中对各种资源的约束很多有些甚至是非线性，要达到的调度目标 也很多，比如要时间最少、代价最小、资源利用率最高等，有些目标相互矛盾， 对于这种多目标多约束的问题找到满足所有约束和目标的全局最优解是很困难 的。 武汉理工大学硕士学位论文 ( 4 ) 由于其他应用引起的资源竞争对性能影响很大，而且会经常出现，网 格资源的复杂多样，不同类型的资源会展示出不同的性能特征，而且相同类型 的资源由于共享等原因所展示的性能也随时间变化。网格的调度，需要建立随 时间变化的性能预测模型，充分利用网格的动态信息来表示网格性能的波动。 2 2 作业调度的目标 简单地说，网格环境中作业调度的目标就是要对用户提交的作业实现最优 调度。具体的目标包括：最优跨度( o p t i m a lm a k e s p a n ) 、服务质量q o s ( q u a l i t y o f s e r v i c e ) 、负载均衡( l o a db a l a n c i n g ) 、经济原则( e c o n o m i cp r i n c i p l e s ) 等【1 8 】。 ( 1 ) 最优跨度 跨度是网格作业调度最常见、最主要的调度目标。它指的是一个用户的所 有作业的调度时间，即从执行第一个作业开始，到所有作业执行完成所花的时 间的总和。跨度越短，证明该调度算法越好，拥有最短跨度的跨度称为最优跨 度。从节约时间、充分利用资源的角度来考虑，以最优跨度为目标是大多数资 源拥有者和网格用户的共同目标。 ( 2 ) 服务质量 网格用户在选择资源时，可能会对资源的某些方面( 如c p u 速度、网速、 存储空间等) 有特殊的要求，他们希望尽可能的有好的服务来满足需要。这些 要求都将包含在用户提交的作业中，并且以q o s 的形式显示出来。在作业调度 时，网格将根据作业中的q o s 要求，选择合适的资源进行调度，充分满足用户 的需求。 ( 3 ) 负载均衡 在开发并行和分布式计算应用时，负载平衡是一个关键问题。网格系统更 进一步扩展了这个问题。网格作业调度是涉及交叉域和大规模应用的调度。解 决好系统的负载均衡是一个非常重要的问题。 ( 4 ) 经济原则 网格环境中的资源在地理上是广泛分布的，而且每个资源都归属于不同的组 织，都有各自的资源管理机制和政策。根据现实生活中的市场经济原则，不同资 源的使用费用也应是不相同的。市场经济驱动的资源管理与作业调度必须使消费 双方( 资源使用者和资源提供者) 互惠互利，才能使网格系统长久地发展下去。 1 2 武汉理工大学硕士学位论文 2 3 网格资源调度组织模式 网格环境下的资源调度可以分为互相间存在通信的任务组的调度即d a g 图 ( 有向无环图) 的调度和互相独立的任务组( m e t a t a s k ) 的调度两类。资源管理 使用调度策略来确定请求和资源调度的相关顺序。图2 2 显示的调度策略的分 类。 图2 2 网格资源调度策略 对于相互间存在通信的任务的调度，现在常用的方法是沿用传统的d a g 图 调度，即将相互间存在数据往来的任务组当作一个有向无环图做出调度策略。 但对于大规模、多管理域的网格系统，d a g 图调度方式可能有较大的困难，经 常采用预置和合作配置的方法来保证任务的执行。 通常在网格环境下主要考虑的是一组相互独立、任务之间没有通讯和数据 往来的元任务、m e t a t a s k 4 3 】映射。由于资源调度是n p 完全问题，解决这类问题 常用启发式算法。针对异构计算环境中的元资源调度，动态启发式算法又分为 在线模式( o n 1 i n e ) 和批模式( b a t c h m o d e ) 两种。在线模式是任务一到就加以 映射，而批处理模式则是把任务收集起来等映射事件到来后对这些任务进行集 中映射。同在线模式相比，批模式得到了大量的资源信息，从而可以做出更合 武汉理工大学硕士学位论文 理的任务映射策略。本文中即属于批处理模式。 2 4 作业调度模式及策略 2 4 1 常见的调度模式 常见的任务调度模式有以下三种： ( 1 ) 集中式调度模式 在集中式调度环境中，一个中央机器扮演着资源管理者的角色，它将作业 调度到环境周围的其它节点。这种调度模型通常在所有资源具有相似特性和使 用规则策略的场合中。 在这种调度中，作业首先提交给中央调度者，然后由它将这些作业分配给 适当的节点，那些不能在一个节点上启动的作业通常存放在中心作业队列中， 以便随后启动。 集中式调度系统的优势之一是调度者能够给出更好的调度策略，因为它拥 有关于可用资源的所有必要的、最新的信息。然而，集中式调度显然不能与它 所管理的不断增长的环境匹配的很好。调度者本身可能成为一个瓶颈，必须保 证其安全和可靠，以防止单点失效，比如建立双网格调度器是解决单点失效的 有效办法。 ( 2 ) 分布式调度模式 在分布式网格调度模型中，每个网格调度器仅维护本管理域的负载信息， 没有中央调度者负责管理所有的作业。相反地，分布式调度涉及到多个本地调 度者，其任务是彼此交互已分配作业给参与的节点。一个调度者和其它调度者 之间有两种通信方式：直接通信和间接通信。 分布式调度克服了集中式调度的可扩展性问题，而且它能够提供更好的容 错能力和可靠性。但由于缺乏中央调度者，分布式调度通常导致不够理想的调 度决策。 ( 3 ) 分层调度模式 网格计算环境中，调度实际上是分为两个阶段，外部调度和内部调度。外 部调度是指，首先通过网格资源信息服务寻找到当前满足任务需求的资源，然 后通过某种策略从这些资源中选择最佳的资源来执行任务。内部调度是指网格 1 4 武汉理工大学硕士学位论文 作业映射到本地服务资源以后，由服务资源本地管理者予以调度。分级式调度 模式就是指在外部调度采用集中式的调度，而在内部调度中允许资源提供者使 用自己的调度策略来进行作业调度。因此，这种模式是一种结合式的方法，比 较适合网格系统。 在小型的网格系统中，采用集中式调度比较好。因为在小型的网格系统中， 资源不是很庞大，调度中心比较容易掌握所有的资源，对一个任务的请求可以 高效地产生调度方案。 而分布式调度其优点是健壮性、可靠性和可用性，但是如果各个调度中心 之间没有高效的吞吐或者通信量比较大时，不易于管理和资源协同分配，所以 很难找到全局最优的资源分配方案。 分层调度器易于实现扩展和容错，易于资源的协同分配，但不支持资源地 域自治和多种调度策略。 2 4 2 作业调度策略及分类 一般从调度策略本身考虑，可将任务调度分为静态调度和动态调度两类。 静态调度的主要特点是实现简单，但调度质量不佳。动态调度的主要特点是能 充分发挥各资源的处理能力，但实现起来比较复杂，可能由于任务的动态调整 影响个别任务的执行效率。目前出现了将静态调度与动态调度相结合的混合调 度方法，可以兼顾二者的优越性。 调度器的组织分为集中式、分层结构和分布式的三种。集中式调