Approximate schedulability analysis

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.