A new algorithm for scheduling periodic, real-time tasks (Q1115592)

We consider the problem of preemptive scheduling a set of periodic, real- time tasks on a multiprocessor computer system. We give a new scheduling algorithm, the so-called slack-time algorithm, and show that it is more effective than the known deadline algorithm. We also give an (exponential-time) algorithm to decide if a task system is schedulable by the slack-time or the deadline-algorithm. The same algorithm can also be used to decide if a task system is schedulable by any given fixed- priority scheduling algorithm. This resolves an open question posed by the author and \textit{J. Whitehead} [Performance Eval. 2, 237-250 (1982; Zbl 0496.90046)]. Finally, it is shown that the problem of deciding if a task system is schedulable by the slack-time, the deadline, or any given fixed-priority scheduling algorithm is co-NP-hard for each fixed \(m\geq 1\).