Betriebssysteme

• Systemsoftware zur Steuerung von Rechnern

• Verwaltung der Hardware eines Rechners

• Folie Erklärung: Das Betriebssystem ist das grundlegendste aller Systemprogramme, das alle Betriebsmittel des Rechensystems verwaltet und eine Basis liefert, auf der Anwendungsprogramme programmiert werden können.

Alle zuteilbaren und benutzbaren Hardware- und Software- Komponenten eines Rechensystems

Anwendungsprogramme zur unmittelbaren Lösung von Benutzerproblemen

Systemprogramme zur Verwaltung des Betriebs eines Rechners

Anwendungsprogramme

Systemprogramme

Hardware

Textverarbeitung

Spiele

Flugbuchungssystem

Anti-Blockier-System

Editoren

Compiler

Binder/Linker

Kommando-Interpreter

Betriebssystem

Maschinensprache

Prozessor(en), Speicher

physikalische Geräte

Benutzungsoberfläche

Dienstprogramme (Utilities)

zur Programmierung benutzte Bibliotheksschnittstellen

Betriebssystem-Dienstschnittstelle

Kommandointerpreter

Graphische Oberflächen

Editoren

Übersetzer (Compiler)

Binder (Linker)

Standardbibliotheken

spezielle Bibliotheken

enthält Systemaufrufe

d.h. "erweiterte Befehle" = Operationen zum Umgang mit den vom BS-Kern offerierten Abstraktionen

(Kernabstraktion)

Programme in Ausführung, damit verbunden Mechanismen zur Prozesssynchronisation und -kommunikation

(Kernabstraktion)

Damit verbunden Dateisysteme (file systems), Verzeichnisse (directories)

(Kernabstraktion)

Ein und Ausgabegeräte, wie Maus, Tastatur, Drucker, Bildschirm

Benutzungsschnittstellen

Bibliotheksschnittstelle

Systemaufrufschnittstelle

Standardhilfprogramme (Shell, Editor, Compiler)

Standardbibliothek (open, close, read, write, fork)

UNIX-Betriebssystem (Prozessverwaltung, Speicherverwaltung, Dateisystem, I/O)

Hardware (CPU, Speicher, Platten, Terminals)

Ja.

• Der Programmierer soll von der komplexen Hardware abgeschirmt werden mittels einer Softwareschicht

• Schnittstelle zum Programmierer aus einfachen Abstraktionen (z.B. Dateikonzept, Lesen und Schreiben von Blöcken)

• Diese Schnittstelle ist einfacher zu verstehen und langlebiger

Vermeidung von Wartezeiten für "teure" CPU während I/O-Vorgängen

• geordnete und kontrollierte Zuteilung der Betriebsmittel an die in Ausführung befindlichen Programme

• ermöglicht gemeinsame Benutzung “teurer“ hardware-Betriebsmittel

• Schutz aller Betriebsmittel vor unberechtigter Benutzung

• Process control subsystem

• File System

Nein

Jede Schicht abstrahiert von Restriktionen der darunterliegenden Schicht und nutzt deren Dienste

Eine Virtualisierung durch "Virtual Machine Monitor": virtuelle Maschinen als mehr oder weniger identische Kopien der unterliegenden Hardware

Auslagerung großer Teile eines Betriebssystem-Kerns in Benutzerprogramme (=lauffähig im Benutzermodus)

• Isolation einzelner “Systemteile“ gegeneinander (vermeidet Fehlerausbreitung)

• Erweiterbarkeit, Anpassungsfähigkeit und flexible Konfigurierbarkeit insbesondere für Verteilte Systeme

• Alle Systemfunktionen werden von nur einer OS-Komponente unterstützt

• Hauptsystemdaten und alle Funktionen können nur durch eine geeignete Schnittstelle zugegriffen werden

• Speicher-Management (einzige architekturabhängige Ausführeinheit)

• Prozess- und Thread-Management

• Sicherheit

• I/O

• Interprozesskommunikation

Thread-Scheduling

Trap-Handlers

Interrupts

Synchronization-Objekte

HAL isoliert das Betriebssystem von plattformspezifischen Hardware unterschieden -> Portierbarkeit

Einige der HW-Funktionen die HAL verwaltet:

• Spezielle System-Prozesse (Beispiele: Session-Manager, Authentifizierungssubsystem, DiensteManager, Anmeldeprozess)

• Dienstprozesse

• Environment-Subsysteme

• Benutzeranwendungen

• Vereinfacht die Aufführungeseinheit

  • Ermöglicht die Konstruktion einer Vielfalt von APIs

• Verbessert Zuverlässigkeit

  • Jeder Server läuft außerhalb der Kernels, geschützt von anderen Servern

• Stellt ein einheitliches Transportmittel bereit, dass Anwendungen via Remote Procedure Calls (RPCs) kommunizieren können

• Stellt Basis für verteiltes Rechnen

• Betriebssystem-Routinen können auf jedem verfügbaren Prozessor laufen

• Mehrere Threads der Ausführungseinheit innerhalb eines einzelnen Prozesses können simultan auf verschiedenen Prozessoren ausgeführt werden

• Server-Prozesse können mehrere Threads nutzen

• Teilen Daten und Ressourcen zwischen Prozessen

• Monolithische Struktur

• Hierarchie von Schichten

• Virtuelle Maschinen

• Client/Server-Struktur (Microkernel)

Ein Prozess ist ein sich in Ausführung befindliches Programm (einschlißlich seiner aktuellen Werte des Programmzählers, der Register, Speichervariablen, Stack)

• Ein Prozess besitzt einen privaten Adressraum

  • Menge von (virtuellen) Adressen, von Prozess zugreifbar Programm und Daten in Adressraum sichtbar

• Prozess besitzt konzeptionell einen eigenen virtuellen Prozessor

• reale(r) Prozessor(en) zwischen den virtuellen Prozessoren umgeschaltet (Mehrprogrammbetrieb)

• Multicore-Prozessoren enthalten mehrere Prozessoren auf einem Chip

• Umschaltungseinheit heißt Scheduler oder Dispatcher, SchedulingAlgorithmus legt Regeln fest

• Umschaltungsvorgang heißt Prozesswechsel oder Kontextwechsel (Context Switch)

• statische Beschreibung eines sequentiellen Algorithmus

• dasselbe Programm kann mehrmals (auch gleichzeitig!) innerhalb verschiedener Prozesse ausgeführt werden

• Ausführungsgeschwindigkeit eines Prozesses ist nicht gleichmäßig und nicht reproduzierbar

• Bei der Programmierung sind keine a-priori-Annahmen über den zeitlichen Verlauf zulässig

• Bei zeitkritische Anforderungen, z.B. Realzeit-System, sind besondere Vorkehrungen im Scheduling-Algorithmus notwendig

• Erzeugender Prozess heißt Vater (-prozess), erzeugte Prozesse heißen Sohn-/ Kindprozesse

• Allgemeiner Fall: Mechanismus notwendig, um Prozesse dynamisch (zur Laufzeit) durch andere Prozesse erzeugen zu können

• Wiederholte Prozesserzeugung durch Kindprozesse → baumartig strukturierte Prozessmenge

• Prozess mit all seinen direkten und indirekten Nachfahren heißt Prozessfamilie

• Jede baumartig strukturierte Menge von Prozessen heißt Prozesshierarchie (ohne notwendigerweise durch Prozesserzeugung aus der Wurzel entstanden zu sein)

• Prozesse, obwohl unabhängig, können aufgrund des Algorithmus logisch voneinander abhängig sein

• In Abhängigkeit von den relativen Ausführungsgeschwindigkeiten kann ein Prozess warten müssen, bis eine Eingabe vorliegt

• Allgemeiner sagt man: Er blockiert und wartet auf ein (für ihn externes) Ereignis

• Auch möglich: Scheduler entscheidet auf Prozesswechsel, obwohl der erste Prozess weiter ausgeführt werden könnte (Preemption)

• rechnend (oder aktiv): dem Prozess ist ein Prozessor zugeordnet, der das Programm vorantreibt

• rechenwillig (oder bereit): Prozess ist ausführbar, aber Prozessor ist anderem Prozess zugeordnet (bzw. alle verfügbaren Prozessoren sind anderen Prozessen zugeordnet)

• blockiert (oder schlafend): Prozess wartet auf Ereignis. Er kann solange nicht ausgeführt werden, bis das Ereignis eintritt

Gelegendlich

• initiiert: in Vorbereitung (Anfangszustand)

• terminiert: Prozess ist beendet (Endzustand)

(1) rechnend →blockiert: Versetzung in den Wartezustand, (Warten auf Ereignis)

(2) rechnend → rechenwillig: Scheduler entzieht den Prozessor

(3) rechenwillig → rechnend: Scheduler teilt Prozessor zu

(4) blockiert → rechenwillig: Ereignis tritt ein

Das Prozessmodell vereinfacht die Beschreibung der Aktivität des Rechensystems

Die unterste Schicht eines Betriebssystems behandelt die Unterbrechungen und ist für das Scheduling verantwortlich.

Der Rest des Systems besteht aus sequentiellen Prozessen

Mechanismen zur Synchronisation und Kommunikation von Prozessen sind notwendig

1. Programmzähler (u.a.) wird durch Hardware auf dem Stack abgelegt

2. Hardware lädt den neuen Programmzählerinhalt aus dem Unterbrechungsvektor

3. Eine Assembler-Routine rettet die Registerinhalte

4. Eine Assembler-Routine bereitet den neuen Stack vor

5. Eine C-Prozedur markiert den unterbrochenen Prozess als rechenwillig

6. Der Scheduler bestimmt den Prozess, der als nächster ausgeführt werden soll

7. Die C-Prozedur gibt die Kontrolle an die Assembler-Routine zurück

8. Die Assembler-Routine startet den ausgewählten Prozess

Einführung von billiger Nebenläufigkeit in einem Prozessadressraum durch „Leichtgewichtsprozesse", sogenannte Threads.

• ausführbares Programm, das Code und globale Daten definiert

• privater Adressraum. Code und Daten über Adressraum zugreifbar.

• Menge von Betriebsmitteln

  • geöffnete Objekte, Betriebssystem-Objekte wie z.B. Timer, Signale, Semaphore

  • dem Prozess durch das BS als Folge der Programmausführung zugeordnet

• Menge von Threads

• Idee einer „parallel ausgeführten Programmfunktion“

• Eigener Prozessor-Context (Registerinhalte usw.)

• Eigener Stack (i.d.R. zwei, getrennt für user und kernel mode)

• Eigener kleiner privater Datenbereich (Thread Local Storage)

• Threads eines Prozesses nutzen gemeinsam Programm, Adressraum und alle Betriebsmittel

Nein

Z.B Java macht es anders als C++ oder Windows oder Linux

• Betriebssystem unterstützt Threads

• Threads sind die Einheiten, denen Prozessoren zugeordnet werden (Schedulable Entities).

• 1:1-Zuordnung

• Programmierung mit Threads, aber BS-Scheduler kennt nur übliche Prozesse.

• 1:n-Zuordnung (allg. m:n)

Rechnende Prozesse können suspendiert werden (Prozessorentzug)

• preemptive-resume: Fortsetzung ohne Verlust

• preemptive-repeat: Beginn von vorne

