6.1 Problemdefinition
325
• s i die Zeit, zu der die Ausführung von J i startet,
• f i die Zeit, zu der die Ausführung von J i beendet wird (engl. finishing time).
In Abbildungen wie in Abb. 6.2 bedeuten nach oben zeigende Pfeile die Zeit, zu
der Jobs ausführungsbereit werden und nach unten zeigende Pfeile die Deadline der
Jobs.
ausführen
C i
d i
f i
s i
r
i
i
r
d i
i
C
l i
i
D
Abb. 6.2 Notation für Jobs
Klassifizieren werden wir Scheduling-Probleme im Folgenden gemäß der TripletNotation, die von Pinedo vorgestellt wurde [455] und die auf einer Notation basiert,
die ursprünglich von Graham, Lawler, Lenstra und Kan vorgeschlagen wurde [190].
Diese Notation nutzt das folgende Triplet:
(α| β|γ).
(6.2)
Das α-Feld
Das α-Feld beschreibt die Maschine, auf der Jobs ausgeführt werden sollen. Einfache
Scheduling-Algorithmen behandeln den Fall eines einzelnen Prozessors, wohingegen
komplexe Algorithmen auch Systeme mit mehreren Prozessoren behandeln können.
In diesem Buch betrachten wir die folgenden Werte für das α-Feld:
• Ein Wert von 1 zeigt einen einzelnen Prozessor an.
• Ein Wert Pm zeigt an, dass es m Prozessoren gibt, die parallel benutzt werden
können. Jeder Job kann mit derselben Ausführungszeit auf jedem der m Prozessoren ausgeführt werden. Man nennt die Prozessoren in diesem Fall identisch oder
homogen. Das β-Feld kann benutzt werden, um die möglichen Zuordnungen von
Jobs zu Prozessoren einzuschränken.
• Ein Wert von Qm bezeichnet parallele Prozessoren mit unterschiedlichen Performanzen (Rechenleistungen). Die Performanz jedes Prozessors wird durch einen
Skalierungsfaktor relativ zum langsamsten der Prozessoren angegeben. Alle Skalierungsfaktoren zusammen werden durch einen Vektor (s 1 , .., s m ) ausgedrückt,
wobei s k der Skalierungsfaktor für Prozessor π k ist. In diesem Fall heißen die
Prozessoren uniform. Das uniforme Prozessormodell ist stark vereinfacht, wir
werden uns kaum darauf beziehen.
• Ein Wert von Rm zeigt an, dass es m Prozessoren mit unterschiedlichen Ausführungszeiten gibt. Die Ausführungszeit von Job oder Task i auf Prozessor k ist
325
• s i die Zeit, zu der die Ausführung von J i startet,
• f i die Zeit, zu der die Ausführung von J i beendet wird (engl. finishing time).
In Abbildungen wie in Abb. 6.2 bedeuten nach oben zeigende Pfeile die Zeit, zu
der Jobs ausführungsbereit werden und nach unten zeigende Pfeile die Deadline der
Jobs.
ausführen
C i
d i
f i
s i
r
i
i
r
d i
i
C
l i
i
D
Abb. 6.2 Notation für Jobs
Klassifizieren werden wir Scheduling-Probleme im Folgenden gemäß der TripletNotation, die von Pinedo vorgestellt wurde [455] und die auf einer Notation basiert,
die ursprünglich von Graham, Lawler, Lenstra und Kan vorgeschlagen wurde [190].
Diese Notation nutzt das folgende Triplet:
(α| β|γ).
(6.2)
Das α-Feld
Das α-Feld beschreibt die Maschine, auf der Jobs ausgeführt werden sollen. Einfache
Scheduling-Algorithmen behandeln den Fall eines einzelnen Prozessors, wohingegen
komplexe Algorithmen auch Systeme mit mehreren Prozessoren behandeln können.
In diesem Buch betrachten wir die folgenden Werte für das α-Feld:
• Ein Wert von 1 zeigt einen einzelnen Prozessor an.
• Ein Wert Pm zeigt an, dass es m Prozessoren gibt, die parallel benutzt werden
können. Jeder Job kann mit derselben Ausführungszeit auf jedem der m Prozessoren ausgeführt werden. Man nennt die Prozessoren in diesem Fall identisch oder
homogen. Das β-Feld kann benutzt werden, um die möglichen Zuordnungen von
Jobs zu Prozessoren einzuschränken.
• Ein Wert von Qm bezeichnet parallele Prozessoren mit unterschiedlichen Performanzen (Rechenleistungen). Die Performanz jedes Prozessors wird durch einen
Skalierungsfaktor relativ zum langsamsten der Prozessoren angegeben. Alle Skalierungsfaktoren zusammen werden durch einen Vektor (s 1 , .., s m ) ausgedrückt,
wobei s k der Skalierungsfaktor für Prozessor π k ist. In diesem Fall heißen die
Prozessoren uniform. Das uniforme Prozessormodell ist stark vereinfacht, wir
werden uns kaum darauf beziehen.
• Ein Wert von Rm zeigt an, dass es m Prozessoren mit unterschiedlichen Ausführungszeiten gibt. Die Ausführungszeit von Job oder Task i auf Prozessor k ist