Page replacement algorithm: Difference between revisions

Revision as of 22:51, 13 October 2023

Latest revision as of 11:20, 6 August 2025

(12 intermediate revisions by 9 users not shown)

Line 3:

{{Use dmy dates|date=February 2021}}

In a [[computer]] [[operating system]] that uses [[memory paging|paging]] for [[virtual memory]] [[memory management|management]], '''page replacement algorithms''' decide which memory pages to page out, sometimes called swap out, or write to disk, when a [[page (computer memory)|page]] of memory needs to be allocated. [[Paging|Page replacement]] happens when a requested page is not in memory ([[page fault]]) and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages is lower than some threshold.

When the paigpage that was selected for replacement and paged out is referenced again it has to be paged in (read in from disk), and this involves waiting for I/O completion. This determines the ''quality'' of the page replacement algorithm: the less time waiting for page-ins, the better the algorithm. A page replacement algorithm looks at the limited information about accesses to the pages provided by hardware, and tries to guess which pages should be replaced to minimize the total number of page misses, while balancing this with the costs (primary storage and processor time) of the algorithm itself.

The page replacing problem is a typical [[online problem]] from the competitive analysis perspective in the sense that the optimal [[deterministic algorithm]] is known.

== History ==

Line 31:

Modern general purpose computers and some embedded processors have support for [[virtual memory]]. Each process has its own virtual address space. A [[page table]] maps a subset of the process virtual addresses to physical addresses. In addition, in most architectures the page table holds an "access" bit and a "dirty" bit for each page in the page table. The CPU sets the access bit when the process reads or writes memory in that page. The CPU sets the dirty bit when the process writes memory in that page. The operating system can modify the access and dirty bits. The operating system can detect accesses to memory and files through the following means:

* By clearing the access bit in pages present in the process' page table. After some time, the OS scans the page table looking for pages that had the access bit set by the CPU. This is fast because the access bit is set automatically by the CPU and inaccurate because the OS does not immediately receive notice of the access nor does it have information about the order in which the process accessed these pages.

* By removing pages from the process' page table without necessarily removing them from physical memory. The next access to that page is detected immediately because it causes a [[page fault]]. This is slow because a page fault involves a [[context switch]] to the OS, software lookup for the corresponding physical address, modification of the page table and a context switch back to the process and accurate because the access is detected immediately after it occurs.

* Directly when the process makes system calls that potentially access the [[page cache]] like <code>read</code> and <code>write</code> in POSIX.

== Precleaning ==

Line 66:

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>{{Citationcite conference |title=Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement |first1=Akanksha |last1=Jain |first2=Calvin |last2=Lin needed|date=June2016 2008|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]].

Line 87:

In simple words, on a page fault, the frame that has been in memory the longest is replaced.

FIFO page replacement algorithm is used by the [[OpenVMS]] operating system, with some modifications.<ref name="Silber">{{Cite book|language=en|title=Operating system concepts|last1=Silberschatz|first1=Abraham|date=14 December 2004|publisher=John Wiley & Sons|last2=Galvin|first2=Peter Baer|last3=Gagne|first3=Greg|isbn=0-47169-466-5|edition=7th|page=339|___location=Hoboken, NJ, USA|oclc=56913661}}</ref> Partial second chance is provided by skipping a limited number of entries with valid translation table references,<ref>[http://mx.isti.cnr.it/cgi-bin/conan?key=Sys_Parameters~TBSKIPWSL&title=VMS%20Help VMS Help — Sys Parameters, TBSKIPWSL]{{Dead link|date=July 2025 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> and additionally, pages are displaced from process working set to a systemwide pool from which they can be recovered if not already re-used.

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

Line 148:

def simulate_aging(Rs: Sequence, k: int) -> None:

# """Simulate aging"""

print(" t | R-bits (0-{length}) | Counters for pages 0-{length}".format(length=len(Rs)))

Vs = [0] * len(Rs[0])

for t, R in enumerate(Rs):

Vs[:] = [R[i] << (k - 1) | V >> 1 for i, V in enumerate(Vs)]

for i, V in enumerate(Vs)]

print("{:02d} | {} | [{}]".format(t, R,

", ".join(["{:0{}b}".format(V, k)