Der Least Recently Used (LRU) Algorithmus ist eine Methode des Page Replacement, bei der das victim der Prozess ist, der am längsten nicht mehr genutzt wurde.
Verwandte Themen
Implementierung
Es gibt mehrere Möglichkeiten, den LRU zu implementieren:
Logische Uhr
Jede Seite bekommt einen Zeitstempel der den letzten Zugriffszeitpunkt speichert. Wenn eine Seite ersetzt werden soll, wird die mit dem kleinsten Zeitstempel gewählt.
Hitliste
Ein spezieller Stack, auf dem die Seitennummern in einer doppelt verketteten Liste gespeichert sind. Wenn eine Seite referenziert wird, wird sie an der obersten Position des Stacks positioniert. Vorteile:
- Der Stack ist viel kleiner als die Page Table, das spart Speicherplatz
- Die älteste (bekannte) Seite liegt immer an der untersten Position, der Zeitaufwand der Suche entfällt also
Reference Bit
- Jede Seite bekommt ein Bit, das zunächst auf 0 gesetzt wird
- Wenn die Seite referenziert wird, ändert sich der Wert zu 1
Wir wissen nicht in welcher Abfolge die Seiten referenziert wurden, aber wir haben ein neues Ersetzungsverfahren: Wir ersetzen Pages Reihum, d.h. eine nach der anderen. Wenn aber die Page das Reference Bit 1 hat:
- Setzen wir ihr Reference Bit auf 0
- Belassen wir die Page im Speicher
- Fahren wir mit der nächsten Page entsprechend fort
Zählverfahren
Für jede Seite gibt es einen Zähler, in dem steht, wie oft die Seite referenziert wurde. Ersetzt wird:
- Beim LFU Algorithmus die Seite mit dem kleinsten Zählwert
- Beim MFU Algorithmus die Seite mit dem größten Zählwert
Ein Argument für MFU wäre, dass die Seiten mit dem kleinsten Zählwert möglicherweise gerade erst geladen wurden und die Verwendung noch bevorsteht.