Address Spaces and Relocation
Imagine two programs, each compiled to believe it starts at memory location 0. If both run at once on the same physical machine, a conflict arises. One of them cannot actually live at physical address 0. Only one program may occupy a given byte of RAM. Yet neither program's code was written with this conflict in mind. This is the central puzzle of memory management. How can many programs, each written in blissful ignorance of the others, coexist safely in one shared physical memory? The Process abstraction gives each running program the illusion of owning the CPU. Its counterpart in memory is the address space. This is the illusion that each process owns all of memory. It starts from address zero, with no other process in sight. Without this illusion, every compiler would need to know in advance exactly where in physical RAM a program would run. This is an impossible requirement in any system that multitasks or reuses memory across executions. This article develops the classical solution to that puzzle. It separates the addresses a program uses (logical addresses) from the addresses memory actually has (physical addresses). These are translated between at run time via relocation. We build up the base-and-limit register mechanism. We trace a concrete example instruction through translation. We also examine why this simple hardware idea — a pair of registers and an adder — was foundational. It was foundational enough to appear in nearly every general-purpose computer built after the 1960s. By the end, you will be able to explain precisely what a logical address space is. You will distinguish static from dynamic relocation. You will hand-simulate the base-and-limit translation and bounds check for a given instruction stream. You will also see why this mechanism, while elegant, is too coarse for real multiprogramming. This motivates the finer-grained schemes of Contiguous Memory Allocation, Segmentation, and Paging: Basic Concept.
- A process's logical (virtual) address space is the set of addresses it generates, always starting conceptually from 0, independent of where it sits in physical RAM.
- Physical addresses are actual locations in RAM; relocation is the process of mapping logical addresses to physical ones.
- Static relocation rewrites addresses once, at load time (in software); dynamic relocation translates addresses on every memory access, at run time (in hardware).
- The classic hardware mechanism is a base register (added to every logical address) plus a limit register (bounds-checks it), enforcing both relocation and protection.
- Translation cost is O(1) per memory access — one add and one compare — making dynamic relocation essentially free in hardware.
- This scheme is the ancestor of Segmentation and Paging: Basic Concept, which replace one base/limit pair with many, to fix the fragmentation and flexibility problems it cannot solve.
A process never sees physical memory directly; hardware transparently translates every logical address it generates into a physical one, via base-and-limit registers, giving both relocation (place anywhere) and protection (stay in bounds).
The idea
Every instruction a CPU executes and every load/store it performs refers to a memory address. The question is: an address in what coordinate system? A logical address (also called a virtual address in this simple context) is the address as generated by the CPU while running a process's code — the numbers that appear in that process's compiled instructions and data references. A physical address is the address as seen by the memory unit itself — the actual row of physical RAM. The set of logical addresses a process can generate constitutes its address space; conventionally we imagine this space beginning at logical address 0 and extending up to some maximum determined by the program's size. Crucially, the compiler and linker that produced a program's binary had no idea, at compile time, where in physical memory that program would eventually run — possibly sharing the machine with other processes, or running at a different location on a different invocation. So compilers traditionally generate code as though the program will be loaded starting at address 0 (or some other compiler-chosen origin). Making this code work correctly wherever it actually ends up in RAM is the job of relocation: transforming or translating logical addresses into the correct physical addresses. Relocation comes in two flavors. Static relocation happens once, before or during loading: a loader scans the executable, and for every address-valued instruction operand, adds the intended physical base offset directly into the binary, producing a new binary hardwired to run at that one physical location. Dynamic relocation defers this decision to run time: the binary is left alone, generating logical addresses starting from 0 as always, and a piece of hardware — the memory management unit (MMU) — adds an offset on every single memory reference, translating logical to physical addresses on the fly, transparently to the running program. Dynamic relocation is strictly more powerful: it allows a process to be moved in physical memory (even while running, via a context switch that reloads the base register), which static relocation cannot support without re-linking.
How it works
The simplest dynamic relocation mechanism uses two hardware registers, loaded by the OS on every context switch:
- a base register, holding the physical starting address assigned to this process, and
- a limit register, holding the size of the process's logical address space (i.e., how many bytes/words it is permitted to address).
Every memory reference generated by the CPU — instruction fetch, load, store — is a logical address `L`. The MMU intercepts it before it reaches physical RAM and performs two operations: a bounds check against the limit, and a translation by adding the base. ``` // Executed in hardware, transparently, on EVERY memory reference // base, limit are per-process registers, loaded by the OS at context switch time function TRANSLATE(logical_address L): if L < 0 or L >= limit: raise TRAP("segmentation fault / addressing error") // OS typically kills the process or delivers a signal physical_address = L + base return physical_address // OS context-switch routine (simplified) function CONTEXT_SWITCH(next_process P): save_registers(current_process) base = P.base_register_value // set by OS when P was loaded/relocated limit = P.limit_register_value restore_registers(P) jump_to(P.saved_program_counter) ``` Two invariants make this correct: 1. Every logical address a process legitimately generates lies in `[0, limit)`. This holds because the compiler/linker built the process assuming an address space of exactly this size, and the OS chose `limit` to match the process's actual memory footprint at load time. 2. The OS never loads two processes with overlapping `[base, base+limit)` physical ranges. This is a bookkeeping invariant the OS memory allocator must maintain (the subject of Contiguous Memory Allocation); base-and-limit hardware enforces bounds within one process but relies on the OS to keep processes from colliding with each other. Given these two invariants, `TRANSLATE` guarantees:
- Relocation correctness: the physical address always equals `L + base`, which lands inside the process's assigned region, regardless of where that region is — the process code itself never needed to know `base`.
- Protection: a process cannot reference memory belonging to another process or the OS, because any `L` outside `[0, limit)` traps before translation occurs.
Trace the figure: the process generates logical address `L = 372`. The MMU checks `0 ≤ 372 < 1000` (passes), then computes `372 + base(4200) = 4572`, the true physical address — landing squarely inside process P's private green region, never touching OS memory or the neighboring processes A and B.
Complexity & correctness
Time complexity. Each translation is a single bounds comparison and a single addition — `O(1)` per memory reference, independent of address space size or number of processes. This is essential: since every memory access requires translation, anything slower than constant time would multiply the cost of all memory traffic in the system. In hardware, the comparator and adder operate in parallel with (or pipelined into) the memory access itself, so dynamic relocation with base-and-limit registers adds negligible latency — often zero visible cycles once pipelined.
Space complexity. The overhead is exactly two registers per running process context (base, limit), each typically one machine word — `O(1)` space overhead regardless of process size. Compare this to static relocation, which requires no extra registers at run time but must rewrite every address-valued word of the loaded binary at load time, costing `O(n)` time and, if a copy is kept, `O(n)` extra space, where `n` is the size of the program image.
Correctness argument. We want to show the scheme provides both relocation transparency and inter-process isolation. Claim 1 (transparency): if a process's logical addresses always lie in `[0, limit)`, the physical addresses produced always lie in `[base, base + limit)`, and this mapping is a bijection (order-preserving, one-to-one) between the process's logical space and its assigned physical region. Proof sketch: the map `f(L) = L + base` is strictly increasing and injective on any interval, so distinct logical addresses map to distinct physical addresses, and the image of `[0, limit)` under `f` is exactly `[base, base+limit)`. Hence the entire logical address space is placed, without gaps or overlaps internally, inside the assigned physical window — this is precisely relocation. The process's own instructions never mention `base`; only the MMU does, so the same binary works no matter what `base` the OS chooses. ∎ Claim 2 (isolation): no sequence of memory references generated by process P (running with `base_P, limit_P`) can produce a physical address outside `[base_P, base_P + limit_P)`, provided the OS assigns non-overlapping regions to different processes. Proof sketch: by construction, `TRANSLATE` traps on any `L ∉ [0, limit_P)`, so only `L ∈ [0, limit_P)` are ever translated, and by Claim 1 these map exactly into `[base_P, base_P+limit_P)` — never beyond it. Hence P can only ever touch physical memory inside its own window. If the OS additionally guarantees windows for distinct processes are disjoint (an allocator invariant, not an MMU one), then P can never observe or corrupt another process's memory. ∎
Honest tradeoffs. Base-and-limit relocation is cheap and simple, but it has a serious limitation: it enforces only one contiguous region per process. This forces the OS to allocate each process's entire memory footprint as one unbroken block — reintroducing external fragmentation as processes come and go (the problem Contiguous Memory Allocation tackles), and it offers no fine-grained protection within a process (e.g., you cannot mark code read-only and stack writable with a single base/limit pair). It also cannot elegantly support a process's memory growing in noncontiguous ways, or sharing a single region (like a shared library) between processes at different logical addresses. These gaps motivate splitting an address space into multiple independently-based-and-limited pieces — Segmentation — and eventually abandoning contiguity altogether via Paging: Basic Concept.
Worked example
Suppose the OS has loaded three processes. The physical memory map (in decimal, word-addressable) is:
| Region | Physical range |
|---|---|
| OS | 0 – 999 |
| Process A | 1000 – 2999 |
| Process B | 3000 – 4199 |
| Process P | 4200 – 5199 |
Process P was compiled assuming it starts at logical address 0 and occupies 1000 words, so the OS sets: ``` base_P = 4200 limit_P = 1000 ``` Now trace four instructions/memory references that process P generates while running, in order:
| Step | Logical address L | Check `0 ≤ L < 1000` | Physical address `L + base_P` | Outcome |
|---|---|---|---|---|
| 1 | 0 | pass | 4200 | fetch first instruction of P's code |
| 2 | 372 | pass | 4572 | load a data variable |
| 3 | 999 | pass | 5199 | access last legal word (top of P's space) |
| 4 | 1000 | fail (1000 ≥ 1000) | — (trap raised) | attempted access just past P's limit — likely a bug (e.g., off-by-one array indexing) or an attack attempting to read process B's memory at what would have been physical address 5200 |
Step 4 is the pedagogically important row: it shows the bounds check earning its keep. Without the limit register, logical address 1000 would translate to physical address 5200 — squarely inside process B's private region — silently corrupting or leaking B's memory. With the limit register, the CPU instead traps into the OS, which typically terminates P with a memory-protection fault (the familiar "segmentation fault"). Now suppose the OS later needs to move process P to make room for a larger neighbor. Under dynamic relocation this is simple: the OS copies P's 1000 words of physical memory to a new region, say starting at physical 9000, and updates one register: ``` base_P = 9000 // limit_P unchanged at 1000 ``` Every subsequent memory reference from P is automatically retranslated relative to the new base — P's code is completely unaware it moved. Under static relocation, by contrast, moving P would require re-scanning and rewriting every address-valued instruction in P's image again, an `O(n)` operation repeated on every move — one of the strongest practical reasons dynamic (hardware) relocation displaced static (loader-time) relocation in general-purpose systems.
Common pitfalls & traps
| Pitfall | Why it happens | Consequence |
|---|---|---|
| Off-by-one in the bounds check (`L <= limit` instead of `L < limit`) | Treating `limit` as the address of the last valid word rather than one past it | Silently allows one word of adjacent process's memory to be read/written |
| Forgetting to reload base/limit on context switch | OS neglects to treat base/limit as part of process context | A process runs with the previous process's base — instant memory corruption |
| Confusing "logical address space size" with "physical memory size" | Conflating the two coordinate systems | Miscomputed limit lets a process address memory it was never allocated |
| Assuming static relocation supports moving a running process | Believing rewritten addresses can be "re-rewritten" cheaply at run time | Requires re-executing the loader's rewrite pass — cannot be done safely while the process runs |
| Treating base+limit as full protection | Believing one region implies fine-grained access control | Cannot distinguish read-only code from writable data within the region — no sub-region permissions |
Pioneers & history
The base-and-limit register idea emerged directly from the practical demands of early multiprogrammed and time-shared systems, where several jobs needed to reside in memory simultaneously without a compiler or programmer having to hand-coordinate their addresses.
Origins · 1 minMaurice Wilkes and how this was discovered
Wilkes led the EDSAC project at Cambridge, one of the first stored-program computers, and grappled directly with the problem of relocating and protecting programs sharing scarce memory — laying groundwork that later systems formalized as base-and-limit hardware.
Where this matters
Base-and-limit relocation, in its purest form, is largely a historical stepping stone in modern general-purpose CPUs — today's systems use paging and segmentation-with-paging almost universally. But the idea it embodies is everywhere:
- Embedded and real-time systems with simple memory protection units (MPUs), such as those in the ARM Cortex-M family, still use region-based base/limit-style checks rather than full paging, precisely because they are cheap and fast for a small, fixed number of processes.
- GPU and accelerator memory windows frequently use base/bound-style range checks to sandbox a kernel's memory access into an allocated buffer.
- Container and sandbox runtimes conceptually re-derive the same idea at a software level: giving each isolated unit its own addressable "space" mapped transparently onto the shared physical resource.
- Understanding base-and-limit relocation is the essential warm-up for the mechanisms that replaced it: Contiguous Memory Allocation (how the OS decides where to place each base/limit region and reclaims fragmented holes), Segmentation (splitting one address space into several independently relocated regions, e.g., code/data/stack), and Paging: Basic Concept (replacing one coarse base/limit pair with many small fixed-size mappings, eliminating external fragmentation entirely).
Ask the tutor: How would you extend base-and-limit relocation to support two processes sharing a single read-only library segment at different logical addresses?
Why can't a compiler just generate the correct physical addresses directly?
A compiler produces one binary meant to run on many different machines, at many different times, possibly alongside a different set of other processes each time. The physical location a process will occupy in RAM depends on run-time conditions — which other programs are loaded, how much memory is free, whether the process is later moved — none of which is knowable at compile time. If addresses were hardwired to specific physical locations, the OS could never run two copies of the same program simultaneously, never move a process to defragment memory, and every program would need re-linking whenever memory layout changed. Generating logical addresses from a fixed, assumed starting point (typically 0) and deferring the actual placement decision to load or run time is what allows one compiled binary to run correctly regardless of where it ends up.
What is the difference between static and dynamic relocation in terms of when translation happens?
Static relocation happens once, at load time: a loader walks through the executable image, finds every address-valued reference, and adds the intended base offset directly into those bytes, producing a modified binary hardwired for one physical location. Dynamic relocation happens continuously, at run time: the binary is never modified, and a hardware unit (the MMU) adds the base to every logical address as it is generated, on every single memory access. Static relocation costs time proportional to program size, paid once; dynamic relocation costs constant time, paid on every memory reference, but allows the same unmodified binary to be moved, shared, or reloaded at different locations without any rewriting.
Does the base-and-limit mechanism actually provide security, or just correctness?
It provides both, and the two are intertwined here. Correctness means a process's own memory references land where the OS intended, so the program runs properly regardless of where it was placed. Protection means a misbehaving or malicious process cannot generate a logical address that resolves to another process's or the OS's physical memory. The limit-register bounds check is precisely what supplies protection: any attempt to reference an address outside `[0, limit)` is trapped before translation occurs, so it never reaches other processes' regions. Without the limit check, you would have relocation (addresses translate correctly for well-behaved programs) but no protection (a buggy or hostile program could read/write any physical address by choosing a large enough logical address).
Why is O(1) translation cost so important here, compared to, say, O(log n)?
Memory references are the single most frequent operation a CPU performs — nearly every instruction fetch and most instructions themselves touch memory. If address translation cost even O(log n) time (say, searching a table of n regions), every memory access in the entire system would inherit that overhead, multiplying the effective cost of instruction execution across all programs. A hardware adder and comparator operate in a fixed, tiny number of gate delays regardless of process size or number of processes running, so translation adds negligible or zero visible latency when pipelined into the memory access path. This constant-time property is precisely why relocation hardware, rather than a software table lookup, is used for every memory reference; software-based translation schemes are reserved for coarser, less frequent operations, such as page table walks cached by a TLB.
How does base-and-limit relate to segmentation and paging?
Base-and-limit gives each process exactly one base register and one limit register — one contiguous physical region per process. Segmentation generalizes this by giving a process several base/limit pairs, one per logical segment (code, data, stack, heap), each independently relocated and sized, which better matches how programs are actually structured and permits per-segment protection (e.g., read-only code). Paging takes a different generalization: it splits the address space into many small, fixed-size pieces (pages) each with its own translation entry, eliminating external fragmentation entirely because pages can be scattered anywhere in physical memory. Both descend conceptually from the same base/limit translate-and-check idea, applied at finer and finer granularity.
What happens to the base and limit registers during a context switch?
They are part of the saved and restored process context, exactly like the program counter and general-purpose registers. When the OS suspends process A and dispatches process P, the dispatcher must load P's previously stored base and limit values into the base/limit registers before P resumes execution, and must have saved A's values before switching away. If this step is skipped or done incorrectly, P's memory references get translated using A's base and limit, causing P to read and corrupt A's memory (and vice versa) — a severe, silent correctness bug rather than a mere slowdown, since it defeats process isolation entirely.
Is base-and-limit relocation still used in modern hardware?
Not in general-purpose desktop, server, or mobile CPUs, which universally use paged (and often segmented-plus-paged) virtual memory managed via multi-level page tables and a translation lookaside buffer (TLB). However, the same base/bound idea survives in simplified form in resource-constrained systems: memory protection units (MPUs) in microcontrollers (e.g., ARM Cortex-M) define a small fixed number of address ranges with permissions, essentially a small array of base/limit-like region descriptors, because full paging hardware is too costly in area and power for that class of device. The conceptual lineage — translate and bounds-check every access — persists even where the exact base-and-limit register pair does not.