6.3 Scheduling für unabhängige Jobs auf identischen Multiprozessoren
347
oder sporadische Natur der Tasks nicht relevant ist, können wir auch eine Menge von
Jobs mit expliziten Deadlines d i betrachten.
Für Multiprozessoren ist es nicht ausreichend, zu entscheiden, wann Tasks oder
Jobs ausgeführt werden. Vielmehr müssen wir entscheiden, wann und wo wir diese
ausführen wollen.
Für m identische Prozessoren gibt es die folgenden notwendigen Schranken für
die Existenz eines Schedules:
∀i : u i ≤ 1
(6.16)
U sum ≤ m
(6.17)
6.3.1 Partitioniertes Scheduling
Unsere Darstellung in den nächsten Abschnitten basiert v.a. auf einem Buch von
Baruah et al. [38] sowie auf einem Übersichtspapier von Davis et al. [121] und
Folien von I. Puaut [461, 462]. Baruah et al. konzentrieren sich dabei auf sporadische
Task-Systeme. Dies wird zum Teil dadurch motiviert, dass sporadische Systeme – im
Gegensatz zu periodischen Task-Systemen – keine globale Zeitsynchronisation für
das Bereitstellen von Jobs benötigen. Es reicht aus, wenn wir mit einem Zeitgeber
sicherstellen, dass die minimalen Zeitabstände eingehalten werden.
Weiterhin beschränken wir uns zunächst auf partitioniertes Scheduling. Dies
bedeutet, dass jede Task einem bestimmten Prozessor zugeordnet ist. Die Verlagerung von Tasks (auf andere Prozessoren) ist nicht erlaubt. Partitioniertes Scheduling
bei synchronen Ankunftszeiten kann mit bin-packing realisiert werden. Bin-packing
[307] kann in einer auf das Scheduling angepassten Notation wie folgt beschrieben
werden:
Definition 6.14: Sei τ = {1, ..., n} eine Menge von Objekten, wobei jedes Objekt
i ∈ τ eine Größe c i ∈ (0, 1] besitzt. Sei π = {1, ...m} eine Menge von Behältern mit
der Kapazität 1. Das Problem, eine Zuordnung a : τ → π so zu finden, dass die
Anzahl nicht-leerer Behälter m ≤ n minimal ist und dass die Kapazität der Behälter
nicht überschritten wird, heißt bin packing-Problem.
Bin packing ist NP-hart [178]. Daher benötigen optimale Algorithmen wie der
von Korf [306] große Laufzeiten. Die Formalisierung des Scheduling-Problems als
bin packing-Problem zielt auf die Minimierung der Anzahl der Prozessoren m.
Für eine gegebene Anzahl m von Prozessoren ist es angemessener, Scheduling
für synchrone Ankunftszeiten als ein Rucksack-Problem (engl. knapsack problem)
zu modellieren, genauer gesagt, als ein 0/1-Multiples Knapsack-Problem (MKP).
Definition 6.15 (Martello [368]): Sei τ = {1, ..., n} eine Menge von n Objekten,
jedes mit einer Größe c i und einem Nutzen b i . Sei π eine Menge von m Rucksäcken,
jeder mit einer Kapazität κ k , mit (m ≤ n). Wir gehen davon aus, dass wir einen
Teil der Objekte den Rucksäcken so zuordnen können (a : τ → π), sodass die
Größenbeschränkungen eingehalten werden:
347
oder sporadische Natur der Tasks nicht relevant ist, können wir auch eine Menge von
Jobs mit expliziten Deadlines d i betrachten.
Für Multiprozessoren ist es nicht ausreichend, zu entscheiden, wann Tasks oder
Jobs ausgeführt werden. Vielmehr müssen wir entscheiden, wann und wo wir diese
ausführen wollen.
Für m identische Prozessoren gibt es die folgenden notwendigen Schranken für
die Existenz eines Schedules:
∀i : u i ≤ 1
(6.16)
U sum ≤ m
(6.17)
6.3.1 Partitioniertes Scheduling
Unsere Darstellung in den nächsten Abschnitten basiert v.a. auf einem Buch von
Baruah et al. [38] sowie auf einem Übersichtspapier von Davis et al. [121] und
Folien von I. Puaut [461, 462]. Baruah et al. konzentrieren sich dabei auf sporadische
Task-Systeme. Dies wird zum Teil dadurch motiviert, dass sporadische Systeme – im
Gegensatz zu periodischen Task-Systemen – keine globale Zeitsynchronisation für
das Bereitstellen von Jobs benötigen. Es reicht aus, wenn wir mit einem Zeitgeber
sicherstellen, dass die minimalen Zeitabstände eingehalten werden.
Weiterhin beschränken wir uns zunächst auf partitioniertes Scheduling. Dies
bedeutet, dass jede Task einem bestimmten Prozessor zugeordnet ist. Die Verlagerung von Tasks (auf andere Prozessoren) ist nicht erlaubt. Partitioniertes Scheduling
bei synchronen Ankunftszeiten kann mit bin-packing realisiert werden. Bin-packing
[307] kann in einer auf das Scheduling angepassten Notation wie folgt beschrieben
werden:
Definition 6.14: Sei τ = {1, ..., n} eine Menge von Objekten, wobei jedes Objekt
i ∈ τ eine Größe c i ∈ (0, 1] besitzt. Sei π = {1, ...m} eine Menge von Behältern mit
der Kapazität 1. Das Problem, eine Zuordnung a : τ → π so zu finden, dass die
Anzahl nicht-leerer Behälter m ≤ n minimal ist und dass die Kapazität der Behälter
nicht überschritten wird, heißt bin packing-Problem.
Bin packing ist NP-hart [178]. Daher benötigen optimale Algorithmen wie der
von Korf [306] große Laufzeiten. Die Formalisierung des Scheduling-Problems als
bin packing-Problem zielt auf die Minimierung der Anzahl der Prozessoren m.
Für eine gegebene Anzahl m von Prozessoren ist es angemessener, Scheduling
für synchrone Ankunftszeiten als ein Rucksack-Problem (engl. knapsack problem)
zu modellieren, genauer gesagt, als ein 0/1-Multiples Knapsack-Problem (MKP).
Definition 6.15 (Martello [368]): Sei τ = {1, ..., n} eine Menge von n Objekten,
jedes mit einer Größe c i und einem Nutzen b i . Sei π eine Menge von m Rucksäcken,
jeder mit einer Kapazität κ k , mit (m ≤ n). Wir gehen davon aus, dass wir einen
Teil der Objekte den Rucksäcken so zuordnen können (a : τ → π), sodass die
Größenbeschränkungen eingehalten werden: