分类：
2008-10-15 16:28:32
引言
在多处理机系统中，经常出现这种情况：某些处理机负载过重而另外一些负载很轻，甚至空闲。这种情况无疑降低了整体系统的工作效率。为了提高处理机的利用率和系统并行计算的效率，应该把负载过重的处理机上的一部分负载转移到空闲或轻负载处理机上，这就出现了负载分配问题的研究。
简单的说，负载平衡就是要尽量均匀地分配任务，并尽量减少结点之间的通信。解决负载平衡问题，通常有静态和动态两种调度策略：
①静态负载平衡是根据系统的先验知识做出决策，运行时负载不能重新分配。
②动态负载平衡是根据计算机过程中数据项的变化情况，系统的状态信息来决定系统负载的分配。它具有超过静态算法的执行潜力，能够适应系统负载变化情况，比静态算法更灵活、有效。但是由于必须收集、并分析状态信息，因此动态算法会产生比静态算法更多的系统开销，不过这种开销和付出常是有所回报的。
本文描述了一种有效的多处理机系统的负载平衡模型，通过动态判断当前系统的负载情况，自动选择负载平衡算法，从而使整个系统以尽可能小的附加代价来达到全局的负载平衡。最后，在卡内基·梅隆大学的负载平衡框架上，搭建仿真环境进行模拟。结果显示，该模型能较好地平衡各结点的负载。
1 负载分配问题的数学描述
负载(1oad)是对一个处理机上运行的所有任务占用资源的衡量，负载指标(1oad index)是对负载进行量化的评价标准，不同的负载指标定义会得出当前时刻处理机不同的负载程度。关于这个问题，许多学者提出了他们的看法。
参考文献的研究表明，一般效果较好的是，将单项指标中的资源队列长度作为负载指标。参考文献[4]建议使用资源利用率而不是资源队列长度作为负载指标。近年来，随着CPU速度的快速增长。CPU和内存通信之间的瓶颈较为突出，内存空间的不足可能导致频繁的页面，这使得访问延迟大大增加。根据参考文献的研究，定义这样一个负载指标：
定义1 假设系统由N个处理单元构成，记为P0，P1，…，Pn-1。处理单元之间用通信线路连接，每个处理单元的负载记为WORK(i)，0≤i≤n-1。
其中，ε和ω为经验调整系数，O<ε≤10，K1<ω<+∞，ω为足够大的数；μ、L和M分别是处理机i的CPU利用率、运行队列长度和处理机i中所有任务请求的内存之和；Mem(i)为处理机i的可用内存。
整个系统的总负载为：
系统的平均负载wavg可以简单认为是：
Wavg=TotalWork／n
定义负载上界为W1=Wavg+ζ，负载下界为W2=Wavg-ζ。其中，参数ζ视具体系统之不同而定。
有了以上的基础，可以再进一步对各个结点的负载进行划分：某个处理单元的负载WORK(i)
2 嵌入式多处理机系统的动态负载平衡算法
一般来说，系统中每个结点上的任务是动态产生的，负载大小也是动态变化的。在完成任务的过程中，要周期性地检查任务完成的情况，并与其他结点交互这些情况。在此基础上，按照一定原则确定是否对任务进行迁移，以及迁移的源、目的结点和迁移量。
在动态负载平衡策略中，比较有代表性的算法是轻载结点请求算法和重载结点请求算法。在嵌入式多处理机系统中，一般情况下，根据系统当前的负载情况选用其中之一，可以有效地平衡负载；但是，当系统负载发生变化后，可能会由于原先选用的算法不合适而导致附加开销陡增，并且无法有效地平衡负载。因此，考虑到嵌入式系统本身的特点(例如资源有限等)，轻载结点请求算法和重载结点请求算法不加改进而直接用于嵌入式多处理机系统是不合适的。综合这两种算法的优缺点，就有了双向请求算法。
2．1 轻载结点请求算法
轻负载结点会尝试向重载结点请求任务，每个结点都定义了相关域，相关域的定义是把所有与之相邻的结点作为相关域成员。结点只与其相关域中的结点进行交互和任务传递。如果请求到任务，则中止请求，否则就继续询问下一个相邻结点。
启动时，所有结点几乎都是轻载结点。经过一段时间以后，结点开始检查自身是否仍是轻载结点，如果仍是，就试图在相关域中找出重载结点，并请求该结点上的任务。具体来说，设该轻载结点的负载为WORK(p)，相关域中有k个结点WORK(a+1)、WORK(a+2)……WORK(a+k)，则该部分的平均负载Wavg′为：
为达到任务的均匀分布，应求得相关域中重载结点应该传递给该结点的负载量(设为Mk)，但是必须对每个结点引入阈值H(j)，以避免任务从负载更轻的轻载结点迁移过来。若WORK(j)>Wavg′，则H(j)一WORK(j)一Wavg′；否则，H(j)=0。
然后，该结点就可以按照计算出的Mk值，向各个相关结点发出接收任务请求。
轻载结点请求算法流程如下：
①判断自己是否为轻载结点；
②如果是，则找出附近的重载结点，并对它发出任务请求；
③接收到请求算法的重载结点向该轻载结点发送任务。
轻载结点请求算法的优点是：不需要相互交换负载信息；当每个结点均处于忙状态时，不会有结点启动轻载结点请求算法，几乎不需要额外调度开销；处理负载平衡问题的许多工作是由空闲结点来完成的，没有给重载结点增加太多的额外负担。
缺点是：在开始和结束阶段时任务数相对较少，大量轻载结点会不断发出任务请求，并且这些请求中的大多数无法得到满足，于是许多轻载结点会继续发出请求。最终，大量的请求增加了系统的额外开销，影响了系统整体性能，同时大量针对重载结点的任务请求会拖延它们本身任务的执行。
在系统整体负载较轻时，使用轻载结点请求算法反而会造成较大的额外开销，不利于系统的整体性能。因此，轻载结点请求算法适合在整个系统负载较重时使用。
2．2 重载结点请求算法
重负载结点会尝试向轻载结点发送任务，至于发送任务给哪个结点，则取决于该结点相关域中结点的负载状态。因此，该策略需要交换处理器的负载信息。一个结点有多种方法向邻接结点通知它的负载情况，例如定期询问、当任务数发生变化时、接收到执行任务请求时、响应请求或者当任务数超过一定阈值时等。
启动一段时间以后，各结点开始检查自身是否是重载结点，如果是，就试图在相关域中均匀地分布任务。与轻载结点请求算法类似，首先计算域内的平均负载Wavg′，然后计算所要转移的任务量Mk。
设该重载结点的负载为WORK(p)，相关域中有k个结点WORK(a+1)、WORK(a+2)…… WORK(a+k)，则该部分的平均负载Wavg′为：
对每个结点引入阈值H(j)，以避免任务从负载更轻的轻载结点迁移过来。若WORK(j)>Wavg′，则H(j)=WORK(j)一wavg′；否则，H(j)=0。则Mk的值为：
然后该结点就可以按照计算出的Mk值向各个相关结点发送任务。
重载结点请求算法流程如下：
①判断自己是否为重载结点；
②如果是，则找出附近的轻载结点，并对它发出任务转移请求；
③得到同意后，重载结点向该轻载结点发送任务。
重载结点请求的优点是：如果没有过重负载的忙结点，就不会被空闲邻接结点所打扰。这在整个系统负载较轻时显得尤为重要。
[1]
