Introduction

LRU Page Replacement Algorithm works on a prediction that the pages that have been used more times in the last few instructions will probably be used again and again.In Least Recently Used (LRU) algorithm is a Greedy algorithm where the page to be replaced is least recently used. The idea is based on locality of reference, the least recently used page is not likely

Example

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

Learn More