传送策略

为了简单起见，在选用传送策略时，多选用阀值策略。例如，Eager等人的方法是：在判断是否要在本地处理一个任务时，无需交换计算机之间的状态信息，一旦服务队列或等待服务队列的长度大于阀值时，就传送这个任务，而且传送的是刚刚接收的任务。而进程迁移能够迁移正在执行的任务，是对这种只能传送刚刚接收的任务的一种改进。

Zhou在模拟研究七个负载平衡算法时，其传送策略都采用阀值策略。它的阀值策略基于两个阀值∶计算机的负载阀值Load和任务执行时间阀值TCPU。如果计算机的负载超过Load并且任务的执行时间超过TCPU时，就把此任务传送到其它计算机执行。

 

放置策略

经过总结，共有以下四种放置策略。

1. 集中策略。每隔P秒，其中一个计算机被指定为"负载信息中心"（LIC），接受所有其它负载的变更值，并把它们汇集到一个"负载向量"中，然后把负载向量广播给所有其它的计算机。当一台计算机认为一个任务适于传送到其它计算机上执行时，它就给LIC发送一个请求，并告知当前负载的值。LIC选一台具有最短运行队列长度的计算机，并且通知任务所在的计算机把任务发送给它，同时，它把目的主机负载值增加1。
2. 阀值策略。随机选择一台计算机，判断若把任务传送到那台计算机后，那台计算机的任务队列长度是否会超过阀值。如果不超过阀值，就传送此任务；否则，随机选择另一台计算机，并以同样方式判断，继续这样做直到找到一台合适的目的计算机，或探测次数超过一个静态值限制LP，当任务真正到达计算机以后，不管状态如何，必须处理该任务。
3. 最短任务队列策略。随机选择LP台不同的计算机，察看每台计算机的任务队列长度，任务被传送到具有最短任务队列长度的计算机。当任务真正到达计算机，无论状态如何，目的计算机必须处理该任务。对此策略的一个简单改进时，无论何时，遇到一台队列长度为0的计算机时，不再继续探测，因为可以确定此计算机是一台可以接受的目的计算机。
4. 保留策略。 当一个任务从一台计算机离开时，该计算机检查本地负载，如果负载小于阀值T1，就探测其它计算机，并在R个负载大于T1的计算机中登记该计算机的名字，并把登记的内容保留到一个栈中。当一个任务到达一台超载的计算机时，就把这个任务传送到此台计算机栈顶的计算机上。如果一个计算机的负载低于T1，就清空栈里保留的所有计算机名。

Zhou的论文中，比较了（2）和（3） 三种策略，结论是：以简单（计算不昂贵）的方式，利用少量状态信息，第（2）中方法往往获得比第（3）种方法更好的效果。第（3）中方法比较复杂，它必须用性能的改善来补偿额外花费，所以取得的效果会稍差一些[2]。

算法实现

目前，常见的算法有：中心任务调度策略、梯度模型策略、发送者启动策略和接收者启动策略。

1. 中心任务调度策略

   顾名思义，中心任务调度策略就是让一个特定的处理节点担任计算任务分配器的角色，我们称之为调度节点，而把其它完成计算任务的处理节点称作计算节点。调度节点为了掌握任务分布情况，需要维护一个任务分布表。

   在任务启动时，调度节点装入任务的预分布情况表，而计算节点则开始完成分配给它的计算任务。在执行过程中，计算节点按照一定的周期向调度节点提交计算任务完成情况，由调度节点根据这些信息判断处理节点的处理能力，发出任务迁移指令，控制任务从重负载节点向轻负载节点流动，同时还要随之更新在调度节点上的任务分布表。

   中心任务调度的优点显而易见：调度节点掌握所有节点的处理能力和任务的分布情况，因此它可以在综合各种因素的基础上找到最佳的任务迁移方式。但是在计算节点很多时，所有计算机点都必然与中心节点通讯，必然导致严重的冲突，这会大大降低动态负载平衡的效率，甚至抵消动态负载平衡所带来的一切好处。

   另外，还应该注意到，调度节点在判断是否进行任务迁移时，计算节点必须等待，这无疑又浪费了计算节点的处理能力。一种改进的方法是调度节点在收到计算节点的当前任务完成情况时，立即存储之，并把根据上次的信息做出的判断返回给计算节点以减少延迟，在空闲时再根据本次收到的信息做出判断，留到下次使用。这样就把调度节点进行任务迁移决策的时间和计算节点完成计算任务的时间重叠了起来，降低了动态负载平衡的开销。

