Grundbegriffe und Theorien

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

(Kernabstraktion)

Ein Prozess ist ein Programm in Ausführung (einschl. seiner aktuellen Werte des Programmzählers, der Register, Speichervariablen, Stack)

Ein Prozess besitzt einen privaten Adressraum

(Kernabstraktion)

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

(Kernabstraktion)

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

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

Anwender soll von komplexer Hardware abgeschrimt werden.

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

Diese Schnittstelle ist einfacher zu verstehen und langlebiger.

Sie wurde zur vermeidung von Wartezeiten für "teure" CPU während I/O-Vorgängen eingeführt.

Zu einem Zeitpunkt laufen mehrere Programme, Ressourcen werden so verzahnt, dass es bessere Auslastung gibt, Reihenfolge hängt von Prioritäten ab

Reale Prozessoren schaltet zwischen den virtuellen Prozessoren um.

Rechner bearbeitet eine Aufgabe nach der anderen, zu einem Zeitpunkt läuft ein Programm, diesem stehen dann alle Ressourcen zur Verfügung

Zeitscheibenverfahren

Vermeidet den Nachteil des Mehrprogrammbetriebs, Zeituhr läuft ab, neuer Prozess kann beginnen, für jede Interaktion wird CPU-Zeit zugeteilt, faire Verteilung, effizient

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

Schicht 5 Operateur

Schicht 4 Benutzerprogramme

Schicht 3 Ein-/ Ausgabeverwaltung

Schicht 2 Operateur-zu-Prozess-Kommunikation

Schicht 1 Speicher- und Trommelverwaltung

Schicht 0 Prozessorvergabe und Multiprogramming

Mikrokernel ist kleiner, langsamer und einfacher zu erweitern.

Wenn ein Dienst abstürzt, stürzt das gesamte System im monolithischen Kern ab.

• 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)

Umschaltungsvorgang heißt Prozesswechsel oder Kontextwechsel (Context Switch)

Prozesserzeugung, -umschaltung und -kommunikation sind teuer, Threads sind die Lösung:

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

Idee einer „parallel ausgeführten Programmfunktion“.

Ein Prozess ist ein sich in Ausführung befindliches Programm und besitzt einen privaten Adressraum.

Aber Prozesserzeugung, -umschaltung und -kommunikation sind teuer, daher wurde die billiger Nebenläufigkeit in einem Prozessadressraum eingeführt: Durch „Leichtgewichtsprozesse", sogenannte Threads.

Thread hat einen eigenen Prozessor-Context, Stack und kleinen privaten Datenbereich.

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

Umschaltungseinheit heißt Scheduler oder Dispatcher.

Scheduling Algorithmus legt Regeln fest.

Ablaufplaner, ist für die zeitliche Ablaufplanung der Prozesse zuständig.

Setzt Anfangspriorität der Prozesse fest, kann Prioritäten aufgrund des Prozessverhaltens ändern.

Scheduling der niederen Ebene wird dann häufig als Dispatching bezeichnet.

Rechnende Prozesse können suspendiert werden (Prozessorentzug); notwendig bei Echtzeit-Betriebssystemen

1. Round-Robin-Scheduling (RR)

2. Dynamisches Prioritäts-Scheduling

3. Mehrschlangen-Scheduling

4. Mehrschlangen-Feedback-Scheduling

5. Earliest-Deadline-First-Scheduling

(realistisch für heutige Rechensysteme)

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!

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

2. Shortest-Job-First (SJF)

3. Prioritäts-Scheduling (Prio)

(für Stapeljobs mit bekannten Bedienzeiten)

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.

Nutzer-bezogen:

• Kurze Antwortzeiten bei interaktiven Aufträgen

• Kurze Verweilzeiten für Stapelverarbeitungsaufträge

Betreiber-bezogen:

• Hoher Durchsatz (Anzahl der erledigten Aufträge pro Zeiteinheit)

• Hohe Auslastung (Anteil der Zeit im Zustand belegt)

• Fairness in der Behandlung aller Aufträge

• Geringer Aufwand für die Bearbeitung des Scheduling-Algorithmus selbst (Overhead! Als Overhead gelten in der elektronischen Datenverarbeitung Daten, die nicht primär zu den Nutzdaten zählen, sondern als Zusatzinformation zur Übermittlung oder Speicherung benötigt werden)

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

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:

• Gute Antwortzeiten für interaktive Prozesse.

