General and efficient Response Time Analysis for EDF scheduling

Nan Guan, Wang Yi

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

13 Citations (Scopus)


Response Time Analysis (RTA) is one of the key problems in real-time system design. This paper proposes new RTA methods for EDF scheduling, with general system models where workload and resource availability are represented by request/demand bound functions and supply bound functions. The main idea is to derive response time upper bounds by lower-bounding the slack times. We first present a simple over-approximate RTA method, which lower bounds the slack time by measuring the 'horizontal distance' between the demand bound function and the supply bound function. Then we present an exact RTA method based on the above idea but eliminating the pessimism in the first analysis. This new exact RTA method, not only allows to precisely analyze more general system models than existing EDF RTA techniques, but also significantly improves analysis efficiency. Experiments are conducted to show efficiency improvement of our new RTA technique, and tradeoffs between the analysis precision and efficiency of the two methods in this paper are discussed.
Original languageEnglish
Title of host publicationProceedings - Design, Automation and Test in Europe, DATE 2014
ISBN (Print)9783981537024
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event17th Design, Automation and Test in Europe, DATE 2014 - Dresden, Germany
Duration: 24 Mar 201428 Mar 2014


Conference17th Design, Automation and Test in Europe, DATE 2014

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'General and efficient Response Time Analysis for EDF scheduling'. Together they form a unique fingerprint.

Cite this