论文标题
二元性的力量：响应时间分析符合整数编程
The Power of Duality: Response Time Analysis meets Integer Programming
论文作者
论文摘要
我们研究实时系统中响应时间分析与混合集问题之间的相互丰富联系。从而概括了已知结果，我们提出了一种新的方法来计算固定优先级单层实时计划中的响应时间。我们甚至允许任务被某些周期受限的释放抖动延迟。通过将决策问题的双重问题提出作为整数线性程序，我们表明，可以通过算法将条件减少降低到混合集问题的实例来计算最坏情况的响应时间。在谐波周期的重要情况下，我们的新技术承认了对最差案例响应时间的确切计算的近代算法。我们表明，通常，即使在固定优先级调度中，较小的利用率也会导致更有效的算法。最差的响应时间可以理解为至少对非平凡固定点方程的固定点，因此，我们的方法也可以用于解决合适的固定点问题。此外，我们证明我们的技术可以逆转以通过计算最坏情况的响应时间到相关的实时调度任务系统来解决混合集问题。最后，我们还将优化技术应用于使用简单的目标功能求解4块整数程序。
We study a mutually enriching connection between response time analysis in real-time systems and the mixing set problem. Thereby generalizing over known results we present a new approach to the computation of response times in fixed-priority uniprocessor real-time scheduling. We even allow that the tasks are delayed by some period-constrained release jitter. By studying a dual problem formulation of the decision problem as an integer linear program we show that worst-case response times can be computed by algorithmically exploiting a conditional reduction to an instance of the mixing set problem. In the important case of harmonic periods our new technique admits a near-quadratic algorithm to the exact computation of worst-case response times. We show that generally, a smaller utilization leads to more efficient algorithms even in fixed-priority scheduling. Worst-case response times can be understood as least fixed points to non-trivial fixed point equations and as such, our approach may also be used to solve suitable fixed point problems. Furthermore, we show that our technique can be reversed to solve the mixing set problem by computing worst-case response times to associated real-time scheduling task systems. Finally, we also apply our optimization technique to solve 4-block integer programs with simple objective functions.
