Least recently used

Least recently used (LRU; deutsch „Am längsten nicht verwendet“) ist ein Seitenersetzungsalgorithmus. Wenn ein Seitenfehler auftritt und eine Seite ersetzt werden muss, wird die Seite ersetzt, auf welche am längsten nicht zugegriffen wurde. Aufgrund des hohen Aufwands wird er kaum bis gar nicht in der Praxis angewendet.

Bewertung

Vorteile

LRU kommt dem theoretisch optimalen Algorithmus recht nah.

Es werden gezielt Seiten ausgewählt, die in letzter Zeit nicht verwendet wurden. Dies ist in der Regel eine gute Metrik, um vorherzusagen, welche Seiten auch in Zukunft selten bzw. welche oft genutzt werden.

Nachteile

Die Liste muss bei jedem Speicherzugriff aktualisiert werden. Dies involviert das Suchen, Entfernen und Neueinfügen der betroffenen Seite. Dies erzeugt einen sehr großen Mehraufwand.

Least recently used berücksichtigt nicht direkt, wie häufig auf eine Seite zugegriffen wurde, was auch eine nützliche Metrik sein kann, um die Wahrscheinlichkeit eines erneuerten Zugriffs zu beurteilen. Least frequently used (LFU) berücksichtigt dies, hat jedoch das Problem, dass Seiten mit kurzzeitig vielen Zugriffen aufgrund ihres dadurch hohen Zählerstandes selbst dann eingelagert bleiben, wenn auf sie über einen langen Zeitraum nicht mehr zugegriffen wurde.

Implementierung

Linked List

Least recently used wird oft mit Hilfe einer Warteschlange in Form einer verketteten Liste umgesetzt, die Zeiger auf alle eingelagerten Seiten enthält. Wird auf eine Seite zugegriffen (oder eine neue Seite eingelagert), wird das zugehörige Element der Liste an den Anfang verschoben.

Die am längsten nicht referenzierte Seite befindet sich dadurch immer am Ende der Liste. Falls es notwendig ist, Seiten auszulagern, wird diese zuerst ersetzt.

Beispiel

A		B		D
B	–B→	A	–D→	B
C		C		A
	Cache-Hit		Cache-Miss

Siehe auch

Paging