Page Replacement Algorithm
In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out (swap out, write to disk) when a page of memory needs to be allocated. Paging happens when a page fault occurs 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 online problem from the competitive analysis perspective in the sense that optimal deterministic algorithm is known.
Read more about Page Replacement Algorithm: History, Local Vs. Global Replacement, Precleaning, Anticipatory Paging, The (h,k)-Paging Problem, Marking Algorithms, Conservative Algorithms, Working Set
Famous quotes containing the words page and/or replacement:
“I asked myself, “Is it going to prevent me from getting out of here? Is there a risk of death attached to it? Is it permanently disabling? Is it permanently disfiguring? Lastly, is it excruciating?” If it doesn’t fit one of those five categories, then it isn’t important.”
—Rhonda Cornum, United States Army Major. As quoted in Newsweek magazine, “Perspectives” page (July 13, 1992)
“Not even the visionary or mystical experience ever lasts very long. It is for art to capture that experience, to offer it to, in the case of literature, its readers; to be, for a secular, materialist culture, some sort of replacement for what the love of god offers in the world of faith.”
—Salman Rushdie (b. 1947)