6.6 Aufgaben
375
Es gibt zwei Ansätze für ein dynamisches Scheduling: ein vollständig dynamisches Scheduling (engl. on-the-fly mapping) und ein hybrides Scheduling, bei dem
Ergebnisse der Entwurfsraumexploration ausgenutzt werden.
Einen Überblick über 25 verschiedene Ansätze für ein vollständig dynamisches
Scheduling haben Singh et al. [493] veröffentlicht. Diese Art des Schedulings kommt
den Nicht-Echtzeitsystemen am nächsten.
Hybride Scheduling-Techniken benutzen Ergebnisse früherer Entwurfsraumexplorationen, um die o.a. Nachteile von dynamischen Techniken auszugleichen. Beispielsweise können wir Schedules für wahrscheinliche Laufzeitszenarien vorab berechnen und dann zur Laufzeit aufgrund des aktuellen Szenarios auswählen. Singh et
al. unterscheiden Verfahren mit mehreren Schedules, die für eine einzige Anwendung
vorab berechnet sind, Verfahren mit mehreren Schedules für mehrere Anwendungen
und Verfahren, welche die Zuverlässigkeit mit einbeziehen11. Die Autoren geben
eine Übersicht über 21 verschiedene Ansätze für die Abfolge von Analysen zur
Entwurfszeit und Entscheidungen zur Laufzeit.
Man könnte noch einen Schritt weiter gehen und Scheduling mit der Anwendung
integrieren. Beispielsweise hat Kotthaus [308] ein Verfahren zur mathematischen
Optimierung entwickelt, bei dem dies der Fall ist. In diesem Ansatz ist die Anzahl
der Berechnungen der Zielfunktion nicht fest, sondern hängt von dem Fortschritt der
parallelen Berechnungen auf einem Mehrkern-System ab. Eine ähnliche Integration
ist auch für andere Anwendungen möglich.
6.6 Aufgaben
Die folgenden Aufgaben sollten entweder zu Hause oder während einer Anwesenheitsphase nach dem flipped classroom-Konzept [376] bearbeitet werden:
6.1: Gegeben sei eine Menge von vier Jobs. Ankunftszeiten r i , Deadlines D i und
Rechenzeiten C i sind wie folgt:
• J 1 : r 1 =10, D 1 =18, C 1 =4
• J 2 : r 2 =0, D 2 =28, C 2 =12
• J 3 : r 3 =6, D 3 =17, C 3 =3
• J 4 : r 4 =3, D 4 =13, C 4 =6
Erzeugen sie eine graphische Darstellung der Schedules für diese Job-Menge unter Benutzung der Earliest Deadline First und der Least Laxity-(LL-)SchedulingAlgorithmen! Geben Sie beim LL-Scheduling für alle Jobs beim Kontextwechsel
den Schlupf an! Wird ein Job seine Deadline verpassen?
6.2: Gegeben sei eine Menge von sechs Tasks τ 1 bis τ 6 . Ihre Ausführungszeiten und
ihre Deadlines sind die folgenden:
• τ 1 : D 1 =15, C 1 =3
11 Wir haben hier eine etwas gröbere Unterteilung vorgenommen als Singh et al. selbst.
375
Es gibt zwei Ansätze für ein dynamisches Scheduling: ein vollständig dynamisches Scheduling (engl. on-the-fly mapping) und ein hybrides Scheduling, bei dem
Ergebnisse der Entwurfsraumexploration ausgenutzt werden.
Einen Überblick über 25 verschiedene Ansätze für ein vollständig dynamisches
Scheduling haben Singh et al. [493] veröffentlicht. Diese Art des Schedulings kommt
den Nicht-Echtzeitsystemen am nächsten.
Hybride Scheduling-Techniken benutzen Ergebnisse früherer Entwurfsraumexplorationen, um die o.a. Nachteile von dynamischen Techniken auszugleichen. Beispielsweise können wir Schedules für wahrscheinliche Laufzeitszenarien vorab berechnen und dann zur Laufzeit aufgrund des aktuellen Szenarios auswählen. Singh et
al. unterscheiden Verfahren mit mehreren Schedules, die für eine einzige Anwendung
vorab berechnet sind, Verfahren mit mehreren Schedules für mehrere Anwendungen
und Verfahren, welche die Zuverlässigkeit mit einbeziehen11. Die Autoren geben
eine Übersicht über 21 verschiedene Ansätze für die Abfolge von Analysen zur
Entwurfszeit und Entscheidungen zur Laufzeit.
Man könnte noch einen Schritt weiter gehen und Scheduling mit der Anwendung
integrieren. Beispielsweise hat Kotthaus [308] ein Verfahren zur mathematischen
Optimierung entwickelt, bei dem dies der Fall ist. In diesem Ansatz ist die Anzahl
der Berechnungen der Zielfunktion nicht fest, sondern hängt von dem Fortschritt der
parallelen Berechnungen auf einem Mehrkern-System ab. Eine ähnliche Integration
ist auch für andere Anwendungen möglich.
6.6 Aufgaben
Die folgenden Aufgaben sollten entweder zu Hause oder während einer Anwesenheitsphase nach dem flipped classroom-Konzept [376] bearbeitet werden:
6.1: Gegeben sei eine Menge von vier Jobs. Ankunftszeiten r i , Deadlines D i und
Rechenzeiten C i sind wie folgt:
• J 1 : r 1 =10, D 1 =18, C 1 =4
• J 2 : r 2 =0, D 2 =28, C 2 =12
• J 3 : r 3 =6, D 3 =17, C 3 =3
• J 4 : r 4 =3, D 4 =13, C 4 =6
Erzeugen sie eine graphische Darstellung der Schedules für diese Job-Menge unter Benutzung der Earliest Deadline First und der Least Laxity-(LL-)SchedulingAlgorithmen! Geben Sie beim LL-Scheduling für alle Jobs beim Kontextwechsel
den Schlupf an! Wird ein Job seine Deadline verpassen?
6.2: Gegeben sei eine Menge von sechs Tasks τ 1 bis τ 6 . Ihre Ausführungszeiten und
ihre Deadlines sind die folgenden:
• τ 1 : D 1 =15, C 1 =3
11 Wir haben hier eine etwas gröbere Unterteilung vorgenommen als Singh et al. selbst.