（计算机软件与理论专业论文）基于集群的不确定因素下的动态负载平衡.pdf

基于集群的不确定因素下的动态负载平衡 摘要 集群计算技术近年来己成为计算机界研究的一个热点。采用集群技 术来解决大数据量或时间复杂度高的问题不仅在计算机界，而且在其它 科学领域都是首选的。负载平衡是集群系统中的重要技术，用来确定任 务和节点机间的映射，提高系统性能。但往往需要用动态负载平衡来处 理很多不确定因素，如任务执行时间不确定、任务数量动态变化等情况。 本文针对任务执行时间不确定这一因素来研究动态负载平衡，寻求一个 负载调度策略和一个负载估计方法，使得任务在各个节点机上执行，按 照调度评价达到最优。本文主要在以下几方面进行研究： ( 1 ) 在前人四元组动态负载平衡模型的基础上，提出了五元组模型。 动态负载平衡涉及的面比较多，从物理环境到软件环境，以及各种策略， 都是相互影响的。五元组动态负载平衡模型，包含了硬件环境，调度环 境，任务分配，负载估计，调度策略以及调度评价等各个方面，用数学 形式定义，完整地表达了动态负载平衡的各个因素，使各个元素之闻的 逻辑关系更加明确，算法表达更加直观。用形式化语言来描述比用非形 式化语言更能表现问题的逻辑性。 ( 2 ) 根据提出的五元组模型及每个元素对应的解决方案，在l i n u x 集群环境下，一定的实验条件下，实现了动态负载平衡模型。任务分配 用数组下标的传递即可完成分配，不再依赖于系统内核，减少了许多烦 浙江师范人学硕士学位论文 琐的程序，且减少了数据量的传递。对于不确定因素即任务执行时间的 估计，提出了最大最小值法，相比前人做的工作，估计的准确性已经有 所改进。调度策略中把节点机状态精减为空闲机和重节点机两种状态， 由空闲机发起任务请求，主控机接收请求，计算出重节点机，由重节点 机发出起始任务下标给空闲机。这样的调度策略，算法简单，无论是主 控机还是节点机都不会占用太多的时问在任务调度上。 ( 3 ) 本文根据提出的五元组模型，主要对独立性强、任务间相关性 不大、任务执行时间不确定的任务进行实验。实验结果表明，本文的动 态负载平衡策略在同构集群上能够较好地提高任务的响应时间，负载平 衡效率有所提高，同时也进行了调度评价，结果较为满意。 关键词：集群，动态负载平衡，任务分配，负载估计，调度评价 d y n a m i cl o a db a l a n c i n gw i t hu n c e i 凇i n f a c t o rb a s e do nc l u s t e r a b s t r a c t c l u s t e rc o m p u t i n gi so n eo f t h ei m p o r t f i n tb r a n c h e si nc o m p u t e rs c i e n c e u s i n gc l u s t e rc o m p u t i n gt o r e s o l v e l a r g ed a t ap r o b l e m o rh i g ht i m e c o m p l e x i t yp r o b l e mi st h ef i r s tc h o i c ei no t h e rs c i e n t i f i cf i e l d s ，a sw e l lf i t si n t h ec o m p u t e rf i e l d m e a n w h i l e ，l o a db a l a n c i n gi st h ek e yt e c h n o l o g yo f c l u s t e rs y s t e m ，w h i c hi st od e t e r m i n et h em a p p i n gb e t w e e nt a s k sa n dn o d e s a n dt oi 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 h o w e v e r , d l b ( d y n a m i cl o a d b a l a n c i n g ) i sn e e d e dt od e a lw i t hs o m eu n c e r t a i nf a c t o r si nl o a db a l a n c i n g ， s u c ha st h et i m eo ft a s ke x e c u t i n g ，t h en u m b e ro ft a s k s ，e t e t h e r e f o r e ，t h e r e s e a r c ho f d l bi nt h i sp a p e ri sp r o p o s e db a s e do nt h eu n c e r t a i nt i m eo f t a s k e x e c u t i n g ，w h i c ha i m st og a i nal o a ds c h e d u l i n gs t r a t e g ya n dal o a de s t i m a t e m e t h o dt om a k et h es c h e d u l i n ge v a l u a t i o na t t a i nab e t t e rr e s u l t t h em a i n c o n t e n to f t h ep a p e ri sa sf o l l o w s ( 1 ) o nt h eb a s eo ff o u r - t u p l ed l b m ( d y n a m i cl o a db a l a n c i n gm o d e l ) p r o p o s e db yo t h e rs c h o l a r , t h i sp a p e ri n t r o d u c e saf i v e t u p l ed l b m d l b r a n g e s o v e r m a n ya s p e c t s t h a ta r e p h y s i c a le n v i r o n m e n t ，s o f t w a r e e n v i r o n m e n ta n da l lk i n d so fs t r a t e g i e s n e ya r ei n f l u e n c e db ye a c ho t h e r t h e f i v e - t u p l e d l b mi n v o l v e sh a r d w a r e e n v i r o n m e n t ，s c h e d u l i n g e n v i r o n m e n t ，t a s ka l l o t m e n t ，l o a de s t i m a t e ，s c h e d u l i n g s t r a t e g y a n d s c h e d u l i n ge v a l u a t i o n t h e ya r ea l le x p r e s s e dt h r o u g hm a t hd e f i n i t i o n t h e i i i 浙江师范人学硕七学位论文 f i v e t u p l ed l b mi n t e r p r e t st h ef u l la s p e c t so fd l ba n dm a k e st h el o g i c a l r e l a t i o n s h i pb e t w e e nt h ef i v et u p l e sm o r ec l e a rb yu s i n gf o r m a l i z e dl a n g u a g e ( 2 ) a c c o r d i n gt ot h ef i v e t u p l ed l b m a n dt h ec o r r e s p o n d i n gs o l u t i o no f e a c ht u p l e ，t h e p a p e r r e a l i z e dt h em o d e lu n d e rac e r t a i ne x p e r i m e n t a l c o n d i t i o n sb a s e do nt h el i n u xc l u s t e rs y s t e m t a s ka l l o t m e n ti sc o m p l e t e db y t r a n s f e r r i n ga r r a y si n d e x i t ss i m p l ea n di sn on e e dt oa c c e s sk e r n e lf i l e s t h i sp a p e ra d a p t st h em a x m i nm e t h o d ，w h i c hi sb e t t e rt h a nb e f o r ei nt h e a s p e c to fe s t i m a t ea c c u r a c y f u r t h e r m o r e ，t h em a c h i n es t a t u s e sa r er e d u c e d i n t ot w oo n e s ，o n ei si d l e n e s sa n dt h eo t h e ri so v e r l o a d e d f i r s to fa l l ，t h e f o r m e rs e n d sar e q u e s tt ot h ec o n t r o ln o d e o nr e c e i v i n gt h er e q u e s tf r o mt h e i d l en o d e ，c o n t r o ln o d ec a l c u l a t e st h em o s to v e r l o a d e dn o d et h a ti st os e n d t h ef i r s ti n d e xo ft a s k st ob ee x e c u t e dt oi d l en o d e i nt h i sw a y , a l lt h en o d e s s p e n dl e s st i m eo ns c h e d u l i n gt h et a s k s ( 3 ) e x p e r i m e n t sa r em a d ea c c o r d i n gt ot h ef i v e t u p l ed l b m b a s e do n t a s k st h a ta r ei n d e p e n d e n t ，h a v i n gal i t t l eo rn or e l a t i v i t y , u n c e r t a i ne x e c u t i n g t i m e t h er e s u l ts h o w st h a tt h es t r a t e g i e sp r o p o s e di nt h i sp a p e rc a nm a k et h e l o a db a l a n c i n gb e t t e r w h a t sm o r e ，s c h e d u l i n ge v a l u a t ，i o ns h o w st h a tt h e s t r a t e g i e sa r er e a s o n a b l e k e yw o r d s ：c l u s t e r , d y n a m i cl o a db a l a n c i n g ，t a s ka l l o t m e n t ，l o a de s t i m a t e ， s c h e d u l i n ge v a l u a t i o n 学位论文独创性声明 本人声明所里交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机 构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在 论文中作了明确的声明并表示了谢意。 研究生签名：谢覆 吼沙夕 够 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影印、缩 印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方式在不同 、 媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后遵守此协议。 研亮生鲰渤覆翩魏瓢r 眺弘“秘、 第一章绪论 利用集群计算技术来解决问题近年来己成为各领域研究的热点。集群不但能够 充分利用现有的闲置的计算机资源，而且能够使用较低的软硬件，实现较高性能的 计算机系统。随着处理器技术和高性能网络技术的飞速发展，集群系统逐渐成为一 种高性价比的并行分布式计算资源。 负载平衡是集群系统中的重要技术。使用相应的负载平衡技术克服了原有的高 性能计算的弊端，促进了相关领域的发展。 1 1 集群相关概念及分类 集群是一组相互独立的、通过高速网络互联的计算机，它们构成了一个组，并 以单一系统的模式加以管理。一个客户与集群相互作用时，集群像是一个独立的服 务器。采用集群进行并行计算可提高系统的可用性和可缩放性。 和传统的高性能计算机技术相比，集群技术可以利用各档次的服务器作为节 点，系统造价低，可以实现很高的运算速度，完成大运算量的计算，具有较高的响 应能力，能够满足当今日益增长的信息服务的需求。 且集群技术又是一种通用的技术，其目的是为了解决单机运算能力的不足、i o 能力的不足、提高服务的可靠性、获得规模可扩展能力，降低整体方案的运维成本 ( 运行、升级、维护成本) 。只要在其他技术不能达到以上的目的，或者虽然能够达 到以上的目的，但是成本过高的情况下，就可以考虑采用集群技术。 集群系统具有如下主要优点； ( 1 ) 高可扩展性：随着c p u 数的增加，一般系统性能单调递增； ( 2 ) 高可用性：集群的一个节点失效，它的任务可以传递给其他节点执行； ( 3 ) 高性能：负载平衡集群系统允许同时接入更多的用户； ( 4 ) 高性价比：可以采用廉价的符合工业标准的硬件构造高性能的系统。 因此，采用集群技术来解决大数据量或时问复杂度高的问题不仅是计算机界， 而且是其他科学领域都是首选的。 根掘集群系统的不同特征可以有多种分类，但是一般把集群系统分为两类：高 可用( h i 幽a v a i l a b i l i t y ) 集群，简称h a 集群。这类集群致力于提供高度可靠的服务。 高性能计算( h i g hp e f f e r m a n c ec o m p u t i n g ) 集群，简称h p c 集群。这类集群致力于提 供单个计算机所不能提供的强大的计算能力。 ( 1 ) 高可用集群 高可用集群就是采用集群技术来实现计算机系统的高可用性。高可用集群通常 浙江师范人学硕士学位论文 有两种工作方式m ： 容错系统：通常是主从服务器方式。从服务器检测主服务器的状态，当主服务 工作正常时，从服务器并不提供服务。但是一旦主服务器失效，从服务器就开始代 替主服务器向客户提供服务。 + 负载均衡系统：集群中所有的节点都处于活动状态：它们分摊系统的工作负 载。一般w e b 服务器集群、数据库集群和应用服务器集群都属于这种类型。 ( 2 ) 高性能集群 高性能计算( h i g h p e r f o r m a n c ec o m p u t i n g ) 是计算机科学的一个分支，它致力于 开发超级计算机，研究并行算法和丌发相关软件。高性能计算主要研究如下两类问 题： 一 大规模科学问题，像天气预报、地形分析和生物制药等；存储和处理海量数 据，像数据挖掘、图像处理和基因测序；顾名恩义，高性能集群就是采用集群技术 来研究高性能计算。 许多人对l i n u x 高性能集群时第一反映就是b e o w u l f 【2 1 。起初，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 足一利咱够将多台计算机用于并行计算的体系结构。通常b e o w u l f 系统由通 过以太网或其他网络连接的多个计算节点和管理节点构成。管理节点控制整个集群 系统，同时为计算节点提供文件服务和对外的网络连接。它使用的是常见的硬件设 备，象普通p c 、以太网卡和集线器。它很少使用特别定制的硬件和特殊的设备。 b e o w u l f 集群的软件也是随处可见的，像l i n u x 、p v m 和m p i 。 像b e o w u l f 一样，c o w ( c l u s t e ro f w o r k s t a t i o n ) 也是由最常见的硬件设备和软件 系统搭建而成。通常也是由一个控制节点和多个计算节点构成。c o w 和b e o w u l f 的 主要区别在于： c o w 中的计算节点主要都是闲置的计算资源，如办公室中的桌面工作站，它 们就是普通的p c ，采用普通的局域网进行连接。因为这些计算节点白天会作为工作 站使用，所以主要的集群计算发生在晚上和周术等空闲时间。而b e o w u l f 中的计算 节点都是专职于并行计算，并且进行了性能优化。它们采用高速网( m y r i n e t 或 g i g a n e t ) 上的消息传递( p v m 或m p i ) 进行进程浏通信( i p c ) 。 因为c o w 中的计算节点主要的目的是桌面应用，所以它们都具有显示器、键 盘和鼠标等外设。而b e o w u l f 的计算节点通常没有这些外设，对这些计算节点的访 问通常是在管理节点上通过网络或串口线实现的。因为连接c o w 中计算节点的通 常是普通的局域网，所以c o w 上的高性能应用通常是象s e t i h o m e 这样的 s i m d 的高吞吐计算。而b e o w u l f 无论从硬件、网络和软件上都对需要频繁交换数据 第一章绪论 的m i m d 应用做了特别的优化。 m o s i x 集群是种非常特别的集群，它致力于在l i n u x 系统上实现集群系统的单一 系统映象s s i ( s i n g l es y s t e mi m a g e ) 。m o s i x 集群将网络上运行l i n u x 的计算机连接成 一个集群系统。系统自动均衡节点| 日j 的负载。因为m o s i x 是在l i n u x 系统内核中实 现的集群，所以用户态的应用程序不需要任何修改就可以在m o s i x 集群上运行【3 j 。 1 2 集群系统的关键技术 1 高效的通信系统旧 集群计算机是基于高速通信网络互连而成的系统，网络性能的好坏对集群计算 机并行计算效率的提高、处理问题的适应范围以及系统的可扩展性都有很大影响。 通信延迟时间是衡量网络性能的重要因素，它包括协议软件处理开销和网络硬件处 理时间。在使用高速网络的集群系统中，影响通信系统性能的瓶颈已不再是网络硬 件的性能，而是通信软件的处理丌销。 传统的t c p i p 协议是为广域网设计的网际互连协议，它提供了强大而复杂的诸 多功能，这些功能必然带来很大的软件丌销，因此这种协议并不适合集群计算机进 行著行处理。为了降低通信软件处理丌销，需要通过精简协议，开发新的通信机制 和减少系统开销等方法，为用户提供一个低延迟、高带宽、高可靠的通信模式，达 到改善系统性能的目的。 2 并行程序设计环境 3 3 , 3 4 】 ， p v m 、m p i 、e x p r e s s 、p 4 等基于消息传递方式的并行程序设计环境为并行程 序的设计和运行提供一个整体系统和各种辅助工具。它们的功能包括提供统一的虚 拟机、定义和描述通信原语、管理系统资源、提供可移植的用户编程接口和对多种 编程语言的支持。目前研制的集群系统大多支持p v m 和m p i ，除了适应广泛的硬件 平台和编程方便等特点之外，它们都是免费软件，所以在支持语言、容错及工具等 方面都不完善，许多研究机构和大学正在做这方面的研究工作。 开发并行应用程序要比开发串行程序困难得多，它涉及多个处理器之间的数据 交换与同步，要解决数据划分、任务分配、程序调试和性能评测等问题，需要相应 支持工具，比如并行调试器、性能评测工具、并行化辅助工具，它们对程序的开发 效率与运行效率都有重要的作用。目i j ，提供工具较完善的系统有f a u s t 、 e x p r e s s 、t o p s y s 和v i d e 。 3 负载均衡和调度策略1 3 3 , 3 4 1 在集群系统中，一个大的任务往往由多个子任务组成。这些子任务被分配到各 个处理结点上并行执行，称之为负载。对于由异构处理结点构成的集群系统而言， 由于各结点的处理能力不同，相同的负载在其上运行的时间和资源占有率都不同。 因此，准确的负载定义应是绝对的负载量与结点处理能力的比值。当整个系统任舅 浙江师范人学硕士学位论文 较多时，分配给各结点的负载可能并不均衡，整个系统的利用率就会降低。因此， 有效地将各个子任务比较均衡地分布到不同的处理结点并行计算，使各结点的利用 率达到最大。这就是研究调度策略和负载均衡技术的目的。从任务分配决策的时机 讲，负载均衡技术可分为静态和动态两类方法。 4 故障恢复与容错1 3 3 , 3 4 1 随着集群系统逐步推广，人们对可靠性、可用性的要求越来越高，一旦因结点 故障导致整个集群系统失败，程序必须在系统恢复后从头开始执行，浪费了过去大 量有用的工作。因此要求系统能：( 1 ) 自动恢复瞬时、间歇性故障：( 2 ) 在人工干预前 提下恢复永久故障；( 3 ) 在线维修；( 4 ) 处理机资源的排他或限时使用；( 5 ) 为动态负 载均衡服务进行进程迁移。 目前常采用检查点设置和回滚恢复( e r r ，c h e c kp o i n t i n ga n dr o l l b a c kr e c o v e r y ) 技术来实现上述要求，即在程序运行过程中设置检查点，保存进程状态中决定程序 运行证确性的关键内容，当系统出现故障后，程序即回滚到最近的检查点接着执 行，无需从头开始。这是一种后向恢复技术，通过时问( 计算) 冗余，使系统从瞬 时、删歇故障引起的失败中自动恢复，辅助恢复永久故障，并实现进程挂起恢复及 进程迁移。 1 3 负载平衡及相关问题 集群系统的一个基本问题是如何将工作负载有效地分布到各个结点机以实现负 载均衡。对于集群这样的系统，由于任务到达的随机性，各个结点处理能力的差 异，以及在任务运行过程中产生的不确定变化，使得某些结点的任务较多，负载较 重，丽另外有些结点却是空闲的。 负载平衡是把负载信息根据各节点的负载状况进行分配调度，使各节点组成的 集群系统呈现出统一丌始工作，统一结束工作的结果，不会使部分节点因任务的完 成而空闲，同时使某些节点因任务负载过重而忙于处理。 负载平衡是一个广泛的概念，它不仅在计算机领域，而且在电力、通讯、流水 线生产的设计等行业都有其特殊的含义及作用。但是在计算机领域，负载平衡技术 显得尤其重要和突出1 4 1 。 在集群计算机系统中研究负载均衡技术的目的主要有以下两个方面【l 5 】： ( 1 ) 资源共享：观察表明，许多公司和科研单位的工作站或p c 机在大部分时间 里基本处于空闲状态。即使是在利用率较高的时间段，也有相当数量的机器空闲。 采用负载均衡技术，将作业分配到空闲工作站或p c 机上运行，既能缩短作业的平 均响应时间，又显著提高了工作站或p c 机的利用率。目前，这方面的研究已经进 入实用的商品化阶段。比较著名的产品有：i b m 公司的l l ( l o a dl e v e l e r ) ，p l a t f o r m 公司的l s f ( l o a ds h a r i n gf a c i l i t y ) 等。 4 第一章绪论 ( 2 ) 提高并行性能：此类负载均衡面向计算密集型的并行程序，目的就是缩短 程序的运行时间。由于并行模式的多样性，这方面的研究工作也相应地比较多，如 c a l y p s o ，c o n d o r 等。系统设计中的主要问题包括：如何预测并行程序的执行状 况；如何测量与评价工作站或p c 机的空闲情况；采用何种任务调度方式；是否以 及采用何种方式进行任务迁移；如何容错等。 由此可见，解决负载均衡问题可以极大地提高系统利用率，充分发挥各结点机 的性能，减少任务平均响应时间，从而使系统拥有最大的吞吐量。因此，负载均衡 策略就成为集群并行计算研究的一个重要方面。 往往导致负载不平衡主要是由于： ( 1 ) 某些算法的迭代大小不是固定的，但迭代的大小在编译时却可以被求得； ( 2 ) 某些算法的迭代大小不是固定的，并且迭代的大小依赖于被处理的数据， 在编译时无法求得； ( 3 ) 即使迭代大小是固定的，也会有许多不定因素导致计算速度的差异。 但是，重负载结点上的任务需要尽快地被完成；而且，那些结点空闲也是系统 资源的一种浪费。因此，负载平衡被用于对各个结点上的任务进行重新调度，通过 对未执行任务进行重新分配平衡各结点问的负载，从而避免这种空闲与忙等待并存 的情况，有效地提高资源利用率，减少任务的平均响应时间。 本文讲述的负载平衡是动态负载平衡。有些问题可以用静态负载平衡就可以解 决，它在任务初始分配时就决定分配，之后不再改变。而实际情况中存在许多不能 由静态负载平衡解决的问题，比如一个大的循环中，循环的次数是由外部输入的， 事先并不知道循环的次数，此时采用静态负载平衡划分策略就很难实现负载平衡。 总之，任务执行的不确定性是采用动态负载平衡的主要原因之一。 1 4 研究内容及意义 虽然当前处理器性价比越来越高，很多机构或单位都采用高性能多处理器并行 机进行实验和研究；但如果把在实验室闲置的p c 机组建起来搭成一个小型的集群系 统，仍是一个不错的选择。如在1 1 所叙述的，这样的小型集群类似于c o w 系统。 本文在实验室条件下，利用几台闲置的主机，对不确定任务执行时间、任务之 间独立性强的任务计算时进行动态负载平衡，使之效果接近最优。但是要做好动态 负载平衡，涉及到许多方面，从物理环境到软件环境，以及各种策略，都是相互影 响的。因此本文在前人四元组动态负载平衡模型的基础上，提出了五元组动态负载 平衡模型，该模型包含了硬件环境，调度环境，任务分配，负载估计，调度策略以 及调度评价等各个方面，它能完整地表达动态负载平衡的各个因素。 前人在研究负载平衡过程中，对于负载量的估计以及在重分配时如何转移任务， 往往要涉及到操作系统的机制问题，要从内核中去读取信息或转移进程，比较复杂 浙江师范人学硕士学位论文 和烦琐。基于这样的考虑。本文需要避开这些问题，引入数组，结合节点机空闲时 发出任务请求这一策略，把所有任务( 或索引) 存放在数组中，每个节点机保存有这样 的数组，信息传递只需要传递数组下标，因此就可以指导完成任务的转移。 经常有很多时1 1 日j 复杂度高，数据量大的任务需要进行并行计算，初时任务划分 时能够做到任务之日j 高内聚，低耦合；但往往不知道任务的执行时间，因此造成进 行初时分配或迸行重分配时要达到任务均衡就比较困难，因此，本文扶这个角度重 点来考虑如何较好地来估计任务量。 本文的研究为实验室集群并行运算提供一个负载机制，使计算能达到较高的效 率。 1 5 国内外研究现状 美国w i s c o n s i n m a d i s o n 大学的c o n d o r 系统可以在大多数u n i x 平台工作站 机群系统上运行。它出作业管理和资源管理弧部分组成。它的设计目的是调度长运 行时i 日j 的计算作业充分利用空闲工作站进行计算，并保证当空闲工作站的交互式用 户丌始使用机器时及时撤走它调度的后台任务。c o n d o r 不需要重新编译用户程 序，但需要把它们重新链接。另外，c o n d o r 研究小组还开发了一个系统接口 ( c a r m i ) ，将并行环境p v m 和c o n d o r 结合起来实现任务级负载平衡。 加拿大p l a t f o r m 公司的l s f 系统是一个典型的作业管理软件，它在任务调度、 负载平衡等方面有较好的特性。l s f 可以看成足一个通用型分布计算系统。它通过 对资源的较好利用，把机群系统集合成一个对用户来说是单一的系统。l s f 支持串 行或并行程序的交互式或批处理式运行，并提供c 语言函数库，使用户能够在编写 并行程序时利用l s f 的系统功能。l s f 核心山l i m 和r e s 两部分组成。其中 l i m ( l o a di n f o r m a t i o nm a n a g e r ) 的功能是负责收集本地负载信息，向m a s t e rl i m 报 告，由m a s e rl i m 对作业进行分配，并通知相应机器的r e s ( r e m o t ee x e c u t i o n s e r v e r ) 执行。l s f 具有对作业级的任务进行透明的集中式管理、各结点的r e s 接受 远程执行请求并提供透明执行等特点。 美国a r i z o n as t a t e 大学的c a l y p s o 是一个开发程序中的并行性的并行系统， 它向用户提供了一个扩展c 十+ 编程语言c s l ( c a | y p s os o u r c el a n g u a g e ) ，支持 d s m ( d i s t r i b u t e ds h a r e dm e m o r y ) 编程模式，相应增加了并行操作原语：s h a r e d ， p a r b e g i n ，p a r e n d 和r o u t i n e 。运行时系统进行动念负载平衡，并具有容错能力。 c a l y p s o 系统分离了逻辑并行性和物理并行性，使用户无需考虑数据划分和任务分 配”i 。 吉林大学的i l b o t 系统是用于工作站集群系统的粗粒度智能动态负载均衡软 件，它使用不同的资源指标来衡量不同类型的作业对资源的需求。c p u 类作业和 i 0 类作业分别使用c p u 利用率和i 0 利用率作为负载指标。对混合型作业同时使用 6 第一章绪论 c p u 利用率和i o 利用率作为负载指标：若各主机的c p u 利用率均达到满载 ( 1 0 0 9 句，则选用c p u 就绪队列长度作为负载指标。 i l b o t 系统通过大量的实验，在鞠九滨i7 l 提出的用资源利用率作为负载指标的 基础上，吉林大学胡亮f 8 j 详细描述了i l b o t 系统如何进行作业选择，充分考虑了不 同的负载环境对不同类型的作业响应时间的影响，并以此为依据来估算作业转移的 收益与开销。 负载平衡整个算法涉及的问题较多，从一开始的任务分配到后来的调度选择， 每个方面都是一个研究点。大部分的研究主要是针对负载平衡策略中的某一问题， 或者针对静态调度方法提出一个算法，对动态负载平衡算法的系统研究不多。但文 献 1 0 ，1 1 1 都提出动态负载平衡的一般模型，李冬梅l ”j 提出一个四元组来描述负载平 衡的各个方面，采用规则的分层负载平衡调度策略1 9 1 。陈华平1 1 1 】从不同的角度提出了 一个基于混合驱动策略的动态负载平衡模型，用数学语言来描述动作的相关性和交 互性。也有不少学者针对动态负载平衡中的调度策略进行研究，如使用主负载信息 表来维护负载信息1 1 2 1 ；又如文献 1 3 1 对负载均衡机制用形式化语言来分析。在讨论负 载平衡时，用形式化语言来描述方法，又用形式化语言来证明方法。清华大学傅强【1 4 1 分析并证明了一种适用与机群的“惰性”任务调度方法，即不借助进程迁移而实现低 开销的任务再分配，它与本文提出的任务不进行转移的思想是不一样的，它通过尽 量延迟任务的执行丌始时白j ，在任务再分配时避免了进程迁移。而文献 1 6 】所述的一 个有效的动态负载平衡算法，有比较大的参考价值，非常详细地考虑了对于确定任 务执行步骤的负载平衡。主要讨论了负载平衡的条件，通过移动产生的开销来和移 动后的结果权衡是否移动负载，但其基础是明确执行任务的步骤数，如针对单个的 矩阵相乘。 动态负载平衡最大的问题就是要知道未执行任务最多的信息，但往往在未执行 之前就难以获得某些信息，因此对于那些依赖于执行任务大小的很多调度方法都不 可用。h a u y e es i t l l 7 1 在众多的方法中却是避丌了任务大小的问题，通过估计前面任务 执行时间的多少来估计负载量，但这个方法过度依赖于前一任务，对于确定有哪些 主机进行负载平衡则采用了聚类算法，用聚类算法本身时间开销也大，平衡过程 中，最好能在最短的时间内作出决策。 a o s m a n 0 9 1 根据当今该领域的发展现状，总结了各种动态负载平衡技术在不同 环境下的应用，供其他研究人员比较并选择最适合的负载平衡技术。他对不同的负 载平衡算法进行分类，有中心算法1 2 0 , 2 1 1 ，r c n d e z v o u s 算法【2 2 i ，随机算法1 2 4 i ，滑动 窗算法口3 j 等，其中滑动窗算法把节点分成各个子区域，开始负载平衡时只在某些区 域内进行平衡，在下一平衡阶段，滑动到另外一些区域，两者只有部分区域是相交 的。而有些学者也详细地考虑了整个负载平衡的过程，如文献 2 5 1 提出了使用对象迁 7 浙江师范人学硕十学位论文 移，一个对象中有好多事件；采用两层机制，第一层中协调器负责决定有哪些主机 提供负载，哪些主机接收负载；第二层则是使负载进行迁移。在如何进行负载重分 配。该文章中提出重新分配任务时，根据该主机上一次负载平衡以来处理的任务数 来分配任务。但如果每次的任务性质相差很大，而且任务也不可能都是均衡的。 y a n g s u kk e e t z 7 l 采用把任务分配给执行速度快的主机的思想比较有参考价值。 但也存在一些情况，如果把任务分给馒主机，则所用的开销，可能比由原来的主机 执行还要多，总体时i 日j 可能更慢。文章主要是把消息分成一个个的基本消息，又证 明了当消息大于i k b 时，所用的丌销比较小，这又涉及到任务大小问题在不确定情 况下无法解决。对于任务的分配基本采用主机执行速度来分配，而关于负载移动则 没有较多的阐述。 d a v i dk a r g e r l 3 0 1 提出的分配任务的方法是在c h o r dd h t ( 一致性分布式哈希) 的环 境中，初始分配任务采用改进的一致哈希法，该方法是动态的，对于插入或删除去 改变任务的位置。文献也提出移动项来对有顺序的数据进行负载平衡，主要是采用 随机策略，是在p 2 p 框架路由的基础上。文献背景就是要在数据库中搜索，因此有 对应的应用环境。文献 3 2 1 与其类似，也是在点对点的异构系统中，但它的着重点 放在平衡不同的资源上，包括存储、带宽和处理器周期。 文献【3 1 】主要是对于分配任务采用重新分配的策略以消除初始分配的不均衡。 前提是基于已知任务大小的基础上，提出一系列的算法来提高最终的性能。 动念负载平衡技术的研究成果相对来讲不是很多，目前最流行的算法采用的技 术通常是针对一个特殊的问题领域，并在这个限定的范围内根据一定的条件开展研 究的。 1 6 本文内容的组织 本文是按照如下结构来组织的： 第一章为绪论，介绍了集群及相关概念、负载平衡及相关问题、国内外研究现 状以及本文的研究内容和意义等。 第二章介绍了负载平衡技术，重点介绍了动态负载平衡技术及其算法。 第三章在前人动态负载平衡模型四元组的基础上，提出了五元组动态负载平衡 模型，引入了调度评价因子，并解释了模型的各个因子，提出了本文的设计思路。 。第四章在实验室小型集群环境下，任务问独立性强的前提下，对本文的五元组 模型设计思路进行详细探讨，提出了剩余任务量的估计方法“最大最小法”，基于空 闲机发起任务请求的调度策略，以及主控机获得节点机“生存”与否的信息并作出 相应动作的策略。 一 第五章在前一章的基础上进行实验，对实验结果进行分析和评价。 最后对本文设计的不足和创新进行总结，以指导之后的研究。 8 第二章负载平衡算法 尽管负载平衡提出至今已有2 0 多年的历史，但是真正能令人满意的实现的系统 并不多，一个好的负载平衡算法，必须考虑以下的几条要求1 3 5 】： 有效性：算法的加入和运行，提高了系统的效率和性能，降低了任务平均响应 时间。为提高算法的有效性，要求系统用于负载平衡的附加代价尽可能小，并改善 通讯设备的性能。 稳定性：指系统正常工作的能力。特别是当系统大多数节点处于重负载状况 时，算法的运行，是提高系统的性能，而不是使系统负载的情况进一步恶化。为提 高系统负载平衡的稳定性，要求解决任务迁移的抖动问题。 可靠性：一个节点的崩溃，并不影响其他节点的正常工作。 用户透明性：用户不需要知道任务具体在哪台机器上执行，对用户来说，任务 的迁移及远程执行都是透明的。 2 1 负载平衡算法分类 负载平衡算法一般分为静态、动态和自适应三种。 静态负载平衡通常指映射问题或调度问题1 3 。 主要通过一些策略在一开始分配任务时就确定某台结点机执行哪些任务，而且 一旦确定就不予更改，直到任务结束。这种算法一般缺少灵活性，只对某些特定的 问题具有较高的应用性。可用的算法有循环算法，随机算法，递归对分，模拟退火 和遗传算法等。 动态负载平衡算法具有比静态算法更强的执行能力，把握系统的状态信息决定 系统负载的分配。这种算法利用系统执行过程中的负载波动来调节负载分配提高性 能。这样必然造成较多的丌销，如信息的收集、存储和信息分析等。但往往这种开 销能被抵消掉，j 下是因为具有更多的“利益”才会采用这种算法。 解决动态负载平衡的方法主要包括以下几种：基于随机选择任务移动结点的概 率调度算法【4 孔、根据负载变化而基于梯度模型的调度算法、自适应的近邻契约算 法【4 5 , , 1 6 1 等。 自适应负载平衡算法是一种特殊的动态算法，它们通过动态地改变其中的参 数、阙值和策略来调节其行为来适应变化的系统状态。一个简单的自适应算法能根 据对系统状态的观察来选择合适的负载平衡算法。因此自适应算法比动态算法更为 复杂，且牵涉到系统自适应理论和最优化理论，研究难度更大，目前实际应用较 少。 9 浙江师范人学硕士学位论文 本文研究的是基于近似易并行计算的动态负载平衡。主要针对任务执行时间的 不确定性讨论动态负载平衡的调度策略，形成一定条件下的通用性模型。结合静态 分配的高效性，初时任务分配采用静念分配的方式。执行过程中不考虑进程转移来 进行任务转移，利用数组来选择执行的任务对象。调度完全考虑空节点的任务请 求，进行任务重新分配。 2 2 动态负载平衡算法的构成 一个典型的动态负载平衡算法包含以下四个部分： ( 1 ) 转移策略 在调度活动的生命周期中，转移策略决定调度组中的结点是否处于合适的状态 来参与任务转移工作，充当任务转移的发送者或者接收者角色。一种普遍认可的转 移策略是阈值策略： 当某结点完成一个任务使其负载小于阈值扎时，就将该结点确定为接收者，为 轻载节点；当某结点从用户或者其它结点接收新任务，使其负载大于阈值 时，为 重载节点，就将该结点确定为发送者。此时称y l 为接收阈值，n 是发送阈值。阈值 设置要适当，如果闽值设置过低，负载量被人为提高：如果闽值设置过高，结点事 实上已经支持过重的计算，但表面上仍显得空闲。这种方法也称绝对转移策略，与 之相对的为相对转移策略，即在调度组中，确定相对于其它结点负载最轻的结点为 接收者，相对于其它结点负载最重的结点为发送者【1 0 l 。 ( 3 1 选择策略 在调度活动的生命周期中，选择策略在转移策略之后启动。一旦转移策略确定 了发送者之后，选择策略负责从该结点选择一个待转移任务，如果选择策略找不到 合适的转移任务，则该结点就不再被认为是发送者。最简单的选择策略方法是选择 导致垓结点成为发送者的新任务作为转移任务，此时任务转移的开销较小。选择策 略要考虑以下几个因素：转移的额外丌销尽量小，被选择的任务应该足够大，以值 得花去额外丌销p ”。 ( 4 ) 定位策略 定位策略主要选择待转移任务的接收者。在静念调度算法中，由调度服务器负 责定位、收集系统信息，发送者从调度服务器获得系统信息来确定接收者。在动态 调度算法中，一个广泛采用的方法是轮询，即采取串行或并行两种方式( 并行即广播 方式) ，由发送者询问其他每个结点以确定是否可以共享负载。 这种轮询方法有以下三种策略，z h o us o n g n i a n 3 7 对这三种策略作了比较： 随机策略：这是最简单的定位策略，任务被随机地选择发送到一个结点 上。随机策略不需要使用远程状态信息，因此结点之问不必彼此交换信息。随机策 略的缺点是，当整个系统的负载比较平均时，可能使所有结点都忙于转移任务而无 0 第二章负载平衡算法 暇去执行它们，为此，必须限定轮询的次数。 阚值策赂：为避免没有必要的转移，先要查看转移到某结点上是否会造成 该结点负载超过某个阈值，如果没有，就转移，否则，再看其他结点。为了减少额 外开销，与随机策略一样，阈值策略也需要限制轮询的次数。 最短策略：选择具有最短任务队列的结点作为转移对象( 即接收者) 。与前 两种定位策略相比，最短策略不仅能决定哪些结点可以接收任务，还能决定哪些结 点接收任务更好些。 ( 4 ) 信息策略 信息策略决定如何收集、从哪儿收集、收集系统及结点的哪些状态信息等。下 述为常见的三种信息策略类型： 要求驱动策略：一个结点只有在成为发送者或接收者时才去收