Page replacement algorithm: Difference between revisions

Revision as of 15:53, 22 January 2023

Revision as of 21:08, 29 January 2023

Line 109:

====Variants of clock====

* GCLOCK: Generalized clock page replacement algorithm.<ref>{{cite journal|last1=Smith|first1=Alan Jay|title=Sequentiality and prefetching in database systems|journal=ACM Transactions on Database Systems|volume=3|issue=3|pages=223–247|date=September 1978|doi=10.1145/320263.320276|publisher=ACM|language=en|___location=New York, NY, USA|s2cid=11611563|doi-access=free}}</ref>

* Clock-Pro keeps a circular list of information about recently referenced pages, including all M pages in memory as well as the most recent M pages that have been paged out. This extra information on paged-out pages, like the similar information maintained by [[adaptive replacement cache|ARC]], helps it work better than LRU on large loops and one-time scans.<ref>{{cite conference |first2=Feng |last2=Chen |url=http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-05-3.pdf |title=CLOCK-Pro: an effective improvement of the CLOCK replacement |first3=Xiaodong |last3=Zhang |first1=Song |last1=Jiang |date=10-15 April 2005 |conference=2005 USENIX Annual Technical Conference |conference-url=https://www.usenix.org/conference/2005usenixannualtechnicalconference |publisher=USENIX Association |archive-url=http://archive.wikiwix.com/cache/20190612095142/http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-05-3.pdf |archive-date=12 June 2019 |___location=Anaheim, CA, USA |page=35 |url-status=live |language=en |access-date=24 March 2009 }}</ref>

* WSclock.<ref>{{cite conference |first2=John L. |last2=Hennessy |url=http://infolab.stanford.edu/~manku/quals/zpapers/81-wsclock.pdf.gz |title=WSCLOCK—a simple and effective algorithm for virtual memory management |format=gzipped PDF |first1=Richard W. |last1=Carr |date=14-16 December 1981 |conference=Eighth ACM symposium on Operating systems principles |conference-url=https://dl.acm.org/citation.cfm?doid=800216 |publisher=ACM |archive-url=https://web.archive.org/web/20070610070838/http://infolab.stanford.edu/~manku/quals/zpapers/81-wsclock.pdf.gz |archive-date=10 June 2007 |___location=Pacific Grove, CA, USA |pages=87–95 |url-status=live |language=en |isbn=0-89791-062-1 |doi=10.1145/800216.806596}}</ref> By combining the Clock algorithm with the concept of a working set (i.e., the set of pages expected to be used by that process during some time interval), the performance of the algorithm can be improved. In practice, the "aging" algorithm and the "WSClock" algorithm are probably the most important page replacement algorithms.<ref>{{cite web|last1=Gottlieb|first1=Allan|title=WSClock|url=http://www.cs.nyu.edu/courses/spring09/V22.0202-002/wsclock-davis.html|website=New York University Computer Science Department|access-date=12 June 2019|archive-url=https://archive.today/20120730042750/http://www.cs.nyu.edu/courses/spring09/V22.0202-002/wsclock-davis.html|archive-date=30 July 2012|url-status=live}}</ref><ref>{{cite web|last1=Tanenbaum|first1=Andrew S.|title=Page Replacement Algorithms|url=http://www.informit.com/articles/article.aspx?p=25260&seqNum=11|website=InformIT|access-date=12 June 2019|archive-url=https://archive.today/20120910015221/http://www.informit.com/articles/article.aspx?p=25260&seqNum=11|archive-date=10 September 2012|url-status=live}}</ref>

Line 221:

* {{cite book |first=Andrew S. |last=Tanenbaum |date=1997 |title=Operating Systems: Design and Implementation |edition=2nd |publisher=Prentice-Hall |___location=Upper Saddle River, NJ, USA |isbn=0-13-638677-6 |lccn=96037153 |ol=998396M |url=https://archive.org/details/operatingsystems00tane }}

* {{cite book |first=Andrew S. |last=Tanenbaum |date=2001 |title=Modern Operating Systems |edition=2nd |publisher=Prentice-Hall |___location=Upper Saddle River, NJ, USA |isbn=978-0-13-031358-4 |lccn=00051666 |ol=24214243M |oclc=45284637 |url=https://archive.org/details/modernoperatings00tane }} Online excerpt on page replacement algorithms: [http://www.informit.com/articles/article.aspx?p=25260 Page Replacement Algorithms].

* {{cite conference |first2=Pei |last2=Cao |url=https://dl.acm.org/citation.cfm?id=258681 |title=Adaptive page replacement based on memory reference behavior |first1=Gideon |last1=Glass |date=15-18 June 1997 |conference=1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems |conference-url=https://dl.acm.org/citation.cfm?id=258612 |publisher=ACM |url-access=subscription |___location=Seattle, WA, USA |pages=115–126 |language=en |doi=10.1145/258612.258681 |isbn=0-89791-909-2|doi-access=free }} Also available in extended form as {{cite journal|url=https://minds.wisconsin.edu/handle/1793/60102|title=Technical Report 1338|website=Department of Computer Sciences, University of Wisconsin-Madison|year=1997|last1=Glass|first1=Gideon|last2=Cao|first2=Pei}}

* {{cite conference |url=https://www.usenix.org/legacy/events/osdi2000/full_papers/kim/kim.pdf |title=A Low-Overhead High-Performance Unified Buffer Management Scheme that Exploits Sequential and Looping References |url-status=live |archive-url=https://web.archive.org/web/20040918122454/http://ssrnet.snu.ac.kr/~choijm/paper/IC-2000-OSDI-UBM.pdf |archive-date=18 September 2004|language=en |last2=Choi |first2=Jongmoo |last3=Kim |first3=Jesung |last1=Kim |first1=Jong Min |last4=Noh |first4=Sam H. |last5=Min |first5=Sang Lyul |last6=Cho |first6=Yookun |last7=Kim |first7=Chong Sang |date=17–21 October 2000 |conference=4th Usenix Symposium on Operating System Design and Implementation (OSDI'2000) |conference-url=http://www.usenix.org/events/osdi2000/ |___location=San Diego, CA, USA |display-authors=1 |publisher=USENIX Association |volume=4 |issue=9}}

* {{cite conference |first3=Paul |last3=Wilson |first2=Scott |last2=Kaplan |url=http://www.amherst.edu/~sfkaplan/courses/spring-2004/cs40/papers/SKW:EELRUSEAPR.pdf |title=EELRU: simple and effective adaptive page replacement |first1=Yannis |last1=Smaragdakis |date=1-4 May 1999 |conference=1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems |conference-url=https://dl.acm.org/citation.cfm?id=301453&picked=prox |publisher=ACM |archive-url=http://archive.wikiwix.com/cache/20160304000000/http://www.amherst.edu/~sfkaplan/courses/spring-2004/cs40/papers/SKW:EELRUSEAPR.pdf |archive-date=4 March 2016 |___location=Atlanta, GA, USA |pages=122–133 |url-status=live |language=en |isbn=1-58113-083-X |doi=10.1145/301453.301486}}