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 Frequently Used (LRU) Page Replacement Algorithm and also write a program for the Least Frequently Used (LRU) Page Replacement algorithm. In this algorithm, the operating system keeps track of all pages in the memory in a queue. When a page needs to be replaced, the operating system chooses the page which is least frequently used for the replacement with 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 LFU 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 LFU page replacement program in C++.
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,i,j,k;
cout<<"Enter number of frames\n";
cin>>n;
cout<<"Enter number of processes\n";
cin>>m;
vector<int> p(m);
cout<<"Enter processes\n";
for(i=0;i<m;i++){
cin>>p[i];
}
vector<vector<int>> a(n,vector<int>(m,-1));
map <int, int> mp,lfmp;
for(i=0;i<m;i++){
vector<int> op;
vector<pair<int,int>> c,lf;
for(auto q: mp){
c.push_back({q.second,q.first});
}
for(auto q:lfmp){
lf.push_back({q.second,q.first});
}
sort(lf.begin(),lf.end());
bool dontCall=true;
if(lf.size()>2){
if(lf[0].first!=lf[1].first){
dontCall=false;
}
}
sort(c.begin(),c.end());
bool hasrun=false;
for(j=0;j<n;j++){
if(a[j][i]==p[i]){
mp[p[i]]++;
lfmp[p[i]]++;
hasrun=true;
break;
}
if(a[j][i]==-1){
for(k=i;k<m;k++)
a[j][k]=p[i];
mp[p[i]]++;
lfmp[p[i]]++;
hasrun=true;
break;
}
}
if(j==n||hasrun==false){
for(j=0;j<n;j++){
if(dontCall==true){
int q;
if(lf[lf.size()-1].second==c[c.size()-1].second&&lf[lf.size()-1].first>1){
if(a[j][i]==c[c.size()-2].second){
mp.erase(a[j][i]);
lfmp.erase(a[j][i]);
for(k=i;k<m;k++)
a[j][k]=p[i];
mp[p[i]]++;
lfmp[p[i]]++;
break;
}
}
else{
if(a[j][i]==c[c.size()-1].second){
mp.erase(a[j][i]);
lfmp.erase(a[j][i]);
for(k=i;k<m;k++)
a[j][k]=p[i];
mp[p[i]]++;
lfmp[p[i]]++;
break;
}
}
}
else if(dontCall==false){
if(a[j][i]==lf[0].second){
mp.erase(a[j][i]);
lfmp.erase(a[j][i]);
for(k=i;k<m;k++)
a[j][k]=p[i];
mp[p[i]]++;
lfmp[p[i]]++;
break;
}
}
}
}
for(auto q:mp){
if(q.first!=p[i]){
mp[q.first]++;
}
}
}
int hit=0;
vector<int> hitv(m);
for(i=1;i<m;i++){
for(j=0;j<n;j++){
if(p[i]==a[j][i-1]){
hit++;
hitv[i]=1;
break;
}
}
}
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';
}
cout<<"HIT ";
for(i=0;i<hitv.size();i++){
if(hitv[i]==0)
cout<<" ";
else
cout<<hitv[i]<<" ";
}
cout<<"\n";
cout<<"Hit "<<hit<<'\n'<<"Page Fault "<<m-hit<<'\n';
return 0;
}
OUTPUT:
Enter number of frames 3 Enter number of processes 15 Enter processes 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 Process 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 Frame 0 7 7 7 2 2 2 2 4 4 3 3 3 3 3 3 Frame 1 E 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Frame 2 E E 1 1 1 3 3 3 2 2 2 2 2 1 2 HIT 1 1 1 1 1 Hit 5 Page Fault 10
Other page replacement algorithms:
Let us know in the comments if you are having any questions regarding this LFU page replacement Algorithm.
And if you found this post helpful, then please help us by sharing this post with your friends. Thank You
Excelente! Good Joob! Thanks!