Calculating page faults with Least Recently Used

Question

I am new to memory management and page replacement algorithms. I found and printed a question about the Least Recently Used algorithm, but unfortunately, I cannot determine if my answer and thought process are correct.

I am trying very hard to solidify my understanding of the algorithm by reading free textbooks and watching examples on YouTube. However, I would greatly appreciate it you could explain if I am grasping the concept, and provide any suggestions of how to improve my answer and correct my thought process. Please see the image below where the bolded numbers are page faults and the numbers with stars are page hits (I calculated 21 page faults):

P.S. I am sorry if it is difficult to read sideways, but it is the only way I could fit the whole table in the image without having small numbers.

Answer 1

In the case of a page fault LRU (least recently used) looks for that page in the page table which was accessed last and replace it with the new page. In your diagram, I can see a mistake in 6th-page fault when you replace 2 by 1. This is how I think in this algorithm:

• Looks for page in the page table (If page hit then move next)

• If there is a page fault than find out which page was accessed last in the page table.(It has nothing to do with the last replaced page in the table.)

• Replace that page with the new page for which we got the page fault.

Taking your case as an example :

1. You received page fault for 1.
2. first element in the page table is 5 which was accessed last (give it number 0).
3. second element is 2, accessed 2 step ago.
4. third element is 3, accessed 5 step ago.
5. fourth element is 4 , accessed 1 step ago.

So you need replace the 3 with the new page which was accessed last.