Editing Cache replacement policies (section)

==== {{Anchor|LRU}}Least Recently Used (LRU) ====
Discards least recently used items first. This algorithm requires keeping track of what was used and when, which is cumbersome. It requires "age bits" for [[CPU cache#Cache entries|cache lines]], and tracks the least recently used cache line based on these age bits. When a cache line is used, the age of the other cache lines changes. LRU is [[Page replacement algorithm#Variants on LRU|a family of caching algorithms]], that includes 2Q by Theodore Johnson and Dennis Shasha<ref>{{Cite journal |last1=Johnson |first1=Theodore |last2=Shasha |first2=Dennis |date=1994-09-12 |title=2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm |journal=Proceedings of the 20th International Conference on Very Large Data Bases |series=VLDB '94 |location=San Francisco, CA |publisher=Morgan Kaufmann Publishers Inc. |pages=439–450 |isbn=978-1-55860-153-6 |s2cid=6259428 |url=http://www.vldb.org/conf/1994/P439.PDF}}</ref> and LRU/K by Pat O'Neil, Betty O'Neil and Gerhard Weikum.<ref>{{Cite book|publisher = ACM|date = 1993|location = New York, NY, USA|isbn = 978-0-89791-592-2|pages = 297–306|doi = 10.1145/170035.170081|first1 = Elizabeth J.|last1 = O'Neil|author-link=Elizabeth O'Neil|first2 = Patrick E.|last2 = O'Neil|first3 = Gerhard|last3 = Weikum| title=Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93 | chapter=The LRU-K page replacement algorithm for database disk buffering |citeseerx = 10.1.1.102.8240|s2cid = 207177617}}</ref> The access sequence for the example is A B C D E D F:

[[File:Lruexample.png|center|alt=Graphic example of an LRU algorithm]]

When A B C D is installed in the blocks with sequence numbers (increment 1 for each new access) and E is accessed, it is a [[CPU cache#Cache miss|miss]] and must be installed in a block. With the LRU algorithm, E will replace A because A has the lowest rank (A(0)). In the next-to-last step, D is accessed and the sequence number is updated. F is then accessed, replacing B{{snd}}which had the lowest rank, (B(1)).