First-in first-out (FIFO) page replacement algorithm

" The FIFO page replacement algorithm works based on the principle of "First-In-First-Out." When a page fault occurs and the page table is full, the operating system selects the oldest page in memory (i.e., the page that has been in memory the longest) for eviction. The newly requested page is then loaded into the memory page frame freed up by the eviction."

Key Points:

                        - FIFO is easy to implement and requires minimal bookkeeping.
                        - It suffers from the "Belady's Anomaly," where increasing the number of page frames can result in more page faults.
                        - FIFO does not consider the frequency of page access or the likelihood of future page accesses.
                        - Despite its simplicity, FIFO is not always the most efficient page replacement algorithm, especially in scenarios where pages have varying access frequencies.


#include<iostream>
#include<string>
#include<vector>
#include<unordered_set>
#include<queue>
#include<sstream>
#include<limits>
using namespace std;


int pageFaults(vector& pages, int capacity) {
    unordered_set s;

    queue indexes;

    int page_faults = 0;

    for (int page : pages) {

        if (s.size() < capacity) {

            if (s.find(page) == s.end()) {
                s.insert(page);
                
                page_faults++;
            
                indexes.push(page);
            }
        }
    
        else {
            
            if (s.find(page) == s.end()) {
                
                int val = indexes.front();
                
                indexes.pop();
                s.erase(val);
                s.insert(page);
                indexes.push(page);
                page_faults++;
            }
        }
    }

    return page_faults;
}

int main() {
    cout << "Enter the reference string (space-separated): ";
    string referenceStringInput;
    getline(cin, referenceStringInput, '\n');
    istringstream iss(referenceStringInput);
    vector referenceString;
    int page;
    while (iss >> page) {
        referenceString.push_back(page);
    }

    int pageFrameSize;
    cout << "Enter the page frame size: ";
    while (!(cin >> pageFrameSize)) {
        cout << "Invalid input. Please enter an integer: ";
        cin.clear();
        cin.ignore(numeric_limits::max(), '\n');
    }

    cout << "Total page faults: " << pageFaults(referenceString, pageFrameSize) << endl;
    return 0;
}