一种用于实时集群的多任务负载均衡算法

文章编号：1000—3428(2003)12 0036——03

文献标识码：A

2003年7月 July 2003

中图分类号： TP301.6

一种用于实时集群的多任务负载均衡算法向建军，白 欣，左继章(空军工程大学工程学院电子工程系，西安710038)

摘 要：多任务负载均衡是集群并行处理中的一个重要问题。该文在分析轮转式调度算法和任务最少优先法的优缺点基础上，引入负载当量来更准确地描述集群节点的负载状况，提出了一种有效的负载均衡算法——负载当量轮转法，并采用以动态任务分配表为核心的多任务负载分配方式。最后，通过测试验证了该算法明显优于前两种算法。关键词：实时集群；负载均衡；负载当量轮转法；任务分配表

A Multipletask Load Balancing

Algorithm Used in Real-time Cluster System

XIANG Jianjun，BAI Xin，ZUO Jizhang

(Electronic Engineering Department of Air Force Engineering University,Xi'an 710038)

【Abstract】Multi-task load balancing is an important problem in the parallel processing of cluster. After analyzing the merits and demerits of round-robin algorithm and least tasks first algorithm, this paper introduces LW(load weigh) to describe the load state of cluster node more accurately. Furthermore, it presents an effective load balancing algorithm——LWRR and adopts the method of dynamic task distributing table to realize the algorithm. At last, the test results show the algorithm is prior to the front two algorithms.

【Key words】 Real-time cluster；Load balancing；Load weigh round robin(LWRR)；Task distributing table

负载均衡是并行处理中的一个重要问题，其解决的好坏各种任务调度算法都有优劣[4]。轮转式任务调度是最简单的直接影响整个系统的性能[1]。负载均衡的核心就是任务调任务分配方法，循环地将各个应用任务分配到各个计算节

度，将多个任务请求比较均衡地分布到不同的处理节点进行点，既可避免计算节点任务的分配失衡，又可减少系统的反并行处理，使各个有效节点的利用率最大，从而提高系统的应时间。但它没有考虑计算节点计算能力的差异和不同应用吞吐能力，保证整个系统的高效性。本文立足于任务级应用任务对计算节点负载的影响，只是按照任务数量简单地来衡问题，针对实时集群系统的多任务并行处理，在轮转式任务量计算节点的负载。最少任务优先分配法是任务负载均衡最调度法和任务最少优先法的基础上，采用负载当量更准确地直观的分配方法，将应用任务请求分配到当前应用任务数量刻画各个节点的负载状况，提出了一种改进的多任务负载均最少的节点机上，但应用任务最少并不等于节点的负载最衡算法——负载当量轮转法，进行任务级的负载调度与分轻，并且也没有考虑到节点机的计算能力的差异。配。实验证明该算法不仅提高了任务调度分配的均衡性，而为了能够客观准确地刻画各个计算节点的负载状况，引且有利于保证任务处理的实时性。入负载当量的概念，提出负载当量轮转法的负载均衡策略，

并采用以动态任务分配表为核心的任务负载调度分配方式。1 实时集群的多任务并行处理任务是资源分配的基本单位。针对实时集群系统，采用集群计算机技术能很好地实现多任务的并行处理[2]。整

任务的执行时间来描述各个任务请求的计算工作量，定义任个集群多任务的并行处理是在集群任务负载均衡策略的控制

务权值w表征各个任务在计算节点中负载的大小，任务权值下，将各个任务请求分配到不同的计算节点上进行处理。实

可用于对任务请求进行分类。对于异构集群计算机系统，各时集群采用的是全局集中式负载均衡策略，计算节点间的实

个节点的计算处理能力不尽相同，我们用节点资源权值cs来时任务调度分配是由控制节点来进行，控制节点只负责实时任务的调度分配；由多个计算节点共同完成整个多任务的实

时处理，属于任务级的并行处理。

实时系统是工作在时间约束下的系统，不但要保证计算结果的逻辑正确性，而且实时任务要在规定的时间内完成计算[3]。实时集群多任务并行处理的核心是实现多任务请求的实时调度和失效计算节点任务的实时性迁移，保证各计算节点的任务负载均衡，以达到任务处理的实时性要求和系统的高可用性。因此，在系统资源一定的前提下，实时任务调度的负载均衡策略是提高整个实时集群系统的关键问题。

lw=(∑miwi)/cs表示共衡量。定义计算节点的负载当量 ,K

i=1K

有K 类任务，w

i

表示相应的任务权值，mi表示任务权值

相等的任务数，cs表示节点的资源权值。负载当量将任务权

值、任务数量和节点资源权值相结合，较单纯的任务数量而言能更准确地刻画各个计算节点的负载大小。

基金项目：国家科技型企业技术创新基金项目(01c26226111003) 作者简介：向建军(1975－，男，博士生，研究方向：实时集群并)行计算，子波变换与语音信号处理；白 欣，博士生；左继章，教授、博导收稿日期：2002-06-20 修回日期：2002-08-092 多任务负载均衡的模型与策略集群系统多任务负载均衡算法的研究一直是集群计算机

的研究热点，用于任务请求调度的负载均衡算法有很多种，

—36—

定义N个计算节点的负载当量向量为：LW

={lw1,lw

2

,...,lw

N

}。

由负载当量向量可得最重载和最轻载计算节点的负载当量分别为：

lwmax=max(LW)、lwmin=min(LW)。

计算。此外，计算节点的定时中断服务进程定时单向发送自

身的信息软、硬件和负载状态给控制节点。()

控制节点多任务负载均衡算法：For(;;)

step1:控制节点收集本时统内有效计算节点数、有效计算节点号和有效计算进程号。

step2:计算本时统内各个有效计算节点的负载当量、负载当量差、平均负载当量和负载当量阈值。

step3:阻塞接收计算任务请求(taski)，根据计算任务类型，赋予相应的任务类型权值。

step4:判断并分配任务请求：

if(lwdiff>lwthres)

将计算任务请求分配到负载当量最小的计算节点，then填

充相应的动态任务分配表。

esle

将计算任务请求轮转地分配到各个有效节点，then填充相应的动态任务分配表。

step5:广播动态任务分配表给各个计算节点，转向step1。 Endfor

N个计算节点平均负载当量为： lw

ave

=(∑lwi)/N。

i=1

N

定义负载当量差为： lwdiff

=lwmax−lwmin

。

负载当量阈值为：

lwthres=lwave×10%。

负载当量阈值大小要对任务请求状况与集群节点间通信开销进行比较，应折中考虑。

针对轮转任务调度法和最少任务优先调度法的优缺点，在轮转任务调度法中融入最少任务优先法。当各个有效计算节点的负载当量差别不大时，顺序地将各个任务请求分配给各个有效计算节点；当负载当量差别较大，将任务请求分配给当前负载当量最小的有效计算节点。在实时任务负载均衡算法中引入负载阈值，结合任务负载最小优先分配原则，可以平滑突发性实时任务，改善了单纯轮转式任务调度算法的负载均衡能力。既保证了整个系统的负载均衡性，又提高了系统的实时性。

计算进程的算法：

For(;;)

step1:阻塞接收数据包。

step2:if( 接收到动态任务分配表)

then将动态任务分配表写入任务分配表共享内存，并且设置分配表有效标志。

elseif(接收到任务原始数据)

then将任务原始数据写入数据共享内存，并且设置任务数据有效标志。

endif

step3:if(分配表标志有效&&任务数据标志有效) (1)读取任务分配表共享内存和读取任务数据共享内存。task_process()/*本计算节点任务数据按照任务分配表进 (2)

行计算*/

step4:定时向控制节点的控制进程发送本机信息资源权值、(负载状况、软硬件状况等)。

Endfor

3 多任务负载均衡的算法描述在实时集群的多任务负载均衡模型中有两种任务进程：

一种是负责实时任务的调度和分配，由控制节点完成；另一种是实时任务的计算处理，由各个计表1 动态任务分配表 算节点完成。

控制节点运行多任务负载均衡调表头

度进程，在每个时统周期收集各个计任务类型权值算节点的信息，根据各个计算节点的任务处理精度负载状况，将当前接收到的应用任务任务处理节点号按照负载当量轮转法的策略，以动态任务处理进程号任务分配表的方式分配给各个计算节任务处理结果去向点。动态任务分配表采用动态链表的指向下一节点数据结构，每个链表节点有效数据结构如表1。

动态任务分配表的维护和更新是控制节点的调度核心，控制节点在下列时刻要更新任务分配表：(1)有新的任务请求；(2)有计算进程失效；(3)有计算节点失效。并且控制节点在动态任务分配表更新时采用单向广播的方式，不查询各个计算节点的状况，这样有利于降低系统资源的开销。

移动任务负载有时会导致计算节点接收大量的数据。在实时集群系统中应该尽量减少任务负载的移动次数。在负载当量轮转法负载均衡模型中，任务是资源分配的基本单位，我们规定只在计算进程或计算节点失效时才进行任务迁移：(1)当计算进程失效时，任务只在计算节点内部进行迁移； (2)当计算节点失效时，任务迁移到其它有效计算节点。任务迁移将失效节点或失效进程的处理任务视为新的任务请求，通过更新动态任务分配表将任务迁移给其他有效计算节点或有效进程。

计算节点中两个镜像的计算进程常驻内存。各个计算节点的任务处理不进行同步等待，计算进程在本节点有任务分配表和任务原始数据的情况下就进行本节点任务数据的处理

4 实验结果我们采用的实时集群计算机分为2个控制节点和4个计算节点，为同构集群系统。集群节点为浪潮NF300服务器，操作系统为Rtlinux，集群计算机节点通过千兆光纤以太网络互联。

定义负载均方差lwσ={∑(lwi−lwave)2}/N，lwi

i=1N

lwave表示平均负载大小，N表示节表示节点的负载大小， i点总数。在实验中，使用负载相对均方差 lwcomp=lwσ/lwave来衡量各集群节点机的负载状况。实时集群的控制节点运行多实时任务负载均衡进程，计算节点

运行两个计算进程。用不同计算量的高浮点运算程序段模拟

—37—

不同任务类型权值的实时任务请求。

(1)负载阈值选取对节点负载的影响

在负载当量轮转算法中，负载阈值参数的选取可以决定负载平衡算法的性能。在实验中，提交相同的任务请求，而通过估算系统并行通信开销选取不同的负载阈值，计算各节点的负载相对均方差，统计测试结果如图1。可见，在负载阈值取平均负载10%的时候，负载相对均方差较小。

算能力越强，模拟异构集群系统。控制节点根据节点信息)

