354
6 Abbildung von Anwendungen
∀i ∈ [1..m] : T i = 1, C i = 2ε, u i = 2ε
(6.30)
T m+1 = 1 + ε, C m+1 = 1, u m+1 =
1
1+ε
(6.31)
.........
ε
ε
1
1+
τ
τ m
1
....
m+1
τ
t
2
0
Abb. 6.22 Dhall-Effekt
Abb. 6.12 zeigt ein entsprechendes
Schedule. Anfangs werden nur Tasks
τ 1 , .., τ m ausgeführt. Die Ausführung von
Task τ m+1 startet erst, nachdem die ersten m Tasks ihre Ausführung beendet
haben. Task τ m+1 verpasst ihre Deadline. Die Anwesenheit einer einzigen Task
τ m+1 mit hoher Auslastung ist ausreichend, um eine Deadline bei t = 1 + ε
zu verpassen. Dies passiert, obwohl die
Auslastung der anderen Tasks sehr klein
ist. Tatsächlich kann die Auslastung für die Tasks τ 1 , ..τ m beliebig klein sein und wir
verpassen immer noch die Deadline.
∇
Dies motiviert uns, Varianten von Algorithmen zu nutzen, die Tasks mit einer
hohen Auslastung eine hohe Priorität zuweisen, unabhängig von der Deadline oder
der Periode.
Algorithmus fpEDF ist ein solcher Algorithmus. Wir nehmen an, dass ein sporadisches Task-System τ = {τ 1 , ...τ n } mit impliziten Deadlines gegeben ist und
dass Tasks nach nicht-aufsteigenden Task-Auslastungen u i sortiert sind. Unser Ziel
ist es, einen Ablaufplan (Schedule) für die Ausführung dieser Tasks auf m identischen Prozessoren zu entwickeln, wobei der Dhall-Effekt vermieden werden soll.
Der fpEDF-Algorithmus arbeitet wie folgt [38]:
for (i=1; i ≤ m − 1; i++){
if (u i >0.5) die Jobs von τ i erhaaten die höchste Priorität
/* Bei GGeichstand erfoogt eine beeiebige Auswahh */
eese break;
}
/* Verbbeibende Jobs erhaaten eine Priorität gemäß EDF. */
Mithin erhalten m − 1 Tasks mit der höchsten Auslastung die höchste Priorität,
wenn ihre Auslastung größer ist als 0,5.
Theorem 6.8: Algorithmus f pE DF hat eine Auslastungsschranke von mindestens
m+1
2 .
Nach dem folgenden Theorem ist dies die beste Schranke, die wir erwarten
können.
Theorem 6.9: Kein Scheduling-Algorithmus mit festen Job-Prioritäten für m Prozessoren hat eine Auslastungsschranke größer als
m+1
2 .
Der Beweis beider Theoreme kann bei Baruah [38] nachgelesen werden. Wie
im Fall von partitioniertem Scheduling sind stärkere Schranken möglich, wenn die
größte Auslastung bekannt ist.
6 Abbildung von Anwendungen
∀i ∈ [1..m] : T i = 1, C i = 2ε, u i = 2ε
(6.30)
T m+1 = 1 + ε, C m+1 = 1, u m+1 =
1
1+ε
(6.31)
.........
ε
ε
1
1+
τ
τ m
1
....
m+1
τ
t
2
0
Abb. 6.22 Dhall-Effekt
Abb. 6.12 zeigt ein entsprechendes
Schedule. Anfangs werden nur Tasks
τ 1 , .., τ m ausgeführt. Die Ausführung von
Task τ m+1 startet erst, nachdem die ersten m Tasks ihre Ausführung beendet
haben. Task τ m+1 verpasst ihre Deadline. Die Anwesenheit einer einzigen Task
τ m+1 mit hoher Auslastung ist ausreichend, um eine Deadline bei t = 1 + ε
zu verpassen. Dies passiert, obwohl die
Auslastung der anderen Tasks sehr klein
ist. Tatsächlich kann die Auslastung für die Tasks τ 1 , ..τ m beliebig klein sein und wir
verpassen immer noch die Deadline.
∇
Dies motiviert uns, Varianten von Algorithmen zu nutzen, die Tasks mit einer
hohen Auslastung eine hohe Priorität zuweisen, unabhängig von der Deadline oder
der Periode.
Algorithmus fpEDF ist ein solcher Algorithmus. Wir nehmen an, dass ein sporadisches Task-System τ = {τ 1 , ...τ n } mit impliziten Deadlines gegeben ist und
dass Tasks nach nicht-aufsteigenden Task-Auslastungen u i sortiert sind. Unser Ziel
ist es, einen Ablaufplan (Schedule) für die Ausführung dieser Tasks auf m identischen Prozessoren zu entwickeln, wobei der Dhall-Effekt vermieden werden soll.
Der fpEDF-Algorithmus arbeitet wie folgt [38]:
for (i=1; i ≤ m − 1; i++){
if (u i >0.5) die Jobs von τ i erhaaten die höchste Priorität
/* Bei GGeichstand erfoogt eine beeiebige Auswahh */
eese break;
}
/* Verbbeibende Jobs erhaaten eine Priorität gemäß EDF. */
Mithin erhalten m − 1 Tasks mit der höchsten Auslastung die höchste Priorität,
wenn ihre Auslastung größer ist als 0,5.
Theorem 6.8: Algorithmus f pE DF hat eine Auslastungsschranke von mindestens
m+1
2 .
Nach dem folgenden Theorem ist dies die beste Schranke, die wir erwarten
können.
Theorem 6.9: Kein Scheduling-Algorithmus mit festen Job-Prioritäten für m Prozessoren hat eine Auslastungsschranke größer als
m+1
2 .
Der Beweis beider Theoreme kann bei Baruah [38] nachgelesen werden. Wie
im Fall von partitioniertem Scheduling sind stärkere Schranken möglich, wenn die
größte Auslastung bekannt ist.