Last recently used

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

Grundlagen

Ein Cache ist ein schneller Pufferspeicher, der Daten aus langsamen Speichern zwischenlagert und so schneller verfügbar macht. Die kleinste Einheit an Daten, die zwischen beiden Speicherformen ausgetauscht werden, ist eine Speicherseite (Kachel). Ein Cache kann nur eine geringe Anzahl an Speicherseiten fassen. Ist der Cache voll, muss für jede neu einzulagernde Seite eine alte weichen. Die Seitenverdrängungsstrategie legt fest, welche Seiten als „alt“ betrachtet und ausgelagert werden.

Wird auf die Daten einer Seite zugegriffen, so sagt man, die Seite werde „referenziert“. Befindet sich eine referenzierte Seite gerade im Cache, so spricht man von einem „Treffer“ (Cache Hit), ist dies nicht der Fall, entsprechend von „keinem Treffer“ (Cache Miss). Das durchschnittliche Verhältnis „Treffer“ zu „kein Treffer“ ist die „Trefferrate“.

Bewertung

Vorteile

  • Die Strategie ist leicht implementierbar und erfordert kaum Verwaltungsaufwand.
  • Sie wählt gezielt Seiten aus, die in letzter Zeit nicht verwendet wurden.

Nachteile

  • Nur mittelmäßige Trefferrate. Wichtiger als die Frage, ob eine Seite referenziert wurde, ist oftmals die Frage, wie oft sie referenziert wurde. Least recently used nimmt auf diese Tatsache keine Rücksicht, was meist zu einer nur mittelmäßigen Trefferrate führt. Daher gelten Verfahren wie Least frequently used (LFU) als effizienter.

Implementierung

Least recently used wird mit Hilfe einer Warteschlange umgesetzt, in der alle eingelagerten Seiten darauf warten, ausgelagert zu werden. Muss eine Seite ausgelagert werden, so trifft es stets diejenige an der Spitze der Warteschlange (d.h. wähle Seite am Ende der Liste als zu ersetzende Seite). Wird eine Seite referenziert, so verlässt sie ihre Position und reiht sich am Ende der Schlange neu ein.

Beispiel

A              B               D
B     -B->     A     -D->      B
C              C               A
   Cache- Hit     Cache- Miss

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

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

  • last in, first out — ( LIFO) One of the methods for accounting for business inventory permitted by generally accepted accounting principals ( GAAP). American Banker Glossary ( LIFO) An accounting method that fixes the cost of goods sold to the most recent purchases.… …   Financial and business terms

  • last — last1 [last, läst] adj. [ME laste, earlier latest, latst < OE latost, superl. of adj. læt, adv. late: see LATE] 1. alt. superl. of LATE 2. being or coming after all others in place; farthest from the first; hindmost 3. coming after all others… …   English World dictionary

  • last in, first out — used for saying that the person who started to work for an employer most recently should be the first to leave if the number of workers is reduced …   English dictionary

  • last — last1 [ læst ] function word *** Last can be used in the following ways: as a determiner (followed by a noun): I saw him last night. I wasn t here last time. as an adjective (after a determiner and before a noun): My last job was in London. I ate …   Usage of the words and phrases in modern English

  • Last.fm — Infobox Website name = Last.fm favicon = caption = url = [http://www.last.fm/ www.last.fm] commercial = Yes type = Music, Statistics Community registration = Free, or subscribe for £1.50 per month ($3 USD) owner = CBS Interactive language =… …   Wikipedia

  • last — I UK [lɑːst] / US [læst] adjective, adverb, determiner, noun, pronoun *** Summary: Last can be used in the following ways: as a determiner (followed by a noun): I saw him last night. ♦ I wasn t here last time. as an adjective (after a determiner… …   English dictionary

  • last — last1 W1S1 [la:st US læst] determiner, adj 1.) most recent or nearest to the present time →↑next (12) ▪ I hadn t seen him since the last meeting. last night/week/year etc ▪ Did you see the game on TV last night? ▪ The law was passed last August.… …   Dictionary of contemporary English

  • Last mile — The last mile is the final leg of delivering connectivity from a communications provider to a customer. Usually referred to by the telecommunications and cable television industries, it is typically seen as an expensive challenge because fanning… …   Wikipedia

  • last — 1 determiner 1 most recent; the nearest one to the present time: I haven t seen you since the last meeting. | last night/week/year etc: Did you watch the game on TV last night? | Fashion has changed in the last twenty years. | (the) last time… …   Longman dictionary of contemporary English

  • Last Supper — For other uses, see The Last Supper (disambiguation). Depictions of the Last Supper in Christian art have been undertaken by artistic masters for centuries, Leonardo da Vinci s late 1490s mural painting in Milan, Italy, being perhaps the best… …   Wikipedia

Share the article and excerpts

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