Grundlagen der Betriebssysteme

Prof. Dr. Dieter Zöbel B.Sc. Inform. Dawid Zdzislaw Bijak

 

Aktuelles - Inhalte - Literatur - Aufgaben - Material -Organisation - Zielgruppe - Leistungsnachweis - Termine

Aktuelles

  • Die Veranstaltung Grundlagen der Betriebssysteme umfasst 3 Stunden Vorlesung (V) und eine Stunde Übung (Ü) pro Woche. Die Veranstaltung findet an folgenden Terminen statt:
    Mo., jeweils 10:15 - 11:45 in B016 (2V)
    Mi.,
    jeweils 10:15 - 11:45 in K107 (1V+1Ü)

  • Die erste Übungsveranstaltung zur Vorlesung ist am Mo., 25.10.2017, 10:00 - 11:00 Uhr in Raum K107:

  • Nachklausur wurde festgelegt! Siehe ganz unten!

Inhalte

Die Vorlesung Betriebssysteme führt in die Aufbauprinzipien, in die Basisfunktionen und in die wesentlichen Komponenten von Betriebssystemen ein. Am Ende steht eine Betrachtung verteilter Systeme und deren Anforderungen für den Aufbau entsprechender Betriebssysteme. Die Vorlesung gliedert sich im Wesentlichen in:

  1. Einführung
    Aufgaben, Prinzipien, Kategorien und Genealogien von Betriebssystemen

  2. Parallele Programmierung
    Parallelität, Konzepte der Synchronisierung, Systematik der Entwicklung paraller Programme

  3. Komponenten von Betriebssystemen
    Prozessverwaltung, Speicherverwaltung, Dateiverwaltung, Geräteverwaltung, Aufbauprinzipien von Betriebssystemen

  4. Verteilte Systeme
    Kommunikation und Synchronisierung mit Nachrichten, Ordnung der Ereignisse, Standardalgorithmen

Literatur

Buchliteratur zur Vorlesung

Empfehlungen bzgl. Begleitliteratur sind hier aufgelistet: Literaturempfehlungen

URLs

Die Vorlesung "Grundlagen der Betriebssysteme" basiert auf einem Skript in vier Kapiteln, entsprechend der Gliederung der Vorlesung:

Kapitel 1

Kapitel 2

Kapitel 3

Kapitel 4

Vorlesung

Hier finden sich Angaben über den Verlauf der 3-stündigen Vorlesung:

16.10.: Informationen zum Ablauf der Veranstaltung, Festlegung des Klausurtermins und der Voraussetzungen zur Teilnahme, grundlegende Konzeption der Veranstaltung, 1. Einführung, 1.1 Allgemeine Zielsetzungen, Versuch der Definion von Betriebssystemen, DIN 44300, Erläuterungen zu Betriebsmitteln und Prozessen, Beispiel: Betriebsmittel eines Smartphone, Schema der Soft- und Hardware-Architektur eines Fahrzeugs, Schnittstellen zum Betriebssystem, Rollen im Verhältnis zu einem Betriebssystem, 1.2 Epochen der Betriebssystem-Entwicklung,

18.10.: Epochen der Betriebssystementwicklung nach Tanenbaum: elektrische Röhre, Transistor, integrierte und hochintegrierte Schaltungen, Fortfürhung der Epochen über Tanenbaum hinaus: Rechner im WAN, allgegenwärtige Rechner, Ziele von Industrie 4.0, Meilensteine der Betriebsystem-Entwicklung: Mehrprogrammbetrieb, virtuelle Adressierung, Client-Server-Paradigma, virtuelle Maschinen, 1.2 Aufbauprinzipien von Betriebssystemen, Monolithischer Aufbau Schema eines Systemaufrufs, Beispiel: Systemaufruf unter Linux auf einem Intel-Prozessor, schalenorientierter Aufbau, Formen der Hierarchiebildung

