多核系统负载平衡模型设计

为达到任务的均匀分布，应求得相关域中重载结点应该传递给该结点的负载量(设为Mk)，但是必须对每个结点引入阈值H(j)，以避免任务从负载更轻的轻载结点迁移过来。若WORK(j)>点引入阈值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值向各个相关结点发送任务。

重载结点请求算法流程如下：
①判断自己是否为重载结点；
②如果是，则找出附近的轻载结点，并对它发出任务转移请求；
③得到同意后，重载结点向该轻载结点发送任务。

重载结点请求的优点是：如果没有过重负载的忙结点，就不会被空闲邻接结点所打扰。这在整个系统负载较轻时显得尤为重要。

缺点是：负载过重的重载结点还要额外增加处理负载平衡调度的负担。

系统整体负载较重时，如果使用重载结点请求算法，那么重载结点在自身已经高负荷的情况下，还要负担额外的处理负载平衡调度的负担，发出任务转移请求。由于重载结点数目较多，多数任务转移请求无法得到满足，重负载结点会在将来继续发出请求，这些请求反而会造成较大的额外开销。因此，重载结点请求算法适合在整个系统负载较轻时采用。

2．3 双向请求算法

综合上面两种算法的优缺点，就有了双向请求算法。发送者和接收者都能转移任务，因此该算法兼有重载结点请求算法和轻载结点请求算法的优点。在系统负载较轻时，使用重载结点请求算法；在系统负载较重时，使用轻载结点请求算法。

一个需要解决的问题是：怎么样判断系统负载的轻与重，即怎样决定何时使用重载结点请求算法，何时使用轻载结点请求算法。这是非常关键的，如果解决得不恰当，那么双向请求算法就不是结合重载结点请求算法与轻载结点请求算法的优点，而是结合了二者的缺点。

2．4 双向请求算法的改进

改进算法采用自适应算法，合理地设置判断负载的阈值，并随着每个结点的任务负荷变化，动态地改变这个评判标准，在系统负载重时采用轻载结点请求算法，在系统负载轻时采用重载结点请求算法。

改进算法中，每个结点记录其相关域中其他结点的状态信息，它维护2个集合，分别是轻载集θ和重载集φ。轻载集中保存的是其相关域中轻载结点的信息，而重载集中保存的是其相关域中重载结点的信息。每当结点状态发生变化时，发消息给相关域中的各结点，各结点相应地改变其轻载集和重载集。

比较两个集合的大小来决定采用重载结点请求算法还是轻载结点请求算法。当系统处于重负载时，会有大量的重负载结点，因而轻载集较小，而重载集较大，那么就采用轻载结点请求算法，在轻载集中找到接收者，由接收者主动申请结点的任务；当系统处于轻负载时，会有大量的轻负载结点，因而重载集较小