Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems
Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems
复制标题
DOI：
10.1007/s11241-010-9106-5
复制
发表时间：
2011-01-01
影响因子：
1.3
通讯作者：
Burns, Alan
中科院分区：
文献类型：
--
作者：
Davis, Robert I.;Burns, Alan
本文是 2009 年 IEEE 实时系统研讨会论文集的扩展版本。本文针对可调度性分析方面的进展进行了更新，并包含许多重要的附加结果。本文使用全局固定任务优先级抢占式调度解决了多处理器实时系统中的优先级分配问题。我们证明了 Audsley 的最优优先级分配 (OPA) 该算法最初是为单处理器调度而设计的，如果所使用的可调度性测试满足三个条件，则适用于多处理器情况。我们的实证研究表明，最优优先级分配策略和简单的兼容可调度性测试的组合在可调度的任务集数量方面非常有效。我们还检查了启发式优先级分配策略（例如 Deadline Monotonic）的性能，以及称为 DkC 的 TkC 优先级分配策略的扩展，可以与任何可调度性测试一起使用。这里我们发现Deadline Monotonic优先级分配在多处理器情况下性能相对较差，而DkC优先级分配非常有效。
This paper is an extended version of a paper that appeared in the proceedings of the IEEE Real-Time Systems Symposium 2009. This paper has been updated with respect to advances made in schedulability analysis, and contains a number of significant additional results.The paper addresses the problem of priority assignment in multiprocessor real-time systems using global fixed task-priority pre-emptive scheduling.We prove that Audsley's Optimal Priority Assignment (OPA) algorithm, originally devised for uniprocessor scheduling, is applicable to the multiprocessor case, provided that three conditions hold with respect to the schedulability tests used. Our empirical investigations show that the combination of optimal priority assignment policy and a simple compatible schedulability test is highly effective in terms of the number of tasksets deemed to be schedulable.We also examine the performance of heuristic priority assignment policies such as Deadline Monotonic, and an extension of the TkC priority assignment policy called DkC that can be used with any schedulability test. Here we find that Deadline Monotonic priority assignment has relatively poor performance in the multiprocessor case, while DkC priority assignment is highly effective.