Demonstration and Analysis of Belady’s Anomaly

 

Demonstration and Analysis of Belady’s Anomaly 

1. Aim

To demonstrate Belady’s Anomaly using FIFO page replacement by displaying the frame table with Hit/Miss status and comparing page faults for different frame sizes.

---

2. Objective

• To simulate FIFO page replacement

• To display frame contents after each reference

• To calculate total page faults

• To verify Belady’s anomaly

---

3. Theory

🔹 Belady’s Anomaly

Belady’s anomaly occurs when:

Increasing the number of frames results in an increase in page faults.

This happens in FIFO, but not in LRU or Optimal (stack algorithms).

---

4. Classic Reference String

1 2 3 4 1 2 5 1 2 3 4 5

This string shows anomaly for FIFO when frames increase from 3 to 4.

---

5. Algorithm

For each frame size:

1. Initialize frames as empty.

2. For each page reference:

   • If page exists → Hit

   • Else → Replace using FIFO → Miss

3. Display frame contents and status.

4. Count page faults.

5. Compare results.

---

C Program (With Frame Table and Hit/Miss)

#include <stdio.h>

#define MAX 50

void simulateFIFO(int pages[], int n, int framesCount) {
    int frames[10];
    int pointer = 0;
    int faults = 0;
    int hits = 0;

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

    printf("\nFIFO with %d Frames:\n", framesCount);
    printf("Page\t");
    for (int i = 0; i < framesCount; i++)
        printf("F%d\t", i+1);
    printf("Status\n");

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

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

        if (found) {
            hits++;
        } else {
            frames[pointer] = pages[i];
            pointer = (pointer + 1) % framesCount;
            faults++;
        }

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

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

    printf("\nTotal Hits   = %d\n", hits);
    printf("Total Misses = %d\n", faults);
    printf("Hit Rate     = %.2f%%\n", (hits * 100.0) / n);
}

int main() {
    int pages[MAX];
    int n;

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

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

    // Run FIFO for 3 and 4 frames
    simulateFIFO(pages, n, 3);
    simulateFIFO(pages, n, 4);

    return 0;
}

---

Sample Input

Enter number of pages: 12
Enter page reference string:
1 2 3 4 1 2 5 1 2 3 4 5

---

Sample Output 

FIFO with 3 Frames

FIFO with 3 Frames:
Page    F1      F2      F3      Status
1       1       -       -       Miss
2       1       2       -       Miss
3       1       2       3       Miss
4       4       2       3       Miss
1       4       1       3       Miss
2       4       1       2       Miss
5       5       1       2       Miss
1       5       1       2       Hit
2       5       1       2       Hit
3       5       3       2       Miss
4       5       3       4       Miss
5       5       3       4       Hit

Total Hits   = 3
Total Misses = 9
Hit Rate     = 25.00%
FIFO with 4 Frames
FIFO with 4 Frames:
Page    F1      F2      F3      F4      Status
1       1       -       -       -       Miss
2       1       2       -       -       Miss
3       1       2       3       -       Miss
4       1       2       3       4       Miss
1       1       2       3       4       Hit
2       1       2       3       4       Hit
5       5       2       3       4       Miss
1       5       1       3       4       Miss
2       5       1       2       4       Miss
3       5       1       2       3       Miss
4       4       1       2       3       Miss
5       4       5       2       3       Miss

Total Hits   = 2
Total Misses = 10
Hit Rate     = 16.67%

---

Observation Table

Frames	Hits	Misses
3	3	9
4	2	10

Page faults increased when frames increased → Belady’s Anomaly observed.

---

6. Result

Belady’s Anomaly was successfully demonstrated using FIFO. The frame table clearly shows that increasing frames from 3 to 4 increased page faults.