Använt minst
Använt minst eller Least Frequently Used (LFU) är en typ av cachesalgoritm som används för att hantera minne i en dator.
Standardegenskaperna för denna metod involverar att systemet håller reda på hur många gånger ett minnesblock refereras till. När cacheminnet är fullt och kräver mer utrymme, kommer systemet att skriva över objektet med den lägsta referensfrekvensen.
LFU kombineras ibland med en senast använt eller least recently used (LRU) algoritm och kallas då för LRFU.[1]
Genomförande redigera
Den enklaste metoden att använda en LFU-algoritm är att tilldela en räknare till varje block som ligger i cacheminnet. Varje gång något refererar till blocket ökas räknaren med ett. När cacheminnet når kapacitet och har ett nytt block som väntar på att införas, söker systemet efter blocket med den lägsta räknaren och tar bort det från cacheminnet.[2]
Problem redigera
Medan LFU-metoden kan verka som ett intuitivt tillvägagångssätt för minneshantering är det inte utan fel. Tänk på ett objekt i minnet som det refereras till upprepade gånger under en kort tid och sedan inte används en längre tid. På grund av hur snabbt räknare ökade kommer den ligga kvar i cacheminnet trots att den inte används under en lång tid efter en kort men intensiv användningsperiod. Detta gör att block som används av andra metoder som inte är lika intensiva fortare lämnar cacheminnet.[3]
Dessutom är nya objekt som precis lästs in i cacheminnet föremål för att tas bort mycket snart igen, eftersom de börjar med en låg räknare, trots att 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 hybrider som använder LFU-koncept.[4]
Se även redigera
Referenser redigera
- ^ Donghee Lee; Jongmoo Choi; Jong-Hun Kim; Noh, S.H.; Sang Lyul Min; Yookun Cho; Chong Sang Kim. LRFU: a spectrum of policies that subsumes the least recently used and least frequently used policies. IEEE Transactions on Computers
- ^ Silvano Maffeis. Cache Management Algorithms for Flexible Filesystems. ACM SIGMETRICS Performance Evaluation Review, Vol. 21, No. 3
- ^ William Stallings. Operating Systems: Internals and Design Principles 7th Edition. 2012
- ^ B.T. Zivkoz and A.J. Smith. Disk Caching in Large Database and Timeshared Systems. IEEE MASCOTS, 1997
Externa länkar redigera
- En O (1) -algoritm för genomförande av LFU-cachesutkastningsplanen, 16 augusti 2010, av Ketan Shah, Anirban Mitra och Dhruv Matani