Политики замены кеша - Cache replacement policies

Было высказано предположение, что Алгоритм замены страницы быть слился в эту статью. (Обсуждать) Предлагается с июля 2020 года.

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

Обзор

Среднее время обращения к памяти составляет^[1]

${ displaystyle T = m times T_ {m} + T_ {h} + E}$

куда

${ displaystyle m}$ = коэффициент промахов = 1 - (коэффициент попадания)

${ displaystyle T_ {m}}$ = время для выполнения доступа к основной памяти в случае промаха (или, с многоуровневым кешем, среднее время обращения к памяти для следующего более низкого кеша)

${ displaystyle T_ {h}}$= задержка: время обращения к кешу (должно быть одинаковым для попаданий и промахов)

${ displaystyle E}$ = различные вторичные эффекты, такие как эффекты очереди в многопроцессорных системах

Есть два основных показателя качества кеша: задержка и частота попаданий. Есть также ряд второстепенных факторов, влияющих на производительность кеша.^[1]

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

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

Каждая стратегия замены - это компромисс между частотой совпадений и задержкой.

Измерения частоты попаданий обычно выполняются на ориентир Приложения. Фактический коэффициент попадания сильно варьируется от одного приложения к другому. В частности, приложения для потоковой передачи видео и аудио часто имеют коэффициент совпадений, близкий к нулю, потому что каждый бит данных в потоке считывается один раз в первый раз (принудительный промах), используется, а затем никогда не читается и не записывается снова. Хуже того, многие алгоритмы кеширования (в частности, LRU) позволяют этим потоковым данным заполнять кеш, выталкивая из кеша информацию, которая вскоре будет использоваться снова (загрязнение кеша ).^[2]

Другие вещи, которые следует учитывать:

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

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

Политики

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

В наиболее эффективный алгоритм кэширования всегда будет отбрасывать информацию, которая не понадобится в течение долгого времени в будущем. Этот оптимальный результат называется Bélády оптимальный алгоритм / просто оптимальная политика замены или алгоритм ясновидения. Поскольку, как правило, невозможно предсказать, насколько далеко в будущем потребуется информация, на практике это, как правило, невозможно. Практический минимум можно рассчитать только после экспериментов, и можно сравнить эффективность фактически выбранного алгоритма кеширования.

В тот момент, когда ошибка страницы происходит, в памяти находится какой-то набор страниц. В этом примере к последовательности «5», «0», «1» обращаются кадры 1, 2 и 3 соответственно. Затем, когда осуществляется доступ к «2», он заменяет значение «5», которое находится в кадре 1, поскольку он предсказывает, что значение «5» не будет доступно в ближайшем будущем. Поскольку реальная операционная система общего назначения не может фактически предсказать, когда будет осуществлен доступ к «5», алгоритм Белади не может быть реализован в такой системе.

Первый пришел - первый ушел (FIFO)

При использовании этого алгоритма кеш ведет себя так же, как и Очередь FIFO. Кэш удаляет блоки в том порядке, в котором они были добавлены, независимо от того, как часто и сколько раз к ним обращались раньше.

Последний пришел - первый ушел (LIFO) или первым пришел последний ушел (FILO)

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

Наименее недавно использованный (LRU)

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

Последовательность доступа для приведенного ниже примера - A B C D E D F.

В приведенном выше примере, когда A B C D устанавливается в блоки с порядковыми номерами (приращение 1 для каждого нового доступа), и когда E получает доступ, это промах, и его необходимо установить в одном из блоков. Согласно алгоритму LRU, поскольку A имеет самый низкий ранг (A (0)), E заменит A.

LRU, как и многие другие политики замещения, можно охарактеризовать с помощью поля перехода состояний в векторном пространстве, которое определяет изменения состояния динамического кэша, аналогично тому, как электромагнитное поле определяет движение помещенной в него заряженной частицы.^[5]

Время с учетом наименее недавно использованного (TLRU)

