Из Википедии, свободной энциклопедии
  (Перенаправлено из алгоритмов кеширования )
Перейти к навигации Перейти к поиску
Эта статья посвящена общим алгоритмам кеширования. Подробные сведения об алгоритмах, относящихся к подкачке, см. В разделе Алгоритм замены страницы . Подробные алгоритмы, относящиеся к кэш-памяти между ЦП и ОЗУ, см. В разделе Кэш ЦП .
Не путать с политиками размещения кэша .

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

Обзор [ править ]

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

где

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

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

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

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

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

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

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

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

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

Политики [ править ]

Алгоритм Белади [ править ]

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

Оптимальная работа

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

Первый пришел - первый ушел (FIFO) [ править ]

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

Последним пришел - первым ушел (LIFO) или первым пришел - последним (FILO) [ править ]

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

Наименее недавно использовавшиеся (LRU) [ править ]

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

Последовательность доступа для приведенного ниже примера - ABCDED F.

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

На втором последнем шаге осуществляется доступ к D и, следовательно, обновляется порядковый номер.

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

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

Функция Least Recently Used (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 наиболее полезны в ситуациях, когда чем старше элемент, тем выше вероятность доступа к нему.

Последовательность доступа для приведенного ниже примера - ABCDECD B.

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

Псевдо-LRU (PLRU) [ править ]

Дополнительная информация: Псевдо-LRU

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

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

Последовательность доступа - ABCD E.

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

Случайная замена (RR) [ править ]

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

Последовательность доступа для приведенного ниже примера - ABCDEBDF.

Сегментированный 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

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 = {A1, A2} и набор HIR = {A3, A4, A5}. Теперь в момент 10, если есть доступ к A4, происходит промах. Алгоритм LIRS теперь удаляет A5 вместо A2 из-за его наибольшей давности.

ЧАСЫ-Pro [ править ]

Алгоритм LRU не может быть напрямую реализован на критическом пути компьютерных систем, таких как операционные системы , из-за его высоких накладных расходов. Для реализации обычно используется приближение LRU, называемое CLOCK . Точно так же CLOCK-Pro является приближением LIRS для недорогой реализации в системах. [15] CLOCK-Pro находится под базовым CLOCKframework, но имеет три основных достоинства. Во-первых, 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) и CLOCK. 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 содержит m очередей LRU: Q 0 , Q 1 , ..., Q m -1 . Здесь значение m представляет иерархию, основанную на времени жизни всех блоков в этой конкретной очереди. Например, если j > i , блоки в Q j будут иметь более длительный срок службы, чем блоки в Q i . В дополнение к ним есть еще один буфер истории Q out, очередь, которая поддерживает список всех идентификаторов блоков вместе с их частотами доступа. Когда Q out заполнен, самый старый идентификатор удаляется. Блоки остаются в очередях LRU в течение заданного времени жизни, которое динамически определяется алгоритмом MQ как максимальное временное расстояние между двумя доступами к одному и тому же файлу или количество блоков кэша, в зависимости от того, что больше. Если на блок не ссылались в течение его времени жизни, он понижается с Q i до Q i -1 или удаляется из кэша, если он находится в Q 0 . Каждая очередь также имеет максимальное количество обращений; если к блоку в очереди Q i обращаются более 2 i раз, этот блок повышается до Q i +1до тех пор, пока не будет доступна более 2 я + 1 раз или его срок службы истекает. В рамках данной очереди блоки ранжируются по давности доступа в соответствии с LRU . [22]