Run-to-Completion, d.h. Prozess ist solange aktiv, bis er endet oder sich selbst blockiert.

Ist aber für General Purpose Systeme mit interaktiven Benutzern nicht geeignet!

Sie ordnen Prozessen Prioritäten zu.

Prioritäten können extern vorgegeben sein, oder intern durch das Betriebssystem selbst bestimmt werden.

Prioritäten können statisch sein, d.h. ändern sich während der Bearbeitung nicht, andernfalls dynamischen Prioritäten

Zeitscheiben-basierte Scheduling-Verfahren

Ja.

Scheduler auf mehreren Ebenen:

Nur die auf einer höheren Ebene durch den entsprechenden Scheduler ausgewählten Prozesse sind dem Scheduler der nächst niederen Ebene für sein Scheduling sichtbar. Scheduling der niederen Ebene wird dann häufig als Dispatching bezeichnet.

2-stufiges Scheduling; Der Scheduler der höheren Ebene transportiert Aufträge vom Hintergrundspeicher in den Arbeitsspeicher und zurück (Swapping); der Scheduler der niederen Ebene berücksichtigt ausschließlich Prozesse, die sich im Arbeitsspeicher befinden.

Auftrag: Einheit zur Bearbeitung (z.B. Stapeljob, Dialogschritt)

Bedienzeit: Zeitdauer für die reine Bearbeitung eines Auftrags durch die Bedienstation (den Prozessor)

Wartedisziplin: (einfache)

• FCFS (First-Come-First-Served) oder FIFO (First-In-First-Out)

• LIFO (Last-In-First-Out)

• Random (zufällig ausgewählt)

Antwortzeit: Zeitdauer vom Eintreffen eines Auftrags bis Fertigstellung (Zeitdauer von einer Eingabe eines Benutzers (z.B. Drücken der Return-Taste) bis zur Erzeugung einer zugehörigen Ausgabe (z.B. auf dem Bildschirm) bei Stapelaufträgen auch Verweilzeit genannt)

Wartezeit: Antwortzeit - Bedienzeit

Durchsatz: Anzahl der erledigten Aufträge pro Zeiteinheit

Auslastung: Anteil der Zeit im Zustand belegt

Fairness: "Gerechte" Behandlung aller Aufträge, z.B. alle rechenwilligen Prozesse haben gleichen Anteil an der zur Verfügung stehenden Prozessorzeit

Nutzer-bezogen:

• Kurze Antwortzeiten bei interaktiven Aufträgen

• Kurze Verweilzeiten für Stapelverarbeitungsaufträge

Betreiber-bezogen:

• Hoher Durchsatz

• Hohe Auslastung

• Fairness in der Behandlung aller Aufträge

• Geringer Aufwand für die Bearbeitung des Scheduling-Algorithmus selbst (Overhead!)

Vorabwissen über die Bedienzeit:

• Einige Verfahren verlangen Kenntnis der Bedienzeit eines Auftrags bei dessen Ankunft (vgl. Verfahren zur Maschinenbelegung, Operations Research)

• Nur (teilweise) realistisch für wiederkehrende Stapeljobs, nicht realistisch bei interaktiven Aufträgen

• Ziel: höhere Flexibilität

• Parametrisierbarer Scheduling-Mechanismus auf niederer Ebene (im Betriebssystemkern)

• Parameter können auf höherer Ebene (z.B. über Systemaufrufe in Benutzerprozessen) gesetzt werden, um applikationsbezogene Strategie zu implementieren

  → Das Scheduling wird damit weiter auf niederer Ebene durchgeführt, aber von der Applikationsebene aus gesteuert

Über die von der letzten Antwort gennanten Forderung hinaus kann ein Applikations-programm dem Betriebssystem z.B. über einen Systemaufruf einen Scheduler übergeben, der für eine Teilmenge der Prozesse deren Scheduling durchführt (Höchstmaß an Flexibilität)

Nur in wenigen Betriebssystemen vorhanden

1. First-Come-First-Served (FCFS)

2. Shortest-Job-First (SJF)

3. Prioritäts-Scheduling (Prio)

Algorithmus:

• Einfachst-Algorithmus: "Wer zuerst kommt, mahlt zuerst“

• Vollständige Bearbeitung jedes Auftrags, bevor ein neuer begonnen wird

Implementierung:

• Die Ready-Queue wird als FIFO- Liste verwaltet

• Bedienungsmodell:

Algorithmus:

• Von allen rechenwilligen Prozessen wird derjenige mit der kleinsten Bedienzeitanforderung ausgewählt

• Bei gleicher Bedienzeitanforderung wird nach FCFS gewählt

• Der Algorithmus SJF ist in dem Sinne optimal in der Menge aller möglichen Algorithmen, dass er die kürzeste mittlere Wartezeit für alle Aufträge sichert

• Notwendigkeit der Kenntnis der Bedienzeit!

Algorithmus:

• Jeder Auftrag besitze eine statische Priorität.

• Von allen rechenwilligen Prozessen wird derjenige mit der höchsten Priorität ausgewählt.

• Bei gleicher Priorität wird nach FCFS ausgewählt.

1. Round-Robin-Scheduling (RR)

2. Dynamisches Prioritäts-Scheduling

3. Mehrschlangen-Scheduling

4. Mehrschlangen-Feedback-Scheduling

5. Earliest-Deadline-First-Scheduling

Algorithmus:

• Menge der rechenwilligen Prozesse linear geordnet

• Jeder rechenwillige Prozess erhält den Prozessor für eine feste Zeitdauer q, die Zeitscheibe (time slice) oder Quantum genannt wird

• Nach Ablauf des Quantums wird der Prozessor entzogen und dem nächsten zugeordnet (preemptive-resume)

• Tritt vor Ende des Quantums Blockierung oder Prozessende ein, erfolgt der Prozesswechsel sofort

• Dynamisch eintreffende Aufträge werden z.B. am Ende der Warteschlange eingefügt

Implementierung:

• Die Zeitscheibe wird durch einen Uhr-Interrupt realisiert

• Die Ready Queue wird als lineare Liste verwaltet, bei Ende eines Quantums wird der Prozess am Ende der Ready Queue eingefügt

Round-Robin ist einfach und weit verbreitet.

Alle Prozesse werden als gleichwichtig angenommen und fair bedient

Einziger kritischer Punkt: Wahl der Dauer des Quantums:

• Quantum zu klein → häufige Prozesswechsel, sinnvolle Prozessornutzung sinkt

• Quantum zu groß → schlechte Antwortzeiten bei kurzen interaktiven Aufträgen

Jedem Prozess ist eine statische Priorität zugeordnet

Prozesse werden gemäß ihrer Priorität in eine Warteschlange eingereiht

Es wird jeweils der rechenwillige Prozess mit der höchsten Priorität ausgewählt und bedient

Wird ein Prozess höherer Priorität rechenwillig (z.B. nach Beendigung einer Blockierung), so wird der laufende Prozess unterbrochen (preemption) und in die Ready Queue eingefügt

Prozesse werden statisch klassifiziert als einer bestimmten Gruppe zugehörig (z.B. interaktiv, batch)

Alle rechenwilligen Prozesse einer bestimmten Klasse werden in einer eigenen Ready Queue verwaltet

Jede Ready Queue kann ihr eigenes Scheduling-Verfahren haben (z.B. RoundRobin für interaktive Prozesse, FCFS für batch-Prozesse)

Zwischen den Ready Queues wird i.d.R. unterbrechendes PrioritätsScheduling angewendet, d.h.: jede Ready Queue besitzt eine feste Priorität im Verhältnis zu den anderen; wird ein Prozess höherer Priorität rechenwillig, wird der laufende Prozess unterbrochen (preemption)

Erweiterung des Mehrschlangen-Scheduling

Rechenwillige Prozesse können im Verlauf in verschiedene Warteschlangen eingeordnet werden (dynamische Prioritäten)

Algorithmen zur Neubestimmung der Priorität wesentlich

• Beispiel 1: Wenn ein Prozess blockiert, wird die Priorität nach Ende der Blockierung um so größer, je weniger er von seinem Quantum verbraucht hat (Bevorzugung von I/O-intensiven Prozessen)

• Beispiel 2: Wenn ein Prozess in einer bestimmten Priorität viel Rechenzeit zugeordnet bekommen hat, wird seine Priorität verschlechtert (Bestrafung von Langläufern)

• Beispiel 3: Wenn ein Prozess lange nicht bedient worden ist, wird seine Priorität verbessert (Altern, Vermeidung einer "ewigen" Bestrafung)

Mit wachsender Bedienzeit sinkt die Priorität, d.h. Kurzläufer werden bevorzugt, Langläufer werden zurückgesetzt

Wachsende Länge des Quantums mit fallender Priorität verringert die Anzahl der notwendigen Prozesswechsel (Einsparen von Overhead)

Verbesserung der Priorität nach Beendigung einer Blockierung berücksichtigt I/O-Verhalten (Bevorzugung von I/O-intensiven Prozessen)

Durch Unterscheidung von Terminal I/O und sonstigem I/O können interaktive Prozesse weiter bevorzugt werden

sehr flexibel

Scheduling in Realzeit-Systemen beinhaltet zahlreiche neue Aspekte, hier nur erster kleiner Einblick

Varianten in der Vorgehensweise

• Statisches Scheduling: Alle Daten für die Planung sind vorab bekannt, die Planung erfolgt durch eine Offline-Analyse

• Dynamisches Scheduling: Daten für die Planung fallen zur Laufzeit an und müssen zur Laufzeit verarbeitet werden

• Explizite Planung: Dem Rechensystem wird ein vollständiger Ausführungsplan (Schedule) übergeben und zur Laufzeit befolgt (Umfang kann extrem groß werden)

• Implizite Planung: Dem Rechensystem werden nur die Planungsregeln übergeben

Gewisse Prozesse müssen häufig zyklisch ausgeführt werden

Hard-Realtime-Prozesse müssen unter allen Umständen ausgeführt werden (ansonsten sind z.B. Menschenleben bedroht)

Zeitliche Fristen (Deadlines) vorgegeben, zu denen der Auftrag erledigt sein muss

Scheduler muss die Erledigung aller Hard-Realtime-Prozesse innerhalb der Fristen garantieren

Scheduling geschieht in manchen Anwendungssystemen statisch vor Beginn der Laufzeit (z.B. Automotive): Bedienzeit-Anforderung (z.B. worst case) muss bekannt sein

Im Falle von dynamischem Scheduling ist das Earliest-Deadline-First-SchedulingVerfahren verbreitet, das den Prozess mit der frühesten fälligen Frist zur Ausführung auswählt

Ziel:

• Gute Antwortzeiten für interaktive Prozesse.

Vorgehensweise:

• Zweistufiges Scheduling: Hintergrundspeicher-Hauptspeicher-Swapping

• Scheduling von im Hauptspeicher befindlichen Prozessen

Ziel:

• Vermeidung ungewollter gegenseitiger Beeinflussung

• Unterstützung gewollter Kooperation zwischen Prozessen Gemeinsame Benutzung von Betriebsmitteln (Sharing) Übermittlung von Signalen Nachrichtenaustausch

Fazit: Mechanismen zur Synchronisation und Kommunikation von Prozessen sind notwendig

