CODEWITHSUNDEEP
paginglru
f855a864
f855a864

Reputation: 277

Calculating cache memory based on LRU algorithm

Assuming i have 4 blocks of cache memory, Using the LRU (Least Recently Used) replacement algorithm on this following sequence of access to memory blocks: 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 in the end, the cache memory will contains this memory blocks : "5 2 1 3"

But the correct result is "1 5 2 3"

Please tell me what am I doing wrong here!

Edit:

I will be honest, I'm doing an excercise and can't get help from anywhere but here, and may be I misread the question, so this is the original question :

enter image description here

Upvotes: 3

Views: 892

Answers (3)

Billz
Billz

Reputation: 8105

According to Abraham Silberschatz Operating System Concepts 8th edition Chapter 9 figure 9.15. The order of cache in the CPU doesn't matter. What is important is the cache miss or page-fault rate.

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

Unfortunately, good CPU design will not work this way. Since, each cache block has to refresh with the new data with each input. This defeat the purpose of using cache!

Upvotes: 2

Raymond Hettinger
Raymond Hettinger

Reputation: 226336

So is my simulation of the LRU wrong? Honestly i still don't get it!

The simulation goes awry in column 5 where you add the newest data to the oldest position.

Here's the correction:

            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
  • Notice that the newest row is always equal to your input sequence.
  • The other elements age one row at a time unless they are brought to the front with a new access

Upvotes: 3

MSalters
MSalters

Reputation: 179877

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

... 1 5 2 3

Upvotes: 4

Related Questions