（计算机软件与理论专业论文）基于层次策略的动态负载均衡算法研究.pdf

摘要 随着计算机及网络技术的发展，大规模并行分布式处理系统得到了广泛的应用。对于一个分布 式系统而言，多个节点之闻如何进行动态的任务分配调度，即动态负载均衡，在很大程度上影响着 系统的性能，因而具有较高的理论研究价值和应用前景，受到了人们长期的关注。近年来，各国研 究人员对此进行了大量的研究，提出了一系列的动态负载均衡算法。但这些算法并没有完全解决目 前存在的问题，因此仍有必要对分布式系统的动态负载均衡进行进一步的研究。 本文对负载均衡所涉及的各个方面，包括概念、分类、特点、算法机制、驱动策略、难点、算 法步骤等进行了详细的讨论，总结了负载均衡的研究现状，同时还重点分析比较了现有的多个静态 和动态负载均衡算法，指出了它们各自的特点和缺陷。 在上述讨论的基础之上，本文从网络基础体系结构拓扑出发，通过对常见的网孔、超立方 和网状拓扑进行逻辑上的改造，根据本文中所给法则将物理拓扑划分为多个物理区域并指定每个区 域的信息中心节点，必要对对这些信息中心节点组成的二级逻辑分区再指定二级信息中心节点，依 此类推。最后使得物理拓扑形成逻辑上的层次结构。通过推导和计算可以证明，网络上的通信经这 样的层次处理后，能够从局部区域扩展到整体，确实减少了很多基础的通信开销。 基于上述的层次方法，本文提出了一个新的动态负载均衡算法，能够较好解决已有算法的诸如 稳定性不够、应用比较单一、通用性不够等缺陷和不足。在此基础之上，本文还提出了一个基于预 测的算法机制，该机制能够应用于均衡算法使得节点负载信息能够被准确及时的获取，从而为任务 的迁移提供更好的依据；并由此建立了一个基于预测的层次负载均衡模型。算法的主要思想是通过 各个局部区域的优化达到系统整体的接近最优化并特别考虑了任务之间的相互关系和系统内节点性 能可能存在的差异；算法还通过改进传统的驱动策略，使用新的任务调度规则，在改善底层通信的 基础上，使得系统减少了较多的额外开销，提高了算法的效率。该算法的主要特点是： ( 1 ) 自适应参数可调。算法不是单一的使用某种驱动策略，两是在系统运行过程中动态调整负载 阈值和参数，视用户对系统的要求选择参数值，从而获得更好的性能表现。 ( 2 ) 系统稳定，不会出现颠簸。算法中局部区域的使用，使得节点处理机上任务的迁移首先在内 部区域上进行，必要时再进行区域之间的迁移；同时算法改进了以往的驱动策略，迁移必须从重载 节点到轻载节点，目的性强，避免了一些效率不商的迁移和对节点不必要的打扰。 ( 3 ) 简单实用。算法没有采用基于人工智能理论等耗费较大的调度方法，而是使用局部优化带动 全局优化的思想方法和较有针对性的“极端”任务调度方法，除了增加一定空间耗费和任务迁移本 身带来的通信路径上的开销外，额外开销比较少。 ( 4 ) 具有较好的通用性。算法可以适用于目前最常见的网孔和超立方拓扑构成的同构、异构分布 式系统，也可以推广到最一般的网状拓扑。 论文还通过实验比较和实例分析验证了层次策略负载均衡算法的正确性和有效性。因此，本文 提出的层次策略负载均衡算法确实能够比较有效和灵活地解决分布式系统的负载均衡问题，从而弥 补了现有算法存在的一些缺陷。 关键词：分布式系统，负载均衡，层次策略，拓扑，网孔，超立方，网状 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e ra n dn e t w o r kt e c h n o l o g y , l a r g e - s c a l ep a r a l l e ld i s l r i b u t e dp r o c e s s i n g a y s t c mh a sb e e ne x t e n s i v e l ya p p l i e d f o ro n ed i s t r i b u t e ds y s t e r n ，h o wt od y n a m i c a l l ya s s i g na n ds c h e d u l e t h et a s k sa m o n gt h en o d e s ，t h a ti s ，d y n a m i cl o a db a l a n c i n g ，h a sm u c hi n f l u e n c et ot h ep e r f o r m a n c eo f s y s t e m l o a db a l a n c i n gh a sal o to fr e s e a r c hv a l u ei nt h e o r ya n da p p l i c a t i o n p e o p l eh a v en o t i c e di tf o ra l o n gw h i l e i nr e c e n ty e a r sm a n yr e s e s m h e ro f s o m ec o u n t r i e sh a v ee n g a g e di ni ta n dp u tf o r w a r ds e r i e so f d y n a m i cl o a db a l a n c i n ga l g o r i t h m s b e c a u s e t h o s ea l g o r i t h m sd i d n ts o l v et h e e x i s t i n gp r o b l e m s c o r n p l e t e l ys ow em u s t d ot h er e s e a r c hf o rd y n a m i cl o a db a l a n c i n go f d i s t r i b u t e ds y s t e mm o l ee x t e n s i v e l y m a n ya s p e c t sa b o u tl o a db a l a n c i n g a r ep a r t i c u l a r l yd i s c u s s e d ，i n c l u d i n gc o n c e p t ，c l a s s i f i c a t i o n ， c h a r a c t e r i s t i c ，a l g o r i t h mm e c h a n i s m ，d r i v e ns t r a t e g y , d i f f i c u l t y ，a p p r o a c h ，e t c ，r e s e a r c ha c t u a l i t yf o rl o a d b a l a n c i n gi ss u m m a r i z e da n dm a n ye x i s t i n gs m f i ca n dd y n a m i cl o a db a l a n c i n ga l g o r i t h m sa 指c o m p a r e d t h o s ea l g o r i t h m sa r ep o i n t e dl l l e i ra d v a n t a g e sa n dd i s a d v a n t a g e s o nt h i sb a s e ，f r o mt h en e t w o r ka r c h i t e c t u r e , t h a ti s ，t o p o l o g y , s o m el o g i ca l t e r a t i o ni sd o n ei nc o m m o n m e s h ，h y p e f c u b ea n dn e tt o p o l o g y b yc e r t a i np r i n t i p l ep h y s i o a lt o p o l o g yi sp a r t i t i o n e di n t om a n yr e g i o n s a n do n ei n f o r m a t i o nc e n t r a ln o d ei ss e l e c t e df o re v e r yr e g i o n t h o s ci n f o r m a t i o nc e n t r a ln o d e sf o r mt h e s e c o n dl o g i or e g i o n sa n di n f o r m a t i o nc e n t r a ln o d ei ss e l e c t e da g a i ni fn e c e s s a r y , a n ds oo n f i n a l l yl o g i c h i e r a r c h i c a ls l n c l t t t ei sc o m ei n t ob e i n go n 曲y s i e a lt o p o l o g yf i n a l b - b yr e a s o n i n ga n dc o m p u t i n gt o a p p r o v et h a tc o m m u n i c a t i o n0 1 1n e t w o r kc a ns p r e a df r o ml o c a lr e g i o nt ot o t a lt o p o l o g yb yt h ew a yo f p a r t i t i o na n dm a n yb a s i cc o m m u n i c a t i o nc o s t sa i 己r e d u c e d o nt h eb a s eo f h i e r a r c h i o a lw a y , an 钾d y n a m i cl o a d b a l a n c i n ga l g o r i t h mi sp r o p o s e d t h ea l g o r i t h mc a l l s o l v es o m ed i s a d v a n t a g e ss u c h 鹋l a c ko f s t a b i l i t y , l a c ko f a g i l i t y 1 a c ko f g e n e r a li ne x i s t i n ga l g o r i t h m s o n t h i sb a s e o n ea l g o r i t h mm e c h a n i s mb a s eo f p r e d i c t i o ni sp r o p o s e d t h em e c h a n i s mc a nb ea p p l i e di nl o a d b a l a n c i n ga l g o r i t h mt om a k et h e1 0 a di n f o r m a t i o no nn o d ek n o w ne x a c t l ya n db e t i m e s t h em e c h a n i s m a l s op r o v i d e sb a t t e rb a s i sf o rt h et r a n s f e ra m o n gt h en o d e s t h e no n ed y n a m i cl o a db a l a n c i n gm o d e lb a s i n g p r e d i c t i o na n du s i n gh i e r a r c h i c a lw a yi sb u i l t t h em a i nt h i n k i n go fa l g o r i t h mi sb yl o c a l1 e g i o n s o p t i m i z a t i o n t oa c h i e v ew h o l es y s t e m sn c 8 l o p a m i z a t i o n t h er e l a t i o n s h i pb e i t 3 v o e nt a s k sa n dt h e d i f f e r e n c eo fn o d e si ns y s t e ma i ec o n s i d e r e d t h ea l g o r i t h mi m p r o v e st h et r a d i t i o n a ld r i v e ns t r a t e g ya n d u s en e ws c h e d u l er u l e sa m o n gt a s k s o nb a s eo f r a d u c i n gb a s i cc o m m u n i c a t i o nc o s t s ，t h ea l g o r i t h mr d u c m u c ha d d i t i o n a lc o s t so fs y s t e ma n de n i 埔皿。髂t h ee f f i c i e n c yo fi t s e l f t h em a l nc h a r a c t e r i s t i c so ft h e a l g o r i t h ma r e ： ( 1 ) s e l f - a d a p t i v ea n dp a r a m e t e rv a r i a t i o n a l t h ea l g o r i t h mu s e sn o ts i n g l ed r i v e ns t r a t e g yb u ta d j u s t l o a d i n gt h r e s h o l da n dp a r a m e t e r sd y n a m i c a l l yi nt h ep r o c e s so fs y s t e mr u n n i n g u s e r sc a l ls e l e c tt h e v a l u e o f p a r a m e t e r s a c c o r d i n g t o t h e d e m a n d f o rs y s t e z n t h e no b t a i n e x c e l l e n t p e r f o r m a n c e ( 2 ) s y s t e ms t a b l ea n d n ot h r a s h t h en s eo f l o c e lr e g i o ni na l g o r i t h mm a k et h et r a n s f e rf o rt a s k sa m o n gt h e n o d e so c c u r 8i nl o c a lr e g i o n sf n s t l ya n dt r a n s f e rb e i w e c nt h e1 g i o n so e c r l r $ i f n e c e s s a r y b e s i d e st h e a l g o r i t h mi m p r o v et h ef o r m e rd r i v e ns t r a t e g yt om a k et h et r a n s f e rm u s tf r o mo v e rl o a d i n gn o d e st o 1 i g h tl o a d i n gn o d e s t h i sm e t h n d sp u r p o s ei ss t r o n g i ta v o i d ss o m et r a n s f e ro fl o we f f i c i e n c ya n d u n n e c e s s a r yd i s t u r b a n c et on o d e s ( 3 ) s i m p l ea n dp r a c t i c a l t h ea l g o r i t h ma d o p t sn o ts c h e d u l em e t h o dw i t hm a n yc o s t ss u c ha sa it h e o r yb u t t h et h i n k i n go f f r o ml c o a lo p t i m i z a t i o nt ow h o l eo p t i m i z a t i o na n do n ee x t r e m es c h e d u l em e t h o dw i t h p e r t i n e n c e t h ea l g o r i t h mo n l yi n c r e a s e ss o m es p a c ec o s t sa n dt h ec o s t so fc o m m u n i c a t i o nr o u t ef o r t a s k st r a n s f e r t h ea d d i t i o n a lc o s t sa r ef e w ( 4 ) g e n e r a l t h ea l g o r i t h mc a nb ea p p l i e do ni s o m o r p h i ca n di s o m e r o u sd i s t r i b u t e ds y s t e m sc o m p o s e do f m o s tc o m m o nm e s ha n dh y p e m u b a i tc a nb ea p p l i e do ng e n e r a ln e tt o p o l o g y 1 1 s o m ec x p c r i n l e i l t sf o rc o l n p a r i s o na n di n s t a n c e sf o ra n a l y s i sa r cd o n et ov a l i d a t et h ee x a c t n p _ 镕sa n d a v a i l a b i l i t yo f h i e r a r c h i e a ls t r a t e g yl o a db a l a n c i n ga l g o r i t h m s i n c et h eh i e r a r c h i c a ls t r a t e g yl o a db a l a n c i n g a l g o r i t h mc a l li n d e e ds o l v et h ep r o b l e mo fl o a db a l a n c i n gf o rd i s t r i b u t e ds y s t e m sa v a i l a b l ea n df l e x i b l e t h ea l g o r i t h mm a k e su ps o m ed e f o e t si ne x i s t i n ga l g o d t h r a s k e yw o r d s ：d i s t r i b u t e ds y s t e m ，l o a d i n gb a l a n c i n g ，h i e r a r c h i c a ls t r a t e g y , t o p o l o g y , m e s h ，h y p e r c u b e ， n e t l i l 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 研究生签名：3 蒸日期： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容，论文的公布( 包括列登) 授权东南大学研 究生院办理。 研究生签名： 3i 塾 导师签名：期：递3 1 1 诋 第章引言 1 1 研究背景 第一章引言 随着信息技术的发展和工业技术的需求推动，分布式系统的各项技术一直有着很快的发展，这 方面的研究也在持续不断的深入。分布式系统以其结构灵活、程序并行、并行任务派生、进程同步、 资源分配和进程调度等特点大量应用于科学计算的重大课题，如全球气候预报、基因工程、飞行动 力学、海洋环流、流体动力学、超导建模、半导体建模、量子染色动力学和视觉等【1 口6 j 口”。常见的 分布式系统有对称多处理机系统( s y m m e t r i cm u l t ip r o c e s s i n g ，s m p ) 和大规模并行处理系统 ( m a s s i v e l yp a r a l l e lp r o c e s s i n g ，m p p ) 等。 在分布式系统上提交的各项任务如何快速有效合理的运行，得至i 用户想要的结果，除了依赖于 系统本身。包括系统规模，各处理单元的运算能力，互连网络和并行算法外，关键在于对负载的调 度和管理。 当用户提交任务给系统，我们希望能够得到最小的平均任务响应时间，也就是说用户不关心各 个任务是如何在分布式系统上执行的，他们关心的是能不能够尽快得到计算结果。因此，我们应该 努力使得各个处理单元上的任务尽可能同时完成，即所有的处理单元在任务提交后尽量繁忙，而整 个过程对用户是透明的。 由于任务大小的不同、任务何时到达系统的不确定性、系统中各节点( 即处理单元，可以是一 台计算机或处理杌) 处理能力的不同、各任务之间通信耗费的不同，即使一开始比较平均地分配任 务，但各节点的负载也可能逐渐出现不均衡现象，即有些节点上等待执行的任务很多而有的节点却 空闲。若系统出现负载不均衡的情况丽不加以改进，任务的完成就会被大大延迟，影响分布式系统 的效率和性能。 为尽量避免负载不均衡，我们必须采取合理有效的任务调度和负载均衡措施。总体上看，任务 调度有两种策略：静态分配策略和动态分配策略。静态分配策略是在系统运行的初始时刻，综合考 虑系统各节点处理单元的能力和任务在其上的执行时间，将用户要提交的任务一次性的、尽量均匀 的分配给系统中各处理单元，运行过程中不干预任务在各处理单元的执行。静态分配策略的特点是 实现原理简单，但其效果有限，很容易造成负载不均衡。动态分配策略是指在系统运行过程中将任 务分配给多个处理单元，并对各处理单元上的任务数进行动态调整，尽可能使系统中各单元的负载 达到平衡，一般称其为动态负载均衡，亦称动态负载平衡。 如何进行动态负载均衡? 要完成这一任务，主要可以归结为三个问题：信息问题，即该用什 么样的信息来表示节点负载? 这些信息又如何获得? 迁移问题，即需要进行节点处理单元之间的 任务迁移时，该选择哪些任务进行迁移? 定位问题，即任务迁移的源节点和目标节点该如何选择? 解决以上这三个问题是实施动态负载均衡的核心。而动态负载均衡算法是对这三个问题解决方 式的集中描述，其性能将直接影响负载均衡的效果，因此本文的研究重点是动态负载均衡算法。在 整个动态负载调度过程中将会产生大量的开销，如任务之间通信的时间开销。处理机之间通信的时 间开销任务迁移的时间开销以及动态均衡算法带来的额外时空开销。如何减少这些开销是提高系 统性能的重要因素，因此是我们需要解决的重点问题。 数十年来，分布式系统负载均衡相关方面的研究已经取得了不少进展，在负载均衡的分类、策 略、实施要素、模型、技术实现、基本研究方法等方蕊都已经有了较多的理论成果。在负载均衡算 法方面，研究人员已经提出一些可行且有效的算法策略，其中大都是采用不同的技术手段对负载均 衡的三个方面( 信息表示与获取问题、任务迁移问题、节点定位问题) 进行处理。现有的这些算法 都在某些方面对负载均衡进行了改进，提高了系统的效率。但现在的大多数算法还有一些缺陷： 有些算法本身太复杂，会带来较多额外开销，也不方便实施。有些算法可能会带来系统颠簸，造 l 东南大学硕士学位论文 成分布式系统的不稳定，影响任务的执行。算法的通用性不够，一般只能应用于特定拓扑、特定 规模的分布式系统。因此，在动态负载均衡算法策略方匾还有必要进行进一步的研究来逐步解决上 述这些问题。 为了能够在一定程度上解决诸如稳定性不够、算法应用面较局限且不灵活等算法方面存在的问 题，更好地改善分布式系统的处理性能，本文对分布式系统上的动态负载均衡问题进行了研究。由 于系统的分布特性、互连网络拓扑的多样性和任务到来的不确定性，该问题是一个n p 完全问题m 】， 目前不可能有多项式时间复杂度的解决方法，因此需要使用一些优化方法来获取近似最优解。本文 把局部策略和自适应思想结合起来，从网络基础结构拓扑出发，对系统结构进行逻辑上的层次 优化改造，并在所给层次方法的基础上提出了一个层砍策略动态负载均衡算法，该算法有稳定性较 好、通用性较强、比较灵活等特性，使得系绕在相当程度上减少了网络通信的开销，获得了较好的 负载均衡效果。 1 2 论文的目标 本文以分布式系统为研究对象，以负载均衡为研究点。分布式系统的拓扑多种多样，规模也大 小不一，现有的动态负载均衡算法很少从拓扑结构出发进行研究，因此在通用性方面存在不足：现 有算法有的缺少稳定性，即系统可自会出现颠簸，而稳定性是能够达到负载均衡目的的首要要求： 现有算法大都不具有良好的灵活性，使得应用单一化：在负载信息的获取方面存在一个负载信息“过 时”的难点，即经常不能得到节点及时正确的负载状况，为后面的决策留下了隐患。 根据上述情况，本文制定了如下的目标： ( 1 ) 对网络拓扑使用一种新的层次构造方法，优化网络结构； ( 2 ) j 是出新的层次策略负载均衡算法，在稳定性、灵活性、动态调节性等方面要优于已有算法： ( 3 ) j 是出信息获取的预测机制并改进驱动策略，提出基于预测的层次负载均衡模型。 1 3 论文的研究内容和组织结构 本论文主要针对s m p 和m p p 系统的动态负载均衡问题进行分析和研究，从网络基础体系结构 改造的角度出发，通过对典型的网孔、超立方拓扑进行分层优化。在相当程度上减少了网络上的通 信开销，结合局部优化策略的使用，围绕负载均衡的难点问题，提出一个新的负载均衡算法一层 次策略负载均衡算法，并对基于预测的驱动策略进行了一定的探索。最后通过实验对算法的性能进 行了分析研究。层次策略负载均衡算法的主要优点和改进在于： ( 1 ) 在负载信息的收集上，我们采用运行队列中的任务数作为负载衡量的标准，避免了由于采集 过多参数可能导致的性能反而下降的缺点； ( 2 ) 任务的迁移有别于接收者驱动和发送者驱动，采用一定条件下的双向驱动策略，任务的迁移 一定要满足从超载节点到轻载节点才开始发生，避免了对节点不必要的打扰，并考虑了任务之间的 关联关系： ( 3 ) 任务的迁移首先在局部进行，避免了经常性的长路径迁移，减少了开销： ( 4 ) 可以根据用户的需要动态调整负载参数，具有一定的灵活性，避免了算法使用单一性的缺点。 本文各章的主要内容如下： 第一章f 引言j 介绍了分布式系统负载均衡课题的研究背景、研究意义和研究现状。指出了现 有负载均衡算法的不足之处，阐述了本论文的主要目标，对本文所做工作进行综合概括并简介各章 主要内容。 第二章r 分布式系统动态负载均衡】介绍了该领域的研究现状，对负载均衡的相关问题，包括 分类、特点、算法机制、算法驱动策略、算法难点、算法要求、算法步骤等，进行了综合阐述。对 已有的静态、动态负载均衡策略进行了描述和评价。 2 第一章引言 第三章r 分布式系统网络拓扑与层次方法j 介绍了常用网络拓扑结构以及作者所研究的层次方 去，以及对网孔、超立方和一般的网状拓扑进行的分层优化处理。同时分析讨论了层次方法的优缺 点。 第四章r 典型拓扑层次策略动态负载均衡j 介绍了作者将层次方法应用于一些典型网络拓扑的 情况、特别是作者提出的层次策略动态负载均衡算法、关于其有效性所作的理论证明；以及针对负 载信息收集的“过时”问题所提出的个基于预测的层次负载均衡模型、对实例进行的模拟仿真实 验和实验结果的分析。 第五章r 总结与展望j 对本论文工作进行了总结归纳，分析比较了层次方法和其他方法的优势 与不足，并指出进一步的研究方向。 3 东南大学硕士学位论文 第二章分布式系统动态负载均衡 正如前文所述为了提高分布式系统的性能和增加系统吞吐量，就必须采取有效的调度策略来 平衡各节点处理机的负载( 即负载均衡) ，从而才能使得整个系统资源的利用率得到提高。近年来， 由于是否能够很好地处理负载均衡问题将直接影响到系统性能的好坏，再加上研究对象的分布特性， 因此负载均衡的研究。已成为人们的研究热点。本章我们将从多方面( 概念、研究方法、已有成果 等) 讨论分布式系统的负载均衡问题，其中包括负载均衡的概念，负载均衡的分类、特点以及算法 机制，负载均衡算法中的驱动策略、实现动态负载均衡的难点、算法要求和算法步骤。在此基础之 上，我们对现有的静态、动态负载均衡算法进行分析和比较，并指出这些算法各自的优缺点。 2 1 负载均衡问题概述 2 1 1 负载均衡的概念 分布式系统中的负载均衡问题是一个经典的组合优化难题，在过去的二十多年中，各国研究人 员对此问题进行了大量的研究工作，提出多种解决负载不平衡的算法。一个分布式系统可以被看作 是由多个用户动态共享的计算和通信资源的集合，随着对系统计算能力需求的不断增长，负载均衡 变得越来越重要。通常对该问题的描述是：给定很大数量的一批任务，找到一种把任务分配给各个 处理机的方法，使得对于一个给定的目标函数( 譬如总执行时间) ，对处理机的分配方式进行最优化 处理i l ”。具体来说，分布式系统负载均衡问题可以描述如下。 如图1 所示，( t l ，t 2 ，, t i n ) 是一组待处理的任务模块，( p i , p 2 ，in ) 是分布式系统的n 个处 理机，通常m n 。处理机之间按照一定的拓扑形式进行通信，任务分配机制s 把m 个任务模块分配 给n 个处理机。要求考虑如何在各个处理机间实现任务的均衡分配，从而使完成整个任务的代价晟 小。一般这m 个任务模块是由一个大的任务分解而来的。位于不同处理机上的模块信息交换是通过 处理机彼此间通信来实现的。 通 信 网 络 图1 分布式系统示意图 用在处理机通信上的耗费通常可分为两类：i p c 和i m c 。 i p c ( i n t e r p r o c e s s o rc o m r a u n i e a t i o n ，处理机闻通信) 开销是由不同处理规上的模块之间相互传 递信息所引起的。此种通信会占用大小不等的系统资源，通信路径长度越长则开销越大。i m c ( i n t e r m o d u l ec o m m u n i c a t i o n ，模块问通信) 开销是由于任务模块间进行同步协调时进行通信所导 致的。当两个模块被分配到同一个处理机上时，它们之间的i m c 不会引起i p c ；如果两个模块在不 同的处理机上，它们之间的i m c 就会引起i p c 。所以应该将i m c 开销较大的模块尽量分配到一个处 理机上。极端情况是把所有模块都放在一个处理机上执行，这样当然i p c 开销最小，但整个系统性 能却会变得很差，而均衡负载就是要把各个任务模块尽可能“平均”地分配给各处理机，使得各处 理机能够充分得到利用，从而提高系统吞吐量。因此，减少i p c 和进行均衡负载是两个彼此之间有 4 第二章分布式系统动态负载均衡 冲突的目标，而任务调度就是要在这两者之间作协调处理，以使整个系统的性能达到最优。 2 1 2 负载均衡的分类与特点 负载均衡任务调度有静态任务调度和动态任务调度两种。静态任务调度是指在任务提交前就分 配好处理机，在执行过程中并不进行任务的迁移。动态分配调度是指在运行过程中将任务分配给多 个处理机，并对其上的任务数进行动态调整，尽可能使系统中各处理器上的负载达到平衡，一般就 称为动态负载均衡或动态负载平衡。静态任务调度只有在任务数较少、可以一次分配完的情况下有 效，而多数情况下，分布式系统中每个节点( 即处理机) 上的任务是动态产生的，每个节点的负载 大小是动态变化的，因此应主要采用动态负载均衡调度。在完成任务的过程中，调度算法周期性地 检查任务完成的情况，并与其他节点交互这些信息。在此基础之上，算法按照一定原则确定是否对 任务进行迁移，并在需要迁移时确定迁移的源、目的节点和迁移量。 静态任务调度的优点是简单容易实现，其缺点是适用范围狭窄，在大多情况下得不到很好的效 果；动态负载均衡的优点是能充分发挥各处理机的能力，提高整个系统的吞吐量，缺点是实现起来 复杂程度高，会给各处理机带来额外的开销，不过事实证明如果调度得当，这些额外开销对整个系 统性能的改善来说是值得的田j 【删。 2 1 3 负载均衡的算法机制 就分布式系统规模而言，小到紧耦合的多处理机，大到地理上分布极广的计算网格，如何通过 负载均衡算法来进行系统资源( 计算机，存储器等) 的分配调度是一个必须考虑的问题。系统资源 是分布的由利己主义的a g e n t 或组织( o r g a n i z a t i o n ) 拥有的。这些a g e m t 或组织，为了它们自己的利 益( 获得更多的资源) 操控资源分配算法，可能会使得某些已经得到调度执行的任务由于资源的不 足而无法执行，因此a g e n t 的自私行为可能会导致严重的系统性能降低和效率低下 2 1 。机制设计理论 的目标就是解决这样的问题。 一种较好的算法机制设计思想闭如图2 所示。图中c i 为系统中的处理机，每个处理机上都有一 个a g e n t ，b i 是各a g o r o t 对机制提出的资源要求，p i 是机制为各a g e n t 服务所需耗费，“是各a g e n t l 的平均处理率( 1 i n ) ，表征系统中各处理机的处理能力， = ( i ， 2 ， 。) 是指定给各处理机 的负载向量。该机制使用多a g e n t 技术，把处理机对机制的资源要求和机制服务处理机的开销结合起 来，形成对机制本身的一个合理评价方法，取得了在合理分配利用系统资源上比较好的效果口】。 基于以上算法机制模型可以设计出比较真实的资源和负载均衡间的协议8 】。本文将对该机制进 行简化改造，重点减少算法机制的服务开销，结合改进的驱动策略和新的信息获取办法，以此保证 负载均衡算法的顺利进行。 东南大学硕士学位论文 图2 算法机制设计 2 2 动态负载均衡算法的驱动策略 b 2 u n 按照系统调度中任务迁移时的“启动”节点类型，可以把动态负载均衡算法中采用的驱动策略 分为以下三种：接收者驱动、发送者驱动和双向混合驱动。 2 2 1 接收者驱动策略 分布式系统中的所有节点可以按闽值m 划分成轻载节点和重载节点，重载节点指的是当前负载 t m 的节点，轻载节点指的是t m 的节点。般来说，这个阈值对于系统所有节点都是相同的，即 是全局阈值；如果系统中节点处理能力不同。可以为不同处理机设置不同的阈值；如果是多个异构 系统连接起来的系统，可以为不同的局部区域设置局部阐值。由于为分布式系统设置不同的局部阈 值会增加一些额外计算开销，因此大多数负载均衡算法均采用全局闺值的办法，故本文也以全局阚 值来考虑。 接收着驱动策略的主要思想是：当一个节点的负载低于系统闽值m 时，它就依照某种规则尝试 向某些重载节点请求任务，如果请求到任务，则中止请求，否则继续询问下一个节点；如果经过一 定数量的请求仍然没有出现满足要求的节点，贝n 请求节点就进入等待状态，过一定时间后再向重载 节点发出任务请求。 系统启动时，所有节点开始执行任务，经过一段时问以后，节点开始检查自身是否为轻载节点， 如果是，该轻载节点就试图在系统中找出重载节点，并向该重载节点请求任务。具体来说，设轻载 节点的负载为，除此节点外系统还有k 个节点，其负载分别为五，如，k ，则平均负载。为： 1 x 三。2 亩( z ，十酗 为达到任务的均匀分布，应求得系统中重载节点需传递给负载为的轻载节点的负载量( 1 q k ，q 是不同于p 的其它节点) ，我们引入权值以避免从负载更轻的轻载节点迁移任务给负 载为f ，的节点。如果m m 的节点，轻载节点指的是t k ，则 g = 一k ，否则 g = 0 。因此”崎为： 7 厅 m 可 是 ) 坼 己 一 pu = g m 东南大学硕士学位论文 当求出之后，此负载为的节点就可以按照向各个相关节点发送任务图4 示出了发送者驱 动算法流程。当用户提交一个新任务时，系统队列长度增一，此时如果太子系统阈值，则启动发送 者驱动策略。 新任务到达 q l 为任务队列长虞，q l i 为节点i 的任务队事i 长度，为阈值 图4 发送者驱动算法流程 与前节的接收者驱动策略相比，发送者驱动策略的主要优点是：没有过重负载的忙节点，不会 被空闲节点所打扰；任务自己寻找转移节点，更有主动性和目的性。这些在系统整个负载较低时尤 为熏要。 发送者驱动的主要缺点是：负载过重的忙节点还要额外增加处理负载均衡调度的负担。 发送者驱动策略更适合系统总负载较轻的情况【1 m h ”。 2 2 1 3 混合( 双向) 驱动策略 在任务的不断提交、分配和执行过程中，由于任务到来是不确定的，并且系统负载情况会经常 动态变化( 一般是前期和后期系统负载较轻，中期较重) ，如果单一采用接收者驱动策略或者发送者 驱动策略。则由于各自特点的不同，两者都不能在整个过程中得到非常好的效果，所以根据系统负 载情况和任务运行进程。可以灵活使用这两种驱动策略，在不同的时期使用不同的驱动策略，这也 就是所谓混合( 双向) 驱动策略。此策略的主要思想是：发送者与接收者都能转移任务。因此，该 策略兼有发送者驱动和接收者驱动策略的优点：在系统负载较低时，发送者驱动策略能够较容易地 发现轻载节点；而在系统负载较高时，接收者驱动燕略能够较容易地找到重载节点。但双向驱动策 略也有一些不足，如在系统负载较高时，使用发送者驱动容易造成系统的不稳定等。一个较好的解 决方法是采用自适应算法，合理的设置阈值，在系统高负载时采用接收者驱动，在系统低负载时采 用发送者驱动。 概括来说，在动态负载均衡算法中到底使用哪一种驱动策略，需要结台算法的特点和系统运行 时的状况：在任务提交的开始，一般先使用发送者驱动策略；随着系统外任务的不断随机达到，当 系统的总负载较高时，应该使用接收者驱动策略，因为此时轻载节点少，更容易找到。现在较多的 负载均衡算法都采用混合( 双向) 驱动策略。轻载、重载的标准则根据不同系统由用户指定或在运 行过程中动态进行调整。因此即使是在同一系统上，每一次的大任务运行都可能得到不同的负载均 衡效果。 8 第二章分布式系统动态负载均衡 2 3 分布式系统动态负载均衡难点 在分布式系统动态负载均衡问题上，有一些普遍的难点：首先是如何尽量减少由于评价负载、 获取负载信息所产生的额外开销；其次是如何避免任务迁移时所出现的“抖动”现象；再次是如何 解决网络通信延迟的问题；以及负载均衡算法的通用性等问题。负载均衡算法所要达到的目标，就 是尽量解决上述问题。 2 3 1 动态负载均衡常见问题 1 ) 要在分布式系统上有效地实现负载均衡，往往必须对系统的负载情况进行评价。然而，这是 一个很复杂的问题，因为与节点负载情况相关的因素有很多，如：运行队列中的任务数、可用资源 ( 内存等) 、上下文切换速率、系统调用速率、i o 开销等。在这些单个的负载参数中，采用运行队 列中的任务数作为描述负载的参数是最有效的1 3 】j 。有时候，为了能更全面地反映系统信息，我们可 以考虑诸如上述那些的更多的因素，如c p u 利用率等，这就需要负载均衡算法采集更多的信息显 然这种做法会增加很多额外开销，经常会导致得不到用户所希望的性能改善，对于系统整体性能来 说是得不偿失。因此一般采取一到二个最能体现负载情况的参数对负载进行评价，本文采用运行队 列中的任务数作为衡量负载的标准。 2 ) 负载均衡常出现的一个问题是，一个任务在各节点问被不断迁移而得不到执行，此种现象被 称为任务迁移的“抖动”，它会造成系统的不稳定，即一些本该很早完成的任务被大大延迟，进而影 响到后继任务的执行，从而可能造成系统执行差不多量的任务存在较大响应时间差别( 即同一个系 统在不同时间执行同样的任务完成的时问不同) 的现象，称之为系统的“颠簸”。因此要采取诸如限 制迁移次数等方法和对策来避免此现象的发生。 3 ) 因各节点通过通信网络相连，如果有比较大的通讯延迟，则很可能使迁移到其它节点执行的 任务的响应时间，比在本地执行的时间还要长。节点之间的信息传输，总有一定的延迟时间，这就 使得任务的响应时间变为迁出时间、在远程节点的逗留时间以及结果的返回时间之和了。因此在进 行负载均衡时，要综合考虑这三者的因素。 4 ) 负载均衡的性能受网络拓扑结构和系统节点数目的影响。到目前为止，还没出现与网络拓扑 结构、处理机数目完全无关的通用算法。因此要从网络拓扑结构出发，研究其本身的特点，进而设 计出较通用的负载均衡算法。 2 3 2 动态负载均衡算法的要求 一个好的动态负载均衡算法，通常需要考虑以下几条要求【】5 】： 1 ) 有效性是指算法在性能方面的要求。性能是我们在进行负载调度时需要首先考虑的问题， 也就是说，调度算