Paging: Address Translation Arithmetic

The Tripos arithmetic pattern

Paging questions on the Tripos typically follow a fixed pattern: given a virtual address size, page size, and PTE size, compute table sizes, entry counts, and address splits. The key formula is:

$\text{number of pages} = \frac{2^{\text{address bits}}}{2^{\text{page offset bits}}} = 2^{\text{address bits} - \text{page offset bits}}$

$\text{page table size} = \text{number of pages} \times \text{PTE size}$

Worked example: 32-bit system, 4 KB pages, 4-byte PTEs

• Page offset bits: $\log_2(4096) = 12$ bits.
• Page number bits: $32 - 12 = 20$ bits.
• Number of pages: $2^{20} = 1{,}048{,}576$.
• Page table size: $2^{20} \times 4 = 4$ MB per process.

Multi-level arithmetic

With 2-level paging, the page number is split into an outer page index and an inner page index. Suppose each inner page table fits in one 4 KB page and contains 4-byte PTEs:

• PTEs per inner table: $4096 \text{ bytes} \div 4 \text{ bytes/PTE} = 1024$ PTEs.
• Bits needed to index the inner table: $\log_2(1024) = 10$ bits.

If the logical address is 32 bits, with 12-bit offset:

• Inner index: 10 bits (inner PT has 1024 entries)
• Outer index: $32 - 12 - 10 = 10$ bits (outer PT also has 1024 entries)
• Total addressable pages: $2^{10} \times 2^{10} = 2^{20} = 1\text{M}$ pages — same as single-level, but the table is sparse.

The 5-level paging case (57-bit, 2025 paper)

The 2025 Tripos Q4 modelled a 64-bit machine with 57-bit virtual addressing, 4 KB pages, and 64-bit PTEs. This is the 5-level paging scheme proposed for Intel x86 (Ice Lake onwards).

• Page offset: $\log_2(4096) = 12$ bits.
• Remaining bits for page-table indices: $57 - 12 = 45$ bits.
• Each level indexes a 4 KB page of PTEs: $4096 \text{ bytes} \div 8 \text{ bytes/PTE} = 512$ PTEs.

Each level therefore uses $\log_2(512) = 9$ bits. Five levels: $5 \times 9 = 45$ bits — exactly matching the 45 bits above the offset.

Address decomposition

Given a 57-bit virtual address 0x00c0_ffee_ba5e_f00d:

Break into five 9-bit indices (from most significant) and a 12-bit offset:

$\underbrace{\text{bits } 56..48}_{\text{Level 5}} \mid \underbrace{47..39}_{\text{L4}} \mid \underbrace{38..30}_{\text{L3}} \mid \underbrace{29..21}_{\text{L2}} \mid \underbrace{20..12}_{\text{L1}} \mid \underbrace{11..0}_{\text{Offset}}$

Table sizes

Level	Entries	Size
Level 5 (outermost)	$512^1 = 512$	4 KB (1 page)
Level 4	$512^2 = 262{,}144$	2 MB
Level 3	$512^3 = 134{,}217{,}728$	1 GB
Level 2	$512^4 = 68{,}719{,}476{,}736$	512 GB
Level 1 (innermost)	$512^5 = 35{,}184{,}372{,}088{,}832$	256 TB

The total page-table size if fully populated is $256 \text{ TB}$. In practice, it is sparsely populated — only the parts of the address space actually used are backed by physical page-table pages. A process using 2 GB of memory would populate only a tiny fraction of the table.

Addressable memory

57-bit addressing gives $2^{57}$ bytes. Using SI units:

$2^{57} = 2^{7} \times 2^{50} = 128 \times 2^{50} = 128 \text{ PB}$

(pebibyte or petabyte — both accepted in the mark scheme).

The key insight

Each additional level of page table adds 9 bits of address space (on systems with 512 entries per page). The number of bits above the offset is always a multiple of the bits needed to index one level. Stripping a virtual address into these bit-fields and showing the walk through each level is the standard Tripos technique.

Summary

• Address decomposition: split the virtual address into page-number fields and offset.
• Each level of a multi-level page table is indexed by one field.
• Total page-table size is astronomical if fully populated but sparse in practice.
• Each inner table fits exactly into one page, making memory management for the page table itself consistent with paging of user data.

---

Past Paper Questions

2025 Paper 2 Question 4: 57-bit virtual addressing, 5-level page table, 64-bit PTEs, 4 KB pages. Compute addressable memory, walk a virtual address through the levels, compute table sizes, and analyse a TLB + EAT problem. [20 marks]

2021 Paper 2 Question 3(a): Paging arithmetic on a system with given page size and address width.