Least frequently used - LinkFang.de





Least frequently used


Dieser Artikel oder Abschnitt ist nicht ausreichend belegt.

Least frequently used (LFU) („am wenigsten verwendet“) ist ein Algorithmus, der das Vorgehen beim Auswechseln einer Page in der Pagetable beschreibt. Dabei versteht man unter einer Page einen Speicherblock des Computerspeichers mit fester Größe. Die Pagetable ist eine Tabelle, mit deren Hilfe man eine logische Speicheradresse in eine physische Speicheradresse (oder umgekehrt) umrechnen kann (Paging).

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 hoch genug ist. Somit verliert man einen Platz in der Pagetable. Eine Lösung für dieses Problem kann zum Beispiel sein, den Zähler pro Zeiteinheit um ein Bit nach rechts zu schieben, was zu einer exponentiellen Abnahme des Zählers 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 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 angewandt werden.

Vorteile:

  • Relativ leicht zu implementieren
  • Beachtet das Alter einer Seite
  • Beachtet die Referenzhäufigkeit einer Seite

Nachteile:

  • Eine einmal häufig referenzierte Seite wird erst nach vielen Misses ersetzt und blockiert somit den Cache

Implementierung

Bei LFU wird zu jeder Seite im Cache ein Referenzzähler geführt, der angibt wie oft auf die Seite zugegriffen wurde. Jeder Seitenzugriff erhöht den Referenzzähler. Muss eine Seite ersetzt werden, weil der Cache voll ist, wird die Seite mit den wenigsten Referenzen 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

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)

Kategorien: Betriebssystemtheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Least frequently used (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.