List the steps needed to perform page replacement. Explain the different page replacement policies. Also list out the main requirements, which should be satisfied by a page replacement policy.

The steps needed to perform page replacement are:
1.Determine which page is to be removed from the memory.
2.Perform a page-out operation.
3.Perform a page-in operation.

Different page replacement algorithms are briefly described below:

1. First-in, first-out

The first-in, first-out (FIFO) page replacement algorithm is a low-overhead algorithm. Here the operating system keeps track of all the pages in memory in a queue, with the most recent arrival at the back, and the earliest arrival in front. When a page needs to be replaced, the page at the front of the queue (the oldest page) is selected.
Advantage: 

•  FIFO is cheap and intuitive.

Disadvantage:  

• Performs poorly in practical application.
• Suffers from Belady’s anomaly.

2. Not recently used

The not recently used (NRU) page replacement algorithm works on the following principle: when a page is referenced, a referenced bit is set for that page, marking it as referenced. Similarly, when a page is modified (written to), a modified bit is set. At a certain fixed time interval, the clock interrupt triggers and clears the referenced bit of all the pages, so only pages referenced within the current clock interval are marked with a referenced bit. 

When a page needs to be replaced, the operating system divides the pages into four classes:
• Class 0: not referenced, not modified  
• Class 1: not referenced, modified
• Class 2: referenced, not modified
• Class 3: referenced, modified.
The NRU algorithm picks a random page from the lowest category for removal.

3. Optimal page replacement algorithm

The optimal page replacement algorithm (also known as OPT )is an algorithm that works as follows: when a page needs to be swapped in, the operating system swaps out the page whose next use will occur farthest in the future. For example, a page that is not going to be used for the next 6 seconds will be swapped out over a page that is going to be used within the next 0.4 seconds.
Disadvantage: This algorithm cannot be implemented in the general purpose operating system because it is impossible to compute reliably how long it will be before a page is going to be used.
The main requirements, which should be satisfied by a page replacement policy, are:

1. Non-interference with the program’s locality of reference: The page replacement policy must not remove a page that may be referenced in the immediate future.
2. The page fault rate must not increase with an increase in the memory allocation for a program.