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

《多处理器固定优先级算法的可调度性分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、多处理器固定优先级算法的可调度性分析摘要:针对多处理器实时调度中的固定优先级(fp)调度算法,提出了一种改进的可调度性判定方法。引入baruah的最早截止期优先(edf)窗口分析框架,将高优先级任务带入作业的最大数量限定为m-1(m为处理器个数),进而对任务的干涉上界进行重新界定,并由此得到一个更加紧密的可调度性判定充分条件。仿真实验结果表明,该方法增加了通过判定任务集的数量,体现出更优的可调度判定性能。关键词:多处理器;实时调度;固定优先级;可调度性判定;干涉analysisonschedulability

2、offixed-prioritymultiprocessorscheduling英文作者名bailu*,yanli英文地址(schoolofcomputerscienceandcommunicationengineering,jiangsuuniversity,zhenjiangjiangsu212013,china)abstract:concerningthefixed-priority(fp)algorithmofmultiprocessorreal-timescheduling,animprovedsc

3、hedulabilitytestwasproposed.thispaperappliedbaruahswindowanalyticalframeworkofearliestdeadlinefirst(edf)tofp,boundedthemaxnumberofhigherprioritytasksdoingcarry-inbym-1(withmbeingthenumberofprocessors),andthusgotanewupperboundofinterferenceatasksuffered.the

4、n,atightersufficientconditiontodetermineschedulabilitywasderived.thesimulationresultsshowtheschedulabilitytestismoreefficientbyincreasingthenumberofdetectedschedulabletasksets.keywords:multiprocessor;real-timescheduling;fixed-priority(fp);schedulabilitytest

5、;interference0引言随着多处理器芯片的普及,多处理器平台上的实时应用系统开发也引起越来越广泛的关注。为了保障这些系统的时间约束性和高可靠性,可调度性判定亦成为实时系统调度理论研究的核心问题。自1973年liu和layland[1]对多处理器系统的可调度性判定问题进行研究后,越来越多的人开始研究多处理器平台的可调度性判定技术,近年来提出了一些切实有效的方法[2-10]。baker[2-3]开创性地从任务错过其截止期的角度出发,对全局最早截止期优先（earliestdeadlinefirst,edf）

6、和固定优先级（fixed-priority,fp）算法进行了研究,分别得到了一个可调度性判定的充分条件;bertogna等[4]对实现工作保持的调度算法进行研究,得到任务集满足可调度性判定的充要条件,但由于没有理想复杂度的方法计算任务受到的干涉,使用工作负载作为干涉上界进行替代,得到了一个充分的可调度判定——bcl判定[5]。然而,得到的工作负载取值过于悲观,导致了大量的可调度任务集不能通过判定。本文针对全局fp调度算法的可调度性判定问题,引入文献[6]中的窗口分析框架,分析限定高优先级任务带入作业的最大数量

7、,求得一个更加逼近真实的任务干涉上界,改进了bcl判定方法,由此得到一个更加紧密的可调度性判定充分条件。通过实验将改进后的判定方法和bcl判定方法进行了比较,验证了改进后的方法可以检测到更多的可调度任务集,具有更高的可调度判定性能。1系统模型及相关定义讨论的内容基于以下系统模型:1)实时多处理器系统由m个具有相同处理能力的处理器组成,且任务在它们间可以互相迁移。2)每个任务的不同作业可以在不同的处理器上执行,但单个作业只能在同一个处理器上执行。3)任务之间是相互独立的,不存在先后次序约束,不存在除处理器外的资

8、源访问冲突;任务之间可抢占,任务上下文切换、迁移和调度的开销忽略不计。4)任务集中任务按照优先级由高到低的顺序排列,若任务τi的优先级高于τj,则有1≤i1的情形;周期tk服从[1,1000]内的均匀分布;相对截止期dk服从[ck,tk]内的均匀分布。实验流程如下:1)生成一个具有m+1个任务的任务集,任务集计数加1。2)对该任务集使用文献[7]提出的任务集可行性必要条件进行检验。若任务集具有可行性