C++: page replacement with FIFO and LRU
Virtual memory keeps only some pages in physical frames. When a program touches a page that is not in memory, a page fault occurs, and if all frames are full the operating system must choose a page to evict. A good policy evicts a page that will not be needed soon.
C++
#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>
int fifo_faults(const std::vector<int>& refs, std::size_t frames) {
std::deque<int> memory;
int faults = 0;
for (int page : refs) {
if (std::find(memory.begin(), memory.end(), page) == memory.end()) {
++faults;
if (memory.size() == frames) {
memory.pop_front();
}
memory.push_back(page);
}
}
return faults;
}
int lru_faults(const std::vector<int>& refs, std::size_t frames) {
std::vector<int> memory; // least recently used page at the front
int faults = 0;
for (int page : refs) {
auto it = std::find(memory.begin(), memory.end(), page);
if (it != memory.end()) {
memory.erase(it);
} else {
++faults;
if (memory.size() == frames) {
memory.erase(memory.begin());
}
}
memory.push_back(page);
}
return faults;
}
int main() {
std::vector<int> refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
std::cout << "FIFO, 3 frames: " << fifo_faults(refs, 3) << "\n";
std::cout << "LRU, 3 frames: " << lru_faults(refs, 3) << "\n";
std::vector<int> belady = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
std::cout << "Belady FIFO, 3 frames: " << fifo_faults(belady, 3) << "\n";
std::cout << "Belady FIFO, 4 frames: " << fifo_faults(belady, 4) << "\n";
}