（计算机应用技术专业论文）异构系统的任务调度和负载平衡研究.pdf

异构系统的任务调度和负载平衡研究 摘要 随着网络技术的发展，通过高性能网络互联的集群系统正成为实现高可伸缩 的、高可用网络服务的有效结构。但是由于节点和应用的动态性、复杂性以及资 源类型的多样性，集群系统在实际运行中常出现负载不均现象，大大降低了系统 的性能。因此，有效的负载平衡和任务调度技术是提高集群系统的整体性能的关 键因素。 在深入分析任务调度国内外相关研究现状后，针对系统环境的不同情形，分 别提出了基于树形扩散负载平衡算法和面向异构系统的自适应动态负载平衡算 法：在先进集群管理系统环境下，根据扩散路径上的每一个中间节点的负载情况 决定局部的剩余传播路径，并通过树形扩散负载平衡算法调度来维持集群系统内 部传输网络的负载平衡。 面向异构系统的自适应动态负载平衡算法由两个部分构成：首先动态的收集 系统中各节点的负载信息，计算出各节点在系统平衡后的负载量，用负载分布样 本方差公式判断启动负载平衡算法时机，然后给出负载迁移最佳时机的价值函数 和迁移负载的粒度公式，根据各节点的负载情况将节点分为重载、轻载、正常负 载三个集合，利用自适应策略从重载集合中选取节点与轻载集合中的节点进行负 载迁移，实现系统的动态负载平衡。此算法的突出特点是可根据应用问题的性质 动态的调整负载信息的常系数，以自适应的方式提高系统性能。 通过g r i d s i m 模拟器构造一个八个节点的集群系统，启用自适应动态负载平 衡算法，实验结果表明，随着额外负载的增加，自适应负载平衡算法比不进行负 载平衡的并行程序的执行时间增长要缓慢得多。 关键字：集群系统；异构性；动态负载平衡；负载迁移：自适应性 i i a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n i q u e ，t h r o u g ht h em e d i u mo fh i g h p e r f o r m a n c en e t w o r ki n t e r c o n n e c t c l u s t e rs y s t e mb e c o m eav a l i d c o n s t r u c t i o nt o p r o v i d eh i g h - s c a l a b i l i t ya n dh i g h - a v a i l a b i l i t yn e t w o r ks e r v i c e b u to w i n gt o t h e d y n a m i c sa n dc o m p l e x i t yo f n o d ea n da p p l i c a t i o na n dv e r s a t i l i t yo f r e s o u r c es t y l e ，l o a d u n b a l a n c ep h e n o m e n ao f t e no c c u ri nt h ec l u s t e rs y s t e ma tp r a c t i c a lr u n n i n g s od e b a s e s y s t e m i cp e r f o r m a n c e c o n s e q u e n t l y , t h ek e yt oi m p r o v et h ew h o l ep e r f o r m a n c eo f c l u s t e rs y s t e mi st h et e c h n i q u eo f l o a db a l a n c ea n dt a s ks c h e d u l e a t t e rd e e pa n a l y z i n gc o r r e l a t i o nr e s e a r c hs t a t u sq u oo ft a s ks c h e d u l eo f d o m e s t i c a n do v e r s e a s ，a i ma td i f f e r e n tc o n d i t i o no fs y s t e m i ce n v i r o m n e n t , al o a db a l a n c i n g a l g o r i t h mb a s e do nt r e es p r e a d i n gt h o u g h t sa n da l la d a p t i v ed y n a m i cl o a db a l a n c i n g a l g o r i t h mf o rh e t e r o g e n e o u ss y s t e mi sp u tf o r w a r dr e s p e c t i v e l y , u n d e re n v i r o n m e n to f a d v a n c e de l u s t e rm a n a g e m e n ts y s t e m ，t h ea l g o r i t h mw a r r a n td i f f u s ep a t hl a s te v e r y l a s ti n t e r m e d i a t en o d el o a d i n gc o n d i t i o nd e c i s i o nl o c a ls u r p l u sp r o p a g a t i o np a t h ，i n s u c haw a yt h a tt r e es p r e a d i n gt h o u g h t ss c h e d u l e rm a i n t a i nl o a db a l a n c i n go fc l u s t e r s y s t e mi n t e r i o rt r a n s p o r tn e t w o r k a na d a p t i v ed y n a m i cl o a db a l a n c ea l g o r i t h mi n c l u d e st w op a r t s a tf i r s t ，t h r o u g h c o l l e c t i n gd y n a m i c a l l yt h el o a dm e s s a g e so fa l ln o d e si ns y s t e m ，b yw h i c hc a l c u l a t e l o a dn u m b e ro f e a c hn o d ea f t e rs y s t e mb a l a n c e ，t h i sp a p e ru s eaq u i n t i cf o r m u l ao f l o a d s p e c i m e nd i s t r i b u t i o nt oj u d g et h eo p p o r t u n i t yo fs t a r t i n gt h el o a db a l a n c ea l g o r i t h m a n dt h e nt h ev a l u ef u n c t i o no ft h eb e s tt i m et om o v ea n daf o r m u l ao f l o a dm i g r a t i o n a r eg i v e nb yl o a db a l a n c ea l g o r i t h mq u a l i t a t i v e l y ，t h en o d e sc a nb ed i s t r i c t e dt ot h r e e s e t sa sh e a v yl o a d 、l i g h tl o a da n dn o r m a ll o a d ，t h en o d e ss e l e c t e di nh e a v yl o a ds e tb y u s i n ga d a p t i v et a c t i c sa r ec a r r i e do nt h el o a dm o v e m e n tw i t ht h en o d e si nl i g h tl o a ds e t ， a n dc o n s e q u e n t l yt h ed y n a m i cl o a db a l a n c eo ft h es y s t e mi sr e a l i z e d o t h e r w i s e ，t h e a i g o f i t h r nc a nr e g u l a t ed y n a m i c a l l yt h ec o n s t a n tc o e f f i c i e n to f l o a dm e s s a g ea c c o r d i n g t ot h eq u a i i t yo fa p p l i c a t i o np r o b l e m c o n s e q u e n t l yt h es y s t e mi so p t i m i z e da n dt h e p e r f o r m a n c ei si m p r o v e d p a s s i n gg r i d s i ms i m u l a t o rc o n s t r u c t i n gc l u s t e rs y s t e mw i t he i g h tn o d e s ，a n d s t a r t u pa d a p t i v ed y n a m i cl o a db a l a n c ea l g o r i t h m ，e x p e r i m e n t a lr e s u l tm a k es h o w , a l o n g w i t he x t r al o a di n c r e a s i n g ，r u n t i m eo fp a r a l l e lp r o g r a mw i t ha d a p t i v ed y n a m i cl o a d i i i b a l a n c ea l g o r i t h mi n c r e a s ef l o w e rt h a nt h a to f w i t h o u tl o a db a l a n c e k e yw o r d s ：c l u s t e rs y s t e m ；h e t e r o g e n e i t y ；d y n a m i cl o a db a l a n c i n g ；l o a dm i g r a t i o n ； a d a p t a b i l i t y i v 异构系统的任务调度和负载平衡研究 插图索弓 图2 1 集群结构图8 图2 2l v s 集群的体系结构9 图3 1 任务模型1 9 图3 - 2 三种通信模型下的完成时问2 0 图3 3 任务分配模型2 2 图3 4 通信时间与并行性2 3 图3 。5 通过任务复制来减少通信时间，2 4 图3 6 均衡负载分配策略2 5 图4 1 接受者驱动算法流程31 图4 2 发送者驱动算法流程3 2 图4 3a c m si d 结构说明3 3 图4 4a c m si d 消息扩散过程3 4 图4 5 初始负载所构成的二叉树3 7 图4 6 第一趟负载迁移后构成的二叉树3 7 图4 7 第二趟负载迁移后所构成的二叉树3 7 图5 1 负载平衡实现机制结构4 1 图5 2 动态反馈负载均衡算法的工作环境4 2 图5 3 并行矩阵乘的执行时间5 1 v i i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本文不包含任何其他个人 或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 五圾日期：力z 年罗月彭日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名：圣软 导师签 如v 日期：加z 年5 月j 3 日 日期：加6 年；月2 ) 日 硕士学位论文 1 1 选题背景与意义 第1 章绪论 本课题得到国家发改委重点项目( 计高技 2 0 0 0 1 2 0 3 4 号) 和教育部重点项目 ( 1 0 5 1 2 8 ) 的资助。 随着i n t e m e t 技术的迅猛发展，计算机技术已进入以网络为中心的计算时期， 网络技术、性能的不断提高，高可伸缩性、高可用性、可管理性、价格有效性的 网络服务技术将成为网络服务技术的主导。而摩尔定律的慢慢失效和人们为了追 求信息系统的高性能和高可靠性，单c p u 的集成电路技术和工艺慢慢走到了技 术的极限。再加上以高性能计算机为基础的计算科学得到了长足的发展，它与理 论科学和实验科学相辅相成、彼此印证，成为人类科学研究必不可少的方法之一。 在许多工业领域，如汽车、航空航天器的设计制造，石油勘探、地震资料处理及 国防( 核爆炸模拟) 等，科学计算已经成为首选研究方法。所以并行计算平台正 从昂贵专用的超级计算机转向集群系统，它是逶过高速互联网络连接起来的多台 自治计算机和相关资源组成的高性能系统。对集群系统的研究正成为一个新的研 究研究方向。 集群计算的主要目标是通过网络互连实现全系统范围内的资源的共享，并且 通过高效的资源管理和任务调度技术实现资源的有效共享，从而提高资源利用 率，获得高性能。在集群系统中，由于各节点、多种资源、管理机制、用户和应 用程序间存在大规模的异构性，所以对资源的管理、重用、交互和共享，以及如 何提高系统性能正成为一个突出的问题【啦】。高效的负载平衡算法和任务调度是 优化系统、提高系统性能的关键所在【3 】，它不仅能合理地利用系统中的各种资源， 还能平衡各节点的负载，充分发挥节点和资源的作用。 为了有效地协同不同任务在竞争处理器时的关系，我们用任务调度器来决定 处理器在什么时候执行什么任务【4 】。任务调度在处理任务之间关系时，有两种策 略：p r e e m p t i v e 和c o o p e r a t i v e 。在一个p r e e m p t i v e 系统中，一个任务在它的执行 时间里被赋予了优先权，这意味着s c h e d u l e r 能够根据系统所处的阶段将处理器 分配给其他的任务。对于需要长执行时间的任务来说，赋予优先权是一个非常好 的方法；重要性更高的任务将比重要性低的任务更有效地利用处理器。在一个 c o o p e r a t i v e 系统中，每一个任务在它的执行时间里独占c p u 。除非任务自动放弃 对处理器的控制，否则任务间的切换不会出现。有两种基本的调度方式：静态调 度( 根据时间来进行调度) ，和动态调度( 根据事件来调度) 。在静态调度方式 下，提前定义了任务的执行顺序。在动态调度的方式下，一个任务在运行其间是 否被执行由系统状态来决定。任务调度器根据当前的任务状态进行调整。在动态 调度方式下，只有当存在实际需要时( 出现一个外部事件) ，处理器才执行任务， 处理器的能力将得到更有效的利用( 这与静态调度方式无关) 。所以在集群系统 中，为了减少任务执行时间和通信成本，经常采用不同的任务调度策略来提高系 统的吞吐量和整体性能。 负载平衡问题主要分为静态负载平衡和动态负载平衡。人们利用系统的相关 信息，以数学公式或者是其它方法将静态任务进行划分【5 】并分配到集群系统的各 个节点上，间接地实现了静态负载平衡。而根据系统当前的负载状态，依照相关 策略将各节点上的任务进行调度，动态做出负载迁移的决定，直接地实现了动态 负载平衡。在大部分状况下，动态负载平衡所表现出来的系统性能明显优于静态 负载平衡。因此，动态负载平衡是许多研究学者的研究焦点v - s j 。 一个负载平衡算法一般由三个部分构成。首先制定任务放置策略的制定者使 用的负载和任务量，以及信息分配的方式；然后基于任务和计算机负载，判断是 否要把一个任务传送到其它计算机上处理；最后对于适合传送到其它计算机处理 的任务，选择任务将被传送的目的计算机。负载平衡算法的三个部分之间是以不 同的方式相互作用的。放置策略利用信息策略提供的负载信息，仅当任务被传送 策略判断为适于传送之后才行动。总之，负载平衡的目标是：提供最短的平均任 务响应时间；能适于变化的负载：是可靠的负载平衡机制。 由于集群系统构造的复杂性，节点和资源的广泛分布，以及资源动态变化， 应用之间的资源竞争对整体系统的性能影响很大。高效的负载平衡算法必须能够 充分利用节点资源、提高系统的负载平衡减少任务的完成时间。因此，资源利用 率、系统负载平衡和任务完成时间成为评价算法性能的标准。 1 2 本文研究内容 本文以集群系统的体系结构、负载分布、负载迁移时机、迁移粒度为研究目 标。首先对集群系统的体系结构进行了研究，针对于不同的结构可以将集群系统 模型化一个无向图。图中的节点，对应于系统中的处理机，然后通过分析影响任 务完成时间的关键因素和系统中处理机运行之闯的关系。可以将集群系统分为同 构系统和异构系统。本文所研究的对象主要是异构集群系统，它是由高速互联网 络连接起来的多台自治计算机组成的高性能的系统，计算节点是开放性的。用户 可以自由地向任何一个计算节点提交不同资源的需求任务，可以根据影响任务完 成时间的各个因素，动态的给出节点的动态权值以及负载分布样本方差公式，用 以决定启动负载的时机，在此基础上，提出了一种面向异构系统的自适应动态 硕士学位论文 负载平衡算法。该算法综合考虑了影响任务完成的各个因素，根据节点运行性能 和通信成本的关系，并定性地给出了相关公式，采用一定的策略实现系统的动态 负载平衡。最后通过与几个经典的动态负载平衡的实验分析比较，该算法能够很 好的实现系统负载平衡，提高系统的整体性能。 另外，通过对先进集群管理软件的体系结构的研究，提出了一种基于树形扩 散的负载平衡算法，它能克服消息传输中前端节点的内部网络接口成为瓶颈的问 题，并能使系统在有限步骤内快速的趋于理想平衡。 1 3 本文主要工作 本文首先从集群系统的特点、层次和体系结构出发，研究了的任务调度的模 型和通信模型，并根据影响任务调度的因素对任务完成时间的关系，提出了一种 面向异构系统的自适应动态负载平衡算法。具体内容如下。 ( 1 ) 任务调度 在研究分析集群系统的结构时，对集群系统进行了模型化，并对在集群系统 中进行任务调度作了深入的研究。任务调度分为二大类：一类是静态调度，静态 调度又包含没有时序关系的任务调度，存在优先关系的任务调度。在任务调度中 的关键问题是任务完成时间与通信成本之间的关系。由此给出了任务完成时间与 通信成本之间的价值函数。另一类是动态调度，动态调度又可以分为负载平衡和 自适应调度。 二、负载平衡 在对负载平衡的研究中，可以根据对任务的划分和分配将负载平衡分静态负 载平衡和动态负载平衡。本文主要是针对动态负载平衡策略进行研究。主要完成 如下研究： l 、负载分布，当系统处于负载不平衡状态下，如果马上启动负载平衡算法， 可能会增加节点和网络的负担，所以在启动负载平衡算法之前，必须对系统中各 节点的负载进行分析，所以给出了一个负载分布样本方差公式用以判断启动负载 平衡算法的最佳时机。 2 、动态信息采集与分析，因为系统中各节点的性能不同，所以系统如果处 于平衡状态下各节点所就具有的负载量也不同，因而必须进行动态信息采集与分 析，这样才能使我们对负载的状态有一个较准确的估计，这也是我们下一进行负 载平衡的基础教育，对负载信息的采集不能太过于频繁，否则会增加网络的负担， 而降低系统的性能。 3 、权值计算，通过收集的负载信息给出各节点的动态公值，这就能准确的 反映节点的执行能力，为负载迁移以及负载迁移粒度提供了一个根据。 = 一：= = = 一：= = ：一耋丝墼堡叁望墼堡墼鎏墅垒一= ：= = ! = ：= 兰一： 4 、任务粒度划分，当系统处于不平衡状态下，可能要进行负载迁移，如果 负载迁移的粒度太大，就会造成不必要的颠簸；如果迁移得太少，还抵不上迁移 负载的额外开销，又不划算。本文给了负载迁移粒度的公式，可以保证负载迁移 的粒度不小于节点在平衡状态下的负载量，并通过一个价值函数可以保证负载迁 移的粒度是值得的。 5 、价值函数，它是通过任务完成时间与通信成本的关系所给的。虽说影响 节点的执行能力的参数有很多，但最主要的是c p u 和内存。所以根据通信成本 与c p u 的速度和利用率以及内存大小、利用率和传输宽带构成个价值函数可 以判断迁移负载的时机。 1 4 论文组织结构 本文以介绍集群系统的概念、特点、层次、体系结构为起点，分析影响系统 性能的关键因素，并针对这此因素展开了深入的研究，对已有的相关算法进行分 析改进，按照从理论到模型设计再到算法的实现路线，提出了一种面向异构系统 的自适应动态负载平衡算法。最后通过与几种经典的动态负载平衡的实验结果的 比较和分析，验证了算法的正确性和有效性，得出该算法能减少任务完成时间、 提高系统负载平衡、优化系统和提高系统整体性能的结论。按照研究工作完成的 顺序，论文的组织结构和章节安排如下： 第一章为绪论，介绍本文的选题背景和研究工作的基础，并对整个研究使用 的方法与流程做简单的说明。 第二章为背景知识及研究现状，对集群系统、任务调度、负载平衡的特点、 层次、模型以及关键技术进行了介绍，提出了本课题的研究对象和目标。 第三章集群系统任务调度算法研究，对任务调度展开了深入的研究，发现了 影响调度的关键问题所在，为后面的新算法提供了理论基础。 第四章集群系统的负载平衡与智能调度，仔细研究了负载平衡算法的原理和 具体实现，并针对装有先进集群管理系统的集群系统环境下，提出了一种基于树 形扩散的负载平衡算法。 第五章面向异构系统的自适应动态负载平衡算法，对影响负载平衡算法的主 要问题进行展开，发现其中的关系，并进行了定性的分析，给出了它们之间的公 式，提出了面向异构系统的自适应动态负载平衡算法，通过新算法与几个经典的 算法的实验结果的比较，得出相关的结论。 最后是全文的总结和研究工作展望。 第2 章背景知识 本章首先介绍了集群系统的特点、层次和结构的优缺点，再对集群系统中任 务调度和负载平衡的关键技术、主要难点及解决途径进行研究，通过分析现在的 集群系统中的任务调度和负载平衡技术，提出本课题研究的对象和目标。 2 1 集群系统 小型化、并行化、网络化、智能化是当今计算机发展的主要趋势，集群系统 是这些发展的主要挑战性问题之一p “l ，也是当前计算机科学的一个研究热点。 集群系统是一种并行或者分布处理系统它由一组互连的单机组成，这些单机协调 工作提供一个单一的、完整的计算资源。它利用一定的智能机制实现动态的网络 范围内的资源共享，并随着资源供求的变化而变化。这引起机制给集群带来了可 扩展性而且允许灵活地使用工作站，因为集群或网络范围内的可用资源应该比 集群中某个节点、工作站上的资源充足。智能机制同样使得集群能支持多用户、 分时共享和并行执行环境。在这引起系统中，可以通过共享资源和动态分配负载 从而有效利用全局资源的功能。有效地开发工作站集群计算能力的想法已经在高 性能计算领域内得到高度重视，当前的趋势也更倾向于这种商品化的超级计算 机。集群计算已被认为是未来解决大型科学或商业计算的主流方案。 2 1 1 集群系统的特点 集群都是将普通p c 工作站、工作站或服务器通过某种方式连接起来构成的 多机系统。连接方式可以采取通过网络适配器和网络集线器，或通过将备个机器 的r s 2 3 2 串口直接连接起来，还可以通过内存通道卡和内存通道集线器的方式 连接各台机器。集群系统具有以下特点： 可用性。即它们都能够在集群的某部分资源出现故障的情况下继续向用 户提供持续的服务。几乎所有的典型集群都拥有灾难恢复功能。 集群系统有怠好的可扩展性。只需很少的配置工作就可以方便地向集 群中加入或删除工作节点。 典型的集群系统提供了良好的可管理性。管理人员通过简单的操作就 可以对集群中的工作节点或控制节点进行配置工作。 集群系统一般都提供了负载平衡功能。负载平衡包括静态负载平衡和动 态负载平衡，为了最大程度地利用集群中的一切资源，集群需要具有动 态负载平衡，为了最大程度地利用集群中的一切资源，集群需要具有动 异构系统的任务调度和负载平衡研究 态负载平衡功能，它能够通过监视集群中的实际节点的负载情况并动态 地进行调度的改变。 大部分集群系统都有一个主控机，它能够对集群中的机器的运行状态 进行监视，而且能够根据各机器的负载轻重进行任务的调度。 2 1 2 集群系统的类型 最常见的三种集群类型包括高性能科学集群、负载均衡集群和高可用性集 群。 ( 1 ) 高性熊科学集群 通常，第一种涉及为集群开发并行编程应用程序，以解决复杂的科学问题。 这是并行计算的基础，尽管它不使用专门的并行超级计算机，这种超级计算机内 部由十至上万个独立处理器组成。但它却使用商业系统，如通过高速连接来链接 的一组单处理器或双处理器p c ，并且在公共消息传递层上进行通信以运行并行 应用程序。因此，您会常常听说又有一种便宜的l i n u x 超级计算机问世了。但 它实际是一个计算机集群，其处理能力与真的超级计算机相等，通常一套集群系 统的配置开销要超过$ 1 0 0 ，0 0 0 。这对一般人来说似乎是太贵了，但与价值上百 万美元的专用超级计算机相比还算是便宜的。 某些并行集群系统可以达到如此高的带宽和低延迟，其原因是它们通常绕过 使用网络协议，如t c p i p 。虽然网际协议对于广域网很重要，但它包含了太多 的开销，而这些开销在节点相互已知的封闭网络集群中是不必要的。其实，那些 系统中有一部分可以在节点之间使用直接内存访问( d m a ) ，它类似于图形卡和 其它外围设备在一台机器中的工作方式。因此横跨集群，可以通过任何节点上的 任何处理器直接访问一种形式的分布式共享内存。它们也可以使用低开销的消息 传递系统，在节点之间进行通信。 消息传递接1 ：3 ( m p i ) 是并行集群系统闻消息传递层的最常见实现。m p i 存 在几种衍生版本，但在所有情况下，它为开发者访问并行应用程序提供了一个公 共a p i ，这样开发者就不必手工解决如何在集群的节点之间分发代码段。其中一 个，b e o w u l f 系统首先将m p i 用作公共编程接1 2 1 。很难决定使用哪种高性能集 群包。许多都提供类似服务，但计算的具体要求才是决定性因素。很多情况下， 在那些系统中的研究工作只是解决需求的一半，而且使用那些软件需要集群开发 者的特殊帮助和合作。 ( 2 ) 负载均衡集群 负载均衡集群为企业需求提供了更实用的系统。如名称所暗示的，该系统使 负载可以在计算机集群中尽可能平均地分摊处理。该负载可能是需要均衡的应用 碗士学位论文 程序处理负载或网络流量负载。这样的系统非常适合于运行同一组应用程序的大 量用户。每个节点都可以处理一部分负载，并且可以在节点之间动态分配负载， 以实现平衡。对于网络流量也如此。通常，网络服务器应用程序接受了太多入网 流量，以致无法迅速处理，这就需要将流量发送给在其它节点上运行的网络服务 器应用。还可以根据每个节点上不同的可用资源或网络的特殊环境来进行优化? 负载均衡集群在多节点之间分发网络或计算处理负载。在这种情况下，区别 在于缺少跨节点运行的单并行程序。大多数情况下，那种集群中的每个节点都是 运行单独软件的独立系统。但是，不管是在节点之间进行直接通信，还是通过中 央负载均衡服务器来控制每个节点的负载，在节点之间都有一种公共关系。通常， 使用特定的算法来分发该负载。 网络流量负载均衡是一个过程，它检查到某个集群的入网流量，然后将流量 分发到各个节点以进行适当处理。它晟适合大烈网络应用程序，如w e b 或f t p 服务器。负载均衡网络应用服务要求集群软件检查每个节点的当前负载，并确定 哪些节点可以接受新的作业。这最适合运行如数据分析等串行和批处理作业。那 些系统还可以配置成关注某特定节点的硬件或操作系统功能：这样，集群中的节 点就没有必要是一致的。 ( 3 ) 高可用性集群 高可用性集群的出现是为了使集群的整体服务尽可能可用，以便考虑计算硬 件和软件的易错性。如果高可用性集群中的主节点发生了故障，那么这段时间内 将由次节点代替它。次节点通常是主节点的镜像，所以当它代替主节点时，它可 以完全接管其身份，并且因此使系统环境对于用户是一致的。 在集群的这三种基本类型之间，经常会发生混合与交杂。于是，可以发现高 可用性集群也可以在其节点之间均衡用户负载，同时仍试图维持高可用性程度。 同样，可以从应用程序的集群应用中找到一个并行集群，它可以在节点之间执行 负载均衡。尽管集群系统本身独立于它在使用的软件或硬件，但要有效运行系统 时，硬件连接将起关键作用。 高可用性( h a ) 集群致力于使服务器系统的运行速度和响应速度尽可能快。 它们经常使用在多台机器上运行的冗余节点和服务，用来相互跟踪。如果某个节 点失败，它的替补将在几秒钟或更短时间内接管它的职责。因此，对于用户而言， 集群永远不会停机。某些h a 集群也可以维护节点间冗余应用程序。因此，用 户的应用程序将继续运行，即使他或她使用的节点出了故障。正在运行的应用程 序会在几秒之内迁移到另一个节点，而所有用户只会察觉到响应稍微慢了一点。 但是，这种应用程序级冗余要求将软件设计成具有集群意识的，并且知道节点失 败时应该做什么。但对于l i n u x ，大多数现在还做不到。因为l i n u x 系统没有 h a 集群标准，并且也没有公共a p i 可供应用程序开发者构建有集群意识的软 件。 h a 集群可以执行负载均衡，但通常主服务器运行作业，而系统使辅助服务 器保持闲置。辅助服务器通常是主服务器操作系统设置的镜像，尽管硬件本身稍 有不同。辅助节点对主服务器进行活动监控或心跳观察，以查看它是否仍在运行。 如果心跳计时器没有接收到主服务器的响应，则辅助节点将接管网络和系统身份 ( 如果是l i n u x 系统，则是i p 主机名和地址) 。 2 ，1 3 集群系统的结构 集群系统是由专用或通用网络上一组互联的计算单元及相关的资源构成的 一个整体，可被用户视为单一的计算环境使用【1 。一个计算单元可以是一个具 有存储器、i o 设备和操作系统的单机或者多处理器系统( p c 机、工作站或者 s m p 机器) 。一个集群一般指的是两个或者两个以上互相连接起来的计算机( 节 点) 。这些节点可以放在同一个机柜中，也可以分布在不同的地方并通过局域网 连接。一个( 通过局域网) 互连的集群对使用者和应用程序来说表现为一个单一 的系统。这样的系统能够廉价地获得原来只有昂贵的私有共享存储系统才具有的 特征和优点( 快捷而且可靠的服务) 。集群的典型结构如图2 1 所示： 并行应用程序 串行应用程序l| j并行编程森境 集群中间件 单一系统映象和可用性基础构架 p c i 作站 通信软件 网络接门硬件 p c 工作站 通信软件 网络接口硬件 p c 工作站 通信软件 网络接口硬件 p c 工作站 通信软件 网络接口硬件 p c 工作站 通信软件 网络接口硬件 高速网络，交换机 图2 1 集群结构图 网络接口硬件充当个通信处理器并且负责在集群各节点之问通过网络或 者交换机收发数据包。 通信软件在集群各节点以及集群和外界之间提供了一个快捷、可靠的数据通 信手段。具有特殊网络或者交换机的集群经常采用积极消息以便在节点间实现快 硕士学位论文 速通信。它们实际上绕过了操作系统，去掉了很多的通信开销，从而给用户提供 了到网络的直接访问接口。 2 1 4 集群系统的发展趋势 随着i n t e m e t 技术的迅猛发展，网络技术、性能的不断提高，高可伸缩性、 高可用性、可管理性、价格有效性的网络服务技术将成为网络服务技术的主导。 各种平台下的技术方案应运而生。其中影响最大的是由章文嵩博士成立了l i n u x v i r t u a ls e r v e r 的自由软件项目，进行l i n u x 服务器集群的开发工作。同时，l i n u x v i r t u a ls e r v e r 项目也是国内最早出现的自由软件项目之一。该项目针对高可伸 缩、高可用网络服务的需求，给出了基于口层和基于内容请求分发的负载平衡 调度解决方法，它通过前端一个负载调度器( l o a db a l a n c e r ) 无缝地将网络请求 调度到真实服务器上，从而使得服务器集群的结构对客户是透明的，客户访问集 群系统提供的网络服务就像访问一台高性能、高可用的服务器一样。客户程序不 受服务器集群的影响不需作任何修改。系统的伸缩性通过在服务集群中透明地加 入和删除一个节点来达到，通过检测节点或服务进程故障和正确地重置系统达到 高可用性。并在l i n u x 内核中实现了这些方法，将一组服务器构成一个实现可伸 缩的、高可用网络服务的虚拟服务器。 l v s 集群采用i p 负载平衡技术和基于内容请求分发技术。调度器有很好的 吞吐率，将请求均衡地转移到不同服务器上执行，且调度器自动屏蔽服务器的故 障，从而将一组服务器构成一个高性能的、高可用的虚拟服务器。整个服务器集 群的结构对客户是透明的，而且无需修改用户端和服务器端的程序。 l o a db a l a n c e rs e r v e rc l u s t e r s t o r a g e 图2 2l v s 集群的体系结构 为此，在设计需要考虑系统的透明性、可伸缩性、高可用性和易管理性。一 般来说，l v s 集群采用三层结构，其体系结构如图2 2 所示，三层主要组成部分 为： 负载调度器( 1 0 a db a l a n c e r ) ，它是整个集群对外面的前端机，负责将客 户的请求发送到一组服务器上执行，而客户认为服务是来自一个i p 地址 ( 我们可称之为虚拟i p 地址) 上的。 服务器池( s e r v e rp 0 0 1 ) ，是一组真正执行客户请求的服务器，执行的服 务有w e b 、m a i l 、f t p 和d n s 等。 共享存储( s h a r e ds t o r a g e ) ，它为服务器池提供一个共享的存储区，这样 很容易使得服务器池拥有相同的内容，提供相同的服务。 调度器是服务器集群系统的唯一入口点( s i n g l ee n t r yp o i n t ) ，它可以采用 i p 负载均衡技术、基于内容请求分发技术或者两者相结合。在i p 负载均衡技术 中，需要服务器池拥有相同的内容提供相同的服务。当客户请求到达时，调度器 只根据服务器负载情况和设定的调度算法从服务器池中选出一个服务器，将该请 求转发到选出的服务器，并记录这个调度；当这个请求的其他报文到达，也会被 转发到前面选出的服务器。在基于内容请求分发技术中，服务器可以提供不同的 服务，当客户请求到达时，调度器可根据请求的内容选择服务器执行请求。因为 所有的操作都是在l i n u x 操作系统核心空间中将完成的，它的调度开销很小，所 以它具有很高的吞吐率。 服务器池的节点数目是可变的。当整个系统收到的负载超过目前所有节点的 处理能力时，可以在服务器池中增加服务器来满足不断增长的请求负载。对大多 数网络服务来说，请求间不存在很强的相关性，请求可以在不同的节点上并行执 行，所以整个系统的性能基本上可以随着服务器池的节点数日增加而线性增长。 共享存储通常是数据库、网络文件系统或者分布式文件系统。服务器节点需 要动态更新的数据一般存储在数据库系统中，同时数据库会保证并发访问时数据 的一致性。静态的数据可以存储在网络文件系统( 如n f s c i f s ) 中，但网络文 件系统的伸缩能力有限，一般来说，n f s c i f s 服务器只能支持3 “个繁忙的服 务器节点。对于规模较大的集群系统，可以考虑用分布式文件系统，如a f s f l 2 j 、 g f s t l 3 , 1 4 1 、c o d a t 协1 和i n t e r m e z z o 1 6 1 等。分布式文件系统可为各服务器提供共享的 存储区，它们访问分布式文件系统就像访问本地文件系统一样，同时分布式文件 系统可提供良好的伸缩性和可用性。此外，当不同服务器上的应用程序同时读写 访问分布式文件系统上同一资源时，应用程序的访问冲突需要消解才能使得资源 处于一致状态。这需要一个分布式锁管理器( d i s t r i b u t e dl o c km a n a g e r ) ，它可 能是分布式文件系统内部提供的，也可能是外部的。开发者在写应用程序时，可 以使用分布式锁管理器来保证应用程序在不同节点上并发访问的一致性。 负载调度器、服务器池和共享存储系统通过高速网络相连接，如1 0 0 m b p s 交换网络、m y r i n e t 和g i g a b i t 网络等。使用高速的网络，主要为避免当系统规模 扩大时互联网络成为整个系统的瓶颈。 g r a p h i cm o n i t o r 是为系统管理员提供整个集群系统的监视器，它可以监视系 统的状态。g r a p h i cm o n i t o r 是基于浏览器的，所以无论管理员在本地还是异地都 可以监测系统的状况。为了安全的原因，浏览器要通过h t t p s ( s e c u r eh t t p ) 协议和身份认证后，才能进行系统监测，并进行系统的配置和管理。现在大多数 企业和研究机构都采用l v s 集群系统。 2 2 任务调度技术和主要问题 随着计算机网络的飞速发展，使用工作站和个人计算机进行分布并行处理虽 然是个非常有前景的途径，但这种集群计算也提出了大量困难和课题例如并行 算法的设计、任务的划分、通信的协调和同步、任务的调度。这些问题不解决， 则不能从并行分布处理中得到任何好处。在这些问题中，调度和负载平衡是一个 重要问题。它的根本问题是，当一个并行程序实现一组任务后，就需要将它们合 理或优化地分配到集群系统中的处理单元。如果这个问题得不到解决则有可能导 致分布计算效率低下，更有甚者，有可能造成其效率不如单机计算，甚至计算失 败因此，调度问题是分布计算的瓶颈问题之一。 2 2 1 调度问题的定义和分类 多任务的调度问题在计算机科学学领域说不是一个很新的课题但它还一直 是个远远没有得到很好解决的问题。 ( 1 ) 调度问题的定义 在分布系统中，一个程序可以看成是一个任务集，这引起任务可以并行或串 行地执行。任务之间一般是有优先次序约束的。调度问题的目标是要在满足一定 的性能指标和优先约束关系的前提下，将可并行执行的任务按适当分配策略确定 一种分派和执行顺序，合理分配到各处理机上有序地执行，以达到减少总的执行 时间的目的。 性能和效率是评价调度系统的两个基本特征。我们应以任务分派的质量和调 度算法的效率为基础来评价调度系统。调度质量以产生的优化调度的性能为基础 来衡量；调度算法的效率以时间复杂性为基础来衡量。 ( 2 ) 调度问题的分类 异构系统的任务调度和负载平衡研究 调度问题可以根据一个程序的任务是确定的还是非确定的来进行划分。确定 的调度是指被调度的任务和它们之间的相互关系在系统执行之前就可完全确定： 非确定的调度是指，只有部分初始任务是已知的随着系统的执行任务会动态地增 减。所以，一般将调度划分为两种形式的调度：静态调度和动态调度。 静态调度通常是在编译时已经确定了并行程序的特点和性质，如：任务的处 理时间、通信和同步要求、数据依赖等。也就是说，这引起特点在程序执行前都 是已知的，因而一个并行程序可以表示成由加权边和加权节点组成的有向无环 图，图中节点的权表示任务的处理时间，边的权表示数据依赖关系和任务间的通 信时间。使用静态调度对许多科学计算是非常有效的。例如，用图像处理方法进 行物体识别和数值计算等任务都非常适合静态调度的方法进行处理。 在动态调度中，调度中的许多问题都是未知的。动态调度的目标不仅是减少 程序的完成时间，而且还要减少调度本身的开销，这种开销就是运行调度程序本 身所付出的代价。通常有分布系统中，动态调度算法采用所谓“偷取空闲周期” 的方法来均衡各处理器之间的负载。然而，当调度的目标是减少某些特定应用的 执行时间时，这种方法是不适用的。 从上述调度问题的分类可看出，调度策略分为静态或动态的，在某种程序上 主要取决于任务分派的时间，时间静态调度可被看做是预调度，在编译时就可确 定哪些任务在哪台处理机上执行。显然这种策略需要所有的任务在执行前都是已 知的，执行调度程序的费用也可忽略不计。因为仅仅根据处理机编号和任务标识， 处理机就可以知道它应该执行哪些任务。如果任务的所有特征在编译时都可以确 定，静态调度就可通过某种有效的算法，合理地把任务分配到各处理机上【1 7 】。目 前