Page replacement algorithm

In a <a href="/facts/Computer/SQe1aK05">computer</a> <a href="/facts/Operating_system/8XTuvMh2">operating system</a> that uses <a href="/facts/Memory_paging/KR889x5k">paging</a> for <a href="/facts/Virtual_memory/Lw2GemF5">virtual memory</a> <a href="/facts/Memory_management/vthLkUpz">management</a>, page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write to disk, when a <a href="/facts/Page_(computer_memory)/CNGruG1H">page</a> of memory needs to be allocated. Page replacement happens when a requested page is not in memory (<a href="/facts/Page_fault/0pzn9ByX">page fault</a>) 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 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 <a href="/facts/Online_problem/64TsU7Yz">online problem</a> from the competitive analysis perspective in the sense that the optimal deterministic algorithm is known.

Page replacement algorithm open-in-new

Page replacement algorithm