On optimal lateness and tardiness scheduling in real-time systems

Abstract

We address lateness and tardiness scheduling policies for real-time systems. It is well-known that preemptive Earliest Deadline First (EDF) minimizes the worst lateness and tardiness of a finite set of tasks with known arrival times, service times and deadlines to the finishing time, on a uniprocessor. We extend this result significantly, to include an arbitrary (possibly infinite) number of tasks with arbitrary arrival and service times, and deadlines, and to show that EDF 1. minimizes the lateness and tardiness of the tasks that are in the system at an arbitrary time. 2. minimizes lateness within a busy interval, for an arbitrary, possibly infinite number of tasks. 3. maximizes the time to the first missed deadline, and 4. minimizes the length of time during which there is at least one missed deadline in the system. We also show that a combination of EDF and Shortest Remaining Processing Time First (SRPTF) policy minimizes maximum latenesses in a vector sense (as defined tin the paper) and minimizes the number of tasks that miss their deadline at the time the first missed deadline occurs. For non-preemptive non-idling polices, we establish new, similar results in a stochastic sense. We attempt extending our findings to multiprocessor systems. We demonstrate that under the assumptions of arbitrary distributions of arrival times, service times and deadlines, our results no longer hold true. When a further assumption of unit-length service times and integer-valued arrival times is introduced, we are able to re-establish the results in the multiprocessor case. © 1992 Springer-Verlag.