Least recently used

Least recently used (LRU) („Am längsten nicht verwendet“) ist eine Seitenverdrängungsstrategie für Cache-Speicher. Sie lagert diejenige Seite aus, deren letzte Referenzierung zeitlich am längsten zurückliegt.

Bewertung

Vorteile

• Die Strategie ist leicht implementierbar und erfordert kaum Verwaltungsaufwand.
• Sie wählt gezielt Seiten aus, die in letzter Zeit nicht verwendet wurden.

Nachteile

• Nur mittelmäßige Trefferrate. Wichtiger als die Frage, ob eine Seite referenziert wurde, ist oftmals die Frage, wie oft sie referenziert wurde. Least recently used nimmt auf diese Tatsache keine Rücksicht, was meist zu einer nur mittelmäßigen Trefferrate führt. Daher gelten Verfahren wie Least frequently used (LFU) als effizienter.

Implementierung

Least recently used wird mit Hilfe einer Warteschlange umgesetzt, in der alle eingelagerten Seiten darauf warten, ausgelagert zu werden. Muss eine Seite ausgelagert werden, so trifft es stets diejenige an der Spitze der Warteschlange (d. h. wähle Seite am Ende der Liste als zu ersetzende Seite). Wird eine Seite referenziert, so verlässt sie ihre Position und reiht sich am Ende der Schlange neu ein.

Beispiel

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

Siehe auch

• Paging