











FIFO 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)
Incoming Page Stream -> | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Existing at position 1 | 7 | 7 | 7 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | |||
Existing at position 2 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | ||||
Existing at position 3 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | |||||
Page Fault | x | x | x | x | x | x | x | x | x | x | x |
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