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

Paging: Introduction

OS space management often picks one of two paths:

Variable-sized pieces — segmentation. Leads to external fragmentation.
Fixed-sized pieces — paging (Atlas [KE+62, L78]).

Split the virtual address space into fixed-size pages. View physical memory as an array of page frames; each frame holds one page.

Crux: how virtualize memory with pages to avoid segmentation’s problems — and keep space and time overheads reasonable?

A simple example

Tiny 64-byte address space → four 16-byte pages (VPN 0–3). Physical memory: 128 bytes → eight frames.

Example placement (Figure 18.2):

Virtual page	Physical frame
0	3
1	7
2	5
3	2

Frames 1, 4, 6 free; frame 0 reserved for the OS.

Advantages over segmentation:

Flexibility — no assumptions about heap/stack growth direction
Simple free-space management — grab free frames from a free list; no external fragmentation

Page tables

Per-process page table stores VPN → PFN translations. Another process gets its own table (except when sharing).

Address translation

Virtual address → VPN + offset.

64-byte space → 6 address bits; 16-byte pages → 2-bit VPN, 4-bit offset:

Va5 Va4 | Va3 Va2 Va1 Va0
  VPN   |     offset

Example: movl 21, %eax

21 = 010101 → VPN=01 (1), offset=0101 (5)
Page table[1] = PFN 7 (111)
Physical = 111 ‖ 0101 = 1110101 = 117

The offset is not translated — it selects the byte within the page.

Where are page tables stored?

Linear page tables can be huge.

32-bit AS, 4 KB pages → 20-bit VPN → (2^20) PTEs. At 4 bytes/PTE → 4 MB per process. 100 processes → 400 MB just for tables.

So: no full page table in on-chip MMU registers. Store tables in memory (for now: physical memory managed by the OS). A page-table base register (PTBR) points at the current process’s table.

What’s in a PTE?

Simplest structure: linear page table — array indexed by VPN.

Field	Role
Valid	Translation exists; unused sparse pages → invalid (save frames)
Protection	Read / write / execute
Present	In RAM vs swapped to disk (later)
Dirty	Modified since brought in
Referenced / accessed	Popular for replacement policy
PFN	Physical frame number

x86 PTEs pack present, R/W, U/S, cache bits, A, D, and the PFN [I09].

Paging: also too slow

Every explicit load/store (and each instruction fetch) needs:

Fetch PTE from the page table
Then fetch/store the actual data

VPN     = (VirtualAddress & VPN_MASK) >> SHIFT;
PTEAddr = PTBR + (VPN * sizeof(PTE));
PTE     = AccessMemory(PTEAddr);
// check valid + protect …
offset  = VirtualAddress & OFFSET_MASK;
PhysAddr = (PTE.PFN << SHIFT) | offset;
Register = AccessMemory(PhysAddr);

≈ 2× memory references — can cut performance roughly in half.

Quiz

Rank the sequence

1 / 1

Order the steps of translating a virtual address under paging.

OrderDrag the handle to rearrange — top should be first.

1Split the virtual address into VPN and offset
2Compute the PTE address from PTBR and VPN, then fetch the PTE from memory
3Access memory at the physical address to get the actual data
4Add the PFN (from the PTE) to the offset to form the physical address

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

Two problems to solve next: page tables are too big and translation is too slow.

Memory trace sketch

Zeroing an array in a loop generates, per iteration roughly:

Instruction fetches (each needs a PTE lookup)
One explicit store to the array (PTE + data)

With a 1 KB page and mapped code/array pages, the trace shows page-table accesses interleaved with code and array accesses (Figure 18.7) — and it only gets more complex from here.

Interactive

Try: virtual/physical layout · translate VA 21 · PTE bits · extra memory access cost.

Check your understanding

Quiz