Paging
Fixed-size pages and frames. The idea that makes virtual memory practical.
Level: intermediate
What is it?
Virtual address spaces are chopped into pages (often 4 KiB). Physical memory is chopped into frames of the same size. The page table records which page lives in which frame, or that it is not resident.
Why does it matter?
Paging gives isolation, sparse address spaces, sharing (map the same frame twice), and the ability to overcommit with disk. It is how every modern general-purpose OS presents memory.
Mental model
A library of equal-sized boxes. Your library card (virtual address) names a box and an offset. The catalog (page table) tells the clerk which shelf (frame) that box is on, or that it is in off-site storage (swap).
How it works
- Split the VA: VPN + offset. Walk the page table to a PFN, then PFN+offset.
- Multi-level tables keep the catalog sparse. x86-64 is four (or five) levels.
- TLB caches recent translations. A miss walks the table; a fault may trap to the OS.
- A page fault is not always an error: demand paging, copy-on-write, and growth of the stack/heap use it.
Real-world usage
- Every user process
- mmap of files
- Shared libraries mapped once, used many times
Common mistakes
- Mixing page size with frame size — they match
- Thinking swap is required for virtual memory (overcommit is optional; translation is not)
Interview questions
What happens on a TLB miss?
Hardware (or software, on some ISAs) walks the page table. If the PTE is invalid, the OS gets a page fault.
Why multi-level page tables?
A flat table for a 48-bit space would be huge. Levels let unused regions take no RAM.