344
6 Abbildung von Anwendungen
τ
τ
1
2
t
0
6
12
2
4
8
10
16
14
18
20 22 24
Abb. 6.17 Mit EDF erzeugtes Schedule für das Beispiel aus Abb. 6.14
∇
Tasks mit expliziter Deadline
Nunmehr gehen wir über zur Betrachtung von Tasks, deren Deadline von der Periode
verschieden ist. Solche Tasks heißen Tasks mit expliziter Deadline. In einem solchen
System ist jede Task durch ein Tripel (C i , D i ,T i ) charakterisiert, wobei D i die relative
Deadline ist. Der Fall D i ≤ T i heißt constrained deadline-Fall. Wenn eine solche
Einschränkung nicht existiert, sprechen wir von einer beliebigen Deadline (engl.
arbitrary deadline). Offensichtlich ist der Fall einer expliziten Deadline allgemeiner
als der Fall einer impliziten Deadline und jede Task mit impliziter Deadline ist auch
eine Task mit expliziter Deadline.
Bei Tasks mit expliziter Deadline ist die Auslastung nur sehr begrenzt zur Charakterisierung der Rechenanforderungen geeignet. In gewissem Umfang spielt nunmehr
die Dichte (engl. density) die Rolle, welche bislang die Auslastung spielte. Die
Dichte ist wie folgt definiert:
dens i =
C i
min(D i ,T i )
(6.10)
dens sum (τ) =
τ i ∈τ
dens i
(6.11)
dens max (τ) = max
τ i ∈τ
(dens i )
(6.12)
Werte der Dichte charakterisieren Rechenzeitanforderungen. Die Demand-BoundFunction (DBF) liefert allerdings bessere Schranken:
Definition 6.13: Die Demand-Bound-Function DBF(τ i , t) ist, für jede sporadische
Task τ i und jede reelle Zahl t ≥ 0, die größte aufsummierte Rechenanforderung
aller Jobs, die von τ i erzeugt werden können und die sowohl den Zeitpukt der
Ausführbarkeit wie auch die Deadline in einem zusammenhängenden Intervall der
Länge t haben.
Die aufsummierten Rechenanforderungen von Task τ i in einem Intervall [t 0 , t 0 + t)
sind maximiert, wenn einer ihrer Jobs zu Beginn des Intervalls eintrifft (d.h. zur Zeit
t 0 ) und die nachfolgenden Jobs treffen so schnell wie erlaubt ein, d.h. an Zeitpunkten
t 0 +T i , t 0 +2T i , t 0 +3T i , .... Diese Beobachtung führt uns zur Gleichung (6.13) [40, 38]:
6 Abbildung von Anwendungen
τ
τ
1
2
t
0
6
12
2
4
8
10
16
14
18
20 22 24
Abb. 6.17 Mit EDF erzeugtes Schedule für das Beispiel aus Abb. 6.14
∇
Tasks mit expliziter Deadline
Nunmehr gehen wir über zur Betrachtung von Tasks, deren Deadline von der Periode
verschieden ist. Solche Tasks heißen Tasks mit expliziter Deadline. In einem solchen
System ist jede Task durch ein Tripel (C i , D i ,T i ) charakterisiert, wobei D i die relative
Deadline ist. Der Fall D i ≤ T i heißt constrained deadline-Fall. Wenn eine solche
Einschränkung nicht existiert, sprechen wir von einer beliebigen Deadline (engl.
arbitrary deadline). Offensichtlich ist der Fall einer expliziten Deadline allgemeiner
als der Fall einer impliziten Deadline und jede Task mit impliziter Deadline ist auch
eine Task mit expliziter Deadline.
Bei Tasks mit expliziter Deadline ist die Auslastung nur sehr begrenzt zur Charakterisierung der Rechenanforderungen geeignet. In gewissem Umfang spielt nunmehr
die Dichte (engl. density) die Rolle, welche bislang die Auslastung spielte. Die
Dichte ist wie folgt definiert:
dens i =
C i
min(D i ,T i )
(6.10)
dens sum (τ) =
τ i ∈τ
dens i
(6.11)
dens max (τ) = max
τ i ∈τ
(dens i )
(6.12)
Werte der Dichte charakterisieren Rechenzeitanforderungen. Die Demand-BoundFunction (DBF) liefert allerdings bessere Schranken:
Definition 6.13: Die Demand-Bound-Function DBF(τ i , t) ist, für jede sporadische
Task τ i und jede reelle Zahl t ≥ 0, die größte aufsummierte Rechenanforderung
aller Jobs, die von τ i erzeugt werden können und die sowohl den Zeitpukt der
Ausführbarkeit wie auch die Deadline in einem zusammenhängenden Intervall der
Länge t haben.
Die aufsummierten Rechenanforderungen von Task τ i in einem Intervall [t 0 , t 0 + t)
sind maximiert, wenn einer ihrer Jobs zu Beginn des Intervalls eintrifft (d.h. zur Zeit
t 0 ) und die nachfolgenden Jobs treffen so schnell wie erlaubt ein, d.h. an Zeitpunkten
t 0 +T i , t 0 +2T i , t 0 +3T i , .... Diese Beobachtung führt uns zur Gleichung (6.13) [40, 38]: