Abstract: This paper examines a fundamental problem in the theory of real-time scheduling, that of scheduling a set of periodic or sporadic tasks on a uniprocessor without preemption and without inserted idle time. We exhibit 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. We then show that any set of periodic or sporadic tasks that satisfies conditions C can be scheduled with an earliest deadline first (EDF) scheduling algorithm.
We also address the question of schedulability of a set of tasks with specified release times. For sets of sporadic tasks with specified release times, we show that the conditions C are again necessary and sufficient for schedulability. How- ever, for sets of periodic tasks with specified release times, the conditions C, while sufficient, are not necessary. In fact, we show that determining whether a set of periodic tasks with specified release times is schedulable is intractable (i.e., NP-hard in the strong sense). Moreover, we show that the existence of a universal algorithm for scheduling periodic tasks with specified release times would imply that P = NP.