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

Mechanism: Address Translation

CPU virtualization used limited direct execution (LDE): run programs on hardware, but the OS interposes at traps and timer interrupts for control.

Memory virtualization follows the same pattern: efficiency (hardware helps on every access) and control (only your address space is reachable), plus flexibility (programs use virtual layout however they need).

Crux: how do we virtualize memory efficiently and flexibly while restricting each application to its own locations?

Answer: hardware-based address translation — on each fetch/load/store, the MMU turns a virtual address into a physical address. The OS sets up hardware at key points; the hardware runs fast on the hot path.

Interposition is powerful

The MMU interposes on every memory access. The same pattern applies to many interfaces — add behavior transparently to clients.

Book note

OSTEP’s Interlude: Memory API (Ch. 14) covers malloc, brk, etc. We go straight to the mechanism here; you can read that interlude anytime.

Assumptions (for now)

We start simple — almost laughably so:

Assumption	Meaning
Contiguous	Each address space sits in one contiguous physical chunk
Fits in RAM	Space size < physical memory
Fixed size	Every process has the same-sized slot

We relax these later (segmentation, paging, …).

Example: one line of C

void func() {
    int x = 3000;
    x = x + 3;   // line we trace
    ...
}

x86-ish assembly (use objdump / otool on real binaries):

128: movl 0x0(%ebx), %eax   ; load from address in ebx
132: addl $0x03, %eax
135: movl %eax, 0x0(%ebx)   ; store back

Layout in a 16 KB virtual space: code near 128, variable x at 15 KB on the stack (value 3000).

Memory references from the process’s view:

1. Fetch at 128
2. Load from 15 KB
3. Fetch at 132
4. Fetch at 135
5. Store to 15 KB

The process thinks its space runs 0 … 16 KB. The OS may place it at physical 32 KB instead. How relocate transparently?

Dynamic relocation (base and bounds)

Late 1950s time-sharing: base and bounds (also dynamic relocation) [SS74].

Two MMU registers per CPU:

Register	Role
Base	Where the address space lives in physical memory
Bounds (limit)	Size of the address space (check before add)

Program linked at virtual 0. On run, OS picks a physical slot and sets base.

Translation:

physical = virtual + base     (if 0 <= virtual < bounds)
           fault              (otherwise)

Example: base = 32 KB, fetch at virtual 128 → physical 32896. Load at virtual 15 KB → physical 47 KB.

Static relocation (software only)

Loaders once rewrote addresses in the executable (static relocation). Problems: no protection, hard to move a running space [M65]. Hardware base/bounds fixes both.

Example translations

4 KB space loaded at physical 16 KB (base = 16384, bounds = 4096):

Virtual	Physical
0	16 KB
1 KB	17 KB
3000	19384
4400	Fault (≥ bounds)

Negative virtual addresses fault as well.

Hardware support (summary)

Requirement	Why
User / kernel mode	Only OS sets base/bounds
Base & bounds registers	Per-CPU translation + limit check
Translate + check circuitry	MMU on every access
Privileged setup instructions	OS configures before run
Exception handlers	Out-of-bounds → OS (often kill process)

If user code could change base, it could read/write anywhere — “ghastly nightmares.”

OS responsibilities

When	OS action
Process create	Find a free slot (e.g. free list); mark used
Process exit	Return slot to free list
Context switch	Save/restore base/bounds in PCB
Fault	Handle illegal access — usually terminate
Optional move	While stopped, copy space to new physical location; update saved base

Still LDE: hardware translates on every access; OS runs only at setup, switch, and faults (Figure 15.5).

Quiz

Rank the sequence

1 / 1

Order these OS responsibilities as they occur across a process’s life (top = first).

OrderDrag the handle to rearrange — top should be first.

1. ⋮⋮1Process exit: return the slot to the free list
2. ⋮⋮2Context switch: save/restore base and bounds registers
3. ⋮⋮3Process create: find a free slot in physical memory and mark it used
4. ⋮⋮4Fault: an illegal access is handled, usually terminating the process

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

Internal fragmentation

In Figure 15.2 the process uses 32–48 KB but code+stack may use far less — wasted space inside the slot is internal fragmentation. Fixed-size slots limit how many processes fit even when plenty of RAM is “free.”

Next mechanism: segmentation — multiple base/bounds pairs per process.

Interactive: translate addresses

Try: relocated layout · OSTEP example table · instruction trace · context switch + fault.

Check your understanding

Quiz

Base and bounds

1 / 6

Address translation on each memory access means…

Pick an answer to see if you are right.

Coding challenges

Python mirrors relocation.py — bounds check, then add base.

Homework lab: relocation.py

Use the OSTEP VM mechanism homework (relocation.py). Predict in/out-of-bounds and translations before -c.

Lab

Homework: relocation.py

0/5 started

Loading lab…

Summary

Piece	Role
Address translation	Virtual → physical on every access
Base register	Relocation offset
Bounds register	Limit / protection
MMU	Hardware that performs translate + check
OS	Free list, setup, context switch, fault handling
LDE	Fast common case; OS on faults
Cost	Internal fragmentation with fixed slots

Previous: Address Spaces

Next: Segmentation — multiple base/bounds pairs per process.

Further Reading

• Remzi & Andrea Arpaci-Dusseau — Operating Systems: Three Easy Pieces Ch. 15
• OSTEP relocation homework
• McGee [M65] — dynamic relocation; Saltzer & Schroeder [SS74] — base/bounds history