Page Replacement Algorithms in Operating System

In a multiprogramming environment, the following scenario often results:

•  While execution of a process, a page fault occurs and there are no free frames on the free frame list. This is called over allocation of memory and results due to increase in the degree of multi-programming.
• Page replacement is a technique to solve this problem.  

Concept:

If no free frame is available, a frame is found which is not in use. The contents of the frame are written on to a backing store and the page tables are modified to indicate that the page is no longer in memory. Thus, the frame can be used to hold the page for which the page fault was generated.

One bit is associated with each frame. If the bit is 1, this implies that the contents of the page were modified. This is called the dirty bit. If the dirty bit is 0, the content of the frame need not be written to the backing store.

Page Replacement Algorithms:

FIFO (First in First Out):

• ·       Each page in the memory is associated with a time when it was brought into memory. The oldest page is chosen. A queue is maintained for the pages. When a page is brought into memory, it is inserted at the tail of the queue. A page is replaced at the head of queue.
• ·       The FIFO algorithm is simple to implement. The performance though is not very good. The algorithm suffers from Belady’s anomaly means that the page fault rate may increase as the number of frames allocated increases.

Optimal Page Replacement:

• The page which will not be used for a longer period of time is replaced.
• This algorithm gives a lowest page fault rate. It is very difficult  to implement because it requires future knowledge about the usage of the page.

LRU (Least Recently Used):

• The page which has not been used for a longest period of time is replaced.
• LRU algorithm needs considerable hardware assistance for implementation of this strategy.

Example:

 Given Reference string is 0, 1, 4, 2, 0, 2, 6, 5, 1, 2, 3, 2, 1, 2, 6, 2, 1, 3, 6, 2

 How many page faults will occur, if the program has three page frames?

    

 FIFO (First in First Out): Number of  Frames= 3

       Total number of page faults=13

Optimal Page Replacement: Number of  Frames= 3

  Total number of page faults=9

LRU (Least Recently Used): 

  Total number of page faults=14