Page Replacement Algorithms, Cache

LRU Scheme

The least recently used (LRU) scheme is a replacement scheme in which the block replaced is the one that has been unused for the longest time.

https://www.geeksforgeeks.org/lru-cache-implementation/

This is used in Set Associative Cache. Also in page replacement policy.

Least Recently Used (LRU)

• Uses the assumption of the principle of locality
• Nearly as good as the optimal algorithm
• Replaces the page that has not been referenced for the longest time
• By the principle of locality, this should be the page least likely to be referenced in the near future
• Each page could be tagged with the time of last reference. This would require a great deal of overhead. ⇒ clock algorithms