Paging

What is it: Memory management technique that divides both virtual address space and physical memory into fixed-size chunks called pages (typically 4KB). The OS maintains a page table mapping virtual pages to physical frames.

Why: Without paging, memory allocation requires contiguous physical blocks. External fragmentation builds up: many small free gaps, no single contiguous block large enough for a new allocation. Paging allows a process to use non-contiguous physical pages while seeing a contiguous virtual address space. The OS assigns any available physical frame to any virtual page.

graph LR va["Virtual address"] --> tlb{"In TLB?"} tlb -->|"hit (~1ns)"| pa["Physical address"] tlb -->|"miss"| pt["Walk page table (~10 extra accesses)"] pt --> tlb2["Cache in TLB"] tlb2 --> pa

Page table: Each entry (PTE) maps a virtual page number to a physical frame number plus flags (present, writable, user-accessible, dirty, accessed). On every memory access, the MMU looks up the PTE. The TLB caches recent PTEs to avoid the lookup overhead.

What happens when RAM is full: If a new page is needed and physical RAM is exhausted, the OS invokes a page replacement algorithm to evict a victim page. If the victim is dirty (modified), it is written to swap (disk) first. The needed page is loaded from disk (or initialized to zero). The faulting process resumes.

Swap access cost: ~10ms (HDD) or ~0.1ms (SSD) vs ~100ns (RAM). A single page fault adds orders-of-magnitude latency to the faulting operation.

Thrashing: When the working sets of all running processes together exceed physical RAM, the system spends nearly all its time swapping pages in and out. CPU utilization drops close to zero (all processes are blocked waiting for page faults). The OS detects thrashing via high page fault rate and may kill the lowest-priority processes (OOM killer) to relieve memory pressure.

Page replacement algorithms:

FIFO (First In First Out): evict the page that has been in memory the longest. Simple, but evicts heavily-used pages if they are old.

LRU (Least Recently Used): evict the page that was accessed least recently. Optimal in theory (approximates temporal locality), but tracking exact LRU requires updating a data structure on every memory access — too expensive. Approximation: use the "accessed" bit in the PTE. The clock algorithm sweeps pages; if the accessed bit is set, clear it and move on (give it a second chance); if clear, evict it.

Fragmentation in paging: Internal fragmentation: a process needs 4097 bytes but gets two 4KB pages (8192 bytes) — wastes 4095 bytes. External fragmentation is eliminated: any free frame can satisfy any page request. This is the key advantage over contiguous allocation.

Trade-offs: paging adds MMU overhead (mitigated by TLB), wastes some RAM due to internal fragmentation, and requires page tables in RAM (large address spaces need large page tables — mitigated by multi-level page tables and TLB). Huge pages (2MB, 1GB) reduce TLB pressure for memory-hungry processes like databases and JVM heaps.

Real-world usage: Redis is configured with vm.overcommit_memory=1 on Linux to allow fork() to succeed even when apparent memory usage is near RAM capacity (CoW means the child won't actually use as much memory as it appears).

Common pitfall

Diagnosing "high memory usage" without distinguishing page-table overhead from actual data is a common confusion at scale — a process with a huge, sparse virtual address space (many mmap regions, each needing page table entries even for untouched pages) can show significant memory management overhead that has nothing to do with how much real data it's holding. Conflating "process is thrashing" with "process legitimately needs more RAM" leads to the wrong fix (adding RAM) when the real issue might be too many small mappings needing consolidation, or vice versa — checking actual page fault rate (vmstat, /proc/vmstat) distinguishes the two, size and usage metrics alone don't.