332
6 Abbildung von Anwendungen
2. L ′
a ≤ L ′
b :
In diesem Fall haben wir:
L ′
max (a, b) = f ′
b − d b = f a − d b (siehe Abb. 6.4).
Die Deadline von J a liegt vor derjenigen von J b . Dies führt auf
L ′
max (a, b) < f a − d a
Wieder gilt:
L ′
max (a, b) < L max (a, b)
Als Ergebnis kann jedes von einem EDD-Schedule verschiedene Schedule in endlich
vielen Vertauschungen in ein EDD-Schedule transformiert werden, wobei die maximale Verspätung nur kleiner werden kann. Also ist EDD optimal für diese Klasse
von Scheduling-Problemen. q.e.d.
⊓ ⊔
Earliest Deadline First-Algorithmus
Betrachten wir nun den Fall von unterschiedlichen Ankunftszeiten für ein Einzelprozessor-System. Bei diesem Szenario kann ein Verdrängen von Jobs (engl.
preemption) potentiell die maximale Verspätung verbessern. In der Triplet-Notation
entspricht dies dem Fall (1 | r i , prmp | L max ).
Der Earliest Deadline First (EDF)-Algorithmus ist optimal in Bezug auf die
Minimierung der maximalen Verspätung. Er basiert auf folgendem Theorem [223]:
Theorem 6.2: Wenn eine Menge von n unabhängigen Jobs mit beliebigen Ankunftszeiten gegeben ist, so ist ein Algorithmus, der zu jedem Zeitpunkt den ausführungsbereiten Job mit der frühesten absoluten Deadline ausführt, optimal in Bezug auf
die Minimierung der maximalen Verspätung.
Bei EDF muss jeder ankommende ausführungsbereite Job in eine Warteschlange
von ausführbereiten Jobs eingefügt werden. Die Jobs in der Warteschlange sind nach
ihrer Deadline sortiert. Wenn ein neu angekommener Job als erstes Element in die
Warteschlange eingefügt wird, muss der gerade ausgeführte Job beendet werden.
Beispiel 6.1: Abb. 6.5 zeigt ein EDF-Schedule.
J 1
J 3
J 2
3
J
2
J
1
J
32
30
Deadline
Ankünfte
Dauer
Ankunft
t
2
4
6
8
10 12 14 16 18 20 22
0
33
29
28
10
3
10
5
4
0
24 26 28
Abb. 6.5 EDF-Schedule
6 Abbildung von Anwendungen
2. L ′
a ≤ L ′
b :
In diesem Fall haben wir:
L ′
max (a, b) = f ′
b − d b = f a − d b (siehe Abb. 6.4).
Die Deadline von J a liegt vor derjenigen von J b . Dies führt auf
L ′
max (a, b) < f a − d a
Wieder gilt:
L ′
max (a, b) < L max (a, b)
Als Ergebnis kann jedes von einem EDD-Schedule verschiedene Schedule in endlich
vielen Vertauschungen in ein EDD-Schedule transformiert werden, wobei die maximale Verspätung nur kleiner werden kann. Also ist EDD optimal für diese Klasse
von Scheduling-Problemen. q.e.d.
⊓ ⊔
Earliest Deadline First-Algorithmus
Betrachten wir nun den Fall von unterschiedlichen Ankunftszeiten für ein Einzelprozessor-System. Bei diesem Szenario kann ein Verdrängen von Jobs (engl.
preemption) potentiell die maximale Verspätung verbessern. In der Triplet-Notation
entspricht dies dem Fall (1 | r i , prmp | L max ).
Der Earliest Deadline First (EDF)-Algorithmus ist optimal in Bezug auf die
Minimierung der maximalen Verspätung. Er basiert auf folgendem Theorem [223]:
Theorem 6.2: Wenn eine Menge von n unabhängigen Jobs mit beliebigen Ankunftszeiten gegeben ist, so ist ein Algorithmus, der zu jedem Zeitpunkt den ausführungsbereiten Job mit der frühesten absoluten Deadline ausführt, optimal in Bezug auf
die Minimierung der maximalen Verspätung.
Bei EDF muss jeder ankommende ausführungsbereite Job in eine Warteschlange
von ausführbereiten Jobs eingefügt werden. Die Jobs in der Warteschlange sind nach
ihrer Deadline sortiert. Wenn ein neu angekommener Job als erstes Element in die
Warteschlange eingefügt wird, muss der gerade ausgeführte Job beendet werden.
Beispiel 6.1: Abb. 6.5 zeigt ein EDF-Schedule.
J 1
J 3
J 2
3
J
2
J
1
J
32
30
Deadline
Ankünfte
Dauer
Ankunft
t
2
4
6
8
10 12 14 16 18 20 22
0
33
29
28
10
3
10
5
4
0
24 26 28
Abb. 6.5 EDF-Schedule