chit6

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
#include <algorithm>

using namespace std;

void optimalPageReplacement(vector<int>& pages, int capacity) {
int pageFaults = 0;
vector<int> pageFrames(capacity, -1);

for (int i = 0; i < pages.size(); i++) {
    bool pageFound = false;

    // Check if the page is already in the memory
    for (int j = 0; j < capacity; j++) {
        if (pageFrames[j] == pages[i]) {
            pageFound = true;
            break;
        }
    }

    if (!pageFound) {
        // If there is an empty frame, place the page in it
        bool emptyFrame = false;
        for (int j = 0; j < capacity; j++) {
            if (pageFrames[j] == -1) {
                pageFrames[j] = pages[i];
                emptyFrame = true;
                break;
            }
        }

        if (!emptyFrame) {
            // If no empty frame, find the page that will not be used for the longest period in the future
            unordered_map<int, int> futureOccurrences;

            // Track future occurrences of pages in the frame
            for (int j = 0; j < capacity; j++) {
                futureOccurrences[pageFrames[j]] = INT_MAX;
            }

            for (int j = i + 1; j < pages.size(); j++) {
                for (int k = 0; k < capacity; k++) {
                    if (pageFrames[k] == pages[j]) {
                        futureOccurrences[pages[j]] = j;
                        break;
                    }
                }
            }

            // Find the page that is furthest in the future
            int pageToReplace = -1;
            int farthestIndex = -1;
            for (int j = 0; j < capacity; j++) {
                if (futureOccurrences[pageFrames[j]] > farthestIndex) {
                    farthestIndex = futureOccurrences[pageFrames[j]];
                    pageToReplace = pageFrames[j];
                }
            }

            // Replace the page
            for (int j = 0; j < capacity; j++) {
                if (pageFrames[j] == pageToReplace) {
                    pageFrames[j] = pages[i];
                    break;
                }
            }
        }

        cout << "Page " << pages[i] << " is loaded into the memory." << endl;
        pageFaults++;
    } else {
        cout << "Page " << pages[i] << " is already in the memory." << endl;
    }
}

cout << "\nTotal Page Faults: " << pageFaults << endl;

}

int main() {
// Example usage
vector<int> pageReferences = {2, 3, 4, 2, 1, 3, 7, 5, 4, 3};
int memoryCapacity = 3;

optimalPageReplacement(pageReferences, memoryCapacity);

return 0;

}