3.3.2.2.3.2 NRU - Not Recently Used Algorithmus
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 beantwortet, bzw. Probleme gelöst werden:
- Wie kann festgestellt werden, ob auf eine Seite zugegriffen wurde?
- 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.
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.
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
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 in Folge eines Page faults 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.
Dies ist der schlechteste Fall, der eintreten kann: Viel Zeitbedarf zum Schreiben der Seite in den Hintergrundspeicher und mit hoher Wahrscheinlichkeit in Kürze ein Folge-Seitenfehler.
Aufgabe 2
Könnte es vorkommen, dass in allen vier Klassen keine Seiten vorhanden sind? Begründe deine Meinung.
Die Arbeitsweise von NRU ist nun weitgehend bekannt. Allerdings fehlt noch die Antwort auf die zweite Frage von oben:
Wie lang ist die mit "in letzter Zeit" gemeinte Zeitspanne?
Tanenbaum 2009 nennt hier "ungefähr 20 ms", andere Autoren verzichten ganz auf eine konkrete Angabe. Es darf jedoch davon ausgegangen werden, dass diese Zeitspanne relativ kurz im Verhältnis zum menschlichen Zeitempfinden gewählt werden sollte.
Bevor die Auswirkung dieser Zeitspanne näher erläutert wird, 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 zwangsläufig gesetzt.
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.
Jetzt kommt jedoch die erwähnte Zeitspanne ins Spiel: Immer nach Ablauf dieser Zeit werden in allen Seitentabellen alle R-Bits gelöscht (also auf 0 gesetzt)!
Damit dient das R-Bit als Indikator für all diejenigen eingelagerten virtuellen Seiten, die seit dem letzten "Auf-0-setzen" des R-Bits referenziert wurden. Folglich können sehr wohl Seiten in den Klassen 1 und 2 vorkommen.
Aufgabe 3
Wenn nach Ablauf der erwähnten Zeitspanne das R-Bit gelöscht wird, sollte dann gleich auch das M-Bit mit gelöscht werden? Begründe deine Meinung!
Diese Seite steht unter der Creative Commons Namensnennung 3.0 Unported Lizenz http://i.creativecommons.org/l/by/3.0/80x15.png