Worst-Case Response Time Analysis of Earliest Deadline First in an Industrial Case Study

Inhalt:
Earliest deadline first (EDF) is a well-studied scheduling policy in real-time theory and is known to be optimal for certain task models. Nevertheless EDF is hardly used in practice. A possible reason is that EDF is not decisive for multiple, equal deadlines which can lead to a non-deterministic real-time scheduler. This means EDF has to be extended by a tie-breaking rule. However, the literature on response time analysis of EDF, such as Spuri and Palencia and Harbour, does not formalize such a tie-breaking rule. This can cause an overestimation of the worst-case response time. To address this, we present a new worst-case response time analysis for EDF with tie-breaking. The analysis is demonstrated on a real industrial case study. The results of the experiment show that the inclusion of a tie-breaking rule improves the estimation of worst-case response times for this case study by a factor of 12 on average in comparison to the method by Palencia and Harbour.