Skip to main content

Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 20, Arpaci-Dusseau & Arpaci-Dusseau

Paging: Smaller Tables

Linear page tables are too big. 32-bit AS, 4 KB pages, 4-byte PTE → (2^20) entries → 4 MB per process. A hundred processes → hundreds of MB just for tables.

Crux: how make page tables smaller? What ideas help? What new costs appear?

Bigger pages​

16 KB pages → 18-bit VPN → (2^18) PTEs → 1 MB table (4× smaller).

Problem: internal fragmentation — apps use little of each large page; memory fills with waste. Common default stays 4 KB (x86) or 8 KB (SPARCv9).

Multiple page sizes

Many ISAs support huge pages (e.g. 4 MB) mainly to raise TLB coverage, not to shrink tables. Superpages complicate the VM manager [N+02]; databases often request them explicitly.

Hybrid: paging + segments​

Multics idea [M07]: one page table per logical segment (code, heap, stack).

  • Base register → physical address of that segment’s page table
  • Bounds → max valid page in the segment

Top bits of the VA select the segment; then index that segment’s linear PT.

Win: no giant invalid middle between heap and stack.
Loss: still assumes a segment layout; sparse heaps waste PT space; PT sizes vary → external fragmentation for allocating page tables.

Use hybrids

Two good opposing ideas? Try combining them — when it isn’t a Zeedonk.

Multi-level page tables​

Attack invalid regions without segmentation:

  1. Chop the linear page table into page-sized chunks
  2. If an entire chunk is invalid — don’t allocate it
  3. A page directory records which PT pages exist (and where)

Each PDE has a valid bit + PFN. Valid PDE ⇒ at least one valid PTE in that PT page.

Advantages:

  • Space ≈ used address space (sparse-friendly)
  • Every piece fits in a page → allocate with a simple free list of frames
  • PT pages need not be contiguous in physical memory

Costs:

  • TLB miss may need two (or more) memory fetches — time–space trade-off
  • More complex walk (hardware or OS)

Detailed example​

16 KB AS, 64-byte pages → 14-bit VA, 8-bit VPN, 6-bit offset. Linear PT: 256 × 4B = 1 KB = 16 PT pages. Page directory: 16 PDEs → top 4 VPN bits = PD index; next 4 = PT index.

Used: VPN 0–1 (code), 4–5 (heap), 254–255 (stack). Allocate directory + two PT pages instead of sixteen.

Translate VA 0x3F80 (VPN 254, offset 0):

  1. PD index 1111 (15) → PDE → PT at PFN 101
  2. PT index 1110 (14) → PTE → PFN 55
  3. PA = (55 << 6) | 0 = 0x0DC0
Quiz

Rank the sequence

1 / 1

Order the steps of translating VA 0x3F80 with the two-level page table (top = first).

OrderDrag the handle to rearrange — top should be first.

  1. 1Compute PA = (PFN << 6) | offset = 0x0DC0
  2. 2Use the next 4 VPN bits as the PT index to find the PTE and its PFN
  3. 3Use the top 4 VPN bits as the PD index to find the PT’s physical frame

Drag items into the correct order (or use ↑↓), then check.

More than two levels​

If the directory itself spans many pages, add another level (PD0, PD1, PT). Goal: every piece fits in one page. x86-style trees follow this pattern.

Remember the TLB​

Always: TLB lookup first. Multi-level walks run only on a miss. Hits cost the same as with a linear table.

Quiz

Rank the sequence

1 / 1

Order the steps of building a multi-level page table to avoid allocating invalid regions (top = first).

OrderDrag the handle to rearrange — top should be first.

  1. 1Skip allocating any chunk that is entirely invalid
  2. 2Record in a page directory which PT pages actually exist
  3. 3Chop the linear page table into page-sized chunks

Drag items into the correct order (or use ↑↓), then check.

Inverted page tables​

One table with an entry per physical frame: which process + VPN maps here. Lookup via hash (PowerPC [JM98]). Extreme space savings; different search cost.

Swapping page tables​

Even compact tables can exceed RAM. Some systems put page tables in kernel virtual memory and swap them — revisited with VAX/VMS later.

Be wary of complexity

Implement the least complex system that meets the goal. Saint-Exupéry: perfection is when there is nothing left to take away.

Interactive​

Try: bigger pages · hybrid · linear vs multi-level · translate 0x3F80.

Check your understanding​

Quiz

Smaller page tables

1 / 6

A linear page table for a 32-bit AS with 4KB pages and 4-byte PTEs is about…

Pick an answer to see if you are right.

Coding challenges​

Homework lab: paging-multilevel-translate.py​

Use the OSTEP multi-level paging homework (paging-multilevel-translate.py).

Lab

Homework: paging-multilevel-translate.py

0/3 started

Loading lab…

Summary​

ApproachIdeaMain cost
Bigger pagesFewer VPN bitsInternal fragmentation
HybridPT per segmentInflexible layout; PT external frag
Multi-levelTree; skip empty PT pagesMore loads on TLB miss
InvertedOne entry per frameSearch / hash complexity
Swap PTsKernel VA for tablesLater chapters

Previous: TLBs

Next: Beyond Physical Memory — Mechanisms — swap, present bit, page faults.

Further Reading​