# 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.

What's New

Top Interview Coding Problems/Challenges!

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates