Page Replacement Algorithms
There are some page replacement algorithms. The main goal of a page replacement algorithm is to minimize the page fault rate. When number of frames are fixed that is known as static allocation and when number of frames are not fixed that is known as dynamic allocation. There are some static page replacement algorithms as described below.
FIFO(First Come First Out) replacement:
This algorithm replaces a page that has longest time or oldest page, when a page fault occurs and there is no available free frame. This algorithm can be implemented using queue or time stamp of pages.
Example1:
Consider the following reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Find the number of page faults using FIFO page replacement algorithm with 3 page frames.
1 
1 
1 
4 
4 
4 
5 
5 
5 
hit 

2 
2 
2 
1 
1 
1 
hit 
3 
3 

3 
3 
3 
2 
2 
hit 
1 
4 
Total number of page faults = 9
Example2:
Consider the following reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Find the number of page faults using FIFO page replacement algorithm with 4 page frames.
1 
1 
1 
1 
hit 
5 
5 
5 
5 
4 
4 

2 
2 
2 
hit 
2 
1 
1 
1 
1 
5 

3 
3 
3 
3 
2 
2 
2 
2 

4 
4 
4 
4 
3 
3 
3 
Total number of page faults = 10
Belady’s Anomaly
This is the phenomenon occurs when number of page frames increasing, the number of page faults also increase. Belady’s anomaly occurs in FIFO, Random, and Second chance page replacement algorithms.
Above two examples 1 and example 2 shows this phenomenon in FIFO page replacement algorithm.
Optimal Page Replacement
This algorithm replace the page in the memory that will not be used for the longest period of time. This algorithm gives less number of page faults compared to any other algorithms. However, optimal algorithm is not possible to implement in practice.
Example:
Consider the following reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Find the number of page faults using FIFO page replacement algorithm with 3 page frames.
1 
1 
1 
1 
hit 
1 
hit 
3 
3 

2 
2 
2 
hit 
2 
hit 
2 
4 

3 
4 
5 
5 
5 
hit 
Total number of page faults = 7
LRU Page Replacement
LRU(least recently used) page replacement algorithm replaces page that has not been used for the longest period of time. This algorithm can be implemented using stack or counter.
Example:
Consider the following reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Find the number of page faults using FIFO page replacement algorithm with 3 page frames.
1 
1 
1 
4 
4 
4 
5 
3 
3 
3 

2 
2 
2 
1 
1 
1 
hit 
1 
4 
4 

3 
3 
3 
2 
2 
hit 
2 
2 
5 
Total number of page faults = 10