23.10.: Virtuelles Aufbauschema, Vorteile der Virtualisierung, Beispiel: Klassische Virtualisierung mit IBM VM/370 und aktuelle Virtualisierung mit IBM z/VM, Mikrokern-basierter Aufbau, Definition zum Begriff des Betriebssystemkerns, Bedeutung der Interprozesskommunikation (IPC), Beispiel: Mikrokern-Architektur und Interprozesskommunikation unter dem Betriebssystem QNX, 1.4 Einsatzbreite von Betriebssystemen, Betriebsarten, Entwicklungsformen von Echtzeitbetriebssystemen, Standardisierungen Beispiel: POSIX, Beispiel Qt, Mobile Betriebssysteme, 1.5 Genealogie wichtiger Betriebssysteme, Beispiel: Windows-Betriebssysteme

30.10: Beispiel: Unix-artige Betriebssysteme, 2. Parallelität und Synchronisierung, 2.1 Parallele Prozesse, parallelism and concurrency, Pseudo-Parallelität, Unterscheidung zwischen Prozesstyp, Prozessobjekt und Prozessausführung, Schema der Erzeugung schwergewichtiger Prozesse mittels fork-join-Konzept, schwergewichtige und leichtgewichtige Prozesse (threads), Beispiel: Erzeugung leichtgewichtiger Prozesse mit der POSIX pthread-Bibliothek, Synopsen wichtiger pthread-Funktionen, Schema der Erzeugung leichtgewichtiger Prozesse unter C++11

6.11.: Formen der Abbildung von Threads der Anwendung auf das Betriebssystem und die Hardware: N:1, 1:1 und N:M, der Aufruf pthread_setaffinity(), Programmiermodelle für parallele und verteilte Programmierung, Beispiel: Vektorparallelität für viele Prozessoren (insb. GPUs) mit CUDA, Parallelität auf Rechensystemen, Klassifizierung von Rechensystemen nach Flynn, UMA uns NUMA-Prinzip, Hyperthreading, Cache-Kohärenz, Verlust an Arbeitsleistung durch Prozessumschaltungen, 2.2 Parallelität und Synchronisierung, die Parallelanweisung, Beispiel: elementares Konsistenzproblem mit den Operationen x++ und x--, die atomare Anweisung

8.11. (Ü) Programmierung mit der C++(version11) thread-Klasse, Übergabe von Parametern und Ergebnissen, Erläuterungen zur Übungsaufgabe,
(V) Erläuterungen zur Cache-Kohärenz, Zustände des MESI-Protokolls, Überlegungen zu Menge der Ergebnisse bei parallelen Berechnungen

13.11.: Unterscheidung zwischen multicore- und manycore-Parallelismus, Das Erzeuger-Verbraucher-Problem, Invarianten zur Beschreibung der korrekten Funktion von Erzeuger-Verbraucher-Anwendungen, Aufgaben der Synchronisierung, Grundlegende Synchronisierungsoperationen: Verzögern (sich) und Anstoßen (andere), Definition kritischer Gebiete und der Methode des gegenseitigen Ausschlusses, kritische Gebiete beim Erzeuger-Verbraucher-Problem, 2.3 Systematische Entwicklung paralleler Programme, die Synchronisierungsanweisung, Entwicklung einer Lösung zum gegenseitigen Ausschluss, Gütekriterien für eine Lösung zum gegenseitigen Ausschluss

15.11.: (Ü) Erzeugung von Ordung der Berechnung durch kritische Gebiete, Methoden in C++11 zum gegenseitigen Ausschluss
(V) Fairness als Anforderung an den Scheduler zum Fortschreiten der Prozessausführung, starke und schwache Fairness, Beispiel: Operationen auf Listen mit Fehlern bei der parallelen Ausführung dieser Operationen

20.11.: 2.4 Deadlocks in der parallelen Programmierung, Beispiel: Konkurrierendes Öffnen zwei Dateien durch zwei Prozesse, die vier notwendigen und hinreichenden Bedingungen für das Zustandekommen eines Deadlock, graphische Darstellung eines Deadlock im PRG (process resource graph) und im PWG (process wait graph), Deadlocksituationen in verschiedenen Anwendungsbereichen,  der Banker's Algorithm mit Beispielen, Deadlockbehandlung durch Außerkraftsetzten einer der vier notwendigen und hinreichenden Bedingungen, Hierarchisierung von Betriebsmitteln

