多处理机系统的负载平衡模型设计

引言
    在嵌入式多处理机系统中，经常出现这种情况：某些处理机负载过重而另外一些负载很轻，甚至空闲。这种情况无疑降低了整体系统的工作效率。为了提高处理机的利用率和系统并行计算的效率，应该把负载过重的处理机上的一部分负载转移到空闲或轻负载处理机上，这就出现了负载分配问题的研究。
    简单的说，负载平衡就是要尽量均匀地分配任务，并尽量减少结点之间的通信。解决负载平衡问题，通常有静态和动态两种调度策略：
    ①静态负载平衡是根据系统的先验知识做出决策，运行时负载不能重新分配。
    ②动态负载平衡是根据计算机过程中数据项的变化情况，交换系统的状态信息来决定系统负载的分配。它具有超过静态算法的执行潜力，能够适应系统负载变化情况，比静态算法更灵活、有效。但是由于必须收集、存储并分析状态信息，因此动态算法会产生比静态算法更多的系统开销，不过这种开销和付出常是有所回报的。
    本文描述了一种有效的嵌入式多处理机系统的负载平衡模型，通过动态判断当前系统的负载情况，自动选择负载平衡算法，从而使整个系统以尽可能小的附加代价来达到全局的负载平衡。最后，在卡内基·梅隆大学的负载平衡测试框架上，搭建仿真环境进行模拟测试。结果显示，该模型能较好地平衡各结点的负载。

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)<W1，则为轻载结点；W1<WORK(i)<W2的为适载结点；WORK(i)>W2的为重载结点；WORK(i)=0的是空载结点，如图1所示。

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值向各个相关结点发送任务。
    重载结点请求算法流程如下：
    ①判断自己是否为重载结点；
    ②如果是，则找出附近的轻载结点，并对它发出任务转移请求；
    ③得到同意后，重载结点向该轻载结点发送任务。
    重载结点请求的优点是：如果没有过重负载的忙结点，就不会被空闲邻接结点所打扰。这在整个系统负载较轻时显得尤为重要。
    缺点是：负载过重的重载结点还要额外增加处理负载平衡调度的负担。
    系统整体负载较重时，如果使用重载结点请求算法，那么重载结点在自身已经高负荷的情况下，还要负担额外的处理负载平衡调度的负担，发出任务转移请求。由于重载结点数目较多，多数任务转移请求无法得到满足，重负载结点会在将来继续发出请求，这些请求反而会造成较大的额外开销。因此，重载结点请求算法适合在整个系统负载较轻时采用。
2．3 双向请求算法
    综合上面两种算法的优缺点，就有了双向请求算法。发送者和接收者都能转移任务，因此该算法兼有重载结点请求算法和轻载结点请求算法的优点。在系统负载较轻时，使用重载结点请求算法；在系统负载较重时，使用轻载结点请求算法。
    一个需要解决的问题是：怎么样判断系统负载的轻与重，即怎样决定何时使用重载结点请求算法，何时使用轻载结点请求算法。这是非常关键的，如果解决得不恰当，那么双向请求算法就不是结合重载结点请求算法与轻载结点请求算法的优点，而是结合了二者的缺点。
2．4 双向请求算法的改进
    改进算法采用自适应算法，合理地设置判断负载的阈值，并随着每个结点的任务负荷变化，动态地改变这个评判标准，在系统负载重时采用轻载结点请求算法，在系统负载轻时采用重载结点请求算法。
    改进算法中，每个结点记录其相关域中其他结点的状态信息，它维护2个集合，分别是轻载集θ和重载集φ。轻载集中保存的是其相关域中轻载结点的信息，而重载集中保存的是其相关域中重载结点的信息。每当结点状态发生变化时，发消息给相关域中的各结点，各结点相应地改变其轻载集和重载集。
    比较两个集合的大小来决定采用重载结点请求算法还是轻载结点请求算法。当系统处于重负载时，会有大量的重负载结点，因而轻载集较小，而重载集较大，那么就采用轻载结点请求算法，在轻载集中找到接收者，由接收者主动申请结点的任务；当系统处于轻负载时，会有大量的轻负载结点，因而重载集较小，而轻载集较大，那么就采用重载结点请求算法，在重载集中找到发送者，由发送者主动迁移任务给结点。
    各结点的状态分为R(轻载，即任务接收者)和S(重载，即任务发送者)，阈值记为Mk。系统刚启动时，各结点负载都比较轻(即均为R)，因此，重载集合为空，轻载集合则等于结点全集。当产生新任务时，只要结点负载不超过阈值Mk，这个新任务就在本地运行，结点状态仍旧是R。此时的系统处于低负载，使用重载结点请求算法。随着一个个新任务的到来，结点负载增大，当超过阈值Mk时，结点状态变为S，并通知其他结点改变它们所维护的重载集与轻载集。
    然后，比较结点轻载集和重载集的大小：若重载集小于轻载集，则继续采用重载结点请求算法，按重载结点请求算法遍历其轻载集中的结点，找出最合适执行新产生任务的结点，并发送任务；若重载集大于轻载集，则改用轻载结点请求算法，按轻载结点请求算法遍历重载集中的结点，并发送请求任务的信号。
    图2为改进的双向请求算法流程。

    在嵌入式多处理机系统中，要实现任务的再次分配，一般是采取进程迁移的方式。但是进程迁移开销较大，而且选择可迁移进程的标准和策略是实现动态抢先式负载平衡的关键问题，若选择了不该迁移的进程进行迁移，则可能会抵消负载平衡所带来的性能的改善。
    定义2 进程从开始执行到最终结束所花费的CPU周期数称为“进程生存周期数”，进程当前已经耗费掉的CPU周期数称为“进程已生存周期数”。
    最简单的方法是选择最新生成的任务，导致处理器工作负载超出门限值，这些任务相对来说迁移的代价不大。也可以选择已运行的任务，然而，可能的结果是迁移运行任务的代价抵消了作业运行时间的减少。因此，选择生存期长、已生存周期数较少的进程更有利，可以使迁移开销有时间得以补偿。在本模型中，选择前一种迁移策略。
    仿真测试基于卡内基·梅隆大学的负载平衡测试框架，设置了5个结点。输入具有代表性的任务集之后，分别在系统负载较轻、较重和正常的情况下进行仿真测试。每个结点的剩余负载能力不同，分别记为：20，90，30，20，40。不妨假设，在负载平衡前，负载是平均分配到5个结点上的，使用本文中的策略进行负载平衡后，剩余负载能力较强的结点将负担更多的负载。由于篇幅所限，这里只能列出部分测试结果，分别如图3～图5所示。

结 语
    负载平衡调度是嵌入式多处理机系统利用处理器资源的一种有效途径，它能让多个处理单元比较平衡地共同承担一系列繁重的任务，从而大大提高了系统的吞吐率与性能。动态负载平衡问题是一个正在蓬勃发展的研究热点，还有许多未知的问题有待进一步地探索和研究。仿真结果表明，本文介绍的改进算法有效地平衡了各结点的负载，提高了整个系统资源的吞吐率与性能。该算法还有待在今后的研究工作中，通过实践的检验，找出该算法所需设置的参数(例如阈值Mk和H(j))的合适值。