Annahme: Prozesse mit Lese/Schreib-Operationen auf Betriebsmitteln

Zwei nebenläufige Prozesse heißen im Konflikt zueinander stehend oder überlappend, wenn es ein Betriebsmittel gibt, das sie gemeinsam (lesend und schreibend) benutzen, ansonsten heißen sie unabhängig oder disjunkt

Folgen von Lese/Schreib-Operationen der verschiedenen Prozesse heißen zeitkritische Abläufe (engl. race conditions), wenn die Endzustände der Betriebsmittel (Endergebnisse der Datenbereiche) abhängig von der zeitlichen Reihenfolge der Lese/Schreib-Operationen sind

(engl. mutual exclusion): Verfahren, das verhindert, dass zu einem Zeitpunkt mehr als ein Prozess zugreift

Bemerkung: Ein Verfahren zum wechselseitigen Ausschluss vermeidet zeitkritische Abläufe. Es löst damit ein Basisproblem des Concurrent Programming

(engl. critical section oder critical region): Teil eines Programms, in dem auf gemeinsam benutzte Datenbereiche zugegriffen wird

Bemerkung: Ein Verfahren, das sicherstellt, dass sich zu keinem Zeitpunkt zwei Prozesse in ihrem kritischen Abschnitt befinden, vermeidet zeitkritische Abläufe

Kritische Abschnitte realisieren sog. komplexe unteilbare oder atomare Operationen

1. Zu jedem Zeitpunkt darf sich nur ein Prozess in seinem kritischen Abschnitt befinden (Korrektheit, Basisforderung)

2. Es dürfen keine Annahmen über die Ausführungsgeschwindigkeiten oder die Anzahl der unterliegenden Prozessoren gemacht werden

3. Kein Prozess, der sich nicht in seinem kritischen Abschnitt befindet, darf andere Prozesse blockieren (Fortschritt)

4. Alle Prozesse werden gleich behandelt (Fairness)

5. Kein Prozess darf unendlich lange warten müssen, bis er in seinen kritischen Abschnitt eintreten kann ("Verhungern", engl. starvation)

• Prolog

• Critical section

• Epilog

Aktives Warten auf Eintritt in den kritischen Abschnitt (engl. busy waiting).

Aktives Warten für einen längeren Zeitraum verschwendet Prozessorzeit .

Alle Prozesse müssen sich an das Vorgehen halten.

1. Sperren aller Unterbrechungen

2. Sperrvariablen

3. Striktes Alternieren

4. Lösung von Peterson

5. Test-and-Set-Instruktion

Es ist die einfachste Lösung:

• Jeder Prozess sperrt vor Eintritt in seinen kritischen Abschnitt alle Unterbrechungen (Disable Interrupts)

• Jeder Prozess lässt die Unterbrechungen am Ende seines kritischen Abschnitts wieder zu (Enable Interrupts)

• Der Prozessor kann nur dann zu einem anderen Prozess wechseln, wenn eine Unterbrechung auftritt. Also ist für diese Lösung die Korrektheitsforderung erfüllt

• Lösung ist unbrauchbar für allgemeine Benutzerprozesse, da nicht zugesichert werden kann, dass sie die Interrupts auch wieder zulassen (z.B. wegen Programmierfehler)

• Lösung wird häufig innerhalb des Betriebssystemkerns selbst eingesetzt, um wechselseitigen Ausschluss zwischen Kernroutinen zu gewährleisten (z.B. im alten Einprozessor-UNIX-Kern, um wechselseitigen Ausschluss mit einem Interrupt-Handler sicherzustellen)

• Lösung unbrauchbar im Falle eines Multiprozessor-Systems, da sich die InterruptSperre i.d.R. nur auf einen Prozessor auswirkt

Einfacher, falscher Lösungsansatz:

• Jedem krit. Abschnitt wird eine Sperrvariable zugeordnet:

  • Wert 0 bedeutet "frei“

  • Wert 1 bedeutet "belegt“

• Jeder Prozess prüft die Sperrvariable vor Eintritt in den kritischen Abschnitt:

  • Ist sie 0, so setzt er sie auf 1 und tritt in den kritischen Abschnitt ein

  • Ist sie 1, so wartet er, bis sie den Wert 0 annimmt

Am Ende seines kritischen Abschnitts setzt der Prozess den Wert der Sperrvariablen auf 0 zurück

• Prinzipiell gleicher Fehler wie bei Spooler-Beispiel: Zwischen Abfrage der Sperrvariablen und folgendem Setzen kann der Prozess unterbrochen werden

• Damit ist es möglich, dass sich beide Prozesse im kritischen Abschnitt befinden (Korrektheitsbedingung verletzt !!)

• Speicher (-wörter, -variablen) erlauben nur unteilbare Lese- und Schreibzugriffe (Eigenschaft der Architektur des Speicherwerks)

• Warten wird aktiv durchgeführt

• Prozesse wechseln sich ab: 0,1,0,1,...

• Lösung erfüllt Korrektheitsbedingung, aber

• Fortschrittsbedingung (3) kann verletzt sein, wenn ein Prozess wesentlich langsamer als der andere ist

• Fazit: keine ernsthafte Lösung

Lösung von Peterson (1981) (im Folgenden betrachtet) basiert ebenfalls auf unteilbaren Speicheroperationen und aktivem Warten, ist aber einfacher

Algorithmen zu komplex, die nur auf atomaren Speicherzugriffen basieren (siehe Peterson Code)

→ Notwendigkeit für effiziente Lösung

Jedem kritischen Abschnitt wird eine Sperrvariable flag zugeordnet. Wert 0 bedeutet "frei", Wert 1 bedeutet "belegt".

Auf Test-and-Set basierende Sperrvariablen mit aktivem Warten heißen auch spin locks. Hohe Bedeutung in Multiprozessor-Betriebssystemen.

Lösung durch Hardware-Unterstützung:

• Einführung eines Maschinenbefehls Test-and-Set: unteilbares Lesen einer Speicherzelle mit anschließendem Schreiben eines Wertes in die Zelle (Speicherbus wird dazwischen nicht freigegeben)

Heute

• Standard auf praktisch allen Architekturen (mit geringen Abweichungen)

• notwendig für Multiprozessor-Systeme

• häufig zusätzliche unteilbare Maschinen-Operationen zur Listenmanipulation

• Dieses Problem kann trotz korrekter Lösungen mit aktivem Warten (Peterson, Testand-Set, s.o.) auftreten

• Prozess H habe hohe Priorität, Prozess L habe niedere Priorität. Scheduling-Regel: wenn H rechenwillig ist, soll H ausgeführt werden

• Es werde H rechenwillig, während L sich in seinem kritischen Abschnitt befindet. H wolle ebenfalls in seinen kritischen Abschnitt eintreten

• Wird nun der höher priore Prozess H ausgeführt, so wartet er aktiv für immer, da L seinen kritischen Abschnitt nicht beenden kann

• Es muss also der nieder priore Prozess ausgeführt werden! Diese Situation heißt auch Prioritätsinversionsproblem

• (Darüberhinaus tritt das Problem in Lösungen mit passivem Warten ebenfalls auf. Insbesondere in Echtzeitbetriebssystemen ist eine Lösung hierfür extrem wichtig.) Problem der Prioritätsinversion

Prioritätsinversion benötigt eigentlich drei Prozesse

Prolog-Operationen zum Betreten des kritischen Abschnitts führen zum Aktiven Warten, bis der betreffende Prozess in den krit. Abschnitt eintreten kann

Lediglich auf Multiprozessor-Systemen kann kurzzeitiges Aktives Warten zur Vermeidung eines Prozesswechsels sinnvoll sein (spin locks)

Ziel: Vermeidung von verschwendeter Prozessorzeit

Vorgehensweise: Prozesse blockieren, wenn sie nicht in ihren kritischen Abschnitt eintreten können

Ein blockierter Prozess wird durch den aus seinem krit. Abschnitt austretenden Prozess entblockiert

• Einfachste Primitive werden als SLEEP und WAKEUP bezeichnet

• SLEEP() blockiert den ausführenden Prozess, bis er von einem anderen Prozess geweckt wird

• WAKEUP(process) weckt den Prozess process. Der ausführende Prozess wird dabei nie blockiert

• Häufig wird als Parameter von SLEEP und WAKEUP ein Ereignis (Speicheradresse einer beschreibenden Struktur) verwendet, um die Zuordnung treffen zu können, (vgl. 3.2 Beispiel UNIX(7) Kernroutinen)

• Diese Primitive können auch der allgemeinen ereignisorientierten Kommunikation dienen

• Der Begriff Mutex ist von mutual exclusion abgeleitet.

• Ein Mutex offeriert Operationen

  • lock als Prolog-Operation zum Betreten des kritischen Abschnitts

  • unlock als Epilog-Operation beim Verlassen des kritischen Abschnitts

• Mutexe können als Spezialfall von Semaphoren angesehen werden (vgl. 5.2.3).

• Gelegentlich wird angenommen, dass unlock alle wartenden Prozesse entblockiert und sich diese dann erneut um das Betreten des kritischen Abschnitts bewerben

Ein Semaphor s ist ein Objekt, das eine lokale integer-Variable i enthält, die mit einer natürlichen Zahl n initialisiert wird, und das die folgenden atomaren (unteilbaren) Operationen offeriert:

P(s) oder DOWN(s):

i > 0 → i := i - 1; Prozess fährt fort

i = 0 → ausführender Prozess blockiert (Er legt sich am Semaphor schlafen)

Wichtig: Atomarität bedeutet, dass Überprüfen des Wertes, Verändern des Wertes und sich Schlafen legen als eine einzige, unteilbare Operation ausgeführt werden. Dieses vermeidet zeitkritische Abläufe.

V(s) oder UP(s):

i := i + 1;

• Wenn es blockierte Prozesse gibt, wird einer von ihnen ausgewählt. Er kann seine P-Operation jetzt erfolgreich beenden. Das Semaphor hat in diesem Fall dann weiterhin den Wert Null, aber es gibt einen Prozess weniger, der an dem Semaphor schläft.

• Erhöhen des Semaphor-Wertes und ev. Wecken eines Prozesses werden ebenfalls als unteilbare Operation ausgeführt

• Kein Prozess wird bei der Ausführung einer V-Operation blockiert

• Semaphore, die nur die Werte 0 und 1 annehmen, heißen binäre Semaphore, ansonsten heißen sie Zählsemaphore

• Binäre Semaphore zur Realisierung des wechselseitigen Ausschlusses.

• Ein mit n > 1 initialisiertes Zählsemaphor kann zur Kontrolle der Benutzung eines in n Exemplaren vorhandenen Typs von sequentiell wiederverwendbaren Betriebsmitteln verwendet werden

• P und V sind vom Holländischen proberen und verhogen abgeleitet

• Semaphore weit verbreitet

• innerhalb von Betriebssystemen

• zur Programmierung nebenläufiger Anwendungen

• Programmierung mit Semaphoren ist oft fehleranfällig, wenn mehrere Semaphore benutzt werden müssen

• Mutex-locks können als binäre Semaphore angesehen werden

Das mit 1 initialisierte Semaphor sem wird von allen beteiligten Prozessen benutzt

Jeder Prozess klammert seinen kritischen Abschnitt, mit P(sem) zum Eintreten und V(sem) zum Verlassen