22.11.: (Ü) Verklemmungen bei der Benutzung verschiedener lock-Operationen unter der Programmiersprache C++11, Anwendung des Banker's Algorthmus

(V) Methoden der Deadlockvermeidung: Erkennung und Beseitigung, Vermeidung, Verhinderung, Vergleich der Methoden u.a. hinsichtlich Aufwand und Parallelität, 2.5 Elementare Methoden der Synchronisierung, Bedeutung der Dekkerschen Lösungen

27.11.: Einführung in die temporale Logik, Vergleich der Dekkerschen Lösungen und temporallogischen Gesichtspunkten, Gegenseitiger Ausschluss nach Peterson, Einführung in Petri-Netze, insbesondere Bedingungs-Ereignis-Netze (BE-Netze), Modellierung der Petersonchen Lösung mit Hilfe von BE-Netzen, Erzwingung von Atomarität durch Sperren von Interrupts, Unterstützung beim gegenseitigen Ausschluss durch die Hardware: der test and set-Befehl

29.11.: (Ü) Besprechung der letzten Übungsaufgabe, Verhinderung von Deadlocks durch Hierarchisierung von BM, Beispiel: Termination eines Programms abhängig vom Grad der Fairness, Einführung in die GoLang

4.12.: Spinlocks in Linux, 2.6 Fortgeschrittene Methoden der Synchronisierung, Vergleich der elementaren mit den fortgeschrittenen Methoden der Snchronisierung anhand von SPI und API, der abstrakte Datentyp Semaphor, Beispiel: Semaphore als Mutexe unter POSIX, Zustandsmodell für Anwenderprozesse, Implementierung von Semaphoren, zählende Semaphoren, Beispiel: das Erzeuger-Verbraucher-Problem mit Semaphoren, Semaphore zwischen schwergewichtigen Prozessen

6.12.: (Ü) Synchronisierung nach dem lock-free Ansatz, Bearbeitung von Listen mit Hilfe des CAS-Befehls (compare and swap),
Semaphore zwischen schwergewichtigen Prozessen, das Monitorkonzept, Monitorobjekte als kritische Gebiete mit Methoden und lokalen Daten, Trennung zwischen der Implementierung von Monitor(klassen) und deren Benutzung

11.12.: Synchronisierung im Monitor mit den Operationen WAIT und SIGNAL auf dem Datentyp Condition, neuer Zustand: passiv im Monitor, Vergleich der Monitor-Implementierungen bei verschiedenen Spachen und Schnittstellen (Modula2, Java, POSIX), unterschiedliche Monitorkonzepte SW (signal and wait), SC (signal and continue) und SU (signal and urgent wait), Monitore unter POSIX mittels Condition-Variabe, Monitore in Java, Erzeugung paralleler Prozesse in Java, Schnittstelle Runnable, Verwaltung von Threads durch JVM (Java Virtual Machine), Thread-Pools in Java

13.12.: (Ü) Besprechung der Übungsaufgaben, Beweis der Deadlockfreiheit durch Hierarchisierung der Betriebsmittel,
das synchomized-Attribut in Java, Zustandsmodell für Threads in Java, Speichermodelle für die parallele Programmierung, Beispiel: das volatile-Attribut in Java, Beispiel: atomare Variablen in Java, blockierende und nicht blockierende Synchronisierung (lock-free)

18.12.: 2.7 Paradigmen der parallelen Programmierung, Bedeutung des wissenschaftlichen Paradigmas, systematische Lösung des Leser-Schreiber-Problems anhand von Zustandsinvarianten, Überlegungen Deadlockfreiheit und zur Livelockfreiheit von Lösungen des Leser-Schreiber-Problems, das Fünf-Philosophen-Problem, Unmöglichkeit der Symmetrie einer Lösung des Fünf-Philosophen-Problems, das  Barriere-Problem

20.12.: (Ü) Lösung des Jungle-Bridge-Problems, Beispiele: Atomare Operationen unter Java
Zweiphasige Lösung des Barriere-Problems, Überlegungen zur Verfikation der Lösung, 3. Komponenten von Betriebssystemen, relevante Komponenten, 3.1 Prozessplanung und -verwaltung, Zustandsmodell für unterbrechbare Prozesse, Datenstrukturen für die Prozessverwaltung, dynamische und statische Prozessverwaltung

