Least frequently used

Least frequently used

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 (deutsch: „Seite“) 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.

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


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Least Frequently Used — Algorithmes de remplacement des lignes de cache Il existe différents types de mémoire cache, dont l organisation amène des situations où une ligne de la mémoire principale est mappé sur un ensemble de lignes de mémoire cache remplie. Il faut donc …   Wikipédia en Français

  • Least recently used — (LRU) („Am längsten nicht verwendet“) ist eine Seitenverdrängungsstrategie für Cache Speicher. Sie lagert diejenige Seite aus, deren letzte Referenzierung zeitlich am längsten zurückliegt. Inhaltsverzeichnis 1 Bewertung 1.1 Vorteile 1.2 Nachteile …   Deutsch Wikipedia

  • Last recently used — Least recently used (LRU) („Am längsten nicht verwendet“) ist eine Seitenverdrängungsstrategie für Cache Speicher. Sie lagert diejenige Seite aus, deren letzte Referenzierung zeitlich am längsten zurückliegt. Inhaltsverzeichnis 1 Grundlagen 2… …   Deutsch Wikipedia

  • Least Storm Petrel — Conservation status Least Concern (IUCN 3.1) Scientific classification Kin …   Wikipedia

  • least, less, lest — Least is the superlative degree of little; less is the comparative: Toby has less money that I have; in fact, she has the least money of any girl in our group. Both least and less always refer to amount, size, or importance: less value, least… …   Dictionary of problem words and expressions

  • Least significant bit — In computing, the least significant bit (lsb) is the bit position in a binary integer giving the units value, that is, determining whether the number is even or odd. The lsb is sometimes referred to as the right most bit, due to the convention in …   Wikipedia

  • Least Storm-petrel — Taxobox name = Least Storm petrel status = LC | status system = IUCN3.1 regnum = Animalia phylum = Chordata classis = Aves ordo = Procellariiformes familia = Hydrobatidae genus = Halocyptena genus authority = Coues, 1864 species = H. microsoma… …   Wikipedia

  • Yiddish words used by English-speaking Jews — Yiddish words may be used in a primarily English language context. An English sentence that uses these words sometimes is said to be in Yinglish, however the primary meaning of Yinglish is an anglicism used in Yiddish. This secondary sense of the …   Wikipedia

  • List of terms used for Germans — There are many alternative ways to describe the people of Germany, though in English the official designated nationality as well as the standard noun is German. (see also demonym). During the early Renaissance, German implied that the person… …   Wikipedia

  • Ordinary least squares — This article is about the statistical properties of unweighted linear regression analysis. For more general regression analysis, see regression analysis. For linear regression on a single variable, see simple linear regression. For the… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”