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>
#include <stdlib.h>
#include <limits.h>

#define MAX_FRAMES 100

// Function to find the optimal page to replace
int find_optimal_page(int frames[], int num_frames, int reference_string[], int start, int end) {
    int page_indices[MAX_FRAMES];
    for (int i = 0; i < num_frames; i++) {
        page_indices[i] = -1; // Initialize all indices to -1
    }

    // Fill the indices with the next occurrence of each page
    for (int i = start; i < end; i++) {
        for (int j = 0; j < num_frames; j++) {
            if (frames[j] == reference_string[i]) {
                page_indices[j] = i;
                break;
            }
        }
    }

    // Find the page with the farthest next occurrence
    int max_index = 0;
    int max_distance = INT_MIN;
    for (int i = 0; i < num_frames; i++) {
        if (page_indices[i] == -1) {
            return i; // If a page is not going to be used again, replace it
        }
        if (page_indices[i] > max_distance) {
            max_distance = page_indices[i];
            max_index = i;
        }
    }
    return max_index;
}

// Function to simulate the Optimal Page Replacement algorithm
void optimal_page_replacement(int reference_string[], int num_references, int num_frames) {
    int frames[MAX_FRAMES];
    int page_faults = 0;

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

    printf("Reference String: ");
    for (int i = 0; i < num_references; i++) {
        printf("%d ", reference_string[i]);
    }
    printf("\n");

    printf("Page Scheduling:\n");

    for (int i = 0; i < num_references; i++) {
        int page = reference_string[i];
        int page_index = -1;

        // Check if the page is already in one of the frames
        for (int j = 0; j < num_frames; j++) {
            if (frames[j] == page) {
                page_index = j;
                break;
            }
        }

        if (page_index == -1) { // Page fault
            // Find the page to replace
            int replace_index = find_optimal_page(frames, num_frames, reference_string, i + 1, num_references);
            frames[replace_index] = page;
            page_faults++;

            printf("Reference: %d | Frames: ", page);
            for (int j = 0; j < num_frames; j++) {
                printf("%d ", frames[j]);
            }
            printf("(Page fault)\n");
        } else {
            printf("Reference: %d | Frames: ", page);
            for (int j = 0; j < num_frames; j++) {
                printf("%d ", frames[j]);
            }
            printf("(No page fault)\n");
        }
    }

    printf("Total Page Faults: %d\n", page_faults);
}

int main() {
    // Define the reference string and the number of frames
    int reference_string[] = {7, 5, 4, 8, 5, 7, 2, 3, 1, 3, 5, 9, 4, 6, 2};
    int num_references = sizeof(reference_string) / sizeof(reference_string[0]);
    int num_frames = 3; // Number of memory frames

    // Simulate Optimal page replacement
    optimal_page_replacement(reference_string, num_references, num_frames);

    return 0;
}