On non-preemptive scheduling of period and sporadic tasks

A fundamental problem in the theory of real-time scheduling is examined: scheduling a set of periodic or sporadic tasks on a uniprocessor without preemption and without inserted idle time. The authors give a necessary and sufficient set of conditions C for a set of periodic or sporadic tasks to be schedulable for arbitrary release times of the tasks. They show that any set of periodic or sporadic tasks that satisfies C can be scheduled with an earliest-deadline-first (EDF) scheduling algorithm. The authors present the scheduling model, briefly review the literature in real-time scheduling, prove that the non-preemptive EDF algorithm is universal for sets of tasks, whether periodic or sporadic, and demonstrate the absence of a universal algorithm for periodic tasks with specified release times. It is proved that the problem of deciding schedulability of a set of concrete periodic tasks is intractable.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>