Operating systems
Part 3 of 6 · Virtual Memory — Paging, Swapping & CachesFaults, Swapping, and Thrashing — Working Set and the Clock
A 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.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
Is a page fault always a bug?
Answer
No. First touch of anonymous memory and a second mmap of a cached file are minor faults. SIGSEGV is the invalid case.
L2
What makes a fault major?
Answer
The kernel has to read the page from a file or from swap. NVMe is tens to hundreds of microseconds. A disk is milliseconds.
L3
What does CLOCK use instead of a software LRU list?
Answer
The MMU sets an accessed bit. A hand clears bits and evicts the first page whose bit is already clear.
L4
What is Belady's anomaly?
Answer
Under FIFO, giving the process more frames can increase the fault count. OPT and LRU do not do that.
L5
Define the working set.
Answer
The distinct pages referenced in the last window of references or time. If the sum of working sets exceeds RAM, the system thrashes.
L6
What does fork copy?
Answer
The page tables. Private pages become read-only in parent and child. The first write copies that page, 4 KiB or 2 MiB if a huge page backs it.
L7
How is KV preemption like paging, and how is it not?
Answer
Victims lose their blocks to a slower tier or to discard. Discarded KV is recomputed, not reloaded, and the victim is a sequence the scheduler chose.
Failure modes
Direct reclaim in the request path
kswapd fell behind. The allocating thread writes back or swaps before it can return. PSI memory stall time is this wait.
Thrashing feedback
CPU looks idle because everyone waits on I/O, so a naive scheduler admits more work and the fault rate rises.
Redis BGSAVE under writes with THP
Each copy-on-write break copies 2 MiB. Peak memory approaches twice the base and the tail moves.
Preempt and re-prefill
Too many sequences for the KV pool. Prefill steals GPU time from decode and the pool never recovers.
Misconceptions
Every page fault should be alerted.
Minor faults on startup and heap growth are normal. Major faults and PSI are the signal.
Fork is free because of copy-on-write.
Copying the page tables is real work, and every write during the snapshot copies a page.
Idle CPU during a fault storm means you should add concurrency.
That is the thrashing loop. Reduce the multiprogramming level.
Interviewer traps
Describing Redis eviction policy as the kernel CLOCK.
Say both approximate recency because exact LRU is too expensive, then point at the Redis page for the policy names.
Answering a preemption question with a disk I/O cost.
The miss may be GPU recompute. Say which one, and send the scheduler to the engine page.
Design scenario
Same prompt for every reader.
Requirements
Separate a minor-fault startup from this storm. Name admission control, working-set size, and cgroup isolation. Explain the Redis copy size. Treat KV preemption as the same cliff with a different miss cost.
Traffic / scale
Several services whose hot pages no longer fit, plus one snapshot and one over-admitted GPU batch.
Latency
Direct reclaim and major faults sit on the request path. Re-prefill sits on the GPU critical path.
Consistency
Copy-on-write must not let the child observe a torn page. The snapshot sees the share at fork.
Availability
Killing a neighbor is not a substitute for shedding load. The OOM killer is the last step, not the tuner.
Failure assumptions
- Background reclaim cannot keep the watermark.
- THP may be always.
- The GPU pool is full of refcounted blocks.
Constraints
- Do not raise concurrency because the CPU looks idle.
- Do not retell the attention kernel.
Prompt
Major faults and swap-ins are climbing, throughput is falling, and CPU is mostly iowait. A Redis BGSAVE is in progress on a host with transparent huge pages set to always. A GPU server is preempting sequences and re-prefilling them.
API
Which counters separate minor faults from major faults?
Data
Which pages are file-backed and which need swap?
Architecture
What is the admission cap, in processes or in sequences?
When the frame pool runs dry
Prefer
Background reclaim, then admission control
kswapd keeps free frames above the watermark. If the working set does not fit, shed load instead of paging the request handler.
- Clean file pages are the cheap victims. The file is the backing store.
- Anonymous pages need swap. Latency-critical caches should not be those victims.
- One more frame than the loop makes the fault storm vanish.
Alternative
Admit more work because the CPU looks idle
Everyone is in iowait. The scheduler reads idle CPU as spare capacity and the fault rate climbs.
- Direct reclaim runs inside the request thread.
- Dirty writeback competes with your own I/O.
- The OOM killer is what remains after reclaim fails.
From a missing frame to a kill
Step 7 is the latency spike. Step 9 is the outage.
- 1
Allocate if free frames sit above the watermark
The fast path never enters reclaim. - 2
Otherwise let kswapd reclaim in the background
Drop a clean file page, write back a dirty file page, or swap an anonymous page. - 3
If that loses the race, reclaim in the allocating thread
Your handler does the I/O. PSI memory some and full time measures the stall. - 4
If reclaim still fails, the OOM killer runs
Inside a cgroup this is a cgroup kill, even when the node has free memory.
Fault taxonomy
| Fault | Trigger | Kernel work | Typical cost | Backend example |
|---|---|---|---|---|
| Minor, zero page | First touch of anonymous memory | Allocate and zero a frame, map it | About 0.5 to 2 us | Heap growth, a new arena |
| Minor, page cache hit | mmap of a file already cached | Map the existing page | About 0.5 to 1 us | A second process opening the same weights |
| Major, file | Page not in the page cache | Block I/O, then map | 50 to 200 us on NVMe, 5 to 10 ms on HDD | Cold mmap of an index |
| Major, swap | Anonymous page was swapped out | Swap-in I/O | Same as file, plus swap-cache bookkeeping | A Redis key touched after swap-out |
| Protection, copy-on-write | Write to a shared read-only page after fork | Copy the page, remap writable | The copy, 4 KiB or 2 MiB with huge pages | Redis BGSAVE under write load |
| Invalid | Address outside any VMA | Deliver SIGSEGV | The process dies | Use-after-free, a null dereference |
Minor faults are a trap plus bookkeeping and maybe zeroing: around a microsecond. Major faults add storage. That is about 1,000x to 100,000x a DRAM access, so a small major-fault rate can own the latency.
Swapping versus demand paging
| Dimension | Whole-process swapping | Demand paging |
|---|---|---|
| Granularity | Entire process | One page |
| Resume latency | Read the whole image back | Fault pages in as they are touched |
| Memory efficiency | Cold and hot pages move together | Only hot pages stay |
| Predictability | The process is in or out | Tail latency tracks the fault rate |
| Modern use | Mostly historical. Echoes in container checkpoint and restore | All mainstream kernels |
| KV analog | Preempt a whole sequence's KV to CPU | Per-block offload tiers |
On Linux, swap means paging anonymous pages to a swap device. Clean file-backed pages are dropped. Dirty file pages are written back, because the file is the backing store. vm.swappiness biases reclaim between anonymous and file pages.
Reclaim under pressure
Decisions
- 1
1 Allocation needs a frame
- next2 Free frames above watermark
- ?
2 Free frames above watermark
- 2a yesAllocate and continue
- 2b no3 kswapd background reclaim
- 3
Allocate and continue
- 4
3 kswapd background reclaim
- next4 Pick victim from inactive list
- ?
4 Pick victim from inactive list
- 4a clean file page5a Drop it - file is the backing store
- 4b dirty file page5b Write back then drop
- 4c anonymous page5c Write to swap then drop
- 6
5a Drop it - file is the backing store
- next6 Enough freed
- 7
5b Write back then drop
- next6 Enough freed
- 8
5c Write to swap then drop
- next6 Enough freed
- ?
6 Enough freed
- 6a yesAllocate and continue
- 6b no - allocation stalls7 Direct reclaim in the allocating thread
- 10
7 Direct reclaim in the allocating thread
- next8 Still failing
- ?
8 Still failing
- 8a yes9 OOM killer or cgroup OOM
- 8b noAllocate and continue
- 12
9 OOM killer or cgroup OOM
Lesson map
Faults, Swapping, and Thrashing — Working Set and the Clock
A 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.
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 r["Redis parent"] k["Kernel"] c["BGSAVE child"] r -->|1 fork| k k -->|2 child shares| c r -->|4 client write| k k -->|6 parent gets a| r c -->|8 child exits| r
When background reclaim cannot keep up, the thread that wanted memory does the reclaim. That is the latency spike. /proc/pressure/memory measures the stall. Container limits and QoS live on requests, limits, and QoS. This page only needs the fact that the cgroup, not the node, is the budget.
Replacement policies
| Policy | Idea | Pros | Cons | Who uses it |
|---|---|---|---|---|
| FIFO | Evict the oldest load | Trivial | Evicts hot pages. Belady's anomaly: more frames can mean more faults | Almost nobody alone |
| LRU | Evict least recently used | Good when recency matters | Exact LRU updates on every access. Scans flush it | Software caches with an access hook |
| CLOCK | An accessed bit. The hand clears bits and evicts the first zero | No per-access software cost. Close to LRU | Approximate. Long sweeps under pressure | Kernels, in variants |
| Two lists | New pages on probation. A second touch promotes | Scan resistant | List sizes matter | Linux active and inactive. InnoDB midpoint insertion |
| LFU | Evict least frequently used | Holds long-term popular items | Slow to adapt. Counters need aging | Redis allkeys-lfu, TinyLFU in Caffeine |
| OPT | Evict the page used farthest in the future | A provable lower bound | Needs the future | Benchmarks only |
True LRU cannot run in hardware at memory-access rates. The MMU sets the accessed bit for free. Linux elaborates CLOCK with active and inactive lists and, in newer kernels, multi-generational LRU.
Sandbox
A fault in this lab stands for a major fault. The loop at the end is the cliff: one frame short of the working set and LRU misses on every access.
ProblemCompare the four policies on a hot-and-cold trace, then run LRU and CLOCK on a pure loop of 20 pages.
ExpectedOn the loop, 19 frames fault on every reference. 20 frames fault only on the first pass. OPT never faults more than LRU on the small demo trace.
Edge cases
- An empty memory faults on the first reference of each distinct page.
- More frames cannot increase OPT or LRU faults on this loop.
- Test: loop misses every access one frame short
lru_short == 1000 and clock_short == 1000 - Test: loop misses only the first pass when it fits
lru_fit == 20 and clock_fit == 20 - Test: OPT is at least as good as LRU on the demo
opt_demo <= lru_demo - Test: FIFO is defined on the same demo
fifo_demo >= opt_demo
Press Run. Snippets must be self-contained — no network, files, or native modules.
ProblemMeasure distinct pages in a window of 50 references across a phase change, then run a dirty-aware clock at several frame counts.
ExpectedDuring the first phase the window stays within 8 pages. At the phase change the window grows. More frames do not increase faults.
Edge cases
- A window shorter than the phase still mixes both phases at the boundary.
- A null slot is taken before any victim scan finishes.
- Test: first phase window is the hot handful
ws[100] <= 8 && ws[299] <= 8 - Test: phase change enlarges the working set
ws[320] > ws[299] - Test: late window stays inside the batch pages
ws[599] <= 20 - Test: more frames do not create faults
faults24 <= faults8
Press Run. Snippets must be self-contained — no network, files, or native modules.
The working-set size jumps when the trace leaves the request handler and enters the batch job. Dirty pages cost a write before reuse, so reclaim prefers clean pages and write-heavy workloads under pressure hurt twice. Dirty-ratio throttling can stall writers when too many pages are dirty. That stall is not a fault, and it still sits on the latency path.
Copy-on-write fork
fork duplicates a process by copying page tables and marking every private page read-only in both parent and child. Nothing is copied until a write. The fault handler then copies that page.
Sequence
- 1
Redis parent → Kernel
1 fork
- 2
Kernel → BGSAVE child
2 child shares pages read-only
- 3
BGSAVE child → BGSAVE child
3 iterate keys and write the RDB
- 4
Redis parent → Kernel
4 client write hits a shared page
- 5
Kernel → Kernel
5 copy 4 KiB, or 2 MiB if THP backs it
- 6
Kernel → Redis parent
6 parent gets a private writable copy
- 7
Redis parent
7 memory grows by pages written during the snapshot
- 8
BGSAVE child → Redis parent
8 child exits and shared pages are freed
State this in an interview:
- Peak memory during a snapshot is the base plus the pages written while it runs. A write-heavy Redis can approach 2x.
- Transparent huge pages make each copy 2 MiB instead of 4 KiB. Redis warns you to turn them off.
- Fork of a large page table is itself slow. The latency spike can land at snapshot start, before any copy-on-write.
- Python multiprocessing with fork shares the parent heap, but reference-count updates write object headers, so a read-only walk quietly copies.
- Postgres forks a backend per connection.
shared_bufferslives in shared memory, so it is not duplicated.
The same ideas one layer up
An application-cache miss that goes to the database is the backend's major fault: orders of magnitude slower, and a burst after a deploy is a fault storm. Stampede protection on cache-aside and single-flight fills are the equivalent of not letting a hundred threads fault the same page.
Eviction is the same question. Redis allkeys-lru is a sampled approximation for the same reason the kernel uses CLOCK. Exact LRU is too expensive at that rate. The policy list is Redis eviction.
Swap is poison for an in-memory cache. A swapped Redis page turns a fast GET into milliseconds. Give the cache headroom and keep its cgroup from swapping.
Buffer pools thrash too. If hot index pages exceed the pool, every query becomes a disk read. More memory, a smaller working set, or admission control are the same fixes. Page residency is B-tree internals.
LLM preemption is paging out. When the block pool is full, a vLLM-style scheduler swaps blocks to CPU memory or drops them and recomputes. The cost of a drop is GPU compute, not I/O. Admitting too many sequences is the thrashing loop: preempt, re-prefill, preempt again. The OS reading of that loop is the last lesson. The scheduler itself is PagedAttention and continuous batching.
Interview Q&A
What does a page fault cost, and why the huge range?
Answer
Minor faults are a trap plus kernel bookkeeping and possibly zeroing a page: around a microsecond. Major faults add storage I/O: tens to hundreds of microseconds on NVMe, milliseconds on a hard disk or network storage. That is roughly 1,000x to 100,000x a DRAM access, so even a 0.1 percent major-fault rate can dominate latency.
What is thrashing and how do you detect and fix it?
Answer
The working sets of active processes exceed physical memory, so the system mostly services faults. Detect it with rising major faults and swap-ins, high PSI memory stall time, and falling throughput while the CPU is idle or in iowait. Fix it by reducing concurrency, adding memory, shrinking working sets, or isolating a noisy neighbor with a cgroup limit. Container limits are requests, limits, and QoS.
Explain copy-on-write and one production gotcha.
Answer
After fork, parent and child share pages read-only. The first write copies just that page. Redis BGSAVE under heavy writes can nearly double memory, and with transparent huge pages each copy is 2 MiB, which spikes latency and risks OOM.
Why do kernels use CLOCK instead of true LRU?
Answer
True LRU updates order on every memory access. Hardware will not do that. The MMU sets an accessed bit for free, and CLOCK scans and clears those bits to approximate recency. Linux adds active and inactive lists and, in newer kernels, multi-generational LRU.
Should production servers have swap?
Answer
It depends on the workload. For Redis or Memcached, do not swap their memory. It turns pressure into tail latency. For a general host, a modest swap and low swappiness lets the kernel park truly cold anonymous pages and gives a warning instead of an instant OOM. Kubernetes historically required swap off. Newer versions allow it with limits.
How is vLLM preemption similar to OS paging, and how is it different?
Answer
When the block pool is exhausted, victims are chosen and their KV blocks move to a slower tier or are discarded. Discarded KV is not read back from storage. It is recomputed by prefill, so the cost is GPU compute. Victims are whole sequences chosen by a scheduler, not single pages chosen only by recency. Engine detail stays on PagedAttention.
What is the difference between dropping a file page and swapping?
Answer
A clean file page can be dropped. The file is the copy. A dirty file page must be written back first. An anonymous page has no file, so reclaim writes it to swap. vm.swappiness is the bias between those choices.
Why can FIFO get worse when you add frames?
Answer
Belady's anomaly. The pages FIFO keeps are the ones loaded earliest, not the ones you will use next. A larger memory can hold a different unlucky set. LRU and OPT do not show that anomaly. It is one reason nobody ships FIFO alone.
Pitfalls
- Treating every page fault as bad. Minor faults on startup and heap growth are normal.
- Raising concurrency when the CPU looks idle during a fault storm.
- Forgetting that dirty writeback competes with your I/O, and that
dirty_ratiocan stall writers. - Assuming fork is free because of copy-on-write.
Say what happens to LRU faults on a loop of W pages when you have W minus 1 frames, then W frames. Then say the production version: major faults up, PSI up, CPU in iowait, and the wrong fix is more concurrency.