论文标题
在全球速率单调调度下的并行实时任务的可计划性范围
Schedulability Bounds for Parallel Real-Time Tasks under Global Rate-Monotonic Scheduling
论文作者
论文摘要
可调度性界限不仅可以作为有效测试来决定实时任务系统的调度性，而且还揭示了有关调度算法最差的案例性能的见解。不同的是，使用的顺序实时任务系统是利用是一个适合开发可调度性界限的度量，并行实时任务的调度性不仅取决于利用率，还取决于任务的工作负载图结构，这可以通过张力指标很好地表示。在本文中，我们在全球速率 - 单调（G-RM）计划下针对并行实时任务系统开发了新的分析技术，并根据这两个指标获得了针对计划界限的新结果：利用率和张力。首先，我们开发了针对G-RM的第一个利用率 - 最高密度。其次，我们将G-RM的容量增强限制从最著名的值3.73提高到3.18。这些可调度性界限不仅提供了有关G-RM实时性能的理论见解，而且还提供了高效的可调度性测试，这些测试特别适合于设计场景，其中详细的任务图结构未知或在运行时可能会发生变化。随机生成的任务集的实验表明，在不同的参数设置下，我们的新结果始终优于最先进的最新结果。
Schedulability bounds not only serve as efficient tests to decide schedulability of real-time task systems but also reveal insights about the worst-case performance of scheduling algorithms. Different from sequential real-time task systems for which utilization is a suitable metric to develop schedulability bounds, schedulability of parallel real-time tasks depends on not only utilization but also the workload graph structure of tasks, which can be well represented by the tensity metric. In this paper, we develop new analysis techniques for parallel real-time task systems under Global Rate-Monotonic (G-RM) scheduling and obtain new results on schedulability bounds based on these two metrics: utilization and tensity. First, we develop the first utilization-tensity bound for G-RM. Second, we improve the capacity augmentation bound of G-RM from the best known value 3.73 to 3.18. These schedulability bounds not only provide theoretical insights about real-time performance of G-RM, but also serve as highly efficient schedulability tests, which are particularly suitable to design scenarios in which detailed task graph structures are unknown or may change at run-time. Experiments with randomly generated task sets show that our new results consistently outperform the state-of-the-art with a significant margin under different parameter settings.