• Jedem I/O-Gerät wird ein Geräteprozess und ein mit 0 initialisiertes Semaphor zugeordnet

• Nach dem Start des Geräteprozesses führt dieser eine P-Operation auf dem Semaphor aus (und blockiert)

• Im Falle eines Interrupts des Gerätes führt der Interrupt Handler eine VOperation auf dem Semaphor aus. Der Geräteprozess wird entblockiert (und dadurch rechenwillig) und kann das Gerät bedienen

Es seien n Exemplare vom Betriebsmitteltyp bm vorhanden

Jedes BM dieses Typs sei sequentiell benutzbar

Dem BM-Typ bm wird ein Semaphor bm zugeordnet

Beantragen eines BM durch P(bm), ev. mit Blockieren, bis ein BM verfügbar wird

Nach der Benutzung freigeben des BM durch V(bm) (Es kann damit von einem weiteren Prozess benutzt werden)

• Üblich als Systemaufrufe. Intern Nutzung von Sich-Schlafen-Legen und Aufwecken.

• Wesentlich ist die Unteilbarkeit der Implementierung von P() und V():

  • Auf Einprozessorsystemen: Unteilbarkeit kann durch Sperren aller Unterbrechungen während der Ausführung von P() und V() erreicht werden. Zulässig, da nur wenige Maschineninstuktionen zur Implementierung nötig sind.

  • Auf Multiprozessorsystemen: Jedem Semaphor wird eine mittels Test-and-Set realisierte Sperrvariable mit Aktivem Warten vorgeschaltet. Hierdurch kann zu jedem Zeitpunkt nur höchstens ein Prozessor das Semaphor manipulieren.

• Beachte: Unterscheide zwischen Aktivem Warten auf den Zugang zum Semaphor, das einen kritischen Abschnitt schützt (einige Instruktionen, Mikrosekunden) und Aktivem Warten auf den Zugang zum kritischen Abschnitt selbst (problemabhängig, Zeitdauer nicht vorab bekannt oder begrenzt)

Ja, erheblich. Es werden Gruppen von Semaphoren betrachtet.

Windows NT offeriert Zählsemaphore als Systemobjekte für die Synchronisation von Threads beliebiger Prozesse.

In Programmiersprache eingebettete Primitive zur einfacheren Entwicklung korrekter nebenläufiger Programme.

Heutige Sicht: Monitor entspricht einer Instanz eines abstrakten Datentyps mit automatischem wechselseitigen Ausschluss.

(Monitore haben kaum Eingang in Programmiersprachen gefunden)

1. Erzeuger-Verbraucher-Problem

2. Philosophen-Problem

3. Leser-Schreiber-Problem

• Erzeuger: Will Einfügen, aber Puffer ist voll

  • Lösung: Lege dich schlafen, lass dich vom Verbraucher wecken, wenn er ein Datum entnommen hat

• Verbraucher: Will Entnehmen, aber Puffer ist leer

  • Lösung: Lege dich schlafen, lass dich vom Erzeuger wecken, wenn er ein Datum eingefügt hat

Dieses Problem wird auch "Problem des beschränkten Puffers" (bounded buffer problem) genannt.

Im weiteren werden folgende Lösungsansätze betrachtet:

1. Lösung mit Semaphoren

2. Lösung mit Monitoren

3. Lösung mit Nachrichtenaustausch

5 Philosophen sitzen am runden Tisch. Jeder hat einen Teller, zwischen je zwei benachbarten Tellern liegt eine Gabel. Linke und rechte Gabel werden zum Essen benötigt. Nach dem Essen werden beide Gabeln abgelegt. Essen und Denken wechseln einander fortlaufend ab.

Wenn alle Philosophen die 2 Gabeln greifen wollen entsteht eine Deadlock.

Beim so genannten Leser-Schreiber-Problem gibt es zwei Typen von Prozessen, die Leser und die Schreiber. Eine Menge von Lesern und Schreibern wollen einen gemeinsamen kritischen Abschnittbetreten. Dabei gilt es jedoch, folgende Bedingungen einzuhalten:

• Im kritischen Abschnitt dürfen sich niemals Leser und Schreiber gleichzeitig aufhalten.

• Im kritischen Abschnitt dürfen sich beliebig viele Leser gleichzeitig aufhalten.

• Im kritischen Abschnitt dürfen sich niemals mehrere Schreiber gleichzeitig aufhalten.

Interaktionen zwischen Prozessen können zu zeitkritischen Abläufen führen, d.h. Situationen, in denen das Ergebnis vom zeitlichen Ablauf abhängt. Zeitkritische Abläufe führen zu einem nicht reproduzierbaren Verhalten und müssen vermieden werden.

Kritische Bereiche als Teile von Programmen, in denen mit anderen Prozessen gemeinsamer Zustand manipuliert wird, bieten die Möglichkeit des wechselseitigen Ausschlusses. Sie vermeiden damit zeitkritische Abläufe und erlauben komplexe unteilbare (atomare) Aktionen

Viele Primitive zur Synchronisation und Kommunikation von Prozessen wurden vorgeschlagen. Sie machen verschiedene Annahmen über die unterlagerten elementaren unteilbaren Operationen, sind aber im Prinzip gleichmächtig. Besprochen wurden insbesondere Semaphoren und Nachrichtenaustausch, die in aktuellen Systemen weit verbreitet sind.

Sie sind zur Vermeidung von zeitkritischen Abläufen da aber auch zur Signalisierung von Ereignissen zwischen Prozessen geeignet (z.B. Fertig-Signale zur Durchsetzung einer Vorrangrelation zwischen Prozessen eines Prozesssystems)

• Betriebssysteme können darüberhinaus spezielle Mechanismen für die Kommunikation (Signalisierung) von Ereignissen offerieren. (Diese Mechanismen können wiederum auch zur Synchronisation eingesetzt werden)

• Kommunikation von Ereignissen ist ein Spezialfall der Nachrichten-orienterten Kommunikation

• Ereignisse zeigen das Eintreten einer "wichtigen Begebenheit" an

  • z.B. das Erreichen eines best. Zustands

  • das Eintreten eines Fehlers

  • den Ablauf einer vorgegebenen Zeitspanne

• Ereigniskonzept als Übertragung des Hardware-Interrupt-Konzepts auf die Software-Ebene

• Ereignisse werden lediglich nummeriert, Zuordnung einer tatsächlichen Bedeutung kann ganz oder teilweise vorgegeben oder den Anwendungen überlassen sein

• Bereitstellung eines effizienten Ereigniskonzepts ist insbesondere für Echtzeitbetriebssysteme von Bedeutung: In Echtzeitanwendungen modellieren Ereignisse häufig reale Ereignisse in der Außenwelt

• UNIX unterscheidet zwei Arten von Signalen:

• Fehler-Ereignisse, die bei der Programmausführung auftreten, z.B.: Adressierung eines ungültigen Speicherbereichs

• Asynchrone Ereignisse, die von außerhalb des Prozesses stammen, z.B.: Beendigung eines Sohn-Prozesses

Das UNIX-Signalkonzept überträgt das Hardware-Interrupt-Konzept auf die Software-Ebene:

Interrupt → Signal

Interrupt Handler → Signal Handler

Maskieren von Interrupts → Maskieren von Signalen

• Ein Prozess im Zustand rechnend kann durch den BS-Kern Signale senden und empfangen

• Nicht-rechnende Prozesse können nur Signale von rechnenden Prozessen empfangen

• Ein Prozess kann festlegen, dass er bestimmte Signale selbst durch einen Signal-Handler behandeln oder ignorieren will. Einige Signale (wie z.B. SIGKILL) können nicht abgefangen werden.

• Ein Prozess kann nur Signale an Prozesse mit derselben realen oder effektiven User-Id senden (Prozessgruppe), insbesondere an sich selbst. Darüberhinaus können Prozesse mit der realen oder effektiven User-Id 0 (d.h. mit Superuser-Berechtigung) Signale an beliebige Prozesse senden.

• Der BS-Kern kann jedes Signal an jeden Prozess senden

• Die Verarbeitung von anstehenden Signalen geschieht, wenn der Prozess aktiv ist und im Kernmodus ausgeführt wird

• Das Betriebssystem hält die Signalmasken im Prozesskontrollblock des Prozesses

• Signalisierung von Ereignissen ist Spezialfall des Austausches von Nachrichten beliebiger Art (Paradigma der Kooperation durch Nachrichtenaustausch)

• Betriebssysteme besitzen i.d.R. entsprechende Mechanismen zur nachrichtenorientierten Kommunikation

• Nachrichtenorientierte Kommunikation ist sowohl für lokale wie auch für verteilte Rechensysteme anwendbar

Kopplung/Verbindung der Kommunikationspartner notwendig, um die Kommunikation zu ermöglichen

• Verbindung heißt Kommunikationskanal oder Kanal

• Ein Prozess kann zu einem Zeitpunkt mehrere Kanäle aufrecht erhalten (i.d.R. zu verschiedenen Prozessen)

Wichtige Entwurfsaspekte eines Nachrichtensystems:

• Adressierung, Pufferung, Nachrichtenstruktur

Operationen:

• SEND ( message, ... ) zum Senden einer Nachricht durch einen Sendeprozess oder einfach Sender

• RECEIVE ( message, ... ) zum Empfangen einer Nachricht durch einen Empfangsprozess oder Empfänger

Anzahl der Kommunikationsteilnehmer eines Kanals

• Genau zwei: Regelfall

• Mehr als zwei: Gruppenkommunikation (Multicast-Dienst, Spezialfall: Broadcast, d.h. Rundsendung an alle), hier nicht weiter betrachtet

Richtung des Nachrichtenflusses eines Kanals

• Kanal heißt gerichtet oder unidirektional, wenn ein Prozess ausschließlich die Sender-Rolle, der andere ausschließlich die Empfänger-Rolle ausübt, ansonsten ungerichtet oder bidirektional

• Direkte Adressierung

• Asymmetrische Variante (z.B. für Server-Prozesse)

• Indirekte Adressierung

Direkte Adressierung

• Prozesse haben eindeutige Adressen

• Benennung ist explizit und symmetrisch: sendender Prozess muss Empfänger benennen und umgekehrt. z.B.:

  • SEND ( P, message ) // Sende eine Nachricht an Prozess P

  • RECEIVE ( Q, message ) // Empfange eine Nachricht von Prozess Q

Asymmetrische Variante (z.B. für Server-Prozesse)

• Sender benennt Empfänger, Empfänger (Server-Prozess) wird mit dem Empfang die Identität des Senders bekannt:

  • SEND ( P, message )

  • RECEIVE ( sender_id , message )

Indirekte Adressierung

• Kommunikation erfolgt indirekt über zwischengeschaltete Mailboxes (Puffer für eine Anzahl von Nachrichten):

  • SEND (mbox, message) Sende eine Nachricht an Mailbox mbox

  • RECEIVE (mbox, message) Empfange eine Nachricht von Mailbox mbox

Vorteile:

• Verbesserte Modularität

• Prozessmenge kann transparent restrukturiert werden, z.B. nach Ausfall eines Empfangsprozesses

• Erweiterte Zuordnungsmöglichkeiten von Sendern und Empfängern, wie z.B. m:1, 1:n, m:n

