Алгоритм кеширования LIRS - LIRS caching algorithm

LIRS (Набор с низкой периодичностью ссылки) это алгоритм замены страницы с улучшенной производительностью по сравнению с LRU (Наименее недавно использованные) и многие другие новые алгоритмы замены.[1] Это достигается за счет использования «дистанции повторного использования».[2] как показатель местоположения для динамического ранжирования страниц, к которым осуществляется доступ, для принятия решения о замене.

Резюме

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

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

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

 . . . Б. . . Б. . . . . . . . . . Б. . . . . ^ ---- Расстояние повторного использования --- ^ - Давность - ^ T1 T2 T3

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

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

Операции по замене ЛИРС
  1. Кэш разделен на разделы с низкой периодичностью между ссылками (LIR) и с высокой периодичностью между ссылками (HIR). Раздел LIR предназначен для хранения страниц с самым высоким рейтингом (страницы LIR), а раздел HIR - для хранения некоторых других страниц (страницы HIR).
  2. Раздел LIR содержит большую часть кеша, и все страницы LIR находятся в кэше.
  3. Все недавно открытые страницы помещаются в очередь FIFO, называемую стеком LIRS (стек S на графике), и все резидентные страницы HIR также помещаются в другую очередь FIFO (стек Q на графике).
  4. Открытая страница перемещается в верхнюю часть стека S, а все HIR-страницы из нижней части стека удаляются. Например, График (b) создается после доступа к странице B на Графике (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 Грид-платформа данных.[5] Приближение LIRS, CLOCK-Pro,[6] принят в NetBSD.[7]

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

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

  1. ^ Сун Цзян и Сяодун Чжан "LIRS: эффективная политика замены набора с недавних пор с малыми ссылками для повышения производительности буферного кеша ", в материалах конференции ACM SIGMETRICS по измерению и моделированию компьютерных систем (SIGMETRICS'02), Марина Дель Рей, Калифорния, июнь 2002 г.
  2. ^ Дж. Гечей, Д. Р. Слуц и И. Л. Трейгер, «Методы оценки иерархий хранения», IBM Systems Journal, № 2, 1970. https://pdfs.semanticscholar.org/4a58/e3066f12bb86d7aef2776e9d8a2a4e4daf3e.pdf
  3. ^ Сун Цзян и Сяодун Чжан "Делаем LRU дружественным к рабочим нагрузкам слабой локализации: новый алгоритм замены для повышения производительности кэша файлового буфера ", в IEEE Transactions on Computers, 54 (8): 939-952, август 2005 г.
  4. ^ svn commit - mysqldoc @ docsrva: r6768 - ствол / ndbapi
  5. ^ Выселение Infinispan, пакетные обновления и LIRS
  6. ^ Сун Цзян, Фэн Чен и Сяодун Чжан "ЧАСЫ-Pro: эффективное улучшение замены ЧАСОВ ", в материалах Ежегодной технической конференции USENIX 2005 г. (USENIX'05), Анахайм, Калифорния, апрель 2005 г.
  7. ^ Перекрестная ссылка ядра FreeBSD / Linux sys / uvm / uvm_pdpolicy_clockpro.c

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

  • К О (1) ВМ Рик ван Риль о возможном использовании LIRS для балансировки кеш-памяти и программной памяти в Linux.
  • А отчет о выполнении замены страницы ЧАСЫ-Про.
  • Расширенные проекты замены страниц создана командой разработчиков управления памятью Linux.
  • ЧАСЫ-Pro пластырь разработан Риком ван Риелем.
  • ЧАСЫ-Pro пластырь разработал Питер Зийлстра.
  • CLOCK-Pro упоминается как пример в разделе Linux и академия в книге Профессиональная архитектура ядра Linux пользователя Wolfgan Mauerer.
  • А бумага подробное описание различий в производительности LIRS и других алгоритмов «Влияние предварительной выборки ядра на алгоритмы замены буферного кэша на производительность» Али Р. Батта, Криса Гниади и Ю. Чарли Ху.