Address Translation — Base and Bounds — Operating Systems

What it is#

Base-and-bounds (a.k.a. dynamic relocation) is the original hardware mechanism for virtualizing memory. Each process is given a single contiguous chunk of physical DRAM. Two CPU registers describe the chunk:

Base — the physical address where the process’s chunk starts.
Bounds — the size of the chunk (or, equivalently, the highest legal virtual offset).

Every memory access the CPU makes is rewritten by the MMU as physical = base + virtual, with a hardware check that virtual < bounds. If the offset is in range, the access proceeds against the translated physical address; if not, the hardware raises a fault and traps into the kernel.

virtual address (process view):
   0  ──────────────────  bounds-1
   │                        │
   │   add base │ check < bounds
   ▼
physical address (DRAM):
   base  ────────────────  base + bounds-1

The mechanism is small, fast, and gives you the two big wins of virtualization: every process can be compiled to “starts at address 0” (transparency), and no process can read or write outside its own chunk (protection).

When to use it#

Base-and-bounds is rarely deployed in modern general-purpose systems — paging has displaced it almost everywhere. The reasons to study it anyway:

It’s the cleanest illustration of the virtualization concept. Strip away page tables and TLBs and you’re left with this — one register pair, two operations per access.
Embedded systems still use it. Cortex-M MPUs (memory-protection units) implement a base+limit per region with no page table. Tiny RTOSes (FreeRTOS with MPU support) lean on this for fault isolation between tasks.
Hypervisor-like shims sometimes use base-and-bounds-style relocation for guest physical to host physical when the address ranges are coarse.
Hardware capability machines (CHERI) generalise base-and-bounds into per-pointer capabilities — a pointer carries its own bounds and permissions.

Whenever you hear “the simplest hardware that gives you isolation,” base-and-bounds is the answer.

How it works#

Translation, step by step#

On a load from virtual address va:

1. CPU issues load(va).
2. MMU computes: pa = va + base.
3. MMU checks: va < bounds.
   - if not, raise out-of-bounds fault → trap to kernel.
4. MMU issues load(pa) to DRAM.
5. Result returned to CPU.

The whole thing happens inside the MMU in one cycle (or pipelined into normal load latency). No memory access required for translation itself — base and bounds are CPU registers.

What the OS does#

The OS owns the lifecycle:

At process creation, it finds a free physical chunk big enough to hold the program’s image and stack, copies the image in, sets base to the chunk’s physical start, and sets bounds to the chunk size.
On context switch, it saves the outgoing process’s (base, bounds) in the PCB and loads the incoming process’s values into the relocation registers.
On a bounds fault, it inspects the faulting access, decides whether the process is misbehaving (SIGSEGV) or whether it needs to grow the chunk (analogous to brk growth), and handles accordingly.
On free / exit, the chunk is returned to the OS’s free list.

Free-space tracking#

Because each process gets a single contiguous chunk, the OS must track free physical ranges and find one big enough on each fork / exec. This is exactly the free-list / first-fit / best-fit problem covered in Free Space Management — base-and-bounds is the reason that problem exists at all.

A worked example#

Suppose physical memory is 64 KB, process A occupies bytes 16384–32767 (base=16384, bounds=16384), process B occupies 32768–49151 (base=32768, bounds=16384).

Process A executes load 100:

MMU: pa = 100 + 16384 = 16484; 100 < 16384 OK; load from physical 16484.

Process A executes load 20000:

MMU: 20000 >= 16384 → bounds fault; trap to kernel; SIGSEGV.

Context-switch to B, kernel reloads base=32768, bounds=16384. Process B’s load 100 now goes to physical 32868, completely different bytes, completely transparent.

Variants#

Static relocation#

The historical predecessor: instead of hardware-translating each access, the loader rewrites all the absolute addresses in the binary at load time so the program “starts at” the right physical address. Cheaper (no hardware needed) but offers no protection — once running, the process can address all of memory. Used in early multiprogramming systems before hardware MMUs were common.

Base + bounds + protection bits#

A small extension: add read / write / execute bits to the register pair so the kernel can mark code read-only, data no-execute, etc. This is essentially the “memory protection unit” (MPU) approach used in Cortex-M microcontrollers, where you get a handful of (base, bounds, permissions) regions instead of just one.

Multiple base-bounds pairs per process#

If each process has separate (base, bounds) for code and data, you get the natural shape of Segmentation — base-and-bounds generalised to multiple variable-sized regions. The same isolation, with sharing (two processes can have the same code segment mapped at the same physical address) and per-segment growth.

Trade-offs#

Base-and-bounds — minimal hardware (two registers, one adder, one comparator), one-cycle translation, no page-table walk, no TLB. The mechanism is so simple that a college student can implement it on an FPGA in a weekend.

Paging — translation requires a multi-level walk, a TLB, shootdowns, and complex bookkeeping. The reward is no external fragmentation, fine-grained sharing, lazy allocation, and demand paging.

The fundamental costs of base-and-bounds:

External fragmentation. Because each process gets a single contiguous chunk, the OS has to find a hole big enough. As processes come and go, free space ends up scattered into many small holes that, combined, are huge but individually too small. Compaction can repair this, but compaction requires copying running processes’ memory, which is slow.
No fine-grained sharing. Two processes wanting to share a library have to share their entire chunk, which defeats the protection model. Segmentation fixes this.
No internal sparsity. A process that wants a 16 GB virtual address space but only uses 64 KB of it has to either pre-allocate the full 16 GB of DRAM (impossible) or get a small chunk and fail when it grows. There’s no “allocate on demand.”
Stack and heap can’t grow independently of the chunk’s size. If the chunk is sized for the initial stack and heap, a deep recursion either overflows into the heap or faults.

If base-and-bounds is so limited, why isn't paging always better?

Paging is always better for general-purpose multiprocessing — that’s why it won. But paging has a non-trivial hardware cost: an MMU, a TLB, a page-table walker, shootdown support, and the silicon area they consume. On a microcontroller running a single workload with bounded memory needs, two registers and a comparator give you most of the protection benefit at a tiny fraction of the cost. The MPU approach (a handful of base-bounds regions) is still shipping on billions of chips for this reason.

Common pitfalls#

Forgetting to save / restore the registers on context switch. Symptom: process B reads process A’s memory until A’s bounds fault stops it. Caught instantly in any test suite that runs two processes.
Setting bounds too tight. Many programs do int* p = (int*)0x... ; p[i] with i close to the limit; off-by-one in bounds yields a fault on the last legal access.
Treating base as virtual. Base is a physical address. Mixing it up means translation produces nonsense.
Assuming compaction is free. Moving a 16 MB process so a new one fits requires copying 16 MB of DRAM and pausing the moved process while pointers are valid. Real systems with base-and-bounds avoid compaction by setting a generous bound up front, which wastes space.
Expecting mmap-style sparse mappings. Base-and-bounds doesn’t give you sparse address spaces. The whole [0, bounds) range is physically backed. There’s no equivalent of “reserve 1 TB virtual, commit 4 KB.”

Address Spaces — the abstraction base-and-bounds first implements.
Segmentation — the natural generalisation to multiple regions.
Paging Fundamentals — what replaced it everywhere except embedded.
Free Space Management — the bookkeeping that base-and-bounds forces on the OS.
Limited Direct Execution — the broader story of “let user code run fast while keeping the kernel in charge.”