Preemptively scheduling hard-real-time sporadic tasks on one processor

Abstract

Consideration is given to the preemptive scheduling of hard-real-time sporadic task systems on one processor. The authors first give necessary and sufficient conditions for a sporadic task system to be feasible (i.e., schedulable). The conditions cannot, in general, be tested efficiently (unless P=NP). They do, however, lead to a feasibility test that runs in efficient pseudo-polynomial time for a very large percentage of sporadic task systems.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>