FIFO Page Replacement Algorithm In C Plus Plus

May 7, 2021

FIFO in OS

FIFO Page Replacement Algorithm in C++

 

FIFO is an acronym for 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.

Program in C++

#C++ programming code for FIFO algorithm

#include<bits/stdc++.h>

using namespace std;

// Method to determine pager faults using FIFO

int pageFaults(int pages[], int n, int capacity)

{

       // 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 s;

      // The code will store the pages in FIFO technique

      queue indexes;

      // Stating from the first page

      int page_faults = 0;

      for (int i=0; i<n; i++)

       {

            // Checking the capacity to hold more pages

             if (s.size() < capacity)

              {

                 // if the page is absent, insert it into the set

                // the condition represents page fault

                 if (s.find(pages[i])==s.end())

                    {      
          
                 
          s.insert(pages[i]);

                     // increment the conter for page fault

              page_faults++;

         // 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 (s.find(pages[i]) == s.end())

   {

     //Remove the first page from the queue

     int val = indexes.front();

     indexes.pop();

    // Pop the index page

    s.erase(val);

   // Push the current page in the queue

    s.insert(pages[i]);

    indexes.push(pages[i]);

   // Increment page faults

   page_faults++;

   }

  }

  }

return page_faults;

}

// Driver code

int main()

{

   int pages[] = {7, 0, 1, 2, 0, 3, 0, 4,

    2, 3, 0, 3, 2};

   int n = sizeof(pages)/sizeof(pages[0]);

    int capacity = 4;

    cout << pageFaults(pages, n, capacity);

    return 0;

}

Output:

7