Page Fault

A TLB hit costs 1, a page table read costs 10, and a fault costs 100,000. Nothing was timed to get those. What they are meant to carry is the SHAPE: a fault is not somewhat slower than a hit, it is four to six orders of magnitude slower, because it involves a mechanical device. The Atlas drum had an average access of about 6 milliseconds against a core cycle of 2 microseconds, which is a factor of roughly three thousand; a modern disk against a modern cache is worse. Rounding that to 100,000 keeps the shape and admits the number is chosen.

When the frames are full this evicts the resident page with the lowest number. That is not least-recently-used, not clock, and not working set. Choosing a victim well is a whole subject — Denning's working set paper is in the sources and is about exactly this — and implementing a policy whose reasoning is never shown on screen would be worse than admitting to a simple one. The eviction column says which page went, so you can see it is arbitrary.

This machine fills the TLB from the page table and never writes it separately, so the two are always consistent. Real hardware has exactly the opposite problem: change a page table entry and the TLB still holds the old translation until something invalidates it. That is what a TLB shootdown is, it is expensive, and getting it wrong is a genuine class of operating system bug. None of that is modelled here.

One flat table of 256 entries is shown because it fits on a screen. A 64-bit machine cannot have a flat table — it would be larger than memory — so the page number is itself split into four or five pieces indexing a tree of tables, and a TLB miss then costs four or five memory reads rather than one. The mechanism is the same at every level, which is why it is drawn once.