Алгоритмы кэширования

В информатике под алгоритмами кэширования (часто называемыми алгоритмами вытеснения или политиками вытеснения, а также «алгоритмами/политиками замещения») понимают оптимизацию инструкций — алгоритмы — особая компьютерная программа или аппаратно поддерживаемая структура, способная управлять кэшем информации, хранимой в компьютере. Когда кэш заполнен, алгоритм должен выбрать, что именно нужно удалить из него, чтобы иметь возможность записи (в кэш) новой, более актуальной информации.

«Уровень попаданий» кэша означает то, насколько часто искомые данные обнаруживаются в кэше. Более эффективные политики вытеснения отслеживают обращения к наиболее используемой информации, чтобы улучшить уровень попаданий (при том же размере кэша).

«Латентность» кэша означает, насколько быстро кэш может вернуть запрошенные данные непосредственно после запроса (в случае, если происходит «попадание»). Более быстрые стратегии вытеснения обычно отслеживают наименее используемую информацию — или, в случае кэша прямого отображения (direct-mapped cache), отсутствие информации, чтобы снизить затраты времени на обновление информации.

Каждая стратегия вытеснения является компромиссом между уровнем попаданий и латентностью.

Источник: Википедия