The Concept of Unschedulability Core for Optimizing Real-Time Systems with Fixed-Priority Scheduling
The Concept of Unschedulability Core for Optimizing Real-Time Systems with Fixed-Priority Scheduling
复制标题
DOI：
10.1109/tc.2018.2878835
复制
发表时间：
2019-06
影响因子：
3.7
通讯作者：
Yecheng Zhao;Haibo Zeng
中科院分区：
文献类型：
--
作者：
Yecheng Zhao;Haibo Zeng
在具有固定优先级调度的实时系统的设计优化中，可调度性分析被用来定义任务在其截止期内满足的可行域，从而优化算法可以在该可行域内找到最优解。然而，可扩展性分析技术的复杂性通常使得难以利用现有的优化框架并扩展到大型设计。在本文中，我们提出的概念，不可扩展性的核心，一个紧凑的表示的可扩展性条件，并制定有效的算法计算。我们提出了一个新的优化框架，利用这样的概念。我们表明，这个概念是适用于一系列的优化问题，例如，当决策变量包括任务优先级分配和选择的机制保护共享缓冲区。两个案例研究的实验结果表明，新的优化过程保持了最优的解决方案，但比其他精确算法（分支定界，整数线性规划）快几个数量级。
In the design optimization of real-time systems scheduled with fixed priority, schedulability analysis is used to define the feasibility region within which tasks meet their deadlines, so that optimization algorithms can find the best solution within the region. However, the complexity of schedulability analysis techniques often makes it difficult to leverage existing optimization frameworks and scale to large designs. In this paper, we propose the concept of unschedulability core, a compact representation of the schedulability conditions, and develop efficient algorithms for its calculation. We present a new optimization framework that leverages such a concept. We show that this concept is applicable to a range of optimization problems, for example, when the decision variables include the task priority assignment and the selection of mechanisms protecting shared buffers. Experimental results on two case studies demonstrate that the new optimization procedure maintains the optimality of the solutions, but is a few orders of magnitude faster than other exact algorithms (branch-and-bound, integer linear programming).