Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
0FIFO Page Replacement Algorithm In C++
FIFO Page Replacement Algorithm in C++
FIFO is an acronym for the First in First out approach. The concept is based on the fact that the elements present in the stack are removed following the same order in which they were filled.
Precisely, the element present at the bottom of the stack will be removed first. This also means the element present on the top of the stack will be removed last.
The approach is implemented with the help of an algorithm which is also known as the scheduling algorithm. The algorithm is dedicated to giving every process the Central Operating System (CPU) time in the order in which it is demanded.
Very important
Program in C++ (Method 1)
This method uses sets and queues –
Run
//C++ program for FIFO algorithm
#include <bits/stdc++.h>
using namespace std;
// Method to determine pager faults using FIFO
int getPageFaults(int pages[], int n, int frames)
{
// To denote the current page set, we use an unordered_set.
// It will help to have a quick check
// The availability of the page in the set.
unordered_set <int> set;
// The code will store the pages in FIFO technique
queue <int> indexes;
// Stating from the first page
int countPageFaults = 0;
for (int i=0; i < n; i++)
{
// Checking the capacity to hold more pages
if (set.size() < frames)
{
// if the page is absent, insert it into the set
// the condition represents page fault
if (set.find(pages[i])==set.end())
{
set.insert(pages[i]);
// increment the conter for page fault
countPageFaults++;
// Push the current page into the queue
indexes.push(pages[i]);
}
}
// If the queue is full, we need to remove one page through FIFO
// The topmost page from the queue will be removed
// Now insert the current page to meet the demand
else
{
// Check if the page in demand is not already present in the queue
if (set.find(pages[i]) == set.end())
{
// Remove the first page from the queue
int val = indexes.front();
indexes.pop();
// Pop the index page
set.erase(val);
// Push the current page in the queue
set.insert(pages[i]);
indexes.push(pages[i]);
// Increment page faults
countPageFaults++;
}
}
}
return countPageFaults;
}
// Driver code
int main()
{
int pages[] = {4, 1, 2, 4, 5};
int n = sizeof(pages)/sizeof(pages[0]);
int frames = 4;
cout << "Page Faults: " << getPageFaults(pages, n, frames);
return 0;
}
Output:
Page Faults: 4
Method 2 (Using Vectors)
Example for output –
Incoming page Steam – 7, 0, 1, 2, 0 , 3, 0, 4, 2, 3, 0, 3, 2, 1
Page Size/ Frame Size = 3
Table will look like(Explanation after the table)
[table id=372 /]
Program in C++ (Method 2)
This method uses vectors –
Run
#include<bits/stdc++.h>
using namespace std;
int main(){
int i, j, k, hitCount = 0;
int frames = 3;
int p_count = 14;
vector <int> processes{7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1};
vector <int> hit(p_count);
vector<vector<int>> a(frames);
for(i = 0; i < frames; i++){
a[i] = vector <int>(p_count,-1);
}
map <int, int> mp;
for(i = 0; i < p_count ; i++){
vector<pair<int,int>> c;
for(auto x: mp)
{
c.push_back({x.second, x.first});
}
sort(c.begin(),c.end());
bool hasCompleted = false;
for(j = 0;j < frames; j++){
if(a[j][i] == processes[i])
{
hitCount++;
hit[i] = true;
mp[processes[i]]++;
hasCompleted = true;
break;
}
if(a[j][i] == -1)
{
for(k = i ; k < p_count; k++)
a[j][k] = processes[i];
mp[processes[i]]++;
hasCompleted = true;
break;
}
}
if(j == frames || hasCompleted == false){
for(j = 0;j < frames; j++){
if(a[j][i] == c[c.size() - 1].second){
mp.erase(a[j][i]);
for(k = i; k < p_count ; k++)
a[j][k]= processes[i];
mp[processes[i]]++;
break;
}
}
}
for(auto x:mp){
if(x.first != processes[i]){
mp[x.first]++;
}
}
}
cout << "Process ";
for(i = 0 ; i < p_count; i++){
cout << processes[i] << " ";
}
cout << endl;
for(i = 0; i < frames; i++){
cout << "Frame" << i << " ";
for(j = 0; j < p_count; j++){
if(a[i][j] == -1)
cout << "- ";
else
cout << a[i][j] << " ";
}
cout << endl;
}
cout << "Page Fault ";
for(i = 0; i < p_count; i++){
// page fault occurs if hi[i] == True
// hit occurs when hi[i] = false
if(hit[i])
cout << "N ";
else
cout << "Y ";
}
cout << "\n\n";
cout << "Page Fault " << p_count - hitCount << endl;
cout << "Hit " << hitCount << endl;
return 0;
}
Output
Process 7 0 1 2 0 3 0 4 2 3 0 3 2 1
Frame0 7 7 7 2 2 2 2 4 4 4 0 0 0 0
Frame1 - 0 0 0 0 3 3 3 2 2 2 2 2 1
Frame2 - - 1 1 1 1 0 0 0 3 3 3 3 3
Page Fault Y Y Y Y N Y Y Y Y Y Y N N Y
Page Fault 11
Hit 3
Method 3
Using basic arrays and non-stl methods
Program in C++ (Method 3)
This method uses arrays –
Run
// C++ program for FIFO page replacement algorithm
#include <iostream>
using namespace std;
int main()
{
int incomingStream[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1};
int pageFaults = 0;
int frames = 3;
int m, n, s, pages;
pages = sizeof(incomingStream)/sizeof(incomingStream[0]);
printf("Incoming \t Frame 1 \t Frame 2 \t Frame 3");
int temp[frames];
for(m = 0; m < frames; m++)
{
temp[m] = -1;
}
for(m = 0; m < pages; m++)
{
s = 0;
for(n = 0; n < frames; n++)
{
if(incomingStream[m] == temp[n])
{
s++;
pageFaults--;
}
}
pageFaults++;
if((pageFaults <= frames) && (s == 0))
{
temp[m] = incomingStream[m];
}
else if(s == 0)
{
temp[(pageFaults - 1) % frames] = incomingStream[m];
}
cout << "\n";
cout << incomingStream[m] << "\t\t\t";
for(n = 0; n < frames; n++)
{
if(temp[n] != -1)
cout << temp[n] << "\t\t\t";
else
cout << "- \t\t\t";
}
}
cout << "\n\nTotal Page Faults:\t" << pageFaults;
cout << "\nTotal Hits :\t" << pages - pageFaults;
return 0;
}
Output
Incoming Frame 1 Frame 2 Frame 3 7 7 - - 0 7 0 - 1 7 0 1 2 2 0 1 0 2 0 1 3 2 3 1 0 2 3 0 4 4 3 0 2 4 2 0 3 4 2 3 0 0 2 3 3 0 2 3 2 0 2 3 1 0 1 3 Total Page Faults: 11 Total Hits : 3
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment