Cache experiments and accounting

What this concept is

The lab uses a fully associative LRU translation cache with least-to-most-recent ordering. Only successful accesses update recency. Evicting a translation changes future lookup cost; it does not remove the resident page mapping.

Why it matters here

A reported hit rate is meaningful only alongside the reference sequence, initial state, capacity, admission and replacement rules. Counts alone are not latency measurements. A cache that mistakenly behaves like FIFO can pass many short examples.

Concrete example

With capacity 2 and empty state, resident pages 1,2,1,3,1 yield miss,miss,hit,miss,hit. Cache orders are [1], [1,2], [2,1], [1,3], [3,1]. If hits do not refresh recency, insertion of 3 evicts 1 and the last access misses: a discriminating FIFO-versus-LRU trace.

Common confusion / misconception

TLB replacement and physical-page replacement manage different objects. Exact LRU here is a teaching choice, not a hardware guarantee or a claim that kernels never approximate LRU. No disk, cache-line, huge-page or multilevel-walk latency can be inferred from these counts alone.

How to use it

Check accesses = hits + misses and = successful accesses + all fault outcomes. In this simplified model, walks equal misses. Compare capacities 1,2,3 on the same trace from empty state. Keep fault counts separate and avoid converting counts to nanoseconds without a declared cost model.

Check yourself

Does an unpermitted cache hit refresh recency? Not under this lab contract. Would a real processor necessarily implement that rule? No. Does a third page inserted into a two-entry TLB force a resident page to disk? No.

Mini drill or application

Write a list-based oracle independent of your cache data structure. Trace all five steps by hand, then compare capacities. Add repeated faults and prove they do not populate the cache. Give one example where high translation hit rate coexists with application slowness unrelated to translation.

Read this only if stuck

Use the memory abstraction in OSTEP chapter 13 and the selective TLB reading; return with a claim about a named object, not just “memory misses.”