FIFO Page Replacement Algorithm

 

FIFO Page Replacement Algorithm 

---

1. Aim

To simulate the FIFO page replacement algorithm and display the frame contents in a tabular form for each page reference.

---

2. Objective

• To understand FIFO page replacement

• To observe page hits and faults

• To display memory frame status step-by-step

---

3. Theory 

3.1 Virtual Memory

Virtual memory allows execution of processes larger than physical memory by dividing memory into pages.

When a required page is not in memory, a page fault occurs and the OS must replace an existing page.

---

3.2 FIFO Page Replacement Algorithm

FIFO (First-In First-Out) replaces the page that entered memory earliest, irrespective of how frequently or recently it was used.

➡ Conceptually simple but may suffer from Belady’s anomaly.

---

3.3 Key Characteristics

Feature	Description
Replacement policy	Oldest page
Data structure	Queue
Implementation	Simple
Drawback	Belady’s anomaly

4. Algorithm (FIFO)

1. Initialize all frames to -1

2. Maintain a pointer (next) to track the oldest page

3. For each page reference:

   • If page is found → Hit

   • Else → Fault

     • Replace frame at next

     • Move next circularly

4. Count total page faults

---

5. Example

Page Reference String

7 0 1 2 0 3 0 4

Number of Frames

3

---

6. Expected Tabular Format

Page	Frame 1	Frame 2	Frame 3	Status
7	7	-	-	Fault
0	7	0	-	Fault
1	7	0	1	Fault
2	2	0	1	Fault
0	2	0	1	Hit
3	2	3	1	Fault
0	2	3	0	Fault
4	4	3	0	Fault

---

7. C Program 

#include <stdio.h>

int main() {
    int pages[50], frames[10];
    int n, f;
    int i, j;
    int next = 0;      // FIFO pointer
    int found;
    int faults = 0;

    printf("Enter number of pages: ");
    scanf("%d", &n);

    printf("Enter page reference string:\n");
    for (i = 0; i < n; i++)
        scanf("%d", &pages[i]);

    printf("Enter number of frames: ");
    scanf("%d", &f);

    // Initialize frames
    for (i = 0; i < f; i++)
        frames[i] = -1;

    // Table header
    printf("\nPage\t");
    for (i = 0; i < f; i++)
        printf("Frame%d\t", i + 1);
    printf("Status\n");

    // FIFO Simulation
    for (i = 0; i < n; i++) {
        found = 0;

        // Check hit
        for (j = 0; j < f; j++) {
            if (frames[j] == pages[i]) {
                found = 1;
                break;
            }
        }

        if (!found) {
            frames[next] = pages[i];
            next = (next + 1) % f;
            faults++;
        }

        // Print row
        printf("%d\t", pages[i]);
        for (j = 0; j < f; j++) {
            if (frames[j] == -1)
                printf("-\t");
            else
                printf("%d\t", frames[j]);
        }

        if (found)
            printf("Hit\n");
        else
            printf("Fault\n");
    }

    printf("\nTotal Page Faults = %d\n", faults);

    return 0;
}

---

8. Sample Input

Enter number of pages: 8
Enter page reference string:
7 0 1 2 0 3 0 4
Enter number of frames: 3

---

9. Sample Output (Formatted)

Page    Frame1  Frame2  Frame3  Status
7       7       -       -       Fault
0       7       0       -       Fault
1       7       0       1       Fault
2       2       0       1       Fault
0       2       0       1       Hit
3       2       3       1       Fault
0       2       3       0       Fault
4       4       3       0       Fault

Total Page Faults = 7

---

10. Observations

• FIFO uses a circular pointer

• Frame replacement is independent of usage

• Recently used pages may be replaced

---

11. Advantages

• Simple and fast

• Easy to implement

---

12. Disadvantages

• Suffers from Belady’s anomaly

• Not optimal for real systems

---

13. Result

The FIFO page replacement algorithm was successfully implemented and the frame contents were displayed in a tabular format for each page reference.