Schedulability Analysis for Real-Time Systems with EDF Scheduling
Fengxiang Zhang and Alan Burns
Real-time scheduling is the theoretical basis of real-time systems engineering. Earliest Deadline First (EDF) is an optimal scheduling algorithm for uniprocessor real-time systems. The existing results on an exact schedulability test for EDF scheduling with arbitrary relative deadlines need to calculate the processor demand of the task set at every absolute deadline to check if there is an overflow in a specified time interval. The large amount of calculations restricts the use of EDF in practice. In this paper, we proposes new results on necessary and sufficient schedulability analysis for EDF scheduling; the new results reduce the calculation times in logarithm scales in all situations. For example a 16 tasks system that in the previous analysis had to check 858,331 points (deadlines) can, with the new analysis, be optimally check at just 12 points. The required calculation by the proposed analysis is stable for all kinds of task sets. There is no restriction on the new results: each task can be periodic or sporadic, with relative deadline which can be less than, equal to or greater than its period; the tasks can have release jitter, and they can share non-preemptable resources in the system.
Download Not Available
BibTex Entry
@techreport{Zhang2008,
author = {Fengxiang Zhang and Alan Burns},
institution = {Real-Time Systems Group, University of York},
month = {February},
number = {YCS-2008-426},
title = {Schedulability Analysis for Real-Time Systems with EDF Scheduling},
year = {2008}
}