Home » Algorithms

Analysis of LRU page replacement algorithm and Belady's anomaly

In this article, we are going to see how no of page faults changes with increase in frame size in LRU replacement policy?
Submitted by Radib Kar, on November 21, 2018

Problem statement:

Write a program to simulate Least Recently Used (LRU) page replacement algorithm for the following page reference string: 9, 10, 11, 7, 12, 8, 7, 6, 12, 5, 4, 3, 10, 11, 12, 4, 5, 6, 9, 4, 5.

Consider (i) 4 frames and (ii) 5 frames. Compare the results...

Solution

LRU Page replacement algorithm

1. Set page_fault=0 & frame_size to the value given as input.
2. Start traversing the pages.
   If
   1. Page_set holds less pages than frame_size. Insert pages one by one until the size of page_set reaches frame_size or all page references are processed. Simultaneously maintain the recent occurred counter (which has come most recently or least recently) of each page in a map called page_counter.
   2. Increment page_fault.
   
   Else
   

   If current page is present in page_set
       Continue;
   Else
   

   1. Find the page in the set that was least recently used. We find it using the map we created. We basically need to replace the page with minimum counter.
   2. Replace the page having the least counter value with current page.
   3. Increment page_fault.
   4. Update counter of current page.
3. Return page_fault.

C++ implementation of LRU page replacement algorithm and Belady's anomaly

#include <bits/stdc++.h>
using namespace std;

int page_faults(int page[],int n, int frame_size){
	//STL set to hold current pages,max size=frame_size
	unordered_set<int> page_set ; 
	//STL map to store counter of each referenced pages 
	unordered_map<int,int> page_counter;
	int page_fault=0;
	//for each memory reference
	for(int i=0;i<n;i++){ 
		//frame_size =max set size 
		cout<<"processing request page no "<<page[i]<<endl;
		//when all frames are not allocated
		if(page_set.size()<frame_size){ 
			//if page is not present in memory
			if(page_set.find(page[i])==page_set.end()){ 
				page_set.insert(page[i]); //insert pages
				page_fault++; //increase page-fault
			}
			//update counter value of the referenced page
			page_counter[page[i]]=i; 
		}
		//when all frames are allocated
		else{ 
			//if referenced page is not present
			if(page_set.find(page[i])==page_set.end()){ 
				int lru=INT_MAX,val;
				for(auto it=page_set.begin();it!=page_set.end();it++){
					//find the least recently used page
					if(page_counter[*it]<lru){  
						lru=page_counter[*it];
						val=*it;
					}
				}
				//erase the least recently used page
				page_set.erase(val); 
				//insert the current page
				page_set.insert(page[i]); 
				//increase page fault
				page_fault++; 
			}
			//update counter value of current page
			page_counter[page[i]]=i; 
		}
		//display existing pages in the frames 
		//after each page request processed
		cout<<"pages in the frames are: ";    
		for(auto it=page_set.begin();it!=page_set.end();it++)
			cout<<*it<<" ";
		cout<<endl;
	}
}

int main(){
	//page reference requests
	int page[]={9, 10, 11, 7, 12, 8, 7, 6, 12, 5, 4, 3, 10, 11, 12, 4, 5, 6, 9, 4, 5}; 
	int n=sizeof(page)/sizeof(int);
	//total no of frames in memory
	int frame_size;   
	//input frame_size
	cout<<"enter no of frames"<<endl; 
	cin>>frame_size;
	//compute memory value
	cout<<"no of page faults for "<<frame_size<<" frames are: "<<page_faults(page,n,frame_size)<<endl; 

	return 0;
}

Output (first run)

enter no of frames 
4
processing page no 9 
pages in the frames are: 9 
processing page no 10
pages in the frames are: 10 9
processing page no 11
pages in the frames are: 11 9 10 
processing page no 7 
pages in the frames are: 7 11 9 10 
processing page no 12
pages in the frames are: 12 7 11 10
processing page no 8 
pages in the frames are: 8 12 7 11 
processing page no 7 
pages in the frames are: 8 12 7 11 
processing page no 6 
pages in the frames are: 6 8 12 7
processing page no 12
pages in the frames are: 6 8 12 7
processing page no 5 
pages in the frames are: 6 5 12 7
processing page no 4 
pages in the frames are: 4 6 5 12
processing page no 3 
pages in the frames are: 3 4 5 12
processing page no 10
pages in the frames are: 10 3 4 5
processing page no 11
pages in the frames are: 10 3 11 4 
processing page no 12
pages in the frames are: 12 10 3 11
processing page no 4 
pages in the frames are: 12 10 4 11
processing page no 5 
pages in the frames are: 5 12 4 11 
processing page no 6 
pages in the frames are: 6 5 12 4
processing page no 9 
pages in the frames are: 9 6 5 4 
processing page no 4 
pages in the frames are: 9 6 5 4 
processing page no 5 
pages in the frames are: 9 6 5 4 
...........no of page faults for 4 frames are: 17........ 

Output (second run)

enter no of frames 
5
processing page no 9 
pages in the frames are: 9 
processing page no 10
pages in the frames are: 10 9
processing page no 11
pages in the frames are: 11 9 10 
processing page no 7 
pages in the frames are: 7 11 9 10 
processing page no 12
pages in the frames are: 12 7 11 9 10
processing page no 8 
pages in the frames are: 8 12 7 11 10
processing page no 7 
pages in the frames are: 8 12 7 11 10
processing page no 6 
pages in the frames are: 6 8 12 7 11 
processing page no 12
pages in the frames are: 6 8 12 7 11 
processing page no 5 
pages in the frames are: 6 8 5 12 7
processing page no 4 
pages in the frames are: 4 6 5 12 7
processing page no 3 
pages in the frames are: 3 4 6 5 12
processing page no 10
pages in the frames are: 10 3 4 5 12 
processing page no 11
pages in the frames are: 10 3 11 4 5 
processing page no 12
pages in the frames are: 12 10 3 11 4
processing page no 4 
pages in the frames are: 12 10 3 11 4
processing page no 5 
pages in the frames are: 5 12 10 11 4
processing page no 6 
pages in the frames are: 6 5 12 11 4 
processing page no 9 
pages in the frames are: 9 6 5 12 4
processing page no 4 
pages in the frames are: 9 6 5 12 4
processing page no 5 
pages in the frames are: 9 6 5 12 4
...........no of page faults for 5 frames are: 16........

Comparison of result

The outputs show that the no of page fault for 4 frames are 17 while the no of page fault for 5 frames are 16. That means no of page faults has decreased with the increase in frame number.

Comment

This phenomenon is an example of Belady's anomaly. Belady's anomaly states that increasing number of frames will never increase number of page faults if LRU page replacement algorithm is used. Using LRU page replacement algo, no. of page fault may decrease or remain same if no of frame is increased. This is so because LRU is a stack algorithm.