Skip to main content

Base/Bounds and Segmentation: The First Answer

What This Concept Is​

Before paging, hardware offered two simpler translation schemes.

Base and bounds (dynamic relocation) gives the MMU two registers per process:

  • base: added to every virtual address
  • bounds: an upper limit the virtual address must be under

A process issues address va. The hardware computes pa = base + va, checks va < bounds, raises a fault on violation, and otherwise emits pa. One contiguous region of physical memory per process, translated by a single add.

Segmentation generalizes that idea: instead of one (base, bounds) pair per process, the hardware supports several, one per logical segment (code, heap, stack, data, extra). The top few bits of the virtual address (or a segment register) select which segment's (base, bounds) to use, the remainder is the offset. The stack can grow down, the heap can grow up, and each can be placed in physical memory independently.

Why It Matters Here​

Segmentation is the bridge from a totally flat view of physical memory to full paging. Understanding its failure modes explains why we pay for paging:

  • Base and bounds force the whole address space to be contiguous in physical memory, which creates huge external fragmentation.
  • Segmentation relaxes that by allowing a handful of independently-placed regions, but external fragmentation is still a serious problem at the granularity of segments.
  • Neither scheme lets the OS easily swap out small parts of an address space, because regions are big and variably-sized.
  • Sharing works only at segment granularity, which is too coarse for things like a shared library.

Paging's answer is: chop everything into fixed-size pieces, and the fragmentation and sharing stories become solvable.

Concrete Example​

A 16 KiB address space with base-and-bounds:

  • base = 32768, bounds = 16384
  • virtual address 1234 -> physical 32768 + 1234 = 34002 (check 1234 < 16384, OK)
  • virtual address 17000 -> bounds fault

A segmented scheme with three segments (code, heap, stack):

SegmentBaseBoundsGrows
Code327684096no
Heap348168192up
Stack286724096down

A virtual address with segment bits 01 (heap) and offset 0x400 translates to 34816 + 0x400. An offset above the heap's bounds faults. The code and heap live in completely different parts of physical RAM, and the stack can even grow in the opposite direction in its own segment.

Common Confusion / Misconception​

"Segmentation faults come from segmentation hardware." The name comes from it, but on modern systems a segfault is raised by the paging subsystem when you touch an unmapped or protection-violating virtual address. Linux/x86-64 uses flat segmentation (all segment bases are 0) and does the real work in the page tables.

"External fragmentation is solved by compacting the heap." Compaction exists, but on a system with many processes and many segments it is expensive. That expense is why industry moved to paging, which makes external fragmentation structural rather than worst-case.

How To Use It​

Use segmentation as a mental lens when you meet a scheme (language runtimes, managed heaps, NUMA nodes, persistent memory) that treats memory as a small number of big regions. Ask:

  1. What are the regions?
  2. Are they contiguous in physical memory? If so, can they grow without moving?
  3. What is the granularity of protection and sharing?
  4. What does external fragmentation look like here?

If the answers are "a few regions, contiguous, coarse granularity," you are looking at a segmentation-flavored scheme with all of its historical limitations.

Check Yourself​

  1. Why does base-and-bounds force the entire address space to occupy one contiguous physical region?
  2. Segmentation allows stack and heap to grow independently. What does it not solve that paging does?
  3. What is external fragmentation, and how does segmentation make it worse over time?

Mini Drill or Application​

For each scheme, compute the translation or identify the fault:

  1. Base 24576, bounds 8192. Access at virtual 3000.
  2. Base 24576, bounds 8192. Access at virtual 8192.
  3. Segmentation, stack segment base 65536, bounds 4096, stack grows down (offsets encoded as distance from top). Access at virtual offset 4000 from the top of stack.
  4. Why does inserting a new 12 KiB segment into a physical memory that has [free 8 KiB] [used] [free 10 KiB] [used] [free 20 KiB] possibly fail, even though free memory sums to 38 KiB?

Read This Only If Stuck​