（计算机软件与理论专业论文）集群计算机系统负载均衡技术研究.pdf

哈尔滨t 科人学硕十学何论文 摘要 随着微处理器技术和高性能网络技术的飞速发展，集群计算逐渐成为一 种高性价比的并行分布式计算资源。负载均衡是集群系统中的重要技术，通 过平衡各个节点间的负载来提高集群系统的性能。而动态负载均衡近年来成 为研究的热点，因为它根据集群的负载状况动态地负载分配，相对来说能更 大地提高系统的性能。 基于剩余计算能力的动态负载均衡系统是一种基于新型负载向量的动态 负载均衡系统。该系统使用一种新的负载评价指标：剩余计算能力，它兼顾 节点的资源使用情况及节点本身的性能特征两个方面，更好地体现了集群系 统的处理能力和系统正在处理的负载情况，比常用的其它负载向量更加灵活、 准确。 该系统实现了信息的分散收集和集中管理，各节点在自己状态改变时收 集负载信息汇报给控制节点，形成剩余计算能力向量表。控制节点根据此表， 进行负载均衡决策。除此，系统还将任务调度和进程迁移结合起来，以达到 更有效的系统负载均衡，同时，也减小系统负载均衡带来的额外开销。 测试结果表明，与其它负载均衡系统相比，该系统缩短任务的响应时间， 从而提高了集群的性能。因此，本文提出的动态负载均衡系统确实能够比较 有效和灵活地解决集群系统的负载均衡问题，弥补现有系统存在的一些不足 之，处。 关键词：集群；负载均衡；任务调度；进程迁移；剩余计算能力 a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n to fm i c r o - p r o c e s s o ra n dh i g hp e r f o r m a n c e n e t w o r k ，c l u s t e rc o m p u t i n gh a s g r a d u a l l yb e c o m eah i g hc o s t p e r f o r m a n c e p a r a l l e l d i s t r i b u t e d c o m p u t i n g r e s o u r c e l o a d b a l a n c i n g i sa n i m p o r t a n t t e c h n o l o g y i nc l u s t e r s y s t e m sw h i c hi m p r o v et h e s y s t e mp e r f o r m a n c eb y b a l a n c i n gt h el o a db e t w e e nn o d e s d y n a m i cl o a db a l a n c i n gh a sb e c o m eah o t f i e l di nr e c e n t y e a r s ；i tm a k e sd i s t r i b u t i n gl o a dd e c i s i o n sa c e o r d i n gt ot h e s y s t e m s t a t ei n f o r m a t i o n s oi tc a ng e tb e t t e rp e r f o r m a n c e t h ed y n a m i cl o a db a l a n c i n g s y s t e mb a s e do ns u r p l u sc o m p u t a t i o n a l p o w e ri sad y n a m i cl o a db a l a n c i n gs y s t e mu s i n gan e wl o a di n d e xw h i c hi s t h e s u r p l u sc o m p u t a t i o n a lp o w e ro ft h en o d e t h en e wl o a di n d e xn o to n l yt a k e st h e s t a t u sr e s o u r c e si n t oa c c o u n tb u ta l s ot h en o d ec a p a b i l i t y s oi t p r e s e n t sc l u s t e r s y s t e mp r o c e s s i n ga b i l i t ya n dt h el o a db e i n gd e a lw i t hw e l la n db e t t e rf l e x i b l e t h a no t h e rl o a di n d e xi nl o a db a l a n c i n gs y t e m t h el o a di n f o r m a t i o no ft h es y s t e mi s c o l l e c t e dd i s p e r s e d l ya n dm a n a g e d c e n t r a l l y a l ln o d e sc o l l e c tl o a di n f o r m a t i o na n dr e p o r ti tt ot h ec e n t e r a ln o d et o f o r mi n f o r m a t i o nv e c t o rt a b l ea st h e i rs t a t eh a sc h a n g e d c e n t e r a ln o d em a k e s d e c i s i o n sa c c o r d i n gt ot h i st a b l e b e s i d e s ，w ec o m b i n e dt a s k s c h e d u l i n ga n d p r o c e s sm i g r a t i o nt og e tb e t t e rs y s t e mp e r f o r m c ea n dr e d u c ea d d i t i o n a lc o s to f l o a db a l a n c i n gs y s t e m t h ee x p e r i m e n tr e s u l t ss h o wt h a to u rl o a db a l a n c i n gs y s t e md e c r e a s e st h e e x e c u t i n gt i m eo ft a s k sa n di m p r o v e st h ec l u s t e r sp e r f o r m a n c ec o m p a r e dw i t h o t h e rs y s t e m s s oo u rl o a db a l a n c i n gs y s t e mc a ns o l v et h ec l u s t e rl o a db a l a n c i n g p r o b l e me f f e c t i v e l ya n df l e x i b l y o u rs y s t e mm a k e su ps o m ed e f e c t si ne x i s t i n g s y s t e m s k e yw o r d s ：c l u s t e r ；l o a db a l a n c i n g ； c o m p u t a t i o n a lp o w e r t a s ks h e d u l i n g ；p r o c e s sm i g r a t i o n ；s u r p l u s 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用己在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：州刨 日期：2 0 0 9 年月牛日 哈尔滨t 程大学硕十学位论文 第1 章绪论 1 1 课题背景及研究现状 本课题来源于哈尔滨工程大学基础研究基金：分布式计算机系统容错策 略的研究( h e u f t 0 5 0 0 9 ) 与哈尔滨工程大学基础平台建设开发项目：集群 计算系统研究。 随着计算技术的发展，计算机被应用到越来越广阔的领域。除了日常生 活中经常见到的计算办公应用之外，还存在一些非常复杂的领域，例如大型 科学计算、海量数据信息处理等，它们通常对计算机的处理能力有更高的要 求，常用的p c 机根本不能满足它们的需要。此时人们发现集群方式可以提 供更高的性价比，解决上述问题。在许多工业领域，如汽车、航空航天器的 设计制造，石油勘探、地震资料处理及国防( 核爆炸模拟) 等，科学计算已 经从昂贵专用的超级计算机转向集群系统，它是通过高速互联网络连接起来 的多台自治计算机和相关资源组成的高性能系统。对集群系统的研究正成为 一个新的研究方向。目前国外有一些成型的集群系统，如m o s i x 担1 、n o w 及b e o w u l f 等。 集群系统的主要目标是通过网络互连实现全系统范围内的资源共享，同 时通过高效的资源管理和任务分配技术实现资源的有效共享，提高系统资源 利用率，获得高性能。因此，资源的有效利用是集群系统软件研究的一个关 键性问题。负载均衡技术是解决上述问题的有效途径。负载均衡技术是2 0 世纪8 0 年代以来的研究热点，经过大量研究人员的深入研究，负载均衡技术 得到飞速的发展。同时，出现了许多负载均衡系统。 集群系统为尽量避免负载不均衡，必须采取合理有效的负载均衡措施。 数十年来，集群系统负载均衡相关方面的研究已经取得了不少进展n 。7 ，。在负 载均衡算法方面，研究人员已经提出一些可行且有效的算法策略，其中大都 是采用不同的技术手段对负载均衡的三个方面( 信息表示与获取问题、任务 迁移问题、节点定位问题) 进行处理。现有的这些算法都在某些方面对负载 哈尔滨i - 程1 3 人学硕+ 学位论文 均衡进行改进，提高了系统的效率。但现在的大多数算法还有一些缺陷： 有些算法本身太复杂，会带来较多额外开销，也不方便实施；有些算法可 能会带来系统颠簸，造成分布式系统的不稳定，影响任务的执行；算法的 通用性不够，一般只能应用于特定拓扑结构、特定规模的集群系统。因此， 在动态负载均衡算法策略方面还有必要进行进一步的研究来逐步解决上述这 些问题【。，。 为了能够在一定程度上解决诸如稳定性不够、算法应用面较局限且不灵 活等算法方面存在的问题，更好地改善集群系统的处理性能，本课题对集群 系统上的动态负载均衡问题进行研究。把任务分发调度和进程迁移策略结合 起来，从信息策略出发，对现有系统的信息策略和调度方法进行改造，提出 一个基于剩余计算能力的动态负载均衡系统。该系统有较好的灵活性、较强 的通用性、较少的通信代价等特性，在相当程度上减少网络通信的开销，获 得较好的负载均衡效果。 1 2 研究内容及任务 主要研究内容： 以集群系统、负载均衡、任务调度及进程迁移为主要研究内容。研究集 群系统中负载均衡技术，以剩余计算能力为依据，通过任务初始调度和进程 迁移的方法实现集群系统的动态负载均衡。 提出一种考虑到机器固有属性和系统当前负载两方面因素的负载均衡信 息评价策略，剩余计算能力信息策略。基于这种信息策略，提出一个具有代 价较小的动态负载均衡系统。系统结合任务调度和进程迁移两种工具，很好 的实现集群系统的负载均衡，并且使得系统在初始任务调度时就尽可能实现 负载均衡，减少进程迁移，减小系统由于迁移而增加的而外的开销。同时系 统使用就绪任务队列，在系统任务过重时，对到来的任务并不立即分配到后 台节点，这样使得后台节点能够处于高效的工作状态，提高系统效率。 主要任务： ( 1 ) 研究当前负载均衡算法的信息评价指标，提出一种剩余计算能力的 信息评价指标： 哈尔滨r 程大学硕十学位论文 ( 2 ) 提出一种本地分散收集，主控节点集中管理的信息策略，剩余计算 能力信息策略： ( 3 ) 基于剩余计算能力信息策略，提出一种结合调度和进程迁移的动态 负载均衡系统； ( 4 ) 研究动态负载均衡系统的任务调度机制和进程迁移机制； ( 5 ) 给出系统的设计和实现，并对实验结果进行分析。 1 3 论文组织结构 图1 1 给出了论文的组织结构。其中绪论和相关技术为本文的前序部分， 信息策略研究、基于剩余计算能力的动态负载均衡系统、系统的设计和实现 及系统测试及结果分析为本文的主体部分，结论是本文的结束部分。 匡囝藿零亟凰 论文主体部分 图1 1 论文组织结构 下面是本文的各章内容简要介绍。 第1 章是绪论。主要介绍课题背景及研究现状、论文的研究内容和论文 的组织结构三方面内容。 第2 章是相关技术。分别从集群、负载均衡、任务调度及进程迁移四个 方面阐述本文所要用到的相关技术。 哈尔暝1 程大学硕十学位论文 暑宣皇鼍暑i 宣i i ；昌；i ；i ；宣宣- s i n - - - - ii in 宣i i ；宣；i 宣皇宣i 罨葺皇；i ；i i 宣i i 皇j 第3 章是信息策略研究。讨论负载均衡算法中的信息策略。在讨论负载 评价策略、负载分类策略、负载收集策略以及负载管理策略之后，给出剩余 计算能力信息策略。 第4 章是基于剩余计算能力的动态负载均衡系统。根据第3 章的信息策 略，结合任务调度和进程迁移两种负载均衡手段，提出基于剩余计算能力的 动态负载均衡系统。 第5 章是系统的设计和实现。给出系统的总体设计以及各个子模块的设 计和实现。 第6 章是系统的测试和分析。介绍系统测试环境；根据系统测试结果及 分析得出本负载均衡系统与传统的负载均衡系统相比，提高了系统的性能。 最后是结论及展望。总结本文，指出本文需要进一步研究的内容。 4 哈尔滨1 ：程火学硕十学位论文 第2 章相关技术 本章主要介绍并分析负载均衡系统涉及的相关技术：集群技术、负载均 衡技术、任务调度技术以及进程迁移技术，为工作的进一步展开奠定基础。 2 1 集群技术 2 1 1 集群概述 集群系统是高性能网络或者l a n 进行物理连接的计算机的集合悟- o ，。集 合里的计算机又叫做节点( n o d e s ) ，这些计算机可以是工作站、服务器或普通 p c ，每个节点都有自己的存储器、i 0 设备和操作系统。集群各个节点必须 能够在一起协同工作，形成一个单一的、集成的系统资源，向用户提供低价 高效的高性能环境和快速可靠的服务。 集群计算机系统之所以能有如此快的发展速度，主要在于它具有其它并 行系统所无法比拟的优点，能够充分满足人们对计算机处理能力不断增长的 需求。集群系统的主要特点是： ( 1 ) 高可用性 即它们都能够在集群的一部分资源出现故障的情况下继续向用户提供持 续的服务。集群的组件都是廉价的商业化产品，因此可以提供冗余量大的高 可用性。 ( 2 ) 性价比高 集群系统良好的性能价格比是它受到人们青睐的重要因素，它可以把一 些廉价系统组合在一起协同工作，在总体上的性能却可以超过大型机甚至巨 型机。 ( 3 ) 易使用 集群系统的单个节点仍旧是传统的平台，所以用户可以在他们平时就很 熟悉的环境下面开发和运行应用程序。同时，这也可以让许多现有的程序可 以不加以修改地运行在处理能力强大的集群系统平台上，非常有利于保护用 哈尔滨t 程入学硕十学位论文 户已有的软件投资。 ( 4 ) 可扩展性好 当计算能力需要更高要求时，集群系统中的各个节点相对独立能够很方 便的通过添加节点的方式来达到计算性能的提高，从而实现了集群系统的可 扩展性。在系统规模扩大的同时提高系统性能这一点上，其它系统很难达到 与集群相同的效果。 2 1 2 集群分类 按照完成的功能不同，可以将集群系统分成下面三类： ( 1 ) 高性能集群 高性能集群应用在天气预报、地震模拟等需要大数据量运算的部门，主 要用来处理大规模数值计算，解决复杂的科学问题。在这种集群上运行的是 专门开发的并行应用程序，利用这些计算机的共同资源来完成计算任务，从 而可以解决单台计算机不能胜任的工作。 ( 2 ) 负载均衡集群 与高性能集群一样，负载均衡群集也在多节点之间分发计算处理负载。 它们之间的最大区别在于负载均衡集群缺少跨节点运行的并行程序。一般来 说，负载均衡集群的计算任务的粒度比科学计算集群要大一些。这种集群追 求的不是高速的计算能力，而是快速的事务处理和响应能力。它能够在多节 点之间分发网络或计算处理负载，从而提供和节点个数成正比的负载能力。 这种集群是随着i n t e m e t 的发展和网络负荷增加而产生的。负载均衡集群往 往也具有一定的高可用性特点，l v s 集群就属于这种类型。 ( 3 ) 高可用性集群 容错性是集群系统一个不可忽视的研究热点，高可用性集群的出现正是 为了使集群的整体服务尽可能不中断，主要考虑了整个系统硬件和软件的冗 余性和容错性。一般系统由主、备节点和共享存储器等组成，如果高可用性 群集中的主节点发生故障，那么这段时间内将由备用节点代替它。备用节点 通常是主节点的镜像，所以当它代替主节点时，它可以完全接管其身份，并 且系统环境对于用户是透明的。 6 哈尔滨1 ：程大学硕十学位论文 2 1 3 集群的组成和结构 集群系统是由专用或通用网络上一组互联的计算单元及相关的资源构成 的一个整体，可被用户视为单一的计算环境使用。集群系统的主要组件包 括：集群计算结点，高速网络，集群中间件，并行程序设计环境、编译器和 语言。 一般的集群系统结构如图2 1 所示： 图2 1 集群系统组成结构 网络接口硬件充当一个通信处理器并且负责在集群各节点之间通过网络 或者交换机收发数据包。 通信软件在集群各节点以及集群和外界之间提供一个快捷、可靠的数据 通信手段。具有特殊网络或者交换机的集群经常采用积极消息以便在节点间 实现快速通信。它们实际上绕过了操作系统，去掉很多的通信开销，从而给 用户提供了到网络的直接访问接口。 2 2 负载均衡技术 对于一个集群计算机系统，由于任务到达的随机性，以及各处理结点处 理能力上的差异，当系统运行一段时间后，某些结点分配的任务还很多( 称 哈尔滨r 稗大学硕十学位论文 之为超载) ，而另一些结点却是空闲的( 称之为轻载) 。一方面，使超载结点 上的任务尽可能快地完成是当务之急；另一方面，使某些结点空闲是一种浪 费。如何避免这种空闲与忙等待并存的情况，从而有效地提高系统的资源利 用率，减少任务地平均响应时间，这成为了负载均衡产生的原因。 2 2 1 负载均衡概述 负载均衡问题是一个经典的组合优化难题之一，其难度与h a m i l t o n 问题 相当，是一个n p 完全问题n ”。对各个集群系统节点进行负载均衡就是通过 任务分配与再分配实现各个节点负载的大致平衡，从而提高整个系统的性能， 在不影响节点的情况下，减少并行计算时间。所以采用有效的调度策略和进 程迁移算法来平衡各节点的负载，提高系统资源利用率和系统性能，也就成 为人们研究的热点之一u ”。 广义的负载均衡概念包括了负载共享“3 ，与负载均衡。负载共享的目标是 使分布式系统的运行速度最大化，因此，负载共享要避免和处理一些非理想 状态的情况：系统中一些计算机处于空闲状态而有些结点则负载过重。这种 非理想状态可以通过向空闲结点迁移任务来处理n ”。 与负载共享相比，负载均衡要求更高。负载均衡不仅要求系统的运行速 度最大化，而且要求系统中各结点的负载大致相等，负载均衡策略可以潜在 地减少任务的响应时间。但是要达到每个结点的负载大致相等，需要复杂的 算法，以及大量频繁的任务迁移，算法实现的难度以及任务迁移带来的负载 降低了负载均衡实现的意义。所以现在的负载均衡系统中实现的主要是负载 共享，但由于习惯的原因，仍称之为负载均衡算法。 2 。2 2 负载均衡分类 按照不同的分类方法，对于负载均衡有多种分类n “。 ( 1 ) 静态和动态 静态负载均衡策略一般是利用列举法、图论和排队论等技术产生较优的 调度方案，它不考虑系统的状态，而根据固定的策略( 如轮转法) 将新产生 的任务分派到各个节点，并且在分配后，任务不再迁移。这种策略的优点是 容易建立数学模型分析且易于实现，但是在分派任务时不考虑节点当前的负 哈尔滨r 程人学硕十学位论文 载状况，所以不能较好的达到负载均衡的目的，在某些情况下更会加剧节点 间负载的不平衡，导致集群系统性能较差。 静态负载均衡只有在任务数较少、可以一次分配完的情况下有效，而多 数情况下，集群系统中每个节点( 即处理机) 上的任务是动态产生的，每个 节点的负载大小是动态变化的，因此应主要采用动态负载均衡调度。相对来 说，动态负载均衡”“町系统是根据集群的负载状态动态的做出负载分配的决 定，因此能够将一个新产生的任务分派到最合适运行它的节点上去，更大地 提高系统的整体性能。动态负载均衡的优点是能充分发挥各处理机的能力， 提高整个系统的吞吐量，缺点是实现起来复杂程度高，会给各处理机带来额 外的开销，不过事实证明如果调度得当，这些额外开销对整个系统性能的改 善来说是值得的n 。 ( 2 ) 局部和全局 局部负载均衡处理单个处理器上的进程对时间片( 单元) 的分配。全局 负载均衡首先进行进程对处理器的分配，然后完成每个处理器内这些进程的 局部调度。 ( 3 ) 集中式和分散式 在集中式算法中，设置了一台主机专门负责系统的负载状况的收集和迁 移决策。在分散式算法中，这些工作被分配给不同的处理器。 2 2 3 负载均衡算法构成 一个典型的负载均衡算法包含以下四个部分： ( 1 ) 传送策略 传送策略用来决定一个结点是否适合参与一次任务的迁移，在这次迁移 中，结点可以作为发送结点，也可以作为接收结点。常用的传送策略使用阈 值策略。当一个结点产生一个新的任务时，传送策略判断该结点的负载是否 超过了上阈值t h ，需要成为发送结点迁移任务：与其对应的，当一个结点 的负载降到下阈值t l 以下，传送策略决定该结点是否可以加入系统的可用 结点集合，准备分担系统负载。t h 与t l 值可以不同，也可以是一个值。 除了阈值策略外，还有相对传送策略。相对传送策略考虑系统中节点的 负载差值。例如，当一个结点的负载与另个结点的负载差别大于了某个确 哈尔滨下程大学硕士学位论文 定的值c ，则启动任务迁移策略。一般可以将系统中负载最轻的结点作为接 收者。 ( 2 ) 选择策略 选择策略“o 】在传送策略之后启动。一旦传送策略确定了发送者之后，选 择策略负责从该结点选择一个待迁移任务，如果选择策略找不到合适的转移 任务，则该结点就不再被认为是发送者。最简单的选择策略方法是选择导致 该结点成为发送者的新任务作为转移任务，此时任务转移的开销较小。选择 策略要考虑以下两个因素：转移的额外开销尽量小；被选中的任务应该 可以运行足够长的时间，值得花去额外开销。 ( 3 ) 放置策略 放置策略即确定进程迁移的目的节点，最佳放置策略即将任务迁移到系 统中负载最轻的节点m “。在分布式策略中一个广泛使用的选择合适结点的方 法是“轮询”，一个结点向另外的结点询问对方是否适合作为传送搭档，这种 询问可以串行，也可以并行发送询问包。询问结点的选择可以基于上一次的 轮询信息，或者基于“最近邻居理论。可选择的方法是发送询问的广播包来 寻找可以任意一个负载均衡的可用结点。 在集中策略中，传送策略选中的结点与系统中的“管理者”联系，查询 并得到一个可用结点。系统中的这个“管理者”负责收集系统的所有信息， 传送策略使用这些信息来选择一个接收者。 ( 4 ) 信息策略 信息策略是负载均衡算法的核心部分，信息策略的好坏直接影响到负载 均衡系统的性能，一个好的信息策略可以使得系统的性能得到很大的提高。 集群系统的信息策略决定系统结点的信息何时被收集，从何处收集这些信息， 具体要收集哪些信息，以及收集到的信息如何管理。对于何时收集信息，典 型的有周期性收集策略和事件驱动策略；对于要收集哪些信息，对此已有大 量的研究工作，主要有资源利用率，c p u 对列长度等方式：管理收集到的信 息可以采用集中式管理，也可以采用分散式管理。 2 2 4 负载均衡实现方式 目前负载均衡常用的实现方式有下面三种：发送者主动策略、接收者主 1 0 哈尔滨r 程人学硕十学位论文 动策略、对称启动策略“_ 8 。 1 发送者主动策略 发送者主动策略由发送者来激发负载的分配，即当一个结点变成发送者 时，它主动去寻找接收者来接收自己的一部分负载。具体的说，把集群系统 中的所有节点均按阈值m 1 、m 2 划分为重载节点、轻载节点和适合节点，重 载节点指的是当前负载t m 2 的节点，轻载节点指的是t ， 直 图2 3 接收者策略 毫 接收者主动驱动策略的主要优点是：节点间不需要相互交换负载信息： 哈尔滨r r 程大学硕十学位论文 对于大规模并行计算问题，当每个节点均处于忙碌状态时，几乎不需要额外 调度开销；负载均衡的许多工作由空闲节点来完成，没有给忙节点增加较多 的额外负担。接收者驱动策略的主要缺点是：在开始和结束阶段时，任务数 相对较少，这样轻载节点比较多，会产生很多任务请求，这些任务请求会延 迟忙节点的执行时间。接收者驱动策略更适合于系统总负载较重的情况m - 。 3 对称启动算法 在任务的不断提交、分配和执行过程中，由于任务到来是不确定的，并 且系统负载情况会经常动态变化( 一般是前期和后期系统负载较轻，中期较 重) ，如果单一采用接收者驱动策略或者发送者驱动策略，则由于各自特点的 不同，两者都不能在整个过程中得到非常好的效果，所以根据系统负载情况 和任务运行进程，可以灵活使用这两种驱动策略，在不同的时期使用不同的 驱动策略，这也就是所谓对称启动算法。对称启动算法是前两种算法相结合 的产物，因而同时拥有前两种算法的优点和缺点，发送者和接收者均参与负 载的分配活动。在系统轻负载时，发送者主动算法有效，但接收者主动算法 需要支持抢先式任务转移，当系统重负载时，接收者主动算法有效，但发送 者主动算法会引起系统不稳定。它的性能在各种系统负载级上都好于或相当 于采用阈值定位策略的发送者主动算法，而在低、中度系统负载的情况下优 于接收者主动算法。 概括来说，在动态负载均衡算法中到底使用哪一种驱动策略，需要结合 算法的特点和系统运行时的状况：在任务提交的开始，一般先使用发送者驱 动策略；随着系统外任务的不断随机达到，当系统的总负载较高时，应该使 用接收者驱动策略，因为此时轻载节点少，更容易找到。现在较多的负载均 衡算法都采用混合( 双向) 驱动策略。轻载、重载的标准则根据不同系统由 用户指定或在运行过程中动态进行调整。因此即使是在同系统上，每一次 的大任务运行都可能得到不同的负载均衡效果。 2 3 任务调度技术 多任务的调度问题在计算机科学学领域虽然不是一个很新的课题但它还 一直是个远远没有得到很好解决的问题。它的根本问题是，当一个并行程序 哈尔滨工程人学硕十学位论文 实现一组任务后，就需要将它们合理或优化地分配到集群系统中的处理单元。 如果这个问题得不到解决则有可能导致分布计算效率低下，更有甚者，有可 能造成其效率不如单机计算，甚至计算失败因此，调度问题是分布计算的瓶 颈问题之一。 2 3 1 任务调度概述 在集群系统中，一个程序可以看成是一个任务集，这引起任务可以并行 或串行地执行。任务之间一般是有优先次序约束的。调度问题的目标是要在 满足一定的性能指标和优先约束关系的前提下，将可并行执行的任务按适当 分配策略确定一种分派和执行顺序，合理分配到各处理机上有序地执行，以 达到减少总的执行时间的目的。 性能和效率是评价调度系统的两个基本特征。应以任务分派的质量和调 度算法的效率为基础来评价调度系统。调度质量以产生的优化调度的性能为 基础来衡量；调度算法的效率以时间复杂性为基础来衡量。 2 3 2 任务调度常用算法 常用的任务调度算法有以下四种啪j ( 1 ) 轮询调度 轮询调度( r o u n d r o b i ns c h e d u l i n g ) 算法就是以轮询的方式依次将请求 调度不同的服务器，即每次调度执行i - ( i + 1 ) m o dn ( 其中n 为服务器总数) ， 并选出第i 台服务器。 但是，轮询调度总是假设所有服务器处理性能均相同，不管服务器的当 前连接数和响应时间。所以该算法不适用于服务器组中处理性能不一的情况， 而且当请求服务时间变化比较大时，轮询调度算法容易导致服务器间的负载 不平衡。 ( 2 ) 加权轮询调度 加权轮询调度( w e i g h t e dr o u n d - r o b i ns c h e d u l i n g ) 算法可以解决服务器 间处理性能不一的情况。它根据实际服务器的配置情况和处理能力，给每台 实际服务器指定一个整数类型的权值，此整数值用来标志服务器处理用户请 求的能力。在加权循环轮转分配用户请求时，优先把请求分配给权值大的服 1 4 哈尔滨。f ：程大学硕士学位论文 务器，权值大的服务器将被赋予更多的请求，一段时间后，各服务器处理的 请求数趋向于各自权值的比例。 它虽然考虑了系统中各个实际服务器处理能力的不同，但是没有考虑到 各个实际服务器不断变化的状态信息，因此当请求的服务时间变化很大，单 独的加权轮转调度算法依然会导致服务器间的负载不平衡。系统的性能也只 是比轮转调度算法的性能有了一定程度的提高。 ( 3 ) 最小连接调度 最小连接调度( l e a s t c o n n e c t i o ns c h e d u l i n g ) 算法是把新的连接请求分 配到当前连接数最小的服务器。最小连接调度是一种动态调度算法，它通过 服务器当前所活跃的连接数来估计服务器的负载情况。调度器需要记录各个 服务器已建立连接的数目，当一个请求被调度到某台服务器，其连接数加l ： 当连接中止或超时，其连接数减一。 最小链接调度虽然考虑了系统不断变化的状态信息，但是没有考虑到系 统中各个实际服务器处理能力的不同，因而可能出现某个实际服务器的连接 数虽然小，但它已经达到其处理能力的最大限度，如果此时依旧把任务分给 服务器，就会引起服务器进入不稳定状态，从而导致系统性能下降。 ( 4 ) 加权最小连接调度 加权最小连接调度( w e i g h t e dl e a s t c o n n e c t i o ns c h e d u l i n g ) 算法是最小 连接调度的超集。在最少连接法中，加入考虑实际服务器处理能力的因素， 给每台服务器赋予一个整型权值作为衡量标准。在分配用户请求时，负载均 衡器根据当前实际服务器的连接数目与其权值的比值，将用户请求分配给连 接数与权值比值最少的服务器。 算法既考虑到系统各个实际服务器处理能力的不同，也考虑了各个实际 服务器的状态信息，因此虽然算法比上面所述三种算法的复杂度稍微大些， 但是算法的有效性、并行性提高了，系统的性能也得到了相应的提高，而且 避免了最少连接法可能出现的实际服务器进入不稳定状态的问题。 2 4 进程迁移技术 负载均衡是在集群系统的多个计算结点间平均地分配计算任务的行为， 哈尔滨- i 仟ii 大学硕十学位论文 而进程迁移机制是负载均衡的实现机制。进程迁移可以实现集群系统负载的 动态分配，有效的共享系统资源。 2 4 1 进程迁移概述 所谓的进程迁移就是指，在进程运行过程中，根据系统的负载情况，将 活跃进程从负载较重的结点转移到负载较轻的结点继续执行的技术。 进程迁移是当进程运行时，在源结点与目标结点之间转移进程的行为。 由于在这个过程中转移的是活跃进程，因此又称为抢占式进程迁移。一般地， 进程在迁移之前必须停止，并使进程的状态能够被获取并转移到目标结点。 在目标结点，进程的执行信息被重建并开始执行。进程迁移的基本过程见图 2 4 ： 图2 4 进程迁移过程 进程迁移机制是集群系统一项重要技术，可以满足系统的实时性，实现 以下目标： ( 1 ) 提高系统负载均衡 在特定时间内，各主机负载具有不确定性，会出现负载不平衡。这时通 过进程迁移将超载结点进程迁移到欠载结点执行，才能使主机实时地计算任 务，实时地动态调度，使系统内部真正达到动态负载均衡，有效共享系统资 源。 ( 2 ) 实现高效率容错 在集群系统中，当一个主机发生故障时，则需要将该主机正在运行的进 程迁移到其它正常结点继续执行：否则，如果主机正在运行的是某些关键进 程，则这样有可能导致整个系统任务的错误运行，后果将不堪设想。 1 6 哈尔滨r 程人学硕十学位论文 ( 3 ) 改善系统管理 进程从将要关闭或者不可用的结点迁移到其它的结点继续执行，可以改 善系统的管理。 ( 4 ) 减少网络通信负载 当某一进程与其它进程存在通信，而与其通信的相对较多的进程不在同 一主机上，那么就将该进程进行迁移，从而减少整个网络通信的负载。 2 4 2 进程迁移算法 在目前进程迁移算法主要有贪婪拷贝算法、惰性拷贝算法、预拷贝算法 等1 。这几种算法的不同点主要体现在以下三个方面：需从源主机传输多 少状态到目标主机? 何时挂起在源主机上运行的进程? 何时启动在目标 主机上的进程? ( 1 ) 贪婪拷贝算法( e a g e rc o p y ) 先挂起源主机进程，然后传输进程的全部状态( 包括一些打开的文件、 执行状态等) 到目标主机后，再启动目标主机进程。这种算法简单，易于实 现，但有不足：延时较长，这对于实时系统是不可接受的；有些冗余数 据传输到目标主机后，实际并没有用上，造成网络负担。 ( 2 ) 惰性拷贝算法( l a z yc o p y ) 先传输进程在目标主机上重新执行所需要的最小相关信息。比起贪婪拷 贝算法，它传输的是必需的最少量的状态集合，然后在主机上启动。这些信 息通常是进程的部分或全部核心数据和一小部分( 二、三页) 地址空间。当 进程在目标主机上的执行需要其余状态信息时，再传输这些信息。其优点是 延迟小、网络负担少，缺点是会导致对源主机的剩余依赖性，因此不能提高 系统的可靠性。 ( 3 ) 预拷贝算法( p r e - c o p y ) 与前面两种算法不同的是，预拷贝算法在进程的部分或全部地址空间从 源主机到目标主机的传输完毕时，源主机才挂起进程并且传输核心数据。也 就是说，当进程在源主机上执行时，并行传输地址空间到目标主机上；进程 挂起后在传输的核心数据( 包括打开的文件、执行状态、当前目录等) 和一 些先前已经传输而后被改变的地址空间一起传输到目标主机上。这样就会产 哈尔滨i ：群大学硕十学位论文 生一个问题：这种算法虽然降低了进程挂起的时f a j ，避免因挂起时间长而导 致的开销和错误，但是却会将某些信息拷贝两次，总的传输时间反而增长。 2 5 本章小结 本章给出课题研究的相关技术：集群技术、负载均衡技术、任务调度技 术以及进程迁移技术。开始介绍系统研究的平台：集群环境，包括集群的概 念、分类以及组成结构；接着研究本文研究的主题：负载均衡技术，主要研 究了负载均衡算法的构成和实现方式。在接下来的两节中，介绍负载均衡的 实现手段：任务调度技术和进程迁移技术。 1 8 哈尔滨r f 程大学硕十学1 1 f 7 = 论文 第3 章信息策略研究 信息策略是负载均衡算法的重要组成部分，是集群负载均衡的基础。信 息策略主要负责负载信息的获取、管理和使用，以作为集群负载均衡系统均 衡决策的依据。信息策略的好坏直接决定着负载均衡算法的优劣，影响着集 群系统的性能。本章内容主要介绍负载信息的评价策略、分类策略、收集策 略和管理策略，最后给出剩余计算能力信息策略。 3 1 负载信息评价策略 在负载信息收集算法中，如何选取能够有效的代表结点资源使用状况的 资源负载指标非常重要，这种指标一般被称为负载向量。常用的负载向量有 c p u 队列长度、平均c p u 队列长度、可用内存大小、c p u 及内存利用率等。 研究者发现使用不同的负载向量对于负载均衡算法的性能有重大的影响，而 且在不同的环境中使用不同的负载评价指标会有不同的效果n 。 选择一个负载评价的指标，要考虑两方面的内容：该指标能否及时准 确地表示出当前的节点机负载：收集、处理这些信息所增加的额外负载。 以下为几种常用的负载信息评价指标“5 ： 3 1 1 资源利用率 负载均衡的目的是缩短任务响应时间及提高集群系统的资源利用率，所 以很多研究从资源使用情况入手选择负载向量。通常使用资源利用率负载指 标有c p u 、内存及i o 等。 ( 1 ) c p u 资源 c p u 是计算机中最重要的资源之一，早期对于负载向量的研究都考虑到 c p u 的利用率陪圳作为节点负载评价的标准。c p u 的利用率根据系统使用的 时钟数比时钟总数得到，在资源异构的系统中，各个节点拥有c p u 的数量及 处理速度均不同，所以在使用c p u 利用率做负载向量时，需要考虑这些差异。 ( 2 ) 内存资源 哈尔滨t 程大学硕+ 学位论文 处理器和存储器问速度的差距相当大，一次内存缺页或者一个页错花费 的延迟是普通一次访问命中延迟的1 0 0 0 倍。当前应用中对数据访问的需求在 不断增长，数据访问及数据移动操作带来的负荷( 如访问缺页) 已经非常大， 因此如果在负载均衡算法中不仔细考虑内存资源，则集群系统的总体性能会 有显著的降低。 考虑内存资源作为负载向量时，主要是从应用的角度考虑对内存大小的 需求，所以内存利用率无法确定可用内存的大小，一般考虑绝对的剩余空间。 ( 3 ) 其它资源 其它资源还有网络资源，i o 资源等，一般来说，使用资源负载向量是 与系统中负载、作业类型相关的，如果系统中主要是计算类型的作业，那么 使用c p u 资源作为负载向量效果较好，而使用i 0 资源评价系统负载则不准 确。 3 1 2 队列长度 使用资源使用情况作为评价负载的指标其实是评价节点在某个时刻的状 态。而使用队列长度，则是从资源的使用者一作业( 进程) 的角度考虑的， 一种带有预测性质的负载评价。如果队列中任务数较多，那么就推断该节点 负载重。这种预测也会存在一些问题，例如队列中有很多任务，而每个任务 只占用非常少的资源，则评价有失准确。 队列长度包括c p u 队列长度。、i o 队列长度等，这里只讨论c p u 队 列长度。c p u 队列长度普遍被认为是当前最优的负载均衡指标，其参数容易 获取，用于搜集和处理该信息的开销小，且容易建立数学模型进行分析。使 用c p u 队列长度一般有两种：即使用当前瞬时的c p u 队列长度和使用一段 时间内的平均c p u 队列长度。 使用队列长度，即当前节点上运行任务的个数作为负载向量有以下两个 不足：忽略了节点机性能的差异，这有点可以和上面c p u 利用率相似的考 虑；忽略了任务大小的不同。 3 1 3 综合负载评价策略 综合策略一般指同时考虑多项负载指标，以多种简单的负载向量为基准， 哈尔滨t 科人学硕十学位论文 通过加权计算最后得出一个负载的综合值。 综合负载向量有两种：第一种是以上两种策略中多种指标的综合，比如， 使用队列长度时，既考虑c p u 队列长度，又考虑i o 队列长度，或者在使用 资源利用率时，一般考虑多种资源：第二种是完全的综合，既考虑队列长度， 又考虑资源使用情况。对于简单负载向量的综合一般使用线性函数，如有1 1 种单一负载向量l l ，l 2 ，l 。，则一般使用函数 f ( l l ，l 2 ，l 。) 2 l _ i * e t l + l 2 * o t 2 ，l 。幸0 i 。( 3 一1 ) 可以同样地设置阈值，在节点负载超过这一阈值，或者两节点负载差超 过这一阈值时启动平衡策略。函数中使用的系数qi ( i = 1 ，2 ，n ) 有两个作 用，首先是使各种负载向量的数量级平衡，由于各种负载向量由于类别不同， 数量差异很大的，如c p u 队列长度一般小于1 0 ，或者是几十，而实际系统 中节点剩余内存的大小在几十兆字节左右。所以系数q 首先要调节这种数量 级上的差异；其次，系数要能够确定每种负载向量在函数中的比例。 另外的一种综合负载向量是考虑多种资源的优先级。例如，优先考虑任 务对于内存的需求，在保证有足够内存空间的情况下，再考虑c