2. 梯度模型策略

   在中心任务调度策略中，计算节点越多，冲突就越多。为了减少冲突，适应大量处理节点的需要。梯度模型策略、发送者启动策略和接收者启动策略都不设置专用的调度节点，而且每个节点只与一部分节点进行交互，以减少由负载平衡导致的冲突。

   在梯度模型策略中，所有处理节点仅与直接相邻的节点进行交互，并引入两个阀值：M 1 和Mh。在运行过程中，我们将所在节点划分成三类：设一个节点的剩余任务量为t，如果t < M 1则称之为轻负载节点；如果M 1< t < M h则称之为中负载节点；如果t > M h则称之为重负载节点。另外，把从一个节点到与之最接近的轻负载节点的最短距离定义为这个节点的梯度。

   在启动时，每个节点都是重负载节点，梯度都是无穷大。在计算过程中，周期性地检查其剩余负载是否大于M1。当某一节点发现自身剩余的负载小于M1时就把它的梯度设为零，随后把自身当前的梯度与相邻节点间的距离之和发送给相邻的节点。相邻的节点接收到这个新梯度，就与自身当前梯度进行比较。 如果自身梯度小于等于新梯度，则不做任何事；如果自身梯度大于新梯度，则将自身梯度设置为新梯度，并向发送给它新梯度信息的节点一样传播新梯度。这样，梯度信息（实际上就是计算任务完成的情况）就会被传播开来，重负载节点就可以把它多余的负载发送给向临界点中梯度最小的节点。于是，计算任务就在梯度的引导之下从重负载节点流向轻负载节点。

   可是，按照这种方式，有可能导致过多的计算任务涌向一个轻负载节点。如果轻负载节点接收了过多的新任务，就有可能重新变成中负载甚至重负载节点。一旦出现这种情况，梯度信息就不再能够正确地引导计算任务了。为此，必须使轻负载节点察看要接受的计算任务，如果接收计算任务使本节点脱离轻节点状态，就拒绝接受它。这虽然延迟了任务的接收，但随着时间的推移，轻负载节点实际上不久就可以接受被它拒绝接受的任务了，同时还可以保持节点的梯度的有效性。

3. 发送者启动策略

   发送者启动策略也引入了一个阀值M来把所有的处理节点划分成轻负载节点和重负载节点，所有当前剩余负载t > M的节点都被称为重负载节点，t < M的节点被称为轻负载节点。发送者启动策略还需要为每个节点定义一个相关域，节点只与它的相关域中的节点进行交互和任务传递。一个直观的相关域的定义是把所有与之相邻的节点作为相关域。

   在启动时，所有节点开始执行计算任务。在执行一段时间之后，节点就开始检查其自身是否是重负载节点。如果是重负载节点，则它就试图在相关域中均匀地分布任务。具体地：设该重负载节点的负载为l p，相关域中有K个节点，其负载分别为l 1，…….， l k，则平均负载L avg为：

   

   为了达到均匀分布，应求得重负载节点应该传递给每个相关域中节点的负载量m k。我们首先引入h k以避免负载被迁移到相关域中负载最重的重负载节点。如果L avg> l k，则 ，否则h k= 0。那么m k为

   

   随后该节点就可以按照m k向各个相关节点发送任务了。

4. 接收者启动策略

   接收者启动策略与发送者启动策略除了是由轻负载节点启动，要求其它节点把任务发送给它之外，其它基本相同。

   接收者启动策略同样引入M以区分轻、重负载节点，引入相关域以确定交互范围。

   在启动时，所有节点开始执行计算任务，经过一段时间之后，一旦某个节点发现自身成为轻负载节点，就试图在它的相关域中均匀地分布负载。具体地：设该轻负载节点的负载为l p ，相关域中有K个节点，其负载分别为l 1 ，…….， l k，则平均负载L avg为：

   

   为了达到均匀分布，应求得相关域中节点应该传递给轻负载节点的负载量m k。我们首先引入权h k以避免负载从负载更轻的相关域中的节点被迁移到该节点。如果L avg< l k， 则 ， 否则h k=0。那么m k为：

   

   随后该节点就可以按照m k发出接受任务的请求了。