How Paging Works
Paging is the mechanism by which an operating system divides both virtual memory and physical memory into fixed-size blocks. Virtual memory blocks are called pages, and physical memory blocks are called frames. The standard page size on most systems is 4 KB (4096 bytes).
Virtual-to-Physical Mapping
Every memory access from a program uses a virtual address. The CPU's memory management unit (MMU) translates this into a physical address using a page table. A virtual address is split into two parts:
- Virtual Page Number (VPN): identifies which page the address falls in.
- Page Offset: identifies the byte within that page (for 4 KB pages, this is the low 12 bits).
The page table maps each VPN to a Physical Frame Number (PFN). The physical address is formed by concatenating the PFN with the offset.
Page Table Entries (PTEs)
Each entry in the page table contains more than just the frame number. Important bit fields include:
| Bit | Name | Purpose |
|---|---|---|
| P | Present | Is this page currently in physical memory? |
| R/W | Read/Write | Is writing allowed? |
| U/S | User/Supervisor | Can user-mode code access this page? |
| D | Dirty | Has this page been written to since loaded? |
| A | Accessed | Has this page been read or written recently? |
Multi-Level Page Tables
A flat page table for a 64-bit address space would be impossibly large. Instead, modern systems use multi-level page tables. A two-level page table splits the VPN into a page directory index and a page table index. The page directory points to second-level page tables, which point to frames. Pages that are never used need no second-level table allocated, saving enormous amounts of memory.
x86-64 uses a four-level page table (PML4 -> PDPT -> PD -> PT), each level indexed by 9 bits of the virtual address, with 12 bits for the offset, covering 48-bit virtual addresses (256 TB).
Page Faults
When the present bit is 0, accessing that page triggers a page fault -- a CPU exception. The OS page fault handler can then load the page from disk, update the page table, and restart the instruction.
Two-Level Page Table Walkthrough
Consider a 32-bit system with 4 KB pages and a two-level page table. A virtual address is 32 bits:
- Bits 31-22 (10 bits): Page Directory Index (1024 entries)
- Bits 21-12 (10 bits): Page Table Index (1024 entries)
- Bits 11-0 (12 bits): Page Offset
Example: Virtual address 0x00403004
- Binary:
0000 0000 0100 0000 0011 0000 0000 0100 - Page Directory Index = bits 31-22 =
0000000001= 1 - Page Table Index = bits 21-12 =
0000000011= 3 - Page Offset = bits 11-0 =
000000000100= 4
The MMU reads entry 1 in the page directory to find the base address of the second-level page table, then reads entry 3 in that table to find frame number (say, 0x8F). The physical address is 0x8F004 (frame 0x8F, offset 4).
Why multi-level saves memory: if a process only uses a tiny portion of its address space, most page directory entries are marked "not present" and no second-level tables need to exist for those regions.