Алгоритм адаптивной замены кеша
Я пытаюсь реализовать алгоритм Adaptive Replacement Cache, но я читаю в литературе и не могу понять алгоритм. Кто-нибудь может объяснить мне этот алгоритм? Я вижу, что он использует два списка L1 для частоты и L2 для недавности. Но T1, B1 и T2, B2 для списков L1 и L2, я не могу понять.
ftp://paranoidbits.com/ebooks/Outperforming%20LRU%20with%20an%20Adaptive%20Replacement%20Cache.pdf В этой статье я увидел эту информацию.
2 ответа
T1 и T2 содержат фактические данные, которые кэшируются. T1 содержит все данные (страницы), на которые ссылались ровно один раз. T2 содержит страницы, на которые ссылались 2 или более раз. B1 - это список призраков, который используется для запоминания того, какие страницы когда-то были в кэше T1. B2 такой же, только для кеша T2. Когда вы добавляете T1 и B1 вместе, вы получаете набор (называемый L1) ссылок на страницы, которые были или в настоящее время кэшированы, потому что на них ссылались один раз. То же самое касается L2, только он содержит ссылки на страницы, на которые ссылались как минимум дважды.
T1 и T2 совместно используют набор слотов фиксированного размера (каждый слот может содержать одну страницу), и мы используем B1 и B2, чтобы решить, как разделить эти слоты между T1 и T2. Это то, что делает ARC адаптивным - автоматическая настройка того, кто получает больше слотов. Если B1 содержит несколько ссылок на одну и ту же страницу, это означает, что мы не позволяем T1 удерживать свои страницы достаточно долго, и что должно быть разрешено большее количество слотов для противодействия этому. То же самое касается B2.
Я не буду пытаться объяснить весь алгоритм здесь, но это, по крайней мере, мое понимание списков ARC.
Я хотел бы выделить некоторые из ключевых идей и помочь вам следовать повествованию статьи. Это должно помочь вам развить некоторую интуицию о ARC.
Начнем с LRU-кэша размером c. Помимо кэша страниц, мы также поддерживаем каталог кэша T размера c, который является просто массивом метаданных, описывающих страницы в кэше. Метаданные страницы содержат, например, физический адрес страницы на носителе данных.
Теперь обратите внимание, что LRU не устойчив к сканированию. Если процесс извлекает последовательность из c страниц, каждая страница в кэше будет удалена. Это не очень эффективно, и мы хотим иметь возможность оптимизировать как по актуальности, так и по частоте.
Основная идея № 1: разбить кеш на 2 списка: T1 и T2. T1 содержит недавно использованные страницы, а T2 содержит часто используемые страницы. Это устойчиво к сканированию, поскольку сканирование приведет к опустошению T1, но в основном не повлияет на T2.
Когда кэш заполнен, алгоритм должен выбрать изгнание жертвы из T1 или из T2. Обратите внимание, что эти списки не обязательно должны иметь одинаковый размер, и мы можем разумно предоставить больше кеша последним или частым страницам в зависимости от шаблонов доступа. Вы можете изобрести свою собственную эвристику здесь.
Ключевая идея № 2: сохранить дополнительную историю. Пусть B1 и B2 отслеживают метаданные выселенных страниц из T1 и T2 соответственно. Если мы наблюдаем много пропусков кеша в T1, которые являются попаданиями в B1, мы сожалеем о выселении и отдаем больше кеша T1.
ARC сохраняет число p, чтобы разделить кэш между T1 и T2.
Ключевая идея № 3: при промахе кэша в T1 и попадании в B1 ARC увеличивает p на, Это "дельта", или "коэффициент сожаления", который сравнивает вероятность попадания в В1 с вероятностью попадания в В2, предполагая равномерное распределение по всем страницам.