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.

First-In, First-Out

• The simplest page-replacement algorithm is a FIFO algorithm.
• The first-in, first-out (FIFO) page replacement algorithm is a low-overhead algorithm that requires little bookkeeping on the part of the operating system.
• The idea is obvious from the name – the operating system keeps track of all the pages in memory in a queue, with the most recent arrival at the back, and the oldest arrival in front.
• When a page needs to be replaced, the page at the front of the queue (the oldest page) is selected.
• While FIFO is cheap and intuitive, it performs poorly in practical application. Thus, it is rarely used in its unmodified form.
• FIFO page replacement algorithm is used by the VAX/VMS operating system, with some modifications. Partial second chance is provided by skipping a limited number of entries with valid translation table references, and additionally, pages are displaced from process working set to a system wide pool from which they can be recovered if not already re-used.
• FIFO is a conservative algorithm, so it is competitive.

$$\frac{k}{K - h + 1}$$

Least Recently Used

• The least recently used (LRU) page replacement algorithm, though similar in name to NRU, differs in the fact that LRU keeps track of page usage over a short period of time, while NRU just looks at the usage in the last clock interval.
• LRU works on the idea that pages that have been most heavily used in the past few instructions are most likely to be used heavily in the next few instructions too. While LRU can provide near-optimal performance in theory (almost as good as Adaptive Replacement Cache), it is rather expensive to implement in practice.
• There are a few implementation methods for this algorithm that try to reduce the cost yet keep as much of the performance as possible.
• The most expensive method is the linked list method, which uses a linked list containing all the pages in memory. At the back of this list is the least recently used page, and at the front is the most recently used page.
• The cost of this implementation lies in the fact that items in the list will have to be moved about every memory reference, which is a very time-consuming process.
• Another method that requires hardware support is as follows: suppose the hardware has a 64-bit counter that is incremented at every instruction.
• Whenever a page is accessed, it acquires the value equal to the counter at the time of page access.
• Whenever a page needs to be replaced, the operating system selects the page with the lowest counter and swaps it out.
• With present hardware, this is not feasible because the OS needs to examine the counter for every page in the cache memory.
• Because of implementation costs, one may consider algorithms (like those that - One important advantage of the LRU algorithm is that it is amenable to full statistical analysis.
• It has been proven, for example, that LRU can never result in more than N-times more page faults than OPT algorithm, where N is proportional to the number of pages in the managed pool.
• On the other hand, LRU's weakness is that its performance tends to degenerate under many quite common reference patterns.
• For example, if there are N pages in the LRU pool, an application executing a loop over array of N + 1 pages will cause a page fault on each and every access. As loops over large arrays are common, much effort has been put into modifying LRU to work better in such situations.
• Many of the proposed LRU modifications try to detect looping reference patterns and to switch into suitable replacement algorithm, like Most Recently Used (MRU)