8.1.: Grundlegende Aufgaben des Scheduling, probabilistisches und deterministisches Scheduling, Beispiel: Scheduling-Strategien unter Windows, Strategien des Scheduling für nicht unterbrechbare und unterbrechbare Prozesse, Beispiel: Dynamic Priority Round Robin (DPRR), Scheduling in der Programmiersprache GO, Kernel-Level und User-Level Scheduling, Beispiel: Datenstrukturen und Verfahren beim Scheduling von Threads auf Prozessoren unter Linux

10.1.: (Ü) Schaffung von Ausführungsreihenfolgen von Anweisungen durch P- und V-Operationen,
Schedulingstrategie: work stealing, Beispiel: User-Level Scheduling in der Programmierspache GO, Einschub: CSP (communicating sequential processes)

15.1.: Einschub: 4.3 Verteilte Programmierung, Überblick über programmiertechnische Konstrukte der verteilten Programmierung, Parallelanweisung, synchrones Senden an einen Prozess oder synchrones Empfangen von eimen Prozess, Deadlocks bei der synchronen Nachrichtenübertragung, die bewachte Anweisung (guarded command) mit I- oder O-Guards, alternative Anweisung, Wiederholungsanweisung und deren Terminationseigenschaft, Beispiel: verteiltes Sortieren nach der Idee eines Bubble-Sort, Beispiel: Sortieren mit I- und O-Guards innerhalb einer alternativen Anweisung, Konzept der Kanäle (channel) bei der Programmiersprache GO, Beispiel: einfache Pipeline in GO

17.1.: (Ü) Diskussion von Lösungen zum Barrier-Problem, Vergelich der Laufzeit von vergleichbaren Java- und GO-Programmen mit Kanälen
Verwaltung von Kanälen im Laufzeitsystem von GO, Möglichkeiten des Zugriffs auf Kanäle in GO, Vergleich der Alternativen Anweisung in CSP mit der select-Anweisung in GO, Beispiel: Ein GO-Programm mit einem nicht entdeckten Deadlock

22.1.: 3.2 Speicherverwaltung, Aufgaben und Ziele der Speicherverwaltung, Gegenläufigkeit von Preis und Zugriffszeit bei Speichermedien, Strategien der Vergabe des Hauptspeichers, Partitionierung, Virtuelle Adressierung, Bedeutung der MMU (memory management unit), Beispiel: Virtuelle Adressräume bei Windows auf der Grundlage der 64-Bit Architektur, Segmentierung und Paging, Mehrstufigkeit des Speicherzugriffs, Beschleunigung der MMU durch einen TLB (translation look-aside buffer), Aktivierung der Seitenverwaltung, Effizienz der virtuellen Adressierung wegen der Lokalität und Gleichförmigkeit von Programmen, Seitenflattern (thrashing), Verzögerungseffekte beim Seitenfehler abhängig von der Zahl der Prozesse

24.1.: (Ü) Sortieralgorithmen auf den Basis von CSP, Umsetzung der Sortieralgorithmen in die Programmiersprache GO, Erzeugung von Seitenflattern (thrashing),
Schema der Seitenaustauschalgorithmen, der LRU-Algorithmus (least recently used), Hardware-technische Realisierung des LRU-Algorithmus, Prinzip des optimalen Seitenaustausches, Seitenfehlerwahrscheinlichkeit, das Arbeitsmengen Modell (working set), der PFF-Algorithmus (page-fault frequency)

29.1.: Beispiel: Working Set Strategien unter Windows (fetch policy, placement policy, replacement policy), Strategien der Speicherverwaltung eines Haufens (heap), Beispiel: first fit und andere sowie buddy system anhand eine Folge von Operationen zur Anlegen und Freigeben von Speicher, interne und externe Fragmentierung, Binden und Laden von Objektmoduln, 3.3 Datei und Geräteverwaltung, Dateien im weiteren und engeren Sinn, interne und externe Aufgaben der Dateiverwaltung, Geräteverwaltung, Beispiel: E/A-Operationen unter der Programmiersprache C sowie unter den Betriebssystemen UNIX und Windows, Beispiel: detaillierter Ablauf eine E/A-Operation mittels relevanter BS-Komponenten unter Windows

