Writing an OS Kernel from Scratch | Virtual Memory — The Complete Journey of Paging and Linear Addresses
You write int *p = (int*)0x00401000; *p = 42; — is this address a real physical address? How does the operating system ensure every process feels it has 4GB of memory when there’s actually only 8GB of physical memory?
The answer is paging.
Paging is the core mechanism of modern operating system virtual memory management: the CPU translates linear addresses (the addresses seen by programs) into physical addresses (the addresses actually accessed by hardware) through page tables, and the operating system is responsible for building and maintaining this mapping table, using page replacement algorithms to allow limited memory to serve an unlimited number of processes.
Today, we’ll walk through this translation process completely.
1. Why Paging Is Needed: Continuous vs Discrete
If we don’t use paging, what other ways are there to manage memory?
Segmentation: Each program gets a contiguous space, using a base register + limit register. The problem is external fragmentation — every program needs contiguous physical memory; large programs struggle to find space, while small programs waste space.
Paging: Split both physical memory and virtual memory into fixed-size blocks (pages). The program’s virtual address space is also split into same-sized pages. Discrete mapping solves external fragmentation, greatly improving memory utilization.
Segmentation vs Paging:
Segmentation: Each process gets a contiguous space
Process A: [Physical 0-100K] Process B: [Physical 200-300K] Process C: [Physical 150-200K]
→ Large programs can't fit in
Paging: Fixed 4KB blocks, mapped to any physical page
Process A Virtual Page 0 → Physical Page 5 Process A Virtual Page 1 → Physical Page 12
Process B Virtual Page 0 → Physical Page 7 Process B Virtual Page 1 → Physical Page 3
→ Physical pages can be arbitrarily arranged and combined, no external fragmentation2. x86 Paging Basics: Two-Level Page Tables
x86’s paging mechanism has gone through two generations: 32-bit two-level page tables (IA-32) and PAE four-level page tables (IA-32e), followed by x86_64’s four-level page tables (PML4).
2.1 32-bit Two-Level Page Tables (No PAE)
32-bit Linear Address Breakdown:
┌──────────┬──────────┬──────────┐
│ Dir(10) │ Table(10)│ Offset(12)│
└──────────┴──────────┴──────────┘
↑ ↑ ↑
CR3 points Page Dir 4KB page
to Page Entry (PDE) offset
Dir
Translation process:
CR3 (Page Directory Base) → Find Page Directory Entry (PDE) → Find Page Table (PTE) → Find Physical Page Frame → Add OffsetEach level indexes 10 bits, so the page directory and page table each have 1024 entries (4KB, exactly one page).
Page Directory Entry (PDE) Format (4 bytes):
┌─────────────────────────────────────────────────────────────────┐
│ Bit 31-12: Page Table Base (high 20 bits, 4KB aligned) │
│ Bit 9: Reserved (0) │
│ Bit 8: PCD (Page Cache Disable) │
│ Bit 7: PWT (Write-Through) │
│ Bit 6: Accessed │
│ Bit 5: Reserved (0) │
│ Bit 4: PS (Page Size) = 0 (indicates pointing to page │
│ table, not a large page) │
│ Bit 3: P (Present) = 1 means present │
│ Bit 2: R/W (Read/Write) │
│ Bit 1: U/S (User/Supervisor) │
│ Bit 0: P (Present) ... [truncated]
Comments