3.3.2.2.3.2 NRU - Not Recently Used Algorithmus

[gesichtete Version]

Aktuelle Version vom 10. November 2020, 13:56 Uhr

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:

Frage

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.

Abb. 61: 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. 172: 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?

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

Aufgabe

Aufg. 173: 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 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.

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.

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

Aufgabe

Aufg. 174: Auch das M-Bit löschen?

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}

@@ Zeile 1: / Zeile 1: @@
-<p>
-{{#index:NRU, Seitenersetzungsalgorithmus|Not Recently Used Seitenersetzungsalgorithmus}}
+<loop_index id="5fa9786c0c1d2">NRU, Seitenersetzungsalgorithmus</loop_index><loop_index id="5fa978b80228a">Not Recently Used Seitenersetzungsalgorithmus</loop_index>
 Der '''Not Recently Used Seitenersetzungsalgorithmus''', kurz '''NRU''', ersetzt immer eine Seite, auf die ''in letzter Zeit'' nicht zugegriffen wurde.
 </p>
@@ Zeile 8: / Zeile 8: @@
 <p>
-Um dieses Verfahren zu implementieren, müssen zwei Fragen oder Probleme gelöst werden:
+Um dieses Verfahren zu implementieren, müssen zwei Fragen beantwortet, bzw. Probleme gelöst werden:
 </p>
@@ Zeile 14: / Zeile 14: @@
 <loop_area type="question">
 <p>
-# Wie kann festgestellt werden, ob auf eine Seite zugegriffen wurde?
+# Wie kann festgestellt werden, ob auf eine Seite zugegriffen wurde?<br /><br />
 # Wie lang ist die mit "''in letzter Zeit''" gemeinte Zeitspanne?
 </p>
 </loop_area>
 </p>
+<br />
 <p>
-Auf Frage 1 gibt es eine ganz einfache Antwort: Das R-Bit.
+Auf die erste Frage gibt es eine ganz einfache Antwort: Mit Hilfe des R-Bits.
 </p>
 <br />
-==== Das Referenziert-Bit ====
+== Das Referenziert-Bit ==
 <p>
 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.
 </p>
 <p>
-{{#index:Referenziert-Bit|Seitentabelleneintrag, Referenziert-Bit|R-Bit|Seitentabelleneintrag, R-Bit}}
+<loop_index id="5fa9786c0c1dd">Referenziert-Bit</loop_index><loop_index id="5fa9786c492bf">Seitentabelleneintrag, Referenziert-Bit</loop_index><loop_index id="5fa9786c492ca">R-Bit</loop_index><loop_index id="5fa9786c492d2">Seitentabelleneintrag, R-Bit</loop_index>
 Man spricht hier vom sogenannten '''Referenziert-Bit''', oder kurz vom '''R-Bit'''.
 </p>
@@ Zeile 42: / Zeile 44: @@
 <br />
 <p>
-<loop_figure title="Seitentabelle mit zusätzlicher Spalte für R-Bit" description="" copyright="CC-BY" index=true show_copyright=true>
+<loop_figure title="Seitentabelle mit zusätzlicher Spalte für R-Bit" description="" copyright="CC-BY" index=true show_copyright=true id="5fa9786c0c1e4">
 [[Datei:Seitentabelle-RM.JPG]]
 </loop_figure>
@@ Zeile 49: / Zeile 51: @@
 <br />
 <p>
-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.
+Es liegt auf der Hand, dass das R-Bit (genau wie das [[Das_Modifiziert-Bit|M-Bit]]) beim Einlagern einer virtuellen Seite in einen Seitenrahmen im betreffenden Seitentabelleneintrag mit 0 initialisiert wird.
 </p>
 <p>
@@ Zeile 56: / Zeile 58: @@
 <br />
-==== Aufgabe 1 ====
+== Aufgabe 1 ==
 <p>
 <loop_area type="task">
-<loop_task title="Lesen, schreiben, R-Bit?">
+<loop_task title="Lesen, schreiben, R-Bit?" id="5fa9786c0c1ec">
 <p>
 Es ist klar, dass das R-Bit bei einem '''lesenden Zugriff''' auf eine Seite von der [[MMU - Memory Management Unit|MMU]] gesetzt werden muss.
 </p>
 <p>
-Muss das R-Bit aber auch bei einem '''schreibenden Zugriff''' gesetzt werden? Zusammen mit dem [[Seitenersetzungsverfahren#Das_Modifiziert-Bit|M-Bit]]?
+Muss das R-Bit aber auch bei einem '''schreibenden Zugriff''' gesetzt werden? Zusammen mit dem [[Das_Modifiziert-Bit|M-Bit]]?
 </p>
 <spoiler text="Tipp">
@@ Zeile 76: / Zeile 79: @@
 <br />
+== Arbeitsweise von NRU ==
+<p>
+Sobald eine Entscheidung bzgl. der zu ersetzenden Seite herbeigeführt werden muss, kategorisiert NRU alle in Seitenrahmen eingelagerte virtuelle Seiten in vier Klassen:
+</p>
+<p>
+* '''Klasse 1:''' Eingelagerte Seiten mit R=0 und M=0.<br />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.<br />Dies ist der beste Fall, der in Folge eines Page faults eintreten kann.
+</p>
+<p>
+* '''Klasse 2:''' Eingelagerte Seiten mit R=0 und M=1.<br />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.
+</p>
+<p>
+* '''Klasse 3:''' Eingelagerte Seiten mit R=1 und M=0.<br />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.
+</p>
+<p>
+* '''Klasse 4:''' Eingelagerte Seiten mit R=1 und M=1.<br />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.<br />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.
+</p>
+<br />
+== Aufgabe 2 ==
+<p>
+<loop_area type="task">
+<loop_task title="Vier Klassen ohne Seiten?" id="5fa9786c0c1f3">
+<p>
+Könnte es vorkommen, dass in allen vier Klassen keine Seiten vorhanden sind? Begründe deine Meinung.
+</p>
+</loop_task>
+</loop_area>
+</p>
+<br />
+<p>
+Die Arbeitsweise von NRU ist nun weitgehend bekannt. Allerdings fehlt noch die Antwort auf die zweite Frage von oben:
+</p>
+<br />
+==  Wie lang ist die mit "in letzter Zeit" gemeinte Zeitspanne? ==
+<p>
+<cite id="5fa9786c0c1f9">Tanenbaum+2009</cite> 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.
+</p>
 <p>
-to do: 4 Klassen
+Bevor die Auswirkung dieser Zeitspanne näher erläutert wird, noch folgende Überlegung:
 </p>
 <p>
-Klasse 1: Eingelagerte Seiten mit R=0 und M=0.
+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.
+</p>
+<p>
+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.
 </p>
+<br />
+<p>
+<loop_area type="question">
 <p>
-Klasse 2: Eingelagerte Seiten mit R=0 und M=1.
+Können deshalb eigentlich eingelagerte Seiten mit R=0 vorkommen?<br />
+Sind also Seiten in Klasse 1 und 2 zu erwarten?
+</p>
+</loop_area>
+</p>
+<p>
+Die Wahrscheinlichkeit dafür dürfte sehr gering sein.
 </p>
+<br />
+<p>
+Jetzt kommt jedoch die [[NRU_-_Not_Recently_Used_Algorithmus#Wie_lang_ist_die_mit_.22in_letzter_Zeit.22_gemeinte_Zeitspanne.3F|erwähnte Zeitspanne]] ins Spiel: '''Immer nach Ablauf dieser Zeit werden in allen Seitentabellen alle R-Bits gelöscht (also auf 0 gesetzt)!'''
+</p>
 <p>
-Klasse 3: Eingelagerte Seiten mit R=1 und M=0.
+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.
 </p>
+<br />
+== Aufgabe 3 ==
+<p>
+<loop_area type="task">
+<loop_task title="Auch das M-Bit löschen?" id="5fa9786c0c200">
 <p>
-Klasse 4: Eingelagerte Seiten mit R=1 und M=1.
+Wenn nach Ablauf der [[NRU_-_Not_Recently_Used_Algorithmus#Wie_lang_ist_die_mit_.22in_letzter_Zeit.22_gemeinte_Zeitspanne.3F|erwähnten Zeitspanne]] das R-Bit gelöscht wird, sollte dann gleich auch das [[Seitenersetzungsverfahren#Das_Modifiziert-Bit|M-Bit]] mit gelöscht werden? Begründe deine Meinung!
+</p>
+</loop_task>
+</loop_area>
 </p>