Linear Time On-Line Feasibility Testing Algorithms for Fixed-Priority, Hard Real-Time Systems: A Performance Evaluation
Michael E. Thomadakis · 2001
In this paper we develop linear time, on-line feasibility testing algorithms for the guaranteed scheduling of firm aperiodic tasks in fixed-priority real-time systems. Firm aperiodic, unlike critical periodic tasks which are guaranteed off-line, can be guaranteed dynamically only if they pass on-line feasibility tests. In this paper we derive feasibility tests requiring a one time $\Theta(n)$ computation time, where $n$ is the number of periodic tasks. Our tests draw upon the {\em Workload-Matrix} method, an innovative technique which determines the idle capacity within arbitrary intervals $[t_1, t_2)$ of a periodic schedule {\em exactly}. To the best of our knowledge, this is the first algorithm reported in the literature, which can perform on-line schedulability testing in linear time. Previous state-of-the-art on-line schedulability methods are based on either static or dynamic slack stealing, or EDL methods by Silly and Chetto, and they require pseudo-polynomial time to guarantee one single task and they incur continuously overhead for state variable maintenance. The proposed method utilizes the entire spare capacity in the schedule, it maintaines guarantess to the periodic tasks, and experiments show that the computation time for admission control is in the order of a few $\mu$-secs on commodity Unix workstations. For clarity we present feasibility testign algorithms for one outstanding firm task at a time. The feasibility testing method maximizes the probability of admission for firm aperiodic tasks under different workload conditions and with different periodic task sets.