Page replacement algorithm: Difference between revisions

Revision as of 09:01, 4 May 2021

Revision as of 12:17, 4 May 2021

Line 58:

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.

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> \dfractfrac{k}{k-h+1}</math>-competitive. So every marking algorithm attains the <math> \dfractfrac{k}{k-h+1}</math>-competitive ratio.

LRU is a marking algorithm while FIFO is not a marking algorithm. {{confusing|date=December 2015}}

Line 65:

An algorithm is conservative, if on any consecutive request sequence containing k or fewer distinct page references, the algorithm will incur k or fewer page faults.

If ALG is a conservative algorithm with a cache of size k, and OPT is the optimal algorithm with a cache of <math>h \leq k</math>, then ALG is <math> \dfractfrac{k}{k-h+1}</math>-competitive. So every conservative algorithm attains the <math> \dfractfrac{k}{k-h+1}</math>-competitive ratio.

LRU, FIFO and CLOCK are conservative algorithms.

Line 90:

Although it does not seem possible for a page to be modified yet not referenced, this happens when a class 3 page has its referenced bit cleared by the timer interrupt. The NRU algorithm picks a random page from the lowest category for removal. So out of the above four page categories, the NRU algorithm will replace a not-referenced, not-modified page if such a page exists. Note that this algorithm implies that a modified but not-referenced (within the last timer interval) page is less important than a not-modified page that is intensely referenced.

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

===First-in, first-out===

Line 98:

FIFO page replacement algorithm is used by the [[VAX/VMS]] 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]</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> \dfractfrac{k}{k-h+1}</math>-competitive.

===Second-chance===

Line 114:

* Clock with Adaptive Replacement (CAR) is a page replacement algorithm that has performance comparable to [[Adaptive replacement cache|ARC]], and substantially outperforms both LRU and CLOCK.<ref>{{cite conference |first2=Dharmendra S. |last2=Modha |name-list-style=amp |url=http://usenix.org/publications/library/proceedings/fast04/tech/full_papers/bansal/bansal.pdf |title=CAR: Clock with Adaptive Replacement |first1=Sorav |last1=Bansal |date=31 March – 2 April 2004 |conference=3rd USENIX Conference on File and Storage Technologies (FAST '04) |conference-url=https://www.usenix.org/conference/fast04 |publisher=USENIX Association |archive-url=https://web.archive.org/web/20040731112559/http://www.almaden.ibm.com/cs/people/dmodha/clockfast.pdf |archive-date=31 July 2004| url-status=live |___location=San Francisco, CA, USA |pages=187–200 |language=en |citeseerx=10.1.1.105.6057}}</ref> The algorithm CAR is self-tuning and requires no user-specified magic parameters.

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

===Least recently used===

Line 135:

A comparison of ARC with other algorithms (LRU, MQ, 2Q, LRU-2, LRFU, [[The 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> \dfractfrac{k}{k-h+1}</math>-competitive.

===Random===

Line 203:

* The file cache including; written to the underlying block storage (possibly going through the buffer, see below) when paged out.

* The cache of [[block device]]s, called the "buffer" by Linux (not to be confused with other structures also called buffers like those use for [[anonymous pipe|pipes]] and buffers used internally in Linux); written to the underlying storage when paged out.

The unified page cache operates on units of the smallest page size supported by the CPU (4 &nbsp;KiB in [[ARMv8]], [[x86]] and [[x86-64]]) with some pages of the next larger size (2 MiB in [[x86-64]]) called "huge pages" by Linux. The pages in the page cache are divided in an "active" set and an "inactive" set. Both sets keep a LRU list of pages. In the basic case, when a page is accessed by a user-space program it is put in the head of the inactive set. When it is accessed repeatedly, it is moved to the active list. Linux moves the pages from the active set to the inactive set as needed so that the active set is smaller than the inactive set. When a page is moved to the inactive set it is removed from the page table of any process address space, without being paged out of physical memory.<ref>See explanation at the start of [https://github.com/torvalds/linux/blob/master/mm/workingset.c <code>/mm/workingset.c</code>] in the Linux source</ref><ref>{{cite news|last1=Corbet|first1=Jonathan Corbet|title=Better active/inactive list balancing|url=https://lwn.net/Articles/495543/|date=2012-05-02|work=[[LWN.net]]}}</ref> When a page is removed from the inactive set, it is paged out of physical memory. The size of the "active" and "inactive" list can be queried from <code>/proc/meminfo</code> in the fields "Active", "Inactive", "Active(anon)", "Inactive(anon)", "Active(file)" and "Inactive(anon)".

== Working set ==