WikiSort.ru - Не сортированное

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

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

Least recently used (Вытеснение давно неиспользуемых)

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

Most Recently Used (Наиболее недавно использовавшийся)

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

Псевдо-LRU

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

Сегментированный LRU

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

2-Way Set Associative (2-канальная ассоциативность)

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

Кэш прямого отображения (Direct-mapped cache)

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

Least-Frequently Used (Наименее часто используемый)

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

Adaptive Replacement Cache (Адаптивная замена)

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

Multi Queue Caching Algorithm (Алгоритм многопоточного кэширования)

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

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

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

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