Def. Kapazität

• Kapazität eines Kanals bezeichnet Anzahl der Nachrichten, die vorübergehend in einem Kanal gespeichert werden können, um Sender und Empfänger zeitlich zu entkoppeln

• Die Pufferungsfähigkeit eines Kanals wird i.d.R. durch einen Warteraum/Warteschlange im Betriebssystemkern erreicht

• Sender wird blockiert, wenn SEND-Operation vor entsprechender RECEIVE-Operation stattfindet. Wird dann die entsprechende RECEIVE-Operation ausgeführt, wird die Nachricht ohne Zwischenspeicherung unmittelbar vom Sender- zum EmpfängerProzess kopiert

• Findet umgekehrt RECEIVE zuerst statt, so wird der Empfänger bis zum Aufruf der SEND-Operation blockiert

• Diese ungepufferte Kommunikationsform, die Sender und Empfänger zeitlich sehr eng koppelt, heißt Rendezvous oder synchroner Nachrichtenaustausch

• Synchroner Nachrichtenaustausch wird häufig als zu inflexibel angesehen.

• Kanal kann zu einem Zeitpunkt maximal N Nachrichten enthalten (Warteraum der Kapazität N)

• Im Falle einer SEND-Operation bei nicht-vollem Warteraum wird die Nachricht im Warteraum abgelegt und Sendeprozess fährt fort

• Ist der Warteraum voll (er enthält N gesendete aber noch nicht empfangene Nachrichten), so wird der Sender blockiert, bis ein freier Warteplatz vorhanden ist

• Ablegen der Nachricht kann durch Kopieren der Nachricht oder Speichern eines Zeigers auf die Nachricht realisiert sein

• Analog wird Empfänger bei Ausführung einer RECEIVE-Operation blockiert, wenn Warteraum leer

• Kanal kann potentiell eine unbeschränkte Anzahl von Nachrichten enthalten

• SEND-Operation kann nicht blockieren

• Lediglich Empfänger kann bei Ausführung einer RECEIVE-Operation blockieren, wenn Warteraum leer

• Implementierung kann erfolgen, in dem Sender und Empfänger die Warteplätze beim Aufruf "mitbringen“

• Gepufferte Kommunikation (beschränkt oder unbeschränkt) bewirkt zeitlich lose Kopplung der Kommunikationspartner

• Nach Abschluss der SEND-Operation weiß der Sender nicht, dass der Empfänger die Nachricht erhalten hat. Er kennt i.d.R. auch keine maximale Zeitdauer dafür

• Wenn dieses Wissen wesentlich für den Sender ist, muss dazu eine explizite Kommunikation zwischen Sender und Empfänger durchgeführt werden:

Nachrichten haben eine typisierte Struktur.

Typ ist Sender und Empfänger und z.T. dem Nachrichten-system bekannt und wird in Operationen verwendet.

Beispielhafter Aufbau einer Nachricht:

Nachrichtencontainer

• Nachrichten sind für Sender und Empfänger identifizierbare Einheiten fester oder variabler Länge. Nachrichtengrenzen bleiben erhalten.

• Korrekte Interpretation der internen Struktur einer Nachricht obliegt den Kommunikationspartnern

• Beispiel: UNIX message queues

Bytestrom

• Empfänger (und das Nachrichtensystem) sehen ausschließlich eine Folge von Zeichen (Bytestrom)

• Übergebene Nachrichten verschiedener SEND-Operationen sind als Einheiten nicht mehr identifizierbar. Nachrichtengrenzen gehen verloren

• Beispiel: UNIX pipes

Klassische Implementierung

• Speicher für zu puffernde Nachrichten liegt im BS-Kern

• Bei Ausführung von SEND wird die Nachricht aus dem sendenden Prozess(- adressraum) in den BS-Kern kopiert

• Bei Ausführung von RECEIVE wird die Nachricht aus dem BS-Kern in den empfangenden Prozess(-adressraum) kopiert

• Fazit: 2-maliges Kopieren. Aufwendig!

Integration mit Speicherverwaltung

• In modernen Betriebssystemen wird die Implementierung von Nachrichtenkommunikation mit dem Virtual Memory Management integriert (z.B. Mach)

• Versenden von Nachrichten wird auf das Kopieren von Deskriptoren von Speicherbereichen beschränkt

• Die Speicherbereiche werden durch Markierung als copy-on-write nur im Notfall wirklich kopiert (lazy copying)

Pipes

• Ursprünglicher Mechanismus zum unidirektionalen Nachrichten-transport (Bytestrom) zwischen verwandten Prozessen

• Vererbung der Kommunikationsendpunkte durch fork()

Named Pipes oder FIFOs

• Erweiterung auf nicht-verwandte Prozesse

• Dateisystem-Namensraum als gemeinsamer Namensraum zur Benennung von Named Pipes

• Repräsentierung von Named Pipes im Dateisystem

Message Queues

• Bestandteil der System V IPC-Mechanismen

• Message Queue ist komplexes, gemeinsam benutztes Objekt zum Austausch typisierter Nachrichten zwischen potentiell beliebig vielen Sende- und Empfangs-Prozessen

Sockets

• In 4.2BSD UNIX zusammen mit TCP/IP eingeführtes Konzept zur allgemeinen, rechnerübergreifenden, bidirektionalen, nachrichtenorientierten Interprozesskommunikation

• zur Programmierung von Client/Server-Kommunikation geeignet

• weit verbreitet (wird in LV Verteilte Systeme behandelt)

STREAMS

• Mit UNIX System V Rel. 3 erstmals eingeführte Gesamtumgebung zur Entwicklung von geschichteten IPC-Protokollen

• Modularisierung durch verkettbare STREAMS-Module

• In UNIX System V Rel. 4 werden Pipes, Named Pipes, TerminalProtokolle und Netzwerkkommunikation in der STREAMS-Umgebung bereitgestellt

Eigenschaften:

• Anonyme Pipe definiert namenlosen unidirektionalen Kommunikationskanal, über den zwei Prozesse mit einem gemeinsamen Vorfahren einen Bytestrom kommunizieren können

• Pipe besitzt eine Pufferkapazität von einer Seite (z.B. 4 Kb)

• wird von den Prozessen wie eine Datei behandelt

Typischer Umgang:

• Vater legt Pipe an, erzeugt zwei Söhne durch fork(), die die geöffneten Enden der Pipe als File-Deskriptoren erben

• Der Schreiber schließt (mittels close) die Lese-Seite, der Leser die Schreib-Seite, der Vater beide Seiten

• Analog kann der Vater mit einem Sohn über eine Pipe kommunizieren.

• Eine benannte Pipe, auch FIFO genannt, definiert einen Kommunikationskanal, über den mehrere Sender- und mehrere Empfänger-Prozesse, die nicht miteinander verwandt sein müssen, einen gemeinsamen Bytestrom kommunizieren können

• Eine benannte Pipe besitzt einen Namen aus dem Dateinamensraum und eine Repräsentierung im Dateisystem (inode, Dateikontrollblock, vgl. Kap. 10) aber keine Datenblöcke, sondern lediglich einen SeitenPuffer im Arbeitsspeicher

• Für benannte Pipes existieren Zugriffsrechte wie bei Dateien, die beim Öffnen überprüft werden

• In System V sind FIFOs durch ein spezielles vnode-Dateisystem fifofs implementiert

• Message Queues (Nachrichtenwarteschlangen) im Rahmen der UNIX System V IPC-Mechanismen eingeführt, Bedeutung gesunken

• Message Queue definiert Kommunikationskanal, über den mehrere Senderund mehrere Empfänger-Prozesse, die nicht miteinander verwandt sein müssen, typisierte Nachrichten variabler Länge kommunizieren können

• Message Queues besitzen eindeutigen Bezeichner aus dem KeyNamensraum, geöffnete Message Queue wird intern über Integer-Id bezeichnet

• Nachricht besteht aus einem Integer-Nachrichtentyp und variabel langem Nachrichteninhalt. Festlegung der Bedeutung von Typ und Inhalt ist den Prozessen vorbehalten.

• Message Queue hält Berechtigungen zur Zugriffskontrolle.

• Anzahl und Puffergröße der Message Queues werden bei der Systemgenerierung festgelegt.

Anonyme Pipes

• Semantik ähnlich wie UNIX anonyme Pipes

Named Pipes

• geht über die UNIX-Semantik teilweise hinaus: bidirektionaler Kommunikationskanal für mehrere Sende-Prozesse/Threads und einen Empfänger (Server-Prozess), auch auf verschiedenen Windows-Rechnern im Netzwerk

Mailslots

• Für jeden Mailslot gibt es einen Empfänger (den Erzeuger des Mailslots) und mehrere mögliche Sender. Wird derselbe Mailslot-Name für mehrere Mailslots auf verschiedenen Rechnern verwendet, so werden gesendete Nachrichten an allen diesen Mailslots zugestellt.

• Prozesse müssen kommunizieren können. Die grundlegenden Kommunikationsmöglichkeiten basieren auf der gemeinsamen Benutzung von Speicher (Sharing) sowie dem Nachrichtenaustausch.

• Kommunikation von Ereignissen (Signalisierung) wurde am Beispiel UNIX erläutert

• Grundlagen der nachrichtenrichtenorientierten Kommunikation wurden vorgestellt und am Beispiel der UNIX Pipes, Named Pipes und Message Queues verdeutlicht

• Ein grundlegendes Problem bei der Benutzung exklusiv benutzbarer Betriebsmittel - das sogenannte Deadlock-Problem.

• Ein Deadlock wird auch als Systemverklemmungszustand bezeichnet.

• Untersuchungen zu Deadlocks nehmen breiten Raum in der frühen Betriebssystem-Literatur ein.

Ziel hier: Kennenlernen von Methoden zur Erkennung, Behebung, Vermeidung und Verhinderung von Deadlocks

Zwei Prozesse A und B wollen je eine von einem Scanner eingelesene Datei ausdrucken

Das System besitze genau einen Drucker und genau ein Scanner

Verhalten:

Beide Prozesse sind blockiert und bleiben es für immer

Eine solche Situation heißt Deadlock. Eine genauere Definition folgt.

Deadlocks treten auch in vielen anderen Situationen auf, z.B. beim Sperren von Datensätzen in Datenbanken

Betriebsmittel (BM):

• Einheiten, auf die ein Zugriff erteilt werden kann

• Betriebsmittel können HW- oder SW-Komponenten sein

• Ein Betriebsmittel(typ) kann in mehreren identischen Instanzen oder Einheiten vorliegen

• Ein Betriebsmittel heißt unterbrechbar, wenn es einem Prozess ohne nachteilige Auswirkungen wieder entzogen werden kann, ansonsten heißt es ununterbrechbar

Beispiele:

• Arbeitsspeicher: unterbrechbares BM Kann Prozessen durch Auslagerung entzogen werden. Prozesse können nach Wiedereinlagerung ihre Arbeit ohne Wiederholung (resume) fortsetzen.

• Drucker: ununterbrechbares BM

Schritte zur Benutzung eines Betriebsmittels:

• Anfordern des BMs

• Benutzen des BMs

• Freigeben des BMs

Falls BM angefordert wird aber nicht verfügbar ist, muss der anfordernde Prozess warten. Warten kann durch Blockieren oder durch Busy Waiting realisiert sein.

