Translate an address through pages and a TLB

Prerequisites: Virtual addresses, physical memory, and permissions.

Learning objectives

• Split a virtual address into page number and offset.
• Explain a TLB miss versus a page fault.
• Calculate a simplified translation-time estimate.

Translation preserves the page offset

Paging divides a virtual address space into fixed-size pages and physical memory into frames of the same size. A page-table entry maps a virtual page to a physical frame and carries status or permission information. Within a mapped page, the offset remains unchanged.

With 4096-byte pages, the low twelve address bits form the offset. Virtual address 0x5234 has virtual page number 5 and offset 0x234. If page 5 maps to physical frame 0xA, the physical address is 0xA234. The numerical similarity of parts is a consequence of page alignment, not a general identity between virtual and physical addresses.

page_size = 4096
virtual_address = 0x5234
vpn, offset = divmod(virtual_address, page_size)
physical_address = 0xA * page_size + offset
assert (vpn, offset, physical_address) == (5, 0x234, 0xA234)

Cache the translation itself

A translation lookaside buffer, or TLB, caches recent translations and associated access information. On a hit, the processor can obtain the physical frame without a full page-table walk. A TLB miss means the translation is absent from this cache. It does not imply that the data page is absent from RAM.

If the page tables contain a valid permitted mapping, a hardware or software mechanism can obtain it and refill the TLB. A page fault occurs when translation or access checks require operating-system handling, such as an absent page or a protection violation. Some faults allocate a fresh zero-filled page or establish copy-on-write storage; others reject the access. A disk transfer is only one possible outcome.

Quantify a stated model

Suppose a TLB lookup takes one nanosecond, a data access takes fifty, and a miss adds one fifty-nanosecond page-table access. Assume serial accesses, a single-level table, no caches, and no faults. A hit costs 51 ns and a miss 101 ns. At a 98% hit rate, the average is 0.98×51+0.02×101=52 ns. Real designs often overlap work and use multilevel walks with caches, so this is a model to reason with, not a universal latency formula.

Translation caches also create consistency obligations. If the operating system changes a mapping or permission, processors must not keep using an obsolete cached translation indefinitely. Context identifiers can distinguish address spaces, and invalidation mechanisms remove stale entries when required. The page size affects both internal fragmentation and TLB coverage. Larger pages cover more memory per cached translation, but are not a free improvement for every allocation pattern.

Primary reading

• Paging: Introduction (Arpaci-Dusseau and Arpaci-Dusseau, OSTEP).

Practice problem

Use 4096-byte pages. Translate virtual address 0x7ABC if virtual page 7 maps to physical frame 0x12. Then consider a TLB miss where the page-table entry is valid and readable. Explain why this need not be a page fault or disk access. Finally, compute TLB coverage for 64 entries when each maps one ordinary page.

Worked solution

The virtual page is seven and the offset is 0xABC. Replacing the page number with frame 0x12 gives physical address 0x12ABC. A TLB miss merely says that the fast translation cache lacks this mapping. A page-table walk can find the existing valid readable entry in memory and refill the TLB, after which the data access proceeds. No missing data page or storage transfer is implied. Sixty-four entries times 4096 bytes gives 262144 bytes, or 256 KiB, of page coverage if all entries represent distinct ordinary pages. That is a coverage bound under the stated organization, not a guarantee that an arbitrary 256 KiB access pattern has no TLB conflicts or replacement misses.

Check your understanding

Which part of an address remains unchanged under ordinary page translation?

• The entire virtual page number.
• The offset within the page.
• Every permission bit.
• The process identifier.

Explanation

Translation replaces the virtual page with a physical frame while retaining the within-page offset.

A TLB miss necessarily means what?

• A disk read is required.
• The cached translation was not found.
• The process must terminate.
• The page is writable.

Explanation

The page tables and permission checks determine what happens next.

Primary reading

• Paging: Introduction: Arpaci-Dusseau and Arpaci-Dusseau, OSTEP

Open the study and save your work →