Segmentation
A compiler produces code, a stack, and a heap. These grow at wildly different rates. They also need different protections. Cramming these into one flat, linearly-addressed region forces awkward compromises. The stack and heap must guess how much room to leave each other. There is no natural way to say "this region is read-only code" versus "this region is writable data." Segmentation solves this by giving a process several independent linear address spaces — segments. Each segment has its own base, limit, and permissions. This matches how programmers and compilers already think about a program's structure. This idea matters because Contiguous Memory Allocation treats an entire process as one indivisible block. This is simple but brittle. Any growth in the stack or heap risks colliding with the other. Sharing code between processes (like a common library) means either duplicating it or accepting weak protection. Segmentation restores structure to the address space. It lets the operating system protect each logical unit differently. It also lets two processes share a segment — say, read-only library code. Meanwhile their private data segments stay separate. It is the conceptual bridge between the flat-address model of early systems and the fully hardware-virtualized memory of modern paging systems. The big picture: a process's logical address space is no longer "byte 0 through byte N." Instead it is a small number of named segments (code, stack, heap, and others). Each segment is independently based and bounded. The CPU generates addresses as pairs `(segment number, offset)`. A per-process segment table translates each pair into a physical address. It checks the offset against that segment's limit on every access. This turns memory protection and sharing into table lookups rather than ad-hoc bookkeeping. It does so with hardware support comparable in cost to the base/limit register pair used in contiguous allocation. This article builds the segmentation model from first principles. It covers how the address is structured, how the segment table works, and how protection bits and sharing are implemented. It also shows where the scheme is efficient and where it breaks down. It ends by pointing toward Paging: Basic Concept. This solves segmentation's fragmentation problem by cutting memory into fixed-size pieces instead of variable-size logical units.
- Segmentation splits an address space into logical units (code, stack, heap, ...), each with its own base and limit.
- A logical address is a pair `(segment number, offset)`; hardware translates it via a per-process segment table.
- Each segment table entry stores a base address, a limit (length), and protection bits (read/write/execute).
- Sharing is achieved by pointing two processes' segment tables at the same physical base for a shared segment.
- Variable-sized segments reintroduce external fragmentation, the same problem seen in Contiguous Memory Allocation.
- Segmentation foreshadows Paging: Basic Concept, which fixes fragmentation by using fixed-size units instead.
Segmentation maps a process's logical structure — not its raw byte count — into independently based, bounded, and protected regions of physical memory.
The idea
A segment is a logically contiguous, variable-length region of a process's address space that represents a single meaningful unit: the code segment, the stack segment, the heap segment, or a segment for a shared library. Unlike a flat address space, where an address is just an offset from address zero, a segmented address space names which logical unit an address belongs to as well as the offset within it. A logical address therefore has two components: ``` logical address = (s, d) ``` where `s` is a segment number and `d` is an offset (displacement) within that segment. This is fundamentally different from paging, where the two components of an address are mechanically derived from splitting a single linear number into fixed-size chunks; in segmentation, the split reflects the program's actual structure, and segment lengths vary — a stack segment might be 8 KB while a code segment is 400 KB. The operating system maintains, for each process, a segment table: an array indexed by segment number, where each entry — called a segment table entry or descriptor — holds:
- base: the physical starting address of the segment,
- limit: the segment's length (so `0 <= d < limit` is required for a valid access),
- protection bits: read/write/execute permissions, and often a valid/present bit.
A dedicated hardware register, the segment table base register (STBR), points to the current process's segment table in memory, just as a page table base register will later point to a page table. On a context switch, the OS reloads STBR (and often a length register STLR bounding the number of segments), exactly as it would reload a base/limit pair in pure contiguous allocation — the difference is that segmentation gives the process several such base/limit pairs instead of one.
How it works
Step 1 — Compile-time or link-time segment assignment. The compiler or linker organizes generated code and data into logical segments (for example, segment 0 = code, segment 1 = data/heap, segment 2 = stack). Every symbolic reference the compiler emits is really a `(segment, offset)` pair, though on many architectures the segment number is implicit from context (instruction fetches use the code segment, stack operations use the stack segment, and so on).
Step 2 — Segment table construction. When the OS loads the process, it allocates physical memory for each segment (using an allocator such as first-fit or best-fit, as in contiguous allocation) and fills in the base, limit, and protection bits of each segment table entry.
Step 3 — Address translation on every memory access. The CPU's memory management unit (MMU) intercepts every logical address `(s, d)` and performs: ``` function translate(s, d): if s < 0 or s >= number_of_segments(process): raise SEGMENTATION_FAULT # invalid segment number entry = segment_table[s] if not entry.valid: raise SEGMENTATION_FAULT # segment not present if d < 0 or d >= entry.limit: raise SEGMENTATION_FAULT # offset out of bounds if access_type not permitted by entry.protection_bits: raise PROTECTION_FAULT # e.g., write to read-only segment physical_address = entry.base + d return physical_address ```
Step 4 — Memory access. Once translated, the physical address is sent to the memory bus exactly as in an unsegmented system; segmentation only changes how the address is computed and checked, not how memory itself is organized.
Step 5 — Growth. When a segment (typically the heap or stack) needs to grow, the OS checks whether adjacent physical space is free. If so, it extends the limit in the segment table entry. If not, it must relocate the segment to a larger free hole (updating base, and possibly limit), or fail the allocation if no such hole exists — precisely the Contiguous Memory Allocation fragmentation problem, but now scoped per-segment rather than per-process.
Step 6 — Sharing. To share a segment (e.g., a common library) between two processes, the OS sets both processes' segment table entries for that segment to the same physical base and limit, typically both marked read-only/execute-only to prevent one process's writes from corrupting the shared code for the other. Only one physical copy exists in memory, referenced by multiple segment tables. ``` // Sharing segment k between process P and process Q segment_table[P][k].base = shared_base segment_table[P][k].limit = shared_limit segment_table[P][k].protection = READ | EXECUTE segment_table[Q][k].base = shared_base // same physical location segment_table[Q][k].limit = shared_limit segment_table[Q][k].protection = READ | EXECUTE ``` ```pseudocode // Full lifecycle: load, translate, grow, and free a segmented process structure SegmentEntry: base: integer // physical start address limit: integer // length in bytes valid: boolean // is this segment currently mapped? protection: bitmask // READ, WRITE, EXECUTE function load_process(segments): // segments: list of (size, protection) table = new array of SegmentEntry[len(segments)] for i, (size, prot) in enumerate(segments): hole = allocator.find_free_block(size) // first-fit / best-fit search if hole is None: raise OUT_OF_MEMORY table[i].base = hole.address table[i].limit = size table[i].valid = true table[i].protection = prot allocator.mark_used(hole.address, size) return table function translate(table, s, d, access_type): if s < 0 or s >= len(table): raise SEGMENTATION_FAULT entry = table[s] if not entry.valid: raise SEGMENTATION_FAULT if d < 0 or d >= entry.limit: raise SEGMENTATION_FAULT if access_type not in entry.protection: raise PROTECTION_FAULT return entry.base + d function grow_segment(table, s, extra_bytes): entry = table[s] if allocator.extend_in_place(entry.base, entry.limit, extra_bytes): entry.limit += extra_bytes return SUCCESS // no room to extend in place: relocate new_size = entry.limit + extra_bytes new_hole = allocator.find_free_block(new_size) if new_hole is None: return FAILURE // caller sees allocation failure copy_memory(new_hole.address, entry.base, entry.limit) allocator.free(entry.base, entry.limit) entry.base = new_hole.address entry.limit = new_size return SUCCESS function free_process(table): for entry in table: if entry.valid: allocator.free(entry.base, entry.limit) ```
Complexity & correctness
Time complexity. Address translation is `O(1)`: a single segment-table index, two comparisons (`d` against `0` and `limit`), a permission check, and one addition. This is identical in asymptotic cost to the base/limit check in plain contiguous allocation — segmentation adds only a constant-factor overhead (one extra table indexing step to pick which base/limit pair to use, since there are now several). In hardware, the segment table for a small, fixed number of segments (as in early x86 real/protected mode) is held in fast on-chip registers, keeping translation at true `O(1)` with no memory access beyond the data reference itself; for a large or variable number of segments, the table lives in memory and may itself be cached (a translation lookaside buffer analogous to the one used in paging).
Space complexity. The segment table needs `O(k)` entries for a process with `k` segments, where `k` is typically small (single digits to a few dozen), versus a page table's `O(n / page_size)` entries for an `n`-byte address space. This is segmentation's structural space advantage over naive paging: table size tracks the number of logical units, not the address space size.
Correctness argument. The translation function is correct if it upholds two invariants for every access: 1. Containment invariant: every physical address returned lies within `[entry.base, entry.base + entry.limit)`, the boundaries of physical memory actually allocated to that segment. This holds because the code checks `0 <= d < entry.limit` before computing `entry.base + d`; no other code path returns an address. 2. Isolation invariant: no process can construct a logical address that translates into another process's memory, unless the OS has explicitly aliased a segment table entry to a shared segment. This holds because segment numbers are indices into that process's own segment table (reached only through its private STBR), so a process cannot even name another process's segment table entry, let alone bypass its limit check. Together these invariants give memory protection by construction: a process cannot read, write, or execute outside a segment's declared bounds and permissions without the hardware raising a fault before the access reaches physical memory. This is a genuine safety property, not merely emergent behavior — it follows directly from the fact that translation is total (every logical address either yields a checked physical address or raises a fault) and that the checks are performed before the memory bus is ever driven.
Tradeoffs. Segmentation reintroduces the core weakness of contiguous allocation within each segment: because segments are variable-length, growing them or fitting them into physical memory causes external fragmentation — free memory scattered in holes too small individually to satisfy a new request, even though their sum is sufficient. Compaction (as in pure contiguous allocation) can defragment, but at the cost of pausing execution and copying memory, an `O(n)` operation in the size of memory in use. Segmentation also complicates the allocator's job: instead of finding one hole per process, it must find (or grow) one hole per segment, increasing the frequency and granularity of allocation requests. These costs are exactly what motivate replacing variable-length segments with fixed-size pages, discussed in Paging: Basic Concept.
Worked example
Consider a process with four segments loaded into physical memory as shown in the figure above:
| Segment | Name | Base | Limit | Protection |
|---|---|---|---|---|
| 0 | code | 1000 | 500 | R-X |
| 1 | heap | 2200 | 300 | RW- |
| 2 | stack | 3000 | 200 | RW- |
| 3 | shared | 5000 | 400 | R-- |
Trace four accesses issued by the running program:
| Access | Logical (s, d) | Check | Result |
|---|---|---|---|
| Fetch instruction | (0, 50) | `0 <= 50 < 500` ✓, EXECUTE permitted | physical = 1000 + 50 = 1050 |
| Push to stack | (2, 120) | `0 <= 120 < 200` ✓, WRITE permitted | physical = 3000 + 120 = 3120 |
| Read library string | (3, 40) | `0 <= 40 < 400` ✓, READ permitted | physical = 5000 + 40 = 5040 |
| Write library string | (3, 40) | limit OK, but WRITE not in R-- | PROTECTION_FAULT (attempted write to read-only segment) |
| Overflow the stack | (2, 250) | `250 >= limit (200)` | SEGMENTATION_FAULT (offset exceeds segment bound) |
The fourth row is exactly the everyday meaning of the term "segmentation fault": not necessarily a crash from corrupted memory, but the hardware's own bounds check refusing an out-of-range offset within a named segment. The third row demonstrates sharing: segment 3's base (5000) is identical in a second process's segment table, so both processes read the same physical bytes, yet neither can corrupt them because both entries mark the segment read-only. Now trace a growth scenario: the heap (segment 1, base 2200, limit 300) needs 150 more bytes. 1. The allocator checks addresses 2500–2649 (immediately following the heap) — suppose they are free. 2. `grow_segment` extends in place: `entry.limit` becomes `300 + 150 = 450`; base stays 2200. 3. No copying was needed, and translation for the heap is unaffected in cost — still one table lookup. But suppose instead addresses 2500–2649 are occupied by another segment. Then: 1. `extend_in_place` fails. 2. The allocator searches for a free hole of size 450 elsewhere — say it finds one at address 6000. 3. The 300 bytes at 2200–2499 are copied to 6000–6299, the old range is freed, and `entry.base` becomes 6000, `entry.limit` becomes 450. 4. This copy is `O(current segment size)`, and every other segment's table entries are untouched — only the heap's own entry changes, illustrating that a growth or relocation in one segment never disturbs the code, stack, or shared segments' translations.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Off-by-one in the limit check | Using `d <= limit` instead of `d < limit` allows one byte past the segment | Always check `0 <= d < limit`; limit is a length, not a maximum valid offset |
| Forgetting the segment-number bound check | Assuming `s` is always valid lets a corrupted or malicious program index outside the table | Validate `0 <= s < number_of_segments` before indexing the table at all |
| Sharing a segment with mismatched protection bits | One process marks a shared segment writable, letting it corrupt code another process trusts as read-only | Enforce identical (or more restrictive) protection on every alias of a shared segment |
| Treating segment growth as free | Assuming `grow_segment` never needs to relocate | Always handle the "no room in place" branch — relocation and copying cost `O(segment size)` and can fail |
| Confusing segmentation faults with memory corruption | Assuming any "segmentation fault" message implies overwritten data | It really means: bounds or permission check failed before any memory was touched — a safety success, not silent corruption |
| Ignoring external fragmentation growth over time | Assuming segment allocation behaves like a single contiguous block | Track fragmentation per segment class; consider periodic compaction or moving to paging |
Pioneers & history
Segmentation as a distinct memory-management model — separate from paging — emerged from the recognition that programs have logical structure that flat or fixed-size addressing discards. The Burroughs B5000, the Multics project at MIT and Bell Labs, and later Intel's segmented x86 architecture each explored how far hardware could go in exposing and protecting a program's natural units directly.
Origins · 1 minJack B. Dennis and how this was discovered
Jack Dennis's work on segmentation and virtual memory at MIT in the early 1960s helped formalize the idea that an address space could be organized as a set of independently protected, growable segments rather than one flat region — directly influencing the design of Multics and, through it, later Unix-family systems.
Where this matters
Segmentation's core ideas persist even where pure segmented hardware has faded. The x86 architecture still retains segment registers (`CS`, `DS`, `SS`, and others) for historical compatibility, and operating systems use them minimally — often mapping all segments to the same base to emulate a flat address space, while relying on paging for the real protection and translation work. Modern systems more often combine segmentation's logical insight with paging's fixed-size efficiency: a process's logical regions (code, heap, stack, memory-mapped files, shared libraries) are still tracked as distinct, independently protected units by the OS — visible as "VMAs" (virtual memory areas) in Linux or "regions" in other kernels — even though the underlying translation hardware is page-based, not segment-based. The sharing model segmentation pioneered directly motivates shared library mechanisms (`.so` files, DLLs), where a single physical copy of library code is mapped read-only into many processes' address spaces. Kernel designs that separate code, read-only data, and writable data into distinct protected regions — a pattern now enforced largely through page-level permission bits rather than segment tables — inherit segmentation's core protection philosophy: give each logical unit exactly the access it needs and no more. Understanding segmentation is therefore essential preparation for Paging: Basic Concept, which keeps this per-region mindset but replaces variable-length, fragmentable segments with fixed-size, easily managed pages, and for Address Spaces and Relocation, whose base/limit translation segmentation directly generalizes.
Ask the tutor: How would combining segmentation with paging (segments made of pages) change the translation steps and the size of the tables involved?
How is segmentation different from paging?
Segmentation divides an address space into variable-length logical units chosen to match a program's structure — code, heap, stack — while paging divides both logical and physical memory into fixed-size, mechanically defined blocks unrelated to program structure. A segment table entry needs a base and a limit because segments vary in size; a page table entry needs only a frame number, since every page is the same fixed size by definition. Consequently segmentation naturally expresses sharing and protection at the granularity of meaningful program regions, but reintroduces external fragmentation, while paging eliminates external fragmentation (at the cost of internal fragmentation within the last page of a region) but loses the direct correspondence between a table entry and a meaningful logical unit. Many real systems, including Multics and modern virtual memory areas, blend both ideas.
Why does a "segmentation fault" not always mean the program crashed from corrupted data?
The name reflects the original hardware mechanism: an offset `d` that falls outside `[0, limit)` for its segment, or an access that violates the segment's protection bits, is caught by the bounds/permission check before the memory bus is ever driven. The fault is a successful safety mechanism, not evidence that memory was actually overwritten. In modern operating systems the term persists (as `SIGSEGV` on Unix-like systems) even though the underlying hardware is usually paging-based; it still signals an out-of-bounds or unauthorized access caught by translation hardware, just implemented via page tables rather than a literal segment table.
Can a process have more segments than fit in a fixed number of hardware segment registers?
Yes, if the architecture supports a segment table stored in memory (indexed by the STBR) rather than a small fixed set of on-chip registers. Early hardware, such as original x86 real mode, offered only a handful of segment registers, limiting flexibility; later designs, such as Multics and the 80386's descriptor tables, allowed a much larger, memory-resident segment table with hundreds or thousands of entries, at the cost of an extra memory access per translation unless a translation cache (analogous to a TLB) holds recently used entries.
Does segmentation prevent all forms of memory corruption?
No. It prevents a process from accessing memory outside its own segments' declared bounds and permissions, which stops many classes of accidental or malicious out-of-bounds access. It does not prevent bugs within a segment's own bounds, such as writing garbage to a valid heap offset that another part of the same program later misreads, nor does it prevent races between threads sharing the same segment's writable data. Those require additional mechanisms such as Contiguous Memory Allocation-aware allocators with internal bookkeeping, or higher-level synchronization, rather than segmentation's coarse-grained per-segment checks.
Why did most general-purpose operating systems move away from pure segmentation?
Variable-length segments make memory management harder: finding a hole for a growing segment, or compacting memory to eliminate external fragmentation, are both costlier and more failure-prone than managing fixed-size pages. Paging also simplifies swapping a process's memory to disk, since every page is the same size and can be relocated independently, whereas segments of differing sizes complicate that story. Most systems kept segmentation's logical grouping idea (tracking regions like code, heap, and stack) but implemented the actual translation and physical allocation using paging, gaining paging's simplicity while retaining per-region protection through page permission bits.
What hardware state must be saved and restored on a context switch under segmentation?
At minimum, the segment table base register (STBR), pointing to the outgoing or incoming process's segment table, and often a segment table length register (STLR) bounding how many entries that table contains. This is the direct generalization of saving a single base/limit pair in pure contiguous allocation: instead of one pair, segmentation requires the OS to swap in a pointer to an entire table of base/limit/protection triples, though the table itself typically lives in memory and does not need to be copied on every switch — only the pointer to it changes.
Is a segment table entry the same thing as a page table entry?
No, though they play analogous roles. A segment table entry stores a base address and a limit, because segments have arbitrary, varying lengths that must be checked on every access. A page table entry stores only a frame number (and permission bits), because every page has the same fixed size fixed by the hardware, so no per-entry length field is needed. This distinction is exactly why segmentation supports natural, variable-size logical units while paging supports simpler, fixed-size physical management — a tradeoff explored further in Paging: Basic Concept.