0
$\begingroup$

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 answer is "1 5 2 3"

Please tell me what am I doing wrong here!

$\endgroup$
2
$\begingroup$

Least recently used cache do the following things: we add the numbers to the top(front) representing that it is the "most recent" and thus the end of this will be the number which is least recent.

  1. If the cache is not full, 1 a). add to the cache if the entry is not in the cache. 1 b). If the entry is in cache we make that most recent and continue.
  2. If the cache is full, 2 a) If the value is already in the cache we just move it up(front) so that it represent most recent after this. 2 b) If the value is not in the cache we remove the least recent one and add the current value to the top(front)to represent that as the most recent.

Now let me explain you the sample which you have provided.

**Input**                     **cache**(front represent most recent and end represent least recent


1   2   3   4   5   2   5   4   1   5   2   3  --> inputs

1   2   3   4   5   2   5   4   1   5   2   3  --->(this is our cache) **top represent most recent** 
-   1   2   3   4   5   2   5   4   1   5   2
-   -   1   2   3   4   4   2   5   4   1   5
-   -   -   1   2   3   3   3   2   2   4   1  ----> **end represent the least recent** 

So we have our answer as,(from most recent to least recent) = 3,2,5,1 input and cache

hope this helps you.Sorry for my bad editing.

$\endgroup$
  • $\begingroup$ With all respects, but based on this link, my approach seems correct ? csee.wvu.edu/~jdm/classes/cs550/notes/tech/vmem/lru.html $\endgroup$ – f855a864 Oct 8 '14 at 15:51
  • $\begingroup$ or this : cs.uttyler.edu/Faculty/Rainwater/COSC3355/Animations/… $\endgroup$ – f855a864 Oct 8 '14 at 15:53
  • $\begingroup$ With your approach, if the cache is not full, you put the entry to the top, but in all the documents i found online, the entry will be put at the bottom, i don't understand ! $\endgroup$ – f855a864 Oct 8 '14 at 15:54
  • 1
    $\begingroup$ It is not necessary whether you consider start as the most recent or the end as the most recent.You can assume it as you like or want. $\endgroup$ – govindpatel Oct 9 '14 at 14:50
  • $\begingroup$ So my answer is also a correct one? $\endgroup$ – f855a864 Oct 9 '14 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.