Skripte DHBW

Vorlesungsskripte aus dem DHBW-Studium

Zusammenfassung Betriebssysteme

geschrieben von Morten Terhart am 24.03.2018


Inhaltsverzeichnis

Einführung

Was ist ein Betriebssystem?

“Als Betriebssystem bezeichnet man die Software, die den Ablauf von Programmen auf der Hardware steuert und die vorhandenen Betriebsmittel verwaltet.”

Siehe dazu folgendes Schema:
Definition Betriebssystem
Abbildung 1: Einordnung des Betriebssystems in die Abstraktionsebenen eines Rechners

Anforderungen an ein Betriebssystem

Betriebsarten von Betriebssystem

  1. Klassifikation nach Art der Auftragsbearbeitung
    • Stapelverarbeitung
    • Interaktiver Betrieb
    • Echtzeitbetrieb
  2. Weitere Möglichkeit der Klassifikation
    • Einbenutzer- / Mehrbenutzerbetrieb
    • Einprogramm- / Mehrprogrammbetrieb
    • Einprozessor- / Mehrprozessorbetrieb

Aufgaben eines Betriebssystems

Dienste eines Betriebssystems

Einblick in UNIX

Komponenten von UNIX
Abbildung 2: Komponenten von UNIX (oben: Benutzerschnittstelle, unten: System- und Hardwareschicht und Kernel)

Unterbrechungen (Interrupts)

2 Arten der Unterbrechung:

Ablauf einer Unterbrechung:

Ablauf einer Unterbrechung
Abbildung 3: Durchführung einer Unterbrechungssequenz
PC = Program Counter

Prozesse

Definition

“Ein Prozess ist ein Programm während der Ausführung im Arbeitsspeicher einschließlich seiner Umgebung.”

Umgebung eines Prozessors

Verhalten eines Prozesses

Zustände eines Prozesses

Zustandsübergänge eines Prozesses
Abbildung 4: Zustandsübergänge eines Prozesses

Prozesszustände und Warteschlangen
Abbildung 5: Prozesszustände und Warteschlangen

Prozessverwaltung

Steuerung von Prozessen

Scheduling-Strategien

2 Arten von Strategien:

Moderne Betriebssysteme verwenden ausschließlich preemptive Strategien.

Non-preemptive Scheduling-Strategien

Preemptive Scheduling-Strategien

Prozess-Scheduling in UNIX

Prozessplanung unter UNIX
Abbildung 8: Prozessplanung unter UNIX

Prozesshierarchie

Threads und Prozesse

Kommunikation zwischen Prozessen

Prozesse müssen ständig miteinander kommunizieren, z.B. für den Aufbau von Pipelines (Übergabe der Ausgabe des vorherigen Prozesses an den nächsten Prozess).

Möglichkeiten der Prozesskommunikation

Eine sichere Prozesskommunikation bedarf einer geeigneten Prozesssynchronisation, um den gegenseitigen Ausschluss umzusetzen.

Problem: mehrere Prozesse greifen gleichzeitig auf eine gemeinsame Ressource zu (z.B. Speichervariable)

Code-Abschnitte, die nicht unterbrochen werden dürfen, weil sie bspw. eine Transaktion tätigen, bezeichnet man als kritischen Abschnitt. Daher dürfen sich mehrere Prozesse nicht gleichzeitig in ihren kritischen Abschnitten befinden.

Bedingungen für den gegenseitigen Ausschluss (mutual exclusion)

  1. Nur ein Prozess darf sich im kritischen Abschnitt befinden.
  2. Prozesse, die in den kritischen Abschnitt eintreten oder diesen verlassen, müssen die anderen wartenden Prozesse über dieses Ereignis informieren.
  3. Auch bei mehr als 2 Prozessen muss das Verfahren einwandfrei sein.
  4. Jeder Prozess soll gleiche Chancen auf den Eintritt in einen kritischen Abschnitt haben.
  5. Kein Prozess in einem kritischen Abschnitt darf andere blockieren.
  6. Kein Prozess soll unendlich lange warten müssen.

Unterbrechungssperre

