Används minst ofta

Least Frequently Used ( LFU ) är en typ av cachealgoritm som används för att hantera minne i en dator. Standardegenskaperna för denna metod innebär att systemet håller reda på hur många gånger ett block refereras i minnet . När cachen är full och kräver mer utrymme kommer systemet att rensa objektet med den lägsta referensfrekvensen.

LFU kombineras ibland med en minst nyligen använd algoritm och kallas LRFU.

Genomförande

Den enklaste metoden att använda en LFU-algoritm är att tilldela en räknare till varje block som laddas in i cachen. Varje gång en hänvisning görs till det blocket ökas räknaren med en. När cachen når kapacitet och har ett nytt block som väntar på att infogas kommer systemet att söka efter blocket med den lägsta räknaren och ta bort det från cachen.

• Idealisk LFU: det finns en räknare för varje artikel i katalogen
• Praktisk LFU: det finns en räknare för objekten lagrade i cachen. Disken glöms bort om föremålet vräks.

Problem

Även om LFU-metoden kan verka som en intuitiv metod för minneshantering är den inte felfri. Betrakta ett objekt i minnet som refereras upprepade gånger under en kort tidsperiod och som inte nås igen under en längre tidsperiod. På grund av hur snabbt den just nåddes har dess disk ökat drastiskt även om den inte kommer att användas igen under en anständig tid. Detta gör att andra block som faktiskt kan användas oftare är känsliga för rensning bara för att de nåddes med en annan metod.

Dessutom kommer nya objekt som precis kommit in i cachen att tas bort mycket snart igen, eftersom de börjar med en låg räknare, även om de kan användas mycket ofta efter det. På grund av stora problem som dessa är ett explicit LFU-system ganska ovanligt; istället finns det hybrider som använder LFU-koncept.

Se även

• Personsökning
• Sidersättningsalgoritm
• Används inte ofta

externa länkar

• En O(1)-algoritm för implementering av LFU-cache-eviction-schemat, 16 augusti 2010, av Ketan Shah, Anirban Mitra och Dhruv Matani