A Generalized Parallel Task Model for Recurrent Real-time Processes
A Generalized Parallel Task Model for Recurrent Real-time Processes
复制标题
DOI：
10.1145/3322809
复制
发表时间：
2012-12
期刊：
影响因子：
--
通讯作者：
Sanjoy Baruah;V. Bonifaci;A. Marchetti-Spaccamela;L. Stougie;Andreas Wiese
中科院分区：
文献类型：
--
作者：
Sanjoy Baruah;V. Bonifaci;A. Marchetti-Spaccamela;L. Stougie;Andreas Wiese
一个模型被认为是代表经常性的优先约束的任务，在多处理器平台上执行。周期性任务被指定为有向循环图（DAG）、周期和相对截止日期。DAG的每个顶点表示一个顺序作业，而DAG的边表示这些作业之间的优先约束。DAG的所有作业同时发布，并且需要在其发布的指定相对截止日期内完成执行。任务可以以这种方式释放作业无限次，连续的释放至少间隔指定的时间段。调度问题是确定这样一个经常性的任务是否可以被调度，总是满足所有的最后期限上指定数量的处理器，专用于此任务。这个问题被证明是计算上棘手的，但服从有效的近似解。EDF是一种很好的近似调度算法。多项式和伪多项式的可扩展性测试，不同的有效性，提出了用于确定是否一个给定的任务可以调度EDF总是满足指定数量的处理器上的所有截止日期。
A model is considered for representing recurrent precedence-constrained tasks that are to execute on multiprocessor platforms. A recurrent task is specified as a directed a cyclic 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 need to complete execution within the specified relative deadline of their release. The task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. The scheduling problem is to determine whether such a recurrent task can be scheduled to always meet all deadlines upon a specified number of processors that are dedicated for the use of this task. This problem is shown to be computationally intractable, but amenable to efficient approximate solutions. EDF is shown to be a good approximate scheduling algorithm. Polynomial and pseudo-polynomial schedulability tests, of differing effectiveness, are presented for determining whether a given task can be scheduled by EDF to always meet all deadlines on a specified number of processors.