（计算机科学与技术专业论文）异构分布式系统中的负载均衡调度算法研究.pdf

r e s e a r c hf o rs c h e d u l i n ga l g o r i t h mb a s e do nl o a d b a l a n c i n gi n d i s t r i b u t e dh e t e r o g e n e o u s s y s t e m s b y 洲gj i n b e ( h u n a nu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fs c i e n c e c o m p u t e rs c i e n c ea n dt e c h n o l o g y i n t h e g r a d u a t es c h o o l h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rk e n l il i m a y , 2 0 1 1 啪49 2609-y 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 车易喑 e l 期：矽i1 年r 月h 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书。 2 不保密团。 ( 请在以上相应方框内打“”) 作者签 导师签 日期：口年r 月。日 日期：洳1 年f 月如日 硕一f ：学位论文 摘要 随着社会的发展，经济的突飞猛进，为了促进社会和谐，地震灾变的预测也 就越来越重要了。现代计算机技术的迅猛发展，包括地震灾变预测等越来越多的 工程计算问题都依靠于大型高性能超级计算机来解决。而工程计算从一定程度上 又驱动了高性能计算机的发展。目前，并行系统，网格计算等分布式技术已经成 为解决工程问题的重要方法，而在分布式系统中，为了提高分布式系统的性能， 调度问题成为了现代分布式系统中的一个热点问题。各种调度算法被大批的研究 人员所提出，它们的调度优化目标不尽相同，但是总的来说都是为了改进分布式 系统的性能。为此本文以任务调度的负载均衡为目标，对任务调度问题进行了深 入的研究。 首先，针对现在异构分布式系统的负载均衡问题，本文设计了一个改进的动 态遗传算法i d g a ( i m p r o v e dd y n a m i cg e n e t i ca l g o r i t h m ) 应用于异构分布式系统的 调度器中，以此来优化异构分布式系统的负载均衡性能。考虑到传统的遗传算法 在任务调度的应用中存在着最大进化代数有限的缺点，本文涉及了i d g a 算法， 克服了最大进化代数受限的缺点，并且在找到符合负载均衡标准的解以后，i d g a 算法会按照一定的策略重新设置系统的负载均衡标准来试图找到比当前最优调度 更好的调度。 其次，由于i d g a 算法可以动态设置最大进化代数，那么有可能引起遗传算 法时间复杂度的增加，为了提高i d g a 算法的效率，通过引入m a p r e d u e e 分布式 系统模型，将i d g a 算法在m a p r e d u c e 模型下并行化。 最后，在i d g a 算法的并行化过程中，提出了一个用来表示遗传算法初始种 群的数据结构二叉选择树，在利用这个数据结构对遗传算法进行选择操作的 时候，可以提高选择操作的时间效率。该二叉选择树是一个平衡的二叉树，所以 搜索的平均复杂度是o ( 1 0 9n ) ，其中1 1 代表种群的规模。而传统的遗传算法中， 只能通过线性时间复杂度o ( n ) 才能成功选择出一个个体。该二叉树的每个节点上 都记录了该节点左子树的所有节点的适应度之和与右子树的所有节点的适应度之 和。所以在决定选择左子树、右子树还是当前节点时可以通过产生一个随机数， 并根据各自的适应度函数值来进行选择，这样明显提高了选择操作的效率。 关键词：地震灾变模拟；任务调度；异构分布式系统；遗传算法 i i a b s t r a c t w i t ht h es o c i a ld e v e l o p m e n ta n de c o n o m i ca d v a n c e s ，t h ep r e d i c t i o no fe a r t h q u a k e d i s a s t e ri sm o r ea n dm o r ei m p o r t a n tf o rp r o m o t i o no fs o c i a lh a r m o n y w i t ht h er a p i d d e v e l o p m e n to fm o d e r nc o m p u t e rt e c h n o l o g y ，c a l c u l a t i o n so fag r o w i n gn u m b e ro f p r o je c t sa r ed e p e n d e n to nl a r g e s c a l eh i g h p e r f o r m a n c es u p e r c o m p u t e r s t os o l v e ，s u c h a st h ee a r t h q u a k ed i s a s t e rp r e d i c t i o n a n de n g i n e e r i n g c a l c u l a t i o n sa l s od r i v et h e d e v e l o p m e n t o fh i g h p e r f o r m a n c ec o m p u t e r s c u r r e n t l y , t h ep a r a l l e ls y s t e m ，g r i d c o m p u t i n ga n do t h e rd i s t r i b u t e dt e c h n o l o g y s a r ei n c r e a s i n g l yb e c o m i n gi m p o r t a n t a p p r o a c h e st os o l v et h ee n g i n e e r i n gp r o b l e m 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 f d i s t r i b u t e ds y s t e m s ，t h es c h e d u l i n gh a v eb e c a m eah e a t e d i s s u e i nm o r d e nt i m e v a r i o u ss c h e d u l i n ga l g o r i t h m sh a v eb e e np r o p o s e db yal a r g en u m b e ro fr e s e a r c h e r s t h e yh a v ed i f f e r e n tp u r p o s e s ，b u ti ng e n e r a la r ei n t e n d e dt oi m p r o v e t h ep e r f o r m a n c e o fd i s t r i b u t e ds y s t e m s i nt h i sp a p e r , w ea n a l y s et h e t a s k so fe a r t h q u a k ed i s a s t e r e n g i n e e r i n gi nh e t e r o g e n e o u sd i s t r i b u t e dc o m p u t i n gs y s t e m ，a n dt h o r o u g h l y s t u d i e d t h ep r o b l e mo ft a s ks c h e d u l i n gi no r d e rt oi m p r o v et h ep e r f o r m a n c eo ft h e l o a d b a l a n c i n gi nh e t e r o g e n e o u sd i s t r i b u t e ds y s t e m f i r s t l y ，i no r d e rt os o l v et h ep r o b l e mo fl o a db a l a n c i n gi nd i s t r i b u t e ds y s t e m s ，w e d e s i g n e da ni m p r o v e dd y n a m i cg e n e t i ca l g o r i t h mn a m e di d g a ( i m p r o v e dd y n a m i c a l g o r i t h m ) a st h es c h e d u l i n gs t r a t e g yo fah e t e r o g e n e o u sd i s t r i b u t e ds y s t e m t a k i n g i n t oa c c o u n tt h et r a d i t i o n a lg e n e t i ca l g o r i t h mn e e dt o s e tt h em a x i m u me v o l u t i o n g e n e r a t i o na sac o n s t ，i d g aa l g o r i t h mw h i c ho v e r c o m e st h ed e f e c t so f t h ec l a s s i cg a c a nd y n a m i c a l l yc h a n g et h es e t t i n go ft h em a x i m u me v o l u t i o ng e n e r a t i o n t h ei d g a a i g o r i t h mt r i e st or e m e m b e rt h eo p t i m a lc h r o m ed u r i n gt h ep r o c e d u r eo f a l lo v e rt h e e v o l u t i o n s e c o n d l y , b e c a u s e t h ei d g aa l g o r i t h mc a nd y n a m i c a l l y s e tt h em a x i m u m e v o l u t i o n a r yg e n e r a t i o n ，t h eg e n e t i c a l g o r i t h mm a y c a u s ea ni n c r e a s e dt i m e c o m p l e x i t y i no r d e rt oi m p r o v et h ee f f i c i e n c yo f t h ei d g aa l g o r i t h m ，w ep r o p o s e da m o d e lw h i c hb a s e do nt h em a p r e d u c e o u rt a r g e ti st op a r a l l e lt h ei d g aa l g o r i t h mi n o u rp r o p o s e dm o d e l f i n a l l y ，w ep r o p o s e dad a t as t r u c t u r e ab i n a r yc h o i c et r e et oo r g a n i z et h ei n i t i a l p o p u l a t i o no ft h eg e n e t i ca l g o r i t h m u s i n gt h i ss t r u c t u r e ，t h et i m ec o m p l e x i t yo f t h e s e l e c t i o no p e r a t i o ni nt h eg e n e t i ca l g o r i t h mw i l lb ei m p r o v e d i nd e t a i l ，t h eb i n a r y i v 硕一i ：学位论文 c h o i c et r e ei sab a l a n c i n gt r e e ，s oi tc a ni m p r o v et i m ec o m p l e x i t yo ft h es e l e c t i o n o p e r a t i o nf r o m0 ( n ) t o0 ( 1 0 9n ) ，w h i c hnr e p r e s e n t a t i v es c a l eo ft h ep o p u l a t i o n s e a c hn o d eo ft h eb i n a r yt r e em u s tr e m e m b e r st h r e ef i t n e s s e s ，t h o s ea r e ：t h ef i t n e s so f r i g h ts u b t r e e ，t h ef i t n e s so fl e f ts u b t r e ea n dt h ef i n t n e s so fi t s e l f t h e r e f o r e ，b e f o r ew e h a v et od e s i d ew h i c ho n ew o u l db es e l e c t e d ，r i g h ts u b t r e e ，l e f ts u b t r e eo ft h ec u r e n t n o d e ，w ec a np r o d u c ea nr a n d o mn u m b e rn ，w h i c hni sl e s st h a n1a n db i g g e rt h a n0 ， t oh e l pu st om a k et h ed e c i s i o n s ot h eb i n a r yc h o i c et r e es i g n i f i c a n t l yi m p r o v e st h e e f f i c i e n c yo fs e l e c t i o no p e r a t i o n k e yw o r d s ：e a r t h q u a k ed i s a s t e rs i m u l a t i o n ；s c h e d u l i n g ；d i s t r i b u t e ds y s t e m ；g e n e t i c a r l g o r i t h m v 异构分布式系统中的负载均衡算法研究 目录 学位论文原创性声明及学位论文版权使用授权书：。i 摘要i i a b s t r a c t i v 插图索引v i i i 附表索引i x 第l 章绪论1 1 i 课题来源1 1 2 课题背景l 1 3 调度问题研究意义2 1 3 1 任务调度问题的目标3 1 3 2 任务调度问题的特点4 1 3 3 任务调度问题的分类5 1 3 4 经典任务调度算法介绍7 1 4 论文主要工作8 1 5 论文组织结构9 1 6 ，j 、结9 第2 章相关背景知识和研究工作1 0 2 1 地震灾变的模拟过程1o 2 2 问题的提出lo 2 3 相关的研究工作一1 1 2 4 遗传算法1 2 2 4 1 遗传算法的历史1 2 2 4 2 遗传算法的基本概念1 2 2 4 3 遗传算法的优缺点1 3 2 4 4 标准遗传算法的流程1 4 2 5 小结：16 第3 章异构分布式系统中一种基于遗传算法的负载均衡调度算法1 7 3 1 异构系统调度模型17 3 2 优化目标形式化18 3 3 改进的动态遗传算法( i d g a i m p r o v e dd y n a m i cg e n e t i ca l g o r i t h m ) 。19 3 3 1 染色体设计19 v i 硕 = 学位论文 3 3 2 算法描述和分析2 0 3 3 3 适应度函数2 1 3 4 实验设计。2 2 3 4 1 预处理模块2 2 3 4 2 调度算法模块2 2 3 5 结果分析2 5 3 6 j 、结2 8 第4 章i d g a 算法在m a p r e d u c e 系统模型中的并行化3 1 4 1 并行遗传算法介绍31 4 2m a p r e d u c e 基本原理介绍3 3 4 3m a p r e d u c e 模型中的并行i d g a 算法( p i d g a m a p r e d u c e ) 3 6 4 3 1m a p 阶段设计一3 6 4 3 2r e d u c e 阶段设计以及二叉选择树3 7 4 3 3 整体流程4 3 4 4p i d g a m a p r e d u c e 与i d g a 的时间复杂度分析4 5 4 5 j 、结4 6 结论4 7 参考文献4 9 致 射5 3 附录a ( 攻读硕士期间发表论文与申请专利目录) 5 4 附录b ( 攻读硕士期间参加的科研项目) 。5 5 v 异构分布式系统中的负载均衡算法研究 插图索引 图2 1 地震灾变系统模拟过程1o 图2 2 标准遗传算法流程图。15 图3 1 异构系统调度模型1 7 图3 2 染色体模型1 9 图3 3 交叉操作前的染色体一2 0 图3 4 交叉操作后的染色体2 0 图3 5 变异操作2 0 图3 6 预处理模块2 2 图3 7 调度算法模块一2 3 图3 8 系统利用率计算示意图2 6 图3 9 系统利用率随着任务数目变化曲线3 0 图3 1 0 平均系统利用率示图3 0 图4 1 两线程分布式遗传算法的基本流程3 2 图4 2g o o g l e 的m a p r e d u c e 执行方式3 5 图4 3p i d g a m a p r e d u c e 的m a p 模型图3 6 图4 4p i d g a m a p r e d u c e 的r e d u c e 模型图3 8 图4 5 个体结构图3 9 图4 6 树形结构选择操作示例4 1 图4 7 新个体和被淘汰个体一4 l 图4 8 新个体替换被淘汰个体4 2 图4 9 更新新个体的祖先节点( 1 ) 4 2 图4 1o 更新新个体的祖先节点( 2 ) 4 2 图4 11p i d g a m a p r e d u c e 的算法流程图4 3 v i i i 硕一t - 学位论文 附表索引 表3 1 参数说明表2 7 表3 2 实验数据一一2 8 表3 3 实验数据二。2 9 表4 1 参数意义表4 5 i x 硕上学位论文 1 1 课题来源 第1 章绪论 本文的研究课题背景来源于国家自然科学基金重大研究计划”重大工程的动 力灾变”的培育项目”网格环境下地震模拟支撑系统的关键理论与技术研 究”( 9 0 7 1 5 0 2 9 0 ) 。 ， 1 2 课题背景 大型科学工程计算问题需要非常复杂的运算，随着现代的计算机技术飞速发 展，在高性能计算机上进行科学工程计算是一种最有效的解决方法。从某种程度 上来说，大型的科学工程计算驱动了高性能计算机的发展。但是由于硬件上的局 限，要将一个复杂的工程计算问题用一台单独的计算机来处理，似乎不能满足我 们对于计算速度的要求。目前，随着计算机网络，特别是i n t e r n e t 的迅猛发展，传 统的信息系统概念发生了巨大的变化，这些变化突出表现在信息的存储、传递、 发布及获取的方式所发生的革命性变革。如何在更为广域和异构的计算环境中有 效地发布和获取信息，利用更大范围的资源来处理复杂的问题，已成为了日益严 峻的问题。分布式系统正式为了解决上述问题，它将分布在不同地域的计算机或 者资源组织整合起来，形成一个高性能的综合系统。正是因为分布式系统的这个 优点，解决大型科学工程计算问题的计算机越来越趋于并行化，网络化，智能化。 所以集群系统成为了当前计算机科学领域的一个的一个研究热点【1 3 1 。集群系统是 由一组独立自治的计算机连接在一起而形成的计算机组合，但集群系统的这种结 构对于用户却是透明的，节点集合作为一个整体为用户提供所需要的服务，其中 集群中的每个节点都有自己独立的进程来，通过节点进程之间的彼此通信来协调 请求的分配。这种系统不仅能提高计算速度，使得尽可能多的普通用户能够完成 庞大的计算任务，而且可以节约成本，动态扩缩规模，具有良好的扩展性，能够 满足日益增长的计算要求。集群计算多种多样，其中包括工作站网络( n e t w o r ko f w o r k s t a t i o n ) 、元计算( m e t a c o m p u t i n g ) 、异构计算( h e t e r o g e n e o u sc o m p u t i n g ) 、网 格计算( g r i dc o m p u t i n g ) 等【4 7 】。 长期以来，由于基于高性能计算的数值灾变模拟系统不但需要计算速度快的 超级计算机，对计算机软件的要求也非常高，所以目前利用高性能计算机对强地 震情况下结构如何倒塌的模拟与再现存在比较大的困难。所以传统的利用集中式 超级计算机进行集中式计算的方法已经不能适应局势的发展，其在地震灾变模拟 方面存在着明显的缺陷，具体表现为： 异构分布式系统中的负载均衡算法研究 ( 1 ) 处理大规模任务集合计算任务方面 虽然可以通过优化提高计算机网络网络的带宽、服务器的性能等方法来加快 任务的计算速度，但是这种方法的提升空间毕竟存在一个局限，由于物理硬件制 造工艺方面的限制，现代计算机硬件制造工艺已经趋于极限，所带来的就是传统 集中式p c 处理性能的瓶颈将会出现。单个p c 上的处理规模已过度膨胀，想象一 下，如果把数万个地震灾变模拟任务调度到一台计算机上进行运算，那将是一件 非常可怕的事情。所以说，传统的集中式计算方法对于处理大规模数值计算的要 求已经越来越难以满足，从而导致难以得到我们所需要的仿真结果。 ( 2 ) 资源需求多样性任务处理 资源需求多样性是指，在一个地震灾变科学计算任务的计算过程中，它的每 个子任务有可能需要各种不同的数值分析软件以及一些其它的计算资源。传统的 集中式处理就需要在该集中系统上装上各种各样计算任务所需要的资源，当所有 的资源都启动后，对系统的性能将造成影响。资源需求越多，系统的效率也就越 低。而且目前的数值模拟工具是非常昂贵的，有时为了解决一个不常见的小问题 而不得不去将整个软件的使用权购买下来这样是很不划算的。而分布式的计算方 法则可以在不同的计算节点上装有不同的资源，利用分布式系统的资源协同的特 点来解决这个问题，所以不同机构之间利用分布式系统可以相互利用自己不常用 而又有时候不得不用的一些资源，从而降低了成本。 分布式计算方法不仅克服了传统集中式计算方法的缺陷，还具有以下优点： ( 1 ) 实现了系统对用户的透明性； ( 2 ) 可以实现负载迁移，提高系统利用率； ( 3 ) 个别节点的崩溃不会引起整个系统的服务异常。 总结以上原因，基于分布式系统的重大在变模拟软件的开发已经成为了我国 灾变预测领域的一个重要投资。 1 3 调度问题研究意义 研究表明，在异构系统中很多节点在大部分时间里都是处于空闲状态或者是 低利用率状态。就算是在每天使用最频繁的时间段，也有平均将近6 0 的节点出 于空闲状态或低利用率状态。这样就造成了资源的浪费，许多节点的c p u 内存等 等计算资源都没有得到最充分有效的利用。为了解决这种情况，我们需要通过一 定的机制来提高系统的利用率，使得空闲节点的数目减少，这样就降低了系统中 一些负载过重的节点的负担，使得系统的计算能力和效率都得到明显的提高。在 实际的异构系统中，往往通过设计一个适当的任务调度器，通过对用户提交的任 务进行分析处理后，按照一定的策略将任务分配到适当的节点上。高效的任务调 度器能够充分发挥系统的并行计算能力，并且可以提高系统的吞吐量、改善系统 2 硕士学位论文 的负载均衡性能、最大限度地提高任务的平均响应时间等等。任务调度的本质就 是对于提交的任务集合，要如何将该任务集合的每个任务映射到异构系统的节点 集合上，从而使得特定系统的优化目标达到最优。具体来说，不同的的异构系统 的任务调度优化目标是不一致的，在实时系统中，可能会比较关心任务的响应时 间；而另外有些系统比较关系系统的吞吐率或者负载均衡等因素。 分布式系统的任务调度问题已经被证明是一个n p 问题。对于一个n p 问题， 它有这样一个性质：它可以在多项式时间内求解，当且仅当所有的其他的n p 完 全问题也可以在多项式时间内求解。p 是所有可在多项式时间内用确定算法求解 的判定问题的集合，n p 问题是所有可用多项式时间算法验证其猜测准确性的问 题的集合1 8 j 。调度问题作为一个n p 问题，一直都是是计算机科学研究领域的一 个热点问题【9 】，在过去对于调度问题的的研究过程中中，已经有很多人提出了一 些性能良好的调度算法 1 0 “1 3 j 。 一 1 3 1 任务调度问题的目标 上文中已经提到，不同系统对于任务调度的目标是各不相同的。但是比较常 见的任务的调度问题的目标有任务执行的时间跨度( m a k e s p a n ) ，系统的服务质量 ( q o s ) ，系统的可用性( a v a i l a b i l i t y ) ，系统的负载均衡( 1 0 a db a l a n c i n g ) 等【1 4 “6 1 。 ( 1 ) 时间跨度。时间跨度是异构系统调度算法最常见的优化目标，它指的是 从任务集合提交到任务集合中的最后一个任务完成所需要的时间。对于一个优化 时间跨度的任务调度算法来说，如果能够获得更短的时间跨度，也就证明了任务 调度算法的高效性。站在用户的角度来说，大部分时候都希望在提交任务后能够 尽快地得到计算结果，所以时间跨度这个目标能够越短越好。所以说时间跨度是 任务调度问题中的一个至关重要的参数。 ( 2 ) 服务质量。异构系统面向的用户群是多种多样的，所以用户对资源的要 求也是多种多样的，这种关系就是通过服务质量( q o s ) 反映出来的，系统必须根 据用户的需求给用户分配资源。但是这个过程对于用户是透明的，用户不必关心 资源的获取过程，那么如何协同各个不同用户与不同资源之间的分配就成为任务 调度问题需要优化的一个目标。 ( 3 ) 可用性。对于一些不可中断任务来说，如果在执行任务的过程中机器突 然出现故障，那么这个任务就要重新开始执行。那么对于这类任务，都有一个对 机器可用性的要求。所谓机器的可用性就是指机器正常运行不发生故障的概率。 如果任务根据自身的可用性要求来选择可用性达到要求的机器，这样就可以提高 整个系统的可用性。系统可用性的提高从某种意义上来说也减少了时间跨度和任 务失败的概率。所以把可用性作为任务调度问题的目标也是非常合理的。 ( 4 ) 负载均衡。异构系统通过共享和协同系统内部资源，从而满足复杂应用 中对大规模计算能力的需求。但是由于异构系统中各个节点的处理能力和容量不 异构分布式系统中的负载均衡算法研究 均衡，作业的到达模式不一致，从而造成有的节点大量的资源被闲置，有的节点 却负载过重。由于负载分配不均衡从而造成系统中的资源利用率下降，很多负载 过重的节点由于资源有限，很容易导致大部分任务由于分配不到资源而执行失败， 最后可能造成系统发生故障的概率增高，利用率急剧下降。那么负载均衡问题也 是异构系统中必须解决的一个问题，所以将负载均衡作为任务调度问题的一个目 标也是理所当然的。 1 3 2 任务调度问题的特点 分布式的任务调度系统那个一般具有以下几个特点： ( 1 ) 分布式任务调度是面向异构平台的。分布式系统一般是将一些不同平台 的资源信息等整合起来。不管从硬件上还是系统以及软件上来说，分布式系统一 般是具有异构性的。因为分布式系统中的每个节点都是分布在互联网上，他们属 于不同的物理地域。并且每个节点的操作系统可能各不相同，有的节点可能是服 务器，拥有较高的配置，而有的节点可能是普通的p c ，只够处理一般的办公程序。 也可能该节点就是一个拥有大量节点的集群系统，该节点只是对外的一个接口而 已。所以，我们的分布式任务调度系统面向的是由大量各不相同的机器所组织起 来的异构集群系统。 ( 2 ) 分布式系统中的任务调度独立于每个节点内部的调度策略。异构分布式 系统的特点是：系统中每个节点都是自治的，它们通过资源协同来处理任务，而 当任务分配到具体的节点之后，c p u 根据什么策略对任务进行调度这是由各个节 点的操作系统决定的。异构系统的调度策略和节点内c p u 的调度策略是互不相干 的。 ( 3 ) 异构分布式系统中的任务调度是大规模的非集中式调度。要在一个规模 庞大的分布式环境中实现一个全局的集中任务调度管理从根本上来说是很难甚至 是不可能实现的。所以在分布式环境的任务调度必须以分布、并行等方式对任务 进行调度与管理。 ( 4 ) 可扩展性是任务调度必须具有的特点。可扩展性是很多异构系统需要考 虑的因素。在异构系统的初始阶段，由于计算量不大，可能系统的硬件性能，规 模大小等都存在局限性。但是随着计算任务数量和种类的增加，要使得原来的系 统仍然能够满足现在的计算要求，必须对异构系统进行扩展，这就要求异构系统 必须具有良好的可扩展性。 ( 5 ) 任务调度能够动态自适应。网络中的资源出了异构的特点外还具有可改 变性：有的资源由于故障原因退出了利用范围，而有的由于新节点的加入或者某 些节点性能扩展而增加了新的资源，而另外一些情况下，那么本来被占据的资源 由于计算任务的完成而被释放从而重新加入可利用的行列。那么如何在异构系统 资源千变万化的情况下动态搜集资源信息，不会因为资源信息过时而导致计算任 4 硕士学位论文 务所分配的资源不可用就成为了一个重要的问题，所以任务调度必须要可以动态 自适应地处理搜集资源信息。 1 3 3 任务调度问题的分类 根据国内外对任务调度问题的研究分类，目前任务调度主要分为： ( 1 ) 在线( 动态) 任务调度和批模式( 静态) 任务调度 国内外对于任务调度问题已经做了大量研究，并且提出了大量的启发式算 法，m u t h u c u m a r um a h e s w a r a n 等人根据任务和处理器之间的映射策略将任务调度 算法分为为静态( 在线) 模式( o n 1 i n e ) 和动态( 批) 模式( b a t c h m o d e ) 两种，实际上这两 种模式的区别就体现在决定每个任务的具体调度的时刻上。在线模式调度的主要 特点是实时性比较高，用户每提交一个任务，调度器就立刻决定这个任务的映射 节点并将任务分配到该节点，但是但实现起来比较复杂，可能由于任务的动态调整 影响个别任务的执行效率。批模式调度的主要特点是能集中充分考虑提交的任务 集合与节点集合的状态信息，对多个调度进行比较后，再选出一个最佳的调度来 进行任务和机器的映射，批模式总会在收集到用户提交的一批任务后才对任务按 照一定的策略来分配。 批模式调度是以异构系统的资源情况和性能的参数已知为前提的。往往在任 务真正调度到各个运行节点以前，批模式调度策略都会对该任务集合的映射作各 种假设，然后选择一个相对最优的任务到节点的映射，按照这个映射将当前待调 度的任务集合分配到各个节点上。对于某些大的计算任务，可能是任务量可分解 的任务，那么也可以利用批模式调度来分解任务量，找到最佳分解方法使得任务 的总执行时间最少。像这样的任务调度策略可以应用在很多领域，比如如图像处 理，数所挖掘和工程的科学计算中等。该模式的调度也可以对一批毫不相干的独 立任务进行调度，这种批模式调度以寻找任务的最佳资源匹配使得任务的时间跨 度( m a k e s p a n ) 最小为目标。批模式的调度算法有足够的时间将任务信息和系统信 息考虑进来，从而提高了算法的调度性能。在实时系统中，用户对系统的响应时 间比较关心，所以使用在线的调度算法效果会更好。而在实时性要求相对不高的 系统中，由于用户对于系统的响应时间没有很高的要求，使得系统用后充足的时 间来对用户提交的任务进行分析映射，那么使用批模式的调度算法将会获得更好 的性能和横好地系统利用率。批模式调度还必须知道所有的系统响应参数和任务 参数都是一致的( 比如说特定的任务在特定过得节点上的执行时间已知) ，但是这 在实际的运用中很难达到这些要求。 与在线调度模式相比，由于批模式调度是以任务信息和节点信息的已知为前 提的，它通常具有更好的调度性能，文献【1 7 1 和t 1 8 】中通过实验数据证实这个论点。 在文献t 1 8 】中作者对m a x m i n t l 9 2 1 1 、m i n m i n t l 9 2 1 1 、g a 和a 母等若一系列算法进行 了比较，结果表明g a 算法具有最优的性能，其次是m i n m i n 算法和a 幸算法，但 5 异构分布式系统中的负载均衡算法研究 当g a 算法在有些主机性能发生突变时，性能将会大打折扣，而在文献【l7 j 则对 m i n m i n 算法和m a x m i n 算法进行了对比研究，结果表明m i n m i n 算法相对于 m a x m i n 算法具有更好的m a k e s p a n ，所以说m i n m i n 算法仍然是目前分布式调 度算法最重要的研究基础。此外，目前还有人提出了o l b ( o p p o r t u n i s t i cl o a d b a l a n c i n g ) 、m e t ( m i n i m u me x e c u t i o nt i m e ) 、s a ( s i m u l a t e da n n e a l i n g ) 等批模式 调度算法。 在线模式调度算法【2 2 】是对目前提交的任务进行实时处理，也就是任务一经提 交，调度器就对任务进行任务到机器的映射。在线模式调度算法有一个很重要的 特点，那就是实时性，所以在设计在线调度算法时，不仅要考虑减少任务最重的 执行时间，还要考虑算法本身的代价，这种代价就是调度算法本身的运行时间， 这将直接影响到实时系统的性能。目前经典的在线模式调度算法主要包括 m c t ( m i n i m u mc o m p l e t i o nt i m e ) 、e d f ( e a r l i e s td e a d l i n ef i r s t ) 、s a ( s w i t c h i n g a l g o r i t h m ) 、k p b ( k p e r c e n tb e s t ) 、o l b ( o p p o n u n i s t i cl o a db a l a n c i n g ) 等若干算法【1 7 j 。 最早时限优先调度( e a r l i e s td e a d l i n ef i r s t ) 是一种动态可抢占优先级的在线实 时模式的调度算法，它最大的好处是所有节点的利用率可以达到1 0 0 。此外，e d f 算法对于那些任务优先级周期动态变化的任务也有很好的支持。但是e d f 算法在 预测诸如任务计算的成功性及瞬时过载时的非确定性等方面还存在着明显的不 足。另外一种可以将节点的利用率保持在1 0 0 的算法叫做m l f 算法，这也是一 种在线模式的实时调度算法，和e d f 算法不同，m l f 算法将所提交任务的运行时 间作为调度目标的参考参数。这两个算法的相同处在于：当任务量瞬时过载的情 况下，e d f 算法和m l f 算法都不能控制或预测任务的失败或者成功，所以它们都 不能保证所有的任务都可以成功完成预期的结果。m c t 算法在处理一个任务到达 时，首先计算该任务在各台节点上的完成时间，以便确定那个节点的预期完成时 间最少，然后立即将其映射到预期完成时间最少的节点上，因此，该算法的复杂 度和异构系统节点的数目成一个线性比例。但是实际上m c t 算法