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 thatEDF

• 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 ofEDF 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.

Zusammenfassung

Diese Arbeit beschäftigt sich mit Lösungsansätzen für das Problem der verfrühten (Lateness) bzw. verspäteten (Tardiness) Beendigung von Tasks in Realzeitsystemen. Es ist hinlänglich bekannt, daß Earliest Deadline First (EDF) Algorithmen die schlechtest mögliche Lateness und Tardiness minimieren, vorausgesetzt es handelt sich um eine endliche Menge von Tasks mit bekannten Ankunftszeiten, Servicezeiten und Deadlines auf einer Einprozessor-Architektur. Wir erweitern die bekannten Resultate signifikant um die Möglichkeit der Handhabung einer unbestimmten (möglicherweise unendlichen) Anzahl von Tasks mit freien Ankunfts- und Servicezeiten und mit unbestimmten Deadlines. Wir zeigen dabei die Gültigkeit der folgenden Aussagen:

• 1. EDF minimiert Lateness und Tardiness von Tasks, die sich zu einem beliebigen Zeitpunkt im System befinden.

• 2. EDF minimiert Lateness innerhalb eines aktiven Intervalls für eine beliebige, möglicherweise unendliche Anzahl von Tasks.

• 3. EDF maximiert die Zeit, bis die erste Deadline versäumt wird.

• 4. EDF minimiert die Zeitspanne, während der zumindets eine versäumte Deadline im System ist.

Weiters zeigen wir, daß eine Kombination vonEDF und Shortest Remaining Processing Time First (SRPRF) doppelt minimierende Wirkung hat. Minimiert wird sowohl die schlechtest möglichen Lateness im System im Sinne eines Vektors (wie in der Arbeit definiert), als auch die Anzahl von Tasks die ihre Deadline zu dem Zeitpunkt versäumen, zu dem die erste versäumte Deadline überhaupt auftritt. Für non-preemptive, non-idling Algorithmen leiten wir ähnliche neue Resultate auf stochastischer Basis ab.

Wir verifizieren unsere Ergebnisse für Multiprozessor-Architekturen und demonstrieren dabei, daßunter der Annahme beliebiger Verteilung der Ankunftszeiten, Servicezeiten und Deadlines unsere Resultate nicht länger gültig, bleiben. Unter der Voraussetzung weiterer Annahmen, nämlich der Beschränkung der Servicezeiten auf die im System verwendeten Zeiteinheiten und auf ganzzahligen, Ankunftszeiten, können wir die weiter oben angesprochenen Resultate auch für den Fall eines Mehrprozessorsystems aufrecht erhalten.