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

，而轻载集较大，那么就采用重载结点请求算法，在重载集中找到发送者，由发送者主动迁移任务给结点。

各结点的状态分为R(轻载，即任务接收者)和S(重载，即任务发送者)，阈值记为Mk。系统刚启动时，各结点负载都比较轻(即均为R)，因此，重载集合为空，轻载集合则等于结点全集。当产生新任务时，只要结点负载不超过阈值Mk，这个新任务就在本地运行，结点状态仍旧是R。此时的系统处于低负载，使用重载结点请求算法。随着一个个新任务的到来，结点负载增大，当超过阈值Mk时，结点状态变为S，并通知其他结点改变它们所维护的重载集与轻载集。

然后，比较结点轻载集和重载集的大小：若重载集小于轻载集，则继续采用重载结点请求算法，按重载结点请求算法遍历其轻载集中的结点，找出最合适执行新产生任务的结点，并发送任务；若重载集大于轻载集，则改用轻载结点请求算法，按轻载结点请求算法遍历重载集中的结点，并发送请求任务的信号。

图2为改进的双向请求算法流程。

在嵌入式多处理机系统中，要实现任务的再次分配，一般是采取进程迁移的方式。但是进程迁移开销较大，而且选择可迁移进程的标准和策略是实现动态抢先式负载平衡的关键问题，若选择了不该迁移的进程进行迁移，则可能会抵消负载平衡所带来的性能的改善。

定义2 进程从开始执行到最终结束所花费的CPU周期数称为"进程生存周期数"，进程当前已经耗费掉的CPU周期数称为"进程已生存周期数"。

最简单的方法是选择最新生成的任务，导致处理器工作负载超出门限值，这些任务相对来说迁移的代价不大。也可以选择已运行的任务，然而，可能的结果是迁移运行任务的代价抵消了作业运行时间的减少。因此，选择生存期长、已生存周期数较少的进程更有利，可以使迁移开销有时间得以补偿。在本模型中，选择前一种迁移策略。

仿真测试基于卡内基·梅隆大学的负载平衡测试框架，设置了5个结点。输入具有代表性的任务集之后，分别在系统负载较轻、较重和正常的情况下进行仿真测试。每个结点的剩余负载能力不同，分别记为：20，90，30，20，40。不妨假设，在负载平衡前，负载是平均分配到5个结点上的，使用本文中的策略进行负载平衡后，剩余负载能力较强的结点将负担更多的负载。由于篇幅所限，这里只能列出部分测试结果，分别如图3～图5所示。

结 语

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