Idee: Unterbrechungen (Interrupts) werden bei Ausführungen eines kritischen Abschnitts ignoriert / maskiert. Selbst das Betriebssystem kann den laufenden Prozess nicht anhalten.

Vorteile Nachteile
+ einfache Realisierung - Anwender muss Maskierung wieder aufheben (kann leicht vergessen werden)
- hohe Reaktionszeit bei eintreffenden E/A-Unterbrechungsanforderungen können zu Datenverlust führen
- funktioniert nicht bei Mehrprozessorbetrieb

Verwendung eines Semaphors

Definition: Ein Semaphor (DIJKSTRA, 1965) ist eine Variable SS, auf der die zwei folgenden ununterbrechenbaren Operationen P (Passieren) und V (Verlassen) definiert sind:

P(S) := [ while (S <= 0) { /* do nothing */ }; S = S - 1; ]
V(S) := [ S = S + 1; ]

Initialisierung mit S = 1.

Implementation:

int S = 1; // Zahl der verfügbaren Betriebsmittel
P(S);
// kritischer Abschnitt hier
V(S);

Nachteil: rechenintensive Warteschleife in P(S) (busy wait loop)

effizientere Implementation mit S als Objekt mit den Attributen ctr (Wert des Semaphors) und list (Liste wartender Prozesse):

P(S) := [ S.ctr = S.ctr – 1;
          if (S.ctr < 0) {
              put pid in S.list;
              sleep();
          }
        ]
V(S) := [ S.ctr = S.ctr + 1;
          if (S.ctr <= 0) {
              get pid from S.list;
              wakeUp(pid);
          }
        ]

Systemaufruf sleep() blockiert Prozess pid und verbraucht so keine CPU-Zeit mehr, bis er durch wakeUp(pid) wieder reaktiviert wird.

Erzeuger- / Verbraucher-Problem

1. Idee: Realisierung eines gegenseitigen Ausschlusses mit Semaphor mutex = 1
\rightarrow unsicher, da Deadlocks auftreten können

2. Idee: Verwendung weiteres Semaphors für

  1. die Anzahl belegter Speicherplätze used
  2. die Anzahl freier Speicherplätze free

Bewertung des Semaphor-Konzepts

Vorteile Nachteile
+ mächtiges Konzept - teils schwierige Suche nach korrekter Lösung
+ flexibel - Verklemmungen zwischen Prozessen ist möglich
+ vielseitig - unübersichtlich (P und V im Code verstreut)
+ einfache Realisierung - leichte Programmierfehler durch Vertauschungen

Kommunikation mittels Nachrichten

2 Kommunikationsroutinen:

Empfänger-Prozess blockiert, falls er keine Nachricht empfängt, und wartet auf eine Nachricht. Sender und Empfänger können sich auf demselben Rechner oder auf getrennten Rechnern befinden.

Der Nachrichtenkanal wird als unsicher angesehen:

  1. Empfänger bestätigt Empfang einer Nachricht.
  2. Falls Sender nach einer vorgegebenen Zeitspanne keine Empfangsbestätigung erhält, wiederholt er das Senden der Nachricht.
  3. Empfänger muss nun die wiederholte Nachricht empfangen, da auch die Bestätigung verlorengehen kann.

Verschiedene Arbeitsweisen:

Verklemmungen (Deadlocks)

Speicherverwaltung

Zu bewältigende Aufgaben

Die Speicherverwaltung ist die Komponente, die Prozessen einen Bereich im Hauptspeicher (Kachel) zuweist. Der Arbeitsspeicher eines Systems aus SS Worten wird eingeteilt in SK\frac{S}{K} Seiten aus jeweils K=2kK = 2\text{k} Worten (typisch 4 Kbyte). Das Betriebssystem wird beim Startvorgang durch das BIOS (Basic Input Output System) in die ersten Kacheln des Hauptspeichers geladen. Die Anwendungsprogramme finden in den übrigen Kacheln Platz.

Speicherpartitionierung und Fragmentierung

