作者:许广斌
实现过程之理论先导篇(2)
本篇是实现过程的第二个理论先导篇，作者将向我们讲述负载平衡机制的理论研究。
在计算机硬件价格下降、计算机网络拓扑发展的情况下，分布式计算机系统给用户提供了一个丰富的资源集合。人们在研究分布式系统时，就注意到了这样一个问题：在一个由网络连接起来的多计算机环境中，在某一时刻，一些计算机的负载比较重，而另外一些计算机的负载却比较轻。平衡各计算机之间的负载是任务分配与调度的一个主要目标，它能够提高整个系统的性能。
为了改善系统的性能，通过在多台计算机之间合理地分配负载，使各台计算机的负载基本均衡，这种计算能力共享的形式，通常被称为负载平衡或负载共享。一般来说，"负载平衡"要达到的目标是使各台计算机之间的负载基本均衡，而"负载共享"意味着只是简单的负载的重新分配。
负载平衡包括两种，一种是静态负载平衡，一种是动态负载平衡。只是利用系统负载的平均信息，而忽视系统当前的负载状况的方法被称为静态负载平衡。根据系统当前的负载状况来调整任务划分的方法被称为动态负载平衡。
导致负载不平衡主要是由于：
某些算法的迭代大小不是固定的，但迭代的大小在编译时却可以被求得；
某些算法的迭代大小不是固定的，并且迭代的大小依赖于被处理的数据，在编译时无法求得；
即使迭代大小是固定的，也会有许多不定因素导致计算速度的差异。
考察这三个原因，对第一种情况可在编译时估计各迭代的工作量，按照处理节点的处理能力分布迭代，这就是静态负载平衡的方法。对第二、三种情况来说，必须采用动态负载平衡的手段，在运行过程中根据各个处理节点完成任务的情况，动态地迁移任务，实现动态负载平衡。进行动态负载平衡需要考察处理节点的处理能力，它的基本依据是根据处理节点先前的处理速度预见未来的处理速度。
负载平衡算法
一个负载平衡算法都包含以下三个组成部分：
信息策略：制定任务放置策略的制定者使用的负载和任务量，以及信息分配的方式。
传送策略：基于任务和计算机负载，判断是否要把一个任务传送到其它计算机上处理。
放置策略：对于适合传送到其它计算机处理的任务，选择任务将被传送的目的计算机。
负载平衡的上述三个部分之间是以不同的方式相互作用的。放置策略利用信息策略提供的负载信息，仅当任务被传送策略判断为适于传送之后才行动。
总之，负载平衡的目标是：提供最短的平均任务响应时间；能适于变化的负载；是可靠的负载平衡机制。
信息策略
人们用来描述负载信息采用的参数有：
运行队列中的任务数；
系统调用的速率；
CPU上下文切换率；
空闲CPU时间百分比；
空闲存储器的大小（K字节）；
1分钟内的平均负载。对于这些单个的负载描述参数，第（1）个，即采用运行队列中的任务数作为描述负载的参数被证明是最有效的，即它的平均任务响应时间最短，并且已经得到广泛应用。但是，如果为了使系统信息更全面而采集了更多的参数，则往往由于增加了额外开销，却得不到所希望的性能改善。例如，采用将六个参数中的某两个进行"AND"或"OR"组合，得到的平均响应时间反而比单个参数的平均响应时间还要差一些。
传送策略
为了简单起见，在选用传送策略时，多选用阀值策略。例如，Eager等人的方法是：在判断是否要在本地处理一个任务时，无需交换计算机之间的状态信息，一旦服务队列或等待服务队列的长度大于阀值时，就传送这个任务，而且传送的是刚刚接收的任务。而进程迁移能够迁移正在执行的任务，是对这种只能传送刚刚接收的任务的一种改进。
Zhou在模拟研究七个负载平衡算法时，其传送策略都采用阀值策略。它的阀值策略基于两个阀值∶计算机的负载阀值Load和任务执行时间阀值TCPU。如果计算机的负载超过Load并且任务的执行时间超过TCPU时，就把此任务传送到其它计算机执行。
放置策略
经过总结，共有以下四种放置策略。
集中策略。每隔P秒，其中一个计算机被指定为"负载信息中心"（LIC），接受所有其它负载的变更值，并把它们汇集到一个"负载向量"中，然后把负载向量广播给所有其它的计算机。当一台计算机认为一个任务适于传送到其它计算机上执行时，它就给LIC发送一个请求，并告知当前负载的值。LIC选一台具有最短运行队列长度的计算机，并且通知任务所在的计算机把任务发送给它，同时，它把目的主机负载值增加1。
阀值策略。随机选择一台计算机，判断若把任务传送到那台计算机后，那台计算机的任务队列长度是否会超过阀值。如果不超过阀值，就传送此任务；否则，随机选择另一台计算机，并以同样方式判断，继续这样做直到找到一台合适的目的计算机，或探测次数超过一个静态值限制LP，当任务真正到达计算机以后，不管状态如何，必须处理该任务。
最短任务队列策略。随机选择LP台不同的计算机，察看每台计算机的任务队列长度，任务被传送到具有最短任务队列长度的计算机。当任务真正到达计算机，无论状态如何，目的计算机必须处理该任务。对此策略的一个简单改进时，无论何时，遇到一台队列长度为0的计算机时，不再继续探测，因为可以确定此计算机是一台可以接受的目的计算机。
保留策略。当一个任务从一台计算机离开时，该计算机检查本地负载，如果负载小于阀值T1，就探测其它计算机，并在R个负载大于T1的计算机中登记该计算机的名字，并把登记的内容保留到一个栈中。当一个任务到达一台超载的计算机时，就把这个任务传送到此台计算机栈顶的计算机上。如果一个计算机的负载低于T1，就清空栈里保留的所有计算机名。
Zhou的论文中，比较了（2）和（3）三种策略，结论是：以简单（计算不昂贵）的方式，利用少量状态信息，第（2）中方法往往获得比第（3）种方法更好的效果。第（3）中方法比较复杂，它必须用性能的改善来补偿额外花费，所以取得的效果会稍差一些[2]。
算法实现
目前，常见的算法有：中心任务调度策略、梯度模型策略、发送者启动策略和接收者启动策略。
中心任务调度策略
顾名思义，中心任务调度策略就是让一个特定的处理节点担任计算任务分配器的角色，我们称之为调度节点，而把其它完成计算任务的处理节点称作计算节点。调度节点为了掌握任务分布情况，需要维护一个任务分布表。
在任务启动时，调度节点装入任务的预分布情况表，而计算节点则开始完成分配给它的计算任务。在执行过程中，计算节点按照一定的周期向调度节点提交计算任务完成情况，由调度节点根据这些信息判断处理节点的处理能力，发出任务迁移指令，控制任务从重负载节点向轻负载节点流动，同时还要随之更新在调度节点上的任务分布表。
中心任务调度的优点显而易见：调度节点掌握所有节点的处理能力和任务的分布情况，因此它可以在综合各种因素的基础上找到最佳的任务迁移方式。但是在计算节点很多时，所有计算机点都必然与中心节点通讯，必然导致严重的冲突，这会大大降低动态负载平衡的效率，甚至抵消动态负载平衡所带来的一切好处。
另外，还应该注意到，调度节点在判断是否进行任务迁移时，计算节点必须等待，这无疑又浪费了计算节点的处理能力。一种改进的方法是调度节点在收到计算节点的当前任务完成情况时，立即存储之，并把根据上次的信息做出的判断返回给计算节点以减少延迟，在空闲时再根据本次收到的信息做出判断，留到下次使用。这样就把调度节点进行任务迁移决策的时间和计算节点完成计算任务的时间重叠了起来，降低了动态负载平衡的开销。
梯度模型策略
在中心任务调度策略中，计算节点越多，冲突就越多。为了减少冲突，适应大量处理节点的需要。梯度模型策略、发送者启动策略和接收者启动策略都不设置专用的调度节点，而且每个节点只与一部分节点进行交互，以减少由负载平衡导致的冲突。
在梯度模型策略中，所有处理节点仅与直接相邻的节点进行交互，并引入两个阀值：M 1 和Mh。在运行过程中，我们将所在节点划分成三类：设一个节点的剩余任务量为t，如果t Mh则称之为重负载节点。另外，把从一个节点到与之最接近的轻负载节点的最短距离定义为这个节点的梯度。
在启动时，每个节点都是重负载节点，梯度都是无穷大。在计算过程中，周期性地检查其剩余负载是否大于M1。当某一节点发现自身剩余的负载小于M1时就把它的梯度设为零，随后把自身当前的梯度与相邻节点间的距离之和发送给相邻的节点。相邻的节点接收到这个新梯度，就与自身当前梯度进行比较。如果自身梯度小于等于新梯度，则不做任何事；如果自身梯度大于新梯度，则将自身梯度设置为新梯度，并向发送给它新梯度信息的节点一样传播新梯度。这样，梯度信息（实际上就是计算任务完成的情况）就会被传播开来，重负载节点就可以把它多余的负载发送给向临界点中梯度最小的节点。于是，计算任务就在梯度的引导之下从重负载节点流向轻负载节点。
可是，按照这种方式，有可能导致过多的计算任务涌向一个轻负载节点。如果轻负载节点接收了过多的新任务，就有可能重新变成中负载甚至重负载节点。一旦出现这种情况，梯度信息就不再能够正确地引导计算任务了。为此，必须使轻负载节点察看要接受的计算任务，如果接收计算任务使本节点脱离轻节点状态，就拒绝接受它。这虽然延迟了任务的接收，但随着时间的推移，轻负
