Improvement in feasibility testing for real-time tasks

Scheduling analysis in real-time systems require an off-line feasibility (schedulability) test to guarantee the response time of critical tasks. There are fast and efficient tests for static schedulers. However, when a dynamic scheduler is required, the available tests are not as feast and efficient as static ones. In this paper, two different characterizations of feasible task sets are presented. These characterizations lead to an new feasibility algorithm. The proposed algorithm has an worst-case exponential complexity, but experimental results indicate that it runs on pseudo-polynomial time for a very large percentage of task sets. The algorithm also provides a sufficient condition for feasible asynchronous task sets. One of the main contributions of this work is the theoretical approach used to obtain the new feasibility test. The results of a large number of simulations, as well as, the theoretical demonstrations point out the improvements reached over previous tests.