Наименее часто используемый ( LFU ) — это тип алгоритма кэширования, используемый для управления памятью компьютера. Стандартные характеристики этого метода заключаются в том, что система отслеживает количество обращений к блоку в памяти . Когда кэш заполнен и требуется больше места, система удалит элемент с наименьшей опорной частотой.
LFU иногда комбинируется с алгоритмом «Наименее недавно использованный» и называется LRFU. [1]
Самый простой способ использовать алгоритм LFU — назначить счетчик каждому блоку, загружаемому в кэш. Каждый раз, когда делается ссылка на этот блок, счетчик увеличивается на единицу. Когда кеш достигнет емкости и появится новый блок, ожидающий вставки, система будет искать блок с наименьшим счетчиком и удалять его из кеша в случае ничьей (т. е. двух или более ключей с одинаковой частотой). ключ , который использовался реже всего, будет признан недействительным. [2]
Хотя метод LFU может показаться интуитивным подходом к управлению памятью, он не лишен недостатков. Рассмотрим элемент в памяти, к которому неоднократно обращаются в течение короткого периода времени и к которому больше не обращаются в течение длительного периода времени. Из-за того, как быстро к нему только что был осуществлен доступ, его счетчик резко увеличился, хотя он не будет использоваться снова в течение приличного количества времени. Это оставляет другие блоки, которые на самом деле могут использоваться чаще, уязвимыми для очистки просто потому, что к ним был получен доступ другим методом. [3]
Более того, новые элементы, которые только что попали в кэш, могут очень скоро снова быть удалены, поскольку они начинаются с низкого счетчика, даже если после этого они могут использоваться очень часто. Из-за подобных серьезных проблем явная система LFU встречается довольно редко; вместо этого существуют гибриды, использующие концепции LFU. [4]