Hierarchical Multilevel Paging & Translation

Tanenbaum Section 3.3.4 (Fig. 3-13): Visualizing bit-slicing bitwise math, Level-1 directory tables, and physical DRAM walkthroughs.

1. The Problem: The Linear Page Table Memory Explosion

As explored in previous lessons, a single-level linear page table requires an entry for every virtual page in a process's address space. On a 32-bit architecture with 4 KB pages (212 = 4,096 bytes), a process has 232 / 212 = 220 (1,048,576) virtual pages.

If each Page Table Entry (PTE) is 4 bytes, a single process must allocate a 4 MB contiguous block of RAM solely to store its page table. In a multiprogrammed system running 64 active processes, over 256 MB of physical RAM is consumed strictly by bookkeeping page tables—even if most of those virtual addresses are never touched! On 64-bit architectures, a linear table would require petabytes of RAM, making it physically impossible.

Figure 1: The Memory Waste of a Single-Level Linear Page Table (4 MB Continuous Block) Code (Active) Unused Address Gap (Wasted RAM) Heap Stack (Active) Result: The OS must allocate 4 MB in RAM for the entire table, even for huge unused gaps!

2. The Solution: Hierarchical Multilevel Paging

To avoid allocating memory for unused virtual address ranges, operating systems adopt Hierarchical Multilevel Paging (such as two-level paging in 32-bit systems or four-level paging in x86_64).

Instead of keeping the entire million-entry page table in memory, the page table itself is broken up into page-sized pieces (e.g., 1,024 entries per table). A Top-Level Page Directory is introduced, where each entry points to a second-level page table.

Sparse Allocation Benefit:
If a large chunk of virtual memory (e.g., between the heap and the stack) is completely unallocated, the corresponding top-level directory entry is marked NULL. Consequently, the entire 4 MB second-level page table for that region does not need to exist in physical memory at all!
Figure 2: Tanenbaum Fig. 3-13 — Two-Level Paging Architecture (PT1 → PT2 → Offset) Virtual Address PT1 [31:22] | PT2 [21:12] Offset [11:0] Top-Level Directory [0] NULL [1] → PT2 Table [2..1023] NULL Second-Level Table [0..2] Invalid [3] → PFN 65 [4..1023] Unused Physical Frame PFN 65 (0x00041000)

3. Address Slicing Mechanics

A 32-bit virtual address is split into three distinct fields:

  • PT1 (Top 10 bits, bits 31–22): Indexes into the Top-Level Page Directory (1,024 possible entries).
  • PT2 (Middle 10 bits, bits 21–12): Indexes into the chosen Second-Level Page Table (1,024 entries per table).
  • Offset (Lowest 12 bits, bits 11–0): Locates the exact byte within the 4 KB physical frame (4,096 bytes).
Figure 11-30: Virtual to physical address translation with a 4-level page table scheme implementing 48-bits of virtual address. 64-bit Virtual Address Canonical Bits PXE Index PPE Index PDE Index PTE Index Byte Offset 63 48 39 30 21 12 0 9 bits 9 bits 9 bits 9 bits 12 bits CPU Register PXE Page Map Level 4 PPE Page Directory Pointers PDE Page Directory PTE Page Table RAM Page Byte
Part 2: Guided Walkthrough & Graphical Bit Manipulation Step 1 of 4
Live 32-Bit Binary Slicing & Shifting Visualizer PT1 [31:22] (10 bits) 0000000001 PT2 [21:12] (10 bits) 0000000011 Offset [11:0] (12 bits) 000000000100 Hardware Action: 1. Inspecting Virtual Address 0x00403004
Level-1 Directory (Populated)Entries [0..4]
Level-2 Page Table (Populated)Entries [0..5]
Physical DRAMTarget Frame
Part 3: Interactive Translation Sandbox (Fully Clickable Tables) Click any row to test valid vs NULL mappings!
32-Bit Virtual Address Breakdown
PT1 (Bits 31-22) 0000000001 (1)
PT2 (Bits 21-12) 0000000011 (3)
Offset (Bits 11-0) 000000000100 (4)
Top-Level Directory Index [0..4] (Clickable)
PT2 Table (Clickable) Index [0..5]
Hardware MMU Physical Bus
Virtual Addr: 0x00403004
Decoded: PT1=1, PT2=3, Offset=4
Page Frame Number (PFN): PFN 65
Physical Frame Base: 0x00041000
Physical Address (+Offset): 0x00041004

Notice how top-level entries without active mappings hold NULL, meaning the entire 4 MB second-level table does not need to exist in memory.