Scheduling Arbitrary-Deadline Sporadic Task Systems on Multiprocessors

A new algorithm is proposed for scheduling preemptible arbitrary-deadline sporadic task systems upon multiprocessor plaforms, with interprocessor migration permitted. This algorithm is based on a task-splitting approach while most tasks are entirely assigned to specific processors, a few tasks (fewer than the number of processors) may be split across two processors. This algorithm can be used for two distinct purposes: for actually scheduling specific sporadic task systems, and for feasibility analysis. Simulation-based evaluation indicates that this algorithm offers a significant improvement on the ability to schedule arbitrary-deadline sporadic task systems as compared to the contemporary state-of-art. With regard to feasibility analysis, the new algorithm is proved to offer superior performance guarantees in comparison to prior feasibility tests.