Not recently used

Not recently used (NRU) („In letzter Zeit nicht verwendet“) ist eine Paging-Strategie für den Arbeitsspeicher. Sie lagert bevorzugt Seiten aus, die innerhalb eines Zeitintervalls nicht benutzt und nicht modifiziert wurden. Dazu werden die Seiten in regelmäßigen Abständen als ungelesen und unverändert markiert. Wenn eine Seite ausgelagert werden muss, wird geprüft, bei welchen Seiten sich diese Markierungen nicht geändert haben.

Grundlagen

Eine Aufgabe eines Betriebssystems ist die Verwaltung des Arbeitsspeichers. Der Arbeitsspeicher wird dazu in Einheiten fester Größe unterteilt, den Speicherseiten (Kacheln). Ist der Arbeitsspeicher voll ausgenutzt, muss eine Seite auf die Festplatte ausgelagert werden. Da die Festplatte viel langsamer als der Arbeitsspeicher ist, gibt es Strategien, um eine Seite zur Auslagerung auszuwählen, die nicht sofort wieder benötigt wird und eingelagert werden muss.

Implementierung

Jeder Eintrag in der Seitentabelle hat beim NRU-Algorithmus zwei Markierungen:

  • Das A-Bit (Access für engl. Zugriff) gibt an, ob ein Zugriff auf die Seite erfolgt ist
  • Das M-Bit (Modified für engl. verändert) gibt an, ob die Seite verändert wurde

Immer wenn ein Zugriff auf eine Seite erfolgt, wird das A-Bit auf 1 gesetzt. Und immer wenn die Daten einer Seite verändert werden, wird das M-Bit auf 1 gesetzt. In regelmäßigen Abständen werden die A-Bits wieder auf 0 gesetzt.

Wenn eine Seite ausgelagert werden muss, wird eine zufällig ausgewählte Seite ausgelagert, die nicht verändert (M=0) und auf die in letzter Zeit, d. h. seit dem letzten Zurücksetzen der A-Bits, nicht zugegriffen wurde (A=0). Da es möglich ist, dass keine Seite diese Eigenschaft hat, muss evtl. eine Seite ausgelagert werden, die verändert oder auf die zugegriffen wurde. Die folgende Liste gibt an, mit welcher Priorität eine Seite ausgelagert wird:

  1. A=0, M=0 (nicht gelesen, nicht verändert)
  2. A=0, M=1 (nicht gelesen, aber verändert)
  3. A=1, M=0 (gelesen, aber nicht verändert)
  4. A=1, M=1 (gelesen und verändert)

Der NRU-Algorithmus stellt sicher, dass bevorzugt Seiten ausgelagert werden, die lange nicht benutzt wurden und daher vermutlich auch in nächster Zeit nicht benutzt werden. So soll vermieden werden, dass häufig Seiten ausgelagert werden müssen, sodass möglichst wenige Zugriffe auf den langsameren Hintergrundspeicher erfolgen müssen.

Der Algorithmus führt in der Praxis zu annehmbaren Ergebnissen. Darüber hinaus hat er den Vorteil, dass er leicht implementierbar ist.