Content deleted Content added
m →Techniques for hardware with no reference bit: formatting fix |
|||
| (26 intermediate revisions by 16 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.
When the page 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 38:
To deal with this situation, various ''precleaning'' policies are implemented. Precleaning is the mechanism that starts I/O on dirty pages that are (likely) to be replaced soon. The idea is that by the time the precleaned page is actually selected for the replacement, the I/O will complete and the page will be clean. Precleaning assumes that it is possible to identify pages that will be replaced ''next''. Precleaning that is too eager can waste I/O bandwidth by writing pages that manage to get re-dirtied before being selected for replacement.
{{confusing|date=January 2018}}▼
==The (h,k)-paging problem==
Line 57 ⟶ 45:
==Marking algorithms==
Marking algorithms is a general class of paging algorithms. For each page, we associate it with a bit called its mark. Initially, we set all pages as unmarked. During a stage of page requests, we mark a page when it is first requested in this stage. A marking algorithm is such an algorithm that never pages out a marked page.▼
▲Marking algorithms is a general class of paging algorithms. For each page, we associate it with a bit called its mark. Initially, we set all pages as unmarked. During a stage (a period of operation or a sequence of requests) of page requests, we mark a page when it is first requested in this stage. A marking algorithm is such an algorithm that never pages out a marked page.
If ALG is a marking algorithm with a cache of size k, and OPT is the optimal algorithm with a cache of size h, where <math>h \leq k</math>, then ALG is <math> \tfrac{k}{k-h+1}</math>-competitive. So every marking algorithm attains the <math> \tfrac{k}{k-h+1}</math>-competitive ratio.
LRU is a marking algorithm while FIFO is not a marking algorithm.
==Conservative algorithms==
Line 76 ⟶ 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>{{
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 97 ⟶ 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 150 ⟶ 140:
===Aging===
The aging algorithm is a descendant of the NFU algorithm, with modifications to make it aware of the time span of use. Instead of just incrementing the counters of pages referenced, putting equal emphasis on page references regardless of the time, the reference counter on a page is first shifted right (divided by 2), before adding the referenced bit to the left of that binary number. For instance, if a page has referenced bits 1,0,0,1,1,0 in the past 6 clock ticks, its referenced counter will look like this in chronological order: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100. Page references closer to the present time have more impact than page references long ago. This ensures that pages referenced more recently, though less frequently referenced, will have higher priority over pages more frequently referenced in the past. Thus, when a page needs to be swapped out, the page with the lowest counter will be chosen.
The following [[Python (programming language)|Python]] code simulates the aging algorithm.
Line 158 ⟶ 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)]
print("{:02d} | {} | [{}]".format(t, R,
", ".join(["{:0{}b}".format(V, k)
Line 198 ⟶ 187:
=== Page cache in Linux ===
[[Linux
* [[sbrk|<code>brk</code>]] and anonymous [[mmap|<code>mmap</code>]]ed-regions. This includes the [[heap (programming)|heap]] and [[stack-based memory allocation|stack]] of [[user space and kernel space|user-space]] programs. It is written to swap when paged out.
* Non-anonymous (file-backed) <code>mmap</code>ed regions. If present in memory and not privately modified the physical page is shared with file cache or buffer.
* Shared memory acquired through [[shared memory#Support on Unix-like systems|<code>shm_open</code>]].
Line 219 ⟶ 208:
{{Div col|colwidth=30em}}
* {{cite journal|last=Wong|first=Kin-Yeung|title=Web cache replacement policies: a pragmatic approach|journal=IEEE Network|volume=20|issue=1|pages=28–34|date=23 January 2006|doi=10.1109/MNET.2006.1580916|issn=0890-8044|publisher=IEEE|s2cid=17969287|language=en|id=INSPEC Accession Number 8964134}}
* {{cite journal|last2=Denning|first2=Peter J.|last3=Ullman|first3=Jeffrey D.|last1=Aho|first1=Alfred V.|title=Principles of Optimal Page Replacement|journal=Journal of the ACM|volume=18|issue=1|pages=80–93|date=January 1971|doi=10.1145/321623.321632|publisher=ACM|language=en|___location=New York, NY, USA|s2cid=3154537|doi-access=free}}
* {{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].
| |||