Approximate schedulability analysis
Authors:
- S. ChakrabortySCS. Chakraborty
- S. KunzliSKS. Kunzli
- L. ThieleLTL. Thiele
- 26 June 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 159-168
Abstract
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 thedecisions 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.Keywords
This publication has 6 references indexed in Scilit:
- A general model for recurring real-time tasks2002
- Schedulability of generalized multiframe task sets under static priority assignment2002
- Schedulability of event-driven code blocks in real-time embedded systems2002
- On the Complexity of Scheduling Conditional Real-Time Code2001
- Generalized Multiframe TasksReal-Time Systems, 1999
- A multiframe model for real-time tasksIEEE Transactions on Software Engineering, 1997