Seminar: On-line Scheduling

Im Sommersemester 1995 findet ein Hauptseminar über On-line Scheduling statt. Die Vorbesprechung mit Anmeldung dafür wird am Mittwoch, den 22.2.1995, um 15:15 Uhr im Raum S2225 durchgeführt. Die Vorträge finden jeweils donnerstags von 14:15 - 16:00 Uhr im Raum S2229 statt.

Folgende Themen werden behandelt:

Scheduling baum-geordneter Tasks
Anomalien bei List-scheduling
Verbessertes List-scheduling
Gewinnung von on-line- aus off-line-Algorithmen
On-line Scheduling auf verschiedenen Architekturen
On-line scheduling voneinander abhängiger Jobs
Scheduling parallelisierbarer Tasks
On-line Lastbalancierung
Scheduling von Tasks mit exponentiell verteilten Ausführungszeiten
Routing als Anwendung von on-line Lastbalancierung
Intervall-Scheduling
NP-vollständige Schedulingprobleme

Was ist Scheduling?

Allgemein beschäftigt man sich unter dem Begriff "Scheduling" mit der Lösung des Problems, eine Menge von Tasks so auf eine Menge paralleler Prozessoren zu verteilen, daß ein vorgegebenes Kriterium (etwa die Gesamtzeit für die Ausführung aller Tasks) optimiert wird. Dabei werden viele unterschiedliche Ausprägungen des Problems untersucht: Es gibt Algorithmen für zwei Prozessoren, für beliebig viele Prozessoren, für verschieden schnelle Prozessoren, etc. Die Tasks können als unabhängig voneinander vorausgesetzt werden, oder man kann eine partielle Ordnung unter ihnen annehmen (sodaß ein Task nicht ausgeführt werden darf, bevor alle seine Vorgänger beendet wurden). Zusätzlich können den Tasks noch Release-Times (frühestmöglicher Zeitpunkt für den Beginn der Ausführung eines Tasks) oder Deadlines (spätestmöglicher Zeitpunkt für die Beendigung eines Tasks) zugeordnet sein. Das Ziel eines Scheduling-Algorithmus muß nicht immer die Minimierung der Gesamtzeit für die Ausführung aller Tasks sein. Auch die Beendigung möglichst vieler Tasks vor ihrer Deadline oder die Minimierung der durchschnittlichen Zeit bis zur Beendigung eines Tasks werden als Optimierungs-Kriterien betrachtet. Bei Scheduling geht man üblicherweise davon aus, daß jeder Prozessor zu jedem Zeitpunkt nur einen Task ausführt. Andere Modelle, bei denen ein Prozessor auch mehrere Tasks gleichzeitig ausführen kann, werden unter dem Stichwort Lastbalancierung untersucht.

Worum geht es beim Seminar On-line Scheduling?

Das Seminar soll einen Überblick über größtenteils aktuelle Ergebnisse auf dem Gebiet des On-line Scheduling vermitteln. Bei On-line Scheduling wird im Unterschied zu Off-line Scheduling von der realistischen Annahme ausgegangen, daß nicht alle Daten über die Tasks (insbesondere die Ausführungszeiten) von vornherein bekannt sind. On-line Algorithmen werden dann in der Regel danach beurteilt, um welchen Faktor sie schlimmstenfalls schlechter sind als ein optimaler off-line Algorithmus (Analyse durch "competitive ratio"). Neben dem Scheduling von Tasks, die auf jeweils einem Prozessor laufen, wird (in drei Vorträgen) auch das Scheduling von "parallelisierbaren" Tasks untersucht. Ein parallelisierbarer Task ist ein Task, für dessen Ausführung auch mehrere Prozessoren verwendet werden können, wodurch er schneller beendet wird als auf einem Prozessor. Über die typischen Scheduling-Probleme hinausgehend werden dann noch Lastbalancierung und ein mit Scheduling verwandtes Routing-Problem betrachtet. Ein Vortrag über Intervall-Scheduling beschäftigt sich mit der Zuteilung einer exklusiven Ressource (z.B. Festplattenzugriff auf hardware-naher Ebene) an konkurrierende Tasks mit dem Ziel, eine möglichst große Auslastung der Ressource zu erreichen. Klassische Ergebnisse über optimale Algorithmen für Probleme, in denen die partielle Ordnung der Tasks Baumstruktur hat (Vortrag 1), über List-Scheduling (Vortrag 2) sowie über die NP-Vollständigkeit bestimmter Scheduling-Probleme (Vortrag 12) runden das Seminar ab.

Weitere Auskünfte erteilen Thomas Erlebach oder Klaus Kühnle

Thomas Erlebach, 1995-02-15