Virtual Memory — Paging, Swapping & Caches

Operating systems

Virtual memory, paging, the page cache, and Linux I/O models: blocking calls, epoll, io_uring, and event-loop backpressure.

• Virtual Memory — Paging, Swapping & Caches

  6 studies
  1. 1.Virtual Memory — Paging, Swapping, and Why Caches ExistEvery cache you will ever design is a smaller, faster copy of something bigger and slower, plus a rule for what to throw away. Virtual memory is the original version of that idea, built into the CPU and the kernel. A process sees a huge private address space; the kernel and MMU map small fixed-size pages of it onto physical RAM frames, keep a hot subset resident, and push the rest to disk or never materialize it at all. Once you understand page tables, the TLB, page faults, the page cache, eviction (CLOCK and working sets), huge pages, NUMA, and overcommit, three things you touch daily stop being magic: why Redis and a database buffer pool behave the way they do on a real box, why a container gets OOM-killed when the dashboard said "plenty of memory", and why vLLM chose to manage KV cache with block tables that look exactly like page tables. This hub gives the mental model and the map; five sibling lessons go deep.
  2. 2.Address Spaces — Paging, Segmentation, Paged Segmentation, and the TLBAn address space is a contract: the process sees contiguous private addresses, the hardware and kernel decide where the bytes actually live. Segmentation splits memory into variable-size logical regions with a base and a limit; paging splits it into fixed-size pages mapped through a page table; paged segmentation does both. Paging won because fixed-size units kill external fragmentation and make sharing, swapping, and lazy allocation trivial, but it costs page-table memory and a translation on every access. The TLB is the cache that makes that translation nearly free, and its limited reach is why random access over large heaps is slower than the big-O suggests. This lesson builds both translators in code and ends with the interview staples: multi-level tables, TLB shootdowns, ASIDs and PCIDs, and why these ideas reappear in database page ids and LLM block tables.
  3. 3.Faults, Swapping, and Thrashing — Working Set and the ClockA page fault is not an error; it is how the kernel implements laziness. Minor faults map a page that is already in RAM or hand out a zeroed frame in about a microsecond. Major faults read from disk or swap and cost tens of microseconds on NVMe or milliseconds on spinning disk, which is three to five orders of magnitude slower than a DRAM access. Old systems swapped whole processes; modern ones page on demand and reclaim individual pages with an approximation of LRU called CLOCK (Linux uses active and inactive lists, and newer kernels MGLRU). When the combined working sets of running processes exceed RAM, the system spends its time faulting instead of working: thrashing. This lesson builds FIFO, LRU, CLOCK, and Belady's OPT, shows the thrashing cliff, explains copy-on-write fork (Redis BGSAVE), and maps every idea onto cache design and KV-cache preemption.
  4. 4.The Page Cache — OS Cache vs Application Cache vs Buffer PoolLinux caches file contents in otherwise idle RAM: the page cache. Every buffered read and write, every mmap of a file, and every database that does not bypass it goes through this cache, keyed by file and offset and evicted by kernel policy. On top of it you usually stack more caches: a database buffer pool keyed by page id, an in-process LRU keyed by object, a shared Redis keyed by business identity, a CDN keyed by URL, and in LLM serving a KV cache keyed by token prefix. Each layer exists because it knows something the layer below cannot: object boundaries, transaction visibility, invalidation events, network locality, or the fact that a KV block can be recomputed. Stacking them carelessly double-caches the same bytes, wastes RAM, and lets one layer's eviction sabotage another. This lesson explains the read and write paths, mmap versus read versus direct I/O, why Postgres and InnoDB made opposite choices, why Redis is not the page cache, and how to pick the layer for each kind of data.
  5. 5.Scaling Memory — Huge Pages, NUMA, Bandwidth, and OvercommitMemory does not scale by adding gigabytes alone. Four walls appear as working sets grow. First, translation: with 4 KiB pages the TLB covers only a few megabytes, so large random-access heaps pay page walks constantly; huge pages (2 MiB, 1 GiB) multiply TLB reach but bring compaction stalls, bloat, and copy-on-write amplification. Second, locality: multi-socket servers are NUMA, so memory attached to the other socket is slower and its interconnect is shared. Third, bandwidth: many workloads, including LLM decode, are limited by bytes per second, not FLOPs or cores, so the fix is moving fewer bytes. Fourth, promises: Linux overcommits virtual memory, and when the bet fails the OOM killer picks a victim, often your largest cache. This lesson covers each wall with tradeoff tables, a TLB-reach and bandwidth calculator, an overcommit simulator, and the container and Kubernetes angle.
  6. 6.From Pages to KV Cache — Block Tables, Fragmentation, and Prefix CacheThis lesson is the OS lens on LLM KV cache, not a second PagedAttention tutorial. The existing lesson on PagedAttention teaches the block table, the attention kernel, and continuous batching; read it for engine internals. Here we take the vocabulary of the previous lessons and apply it: contiguous per-request KV reservation is segmentation and fails the same way, with internal waste from worst-case sizing and external fragmentation from churn; fixed-size KV blocks with a per-sequence block table are paging; block size is the page-size tradeoff; prefix caching is a page cache keyed by token content with refcounts and LRU; preemption by swapping blocks to CPU or recomputing them is demand paging where the backing store can be computation. We quantify fragmentation, build a prefix block cache that evicts like the kernel does, and work through swap versus recompute and KV offload tiers. The goal is to answer why PagedAttention uses pages, in OS terms, and to know exactly where the analogy breaks.