多处理器固定优先级算法的可调度性分析.doc

多处理器固定优先级算法的可调度性分析摘要:针对多处理器实时调度中的固定优先级(fp)调度算法,提出了一种改进的可调度性判定方法。引入baruah的最早截止期优先(edf)窗口分析框架,将高优先级任务带入作业的最大数量限定为m-1(m为处理器个数),进而对任务的干涉上界进行重新界定,并由此得到一个更加紧密的可调度性判定充分条件。仿真实验结果表明,该方法增加了通过判定任务集的数量,体现出更优的可调度判定性能。关键词:多处理器;实时调度;固定优先级;可调度性判定;干涉analysis on schedulability of fixed-priority multiprocessor scheduling英文作者名bai lu*,yan li英文地址(school of computer science and communication engineering, jiangsu university, zhenjiang jiangsu 212013, china)abstract: concerning the fixed-priority (fp) algorithm of multiprocessor real-time scheduling, an improved schedulability test was proposed. this paper applied baruahs window analytical framework of earliest deadline first (edf) to fp, bounded the max number of higher priority tasks doing carry-in by m-1 (with m being the number of processors), and thus got a new upper bound of interference a task suffered. then, a tighter sufficient condition to determine schedulability was derived. the simulation results show the schedulability test is more efficient by increasing the number of detected schedulable task sets.key words: multiprocessor; real-time scheduling; fixed-priority (fp); schedulability test; interference0引言随着多处理器芯片的普及,多处理器平台上的实时应用系统开发也引起越来越广泛的关注。为了保障这些系统的时间约束性和高可靠性,可调度性判定亦成为实时系统调度理论研究的核心问题。自1973年liu和 layland1对多处理器系统的可调度性判定问题进行研究后,越来越多的人开始研究多处理器平台的可调度性判定技术,近年来提出了一些切实有效的方法2-10。baker2-3开创性地从任务错过其截止期的角度出发,对全局最早截止期优先（earliest deadline first, edf）和固定优先级（ fixed-priority, fp）算法进行了研究,分别得到了一个可调度性判定的充分条件;bertogna等4对实现工作保持的调度算法进行研究,得到任务集满足可调度性判定的充要条件,但由于没有理想复杂度的方法计算任务受到的干涉,使用工作负载作为干涉上界进行替代,得到了一个充分的可调度判定bcl判定5。然而,得到的工作负载取值过于悲观,导致了大量的可调度任务集不能通过判定。本文针对全局fp调度算法的可调度性判定问题,引入文献6中的窗口分析框架,分析限定高优先级任务带入作业的最大数量,求得一个更加逼近真实的任务干涉上界,改进了bcl判定方法,由此得到一个更加紧密的可调度性判定充分条件。通过实验将改进后的判定方法和bcl判定方法进行了比较,验证了改进后的方法可以检测到更多的可调度任务集,具有更高的可调度判定性能。1系统模型及相关定义讨论的内容基于以下系统模型:1)实时多处理器系统由m个具有相同处理能力的处理器组成,且任务在它们间可以互相迁移。2)每个任务的不同作业可以在不同的处理器上执行,但单个作业只能在同一个处理器上执行。3)任务之间是相互独立的,不存在先后次序约束,不存在除处理器外的资源访问冲突;任务之间可抢占,任务上下文切换、迁移和调度的开销忽略不计。4)任务集中任务按照优先级由高到低的顺序排列,若任务i的优先级高于j,则有1i1的情形;周期tk服从1,1000内的均匀分布;相对截止期dk服从ck,tk内的均匀分布。实验流程如下:1)生成一个具有m+1个任务的任务集,任务集计数加1。2)对该任务集使用文献7提出的任务集可行性必要条件进行检验。若任务集具有可行性,则使用给定的方法对该任务集进行可调度性判定；否则重复上一步重新生成任务集。3)若该任务集被判定为可调度任务集,则向该任务集中增加一个新任务以增大其总利用率,得到一个新的任务集,重复上一步的检验。根据上述流程当任务集数量达到105时停止。可以得到判定方法的利用率/可调度任务集数量的数据。我们改进的判定方法与bcl判定方法进行了比较。如图3显示了处理器数量m=2,任务集的平均利用率u=0.2,运用dm算法进行调度的仿真结果。另外,还使用m=4,8,16和u=0.25,0.3,0.5以及rm算法等条件重做了实验,得到的结果与图3类似,不再一一给出。图片图3u=0.2和m =2的实验数据由图3可看出:改进后的判定方法比bcl判定方法检测到更多的可调度任务集,体现出更高的可调度判定性能。根据文中的分析可以预见,当每个任务集中任务的数量远远大于处理器的个数(nm)时,把高优先级任务带入作业的总数量限定在m-1,对比bcl判定方法的所有高优先级任务都存在带入作业情况,可调度性能的提高将更加显著。4结语本文对多处理器fp调度算法的可调度性进行研究,将文献6中针对edf算法的窗口分析框架应用到fp算法上,对高优先级任务带入作业的数量进行限定,得到更为精确的干涉上界,进而提出一个更为紧密的充分判定条件。实验结果显示本文的改进方法是行之有效的,在可调度性判定上表现出更优的性能。参考文献:1liu c, layland j w. scheduling algorithms for multiprogramming in a hard-real-time environment j. journal of the acm, 1973,20(1): 46-61.2baker t p. multiprocessor edf