#include <iostream>
#include <vector>
#include <list>
#include <unordered_set>
using namespace std;
// Function to perform FIFO page replacement algorithm
double FIFO(vector<int>& pages, int frames) {
list<int> frameList;
unordered_set<int> frameSet;
int pageFaults = 0;
for(int page : pages) {
if(frameSet.find(page) == frameSet.end()) {
if(frameList.size() == frames) {
int front = frameList.front();
frameSet.erase(front);
frameList.pop_front();
frameList.push_back(page);
frameSet.insert(page);
pageFaults++;
return 1.0 - (double)pageFaults / pages.size();
}
// Function to perform LRU page replacement algorithm
double LRU(vector<int>& pages, int frames) {
list<int> frameList;
unordered_set<int> frameSet;
int pageFaults = 0;
for(int page : pages) {
if(frameSet.find(page) == frameSet.end()) {
if(frameList.size() == frames) {
int back = frameList.back();
frameSet.erase(back);
frameList.pop_back();
frameList.push_front(page);
frameSet.insert(page);
pageFaults++;
} else {
frameList.remove(page);
frameList.push_front(page);
return 1.0 - (double)pageFaults / pages.size();
// Function to perform Optimal page replacement algorithm
double Optimal(vector<int>& pages, int frames) {
vector<int> frame(frames, -1);
int pageFaults = 0;
for(int i = 0; i < pages.size(); ++i) {
bool pageFound = false;
for(int j = 0; j < frames; ++j) {
if(frame[j] == pages[i]) {
pageFound = true;
break;
if(!pageFound) {
int pageToReplace = -1;
int farthest = i;
for(int j = 0; j < frames; ++j) {
int k;
for(k = i; k < pages.size(); ++k) {
if(frame[j] == pages[k]) {
break;
if(k == pages.size()) {
pageToReplace = j;
break;
if(k > farthest) {
farthest = k;
pageToReplace = j;
}
frame[pageToReplace] = pages[i];
pageFaults++;
return 1.0 - (double)pageFaults / pages.size();
int main() {
vector<int> pages = {7,5,3,1,2,0,3,2,7,1,0,3,2,0,1,7,5,3,6,3,2,0};
int frames = 3;
double hitRatioFIFO = FIFO(pages, frames);
double hitRatioLRU = LRU(pages, frames);
double hitRatioOptimal = Optimal(pages, frames);
cout << "FIFO Hit Ratio: " << hitRatioFIFO * 100 << "%" << endl;
cout << "LRU Hit Ratio: " << hitRatioLRU * 100 << "%" << endl;
cout << "Optimal Hit Ratio: " << hitRatioOptimal * 100 << "%" << endl;
return 0;
