论文部分内容阅读
目前,越来越多的实时应用需求推动着实时系统的发展。同时计算机的迅猛发展和硬件价格的降低使得多处理器实时系统得到广泛的应用。多处理器系统的调度问题也受到更多的关注。
对多处理器实时调度问题的研究大多集中在强实时任务系统。在满足强定时约束的条件下,一般认为按比例公平使用资源(Proportionate Fair,简称Pfair)调度模型是最优的。Pfair调度模型有多种算法,其中的最优算法涉及处理器之间频繁的抢占和迁移,因此而带来的开销对于弱实时系统和某些强实时系统是不必要或不允许的。Pfair调度模型中的最早伪时限优先(Earliest Pseudo-Deadlinefirst,简称EPDF)算法在两个以上处理器构成的平台上虽不是Pfair调度模型中最优的算法,但它没有额外的参数和规则限制。针对弱实时系统和任务重组频繁的动态任务系统,EPDF算法与最优的Pfair调度算法相比是较好的选择。
本文从Pfair调度模型出发,分析了Plait调度的最优性和可行性,指出了最优Pfair算法在一些实时系统应用中的不足之处,为此引入了EPDF Pfair调度算法。本文对EPDF调度算法进行了较为深入的研究。针对强实时系统中的EPDF算法,本文分析了可调度利用率约束以及现有的一些判定方法,对已有的可调度利用率判定作了改进,得到了一种基于利用率的可调度性判定方法和可调度性判定的一种组合方案。针对弱实时系统,论文从权值约束角度分析了EPDF算法确保延缓的约束条件,推出了不限制任务权值情况下的充分利用率约束。
在算法测试与验证上,本课题编写了一个测试EPDF调度算法可调度性判定方法和延缓约束条件的程序。这个程序可以对设计的任务集合进行EPDF算法可调度性判定和延缓约束评估,为EPDF调度算法在强实时系统和弱实时系统中的应用提供了一种度量方法。