Least frequently used

LFU (least frequently used) ist ein Algorithmus, der das Vorgehen beim Auswechseln einer Page in der Pagetable beschreibt. Dabei versteht man unter einer Page (zu Deutsch "Seite") einen Speicherblock des Computerspeichers mit fixer Größe. Die Pagetable ist eine Tabelle, mit deren Hilfe man eine logische Speicheradresse in eine physische Speicheradresse, oder umgekehrt, umrechnen kann.

Der Algorithmus besagt, dass derjenige Pageeintrag in der Pagetable ersetzt wird, der bislang am wenigsten verwendet wurde.

Ein Problem bei diesem Algorithmus ist, dass eine Page, die zu Beginn viel verwendet wurde, einen hohen Zähler besitzt (der Zähler zeigt an, wie viele Male der Pageeintrag in der Pagetable verwendet wurde). Diese Situation ist durchaus denkbar beim Ladevorgang. Obwohl der Pageeintrag danach nicht mehr abgefragt wird, bleibt dieser Eintrag in der Pagetable, da der Zähler genug hoch ist. Somit verlieren wir einen Platz in der Pagetable. Eine Ablösung für dieses Problem kann zum Beispiel sein, denn Zähler pro Zeiteinheit, die vorbeigeht, um ein Bit nach rechts zu schieben. Dadurch erhalten wir eine exponentielle Abnahme des Zählers. Dadurch wird verhindert, dass sich ein Eintrag, der eine Weile viel verwendet wurde und danach sozusagen gar nicht mehr, ewigs in der Pagetable halten kann.

Falls sich die Situation ergeben sollte, dass der Algorithmus zwischen zwei Pageeinträgen mit gleich hohem Zähler auswählen muss, kann zum Beispiel der FIFO Algorithmus angwendet werden.

--hammer 03:30, 27. Nov 2004 (CET)