c++calgorithmpage-replacement

Understanding LRU Algorithm


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


Solution

  • Store two items for each "item". The value (of course) and the "time" which is an ever-increasing integer.

    So, using your data, assuming that 1 through 4 were accessed in order:

    (1, 1), (2, 2), (3, 3), (4, 4)
    

    access "1" (sorted by time for clarity, time = 5)

    (2, 2), (3, 3), (4, 4), (1, 5)
    

    access "2" (sorted by time for clarity, time = 6)

    (3, 3), (4, 4), (1, 5), (2, 6)
    

    access "5" which will not be found, causing a cache miss. To find the "space" to store the "5", we need to flush the Least Recently Used (LRU). This means dropping "3". Note that time = 7.

    (4, 4), (1, 5), (2, 6), (5, 7)
    

    access "1" (sorted by time for clarity, time = 8)

    (4, 4), (2, 6), (5, 7), (1, 8)
    

    access "2" (sorted by time for clarity, time = 9)

    (4, 4), (5, 7), (1, 8), (2, 9)
    

    access "3" which will not be found, causing a cache miss. To find the "space" to store the "3", we need to flush the Least Recently Used (LRU). This means dropping "4". Note that time = 10.

    (5, 7), (1, 8), (2, 9), (3, 10)
    

    access "4" which will not be found, causing a cache miss. To find the "space" to store the "4", we need to flush the Least Recently Used (LRU). This means dropping "5". Note that time = 11.

    (1, 8), (2, 9), (3, 10), (4, 11)
    

    access "5" which will not be found, causing a cache miss. To find the "space" to store the "5", we need to flush the Least Recently Used (LRU). This means dropping "1". Note that time = 12.

    (2, 9), (3, 10), (4, 11), (5, 12)
    

    Now that you know how the item to be flushed was selected, and have a working example, the flushing of the item without moving it around in the array is up to you to implement.

    --- Edited With additional explanation ---

    Ok, the idea of showing stuff in list form seems to have raised a few questions, so I'll show it in array form

    Access 1, cache miss, empty slot available, store in first available slot

    Value   Age
    1       1
    ---     ---
    ---     ---
    ---     ---
    

    Access 2, cache miss, empty slot available, store in first available slot

    Value   Age
    1       1
    2       2
    ---     ---
    ---     ---
    

    Access 3, cache miss, empty slot available, store in first available slot

    Value   Age
    1       1
    2       2
    3       3
    ---     ---
    

    Access 4, cache miss, empty slot available, store in first available slot

    Value   Age
    1       1
    2       2
    3       3
    4       4
    

    Access 1, cache hit, update access time

    Value   Age
    1       5
    2       2
    3       3
    4       4
    

    Access 2, cache hit, update access time

    Value   Age
    1       5
    2       6
    3       3
    4       4
    

    Access 5, cache miss, no available empties, discard and replace "least recently used"

    Value   Age
    1       5
    2       6
    5       7
    4       4
    

    Access 1, cache hit, update access time

    Value   Age
    1       8
    2       6
    5       7
    4       4
    

    Access 2, cache hit, update access time

    Value   Age
    1       8
    2       9
    5       7
    4       4
    

    Access 3, cache miss, no available empties, discard and replace "least recently used"

    Value   Age
    1       8
    2       9
    5       7
    3       10
    

    Access 4, cache miss, no available empties, discard and replace "least recently used"

    Value   Age
    1       8
    2       9
    4       11
    3       10
    

    Access 5, cache miss, no available empties, discard and replace "least recently used"

    Value   Age
    5       12
    2       9
    4       11
    3       10