Политики замены кэша

Эта статья посвящена общим алгоритмам кэширования. Подробные алгоритмы, специфичные для подкачки, см. в разделе «Алгоритм замены страниц» . Подробные алгоритмы, относящиеся к кэшу между ЦП и ОЗУ, см. в разделе Кэш ЦП .

Не путать с политикой размещения кэша .

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

Обзор

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

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

где

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

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

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

$E$ = вторичные эффекты, такие как эффекты массового обслуживания в многопроцессорных системах

Кэш имеет два основных показателя качества: задержка и коэффициент попаданий. На производительность кэша также влияет ряд второстепенных факторов.

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

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

Политика

Аномалия Белади в алгоритмах замены страниц

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

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

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

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

Простые политики на основе очередей

«Первым пришел — первым обслужен» (FIFO)

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

«Последним пришел — первым ушел» (LIFO) или «Первым пришел — последним ушел» (FILO)

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

СИТО

SIEVE — это простой алгоритм вытеснения, разработанный специально для веб-кешей, таких как кеши «ключ-значение» и сети доставки контента. Он использует идею ленивого продвижения по службе и быстрого понижения в должности. Таким образом, SIEVE не обновляет глобальную структуру данных при попадании в кэш и откладывает обновление до времени вытеснения; в то же время он быстро удаляет вновь вставленные объекты, поскольку рабочие нагрузки кэша имеют тенденцию показывать высокий коэффициент «одного попадания», и большинство новых объектов не имеют смысла хранить в кэше. SIEVE использует единую очередь FIFO и использует движущуюся руку для выбора объектов для выселения. Объекты в кэше имеют один бит метаданных, указывающий, был ли объект запрошен после того, как его допустили в кэш. Стрелка выселения указывает на хвост очереди в начале и со временем перемещается к ее началу. По сравнению с алгоритмом выселения CLOCK, сохраненные объекты в SIEVE остаются в старом положении. Поэтому новые объекты всегда находятся в начале, а старые — в хвосте. Когда рука движется к голове, новые объекты быстро вытесняются (быстрое понижение в должности), что является ключом к высокой эффективности алгоритма вытеснения SIEVE. SIEVE проще, чем LRU, но обеспечивает удивительно меньший коэффициент ошибок, чем LRU, наравне с современными алгоритмами вытеснения. Более того, при стационарных неравномерных нагрузках SIEVE лучше, чем существующие известные алгоритмы, включая LFU.

Простые политики на основе давности

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

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

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

С учетом времени, использовался реже всего

С учетом времени, реже всего использовавшийся (TLRU) — это вариант LRU, предназначенный для случаев, когда содержимое кэша имеет допустимый срок жизни. Алгоритм подходит для приложений сетевого кэширования, таких как информационно-ориентированные сети (ICN), сети доставки контента (CDN) и распределенные сети в целом. TLRU вводит термин: TTU (время использования), временную метку контента (или страницы), которая определяет время использования контента в зависимости от его местоположения и издателя контента. TTU предоставляет локальному администратору больше контроля над регулированием сетевого хранилища.

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

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

В отличие от LRU, MRU сначала отбрасывает самые недавно использованные элементы. На 11-й конференции VLDB Чоу и ДеВитт заявили: «Когда файл многократно сканируется в [циклически последовательном] эталонном шаблоне, MRU является лучшим алгоритмом замены ». Исследователи, выступавшие на 22-й конференции VLDB, отметили, что для шаблонов произвольного доступа и повторного сканирования больших наборов данных (также известных как шаблоны циклического доступа) алгоритмы кэширования MRU имеют больше совпадений, чем LRU, из-за их склонности сохранять более старые данные. Алгоритмы MRU наиболее полезны в ситуациях, когда чем старше элемент, тем выше вероятность доступа к нему. Последовательность доступа для примера: ABCDECDB:

ABCD помещаются в кэш, поскольку там есть свободное место. При пятом доступе (E) блок, в котором содержался D, заменяется на E, поскольку этот блок использовался последним. При следующем доступе (к D) C заменяется, поскольку доступ к этому блоку был непосредственно перед D.

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

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

LRU-приближения

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

Псевдо-LRU (PLRU)

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

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

Биты работают как двоичное дерево однобитовых указателей, которые указывают на поддерево, которое использовалось реже. Следование по цепочке указателей до конечного узла идентифицирует кандидата на замену. При доступе все указатели в цепочке от листового узла пути доступа до корневого узла устанавливаются так, чтобы указывать на поддерево, которое не содержит путь доступа. Последовательность доступа в примере — ABCDE:

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

Часы-Про

