Page replacement algorithm

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 ]]bit]]s 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