（系统分析与集成专业论文）集群环境负载平衡的分析与两层调度模式的实现.pdf

摘要 高速发展的网络和不断提高的微处理芯片性能使得计算机网络成为吸引人 的并行计算载体。仅依赖于商业化的硬件和软件，计算机网络能够提供高性价比、 高可用性的计算，这种高性能计算潮流被称为集群计算。 当今，集群计算已经成为一种解决许多大型科学和工程问题的十分有效的方 式。影响集群计算性能的因素有很多，诸如任务粒度、负载平衡、处理机的分配 和网络拓扑等，其中负载均衡和任务调度策略是影响其性能的关键，已发展成为 并行计算领域中的研究热点。 基于集群环境上的并行计算，由于其环境的异构性，为了更高效的充分利用 各类计算资源，就要求程序设计人员依据各计算结点的不同特性分配其上不同类 别的子任务，以达最佳效率。其中，负载均衡是影响计算性能的重要因素之一。 本文首先研究负载均衡调度策略及调度问题的一般模型，总结了影响调度性 能孵各种因素。针对这些不同的因素，本文提出了一些新的策略，改进了某些现 有的方法：如为了解决集中式的任务调度策略中调度结点容易成为瓶颈的问题， 本文提出两层调度的思想，使系统具有良好的扩放性和负载均衡性能；通过将主 动报告与自适应周期汇报相结合来解决负载收集问题，尽量保证负载信息的有效 性又合理的避免了过多通信带来的开销。最后，综合以上内容，在m p i c h 环境上 给出一个完整的两层调度算法，以一个实例进行测试，证明其有效性。 关键词：集群计算；两层调度：负载均衡；m p i c h a b s t r a c t h i g hs p e e dn e t w o r ka n di m p r o v e dm i c r o p r o c e s s o rp e r f o r m a n c eh a v em a d e n o w ( n e t w o r k so fc o m p u t e r s ) b e c o m ea na p p e a l i n gv e h i c l ef o rp a r a l l e l c o m p u t i n g b yr e l y i n gs o l e l yo nc o m m e r c i a lh a t d w a r ea n ds o f t w a r e ，n o wc a n o f f e rc o s t e f f e c t i v eh i g hp e r f o r m a n c ea n dh i g ha v a i l a b i l i t yc o m p u t i n g t h i sn e ww a v ei nh p c ( h i g hp e r f o r m a n c ec o m p u t i n g ) i sp o p u l a r l yc a l l e d c l u s t e rc o m p u t i n g t o d a y ，c l u s t e rc o m p u t i n gh a sb e c o m ea ne x t r e m e l ye f f e c t i v ew a yt o s o l v em a n y p r o b l e m s i nt h e l a r g e s c a l e s c i e n t i f i c c o m p u t i n g a n d e n g i n e e r i n gf i e l d h o w e v e r ，t h e r ea r em a n yf a c t o r st oa f f e c tt h e e f f i c i e n c yo fc l u s t e rc o m p u t i n g ，s u c ha st a s kg r a n u l a r i t y ，p r o c e s s o r s a l l o c a t i n ga n dn e t w o r kt o p o l o g y ，i nw h i c hl o a db a l a n c i n ga n dt a s k s c h g d u li n gs t r a t e g ya r ec r u c i a lo n e sa n dt h u sh a v eb e c o m eh o tr e s e a r c h s p o ti nt h ef i e l do fp a r a l l e lp r o c e s s i n g p a r a l l e l c o m p u t i n gw h i c hi s b a s e do nt h en o w ，b e c a u s eo ft h e h e t e r o g e n e o u so ft h en o w ，r e q u i r e st h ep r o g r a m m e rt od i s p a t c hd i f f e r e n t t a s k st od i f f e r e n tn o d e sa c c o r d i n gt ot h e i rc h a r a c t e r i s t i c si no r d e rt o u s ea l lk i n d so fr e s o u r c e so ft h en o wm o r ee f f i c i e n t l y a m o n gt h o s e ，l o a d b a l a n c i n gi so n eo ft h ei m p o r t a n tf a c t o r sw h i c ha f f e c tt h ec o m p u t i n g p e r f o r m a n c e i nt h i sp a p e r ，f i r s t l y ，i ti sa n a l y z e dt h a tt h es c h e d u l i n gs t r a t e g y o fl o a db a l a n c i n ga n dt h eg e n e r a lm o d e lo fs c h e d u l i n gp r o b l e m ，a n dt h e n t h ef a c t o r sa f f e c t i n gt h es c h e d u l i n g e f f i c i e n c ya r es u m m a r i z e d f o rt h e s e d i f f e r e n tk i n d so ff a c t o r s ，s o m en e ws t r a t e g ie sa r ep r o m o t e da n ds o m e i m p r o v e dm e t h o d sa r ep r o v i d e d ：s u c ha si no r d e rt or e s o l v et h eb o t t l e n e c k l a c e p r o b l e m s i nc e n t r a l i z e dt a s k s c h e d u l i n gs t r a t e g ya n d s i m u l t a n e o u s l yo b t a i nb e t t e rl o a db a l a n c i n gc a p a b i l i t y ，t h ei d e a so f t w o t i e rs c h e d u l i n g s t r a t e g y c o m ei n t o m i n d ：b yc o m b i n i n gt h e h i a c t i v e r e p o r t i n gm e c h a n i s ma n da d a p t i v ep e r i o d i c 。r e p o r t i n gm e c h a n i s mt o s o l v et h ep r o b l e mo nc o l l e c t i n gt h el o a di n f o r m a t i o n ，i td o e st h eb e s t t oa s s u r et h ev a l i d i t yo ft h el o a di n f o r m a t i o na n dl o g i c a l l ya v o i dt o o m u c hc o m m u n i c a t i o nc o s t a tl a s t ，c o m b i n i n gt h ed i s c u s s e da b o r e ，t h i s p a p e rg i v e saf u l lt w o - t i e rs c h e d u l i n ga l g o r i t h mb a s e do nt h em p i c h e n v i r o n m e n t ，a n das a m p l ei sd e s i g n e dt ot e s ti ta n dt e s t i f yt h ev a l i d i t y k e y w o r d s ：p a r a l l e lc o m p u t i n g ；t w o t i e rs c h e d u l i n g ；l o a db a l a n c i n g ：m p i c h 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得 的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体己经发表或撰写过 的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 声明的法律后果由本人承担。 论文作者签名：；i 【衫车 时间：z w6 年r 月吖日 学位论文使用授权说明 本人完全了解湖北大学关于收集、保存、使用学位论文的规定，即：按照学校要求提交学 位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并提供目录检索与 阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文：在不以赢利为目的 前提下，学校可以公布论文的部分或全部内容。 ( 保密论文在解密后遵守此规定) 论文作者签名：主- - 2 ； 签名日期，沙，e 年r 月1 f 日 导师签名： 签名日弩莎叫年r 且洲旧 1 绪论 1 1 论题提出的背景 集群( c l u s t e r ) 计算是1 9 6 0 年由i b m 提出的。多年以来，集群计算技术一直 是计算机界研究的一个热点问题。集群计算的基本思想在于通过网络互连进行资 源共享，充分利用现有的计算机资源，从而以较低的代价获得较高的计算性能。 在六、七十年代的研究中，由于集群系统各组件的性能不高，集群计算技术一直 没有取得突破性的进展。八十年代以来，由于高性能微处理器技术、高速网络技 术、高性能分布计算技术的研究进展，以及典型科学计算和商业应用对高性能价 格比系统的需求，使得榘群计算技术获得了新的发展契机。九十年代直至现在， 集群计算技术越来越受到计算机界的重视，对它的研究已经从传统的学术研究进 入到形成软硬件产品的阶段。近年来，在i n t e r n e t 飞速发展的带动下，人们对 高性能计算、网络计算有了越来越高的要求，而集群计算技术正是一种能够获得 较高性能价格比的技术，这也进一步推动了集群计算技术的发展。近几年来，技 术进步使得微处理器以及网络器件成为便宣的商品，这使得集群成为一种具有很 高性价比的并行分布式计算资源。采用通用商用( c o t s ： c o m m o d i t y 一0 f - t h e - s h e l f ) 硬件以及通用软件建立的集群系统，正在不同领域中 起到越来越大的作用。 集群系统的主要目标是通过网络互连实现全系统范围内的资源共享，同时通 过高效的资源管理和进程调度技术实现资源的有效共享，提高系统资源利用率， 获得高性能。因此，资源的有效利用是集群系统软件研究的一个关键性问题，进 程调度技术是实现资源共享和提高计算效率的有教途径。 1 2 目前国内外的研究现状 在集群系统中，要能够发挥其高性价比，高可用性和可扩展性的优点，系统 设计人员必须解决好集群系统中的进程分配和进程调度问题，即进程调度策略。 进程调度策略是指合理地分配进程到各个计算结点t 作站，保证总任务在最短 时间内完成。目前，对进程调度策略的研究主要集中在以下几个方面：集中式的 调度策略和分布式的调度策略。 集中式的调度策略由一个处理机维护一个进程分布表，并由这个处理机负责 进程的调度。分布进程的调度策略不再由一个集中的处理机管理进程分配表，多 个处理机都维持一个进程分配表的副本，每个处理机只与一部分处理机通信。二 者各有优缺点：集中式的实现方便，但控制结点容易成为系统的瓶颈：分布式避 免了这个问题，但是进程的划分和进程迁移算法复杂，算法开销比较大。 1 进程划分问题 进程粒度( g r a n u l a r i t y ) 圈对于集群系统中进程分配策略的确定具有很重要 有意义。对于所有进程调度算法，进程粒度都是一个影响其性能的重要因素。在 集群系统中，由于不同结点之间进程通讯开销相对较大，过细的进程粒度会使通 信次数频繁，开销增长，抵消并行计算带来的好处。因此，在集群系统中，人们 一直都追求大粒度的进程。然而，如果进程的粒度划分过大，则又会限制进程的 调度并行性。另外，如何将进程按照通信开销划分成适当数目的逻辑组，也是目 前的研究热点。 2 进程迁移 为了实现负载平衡，有时需要将一个已分配到某一计算结点上的进程迁移到 另一计算结点上处理，这就是进程迁移”。进程迁移要能够达到透明性，可伸 缩性，并行性，异构性等要求。进程迁移对要收集已执行进程的虚存映像，进程 控制块，没读的消息和i o 缓冲区，文件指针和己设置的定时器等，由于收集这 些状态信息是比较困难的，所以进程迁移实现起来难度很大，一直是学术界的研 究焦点。 3 负载信息收集策略 要获得良好的负载平衡，在进程分配和再分配时就要收集系统的负载信息。 对于如何选择负载指标”1 ，以及何时收集何种负载信息也一直是学术界研究的热 点m ”。 4 网络并行计算的可伸缩性 在网络并行计算中。一个关键问题是用户如何有效地利用整个网络的系统资 源，其中最重要的就是处理机资源。可伸缩性。是指并行系统如何根据问题的规 2 模自动的伸展，收缩和调节各结点的负载平衡。 1 3 本文的主要贡献和创新 本文在他人已有的成果上，立足于提高集群的可扩展性和可用性入手，开展 了以下几个方面的研究工作： 1 研究集群计算的处理机调度中的相关问题：负载信息的衡量，负载信息的收 集，进程选择和进程迁移机制。 2 研究计算资源的可扩展性和可用性。 3 进程迁移的容错技术。 4 。归纳总结影响调度性能的因素。 5 在m p i c h 2 环境下，部分实现本文中提到理论。 本文的主要贡献包括以下几个方面： 1 对基于d a g 图的预测性“3 进程模型，提出了按层次遍历法生成各进程优先级 别，然后按优先级别进行进程分配的方法，力求保证最大的并行度。 2 基于n o w 环境，采用m p i c h 2 技术，给出了一个完整的两层调度的算法，改 善了由集中式管理方式给集群的扩展带来的限制。 3 结构的优化降级思想：当集群的结点数变动过大时，可以将算法退化为原有 的集中式控制方式，以减少不必要的额外开销。 1 4 论文结构 本文按从理论分析到实践的顺序安排各章节内容： 第一章介绍选题研究情况；第二章重点介绍集群的相关知识；第三章讲述负 载平衡的几种策略以及常用的几种调度算法，并比较分析几种算法各自的优缺 点；第四章通过研究现有的三种拓扑结构，选择一种性价比较高的两层式调度来 作为并行程序调度的虚拟拓扑，并讨论在此环境下的各种调度算法的优缺点，最 后选择主动报告和周期法相结合的方式来报告负载信息，利用综合负载法来生成 负载；第五章综合前面的分析过程，给出在两层拓扑结构下的完整算法。因为并 行计算是应用相关的，在此描述的算法不针对某一具体应用。第六章利用一个矩 阵相乘的例子来测试本算法思想，监控执行过程，验证其良好的扩展性和可用性。 2 集群网络并行计算 集群系统是利用高速通用网络将一组高性能工作站或p c 机，按某种结构连 接起来，并在并行程度设计以及可视化人机交互集成开发环境下，统一调度，协 调处理，实现高效并行处理的系统汹3 。从结构和结点的通信方式来看，它属于分 布存储系统，主要利用消息传递方式实现各主机之间的通信，由建立在一般操作 系统之上的并行编程环境利用消息传递方式实现各主机之间的通信，并完成系统 的资源管理及相互协作，同时也屏蔽工作站及网络的异构性，对程序员和用户来 说，集群系统是一个虚拟的大型机。 m b ：存储总线和i o 总线c p u ：中央处理器 l d ：本地磁盘 m ：存储器 n i c ：网络接口卡 图2 1 集群系统结构 图2 1 表示了集群的典型系统结构。“。每个结点为一台完整的计算机或工 作站：包括处理器、高速缓冲存贮、内存、硬盘和i o 接口。可以只有一个结 点计算机连接所需的外设，其余结点可视需要决定是否安装外设。每个结点都驻 有完整的操作系统。集群结点的硬件和操作系统可以异构。结点可以是共享主存 多处理机系统( s m p ) 或p c ，甚至可以是m p p 。 4 2 1 集群系统的组成 典型的集群系统包含下列组件： 多个高性能计算机( p c ， w o r k s t a t i o n ， s m p ) ，一般称为计算结点 具有当前技术水平的操作系统( 层次结构或者微内核结构) 高性能互连网络 网络接口卡 并行编程环境与工具( 如：m p i “2 ”，p v m ，调试工具等) 2 2 集群系统的特点 集群系统能够以相对较低的代价获得： 高性能( h i g hp e r f o r m a n c e ) ：一个负载均衡集群系统由多台服务器组成，对 外部而言，整个集群就如同一台高性能服务器，系统只有一个对外的网络地 址( 虚拟i p 地址) ，所有对集群的请求都发到这个地址上。系统中有专门的 机制能够将这些请求按照一定原则分发到集群中的各台服务器上，让它们各 自分担一部分工作。 高可扩展性( s c a l a b i l i t y ) ：负载均衡集群具有较好的可扩展性，因为扩大 系统规模非常容易，只要在集群中增加新的服务器即可。 商吞吐率( h i g ht h r o u g h p u t ) 高可用性( h i g ha v a i l a b i l i t y ) 1 ； 负载均衡集群系统将会在各种商业应用 领域中占有举足轻重的地位。商用系统最重视系统的可靠性和容错性，二者 合在一起称为系统的可用性。常用的系统可用性指标有系统平均无故障时 间、期望不间断工作时间及年平均故障率等。由于负载均衡集群系统中各台 服务器之间相对独立，采用一些不太复杂的技术就能使集群系统达到很高的 可用性。 2 3 集群系统设计中需考虑的因素 2 3 1 通信技术 集群系统的计算时间开销定义为： t = m a x p 。( t ) ) + c ( t ) ：其中( 1 i n )( 2 1 ) 其中t 为某任务的计算时间开销，p 。( t ) 表示各其各子结点的计算时间，n 表 示有多少个计算结点，c ( t ) 表示计算过程中的通信延迟时间。公式( 2 1 ) 表示 集群系统的计算时间由子结点的最大时间开销和通信开销“”构成。所以，提高集 群的计算性能也必须从这两方面着手。 一般，p 。( t ) 由各子计算结点的硬件配置情况决定，通过改善硬件性能可以缩 短各结点上的计算时间。而c ( t ) 则可以通过采用更好的并行程序设计方法来尽 量减少通信次数和通信量，再者，就是通过改善集群之问的互联网络来减小通信 延迟。因为通信延迟的开销比一次计算的开销要大得多，而且由于并行程序运算 过程中各予任务之间不可避免的要迸行信息的交流，故如何减小通信开销是集群 计算中必须考虑的。 通常并行程序设计中对于子任务粒度的划分为三大类；细粒度，中粒度和大 粒度。相对来讲。集群系统更适合于大粒度划分法，大粒度划分可以减少子任务 之间的通信，当然也降低了系统的通信开销。 不过，如果粒度划分的过大，相应的就会限制子任务的并行度。这是一对矛 盾的问题，要依具体问题具体解决。这也从另一方面说明，并行程序设计是一个 与应用有关的问题。 2 3 2 负载平衡与进程迁移 在并行计算中，一个大任务往往由很多小的子任务组成。负载指的是分配到 各个处理结点上的并行执行的子任务。负载在并行系统的各处理结点上分布的均 衡程度称为负载平衡度“”。 从上节中给出的任务计算时间开销的公式( 2 1 ) 中可知，m a x f p 。( t ) ) 是由 各子结点中最晚结束的子结点决定。而各个结点的具体计算所花的时间，又是由 6 其上所分配的任务量来决定的，计算时间开销与其上分配的计算量成正比。故如 何均衡的根据各计算结点的处理能力分配计算量，使其整体所耗费的计算时间最 少显示得尤为重要。 从应用的角度看，任何并行环境要提高并行应用的有效性，负载平衡策略是 必不可少的。集群系统平台上的并行计算，因其异构性，特殊的网络结构，结点 性能的动态变化( 由于交互用户的介入，后台进程的运行等) ，使得负载平衡问题 显示得尤其重要，而因其异构性及实际应用则变得更为复杂。当整个系统任务较 多时，各结点上的负载可能产生不均衡现象，从而会降低整个并行计算的性能， 因此负载平衡度是影响集群并行效率的重要因素。 定义：进程迁移。指的是当集群系统中各运算结点的负载量发生倾斜时，将 重负载结点上的任务转发到空闲结点上去运算，以期整个系统能平衡运算的过 程。 在集群并行系统中，负载平衡要解决的问题主要有： 1 系统资源使用不均。以c p u 资源为例，在并行计算中常常会出现这样的现象， 某个结点的c p u 处于十分繁忙的状态，而另一些结点却非常空闲。这导致了 系统资源的极大浪费和并行效率的下降。在集群系统中，由于现有的并行编 程运算环境负载平衡机制通常十分简单，同时各个结点的体系结构和资源状 态互不相同，如何充分利用资源和调度负载就主要成为程序员的责任。但并 行程序运行时系统资源状况在动态改变，程序员很难做出准确的并行任务动 态调度。因此，必须动态监听系统的资源使用状况，做出准确的分配决策。 2 保证前台用户对工作站的优先使用权。集群并行系统是多用户系统，可能有 多个用户同时运作各自的作业，这时就要保证前台对工作站的优先使用权。 2 3 3 单一系统映像 为了方便、容易的使用和管理c o w 系统，使c o w 系统结构对用户完成透明， 集群系统需要向用户提供一个单一系统映象s s i “6 ”3 ( s i n g l es y s t e mi m a g e ) 的 高层抽象，即一个虚拟的单一巨型工作站或超级服务器。集群的多结点性，异构 性，分布性，异步运行牲及信息传输延迟等均被屏蔽在单一系统映像。它是建立 在计算软件和硬件之上，使得系统中的多台计算看起来就如同一台通常的计算机 7 的抽象表示。 集群系统软件的核心思想就是实现s s i 操作，但目前大多数商品化可用集群 还没有达到完全实现s s i 操作的程度。 2 3 4 利用现有的软硬件技术 美国国家计算科学联盟( n a t i o n a lc o m p u t i o n a ls c i e n c ea l l i a n c e ) 是一个 全国性质的合作团体，由5 0 家学院，政府和商业组织组成以实现面向新世纪的 高性能计算机基础结构的原型。该联盟战略的中心是c l u s t e r i n a b o x ( c i b ) 。 c i b 的目标有两个：开发软件来大大简化安装和运行与联盟高扩展集群相兼容的 并行l i n u x 集群；为其他的软件包一如网格工具包( g r i dt o o l k i t s ) - - 提供一个 软件基础。 c i b 包括的工具是所有的组织都可以得到，测试和预配置的工具 ( h t t p ：w 聊n e s a u i u c e d u ) 。这包括v e r i d i a n 的p o t a b l eb a t c hs y s t e m ， 它调度集群上运行的任务；a r g o n n e 的m p i c h “，它允许m p i 代码运行在多个计 算系统上；美国国家橡树岭实验所( o a kr i d g en a t i o n a ll a b o r a t o r y ) 的集群命 令和控制软件简化了集群的使用和管理；i b m 的l i n u x 集群安装功能( l u i ) ，处 理了系统安装问题：美国国家橡树岭实验所的并行虚拟机( p v m ) ，让并行应用程 序运行在集群上。c i b 还将支持m y r i c o m 的m y r i n e t 进行集群处理器间的互连。 由这个集群实现实例可以看出，集群并行系统的实现可以利用现有的比较成 熟软件硬件资源。这样不但可以大大降低开发成本，关键是可以充分利用快速发 展的微处理技术，网络技术以及不断完善的并行编程环境和工具来提高集群自身 的性能。 2 3 5 其他因素 等。 同时还要考虑：o s 的选择，硬件的购买，现有资源的利用，网络的通信能力 8 2 4 适用范围 集群系统总的来说是一种松藕合系统。随着研究的深入和技术的发展，集群 系统的应用范围越来越广，应用的类型也越来越丰富。 比较适合集群计算的应用类型“”有： 通信或同步不是太频繁的c p u b o u n d 并行应用，如对通信同步要求不高的 s p m d 应用 人机交互不太频繁的串行应用 数据访问位置相对固定或者阶段性相对固定的i o - b o u n d 。”应用 实际上，为了提高系统资源利用率，集群系统应该能够动态获取并有效使用 集群范围内的资源。也就是说，计算实体一进程必须能够在集群系统中的所有结 点间任意迁移( 在进程产生时或者当进程运行时) ，从而平衡集群系统各结点的 不同资源的利用率，达到提高资源利用率的目的。当然，进程的迁移必然会带来 迁移代价，以及随之而来的通信代价问题。由于通信开销的限制，集群系统不太 适合于运行具有大量通信或同步要求的任务。 2 5 成熟的集群系统 2 5 il i n u x 离性能集群系统 当论及l i n u x 高性能集群时，许多人的第一反映就是b e o w u l f 。起初， b e o w u l f 只是一个著名的科学计算集群系统。以后的很多集群都采用b e o w u l f 类 似的架构，所以，实际上，现在b e o w u l f 己经成为一类广为接受的高性能集群 的类型。 2 5 1 1b e o w u l f 集群 简单的说，b e o w u l f 是一种能够将多台计算机用于并行计算的体系结构。通 常b e o w u l f 系统由通过以太网或其他网络连接的多个计算结点和管理结点构成。 管理结点控制整个集群系统，同时为计算结点提供文件服务和对外的网络连接。 它使用的是常见的硬件设备，象普通p c ，以太网卡和集线器。它很少使用特别 9 定制的硬件和特殊的设备。 2 5 1 2m o s i x 集群 m o s i x ”。集群和b e o w u l f 等其他集群相比，m o s i x 集群确实是种非常特别的 集群，它致力于在l i n u x 系统上实现集群系统的单一系统映象s s i ( s i n g l e s y s t e mi m a g e ) 。m o s i x 集群将网络上运行l i n u x 的计算机连接成一个集群系统。 系统自动均衡结点间的负载。因为m o s i x 是在l i n u x 系统内核中实现的集群， 所以用户态的应用程序不需要任何修改就可以在m o s i x 集群上运行。通常用户 很少会注意到l i n u x 和m o s i x 的差别。对于他来说，m o s i x 集群就是运行l i n u x 的一台p c 。尽管现在存在着一定的问题，m o s i x 始终是引人注目的集群系统。 2 5 2w i n d o w s 高性能集群系统 e x p r e s sc l u s t e r 是基于w i n d o w s 下的一个出色集群系统。它提供了2 种结 构用来共享在服务器间应继承的数据：在集群闯共享1 台存储装置的磁盘共享 型。主要定位是大规模的集群系统；在服务器间镜像磁盘的数据镜像型。可以构 筑2 台服务器的集群系统，故定位是较小规模的集群系统。可通过w i n d o w s 的标 准g u i 简单方便地构筑系统和管理系统的运行。可以集中管理和监视多个集群系 统。另外，还支持w e b 浏览器的监视功能，使管理员的行动不受限制。 2 6 集群计算前景 作为并行计算领域中的后起之秀。集群计算正以高性价比日益引起人们的重 视。由于集群计算大多采用商用工作站和p c 机，使结点及系统管理相对容易， 且可靠性高，用户可将开发的重点可放在通信和并行编程环境上，节省了大量的 研制时间，并可利用最新的微处理技术和网络技术。而且集群中每个结点都是传 统的工作站，因此有大量现存的应用软件可以使用。 集群因组建的便利性，也是各个实验室和个人研究的热点。按集群现在的发 展趋势，到2 0 1 0 年，集群计算将会成为并行计算的主动流。随着各行业的不断 发展，集群运算在各个领域的应用会进一步的深入”“。 1 0 3 负载平衡策略 集群系统的主要目标是通过网络互联实现全系统范围内资源的共享，同时通 过高效的资源管理和进程调度技术实现资源的有效共享，达到提高资源利用率、 获得高性能的目的。因此，资源的有效利用是集群系统软件研究的关键问题，资 源共享与调度算法是实现平衡的有效手段。在集群系统这种松藕合( l o o s e c o u p l e d ) 环境中，计算结点间负载不平衡是一种常见到的问题。为了使集群系 统易于管理和使用，迫切需要研究集群系统资源的全局共享、分配与调度问题， 使集群系统中的资源管理与调度系统能够实时响应系统资源的动态变化以及工 作负载的动态变化，从而有效地、透明地使用集群范围内的计算资源。 3 1 负载平衡的目标 从两个方面来看待这个目标：系统角度和用户角度。系统期望系统资源利用 率最大；用户期望任务的计算时间最短。虽然这两者不完全相同，但通常在系统 资源合理的安全利用时，计算时间是最短的。 所有进程执行完时刻的调度长度s l “：反映了整个并行程序进程的执行时 间。一般，进程调度的目标就是要获得最短的整个应用程序执行时间，亦即上述 的调度长度。在许多启发式( h e u r i s t i c ) 进程调度算法”。1 中，有时直接以调 度长度为目标函数来进行操作是非常困难的，所以经常以保持负载平衡，减少进 程间通讯量或减短关键路径长度等为目标函数来执行调度操作，目的一样。 3 2 进程调度通用模型 调度问题在不同的领域有不同的描述方法，一般在并行分布系统中，构成调 度的基本元素有三个，即并行应用程序，资源系统以及应用程序调用资源所依据 的一定策略与规则。调度问题就是在满足并行应用程序和资源系统约束条件的基 础上，设计一个有效的调度系统来管理应用程序如何调用这些资源，并使得整个 系统性能指标达到最优或近似最优。它的一般模型如图3 1 所示。 图3 1 调度问题的一般模型 集群计算系统中的进程调度问题就是根据一定的调度规则和调度策略，把组 成并行程序的一组进程或构成工作负载的一组作业，按照一定执行时序分配到系 统中的多个计算结点上，以期取得较好的系统执行性能。 对于集群异构系统的负载平衡问题，可用下面一个模型图“3 1 来描述： 图3 2 异构系统连通模型 图( 3 z ) 用一组相互连接的水桶来建立异构扩散算法的模型。设有p 个圆柱 形容器，其水平截面积各不相同，在容器底部有一些管道将容器连接起来，水可 通过管道从一个容器中流到另一个容器，称为连通器。所有容器的底厦都处在同 一个水平面上。如果水平面有高有低，水就会在容器间流动，直至所有容器的 水平面调度相同为止。假定该系统是连通的。在此模型中，水的体积与计算量 相对应，水桶的水位与结点的计算时间相对应。容器的横截面积与结点的处理速 度相应，水桶之间的连接管与结点之间的通信线路对应，如果计算时间( 水位) 不相同，一些计算负载( 水) 会从通过处理结点问的通信连接( 管道) 从一个结 点转移到另一个结点。如果计算时间相等，整个系统达到负载均衡，计算负载不 再移动。 3 3 目标机器 一般地，目标机器假定由若干个处理单元组成，各结点可以是同构的，也可 以是异构的。它们通过任意的互连网络进行连接。 目标机器按其提供服务的方式来分，可分为两类：固定计算结点与自愿计算 结点。固定计算结点指：计算开始后，直到停止计算，否则不会随便退出计算过 程；自愿计算结点：随时可能加入计算，也可能随时退出计算，处理情况要复杂 得多。为了保证计算过程的健壮性，必须记录各个计算结点上的进程分布与执行 情况，以便在计算结点因为某种原因退出计算过程后，仍能正常的运行下去。 1 雇佣者模型 在雇佣者模型中，机器的各种可用信息事先都可以知道，基本上可以继承传 统模型的系统结构和组织方式。这样的模型如多c p u 结构的小型机，大型机等。 继承有两种方式，一种是将系统完全改用j a v a 来实现。纯j a v a 实现的好处 是能充分利用j a v a 的可移植性，不同的j a v a 虚拟机之间不存在异构的问题，只 存在性能差异，这给问题的分布和迁移带来了极大的方便。另一种方式是只用 j a v a 实现系统的控制部分，具体工作时利用j a v a 调用本地库，直接利用现有的 资源，比如i c e t 系统。由于j a v a 的效率比c 语言和f o r t r a n 低，调用本地库， 可以取得较好的性能，可以获得代码重用方面的好处。不过这样就要在每台工 作机上都要安装可以相互一致的库，使得程序在任何一台机器上都能正确执行。 2 志愿者模型 志愿者模型中，事先不存在一组固定可用的机器，为了对临时组合的计算资 源加以管理，必须提供一个相对集中的管理机制。系统可以提供一个登记计算结 点( 或主控结点) ，愿意提供服务的机器向其登记，以供客户机查询。 这种模型中，提供处理资源的机器的工作方式是主动的，而不是被动的。工 作机在任何时候都可能撤销服务，系统对此无法进行有效的监控。一种简单的解 决办法是由控制机构定期查询或由工作者定期报告其状态，由控制机构确定其的 确存在。这涉及到容错机制，必须由系统对此提供专门的支持。 3 4 负载平衡的六种策略 在负载平衡算法中，调度的策略( p o li c y ) 与实现的机制( m e c h a n i s m ) 具有完 全不同的含义，需要特别区分。一般而言，策略考虑的问题为： w h e n ：何时进行负载平衡调度一何时进行进程迁移 w h i c h ：选择哪一个进程子任务进行迁移 w h e r e ：将进程子任务迁移到哪一个计算结点 机制主要考虑如何执行策略决定的问题，即：h o w 的问题。由于机制涉及的 是具体的实现方法问题，它一般处于相对较低的实现层次，与操作系统结合比较 紧密，实现比较困难。相对而言，策略发生更改或者替换的可能性比机制要大， 因而应当处于较高的实现层次。 负载平衡算法由六种策略“”1 构成。这六种策略为： 信息策略 转移策略 位置策略 选择策略 接受策略 决定策略 信息策略( i n f o r m a t i o np o l i c y ) 决定负载信息的收集、教布以及管理方法。 信息策略决定何时( w h e n ) 、如何( h o w ) 收集( g a t h e r i n g ) 负载信息，何时、如何散 布( d i s s e m i n a t i o n ) 负载信息以及如何管理负载信息。信息的收集可以采用周期 方式，也可以采用事件驱动方式；信息的散布可以采用周期性广播( b r o a d c a s t i n g ) 方式，也可以采用当有信息需求时由使用者进行轮询( p o l l i n g ) 的方式；信息的 管理可以采用集中管理的方式，也可以采用分布管理的方式。信息策略所获得的 信息被称为负载指数( l o a di n d e x ) 。 转移策略( t r a n s f e rp o l i c y ) 是由计算结点本身根据自身的负载状况，来决 定新生成的进程是否应当在本地运行，或者决定正在运行的活跃进程是否应当继 续在本地运行。调度决定的时机可以是周期方式，也可以是事件驱动方式( 如： 当进程结束时或者新进程到达时) 。负载阀值是转移策略用于衡量自身负载状态 的指标。 1 4 位置策略( l o c a t i o np o l i c y ) 决定迁移进程的目标结点。目标结点的选择需 要以其它结点的负载状况信息作为依据，因此，这种负载信息的一致性极大程度 地影响着目标结点选择的有效性。 选择策略( s e l e c t i o np o l i c y ) 用于决定适合进行迁移的进程。选择策略的主 要问题是迁移进程( 被迁移的进程) 的选择标准。进程的运行特性( 如：c p u 需求、 内存需求等) 对于迁移进程的选择有着决定性的作用。因此，如何对迁移进程的 未来运行特性进行预测是一个重要问题。 接受策略( a c c e p t a n c ep o l i c y ) 用于决定目标结点是否有权拒绝接受外来的 进程。源结点与目标结点之间的通信方式可以是单向的命令方式，也可以是双向 的协商方式。接受策略对于防止可能出现的进程的群聚( h e r d ) 效应，即进程的泛 滥( f l o o d i n g ) 与进程掠夺( l o o t i n g ) 具有很关键的作用。 决定策略( d e c i s i o nm a k i n gp o l i c y ) 主要用于决定以上不同策略在负载平衡 算法中的执行次序。负载平衡算法中各个策略的不同执行次序，尤其是选择策略 与位置策略的不同执行次序对负载平衡算法的性能有着不同的影响。 在这六种策略中，位置策略( w h e r e ) 和选择策略( w h i c h ) 是负载平衡算法的关 键，信息策略是负载平衡算法决策的基础。 3 5 信息策略 信息策略负责负载信息的收集、管理与散布。结点的负载指数( l o a di n d e x ) 和负载阀值( t h r e s h o l d ) 是负载平衡算法进行转移位置选择的基本依据。 3 5 1 负载指数的选择与自适应负载阀值调节机制 负载指标的选择可分如下三类： i 使用资源利用率作为负载指标 通常使用的资源利用率负载指标有c p u 、内存及i 0 三者。 c p u 资源。c p u 是计算机中最重要的资源之一，早期对于负载向量的研究都 考虑到了使用c p u 的利用率作为结点负载评价的标准。在使用c p u 利用率 作负载向量时，需要考虑各结点c p u 数量以及c p u 速度的不同。 内存资源。内存是计算机中另一项重要资源，对于内存需求大的计算，可用 内存的大小对任务执行时间长短的影晌比c p u 速率更为重要。当内存不足 时，会导致内存换页频繁而增加大量i o 操作，增加任务的执行时间。所以， 内存利用率不能使用百分比的利用率，而需要考虑绝对的剩余空间其他资源 还有网络资源、i o 资源等，需要根据具体作业的类型考虑。 2 使用队列长度 队列长度包括c p u 队列长度、i 0 队列长度等，这里我们只讨论c p u 队列长 度。c p u 队列长度普遍被认为是当前最优的负载平衡指标。其参数容易获取，用 于收集和处理该信息的开销小，且容易建立数学模型进行分析。使用c p u 队列 长度一般有两种，即使用当前瞬时的c p u 队列长度和使用一段时间内的平均c p u 队列长度， 使用队列长度，即当前结点上运行任务的个数作为负载向量有以下两个不 足：一是忽略了结点机性能的差异，这有点和上面c p u 利用率相似的考虑；二 是忽略了任务大小的不同。这些在讨论我们使用的负载向量时会有更具体的分 析。 3 使用综合策略 综合策略一般指同时考虑多项负载指标，以多种简单的负载向量为基准，通 过加权计算最后得出一个负载的综合值。 综合负载向量有两种综合，第一种是以上两种策略中多种指标的综合。例如， 使用队列长度时，既考虑c p u 队列长度，又考虑i o 队列长度；或者在使用资 源利用率时一般考虑多种资源。第二种是完全的综合，既考虑队列长度，又考虑 资源使用情况。对于简单负载向量的综合，一般使用线性函数： 州l ，2 ，。) = + 口。 ( 3 i ) - i 其中n 表示负载指标的个数，l ；表示某个负载指标，a ；表示该指标的系数。函数 ( 3 1 ) 中使用的系数( a 。，岛) 的有两个作用，首先是使各种负载向量的数 量级平衡。由于各种负载向量的类别不同，数量差异很大，如c p u 队列长度一 般小于1 0 ，或者是几十，而我们测试系统中结点剩余内存的大小有几十兆字节 左右，所以系数a ；首先要调节这种数量级上的差异。其次，系数要能够确定每种 负载向量在函数中的比例。 1 6 还有一些学者指出利用进程剩余时间总和来衡量结点负载的思想l “，该思想 的有效性前提是要求对各子进程子任务的资源需求情况迸行准确的预测，这在 一般程序中是比较难满足的。 在本文中，利用综合策略，考虑主要的三个因素：c p u 队列长度，内在可用 数量，i o 队列长度。然后利用函数( 3 1 ) ，求得一个综合的负载评定值。 通过定义负载阀值( t h r e s h o l d ) ，可以将计算结点的负载状况分为超载 ( o v e r l