324
6 Abbildung von Anwendungen
auszuführen. Jede einzelne Task bezeichnen wir als τ i und die Menge aller Tasks als
τ = {τ 1 , ..., τ n }.
Definition 6.1: Jede Ausführung einer Task heißt ein Job (siehe auch Definition
4.4). Zu jeder Task τ i gehört eine Menge J(τ i ) von Jobs. Aufgrund der wiederholten
Ausführungen ist die Menge der Jobs von Task τ i möglicherweise nicht endlich.
Definition 6.2: Tasks τ i , die alle T Zeiteinheiten ausführungsbereit werden, heißen
periodische Tasks mit der Periode T.
Definition 6.3: Eine Task τ i heißt sporadisch, wenn es eine untere Schranke für den
Abstand der Zeitpunkte gibt, zu denen die Task ausführungsbereit wird. Für jede
sporadische Task τ i nennen wir diese Schranke auch T i .
Diese Schranke ist wichtig: ohne eine solche Schranke könnten die Ankunftskurven
für jedes ∆ unbeschränkt werden. Es wäre dann nicht möglich, für eine beschränkte
Menge an Ressourcen ein Schedule zu finden.
Definition 6.4: Tasks, die weder periodisch noch sporadisch sind, heißen aperiodisch.
Das Konzept der Hyperperioden ist für periodische und sporadische Task-Systeme
nützlich:
Definition 6.5: Sei τ ein periodisches oder sporadisches Task-System. Seine Hyperperiode ist definiert als das kleinste gemeinsame Vielfache (KGV) der Perioden
der einzelnen Tasks.
Wenn für eine Menge von Tasks für eine Hyperperiode ein Schedule existiert, dann
existiert es aufgrund der wiederholten identischen Scheduling-Aufgaben auch für
alle Hyperperioden.
6.1.2 Typen von Scheduling-Problemen
Im verbleibenden Teil dieses Kapitels wird die nachfolgende Notation für Jobs
benutzt: Sei J = {J i } eine Menge von Jobs. Sei ferner (siehe Abb. 6.2):
• r i der Zeitpunkt, an dem J i ausführungsbereit wird (engl. release time),
• C i die größtmögliche Ausführungszeit (engl. Worst Case Execution Time
(WCET)) von J i ,
• d i die (absolute) Deadline von J i ,
• D i die relative Deadline, d.h. die Zeit zwischen r i und der Zeit, zu der J i seine
Ausführung beendet haben soll (D i = d i − r i ),
• l i der Schlupf (engl. laxity oder slack), definiert als
l i = D i − C i
(6.1)
(wenn l i = 0 ist, dann muss J i sofort ausgeführt werden, nachdem er ausführungsbereit ist),
6 Abbildung von Anwendungen
auszuführen. Jede einzelne Task bezeichnen wir als τ i und die Menge aller Tasks als
τ = {τ 1 , ..., τ n }.
Definition 6.1: Jede Ausführung einer Task heißt ein Job (siehe auch Definition
4.4). Zu jeder Task τ i gehört eine Menge J(τ i ) von Jobs. Aufgrund der wiederholten
Ausführungen ist die Menge der Jobs von Task τ i möglicherweise nicht endlich.
Definition 6.2: Tasks τ i , die alle T Zeiteinheiten ausführungsbereit werden, heißen
periodische Tasks mit der Periode T.
Definition 6.3: Eine Task τ i heißt sporadisch, wenn es eine untere Schranke für den
Abstand der Zeitpunkte gibt, zu denen die Task ausführungsbereit wird. Für jede
sporadische Task τ i nennen wir diese Schranke auch T i .
Diese Schranke ist wichtig: ohne eine solche Schranke könnten die Ankunftskurven
für jedes ∆ unbeschränkt werden. Es wäre dann nicht möglich, für eine beschränkte
Menge an Ressourcen ein Schedule zu finden.
Definition 6.4: Tasks, die weder periodisch noch sporadisch sind, heißen aperiodisch.
Das Konzept der Hyperperioden ist für periodische und sporadische Task-Systeme
nützlich:
Definition 6.5: Sei τ ein periodisches oder sporadisches Task-System. Seine Hyperperiode ist definiert als das kleinste gemeinsame Vielfache (KGV) der Perioden
der einzelnen Tasks.
Wenn für eine Menge von Tasks für eine Hyperperiode ein Schedule existiert, dann
existiert es aufgrund der wiederholten identischen Scheduling-Aufgaben auch für
alle Hyperperioden.
6.1.2 Typen von Scheduling-Problemen
Im verbleibenden Teil dieses Kapitels wird die nachfolgende Notation für Jobs
benutzt: Sei J = {J i } eine Menge von Jobs. Sei ferner (siehe Abb. 6.2):
• r i der Zeitpunkt, an dem J i ausführungsbereit wird (engl. release time),
• C i die größtmögliche Ausführungszeit (engl. Worst Case Execution Time
(WCET)) von J i ,
• d i die (absolute) Deadline von J i ,
• D i die relative Deadline, d.h. die Zeit zwischen r i und der Zeit, zu der J i seine
Ausführung beendet haben soll (D i = d i − r i ),
• l i der Schlupf (engl. laxity oder slack), definiert als
l i = D i − C i
(6.1)
(wenn l i = 0 ist, dann muss J i sofort ausgeführt werden, nachdem er ausführungsbereit ist),