Editing Page replacement algorithm (section)

====Variants on LRU====
# LRU-K<ref>{{cite conference |first2=Patrick E. |last2=O'Neil |url=https://www.cs.cmu.edu/~christos/courses/721-resources/p297-o_neil.pdf |title=The LRU-K page replacement algorithm for database disk buffering |first1=Elizabeth J. |last1=O'Neil |date=25-28 May 1993 |conference=1993 ACM SIGMOD international conference on Management of data |conference-url=https://dl.acm.org/citation.cfm?id=170035 |publisher=ACM |location=Washington, D.C., USA |pages=297–306 |url-status=live |language=en |isbn=0-89791-592-5 |doi=10.1145/170035.170081 |display-authors=1 |last3=Weikum |first3=Gerhard |archive-url=http://archive.wikiwix.com/cache/20190906015742/https://www.cs.cmu.edu/~christos/courses/721-resources/p297-o_neil.pdf |archive-date=6 September 2019 |citeseerx=10.1.1.18.1434}}</ref> evicts the page whose K-th most recent access is furthest in the past. For example, LRU-1 is simply LRU whereas LRU-2 evicts pages according to the time of their penultimate access. LRU-K improves greatly on LRU with regards to locality in time.
# The [[Adaptive replacement cache|ARC]]<ref>{{cite conference |first2=Dharmendra S. |last2=Modha |name-list-style=amp |url=http://www.usenix.org/events/fast03/tech/full_papers/megiddo/megiddo.pdf |title=ARC: A Self-Tuning, Low Overhead Replacement Cache |first1=Nimrod |last1=Megiddo |date=31 March – 2 April 2003 |conference=2nd USENIX Conference on File and Storage Technologies (FAST '03) |conference-url=https://www.usenix.org/conference/fast03 |publisher=USENIX Association |archive-url=https://web.archive.org/web/20100208162647/http://www.almaden.ibm.com/cs/people/dmodha/arcfast.pdf |archive-date=8 February 2010 |url-status=live |location=San Francisco, CA, USA |pages=115–130 |language=en}}</ref> algorithm extends LRU by maintaining a history of recently evicted pages and uses this to change preference to recent or frequent access. It is particularly resistant to sequential scans.
# The 2Q<ref>{{cite conference |first2=Dennis |last2=Shasha |url=http://www.vldb.org/conf/1994/P439.PDF |title=2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm |first1=Theodore |last1=Johnson |date=12-15 September 1994 |conference=20th International Conference on Very Large Data Bases |conference-url=https://dblp.org/db/conf/vldb/vldb94 |publisher=Morgan Kaufmann |archive-url=http://archive.wikiwix.com/cache/20200317170617/http://www.vldb.org/conf/1994/P439.PDF |archive-date=17 March 2020 |location=Santiago de Chile, Chile |pages=439–450 |isbn=1-55860-153-8 |url-status=live |language=en |access-date=31 July 2005 }}</ref> algorithm improves upon the LRU and LRU/2 algorithm. By having two queues, one for hot-path items and the other for slow-path items, items are first placed in the slow-path queue and after a second access of the items placed in the hot-path items. Because references to added items are longer hold than in the LRU and LRU/2 algorithm, it has a better hot-path queue which improves the hit rate of the cache.

A comparison of ARC with other algorithms (LRU, MQ, 2Q, LRU-2, LRFU, [[LIRS caching algorithm|LIRS]]) can be found in Megiddo & Modha 2004.<ref>{{cite journal|last1=Megiddo|first1=Nimrod|last2=Modha|first2=Dharmendra S.|name-list-style=amp|url=http://dbs.uni-leipzig.de/file/ARC.pdf|title=Outperforming LRU with an Adaptive Replacement Cache Algorithm|doi=10.1109/MC.2004.1297303|year=2004|journal=Computer|volume=37|issue=4|pages=58|citeseerx=10.1.1.231.498|archive-url=http://archive.wikiwix.com/cache/20121021000000/http://dbs.uni-leipzig.de/file/ARC.pdf|archive-date=21 October 2012|publisher=IEEE Computer Society|s2cid=5507282|url-status=live|access-date=20 September 2013}}</ref>

LRU is a marking algorithm, so it is <math> \tfrac{k}{k-h+1}</math>-competitive.