Virtual Memory

How does a system keep 50 Chrome tabs, Photoshop, and an IDE open simultaneously with only 16 GB of RAM? Virtual memory is the abstraction that turns limited physical memory into the illusion of limitless space. Each program receives an isolated address space covering the entire machine - all transparently managed by the OS.

• **Why does Chrome use so much memory?** Each tab is a separate process with a virtual address space of tens of gigabytes. But physically, only ~2-3 GB is used thanks to paging and shared memory. Paging allows Chrome to sacrifice memory for security (tab isolation).
• **How does swap work on SSD?** macOS aggressively uses swap even with 32 GB of RAM. Why? By evicting rarely used pages (e.g., application initialization code), the OS frees up RAM for active data and file cache. Result: applications launch faster.
• **Meltdown and Spectre: virtual memory vulnerabilities.** The 2018 attacks exploited speculative execution to read kernel memory via a TLB side-channel. The KPTI patch caused a performance drop of 5-30% due to TLB flush on every syscall. Security vs speed.

Цели урока

• Explain paging: fixed 4K page size, virtual-to-physical mapping via page tables
• Understand multi-level page tables (x86-64: 4 levels, 48-bit virtual address)
• Know the TLB: hardware translation cache, ~99% hit rate, miss costs tens of ns
• Compare page replacement: FIFO, LRU, Clock, Linux active/inactive lists
• Distinguish demand paging, copy-on-write, mmap and when each applies

Paging: page-based memory organization

**Virtual Memory** lets every program treat memory as if it owned the whole machine - addresses 0 to 2⁴⁸ - while RAM may be only a few GB. The mechanism that pulls this off is **paging**: memory in fixed-size chunks, translated on the fly by the MMU.

**How does paging work?** Memory is divided into fixed-size **pages** (usually 4 KB). A program's virtual address is split into two parts: 1. **Page number** 2. **Offset within the page** The OS translates the virtual address to a physical one via a **page table**.

**Why exactly 4 KB pages?** - Too small (512 bytes) → huge page table, lots of overhead - Too large (1 MB) → internal fragmentation (program needs 5 KB, 1 MB allocated) - 4 KB is a balance between overhead and fragmentation New CPUs support **huge pages** (2 MB, 1 GB) for databases and HPC.

**Key advantage of paging:** programs can use more memory than physically installed RAM. Inactive pages are offloaded to disk (**swapping**). The program doesn't notice - the OS transparently loads them upon access.

**Protection through paging.** Each entry in the page table has **protection bits**: Read/Write/Execute. Attempting to write to a read-only page → **segmentation fault**. The OS isolates processes: process A cannot access the memory of process B - their page tables do not overlap.

Page Tables: structure and multilevel tables

**Page Table** is a data structure that stores the mapping of virtual pages to physical frames. Sounds simple, but the implementation is full of tricks. A naive single-level table would be gigantic!

**Solution: multilevel (hierarchical) page tables.** Instead of one huge table - a tree of tables. x86-64 uses a **4-level structure**: PML4 → PDPT → PD → PT. If virtual pages are not used, the corresponding tables are not even allocated!

**Each entry in the page table (PTE - Page Table Entry)** contains not only the address of the physical frame but also metadata:

**Bits in Page Table Entry (x86-64):** - **Present (P):** Page in RAM or on disk (swap) - **Read/Write (R/W):** Writable or not - **User/Supervisor (U/S):** Accessible to userspace programs - **Accessed (A):** Has the page been read (for page replacement) - **Dirty (D):** Has the page been modified (needs saving on swap) - **Execute Disable (XD/NX):** Protection against code execution in data (against exploits)

**Copy-on-Write (COW)** - a clever optimization. During `fork()`, Linux does not copy all the parent's memory - both page tables simply point to the same physical frames, but with the `R/W = 0` bit. On a write attempt → page fault → OS makes a real copy of the page.

**Inverted page table** (inverted PT) - an alternative approach. Instead of a table for each virtual address - a table for each physical frame. Size is proportional to physical RAM, not virtual space. Used in some architectures (PowerPC, IA-64), but lookup is slower - requires a hash table.

Translation Lookaside Buffer (TLB)

**Problem:** with a 4-level page table, each memory access requires 4 additional RAM accesses (one per level for each table). This is catastrophically slow! The solution is the **TLB (Translation Lookaside Buffer)** - a hardware cache for page table entries.

**TLB is a fully associative cache** inside the CPU. Usually 64-512 entries. When accessing a virtual address, the MMU **simultaneously** checks all TLB entries. A match (TLB hit) → instant translation. A miss (TLB miss) → slow page walk through tables.

**TLB characteristics (modern x86-64):** - **L1 DTLB:** 64 entries for data (data TLB) - **L1 ITLB:** 128 entries for instructions (instruction TLB) - **L2 TLB:** 1536 entries (shared for code and data) - **Hit rate:** usually 95-99% (locality of reference) - **Miss penalty:** ~100-200 cycles (page walk) Without TLB, modern processors would be 5-10 times slower!

