Betriebssysteme: Prozessplanung und Speicherverwaltung

SRT (Shortest Remaining Time)

Der nächste Prozess, den der Prozessor ausführt, ist derjenige mit der kürzesten verbleibenden Laufzeit. Wenn ein neuer Prozess ankommt, der kürzer ist als der aktuell ausgeführte, verdrängt letzterer die CPU, und der neue Prozess beginnt zu laufen. Es ist eine präemptive Variante des SJN-Algorithmus (Shortest Job Next).

Merkmale:

• Präemptive Variante von SJN.
• Sehr effiziente und präemptive Strategie.
• Bietet die Möglichkeit der Prioritätszuweisung. In diesem Fall multipliziert oder dividiert das System die verbleibende Zeit (Anzahl der Quanten) je nach Priorität.

Problem dieser Richtlinie:

• Einige Prozesse können unbestimmt aufgeschoben werden, wodurch sie zu 'Zombies' werden.
• Es ist schwierig zu kontrollieren, was mit Prozessen geschieht, wenn Prioritäten nicht angemessen verwaltet werden. Wenn präemptive Algorithmen verwendet werden, besteht die Gefahr, dass Prozesse unbegrenzt verzögert oder zu 'Zombies' werden, es sei denn, es gibt eine andere Möglichkeit, dies zu verhindern.

HRN (Highest Response Ratio Next)

Diese Richtlinie führt den Prozess aus, der das höchste Antwortverhältnis aufweist. Dies bedeutet, dass jeder Prozess Priorität basierend auf seinem Antwortverhältnis erhält.

Priorität = (Wartezeit + Laufzeit) / Laufzeit

Um zu verhindern, dass Prozesse unbegrenzt in der Warteschlange verzögert werden, steigt die Service-Priorität, wenn die Wartezeit (W) zunimmt. Anfangs, wenn das Verhältnis 1 ist, steigt die Priorität schnell an. Dies soll die Verzögerung von Prozessen vermeiden.

Wenn ein Prozess eintritt, läuft der Prozess entweder bis zum Abschluss oder bis zu einer E/A-Operation. Danach wird der nächste Prozess mit der höchsten Priorität ausgeführt. Diese Richtlinie ist nicht präemptiv. Wenn ein Programm läuft, kann es nicht unterbrochen werden, selbst wenn ein anderer Prozess eine höhere Priorität erhält.

Nachteile dieser Richtlinie:

• Wenn ein Benutzer einen kurzen Prozess direkt nach einem langen Prozess hat, muss er lange warten.
• Die Implementierung dieser Richtlinie ist sehr aufwendig, da die Prioritäten für alle wartenden Prozesse ständig neu berechnet werden müssen, was zu einer hohen Systemlast führt.
• Diese Richtlinie ist nicht präemptiv; Änderungen treten nur bei Prozessbeendigung auf. Sie ist nicht förderlich für die Unterbrechung eines Prozesses zugunsten eines anderen.
• Sie ist teuer und überlastet das System.

Mehrere Warteschlangen (Multilevel Queues)

Wenn verschiedene Prozesse mit ähnlichen Eigenschaften in Gruppen zusammengefasst werden können, können wir verschiedene Warteschlangen mit unterschiedlichen Planungsalgorithmen definieren. Wir benötigen einen Planungsalgorithmus, der mehrere verschiedene Warteschlangen verwaltet. Die Möglichkeit, Prozesse in verschiedenen Gruppen zu gruppieren, kann Warteschlangen von 2 bis n umfassen. Sobald Prozesse gruppiert sind, werden sie in den Speicher für ihre jeweilige Warteschlange gelegt; jede Warteschlange hat ihren eigenen Speicherbereich. Wir brauchen einen Algorithmus, der die Verarbeitung der Warteschlangen steuert und ihnen je nach Systempriorität den Prozessor zuweist.

Mehrere Warteschlangen mit Feedback (Multilevel Feedback Queues)

Alle Warteschlangen haben Zugriff auf den Prozessor. Der erste Algorithmus ist die Richtlinie, die für jede Warteschlange implementiert wird. Anstatt die Warteschlangen mit einem komplexen Algorithmus zu steuern, wird ihnen eine zuweisbare Zeit zugewiesen, z.B. dreimal so viel Zeit für Warteschlange 1, zweimal so viel für Warteschlange 2 und einmal für Warteschlange 3. Die letzte Ebene hat die kürzeste Laufzeit. Prozesse wechseln zwischen den Warteschlangen (Ebenen), je nachdem, wie sie sich verhalten. Wenn ein Prozess eine bestimmte Regel verletzt, wird er in die nächste Ebene verschoben.

Alle Warteschlangen haben unabhängig voneinander Zugriff auf den Prozessor. Es wird versucht, kurze Prozesse zu bevorzugen und Prozesse zu unterstützen, die durch E/A-Operationen begrenzt sind. Wenn ein Prozess sein Quantum verbraucht hat, wählt der Prozessor einen neuen Prozess aus einer niedrigeren Warteschlangenebene, falls vorhanden. Sobald ein Prozess sein Quantum eine bestimmte Anzahl von Malen in einer Warteschlange verbraucht hat und nicht beendet ist, wird er in die Warteschlange der nächsthöheren Ebene verschoben. Die Warteschlange geht nur nach unten, und die Laufzeit des letzten Prozesses wird immer größer (Zuteilung in Kaskade).

Merkmale:

• Unterstützt auch Overhead.
• Diese Richtlinie ist präemptiv.
• Sie ist sehr anpassungsfähig an die Bedürfnisse des Systems, da jede Warteschlange unterschiedlich verwaltet werden kann.

Hauptspeicher (RAM)

Hauptspeicherverwaltung: Zwecke des Hauptspeichers

• Programme ausführen: Damit der Prozessor auf ein Programm zugreifen und Daten verarbeiten kann, müssen diese im Hauptspeicher liegen.
• Leistungssteigerung (Multiprogramming): Der Hauptspeicher wird in 'n' Segmente unterteilt. Jeder Prozess läuft in einem dieser Segmente im Hauptspeicher.
• Datenaustausch: Der Hauptspeicher dient als Treffpunkt für Daten zwischen dem Prozessor und anderen Geräten. Die Geschwindigkeit des Hauptspeichers ist ein limitierender Faktor (Engpass) für die Verarbeitungsgeschwindigkeit des Computers.

Grundlegende Konzepte:

• Zugriffszeit auf den Speicher: Die Zeit zwischen Beginn und Ende eines Lese- oder Schreibvorgangs.
• Speicherzykluszeit: Die von der Hardware eines Systems auferlegte Zeit zwischen dem Ende eines E/A-Vorgangs und dem Beginn des nächsten (z.B. wie lange es dauert, bis ein System zurückgesetzt wird oder Parameter zurückgegeben werden).

Adressierung

Fehler wie Blue Screens (z.B. 0A01:ABFC) können auf Adressierungsprobleme hinweisen. Eine virtuelle Adresse wird berechnet als V * 65453 + Offset, wobei V die virtuelle Segmentnummer ist.

Definition einer Adresse:

Die Korrespondenz zwischen einer logischen und einer physischen Speicheradresse.

Adresstypen:

• Symbolische Adressen: Dies sind Namen (Labels), die wir verwenden, um auf Speicherorte zu verweisen. Beim Kompilieren eines Quellprogramms werden diese symbolischen Adressen in absolute Adressen umgewandelt. Variablen, die symbolischen Adressen zugeordnet sind, sind Namen, die vom Programmierer vergeben werden und nur im Quellprogramm sinnvoll sind. Bei der Ausführung werden ihnen Werte zugewiesen, die der Compiler in Bezug auf die Kompilierungsreihenfolge des Programms festlegt.
• Absolute Adressen: Dies sind die tatsächlichen physischen Adressen, auf die der Prozessor zugreift. Sie ergeben sich aus der Multiplikation der Segmentgröße mit der Segmentnummer minus 1, plus dem Offset innerhalb des Segments (Größe * (Nummer-1) + D).

Cache-Speicher: Der Cache-Speicher ist ein Teil des Hauptspeichers, der verwendet wird, um den Zugriff auf Eingangs- und Ausgangsdaten zu beschleunigen. Cache und Hauptspeicher sind primäre Speicher. Der Cache ist schneller, aber kleiner.

Konzept des Multiprogrammings

Multiprogramming ist eine Methode, die es ermöglicht, mehrere Programme gleichzeitig im Hauptspeicher auszuführen. Der Hauptspeicher wird in verschiedene Partitionen oder Regionen unterteilt, in denen unterschiedliche Prozesse laufen. Die Anzahl der Partitionen gibt den Grad des Multiprogrammings im System an. Jedes Segment sollte einen eigenen Cache für Ein- und Ausgaben haben (das System würde 'n' Caches verwalten).

Speicherschutz durch Segmentierung

Bei der Segmentierung, wenn in jedem Segment ein anderer Prozess geladen wird, entsteht die Notwendigkeit, den Zugriff innerhalb des Bereichs jedes Prozesses zu kontrollieren, um Überschneidungen von Programmen oder Daten oder unberechtigten Zugriff eines Programms auf ein anderes Segment zu vermeiden. Dazu werden für jede Partition zwei Grenzregister verwendet (obere und untere Grenze), sodass jede vom Prozess generierte Adresse innerhalb dieser Grenzen liegen muss. Diese Technik erfordert, dass die von den Prozessen generierten Adressen absolut sind, sei es bei der Kompilierung oder zur Laufzeit. In beiden Fällen ist die Zuordnung statisch.

Lösungen:

• Lösung 1 (Statisch): Verwendung von zwei Grenzregistern (obere und untere Grenze) pro Partition. Die Adressen müssen absolut sein, die Zuordnung ist statisch.
• Lösung 2 (Dynamisch): Ein Register enthält die Startadresse der Partition (Basisregister) und ein anderes ihre Größe (Grenzregister). Dies ermöglicht eine dynamische Adresszuweisung; es genügt, den Inhalt des Basisregisters zu aktualisieren, um auf einen Speicherbereich zuzugreifen. Jede vom Prozess generierte Adresse muss kleiner sein als der Wert im Grenzregister.

Entwicklung der Speicherverwaltung

Alle Betriebssysteme verwenden einen Großteil ihrer Software zur Speicherverwaltung.

Monoprogramming

• Ausführung von Programmen nacheinander.
• Durch dedizierten Speicher: Das Programm wird geladen und ausgeführt, der restliche Speicher bleibt ungenutzt. Dies war die erste Methode.
• Speicheraufteilung: Um mehrere Prozesse zu platzieren, werden Grenzen gesetzt und eine Aufteilungspolitik angewendet (Grenzprobleme).

Adressneuzuweisung

Die Adressen werden neu zugewiesen, wobei ein Grenzregister angibt, ab welchem Punkt das Benutzerprogramm geladen werden soll. Es ist notwendig, die Adressen des Programms entsprechend der Grenze zuzuweisen.

• Statische Neuzuweisung: Die Umverteilung erfolgt entweder während der Kompilierung oder beim Laden des Programms in den Speicher. Dies bedeutet, dass jede Größenänderung des Betriebssystems ein neues Kompilieren oder Laden des Programms erfordert. Diese Technik ist einfach, aber zu starr.
• Dynamische Neuzuweisung: Die Ausführung erfolgt während der Programmlaufzeit. Eine spezielle Hardware-Vorrichtung fängt jede vom Programm erzeugte logische Adresse ab und addiert den Inhalt des Basisregisters, um die entsprechende reale Adresse zu erhalten. Das Betriebssystem ermittelt mithilfe der Hardware die Korrespondenz zwischen realen und relativen Adressen, die den physischen Adressraum bilden.

Feste Partitionsgröße im Speicher

Eine der einfachsten Methoden zur Speicherverwaltung ist die Verwendung von zusammenhängenden Partitionen fester Größe, deren Anzahl und Größe bei der Systeminitialisierung definiert werden und für die Dauer der Sitzung unveränderlich bleiben. Wenn ein Programm geladen wird, weist das Betriebssystem eine Partition zu, die es aufnehmen kann. Dies erfordert, dass das System die Programmanforderungen kennt. Die ersten Systeme, die diese Art der Verwaltung nutzten, verwalteten den Speicher über Warteschlangen, wobei jedes Programm vom Betriebssystem einer Warteschlange entsprechend der angeforderten Speichergröße zugewiesen wurde. Diese Technologie ist einfach und leicht zu implementieren, aber ihre Effektivität wird stark vom Speicherbedarf der Programme und der Reihenfolge ihres Eingangs beeinflusst.

Limitierende Faktoren dieses Prozesses:

• Was passiert, wenn eine Anwendung nicht in den vorgesehenen Speicher passt? Sie kann nicht ausgeführt werden.
• Wenn ein Programm geladen wird, das kleiner ist als die zugewiesene Partition, muss man bis zum Ende des Prozesses warten, oder es kommt zu einer Neuverteilung des Systemspeichers in größere Partitionen. Dies führt zu Speicherverschwendung.

Wann immer Speicher verloren geht, spricht man von Speicherfragmentierung.

• Externe Fragmentierung: Speichersegmente, die nicht nutzbar sind, nachdem alle Segmente im Hauptspeicher belegt wurden (was von der Neuverteilung der Segmente übrig bleibt).
• Interne Fragmentierung: Speichersegmente, die innerhalb eines Prozesses nicht genutzt werden. Wenn ein kleines Programm in eine größere Partition geladen wird, entsteht interne Fragmentierung durch den ungenutzten Speicherplatz.

