Editing Page replacement algorithm (section)

===The theoretically optimal page replacement algorithm===
The theoretically optimal page replacement algorithm (also known as OPT, [[Clairvoyance|clairvoyant]] replacement algorithm, or [[László Bélády|Bélády's]] optimal page replacement policy)<ref>{{cite web|url=http://www.read.cs.ucla.edu/111/2006fall/notes/lec11|title=CS111 Lecture 11 notes|archive-url=https://web.archive.org/web/20090109175934/http://www.read.cs.ucla.edu/111/2006fall/notes/lec11|archive-date=9 January 2009|last1=Torrez|first1=Paul|last2=Hallner|first2=Tim|last3=Mathrani|first3=Kiran|last4=Bhaskar|first4=Anu|display-authors=1|url-status=dead|website=UCLA Computer Science Department}}</ref><ref>{{cite conference |title=Characterization of Web reference behavior revisited: Evidence for Dichotomized Cache management |first1=Hyokyung |last1=Bahn |last2=Noh |first2=Sam H. |date=12-14 February 2003 |conference=International Conference on Information Networking 2003 |conference-url=https://link.springer.com/book/10.1007/b13389 |publisher=Springer-Verlag |location=Jeju, South Korea |pages=1018–1027 |isbn=978-3-540-40827-7 |doi=10.1007/978-3-540-45235-5_100 |language=en}}</ref><ref name='lecture notes jones'>{{cite web|last1=Jones|first1=Douglas W.|website=University of Iowa Department of Computer Science|url=http://www.cs.uiowa.edu/~jones/opsys/fall95/notes/0908.html|title=22C:116 Lecture Notes|archive-url=https://archive.today/20120630230917/http://homepage.cs.uiowa.edu/~jones/opsys/fall95/notes/0908.html|archive-date=30 June 2012|url-status=live|access-date=18 March 2008}}</ref> is an algorithm that works as follows: when a page needs to be swapped in, the [[operating system]] swaps out the page whose next use will occur farthest in the future. For example, a page that is not going to be used for the next 6 seconds will be swapped out over a page that is going to be used within the next 0.4 seconds.

This algorithm cannot be implemented in a general purpose operating system because it is impossible to compute reliably how long it will be before a page is going to be used, except when all software that will run on a system is either known beforehand and is amenable to static analysis of its memory reference patterns, or only a class of applications allowing run-time analysis. Despite this limitation, algorithms exist<ref>{{cite conference |title=Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement |first1=Akanksha |last1=Jain |first2=Calvin |last2=Lin |date=2016 |conference=International Symposium on Computer Architecture (ISCA) |publisher=IEEE |location=Seoul, South Korea |doi=10.1109/ISCA.2016.17 |language=en |url=https://www.cs.utexas.edu/~lin/papers/isca16.pdf}}</ref> that can offer near-optimal performance —<!--  on the first run of a program, (conflicts with following sentense) --> the operating system keeps track of all pages referenced by the program, and it uses those data to decide which pages to swap in and out on subsequent runs. This algorithm can offer near-optimal performance, but not on the first run of a program, and only if the program's memory reference pattern is relatively consistent each time it runs.

Analysis of the paging problem has also been done in the field of [[online algorithm]]s. Efficiency of randomized online algorithms for the paging problem is measured using [[amortized analysis]].