Время с учетом наименее недавно использованного (TLRU)^[6] - это вариант LRU, разработанный для ситуации, когда хранимое в кэше содержимое имеет допустимый срок службы. Алгоритм подходит для приложений сетевого кеширования, таких как Информационно-ориентированные сети (ICN), Сети доставки контента (CDN) и распределенные сети в целом. TLRU вводит новый термин: TTU (время использования). TTU - это отметка времени контента / страницы, которая определяет время удобства использования для контента на основе местоположения контента и объявления издателя контента. Благодаря этой метке времени, основанной на местоположении, TTU предоставляет больше возможностей локальному администратору для регулирования в сетевом хранилище. В алгоритме TLRU, когда поступает часть контента, узел кеша вычисляет локальное значение TTU на основе значения TTU, назначенного издатель контента. Локальное значение TTU рассчитывается с использованием локально определенной функции. После вычисления локального значения TTU замена содержимого выполняется на подмножестве общего содержимого, хранящегося в узле кэша. TLRU гарантирует, что менее популярный и небольшой жизненный контент должен быть заменен входящим контентом.

Последний использованный (MRU)

В отличие от LRU, отбрасывает в первую очередь последние использованные элементы. В выводах, представленных на 11-м Конференция VLDB, Чоу и ДеВитт отметили, что «когда файл многократно сканируется в эталонном шаблоне [Looping Sequential], MRU является лучшим алгоритм замены."^[7] Впоследствии другие исследователи, представившие на 22-й конференции VLDB, отметили, что для шаблонов произвольного доступа и повторного сканирования больших наборов данных (иногда называемых шаблонами циклического доступа) алгоритмы кэширования MRU имеют больше совпадений, чем LRU, из-за их тенденции сохранять более старые данные.^[8] Алгоритмы MRU наиболее полезны в ситуациях, когда чем старше элемент, тем выше вероятность доступа к нему.

Последовательность доступа для приведенного ниже примера: A B C D E C D B.

Здесь A B C D помещаются в кэш, поскольку еще есть свободное место. При 5-м доступе E мы видим, что блок, который удерживал D, теперь заменен на E, поскольку этот блок использовался совсем недавно. Другой доступ к C и при следующем доступе к D, C заменяется, поскольку это был блок, к которому осуществлялся доступ непосредственно перед D, и так далее.

Псевдо-LRU (PLRU)

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

В следующем примере показано, как Bits работают как двоичное дерево 1-битных указателей, которые указывают на менее недавно использованное поддерево. Переход по цепочке указателей на листовой узел определяет кандидата на замену. При доступе все указатели в цепочке от листового узла пути доступа к корневому узлу устанавливаются так, чтобы указывать на поддерево, которое не содержит доступный путь.

Последовательность доступа - A B C D E.

Принцип здесь прост для понимания, если мы посмотрим только на указатели стрелок. Когда есть доступ к значению, скажем 'A', и мы не можем найти его в кеше, мы загружаем его из памяти и поместите его в блок, на который в данный момент указывают стрелки, идя сверху вниз. После того, как мы разместили этот блок, мы переверните те же стрелки, чтобы они указывали в противоположную сторону. В приведенном выше примере мы видим, как была размещена буква «A», за которой следовали «B», «C» и «D». Затем, когда кеш заполнился, «E» заменил «A», потому что именно туда в это время указывали стрелки, а стрелки, ведущие к «A», были перевернуты, чтобы указывать в противоположном направлении. Затем стрелки привели к «B», который будет блоком, заменяемым при следующем промахе кеша.

Случайная замена (RR)

Случайным образом выбирает предмет-кандидат и при необходимости отбрасывает его, чтобы освободить место. Этот алгоритм не требует хранения какой-либо информации об истории доступа. Для простоты он использовался в ARM процессоры.^[9] Он допускает эффективное стохастическое моделирование.^[10]

Последовательность доступа для приведенного ниже примера: A B C D E B D F

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

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

Наименее часто используемые (LFU)

Подсчитывает, как часто требуется предмет. Те, которые используются реже, сначала выбрасываются. Это работает очень похоже на LRU, за исключением того, что вместо сохранения значения того, как недавно был осуществлен доступ к блоку, мы сохраняем значение того, сколько раз к нему обращались. Поэтому, конечно же, при выполнении последовательности доступа мы заменим из нашего кеша блок, который использовался наименьшее количество раз. Например, если A использовался (был осуществлен доступ) 5 раз, а B использовался 3 раза, а другие C и D использовались каждый раз по 10, мы заменим B.

Наименее часто используемые в последнее время (LFRU)

