Approximate schedulability analysis

Samarjit Chakraborty, Simon Künzli, Lothar Thiele

Research output: Contribution to conferencePaperpeer-review

42 Scopus citations


The schedulability analysis problem for many realistic task models is intractable. Therefore known algorithms either have exponential complexity or at best can be solved in pseudo-polynomial time, thereby restricting the application of the concerned models to a large extent. We introduce the notion of "approximate schedulability analysis" and show that if a small amount of "error" (which is specified as an input to the algorithm) can be tolerated in the decisions made by the algorithm, then this problem can be solved in polynomial time. Our algorithms are analogous to fully polynomial time approximation schemes in the context of optimization problems. We show that this concept of approximate schedulability analysis is fairly general and can be applied to any task model which satisfies certain "task-independence" assumptions. Lastly, we substantiate our theoretical results with experimental evidence and clearly show the tradeoffs between the running time of the schedulability analysis and the error incurred for various values of the input error parameter.

Original languageEnglish
Number of pages10
StatePublished - 2002
Externally publishedYes
EventProceedings Real-Time Systems Symposium - Austin, TX, United States
Duration: 3 Dec 20025 Dec 2002


ConferenceProceedings Real-Time Systems Symposium
Country/TerritoryUnited States
CityAustin, TX


Dive into the research topics of 'Approximate schedulability analysis'. Together they form a unique fingerprint.

Cite this