6.1 Problemdefinition
329
Auswahl an Algorithmen präsentieren, die in eingebetteten Systemen häufig benutzt
werden. Eine Übersicht über die ausgewählten Algorithmen ist in Tabelle 6.1 zu
sehen. Von links nach rechts betrachtet, beziehen sich die Spalten auf das ProzesTabelle 6.1 Scheduling-Algorithmen dieses Kapitels
α
β
γ
Ab- Algorithmus
Proc. r i prmp prec periodic a D i prio glob Zielfkt. schnitt
1 - -
-
-
L ma x
6.2.1 Earliest Due Date
1 X X
-
-
L ma x
6.2.1 Earliest Deadline First
1 X X
-
-
L ma x
6.2.1 Least Laxity
1 X -
-
-
L ma x
6.2.1 (Theorem 6.3)
1 X X
X
-
Job
L ma x
6.2.2 Latest Deadline First
1 X -
X
-
L ma x
6.2.2 Spring OS [508]
1 X X
-
X
= T i Task
≤ D i
6.2.3 Rate Monotonic
1 X X
-
X
T i Task
≤ D i
6.2.3 Deadline Monotonic
Pm - -
-
-
X
m = |π | 6.3.1 Bin Packing
Pm - -
-
-
X
b i
6.3.1 0/1 Multi-Knapsack
Pm X X
-
X
= T i
≤ D i
6.3.1 First Fit Decreasing
Pm X X
-
X
= T i Job X
≤ D i
6.3.2 Pfair
Pm X X
-
-
Job X
≤ D i
6.3.3 G-EDF, fpEDF, EDZL
Pm X X
-
X
= T i Task X
≤ D i
6.3.4 G-RM, RM-US, RMZL
Pm X X
-
X
T i Task X
≤ D i
6.3.4 Dichte-basiert
Pm - -
X
-
M S ma x 6.4
ASAP, ALAP
Rm b - -
X
-
M S ma x 6.4.3 List Scheduling
Pm - -
X
-
M S ma x 6.4.4 Ganzz.Lin.Progr.(ILP)
Rm - -
X
-
M S ma x 6.5.2 HEFT, CPOP
Rm - -
X
-
M S ma x 6.5.3 ILP, z.B. [362]
Rm X X
X
-
(X) verschiedene 6.5.4 DOL, HOPES, MAPS,
a Algorithmen für aperiodische Task-Mengen können auch für periodische/sporadische Mengen
benutzt werden.
b List scheduling unterstützt heterogene Prozessoren nur eingeschränkt.
sormodell, asynchrone Ankunftszeiten, Verdrängbarkeit, Reihenfolgebeschränkungen, periodische/sporadische vs. aperiodische Tasks bzw. Jobs, das Deadline-Modell
(falls existent), Job- vs. Task-Prioritäten, globales vs. lokales Scheduling (für Multiprozessoren), die Zielfunktion, den Unterabschnitt im Buch und den Namen des
Algorithmus. Algorithmen wie Earliest Deadline First sind für nicht-periodische
Systeme entwickelt, aber sie können auch auf periodische/sporadische angewandt
werden. Aus der ersten Spalte geht hervor, dass heterogene Multiprozessoren nur
durch die Algorithmen in den letzten drei Zeilen voll unterstützt werden. Uniforme
Prozessoren werden nur als Anwendung des 0/1 Multi-Knapsack-Modells erwähnt.
Verdrängungen sind nutzlos, wenn alle Jobs zu derselben Zeit ausführungsbereit
werden (kenntlich gemacht durch ein „-” in der zweiten Spalte). Daher gibt es in
diesem Fall in der dritten Spalte kein X. Einträge in der Spalte D i sind nur für
periodische/sporadische Tasks relevant. Als Zielfunktion wird in vielen Fällen die
maximale Verspätung benutzt. Für periodisches/sporadisches Scheduling ist die wesentliche Frage aber: gibt es ein Schedule, welches die Deadline erfüllt? Bin packing
329
Auswahl an Algorithmen präsentieren, die in eingebetteten Systemen häufig benutzt
werden. Eine Übersicht über die ausgewählten Algorithmen ist in Tabelle 6.1 zu
sehen. Von links nach rechts betrachtet, beziehen sich die Spalten auf das ProzesTabelle 6.1 Scheduling-Algorithmen dieses Kapitels
α
β
γ
Ab- Algorithmus
Proc. r i prmp prec periodic a D i prio glob Zielfkt. schnitt
1 - -
-
-
L ma x
6.2.1 Earliest Due Date
1 X X
-
-
L ma x
6.2.1 Earliest Deadline First
1 X X
-
-
L ma x
6.2.1 Least Laxity
1 X -
-
-
L ma x
6.2.1 (Theorem 6.3)
1 X X
X
-
Job
L ma x
6.2.2 Latest Deadline First
1 X -
X
-
L ma x
6.2.2 Spring OS [508]
1 X X
-
X
= T i Task
≤ D i
6.2.3 Rate Monotonic
1 X X
-
X
T i Task
≤ D i
6.2.3 Deadline Monotonic
Pm - -
-
-
X
m = |π | 6.3.1 Bin Packing
Pm - -
-
-
X
b i
6.3.1 0/1 Multi-Knapsack
Pm X X
-
X
= T i
≤ D i
6.3.1 First Fit Decreasing
Pm X X
-
X
= T i Job X
≤ D i
6.3.2 Pfair
Pm X X
-
-
Job X
≤ D i
6.3.3 G-EDF, fpEDF, EDZL
Pm X X
-
X
= T i Task X
≤ D i
6.3.4 G-RM, RM-US, RMZL
Pm X X
-
X
T i Task X
≤ D i
6.3.4 Dichte-basiert
Pm - -
X
-
M S ma x 6.4
ASAP, ALAP
Rm b - -
X
-
M S ma x 6.4.3 List Scheduling
Pm - -
X
-
M S ma x 6.4.4 Ganzz.Lin.Progr.(ILP)
Rm - -
X
-
M S ma x 6.5.2 HEFT, CPOP
Rm - -
X
-
M S ma x 6.5.3 ILP, z.B. [362]
Rm X X
X
-
(X) verschiedene 6.5.4 DOL, HOPES, MAPS,
a Algorithmen für aperiodische Task-Mengen können auch für periodische/sporadische Mengen
benutzt werden.
b List scheduling unterstützt heterogene Prozessoren nur eingeschränkt.
sormodell, asynchrone Ankunftszeiten, Verdrängbarkeit, Reihenfolgebeschränkungen, periodische/sporadische vs. aperiodische Tasks bzw. Jobs, das Deadline-Modell
(falls existent), Job- vs. Task-Prioritäten, globales vs. lokales Scheduling (für Multiprozessoren), die Zielfunktion, den Unterabschnitt im Buch und den Namen des
Algorithmus. Algorithmen wie Earliest Deadline First sind für nicht-periodische
Systeme entwickelt, aber sie können auch auf periodische/sporadische angewandt
werden. Aus der ersten Spalte geht hervor, dass heterogene Multiprozessoren nur
durch die Algorithmen in den letzten drei Zeilen voll unterstützt werden. Uniforme
Prozessoren werden nur als Anwendung des 0/1 Multi-Knapsack-Modells erwähnt.
Verdrängungen sind nutzlos, wenn alle Jobs zu derselben Zeit ausführungsbereit
werden (kenntlich gemacht durch ein „-” in der zweiten Spalte). Daher gibt es in
diesem Fall in der dritten Spalte kein X. Einträge in der Spalte D i sind nur für
periodische/sporadische Tasks relevant. Als Zielfunktion wird in vielen Fällen die
maximale Verspätung benutzt. Für periodisches/sporadisches Scheduling ist die wesentliche Frage aber: gibt es ein Schedule, welches die Deadline erfüllt? Bin packing