Наименее часто используется - Least frequently used

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

LFU иногда сочетается с Наименее недавно использованные алгоритм и называется LRFU.[1]

Выполнение

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

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

Проблемы

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

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

Смотрите также

Рекомендации

  1. ^ Донхи Ли; Чонму Чой; Чон-Хун Ким; Но, S.H .; Санг Люль Мин; Юкун Чо; Чонг Санг Ким. LRFU: спектр политик, включающий наименее недавно используемые и наименее часто используемые политики. Транзакции IEEE на компьютерах
  2. ^ Сильвано Маффейс. Алгоритмы управления кешем для гибких файловых систем. Обзор оценки эффективности ACM SIGMETRICS, Vol. 21, № 3
  3. ^ Уильям Столлингс. Операционные системы: внутреннее устройство и принципы проектирования, 7-е издание. 2012
  4. ^ Б.Т. Живкоз и А.Дж. Смит. Кэширование диска в больших базах данных и системах с разделением времени. МАСКОТЫ IEEE, 1997 г.

внешняя ссылка