Der LRU-Algorithmus (Least Recent Used) zum Ersetzen von Seiten ersetzt die Seite, die am längsten nicht verwendet wurde.

Zur Implementierung von LRU wird eine Datenstruktur namens Warteschlange benötigt verwendet wird. Bei jedem Zugriff auf eine Seite wird diese an den Anfang der Warteschlange verschoben. Wenn eine Seite ersetzt werden muss, wird die Seite am Ende der Warteschlange (die älteste Seite) ausgewählt.

LRU ist ein gieriger Algorithmus Das bedeutet, dass bei jedem Schritt die beste Entscheidung getroffen wird, ohne Rücksicht auf die Zukunft zu nehmen. Dies kann in einigen Fällen zu einer suboptimalen Leistung führen, ist jedoch im Allgemeinen eine gute Wahl für den allgemeinen Einsatz.

Hier sind die Schritte des LRU-Seitenersetzungsalgorithmus:

1. Wenn auf eine Seite zugegriffen wird, wird sie an den Anfang der Warteschlange verschoben.

2. Wenn eine Seite ersetzt werden muss, wird die Seite am Ende der Warteschlange ausgewählt.

3. Die ausgewählte Seite wird aus der Warteschlange und aus dem physischen Speicher entfernt.

4. Die Seite, die geladen wird, wird an den Anfang der Warteschlange gestellt.