Page tables and address translation

Take a byte-addressed machine with a power-of-two page size. The low address bits identify a byte within the page; the remaining bits identify a virtual page. A page-table entry can associate that virtual page with a physical frame. For an ordinary mapping, translation preserves the offset and replaces the page number. Two virtual pages may refer to one physical frame, so virtual address inequality does not prove that the underlying storage differs. Conversely, identical virtual pointers in different processes can refer to entirely different frames.

Permissions belong to the translation contract as well as the frame number. A present page may permit reads and forbid writes or instruction fetches. The processor checks the effective permissions for the requested operation, including relevant higher-level restrictions and privilege rules. A program therefore cannot establish that an access will succeed merely by observing that physical RAM exists. Use the architecture manual when investigating permission interactions; examples with one simple read-write flag are explanatory reductions, not complete hardware formats.

A flat array needs an entry for every possible virtual page even if the process uses a tiny part of its address space. A hierarchy instead divides page-number bits into indices. An upper entry points to the next table or, on supported architectures and levels, directly maps a large page. Entire absent subtrees can represent large holes. Linux provides architecture-neutral names for multiple levels, but an architecture may fold unused levels. Never infer the actual hardware walk depth from the number of names visible in generic kernel source.

For a teaching calculation, assume base pages of 4 KiB and eight-byte leaf entries. One 4 KiB leaf-table page holds 512 entries, covering 2 MiB of fully mapped virtual space. Mapping a contiguous, base-page-aligned 1 GiB range needs 262,144 leaf entries, containing 2 MiB of entry data. Allocated table pages can also contain unused entries at the range boundaries. This is not the cost of every 1 GiB reservation: untouched holes, huge mappings, alignment, and the tables already present all change allocation. Count installed mappings and allocated table pages rather than multiplying a process virtual-size metric blindly.

A translation lookaside buffer caches recent translations. On hardware with a hardware page walker, a TLB miss can be satisfied by walking valid page tables without a software page-fault exception. A fault instead indicates an access condition requiring the fault path, such as an absent mapping or disallowed write; some faults are recoverable. Translation invalidation also matters when the kernel changes mappings. A stale cached translation cannot simply be left in use because the memory containing its old table entry was updated.

Use the probability lab as a deliberately restricted cache-hit calculation. Set success probability to 0.8 and trials to 20; the displayed mean predicts sixteen hits in an independent equal-probability model. The four expected misses say nothing about whether pages are resident. Change the probability to 0.5 and predict ten hits before inspecting the readout. Real TLB behavior depends on reference order, page sizes, associativity, and invalidations, so the binomial bars neither model a page walk nor establish a fault rate.