中附加的节点资源权值进行任务调度和分配。同测试2一样，我们采用不同的任务负载均衡分配算法对集群系统各节点的负载相对均方差进行统计测试，结果如图3。可知，在异构集群系统下，由于负载当量中的节点资源权值体现了节点不同的计算能力，更体现了负载当量轮转法的负载均衡能力明显优越于其他两种算法。

２０％相１５％对均１０％方差５％ＡＢＣ２０％相１５％对均１０％方差５％０％任务差异小任务差异大ＡＢＣ

０％任务差异小任务差异大

图2 3 同构集群不同算法的测试图异构集群不同算法的测试5 结束语负载阈值(%)

图1 不同负载阈值的测试 (2)同构集群系统下不同均衡算法的性能测试

负载相对均方差不仅与任务负载均衡策略有很大的关系，也与多应用任务请求集自身有关。给集群系统提交两种分布的任务请求：1)任务差异小；2)任务差异大。在采用不同的任务负载均衡分配算法下，提交相同的任务请求，计算各集群节点的负载相对均方差，统计测试结果如图2。图中A为轮转法，B为任务最小优先法，C为负载当量轮转法。由图2可知，负载当量轮转法的负载均衡能力优于轮转法和任务最少优先法。

(3)异构集群系统下不同调度算法的性能测试

