Introduction

This paper derives simple sufficient conditions for schedulability of systems of periodic or sporadic tasks in a multiprocessor preemptive scheduling environment.

In 1973 Liu and Layland[13] proved that systems of independent periodic tasks for which the relative deadline of each task is equal to its period will be scheduled to meet all deadlines by an preemptive earliest-deadline-first (EDF) scheduling policy so long as total processing demand does not exceed 100 percent of the system capacity. Besides showing that that EDF scheduling is optimal for such task systems, this utilization bound provides a simple and effective a priori test for EDF schedulability. In the same paper Liu and Layland showed that if one is restricted to a fixed priority per task the optimal priority assignment is rate monotonic (RM), where tasks with shorter periods get higher priority. Liu and Layland showed further that a set of $n$ periodic tasks is guaranteed to to meet deadlines on a single processor under RM scheduling if the system utilization is no greater than $n(2^{1/n}-1)$. This test for RM scheduling and the 100% test for EDF scheduling have proven to be very useful tests for schedulability on a single processor system.

It is well known that the Liu and Layland results break down on multiprocessor systems[14]. Dhall and Liu[9] gave examples of task systems for which RM and EDF scheduling can fail at very low processor utilizations, essentially leaving all but one processor idle nearly all of the time. Reasoning from such examples, it is tempting to conjecture that there is unlikely to be a useful utilization bound test for EDF or RM scheduling, and even that these are not good real-time scheduling policies for multiprocessor systems. However, neither conclusion is actually justified.

The ill behaving examples have two kinds of tasks: tasks with a high ratio of compute time to deadline, and tasks with a low ratio of compute time to deadline. It is the mixing of those two kinds of tasks that causes the problem. A policy that segregates the heavier tasks from the lighter tasks, on disjoint sets of CPU's, would have no problem with this example. Examination of further examples leads one to conjecture that such a segregated scheduling policy would not miss any deadlines until a very high level of CPU utilization is achieved, and even permits the use of simple utilization-based schedulability tests.

In 1997, Phillips, Stein, Torng, and Wein[16] studied the competitive performance of on-line multiprocessor scheduling algorithms, including EDF and fixed priority scheduling, against optimal (but infeasible) clairvoyant algorithms. Among other things, they showed that if a set of tasks is feasible (schedulable by any means) on $m$ processors of some given speed then the same task set is schedulable by preemptive EDF scheduling on $m$ processors that are faster by a factor of $(2-\frac{1}{m})$. Based on this paper, several overlapping teams of authors have produced a series of schedulability tests for multiprocessor EDF and RM scheduling[2,6,7,8,18].

We have approached the problem in a somewhat different and more direct way, which allows for tasks to have preperiod deadlines. This led to more general schedulability conditions, of which the above cited schedulability tests are special cases. The rest of this paper presents the derivation of these more general multiprocessor EDF and deadline monotonic (DM) schedulability conditions, and their relationship to the above cited prior work.

This conference paper is a condensation and summary of two technical reports, one of which deals with EDF scheduling[4] and the other of which deals with deadline monotonic scheduling[5]. To fit the conference page limits, it refers to those reports (available via HTTP) for most of the details of the proofs. The preliminaries apply equally to both EDF and RM scheduling. When the two cases diverge, the EDF case is treated first, and in slightly more detail.