A5. Page replacement

Goal

When there are no free frames, the kernel chooses which page to evict, and that determines how many times a process stops on a page fault. Module 12 describes the replacement algorithms in words and a table. Here you’ll run them on the same access trace and get numbers, including one that defies common sense: for FIFO, more memory can mean more faults.

After this lab you will be able to:

implement the FIFO, LRU, clock, and optimal algorithms and count the faults for each on a given trace;
reproduce Belady’s anomaly on FIFO and explain why it’s impossible on LRU and on optimal;
explain why exact LRU isn’t implemented in hardware and what the clock algorithm replaces it with;
read a “number of frames → faults” graph and point out the program’s working set size on it;
say why a random trace proves nothing and where to get a real one.

The same curve is behind the question of how much memory to give a service: before the knee, every added megabyte reduces the number of faults; after the knee, it barely does.

Task

Write a program pagesim that reads an access trace from a file and, for a given number of frames, counts page faults and hits for each algorithm.

./pagesim --frames 3 --algo fifo trace.txt
./pagesim --frames 3 --algo all  trace.txt

What it must do:

four algorithms named fifo, lru, clock, and optimal; --algo all runs them all together;
input: an access trace, page numbers one per line. Empty lines and lines with # are ignored;
output: one line per algorithm with the name, the number of faults, and the number of hits separated by spaces. The automated check finds the line by algorithm name and reads the second field from it;
the first load of a page counts as a fault; there can be one or more frames.

fifo     9  3
lru     10  2
clock   10  2
optimal  7  5

What you don’t need to do. You don’t need to simulate a page table, TLB, or address translation: the input is already page numbers. The simulator’s speed isn’t measured, so an array of frames and a linear search are perfectly fine.

Constraints. The check runs pagesim as an executable and reads only the output, so the implementation language doesn’t matter to it; it gets 20 seconds to run.

What to write in the report:

the number of faults for FIFO, LRU, and optimal on the trace 1 2 3 4 1 2 5 1 2 3 4 5 with three and with four frames;
how much work per access exact LRU requires in your implementation and why hardware doesn’t do it that way;
a “number of frames → faults” graph for the four algorithms on a real trace, and the knee you consider the working set size;
the same algorithms on a random trace and an explanation of the difference.

Done when:

./check.sh ./pagesim passes all thirteen checks, including reproducing Belady’s anomaly on FIFO and its absence on LRU;
the graph is built on a trace from a real program;
the report covers the four points above.

Before you start

Read the sections “Page replacement” (including the Aside on Belady’s anomaly) and “Working set and thrashing” in module 12, and the section “Page table entry” in module 11, which describes the reference bit used by the clock algorithm.
Unpack the course archive: the check is in labs/a5-page-replacement/check.sh, and it creates the traces itself.
For a real trace you need valgrind with the lackey tool; the Vagrant machine already has it, as does any system after setup/provision.sh. Any Linux will do, including a container and WSL2.

Stages

FIFO and optimal.

Optimal requires knowing the future, so in a simulator it’s easy to implement: the whole trace is already in front of you. It serves as the lower bound that everything else is compared against.
LRU.

You can implement exact LRU here, because you’re a simulator, not hardware. Pay attention to how much work it requires on every access, and why real systems don’t do it.
The clock algorithm.

A ring of pages, a reference bit, a hand. Compare its result with exact LRU: the difference should be small. That closeness is what justifies replacing LRU with an approximation.
Belady’s anomaly.

Find a trace on which FIFO with four frames gives more faults than with three. The classic one: 1 2 3 4 1 2 5 1 2 3 4 5.

Check that LRU and optimal show no anomaly: this is the practical difference between stack algorithms and non-stack ones.
Working set.

Plot a “number of frames → faults” graph for each algorithm. On a real trace there will be a noticeable knee: past a certain point, adding memory gives almost nothing. That point corresponds to the working set size.
A real trace.

Generate a trace from a real program, not a random one. The easiest way is to run valgrind --tool=lackey --trace-mem=yes and take the high bits of the addresses. Compare the results with a random trace: the difference shows how much everything relies on locality (module 2).

Automated check

The check is in the archive with the course files, and the commands below are run from the unpacked directory.

cd labs/a5-page-replacement
./check.sh ./pagesim

The check runs traces with known answers, including the classic Belady sequence, and separately verifies that the anomaly does not reproduce on LRU.

Common mistakes

The first load isn’t counted as a fault. It is, because cold misses are faults too, and without them your numbers won’t match any textbook.

Clock doesn’t clear the bit. Then it degenerates into FIFO. The hand must clear the bit on the pages it passes over.

Optimal looks at the entire future. It’s enough to find the nearest next access for each page currently in the frames.

The anomaly “doesn’t reproduce”. Check whether you really have FIFO or whether you accidentally implemented LRU. If accessing an already loaded page moves it to the end of the queue, that’s no longer FIFO.

Further, if you’re curious

Add second chance with two bits (referenced + modified), as in Linux, and see how much closer it gets to optimal than the plain clock algorithm.