Ein Anwendungsprogramm benötigt einen zusammenhängenden Speicherbereich (u.U. eine Partition benachbarter Seiten). Durch die Speicherverwaltung werden nur ganze Seiten vergeben, was zu interner Fragmentierung führen kann (siehe Abbildung 9).

Beispiel einer internen Fragmentierung
Abbildung 9: Beispiel einer internen Fragmentierung

2 Arten der Speicheraufteilung:

Prozesseinordnungsalgorithmen

Ziel: Minimierung des Verschnitts, damit nicht mehr so viele kleine freie Bereiche entstehen

Da die Suche nach einer freien Partition über die Belegungstabelle sehr aufwendig ist, bedient man sich einer verketteten Freiliste, die alle freien Partitionen beinhaltet und das Zusammenführen benachbarter freier Bereiche zulässt.

Folgende Algorithmen suchen nach dem geringstmöglichen Verschnitt:

Swapping

Falls der Arbeitsspeicher als Einlagerungsressource für Prozesse nicht ausreicht, fängt das Betriebssystem an, ganze Prozesse auf die Festplatte auszulagern. Dies kostet viel Zeit und die Prozesse auf dem Massenspeicher verlangsamen sich bei einer Transferrate von 10 MB/s\le 10 \ \text{MB/s}. Swapping ist sehr ineffizient, da immer ganze Prozesse aus- und eingelagert werden müssen. Außerdem bietet sich eine Speichergefährdung bei fehlerhafter Adressierung nach Relokation eines Prozesses, wodurch dieser die Daten anderer Prozesse manipulieren könnte.

Der Adressraum

Begriff: Der Begriff Adressraum beschreibt die Menge an erreichbaren Adressen in einem bestimmten Speicher. Sie wird durch die Rechnerarchitektur vorgegeben.

Physischer Adressraum: ein durch Adressleitungen gebildeter Adressraum, referenziert den physikalischen Hauptspeicher, bildet die Prozessoradressen auf die Speicherbausteine und die E/A-Ports ab

Virtueller (logischer) Adressraum: Adressraum für Prozesse, Umrechung der virtuellen Adressen in physikalische Adressen durch Memory Management Unit (MMU) (siehe Abbildung 10)

Konvertierung einer virtuellen in eine physikalische Adresse
Abbildung 10: Konvertierung einer virtuellen in eine physikalische Adresse

Virtueller Speicher

Grundidee: Zuordnung von Speicherobjekten (Prozessdaten) zu Regionen von Adressräumen (siehe Abbildung 11)

Ziel: jedem Prozess wird ein vom Hauptspeicher unabhängiger logischer Adressraum bereitgestellt

Betriebssystem kümmert sich um

Anordnung des virtuellen Speichers
Abbildung 11: Anordnung des virtuellen Speichers

Adressabbildung

Kodierung der virtuellen Adresse
Abbildung 12: Kodierung der virtuellen Adresse

Die Seitentabelle

Ein Seitentabelleneintrag kann folgendermaßen aussehen:

Beispiel eines Seitentabelleneintrages
Abbildung 13: Beispiel eines Seitentabelleneintrages

Seitentabellenattribute:

Seitenwechselstrategien

Einlagerungsstrategien:

Auslagerungsstrategien:

Bewertung des virtuellen Speichers

Vorteile Nachteile
+ geringe E/A-Belastung - hoher Speicherbedarf für Seitentabellen
+ automatischer Speicherschutz: jeder Prozess kann nur auf seine eigenen Seiten zugreifen - hoher Implementierungsaufwand
+ beliebig große Prozesse ausführbar - hoher CPU-Bedarf für Seitenverwaltung, falls keine Hardware-Unterstützung
+ keine externe Fragmentierung
+ dynamischer Speicherplatz

Dateien und Dateisysteme

Problem: Größe vom Hauptspeicher ist begrenzt, Daten gehen verloren, sobald der Prozess beendet wird

Lösung: Sicherung der Daten auf dem permanenten Massenspeicher mit großer Kapazität

Betriebssystem muss bei Dateien auf dem Massenspeicher darauf achten, dass

Massenspeicher / Hintergrundspeicher

Clustering des Hintergrundspeichers
Abbildung 14: Clustering des Hintergrundspeichers

