基于利用率和负载均衡的多核实时调度算法研究
黄姝娟1，2，朱怡安1，2，李兵哲1，陆 伟2
【摘 要】摘 要:针对分区调度算法在实时多处理器系统中处理器利用率不高的现象，提出一种基于利用率和负载均衡的分区调度算法BUWBPA(Based on Utilization and Workload Balance Partition Algorithm)。该算法在满足任务实时性要求的基础上，以寻求高利用率和负载均衡为目标进行任务分配，将任务分配分成两个阶段:第一个阶段以高利用率为原则，选择任务集内利用率最高的任务先分配;第二个阶段以负载均衡为原则，根据处理器数选择利用率总和等于1或接近于1的任务进行分配，并且在此阶段对于未达到充分利用的处理器，选取可能调度的零星任务，对任务进行再次重新分配，以达到负载均衡和系统最大利用率。实验证明，该算法在实现最大利用率的前提下能很好地达到负载均衡。
【期刊名称】西北工业大学学报 【年(卷),期】2012(030)001 【总页数】7
【关键词】关 键 词:多核，实时系统，负载均衡，启发式算法
复杂实时系统为满足处理时限，要求系统具有足够强大的处理能力。单芯片多处理器(多核)的优势就是要为实时系统提供强有力的处理支持，为实时多任务系统的可调度性提供保障。目前多处理器实时调度方法主要分为两类:全局调度和分区调度算法。全局调度算法的思想是所有任务共享所有处理器，任务允许迁移。这种调度算法虽然处理器利用率高但执行开销较大，典型算法如GEDF(Global Earliest Deadline First)［1］ 和 Pfair(Proportionate fairness)
［2］。分区调度算法则是要求同一个分区的任务只能在同一个处理器上调度，且任务不能迁移。这就使多处理器调度转化为多个单处理器调度从而简化了问题。这种调度方法降低了开销但却使处理器利用率不高，典型算法如PEDF(Partition Earliest Deadline First)［3］。目前有许多文献都在如何提高分区算法利用率方面进行研究。如文献［4］根据对多处理器下的RM(Rate-Monotonic)可调度条件和任务分配算法进行了研究与分析，对基于RM的四种分区算法进行了比较。文献［5］在分区时允许任务抢占和限定性迁移以提高系统利用率。文献［6，7］找出了一种需求界限函数(DBF)，根据该函数的近似值进行分区。文献［8］采用将分区和全局调度相结合的方法，将分区死限单调调度PDMS(Partitioned Deadline-Monotonic Scheduling)方法进行扩展，允许最高优先级任务在处理器核上进行划分，并被迁移到多个核上执行，以提高处理器利用率。文献［9］则采用一种新的基于WFD(Worst Fit Decreasing)的启发式分区方法来提升处理器性能。尽管这些算法已经在系统利用率方面有所提高，但分区的复杂性也随之加大了。因此，研究高效的启发式算法，利用多处理器下任务集的可调度条件，开发新型实时任务分区调度算法仍是此领域研究的一个热点问题。
本文在对多处理器实时任务特征进行分析的基础上，提出了一个基于利用率和负载均衡的实时多处理器系统静态和动态调度相结合的调度分配算法。和传统的分区调度算法不同的是，将任务划分为周期任务和非周期任务。对于周期任务，在进行分区时根据其利用率因子的大小进行总体规划，以满足负载均衡和最大利用率为目的;对于非周期任务则根据其到达时间、执行时间以及死限要求进行计算，在保证系统可调度的条件下能够有效地根据多处理机上已经分配的
周期性的实时任务剩余空间选择最佳的调度方案。
1 任务调度模型设计
1.1 调度任务模型特性
假设一个实时多处理器系统有m个处理器(m＞1)，且这些处理器是同构的。考虑n个周期任务τ={τ1，τ2…，τn}和l个非周期任务τ'={τ'1，τ'2…，τ'l}在同构多处理器上的可抢占调度问题。本文的周期任务具有以下特性:
1)每个任务都是一个四元组 τi=(Φi，Ci，Di，Ti)其中，Φi是到达的时间，Ci表示最坏的计算时间，Di表示相应的死限，Ti表示周期，Ci≤ Ti，且 Di≤Ti。本文仅考虑周期任务同时到达并且任务周期和死限都为正整数且相等的情况，即Di=Ti。
2)任务之间是可抢占的且相互独立，不考虑同一个处理器上任务切换带来的开销以及其它一些资源(如变量及缓冲区等)访问开销。
3)每个任务τi都包含一个无限的工作job，而用τik指示τi的第k次工作。rik和dik指示τik的释放时间和第k次工作的死限时间，则有rik=Φi+(k-1)Ti，dik=rik+Di。
4)U(τi)=Ci/Ti表示τi任务的利用率因子Ui，一个周期任务系统的总利用率。设 σ为任务最大可达利用率，σ =max{Ui}，(i=1，…，n)显然σ∈(0，1］。仿真实验中，将根据不同σ的取值比较算法的性能。
本文假定任何一个非周期任务的优先级都低于周期任务，非周期任务都是一个三元组τ'i=(Φ'i，E'i，D'i)其中，Φ'i是到达的时间，E'i表示最坏的计算时间，D'i表示相应的死限。定义非周期任务瞬时利用率为 U(τ'i)=E'i/D'i，U'i∈ (0，1］。
基于利用率和负载均衡的多核实时调度算法研究
