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

Материал из Seo Wiki - Поисковая Оптимизация и Программирование
Перейти к навигацииПерейти к поиску
На эту статью не ссылаются другие статьи Википедии.
Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.

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

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

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

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

Примеры

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

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

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, требующий для элемента кэша только один бит.

Файл:Cache,associative-fill-both.png
Адрес в памяти может быть кэширован в виде адреса в кэше

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

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

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

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

Кэш прямого отображения (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-кэш или кэш веб-браузера). Компьютер может вытеснить элементы вследствие их устаревания. В зависимости от размера кэша, кэширование новых элементов может потребовать вытеснение старых.

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

Смотри также

Ссылки

  1. ↑ Hong-Tai Chou”. David J. Dewitt: http://www.vldb.org/conf/1985/P127.PDF
  2. ↑ Semantic Data Caching and Replacement: http://www.vldb.org/conf/1996/P330.PDF
  3. ↑ Ramakrishna Karedla, J. Spencer Love, and Bradley G. Wherry. Caching Strategies to Improve Disk System Performance. In Computer, 1994.
  4. ↑ http://www.usenix.org/events/fast03/tech/full_papers/megiddo/megiddo.pdf
  5. ↑ [1]

Дополнительные источники

de:Cache-Algorithmus en:Cache algorithms fr:Algorithmes de remplacement des lignes de cache id:Least Recently Used ja:キャッシュアルゴリズム tr:Önbellek algoritmaları zh:快取文件置換機制

Если вам нравится SbUP.com Сайт, вы можете поддержать его - BTC: bc1qppjcl3c2cyjazy6lepmrv3fh6ke9mxs7zpfky0 , TRC20 и ещё....

→

Источник — https://mail.sbup.com:443/w/index.php?title=Алгоритмы_кэширования&oldid=8493