fifoPageReplacement.cpp

#include <iostream>
#include <iomanip>
using namespace std;

class Node {
public:
    int pageNumber;
    Node* next;
    
    Node(int page) {
        pageNumber = page;
        next = nullptr;
    }
};

class FIFOPageReplacement {
private:
    int capacity, size, pageFaults, pageSize;
    Node* front, *rear;

public:
    FIFOPageReplacement(int capacity, int pageSize) {
        this->capacity = capacity;
        this->size = 0;
        this->pageFaults = 0;
        this->pageSize = pageSize;
        front = NULL;
        rear = nullptr;
    }

    bool isPagePresent(int pageNumber) {
        Node* temp = front;
        while (temp) {
            if (temp->pageNumber == pageNumber) return true;
            temp = temp->next;
        }
        return false;
    }

    void removeOldestPage() {
        if (!front) return;
        Node* temp = front;
        front = front->next;
        delete temp;
        size--;
    }

    void insertPage(int pageNumber) {
        if (isPagePresent(pageNumber)) {
            cout << "Page " << pageNumber << " already in memory.\n";
            return;
        }

        if (size == capacity) {
            cout << "Removing oldest page " << front->pageNumber << endl;
            removeOldestPage();
        }

        Node* newNode = new Node(pageNumber);
        if (!rear) {
            front = newNode;
            rear = newNode;
        } 
        else {
            rear->next = newNode;
            rear = newNode;
        }
        size++;
        pageFaults++;
        cout << "Inserted Page " << pageNumber << "\n";
    }

    void displayPages() {
        Node* temp = front;
        cout << "\nCurrent Memory:\n";
        cout << "+";
        for (int i = 0; i < capacity; i++) cout << "------";
        cout << "+\n|";

        int count = 0;
        while (temp) {
            cout << " " << setw(3) << temp->pageNumber << " |";
            temp = temp->next;
            count++;
        }
        while (count < capacity) {
            cout << "     |";
            count++;
        }

        cout << "\n+";
        for (int i = 0; i < capacity; i++) cout << "------";
        cout << "+\n";
    }

    int getPageFaultCount() {
        return pageFaults;
    }

    int getPageHitsCount() {
        return pageSize - pageFaults;
    }

    double hitRate() {
        return (getPageHitsCount()/(double)pageSize)*100.0;
    }

    double faultRate() {
        return (getPageFaultCount()/(double)pageSize)*100.0;
    }

};


int main() {
    cout << "\nEnter the memory size: ";
    int memory;
    cin >> memory;

    int pageSize;
    cout << "Enter the number of pages: ";
    cin >> pageSize;

    FIFOPageReplacement fifo(memory, pageSize);

    int pages[pageSize];
    cout << "Enter the pages separated by space: ";
    for(int i=0; i<pageSize; i++){
        cin >> pages[i];
    }
    cout << endl;

    for (int i = 0; i < pageSize; i++) {
        fifo.insertPage(pages[i]);
        fifo.displayPages();
    }

    cout << "\n\n<----------Result Analysis---------->\n\n";

    cout << "Total Page Faults: " << fifo.getPageFaultCount() << endl;
    cout << "Total Page Hits: " << fifo.getPageHitsCount() << endl << endl;

    cout << "Page Hit Rate = " <<fixed<<setprecision(2) << fifo.hitRate() << " %" << endl;
    cout << "Page Page Rate = " <<fixed<<setprecision(2) << fifo.faultRate() << " %" << endl << endl;
    
    cout << "-------------------------------------";
    return 0;
}


// Total Page Faults = Total Number of Page Requests−Total Page Hits

// Page Fault Rate = Total Page Faults / Total Page Requests

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

// Belady’s Anomaly: for some page-replacement algorithms, the page-fault rate may increase 
// as the number of allocated frames increases.