Wintersemester 2002/2003

Stiege: "Realzeitbetriebssysteme: Scheduling und Verteilung" (3V + 1Ü)

• Modulbeschreibung
• Vorlesung
• Übungen
• Literatur

Termine

Vorlesung	Dienstag	8 - 10	HS    A5 1-160
	Mittwoch	16 - 17	HS    A5 1-160
Übung	Mittwoch	17 - 18	HS    A5 1-160

Modulbeschreibung

Ziele des Moduls: Grundkenntnisse und Überblick der Theorie und Algorithmik von Planungs-
und Verteilungsverfahren. Realzeitfragen werden besonders berücksichtigt.


Zusammenfassung des Inhalts: Deterministische Planungsmethoden (job-shop scheduling).
Scheduling in Realzeit- und anderen Betriebssystemen. Verteilungs- und Zuweisungsprobleme
(assignment). Einführung in stochastische Modellierung.


Voraussetzungen: Grundstudium Informatik (Diplom) bzw die ersten beiden Jahre BSc Informatik


Zählt für Schwerpunktfach: Eingebettete Systeme und Mikrorobotik


Bereichswahl: Praktische Informatik, Theoretische Informatik


Zeitpunkt der Belegung: 4. Woche


Erreichbare ETCS-Punkte: 6


Zu erbringende Leistungen: Hausübungen und mündliche Prüfung


Kriterien zum Erreichen der Notenpunkte 0 - 100: Alle Hausaufgaben müssen abgegeben
und zu mindestens 40% erfolgreich bearbeitet werden. Falls das erfüllt ist, gehen die
Hausaufgaben mit 30%, die mündliche Prüfung mit 70% in die Endnote ein.
Andernfalls wird das Modul mit 0 Punkten bewertet.


Maximale Größe einer Übungsgruppe: 2

Vorlesung

Inhaltsverzeichnis
1. Grundbegriffe

2. Deterministische Planungsverfahren
2.1 Einführung
2.2 Optimale Vergabepläne für Zwei-Prozessorsysteme
2.3 Optimale Vergabepläne für Präzedenzbäume
2.4 Vergabeplanung unabhängiger Prozesse
2.5 Listenpläne
2.6 Vergabepläne mit Unterbrechungen
2.7 Minimale mittlere Verweilzeit

3. Realzeitscheduling
3.1 Planung mit festen Prioritätten - Ein einfaches Modell
3.1.1 Berechnungsmodell
3.1.2 Statische Planung
3.1.3 Planung mit Prioritäten
3.1.4 Einfache Analysemethoden
3.1.4.1 Notwendige Bedingungen
3.1.4.2 Eine hinreichende Bedinung
3.1.5. Exakte Analyse
3.1.5.1 Notwendige und hinreichende Bedinungen
3.1.5.2 Berechnung der Antwortzeiten

4. Stochastische Planungsverfahren
4 Stochastische Planungsverfahren
4.1 Einführung
4.1.1 Messen, Modellieren und Bewerten
4.1.2 Exkurs: Beispiele für stochastische Prozesse
4.2 Bedienmodelle
4.2.1 Größen in einem Bediensystem
4.2.2 Vorgehensweise bei Markovschen Bediensystemen
4.2.3 M/M/c - Systeme
4.2.4 M/M/1/K - Systeme

• Unterlagen zu Kapitel 1
  • Folien
• Unterlagen zu Kapitel 2
  • Folien
• Unterlagen zu Kapitel 3
  • Anmerkungen
• Unterlagen zu Kapitel 4
  • Zu 4 bis 4.2.1 siehe Unterlage04.01

    Zu 4.2.2 siehe Folien (noch nachzutragen)

    Zu 4.2.3 und 4.2.4 siehe Bedienfolien
• Unterlagen zu Kapitel 5

Übungen

• Übungsblätter
  • Übungsblatt 1
  • Übungsblatt 2
  • Übungsblatt 3
  • Übungsblatt 4
  • Übungsblatt 5
  • Übungsblatt 6
  • Übungsblatt 7
• Lösungen
  • Lösung su Übungsblatt 1

Literatur

• [Bokh87] Bokhari, Shahid H. Assignment Problems in Parallel and Distributed Computing. Kluwer Academic Publishers, 1987.
• [CoffD73] Coffmann, E. G., Jr. / Denning, P., Operating Systems Theory, Prentice-Hall, Inc., 1973
• [CoffG93] Coffman/Garey. Proof of the 4/3 Conjecture...
• [Jose96] Joseph, M., Real-time Systems: Specification, Verification and Analysis, Prentice Hall, 1996
• [Liu00] Liu, Jane W.S. Real-Time Systems. Prentice-Hall, 2000
• [Pine95] Pinedo. Scheduling
• [Stie01b] Stierand, Ingo. Ambrosia/MP - Ein Echtzeitbetriebssystem für eingebettete Mikroprozessorsysteme. Universität Oldenburg. Berichte aus dem Fachbereich Informatik 6/01

up