Least Recently Used (LRU)

Eine möglichst nahe Approximation an den optimalen Algorithmus läßt sich aus der empirischen Beobachtung herleiten, dass Seiten die schon lange nicht mehr benötigt wurden, auch in Zukunft längere Zeit nicht mehr benötigt werden und umgekehrt, Seiten, die eben erst benötigt wurden auch in Zukunft schnell wieder benötigt werden.

Es gibt nun zwei Möglichkeiten diesen Algorithmus in der Hardware zu implementieren:

1. Eine erste Möglichkeit wäre das R-Bit der Seitentabelleneinträge durch ein 64-Bit großes Wort zu ersetzten. Jedesmal, wenn auf die Seite zugegriffen wird, wird die aktuelle Zeit als Zeitstempel hierin gespeichert. Wenn dann eine Seite ausgelagert werden soll, werden alle Seiten durchsucht und die mit dem niedrigsten Zeitstempel wird entfernt. Dieser Algorithmus ist nicht sehr effizient, weil bei jedem Seitenfehler alle Seitentabelleneinträge durchsucht werden müssen.
2. Angenommen der physikalische Speicher enthält $n$ Seitenrahmen. Dann muss die Hardware eine Matrix von $n \times n$ Bits zur Verfügung stellen. Immer wenn auf eine Seite $k$ zugegriffen wird, werden zunächst alle Bits der Zeile $k$ auf 1 gesetzt und anschließend alle Bits der Spalte $k$ auf 0 gesetzt. In jedem Moment ist die Zeile deren binärer Wert an kleinsten ist, die, die am wenigsten genutzt wurde.

   Beispiel: Seien vier Seitenrahmen vorhanden und es wird auf die Seiten in der Reichenfolge 1,0,2,3,0,3,1,0 zugegriffen.

   
   

   Zugriff: 1
   	0	1	2	3
   0	0	0	0	0
   1	1	0	1	1
   2	0	0	0	0
   3	0	0	0	0

   Zugriff: 0
   	0	1	2	3
   0	0	1	1	1
   1	0	0	1	1
   2	0	0	0	0
   3	0	0	0	0

   Zugriff: 2
   	0	1	2	3
   0	0	1	0	1
   1	0	0	0	1
   2	0	1	0	1
   3	0	0	0	0

   Zugriff: 3
   	0	1	2	3
   0	0	1	0	0
   1	0	0	0	0
   2	0	1	0	0
   3	1	1	1	0

   
   

   
   

   Zugriff: 0
   	0	1	2	3
   0	0	1	1	1
   1	0	0	0	0
   2	0	1	0	0
   3	0	1	1	0

   Zugriff: 3
   	0	1	2	3
   0	0	1	1	0
   1	0	0	0	0
   2	0	1	0	0
   3	1	1	1	0

   Zugriff: 1
   	0	1	2	3
   0	0	0	1	0
   1	1	0	1	1
   2	0	0	0	0
   3	1	0	1	0

   Zugriff: 0
   	0	1	2	3
   0	0	1	1	1
   1	0	0	1	1
   2	0	0	0	0
   3	0	0	1	0

Falls die Hardware die Benutzung des LRU nicht zulässt, kann auch in diesem Fall durch das Betriebssystem der LRU implementiert werden.