在负载当量中引入节点资源权值因子cs，而在同构系统中不能体现节点资源权值的作用(各节点的资源权值cs均相等。为此，在节点信息中附加一项节点资源权值，)4个节点的资源权值分别取1、2、3、4(资源权值越高代表节点的计

针对应用请求的任务级进行负载分配和均衡，本文在轮转法和任务最少优先法的基础上，提出了负载当量轮转法。首次采用负载当量刻画节点的负载状况，负载当量引入了任务权值和节点资源权值，较单纯的任务数量而言能更准确地刻画节点的负载状况，适用于多机多任务实时系统的粗粒度任务调度和网络计算的任务分配。负载当量阈值的确定是本算法的关键，如何更准确地根据集群系统并行通信开销和任务请求状况来确定负载当量阈值是本文进一步的工作。

参考文献1 .陈国良并行计算——结构、算法、编程北京高等教育出版社.:,19992 ,郑纬民石威高性能集群计算北京电子工业出版社..:,20013 ,毛羽刚金士尧并行与分布硬实时系统的调度计算机科学...1999 (9):51-544 ,徐万鸿宋佳兴基于节点机计算能力的网络计算体系计算机工程..与应用,2001,38(16):54-57

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆(上接第16页)

由上可知，定义作业流的控制流就如同编写一个结构化程序，简单明了。下面给出了一个作业流的结构化构造方法的应用示例。

使用作业流的结构化定义方法，可以将非结构化的作业流改造为结构化的作业流。例如可以将图3 (a)中的网状的作业流转化为图 3 (b)所示的结构化作业流。

显然，图3(b)的表达方法要比图3(a)的表达方式清晰得多，作业的执行过程一目了然。这样的结构化作业流易于构造，容易查错。这也证明了结构化作业流法的优势所在。

式。它简单、易用、灵活，有一个用以构造作业流的基本作业流的完备集，通过这个基集可以构造任何需要的作业流。基本并性组概念的提出使得并行作业的处理简明扼要，大大地方便了处理。

参考文献1 ,胡正国蔡经球程序设计方法学西安西北工业大学出版社..:,19902 .汤小春基于集群技术的作业管理系统的研究与实现博士论文[].西安西北工业大学:,2001-10

3 .范玉顺工作流管理技术基础北京清华大学出版社.:,2001

4 http://www.sw.nec.co.jp/middle/SystemScope/Products/gaiyou.html# top

2 结束语结构化构造方法的引入，极大地简化了作业流的定义形

—38—