Наименее часто используемый

Наименее часто используемый ( LFU ) — это тип алгоритма кэширования, используемый для управления памятью компьютера. Стандартные характеристики этого метода заключаются в том, что система отслеживает количество обращений к в блоку памяти . Когда кэш заполнен и требуется больше места, система удалит элемент с наименьшей опорной частотой.

LFU иногда комбинируется с алгоритмом «Наименее недавно использованный» и называется LRFU. ^[1]

Выполнение

Самый простой способ использовать алгоритм LFU — назначить счетчик каждому блоку, загружаемому в кэш. Каждый раз, когда делается ссылка на этот блок, счетчик увеличивается на единицу. Когда кеш достигнет емкости и в нем появится новый блок, ожидающий вставки, система будет искать блок с наименьшим счетчиком и удалять его из кеша в случае ничьей (т. е. двух или более ключей с одинаковой частотой). ключ , который использовался реже всего, будет признан недействительным. ^[2]

Идеальный ЛФУ: на каждую позицию в каталоге есть счетчик
Практичный LFU: есть счетчик предметов, хранящихся в кеше. Счетчик забывается, если элемент выселен.

Проблемы

Хотя метод LFU может показаться интуитивным подходом к управлению памятью, он не лишен недостатков. Рассмотрим элемент в памяти, к которому неоднократно обращаются в течение короткого периода времени и к которому больше не обращаются в течение длительного периода времени. Из-за того, как быстро к нему только что был осуществлен доступ, его счетчик резко увеличился, хотя он не будет использоваться снова в течение приличного времени. Это оставляет другие блоки, которые на самом деле могут использоваться чаще, уязвимыми для очистки просто потому, что к ним был получен доступ другим методом. ^[3]

Более того, новые элементы, которые только что попали в кэш, могут очень скоро снова быть удалены, поскольку они начинаются с низкого счетчика, даже если после этого они могут использоваться очень часто. Из-за подобных серьезных проблем явная система LFU встречается довольно редко; вместо этого существуют гибриды, использующие концепции LFU. ^[4]

См. также

Ссылки

^ Донхи Ли; Чонму Чой; Чон-Хун Ким; Ш. Нох; Сан Люль Мин; Юкун Чо; Чонг Сан Ким (декабрь 2001 г.). «LRFU: спектр политик, включающий наименее используемые в последнее время и наименее часто используемые политики» . Транзакции IEEE на компьютерах . 50 (12): 1352–1361. дои : 10.1109/TC.2001.970573 . S2CID 2636466 .
^ Сильвано Маффейс (декабрь 1993 г.). «Алгоритмы управления кэшем для гибких файловых систем» . Обзор оценки производительности ACM SIGMETRICS . 21 (2): 16–25. CiteSeerX 10.1.1.48.8399 . дои : 10.1145/174215.174219 . S2CID 7624318 .
^ Уильям Столлингс (2012). Операционные системы: внутреннее устройство и принципы проектирования (7-е изд.).
^ БТ Живкоз; Эй Джей Смит (1997). «Кэширование диска в больших базах данных и системах с разделением времени» . Труды Пятого международного симпозиума по моделированию, анализу и моделированию компьютерных и телекоммуникационных систем . дои : 10.1109/MASCOT.1997.567612 .

Внешние ссылки

Алгоритм O (1) для реализации схемы вытеснения кэша LFU , 16 августа 2010 г., Кетан Шах, Анирбан Митра и Дхрув Матани.

[1] Донхи Ли; Чонму Чой; Чон-Хун Ким; Ш. Нох; Сан Люль Мин; Юкун Чо; Чонг Сан Ким (декабрь 2001 г.). «LRFU: спектр политик, включающий наименее используемые в последнее время и наименее часто используемые политики» . Транзакции IEEE на компьютерах . 50 (12): 1352–1361. дои : 10.1109/TC.2001.970573 . S2CID 2636466 .

[2] Сильвано Маффейс (декабрь 1993 г.). «Алгоритмы управления кэшем для гибких файловых систем» . Обзор оценки производительности ACM SIGMETRICS . 21 (2): 16–25. CiteSeerX 10.1.1.48.8399 . дои : 10.1145/174215.174219 . S2CID 7624318 .

[3] Уильям Столлингс (2012). Операционные системы: внутреннее устройство и принципы проектирования (7-е изд.).

[4] БТ Живкоз; Эй Джей Смит (1997). «Кэширование диска в больших базах данных и системах с разделением времени» . Труды Пятого международного симпозиума по моделированию, анализу и моделированию компьютерных и телекоммуникационных систем . дои : 10.1109/MASCOT.1997.567612 .

[1]

[2]

[3]

[4]