Когда алгоритм LRU будет пропущен на 100%?

Question

Я знаю эти два способа заставить алгоритм LRU пропустить 100%.

1. Циклический доступ к набору данных, который немного больше размера кэша.

2. Произвольные всплески доступа к нечасто доступному набору данных, который загрязняет кеш путем замены наиболее часто используемых записей.

Красный цвет означает отсутствие кэша.

Но есть и другой способ: "Доступ к блокам с разными частотами доступа".

Я не знаю, как описать это на примере.

Answer 1

LRU может учитывать частоту доступа к данным, например:

Data   1    1    2    2    3    4
Cache1 1(1) 1(2) 1(2) 1(2) 1(2) 1(2)
Cache2           2(1) 2(2) 2(2) 2(2)
Cache3                     3(1) 4(1)

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

Таким образом, "Доступ к блокам с различными частотами доступа" может выглядеть следующим образом:

Data   1    1    2    2    3    4    3    4
Cache1 1(1) 1(2) 1(2) 1(2) 1(2) 1(2) 1(2) 1(2)
Cache2           2(1) 2(2) 2(2) 2(2) 2(2) 2(2)
Cache3                     3(1) 4(1) 3(1) 4(1)

Поэтому, несмотря на то, что мы используем только 3 и 4, LRU по-прежнему предпочитает использовать 1 и 2 как более часто используемые.

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

Data   1    2    3    4    1    2    3
Cache1 1(1) 1(1) 1(1) 4(1) 4(1) 4(1) 3(1)
Cache2      2(1) 2(1) 2(1) 1(1) 1(1) 1(1)
Cache3           3(1) 3(1) 3(1) 2(1) 2(1)

Надеюсь это ответит на твой вопрос.