LRU

Least Recently Used

• Nutzt die Lokalitätseigenschaft:

  • Was länger nicht verwendet wurde, wird wahrscheinlich auch weiterhin nicht benötigt.
  • Projektion der Vergangenheit in die Zukunft.

• Gute Approximation der Optimal Page Replacement Strategy (Bélády).

• Nicht einfach zu implementieren (erfordert Zeitstempel oder spezielle Datenstrukturen).

• Fundamentaler Caching-Algorithmus.

Implementierung

Herausforderungen

• Ordnen der Pages nach den letzten Zugriffen

  • Jede Seite im Speicher muss mitverfolgen, wann sie zuletzt verwendet wurde.
  • Die Seite mit dem ältesten Zugriff wird als Nächstes ersetzt.
  • Es braucht eine effiziente Datenstruktur, um die Seiten nach Zugriffszeitpunkt zu sortieren.

• Jeder Zugriff zählt – Lesen & Schreiben

  • Read- und Write-Zugriffe gelten beide als Nutzung einer Seite.
  • Bei jedem Zugriff muss die Reihenfolge aktualisiert werden.

Realisierung basierend auf einer logischen Uhr

Realisierung basierend auf einem Stack