（计算机系统结构专业论文）大规模集群系统的任务调度和资源管理.pdf

摘要 摘要 集群技术是分布式计算的一个重要发展方向，目前，国外对它的研究非常深入，但国内 还处于起步阶段。对于该领域的研究具有1 f 常重要的意义，因为它与国家经济建设的众多部 门都有密切关系，在提高生产力、促进经济发展上具有很大的潜力。现在随着技术的发展， 集群的规模变得越来越人，已有集群的规模达剑了上千节点，在这种犬规模集群环境卜如何 对集群资源进行有效的管理，如何对并行计算任务进行调度是重要的研究方向。因此，本文 将重点研究集群的资源管理和任务调度。 首先，在研究了现有集群资源管理系统的基础上，本文设计实现了一个集群资源管理系 统，该系统采用了分层分域的体系结构，避免分布式体系结构中网络消息过多的问题，减轻 了集中式的单节点瓶颈问题，提高了获取资源信息的实时性，具有良好的可扩展性，适用于 不同规模的集群环境，并且可以用于多集群。 然后，本文对d a g 并行任务调度算法进行了研究，以调度长度最小( 即执行时间最短) 和 减少所需的处理机数目为目标，设计了一个基于动态关键任务复制的多处理器分配算法。并 且将该算法的调度结果和集群资源管理系统中的资源实时状态信息相结合，设计了一个基于 负载均衡的集群资源分配算法。 最后，对并行任务调度和资源分配进行了仿真实验，对集群资源管理系统进行了性能测 试。 关键词：集群集群资源管理d a g 任务调度负载均衡 a b s t r a c t a b s t r a c t c l u s t e rt e c h n o l o g yi sa ni m p o r t a n td e v e l o p m e n td i r e c t i o no fd i s t r i b u t e dc o m p u t i n g ，a tp r e s e n t ， a ta b r o a dt h es t u d ya b o u ti ti sv e r yi nd e p t h d o m e s t i cr e s e a r c ho nt h ec l u s t e rt e c h n o l o g y , h o w e v e r , i ss t i l li ni t si n f a n c y t h i sf i e l do fr e s e a r c hi sv e r yi m p o r t a n tb e c a u s ei ti sc l o s e l yr e l a t e dw i t ht h e c o u n t r y sv a r i o u sd e p a r t m e n t so fe c o n o m i cc o n s t r u c t i o n ；i th a sag r e a tp o t e n t i a li ni m p r o v i n gt h e p r o d u c t i v i t ya n dp r o m o t i n ge c o n o m i cd e v e l o p m e n t w i t ht h ed e v e l o p m e n to ft e c h n o l o g y , t h e c l u s t e rs i z ei sb e c o m i n gi n c r e a s i n g l yl a r g e t h es i z eo fs o m ec l u s t e r sh a se x c e e d e do n et h o u s a n d n o d e s i ns u c hal a r g e s c a l ec l u s t e re n v i r o n m e n t ，i th a sb e c o m ea l li m p o r t a n tr e s e a r c hd i r e c t i o nt o e f f e c t i v e l ym a n a g et h ec l u s t e rr e s o u r c e sa n ds c h e d u l ep a r a l l e lc o m p u t i n gt a s k s t h e r e f o r e ，t h i s p a p e rw i l lf o c u so nc l u s t e rr e s o u r c em a n a g e m e n ta n dt a s ks c h e d u l i n g f i r s t l y , o nab a s i so fr e s e a r c h i n go np o p u l a rc l u s t e rr e s o u r c em a n a g e m e n ts y s t e m ，t h ea u t h o r d e s i g n e da n di m p l e m e n t e dac l u s t e rr e s o u r c em a n a g e m e n ts y s t e m t h es y s t e mu t i l i z e sl a y e r d m u l t i - f i e l da r c h i t e c t u r et oa v o i dm e s s a g ef l o o d i n gp r o b l e mi nt h ed i s t r i b u t e dn e t w o r k ，w h i c hc o u l d r e l i e v et h es i n g l en o d eb o t t l e n e c ka n di m p r o v et h er e a l t i m ep e r f o r m a n c eo ff e t c h i n gr e s o u r c e i n f o r m a t i o n t h i sa r c h i t e c t u r eh a sg o o ds c a l a b i l i t ya n dc a nb ea d j u s t e dt od i f f e r e n tc l u s t e r sw i t l l d i f f e r e n ts c a l e s t h e n ，t h i sp a p e rr e s e a r c h e di n t od a gp a r a l l e lt a s ks c h e d u l i n ga l g o r i t h m s w i t ht h eo b j e c to f d e c r e a s i n ge x e c u t i o nt i m ea n dn e c e s s a r yc o m p u t en o d e s ，t h ea u t h o rd e s i g n e dam u l t i - p r o c e s s o r a l l o c a t i o na l g o r i t h mb a s e do nd y n a m i cc r i t i c a lt a s kr e p l i c a t i o n a n db yc o m b i n i n gt h es c h e d u l i n g r e s u l to ft h ea l g o r i t h mw i t ht h er e a l t i m er e s o u r c es t a t u si n f o r m a t i o ni nt h er e s o u r c em a n a g e m e n t s y s t e m ，d e s i g n e dac l u s t e rr e s o u r c ea l l o c a t i o na l g o r i t h mb a s e do nl o a db a l a n c i n g a tl a s t ，t h ea u t h o rd i ds o m es i m u l a t i n ge x p e r i m e n t so np a r a l l e lt a s ks c h e d u l i n ga n dr e s o u r c e a l l o c a t i o n ，a n dd i ds o m ep e r f o r m a n c et e s t s0 1 1t h ew h o l ec l u s t e rr e s o u r c em a n a g e m e n ts y s t e m ， k e y w o r & ：c l u s t e r , c r m s ，d a gt a s ks c h e d u l i n g ，l o a db a l a n c i n g 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：堇魁整 日 期：2 丝：二哆 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：塑嫠筮导师签名：碰 日期：兰丝：兰) ，岁 第一章引言 1 1 集群技术简介 第一章引言 1 1 1 集群系统基本概念 随着计算机硬件、软件及算法的进步，国际上出现了除理论科学和实验科学以外的“第 三类科学”计算科学。在不少领域，计算己取代了实验成为科学研究的重要手段。作为科学 研究三大手段之一的高性能计算，不仅同科学技术与国民经济的发展密切相关，而且已经成 为体现一个国家综合国力的标忐。近十年来出现了许多不同的支持高性能计算的计算机系 统，集群作为一种易扩充、性价比高的方案得到广泛采纳，成为高性能计算领域令人瞩目的 焦点。 集群是一种并行或分布式处理系统，由很多连接在一起的独立计算机组成，像一个单独 集成的计算机资源一样协同。 作。计算机节点可以是一个单处理器( p c 、工作站) 或多处理 器的系统( 共享存储的多处理机s m p ) ，拥有内存、i o 设备和操作系统，它们作为一个整体 向用户提供一组网络资源。互连各+ 仃点的网络可以采用通用网络，如以太网、f d d i 、快速 以太网，甚至更高带宽的h i p p i 和a t m ，现在更为流行的是m y r i n e t ，l n f i n i b a n d ，g i g a n e t 这 些专用网络。集群系统由节点和网络组成，再配置上全局软件，构成了一种松散耦合的多机 系统。 一般我们把集群系统分为两类：高可用集群和高性能集群。高可用性集群致力于提供高 度可靠的服务，如所有的w e b 服务器、工业控制器和股票处理机等。高性能集群将多台机 器连接起来同时处理复杂的计算问题，致力于提供单个计算机所不能提供的强人的计算能 力。本文所讨论的高性能集群就是这种偏向于大型科学计算的集群系统。高性能集群上运行 的应用程序一般使用并行算法，把一个人的1 孚通问题根据一定的规则分为许多小的子问题， 能在同一时间内执行多条指令或处理多个数据，通过各节点的并行运行实现高性能的分布式 计算。 集群计算机系统的优势简单地概括为以下几点【lj ： 1 良好的扩展性 在集群系统中可以动态地加入新的服务器和删除需要被淘汰的服务器，从而能够最大限 度地扩展系统以满足不断增长的应用需要。 2 可靠性好 可靠性是服务型应用中最重要的因素，是评价和衡量系统的一个重要指标。集群计算机 的体系结构能够保证为用户提供不问断的服务，由于系统中包括了多个结点，当一个结点出 现故障时，整个系统中的其它节点仍然能够继续为用户提供服务。 3 性价比高 性能价格比和传统的人型主机和m p p 机器相比，具有很大的价格优势，而且具有水平 相当的性能。在实际应用中，性能价格比往往是决定一个产品可否生存的关键。 4 资源可充分利用 集群服务器的每个结点都是相对独立的机器，当这些机器不提供服务或者不需要使用的 时候，仍然能够被充分利用。而人型主机上更新卜来的配件就难以被重新利用了。 东南大学硕 ：学位论文 由于以上优点，集群技术已成为高性能计算机体系结构的发展趋势之一，并迅速成为高 性能计算机领域的主流体系结构。 1 1 2 集群管理系统 从系统组成的角度来讲，集群系统是由多台计算机组成的超级计算机，但是从最终用户 的角度来看，集群系统是一台计算机，所以，集群管理的目的就是让集群系统像一台计算机 一样利予管理和使用。集群管理作为集群系统的重要组成部分，它可以统一管理和调度各种 软硬件资源，保证用户可以公平合理地使用集群系统，从而提高整个系统的利用率。 不管是高可用性集群、高性能集群，还是负载均衡集群，集群管理始终是整个系统的核 心，它可以将物理上分散的计算机组织成一个系统，为用户提供单一系统映像( s s i ) 把1 ，保 障整个系统能够以较低的成本，提供强大的批处理和并行计算能力。归纳起米，集群管理系 统一般具有如下儿个功能： l - 资源管理：资源管理就是分配系统的资源和监控系统资源的使用情况，资源这个概念的 范嗣很广，各种硬件、数据和软件都可以看成是资源，比如c p u 、内存、数据库、可运 行程序，甚至是事件的l o g 等。 2 节点管理：能够动态收集节点的状态信息，并响应： 了点的请求，比如在系统运行中增加 和删除一个节点计算机。 3 任务调度：主要执行任务的调度策略，比如根据任务的需求将其分配到集群系统中合适 的节点上进行处理，当任务发生错误时，进行任务的迁移。 4 负载平衡：当集群中某个：l 了点负载过重时，可以将此j l j 点的负载平衡到其他节点上。 1 1 3 目前常见的集群管理系统 1 l s f 3 i l s f ( l o a ds h a r i n gf a c i l i t y ) 是由加拿人p l a t f o r m 公司开发的软件，它为异构u n i x 和 w i n d o w s 网络计算机环境提供了优越的分布式负载共享和复杂的作业执行日历功能。该系统 是基于u n i x 和w i n d o w s 操作系统之上的服务软件。利用所有可用的计算机资源快速处理 负载，大人提高了系统效率，l s f 提供一套a p i 扩展了负载均衡功能，使用这些a p i 用户可 以增强已有的应用程序的分布处理能力和资源共享的能力。 2 p b s 【4 】 p b s ( p o r t a b l eb a t c hs y s t e m ) 是由n a s a a m e s 研究中心和m r s 公司共同开发的通用作业 管理系统。它可运行在基于网络，多平台的u n i x 环境中，可以包括异构工作站集群，人型 机和超大并行系统，主要用于高性能计算领域。使用p b s 管理计算机资源可以增强用户需 求与高性能计算间的理解；增加已有资源的利用率，扩展它们的生命期：对所有计算机具有统 一的接口；减少管理员和操作者的负担；提高服务质量p b s 具有扩展性，灵活性，可操作性， 开放性等特点。 3 b e o 、u l f f 5 】 在科学计算领域中，比较成功的例子是高性能集群系统b e o w u l f , 它最初是由n a s a 的 g o d d a r df l i g h tc e n t e r 进行开发的，主要目的是支持大规模的科学计算问题，如地球和太空 科学面临的一些计算问题。 4 g a n g l i a t 6 l g a n g l i a 是由加州大学伯克利分校开发的，并被应用在了n p a c ir o c k s 项目中，完成对 2 第一章引言 r o c k s 系统的监控。g a n g l i a 系统是建立在分级基础之上，其结构为树状结构，这使得它有 着很好的可扩展性，可以容易的适用不同规模的机群，这也是它大规模服务器远程监控关键 技术及实现被j 泛应用与分布在世界各地的多个不同规模机群上的一个主要原网。基于 x m l 技术的数据传递可以使得系统的状态数据跨越不同的系统平台而进行交互，这是该系 统被广泛应川的另一个重要原冈。此外集中式的管理、低负载和系统的健壮也是该监控系统 的特色。g a n g l i a 由g m o n d 和g m e t a 两个基本模块组成，g m o n d 主要负责在集群的各个资源 诲点上采集和交换节点的资源信息，g m e t a 负责收集g m o n d 采集的节点资源信息。 1 2 并行任务调度算法简介 1 2 1 并行任务调度模型 并行计算环境下的调度问题是一类组合优化问题，在计算机及通信等许多领域有着广泛 的应用，在理论上又与算法设计、复杂性理论关系密切，因而引起了许多学者的研究兴趣【7 】【8 i 。 根据实际应用中的不同要求，存在很多种调度模型，g r a h a m 等人在1 9 7 9 年给出了一个任务 调度模型的标准描述【9 】，即口l l y ，其中。口代表机器环境描述，代表模型限制条件，y 代表优化目标或目标函数。 随着并行处理领域的飞速发展以及现实需求，近年来有更为实际的新模型被研究者们陆 续提出，并加以研究。这其中基丁有向无环图d a g ( d i r e c t e d a c y c l i cg r a p h ) 的并行任务模型 在多处理机上调度的研究在近2 0 年得剑了迅速发展。这种模型的机器环境是完全互连的同 构并行处理机，并且可以假定处理机数目无限。其限制条件是：任务执行具有1 卜抢一i 性，即 处理机只有在执行完某个任务之后才能处理另外一个任务。另外这些任务之间具有前驱后继 的依赖关系，即子任务只有在其所有的父任务处理完毕后才能开始执行。该模型的调度目标 就是要使得整个d a g 图的调度长度最短。早期的d a g 调度模型只引入了各个任务的执行时 间( 用每个节点权值表示) ，而并没有考虑任务之间的通信时间。即使是在这种情况下，这种 d a g 调度仍然被证明是n p 完全问题0 。b k r u a t r a c h u e 博十在1 9 8 8 年提出了包含计算通信 延迟在内的新的d a g 并行任务调度模型( n o d e - l a b e l e da n de d g e - 1 曲e l e dd a g ) ，并且证 明这种一般的d a g 调度仍然是个n p 完全问题。本论文的研究对象就是节点和边均有权值的 d a g 并行任务模型。 l 。2 2d a g 并行任务调度模型 并行任务可以用个节点和边均带权值的有向无环图来表示，节点的权值代表计算开销， 边的权值代表通信开销。它的详细定义如下。 定义l ：一个任务系统可以用一个四元组的有向无环图( d a g ) 表示为g = ( v ，e ，w ，c ) z 中。 v _ n ；l n ；为有序任务，i 2 1 ，2 ，3 ，i v l i v i 是任务数日 e = e ；ji e ；j 表示n ；到n j 的边，n ；称为n j 的父任务，n j 称为n ；的子任务 3 一 东南大学硕十学位论文 w = w ；i w 。表示n ；的计算开销 c = c ；。i c i , j 表示n i 到n ，的通信开销 n e d ( n i ) = n j j e j ，；e ) s u c c ( n i ) = 1 1 j | e 铲e 如果n i 没有父任务，则n i 为开始任务；如果n i 没有子任务，则n i 为结束任务。 1 2 3 基于d a g 模型的任务调度算法 几十年来，国内外的学者们已经对d a g 调度进行了广泛而深入的不懈研究，产生了很多 的d a g 调度算法，但归纳起来，这些各个时期的算法可以分成如下四类引：其一是表调度 算法( l i s ts c h e d u l i n g ) ，其二是聚簇调度算法( c l u s t e r i n g ) ，其二是基于任务复制的调度 算法( t a s kd u p l i c a t i o n ) ，其四是随机化搜索 技术的调度算法( r a n d o m i z e ds e a r c ht e c h n i q u e s ) 。下面分别予以阐述。 1 表调度算法 目前人部分的d a g 调度算法都是基于一种所谓的表调度技术( 1 i s ts c h e d u l i n g ) u 引，表 调度算法的一个基本思想就是通过给每个任务节点赋予优先级，从而确定一个调度序列，然 后重复执行以下两步直到图中所有二宵点被调度： ( 1 ) 从调度序列中移除第一个节点： ( 2 ) 把该任务= 话点调度剑可以最先执行该任务的处理机。 由于在传统的表调度算法中，那些调度表在任务节点调度到处理机之前就已经确定好执 行序列( 即静态创建) ，而且更重要的是，这种调度表在任务调度过程中不再更改，这样可能 在调度过程中造成那些本应优先执行的任务节点冈其优先级别低而迟迟不能执行的情况针 对此，近来人们提出了一种基于动态表调度( d y n a m i c1i s ts c h e d u li n g ) 的方法。该方法在 每次执行一个任务后，它就会重新计算所有朱被调度节点的优先级别，然后重新对调度表进 行排序。也即采用下面三个步骤： ( 1 ) 决定所有朱被调度节点的新的优先级： ( 2 ) 从调度表中选择优先级最高的：1 了点进行调度： ( 3 ) 把该任务节点调度到可以最先执行该任务的处理机。 一般来说这种动态表调度算法可以产生更短的调度长度，但是此方法也会大大增加算法 的时间复杂度。目前基于表调度的算法有e t f 以及m c p 引算法等。 2 聚簇调度算法 聚簇调度算法都假设处理机个数无限( 虚拟处理机) 。它的基本调度思想如下：在调度的 开始阶段，每个d a g 图的任务节点都被认为是一个簇。接下米便进行簇的合并，当然这些合 并要以不增加整个任务的完成时间为前提。该种合并操作要在最后没有任何簇可以合并时为 止。聚簇算法的思想是充分利用更多数目的处理机来最大程度减少任务的调度长度 ( m a k e s p a n ) 。冈为该方法都假设有无限个虚拟处理机，但实际上处理机数目总是有限的。所 以聚簇算法通常需要一个簇( 或者称虚拟处理机) 到现实处理机的一个映射过程。当然映射完 成后还要决定每个任务在各个处理机上的调度时间。 根据簇中有没有独立任务，聚簇算法又可以分为线性聚簇和非线性聚簇话大类。因为聚 4 第一章引言 簇算法具有阶段性的特点，所以它特别适用丁目前的一些任意处理机网络和异构系统的调 度。因为当d a g 图被聚簇后，根据簇到处理机的映射不同，还可以重新计算任务间的通讯延 迟和计算量的人小。这是因为在任意处理机网络和异构系统中，每个处理机的处理能力和处 理机间的通讯速率都会有所不同。现有的聚簇算法有d c p u 驯和e z d c p 1 等。 3 基于任务复制的调度算法 d a g 调度的实质也就是一方面减少任务之间的通讯延迟，另外方面就是要最人化任务之 间的并行度。如果调度策略选取不当，可能会抵消任务并行化所带米的收益。所以d a g 调度 算法必须要在这两者之问进行折衷。基于任务复制的调度算法的思想是：通过在不同处理机 上复制某个或某些任务，以此来减少任务间的通讯延迟。 近年来，为了寻求最小化并行任务的调度时间，人们开始不断研究怎样选取恰当的任务 复制算法。该算法对f o r k 图和j o i n 图可以产生最优的调度。这是显然的，因为对于f o r k 图而肓，我们只要在每个处理机上复制根节点，那么每个孩子节点都可以有最早的任务执行 时间。而对于j o i n 图，虽然没有必要复制每个父亲节点从而让孩子节点最早执行，但是任 务复制算法可以采用个类似递归的调度策略来最小化节点的开始执行时间，这样就可以产生 一个最优调度结果。当采用合理的复制策略时，任务复制算法能获得比其他算法较好的调度 性能引。现有的任务复制调度算法有c p f d 圳，d c t 他0 1 等。 4 随机化搜索技术的调皮算法 随着处理机技术和网络硬件技术的发展，并行处理所应用的平台己经从紧藕合的 l p p 机转向松藕合的工作站集群；并行任务的规模也在变人；d a g 调度算法的性能要求也越来越 高。为了在松藕合的工作站集群进行并行任务凋度，并获得较好的调度算法性能。必须要考 虑下面四个问题：算法性能，时间复杂度，可扩展性以及可应用性。 ( 1 ) 性能：一方面，一个调度算法必须总是产生高效的结果，譬如调度长度最短，用到 的处理机个数最少等等。另一方面，该算法必须具有鲁棒性，这是指算法必须对任何形式的 输入，譬如任意形状的d a g 和任意数目的处理机都能够产生好的结果。 ( 2 ) 时间复杂度：一方面，因为实际的输入往往是具有成千上万处理= 肖点的大型输入数 据。如果时间复杂度较高，将使得算法不适用。另一方面在实时调度系统中，只有快速的算 法才能产生高效的结果。 ( 3 ) 可扩展性：一方面指算法具有问题规模的可扩展性，即随着规模的扩大，算法总能 保证有效的输出，另一方面指算法具有处理能力的可扩展性，即随着处理机数目的增多，输 出结果会更有效。 ( 4 ) 可应用性：指算法必须考虑其实际运行环境。譬如任意大小的任务执行时间和通信 时间，链路竞争以及处理机拓扑结构的易变性等。 为了解决这些问题，人们提出了一些新的调度思想，譬如遗传算法，随机化方法和并行 调度技术等。这些新方法主要结合由前面的搜索结果所获取的知识和一些随机特征来产生新 的调度结果。用随机化搜索技术方法进行调度的结果比较好，但是它们的调度时间要比其它 类的算法高的多。另外譬如遗传算法( g e n e t i ca l g o r i t h m s ) ，它针对不同的d a g 图，其最优 控制参数也不相同，所以在实际调度过程中必须随时变更这些控制参数，从而造成不便。随 机化搜索技术方法包括遗传算法，模拟退火( s i m u l a t e da n n e a l i n g ) ，以及局部搜索技术 ( l o c a ls e a r c ht e c h n iq u e ) 等。 1 3 本文的研究背景和主要工作 现在随着集群技术的发展，单一集群的规模正在变得越来越大，如美国的s u n y 集群 由2 0 0 0 个：符点组成【2 1 1 ，这种大规模的集群环境带来了许多问题，节点数日众多，连接复杂， 5 东南人学硕上学位论文 产生的资源管理信息的数据量很大。如何对这些数据进行传输和存储? 通过对现有的集群资 源管理系统研究，发现现有的集群资源管理系统在单一集群内部主要采用集中式和分布式两 种体系结构，这两种体系结构在大规模集群环境卜存在着以下的问题： 1 在集中式体系结构下，资源管理上作由单一节点完成，中心管理节点负担大，其它节点 需等待此节点的处理结果。 2 在集中式体系结构下采j 甘轮询的方式无法及时获取所有 ，点的资源信息。 3 在分布式的体系结构下，每个：j 了点都要包含其他节点的资源状态信息，这样会造成网络 中的消息数目过多，在集中式的体系结构卜需要n i 条消息( n 为集群的13 点数目) ， 在分布式的体系结构下需要n 幸( n 1 ) 条消息，本文通过仿真实验证明，当集群一肯点数量 大到一定程度时，分布式的体系结构对集群的网络性能会产生严重的影响。 基于以上研究和分析，本文主要进行了以下的研究- t 作： 1 设计实现一个集群资源管理系统，采用分层分域的体系结构，避免了分布式的网络消息 过多的问题，减轻了集中式的单节点瓶颈问题，提高了获取资源信息的实时性，具有良 好的可扩展性，可以适用丁不同规模的集群环境，并且可用于多集群环境。 2 设计了统一分层的资源信息模型，来描述集群资源信息。 3 针对大规模集群产生的实时资源信息的数据量非常大的问题，通过对其汇总和统计以及 归档，减少了资源信息对存储空间的需求。 4 为集群用户提供统一的服务接口和单一的系统映象( s s i ) ，方便集群用户访问并使用集 群资源。 5 研究了现有的分布式b u l l y 选举算法的实现，提出了自己的改进方案，减少了重新触发 选取的次数，提高了系统的稳定性。 6 研究了现有的基于d a g 模型的并行任务调度算法，以调度长度最小( 即执行时间最短) 和减少所需处理机数日为目标，设计了一个动态关键任务复制多处理器分配算法。同时 考虑b a g 并行任务的调度结果与集群资源管理系统获得的集群资源实时状态信息相结 合，以负载均衡为目标进行集群资源的分配。 1 4 本文组织结构 本文共分为六章 第一章为引言，讲述集群技术的发展，介绍并行任务调度算法及本文的主要研究内容。 第二章分析了现有集群资源管理系统存在的问题，提出了自己的资源管理系统设计方 案。 第三章依照集群资源管理系统设计中建立的总体框架，全面介绍了资源管理系统的实 现，包括实现方法以及各大功能模块的实现细节。 第四章研究了动态关键任务复制任务多处理器分配算法，以及该算法的调度结果同集群 资源管理系统获得的资源状态信息结合，以负载均衡为目标进行集群资源分配 的，并进行了模拟测试。 第五章为集群资源管理系统的测试。 第六章是结论，总结论文所做的_ 作，及下一步的工作方向。 6 第一章 舭横集群雠w * 系统的& 计 第二章大规模集群资源管理系统的设计 在人规模集群环境f 如何对任务进乱有效的稠度，如何对系统资源进行台理的分配，是 集群系统中的掰个重要的研究方向。要解决这两个徊题，前先要对大规模集群环境f 所有可 州资源的状况进行监测，采集资源信息从而为任务调度和资渊分配提供决策依据，实现全 局范罔内资 ! 【的台理使川r 提高资源的使用效率。本章将介绍人规模集群资源管理系统的设 计方案。 2 1 现有的集群资源管理系统的体系结构 2 1 1 集中式体系结构 在集中式体系结构中，殴立一个中心管理节点，对所有订点进行集中式管理，所有节点 将资源信息发送到中心管理节点，使得中心管理竹点拥有全部资源信息易于调度整个系 统实现起来简单。集中式结构如图2l 所示。 图2l 集中式结构示意图 这样的结构存在以r 问豚，资源信息中心管理丁作由单一订点完成，这个节点负担大， 其它h 点需等待此节点的处理结果。当集群达到一定的规模时通过网络通信，资源信息管 理中心无法及时获取节点的资源信息，资源管理信息产生后，很难及时通知到所有相关廿点。 2 1 2 分布式体系结构 在分布式体系结构中，节点闻通过多播来交换资源信息这样每个节点都保存着其它节 点的资源信息，管理中心从其中的任意一个节点都能获得集群中所有节点的资源信息，减轻 0 l错 一d p 东南人学顿”论卫 了集中式体系结构中的单竹点瓶颁问题。但集中式体系结构中只需要n 1 条( 对) 消包，而 分布式体系结杠j 则需要n ( n 1 ) 条消息。当集群规模变大时会对网络造成严重的影响。目 前g a n g l i a 在一个集群内部采取分布式的体系结构，当一个集群的规模达到上千 点时，基 r 多播的数据交换的将无法根好的i 作“。分布式体系结构如刚2 2 所示。 n ，p 沙磷0 幽2 2 分布式体系结构示意剧 2 1 3 现有体系结构存在问题和改进思路 1 集中式体系结构中存在的问题 在采用集中式体系结构的集群资源管理系统中，每个集群节点上的资源管理程序每次接 到管理中心节点的请求时都霈要进行资源信息的收集，然后将收集到的数据格式化发同中 心节点。同样管理中心节点要验证由资源管理程序返回的数据格式的正确性解析井保存蛊 源信息的数据包。这样太培的时间消耗在到并个竹点读取数据上，而且节点数越多需要的时 间越多，假定在屉好的情况下，每次发送完采集命令后，立即可以收到遁厨信息，每个节点 需要mm s 的时间，这样如果在n 个节点的集群环境上，顺序读取一次的时间就是n * mm s ， 集群的1 1 点数日越多集群资源信息采集的实时性就越差。 2分布式体系结构中存在的问题 在采用分布式的体系结构的集群资源管理系统中，如g a n g l i a 采用多播的方法在集群中 的节点问交换资赶i 信息当集群的数目报人时这种分布式的多插方式产生的消息数目会很 多如有n 个节点组成的集群一次资源信息交换就会产生m ( n - 1 ) 条消息。 本文在实验室的集群环境f 对太规模集群环境f 的多描数据交抉进行了仿真，分别模拟 了3 0 节点、3 0 0 个讧点、6 0 0 个点、9 0 0 个节点和1 2 0 0 个1 1 点的集群环境。 模拟的环境是干兆蛆太网，由三十个节点组成的集群环境，r e d h a te n t e r p r i s el j 删3 4 操作系统，开旋语言c 语言，远程登录的s h e l l 为神。在每个集群节点上分别运行1 个、 1 0 个、2 0 个、3 0 个、4 0 个多播发送和接收程序。每移= 发送多播数据包的大小为2 5 6 个字节， 主要测试数据包的丢包率，测试结果如图23 所示。 0 图 第二章人规模集群资源管理系统的设计 o 2 5 02 0 02 0 04 0 06 0 0 8 0 01 0 0 01 2 0 0 模拟集群节点数目 图2 3 多播丢包模拟结果 对网络设备如交换机和路由器的主要性能评价指标是带宽和每秒分组数p p s ，一般我们 只会注意网络设备带宽这一指标，而每秒分组数这个指标会远远小于带宽，一般干兆交换机 理论上有1 4 mp p s ，在分布式体系结构下，当集群节点数日很大时。产生的网络数据包数 目非常巨大的，会严重影响网络的性能。如图2 3 所示当模拟： 了点数目达到1 2 0 0 个时丢包 率达到了2 5 。 3 本文的改进思路 通过对现有集群资源管理系统体系结构的分析，论文以解决存在的问题为切入点，提出 了本文的改进思路： 即在面临一个规模很大的集群时，根据集群的网络结构的特点，将其划分成多个较小的 管理域，管理域内的节点在物理位置上临近，如处于同一个交换机之下。 通过对不同的管理域设置不同的多播地址和端口，保证管理域内的多播消息不被发给其 他的管理域的节点，从而减轻网络负载。 通过b u l l y 选举算法矧在管理域的节点中选出一个领导者，由它将本管理域的资源信 息发送给上层的资源信息收集者。 基本系统结构如图2 4 所示。 9 5 0 0 0 静嗣傅 ：兮 o 0 东南 学砸i ，学位* i 图2 a 奉文的基本的系统结构 p 乞0 4 分析比较 文献“”提到，根据实验和实际的使用，g a n g i a 可以完全适用于数百个节点规模的集群 环境。假定集群的规模就是n 个节点，我们来比较改进扁的体系结构和6 a n g l i a 的分布式体 系结构以及冀中式体系结构的优缺点： 从系统产生的网络消息数目的角度米看，划分管理域的方法减少了产生的消息数目。 采用本文设计的体系结构，我们将n 个竹点的集群划分成m 个管理域，每个管理域 n m 个节点，这样每个管理域内缚次资源信息的交换周期会产生 ( ( n m ) 一1 ) x ( n m ) 条网络消息整个集群会有n ( ( n m ) 一1 ) 条网络消息，相比 较g a n g l i a 每次资i f ；f 信息的交换周期会产生的n x ( n 一1 1 条网络消息，减少了 n ( n l 卜n “n m ) 一1 ) = n x l n 一( n m ) 条网络消息。 从与管理中心建立的t c p 连接数目角度来看，与复中式相比减少了t c p 连接数目。 采埘集中式的c s 结构，中心管理节点耍和资源节点建立n 条的t c p 网络连接川丁接收 资源信息。本文采用的体系结构与上层的中心管理节点需要建立m 条t c p 连接来传送数据， 而g a n g l i a 只需要一个t c p 连接来传输数据。 从每个资源节点的角度米分析，减轻了对集群节点的资源消耗。 g 蚰g , l i a 集群中的每个节点在每次资源信息交换周期要处理n 1 个多播消息要保存n - 1 个 f ；居资源节点的实时资源信息数据。而采用本文的方 去，每个资源节点在每次资源信息的 交换周删要处理( n m 卜1 个多播消息，只要保存i n m 卜1 个邻居资源任点的实时数 据。资源管理系统的设计目标中，一个很重要的目标就是最小化对集群中节点的资源消耗。 从资源信息采集的实时性角度分析，提高资源信息采集的实时性。 在集中式轮询的集群资源管理系统体系结构下随着集群规模地增加，轮询一欢集群中 所有节点的周期一定会增加，当集群的规模大到一定程度，资源信息的采集的实时性会很差。 在分布式的集群资源管理系统体系结构下，晟主要的问题是，每次资源信息采集周期会产生 较多资源信息报文当集群的规模达到一定程度时，会对阿络产生严重的影响，这也限制了 第二章人规模集群资源管理系统的设计 资源信息采集的实时性的提高。本文采用的资源管理系统的体系结构避免了以上问题。通过 管理域的划分，减少资源信息报文的数目，同时每个管理域由一个领导者节点和管理中心进 行数据交换。如一个由6 0 个节点组成的集群，划分为2 个管理域，即使采用集中式轮询的 方式，只要轮询两个领导者节点就可以获得整个集群所有的资源信息。 2 2 资源管理系统的总体设计 2 2 i 资源管理系统设计目标 1 提供统一分层的资源信息描述模犁和统一的服务接口。结合系统的结构和资源在系统中 的位置建立对资源信息统一分层的信息描述模型，用x m l 来组织和表现该模型。通过 统一的服务接口隐藏系统内部的实现细节，向最终用户提供简单一致的服务。 2 对集群环境下的资源信息进行采集，定时采集集群中节点的资源静态和动态信息。 3 资源管理系统应能适用于不同规模的集群环境，并且可以适用于有多个集群组成的分布 式环境，具有可扩展性。 4 较低资源消耗，在科学与_ t 程的高性能计算应用中，对资源的需求是巨大的，而资源管 理系统本身对资源的消耗应当尽可能的低。 2 2 2 资源管理系统的总体结构 本文的主要任务是开发一个适用于大规模集群环境的资源管理系统的原形。系统采用了 “分层分域”的思想，在大规模的集群中划分对等的资源管理域，然后将各个局部资源管理 域进行整合形成统一的全局管理域。整个资源管理系统分为全局管理域和局部管理域。这样 的架构可以防止单点失效，提高系统的可扩展性。其逻辑结构如图2 5 所示。 图2 5 资源管理系统的总体框架 1 1 东南人学硕士学位论文 图2 5 中的管理域，是一组相邻资源的聚合，全局管理域、管理子域只是一种区分符号， 用来表明他们之间的父子关系，不同层次的管理域在逻辑上具有相同的结构和功能。每个全 局管理域的用户可以快速查找以该域为根的子树中的所有域的资源的基本信息和实时信息， 整个资源管理系统就是由一些资源管理域组成的树，根就是系统的全局管理中心。 资源管理系统在逻辑上采用图2 5 中结构，实际系统中，在底层由一些r e s o u r c ea g e n t 组成的管理域，r e s o u r c ea g e n t 运行在集群的资源。肖点上。在这些管理域中，r e s o u r c ea g e n t 模块在配置文竹中指定的多播地址和端口 2 4 1 上相且交换资源信息，这样管理域中的每个 r e s o u r c e - a g e n t 都保存管理域中所有的集群：1 了点的资源信息，通过b u l l y 选举算法在管理域 中选出一个r e s o u r c e - a g e n t 作为领导者将本管理域中的所有的资源信息发送给上一层的资 源信息收集者模块。资源信息收集者模块负责接收r e s o u r c e - a g e n t 发送来的资源信息，然 后按照统一的信息表示模型将数据进行汇总和存储，并且将汇总信息发送给上层的全局资源 信息收集者。各个层次的资源信息服务接口模块负责接收用户对资源信息的查询请求，对属 于下一层的资源信息的查询请求，可以定位并调用下一层的资源信息服务接口模块来获取实 时资源信息。因此系统实际结构如图2 6 所示。 图2 6 资源管理系统的总体结构 2 2 3 资源管理系统的组成 资源管理系统中每一个管理域都有资源信息服务接口、资源信息收集者、 r e s o u r c e _ a g e n t 。因此，系统从整体上是由三个相对独立又相互联系的部分组成的，它们的 1 2 第二章大规模集群资源管理系统的设计 功能如下： 资源信息服务接口：直接面向集群用户和上层应用，为用户提供统一的信息服务接口， 实现单一系统映像。资源信息服务接口的功能是接受用户和其他应用的合法的服务请 求，并且通过服务接口发布出资源信息。 资源信息收集者：是运行在各个局部管理域和全局管理域上的进程。在底层局部管理域 的资源信息收集者模块之下是多个r e s o u r c ea g e n t ，在这个层次的资源信息收集者模块 主要负责收集局部管理域内各个资源：l 了点的资源信息，并使用统一的信息模型米管理收 集米的资源信息，定时的向上一层的资源信息收集者模块发送本局部管理域的资源信息 汇总数据。在全局管理域中，资源信息收集者主要从各个局部资源信息收集者那里收集 各个管理域内的汇总的资源信息，用统一的信息模型对资源信息进行统一有效的管理。 r e