Form einer BM-Anforderung ist in konkreten Systemen sehr unterschiedlich, u.U. auch BM-Typ-abhängig

• Typisch: open(bm)

Bewilligung einer Betriebsmittelanforderung heißt auch (Betriebsmittel-) Zuteilung. Prozess wird durch Zuteilung Inhaber des Betriebsmittels.

Eine Menge von Prozessen befindet sich in einem Deadlock-Zustand, falls jeder Prozess der Menge auf ein Ereignis wartet, das nur ein anderer Prozess der Menge auslösen kann.

Man sagt auch:

Die Prozesse sind in einen Deadlock verstrickt.

=> Da alle Prozesse warten, kann keiner jemals ein Ereignis erzeugen, auf das einer der anderen wartet. Alle Prozesse warten also für immer.

1. Bedingung des wechselseitigen Ausschlusses: Jedes Betriebsmittel ist entweder von genau einem Prozess belegt oder frei

2. Belegungs- / Anforderungs-Bedingung: Prozesse, die bereits aufgrund früherer Anforderungen Inhaber von Betriebsmitteln sind, können weitere Betriebsmittel anfordern

3. Ununterbrechbarkeitsbedingung: Zugeteilte Betriebsmittel können nicht entzogen werden, sondern müssen durch den Inhaber explizit freigegeben werden

4. Zyklische Wartebedingung: Es muss eine zyklische Kette aus zwei oder mehr Prozessen existieren, so dass jeder Prozess ein Betriebsmittel anfordert, das vom nächsten Prozess in der Kette belegt ist

Alle vier Bedingungen müssen gleichzeitig vorliegen. Falls EINE der Bedingungen nicht zutrifft, ist kein Deadlock möglich.

3 Prozesse: A, B, C

3 Betriebsmittel: R, S, T

Das Betriebssystem kann jeden nicht blockierten Prozess zu jedem Zeitpunkt zur Ausführung auswählen

Im Falle einer sequentiellen Ausführung (z.B. A, B, C) entsteht kein Deadlock, aber es erfolgt auch keine Nebenläufigkeit. Multiprogramming ist aber notwendig.

Mit Betriebsmittelzuteilungsgraphen kann man erkennen, ob eine Folge von Belegungen/Freigaben zu einer Deadlock-Situation führt:

• Ein Deadlock liegt genau dann vor, wenn der Graph einen Zyklus enthält

Vier grundsätzliche Strategien zum Umgang mit Deadlocks:

• Ignorieren des Problems

• Erkennung und Behebung

• Dynamische Vermeidung durch vorsichtige Betriebsmittelzuteilung (Deadlock Avoidance)

• Verhinderung durch konzeptionelle Maßnahmen, die eine der vier Bedingungen für einen Deadlock nie eintreten lassen (Deadlock Prevention)

Diese Strategien werden im folgenden untersucht

Vier grundsätzliche Strategien zum Umgang mit Deadlocks:

• Ignorieren des Problems

• Erkennung und Behebung

• Dynamische Vermeidung durch vorsichtige Betriebsmittelzuteilung (Deadlock Avoidance)

• Verhinderung durch konzeptionelle Maßnahmen, die eine der vier Bedingungen für einen Deadlock nie eintreten lassen (Deadlock Prevention)

Diese Strategien werden im folgenden untersucht

• Standpunkt: "Deadlocks sind ein theoretisches Problem und für praktische Fälle ohne Bedeutung"

• "Optimistischer" Ansatz

• "Wahrscheinlichkeit für einen Deadlock ist kleiner als für andere negative Ereignisse, die einem Prozess widerfahren können".

Beispiel: BSD UNIX

• In UNIX können Deadlocks auftreten, die weder erkannt geschweige denn automatisch behoben werden:

  • Prozesstabelle ist endlich: fork kann misslingen, wenn kein Eintrag mehr frei ist Aber: In realen Systemen praktisch nicht zu beobachten

  • Analoge Beispiele mit anderen Kerntabellen, wenn diese statisch angelegt werden, z.B. Tabelle der geöffneten Dateien oder Buffer Pool

Engl.: Deadlock Detection and Resolution (Recovery)

Vorgehensweise:

• Das Auftreten von Deadlocks wird vom Betriebssystem nicht verhindert

• Es wird versucht, Deadlocks zu erkennen und anschließend zu beheben

Betrachtet werden im folgenden:

• Deadlock-Erkennung mit einem Betriebsmittel je Klasse (Einfacher Fall)

• Deadlock-Erkennung mit mehreren Betriebsmitteln je Klasse (Allgemeiner Fall)

• Verfahren zur Deadlock-Behebung

Annahme: Es gebe genau ein Betriebsmittel in jeder Klasse, d.h. genau eine Instanz von jedem Typ

Algorithmus:

• Führe den Betriebsmittelanforderungsgraphen zur Laufzeit

• Zeitpunkt der Prüfung des Graphen:

  • Bei jeder Anforderung (Frühe Erkennung)

  • Nach n Zeiteinheiten (Weniger Rechenzeit)

  • Wenn Prozessorauslastung unter einen Schwellwert sinkt (Prozesse evtl. in Deadlock verstrickt)

Enthält der Graph mindestens einen Zyklus, so liegt ein Deadlock vor. Verwende dazu Algorithmus der Graphentheorie zur Zyklus-Erkennung in gerichteten Graphen (wird hier nicht behandelt). Jeder Prozess im Zyklus ist blockiert.

Wende ein Verfahren zur Behebung des Deadlocks an

1. Deadlock-Behebung durch Unterbrechung

• Meistens schwierig bis unmöglich, da eigentlich Ununterbrechbarkeit der BM gegeben ist

2. Deadlock-Behebung durch teilweise Wiederholung

3.Deadlock-Behebung durch Prozessabbruch

• Voraussetzung: Regelmäßiges Erzeugen von sog. Checkpoints (Wiederaufsetzungspunkten) von Prozessen in Dateien. Checkpoint enthält neben Prozesszustand auch die aktuelle Belegung der Betriebsmittel durch ihn.

• Im Falle eines Deadlocks wähle einen Prozess aus, dessen belegte BM benötigt werden, und setze ihn auf einen Checkpoint zurück, zu dem er die benötigten BM noch nicht inne hatte.

• Die Arbeit dieses Prozesses seit diesem Checkpoint ist verloren

• Falls der erneut gestartete Prozess die BM wieder anfordert, muss er blockieren, bis die BM verfügbar sind

• Beispiel: Transaction Abort in Datenbank nach Deadlock-Situation

• Härtestes aber einfachstes Verfahren, einen oder mehrere der in den Deadlock verstrickten Prozesse abzubrechen, bis der Zyklus aufgelöst ist

• Alternativ kann anderer Prozess abgebrochen werden, um die von ihm belegten BM freizubekommen, wenn dadurch Prozesse im Zyklus fortfahren können

• Soweit wie möglich sollten Prozesse abgebrochen werden, die ohne Seiteneffekte erneut gestartet werden können

• Beispiel: Compilation

Annahmen bisher: Prozesse fordern die benötigten BM auf einmal an

In den meisten realen Systemen werden Betriebsmittel jedoch nacheinander angefordert. Betriebssystem muss dynamisch eine Entscheidung über Zuteilung treffen.

Durch sorgfältige Zuteilung soll vermieden werden, dass Deadlock auftritt (Vermeiden eines Zyklus)

Die wichtigsten Algorithmen zur Deadlock-Vermeidung basieren auf Konzept der sicheren Zustände. Dabei werden weiter Informationen über zukünftige Betriebsmittelanforderungen benötigt.

1. Betriebsmittel-Pfade (Graphische Veranschaulichung)

2. Sichere und unsichere Zustände

3. Der Banker's Algorithmus für eine BM-Klasse

4. Der Banker's Algorithmus für mehrere BM-Klassen

Ein Zustand heißt sicher, wenn er kein Deadlock-Zustand ist und es eine Möglichkeit gibt, alle vorliegenden Anforderungen zu erfüllen, in dem die Prozesse in geeigneter Reihenfolge ausgeführt werden, ansonsten heißt er unsicher.

• Deadlock-Vermeidung durch sorgfältige Betriebsmittelzuteilung ist unter den gemachten Voraussetzungen möglich

• Voraussetzungen sind allerdings oft nicht realistisch, da Prozesse ihre zukünftigen Betriebsmittelanforderungen kennen müssen

• In der Praxis daher selten anwendbar

• Deadlocks sind ein Problem in jedem Betriebssystem aber auch in nebenläufigen Anwendungssystemen

• Deadlocks treten auf, wenn einer Menge von Prozessen jeweils exklusiv ein Betriebsmittel zugeteilt ist, und alle ein Betriebsmittel anfordern, das bereits von einem anderen Prozess der Menge belegt ist. Alle Prozesse sind blockiert, keiner kann jemals fortgeführt werden.

• Deadlocks können durch vier notwendige Bedingungen charakterisiert werden:

  • 1. Bedingung des wechselseitigen Ausschlusses

  • 2. Belegungs- / Anforderungs-Bedingung

  • 3. Ununterbrechbarkeitsbedingung

  • 4. Zyklische Wartebedingung

• Deadlocks können vermieden werden, in dem überprüft wird, ob der nachfolgende Zustand sicher ist oder nicht

  • Zustand ist sicher, wenn es Folge von Ereignissen gibt, so dass alle Prozesse ihre Ausführung beenden können

  • In unsicherem Zustand gibt es keine Garantie dafür

  • Der Banker's Algorithmus vermeidet Deadlocks, in dem er Anforderungen zurückstellt, die das System in einen unsicheren Zustand überführen würden

• Deadlocks können durch konstruktive Verfahren verhindert werden

  • z.B. durch Vorabbelegen aller Betriebsmittel

  • durch die geordnete Betriebsmittelbenutzung

1. Bedingung des wechselseitigen Ausschlusses

2. Belegungs- / Anforderungs-Bedingung

3. Ununterbrechbarkeitsbedingung

4. Zyklische Wartebedingung

Falls Betriebsmittel einem Prozess nie exklusiv zugeteilt werden, kann kein Deadlock entstehen.

• Beispiel: Spooling-System verhindert auch Deadlocks bzgl. des Druckers:

  • Prozesse legen ihre Druckaufträge in einem Spooling-Verzeichnis ab

  • Der Spooler-Dämon ist der einzige Prozess, der den realen Drucker anfordern kann

  • Der Spooler-Dämon benötigt keine anderen (hier wesentlichen) Betriebsmittel

Ziele:

• Zuteilung eines BM möglichst vermeiden

• So wenige Prozesse wie möglich sollten ein BM tatsächlich anfordern

Falls alle Betriebsmittel eines Prozesses vor Beginn der Ausführung zugeteilt werden, kann kein Deadlock entstehen (Preclaiming)

Effekt: Falls alle erforderlichen BM zur Verfügung stehen, können sie dem Prozess zugeteilt werden, und der Prozess kann seine Berechnung vollständig ausführen. Andernfalls wird dem Prozess keines der BM zugeteilt, und der Prozess muss auf die Zuteilung warten.

Probleme:

• Prozesse müssen ihre BM-Anforderungen vor Beginn kennen

