Page Replacement Algorithm

When a process executes and the desired page is not in memory, page fault occurs. After locating desired page in memory, OS finds free frame. BUT OS finds that there are no free frames. The OS at this point have multiple options

1.       Terminate the user process

2.       Swap out the process and freeing all its frames

3.       Page Replacement

When no frame is free, process of finding a page that is not currently being used and free it is known as page replacement. The page replacement causes the following sequences of steps to occur

1.       Find the location of the desired page on the disk

2.       Find a free frame

a.       If frame is free, use it

b.      If there is no free frame, use page replacement algorithm to find a page that is not currently being used to select victim frame

c.       Write victim frame back to disk

d.      Update page and frame table

3.       Issue a disk read operation to a free frame

4.       After completing disk read, update page table to show desired page is in the memory now.

5.       Restart the user process

FIFO Page Replacement Algorithm

The simplest page replacement algorithm is First In First Out (FIFO) algorithm. The algorithm associates with each page the time it was brought into the memory.  It replaces that has been in memory for the longest period of time( brought in memory first).  A queue is used to implement FIFO algorithm. A new page is inserted at the rear end whereas page is replaced from the front end of the queue.

The algorithm is easy to understand and program. But performance is not good.

Optimal Page Replacement Algorithm

Optimal Page Replacement algorithm replaces the page that will not be used for the longest period of time.

This algorithm gives lowest possible page fault rate for a fixed number of frames. This algorithm on the other hand is difficult to implement because it requires future knowledge of reference string.

LRU Page Replacement Algorithm

LRU Page replacement algorithm replaces the page that has not been used for the longest period of time. The algorithm associates with each page the time of the page last use.

LRU can be viewed as Optimal Page replacement algorithm in backward  direction and therefore doesnot require future knowledge of reference string.

The algorithm can be implemented in two ways

Keep stack of page numbers. When page is referred, it is popped