Editing Page replacement algorithm (section)

== Implementation details ==

===Techniques for hardware with no reference bit===
Many of the techniques discussed above assume the presence of a reference bit associated with each page.  Some hardware has no such bit, so its efficient use requires techniques that operate well without one.

One notable example is [[VAX]] hardware running [[OpenVMS]]. This system knows if a page has been modified, but not necessarily if a page has been read. Its approach is known as Secondary Page Caching. Pages removed from working sets (process-private memory, generally) are placed on special-purpose lists while remaining in physical memory for some time. Removing a page from a working set is not technically a page-replacement operation, but effectively identifies that page as a candidate. A page whose backing store is still valid (whose contents are not dirty, or otherwise do not need to be preserved) is placed on the tail of the Free Page List. A page that requires writing to backing store will be placed on the Modified Page List. These actions are typically triggered when the size of the Free Page List falls below an adjustable threshold.

Pages may be selected for working set removal in an essentially random fashion, with the expectation that if a poor choice is made, a future reference may retrieve that page from the Free or Modified list before it is removed from physical memory. A page referenced this way will be removed from the Free or Modified list and placed back into a process working set. The Modified Page List additionally provides an opportunity to write pages out to backing store in groups of more than one page, increasing efficiency. These pages can then be placed on the Free Page List. The sequence of pages that works its way to the head of the Free Page List resembles the results of a LRU or NRU mechanism and the overall effect has similarities to the Second-Chance algorithm described earlier.

Another example is used by the [[Linux kernel]] on [[ARM architecture family|ARM]]. The lack of hardware functionality is made up for by providing two page tables – the processor-native page tables, with neither referenced bits nor [[dirty bit]]s, and software-maintained page tables with the required bits present. The emulated bits in the software-maintained table are set by page faults. In order to get the page faults, clearing emulated bits in the second table revokes some of the access rights to the corresponding page, which is implemented by altering the native table.

=== Page cache in Linux ===
[[Linux kernel|Linux]] uses a unified page cache for
* [[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>]].
* The [[tmpfs]] in-memory filesystem; written to swap when paged out.
* 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(file)".