На рис. Видно, как m очередей LRU помещаются в кэш. Также посмотрите на рис., Как Q out хранит идентификаторы блоков и их соответствующие частоты доступа. a был помещен в Q 0, поскольку недавно к нему обращались только один раз, и мы можем проверить в Q , как b и c были помещены в Q 1 и Q 2 соответственно, поскольку их частоты доступа равны 2 и 4. Очередь, в которую помещается блок зависит от частоты доступа (f) как log 2 (f). Когда кеш заполнен, первым удаляемым блоком будет Q 0, в данном случае a . ЕслиДоступ к a осуществляется еще раз, он переместится в Q 1 ниже b .

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ а б Алан Джей Смит. «Дизайн памяти кэша процессора». Proc. IEEE TENCON, 1987. [1]
  2. ^ Пол В. Болотов. «Принципы работы кэш-памяти». Архивировано 14 марта 2012 года на Wayback Machine . 2007 г.
  3. ^ http://www.vldb.org/conf/1994/P439.PDF
  4. ^ О'Нил, Элизабет Дж .; О'Нил, Патрик Э .; Вейкум, Герхард (1993). Алгоритм замены страниц LRU-K для буферизации диска базы данных . Материалы Международной конференции ACM SIGMOD 1993 года по управлению данными . SIGMOD '93. Нью-Йорк, Нью-Йорк, США: ACM. С. 297–306. CiteSeerX  10.1.1.102.8240 . DOI : 10.1145 / 170035.170081 . ISBN 978-0-89791-592-2. S2CID  207177617 .
  5. ^ Гао, Цзе; Чжао, Лянь; Шэнь, Сюэминь (9 сентября 2019 г.). «Исследование динамического кэширования через поле перехода состояний - случай неизменной во времени популярности». arXiv : 1909.04658 [ cs.OS ].}
  6. ^ Билал, Мухаммед; и другие. (2017). «Политика управления кэшем с учетом времени с учетом наименее недавнего использования (TLRU) в ICN». IEEE 16-я Международная конференция по передовым коммуникационным технологиям (ICACT) : 528–532. arXiv : 1801.00390 . Bibcode : 2018arXiv180100390B . DOI : 10.1109 / ICACT.2014.6779016 . ISBN 978-89-968650-3-2. S2CID  830503 .
  7. ^ Хун-Тай Чоу и Дэвид Дж. ДеВитт. Оценка стратегий управления буфером для систем реляционных баз данных. VLDB, 1985.
  8. ↑ Шауль Дар, Майкл Дж. Франклин, Бьорн Тор Йонссон, Дивеш Шривастава и Майкл Тан. Кэширование и замена семантических данных. VLDB, 1996.
  9. ^ Руководство по процессорам серии ARM Cortex-R
  10. ^ Эффективный алгоритм моделирования для кэша политики случайной замены [2]
  11. ^ Рамакришна Karedla, J. Спенсер Любовь и Брэдли Г. Wherry. Стратегии кэширования для повышения производительности дисковой системы. В компьютере , 1994.
  12. ^ Билал, Мухаммед; и другие. (2017). «Схема управления кешем для эффективного вытеснения и репликации контента в кэш-сетях». Доступ IEEE . 5 : 1692–1701. arXiv : 1702.04078 . Bibcode : 2017arXiv170204078B . DOI : 10,1109 / ACCESS.2017.2669344 . S2CID 14517299 . 
  13. ^ Jayarekha, P .; Наир, Т (2010). «Подход адаптивной динамической замены для многоадресной системы кэш-памяти префикса с учетом популярности». arXiv : 1001.4135 [ cs.MM ].
  14. ^ Цзян, Сун; Чжан, Сяодун (июнь 2002 г.). «LIRS: эффективная замена набора с низкой периодичностью между ссылками для повышения производительности буферного кэша» (PDF) . Труды Международной конференции ACM SIGMETRICS 2002 года по измерению и моделированию компьютерных систем . Ассоциация вычислительной техники. 30 (1): 31–42. DOI : 10.1145 / 511399.511340 . ISSN 0163-5999 .  
  15. ^ Цзян, Сун; Чен, Фэн; Чжан, Сяодун (2005). "ЧАСЫ-Pro: Эффективное улучшение замены ЧАСОВ" (PDF) . Материалы ежегодной конференции по Ежегодной технической конференции USENIX . Ассоциация USENIX: 323–336.
  16. ^ «Управление памятью Linux: Дизайн замены страниц» . 30 декабря 2017 . Проверено 30 июня 2020 .
  17. ^ "Реализация замены страницы CLOCK-Pro" . LWN.net . 16 августа 2005 . Проверено 30 июня 2020 .
  18. ^ Нимрод Мегиддо и Дхармендра С. Модха. ARC: самонастраивающийся кэш для замены с низкими накладными расходами. БЫСТРО, 2003.
  19. ^ http://www.c0t0d0s0.org/archives/5329-Some-insight-into-the-read-cache-of-ZFS-or-The-ARC.html
  20. ↑ Дэнни Беренд, Шломи Долев и Марина Коган-Садецкий. AdaptiveClimb: адаптивная политика замены кеша. СИСТОР, 2019.
  21. ^ Yuanyuan Чжоу , Джеймс Philbin, и Кай Ли. Алгоритм замены нескольких очередей для буферных кешей второго уровня. USENIX, 2002.
  22. ^ Эдуардо Пиньейро, Рикардо Бьянкини, Методы энергосбережения для серверов на основе дисковых массивов, Труды 18-й ежегодной международной конференции по суперкомпьютерам, 26 июня - 01 июля 2004 г., Мало, Франция
  23. ^ Ченг Ли, Филип Shilane, Фред Дуглис и Грант Уоллес. Pannier: флэш-кэш на основе контейнеров для составных объектов. ПО промежуточного слоя ACM / IFIP / USENIX, 2015 г.

Внешние ссылки [ править ]

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