This algorithm replaces the page which has not been referred for a long time. This algorithm is just opposite to the optimal page replacement algorithm. In this, we look at the past instead of staring at future.

1. It is open for full analysis.


2. In this, we replace the page which is least recently used, thus free from Belady’s Anomaly.


3. Easy to choose page which has faulted and hasn’t been used for a long time.

1. It requires additional Data Structure to be implemented.


2. Hardware assistance requirement is high.

1. Start traversing the pages.
   
   i) If set holds less pages than capacity.
   
   
   a) Insert page into the set one by one until the size of set reaches capacity or all page requests are processed.
   
   b) Simultaneously maintain the recent occurred index of each page in a map called indexes.
   
   c) Increment page fault
   
   
   ii) Else If current page is present in set, do nothing.
   
   iii) Else
   
   
   a) Find the page in the set that was least recently used. We find it using index array. We basically need to replace the page with minimum index.
   
   b) Replace the found page with current page.
   
   c) Increment page faults.
   
   d) Update index of current page.
   
   


2. If not present, find if a page that is never referenced in future. If such a page exists, replace this page with new page.


3. If no such page exists, find a page that is referenced farthest in future. Replace this page with new page.