带约束释放抖动谐波任务响应时间分析的精确多项式时间算法

• 2019 年 12 月 29 日
• 筆記

原文题目: Exact Polynomial Time Algorithm for the Response Time Analysis of Harmonic Tasks with Constrained Release Jitter

摘要： 在硬实时系统的一些重要应用领域中，在单处理器平台上运行的具有谐波周期和约束时限的抢占性零星任务扮演着重要的角色。我们提出了一种新的算法来确定精确的最坏情况下的响应时间的任务，具有较低的计算复杂度（在任务的数量线性）比已知的算法开发的相同的系统类。如果任务执行在一定的值范围内，我们还允许任务执行由于释放抖动而延迟启动。为了检验这些约束是否满足，我们定义了一个约束规划问题，该问题具有特殊的结构，并且可以在任务数为线性的时间内用启发式组件求解。如果检查确定了抖动值的可容许性，则线性时间算法也可用于确定抖动感知系统的最坏响应时间。

原文作者：Thi Huyen Chau Nguyen, Werner Grass, Klaus Jansen

原文地址：https://arxiv.org/abs/1912.01161