**TLB flush** - a critical moment. When changing context (switching to another process), the TLB becomes useless - it contains entries from the old process! The OS must **flush the TLB**. On x86, this happens when writing to the CR3 register (pointer to the root page table).

**PCID (Process Context ID)** - optimization to avoid TLB flush. Modern CPUs tag each TLB entry with a process identifier (PCID). When switching context, the TLB is not flushed - just the PCID is compared. Saves thousands of cycles on each context switch.

**Huge pages and TLB.** A regular page is 4 KB, a huge page is 2 MB or 1 GB. One TLB entry for a huge page covers 512 times more memory! Databases (PostgreSQL, MySQL) use huge pages to reduce TLB misses.

Page Replacement: eviction algorithms

**Scenario:** a program uses 4 GB of memory, but only 2 GB of RAM is physically available. Half of the pages are on disk (swap). When accessing a page on disk, a **page fault** occurs, and the OS must load it into RAM. But RAM is full! Some page needs to be **evicted**. Which one? This decision affects performance.

**Optimal algorithm (OPT / Belady's):** evict the page that will not be needed for the longest time. Ideal! But... requires knowledge of the future. Impossible to implement, used only for comparison.

**Main page replacement algorithms:** 1. **FIFO** - First-In-First-Out (oldest page) 2. **LRU** - Least Recently Used (not used for a long time) 3. **Clock (Second Chance)** - approximation of LRU 4. **LFU** - Least Frequently Used (rarely used) 5. **Working Set** - based on locality Linux uses a variation of Clock (approximation of LRU).

**FIFO (First-In-First-Out)** - the simplest algorithm. We maintain a queue of pages, evict the oldest one. Problem: the oldest page might be actively used! A classic example is **Belady's Anomaly**: increasing RAM can lead to more page faults.

**LRU (Least Recently Used)** - evict the page that has not been accessed for the longest time. Intuitively correct (locality of reference), but **expensive to implement accurately**. It requires tracking the time of each access - overhead.

**Clock Algorithm (Second Chance)** - approximation of LRU. We use the **Accessed bit** in the PTE (hardware automatically sets it on access). The OS cycles through the pages (like a clock hand). If `Accessed=1` → reset to 0 (give a second chance). If `Accessed=0` → evict.

**Working Set Model.** Programs exhibit **locality of reference**: at any given time, only a subset of pages is actively used (**working set**). If RAM is less than the working set → constant page faults (**thrashing**). If more → smooth operation.

**Linux Page Replacement:** two-list structure. **Active list** - pages recently used. **Inactive list** - candidates for eviction. The periodic process `kswapd` moves pages between lists based on the Accessed bit. When memory is low, pages are evicted from the inactive list (priority: clean → dirty).

Key ideas

• **Paging - the foundation of virtual memory.** Memory is divided into pages (4 KB), virtual addresses are translated to physical ones via page tables. Programs can use more memory than physically installed RAM, thanks to swapping.
• **Multilevel page tables save memory.** A single-level table for a 64-bit system would take up hundreds of gigabytes. A hierarchical structure (4 levels on x86-64) allocates tables only for used regions - overhead ~0.2%.
• **TLB - a performance-critical cache.** Without TLB, each memory access would require 5 RAM accesses (page walk). TLB caches the virtual-to-physical mapping, speeding up translation by ~5 times. TLB miss and thrashing are the main performance enemies.
• **Page replacement - a trade-off between algorithmic complexity and solution quality.** The optimal algorithm (OPT) requires future knowledge. LRU is good but expensive. Clock (Second Chance) is an approximation of LRU, used in Linux. Swap is not evil, but a survival mechanism when memory is scarce.

Related topics

Virtual memory is the foundation of modern OS, connected with many other concepts:

• Memory management — Virtual memory is the high-level abstraction. Under the hood: physical frame allocation, buddy allocator, slab cache
• Processes and threads — Every process has its own virtual address space. fork() uses Copy-on-Write for efficiency
• File systems — mmap() maps files into virtual memory. The page cache uses the same machinery as virtual memory
• OS security — Protection bits in PTEs (NX, U/S) prevent exploits. ASLR randomises virtual addresses to defend against attacks

Вопросы для размышления

• When designing an OS for a device with 512 MB RAM (router, IoT): is swap justified, and which page replacement algorithm minimizes overhead under constrained resources?
• Huge pages (2 MB) speed up databases but are not used by default for all applications. What trade-offs make them undesirable in the general case?
• How would virtual memory architecture change if RAM and disk had identical latency? Would TLB and page replacement still be necessary?

Связанные уроки

• os-07-memory — Virtual memory is a layer above physical memory
• os-09-filesystems — Memory-mapped files unify VM and the filesystem
• os-02-processes — Process isolation is implemented through virtual address spaces
• os-11-security — ASLR and memory protection are features of virtual memory
• db-14-mvcc