In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write to disk when a page of memory needs to be allocated. Page replacement happens when a requested page is not in memory (page fault) and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages is lower than some threshold.
In this post, we will discuss the Least Recently Used (LRU) Page Replacement Algorithm and also write a program for the Least Recently Used (LRU) Page Replacement algorithm. In this algorithm, the operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue. When a page needs to be replaced, the page which is least recently used is replaced by the incoming page.
We will use C++ to write this algorithm due to the standard template library support. Hence, we will write the program of LRU Page Replacement Algorithm in C++, although, it’s very similar to C.
INPUT:
The first line is the number of frames(n).
The second line is the number of processes (m).
The third line is an array of processes (p[m]).
OUTPUT:
Print the matrix for processes and frames.
Also, print the hit and page fault.
The following is the LRU page replacement program in C++.
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,i,j,k,hit=0;
cout<<"Enter number of frames\n";
cin>>n;
cout<<"Enter number of processes\n";
cin>>m;
vector<int> p(m);
vector<int> hi(m);
cout<<"Enter processes\n";
for(i=0;i<m;i++){
cin>>p[i];
}
vector<vector<int>> a(n);
for(i=0;i<n;i++){
a[i]=vector<int>(m,-1);
}
map <int, int> mp;
for(i=0;i<m;i++){
vector<pair<int,int>> c;
for(auto q: mp){
c.push_back({q.second,q.first});
}
sort(c.begin(),c.end());
bool hasrun=false;
for(j=0;j<n;j++){
if(a[j][i]==p[i]){
hit++;
hi[i]=1;
mp[p[i]]=1;
hasrun=true;
break;
}
if(a[j][i]==-1){
for(k=i;k<m;k++)
a[j][k]=p[i];
mp[p[i]]++;
hasrun=true;
break;
}
}
if(j==n||hasrun==false){
for(j=0;j<n;j++){
if(a[j][i]==c[c.size()-1].second){
mp.erase(a[j][i]);
for(k=i;k<m;k++)
a[j][k]=p[i];
mp[p[i]]++;
break;
}
}
}
for(auto q:mp){
if(q.first!=p[i]){
mp[q.first]++;
}
}
}
cout<<"Process ";
for(i=0;i<m;i++){
cout<<p[i]<<" ";
}
cout<<'\n';
for(i=0;i<n;i++){
cout<<"Frame "<<i<<" ";
for(j=0;j<m;j++){
if(a[i][j]==-1)
cout<<"E ";
else
cout<<a[i][j]<<" ";
}
cout<<'\n';
}
for(i=0;i<m;i++){
if(hi[i]==0)
cout<<" ";
else
cout<<hi[i]<<" ";
}
cout<<"\n";
cout<<"Hit "<<hit<<'\n'<<"Page Fault "<<m-hit<<'\n';
return 0;
}
OUTPUT:
Enter number of frames
3
Enter number of processes
12
Enter processes
1 2 3 4 1 2 5 1 2 3 4 5
Process 1 2 3 4 1 2 5 1 2 3 4 5
Frame 0 1 1 1 4 4 4 5 5 5 3 3 3
Frame 1 E 2 2 2 1 1 1 1 1 1 4 4
Frame 2 E E 3 3 3 2 2 2 2 2 2 5
1 1
Hit 2
Page Fault 10
Other page replacement algorithms:
Let us know in the comments if you are having any questions regarding this LRU page replacement Algorithm.
And if you found this post helpful, then please help us by sharing this post with your friends. Thank You