Methoden zur Optimierung der Fragmentierung

(Reduzierung der Fragmentierung)

Zusammenhängende Partitionen variabler Größe

Der Speicher wird dynamisch nach Bedarf zugewiesen. Das Betriebssystem verwaltet eine interne Speichertabelle, die den belegten und freien Speicherplatz aufzeichnet, wobei jeder Auftrag eine Partition der gewünschten Größe erhält.

Operation:

Beim Systemstart wird jedem Prozess ein Segment entsprechend seiner benötigten Größe zugewiesen. Dies kann zu externer Fragmentierung führen. Wenn Prozesse beendet und durch andere Prozesse in einem Segment ersetzt werden, das größer war als der vorherige, entsteht interne Fragmentierung und Speicherverschwendung.

Strategien zur Platzierung:

• First Fit: Platziert das Programm in der ersten freien Partition, unabhängig von ihrer Größe. Die Gefahr besteht, dass, wenn die erste freie Partition zu groß ist, viel Speicherplatz verschwendet wird.
• Best Fit: Wählt die erste freie Partition, die am besten zur Größe des auszuführenden Programms passt.

Der Speicher-Manager führt leere, zusammenhängende Partitionen zusammen. Dies kann jedoch zur Akkumulation externer Fragmentierung führen. Eine periodische Verdichtung ist notwendig, um externe Fragmentierung zu beseitigen (dies verlangsamt die Gesamtleistung des Systems erheblich). Regelmäßig muss eine Neuverteilung erfolgen.

Paging (Seitenverwaltung)

Paging ist eine Form der diskontinuierlichen Speicherzuweisung, die es ermöglicht, Prozesse in Frames zuzuweisen.

• Frame: Ein physisches Speichersegment der exakten Größe der definierten Speicherseiten.
• Seiten: Logische Partitionen, die einen Frame aufteilen. Für jedes Programm wird der benötigte Speicher in Seiten zugewiesen, die dann in Frames geladen werden.

Diese Methode verhindert übermäßige externe Fragmentierung, erzeugt aber weiterhin eine interne Fragmentierung, da es unmöglich ist, dass alle Prozessgrößen genau an die Seitengröße angepasst sind. Wenn man die Speichernutzung optimieren möchte, gilt die Tendenz: Je kleiner die Seitengröße, desto weniger Speicher wird verschwendet, aber dies bedeutet eine größere Anzahl von Seitentabellen für das System.

Das Paging funktioniert wie folgt:

Für jeden aktiven Job gibt ein spezielles 'Basisregister' die Startadresse der Seitentabelle des laufenden Prozesses an. Wenn ein Job wiederhergestellt wird, werden die Informationen aus der entsprechenden Tabelle geladen. Um jede logische Adresse, die der Prozessor generiert, in eine reale Adresse umzuwandeln, muss man die entsprechende Seitentabelle konsultieren und dann die tatsächliche Adresse ermitteln. Dies bedeutet, dass jeder Speicherzugriff zwei Zugriffszeiten verursacht.

Grundlegende Lösungen zur Beschleunigung:

• Cache-Speicher: Ein Cache-Speicher, der die Adressen der zuletzt verwendeten Seiten speichert, reduziert die Verzögerung. Das Problem ist, dass Cache-Speicher sehr teuer ist und die Speicherverwaltung komplexer wird.
• Assoziativspeicher: Für kleine Systeme mit wenigen Einträgen können assoziative Speicher verwendet werden, um diese Tabellen zu halten. Diese bestehen aus einem festen Satz von Datensätzen (assoziative Register), die einen direkten Vergleich mit allen Einträgen ermöglichen (Inhaltssuche).

Ein Vorteil der Auslagerung ist, dass es keine externe Fragmentierung gibt und die interne Fragmentierung minimal ist, nur auf der letzten Seite jedes Programms und erstattungsfähig.

Segmentierung

Programme sind in der Regel um einen Kern von Routinen oder Datenbereichen (z.B. Stacks, Tabellen) organisiert. Logisch gesehen ist dies eine Menge von Komponenten variabler Größe, die einen logischen Adressraum bilden.

Vorteil:

• Externe Fragmentierung ist zeitlich begrenzt, da am Ende jeder Routine der Speicher freigegeben wird und die externe Fragmentierung leicht behoben werden kann.

