Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks
Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks
复制标题
DOI：
10.1109/rtss.2013.31
复制
发表时间：
2013-12
期刊：
影响因子：
--
通讯作者：
V. Bonifaci;A. Marchetti-Spaccamela;Nicole Megow;Andreas Wiese
中科院分区：
文献类型：
--
作者：
V. Bonifaci;A. Marchetti-Spaccamela;Nicole Megow;Andreas Wiese
我们研究单层处理器实时零星任务的先发制度安排。我们将最早的截止日期（EDF）算法考虑固定优先级（FP）调度以及动态优先级调度。我们研究了测试计划性和计算任务响应时间的问题。通常，这些问题在计算上对于截止日期有限的任务系统是可棘手的。在本文中，我们专注于具有谐波周期长度的任务系统的特定情况，这意味着任务的周期对彼此之间的分配。这是实际相关性的特殊情况。我们提供了具有谐波周期的受约束deadline任务系统的有效效率的精确算法。特别是，我们提供了一种确切的多项式时间算法，用于计算具有任意固定优先顺序的系统中任务的响应时间。这也意味着精确的fp-swedulability测试。对于动态优先级调度，我们展示了如何在多项式时间内测试EDF-划安排性。此外，我们为相对截止日期和期间共同谐波的更简单情况提供了非常简单的EDF-避难性测试。
We study the preemptive scheduling of real-time sporadic tasks on a uniprocessor. We consider both fixed priority (FP) scheduling as well as dynamic priority scheduling by the Earliest Deadline First (EDF) algorithm. We investigate the problems of testing schedulability and computing the response time of tasks. Generally these problems are known to be computationally intractable for task systems with constrained deadlines. In this paper, we focus on the particular case of task systems with harmonic period lengths, meaning that the periods of the tasks pair wise divide each other. This is a special case of practical relevance. We present provably efficient exact algorithms for constrained-deadline task systems with harmonic periods. In particular, we provide an exact polynomial-time algorithm for computing the response time of a task in a system with an arbitrary fixed priority order. This also implies an exact FP-schedulability test. For dynamic priority scheduling, we show how to test EDF-schedulability in polynomial time. Additionally, we give a very simple EDF-schedulability test for the simpler case where relative deadlines and periods are jointly harmonic.