Least recently used
Least recently used (LRU; deutsch „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
- Kommt dem optimalen Algorithmus recht nah.
- 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.
- Ist recht aufwändig zu realisieren.
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 |
|---|