Betriebssysteme 1, Wintersemester 2005/2006

Aktuelles

• Die erste Vorlesung am 20.10.2005 findet nicht im MZH 1400, sondern im GW1 B0100 statt.
• Eine Newsgroup ist eingerichtet: fb3/lv/bs1

Auf dieser Seite werden während des Semesters weiterführende Informationen sowie die jeweiligen Aufgabenzettel bereitgestellt. Wir bemühen uns, die Seite so aktuell wie möglich zu halten.

• Überblick
• Veranstaltungsinhalte
• Literatur
• Aufgabenblätter
• Scheine
• CSP
• FDR

Überblick

Die Bücher [1] und [6] sind die wichtigsten Grundlagen der Vorlesung. Die Standardthemen

• Prozesse, Threads und Kommunikationsmechanismen
• Speicherverwaltung
• Dateisysteme
• I/O
• Betriebsmittelvergabe, Synchronisation
• Zuverlässigkeitsmechanismen: Safety, Security, Availability, Reliability

werden für lokale und verteilte Betriebssysteme behandelt.

Die Übungen vertiefen den Vorlesungsstoff durch praktische Anwendung der beschriebenen Konzepte bei der Shell- und Systemprogrammierung unter UNIX. Zur Lösung der praktischen Aufgaben muß man C oder C++ programmieren können. Ein Spezialthema, welches in der zweiten Vorlesung noch weiter vertieft wird, behandelt Beschreibungsmethoden für komplexe Sachverhalte in Betriebssystemen: Die Wirkung einiger Betriebssystemmechanismen (z.B. Security-Funktionen, Real-Time Scheduler) ist so komplex, daß sie mit informalen Sprachmitteln kaum mehr präzise spezifiziert werden kann. Daher sind formale Sprachen erforderlich, um eine eindeutige Beschreibungsweise und eine systematische Verifikation der Korrektheit der Mechanismen zu ermöglichen.

Ein didaktischer Grundgedanke, welcher (hoffentlich ;-) in den Vorlesungen sichtbar wird, besteht im Herausarbeiten von Konzepten oder Paradigmen, die hinter den zur Zeit in Betriebssystemen implementierten Mechanismen stehen. Ich bin mir ziemlich sicher, daß Wissen über die ``bösartigen Details" heutiger Betriebssysteme bereits sehr bald völlig wertlos sein wird und daher nur zur kurzfristigen (kurzsichtigen?) Lösung der Entwicklungsaufgaben im Software-Tagesgeschäft taugt. Verständnis von Konzepten und Paradigmen stellt dagegen einen ``bleibenden" Wert dar, da es uns hilft, neue Technologien effizienter auszunutzen bzw. ihre Eignung für eine Problemstellung erst zur erkennen.

Veranstaltungsinhalte

• Session 0: Überblick
• Session 1: Prozesse, Threads und Kommunikationsmechanismen
• Session 2: CSP
• Session 3: Threads
• Session 4: Virtueller Speicher
• Session 5: Scheduling
• Session 6: Security

Session 0: Überblick über Betriebssysteme

Vorlesung

