334
6 Abbildung von Anwendungen
t =4
1
2
t
11
10
9
8
7
6
5
4
3
2
1
0
3
J
J
J
t
( )=2
S
Abb. 6.7 Schedule nach dem Vertauschen von Jobs S(t) und E(t)
maximale Verspätung in Schedule S gleich 0. Deswegen und weil EDF ein Schedule
mit minimaler Verspätung erzeugt, ist die maximale Verspätung des EDF-Schedules
auch gleich Null. Daher ist das EDF-Schule für diese Problemklasse das optimale
Schedule, das auch die Deadlines einhält.
⊓ ⊔
Least Laxity-Algorithmus
Wir wenden uns nunmehr der Betrachtung des Schlupfes (engl. laxity) zu und untersuchen den Fall (1|r i , prmp, ..|..), wobei wir ein Schedule finden möchten, sofern es
existiert. Least Laxity (LL), Least Slack Time First (LST) und Minimum Laxity First
(MLF) sind drei Namen für eine Schlupf-basierte Scheduling-Strategie [349]. Beim
LL-Scheduling sind die Prioritäten der Jobs eine monoton fallende Funktion ihres
Schlupfs (siehe Gleichung (6.1); je weniger Spielraum ein Job also hat, desto höher
seine Priorität). Der Schlupf verändert sich dynamisch.
Beispiel 6.2: Abb. 6.8 zeigt ein Beispiel eines LL-Schedules mit den berechneten
Laxity-Werten.
J
J
32
30
28
26
24
2
4
6
8
10 12 14 16 18 20 22
0
28
29
33
5
4
0
10
3
10
t
2
3
1
l
l
l
l
l
l
l
l
l
l
l
l
( )=28-4-3=21
( )=33-4-6=23 ( )=33-5-6=22
( )=28-5-2=21
( )=29-5-10=14 ( )=29-13-2=14
( )=28-13-2=13
( )=33-13-6=14
( )=29-16-1=12
( )=33-16-6=11
( )=29-15-2=12
( )=33-15-6=12
1
J
2
J
3
J
J
J
J
J 2
J 1
J 2
J 1
2
J
3
3
3
J 1
J
J 1
3
J
J 1
Ankunft Dauer
Deadline
Abb. 6.8 Least laxity-Schedule
6 Abbildung von Anwendungen
t =4
1
2
t
11
10
9
8
7
6
5
4
3
2
1
0
3
J
J
J
t
( )=2
S
Abb. 6.7 Schedule nach dem Vertauschen von Jobs S(t) und E(t)
maximale Verspätung in Schedule S gleich 0. Deswegen und weil EDF ein Schedule
mit minimaler Verspätung erzeugt, ist die maximale Verspätung des EDF-Schedules
auch gleich Null. Daher ist das EDF-Schule für diese Problemklasse das optimale
Schedule, das auch die Deadlines einhält.
⊓ ⊔
Least Laxity-Algorithmus
Wir wenden uns nunmehr der Betrachtung des Schlupfes (engl. laxity) zu und untersuchen den Fall (1|r i , prmp, ..|..), wobei wir ein Schedule finden möchten, sofern es
existiert. Least Laxity (LL), Least Slack Time First (LST) und Minimum Laxity First
(MLF) sind drei Namen für eine Schlupf-basierte Scheduling-Strategie [349]. Beim
LL-Scheduling sind die Prioritäten der Jobs eine monoton fallende Funktion ihres
Schlupfs (siehe Gleichung (6.1); je weniger Spielraum ein Job also hat, desto höher
seine Priorität). Der Schlupf verändert sich dynamisch.
Beispiel 6.2: Abb. 6.8 zeigt ein Beispiel eines LL-Schedules mit den berechneten
Laxity-Werten.
J
J
32
30
28
26
24
2
4
6
8
10 12 14 16 18 20 22
0
28
29
33
5
4
0
10
3
10
t
2
3
1
l
l
l
l
l
l
l
l
l
l
l
l
( )=28-4-3=21
( )=33-4-6=23 ( )=33-5-6=22
( )=28-5-2=21
( )=29-5-10=14 ( )=29-13-2=14
( )=28-13-2=13
( )=33-13-6=14
( )=29-16-1=12
( )=33-16-6=11
( )=29-15-2=12
( )=33-15-6=12
1
J
2
J
3
J
J
J
J
J 2
J 1
J 2
J 1
2
J
3
3
3
J 1
J
J 1
3
J
J 1
Ankunft Dauer
Deadline
Abb. 6.8 Least laxity-Schedule