Operating systems
Part 1 of 6 · Virtual Memory — Paging, Swapping & CachesVirtual Memory — Paging, Swapping, and Why Caches Exist
Every 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.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
What is the difference between a page and a frame?
Answer
A page is a fixed-size slice of the virtual address space. A frame is the same size of physical RAM. The page table maps one onto the other.
L2
What happens on a TLB hit?
Answer
The CPU gets the frame and permissions and reads the cache line through L1, L2, L3, then DRAM. No page walk, no fault.
L3
What is a minor fault versus a major fault?
Answer
A minor fault maps a page already in RAM or a zero page. A major fault reads from a file or from swap.
L4
Why is low free memory usually not an incident?
Answer
Linux fills idle RAM with the page cache and reclaims it on demand. Watch MemAvailable, major faults, swap-in, and PSI, not free alone.
L5
Why is Redis not the page cache for the database?
Answer
The page cache is local file bytes evicted by the kernel. Redis is shared application objects with your TTL and invalidation. They stack.
L6
Why did vLLM page the KV cache?
Answer
Per-request contiguous reservation fragments like segmentation. Fixed blocks and a block table bound waste and make sharing a refcount.
L7
Where does the OS analogy for KV cache break?
Answer
There is no disk behind a KV block. A miss costs GPU compute. Blocks are scheduled per batch iteration, not by a hardware MMU.
Failure modes
Free memory treated as the outage
The page cache is doing its job. The host looks full while MemAvailable is healthy.
Redis p99 after a deploy
Transparent huge pages plus a fork snapshot turn copy-on-write into multi-megabyte copies.
More cache, slower database
The buffer pool and the page cache hold the same bytes, or a neighbor grew and the working set no longer fits.
Pod OOMKilled under the limit you thought you had
The cgroup charges page cache and kernel memory, and the limit is the cgroup, not free RAM on the node.
Misconceptions
RSS is how much memory the process uses.
RSS ignores swap, double-counts shared pages, and excludes page cache charged to the cgroup.
Swap should be off on every host.
A small swap with low swappiness can park cold anonymous pages. Latency-critical caches such as Redis should not be swapped.
PagedAttention is just the OS, copied.
No disk sits behind the KV cache. Misses cost GPU compute, and the scheduler picks victims per iteration.
Interviewer traps
Retelling the PagedAttention kernel when the question is why paging exists.
Map block table to page table, then point at the engine pages for the kernel and the batcher.
Calling 2 percent free an incident before naming MemAvailable.
Separate free from available, then ask for major faults and PSI.
Design scenario
Same prompt for every reader.
Requirements
Name which signal is healthy cache, which is copy-on-write amplification, which is cgroup accounting, and which is block-pool preemption. Do not add RAM until the layer is identified.
Traffic / scale
One database, one Redis, one memory-limited pod, and one GPU server sharing the same vocabulary.
Latency
Redis and the database care about major faults and copy-on-write copies. The GPU server cares about preemption, not disk I/O.
Consistency
The page cache stays coherent for local file bytes. Redis invalidation is a separate problem.
Availability
Killing Redis to free RAM, or preempting every sequence, is the outage. Admission and headroom are the fix.
Failure assumptions
- Free and available disagree.
- Transparent huge pages may be on.
- The cgroup limit is below the node total.
Constraints
- Do not treat RSS as the whole bill.
- Do not rewrite the PagedAttention lesson.
Prompt
A database host shows 2 percent free memory. Redis p99 rose after a snapshot deploy. A pod was OOMKilled at about 70 percent of its limit. vLLM reports KV cache usage near 95 percent and throughput dropped.
API
Which metric do you read first on the database host?
Data
Which layer owns file bytes, business keys, and KV blocks?
Architecture
Which sibling page do you open for faults, the page cache, huge pages, and the KV lens?
What should own the bytes
Prefer
One layer, one key, one eviction rule
The kernel caches file offsets. Redis caches business keys. The buffer pool caches database pages. The engine caches KV blocks. Each miss has a different cost.
- Watch MemAvailable, major faults, and PSI before you buy RAM.
- Keep swap off the latency-critical cache, not off every host by reflex.
- Page the KV cache because contiguous reservations fragment. Stop there and open the engine page for the kernel.
Alternative
Free memory is the incident
Treat RSS as the bill, disable swap everywhere, double the cache, and describe PagedAttention as the OS copied onto the GPU.
- The page cache looks like a leak and gets flushed.
- Two inclusive caches store the hot set twice.
- A fork under transparent huge pages copies megabytes and the p99 moves.
Follow one load before you name a cache
The ladder is the whole series. Sibling pages hold the machinery.
- 1
The CPU issues a virtual address
The process believes the range is private and contiguous. The MMU has not agreed yet. - 2
Look in the TLB
A hit returns the frame in about a cycle. A miss walks the page table. On x86-64 that walk is four levels. - 3
Fault only if the translation is missing
A minor fault maps RAM or a zero page. A major fault reads disk or swap. That gap is orders of magnitude. - 4
Put the bytes in a CPU cache line
L1, L2, and L3 hold lines of the frame. DRAM is already the slow side of the on-core ladder.
The one-picture path
Every cache you design is a smaller, faster copy of something bigger and slower, plus a rule for what to throw away. Virtual memory is that idea in the CPU and the kernel. A process sees a huge private address space. The kernel and MMU map small fixed-size pages onto physical frames, keep a hot subset resident, and push the rest to disk or never materialize it.
Flow
- 1
1 CPU issues virtual address
- next2 TLB lookup
- 2
2 TLB lookup
- 2a hit - about 1 cycle5 Physical frame in DRAM
- 2b miss3 Page table walk - 4 levels on x86-64
- 3
5 Physical frame in DRAM
- next6 CPU caches L1 L2 L3 hold lines of the frame
- 4
3 Page table walk - 4 levels on x86-64
- 3a present5 Physical frame in DRAM
- 3b not present4 Page fault - kernel handler
- 5
4 Page fault - kernel handler
- 4a minor - page in RAM or zero page5 Physical frame in DRAM
- 4b major - read from disk or swap4c Block device I/O - tens of us to ms
- 6
4c Block device I/O - tens of us to ms
- next5 Physical frame in DRAM
- 7
6 CPU caches L1 L2 L3 hold lines of the frame
Lesson map
Virtual Memory — Paging, Swapping, and Why Caches Exist
Every 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.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["1 CPU issues virtual address"] b["2 TLB lookup"] c["3 Page table walk - 4 levels on x86-64"] d["4 Page fault - kernel handler"] a -->|1 CPU issues virtual address| b b -->|2b miss| c c -->|3b not present| d
Read it as a latency ladder. An L1 hit is about 1 ns. DRAM is about 80 to 120 ns. A TLB miss adds a page walk, several dependent memory reads, partly cached inside the CPU. A minor fault costs roughly a microsecond. A major fault from NVMe is tens to hundreds of microseconds, and from spinning disk it is milliseconds. Every caching decision in this series is about keeping work on the fast side of that ladder.
Why this matters on a real box
Without the model, production noise repeats:
- "Free memory is low, we are out of RAM." Usually the page cache is doing its job. Available memory, not free memory, is the number to watch.
- "Redis p99 spiked after a deploy." Transparent huge pages plus a fork snapshot turn copy-on-write into multi-megabyte copies.
- "The database got slower after we gave it more cache." The buffer pool and the page cache double-store the same pages, or a neighbor grew and the working set no longer fits.
- "The pod was OOMKilled at 70 percent of the limit." cgroup accounting counts page cache and kernel memory, and the limit is the cgroup, not the node.
- "vLLM says KV cache usage is 95 percent and throughput dropped." Block-pool pressure forces preemption. That is paging out under another name.
Cluster map
| Order | Lesson | What you will be able to do |
|---|---|---|
| 1 | This hub | Draw the stack, use the vocabulary, pick the sibling |
| 2 | Address spaces | Translate an address, explain multi-level tables and TLB shootdowns |
| 3 | Faults and thrashing | Diagnose fault storms, explain CLOCK, working set, and copy-on-write fork |
| 4 | The page cache | Decide what to cache where and avoid double caching |
| 5 | Scaling memory | Size boxes and containers, tune huge pages, read OOM behavior |
| 6 | Pages to KV cache | Explain why an LLM server pages KV state, and where the analogy stops |
Core vocabulary
- Virtual address space. The per-process illusion of a large contiguous memory, 48 or 57 bits wide on x86-64.
- Page and frame. Fixed-size units of virtual and physical memory. 4 KiB by default, with 2 MiB and 1 GiB huge pages.
- Page table. A per-process radix tree from virtual page numbers to frames, plus present, writable, user, accessed, dirty, and no-execute bits.
- TLB. A small hardware cache of recent translations. Its miss rate is a hidden tax on random access.
- Page fault. A trap when a translation is missing or a permission fails. Minor faults are cheap. Major faults go to storage.
- Page cache. The kernel's cache of file contents in otherwise free RAM. Buffered reads and writes go through it.
- Anonymous memory. Heap and stack pages with no file behind them. Evicting them requires swap.
- Working set. The pages a process touched in a recent window. If it does not fit, you thrash.
- Copy-on-write. Share pages read-only after fork and copy on the first write. Redis BGSAVE and Python multiprocessing rely on it.
- Overcommit. Promising more virtual memory than RAM plus swap, betting that not all of it is touched.
The big choices
Paging, segmentation, and both
| Scheme | Unit | Strength | What breaks | Where you see it |
|---|---|---|---|---|
| Pure segmentation | Variable segment with base and limit | Matches program structure; cheap bounds checks | External fragmentation. A free gigabyte may have no 100 MiB hole. Growing a segment may move it | Mostly historical. x86-64 keeps FS and GS for thread-local storage |
| Pure paging | Fixed-size page | No external fragmentation. Any frame fits any page. Sharing and swapping are easy | Internal waste in the last page. Page tables cost memory. TLB reach is limited | Every mainstream OS, and vLLM block tables |
| Paged segmentation | A segment backed by its own page table | Logical protection plus paging's placement freedom | Two-step translation and more hardware | Multics and 32-bit x86 protected mode. Alive in spirit as Linux VMAs over one page table |
Swapping versus demand paging
| Approach | What moves | Pros | Cons |
|---|---|---|---|
| Whole-process swapping | The entire address space | Simple. Frees a lot at once | Huge latency to resume. Cold pages move with hot ones |
| Demand paging | Individual pages on a fault | Loads only what is used. Fast startup. Works with mmap and overcommit | Fault storms under pressure. Unpredictable tail latency |
Who caches what
| Cache | Key | Backing store | Who evicts | Cost of a miss |
|---|---|---|---|---|
| OS page cache | File and offset | The file on disk | Kernel LRU lists, active and inactive, or MGLRU | A disk read |
| App cache, Redis or in-process | Business key | A database or service | TTL, LRU, or LFU | Query, serialization, and network |
| DB buffer pool | Tablespace and page number | Data files | A database LRU variant | A disk read, maybe of a page the kernel already cached |
| CDN | URL plus vary headers | The origin | Edge TTL and LRU | An origin round trip |
| LLM KV cache | Sequence and token block, or a prefix hash | Nothing on disk. Recomputed from tokens | The engine scheduler | Recompute prefill on the GPU, or swap in from a CPU tier |
Where the OS shows up in your stack
Redis is a process with anonymous memory. The kernel cannot evict a key. It can only swap the page, which is catastrophic for latency. Redis needs maxmemory and an eviction policy, and it should run with swap effectively off for its memory. Snapshots use fork and copy-on-write, so memory can briefly approach twice the working set under writes. Policy detail stays on Redis eviction. Stampede control on a miss stays on cache-aside.
A CDN is the same hierarchy one level up: a small fast tier near the client, eviction by TTL and recency, shielding a slow origin. That lesson is CDN cache hierarchy.
Postgres reads through the page cache and keeps shared_buffers modest. InnoDB typically uses direct I/O and owns its buffer pool. Both use scan-resistant LRU variants for the same reason the kernel does. Page splits and pinning live on B-tree internals. Many versions of one row change how many pages a hot table occupies; that capacity problem is MVCC and snapshot isolation.
KV tensors grow per token and are freed per request. A contiguous reservation wastes most of the range, the way segmentation does. PagedAttention uses fixed blocks, a per-sequence block table, copy-on-write sharing, and prefix caching. The engine lesson is PagedAttention and continuous batching. The runtime map is LLM inference runtime. Prefill versus decode byte math stays on Prefill vs decode. Sibling 6 is the OS lens on that design. It does not restate the kernel.
RSS is not the whole bill. Allocation profiles and leaks are a different page: memory profiling.
Sandbox
Reserving an address range is not the same as using it. On Linux, an anonymous mmap of 256 MiB does not raise RSS. Touching the first half, one byte per 4 KiB page, raises RSS by about 128 MiB and minor faults by about 32768. With transparent huge pages, one fault can populate 2 MiB, so the fault count drops. The browser sandbox cannot map /proc or reserve a quarter-gigabyte mapping, so this block counts the same faults. The arithmetic is the lesson.
ProblemCount resident bytes and minor faults when half of a 256 MiB anonymous mapping is touched, first with 4 KiB pages and then with 2 MiB pages.
ExpectedThe 4 KiB run residents 128 MiB and records 32768 minor faults. The huge-page run residents the same 128 MiB with 64 faults. Major faults stay zero.
Edge cases
- Touching nothing leaves resident memory at zero.
- A major fault is a disk or swap read. This touch path does not take one.
- Test: 4 KiB resident is half the reservation
base['resident_mib'] == 128 - Test: 4 KiB minor faults match the touched pages
base['minor'] == 32768 - Test: reservation stays 256 MiB
base['reserved_mib'] == 256 - Test: no major faults on first touch
base['major'] == 0 and thp['major'] == 0 - Test: huge pages fault less for the same bytes
thp['minor'] == 64 and thp['resident_mib'] == 128
Press Run. Snippets must be self-contained — no network, files, or native modules.
ProblemRepeat the touch accounting in TypeScript. V8's arrayBuffers counter can jump when the buffer is created. On Linux the RSS jump still waits for the first write to each page.
Expectedbase.minor is 32768 and base.residentMiB is 128. thp.minor is 64. major stays 0.
Edge cases
- A stride larger than the page still faults each touched page once.
- Huge pages do not shrink the resident set if every huge page in the half is touched.
- Test: 4 KiB resident is half
base.residentMiB === 128 - Test: 4 KiB faults match touched pages
base.minor === 32768 - Test: reservation is 256 MiB
base.reservedMiB === 256 - Test: huge pages cut the fault count
thp.minor === 64 && thp.residentMiB === 128 - Test: first touch is not a major fault
base.major === 0 && thp.major === 0
Press Run. Snippets must be self-contained — no network, files, or native modules.
Interview Q&A
What happens, step by step, when a program reads a variable?
Answer
The CPU looks up the virtual page in the TLB. On a hit it gets the frame and reads the cache line through L1, L2, L3, then DRAM. On a TLB miss the hardware walks the page table, four levels on x86-64, fills the TLB, and retries. If the entry is not present, the CPU raises a page fault. The kernel either maps an existing page, a minor fault, or reads it from disk or swap, a major fault, updates the page table, and resumes the instruction.
Why do we need virtual memory at all if RAM is cheap?
Answer
Isolation, so one process cannot address another's memory. Relocation, so every program links as if it owns the address space. Sharing, one copy of libc and of read-only file pages. Lazy allocation, reserve big and pay for what you touch. Memory-mapped files. Capacity overflow to disk is the least important benefit on modern servers.
Free memory is 2 percent on a database host. Is that an incident?
Answer
Usually not. Linux uses idle RAM as page cache and reclaims it on demand. Check MemAvailable, the major-fault rate, the swap-in rate, and PSI memory pressure. Low free with high available is healthy. Rising major faults, or PSI some and full stall time, is the real signal.
Why is Redis not just the page cache for my database?
Answer
The page cache stores file blocks for the local kernel, keyed by file offset, invisible to other hosts, and evicted by kernel policy. Redis stores application objects, keyed by business identity, shared across app servers, with explicit TTLs and invalidation. They solve different problems and stack. The interaction is the page cache lesson.
Why does an LLM server manage its own memory instead of trusting the OS or the CUDA allocator?
Answer
KV cache growth is per token and unpredictable. Requests finish in arbitrary order. GPU memory has no transparent paging to host for this purpose. A general allocator fragments. Fixed-size blocks and a block table give near-zero external fragmentation, cheap sharing, and a place to hang prefix caching and preemption. Pages to KV cache quantifies the waste. The attention kernel stays on PagedAttention.
How is whole-process swapping different from demand paging?
Answer
Swapping moves an entire address space out and back. Resume latency is the whole image, and cold pages travel with hot ones. Demand paging moves one page on a fault, so startup is fast and mmap and overcommit work. The cost is fault storms and a tail that depends on the fault rate.
What does RSS leave out?
Answer
RSS ignores swap, double-counts shared pages, and excludes page cache charged to the cgroup. A container can cross its limit on cache and kernel memory while the dashboard still shows headroom. The profiling tools for allocations and leaks are memory profiling.
When is a bigger cache the wrong fix?
Answer
Past the working set, extra cache returns nothing. Split across two inclusive layers, the hot bytes live twice and the disk rate can get worse. The right move is to name the layer, then size that layer.
Pitfalls
- Treating RSS as the full story.
- Disabling swap everywhere by reflex. The rule is no swap for a latency-critical cache such as Redis, not that swap is evil.
- Assuming bigger caches always help.
- Copying PagedAttention as "just like the OS" and skipping the differences: no disk behind the block, misses cost GPU compute, and victims are chosen per batch iteration.
Out loud: virtual address, TLB, page walk, minor or major fault, DRAM, then L1. Then name which sibling you would open for a fork spike, a fault storm, a double cache, a NUMA miss, or a full KV pool.