Linux集群之负载平衡原理和实现算法

核心提示： 梯度模型策略 在中心任务调度策略中，计算节点越多，Linux集群之负载平衡原理和实现算法(5)，冲突就越多，为了减少冲突，但随着时间的推移，轻负载节点实际上不久就可以接受被它拒绝接受的任务了，适应大量处理节点的需要，梯度模型策略、发送者启动策略和接收者启动策略都不设置专用的调度节点

梯度模型策略

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

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

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

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