Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритмы кэширования - Примеры

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

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

Least Recently Used

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

Most Recently Used

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

Псевдо-LRU

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

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

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

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

2-Way Set Associative

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

Кэш прямого отображения

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

Least-Frequently Used

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

Adaptive Replacement Cache

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

Multi Queue Caching Algorithm

Multi Queue caching algorithm:.

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

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

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