Page replacement algorithm
algorithm in an OS that decides which memory pages to page out (swap out, write to disk) when a requested page is not in memory (page fault) and a free page cannot be used to satisfy the allocation (because there are too few or none)
Certain operating systems use paging to get virtual memory. This means that a part of the hard disk or a file is used so that the applications or the operating system see more memory that is actually there. A Page replacement algorithm is an algorithm that decides which pages should be written to disk or file, when a new page needs to be allocated.
Some of the algorithms used are:
- Not recently used: The algorithm wants to keep pages that have recently been used in memory. It has two bits it sets. One of the bits is set if the page has been used, the other if the page has been modified (written to). The modified bits are cleared periodically.
- First-in, First-out (FIFO): All the pages are kept in a queue, if a new page is allocated it is put at the back of the queue; the page at the front is the oldest one, and can be written to disk. The algorithm is easy and cheap to implement, but it does not have a good performance. Belady's anomaly may also be a problem.
- Second-chance: Small improvement over First-in,First-out: If the page at the front of the queue has the modified bit set, the page is moved to the back of the queue, and the bit is cleared.
- Clock: A modification of FIFO, the buffer is circular, and there is a pointer. The pointer points to the oldest page. When a new page is needed, and the one at the pointer was not modified, the new page can be inserted there.
- Least-recently-used
- Random: Take a page at random to swap out
