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

Please tell me what am I doing wrong here!

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

hope this helps you.Sorry for my bad editing.

• With all respects, but based on this link, my approach seems correct ? csee.wvu.edu/~jdm/classes/cs550/notes/tech/vmem/lru.html Commented Oct 8, 2014 at 15:51
• Commented Oct 8, 2014 at 15:53
• 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 ! Commented Oct 8, 2014 at 15:54
• 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. Commented Oct 9, 2014 at 14:50
• So my answer is also a correct one? Commented Oct 9, 2014 at 15:04