Clever Geek Handbook

LRU Cache Computing

Assuming I have 4 cache blocks, using the LRU (most recently used) algorithm, replace with this the following block access sequence: 1 2 3 4 5 2 5 4 1 5 2 3:

1   2   3   4   5   2   5   4   1   5   2   3

1   1   1   1   5   5   5   5   5   5   5   5
    2   2   2   2   2   2   2   2   2   2   2
        3   3   3   3   3   3   1   1   1   1
            4   4   4   4   4   4   4   4   3

So, at the end, the cache will contain these memory blocks: "5 2 1 3"

But the correct result is "1 5 2 3"

Please tell me what I am doing wrong here!

Edit:

I'll be honest, I'm doing the exercise and can't get help anywhere but here, and maybe I misunderstood the question, so this is the original question:

enter image description here

+3


source to share


3 answers


So is my LRU simulation wrong? To be honest, I still don't understand!

In column 5, the simulation doesn't work when you add the newest data at the oldest position.

Here's the fix:



            1   2   3   3   3   2   2   4   1  <-- Oldest accesses
        1   2   3   4   4   2   5   4   1   5
    1   2   3   4   5   2   5   4   1   5   2
1   2   3   4   5   2   5   4   1   5   2   3  <-- Newest accesses
  • Note that the newest line is always equal to your input sequence.
  • Other elements object one line at a time, unless they are brought to the front with new access
+4


source


In forward cache, order doesn't matter. And the LRU algorithm is simple enough that you don't need to run the entire simulation. Just look at the last 4 numbers in your sequence:



... 1 5 2 3
+4


source


According to the operating system concepts Abraham Silberschatz 8th edition Chapter 9 Figure 9.15. The order of the cache in the CPU doesn't matter. Lack of cache or page failure rate is important.

However, this question is asking the order of caching in the CPU, not what is in the caches. So, Raymond Hettinger's way will give you the correct answer to this question.

Unfortunately, good processor design won't work this way. Because every cache block needs to be updated with new data with every entry. This defeats the purpose of using cache!

+2


source






More articles:


All Articles