Paging: Worked Examples

Worked example 1: single-level paging (32-bit)

A system has 32-bit logical addresses, 4 KB pages, and 4-byte PTEs. A process uses only addresses 0x0000_0000–0x0040_0000 (the first 4 MB of its address space). Compute the page-table size with single-level and two-level paging.

Single-level:

• Page size: $2^{12}$ = 4096 bytes.
• Number of pages: $2^{32} / 2^{12} = 2^{20} = 1{,}048{,}576$.
• Page table size: $2^{20} \times 4 = 4$ MB — larger than the process itself! The page table uses 4 MB even though the process only uses 4 MB of data.

Two-level (10/10/12 split):

• Inner page tables: each maps $2^{10} = 1024$ pages (4 KB each = 4 MB of address space).
• To cover 4 MB: need 1 inner page table (1024 pages × 4 KB = 4 MB).
• Outer page table: 1 entry pointing to the inner table.
• Outer-table size: $2^{10}$ entries = $2^{10} \times 4 = 4$ KB.
• Inner-table size: 4 KB.
• Total page-table size: 8 KB. Versus 4 MB for single-level. The saving is a factor of 512.

Worked example 2: EAT calculation (2023 Paper 2 Q3)

System with memory access time 80 ns, page-fault service time 8 ms (assuming a free frame is available). Target maximum EAT: 100 ns.

(i) Maximum page-fault rate:

$\text{EAT} = (1 - p) \times 80 + p \times 8{,}000{,}000 \le 100$ $80 + 7{,}999{,}920 \cdot p \le 100$ $p \le \frac{20}{7{,}999{,}920} = \frac{1}{399{,}996}$

So at most one page fault per 400,000 accesses — about 0.00025%.

(ii) Double the maximum fault rate:

$p = \frac{1}{199{,}998}$ $\text{EAT} = \left(1 - \frac{1}{199{,}998}\right) \times 80 + \frac{1}{199{,}998} \times 8{,}000{,}000$ $= \frac{199{,}997 \times 80 + 8{,}000{,}000}{199{,}998} = \frac{23{,}999{,}760}{199{,}998} \approx 120 \text{ ns}$

(iii) Half of page faults occur when no free frames are available:

When no free frame is available, a frame must be evicted and written back (dirty). The page-fault service time approximately doubles to $8 + 8 = 16$ ms (well — if half the faults need a swap-out, the effective service time is $0.5 \times 8 + 0.5 \times 16 = 12$ ms):

$\text{EAT} = \left(1 - \frac{1}{199{,}998}\right) \times 80 + \frac{1}{199{,}998} \times 12{,}000{,}000$ $= \frac{199{,}997 \times 80 + 12{,}000{,}000}{199{,}998} = \frac{27{,}999{,}760}{199{,}998} \approx 140 \text{ ns}$

Worked example 3: TLB + EAT (2025 Paper 2 Q4)

$T_\text{mem} = 40 \text{ ns}$, $T_\text{tlb} = 5 \text{ ns}$, $\alpha = 0.99$, 5-level page table ($k = 5$).

$\text{EAT} = 0.99 \times (5 + 40) + 0.01 \times (5 + 5 \times 40 + 40)$ $= 0.99 \times 45 + 0.01 \times 245$ $= 44.55 + 2.45 = 47.0 \text{ ns}$

The answer is 47 ns. Common mistakes: forgetting the TLB lookup time on a miss, or miscounting the number of memory accesses (remember: $k$ PTEs + the final data access = $k + 1$).

Key formulae to memorise

Quantity	Formula
Page offset bits	$\log_2(\text{page size})$
Page number bits	Address bits − offset bits
PTEs per page-table page	Page size ÷ PTE size
Single-level PT size	$2^{\text{page number bits}} \times \text{PTE size}$
EAT (paging only)	$(1 - p) \times T_\text{mem} + p \times T_\text{page-fault}$
EAT (TLB)	$\alpha(T_\text{tlb} + T_\text{mem}) + (1 - \alpha)(T_\text{tlb} + k \cdot T_\text{mem} + T_\text{mem})$

Summary

• Multi-level page tables reduce overhead from “all pages” to “actually used pages”.
• EAT calculations are mechanical: plug the numbers into the formula and be careful with units (ms vs ns).
• Always show your working — the mark scheme awards partial marks for correct steps even if the final arithmetic is wrong.