The concept of Maximal Unschedulable Deadline Assignment for optimization in fixed-priority scheduled real-time systems
The concept of Maximal Unschedulable Deadline Assignment for optimization in fixed-priority scheduled real-time systems
复制标题
DOI：
10.1007/s11241-019-09332-0
复制
发表时间：
2019-02
影响因子：
1.3
通讯作者：
Yecheng Zhao;Haibo Zeng
中科院分区：
文献类型：
--
作者：
Yecheng Zhao;Haibo Zeng
本文考虑了固定优先级调度的实时系统的设计优化问题，其中任务优先级分配是决策变量的一部分，时序约束和/或目标函数线性依赖于任务响应时间的精确值（例如端到端截止时间约束）。响应时间分析技术的复杂性使得利用现有的优化框架和扩展到大型设计变得困难。相反，我们提出了一种高效的优化框架，该框架比整数线性规划（ILP）快三个数量级（1000 倍），同时提供相同质量的解决方案。该框架围绕三个新颖的想法：（1）一种有效的算法，可以找到可调度的任务优先级分配，以最小化平均最坏情况响应时间； （2）最大不可调度截止时间分配（MUDA）的概念，它抽象了可调度性条件，即一组使系统不可调度的最大虚拟截止时间分配； (3) 一种新的优化程序，利用 MUDA 的概念和高效的算法来计算它。
This paper considers the problem of design optimization for real-time systems scheduled with fixed priority, where task priority assignment is part of the decision variables, and the timing constraints and/or objective function linearly depend on the exact value of task response times (such as end-to-end deadline constraints). The complexity of response time analysis techniques makes it difficult to leverage existing optimization frameworks and scale to large designs. Instead, we propose an efficient optimization framework that is three orders of magnitude (1000 times) faster than Integer Linear Programming (ILP) while providing solutions with the same quality. The framework centers around three novel ideas: (1) an efficient algorithm that finds a schedulable task priority assignment for minimizing the average worst-case response time; (2) the concept of Maximal Unschedulable Deadline Assignment (MUDA) that abstracts the schedulability conditions, i.e., a set of maximal virtual deadline assignments such that the system is unschedulable; and (3) a new optimization procedure that leverages the concept of MUDA and the efficient algorithm to compute it.