Least frequently used
Least frequently used (LFU) („am wenigsten verwendet“) ist ein Algorithmus, der in einem Cache mit fester Größe den Eintrag auswählt, der aus dem Cache verdrängt wird, wenn der Cache voll ist. Es wird stets der Eintrag aus dem Cache verdrängt, der bislang am seltensten verwendet wurde. Dazu merkt sich der Algorithmus zu jedem Eintrag in einem Zähler, wie oft bereits auf diesen Eintrag zugegriffen wurde.
Falls sich die Situation ergeben sollte, dass der Algorithmus zwischen zwei Einträgen mit gleich hohem Zähler auswählen muss, kann zum Beispiel der FIFO-Algorithmus angewandt werden.
Implementierung
Bei LFU wird zu jedem Eintrag im Cache ein Zähler geführt, der angibt, wie oft auf den Eintrag zugegriffen wurde. Jeder Zugriff erhöht den Zähler. Muss ein Eintrag ersetzt werden, weil der Cache voll ist, wird der Eintrag mit den wenigsten Zugriffen ersetzt.
Beispiel
| A:2 | A:2 | F:1 | ||
| B:3 | –B→ | B:4 | –F→ | B:4 |
| C:8 | C:8 | C:8 | ||
| Cache-Hit | Cache-Miss |
|---|
Zeitabhängige Variante
Ein Problem bei diesem Algorithmus ist, dass ein Eintrag, der zu Beginn (zum Beispiel beim Laden oder Initialisieren) häufig verwendet wurde, einen hohen Zählerstand besitzt. Selbst wenn anschließend nicht mehr auf den Eintrag zugegriffen wird, bleibt der Zählerstand des Eintrags hoch, und der Eintrag wird erstmal nicht verdrängt. Somit bleibt ein Platz im Cache praktisch ungenutzt.
Eine Lösung für dieses Problem kann zum Beispiel sein, die Zählerstände in regelmäßigen Zeitabständen zu halbieren, was zu einer exponentiellen Abnahme führt. Dadurch wird verhindert, dass sich ein Eintrag, der für einige Zeit viel verwendet wurde, auf den danach aber fast gar nicht mehr zugegriffen wird, auf ewig im Cache halten kann.
Bewertung
Vorteile:
- Relativ leicht zu implementieren
- Beachtet das Alter eines Eintrags (bei regelmäßigem Halbieren der Zählerstände)
- Beachtet die Zugriffshäufigkeit eines Eintrags
Nachteile:
- Ein einmal häufig verwendeter Eintrag wird erst nach vielen Misses ersetzt und blockiert somit den Cache
Siehe auch
Literatur
- Andrew S. Tanenbaum: Moderne Betriebssysteme. 3. Auflage. Pearson Studium, 2009, ISBN 3-8273-7342-5 (umfassende Erläuterungen zur Speicherverwaltung, Übersetzung aus dem Englischen)