Cache Replacement Simulator in C++

A console-based C++20 project that simulates how a fixed-size cache handles memory/page requests. The same reference string is tested with different replacement policies, and the program compares their hits, misses, hit rate, miss rate, replacement count, and final cache state.

This is a small student project focused on Operating Systems and Data Structures concepts. It is not a full OS-level cache system.

Why I built this

Cache replacement is a common topic in Operating Systems. When a cache is full and a new page is requested, the system needs a rule to decide which page should be removed.

I built this project to understand how FIFO, LRU, LFU, and Optimal replacement behave on the same input trace, and how the choice of policy affects the hit ratio.

What the project does

• Accepts a memory reference string as input
• Accepts cache size / frame count as input
• Runs FIFO, LRU, LFU, and Optimal replacement on the same trace
• Prints step-by-step cache state for FIFO
• Prints a final comparison table for all policies
• Calculates cache hits, misses, hit rate, miss rate, replacements, and final cache state
• Includes a sample trace and a small test file

Replacement policies implemented

FIFO

FIFO removes the page that entered the cache first. It is simple, but it does not consider how recently or how often a page was used.

LRU

LRU removes the least recently used page. This project uses a list and unordered_map to keep track of recent usage.

LFU

LFU removes the page with the lowest access frequency. If two pages have the same frequency, this simulator removes the one that was loaded earlier.

Optimal

Optimal removes the page whose next use is farthest in the future. It is included only as a comparison baseline because it needs future knowledge, which real systems usually do not have.

Folder structure

Cache-Replacement-Simulator/
  src/
    main.cpp
    CacheSimulator.cpp
    tests.cpp
  include/
    CacheSimulator.h
  data/
    sample_trace.txt
  Makefile
  run_cache_simulator.bat
  README.md

How to compile and run

Use a compiler that supports C++20.

On Windows PowerShell:

g++ -std=c++20 src/main.cpp src/CacheSimulator.cpp -Iinclude -o cache_simulator.exe
.\cache_simulator.exe

On Linux/macOS:

g++ -std=c++20 src/main.cpp src/CacheSimulator.cpp -Iinclude -o cache_simulator
./cache_simulator

If make is available:

make
make run
make run_test

On Windows, run_cache_simulator.bat can be used after building. It runs the program from the correct folder and waits before closing.

How to run tests

The project includes a small test file in src/tests.cpp.

With make:

make test
make run_test

Without make:

g++ -std=c++20 src/tests.cpp src/CacheSimulator.cpp -Iinclude -o cache_tests
./cache_tests

The GitHub Actions workflow also runs the test command on push and pull request.

Suggested GitHub repository description and topics are listed in .github/repo-details.md.

Input format

The program gives two options:

1. Enter reference string manually
2. Load sample trace from data/sample_trace.txt

Manual input format:

Reference string:
7 0 1 2 0 3 0 4 2 3 0 3 2

Cache size:
3

The sample file follows the same format: one line for the reference string and one line for the cache size.

Sample output

This output is from data/sample_trace.txt.

Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2
Cache size: 3

Final comparison
Policy          Hits    Misses    Hit Rate   Miss Rate   Replacements   Final State
-----------------------------------------------------------------------------------------
FIFO               3        10      23.08%      76.92%              7   [ 0 2 3 ]
LRU                4         9      30.77%      69.23%              6   [ 0 3 2 ]
LFU                5         8      38.46%      61.54%              5   [ 3 0 2 ]
Optimal            6         7      46.15%      53.85%              4   [ 2 0 3 ]

The program also prints the FIFO cache state after each request before showing this final table.

Comparison table

For the included sample trace, LFU gives a better hit rate than FIFO and LRU with the tie-break rule used in this project. Optimal gives the best result because it already knows the future reference string.

Policy	Hits	Misses	Hit Rate	Miss Rate	Replacements
FIFO	3	10	23.08%	76.92%	7
LRU	4	9	30.77%	69.23%	6
LFU	5	8	38.46%	61.54%	5
Optimal	6	7	46.15%	53.85%	4

Time complexity

Let n be the number of page requests and k be the cache size.

Policy	Time complexity in this implementation
FIFO	O(n * k), because the cache vector is searched
LRU	O(n * k), with O(1) recent-list updates after lookup
LFU	O(n * k), because the cache may be scanned to choose a victim
Optimal	O(n * k * n), because future requests are searched

The code is written for readability and learning, not for maximum optimization.

What I learned

• How page replacement policies make different eviction decisions
• How hit rate and miss rate change based on access pattern
• How STL containers like vector, queue, list, and unordered_map can be used in simulation problems
• Why Optimal replacement is useful for comparison but not practical in real systems
• How to keep algorithm output testable with a small sample trace

Limitations

• Input supports only integer page numbers
• Only FIFO currently prints step-by-step cache states
• LFU uses a simple tie-break rule when frequencies are equal
• Optimal needs the complete future trace, so it is only a study baseline
• The project does not generate graphs or save reports to files

Future improvements

• Add step-by-step output for LRU, LFU, and Optimal
• Allow the user to choose which policy to trace
• Add more sample trace files
• Save the comparison table to a CSV file
• Add more test cases for edge inputs