Paging and TLB Explained: Address Translation, EMAT and Exam Traps

Students often memorise offset bits = log2(page size) and one EMAT formula, then lose the answer as an address passes through the VPN, TLB, PTE and physical frame. Use one connected method: split the address, identify the path, preserve the offset and count accesses under the stated timing assumptions. Paging and TLB questions recur across the memory-management practice sets in CS Fundamentals. The earlier Virtual Memory in Operating Systems uses the same resident-page baseline to connect translation with demand paging, replacement and thrashing; this page isolates VPN/PFN translation, TLB reach and hit-versus-miss timing.

What paging changes in memory, and what it does not

Paging divides a process's virtual address space into fixed-size virtual pages and physical memory into equal-size frames. A page table maps the virtual page number, or VPN, to a physical frame number, or PFN. The displacement within that page is the offset, copied unchanged into the physical address.

This lets consecutive virtual pages occupy non-contiguous physical frames, avoiding external fragmentation. The last page can still contain internal fragmentation, and page tables consume memory of their own.

Keep the related ideas separate. Segmentation uses variable-sized logical regions. Demand paging decides when a page is brought into memory. Page replacement chooses a victim only when a required page is absent and a frame must be freed. Memory Management in OS: Paging and Segmentation owns paging versus segmentation and fragmentation; this calculation keeps fixed-size paging and a resident page.

Split a virtual address and read the page-table entry

For byte-addressable memory with a page size of 2^p bytes, the low p address bits form the offset. Every remaining virtual-address bit forms the VPN. With a 32-bit virtual address and 4 KiB pages, 4 KiB = 4096 bytes = 2^12 bytes. The split is therefore:

20-bit VPN | 12-bit offset

That gives 2^20 possible virtual pages. A page-table entry, or PTE, uses a valid or present bit to show whether its in-memory mapping is usable, and a PFN to identify the frame. Protection, referenced and dirty bits are common metadata, but their widths vary. A protection failure is not a page fault, and an absent PTE is not repaired by a TLB lookup.

For a single-level table with 2^20 entries of 4 bytes each:

2^20 x 4 = 2^22 bytes = 4 MiB

Multi-level paging can avoid allocating every lower-level table for sparse regions. It does not alter the 12-bit page offset.

What the TLB stores and how a hit differs from a miss

The translation lookaside buffer, or TLB, is a small associative cache of recent translations. Each entry conceptually holds VPN -> PFN plus status and protection information. The CPU still creates a virtual address. The TLB accelerates translation, but does not hold the requested data byte.

On a hit, the TLB supplies the PFN before the data access. On a miss, the page table is consulted. A valid PTE supplies the PFN, normally makes the translation eligible for TLB insertion, and is followed by the data access. An absent page raises a page fault.

A TLB miss is not a page fault. The miss says the translation was not found in the TLB. The page fault says the required page is not resident.

With 64 entries mapping one 4 KiB base page each, TLB reach is 64 x 4 KiB = 256 KiB. Context-switch handling may tag entries with process identifiers or invalidate affected translations. Implementations differ.

Worked example, Part A: translate one virtual address

Use this setup for both parts: byte-addressable memory, 32-bit virtual and physical addresses, 4 KiB pages, a single-level page table, 4-byte PTEs and a 64-entry TLB. The virtual byte address is 0x12345ABC. The TLB contains a valid, readable entry VPN 0x12345 -> PFN 0x02A7B, and the page table contains the same valid mapping. Reads are permitted, so no protection exception interrupts the reference. Both valid mappings are usable.

First split the address. A 4 KiB page has a 12-bit offset. One hexadecimal digit represents four bits, so the last three hexadecimal digits are the offset:

VA 0x12345ABC = [VPN 0x12345 | offset 0xABC]

Now look up VPN 0x12345. The TLB hits and supplies PFN 0x02A7B. Copy the offset without changing it and concatenate PFN on the left:

PA = [0x02A7B | 0xABC] = 0x02A7BABC

Check the result arithmetically. Shifting PFN 0x02A7B left by 12 bits gives the frame base 0x02A7B000. Then:

0x02A7B000 + 0x00000ABC = 0x02A7BABC

The offset remains 0xABC. Replacing it with zero produces only the frame base, not the requested byte address. The TLB hit avoids a page-table memory access, but it does not avoid the final data access. If the TLB entry were absent while the PTE stayed valid, the lookup path would be longer but the final physical address for this same byte would remain 0x02A7BABC.

Worked example, Part B: calculate EMAT without skipping an access

EMAT depends on the access model. Here TLB lookup is T = 10 ns, one memory access is M = 100 ns, and hit ratio is h = 0.95. Lookup is serial, the table has one level, and the PTE and data are resident. There is no cache, page fault, update cost or overlap.

Count each complete branch before taking the weighted average.

• Hit: TLB lookup plus one data-memory access, so T + M = 10 + 100 = 110 ns.

• Miss with a valid PTE: TLB lookup, one PTE access and one data access, so T + M + M = 10 + 100 + 100 = 210 ns.

Therefore:

EMAT = h(T+M) + (1-h)(T+2M)

= 0.95(110) + 0.05(210)

= 104.5 + 10.5 = 115 ns

Two checks confirm it. 115 ns lies between the 110 ns and 210 ns paths. Also, a miss adds one 100 ns PTE access, so a 5% miss rate adds 0.05 x 100 ns = 5 ns above 110 ns. Page Table Size and EMAT Numericals for GATE extends this branch accounting to multilevel table sizing and additional EMAT cases. Here one level stays fixed so each lookup is visible.

Paging and TLB traps that change the answer

Timing traps are omitting the hit's data access, counting one access on a valid-PTE miss, or reusing 115 ns with overlap or multiple levels. Omit page-fault time when pages are resident.

Diagnostics: the PA retains the 12-bit offset; EMAT lies between branch times; a valid-PTE miss changes latency, not the PFN. State assumptions first.

How exam-style questions combine the concepts

Exam-style practice may ask you to derive VPN and offset bits, count pages or PTEs, size a single-level page table, translate a supplied address, calculate TLB reach, distinguish a hit, valid-PTE miss and page fault, or calculate EMAT from given timings. A question can combine several steps while asking for one final value.

Use this six-step rough-work routine:

1. Convert every size to a power of two.

2. Split the virtual address.

3. Write the TLB result.

4. Consult the PTE only on a TLB miss.

5. Preserve the offset while forming the PA.

6. Draw the timing branches, count every access and weight the totals.

Write whether lookup is serial or parallel, and the number of page-table levels. Recompute one branch from raw timings before choosing a formula.

Paging and TLB in one minute: recap and next step

The VPN selects a translation, the PTE or TLB supplies the PFN, the offset survives unchanged, and EMAT weights complete access paths. Here, VPN 0x12345 and offset 0xABC produced PA 0x02A7BABC; the page table was 4 MiB, TLB reach was 256 KiB, and EMAT was 115 ns.

Now delete the TLB entry but keep the PTE valid. Explain why the PA stays fixed while this reference rises from 110 ns to 210 ns. For structured study beyond this example, continue with Zero to Hero: Complete CS Course.