FIFO Page Replacement Algorithm In C++

May 7, 2022

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.
FIFO in OS

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

Please read page replacement algorithm theory here first

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 ->70120304230321
Existing at position 177722244400
Existing at position 20003332221
Existing at position 3111000333
Page Faultxxxxxxxxxxx

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

Other pages

  1. Page Replacement Algorithms
    1. LRU – C | C++ | Java | Python
    2. FIFO – C | C++ | Java | Python
    3. Optimal Page Replacement algorithm – C | C++ | Java | Python