Vorgehensweise:

• Zweistufiges Scheduling: Hintergrundspeicher-Hauptspeicher-Swapping

• Scheduling von im Hauptspeicher befindlichen Prozessen

Prozesserzeugung, -umschaltung und -kommunikation sind teuer, daher führt man billige Nebenläufigkeit in einem Prozessadressraum durch Leichtgewichtsprozesse ein.

Leichtgewichtsprozesse = Threads

Es gibt ein Betriebsmittel.

Zwei nebenläufige Prozesse wollen das gleiche Betriebsmittel benutzen, lesend und schreibend.

Sie stehen im Konflikt zueinander (auch Überlappend genannt).

Tun die das nicht werden sie unabhängig oder disjunkt gennant.

Zeitkritische Abläufe sind die Folge von Lese/Schreib-Operationen.

Wenn die Endzustände der Betriebsmittel (Endergebnisse der Datenbereiche) abhängig von der zeitlichen Reihenfolge der Lese/Schreib-Operationen sind, nennt man dies zeitkritische Abläufe (engl. race conditions).

(engl. critical section oder critical region)

Teil eines Programms, in dem auf gemeinsam benutzte Datenbereiche zugegriffen wird.

Kritische Abschnitte realisieren sogenante komplexe unteilbare oder atomare Operationen

(engl. mutual exclusion)

Verfahren, das verhindert, dass zu einem Zeitpunkt mehr als ein Prozess zugreift.

Ein Verfahren zum wechselseitigen Ausschluss vermeidet zeitkritische Abläufe.

Aktives warten ist nur auf Multiprozessor-Systemen sinnvoll

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)

1. Sperren aller Unterbrechungen

2. Sperrvariablen

3. Striktes Alternieren

4. Lösung von Peterson (brauchbar)

5. Test-and-Set-Instruktion (brauchbar)

Jeder Prozess sperrt vor Eintritt in seinen kritischen Abschnitt alle Unterbrechungen und lässt Unterbrechungen am Ende des kritischen Abschintts wieder zu.

Ist Unbrauchbar da man nicht sicherstellen kann (etwa wegen Programmierfehlern) das sie die Unterbrechungen auch wieder zulassen.

Jedem krit. Abschnitt wird eine Sperrvariable zugeordnet:

Wert 0 bedeutet "frei“

Wert 1 bedeutet "belegt“

Jeder Prozess prüft die Sperrvariable vor Eintritt:

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

Unbrauchbar da 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 !!)

Man hat 2 Prozesse: Prozess 1 und Prozess 0

Sie wechseln sich ab: 0,1,0,1,...

Unbrauchbar da Fortschrittsbedingung (3) verletzt werden kann, wenn ein Prozess wesentlich langsamer ist als der andere

Bevor ein kritischer Bereich betreten wird, ruft jeder Prozess eine Klasse auf, wo er eine Prozess Nummer zugeteilt kriegt (0 oder 1)

Er wartet (aktiv) bis die Klasse, die zum Eintriff in dem kritischen Bereich dient verlassen wurde.

Problem: Algorithmen, die nur auf atomaren Speicherzugriffen basieren, sind zu komplex

Eine Lösung durch Hardware-Unterstützung (Maschinenbefehl Test-and-Set)

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.

Es ist das standard auf praktisch allen Architekturen

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

Wir haben 2 Prozesse:

Prozess H = hohe Priorität

Prozess L = niedere Priorität

nach Scheduling-Regel soll H ausgeführt werden, wenn H rechenwillig ist.

1. H wird rechenwillig; L ist in seinem kritischen Abschnitt

2. H will ebenfalls in seinen kritischen Abschnitt

3. H wird ausgewählt (wegen hoher Priorität) und wartet aktiv für immer, da L seinen kritischen Abschnitt nicht freigeben kann, da er von H blockiert wird.

(Problem tritt auch beim passivem warten auf)

Dies ist eine Lösung für passives warten

Ein Mutex offeriert Operationen:

lock als Prolog-Operation zum Betreten des kritischen Abschnitts

unlock als Epilog-Operation beim Verlassen des kritischen Abschnitts.

Sie können als binäre Semaphore angesehen werden.

Atomarität bedeutet, dass Überprüfen des Wertes, Verändern des Wertes und sich Schlafen legen als eine einzige, unteilbare Operation ausgeführt werden.

Sie besteht aus:

