Least recently used
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 |
---|