Наименее часто используемые в последнее время (LFRU)^[12] Схема замены кеша сочетает в себе преимущества схем LFU и LRU. LFRU подходит для приложений кэширования «в сети», таких как Информационно-ориентированные сети (ICN), Сети доставки контента (CDN) и распределенные сети в целом. В LFRU кэш разделен на два раздела, которые называются привилегированными и непривилегированными. Привилегированный раздел можно определить как защищенный. Если контент очень популярен, он помещается в привилегированный раздел. Замена привилегированного раздела выполняется следующим образом: LFRU вытесняет контент из непривилегированного раздела, перемещает контент из привилегированного раздела в непривилегированный раздел и, наконец, вставляет новый контент в привилегированный раздел. В описанной выше процедуре LRU используется для привилегированного раздела, а приближенная схема LFU (ALFU) используется для непривилегированного раздела, отсюда и сокращение LFRU.

Основная идея состоит в том, чтобы отфильтровать популярное локально содержимое с помощью схемы ALFU и перенести популярное содержимое в один из привилегированных разделов.

LFU с динамическим старением (LFUDA)

Вариант под названием LFU с динамическим старением (LFUDA), который использует динамическое старение для адаптации к изменениям в наборе популярных объектов. Он добавляет фактор возраста кэша к счетчику ссылок, когда новый объект добавляется в кэш или когда на существующий объект повторно ссылаются. LFUDA увеличивает возраст кеша при удалении блоков, устанавливая для него значение ключа удаленного объекта. Таким образом, возраст кеша всегда меньше или равен минимальному значению ключа в кэше.^[13] Предположим, что когда к объекту часто обращались в прошлом, а теперь он становится непопулярным, он будет оставаться в кеше в течение длительного времени, не позволяя новым или менее популярным объектам заменить его. Таким образом, это динамическое старение вводится, чтобы уменьшить количество таких объектов, тем самым делая их пригодными для замены. Преимущество LFUDA в том, что он снижает загрязнение кеша вызвано LFU, когда размер кеша очень мал. Когда размер кэша большой, достаточно нескольких решений по замене и загрязнение кеша не будет проблемой.

Набор с низкой периодичностью между ссылками (LIRS)

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

На приведенном выше рисунке «x» означает, что доступ к блоку осуществляется в момент времени t. Предположим, что если доступ к блоку A1 осуществляется в момент времени 1, то Recency станет 0, поскольку это первый доступный блок, и IRR будет равно 1, поскольку он предсказывает, что A1 будет доступен снова во время 3. Во время 2 с момента доступа A4, недавность станет 0 для A4 и 1 для A1, потому что A4 является последним доступным объектом, а IRR станет 4 и будет продолжаться. В момент времени 10 алгоритм LIRS будет иметь два набора: LIR set = {A1, A2} и набор HIR = {A3, A4, A5}. Теперь в момент 10, если есть доступ к A4, происходит промах. Алгоритм LIRS теперь удаляет A5 вместо A2 из-за его наибольшей давности.

ЧАСЫ-Pro

Алгоритм LRU не может быть напрямую реализован на критическом пути компьютерных систем, таких как операционные системы из-за высоких накладных расходов. Приближение LRU, называемое ЧАСЫ обычно используется для реализации. Точно так же CLOCK-Pro является приближением LIRS для недорогой реализации в системах.^[15] CLOCK-Pro находится под базовым ЧАСЫ framework, но имеет три основных достоинства. Во-первых, CLOCK-Pro имеет три «стрелки часов» в отличие от простой структуры CLOCK, в которой используется только одна «стрелка». С помощью трех рук CLOCK-Pro может приблизительно измерить расстояние повторного использования доступа к данным. Во-вторых, сохраняются все достоинства LIRS, такие как быстрое исключение элементов данных с одноразовым доступом и / или данных с низкой локализацией. В-третьих, CLOCK-Pro по сложности такой же, как и CLOCK, поэтому его легко реализовать по невысокой цене. Реализация замены буферного кеша в текущей версии Linux представляет собой комбинацию LRU и CLOCK-Pro.^[16][17]

Адаптивный кэш замещения (ARC)

Постоянно балансирует между LRU и LFU, чтобы улучшить общий результат.^[18] ARC улучшает SLRU за счет использования информации о недавно удаленных элементах кэша для динамической корректировки размера защищенного сегмента и испытательного сегмента, чтобы максимально использовать доступное пространство кэша. Алгоритм адаптивной замены поясняется на примере.^[19]

AdaptiveClimb (AC)

Использует недавнее попадание / промах для регулировки прыжка, где при подъеме любое попадание переключает позицию на один слот вверх, а в LRU попадание переключает положение удара на вершину. Таким образом, мы получаем выгоду от оптимальности набора высоты, когда программа находится в фиксированной области действия, и быстрой адаптации к новой области действия, как это делает LRU. ^[20] Также поддерживайте совместное использование кеша между ядрами, выпуская дополнительные функции, когда ссылки находятся в верхней части кеша.

