Алгоритм кэширования LIRS
Алгоритм замены страницы

LIRS ( Low Inter-reference Recency Set ) — это алгоритм замены страниц с улучшенной производительностью по сравнению с LRU (Least Recently Used) и многими другими новыми алгоритмами замены. [1] Это достигается за счет использования «расстояния повторного использования» [2] в качестве метрики локальности для динамического ранжирования посещаемых страниц с целью принятия решения о замене.

Краткое содержание

Количественная оценка местности

В то время как все алгоритмы замены страниц полагаются на существование ссылочной локальности для функционирования, основное различие между различными алгоритмами замены заключается в том, как эта локальность количественно определяется. LIRS использует расстояние повторного использования страницы или количество отдельных страниц, к которым был получен доступ между двумя последовательными ссылками на страницу, для количественной оценки локальности. В частности, LIRS использует для этой цели последнюю и предпоследнюю ссылки (если таковые имеются). Если страница доступна впервые, ее расстояние повторного использования бесконечно. Напротив, LRU использует недавность страницы, которая представляет собой количество отдельных страниц, к которым был получен доступ после ссылки на страницу, для количественной оценки локальности. Чтобы учесть актуальную историю доступа, реализация LIRS фактически использует большее из расстояния повторного использования и недавности страницы в качестве метрики для количественной оценки ее локальности, обозначаемой как RD-R. Предполагая, что кэш имеет емкость C страниц, алгоритм LIRS должен ранжировать недавно посещенные страницы в соответствии с их значениями RD-R и сохранять C страниц с самым высоким рейтингом в кэше.

Концепции расстояния повторного использования и новизны можно визуализировать следующим образом, где T1 и T2 — это предпоследнее и последнее время ссылки на страницу B соответственно, а T3 — это текущее время. 

. . . Б . . . Б . . . . . . . . . Б . . . . . ^----Расстояние повторного использования---^--Давность--^ Т1 Т2 Т3

Выбор жертвы на замену

LIRS организует метаданные кэшированных страниц и некоторых некэшированных страниц и выполняет операции по их замене, описанные ниже, которые также проиллюстрированы примером [3] на графике.

Замена операций LIRS
  1. Кэш разделен на разделы Low Inter-reference Recency (LIR) и High Inter-reference Recency (HIR). Раздел LIR предназначен для хранения страниц с самым высоким рейтингом (страницы LIR), а раздел HIR — для хранения некоторых других страниц (страницы HIR).
  2. Раздел LIR содержит большую часть кэша, и все страницы LIR находятся в кэше.
  3. Все недавно открытые страницы помещаются в очередь FIFO, называемую стеком LIRS (стек S на графике), а все резидентные страницы HIR также помещаются в другую очередь FIFO (стек Q на графике).
  4. Страница, к которой был получен доступ, перемещается наверх стека S , а все страницы HIR в нижней части стека удаляются. Например, Graph (b) создается после того, как страница B была получена на Graph (a).
  5. При доступе к странице HIR в стеке S она превращается в страницу LIR, и соответственно страница LIR, которая в данный момент находится внизу стека S, превращается в страницу HIR и перемещается наверх стека Q. Например, график (c) создается после доступа к странице E в графике (a).
  6. Когда происходит пропуск и резидентная страница должна быть заменена, резидентная страница HIR внизу стека Q выбирается в качестве жертвы для замены. Например, графики (d) и (e) создаются после доступа к страницам D и C на графике (a) соответственно.

Развертывание

LIRS был развернут в MySQL , начиная с версии 5.1, [4] и другой ссылки по ссылке. Он также принят в платформе Infinispan data grid. [5] Приближение LIRS, CLOCK-Pro, [6] принято в NetBSD . [7] LIRS принят в Apache Jackrabbit, репозитории контента. Кэш LIRS в памяти разработан в Red Hat JBoss Data Virtualization System. LIRS используется в H2 Database Engine, который называется Scan Resistant Cache. Кроме того, LIRS используется в Apache Impala, обработке данных с помощью Hadoop.

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

Ссылки

  1. ^ Цзян, Сун; Чжан, Сяодун (июнь 2002 г.). «LIRS: эффективная политика замены набора ссылок с низкой новизной для повышения производительности буферного кэша». Обзор оценки производительности ACM SIGMETRICS . 30 (1): 31– 42. doi :10.1145/511399.511340.
  2. ^ Мэттсон, Р. Л.; Гечеи, Дж.; Слютц, Д. Р.; Трейгер, И. Л. (1970). «Методы оценки иерархий хранения». IBM Systems Journal . 9 (2): 78– 117. doi :10.1147/sj.92.0078.
  3. ^ Сун Цзян; Сяодун Чжан (2005). «Создание LRU дружественного к слабым локальным рабочим нагрузкам: новый алгоритм замены для повышения производительности буферного кэша». IEEE Transactions on Computers . 54 (8): 939– 952. doi :10.1109/TC.2005.130. S2CID  11539061.
  4. ^ svn commit - mysqldoc@docsrva: r6768 - trunk/ndbapi
  5. ^ Выселение Infinispan, пакетные обновления и LIRS
  6. ↑ Сун Цзян, Фэн Чэнь и Сяодун Чжан, «CLOCK-Pro: эффективное улучшение замены CLOCK», в трудах Ежегодной технической конференции USENIX 2005 года (USENIX'05), Анахайм, Калифорния, апрель 2005 г.
  7. ^ Перекрестная ссылка на ядро ​​FreeBSD/Linux sys/uvm/uvm_pdpolicy_clockpro.c
  • На пути к виртуальной машине O(1) Рика ван Рила о возможном использовании LIRS для балансировки кэша и памяти программ в Linux.
  • Отчет о внедрении замены страницы CLOCK-Pro.
  • Расширенные проекты замены страниц, созданные командой разработчиков управления памятью Linux.
  • Патч CLOCK-Pro разработан Риком ван Рилем.
  • Патч CLOCK-Pro разработан Питером Зейлстрой.
  • CLOCK-Pro упоминается в качестве примера в разделе Linux и академические науки книги «Профессиональная архитектура ядра Linux» Вольфгана Мауэрера.
  • Статья, в которой подробно описываются различия в производительности LIRS и других алгоритмов, «Влияние предварительной загрузки ядра на производительность алгоритмов замены буферного кэша» Али Р. Батта, Криса Гниади и Й. Чарли Ху.
Получено с "https://en.wikipedia.org/w/index.php?title=LIRS_caching_algorithm&oldid=1238769707"