Least recently used
Least recently used (LRU; deutsch „Am längsten nicht verwendet“) ist eine Strategie für die Implementierung von Cache-Speichern. Wenn der Cache voll ist, entfernt sie diejenigen Daten aus dem Cache, deren letzter Abruf zeitlich am längsten zurückliegt.
Bewertung
Vorteile
- Kommt dem optimalen Algorithmus recht nah.
- Sie wählt gezielt Daten aus, die in letzter Zeit nicht verwendet wurden.
Nachteile
- Nur mittelmäßige Trefferrate. Wichtiger als die Frage, ob ein Inhalt referenziert wurde, ist oftmals die Frage, wie oft er 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 oft mit Hilfe einer Warteschlange umgesetzt, in der alle zwischengespeicherten Daten gehalten zu werden. Inhalte, die abgerufen werden, werden von ihrer bisherigen Position entfernt und wieder ans Ende der Schlange einsortiert. Wenn bei vollem Cache ein neuer Inhalt im Cache gespeichert werden soll, wird der ebenfalls ans Ende der Warteschlange gestellt und der Inhalt an der Spitze wird aus der Warteschlange entfernt.
Beispiel
| A | B | D | ||
| B | –B→ | A | –D→ | B |
| C | C | A | ||
| Cache-Hit | Cache-Miss |
|---|