Zähler = Anzahl der Prozesse

Operation P = Reservieren/Probieren

Operation V = Freigeben

Ein Prozess, der auf die Ressource zugreifen will, muss vorher die Operation P aufrufen, und danach, wenn er die Ressource nicht mehr benötigt, die Operation V . Bei jeder Reservierung wird der Zähler um 1 heruntergezählt, bei Freigabe wird er wieder um 1 erhöht.

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

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

Auch gennant: Problem des beschränkten Puffers

Es gibt Lösungsansätzte mit Semaphoren, Monitoren und 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 gleichzeitig essen wollen entsteht eine Deadlock oder Starvation, da es nicht genug Gabeln für jeden gibt.

Man hat einen Datenbestand auf dem gelesen und geschrieben werden kann.

Zu jedem Zeitpunkt dürfen entweder mehrere Leser oder ein Schreiber zugreifen.

Wenn ein Schreiber den Datenbestand ändert, während ein Leser ihn liest, ist der Datenbestand nicht konsistent/nicht aktuell.

Lösung mit Semaphore bevorzugt Leser (Schreiber muss theoretisch unendlich lang warten) also wäre die Fairness verletzt.

Eine zyklische Wartesituation zwischen mehreren Prozessen, wobei jeder beteiligte Prozess auf die Freigabe von Betriebsmitteln wartet, die ein anderer beteiligter Prozess bereits exklusiv belegt hat.

Auch Systemverklemmungszustand bezeichnet.

Ein Betriebsmittel heißt unterbrechbar (z.B. Arbeitsspeicher), wenn es einem Prozess ohne nachteilige Auswirkungen wieder entzogen werden kann, ansonsten heißt es ununterbrechbar (z.B. Drucker)

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

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.

1. Ignorieren ("Deadlocks sind ein theoretisches Problem und für praktische Fälle ohne Bedeutung")

2. Erkennung und Behebung (Auftreten wird nicht verhindert;

   Behebung durch Unterbrechung ist schwierig bis unmöglich;

   Behebung durch teilweise Wiederholung nur mit Checkpoints möglich;

   Bei der Behebung druch Prozessabbruch wird ein oder mehrere Prozesse in der Deadlock abgebrochen)

3. Dynamische Vermeidung durch vorsichtige Betriebsmittelzuteilung (Durch sorgfältige Zuteilung und dem Konzept der sicheren Zustände(Information über zukünftige Betreibsmittelanforderungen, daher selten anwendbar))

4. Verhinderung durch konzeptionelle Maßnahmen, die eine der vier Bedingungen für einen Deadlock nie eintreten lassen.(Durch Negieren der notwendigen Bedingungen von Deadlocks:

   Wechselseitiger Ausschluss -> Spooling

   Belegung-/Anforderungs-Bed. -> Belegen aller BM zu Beginn

   Ununterbrechbarkeitsbed. -> Betriebsmittelentzug

   Zyklische Wartebedingung -> Geordnete Betriebsmittelnutzung)

Der Teil des Betriebssystems, der den Arbeitsspeicher verwaltet.

Statische Speicherverwaltung ist ein Verfahren mit fester Zuordnung von Speicher an Prozesse.

Nicht-statische Speicherverwaltung heißt auch dynamische Speicherverwaltung.

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

Das Ziel ist eine bessere Ausnutzung der CPU. Aufteilung des Speichers in feste Partitionen bei Systemstart. In jede Partition kann ein Programm geladen werden.

Es kann zu Schutzproblemen führen: Programme können aufgrund der absoluten Adressierung Speicherbereiche anderer Benutzer lesen und schreiben.

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

Ausstattung der CPU mit zwei zusätzlichen Registern (Basisregister und Grenzregister)

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 befinden sich zu jedem Zeitpunkt nur eine Teilmenge der Prozesse. Die restlichen (möglicherweise auch rechenwilligen) Prozesse werden in einem Bereich im Hintergrundspeicher abgelegt. Dieser Bereich heißt Swap-Bereich (Swap Area)

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

Das Ziel ist die Anpassung an die tatsächlichen Speicheranforderungen und die 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)

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.

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

Segmentierung: zweidimensionaler virtueller Speicher

Speicherverwaltungseinheit welche virtuelle Adressen in reale (physikalische)Adressen umwandelt.

#include <stdio.h>

#include <stdlib.h>

#include <pthread.h>