Least recently used

from Wikipedia, the free encyclopedia

Least recently used ( LRU ; German  " Most recently not used " ) is a page displacement strategy for cache memory . It removes the page that was last referenced longest ago.

rating

advantages

  • Comes quite close to the optimal algorithm.
  • It specifically selects pages that have not been used recently.

disadvantage

  • Only mediocre hit rate. Often more important than the question of whether a page has been referenced is the question of how often it has been referenced. Least recently used does not take this fact into account, which usually leads to an only mediocre hit rate. Therefore, methods like Least Frequently Used (LFU) are considered more efficient.
  • Is quite difficult to implement.

implementation

Least recently used is implemented with the help of a queue in which all stored pages are waiting to be swapped out. If a page has to be swapped out, it always hits the one at the top of the queue (i.e. select the page at the end of the list as the page to be replaced). If a page is referenced, it leaves its position and joins the end of the queue.

example

A. B. D.
B. –B → A. –D → B.
C. C. A.
Cache hit Cache miss

See also