Часы с адаптивной заменой (CAR)

Сочетает в себе преимущества Adaptive Replacement Cache (ARC) и ЧАСЫ. CAR имеет производительность, сравнимую с ARC, и значительно превосходит LRU и CLOCK. Как и ARC, CAR самонастраивается и не требует определенных пользователем магических параметров. Он использует 4 двусвязных списка: два тактовых сигнала T1 и T2 и два простых LRU-списка B1 и B2. Часы T1 хранят страницы на основе «недавности» или «краткосрочной полезности», тогда как T2 хранит страницы с «частотой» или «долгосрочной полезностью». T1 и T2 содержат те страницы, которые находятся в кэше, а B1 и B2 содержат страницы, которые недавно были исключены из T1 и T2 соответственно. Алгоритм пытается поддерживать размер этих списков B1≈T2 и B2≈T1. Новые страницы вставляются в T1 или T2. Если есть попадание в B1, размер T1 увеличивается, и аналогично, если есть попадание в B2, размер T1 уменьшается. Используемое правило адаптации имеет тот же принцип, что и в ARC, инвестируйте больше в списки, которые будут давать больше совпадений при добавлении к ним дополнительных страниц.

Мульти очереди (MQ)

Алгоритм с несколькими очередями или MQ был разработан для повышения производительности буферного кеша второго уровня, например, для буферный кеш сервера. Он представлен в статье Чжоу, Филбина и Ли.^[21] Кэш MQ содержит м количество очередей LRU: Q₀, Q₁, ..., Q_м-1. Здесь значение м представляет собой иерархию, основанную на времени жизни всех блоков в этой конкретной очереди. Например, если j>я, блоки в Q_j будут иметь более длительный срок службы, чем в Q_я. В дополнение к ним есть еще один буфер истории Q_из, очередь, которая поддерживает список всех идентификаторов блоков вместе с их частотами доступа. Когда Q_из заполнен самый старый идентификатор удаляется. Блоки остаются в очередях LRU в течение заданного времени жизни, которое динамически определяется алгоритмом MQ как максимальное временное расстояние между двумя доступами к одному и тому же файлу или количество блоков кэша, в зависимости от того, что больше. Если на блок не ссылались в течение его жизни, он понижается в должности с Q_я к Q_я−1 или исключен из кеша, если он находится в Q₀. Каждая очередь также имеет максимальное количество обращений; если блок в очереди Q_я обращаются более 2^я раз этот блок повышается до Q_я+1 пока к нему не обращаются более 2^я+1 раз или его срок службы истекает. В рамках данной очереди блоки ранжируются по давности доступа в соответствии с LRU.^[22]

Из рис. 1 видно, как м Очереди LRU помещаются в кеш. Также посмотрите на рис., Как Q_из хранит идентификаторы блоков и соответствующие им частоты доступа. а был помещен в Q₀ поскольку недавно к нему обращались только один раз, и мы можем проверить в Q_из как б и c были помещены в Q₁ и Q₂ соответственно, поскольку их частоты доступа равны 2 и 4. Очередь, в которую помещается блок, зависит от частоты доступа (f) как журнал₂(е). Когда кеш заполнен, первым удаляемым блоком будет глава Q₀ в этом случае а. Если а будет доступен еще раз, он переместится в Q₁ ниже б.

Pannier: контейнерный алгоритм кеширования для составных объектов

Pannier ^[23] - это основанный на контейнерах механизм кэширования флэш-памяти, который идентифицирует расходящиеся (разнородные) контейнеры, в которых хранящиеся в них блоки имеют сильно различающиеся шаблоны доступа. Pannier использует структуру очереди выживания на основе очереди приоритетов для ранжирования контейнеров на основе их времени выживания, которое пропорционально текущим данным в контейнере. Pannier построен на основе сегментированного LRU (S2LRU), который разделяет горячие и холодные данные. Pannier также использует многоступенчатый контроллер с обратной связью для ограничения записи во флеш-память, чтобы продлить срок ее службы.

Смотрите также

• Алгоритм без кеширования
• Местоположение ссылки
• Распределенный кеш

Рекомендации

внешняя ссылка

• Определения различных алгоритмов кеширования
• Слайды по различным схемам замены страниц, включая LRU
• Алгоритм кеширования для флеш / SSD