• Schlechte Betriebsmittelausnutzung, da sie während der gesamten Laufzeit belegt werden

Beispiel: Job Control Language (JCL) für den Stapelbetrieb bei Großrechnern

Falls einem Prozess während der Ausführung zugeteilte Betriebsmittel entzogen werden können, kann kein Deadlock entstehen

Praktisch kaum anwendbar

Falls die zyklische Wartebedingung nicht eintreten kann, kann kein Deadlock entstehen

Hauptansatz: geordnete Betriebsmittelbenutzung:

• Lineare Ordnung auf allen Betriebsmitteltypen eingeführt: T1 < T2 < ... < Tm Prozesse können Betriebsmittel nur gemäß der aufsteigenden Ordnung anfordern

• Benötigt ein Prozess mehrere Exemplare eines Typs, müssen sie zusammen in einer Anforderung auftreten

• Der entstehende Betriebsmittelzuteilungsgraph ist zyklusfrei (Beweis durch Widerspruch): Damit ist Deadlock ausgeschlossen

Ansatz ist von hoher praktischer Bedeutung

Beispiel: Deadlock-Verhinderung innerhalb des BS-Kerns

Deadlock-Verhinderung durch Negieren der notwendigen Bedingungen von Deadlocks ist möglich.

Der Speicherverwalter ist der Teil des Betriebssystems, der den Arbeitsspeicher verwaltet

Aufgaben:

• Verwaltung von freien und belegten Speicherbereichen

• Zuweisung von Speicherbereichen an Prozesse, wenn diese sie benötigen (Allokation)

• Freigabe nach Benutzung oder bei Prozessende

• Durchführung von Auslagerungen von Prozessen (oder Teilen) zwischen Arbeitsspeicher und Hintergrundspeicher (Platte) bei Speicherengpässen

• Verfahren mit fester Zuordnung von Speicher an Prozesse

• Zuordnung ist keinen Veränderungen während der Laufzeit des Systems oder der Prozesse unterworfen

• Nicht-statische Speicherverwaltung heißt auch dynamische Speicherverwaltung

• Im folgenden für den historischen Einprogramm- und Mehrprogrammbetrieb betrachtet

• Heute noch in einfachen Echtzeitanwendungen üblich (z.B. Steuerung einfacher Maschinen)

• Nur ein Prozess befindet sich zu einem Zeitpunkt im Speicher. Zuweisung des gesamten Speichers an diesen Prozess

• Einfache Mikrocomputer: Speicheraufteilung zwischen einem Prozess und dem Betriebssystem Typische Alternativen

Ziel: Bessere Ausnutzung der CPU

• Aufteilung des Speichers in feste Partitionen bei Systemstart. In jede Partition kann ein Programm geladen werden.

• Programme können für eine Partition gebunden sein und sind dann nur in dieser lauffähig

• Freie Auswahl einer Partition verlangt Lösung des sog. Relokationsproblems (Verschiebbarkeit), d.h. Anpassung aller (absoluten) Adressen des Programms in Abhängigkeit von der Ladeadresse

• Mögliche Lösung des Relokationsproblems: Loader addiert die Ladeadresse auf alle Adressen gemäß eines vom Binder erstellten Adressverzeichnisses des Programms

Mehrprogrammbetrieb führt zum Schutzproblem:

• Programme können aufgrund der absoluten Adressierung Speicherbereiche anderer Benutzer lesen und schreiben (unerwünscht !)

• Lösung des Schutzproblems in IBM /360:

• Jedem 2kB-Block des Arbeitsspeichers wird ein 4-Bit Schutzcode (protection key) als Schloss zugeordnet

• Jeder Prozess besitzt einen ihm im Programmstatuswort (PSW) zugeordneten Schlüssel, der beim Zugriff auf einen Block passen muss, ansonsten Abbruch

• Nur das Betriebssystem kann Schutzcodes von Speicherblöcken und Schlüssel von Prozessen ändern

→ Fazit: Ein Benutzerprozess kann weder andere Benutzerprozesse noch das Betriebssystem stören

Alternative Vorgehensweise zur Lösung des Schutzproblems wie des Relokationsproblems: Ausstattung der CPU mit zwei zusätzlichen Registern, die Basisregister und Grenzregister genannt werden (base and bound register)

Weiterer Vorteil eines Basisregisters zur Relokation: Verschieblichkeit des Programms nach Programmstart wird möglich

• Bei klassischen Timesharing-Systemen gibt es normalerweise nicht genügend Hauptspeicher, um Prozesse aller Benutzer aufzunehmen

• Swapping beinhaltet das Verschieben von Prozessen vom Hauptspeicher auf Platte (Auslagern) und umgekehrt (Einlagern)

• Im Hauptspeicher zu jedem Zeitpunkt nur eine Teilmenge der Prozesse, diese sind aber vollständig repräsentiert (im Gegensatz zu virtuellem Speicher)

• Die restlichen (möglicherweise auch rechenwilligen) Prozesse werden in einem Bereich im Hintergrundspeicher abgelegt. Dieser Bereich heißt Swap-Bereich (Swap Area)

• Beispiel: Im Unix vor Einführung der virtuellen Speicherverwaltung genutzt

• Mehrprogrammbetrieb kann in variablen Partitionen erfolgen, d.h.: Anzahl, Anfangsadresse und Länge der Partitionen und damit der eingelagerten Prozesse ändern sich dynamisch

• Ein zusammenhängender Speicherbereich variabler Länge heißt auch Speichersegment oder einfach Segment

• Ziele variabler Partitionen:

  • Anpassung an die tatsächlichen Speicheranforderungen

  • Vermeidung von Verschwendung

Zerstückelung von Freispeicher zwischen den belegten Segmenten wird externe Fragmentierung genannt

Abhilfe: Alle unbelegten Speicherbereiche können durch Verschiebung der belegten Segmente zu einem einzigen Bereich zusammengefasst werden (-> Speicherverdichtung oder Kompaktifizierung)

Speicherbedarf eines Prozesses kann sich im Verlaufe ändern (i.d.R. wachsen)

Prozess stellt dynamische Speicheranforderungen, z.B. zur Aufnahme von neu erzeugten Objekten auf dem Heap

Behandlung dynamischer Speicheranforderungen:

• Belegen angrenzender "Löcher", falls vorhanden

• Verschiebung von anderen Prozessen, falls möglich

• Auslagern von anderen Prozessen

• "Raum zum Wachsen": Bei der ersten Speicherbelegung vorab zusätzlichen Speicherplatz alloziieren

• Speicherverwaltung mit Bitmaps

• Speicherverwaltung mit verketteten Listen

• Speicherverwaltung mit dem Buddy-System

Arbeitsweise:

• Der zur Verfügung stehende Speicher wird in Einheiten fester Länge unterteilt (Granularität einige Worte bis einige KB)

• Jeder Speichereinheit wird ein Bit in einer Bitmap zugeordnet: 0 → Einheit ist frei, 1 → Einheit ist belegt

• Je kleiner die Einheit, je größer die Bitmap

• Je größer die Einheit, je mehr Speicher wird verschwendet, da die letzte "angebrochene" Einheit voll alloziiert werden muss

• Hauptproblem: Belegen eines Speicherbereichs von k Einheiten erfordert Durchsuchen der Bitmap nach einer Folge von k Null-Bits. Aufwendig!

• Für Hauptspeicherverwaltung daher selten eingesetzt

Arbeitsweise:

• Jedem alloziierten und jedem freien Speicherbereich wird ein Listenelement zugeordnet

• Segmente dürfen variabel lang sein

• Jedes Listenelement enthält Startadresse und Länge des Segments sowie den Status (zugeordnet, frei)

• Freie Segmente können auch in separater Liste geführt werden, der sog. Freiliste. Die Freiliste kann in dem verwalteten freien Bereichen sein (→ kein zusätzlicher Speicher)

• Segmentliste kann nach Anfangsadressen geordnet sein → Vorteil: freiwerdendes Segment kann mit benachbartem freien Bereich zu einem freien Segment "verschmolzen" werden

• Freiliste kann alternativ nach der Größe des freien Bereichs geordnet sein → Vorteil: Vereinfachung beim Suchen nach einem freien Bereich bestimmter Länge

Voraussetzungen:

• Liste der Segmente nach Anfangsadressen geordnet

• Geforderte Speichergröße bekannt

Es gibt

• First Fit: Durchsuche Freiliste, bis ein freies Segment hinreichender Größe gefunden ist. Zerlege den freien Bereich in ein Segment der geforderten Größe und ein neues freies Segment für den übrig bleibenden Rest. Kurze Suchzeit.

• Rotating First Fit oder Next Fit: Variante von First Fit. Anstelle von vorn zu suchen, beginne Suche an der nachfolgenden Stelle, an der bei letzten Durchlauf ein Segment belegt wurde.

• Best Fit: Durchsuche die gesamte Liste, wähle das kleinste für die Anforderung gerade ausreichende freie Segment und spalte dieses. Langsam. Neigt zur ungewollten Erzeugung vieler kleiner Freisegmente (Fragmentierung)

• Worst Fit: Wähle das größte freie Segment und spalte dieses. Vermeidet vieler kleiner Freisegmente, aber keine gute Idee.

Arbeitsweise:

• Freie und belegte Speicherbereiche haben ausschließlich Längen, die 2-er Potenzen sind

• Da nur bestimmte Längen auftreten, wird von Speicherblöcken (anstelle von Segmenten) gesprochen

• Die maximale Blocklänge Lmax entspricht der größten 2-er-Potenz kleiner gleich dem verfügbaren Speicher, z.B. Lmax = 222 bei 4 MB oder 6 MB

• Es kann eine minimale Blocklänge größer 20 = 1 Byte geben, z.B. Lmin = 26 = 64 Bytes

• Eine Speicheranforderung wird auf die nächst mögliche 2-er-Potenz aufgerundet, z.B.: angefordert 70 KB, belegt 128 KB

• Für jede der verwalteten Blocklängen zwischen Lmin und Lmax wird eine separate Freiliste gehalten

50%-Regel (Knuth): Sind im Mittel n Prozesse im Speicher, so gibt es im Mittel n/2 freie Bereiche. Ursache ist, dass zwei benachbarte Freibereiche zu einem zusammengefasst werden

• Kein freier Block der gesuchten Länge: Halbiere einen Block der nächsthöheren 2-er-Potenz in 2 freie Blöcke der gesuchten Länge. Diese werden Buddies genannt (deutsch: Kumpel)

• Freigabe eines Blocks der Länge 2k : wenn sein Buddy bereits ein freier Block ist, mit diesem zu einem neuen freien Block der Länge 2k+1 vereinen.

• Es lassen sich nicht zwei beliebige benachbarte Blöcke gleicher Länge 2k zusammenfassen!

Die Entscheidung ist einfach aufgrund der Adresse der freien Blöcke möglich:

Vorteile:

• Bei Speicheranforderung insgesamt schnelles Auffinden oder Erzeugen eines freien Blocks

• Bei Freigabe muss nur eine Freiliste durchsucht werden. Falls Buddy bereits frei ist, einfaches Verschmelzen zu einem größeren Block.

Nachteile:

• Ineffizient in der Speicherausnutzung, da immer auf die nächste 2-er-Potenz aufgerundet werden muss

