Replacement Policies

Basic to the implementation of virtual memory is the concept of demand paging. This means that the operating system, and not the programmer, controls the swapping of pages in and out of main memory as they are required by the active processes. When a non-resident page is needed by a process, the operating system must decide which resident page is to be replaced by the requested page. The part of the virtual memory which makes this decision is called the replacement policy.

There are many approaches to the problem of deciding which page to replace but the object is the same for all--the policy which selects the page that will not be referenced again for the longest time.
Examples:

First In First Out (FIFO):
The page to be replaced is the "oldest" page in the memory, the one which was loaded before all the others

Least Recently Used (LRU):
The page to be replaced is the one which has not been referenced since all the others have been referenced

Last In First Out (LIFO):
The page to be replaced is the one most recently loaded into the memory

Least Frequently Used (LFU):
The page to be replaced is the one used least often of the pages currently in the memory

Optimal (OPT or MIN):
The page to be replaced is the one that will not be used for the longest period of time. This algorithm requires future knowledge of the reference string which is not usually available. Thus, this policy is used for comparison studies

The anomalies associated with replacement policies like FIFO have led to the interest in the policies like LRU which do not suffer from such anomalies. They are known as stack algorithms.

---