Schedulability analysis of fixed priority systems with limited priority levels
Xiaohui Liu · Computer Engineering and Applications Journal · 2009
In the area of communication,radar,navigation and various electronic production,embedded real-time scheduling has became the control kernel of those electronic and electrical systems.In fixed priority systems where tasks with the same priority are queued in FIFO(First In First Out) order,counterexamples are used to point out that the necessary assertion of Katcher’s schedulability condition does not hold.A necessary and sufficient condition for fixed priority scheduling with limited priority levels is proposed and proved analytically.Stochastic analysis show that when the execution times of different tasks are remarkably dis- tinct with each other,approximately 15% of schedulable task sets are misjudged by Katcher’s condition.Further simulations show that Liu’s condition,Lehoczky’s condition,and Bini’s condition cannot deal with tasks with the same priority,Katcher’s condition does not hold for its necessary assertion;meanwhile the condition provides the necessary and sufficient perspective of off-line schedulability checking.This method provides an off-line tool for top-down design of real-time scheduling with high utilization.