When will the LRU algorithm be miss 100%?

Question

I know these two ways to make LRU algorithm miss 100%.

1. Cyclic accesses to a data-set that is marginally larger than the cache size.

2. Arbitrary bursts of accesses to an infrequently accessed data-set that pollutes the cache by replaceing the more frequently used entries.

Red color means cache miss.

But it has another way that "Accesses to blocks with varying access frequencies".

I don't know how to describe it with an example.

Answer 1

LRU might take into account the frequency we access the data, for example:

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)

Here is in round brackets a counter which get increased each time there is a cache hit to a corresponding block. So, since we accessed block 1 and 2 two times at the beginning, block 3 get evicted from the cache, despite it was used more recently than block 1 and 2.

So "Accesses to blocks with varying access frequencies" basically might look like this:

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)

So despite we use just 3 and 4, LRU still prefers to keep 1 and 2 as more frequently used.

Another example might be just like your previous examples: we should access blocks just once, so the counter never get increased, i.e.:

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)

Hope that answers your question.