A Norm Approach for the Partitioned EDF Scheduling of Sporadic Task Systems
A Norm Approach for the Partitioned EDF Scheduling of Sporadic Task Systems
复制标题
零星任务系统分区EDF调度的规范方法
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
J. Hermant
中科院分区：
文献类型：
--
作者：
L. George;J. Hermant
在本文中，我们为零星任务系统的最早截止日期（EDF）计划提出了一种新方法。我们考虑任务截止日期限制的情况，即任务的截止日期小于或等于其周期。我们介绍了EDF规范的概念，用于定义在给定固定期间和相对截止日期给定的可计划系统的WCET值的空间。基于此概念，有可能得出必要且充分的可行性条件，以检查EDF计划是否有效对于给定分区有效。 EDF Norm具有有趣的凸性属性，可以使用线性编程方法允许减少需要检查EDF规范的点数。从EDF Norm中，我们得出了一种新的最差拟合降低分区的启发式，并将其性能与基于密度分配和需求绑定函数近似的两个现有分区启发式方法进行了比较。然后，我们根据资源增强范式比较了启发式的性能。
In this paper, we propose a new approach for the partitioned Earliest Deadline First (EDF) scheduling of sporadic task systems. We consider the case of constrained task deadlines where the deadlines of the tasks are less than or equal to their periods. We introduce the concept of the EDF norm, for defining the space of WCET values that result in schedulable systems given fixed periods and relative deadlines. Based on this concept, it is possible to derive a necessary and sufficient feasibility condition to check whether EDF scheduling is valid for a given partitioning. The EDF norm has interesting convexity properties that permit using a Linear Programming approach to reduce the number of points at which the EDF norm needs to be checked. From the EDF norm, we derive a new Worst Fit Decreasing partitioning heuristic and compare its performance with two existing partitioning heuristics based on density partitioning and demand bound function approximation. We then compare the performance of the heuristic in terms of the resource augmentation paradigm.