EDF-schedulability of synchronous periodic task systems is coNP-hard
EDF-schedulability of synchronous periodic task systems is coNP-hard
复制标题
同步周期性任务系统的 EDF 可调度性是共难点
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
T. Rothvoss
中科院分区：
文献类型：
--
作者：
F. Eisenbrand;T. Rothvoss
在<i>同步周期任务模型</i>中，集合τ<sub>1</sub>，.，给定在周期<sub><i>pi</i></sub>的每一整数倍上，每个任务释放运行时间为<i>ci</i><sub><i>的工件</i></sub>，其相对截止期<i>为</i><sub><i>di</i></sub>。<i></i><sub><i></i></sub><i>最早期限优先（EDF）</i>是一种最优的抢占式单处理器调度策略，这是一个经典的结果。对于有约束的最后期限，即<sub><i>di</i></sub>≤<sub><i>pi</i></sub>，EDF调度是可行的当且仅当<i></i><i></i>
[方程式]
虽然大量的文献涉及这个话题，这个测试的复杂性状态仍然未知。我们证明了这样的任务系统的EDF可扩展性测试是（弱）<b>coNP</b>-困难的。这解决了Baruah & Pruhs的调查“实时调度中的开放问题”中的问题2。硬度的结果是通过应用最近的结果丢番图近似的不可逼近性。
In the <i>synchronous periodic task model</i>, a set τ<sub>1</sub>, ..., τ<sub><i>n</i></sub> of tasks is given, each releasing jobs of running time <i>c</i><sub><i>i</i></sub> with relative deadline <i>d</i><sub><i>i</i></sub>, at each integer multiple of the period <i>p</i><sub><i>i</i></sub>. It is a classical result that <i>Earliest Deadline First (EDF)</i> is an optimal preemptive uniprocessor scheduling policy. For constrained deadlines, i.e. <i>d</i><sub><i>i</i></sub> ≤ <i>p</i><sub><i>i</i></sub>, the EDF-schedule is feasible if and only if
[EQUATION]
Though an enormous amount of literature deals with this topic, the complexity status of this test has remained unknown. We prove that testing EDF-schedulability of such a task system is (weakly) <b>coNP</b>-hard. This solves Problem 2 from the survey "Open Problems in Real-time Scheduling" by Baruah & Pruhs. The hardness result is achieved by applying recent results on inapproximability of Diophantine approximation.