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

Наиболее эффективное правило вытеснения — отбрасывать из кэша ту информацию, которая не понадобится в будущем дольше всего. Этот оптимальный алгоритм кэширования назвали алгоритмом Белади или алгоритмом предвидения. Так как в общем случае невозможно предсказать, когда именно в следующий раз потребуется именно эта информация, то на практике (опять же, в общем случае) подобная реализация невозможна. Практический минимум может быть вычислен только опытным путём, после чего можно сравнить с ним эффективность текущего алгоритма кэширования.

Least recently used (LRU): в первую очередь, вытесняется неиспользованный дольше всех. Этот алгоритм требует отслеживания того, что и когда использовалось, что может оказаться довольно накладно, особенно если нужно проводить дополнительную проверку, чтобы в этом убедиться. Общая реализация этого метода требует сохранения «бита возраста» для строк кэша и за счет этого происходит отслеживание наименее использованных строк (то есть за счет сравнения таких битов). В подобной реализации, при каждом обращении к строке кэша меняется «возраст» всех остальных строк. LRU на самом деле является семейством алгоритмов кэширования, в которое входит 2Q, разработанный Теодором Джонсоном и Деннисом Шаша, а также LRU/K от Пэта О’Нила, Бетти О’Нил и Герхарда Вейкума.

Most Recently Used (MRU): в отличие от LRU, в первую очередь вытесняется последний использованный элемент. В соответствии с источником[1], «Когда файл периодически сканируется по циклической схеме, MRU — наилучший алгоритм вытеснения». В источнике[2] авторы также подчеркивают, что для схем произвольного доступа и циклического сканирования больших наборов данных (иногда называемых схемами циклического доступа) алгоритмы кэширования MRU имеют больше попаданий по сравнению с LRU за счет их стремления к сохранению старых данных. Алгоритмы MRU наиболее полезны в случаях, когда чем старше элемент, тем больше обращений к нему происходит.

Псевдо-LRU (PLRU): Для кэшей с большой ассоциативностью (обычно более 4 каналов), необходимые ресурсы для реализации LRU становятся слишком большими. Если достаточна политика, что почти всегда нужно отбрасывать наименее используемый элемент, то в этом случае можно использовать алгоритм PLRU, требующий для элемента кэша только один бит.

Адрес в памяти может быть кэширован в виде адреса в кэше

Сегментированный LRU (Segmented LRU или SLRU): «SLRU-кэш делится на два сегмента. пробный сегмент и защищенный сегмент. Строки в каждом сегменте упорядочены от часто используемых к наименее используемым. Данные при промахах добавляются в кэш, причем в область последних использованных элементов пробного сегмента. Данные при попаданиях убираются где бы они не располагались и добавляются в область часто используемых элементов защищенного сегмента. К строкам защищенного сегмента обращения таким образом происходят по крайней мере дважды. Защищенный сегмент ограничен. Такой перенос строки из пробного сегмента в защищенный сегмент может вызвать перенос последней использованной (LRU) строки в защищенном сегменте в MRU-область пробного сегмента, давая этой линии второй шанс быть использованной перед вытеснением. Размер защищенного сегмента — SLRU-параметр, который меняется в зависимости от схемы работы ввода-вывода. Всякий раз когда данные должны быть вытеснены из кэша, строки запрашиваются из LRU-конца пробного сегмента.[3]»

2-канальная ассоциативность применяется для высокоскоростного процессорного кэша, где даже PLRU слишком медленный. Адрес нового элемента используется для вычисления одного из двух возможных местонахождений в кэше (в отведенной для этого области). По алгоритму LRU два элемента вытесняются. Это требует одного бита для пары строк кэша для указания которые из них использовались последними.

Кэш прямого отображения: для высокоскоростных кэшей процессора, где не хватает быстродействия 2-канального ассоциативного кэширования. Адрес нового элемента используется для вычисления местонахождения в кэше (в отведенной для этого области). Все, что было ранее, — вытесняется.

Least Frequently Used (LFU): LFU подсчитывает как часто используется элемент. Те элементы, обращения к которым происходят реже всего, вытесняются в первую очередь.

Adaptive Replacement Cache (ARC):[4] постоянно балансирует между LRU и LFU, что улучшает итоговый результат.

Multi Queue (MQ) caching algorithm:[5] (разработанный И. Жу, Дж. Ф. Филбином и Каем Ли).

Учитываются следующие моменты:

• Элементы с различной стоимостью: хранение элементов, запрос которых весьма до́рог, например, такие, получение которых потребует много времени.
• Элементы, требующие больше места в кэше: если элементы имеют разный размер, то контроллер кэша может попытаться вытеснить бо́льший элемент, чтобы сохранить несколько элементов поменьше.
• Элементы, устаревающие с течением времени: Некоторые кэши хранят устаревающую информацию (например, кэш новостей, DNS-кэш или кэш веб-браузера). Компьютер может вытеснить элементы вследствие их устаревания. В зависимости от размера кэша, кэширование новых элементов может потребовать вытеснение старых.

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