An Event Stream Driven Approximation for the Analysis of Real-Time Systems

Albers, Karsten and Slomka, Frank
IEEE Proceedings of the 16th Euromicro Conference on Real-Time Systems
This paper presents a new approach to understand the event stream model. Additionally a new approximation algorithm for the feasibility test of the sporadic and the generalized multiframe task system scheduled by earliest deadline first is presented. The new algorithm has a polynomial complexity to solve the Co-NP hard problem of schedulability analysis. The approximation error of the algorithm is bounded. In contrary to earlier work, where the error depends on the different deadlines of the tasks, the error of our algorithm depends only on the capacity of the chosen processor. It guarantees the acceptances of a processor with a slightly higher capacity than the unknown optimal processor. While the algorithm is scalable and the run-time depends on the chosen error, a trade-off between running time and error is possible.
07 / 2004