Optimal Page Replacement Algorithm

 

Optimal Page Replacement Algorithm

---

1. Aim

To implement the Optimal Page Replacement Algorithm and display the frame contents after each page reference.

---

2. Objective

• To understand the working of the Optimal page replacement strategy

• To replace the page that will not be used for the longest time in the future

• To display the frame table after each page arrival

• To analyze page hits and page faults

---

3. Theory

The Optimal Page Replacement Algorithm replaces the page that will not be used for the longest time in the future.

Key Idea:

“Replace the page whose next use is farthest in the future.”

This algorithm produces the minimum possible number of page faults for a given reference string and number of frames.

⚠️ Note:

Optimal replacement cannot be implemented in real operating systems because future page references are unknown.

It is mainly used as a benchmark to compare other algorithms like FIFO and LRU.

---

4. Data Structures Used

Structure	Purpose
frames[]	Stores pages in memory
pages[]	Page reference string
Loop variables	To scan future references

---

5. Algorithm

1. Initialize all frames as empty (-1)

2. For each page reference:

   • If page exists in frames → Hit

   • Else:

     • If empty frame exists → place page

     • Else:

       • For each page in frame, find next future use

       • Replace page with farthest future use (or never used again)

3. Display frame table after each reference

4. Count page faults

---

6. C Program (Optimal Page Replacement)

#include <stdio.h>

#define MAX_PAGES 50
#define MAX_FRAMES 10

int frames[MAX_FRAMES];
int faults = 0;

/* Initialize frames */
void initializeFrames(int f) {
    for (int i = 0; i < f; i++)
        frames[i] = -1;
}

/* Check if page exists */
int findPage(int page, int f) {
    for (int i = 0; i < f; i++) {
        if (frames[i] == page)
            return i;
    }
    return -1;
}

/* Find page to replace using Optimal strategy */
int findOptimal(int pages[], int n, int index, int f) {
    int farthest = index;
    int pos = -1;

    for (int i = 0; i < f; i++) {
        int j;
        for (j = index + 1; j < n; j++) {
            if (frames[i] == pages[j]) {
                if (j > farthest) {
                    farthest = j;
                    pos = i;
                }
                break;
            }
        }

        /* Page not used in future */
        if (j == n)
            return i;
    }

    if (pos == -1)
        return 0;

    return pos;
}

/* Display frame table */
void displayTable(int page, int f, int hit) {
    printf("%d\t", page);
    for (int i = 0; i < f; i++) {
        if (frames[i] == -1)
            printf("-\t");
        else
            printf("%d\t", frames[i]);
    }
    printf("%s\n", hit ? "Hit" : "Fault");
}

int main() {
    int pages[MAX_PAGES];
    int n, f;

    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]);

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

    initializeFrames(f);

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

    /* Optimal Simulation */
    for (int i = 0; i < n; i++) {
        int pos = findPage(pages[i], f);

        if (pos != -1) {
            displayTable(pages[i], f, 1);
        } else {
            int replaceIndex = -1;

            for (int j = 0; j < f; j++) {
                if (frames[j] == -1) {
                    replaceIndex = j;
                    break;
                }
            }

            if (replaceIndex == -1)
                replaceIndex = findOptimal(pages, n, i, f);

            frames[replaceIndex] = pages[i];
            faults++;

            displayTable(pages[i], f, 0);
        }
    }

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

---

7. Sample Input

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

---

8. Sample Output (Frame Table)

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       0       3       Fault
0       2       0       3       Hit
4       2       4       3       Fault

Total Page Faults = 6

---

9. Observations

• Optimal algorithm gives minimum page faults

• Requires future knowledge

• Used as a benchmark algorithm

---

10. Advantages

✔ Produces minimum page faults
✔ Useful for performance comparison
✔ No Belady’s anomaly

---

11. Disadvantages

❌ Not implementable in real systems
❌ Requires future page references
❌ High computational overhead

---

12. Result

The Optimal Page Replacement Algorithm was successfully implemented and the frame contents were displayed after each page reference.