Schedulingtheo­rie

Die Vorlesung wird in diesem Sommersemester letztmalig angeboten!

Inhalt

Beim Entwurf von Betriebssystemen ist die Entscheidung, wann welchem Prozess wieviel Rechenzeit zugeteilt werden kann, von entscheidender Bedeutung. Das gilt bereits für die konventionellen Einsatzgebiete Stapelverarbeitung und interaktiver Betrieb, um so mehr aber für Echtzeitsysteme. Hier liegt auch seit Jahren international der Forschungsschwerpunkt, besonders beeinflusst durch die Ausweitung von Echtzeitanwendungen über dedizierte Systeme hinaus auf den gesamten Multimedia-Bereich und durch ein breit gefächertes Spektrum von QoS-Anforderungen. Dies äußert sich u.a. darin, dass einerseits traditionelle Scheduling-Techniken wie ratenmonotones Scheduling modifiziert wurden zu flexibleren, effizienteren Verfahren und dass andererseits eine Reihe von Protokollen entwickelt wurde, um dem Problem der Prioritätsinversion entgegenzuwirken.

Ziel dieser Vorlesung ist es, die Teilnehmer mit den grundlegenden Begriffen, Verfahren und Ergebnissen der Schedulingtheorie (überwiegend für 1-Prozessor-Systeme) vertraut zu machen. Zu den Schwerpunkten gehören eine Einführung in die Bedienungstheorie (Warteschlangentheorie) als einer wesentlichen Grundlage von Scheduling-Entscheidungen in konventionellen Betriebssystemen sowie der (tiefliegende) Beweis des Admission-Kriteriums von Liu/Layland. Die Vorlesung knüpft eng an das entsprechende Wissen aus der Grundvorlesung „Betriebssysteme“ an. Vorausgesetzt wird Aufgeschlossenheit gegenüber mathematischer Vorgehensweise, aber außer Grundkenntnissen in Stochastik sind keine speziellen Vorkenntnisse erforderlich.

Folien

• Einführung
• „Klassische“ Schedulingtheorie, basierend auf
  • deterministischen Modellen
  • probabilistischen Modellen

• Schedulingtheorie für Echtzeitsysteme

  • Grundlagen und Überblick
  • Ratenmonotones Scheduling
  • Scheduling für flexible Applikationen
    • Statistisches ratenmonotones Scheduling
    • Ungenaue Berechnungen (Imprecise Computations)
    • Quality-Assuring Scheduling
  • Einplanung nichtperiodischer Tasks
  • Konkurrierender Betriebsmittel-Zugriff
• Externspeicher-Scheduling

Übungen

• Teil 1: Kapitel 1 und 2
• Teil 2: Kapitel 3 bis 9