Linear Time On-Line Feasibility Testing Algorithms for Fixed-Priority, Hard Real-Time Systems
Michael E. Thomadakis, Jyh Liu · 2000
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 #(n) computation time, where n is the number of periodic tasks. Our tests draw upon the Workload-Matrix method, an innovative technique which determines the idle capacity within arbitrary intervals [t 1 , t 2 ) of a periodic schedule 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 -secs on commodity Unix workstations.