Алгоритм LRU не может быть реализован на критическом пути компьютерных систем, таких как операционные системы , из-за его высоких накладных расходов; Вместо этого обычно используется Clock , приближенная версия LRU. Clock-Pro — это аппроксимация LIRS для недорогой реализации в системах. Clock-Pro имеет базовую структуру Clock с тремя преимуществами. Он имеет три «стрелки часов» (в отличие от одной «стрелки» Clock) и может приблизительно измерять расстояние повторного использования доступа к данным. с однократным доступом или низкой локальностью Как и LIRS, он может быстро удалять элементы данных . Clock-Pro столь же сложен, как и Clock, и его легко внедрить при небольших затратах. Реализация замены буферного кэша в версии Linux 2017 сочетает в себе LRU и Clock-Pro.

Простые политики на основе частоты

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

Дополнительная информация: Наименее часто используемый.

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

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

Наименее часто используемый в последнее время (LFRU) Алгоритм сочетает в себе преимущества LFU и LRU. LFRU подходит для приложений сетевого кэша, таких как ICN , CDN и распределенных сетей в целом. В LFRU кеш разделен на два раздела: привилегированный и непривилегированный. Привилегированный раздел защищен, и, если контент популярен, он помещается в привилегированный раздел. При замене привилегированного раздела LFRU удаляет содержимое из непривилегированного раздела; перемещает содержимое из привилегированного раздела в непривилегированный раздел и вставляет новое содержимое в привилегированный раздел. LRU используется для привилегированного раздела и приближенный алгоритм LFU (ALFU) для непривилегированного раздела.

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

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

S3-ФИФО

Это новый алгоритм вытеснения, разработанный в 2023 году. По сравнению с существующими алгоритмами, которые в основном основаны на LRU (наименее недавно использовавшемся), S3-FIFO использует только три очереди FIFO: небольшую очередь, занимающую 10% пространства кэша, основную очередь. который использует 90% пространства кэша, и призрачную очередь, в которой хранятся только метаданные объекта. Небольшая очередь используется для фильтрации «чудес с одним попаданием» (объектов, доступ к которым осуществляется только один раз за короткий промежуток времени); основная очередь используется для хранения популярных объектов и использует повторную вставку для сохранения их в кеше; а призрачная очередь используется для перехвата потенциально популярных объектов, которые исключаются из небольшой очереди. Объекты сначала вставляются в малую очередь (если они не найдены в призрачной очереди, в противном случае вставляются в основную очередь); при исключении из малой очереди, если объект был запрошен, он снова вставляется в основную очередь, в противном случае он вытесняется, а метаданные отслеживаются в призрачной очереди.

S3-FIFO демонстрирует, что очередей FIFO достаточно для разработки эффективных и масштабируемых алгоритмов вытеснения. По сравнению с алгоритмами LRU и LRU, S3-FIFO может обеспечить в 6 раз более высокую пропускную способность. Кроме того, при рабочих нагрузках веб-кэша S3-FIFO достигает самого низкого коэффициента ошибок среди 11 современных алгоритмов, с которыми сравнивали авторы.

Политика в стиле RRIP

Политики в стиле RRIP являются основой для других политик замены кэша, включая Hawkeye.

Прогнозирование интервала повторного отсчета (RRIP)

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

При промахе в кэше строка с RRPV, равным максимально возможному RRPV, вытесняется; с 3-битными значениями, строка с RRPV, равным 2 ³ - 1 = 7 выселено. Если ни одна строка не имеет этого значения, все RRPV в наборе увеличиваются на 1, пока одна из них не достигнет этого значения. Нужен тай-брейк, и обычно это первая линия слева. Увеличение необходимо для того, чтобы гарантировать, что старые линии устарели должным образом и будут выселены, если они не будут использоваться повторно.

Статический РРИП (СРРИП)

SRRIP вставляет строки со значением RRPV maxRRPV; только что вставленная строка с наибольшей вероятностью будет удалена из-за промаха в кэше.

Бимодальный РРИП (БРРИП)

SRRIP обычно работает хорошо, но ухудшается, когда рабочий набор намного превышает размер кэша, и вызывает перегрузку кэша . Это исправляется путем вставки строк со значением RRPV maxRRPV большую часть времени, а также вставкой строк со значением RRPV maxRRPV - 1 случайным образом с низкой вероятностью. Это приводит к тому, что некоторые строки «застревают» в кеше и помогают предотвратить перегрузку. Однако BRRIP снижает производительность при доступе без перегрузки. SRRIP работает лучше всего, когда рабочий набор меньше кэша, а BRRIP работает лучше всего, когда рабочий набор больше кэша.

Динамический RRIP (DRRIP)

ДРРИП использует набор дуэлей чтобы выбрать, использовать ли SRRIP или BRRIP. Он выделяет несколько наборов (обычно 32) для использования SRRIP и еще несколько для использования BRRIP, а также использует счетчик политик, который отслеживает производительность набора, чтобы определить, какая политика будет использоваться остальной частью кэша.

Политики, аппроксимирующие алгоритм Белади

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

Соколиный глаз

