FIFO Page Replacement Algorithm In C

March 16, 2022

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.

FIFO in OS

 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

Run 
// C program for FIFO page replacement algorithm
#include <stdio.h>
int main()
{
    int incomingStream[] = {4, 1, 2, 4, 5};
    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];
        }
      
        printf("\n");
        printf("%d\t\t\t",incomingStream[m]);
        for(n = 0; n < frames; n++)
        {
            if(temp[n] != -1)
                printf(" %d\t\t\t", temp[n]);
            else
                printf(" - \t\t\t");
        }
    }

    printf("\nTotal Page Faults:\t%d\n", pageFaults);
    return 0;
}

Output – 

Incoming Frame 1 Frame 2 Frame 3
4         4       -      - 
1         4       1      - 
2         4       1      2 
4         4       1      2 
5         5       1      2 
Total Page Faults: 4
  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