（计算机系统结构专业论文）基于进程剩余运行时间的集群负载平衡系统.pdf

华中科技大学硕士学位论文 摘要 集群计算技术近年来成为计算机界研究的一个热点。集群不但能够充分利用现有 的计算资源，而且能够通过较低的软、硬件代价实现较高性能的计算机系统。随着微 处理器技术和高性能网络技术的飞速发展，集群计算逐渐成为一种高性价比的并行分 布式计算资源。 负栽平衡是集群系统中的重要技术，通过平衡各个节点问的负载来提高集群系统的 性能。研究表明。在集群系统中采用负载平衡技术可以显著的提高集群系统的性能。负 绒、f 衡的策略可以分为静念和动态两大类。静态负载平衡策略在各个节点上分配负载时 只使用系统的静态信息，这种策略的好处是在数学上容易分析且易于实现，但并未考虑 系统节点的当日f 负载情况，因此，对集群系统利用率较低而且性能较差。动态负载平衡 系统根据集群的负载状况动态地分配负载，相对来说能更大地提高系统的性能。 “基于进程剩余运行时间的集群负载平衡系统”是针对资源异构集群设计的一种 牿j 二新型负载向量的动态负载平衡系统。该系统使用一种新的负载评价指标：c p u 就 绪队列中进程剩余运行时间总和，兼顾了节点的资源使用情况及节点收到的任务情况 两个方( f i j ，更好地体现了集群系统的处理能力和系统正在处理的负载情况，比常用的 c p u 队列长度负载向量更加灵活准确。此外，对于集群的资源异构特性，在确定系统 负载的闽值时，考虑了节点问的c p u 及内存大小的差异。 该系统使用集中式策略管理，各节点定时的搜集负载信息汇报给控制节点，控制 节点使用随机策略选择负载平衡的负载转移目的节点，并使用抢占式进程迁移动态地 调节系统负载。系统基于l i n u x 操作系统，主要使用l i n u x 的内核编程技术及应用层 的l c ) 9 络编程。系统虽然涉及到操作系统核心一进程的操作，但是出于采用模块编程， 没有对原内核进行修改，便于软件的安装及升级。 测试结果表明，新的负载向量及新的阈值确定方法缩短了任务的响应时间，提高 了集群的性能。考虑了节点c p u 主频及内存大小差别后确定的阅值，比确定系统统 一的闽值性能提高了系统性能2 6 ；使用新的负载向量与使用传统的c p u 队列长度 负载向量相比，系统性能提高近3 0 。 关键词：集群，负载平衡，负载向量，阖值，进程迁移，进程生命周期 华中科技大学硕士学位论文 a b s t r a c t c l u s t e rc o m p u t i n gi sa l w a y st h ef o c u so fa g r e a td e a lo f r e s e a r c hi nt h ec o m p u t e rf i e l d i nr e c e n ty e a r s c l u s t e rs y s t e mc a nn o to n l ym a k ef u l lu s e o f c o m p u t i n gr e s o u r c e s ，b u ta l s o g a i nh i g hp e r f o r m a n c ei nc o m p u t e rs y s t e mw i t hl o w e rh 盯d w a r ea n ds o f t w a r ec o s t w i t h t h e r a p i dd e v e l o p m e n t o f m i c r o - p r o c e s s o r a n d h i g hp e r f o r m a n c en e t w o r k ，c l u s t e r c o m p u t i n gg r a d u a l l yh a sb e c o m i n g a p a r a l l e l d i s t r i b u t e dc o m p u t i n g r e s o u r c e s l o a db a l a n c i n gi sa ni m p o r t a n tt e c h n o l o g yi nt h ec l u s t e rs y s t e m i ti m p r o v e st h e s y s t e mp e r f o r m a n c eb yb a l a n c i n gt h el o a db e t w e e nn o d e s t h ep r e v i o u sr e s e a r c hp r o v e d t h a tt o a db a l a n c i n gc o u l d g r e a t l yi m p r o v e t h ec l u s t e rs y s t e m s p e r f o r m a n c e l o a db a l a n c i n g a l g o r i t h m sc a nb eg e n e r a l l yc h a r a c t e r i z e d a sd y n a m i ca n ds t a t i c s t a t i cl o a db a l a n c i n g a l g o r i t h m su s e so n l ys t a t i ci n f o r m a t i o nw h e nd i s t r i b u t i n gl o a dt on o d e s i tc a l lb ee a s i l y a n a l y z e d i n t h e o r ya n de a s i l yd e s i g n e d i n i m p l e m e n t a t i o n t h es t a t i c l o a d b a l a n c i n g a l g o r i t t u n s d o e sn o tc o n s i d e rc u r r e n tl o a ds t a t u so fn o d e sw h e nm a k i n gd e c i s i o n so f d i s t r i b u t i n gl o a d t h a tl e a d s t ow o r s e p e r f o r m a n c e b e c a u s et h e s ea l g o r i t h m sc a n tm a k ef u l l u s eo fc l u s t e r r e s o u r c e s d y n a m i c l o a d b a l a n c i n g m a k e s d i s t r i b u t i n g l o a dd e c i s i o n s a c c o r d i n g t ot h es y s t e m - s t a t ei n f o r m a t i o n s oi tc a n g e tb e t t e rp e r f o r m a n c e t h el i n u xc l u s t e rl o a d b a l a n c i n gs y s t e m i sa d y n a m i c l o a d b a l a n c i n gs y s t e mu s i n g a n e wl o a di n d e xi nt h er e s o u r c e sh e t e r o g e n e o u sc l u s t e re n v i r o n m e n t t h en e wl o a di n d e xi s t h et o t a lp r o c e s s e sr e m a i n i n gt i m ei nc p u q u e u e i tt a k e si n t oa c c o u n t n o to n l yt h es t a t u s r e s o u r c e sb u ta l s ot h er e c e i v e dt a s k si n f o s oi tp r e s e n t sc l u s t e rs y s t e mp r o c e s s i n ga b i l i t y a n dt h el o a d b e i n g d e a lw i t hw e l l o t h e r w i s e ，i nt h eh e t e r o g e n e o u sc l u s t e rs y s t e m ， c o n s i d e r i n gc p u a n dm e m o r yf a c t o r sw h e n d e c i d i n g t h et h r e s h o l do f e a c hn o d e t h el o a db a l a n c i n gs y s t e mi sm a n a g e dc 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 n a n dr e p o r ti tt ot h ea d m i n i s t r a n tn o d ep e r i o d i c a l l y t h ea d m i n i s t r a n tn o d ec h o o s e st h e r e c e i v e ru s i n gr a n d o ms e l e c t i n ga l g o r i t h m s p m e m p t i v ep r o c e s sm i g r a t i o ni sa d o p t e dt o b a l a n c et h el o a di ns y s t e md y n a m i c a l l y t h es y s t e mi sb a s e do nl i n u xo p e r a t i n gs y s t e m ， m a i n l yu s i n gl i n u x k e m e l p r o g r a m m i n g a n dn e t w o r k p r o g r a n u n i n gi nu s e rl e v e l a l t h o u g h t h es y s t e md e s i g nd e a l sw i t ho p e r a t i n gs y s t e mk e m e l - - p r o c e s so p e r a t i o n ，t h es o f t w a r ei s i i 华中科技大学硕士学位论文 e a s yt ob ei n s t a l l e da n du p g r a d e db e c a u s e i tt a k eu s eo fm o d u l ep r o g r a m m i n gr a t h e rt h a n m o d i f y t h ek e r n e li t s e l f e x p e r i m e n t a lr e s u l t s s h o wt h a tt h er e wl o a di n d e xa a dt h en e ww a yt oc o n s i d e r t h r e s h o l dd e c r e a s et h ee x e c u t i n gt i m eo f t a s k sm a di m p r o v et h ec l u s t e r sp e r f o r m a n c e t h e n c ww a vt od e c i d e dt h r e s h o l di m p r o v e sc l u s t e rp e r f o r m a n c eb y2 6 c o m p a r e dt ou s i n g s a m et h r e s h o l di n s y s t e m u s i n g n e wl o a d i n d e x i m p r o v e ds y s t e mp e r f o r m a n c 。 a p p r o a c h i n g3 0 c o m p a r e d t ou s i n g l e n g t ho f c p u q u e u e a sl o a di n d e x k e y w o r d s ：c l u s t e r ，l o a db a l a n c e ，l o a d i n d e x ，t h r e s h o l d ，p r o c e s sm i g r a t i o n ， p r o c e s sl i r e t i m e 1 1 1 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中已明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：；矧砷 日期：舛4 月乎日 学位论文版面使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 庠进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适应本授权书。 本论文属于 不保密口。 ( 请在以上方框内打“”) 学位论文作者签名：旅寺坤 日期：砌争年年月f 日 指导教师签名 日期：“叫年妒月日 华中科技大学硕士学位论文 1 绪论 1 1 集群及相关概念 集群是一种并行或分布处理的系统，它由一组相互连接的独立计算机组成，并作 为一个单独的集成计算资源工作。这些计算机可以是单机或多处理器系统，每个节点 都有自己的存储器、i o 设备和操作系统。集群对用户和应用来说是一个单一的系统， 它可以提供低价高效的高性能环境和快速可靠的服务。 集群计算技术近年柬成为计算机界研究的一个热点。集群系统不但能够充分利用 现有的计算资源，而且能够通过较低的软、硬件代价实现较高性能的计算机系统。随 着微处理器技术和高性能网络技术的飞速发展，集群计算逐渐成为一种高性价比的并 行分布式计算资源。 集群系统具有很多优点： ( 1 ) 易于同现有网络集成； ( 2 ) 可伸缩性好，易于保护用户投资； ( 3 ) 其有高性能，高可用性； ( 4 ) ： 作站上现有的丰富的标准成熟的开发工具。 这些都使得集群系统成为一种发展趋势。 1 2 负载平衡及其应用 负载平衡即对负载进行分配调度使其平衡的技术，它是一个广泛的概念，不仅在 计算机领域，丽且在电力、通讯、流水线生产的设计等行业都有其特殊的含义及作用。 但是在计算机领域，负载平衡技术显得尤其重要和突出。 负载平衡最早的提出是在7 0 年代，在分布式系统领域。而在基于服务和连接的 应用，如u w 技术出现后，负载平衡的作用更加突出。对于w e b 服务或数据库服务 等，这些服务的服务器端如果只有一台服务器，则会出现多种问题，如存在物理性能 限制、存在负载容量限制、存在单一失效点等。当前通用的解决方法是将服务或者应 j 程序安装到多台服务器上，在服务器端有一个前端机，负责接收客户端的服务请求， 并根据负载平衡算法，将客户端请求分散到多台服务器上，从而提高了基于服务器程 序( 如w e b 服务器) 的性能。 华中科技大学硕士学位论文 然而基于服务的应用只是计算机中功能的- - 4 , 部分。本文讨论更广泛意义上的负 载1 f 衡，而不仪限于基于服务的应用。这种负载平衡基于任务和进程，定义系统中的 负载评价标准后，自动检测各节点间的负载差异，通过进程的迁移平衡负载。但是山 j 二确：多w e b 的服务设计，在处理客户端的请求时不是以进程为单位的，所以这种负 载平衡对w e b 服务的性能提高不明显。 1 3 负载平衡算法 在硬件结构上，集群即使用高速网络连接起来的p c 或者工作站的集合，对于这 样的一个系统。山于任务到达的随机性，以及各个结点处理能力的差异，在系统的运 行过程中，某些结点的任务较多，负载较重，而另外有些结点却是空闲的。一方面， 重负绒结点上的任务需要尽快的被完成：另一方面，那些空闲的结点也是系统资源的 种浪费。因此，负载平衡被用于对各个结点上的任务进行重新调度，通过进程迁移 等于段平衡各结点问的负载，从而避免这种空闲与忙等待弗存的情况，有效的提高资 源利用率，减少任务的平均响应时间。 1 3 1 负载共事与负载平衡 j “义的负载平衡概念可以进一步分为负载共享( 1 0 a ds h a r i n g ) 与负载平衡( 1 0 a d b a l a n c i n g ) 。负载共享的目标是使分布式系统的运行速度最大化，因此，负载共享要避 免和处理一些非理想状念的情况：系统中一些计算机处于空闲状念而有些结点则负载 过重。这种非理想状态可以通过向空闲结点迁移任务来处理。 负载平衡同样尽力防止非理想状态的出现，但与负载共享相比，要求更高。负载 平衡的目标是使系统中各结点的负载大致相等，k u r e g c r 和l i v n y 【l 】的研究显示，负载 j l z 衡策略可以潜在地减少任务的响应时间。但是要达到每个结点的负载大致相等，需 要复杂的算法，以及大量频繁的任务迁移，算法实现的难度以及任务迁移带来的负载 降低了负载平衡实现的意义。所以现在的负载平衡系统中实现的主要是负载共享，但 l i 习惯的原因，仍称之为负载平衡算法。 尽管负载平衡提出至今已有2 0 年左右的历史，但是真正能令人满意的实现的系 统并不多，一个好的负载平衡算法，必须考虑以下的几条要求： ( 1 ) 有效性：算法的加入和运行，提高了系统的效率和性能，降低了任务平均 l i 向应时问。为提高算法的有效性，要求系统用于负载平衡的附加代价尽可能小，并改 酱通讯设备的性能。 2 华中科技大学硕士学位论文 ( 2 ) 稳定性：指系统正常工作的能力。特别是当系统大多数节点处于重负载状 况时，算法的运行，是提高系统的性能，而不是使系统负载的情况进一步恶化。为捉 商系统负载平衡的稳定性，要求解决任务迁移的抖动问题。 ( 3 ) 可靠性：一个节点的崩溃，并不影响其他节点的正常工作。 ( 4 ) 用户透明性：用户不需要知道任务具体在哪台机器上执行，对用户来说， 任务的迁移及远程执行都是透明的。 上述特性并非各自独立的，而是互相依赖互相影响的。在实现中，要根据具体的 情况进行适当的取舍。 1 3 2 动态负载平衡与静态负载平衡 负载平衡的策略可以分为静态和动态两种。静态的负载平衡策略一般是利用列举 法、图论和排队沦等技术产生较优的迁移方案，它不考虑系统的状念，而根据固定的 策峪( 如轮转法) 将新产生的任务分派到各个节点，并且在分配后任务不可再迁移。这 种策略的优点是容易建立数学模型分析且易于实现，但是在分派任务时不考虑节点当 前的负载状况，所以不能较好的达到负载平衡的目的，在某些情况下更会加剧节点间 负载的不平衡，导致集群系统性能较差。相对来说，动态负载平衡系统根据集群的负 载状态动态的做出负载分配的决定，因此能够将一个新产生的任务分派到最合适运行 它的节点上去，更大地提高系统的整体性能。 x , j 集群动念负载平衡系统的性能评价已有很多研究工作口州，这些工作多采用模 ，理仿真的方法1 2 4 1 ，使用特定的测试数据驱动所设计的模型，虽然有一定的代表性， 但对性能的分析缺乏灵活性。也有一些方法基于数学分析 5 , 6 1 ，但基本都采用排队系 统理论进行模型描述，受限于排队系统理论对并行分布式系统的描述能力，他们的模 型与实际系统相差较大，不能较为真实的描述集群动态负载平衡系统的实际行为特 征。 1 3 3 负载平衡算法的构成 一个典型的动念负载平衡算法包含以下四个部分： ( 1 ) 传送策略 传送策略用来决定一个结点是否适合参与一次任务的迁移，在这次迁移中，结点 州以作为发送结点，也可以作为接收结点【1 0 4 2 1 。常用的传送策略使用阊值策略。当一 个耋占点，* 生一个新的任务时，传送策略判断该结点的负载是否超过了上闽值 华中科技大学硕士学位论文 t h r e sh i g h ，需要成为发送结点迁移任务；与其对应的，当一个结点的负载降到下闽值 t h r e sl o w 以下，传送策略决定该结点是否可以加入系统的可用结点集合，准备分担系 统负载。t h r e sh i 幽与t h r e sl o w 值可以不同【1 m 1 劲，也可以是一个值1 。 除了闽值策略外，还有相刈传送策略。相对传送策略考虑系统中结点的负载差值。 例如，当一个结点的负载与另一个结点的负载差别大于了某个确定的值a ，则启动任 务迁移策略。一般可以将系统中负载最轻的结点作为接收者。 ( 2 ) 选择策略 在传送策略确定一个结点为发送结点后，需要由选择策略挑选一个适合于迁移的 任务( 进程) ，如果在发送结点找不到一个适合迁移的进程，则该结点不再作为发送结 点0 1 3 , 1 4 1 。选择一个迁移进程的最简单的途径是选择一个新生成的任务，因为此时任务 的迁移代价比较小，这种迁移是非抢占式的。 选择策略一般要考虑以下几个方面： 由任务迁移产生的负载应该较小，例如，迁移小的任务( 占用较小的内存空问) ； 被选中的进程应该可以运行足够长的时间，这样由迁移带来的性能提高能够大 于迁移本身带来的负载； 被选中进程的与位置相关的系统调用应该较少。与位置相关的系统调用指必须 在进程产生结点上执行的系统调用，例如进程使用的窗口、时钟及鼠标等资源，都是 对一个结点唯一的。 ( 3 ) 放置策略 放置策略的任务为传送策略确定的接收者( 或发送者) 选择一个合适的传送搭档 ( 发送者或者是接收者) 【1 5 - i 8 1 。 在分布式策略中一个广泛使用的选择合适结点的方法是“轮询”，一个结点向另 外的结点询问对方是否适合作为传送搭档，这种询问可以串行，也可以并行发送询问 包。洵问结点的选择可以基于上一次的轮询信息，或者基于“最近邻居理论”。可选 择的方法是发送询问的广播包来寻找可以任意一个负载平衡的可用结点。 在集中策略中，传送策略选中的结点与系统中的“管理者”联系，查询并得到一 个jj 1 结点。系统巾的这个“管理者”负责收集系统的所有信息，传送策略使用这些 信息来选择个接收者。 ( 4 ) 信息策略 信息策略决定系统结点的信息何时被收集，从何处收集这些信息，以及具体要收 华中科技大学硕士学位论文 集哪些信息【1 9 - 2 1 i 。有三种典型的信息策略： 需求驱动策略 住浚策略下，只有当一个结点成为接收者或者发送者时，系统的“管理者”彳会 收集系统中结点的信息，确定另一个合适结点并启动负载平衡。需求驱动策略是一种 天生的动态策略，因为它的行为是依据系统状态的变化的。需求驱动策略可以是由接 收者、发送者启动，或者是对称启动。在发送者启动策略中，发送者寻找一个可以分 担其负载的结点。在接收者启动策略中，接收者申请分担来自发送者的负载。对称启 动足以上两者的结合，负载平衡由那些对于剩余处理资源或剩余工作的需求启动。 定时策略 集中策略或者分布式策略都可以使用定时机制，隔一定的时间收集系统结点的信 息。传送策略根据收集到的信息迁移进程。定时机制一般不根据系统状态改变收集信 息的速率。例如，在高系统负载的情况下因为大多数结点均处于繁忙状态，则负载平 衡算法的效果就不明显。另外，定期的信息收集也增加了系统的负载。 状态变化驱动策略 在该策略中，当一个结点的状态改变时，该结点向系统发布自己的信息。状态变 化驱动策略与需求驱动策略不同，因为它发布自身信息的方式优于收集其他结点的信 息。在集中策略中，结点将自己的信息发送给系统的“管理者”，在分布式策略中， 信息被发送给其他所有结点。 1 4 国内外研究现状 负载平衡的概念提出已有很长时问，但是整个算法涉及的问题较多，国内大部分 的研究主要是针对负载平衡策略中的某一个问题2 2 2 4 1 ，对负载平衡算法的系统研究不 多，而实现算法的系统就更少。国外有一些成型的集群负载平衡系统，如m o s i x 、 p a n t s 及g l u n i x 等。 1 4 1m o s i x， m o s i x l 2 5 l 是由以色列的h e b r e w 大学设计实现的一个分布式操作系统。这个项目 从1 9 8 1 年开始并持续至今。m o s l x 通过进程迁移完成自动的负载平衡功能，采用单 一系统映像模式s s l ( s i n g l es y s t e m i m a g e ) ，支持所有的u n i x 接口和机制，具有如下 特性： 华中科技大学硕士学位论文 ( 1 ) 易使用性和透明性：支持多用户和时分麸享环境，基于内核的支持，透明 性好，不用修改应用程序； ( 2 ) 动念负载平衡：根据负载的波动和资源的可用性来发起进程迁移，通过在 工作站上平均分布负载来提高性能； ( 3 ) 分椰式控制和高度的可伸缩性：为了利用硬件的冗余来达到高可用性，工 作站之间没有主从关系。控制也是分布的，m o s i x 中不存在集中的控制机构。每个 ：肖点都能够作为独立的系统运行，并且自主的做出控制决策。这种设计允许动态配置， 节点可以自由的加入或退出网络系统而不会给其它节点带来影响。 m o s i x 是一个较成功的负载平衡系统，但也还有一些需要解决的问题： ( 1 ) 在m o s l x 中，一个迁移进程是由用户级上下文( r c m o t c ：远程) 和系统级上 下文( d e p u t y ：代理) 这两部分组成的。d e p u t y 包括进程系统上下文中具有节点依赖性 的那部分，因此是不能被迁移的。r e m o t e 通过d e p u t y 进行节点依赖性的工作，如环 境变量和i o 。如果d e p u t y 所在节点出现故障，r e m o t e 将不能正常运行。而且如果 r e m o t e 与d e p u t y 间有大量的通讯，也会使性能下降； ( 2 ) m o s i x 不支持s o c k e t 迁移。即没有对网络服务器应用程序的迁移支持； ( 3 ) 由于要保持系统的单一系统映像，m o s i x 对操作系统本身的结构改动很多， 降低了系统的可移植性。 1 4 2p a n t s p a n t s ( p a n t sa p p l i c a t i o n n o d e t r a n s p a r e n c ys y s t e m ) 1 2 6 1 是运幸亍在b e o w u l f 集群上 的一个负载共享系统。它的设计目标是给用户及程序员提供一个透明的环境，使得不 断增长的应用需求受益于进程迁移。在p a n t s 中，多进程的应用不需要为分布式的计 算修改程序，重新编译，通过将所有的进程分配到节点的多个节点上执行，从而减少 任务的响应时间，提高系统性能。 p a n t s 中使用抢占式的进程迁移作为负载平衡的手段，这种抢占式的进程迁移是 通过e p c k p t 实现的。雨f e p c k p t 本身存在很多不足。最大的问题是e p c k p t l 句内核中添加 了许多多余的信息。例如，为了获得文件打开的信息，在o p e n 和c l o s e 系统调用中做了 修改。如果想要c h e c k p o i n t 一个进程，必须要在进程初始化日志前调用e p e k p t 添加的系 统凋用c o l l e c td a t a 。否则该进程不能被设最检查点。也就是说，一个进程启动前就需 要确定这个进程是否会被迁移，这是极不方便和低效的。 另外，p a n t s 本身也对l i n u x 核进行了修改，这种修改必须随着l i n u x i , q 核的每 华中科技大学硕士学位论文 个版本做相应的改动，7 这也大大影向了p a n t s 的使用和推广。 1 4 3g l u n i x g l u n i x 的设计思想是1 9 9 3 年提出的，目的是构建一个在b e r k e l e y 学校的n o w 系统r p 使用的操作系统级的平台，一个最主要的目标是同时可以支持交互式的并行和 串行作业。g l u n i x 的主要特点有： ( 1 ) h j 户空间的中间件，支持并行和串行作业； ( 2 ) 设计目标是支持并行及串行作业b a s h 类型透明的远程执行，通过作业分配 和进程迁移提供负载平衡，并可以克服单一失效点； ( 3 ) 进程的迁移发生在系统不平衡或者有一个新的节点加入系统或退出时( 其实 如果系统的机器都在轻负载则没有必要做迁移) 。 但是山于系统实施的某些原因，系统原型的大部分目标并没有很好的实现，该系 统的+ 些缺陷和不足： ( 1 ) 负载平衡在作业启动时候实现，没有实现进程迁移； ( 2 ) 不是完全容错的，因为系统是集中控制，主控节点不能死机，否则系统会 瘫痪。 1 5 本文内容的组织 本文以后的章节组织如下：第二章介绍了有关负载平衡算法的技术背景对负载 算法。l j 的每个构成部分中存在的策略进行了比较和分析，并提出了可以改进的方法， 在负载评价部分，提出了一种新的负载向量一使用就绪c p u 队列中进程剩余运行时 问总和作为负载评价的指标；第三章详细介绍了基于进程剩余运行时间的集群负载平 衡系统，郎l c l b ( l i n u x c l u s t e rl o a db a l a n c i n g ) 系统的总体设计以及该系统的三个内 核模块的设计与实现；第四章重点介绍了该系统中负载平衡算法的实现核心，即应用 层守护进程的设计与实现；第五章是对l c l b 系统的测试并对测试结果进行讨论：最 后，第六章总结了全文，并给出了下一步研究的方向。 华中科技大学硕士学位论文 2 负载平衡算法 负载平衡算法山多个部分构成，要设计一个稳定高效的集群负载平衡系统，需要 刈算法的每个方面进行仔细分析和研究。下面根据逻辑上解决负载平衡的顺序，对负 载算法进行分析和研究，在负载向量部分提出一个新的负载评价指标，并对原有的策 略提出改进的算法。 2 1 负载评价指标 确定负载平衡算法中的第一个关键问题是使用一种合适的负载评价指标，一般被 称为负载向量。常用的负载向量有c p u 队列长度、一段时间内平均c p u 队列长度、 叮用内存大小、系统调用频率、c p u 及内存利用率、中断次数等。研究者发现使用不 h 的负载向量对于负载平衡算法的性能有重大的影响，并且简单的负载向量往往更有 效。例如，k u n z t 7 】的研究发现，负载向量的选择对算法的性能有相当的影响，并且他 的测试结果显示，c p u 队列长度是最佳的负载向量，使用简单负载向量的综合向量并 不能显著的提高算法的性能。 选择一个负载评价的指标，要考虑两方面的内容：首先要考虑该指标能否及时准 确地表示出当前的节点机负载；其次，还要考虑收集、处理这些信息所增加的负载。 当前对于负载平衡的研究主要集中在放置策略与传送策略，而对信息策略的研究，特 别是对负载向量的研究较少，可以分为以下几类： 2 1 1 使用资源利用率作为负载指标 负载平衡的目的是缩短任务响应时间及提高集群系统的资源利用率，所以很多研 究从资源使用情况入手选择负载向量。通常使用资源利用率负载指标有c p u 、内存及 i o 等。 ( 1 ) c p u 资源 c p u 是计算机中最重要的资源之一，早期对于负载向量的研究都考虑到了c p u 的利用率作为节点负载评价愀t 2 7 , 2 s l 。c p u 的利用率根据系统使用的时钟数比时钟 总数得到，在资源异构的系统中，各个节点拥有c p u 的数量及处理速度均不同，所 以在使用c p u 利用率做负载向量时，需要考虑这些差异。 ( 2 ) 内存资源 华中科技大学硕士学位论文 随着r 1 s c 和v l s i 技术的快速发展，处理器的速度有了突飞猛进的增长，根掘 摩尔定律，c p u 的主频1 8 个月就会翻一翻，甚至更快。而另一方面，存储器( 这罩主 婴指r a m ) 的访问速度增长卸不明显，因此处理器和存储器间速度的差距也在逐步扩 人，一次内存缺页或者一个页错花费的延迟是普通一次访问命中延迟的1 0 0 0 倍。当 i l i 应用中对数据访阃的需求也在不断增长，数据访问及数据移动操作带来的负荷( 如 访问缺贞) 已经非常大，因此如果在负载平衡算法中不仔细考虑内存资源，则分布式 系统的总体性能会有显著的降低。 考虑内存资源作为负载向量时，主要是从应用的角度考虑对内存大小的需求，所 以内存利刚率无法确定可用内存的大小，一般考虑绝对的剩余空问。 其他资源还有网络资源， o 资源等，一般来说，使用资源负载向量是与系统中 负载、作业类型榭关的，如果系统中主要是计算类型的作业，那么使用c p u 资源作 为负城向量效果较好，而使用i o 资源评价系统负载则不准确。 2 1 2 使用队列长度作为负载指标 使用资源使用情况作为评价负载的指标其实是评价节点在某个时刻的状态。而 使刚队列长度，则是从资源的使用者一作业( 进程) 的角度考虑的，一种带有预测性 质的负载评价。如果队列中任务数较多，那么就推断该节点负载重。这种预测也会 柠存- 些问题，例如队列中有很多任务，而每个任务只占用非常少的资源。则评价 行失准确。 队列长度包括c p u 队列长度、i d o 队列长度等，这里只讨论c p u 队列长度。c p u 队列长度普遍被认为是当前最优的负载平衡指标【4 。9 。，其参数容易获取，用于搜集和 处理浚信息的丌销小，且容易建立数学模型进行分析。使用c p u 队列长度一般有两 种：即使用当前瞬时的c p u 队列长度和使用一段时间内的平均c p u 队列长度a 使用队列长度，即当前节点上运行任务的个数作为负载向量有以下两个不足：一 足忽略了节点机性能的差异，这有点可以和上面c p u 利用率相似的考虑；= 是忽略 了任务大小的不同。这些在讨论使用新的负载向量时会更具体地分析。 2 1 3 使用综合策略作为负载指标 综合策略一般指同时考虑多项负载指标，以多种简单的负载向量为基准，通过加 权计算最后得出一个负载的综合值【4 ”。 综合负载向量有两种：第一种是以上两种策略中多种指标的综合，比如，使用队 9 华中科技大学硕士学位论文 列长度时，l ! l = 考虑c p u 队列长度，又考虑i o 队列长度，或者在使用资源利用率时， 般考虑多种资源；第二种是完全的综合，既考虑队列长度，又考虑资源使用情况。 对于简单负载向量的综合一般使用线性函数，如有n 种单一负载向量l l ，l 2 ，l n ， 则一般使_ f 1 ) 函数f 【l l ，l 2 ，l n ) = l l x oi + l 2 ( o2 + + l n x an 。可以同样地设胃 闽值，在节点负载超过这一闽值，或者两节点负载差超过这一闽值时启动平衡策略。 函数中使用的系数ni ( i = l ，2 ，n ) 有两个作用，首先是使各种负载向量的数量级平 衡，由于各种负载向量山于类别不同，数量差异很大的，如c p u 队列长度一般小于l o ， 或哲是几十，而实际系统中节点剩余内存的大小在几十兆字节左右。所以系数n 首先 要渊侮这种数量级上的差异；其次，系数要能够确定每种负载向量在函数中的比例。 另外的一种综合负载向量是考虑多种资源的优先级。如在z h a n g i “j 的研究中，优 先考虑任务对于内存的需求，在保证有足够内存空间的情况下，再考虑c p u 资源。 2 1 4 使用进程剩余运行时间作为负载向量 时俩提到了负载平衡的两个目的；提高资源利用率和缩短任务响应时间。下面从 任务的u 向应时问来考虑负载向量的选择。 缩短响应时阍是负载平衡系统追求的目标，所以使用时间作为系统的负载衡量指 标也就是衡量负载的合理标准。在某一时刻两节点间理论上的负载平衡，也就是两节 点l 的进程( 全局进程) 的剩余执行时问相等，而节点负载的轻重，也就可以使用进程 的剩余时问的总和来衡量，这是衡量节点负载的最理想的指标。但是进程的执行时问 足不可预测，或者很难预测的，设计负载向量的方向就是尽量地接近这一目标。 使用c p u 队列长度负载向量也是这个目标的体现。假设每个节点有大量的大小 不等进程( p r o ( 1 ) ，p r o ( 2 ) ，p r o ( n ) ) 时，那么节点n 1 n 2 上进程的平均剩余时间 f a v e rr e m a i n l ，a v e r能近似相等，所以( n ) 女 ，在这_ r e m a i n 2 ) 可p r o n a v e r _ r e m a i n 种情况下，进程的数量也即进程剩余运行时间总和的体现。 但是以上假设忽略了进程的性质和大小，举一个简单的例子，节点n l 接受了大 量的短作、j k ( mop r o _ s h o r t ) ，而n 2 接受了少量的长作业( n x p r o _ l o n g ) ，两节点的剩余 州f j 总和大致柑等。但山于进程数量m i t _ ，从c p u 队列长度来看。则两个节点的 负载极刁i 平衡，需要进行负载平衡，这样就增加了节点n 2 的最长执行时间，所以在 整体上增加了任务的平均响应时间。实际测试的结果证实了这个观点。 研究进程的剩余时间已经不是一个新的课题，比如h a r c h 0 1 b a i t e r 采用统计学得 出的结论1 2 9 】，进程生命时间的概率分布形式为p l i f e t i m e t = t 。，其中k 的值随 1 0 华中科技大学硕士学位论文 爿i 同的系统在1 3 到一0 8 之问变化，通常靠近一l 。但是原有的对于剩余运行时间的研 究是为了选择一个适合迁移的进程，而并未用于评价系统负载。 使用进程剩余运行时间作为负载向量，考虑了任务的大小，而且通过当前进程的 运行l l , j 间，考虑了任务刘于当前的执行速度，因此该负载向量综合考虑了节点的当阿 资源使用与任务未来可能占用资源的情况。在实际系统的测试中，进程剩余时间向量 状得了较好的效果。 2 2 传送策略阈值策略 确定对结点负载的评价标准后，下一步的工作确定什么样的节点适合( 或需要) 参 与负载的平衡，即确定轻重负载节点。在各种算法中，闽值策略实现简单，并具有较 好的性能。每个节点可以根据阈值对自己所处的状态进行判断，并根据状态采取任务 迁入或迁出的决策。 最简单的闺值是系统中确定单一阈值，节点负载大于该闽值为重负载结点，反之 则为轻负载结点。由于只需要确定一个值，所以该策略的优点就是简单易行，也便于 使用数学方法分析，但是该方法也有明显的不足。由于只有一个阈值，当一个结点迁 移r 一个进程给其他结点，或者接收了一个迁入的进程后，该结点就有可能发生轻重 负载结点角色的转换，从而又一次触发启动进程迁移。这种状态的反复也就造成了系 统的不稳定，多次的进程迁移增加了运行开销，出现颠簸现象。 为避免上述情况的发生，通常使用多阈值，将结点区分为多种状态，当节点的状 态发生转换时，进行相应的处理。但是对于状态分级过细也并不能提高决策质量，而 h 多闽值的确定也很复杂，所以系统设计使用双阈值，将系统中的结点分为三种状态： ( 1 ) 重负载结点：负载大于上负载界限m r e sh i g l l ，一旦系统进入该状态，则触 发启动进程迁移，进行负载平衡； ( 2 ) 轻负载结点：负载小于下负载界限t h r e s ，一旦系统进入该状念，则将_low 自己加入系统的可用结点集，等待分担其他结点的过量负载； ( 3 ) 标准运行结点：结点的负载介于t h r e s _ l o w 与t h r e s _ h i g h 之间，此类结点相 对独立的处理自己的任务，不参与负载平衡。 在资源异构的系统中，每个节点拥有的资源不同，其处理速度也存在一定的差异， 凶此系统也存在闽值，系统闽值可以衡量整个系统的状态，它是节点处理能力的评价。 凶此，各竹点的阈值与其系统闽值存在一定的关系。阈值最后的确定，要体现出系统 华中科技大学硕士学位论文 测值。 0 = ( t h r e s _ h i g h t h r e s l o w ) 被称为阈长。阈长直接反映对系统负载平衡的要求程 度。阂长1 3 越大，表示本地处理能力越强，负载平衡的特性就相对较差，阈长b 越小， 本地处理能力降低，进程迁移叮能性越火，负载平衡的特性就相对较好。 日l j i 考虑节点处理速度的差异时，主要涉及c p u 及内存因素，阈值的大小与c p u 主频成i f 比，与内存的大小成正比，即t h r e jl o w ：n x 竺竺望， m e m f h r p 蛳咖：t h r e sl o w + k 2 xr a t e _ c p u ，其中k l 、七2 为系数，女2 竺生理兰即阈长 m e m m e m 佶。 2 3 负载平衡的手段 负载平衡通过任务的迁移平街负载，任务是现实世界的一个概念，计算机中运行 的灾体足进程，所以任务迁移的实际体现是进程的迁移。 进程是实际运行在操作系统中的实体。一个进程有进程标识符( p i d ) 、寄存器集合、 地址空间以及其他一些资源( 如打开的文件) 。在现代操作系统中，一个进程在其本身的 内存空间中运行，与其它进程分离。进程可以和系统中的其他进程或与操作系统本身 逦过系统调用通讯，另外，进程间可以通过操作系统提供的进程间通讯机制传递信息。 进程迁移根据负载平衡的目的有两种形式：非抢占式的进程迁移，主要指远程执 行，这种方法是将新生成的进程调度到其他节