Calculating the size of a single-level page table

Page size fixes the number of offset bits.

Worked answer.

Address split

• Page size = 4 KB = 4096 = 2^12 bytes → 12 offset bits.
• Virtual page number (VPN) bits = 32 − 12 = 20 bits.

Page table size

• Number of entries = 2^20 = 1,048,576.
• Size = 2^20 × 4 bytes = 2^22 bytes = 4 MB per process.

Why this hurts

• Every process needs its own table, so 100 processes would need about 400 MB just for page tables.
• Most of a process's address space is unused (a gap between heap and stack), yet a flat table must hold an entry for every page.
• With 64-bit systems the flat approach is impossible: even x86-64's 48-bit virtual addresses with 4 KB pages give 2^36 entries; at 8 bytes each that is 2^39 bytes = 512 GB per process.

Solution: multi-level (hierarchical) paging

• Split the 20-bit VPN into, say, 10 + 10 bits. The outer table has 2^10 = 1024 entries × 4 bytes = 4 KB, exactly one page.
• Each outer entry points to an inner page table (also 4 KB) covering 4 MB of virtual space (1024 pages × 4 KB).
• Inner tables are allocated only for regions actually in use, so a small process might need the outer table plus a few inner tables — tens of KB instead of 4 MB.
• x86-64 uses four levels (9 + 9 + 9 + 9 bits of index + 12 bits of offset = 48 bits); newer CPUs can add a fifth level.

Other approaches include inverted page tables (one entry per physical frame) and hashed page tables.

Follow-up: "Doesn't multi-level paging make each memory access slower?" Yes — a TLB miss now needs several memory reads to walk the table. The TLB, which caches recent translations and typically has a very high hit rate, is what keeps this affordable.