6.2 Scheduling für Einzelprozessoren
331
Earliest Due Date-Algorithmus
Noch weiter einschränkend betrachten wir die Situation, in der alle Jobs gleichzeitig
ausführungsbereit werden und wir die maximale Verspätung minimieren wollen.
Verdrängungen sind offenbar nutzlos, wenn alle Jobs zur selben Zeit ankommen. In
der Triplet-Notation betrachten wir daher den Fall (1|..|L max ). Für diesen Fall wurde
von Jackson 1955 [264] eine sehr einfache Regel gefunden:
Theorem 6.1 (Jacksons Regel): Wenn eine Menge von n unabhängigen Jobs gegeben ist, so ist jeder Algorithmus, der die Jobs in der Reihenfolge nicht-abnehmender
Deadlines ausführt, optimal in Bezug auf die Minimierung der maximalen Verspätung.
Der Algorithmus, der dieser Regel folgt, heißt Earliest Due Date (EDD). Wenn
die Deadlines vorab bekannt sind, kann EDD als ein statischer Algorithmus realisiert werden. Für EDD müssen die Jobs nach ihren Deadlines sortiert sein. Seine
Komplexität ist aufgrund des Sortierens O(n log(n)).
Beweis (der Optimalität von EDD): Sei S ein Schedule, das durch irgendeinen
Algorithmus A erzeugt wurde. Wenn A nicht die Wirkung von EDD hat, dann gibt
es Jobs J a und J b derart, dass die Ausführung von J b derjenigen von J a vorangeht,
obwohl die Deadline von J a kleiner ist als die von J b (d a < d b ). Wir betrachten nun
ein Schedule S ′ welches aus S durch Vertauschen der Ausführungsreihenfolge von
J a und J b entsteht (siehe Abb. 6.4).
= f ' b
a
f
S
S'
J b
J a
a
J
b
J
Abb. 6.4 SchedulesS und S ′
Für das Schedule S ′ ist L ′
max (a, b) = max(L ′
a , L ′
b ) die maximale Verspätung unter
den Jobs J a und J b . L ′
a ist die maximale Verspätung von Job J a in Schedule S ′ . L ′
b
wird entsprechend definiert. Es gibt zwei mögliche Fälle:
1. L ′
a > L ′
b : in diesem Fall haben wir
L ′
max (a, b) = f ′
a − d a
J a wird im neuen Schedule früher beendet. Deswegen gilt
L ′
max (a, b) = f ′
a − d a < f a − d a .
Die rechte Seite dieser Ungleichung ist die maximale Verspätung in Schedule S.
Deswegen gilt das folgende:
L ′
max (a, b) < L max (a, b)
331
Earliest Due Date-Algorithmus
Noch weiter einschränkend betrachten wir die Situation, in der alle Jobs gleichzeitig
ausführungsbereit werden und wir die maximale Verspätung minimieren wollen.
Verdrängungen sind offenbar nutzlos, wenn alle Jobs zur selben Zeit ankommen. In
der Triplet-Notation betrachten wir daher den Fall (1|..|L max ). Für diesen Fall wurde
von Jackson 1955 [264] eine sehr einfache Regel gefunden:
Theorem 6.1 (Jacksons Regel): Wenn eine Menge von n unabhängigen Jobs gegeben ist, so ist jeder Algorithmus, der die Jobs in der Reihenfolge nicht-abnehmender
Deadlines ausführt, optimal in Bezug auf die Minimierung der maximalen Verspätung.
Der Algorithmus, der dieser Regel folgt, heißt Earliest Due Date (EDD). Wenn
die Deadlines vorab bekannt sind, kann EDD als ein statischer Algorithmus realisiert werden. Für EDD müssen die Jobs nach ihren Deadlines sortiert sein. Seine
Komplexität ist aufgrund des Sortierens O(n log(n)).
Beweis (der Optimalität von EDD): Sei S ein Schedule, das durch irgendeinen
Algorithmus A erzeugt wurde. Wenn A nicht die Wirkung von EDD hat, dann gibt
es Jobs J a und J b derart, dass die Ausführung von J b derjenigen von J a vorangeht,
obwohl die Deadline von J a kleiner ist als die von J b (d a < d b ). Wir betrachten nun
ein Schedule S ′ welches aus S durch Vertauschen der Ausführungsreihenfolge von
J a und J b entsteht (siehe Abb. 6.4).
= f ' b
a
f
S
S'
J b
J a
a
J
b
J
Abb. 6.4 SchedulesS und S ′
Für das Schedule S ′ ist L ′
max (a, b) = max(L ′
a , L ′
b ) die maximale Verspätung unter
den Jobs J a und J b . L ′
a ist die maximale Verspätung von Job J a in Schedule S ′ . L ′
b
wird entsprechend definiert. Es gibt zwei mögliche Fälle:
1. L ′
a > L ′
b : in diesem Fall haben wir
L ′
max (a, b) = f ′
a − d a
J a wird im neuen Schedule früher beendet. Deswegen gilt
L ′
max (a, b) = f ′
a − d a < f a − d a .
Die rechte Seite dieser Ungleichung ist die maximale Verspätung in Schedule S.
Deswegen gilt das folgende:
L ′
max (a, b) < L max (a, b)