31.1.: (Ü) akkumulierte Speicherzugriffszeiten, Seitenaustauschalgorithmen,
Besprechung der Lehrevaluation der Vorlesung GdB,
Informationen zur Durchführung und zu den Fragestellungen der Klausur am 8.2.2018,
Einschub: Beispiel für die Verwaltung des Heap nach dem Buddy-System,
Bedeutung der Pufferung bei E/A-Operationen, Beispiel: besondere Puffer unter Linux: buffer cache, dentry cache und page cache, Organisation einer Festplatte, Beispiel: Barracuda XT mit 2TByte Speicherkapazität

5.2.: Beispiel: aktueller Kostenvergleich zwischen HDD- und SSD-Geräten, Analyse con Zugriffszeiten von HDDs mit besonderer Beachtung der Zeit für das Anfahren der Spuren durch die L/S-Köpfe (seek time) und der Rotations-Latenzzeit (latency time), Bewertung der Latenzzeiten bei den Strategien FCFS und SATF (shortest access time first), Bewertung der Zeit für das Anfahren der Spuren durch die L/S-Köpfe bei den Strategien FCFS, SSTF (shortest seek time first), SCAN, CSCAN und SCAN-EDF, E/A-Scheduling unter Linux mittele CFQ (complete fairness queueing), RAID-Systeme (redundant array of independent discs), Beweggründe für RAID, Grundkonzeptevon RAID: Spiegelung (mirroring) und Zerlegung (stripping), Bewertungskriterien für RAID-Systeme: Nutzdatenverhältnis, Zugriffszeiten und Zuverlässigkeit, Bewertung von RAID 0, RAID1 und RAID 0+1

7.2.: (Ü) Beispiel: Speicherverwaltung auch der Grundlage des Buddy-Systems, Beispiel: Synchronisierung und Nachrichtenübertragung anhand von Java- und Go-Programmen
Betrachtung und Bewertung der Klassen RAID 4 und RAID 6, Beispiel: Dateiserver des GHRKO: ein RAID 1+6-System

 

Übung

Zu Grundlagen der Betriebssysteme findet jeweils mittwochs eine 1-stündige Übungsveranstaltungen statt: 10:15 Uhr in Raum K107

Allgemein zugängliche Materialien zu Vorlesung und Übung findet man im SVN unter:
https://svn.uni-koblenz.de/agrt/gbs-wise1718/allgroups/assignments

Das Gruppenverzeichnis zur Abgabe der Übungsblätter setzt sich wie folgt zusammen:
https://svn.uni-koblenz.de/agrt/gbs-wise1718/allgroups/<GRUPPENNAME>

Die Übungsblätter sollen in Gruppen von 3-4 Personen bearbeitet werden. Mittels der Software TEAMS gibt es die Möglichkeit, sich zu Bearbeitungsgruppen zusammenzufinden:
https://ist.uni-koblenz.de/teams/de/user/registration

Fragen zur Übung können an Dawid Bijak gestellt werden.

Übungsblätter

 

1. Aufgabe: (ohne Punkte) Installation von VirtualBox und Ubuntu für die erste Übungsstunde am Mi., 25.10.2017, 10:15

1. Aufgabenblatt

2. Aufgabenblatt

3. Aufgabenblatt

4. Aufgabenblatt

5. Aufgabenblatt

6. Aufgabenblatt

7. Aufgabenblatt

8. Aufgabenblatt

 

Klausur oder mündliche Prüfung

Zur Veranstaltung wird am 09.02.2018, von 14:00-16:00 in Raum D028 eine Klausur angeboten.

Die Klausur ist mittlerweile korrigiert. Am 16.3.2018 haben Sie zwischen 11:00 und 12:00 die Möglichkeit zur Klausureinsicht in B126.

Zur Veranstaltung wird eine 2. Klausur (Nachklausur) angeboten am Freitag, 06.04.2018, von 14:00-16:00 in Raum D028.

 

Um einen Eindruck von der Art und Aufteilung von Klausuraufgaben zu gewinnen, kann die folgende Musterklausur dienen.