6.3 Scheduling für unabhängige Jobs auf identischen Multiprozessoren
357
Wir verpassen die Deadline für τ 3 , wenn wir die Periode von τ 1 auf T 1 = 4 verlängern
(siehe Abb. 6.25).
τ
τ
τ
16
14
12
10
t
8
6
4
2
0
1
2
3
Abb. 6.25 Mit G-RM erzeugtes Schedule verpasst Deadline bei t = 12
Dieses un-intuitive Ergebnis macht Beweise und Beispiele komplizierter als im
Einzelprozessor-Fall.
⊓ ⊔
Das Theorem 6.4 vom kritischen Zeitpunkt für Einzelprozessoren (siehe Seite 341)
gilt ebenfalls nicht für Multiprozessoren.
Für G-RM wurde die folgende Auslastungsgrenze bewiesen [94]:
Theorem 6.11: Ein periodisches oder sporadisches Task-System τ mit impliziten
Deadlines mit der Auslastung
U sum ≤
m
2
(1 − U max (τ)) + U max (τ)
(6.34)
kann mit G-RM erfolgreich auf einem homogenen m-Prozessorsystem (mit Einheitsgeschwindigkeit) eingeplant werden [50].
G-RM leidet ebenfalls unter dem Dhall-Effekt: In Gleichung (6.34) ist zu sehen,
dass U sum sich Null annähert, wenn U max gegen Eins geht. Wie G-EDF kann der
Algorithmus die Verfügbarkeit mehrerer Prozessoren nicht voll ausschöpfen.
Daher wurde der Algorithmus RM-US(ξ) mit einer Schwelle ξ vorgeschlagen,
wobei US für utilization threshold steht. Gegeben sei ein sporadisches Task-System
mit impliziten Deadlines, wobei die Tasks τ = {τ 1 , ...τ n } gemäß einer nicht-aufsteigenden Reihenfolge der Auslastungen u i sortiert seien. Bis zu (m − 1) Tasks mit
einer hohen Auslastung sollen auf bis zu m − 1 identischen Prozessoren eingeplant
werden. Die verbleibenden Prozessoren dienen der Ausführung der verbliebenen
Tasks. RM-US(ξ) arbeitet wie folgt:
for (i=1; i≤ m − 1; i++) {
if (u i > ξ) τ i wird die höchste Priorität zugewiesen
eese break;
}
/* die verbbeibenden Tasks werden gemäß G-RM eingeppant*/
Theorem 6.12: Für m Prozessoren mit Einheitsgeschwindigkeit hat RM-US(ξ) eine
Auslastungsschranke von mindestens
m 2
(3m−2) .
Das Theorem wurde von Andersson et al. [16] bewiesen. Für 3m ≫ 2 nähert sich
diese Schranke dem Wert
m
3 . Chen et al. [94] haben eine engere Schranke bewiesen.