6.2 Scheduling für Einzelprozessoren
345
DBF(τ i , t) = max
0,
t − D i
T i
+ 1
∗ C i
(6.13)
Die Dichte und die DBF hängen miteinander zusammen:
Lemma 6.2: Für alle Tasks τ i und für alle t ≥ 0:
t ∗ dens i ≥ DBF(τ i , t)
(6.14)
Beweis: Wir vergleichen die graphischen Darstellungen der Dichte und der DBF
als eine Funktion der Zeit. Abb. 6.18 zeigt die beiden Funktionen. Die linke Seite
DBF, dens
t
+3 i
T
i
D
+2 i
T
i
D
i
+T
i
D
i
D
dens
DBF
Abb. 6.18 Vergleich von Dichte und DBF
der Gleichung (6.14) ist als gerade Linie mit Steigung dens i dargestellt. Die DBF
ist eine Stufenfunktion mit Stufen der Höhe C i . Die Stufenfunktion steigt um C i
jedes Mal, wenn eine Task ausgeführt werden muss. Die erste Stufe ist bei t = D i .
Aufgrund der Definition der Dichte übersteigt diese Stufe nie die gerade Linie. Die
nächsten Stufen gibt es bei t = D i + T i , t = D i + 2T i , t = D i + 3T i usw. Auch diese
Stufen werden die Gerade nicht überschreiten.
⊓ ⊔
EDF kann leicht auf den Fall der von den Perioden verschiedenen Deadlines
erweitert werden. Für RMS heißt die Erweiterung Deadline Monotonic Scheduling
(DMS).
Deadline Monotonic Scheduling
Tasks mit expliziten Deadlines können mit Deadline Monotonic Scheduling (DMS)
zeitlich eingeplant werden. Statische Task-Prioritäten basieren bei DMS auf nichtaufsteigenden Deadlines: für zwei Tasks τ i und τ i ′ ist die Priorität von τ i größer als
die von τ i ′ wenn D i < D i ′ ist.
Für constrained deadline-Tasks kann die Schranke in Ungleichung (6.7) zur
Schranke in Ungleichung (6.15) verallgemeinert werden. Diese ist hinreichend, aber
nicht notwendig [81].
345
DBF(τ i , t) = max
0,
t − D i
T i
+ 1
∗ C i
(6.13)
Die Dichte und die DBF hängen miteinander zusammen:
Lemma 6.2: Für alle Tasks τ i und für alle t ≥ 0:
t ∗ dens i ≥ DBF(τ i , t)
(6.14)
Beweis: Wir vergleichen die graphischen Darstellungen der Dichte und der DBF
als eine Funktion der Zeit. Abb. 6.18 zeigt die beiden Funktionen. Die linke Seite
DBF, dens
t
+3 i
T
i
D
+2 i
T
i
D
i
+T
i
D
i
D
dens
DBF
Abb. 6.18 Vergleich von Dichte und DBF
der Gleichung (6.14) ist als gerade Linie mit Steigung dens i dargestellt. Die DBF
ist eine Stufenfunktion mit Stufen der Höhe C i . Die Stufenfunktion steigt um C i
jedes Mal, wenn eine Task ausgeführt werden muss. Die erste Stufe ist bei t = D i .
Aufgrund der Definition der Dichte übersteigt diese Stufe nie die gerade Linie. Die
nächsten Stufen gibt es bei t = D i + T i , t = D i + 2T i , t = D i + 3T i usw. Auch diese
Stufen werden die Gerade nicht überschreiten.
⊓ ⊔
EDF kann leicht auf den Fall der von den Perioden verschiedenen Deadlines
erweitert werden. Für RMS heißt die Erweiterung Deadline Monotonic Scheduling
(DMS).
Deadline Monotonic Scheduling
Tasks mit expliziten Deadlines können mit Deadline Monotonic Scheduling (DMS)
zeitlich eingeplant werden. Statische Task-Prioritäten basieren bei DMS auf nichtaufsteigenden Deadlines: für zwei Tasks τ i und τ i ′ ist die Priorität von τ i größer als
die von τ i ′ wenn D i < D i ′ ist.
Für constrained deadline-Tasks kann die Schranke in Ungleichung (6.7) zur
Schranke in Ungleichung (6.15) verallgemeinert werden. Diese ist hinreichend, aber
nicht notwendig [81].