Сравнение алгоритмов замены страниц MFU и LRU

Question

Сравнение алгоритмов замены страниц MFU и LRU

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

3

algorithm page-replacement

Источник

user1467813 28 ноя '12 в 03:21

3 ответа

Другие вопросы по тегам algorithm page-replacement

user56778 28 ноя '12 в 04:48 2012-11-28 04:48 · Answer 1 · 2012-11-28 04:48

Как правило, я видел кэш MFU, используемый в качестве основного, подкрепленный вторичным кешем, который использует алгоритм замены LRU (кэш MRU). Идея состоит в том, что последние использованные объекты останутся в основном кэше, что обеспечивает очень быстрый доступ. Это уменьшает "отток", который вы видите в кэше MRU, когда небольшое количество элементов используется очень часто. Это также предотвращает удаление этих часто используемых элементов из кэша только потому, что они не использовались некоторое время.

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

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

user2273813 12 апр '13 в 09:42 2013-04-12 09:42 · Answer 2 · 2013-04-12 09:42

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

В этом алгоритме необходимо заменить страницу, которая не использовалась в течение самого длительного периода времени.

Преимущества алгоритма замены страницы LRU:

Подходит для полного статистического анализа.
Никогда не страдает от аномалии Белады.

Алгоритм замены наиболее используемой частоты (MFU)

На самом деле алгоритм MFU считает, что страница, которая использовалась наиболее часто, не понадобится немедленно, поэтому она заменит страницу MFU

Пример: рассмотрим следующую справочную строку:7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

Размер буфера:3 Строка:7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

7 7 7 2 2 2 0 4 2 2 0 0 2 2 2 0 0 7 7 7

  0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0

    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

user11258729 12 апр '22 в 15:06 2022-04-12 15:06 · Answer 3 · 2022-04-12 15:06

Я изо всех сил пытался найти вариант использования MFU, везде MFU путают с MRU. Наиболее цитируемый вариант использования MFU:

Наиболее часто используемый (MFU) алгоритм замены страницы основан на аргументе, что страница с наименьшим количеством, вероятно, была только что добавлена и еще не использовалась.

Но вполне можно понять, что речь идет о MRU — недавно использованном кэше.

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