Betriebssysteme 1, SoSe2003, Übersicht

Auf dieser Seite werden während des Semesters weiterführende Informationen sowie die jeweiligen Aufgabenzettel bereitgestellt.

Eine Übersicht über Inhalte, Termine,... der Veranstaltung findet sich in unserer Liste der Lehrveranstaltungen.

Informationen:

• Überblick
• Veranstaltungsinhalte
• Literatur
• Aufgabenblätter
• Added Value
• CSP
• FDR
• Z Notation

Überblick

Im SS 03 ist das Buch [1] die wichtigste Grundlage 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: Scheduling
• Session 5: Speicherverwaltung
• Session 6: Benutzerdefinierte System-Calls unter Linux

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]
• http://www.intel.com/technology/hyperthread

Session 1: Prozesse, Threads und Kommunikationsmechanismen

Vorlesung

• 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
• 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
• Kritische Abschnitte beim Zugriff auf Betriebsmittel
• 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
  • Peterson's Algorithmus
  • Non-blocking Write Protocol
  • TSL-Verwendung
• Interprocess Communication-Probleme (z.B. Dining Philosophers-Problem, Producer/Consumer-Problem

Literatur

• [1], Kapitel 2, speziell 2.3
• Strict-Alternation aus der Vorlesung vom 5.5.2003
• Ringbuffer aus der Vorlesung vom 19.5.2003
• Consumer aus der Vorlesung vom 19.5.2003
• Producer aus der Vorlesung vom 19.5.2003
• Header für Consumer/Producer aus der Vorlesung vom 19.5.2003
• Alternating Bit Protokoll aus der Vorlesung vom 2.6.2003
• Client aus der Übung am 2.6.2003
• Server aus der Übung am 2.6.2003
• Koordinierung von Weihnachtsmann, Elfen und Rentieren mit Semaphoren aus der Übung vom 23.6.2003

Session 2: CSP

Vorlesung

• Prozesse, parametrisierte Prozesse, STOP, SKIP
• Operatoren

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

• Kanäle, Events
• 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

Literatur

• [9]
• [10]
• FDR-Online-Help, FDR-Manual [.ps] (Syntax ab S.47)
• CSP-Seminar
• Test-Set-Lock (Beispiel aus der Übung)
• Koordinierung von Weihnachtsmann, Elfen und Rentieren mit Semaphoren aus der Übung vom 23.6.2003

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)
• Thread-Safe-Funktionen

Literatur

• [1], Kapitel 2, speziell 2.1 und 2.2

Session 4: Scheduling

Vorlesung

• Scheduling-Algorithmen: SCHED_OTHER, SCHED_RR, SCHED_FIFO
• Fairness
• präemptives / nicht-präemptives Scheduling
• statische /dynamische Prioritäten
• Universell fairer Scheduler
• Scheduling allgemein: First-Come-First-Served, Shortest-Job-First, Round Robin, Shortest-Remaining-Time First, Fixed Priorities, Preemptive Fixed Priorities
• Linux-Scheduling im Kernel

Literatur

• [1], Kapitel 2, speziell 2.5
• Linux-Scheduling aus den Kernel-Datei

Session 5: Speicherverwaltung

Vorlesung

• Swapping
• Paging
• virtueller Speicher
• Memory Management Unit (MMU)
• virtuelle Adressen, physische Adressen
• Seiten, Seitenrahmen, Seitentabellen
• Seitenfehler
• Segementierung

Literatur

• [1], Kapitel 4

Session 6: Benutzerdefinierte System-Calls unter Linux

Vorlesung

• Software-Interrupt 0x80
• Kernel-Wrapper für System-Calls
• Eintragen des System-Calls in die System-Call Tabelle
• Eintragen der System-Call-Nummer

Literatur

• [1], Kapitel 1.6
• Linux-Kernel-Dateien

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.
  Hinweise und sonstige Links zu dem Buch
  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: Operating Systems - Internals and Design Principles, Prentice Hall 1998.
  Diese Buch ist eine Alternative zu den Büchern von Tanenbaum. Es werden ebenfalls alle wichtigen Standardthemen, auch in bezug auf verteilte Systeme, behandelt.
• [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.
• [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 d er HP-UX Access Control Lists (S. 149ff). Eine Postscript-Version liegt zum Download lokal auf den Seiten der Universität Bremen.
• [12] M. Spivey: The Z Notation - A Reference Manual, Prentice Hall 1992.
  Dieses Buch enthät eine kurze Einführung in die formale Sprache Z und beschreibt anschließend ihre Grundlagen in strukturierter Weise. Der Inhalt steht komplett im Internet als Postscript Version zur Verfügung.

Zu Spezialthemen, die über die beschriebenen Bereiche hinausgehen, wird ein Skriptum herausgegeben.

Aufgabenblätter

• Blatt 1: ps - pdf
  Achtung: Korrektur, eine Zeile im Quelltext vergesen!
  Achtung: Abgabe eine Woche später (19.5.)!
• Blatt 2: ps - pdf
  Achtung: Abgabe am 13.6.2003, Druckfehler auf dem Zettel
  
• Blatt 3: ps - pdf
  Achtung: Abgabe am 4.7.2003, Verlängerung der Bearbeitungszeit
  
• Blatt 4: ps - pdf
  Achtung: Aktualisierte Version vom 7.7.2003 online!

Added Value

Eine kleine Sammlung von Nützlichkeiten (CSP-Spezifikationen aus der Vorlesung,...) .... wird während des Semesters überarbeitet und erweitert.

Material aus den vergangenen Semestern

• Strict Alternation als CSP-Spezifikation (29.10./5.11.2001)
• Sperrvariable mit Bug (zum Üben des Umgangs mit FDR) (5.11.2001)
• Producer-Consumer-Problem - Lösung mit Semaphoren (5.11.2001)
• Producer-Comsumer-Problem - Lösung mit Ringbuffer (12.11.2001)
• Beispiel für mögliche Probleme mit CSP-Kanälen (UE 19.11.2001)
• Producer-Consumer-Problem in C - Lösung mit Semaphoren und Shared Memory (12./19.11.2001) producer_20011119.c , consumer_20011119.c , producer_consumer_20011119.h
• Posix-Threads (26.11.2001) pthread_example.cpp übersetzen mit

   g++ pthread_example.cpp -o pthread_example -lpthread 

• Signalhandler (26.11.2001) signals.cpp
• Folien zu Dependability (7.01.2002) dependability.ps (dies sind Folien 1-9 aus dem kompletten Foliensatz zu der Lehrveranstaltung Safety Critical Systems 1)
• CSP-Wiederholung (Folien vom 21.01.2002) csp-wiederholung-4.pdf
• Mirrored Disk Driver (zum Thema Fault Tolerance, Übung 28.01.2002) mirdd.csp
  ( Die fehlerhafte Spec am Ende der Vorlesung mirdd_wie_am_Ende_der_Uebung.csp-- doofe Syntax-Fehler, kann man aber finden. Tip: Keine Klammerfehler sondern "echte" Syntax-Fehler gleich an mehreren Stellen. )
• Betriebssystemaspekte - Eine Übersicht [.ps]
• Single Task System (STS) [.ps]
• Strict Alternation [.csp]
• Ringpuffer [.csp]
• Producer/Consumer Problem - Lösung mit Stack [.csp]
• Scheduler und Fairness [.ps]
• Doppelrechner-System [.ps]
• Access Control Lists (HP-UX-Funktionsumfang) [.ps]
• Active Replication [.ps]

CSP

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

FDR

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

Z Notation

• Z Glossary [.ps]