Memory Management: From Virtual Addresses to Hardware Paging
The goal of memory management is to provide each process with a large, private, and contiguous address space while efficiently sharing the limited physical RAM. This requires a sophisticated orchestration between the kernel and the Memory Management Unit (MMU) hardware.
This chapter explores the hierarchy of memory abstraction, from low-level allocation to modern demand paging and swapping.
1. The Virtual Memory Abstraction
Modern operating systems do not allow processes to access physical RAM directly. Instead, they provide Virtual Memory.
1.1 Why Virtual Memory?
- Isolation: Process A cannot even "name" Process B's memory.
- Over-commitment: The sum of virtual memory used by all processes can exceed physical RAM (via Swapping).
- Relocation: A process can be loaded anywhere in RAM without its internal pointers changing.
- Fragmentation Control: Small, non-contiguous physical chunks can be mapped into a large, contiguous virtual space.
1.2 The Address Translation Cycle
When the CPU executes MOV EAX, [0x12345], the 0x12345 is a Virtual Address.
- The CPU sends this address to the MMU.
- The MMU looks up the translation in its cache (TLB).
- If not found (TLB Miss), the MMU "walks" the Page Tables in RAM.
- The MMU finds the Physical Address (e.g.,
0x98765) and fetches the data.
2. Hardware Mechanisms: Paging and Segmentation
2.1 Paging (The Modern Standard)
Memory is divided into fixed-size units: Pages (Virtual) and Frames (Physical).
- Standard Size: Usually 4 KB.
- Offset: The last 12 bits of an address (for 4KB pages) remain unchanged during translation.
2.2 Multi-Level Page Tables (x86-64)
A single flat page table for a 64-bit address space would be petabytes in size. To save space, we use a hierarchical tree:
- PML4 (Page Map Level 4)
- PDPT (Page Directory Pointer Table)
- PD (Page Directory)
- PT (Page Table)
- Benefit: If a large range of virtual memory is unused, the kernel doesn't allocate the lower-level tables, saving massive amounts of RAM.
2.3 Segmentation (The Legacy Approach)
Dividing memory into logical units (Code, Data, Stack).
- Issue: Leads to External Fragmentation (gaps between segments that are too small to be useful).
- Status: Mostly obsolete on 64-bit systems, which use a "Flat Memory Model" where paging handles everything.
3. Kernel Memory Architecture
How does the kernel manage its own memory and track yours?
3.1 The mm_struct (Linux Kernel)
Every process has an mm_struct that defines its entire memory view:
pgd: Pointer to the top-level Page Global Directory.mmap: A linked list of Virtual Memory Areas (VMAs).mm_rb: A Red-Black tree of VMAs for fast searching.
3.2 Virtual Memory Areas (VMA)
A VMA is a contiguous range of virtual addresses with the same permissions (e.g., "The Heap," "The Stack," or a "Mapped Library").
- Fields:
start_addr,end_addr,permissions(Read/Write/Exec), andbacking_file.
4. Physical Memory Allocation
The kernel must manage physical frames with extreme speed.
4.1 The Buddy System (Large Allocations)
Physical RAM is split into blocks of sizes pages.
- Allocation: If you ask for 4 pages () and only an 8-page block is available, the kernel splits the 8 into two "buddies" of 4.
- Merging: When a block is freed, the kernel checks if its "buddy" is also free. If so, they merge back into a larger block.
- Result: Drastically reduces external fragmentation.
4.2 The SLAB/SLUB Allocator (Small Objects)
The Buddy System is too coarse for small objects like struct task_struct or struct inode.
- Slabs: Pre-allocated "caches" of specific object types.
- Benefit: No internal fragmentation; objects are reused, avoiding the overhead of frequent initialization.
5. Demand Paging and Swapping
A page is only loaded into physical RAM when it is actually needed.
5.1 The Page Fault Lifecycle
- Access: Process tries to read a virtual address.
- Exception: MMU finds the "Present Bit" is 0 in the Page Table and triggers a Page Fault.
- Kernel Intervention:
- Is the address valid? (Check VMAs).
- If valid, find a free Physical Frame.
- Read the data from Disk into the Frame.
- Resumption: Update the Page Table (set Present=1) and restart the CPU instruction.
5.2 Thrashing and the Working Set
- Thrashing: When the OS spends all its time swapping pages in/out rather than executing code.
- Working Set: The set of pages a process has actively used in the last seconds.
- Rule: If
Sum(Working Sets) > RAM, the system will thrash.
6. Advanced Performance Optimizations
6.1 HugePages (2MB / 1GB)
Standard 4KB pages are small for modern multi-GB databases.
- Problem: Small pages mean massive Page Tables and frequent TLB Misses.
- Solution: Use HugePages. A single TLB entry can now cover 2MB, significantly increasing performance for memory-intensive apps.
6.2 TLB Shootdown
In a multi-core system, if Core A updates a page table, Core B might still have the old translation in its local TLB.
- Shootdown: Core A sends an Inter-Processor Interrupt (IPI) to all other cores, forcing them to flush their TLBs. This is expensive and a major scaling bottleneck.
6.3 KSM (Kernel Same-page Merging)
The kernel scans RAM for identical pages (e.g., multiple VMs running the same OS) and merges them into a single page marked Copy-on-Write.
7. Memory Debugging and Monitoring
| Tool | Focus | Key Concept |
|---|---|---|
free -m | System-level | Total/Available RAM |
/proc/meminfo | Kernel-level | Detailed breakdown (Slabs, HugePages) |
valgrind | App-level | Detects leaks and use-after-free |
numastat | Hardware-level | Checks for NUMA (Non-Uniform Memory Access) imbalance |
pmap -x <pid> | Process-level | Shows memory segments of a specific process |
8. Summary Checklist
- Explain how a 4-level page table reduces memory usage.
- What is the role of the TLB, and why is it essential?
- Buddy System vs Slab Allocator: which manages pages and which manages objects?
- Trace a Page Fault from the hardware exception to the restart of the instruction.
- Why does "Thrashing" lead to low CPU utilization?
End of Chapter 04. Continue to Chapter 05: File Systems.