В информатике под алгоритмами кэширования

1.2. Least recently used (Вытеснение дав-

(часто называемыми

алгоритмами

вытеснения

но неиспользуемых)

или политиками вытеснения, а также «алго-

ритмами/политиками

замещения»)

понимают

Least recently used (LRU): в первую очередь, вы-

оптимизацию инструкций — алгоритмы — особая

тесняется неиспользованный дольше всех. Этот ал-

компьютерная программа или аппаратно поддер-

горитм требует отслеживания того, что и когда ис-

живаемая структура, способная управлять кэшем

пользовалось, что может оказаться довольно наклад-

информации, хранимой в компьютере. Когда кэш за-

но, особенно если нужно проводить дополнительную

полнен, алгоритм должен выбрать, что именно нужно

проверку, чтобы в этом убедиться. Общая реализа-

удалить из него, чтобы иметь возможность записи (в

ция этого метода требует сохранения «бита возрас-

кэш) новой, более актуальной информации.

та» для строк кэша и за счет этого происходит отсле-

«Уровень попаданий» кэша означает то, насколько

живание наименее использованных строк (то есть за

часто искомые данные обнаруживаются в кэше. Более

счет сравнения таких битов). В подобной реализации,

эффективные политики вытеснения отслеживают об-

при каждом обращении к строке кэша меняется «воз-

ращения к наиболее используемой информации, что-

раст» всех остальных строк. LRU на самом деле яв-

бы улучшить уровень попаданий (при том же размере

ляется семейством алгоритмов кэширования, в кото-

кэша).

рое входит 2Q, разработанный Теодором Джонсоном

«Латентность» кэша означает, насколько быстро кэш

и Деннисом Шаша, а также LRU/K от Пэта О’Нила,

Бетти О’Нил и Герхарда Вейкума.

может вернуть запрошенные данные непосредствен-

но после запроса (в случае, если происходит «попада-

ние»). Более быстрые стратегии вытеснения обычно

1.3. Most Recently Used (Наиболее недав-

отслеживают наименее используемую информацию

— или, в случае кэша прямого отображения (direct-

но использовавшийся)

mapped cache), отсутствие информации, чтобы сни-

зить затраты времени на обновление информации.

Most Recently Used (MRU): в отличе от LRU, в

Каждая стратегия вытеснения является компромис-

первую очередь вытесняется последний использован-

сом между уровнем попаданий и латентностью.

ный элемент. В соответствии с источником [1], «Ко-

гда файл периодически сканируется по циклической

схеме, MRU — наилучший алгоритм вытеснения».

В источнике [2] авторы также подчеркивают, что для

схем произвольного доступа и циклического скани-

1. Примеры

рования больших наборов данных (иногда называе-

мых схемами циклического доступа) алгоритмы кэ-

ширования MRU имеют больше попаданий по срав-

1.1. Алгоритм Белади

нению с LRU за счет их стремления к сохранению

старых данных. Алгоритмы MRU наиболее полезны

в случаях, когда чем старше элемент, тем больше об-

Наиболее эффективное правило вытеснения - отбра-

ращений к нему происходит.

сывать из кэша ту информацию, которая не понадо-

бится в будущем дольше всего. Этот оптимальный

1.4. Псевдо-LRU

алгоритм кэширования назвали алгоритмом Белади

или алгоритмом предвидения. Так как в общем слу-

чае невозможно предсказать когда именно в следую-

Псевдо-LRU (PLRU): Для кэшей с большой

щий раз потребуется именно эта информация, то на

ассоциативностью (обычно >4 каналов), цена ре-

практике (опять же, в общем случае) подобная ре-

ализации LRU становится непомерно высока.

ализация невозможна. Практический минимум мо-

Если достаточна схема, что почти всегда нужно

жет быть вычислен только опытным путем, после чего

отбрасывать наименее используемый элемент, то в

можно сравнить с ним эффективность текущего алго-

этом случае можно использовать алгоритм PLRU,

ритма кэширования.

требующий для элемента кэша только один бит.

2

1 ПРИМЕРЫ