Understanding LRU Algorithm

c++ c algorithm page-replacement
user249375 picture user249375 · Nov 12, 2012 · Viewed 9.3k times · Source

I am trying to understand LRU and its making no sense to me. If I understand it then it will be easier for me to code. Can someone walk me through the steps? Like,

  1. If the reference string you are currently at is in the array then do you increment to the next space?
  2. When you check to see if somethings in the buffer then do we need to scan where we are at or the whole array?

I just cant seem to follow along. How is it keeping track of least recently used? Shouldnt the least recently used be the one after the index your at?

enter image description here

Answer

Cory Nelson picture Cory Nelson · Nov 12, 2012

An LRU is typically put in a list. When an item is accessed, remove it from the list (if it's there), and push it to the back. The back of the list is the Most Recently Used. Because you're continually moving used items to the back of the list, the least used ones end up naturally at the front of the list. When there's not enough room, you pop from the front.

Related questions

Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97. But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop …

Read More
Fast ceiling of an integer division in C / C++

Given integer values x and y, C and C++ both return as the quotient q = x/y the floor of the floating point equivalent. I'm interested in a method of returning the ceiling instead. For example, ceil(10/5)=2 and ceil(11/5)=3. The …

Read More
Data Compression Algorithms

I was wondering if anyone has a list of data compression algorithms. I know basically nothing about data compression and I was hoping to learn more about different algorithms and see which ones are the newest and have yet to …

Read More