Paper Info
Title
A Norm Approach for the Partitioned EDF Scheduling of Sporadic Task Systems
Abstract
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.
Year
DOI
Venue
2009
10.1109/ECRTS.2009.29
Dublin
Keywords
Field
DocType
linear programming,processor scheduling,constrained task deadline,linear programming approach,multiprocessor scheduling algorithm,partitioned earliest deadline first scheduling,sporadic task system,worst fit decreasing partitioning heuristic,EDF,Linear Programming approach,Partitioned scheduling,Worst Fit Decreasing,real-time
Metrical task system,Heuristic,Function approximation,Scheduling (computing),Computer science,Real-time computing,Feasibility condition,Heuristics,Linear programming,Earliest deadline first scheduling,Distributed computing
Conference
ISSN
ISBN
Citations 
1068-3070
978-0-7695-3724-5
7
PageRank 
References 
Authors
0.54
12
2
Name
Order
Citations
PageRank
Laurent George121429.39
Jean-François Hermant2482.33