FIFO Page Replacement Algorithm In C

May 7, 2021

FIFO in OS

FIFO Page Replacement Algorithm in C

 

The operating system uses the method of paging for memory management. This method involves page replacement algorithms to make a decision about which pages should be replaced when new pages are demanded. The demand occurs when the operating system needs a page for processing, and it is not present in the main memory. The situation is known as a page fault.

 In this situation, the operating system replaces an existing page from the main memory by bringing a new page from the secondary memory.

In such situations, the FIFO method is used, which is also refers to the First in First Out concept. This is the simplest page replacement method in which the operating system maintains all the pages in a queue. Oldest pages are kept in the front, while the newest is kept at the end. On a page fault, these pages from the front are removed first, and the pages in demand are added.

Algorithm for FIFO Page Replacement

  • Step 1. Start to traverse the pages.
  • Step 2. If the memory holds fewer pages, then the capacity else goes to step 5.
  • Step 3. Push pages in the queue one at a time until the queue reaches its maximum capacity or all page requests are fulfilled.
  • Step 4. If the current page is present in the memory, do nothing.
  • Step 5. Else, pop the topmost page from the queue as it was inserted first.
  • Step 6. Replace the topmost page with the current page from the string.
  • Step 7. Increment the page faults.
  • Step 8. Stop

Read Also – FIFO algorithm in python

FIFO Page Replacement Algorithm in C

#include <stdio.h>
int main()
{
      int referenceString[10], pageFaults = 0, m, n, s, pages, frames;
      printf("\nEnter the number of Pages:\t");
      scanf("%d", &pages);
      printf("\nEnter reference string values:\n");
      int(m = 0; m < pages; m++)
      {
            printf("Value No. [%d]:\t", m + 1);
            scanf("%d", &referenceString[m]);
      }
      printf("\n What are the total number of frames:\t");
      {
            scanf("%d", &frames);
      }
      inttemp[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(referenceString[m] == temp[n])
                  {
                        s++;
                        pageFaults--;
                  }
            }     
            pageFaults++;
            if((pageFaults <= frames) && (s == 0))
            {
                  temp[m] = referenceString[m];
            }   
            else if(s == 0)
            {
                  temp[(pageFaults - 1) % frames] = referenceString[m];
            }
            printf("\n");
            for(n = 0; n < frames; n++)
            {     
                  printf("%d\t", temp[n]);
            }
      } 
      printf("\nTotal Page Faults:\t%d\n", pageFaults);
      return 0;
}

Output – 

Enter the number of Pages: 5
Enter reference string values: 
Value No. [1]: 4
Value No. [2]: 1
Value No. [3]: 2
Value No. [4]: 4
Value No. [5]: 5
What are the total number of frames: 3
4	-1	-1
4	1	-1
4	1	2
4	1	2
5	1	2
Total number of page faults: 4