Kombinierte Speicherverwaltung: Paging und Segmentierung

Segmentierung mit Paging

Besteht aus einer Segmentierung, bei der jedes Segment eine Seitentabelle enthält, die die Größe des Programms anzeigt. Für jedes Segment wird eine Tabelle geführt, deren Einträge die Startadresse jeder Seitentabelle und deren Größe angeben. Es wird immer ein spezielles Hardware-Register verwendet.

Paging mit Segmentierung

Verwendet Segmente, deren Größe immer ein Vielfaches der Seitengröße ist, wodurch die externe Fragmentierung, die für die reine Segmentierung charakteristisch ist, vermieden wird.

Virtueller Speicher

Virtueller Speicher ist eine Speicherverwaltungstechnik, die Hardware und Software kombiniert.

Vorteile des virtuellen Speichers:

• Der logische Speicher kann größer sein als der tatsächlich verfügbare physische Speicher.
• Die Effizienz des Multiprogrammings und somit des Systems kann erhöht werden.
• Es sind weniger Festplatten-E/A-Operationen für das Laden und Austauschen von Programmen erforderlich.
• Nur die benötigten Teile eines Programms werden in den Speicher geladen.

Aspekte der Programmladung:

Dazu müssen wir drei Aspekte von Programmen betrachten:

• Laden (Load): Seiten werden nur bei Bedarf geladen (Demand Paging). Wenn Seiten im Voraus geladen werden, spricht man von Pre-Paging.
• Platzierung (Placement): Virtuelle Speichersysteme, die Segmentierung verwenden, müssen entscheiden, wo neue Segmente geladen werden sollen, z.B. nach der Best-Fit- oder First-Fit-Strategie.
• Ersetzung (Substitution): Wenn ein neuer Programmteil geladen werden muss und kein freier Speicherplatz vorhanden ist, muss eine Entscheidung getroffen werden, welcher Teil des Programms entfernt werden soll (z.B. der zuletzt verwendete, der älteste oder der am längsten nicht verwendete).

Funktionsweise des virtuellen Speichers:

Virtueller Speicher kann auf zwei Arten mit Seiten arbeiten:

• Demand Paging (Seiten auf Anforderung): Dies ist die häufigste Methode. Der Algorithmus lädt nicht das gesamte Programm, sondern nur die Seiten, die angefordert werden. Eine neue Seite wird nur geladen, wenn die vom Prozessor angeforderte Adresse nicht im Speicher ist.
• Seitenersetzung (Page Replacement): Die Systemroutine, die den Seitenfehler (Page Fault) verwaltet, funktioniert wie folgt:
  1. Die aufgerufene Seite muss im Sekundärspeicher gefunden werden.
  2. Ein freier Frame muss gefunden werden.
  3. Wenn ein freier Frame vorhanden ist, wird er verwendet. Wenn nicht, wird ein Seitenersetzungsalgorithmus verwendet, um die zu ersetzende Seite auszuwählen.
  4. Die zu ersetzende Seite wird im Sekundärspeicher gespeichert und die betroffenen Tabellen werden aktualisiert.
  5. Die angeforderte Seite wird in den freien Frame geladen und die Tabellen werden aktualisiert.

Seitenersetzungsalgorithmen:

Ein optimaler Seitenersetzungsalgorithmus würde die Seite ersetzen, die am längsten nicht mehr benötigt wird. Es ist jedoch unmöglich, das zukünftige Verhalten von Prozessen vorherzusagen. Die Algorithmen werden verwendet, um den Seitenersetzungsprozess zu steuern und eine annähernd optimale Lösung zu finden. Ihre Effektivität wird durch zwei Faktoren definiert:

• Die Anzahl der Seitenfehler, die durch den Prozess verursacht werden.
• Die Kosten der Nutzung (Overhead).

FIFO-Politik (First-In, First-Out)

Wenn eine Seite ersetzt werden muss, wählt diese Politik die Seite aus, die am längsten im Speicher ist. Um die Verweildauer im Speicher zu verfolgen, wird eine Warteschlange verwendet. Dieser Algorithmus ist sehr einfach und leicht zu implementieren. Er verursacht wenig Overhead und bietet eine relative Effizienz.

LRU-Politik (Least Recently Used)

Ersetzt die Seite, die am längsten nicht verwendet wurde. Die Annahme ist, dass Seiten, die in der jüngsten Vergangenheit nicht verwendet wurden, wahrscheinlich auch in der Zukunft am seltensten verwendet werden. Um das Alter der Seiten zu verfolgen, gibt es verschiedene Methoden.