Multiprocessor real-time scheduling with arbitrary processor affinities: from practice to theory
Multiprocessor real-time scheduling with arbitrary processor affinities: from practice to theory
复制标题
具有任意处理器亲和力的多处理器实时调度：从实践到理论
DOI：
--
复制
发表时间：
2014
影响因子：
1.3
通讯作者：
Björn B. Brandenburg
中科院分区：
文献类型：
--
作者：
A. Gujarati;Felipe Cerqueira;Björn B. Brandenburg
当代的多处理器实时操作系统，例如Linux Works、LynxOS、QNX和Linux的实时变体，允许进程具有任意的处理器亲和性，即，进程可以被固定到系统中的处理器的任意子集。对进程迁移设置这样的硬约束有助于提高特定多线程应用程序的缓存性能，实现应用程序之间的隔离，并有助于负载平衡。然而，到目前为止，缺乏可预测性分析，这样的系统，防止使用任意处理器的亲和力在可预测的硬实时系统。本文首先从实时系统的角度分析了具有任意处理器亲和力的多处理器调度问题。结果表明，作业级固定优先级调度与任意处理器的亲和力是严格更一般的全局，集群，分区作业级固定优先级调度相结合。关于更一般的情况下，作业级的动态优先级，它表明，全球和集群调度是等价的多处理器实时调度与任意处理器的亲和力。Linux的推拉调度器作为一个参考实现进行了研究，并提出了两种方法的可并行性分析的硬实时任务与任意处理器的亲和力。在第一种方法中，调度问题被减少到“全球性”的子问题，现有的全球可扩展性测试可以应用。第二种方法专门基于响应时间分析，并将响应时间计算建模为线性优化问题。后一种基于线性规划的方法比前一种基于约简的方法具有更好的运行时复杂度。可扩展性实验表明，所提出的技术是有效的。
Contemporary multiprocessor real-time operating systems, such as VxWorks, LynxOS, QNX, and real-time variants of Linux, allow a process to have an arbitrary processor affinity, that is, a process may be pinned to an arbitrary subset of the processors in the system. Placing such a hard constraint on process migrations can help to improve cache performance of specific multi-threaded applications, achieve isolation among applications, and aid in load-balancing. However, to date, the lack of schedulability analysis for such systems prevents the use of arbitrary processor affinities in predictable hard real-time systems. This paper presents the first analysis of multiprocessor scheduling with arbitrary processor affinities from a real-time systems perspective. It is shown that job-level fixed-priority scheduling with arbitrary processor affinities is strictly more general than global, clustered, and partitioned job-level fixed-priority scheduling combined. Concerning the more general case of job-level dynamic priorities, it is shown that global and clustered scheduling are equivalent to multiprocessor real-time scheduling with arbitrary processor affinities. The Linux push and pull scheduler is studied as a reference implementation and two approaches for the schedulability analysis of hard real-time tasks with arbitrary processor affinities are presented. In the first approach, the scheduling problem is reduced to “global-like” sub-problems to which existing global schedulability tests can be applied. The second approach is specifically based on response-time analysis and models the response-time computation as a linear optimization problem. The latter linear-programming-based approach has better runtime complexity than the former reduction-based approach. Schedulability experiments show the proposed techniques to be effective.
影响因子：
1.3
作者：
Davis, Robert I.;Burns, Alan
通讯作者：
Burns, Alan
优秀论文奖：具有任意处理器亲和力的 Linux 推拉调度器的可调度性分析
DOI：
10.1109/ecrts.2013.18
发表时间：
2013
期刊：
2013 25th Euromicro Conference on Real-Time Systems
影响因子：
--
作者：
Arpan Gujarati;Felipe Cerqueira;Björn B. Brandenburg
通讯作者：
Björn B. Brandenburg
影响因子：
16.6
作者：
Davis, Robert I.;Burns, Alan
通讯作者：
Burns, Alan