The 1950s answer to transparent relocation — born in the first time-sharing machines — is base and bounds, also called dynamic relocation dynamic relocation Base-and-bounds translation done at runtime by hardware — the address space can even be moved while the process is descheduled. defined in ch. 15 — open in glossary .
15.3 Dynamic (Hardware-Based) Relocation
Two hardware registers per CPU: the base base register Per-CPU MMU register holding where the address space sits in physical memory; physical = virtual + base. defined in ch. 15 — open in glossary and the bounds bounds register Per-CPU MMU register (a.k.a. limit) holding the address-space size; out-of-bounds or negative references raise an exception. defined in ch. 15 — open in glossary (or limit). Programs are compiled as if loaded at address zero; when one starts, the OS picks its physical home and sets the base. From then on, every reference is translated by the processor:
Trace the running example — the process from Figure 15.1, relocated to 32KB:
virtual address
128
MMU (base & bounds)
1. bounds check: 0 ≤ 128 < 16384 ✓
2. add base: 128 + 32768 = 32896
physical address
32896
The fetch of instruction 128 becomes physical 32896; the load of x at 15KB (15360) becomes 47KB (48128). Try 16500 — beyond the 16KB bounds — and watch the exception. Then edit base to 48KB: same process, new home, zero recompilation. That is dynamic relocation.
The bounds register supplies the protection: before (or after — both styles are equivalent) adding the base, the processor checks the virtual address is legal. Greater than bounds, or negative → the CPU raises an exception and the OS’s handler runs (the process, most likely, dies). Note where this circuitry lives: the part of the CPU that helps translate addresses is the memory management unit (MMU) mmu The memory management unit — the part of the CPU that translates addresses; grows from two registers to TLBs and page-table walkers. defined in ch. 15 — open in glossary — two registers and an adder today, TLBs and page-table walkers as the chapters roll on.
Aside: Software-based (static) relocation
Before hardware helped, a loader did a crude version in software — static relocation static relocation A loader rewriting a program's addresses at load time — no protection, and painful to move afterward. defined in ch. 15 — open in glossary : rewrite every address in the executable at load time (movl 1000 becomes movl 4000 when loading at offset 3000). Two fatal flaws: no protection — a bad address still lands anywhere, and true protection wants hardware — and once placed, an address space is painful to move. Dynamic relocation fixes both: translation happens at runtime, and the OS can even relocate a descheduled process by copying it and updating one saved register.Now the book’s worked translations — a tiny 4KB space at physical 16KB:
virtual address
0
MMU (base & bounds)
1. bounds check: 0 ≤ 0 < 4096 ✓
2. add base: 0 + 16384 = 16384
physical address
16 KB (16384)
0 → 16KB · 1KB → 17KB · 3000 → 19384 · 4400 → fault (out of bounds). A virtual address is rightly viewed as an OFFSET into the address space; the base slides that offset to wherever the space really lives.
15.4 Hardware Support: A Summary
Everything the hardware must supply for this simplest of MMUs:
| why it's needed | |
|---|---|
| Privileged mode | restrict user-mode processes |
| Base + bounds registers | one pair per CPU, in the MMU |
| Translate + check circuitry | add base, compare against bounds |
| Privileged update instructions | only the OS may set base/bounds |
| Privileged handler registration | OS tells hardware what to run on faults |
| Exception raising | stop the program, run the OS handler |
Aside: Data structure — the free list
The OS must track which physical memory is unused so it can place new address spaces. The simplest structure: a free list free list The OS structure tracking unused physical memory ranges, searched at process creation and refilled at termination. defined in ch. 15 — open in glossary of unused ranges. (In our same-size-slots world it’s trivial; chapter 17 is what happens when sizes vary and the free list becomes a genuine engineering problem.)Hardware ready; but registers don’t set themselves. What the OS must do — at creation, termination, context switches, and faults — completes the picture next.
Check yourself
1.Base = 32KB. The process fetches the instruction at virtual address 128. What does the memory system see?
2.With bounds = 4KB, the process references virtual address 4400. What happens, step by step?
3.Why must the instructions that modify base/bounds be privileged?
4.Static relocation (the loader rewrites addresses at load time) fails on two counts. Which two?
5.How can the OS move a process's entire address space to a new physical location under base/bounds?