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.

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