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 Optimal Page Replacement Algorithm and also write a program for the Optimal Page Replacement algorithm. In this algorithm, when a page needs to be swapped in, the operating system swaps out the page whose next use will occur farthest in the future. For example, a page that is not going to be used for the next 6 seconds will be swapped out over a page that is going to be used within the next 0.4 seconds.
We will use C++ to write this algorithm due to the standard template library support. Hence, we will write the program of Optimal 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 Optimal 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;
for(i=0;i<m;i++){
vector<int> op;
vector<pair<int,int>> c;
for(auto q: mp){
c.push_back({q.second,q.first});
}
for(int q=i+1;q<m;q++){
for(j=0;j<n;j++){
if(a[j][i]==p[q]){
op.push_back(p[q]);
}
}
}
sort(op.begin(),op.end());
op.erase(unique(op.begin(),op.end()),op.end());
bool dontCall=true;
if(op.size()==n){
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]]++;
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(dontCall==true){
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;
}
}
else if(dontCall==false){
if(a[j][i]==op[op.size()-1]){
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]++;
}
}
}
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 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 1 1 1 1 1 1 3 3 3 Frame 1 E 2 2 2 2 2 2 2 2 2 4 4 Frame 2 E E 3 4 4 4 5 5 5 5 5 5 HIT 1 1 1 1 1 Hit 5 Page Fault 7
Other page replacement algorithms:
Let us know in the comments if you are having any questions regarding this Optimal page replacement Algorithm.
And if you found this post helpful, then please help us by sharing this post with your friends. Thank You
