C++: page replacement with FIFO and LRU

Before you start

C++ vectors, deques, and algorithms.

Count page faults for two replacement policies and see Belady's anomaly.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

FIFO evicts the page that has been in memory longest. LRU evicts the page that was used least recently, which usually matches how programs behave better. FIFO has a surprising property called Belady's anomaly: for some reference strings, giving it more frames increases the number of faults. LRU does not have this problem.

Code example

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";
}

Output

FIFO, 3 frames: 15
LRU,  3 frames: 12
Belady FIFO, 3 frames: 9
Belady FIFO, 4 frames: 10

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1#include <algorithm>

2#include <deque>

3#include <iostream>

4#include <vector>

6int fifo_faults(const std::vector<int>& refs, std::size_t frames) {

7 std::deque<int> memory;

8 int faults = 0;

9 for (int page : refs) {

10 if (std::find(memory.begin(), memory.end(), page) == memory.end()) {

11 ++faults;

12 if (memory.size() == frames) {

13 memory.pop_front();

14 }

15 memory.push_back(page);

16 }

17 }

18 return faults;

19}

21int lru_faults(const std::vector<int>& refs, std::size_t frames) {

22 std::vector<int> memory; // least recently used page at the front

23 int faults = 0;

24 for (int page : refs) {

25 auto it = std::find(memory.begin(), memory.end(), page);

26 if (it != memory.end()) {

27 memory.erase(it);

28 } else {

29 ++faults;

30 if (memory.size() == frames) {

31 memory.erase(memory.begin());

32 }

33 }

34 memory.push_back(page);

35 }

36 return faults;

37}

39int main() {

40 std::vector<int> refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};

41 std::cout << "FIFO, 3 frames: " << fifo_faults(refs, 3) << "\n";

42 std::cout << "LRU, 3 frames: " << lru_faults(refs, 3) << "\n";

44 std::vector<int> belady = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};

45 std::cout << "Belady FIFO, 3 frames: " << fifo_faults(belady, 3) << "\n";

46 std::cout << "Belady FIFO, 4 frames: " << fifo_faults(belady, 4) << "\n";

47}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A page that is not in any frame causes a fault.	`—`	—
FIFO evicts the oldest resident page.	`evict the page loaded first`	—
LRU moves a hit page to the most-recent end; on a miss it evicts the front, the least recently used.	`evict the page loaded first`	—
On this string FIFO makes 15 faults and LRU 12.	`evict the page loaded first`	FIFO, 3 frames: 15 LRU, 3 frames: 12
With FIFO, a fourth frame raises the fault count from 9 to 10: Belady's anomaly.	`evict the page loaded first`	FIFO, 3 frames: 15 LRU, 3 frames: 12 Belady FIFO, 3 frames: 9 Belady FIFO, 4 frames: 10

Behind the scenes

How C++ processes this code

The C++ compiler produces a native executable. Execution enters main, where objects and function calls perform the work.

Cost and common mistakes

Each reference costs O(f) for f frames in this simple model.

Real systems approximate LRU with reference bits (the clock algorithm) because tracking exact recency on every access is too expensive.
These counts depend on the reference string. Policies should be compared on realistic access patterns.

Try it yourself

Which policy would you choose for a program that loops over a few pages repeatedly?

Reveal answer and reasoning

LRU, because recently used pages are likely to be used again, so keeping them resident avoids faults.