FIFO Page Replacement Algorithm

FIFO - First In First Out          

1. * What is FIFO Page Replacement?

   FIFO, or First-In-First-Out, is a straightforward page replacement algorithm. It follows the principle that the first page to be brought into memory is the first one to be replaced.

* How FIFO Works

FIFO operates on a simple premise: when a page needs to be replaced, the oldest one in memory is selected. This ensures a fair and predictable approach to managing the memory space.

* Implementing FIFO in Operating Systems

To implement FIFO, follow these steps:

• Initialize a Queue: Create a queue to hold pages in the order they arrive.
• Page Arrival: Add pages to the queue as they arrive.
• Page Replacement: When a page needs to be replaced, remove the page at the front of the queue.

                                                                                                 

 Here's a step-by-step explanation of the FIFO page replacement algorithm:

• Initialize: Set up a data structure (an array, for example) to represent the page frames in memory. Initially, all frames are empty.

• Page Access: For each page access in the sequence:

• Check if the page is already in a page frame.
  • If yes, it's a page hit.
  • If no, it's a page fault.

• Page Fault Handling: When a page fault occurs:

• Replace the oldest page in memory (the one that has been in memory the longest).
• Update the page frame with the new page.
• Continue to the next page access.
• Repeat: Continue this process for each page access in the sequence.

* Advantages and Disadvantages of FIFO

Advantages:

• Simplicity: FIFO is easy to understand and implement.
• Predictability: The order of page replacement is clear and follows a consistent pattern.

Disadvantages:

• Belady's Anomaly: In some cases, increasing the number of frames may result in more page faults, known as Belady's Anomaly.

****************************************************************

program:

#include <stdio.h>

#include <stdlib.h>

#define MAX_FRAMES 3

// Function to find if a page is present in memory

int isPagePresent(int page, int *frames, int frameCount) {

    for (int i = 0; i < frameCount; i++) {

        if (frames[i] == page) {

            return 1; // Page found in memory

        }

    }

    return 0; // Page not found in memory

}

// Function to display the content of memory frames

void displayFrames(int *frames, int frameCount) {

    printf("Memory frames: ");

    for (int i = 0; i < frameCount; i++) {

        if (frames[i] == -1) {

            printf("[ ] ");

        } else {

            printf("[%d] ", frames[i]);

        }

    }

    printf("\n");

}

// Function to simulate FIFO page replacement algorithm

void fifoPageReplacement(int *pages, int pageCount) {

    int frames[MAX_FRAMES]; // Array to represent memory frames

    int frameCount = 0; // Number of frames currently occupied

    for (int i = 0; i < MAX_FRAMES; i++) {

        frames[i] = -1; // Initialize frames with -1 (indicating an empty frame)

    }

    int pageFaults = 0;

    printf("FIFO Page Replacement Algorithm:\n");

    for (int i = 0; i < pageCount; i++) {

        printf("Reference to page %d:\n", pages[i]);

        if (!isPagePresent(pages[i], frames, frameCount)) {

            // Page fault

            if (frameCount < MAX_FRAMES) {

                // If there is an empty frame, use it

                frames[frameCount] = pages[i];

                frameCount++;

            } else {

                // Replace the oldest page (first in)

                int oldestPageIndex = 0;

                for (int j = 1; j < frameCount; j++) {

                    if (frames[j] < frames[oldestPageIndex]) {

                        oldestPageIndex = j;

                    }

                }

                frames[oldestPageIndex] = pages[i];

            }

            pageFaults++;

            displayFrames(frames, frameCount);

        } else {

            printf("Page %d is already in memory.\n", pages[i]);

        }

    }

    printf("Total page faults: %d\n", pageFaults);

}

int main() {

    int pages[] = {0, 1, 2, 3, 2, 4, 5, 3, 4, 6, 3, 7, 8, 7, 8, 9, 7, 8, 9, 5};

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

    fifoPageReplacement(pages, pageCount);

    return 0;

}

Output :

FIFO Page Replacement Algorithm:

Reference to page 0:

Memory frames: [0]

Reference to page 1:

Memory frames: [0] [1]

Reference to page 2:

Memory frames: [0] [1] [2]

Reference to page 3:

Memory frames: [3] [1] [2]

Reference to page 2:

Page 2 is already in memory.

Reference to page 4:

Memory frames: [3] [4] [2] 

Reference to page 5:

Memory frames: [3] [4] [5]

Reference to page 3:

Page 3 is already in memory.

Reference to page 4:

Page 4 is already in memory.

Reference to page 6:

Memory frames: [6] [4] [5]

Reference to page 3:

Memory frames: [6] [3] [5]

Reference to page 7:

Memory frames: [6] [7] [5]

Reference to page 8:

Memory frames: [6] [7] [8]

Reference to page 7:

Page 7 is already in memory.

Reference to page 8:

Page 8 is already in memory.

Reference to page 9:

Memory frames: [9] [7] [8]

Reference to page 7:

Page 7 is already in memory.

Reference to page 8:

Page 8 is already in memory.

Reference to page 9:

Page 9 is already in memory.

Reference to page 5:

Memory frames: [9] [5] [8]

Total page faults: 12

****************** Thanks for Visiting our website *****************