NRU - Not Recently Used Algorithmus

{{#index:NRU, Seitenersetzungsalgorithmus|Not Recently Used Seitenersetzungsalgorithmus}} Der Not Recently Used Seitenersetzungsalgorithmus, kurz NRU, ersetzt immer eine Seite, auf die in letzter Zeit nicht zugegriffen wurde.

Die Idee dahinter ist: Wenn in letzter Zeit nicht auf die Seite zugegriffen wurde, dann wird vermutlich auch in (naher) Zukunft nicht darauf zugegriffen werden müssen.

Um dieses Verfahren zu implementieren, müssen zwei Fragen oder Probleme gelöst werden:

Frage

1. Wie kann festgestellt werden, ob auf eine Seite zugegriffen wurde?
2. Wie lang ist die mit "in letzter Zeit" gemeinte Zeitspanne?

Auf die erste Frage gibt es eine ganz einfache Antwort: Mit Hilfe des R-Bits.

Das Referenziert-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 referenziert wurde.

{{#index:Referenziert-Bit|Seitentabelleneintrag, Referenziert-Bit|R-Bit|Seitentabelleneintrag, R-Bit}} Man spricht hier vom sogenannten Referenziert-Bit, oder kurz vom R-Bit.

• Das R-Bit ist gesetzt, also 1:
  Der Inhalt der Seite wurde referenziert, es wurde also darauf zugegriffen.

• Das R-Bit ist nicht gesetzt, also 0:
  Der Inhalt der Seite wurde nicht referenziert, es wurde also nicht darauf zugegriffen.

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

CC-BY

Es liegt auf der Hand, dass das R-Bit (genau wie das M-Bit) beim Einlagern einer virtuellen Seite in einen Seitenrahmen im betreffenden Seitentabelleneintrag mit 0 initialisiert wird.

Die MMU nimmt später bei der (erfolgreichen) Umrechnung einer virtuellen in eine physikalische Adresse ein Setzen des R-Bits im betreffenden Eintrag der Seitentabelle vor.

Aufgabe 1

Aufgabe

 Aufg. : Lesen, schreiben, R-Bit?

Es ist klar, dass das R-Bit bei einem lesenden Zugriff auf eine Seite von der MMU gesetzt werden muss.

Muss das R-Bit aber auch bei einem schreibenden Zugriff gesetzt werden? Zusammen mit dem M-Bit?

Tipp

Arbeitsweise von NRU

Sobald eine Entscheidung bzgl. der zu ersetzenden Seite herbeigeführt werden muss, kategorisiert NRU alle in Seitenrahmen eingelagerte virtuelle Seiten in vier Klassen:

• Klasse 1: Eingelagerte Seiten mit R=0 und M=0.
  Von allen in dieser Klasse befindlichen Seiten wird eine zur Ersetzung bestimmt. Wegen M=0 muss diese Seite nicht im Hintergrundspeicher gesichert werden, der aufgetretene Seitenfehler kann also möglichst schnell behoben werden. Dies ist der beste Fall, der eintreten kann.

• Klasse 2: Eingelagerte Seiten mit R=0 und M=1.
  Sofern in Klasse 1 keine Seiten vorhanden sind, wird eine Seite aus Klasse 2 zur Auslagerung bestimmt. Wegen M=1 muss diese Seite zwar in den Hintergrundspeicher geschrieben werden (was Zeit kostet), jedoch lässt R=0 darauf hoffen, dass die Seite in Zukunft nicht so schnell wieder benötigt wird.

• Klasse 3: Eingelagerte Seiten mit R=1 und M=0.
  Sofern in den Klassen 1 und 2 keine Seiten vorhanden sind, wird eine Seite aus Klasse 3 zur Auslagerung bestimmt. Wegen M=0 muss diese Seite nicht im Hintergrundspeicher gesichert werden, jedoch lässt R=1 erwarten, dass die Seite in (naher) Zukunft wieder benötigt wird. Mit hoher Wahrscheinlichkeit tritt deswegen ein Folge-Seitenfehler auf.

• Klasse 4: Eingelagerte Seiten mit R=1 und M=1.
  Sofern in den Klassen 1, 2 und 3 keine Seiten vorhanden sind, wird eine Seite aus Klasse 4 zur Auslagerung bestimmt. Wegen M=1 muss diese Seite in den Hintergrundspeicher geschrieben werden. Zusätzlich lässt R=1 erwarten, dass die Seite in (naher) Zukunft wieder benötigt wird. Dieser Fall ist der schlechteste Fall, der eintreten kann.

Aufgabe 2

Aufgabe

 Aufg. : Vier Klassen ohne Seiten?

Könnte es vorkommen, dass in allen vier Klassen keine Seiten vorhanden sind? Begründe deine Meinung.

Die Arbeitsweise von NRU ist nun weigehend bekannt. Allerdings fehlt noch die Antwort auf die zweite Frage von oben: Wie lang ist die mit "in letzter Zeit" gemeinte Zeitspanne?

Zuvor aber noch folgende Überlegung:

Ein (beliebiger) Seitenersetzungsalgorithmus (und damit speziell auch NRU) lagert eine virtuelle Seite in einen physikalischen Seitenrahmen ein, wenn diese benötigt wird. Es ist eine Reaktion auf einen direkt zuvor aufgetretenen Seitenfehler.

Sobald nun die benötigte Seite eingelagert wurde (und der Scheduler dem betreffenden Prozess die CPU zugeteilt hat), wird der nächste Speicherzugriff sofort auf die gerade eingelagerte Seite erfolgen, das zugehörige R-Bit wird also gesetzt.

Frage

Können deshalb eigentlich eingelagerte Seiten mit R=0 vorkommen?
Sind also Seiten in Klasse 1 und 2 zu erwarten?

Die Wahrscheinlichkeit dafür dürfte sehr gering sein.

---

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