Datei-Konzept

Datei: Eine mit Namen versehene Sammlung zusammengehöriger Informationen

Verzeichniskonzept

Alle Dateien in einem Dateisystem werden durch optionale Partitionen auf der Festplatte und durch Verzeichnisse organisiert (siehe Abbildung 15).

Organisation von Dateien auf Festplatten
Abbildung 15: Organisation von Dateien auf Festplatten

Verzeichnisse bilden eine Struktur auf der Festplatte, unter der Dateien gespeichert werden können. In Verzeichnissen kann man

Verschiedene Varianten von Verzeichnissen

Operationen auf Dateisystemen

Implementierung auf Festplatten

Aufbau einer Festplatte
Abbildung 19: Aufbau einer Festplatte

Implementierung von Dateisystemen

Dateisysteme sind in Schichten realisiert:

Schichten
Anwendungsprogramme
logisches Dateisystem
Dateiorganisationsmodul
Basic-File-System
E/A-Kontrolle
Hardware

Segmente einer Festplatte
Abbildung 20: Segmente einer Festplatte

Allokationsstrategien vom Dateisystem

Ein Dateisystem kann zwischen verschiedenen Möglichkeiten wählen, Blöcke von Daten wie Dateien auf die Festplatte zu schreiben:

Zusammenhängende Belegung

Zusammenhängende Block-Allokation
Abbildung 21: Zusammenhängende Block-Allokation

Zugehörige Struktur des Verzeichnisses

Datei Start Länge
Name1 00 22
Name2 1414 33
Name3 1919 66
Name4 2828 44
Name6 66 22

Verkettete Belegung

Verkettete Block-Allokation
Abbildung 22: Verkettete Block-Allokation

Indizierte Belegung

Indizierte Block-Allokation
Abbildung 23: Indizierte Block-Allokation

Multi-Level-Indexblock

Schema des Muli-Level-Indexblocks
Abbildung 24: Schema des Multi-Level-Indexblocks

UNIX Inodes

Kombination aus

UNIX Inodes
Abbildung 25: UNIX Inodes

Vorteile Nachteile
+ schneller Zugriff für kleine Dateien - maximale Dateigröße ist begrenzt
+ keine externe Fragmentierung - interne Fragmentierung

Ein- und Ausgabekonzepte und Bussysteme

Zur Realisierung einer geeigneten Ein- / Ausgabe benötigt man

Strategien der Ein- / Ausgabe

Kopplung der E/A-Bausteine

E/A-Bausteine haben folgende Register:

Kommunikation zwischen CPU und E/A-Geräten

2 Möglichkeiten der Datenübertragung:

3 verschiedene Übertragungsprotokolle

Direct Memory Access (DMA)

Um die CPU nicht mit trivialen Aufgaben wie der Weiterleitung von langen Datenströmen an Ausgabebausteine zu belasten, wird ein zusätzlicher DMA-Baustein benutzt, der nach einer Initialisierung durch die CPU den Speichertransfer eigenmächtig durchführt. Damit werden häufige Aufgaben wie das Inkrementieren von Adressen, Zählen von Datenwörtern oder Abfragen des Status der E/A-Bausteine ausgelagert.

Ein DMA-Baustein besteht aus folgenden Komponenten:

Ein System mit DMA-Baustein kann folgendermaßen aussehen

Architektur eines Systems mit DMA-Baustein
Abbildung 29: Architektur eines Systems mit DMA-Baustein

Ablauf eines DMA-Transfers

CPU E/A-Baustein DMA-Baustein Hauptspeicher initialisiert initialisiert setzt TransferRQ fordert Bus an (BRQ) deaktiviert Bustreiber und setzt BGT signalisiert Beginn des Datentransfers speichert Daten von E/A gibt Bus wieder frei signalisiert Ende des Datentransfers CPU E/A-Baustein DMA-Baustein Hauptspeicher

Abbildung 30: Ablauf eines DMA-Transfers
TransferRQ = Transfer Request
BRQ = Bus Request
BGT = Bus Grant

E/A-Scheduling-Strategien