Seitenersetzungsverfahren

Tritt bei der Adressumrechnung in der MMU ein Seitenfehler (Page fault) auf, so muss das Betriebssystem dafür sorgen, dass die benötigte virtuelle Seite aus dem Hintergrundspeicher in einen freien Seitenrahmen des physikalischen Speichers eingelagert wird.

Steht derzeit aber kein freier Seitenrahmen zur Verfügung, so ist es die Aufgabe des implementierten Seitenersetzungsverfahrens zu entscheiden, welche momentan eingelagerte virtuelle Seite in den Hintergrundspeicher verschoben wird. Dadurch wird dann (mindestens) ein freier Seitenrahmen geschaffen, die benötigte virtuelle Seite kann eingelagert werden, und die MMU kann die zuvor gescheiterte Adressumrechnung erneut durchführen.

{{#index:Verdrängungsstrategie}} Statt des im vorstehenden Absatz erwähnten Begriffs verschoben findet oftmals auch das Verb verdrängt in gängiger Literatur seine Anwendung. Man spricht hier dann auch von einer Verdrängungsstrategie und meint damit wieder ein Seitenersetzungsverfahren.

Hinweis

Für das Verständnis der folgenden Erläuterungen ist es wichtig, sich über die hier verwendeten Begriffe im Klaren zu sein. Es wird unterschieden zwischen:

• (virtuelle) Seite
• Seitenrahmen
• eingelagerte Seite
• benötigte Seite
• zu ersetzende Seite
• modifizierte Seite

Falls erforderlich gibt es hier noch einige Hinweise

Was bei der Seitenersetzung passiert

Eine einfache Beschreibung des Ablaufs einer Seitenersetzung ist wie folgt:

1. Die MMU stellt fest, dass die benötigte virtuelle Seite B nicht in einem Seitenrahmen eingelagert ist und löst deshalb einen Seitenfehler aus.
2. Es wird festgestellt, dass kein freier Seitenrahmen mehr verfügbar ist, das Seitenersetzungsverfahren wird deshalb gestartet.
3. Die zu ersetzende Seite E wird bestimmt, sie ist derzeit in Seitenrahmen X eingelagert.
4. Die zu ersetzende Seite E wird in den Hintergrundspeicher geschrieben. Damit ist ihr Inhalt gesichert, sie kann später wieder eingelagert werden.
5. Die benötigte Seite B wird eingelagert, d.h. ihr Inhalt wird in den Seitenrahmen X geschrieben. Das Ersetzungsverfahren ist damit abgeschlossen.

Wichtig

Das Schreiben der zu ersetzenden Seite E in den Hintergrundspeicher kostet viel Zeit! Das ist schlecht für die Performance des Gesamtsystems.

Es ist deshalb sinnvoll, eine zu ersetzende Seite nur dann in den Hintergrundspeicher zu kopieren, wenn dies auch tatsächlich notwendig ist.

Eine Seite kann beispielsweise den Programmtext oder die Daten eines Prozesses enthalten.

Aufgabe 1

Aufgabe

 Aufg. : Wenn eine Seite Programmtext enthält

Eine zu ersetzende Seite enthält lediglich Programmtext (also den ausführbaren Maschinencode mit den Befehlen) eines Prozesses. Diese Inhalte dürfen während der Ausführung des zugehörigen Prozesses nicht verändert werden.

Ist es erforderlich, diese Seite in den Hintergrundspeicher auszulagern, oder kann die dafür benötigte Zeit eingespart werden? Erläutere deine Antwort!

Aufgabe 2

Aufgabe

 Aufg. : Wenn eine Seite Daten enthält

Eine zu ersetzende Seite enthält Daten. Diese Inhalte können verändert worden sein, müssen aber es nicht.

Ist es erforderlich, diese Seite in den Hintergrundspeicher auszulagern, oder kann die dafür benötigte Zeit eingespart werden? Erläutere deine Antwort!

Betrachte folgende Situationen:

1. Die Inhalte der Seite wurden verändert, weil Werte in Speicherzellen dieser Seite geschrieben wurden.
2. Die Inhalte der Seite wurden nicht verändert, zudem befindet sich eine Kopie der Seite im Hintergrundspeicher, weil sie zu einem früheren Zeitpunkt bereits einmal ausgelagert war.

Auslagern von modifizierten Seiten

Es liegt auf der Hand, dass modifizierte Seiten nicht einfach ersetzt werden dürfen, bevor sie nicht im Hintergrundspeicher gesichert wurden. Ihre Inhalte wären andernfalls verloren, was negative Auswirkungen auf den betreffenden Prozess nach sich ziehen dürfte. Insbesondere könnten sie zu einem späteren Zeitpunkt nicht wieder eingelagert werden.

Frage

Wie kann das Betriebssystem aber feststellen, ob die Inhalte einer derzeit noch eingelagerten Seite modifiziert wurden, und so eine Auslagerung vor dem Ersetzen erforderlich wird?

Es gibt dafür eine ganz einfache Lösung: Das M-Bit.

Das Modifiziert-Bit

In den Seitentabellen wird eine zusätzliche Spalte eingeführt, siehe Abbildung unten. Für jede einzelne Seite (d.h. in jedem Seitentabelleneintrag) wird mit Hilfe eines einzelnen Bits festgehalten, ob die betreffende Seite verändert wurde.

{{#index:Modifiziert-Bit|Seitentabelleneintrag, Modifiziert-Bit|M-Bit|Seitentabelleneintrag, M-Bit|Dirty-Bit}} Man spricht hier vom sogenannten Modifiziert-Bit, oder kurz vom M-Bit (in einigen Quellen ist auch vom Dirty-Bit die Rede).

• Das M-Bit ist gesetzt, also 1:
  Der Inhalt der Seite wurde modifiziert.

• Das M-Bit ist nicht gesetzt, also 0:
  Der Inhalt der Seite wurde nicht modifiziert.

 Abb. : Seitentabelle mit zusätzlicher Spalte für M-Bit

CC-BY

Die MMU nimmt bei der (erfolgreichen) Umrechnung einer virtuellen in eine physikalische Adresse ein Setzen des Bits im betreffenden Eintrag der Seitentabelle vor, sofern ein schreibender Zugriff auf die betreffende Speicherzelle erfolgen soll.

Hinweis

Ist das M-Bit gesetzt (also gleich 1), so muss die zu ersetzende Seite E ausgelagert werden, d.h. der Zeitaufwand für ein Kopieren der Seite in den Hintergrundspeicher ist unvermeidlich.

Seitenersetzungsverfahren

In der obigen Auflistung findet sich u.a. der Punkt "Die zu ersetzende Seite E wird bestimmt,...", und es stellt sich die Frage:

Frage

Wie wird die zu ersetzende Seite bestimmt?

Diese Aufgabe wird von einem sogenannten Seitenersetzungsalgorithmus erledigt.

Im Laufe der Entwicklungsgeschichte von Betriebssystemen wurden eine ganze Reihe verschiedener Seitenersetzungsverfahren (oder Verdrängungsstrategien) vorgeschlagen bzw. implementiert, u.a.:

{{#index:Optimaler Seitenersetzungsalgorithmus|NRU, Seitenersetzungsalgorithmus|Not Recently Used Algorithmus|FIFO, Seitenersetzungsalgorithmus|First In First Out Seitenersetzungsalgorithmus|Second Chance Seitenersetzungsalgorithmus|Clock Page Seitenersetzungsalgorithmus|LRU, Seitenersetzungsalgorithmus|Least Recently Used Seitenersetzungsalgorithmus|NFU, Seitenersetzungsalgorithmus|Not Frequently Used Seitenersetzungsalgorithmus|Working Set Seitenersetzungsalgorithmus}}

• Optimaler Algorithmus
• NRU - Not Recently Used Algorithmus
• FIFO - First In First Out Algorithmus
• Second Chance Algorithmus
• Clock Page Algorithmus
• LRU - Least Recently Used Algorithmus
• NFU - Not Frequently Used Algorithmus
• Working Set Algorithmus

Hinweis

Weiterführende Literatur

Mandl 2013 erläutert die genannten Algorithmen in den Kapiteln 7.2.3 und 7.2.4. Die Lektüre dieser Quelle sei ausdrücklich empfohlen.

Studierende sind oftmals berechtigt, eine PDF-Version dieses Buches ohne entstehende Kosten über ihre Hochschulen von Springerlink zu beziehen.

Einige der genannten Algorithmen werden auf den folgenden Seiten behandelt. Die ausführlichere Besprechung aller Verfahren leistet jedoch nur die weiterführende Literatur.

Hinweis

Beim Durcharbeiten der genannten Kapitel bei Mandl 2013 kann man sehr schön die Evolution der Algorithmen verfolgen. D.h. ein späteres Verfahren beruht sehr oft auf einem vorangegangenen Verfahren, wobei jedoch ein vorheriger Nachteil verbessert wurde.
Achte mal darauf!

So geht es weiter:

Gliederung

3.3.2.2.3 Seitenersetzungsverfahren

3.3.2.2.3.1 Optimaler Seitenersetzungsalgorithmus

3.3.2.2.3.2 NRU - Not Recently Used Algorithmus

3.3.2.2.3.3 FIFO - First In First Out Algorithmus

3.3.2.2.3.4 Second Chance Algorithmus

3.3.2.2.3.5 Working Set Algorithmus

---

_{Diese Seite steht unter der Creative Commons Namensnennung 3.0 Unported Lizenz http://i.creativecommons.org/l/by/3.0/80x15.png}