Кэширование, назначение, организация и алгоритмы

Кэш (англ. cache, от фр. cacher]— промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена с наибольшей вероятностью. Доступ к данным в кэше осуществляется быстрее, чем выборка исходных данных из более медленной памяти или удаленного источника, однако её объём существенно ограничен по сравнению с хранилищем исходных данных.

Кэш — это память с большей скоростью доступа, предназначенная для ускорения обращения к данным, содержащимся постоянно в памяти с меньшей скоростью доступа. Кэширование применяется ЦПУ, жёсткими дисками, браузерами, веб-серверами, службами DNS и WINS.

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

Когда клиент кэша (ЦПУ, веб-браузер, операционная система) обращается к данным, прежде всего исследуется кэш. Если в кэше найдена запись с идентификатором, совпадающим с идентификатором затребованного элемента данных, то используются элементы данных в кэше. Такой случай называется попаданием кэша. Если в кэше не найдена запись, содержащая затребованный элемент данных, то он читается из основной памяти в кэш, и становится доступным для последующих обращений. Такой случай называется промахом кэша. Процент обращений к кэшу, когда в нём найден результат, называется уровнем попаданий, или коэффициентом попаданий в кэш.

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

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

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

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

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

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

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

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

Least recently used (LRU): в первую очередь, вытесняется неиспользованный дольше всех. Этот алгоритм требует отслеживания того, что и когда использовалось, что может оказаться довольно накладно, особенно если нужно проводить дополнительную проверку, чтобы в этом убедиться. Общая реализация этого метода требует сохранения «бита возраста» для строк кэша и за счет этого происходит отслеживание наименее использованных строк (то есть за счет сравнения таких битов). В подобной реализации, при каждом обращении к строке кэша меняется «возраст» всех остальных строк.

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

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

Псевдо-LRU

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

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

FIFO

Если искомый элемент не находится в кеше, он вставляется в хвост очереди. Если нужно освободить место, удаляются элементы из головы очереди. Таким образом вытесняется элемент, находящийся в кэше дольше всех.

Date: 2016-06-06; view: 1641; Нарушение авторских прав