6.3 Scheduling für unabhängige Jobs auf identischen Multiprozessoren
349
Sortiere die Task-Menge nach nicht-aufsteigenden Aussastungen u i = C i / T i ;
/* Annahme: Task-Menge wird entsprechend der Sortierung neu nummeriert; */
for (mt=0; mt ≤ m; mt++) K[mt] =1;
/* initiaaisiere die Kapazität */
for (i=1; i≤n; i++) {
/* für jede Task */
for (mt=1; (u i >K[mt]) and (mt≤m); mt++); /* ausreichend Kapazität? */
if (mt > m) mt=0;
/* keine Lösung, wähhe Index 0 */
a[i]=mt;
/* Gib Prozessorzuordnung im Array zurück */
K[mt]=K[mt]-u i ;
/* Aktuaaisiere verbbeibende Kapazität */
}
Der heuristische Algorithmus ist sicherlich nicht optimal. Wir können uns fragen:
wie weit sind wir vom Optimum entfernt? Viele Publikationen diskutieren obere
Schranken für die Anzahl von zusätzlichen Prozessoren, die im Vergleich mit der
minimalen Anzahl von Prozessoren beim optimalen bin packing benötigt werden.
Die Publikation von Dosa [136] ist ein Beispiel dafür. Für Echtzeitsysteme ist eine
andere Frage relevant: Gibt für eine gegebene Anzahl von Prozessoren eine obere
Schranke für die Auslastung, bis zu der ein Schedule garantiert ist? Eine solche
Schranke wurde von Lopez et al. [356] bewiesen:
Theorem 6.6: Jeder RA-Algorithmus hat eine Auslastungsschranke nicht kleiner als
U B1 (U max ) = m − (m − 1)U max
(6.19)
Beweis: Wenn eine Task mit einer Auslastung u i nicht zugeordnet werden kann,
dann muss jeder Prozessor bereits Tasks so zugeordnet bekommen haben, dass seine
Auslastung (1 − u i ) übersteigt. Die Gesamtauslastung über alle zugeordneten Tasks
und τ i einschließend muss dann größer sein als
m(1 − u i ) + u i = m − (m − 1)u i
(6.20)
≥ m − (m − 1)U max
(6.21)
Diese Bedingung muss erfüllt sein, damit kein Schedule möglich ist.
⊓ ⊔
Weiterhin definieren wir β als
β =
1
U max
(6.22)
β ist eine untere Schranke für die Anzahl von Tasks, die wir auf einem einzelnen Prozessor ausführen können. Wir nehmen an, dass auf jedem Prozessor EDF als lokales
Scheduling-Verfahren genutzt wird. Lopez et al. zeigten das folgende Theorem:
Theorem 6.7: Kein Zuordnungsalgorithmus kann eine Auslastungsschranke haben,
die größer ist als
U B2 (β) =
βm + 1
β + 1
(6.23)
349
Sortiere die Task-Menge nach nicht-aufsteigenden Aussastungen u i = C i / T i ;
/* Annahme: Task-Menge wird entsprechend der Sortierung neu nummeriert; */
for (mt=0; mt ≤ m; mt++) K[mt] =1;
/* initiaaisiere die Kapazität */
for (i=1; i≤n; i++) {
/* für jede Task */
for (mt=1; (u i >K[mt]) and (mt≤m); mt++); /* ausreichend Kapazität? */
if (mt > m) mt=0;
/* keine Lösung, wähhe Index 0 */
a[i]=mt;
/* Gib Prozessorzuordnung im Array zurück */
K[mt]=K[mt]-u i ;
/* Aktuaaisiere verbbeibende Kapazität */
}
Der heuristische Algorithmus ist sicherlich nicht optimal. Wir können uns fragen:
wie weit sind wir vom Optimum entfernt? Viele Publikationen diskutieren obere
Schranken für die Anzahl von zusätzlichen Prozessoren, die im Vergleich mit der
minimalen Anzahl von Prozessoren beim optimalen bin packing benötigt werden.
Die Publikation von Dosa [136] ist ein Beispiel dafür. Für Echtzeitsysteme ist eine
andere Frage relevant: Gibt für eine gegebene Anzahl von Prozessoren eine obere
Schranke für die Auslastung, bis zu der ein Schedule garantiert ist? Eine solche
Schranke wurde von Lopez et al. [356] bewiesen:
Theorem 6.6: Jeder RA-Algorithmus hat eine Auslastungsschranke nicht kleiner als
U B1 (U max ) = m − (m − 1)U max
(6.19)
Beweis: Wenn eine Task mit einer Auslastung u i nicht zugeordnet werden kann,
dann muss jeder Prozessor bereits Tasks so zugeordnet bekommen haben, dass seine
Auslastung (1 − u i ) übersteigt. Die Gesamtauslastung über alle zugeordneten Tasks
und τ i einschließend muss dann größer sein als
m(1 − u i ) + u i = m − (m − 1)u i
(6.20)
≥ m − (m − 1)U max
(6.21)
Diese Bedingung muss erfüllt sein, damit kein Schedule möglich ist.
⊓ ⊔
Weiterhin definieren wir β als
β =
1
U max
(6.22)
β ist eine untere Schranke für die Anzahl von Tasks, die wir auf einem einzelnen Prozessor ausführen können. Wir nehmen an, dass auf jedem Prozessor EDF als lokales
Scheduling-Verfahren genutzt wird. Lopez et al. zeigten das folgende Theorem:
Theorem 6.7: Kein Zuordnungsalgorithmus kann eine Auslastungsschranke haben,
die größer ist als
U B2 (β) =
βm + 1
β + 1
(6.23)