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!
Asked By : f855a864
Answered By : govindpatel
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.
- 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.
- 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30732
0 comments:
Post a Comment
Let us know your responses and feedback