Last 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.

Grundlagen

Ein Cache ist ein schneller Pufferspeicher, der Daten aus langsamen Speichern zwischenlagert und so schneller verfügbar macht. Die kleinste Einheit an Daten, die zwischen beiden Speicherformen ausgetauscht werden, ist eine Speicherseite (Kachel). Ein Cache kann nur eine geringe Anzahl an Speicherseiten fassen. Ist der Cache voll, muss für jede neu einzulagernde Seite eine alte weichen. Die Seitenverdrängungsstrategie legt fest, welche Seiten als „alt“ betrachtet und ausgelagert werden.

Wird auf die Daten einer Seite zugegriffen, so sagt man, die Seite werde „referenziert“. Befindet sich eine referenzierte Seite gerade im Cache, so spricht man von einem „Treffer“ (Cache Hit), ist dies nicht der Fall, entsprechend von „keinem Treffer“ (Cache Miss). Das durchschnittliche Verhältnis „Treffer“ zu „kein Treffer“ ist die „Trefferrate“.

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