• Motivation für Betriebssystem-Verwendung (Abstraktion, Wiederverwendung, Dependability (Safety, Security, Availability, Reliability)
• Das Betriebssystemen als Virtuelle Maschine zwischen Applikation und Hardware
• Das Application Program Interface (API) dient der Abstraktion von Betriebsmitteln und Systemverhalten
• Die "klassischen" Hauptthemen:
  • Prozesse - Threads - Scheduling - Inter-Prozesskommunikation (IPC)
  • Memory Management
  • Input/Output
  • Dateisysteme
  • Verteilte Kommunikation
  • Graphische Benutzerschnittstellen: Bei Unix eine Serviceschicht über dem eigentlichen Betriebssystem - bei Windows ein Bestandteil des Betriebssystems selbst
  • Dependability (Safety, Security, Availability, Reliability)
• Die zur Zeit besonders aktuellen und teilweise neuen Hauptthemen:
  • Linux als Alternative zu Windows, Solaris, HP-UX, IRIX etc.
  • Multimedia-Subsysteme
  • Echtzeit-Betriebssysteme für Steuerungsanwendungen (Mobile Kommunikation, Luftfahrt, Raumfahrt, Automobiltechnik, Bahn, Prozessautomatisierung, ...)
  • Echtzeit-Betriebssysteme für Multi-Media Anwendungen, Low-Latency Kernel
  • Echtzeit-Betriebssysteme auf Standard PC Architekturen: Mehrprozessor PCs und PC Cluster
  • Betriebssystemunterstützung für eng gekoppelte Mehrprozessorsysteme: Scheduling in Mehr-CPU Systemen, Hyper Threading
  • Kommunikationsbusse: FireWire (IEEE1394), USB2, Myrinet, Reflective Memory Techniken
  • Web- und File-Browser als Bestandteil des Betriebssystems oder als übergeordnete Serviceschicht ?

Literatur

• [1]
• [2]
• http://www.intel.com/technology/hyperthread

Session 1: Prozesse, Threads und Kommunikationsmechanismen

Vorlesung und Übung

• Prozesskommunikation
  • mit Betriebssystem-Beteiligung: Pipes, Shared Memory, Sockets, Message Queues, WIN32-Messages, (Unix-)Signale, Semaphoren
  • ohne Betriebssystem-Beteiligung: Ringpuffer - globale Variablen für die Thread-Kommunikation innerhalb eines Prozesses
• Prozesse: Ablauf im vor anderen Prozessen geschützten Kontext
• Threads: Ablauf im selben Prozesskontext
  • Light Weight Processes (LWPs): Threads mit Kernel Scheduling
  • User Threads: Threads mit vom Kernel unabhängigem Scheduling (Scheduling im User Space)
  • Kernel Threads: Threads im Betriebssystemkern selbst - zur parallelen Abwicklung von Diensten
• Kritische Abschnitte beim Zugriff auf Betriebsmittel
• Deadlocks, Livelocks, Starvation
• Sperrtechniken
  • Locks auf Objekten (z.B. Dateien)
  • Semaphoren und Mutexe
  • Interruptsperren
  • Prozesswechselsperre
  • Monitore
• Algorithmen für wechselseitigen Ausschluss mittels Busy-Waiting (Spin-Locks)
  • Strict Alternation
  • TSL-Verwendung
  • Peterson's Algorithmus
  • Dekker-Algorithmus
• Interprocess Communication-Probleme (z.B. Producer/Consumer-Problem, Reader/Writer, etc.)

Literatur und Beispiele

• [1], Kapitel 2, speziell 2.3
• [6], Kapitel 3, 4 und speziell 5
• Beispiel zur Addressierung von Integers auf SPARC-Architekturen zum Ausprobieren aus der Übung vom 1.11.2005
• Peterson's Algorithmus für zwei Prozesse aus der Vorlesung vom 10.11.2005
• Peterson's Algorithmus für N Prozesse aus der Übung vom 15.11.2005
• Producer/Consumer-Problem mit Semaphoren aus der Vorlesung vom 17.11.2005
• Hintergrundinformationen zu Shared Memory und Semaphoren aus der Übung vom 29.11.2005
• Beispiel Xmas zu Shared Memory und Semaphoren aus der Übung vom 29.11.2005
• Clint/Server aus der Vorlesung vom 1.12.2005

Session 2: CSP

Vorlesung und Übung

• Datentypen
• Prozesse, parametrisierte Prozesse, STOP, SKIP
• Operatoren

  ->   ;   |||   [| |]   []   |~|   \

• Kanäle, Events
• Rekursion und Prozessreferenzen
• Hiding
• CSP-Spezifikation von Algorithmen und Überprüfung erwarteter Eigenschaften
  • Konkrete Spezifikation (Implementierung): Modellierung des Algorithmus (Variablen als Prozesse,...)
  • Überprüfung der gewünschten Eigentschaften mit FDR (Tests auf Deadlock-Freiheit)
  • Überprüfung der Spezifikation mit Watchdogs
  • Abgleich der abstrakten und konkreten Spezifikation mit Trace Refinement

Literatur und Beispiele

• [9]
• [10]
• CSP-Seminar
• Strict Alternation in CSP aus der Übung vom 1.11.2005
• Ringbuffer in CSP aus der Vorlesung vom 3.11.2005
• Ringbuffer in CSP zweite Version aus der Vorlesung vom 3.11.2005
• Test-Set-Lock in CSP aus der Übung vom 8.11.2005
• Dekker-Algorithmus für zwei Prozesse in CSP aus der Übung vom 15.11.2005
• Dekker-Algorithmus für N Prozesse in CSP aus der Übung vom 15.11.2005
• Producer/Consumer-Problem in CSP aus der Übung vom 12.11.2005
• H20 - 1. Lösung (nicht korrekt) aus der Übung vom 12.11.2005
• H20 - 2. L&ouoml;sung (korrekt für einen O- und zwei H-Prozesse) aus der Übung vom 12.11.2005
• H20 - allgemeine Lösung

Session 3: Threads

Vorlesung

• Eigenschaften von Prozessen (Daten pro Prozess)
  • Resourcen: Adressraum, globale Variablen, offene Dateien, Kind-Prozesse, Signale/Signal-Handler
  • Programm-Faden (Thread): Programm-Counter, Register, Stack, Zustand
• Multithreading
• Lightweight Processes - User-Space Threads - Kernel-Space Threads
• POSIX-Threads (portable Schnittstelle, pthread-Bibliothek)
• pth-Bibliothek für User-Space Threads
• Thread-Safe-Funktionen
• User-Space Scheduling mit setjmp()/longjmp(()

Literatur und Beispiele

• [1], Kapitel 2, speziell 2.1 und 2.2
• [6], Kapitel 4
• Beispiel zu User-Space Scheduling mit setjmp()/longjmp() aus der Vorlesung vom 12.1.2006
• Beispiel 1 zu setjmp()/longjmp() aus der Übung vom 17.1.2006
• Beispiel 2 zu setjmp()/longjmp() aus der Übung vom 17.1.2006
• Beispiel 3 zu setjmp()/longjmp() aus der Übung vom 17.1.2006
• Beispiel 4 zu setjmp()/longjmp() aus der Übung vom 17.1.2006
• Beispiel 5 zu setjmp()/longjmp() aus der Übung vom 17.1.2006
• Beispiel zur pthread-Bibliothek aus der Übung vom 24.1.2006
• Beispiel Procuer/Consumer mit der pthread-Bibliothek aus der Übung vom 24.1.2006
• Beispiel Procuer/Consumer mit der pthread-Bibliothek aus der Übung vom 24.1.2006 (Verwendung von Broadcast bei Conditions)

Session 4: Virtueller Speicher

Vorlesung

• Swapping
• Paging: Seite (page), Seitenrahmen (page frame)
• physikalische Adresse, physikalischer Adressraum
• virtuelle Adresse, virtueller Adressraum
• MMU (Memory Management Unit)
• Seitenfehler (page fault)
• Seitentabelle(n)
• Seitenersetzungsalgorithmen:
  • Optimaler/Ökonomischer Algorithmus
  • Least Recently Used (LRU)
  • FIFO
  • Clock-Algorithmus

Literatur

• [1], Kapitel 4, speziell 4.3
• [6], Kapitel 7 und speziell 8

Session 5: Scheduling

Vorlesung

• Scheduling-Algorithmen: SCHED_OTHER, SCHED_RR, SCHED_FIFO
• Fairness
• präemptives / nicht-präemptives Scheduling
• statische /dynamische Prioritäten

Literatur

• [1], Kapitel 2, speziell 2.5
• [6], Kapitel 9 und 10

Session 6: Security

Vorlesung

• Subjekte und Objekte
• Schutzmatrix
• Schutzdomäne
• Rollen
• Access Control Lists (ACL)
• Buffer overflows

Literatur

• [1], Kapitel 9, speziell 9.6
• [6], Kapitel 15
• ACLs in Unix

Literatur

• [1] A. Tanenbaum: Modern Operating Systems, 2nd edition. Prentice Hall, 2001
  Hier werden die Hauptthemen dieses Semesters beschrieben. Die Erweiterungen zur ersten Ausgabe sind enorm.
  Wer unbedingt ein deutsches Buch lesen möchte, muss auf die deutsche Übersetzung der ersten Ausgabe zurückgreifen (siehe [2]).
• [2] A. Tanenbaum: Moderne Betriebssysteme, Hanser 1995
  (Die englische Fassung ist allerdings deutlich besser als die deutsche , da die Übersetzer offensichtlich viel besser Informatik als Deutsch und Englisch können.)
• [3] A. Tanenbaum, A. S. Woodhull: Operating Systems: Design and Implementation, 2nd edition. Prentice Hall, 1997.
  Dies ist eine erweitere Fassung des 1. Teils von [1] bzw. [2].
• [4] A. Tanenbaum: Distributed Operating Systems, Prentice Hall 1995.
  Dies ist eine erweiterte und aktualisierte Fassung des 2. Teils von [1] bzw. [2].
• [5] V. Toth: Programming Windows 98/NT Unleashed, Sams Publishing, 1998.
  Eine umfangreicher Überblick über die Systemprogrammierung u nter Windows 98 und Windows NT inkl. CD-ROM mit Beispielen.
• [6] W. Stallings: Betriebssysteme, Pearson Studium 2002.
  Diese Buch ist eine Alternative zu den Büchern von Tanenbaum. Es werden ebenfalls alle wichtigen Standardthemen, auch in bezug auf verteilte Systeme, behandelt.
  Achtung:Von diesem Buch gibt es nun auch eine günstige Studentenausgabe für 30€ statt 50€
• [7] U. Vahalia: Unix Internals - The New Frontiers, Prentice Hall 1996.
  Dieses Buch geht zu den einzelnen Themenbereichen mehr in die Tiefe als Tanenbaum oder Stallings: Wenn diese beiden Bücher nicht mehr genug Details verraten, lohnt es sich, einen Blick in den Vahalia zu werfen.
• [8] W.R. Stevens: Unix Network Programming, Prentice Hall 1990.
  Eine sehr detaillierte Einführung in die Systemprogrammierung unter UNIX anhand ausführlicher Beispiele. Insbesondere wird auf die Standard Internet Protokolle eingegangen sowie auf Interprozesskommunikationsmechanismen aber auch Remote Login sowie RPCs werden behandelt. Inzwischen gibt es eine überarbeitete zweibändige Ausgabe von 1998. Die Beispiele zu dem Buch liegen auch im Internet zum Download bereit und sind auch alleine häufig sehr hilfreich.
• [9] C.A.R. Hoare: Communicating Sequential Processes, Prentice Hall 1985.
  Das Standardwerk zu CSP, jetzt auch frei als elektronische Version erhältlich
• [10] A.W. Roscoe: The Practice and Theory of Concurrency, Prentice Hall 1998.
  Eine modernisierte Einführung in CSP und FDR.
• [11] J. Peleska: Formal Methods and the Development of Dependable Systems, Christian-Albrechts-Universität zu Kiel 1996.
  In dieser Habilitationsschrift befindet sich u. a. die Spezifikation der HP-UX Access Control Lists (S. 149ff). Eine Postscript-Version liegt zum Download lokal auf den Seiten der Universität Bremen.

Aufgabenblätter

Die Aufgabenblätter werden zwei- bis dreiwöchentlich erscheinen. Zur vollständigen Bearbeitung gehören Programm, Test und Dokumentation. Die erste Serie behandelt CSP, alle folgenden Serien werden in C programmiert. Die Aufgaben werden in den Übungen besprochen.

Die Abgabe der Aufgabenblätter erfolgt als Ausdruck in der Vorlesung und per E-Mail an Kirsten Berkenkötter (kirsten@tzi.de). Dazu gehören:

• Dokumentation (Latex)
• alle Quellcode-Dateien

Fragen zu den Übungsblättern oder auch anderen Dingen bitte an Kirsten Berkenkötter (kirsten@tzi.de).

Scheine

Für ein Fachgespräch ist die erfolgreiche Bearbeitung der Übungsblätter notwendig (60% über alle Zettel müssen erreicht werden). Das Fachgespräch wird mit der gesamten Gruppe durchgeführt und dauert etwa 30 Minuten.

Für die Modulprüfung gibt es keine Voraussetzung. Sie wird einzeln abgelegt und dauert etwa 20 Minuten.

Für beide Prüfungsarten gilt, dass sowohl der Stoff der Vorlesung als auch der Übungszettel präsent sein muss!

• Für Fachgespräche: Vordruck
• Für Modulprüfungen: Vordruck
  Ausserdem gibt es ein anderes Scheinformular (mit Protokoll auf der Rückseite, dass es nicht als pdf-Vorlage gibt. Dieses Formular liegt in der 7. Ebene aus und muss ebenfalls ausgefüllt mitgebracht werden!

CSP

• CSP Quick Reference [.ps]
• CSP-Seminar

FDR

• FDR-Aufruf
• FDR-Online-Help
• FDR-Manual [.ps, .pdf]