Operating systems
Part 2 of 6 · Virtual Memory — Paging, Swapping & CachesAddress Spaces — Paging, Segmentation, Paged Segmentation, and the TLB
An 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.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
What does a segment store?
Answer
A base, a limit, and permissions. The hardware checks the offset against the limit and adds the base.
L2
Which scheme has external fragmentation?
Answer
Segmentation. Free memory exists as holes too small for the next segment. Paging has internal waste in the last page instead.
L3
Why are page tables multi-level?
Answer
A flat table for a 48-bit space with 4 KiB pages would be enormous. A radix tree allocates tables only for mapped regions.
L4
What does a TLB miss cost?
Answer
Up to four or five dependent reads of page-table entries. Paging-structure caches hide some of that. Huge pages stop the walk early.
L5
What is a TLB shootdown?
Answer
The kernel invalidates a stale translation on every core that might hold it, using inter-processor interrupts, and waits.
L6
Why is a process switch more expensive than a thread switch?
Answer
Threads share an address space, so TLB entries stay valid. A process switch changes CR3. Without PCID the TLB is flushed.
L7
Why did fixed KV blocks win over a max-length reservation?
Answer
The reservation is segmentation. Requests grow and finish in arbitrary order, so holes appear. Fixed blocks remove external fragmentation.
Failure modes
TLB treated as a data cache
The TLB caches translations. The bytes live in L1, L2, and L3. A miss still pollutes those caches with page-table entries.
Segmentation declared dead
VMAs, FS and GS thread-local storage, and every variable-size allocator are the same idea.
Shootdown storm
Frequent munmap or mprotect in a many-threaded process shows up as IPI time and latency spikes.
Contiguous KV reservation
Worst-case lengths waste the reservation. Exact lengths fragment. That is the segmentation failure on a GPU.
Misconceptions
The TLB caches data.
It caches virtual-to-physical translations. Data moves through the CPU caches.
A 64-bit process owns 128 TiB of RAM.
Virtual addresses are numbers until touched. Page tables and frames appear for mapped or touched pages.
Paging removed every trace of segments.
Linux still has VMAs with permissions and a backing store, sitting on one page table.
Interviewer traps
Explaining the attention kernel while defining a page walk.
Say the block table is read by the kernel the way a walker reads a page table, then stop.
Calling every pause a TLB flush.
Separate a CR3 switch, a PCID-tagged switch, and a shootdown after mprotect.
Design scenario
Same prompt for every reader.
Requirements
Name TLB reach as the hash-table problem and shootdowns as the mprotect problem. Name external fragmentation as the KV problem. Do not propose a new attention kernel.
Traffic / scale
Random lookups over a heap much larger than TLB reach, plus short-lived mappings.
Latency
Page walks and IPIs show up in the tail. The GPU failure is admission, not a slower kernel.
Consistency
A shootdown must complete before any core uses the old translation.
Availability
Compaction or a TLB flush during the spike is not a fix for a layout that misses on every access.
Failure assumptions
- The working set is far above a few megabytes.
- Threads run on many cores.
- KV length is unknown at admission.
Constraints
- Do not claim the TLB holds the hash-table values.
- Do not redesign PagedAttention.
Prompt
A many-threaded service randomly probes a 50 GiB hash table, and a JIT flips guard pages with mprotect. Latency spikes line up with IPI counts. A second service reserves a max context of KV per request and runs out of GPU memory while most slots are untouched.
API
Which mapping change forces a shootdown?
Data
What is the page-number split on a 4 KiB x86-64 address?
Architecture
Where would a huge page help, and where would it amplify a copy?
Fixed pages or variable segments
Prefer
Paging, with VMAs for the logical regions
Any free frame fits any page. Sharing, swapping, and growth are mapping another page. Linux keeps the segment idea as VMAs over one page table.
- External fragmentation goes away.
- Internal waste is bounded by one page per region.
- The TLB is what makes the extra translation cheap.
Alternative
Pure segmentation for a long-running server
Code, heap, and stack match the hardware regions, until the holes no longer fit the next allocation and compaction stops the world.
- A gigabyte free can still reject a 100 MiB segment.
- Growing the heap may copy it.
- The same failure is a max-length KV reservation.
Translate, then ask who must hear about the change
The walk is local. The shootdown is not.
- 1
Split the address
On 4 KiB x86-64 pages the low 12 bits are the offset. The next four 9-bit fields index PML4, PDPT, PD, and PT. - 2
Try the TLB with the address-space tag
A hit returns the frame. A miss starts at CR3 and reads the tables. - 3
Fault if the entry is absent or forbidden
The kernel checks the VMA. A valid hole becomes a zero page, a file page, a swap-in, or a copy-on-write copy. An invalid address is SIGSEGV. - 4
Shoot down stale copies
munmap, mprotect, migration, and a copy-on-write break must invalidate every core that cached the old translation.
Segmentation
A segment is a contiguous range, such as code, heap, or stack, described by a base, a limit, and permissions. The hardware checks that the offset is inside the limit and adds the base. It is cheap and it matches program structure.
The failure is external fragmentation. Segments have different sizes and come and go, so physical memory becomes a checkerboard of holes. You can have 1 GiB free and still fail to place a 100 MiB segment. Growing a heap segment may require copying it somewhere bigger. Compaction fixes the holes by stopping the world and moving memory.
Paging
Split virtual memory into pages and physical memory into frames of the same size, usually 4 KiB. Any page can go into any free frame, so there is no external fragmentation. The cost moves:
- Internal fragmentation. On average half a page is wasted at the end of each region.
- Page-table memory. One entry per mapped page.
- Translation. Every access needs a virtual page number turned into a frame number. The TLB caches that.
Address split for 4 KiB pages on x86-64
| Bits | 47-39 | 38-30 | 29-21 | 20-12 | 11-0 |
|---|---|---|---|---|---|
| Field | PML4 index | PDPT index | PD index | PT index | Offset |
| Width | 512 entries | 512 entries | 512 entries | 512 entries | 4096 bytes |
Each table is one 4 KiB page of 512 eight-byte entries. A 2 MiB page is a PD entry that points at a frame and stops the walk. A 1 GiB page stops at the PDPT. Five-level paging adds one level for 57-bit addresses.
A flat table for a 48-bit space with 4 KiB pages needs 2^36 entries, hundreds of gigabytes per process. A radix tree allocates inner tables only for regions that are mapped. A sparse space, code low, heap in the middle, stack high, mmaps scattered, costs a few pages of tables. The price on a TLB miss is up to four dependent memory reads, partly absorbed by paging-structure caches in the CPU.
Paged segmentation
Each segment gets its own page table. A logical address is a segment plus an offset. The segment check gives bounds and permissions. Paging gives placement freedom. Multics and 32-bit x86 protected mode worked this way. Modern 64-bit Linux sets segment bases to zero for a flat model and keeps the idea in software as VMAs. Each mmap region, the heap, and the stack is a vm_area_struct with permissions and a backing, file or anonymous, sitting on one page table. That is paged segmentation in spirit.
| Property | Segmentation | Paging | Paged segmentation |
|---|---|---|---|
| Allocation unit | Variable | Fixed | Variable logical, fixed physical |
| External fragmentation | Yes, the main problem | No | No |
| Internal fragmentation | No | Last page per region | Last page per segment |
| Translation | Base plus offset after the limit check | Table walk, cached by the TLB | Segment check, then table walk |
| Sharing | Whole segments | Any page | Pages within segments |
| Growth | May move the segment | Map another page | Map another page |
| Metadata | Tiny | Page tables | Segment table plus page tables |
| Modern analog | FS and GS for thread-local storage | Every OS, buffer pools, KV block tables | Linux VMAs over page tables |
Choose segmentation for a long-running server with churny allocation and you get fragmentation and compaction pauses. That is the contiguous KV reservation problem. Choose tiny pages for a huge random-access heap and the TLB and the page tables become the bottleneck. That is the huge-page lesson.
Translation path
Sequence
- 1
CPU → TLB
1 lookup VPN plus ASID
- 2
TLB → CPU
2a PFN and permissions
- 3
TLB → Page walker
3a start walk at CR3
- 4
Page walker → Page table in RAM
3b read PML4 then PDPT then PD then PT
- 5
Page table in RAM → Page walker
4a PFN
- 6
Page walker → TLB
4b fill entry
- 7
TLB → CPU
4c PFN and retry access
- 8
Page walker → Kernel
5a page fault with faulting address
- 9
Kernel → Kernel
5b check VMA, valid region or SIGSEGV
- 10
Kernel → Page table in RAM
5c map frame, zero page, file, swap, or CoW
- 11
Kernel → CPU
5d return and re-execute
Lesson map
Address Spaces — Paging, Segmentation, Paged Segmentation, and the TLB
An 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.
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 cpu["CPU"] tlb["TLB"] walker["Page walker"] pt["Page table in RAM"] cpu -->|1 lookup VPN| tlb tlb -->|2a PFN and| cpu tlb -->|3a start walk at| walker walker -->|3b read PML4| pt pt -->|4a PFN| walker walker -->|4b fill entry| tlb
The TLB
A TLB is a small associative cache of translations. Think on the order of 64 entries in L1 and one to two thousand in a shared second level per core. TLB reach is entries times page size. With 4 KiB pages that is only about 6 MiB if the second-level TLB holds around 1536 entries. A service doing random lookups into a 50 GiB hash table misses the TLB on nearly every access. That is why huge pages can deliver a double-digit percent speedup for Redis-like workloads, JVMs, and databases. Measuring that miss is a profiling problem, not a new allocator: performance engineering.
Three events invalidate TLB entries:
- Context switch. A new address space makes old translations wrong. Without tags the TLB is flushed. PCID on x86, ASID elsewhere, tags entries per address space so a switch can keep them. Meltdown mitigations, KPTI, made that tagging matter again.
- munmap, mprotect, migration, copy-on-write break. The kernel changed a mapping and must invalidate it.
- TLB shootdown. In a multi-threaded process the same mapping may sit in every core's TLB. The kernel sends inter-processor interrupts to every core running that mm and waits. Heavy mmap and munmap churn, some allocators, or frequent mprotect for a JIT or guard pages, shows up as IPI storms and latency spikes.
Sandbox
A two-level toy is enough to see why a TLB miss is extra memory reads. Real x86-64 walks four or five levels in hardware.
ProblemMap eight contiguous virtual pages onto arbitrary frames. Touch one page sequentially, then stride across all eight with a four-entry TLB, then touch an unmapped page.
ExpectedSequential traffic inside one page is almost all hits. The stride misses more often than it hits. The unmapped address faults once.
Edge cases
- A second touch of the same page is a hit.
- Flushing the TLB drops translations and does not unmap the pages.
- Test: sequential page is mostly hits
stats['hits'] == 8 - Test: stride plus the fault misses more than it hits
stats['misses'] == 25 - Test: one unmapped access faults
faulted is True and stats['faults'] == 1 - Test: mapped misses read both levels
stats['walk_reads'] == 50
Press Run. Snippets must be self-contained — no network, files, or native modules.
ProblemGive code a read-only limit of three pages and the heap a writable limit of ten. Scatter the code frames. Reject a write to code, an offset past the heap limit, and an unmapped heap page. Then map that page and translate it.
Expectedcode plus 5000 lands in frame 2. The three illegal accesses raise protection, segfault, and page fault. After the new map, heap plus 8192 translates.
Edge cases
- An unknown segment id is not a page fault.
- A read of a read-only segment is allowed inside the limit.
- Test: code plus 5000 uses frame 2
codeAddr === 9096 - Test: three distinct failures
errors.length === 3 - Test: write to code is a protection fault
errors[0].indexOf('protection') >= 0 - Test: past the limit is a segfault
errors[1].indexOf('segfault') >= 0 - Test: unmapped heap page faults, then maps
errors[2].indexOf('page fault') >= 0 && heapAddr === 503808
Press Run. Snippets must be self-contained — no network, files, or native modules.
What to notice in the first sandbox: sequential access inside one page is almost all TLB hits. Striding across more pages than the TLB holds misses even though every page is resident. That is a layout problem, not a RAM-size problem. Arrays of structs versus pointer chasing matter on the hot path for the same reason.
What to notice in the second: segmentation produces the bounds and permission errors. Paging produces the lazy fault and the ability to grow without a contiguous physical hole.
The same table outside the kernel
| System | Logical address | Table | Physical unit | Cache of the table |
|---|---|---|---|---|
| CPU and OS | Virtual page number | Page table | 4 KiB frame | TLB |
| Database buffer pool | Relation and block number | Buffer mapping | 8 or 16 KiB buffer slot | The hash table, plus CPU caches |
| LSM or B-tree | Key | Index blocks and fence pointers | Data block on disk | Block cache |
| vLLM PagedAttention | Sequence and logical block | Per-sequence block table | KV block, often 16 tokens | Kept on the GPU next to the kernel |
| CDN | URL | Edge index | Cached object | Edge memory tier |
A pinned buffer is a mapped page that must not be evicted. That is why B-tree internals talks about page ids and pinning. The attention kernel follows a block table the way a page walker follows a page table. PagedAttention and continuous batching owns that structure. Prefill vs decode owns the byte math. This page is only the shared foundation.
Interview Q&A
Internal versus external fragmentation, with an example of each.
Answer
Internal fragmentation is allocated but unused space inside a unit: the half-empty last 4 KiB page of a 6 KiB allocation, or the unused tail of the last KV block. External fragmentation is free space split into pieces too small to use: segmentation holes, or a malloc arena that cannot satisfy a large request despite plenty of free bytes. Fixed-size allocation trades external fragmentation for bounded internal waste.
Why are page tables multi-level, and what is the cost?
Answer
To avoid allocating entries for unmapped regions of a huge sparse address space. A flat table for 48-bit addresses and 4 KiB pages would be enormous. The cost is a longer walk on a TLB miss, up to four or five dependent reads, partly hidden by paging-structure caches. Huge pages shorten the walk.
What is a TLB shootdown and when does it hurt?
Answer
When the kernel changes a mapping shared by threads on several cores, it must invalidate the stale translation in every core's TLB with inter-processor interrupts and wait. It hurts when a many-threaded process frequently unmaps or changes protection, during page migration from NUMA balancing or compaction, and when transparent huge pages split. Symptoms are high system time, high IPI counts, and latency spikes.
Why does a context switch between processes cost more than one between threads?
Answer
Threads share an address space, so TLB entries stay valid. A process switch changes CR3. Without PCID tags the TLB is flushed and the new process pays misses until it warms up. Caches cool too. That is one reason thread pools and event loops beat a process per request at high concurrency.
How does a 64-bit process have 128 TiB of address space on a 16 GiB machine?
Answer
Virtual addresses are numbers until touched. Page tables exist for touched or explicitly mapped pages, and frames are allocated on first write. Overcommit policy decides how much unbacked promise the kernel tolerates. That policy is the scaling lesson.
Why did vLLM pick fixed-size blocks rather than variable-size allocations for KV cache?
Answer
For the same reason operating systems picked paging over segmentation. Requests grow unpredictably and finish in arbitrary order, so variable-size contiguous allocations fragment and force worst-case reservations. Fixed blocks eliminate external fragmentation, bound internal waste to one block per sequence, and make sharing a reference count. The block table itself is taught on PagedAttention.
What do huge pages change in this walk?
Answer
A 2 MiB page stops at the page directory. A 1 GiB page stops at the page-directory-pointer table. TLB reach grows by the page-size ratio, and the leaf table shrinks. The stalls, the bloat, and the copy-on-write amplification are the next scaling page, not a reason to pretend the walk got shorter for free.
Where do you still see segments?
Answer
FS and GS for thread-local storage, Linux VMAs around mmap regions, and any allocator that hands out variable ranges. The hardware on x86-64 is a flat page table. The idea did not leave.
Pitfalls
- Saying the TLB caches data. It caches translations.
- Believing segmentation is gone.
- Forgetting that the page walk itself touches memory. A TLB-miss-heavy workload also pollutes the CPU caches with page-table entries.
Pick virtual address 0x1234 on a 4 KiB page. The offset is the low 12 bits. The page number is the rest. Say which table level you would read first on x86-64, what a TLB hit skips, and what the kernel does if the present bit is clear.