Информатика · объяснение и практика
LRU: как последнее обращение меняет следующего кандидата на удаление
LRU на трассе запросов: порядок последнего использования, попадание и вытеснение, различие с FIFO и сроком годности.

В теме Структуры данных · Учебная карта
В маршруте Случайность, численные оценки и целостность · 10 тем
Главная мысль
LRU вытесняет элемент, к которому дольше всего не обращались среди находящихся в кэше. Попадание обновляет его положение в порядке недавнего использования. LRU не определяет срок годности данных и не означает, что удалённый элемент исчез из основного хранилища.
Порядок меняется даже без загрузки
Пусть кэш вмещает два элемента, изначально пуст и принимает запросы А, Б, А, В. После первых двух запросов порядок от старого к новому равен А, Б. Третий запрос А — попадание, но порядок становится Б, А. При запросе В нужно место, поэтому вытесняется Б.
Если оставить порядок прежним после попадания А, получится другая политика. FIFO ориентируется на поступление, а не на последнее использование; в нашей трассе он вытеснил бы А. Поэтому список содержимого без порядка недостаточен для проверки LRU. Нужно фиксировать, кто был использован последним.
Считаем промахи в продолжении
Продолжим трассу запросом Б. После В в кэше находятся А, В, старее А. Б отсутствует, значит случается промах и вытесняется А. Полная трасса А, Б, А, В, Б содержит четыре промаха и одно попадание. Вместимость не превышалась, каждая новая загрузка при полном кэше сопровождалась одним удалением.
При другом размере результат способен измениться. Для вместимости три все А, Б и В поместились бы вместе, а повторный Б стал бы попаданием. Сравнивая правила вытеснения, нужно держать размер и исходное состояние одинаковыми; иначе нельзя понять, какая именно причина уменьшила число промахов.
Пример
Кэш 2: А→[А], Б→[А,Б], А→[Б,А], В→[А,В], Б→[В,Б].
В квадратных скобках порядок от давно использованного к недавнему. Попадание А передвинуло его, сохранив содержимое.
Недавность не означает свежесть результата
Кэшированное расписание может часто запрашиваться и всё равно устареть после изменения исходных данных. LRU выбирает, чем пожертвовать при нехватке места, а проверка актуальности решает другую задачу. Срок действия, версия источника или явная инвалидизация могут понадобиться независимо от частоты чтения.
Для кэширования функций также важно, что результат действительно допускает повторное использование. Побочные эффекты и изменяемые объекты требуют осторожности. Даже потокобезопасная структура не обязана гарантировать единственный запуск вычисления при одновременном первом запросе; это отдельное свойство, которое нельзя вывести из названия LRU.
От чтения к действию
А теперь — вы
Частые вопросы
LRU удаляет самый редко используемый элемент?
Нет. Он смотрит на давность последнего обращения. Общая частота относится к LFU.
Попадание ничего не меняет?
Содержимое может остаться тем же, но порядок недавности обновляется — это влияет на следующее вытеснение.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
LFU: частота обращений и правило разрешения равенства
LFU на короткой трассе: счётчики обращений, частота против недавности и явное правило для одинаковых частот.
Открыть темуЛокальность памяти: почему порядок обхода меняет обращения к строкам кэша
Временная и пространственная локальность памяти: собственные трассы обращений, размер блока и пределы предсказания.
Открыть тему