Betriebssysteme, Wintersemester 2013/2014

• Termine
• Überblick
• Veranstaltungsinhalte
• Übungszettel
• Leistungsnachweise
• Literatur

Termine

Ü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: Threads
• Session 3: Scheduling
• Session 4: Virtueller Speicher
• Session 5: Security

Session 1: Prozesse, Threads und Kommunikationsmechanismen

• Spinlocks
  • Vor- und Nachteile von Active-Wait Verfahren - das Problem der Prioritäteninversion
  • Strict Alternation Protocol
  • Petersons Algorithmus
  • Fischers Protocol
• Semaphoren
  • Producer- Consumer Problem mit Unix-Semaphoren und Unix-Shared Memory
  • Problem der Speisenden Philosophen mit pthreads und Unix-Semaphoren.
• Ringpuffer-Kommunikation
• Non-Blocking Write Protocol
• Wartegraphen zur Deadlockvermeidung
• Kommunikation über Sockets
  • Client/Server Beispiel
• Spezifikation von Synchronisations- und Kommunikationsmechanismen mit Timed Automata (Werkzeug UPPAAL):
  • UPPAAL Spezifikation Strict Alternation
  • UPPAAL Spezifikation Ringpuffer Kommunikation
  • UPPAAL Spezifikation Non-Blocking Write Protocol
  • UPPAAL Spezifikation des Producer- Consumer Problem
  • UPPAAL Spezifikation von Fischers Protokoll

Literatur und Beispiele

• Byzantine Agreement Protocol: [13]; [14], Abschnitt 7.2.3
• Informationen zum IP-Protokoll:
  • Aufbau eines IP Pakets
  • IP FAQ
• UPPAAL - editor, simulator and model checker for Timed Automata:
  • Installation instructions
  • Tutorial

Session 2: Threads

• 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)
• 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 zum User-Space-Scheduling
• Implementierung des (fast) universell fairen Schedulers mit User-Threads

Session 3: Scheduling

• Orthogonale Zielsetzungen von Scheduling-Algorithmen
• SMP - Symmetric multiprocessing
• Load-balancing
• Scheduling-Klassen im Linux-Kernel
• Scheduling-Policies 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
• [12], Kapitel 12

Session 4: Virtueller Speicher

• Swapping
• Paging: Seite (page), Seitenrahmen (page frame)
• physikalische Adresse, physikalischer Adressraum
• virtuelle Adresse, virtueller Adressraum
• MMU (Memory Management Unit)
• Seitenfehler (page fault)
• Seitentabelle(n), invertierte Seitentabelle

Literatur

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

Session 5: Security

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

Literatur

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

Übungszettel

Die Aufgabenblätter werden zwei- bis dreiwöchentlich erscheinen.

• Übungsblatt 1, Abgabe am 04.11.2013
• Übungsblatt 2, Abgabe am 18.11.2013
• Übungsblatt 3, Abgabe am 09.12.2013 (hierzu: Hinweise zur Aufgabe)
• Übungsblatt 4, Abgabe am 06.01.2014 (hierzu: IP, Internet Protocol, IP Fragmentation - Q&A)
• Übungsblatt 5, Abgabe am 23.01.2014

Leisungsnachweise

Die Kriterien für den Erwerb eines Leistungsnachweises werden in der ersten Vorlesung verhandelt.

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.
• [12] K.R. Apt, F.S. de Boer, E. Olderog: Verification of Sequential and Concurrent Programs, Springer-Verlag New York, Inc. 1991.
• [13] L. Lamport, R. Shostak, M. Pease: The Byzantine Generals Problem, ACM Trans. Program. Lang. Syst. 1982.
• [14] A. S. Tanenbaum, M. van Steen: Verteilte Systeme, Pearson Studium. 2008.