• Diese Verschwendung wird als interne Fragmentierung bezeichnet, da sie innerhalb des alloziierten Speicherbereichs auftritt (im Gegensatz zur externen Fragmentierung)

Ja

Sei s die mittlere Größe eines Prozesses, und k*s sei die mittlere Größe eines Freibereichs für einen Faktor k, der abhängig vom Algorithmus ist. Dann gilt für den ungenutzten Anteil f des Speichers:

f = k / (k+2)

Beispiel: Sei k = 0.5. Dann werden 20% des Speicherplatzes für Freibereiche verbraucht

• Im Hauptspeicher wird zu jedem Zeitpunkt nur eine Teilmenge der Prozesse gehalten. Die restlichen Prozesse sind in einen Swap-Bereich auf Platte ausgelagert.

• Alle Prozesse im Hauptspeicher sind vollständig repräsentiert

• Es wurden Verfahren zur Speicherverwaltung für derartige Systeme besprochen:

  • Verwaltung mittels Bitmaps

  • Verwaltung mittels verketteter Listen

  • Buddy-System

• Es wurden Strategien zur Speicherverwaltung besprochen:

  • First Fit

  • Rotating First Fit

  • Best Fit

Die Größe eines einzelnen Prozesses kann die Größe des insgesamt zur Verfügung stehenden Speichers übersteigen

→ Swapping ist keine Lösung mehr

• Betriebssystem hält "gerade in Benutzung" befindlichen Teile eines Programms im Hauptspeicher, Rest auf Hintergrundspeicher

• Dieser Ansatz wird virtueller Speicher genannt

• Virtueller Speicher und Mehrprogrammbetrieb passen gut zueinander: Werden Teile eines blockierten Prozesses eingelagert, kann der Scheduler den Prozessor einem anderen (rechenwilligen) Prozess zuordnen

• Paging: eindimensionaler virtueller Speicher. Heute am stärksten verbreitet

• Segmentierung: zweidimensionaler virtueller Speicher

Die von den Instruktionen eines Programms generierten Adressen werden virtuelle Adressen genannt. Sie bilden zusammen den (virtuellen) Adressraum des Prozesses, der das Programm ausführt

Speicherverwaltungseinheit (Memory Management Unit, MMU):

• wandelt virtuelle Adressen in reale (physikalische) Adressen um

• reale Adressen werden dann für den Zugriff zum Arbeitsspeicher benutzt

• Abbildung wird abstrakt auch als Speicherfunktion bezeichnet

• Bei heutigen Mikroprozessoren ist die Speicherverwaltungseinheit in den Prozessorchip integriert

Virtueller Adressraum ist in Einheiten fester Länge unterteilt, diese heißen Seiten (Pages)

Physikalischer Speicher wird ebenfalls in Einheiten dieser Länge unterteilt, diese heißen Seitenrahmen (Page Frames, Kacheln)

Transfer zwischen Hauptspeicher und Hintergrundspeicher erfolgt grundsätzlich in Einheiten von Seiten.

Heute typische Größen:

• virtueller Adressraum:

  2^32 Bytes (4 GB) basierend auf 32-Bit Adressen,

  2^48 Bytes (256 TB) basierend auf 64-Bit Adressen (AMD64, Intel64)

• physikalischer Arbeitsspeicher: i.d.R. kleiner, 2-6 GB für Arbeitsplatzrechner, Tendenz steigend

• Seiten / Seitenrahmen: typisch 4 KB oder 8 KB

Die abstrakte Speicherfunktion kann bildlich durch eine Tabelle repräsentiert werden, bezeichnet als Seitentabelle

Die Seitentabelle ordnet jeder Seite des virtuellen Adressraums einen Seitenrahmen des Hauptspeichers oder ein Kennzeichen zu, dass die Seite sich nicht im Hauptspeicher befindet (nicht eingelagert ist). Dieses Kennzeichen wird Present/Absent-Bit genannt

Benennt ein Programm eine virtuelle Adresse, deren zugehörige Seite nicht eingelagert ist, so erzeugt die MMU eine Unterbrechung der CPU. Diese Situation wird als Seitenfehler (Page Fault) bezeichnet.

• Die Behandlung eines Seitenfehlers besteht prinzipiell in der Einlagerung der fehlenden Seite vom Hintergrundspeicher in einen freien Seitenrahmen des RAMs

• Einlagerung als Reaktion auf Seitenfehler wird als Demand Paging bezeichnet

• Liegt kein freier Seitenrahmen vor, muss ein solcher gewonnen werden. I.d.R. hält das Betriebssystem einen Vorrat an freien Rahmen vor. (Algorithmen für die Auswahl zu ersetzender Seiten werden detailliert besprochen)

• Falls die zu ersetzende Seite während ihrer Lebenszeit im Speicher verändert wurde (als Dirty Page bezeichnet), wird sie auf die Platte zurückgeschrieben (Update). Der belegte Seitenrahmen ist danach frei.

• Falls die zu ersetzende Seite nicht verändert wurde (enthält z.B. Programmcode), ist kein Zurückschreiben erforderlich

Bisher wurde die prinzipielle Arbeitsweise besprochen

Für reale Systeme sind die folgenden Aspekte wichtig:

• Jedem Prozess ist ein eigener virtueller Adressraum zugeordnet. Es sind also viele Seitentabellen zu verwalten.

• Behandlung großer virtueller Adressräume:

  • Schon bei 32-Bit-Adressen und Seitengröße 4 KB -> Seitentabelle hat 1 Mio Einträge !

  • 64-Bit-Adressen bereits teilweise eingeführt !

• Adressräume können "dünn besetzt" sein, d.h. im Verhältnis zur möglichen Größe werden an verschiedenen Stellen des Adressraums nur "kleine" Bereiche genutzt

-> 1. Problem: Organisation von Seitentabellen

Die Umrechnung virtueller Adressen in reale muss sehr schnell geschehen:

• Jede Speicherreferenz muss übersetzt werden

• ca. 2 Speicherreferenzen je Instruktion

• 100 MIPS Prozessorleistung entsprechen 10ns je Instruktion (ohne Berücksichtigung von Pipelining, usw.). Es bleiben also nur wenige Nanosekunden für die Adressumsetzung

Hardware-Unterstützung unumgänglich

-> 2. Problem: Schnelle Adressumsetzung

Alle Einträge der Seitentabelle eines Prozesses werden vollständig in Hardware-Registern des Prozessors gehalten

Bei Prozesswechsel werden die Hardware-Register mit der im Hauptspeicher gehaltenen Kopie der Seitentabelle geladen

Es sind dann keine Speicherreferenzen auf Seitentabellen während der Prozessausführung notwendig

Vorteil: Schnell zur Laufzeit

Nachteile:

• zu teuer bei großer Seitentabelle

• Ladevorgang der Hardwareregister bei Prozesswechsel zeitaufwendig

Die Seitentabelle eines Prozesses wird ständig im Hauptspeicher gehalten

Es wird nur ein Hardware-Register benötigt, das einen Zeiger auf den Anfang der Seitentabelle im Hauptspeicher enthält

Bei Prozesswechsel wird das Hardware-Register auf die Seitentabelle des auszuführenden Prozesses gesetzt

Für die Umrechnung jeder Speicheradresse sind ein oder mehrere zusätzliche Speicherreferenzen auf die Seitentabelle des Prozesses während der Prozessausführung notwendig

Vorteil: Fast kein Hardware-Aufwand.

Nachteil: zu langsam

Im folgenden werden einige übliche Lösungen heutiger Rechensysteme aus diesem Spektrum aufgezeigt

• Eine mehrstufige Seitentabelle realisiert die Speicherfunktion in mehreren Schritten. Sie besitzt eine Baumstruktur. Erst die letzte Stufe von Seitentabellen enthält Rahmenadressen von "Nutz"daten, alle vorangehenden enthalten Rahmenadressen von Seitentabellen der nächsten Stufe.

• Nicht alle Seitentabellen des Adressraums müssen existieren. Hierdurch erfolgt die Behandlung von nicht genutzten Bereichen des Adressraums (Im Beispiel sind nur 4 Seitentabellen vorhanden, eine erster Stufe, drei zweiter Stufe).

• Nicht alle definierten Seitentabellen müssen gleichzeitig im Hauptspeicher sein. Sie können z.B. selbst ausgelagert sein

• Eine Erweiterung auf mehr als zwei Stufen ist analog möglich

Verwendung einer n-stufigen Seitentabelle ohne Hardware-Unterstützung würde n zusätzliche Speicherreferenzen je Referenz erfordern

Schnelle Adressumsetzung ist nur durch Hardware-Unterstützung möglich

Kleiner Assoziativspeicher, auch Translation Lookaside Buffer (TLB) genannt, wird als Teil der MMU vorgesehen

Ein Eintrag im Assoziativspeicher beschreibt eine Seite des virtuellen Adressraums. Die gespeicherte Information entspricht dem entsprechenden Eintrag in der Seitentabelle:

• Virtuelle Seitennummer

• Physikalische Seitenrahmennummer

• Zugriffsrechte

• Modified - Bit

• Valid - Bit für den Eintrag selbst

Typisch: 8 - 64 Einträge, i.d.R. voll assoziativer Zugriff

Bei gegebener virtueller Adresse (Seitennummer, Offset) in der MMU erfolgt ein (paralleler) Vergleich der Seitenummer mit den Einträgen des TLB

• Die Seitennummer beinhaltet dabei alle Indexfelder im Falle mehrstufiger Seitentabellen im Arbeitsspeicher

Falls Eintrag für Seite vorhanden und Zugriffsrechte für den beabsichtigten Zugriff ausreichend, dann zugehörige Seitenrahmennummer wird für die Konkatenation mit dem Offset bereitgestellt (-> Bildung der physikalischen Speicheradresse)

Falls Eintrag vorhanden aber nur unzureichende Zugriffsrechte: dann liegt Schutzfehler vor (Abbruch)

Falls kein Eintrag vorhanden, dann MMU durchwandert i.d.R. eigenständig die (mehrstufigen) Seitentabellen im Arbeitsspeicher

• Wird ein Seitendeskriptor für die geforderte Seite gefunden, so ersetzt seine Information einen Eintrag im Assoziativspeicher, andernfalls wird ein Seitenfehler (Page Fault) angezeigt (s.o.)

• i.d.R. wird der am längsten nicht benutzte Eintrag gewählt (Alterungsinformation des TLB wird i.d.R. hardwaremäßig geführt)

• Falls dessen Modified-Bit gesetzt ist, wird das entsprechende ModifiedBit in der Seitentabelle im Arbeitsspeicher gesetzt

Der Anteil der Speicherreferenzen, die mit Hilfe des Assoziativspeichers aufgelöst werden können, wird Trefferrate oder Hitrate des TLB genannt

Je höher die Trefferrate, je besser die Performance

"Wildes" Springen im Programm und in den benutzten Daten ergibt eine Trefferrate nahe 0. Eine hohe Trefferrate ist nur im Falle eines guten Lokalitätsverhaltens des Prozesses möglich

Die effektive Adressübersetzungszeit Teff hängt ab von:

• mittl. Zugriffszeit THS auf die Seitentabelle im Hauptspeicher,

• Zugriffszeit TTLB auf den Assoziativspeicher,

• Trefferrate HTLB des TLB: