Feasibility Tests for Recurrent Real-Time Tasks in the Sporadic DAG Model
Feasibility Tests for Recurrent Real-Time Tasks in the Sporadic DAG Model
复制标题
零星 DAG 模型中循环实时任务的可行性测试
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Andreas Wiese
中科院分区：
文献类型：
--
作者：
V. Bonifaci;A. Marchetti;S. Stiller;Andreas Wiese
在文献[1]中提出了一种模型，用于表示在多处理器平台上执行的周期性优先约束任务，其中每个周期性任务由有向无环图（DAG）、周期和相对截止日期来建模。DAG的每个顶点表示一个顺序作业，而DAG的边表示这些作业之间的优先约束。DAG的所有作业都是同时发布的，并且必须在某个指定的相对截止日期内完成。任务可以以这种方式释放作业无限次，连续的释放至少间隔指定的时间段。可行性问题是确定这样的经常性任务是否可以被调度为总是满足指定数量的专用处理器上的所有截止日期。在[1]中已经考虑了单个任务的情况。本文的主要贡献是考虑多任务的情况下。我们证明了EDF的加速比界为2 − 1/m，其中m是处理器的数量。此外，我们提出了多项式和伪多项式的可扩展性测试，不同的有效性，以确定是否可以由EDF调度一组零星的DAG任务，以满足指定数量的处理器上的所有最后期限。
A model has been proposed in [1] for representing recurrent precedence-constrained tasks to be executed on multiprocessor platforms, where each recurrent task is modeled by a directed acyclic graph (DAG), a period, and a relative deadline. Each vertex of the DAG represents a sequential job, while the edges of the DAG represent precedence constraints between these jobs. All the jobs of the DAG are released simultaneously and have to be completed within some specified relative deadline. The task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. The feasibility problem is to determine whether such a recurrent task can be scheduled to always meet all deadlines on a specified number of dedicated processors. The case of a single task has been considered in [1]. The main contribution of this paper is to consider the case of multiple tasks. We show that EDF has a speedup bound of 2 − 1/m, where m is the number of processors. Moreover, we present polynomial and pseudopolynomial schedulability tests, of differing effectiveness, for determining whether a set of sporadic DAG tasks can be scheduled by EDF to meet all deadlines on a specified number of processors.