Page replacement: FIFO, LRU and Optimal

Step 3 of a page fault says "find a free frame".

The Nova-14 has been running for six hours. Every frame is occupied. There is no free one.

So a page has to be evicted. Somebody's page goes back to swap space to make room.

Choose badly, and the page you evicted is the very next one somebody asks for. You have just created another 100 µs fault to fix the last one.

Why & what

Every algorithm below is measured on the same reference string — the sequence of page numbers a process touches:

1 2 3 4 1 2 5 1 2 3 4 5

with 3 frames available.

FIFO — first in, first out. Evict whichever page has been in memory longest. Keep a queue; the front of it is the victim.

Result: 9 faults.

It is trivial to implement and it ignores everything useful. A page loaded at startup and used constantly ever since is still the oldest, so FIFO throws it out.

LRU — least recently used. Evict the page that has gone unused for the longest time. The reasoning is locality from Topic 6.4: a page untouched for a while is probably not needed soon. Result: 10 faults on this string.

Yes — worse than FIFO here. That is honest and worth knowing. On short reference strings the result depends heavily on the exact sequence; across real workloads LRU beats FIFO consistently. One example does not settle an algorithm.

LRU's real problem is cost. Doing it exactly means updating a timestamp or reordering a list on every single memory access, which hardware will not do. Real systems approximate it, most often with a reference bit that the hardware sets on use and the OS periodically clears.

Optimal — evict the page needed furthest in the future. Result: 7 faults.

It is not implementable, because it requires knowing the future. Notice the parallel with SJF in Topic 3.2 — the same shape of impossibility, the same role. Optimal exists as a benchmark: 7 is the best anyone could ever do here, so LRU's 10 can be judged against a real target.

Belady's anomaly. Here is the result nobody expects. Run the same string through FIFO with 4frames instead of 3:

• FIFO, 3 frames: 9 faults
• FIFO, 4 frames: 10 faults

More memory produced more faults. This is Belady's anomaly, and it is why FIFO is not merely mediocre but genuinely unsound.

LRU and Optimal cannot do this. They belong to a family called stack algorithms, where the pages held with n frames are always a subset of those held with n+1 frames. That property makes the anomaly impossible.

How it works

Simulating a replacement algorithm by hand — this is what you will be asked to do:

1. Draw a column for each reference and a row for each frame.
2. For each reference, check whether the page is already present. If yes, it is a hit; copy the column across unchanged.
3. If not, it is a fault. If a frame is empty, use it.
4. If all frames are full, apply the rule to pick a victim: oldest arrival for FIFO, longest unused for LRU, furthest next use for Optimal.
5. Mark the fault and continue. At the end, count the faults — nothing else is being scored.

Common confusion

"LRU always beats FIFO." Not on every string, as our own numbers show. It wins on average across real workloads, which is a different claim. If an exam string makes LRU look worse, your arithmetic is probably right.

"Optimal is what a good OS uses." No OS can use it. It needs the future reference string. It is a measuring stick, in exactly the way SJF is for scheduling.

"Belady's anomaly means more RAM can slow your computer down." In practice, no. The anomaly is a property of FIFO on particular reference strings. Real systems use LRU approximations, which are stack algorithms and cannot exhibit it. Know it as a fact about FIFO, not as advice about buying RAM.

"LRU is easy — just keep timestamps." Keeping them is easy. Keeping them on every memory access is not. That is hundreds of millions of updates per second, which is why hardware provides only a single reference bit and software approximates from there.

Interview angle

"Simulate FIFO and LRU on this string." Guaranteed to appear. Draw the table, work left to right, count the F's. Being able to do it cleanly and quickly is worth more than any explanation. "What is Belady's anomaly?" More frames producing more faults, which FIFO can exhibit and LRU and Optimal cannot. If you can add the reason — stack algorithms guarantee the smaller frame set is a subset of the larger — that is a strong answer.

"Why is LRU not implemented exactly?" Because it would need bookkeeping on every memory reference. Then name the approximation: a hardware reference bit that the OS samples and clears, which is enough to distinguish recently used pages from cold ones.