Соколиный глаз пытается эмулировать алгоритм Белади, используя прошлые обращения к ПК, чтобы предсказать, будут ли производимые им обращения генерировать доступы, дружественные к кэшу (используются позже), или доступы, не относящиеся к кэшу (не используются позже). Он выбирает несколько наборов невыровненных кэшей, использует историю длины $8\times {\text{the cache size}}$ и эмулирует алгоритм Белади при этих доступах. Это позволяет политике определять, какие строки следует кэшировать, а какие нет, предсказывая, является ли инструкция благоприятной для кэширования или нежелательной. Эти данные затем передаются в RRIP; доступы из инструкций, дружественных к кэшу, имеют более низкое значение RRPV (вероятно, будут исключены позже), а доступы из инструкций, не относящихся к кэшу, имеют более высокое значение RRPV (вероятно, будут исключены раньше). Серверная часть RRIP принимает решения о выселении. Выборочный кеш и генератор OPT устанавливают начальное значение RRPV для вставленных строк кэша. Hawkeye выиграл чемпионат по кэшированию CRC2 в 2017 году. и Гармония является расширением Hawkeye, которое повышает производительность предварительной выборки.

Блок-схема политики замены кэша Mockingjay

Сойка-пересмешница

Сойка-пересмешница пытается улучшить Соколиного Глаза несколькими способами. Он отбрасывает двоичное предсказание, позволяя принимать более детальные решения о том, какие строки кэша следует вытеснить, и оставляет решение о том, какую строку кэша вытеснить, когда будет доступно больше информации.

Сойка-пересмешница хранит выборочный кеш уникальных обращений, компьютеров, которые их произвели, и их временных меток. При повторном доступе к строке в выборочном кэше разница во времени будет отправлена ​​в предиктор расстояния повторного использования. RDP использует обучение временной разнице, где новое значение RDP будет увеличено или уменьшено на небольшое число, чтобы компенсировать выбросы; число рассчитывается как $w=\min \left(1,{\frac {\text{timestamp difference}}{16}}\right)$. Если значение не было инициализировано, наблюдаемое расстояние повторного использования вставляется напрямую. Если выборочный кеш заполнен и строку необходимо отбросить, RDP получает указание, что компьютер, который последним обращался к нему, осуществляет потоковый доступ.

При доступе или вставке расчетное время повторного использования (ETR) для этой линии обновляется, чтобы отразить прогнозируемое расстояние повторного использования. При промахе в кэше строка с наибольшим значением ETR удаляется. Сойка-пересмешница имеет результаты, близкие к оптимальному алгоритму Белади.

Политика машинного обучения

Ряд политик пытались использовать перцептроны , цепи Маркова или другие типы машинного обучения, чтобы предсказать, какую строку исключить. Для замены кэша также существуют алгоритмы расширенного обучения .

Другие политики

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

Дополнительная информация: алгоритм кэширования LIRS.

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

На диаграмме X указывает, что доступ к блоку осуществляется в определенное время. Если доступ к блоку A1 осуществляется в момент времени 1, его актуальность будет равна 0; это блок, к которому осуществляется первый доступ, и IRR будет равен 1, поскольку он прогнозирует, что к A1 будет снова осуществлен доступ во время 3. Во время 2, поскольку осуществляется доступ к A4, давность станет 0 для A4 и 1 для A1; A4 — это объект, к которому последний раз обращались, и IRR станет равным 4. В момент 10 алгоритм LIRS будет иметь два набора: набор LIR = {A1, A2} и набор HIR = {A3, A4, A5}. В момент времени 10, если есть доступ к А4, происходит промах; LIRS исключит A5 вместо A2 из-за его большей давности.

Адаптивный кэш замены

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

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

Часы с адаптивной заменой (CAR) сочетают в себе преимущества ARC и Clock . CAR работает сравнимо с ARC и превосходит LRU и Clock. Как и ARC, CAR является самонастраивающимся и не требует никаких параметров, указываемых пользователем.

Многохвостый

Алгоритм многоочередной замены (MQ) был разработан для повышения производительности буферного кэша второго уровня, такого как буферный кэш сервера, и был представлен в статье Чжоу, Филбина и Ли. Кэш MQ содержит m очередей LRU: Q ₀ , Q ₁ , ..., Q _{m -1} . Значение m представляет собой иерархию, основанную на времени жизни всех блоков в этой очереди.

Паннье

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

Статический анализ

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

Статический анализ LRU не распространяется на политики псевдо-LRU. Согласно теории сложности вычислений , проблемы статического анализа, возникающие при использовании псевдо-LRU и FIFO, относятся к более высоким классам сложности, чем проблемы для LRU.

См. также

• Алгоритм, не обращающий внимания на кэш
• Распределенный кеш

Внешние ссылки

• Определения различных алгоритмов кэширования
• Алгоритм кэширования для флэш/SSD