LRU_page replacement algorithm.

Question

How LRU page replacement algorithm works? I am unable to visualize it from book hamacher. Please anyone explain in simple language.

Answer 1

As the name suggests, the page which is used LEAST RECENTLY i.e. earliest should be replaced.

So all you need to do is:

1. Check whether the new page that has just came in exist in memory

2. If it already exists no need to do the replacement

3. Otherwise replace it.

Let say the page reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 and we have 4 page slots empty.

Initially all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults [7 0 1 2]
0 is already their so —> 0 Page fault. [7 0 1 2]
when 3 came it will take the place of 7 because it is least recently used —>1 Page fault [3 0 1 2]
0 is already in memory so —> 0 Page fault. [3 0 1 2]
4 will takes place of 1 —> 1 Page Fault [3 0 4 2]
Now for the further page reference string —> 0 Page fault because they are already available in the memory. [3 0 4 2]

Comments

Just to make things more clear:

[3 0 1 2] 

4 will takes place of 1 —> 1 Page Fault [3 0 4 2] 

4 will take the position of  1 and not 0, because 0 was just used in the previous page fault.

Age of the pages in increasing order in [3 0 1 2]:

0 < 3 < 2 < 1 and hence 1 will be selected.

---

Thank you :)

---

But I wanted to know in terms of counter. How counter use this technique to replace blocks In cache?

---

I do not understand what do you mean by Counters. Keeping count of the number of access to a particular frame.