Найменш часто використаний
Найменш часто використаний, або LFU (абревіатура від англ. Least Frequently Used) є типом алгоритму кешу, який використовується для управління пам'яттю в комп'ютері. Стандартні характеристики цього методу містять у собі систему, яка відстежує скільки разів виконується посилання на блок в пам'яті. Коли кеш заповнений і вимагає більше місця система очистить з памяті елементи з найнижчою частотою посилань. LFU іноді поєднується з алгоритмом — «найменш недавно використаний» і називається LRFU (абревіатура від англ. Least Recently/Frequently Used).[1]
Найпростіший спосіб використовувати алгоритм LFU, це призначити лічильник для кожного блоку, який завантажується в кеш. Кожен раз, коли робиться посилання на цей блок, лічильник збільшується на одиницю. Коли кеш заповнюється і є новий блок, який чекає, щоб бути вставленим, система буде шукати блок з найменшим лічильником і видалить його з кешу.[2]
Хоча метод LFU може здаватися інтуїтивним підходом до управління пам'яттю, він не позбавлений недоліків. Розглянемо елемент в пам'яті, на який система посилається кілька разів протягом короткого періоду часу і доступ до нього не потрібен протягом тривалого періоду часу. Через те, як швидко система використовувала доступ до нього, його лічильник різко збільшиться, навіть якщо він не буде знову використовуватися пристойну кількість часу. Тоді інші блоки, які насправді можуть бути використані більш часто, схильні до видалення, просто тому, що доступ до них був отриманий через інший метод.[3]
Крім того, нові елементи, які тільки-но увійшли в кеш, вразливі до швидкого видалення знову, тому що вони починають з низького значення лічильника, незважаючи на те, що можуть використовуватися дуже часто після цього. Тому у чистому вигляді система LFU рідко зустрічається; замість цього, є гібриди, які використовують концепції LFU.[4]
- ↑ 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 [Архівовано 7 квітня 2017 у Wayback Machine.]. 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 [Архівовано 4 березня 2016 у Wayback Machine.]. IEEE MASCOTS, 1997
- An O(1) algorithm for implementing the LFU cache eviction scheme, 16 August 2010, by Ketan Shah, Anirban Mitra and Dhruv Matani