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 First in First Out (FIFO) Page Replacement Algorithm and also write a program for First In First Out Page Replacement algorithm. In FIFO 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 in the front of the queue is selected for removal.
We will use C++ to write this algorithm due to the standard template library support. Hence, we will write the program of FIFO 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 FIFO 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]]++; 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 5 5 5 Frame 1 E 2 2 2 1 1 1 1 1 3 3 3 Frame 2 E E 3 3 3 2 2 2 2 2 4 4 1 1 1 Hit 3 Page Fault 9
Other page replacement algorithms:
Let us know in the comments if you are having any questions regarding this FIFO page replacement Algorithm.
And if you found this post helpful, then please help us by sharing this post with your friends. Thank You