Write the simulation program for demand paging and show the page scheduling and total number of page faults according the Optimal page replacement algorithm. Assume the memory of n frames.
Reference String : 7, 5, 4, 8, 5, 7, 2, 3, 1, 3, 5, 9, 4, 6

#include <stdio.h>

#define MAX_PAGES 100
#define MAX_FRAMES 10

// Function to find the index of the page that will not be used for the longest time
int findOptimalPage(int referenceString[], int frame[], int n, int m, int currentIndex) {
    int maxDistance = -1;
    int pageIndex = -1;
    for (int i = 0; i < m; i++) {
        int j;
        for (j = currentIndex; j < n; j++) {
            if (frame[i] == referenceString[j]) {
                break;
            }
        }
        if (j == n) {
            return i; // This page will not be used again
        }
        if (j - currentIndex > maxDistance) {
            maxDistance = j - currentIndex;
            pageIndex = i;
        }
    }
    return pageIndex;
}

// Function to simulate Optimal Page Replacement
void optimalPageReplacement(int referenceString[], int n, int m) {
    int frame[MAX_FRAMES];
    int pageFaults = 0;
    int pageHits = 0;

    // Initialize frames to -1 (indicating empty)
    for (int i = 0; i < m; i++) {
        frame[i] = -1;
    }

    printf("Reference String\tFrames\t\tPage Faults\n");
    for (int i = 0; i < n; i++) {
        int page = referenceString[i];
        int found = 0;

        // Check if the page is already in one of the frames
        for (int j = 0; j < m; j++) {
            if (frame[j] == page) {
                found = 1;
                pageHits++;
                break;
            }
        }

        if (!found) {
            // Page fault
            pageFaults++;
            int replaceIndex = -1;

            // If there's an empty frame, use it
            for (int j = 0; j < m; j++) {
                if (frame[j] == -1) {
                    replaceIndex = j;
                    break;
                }
            }

            // If all frames are full, use optimal replacement strategy
            if (replaceIndex == -1) {
                replaceIndex = findOptimalPage(referenceString, frame, n, m, i + 1);
            }

            frame[replaceIndex] = page;
        }

        // Print the current state
        printf("%d\t\t\t", page);
        for (int j = 0; j < m; j++) {
            if (frame[j] != -1) {
                printf("%d ", frame[j]);
            }
        }
        printf("\t\t%d\n", pageFaults);
    }

    printf("Total number of page faults: %d\n", pageFaults);
    printf("Total number of page hits: %d\n", pageHits);
}

int main() {
    int referenceString[] = {7, 5, 4, 8, 5, 7, 2, 3, 1, 3, 5, 9, 4, 6};
    int n = sizeof(referenceString) / sizeof(referenceString[0]);
    int m;

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

    if (m > MAX_FRAMES) {
        printf("Number of frames exceeds the maximum limit of %d.\n", MAX_FRAMES);
        return 1;
    }

    if (m <= 0) {
        printf("Number of frames must be greater than 0.\n");
        return 1;
    }

    optimalPageReplacement(referenceString, n, m);

    return 0;
}