Worst-Case Response Time Analysis of Earliest Deadline First in an Industrial Case Study
Conference: MBMV 2023 – Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen - 26. Workshop
03/23/2023 - 03/24/2023 at Freiburg
Proceedings: ITG-Fb. 309: MBMV 2023
Pages: 8Language: englishTyp: PDF
Authors:
Fattohi, Iwan Feras; Slomka, Frank (Embedded Real-Time Systems Institute, Ulm University, Germany)
Prehofer, Christian (Corporate R&D, DENSO AUTOMOTIVE, Munich, Germany)
Abstract:
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.