§16.1–16.2Segmentation: Generalized Base/Bounds … Which Segment Are We Referring To?

Base and bounds relocated the whole address space as one slab. Look again at what that slab mostly contains:

The space between stack and heap is not being used — yet it occupies physical memory anyway when the whole space is relocated. One base/bounds pair is wasteful, and it can’t even run a program whose address space exceeds physical memory.

16.1 Segmentation: Generalized Base/Bounds

The fix — dating to the very early 1960s — is segmentation segmentation Virtualizing memory with a base-and-bounds register pair per logical segment (code, heap, stack) instead of one pair for the whole address space, so each segment can be placed independently in physical memory and unused gaps cost nothing. defined in ch. 16 — open in glossary : instead of one base/bounds pair in the 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 , have one per logical segment. A segment segment A contiguous portion of the address space of a particular length — canonically code, heap, or stack — that the hardware relocates and bounds-checks as a unit. defined in ch. 16 — open in glossary is just a contiguous portion of the address space of a particular length; our canonical space has three — code, heap, and stack. Now each can be placed independently in physical memory:

Only used memory gets physical space, so huge, mostly-empty ( sparse sparse address space An address space that is large but mostly unused (e.g. a huge free gap between heap and stack); segmentation accommodates it by allocating physical memory only for the used segments. defined in ch. 16 — open in glossary ) address spaces become affordable. The hardware is exactly what you’d guess: three base/bounds pairs (Figure 16.3 — the register table under the translator below), where each size register plays the old bounds role.

Translation, per segment. Virtual address 100 sits in the code segment: the hardware adds it to code’s base — 100 + 32KB = 32868 — checks 100 < 2KB ✓, and issues the reference. But virtual address 4200 (in the heap) sets a trap: naïvely adding 4200 to the heap base 34KB gives 39016 — the wrong address. We must first extract the offset into the heap: the heap begins at virtual 4KB, so 4200 − 4096 = 104, and 34KB + 104 = 34920. And a reference to 7KB or beyond — past the end of the heap? Out of bounds, trap, likely termination. Try all of them:

16.2 Which Segment Are We Referring To?

How does the hardware know an address’s segment, and its offset within it? The common explicit approach (used by VAX/VMS): chop the address space by the top few bits of the virtual address. Three segments need two bits; our 14-bit address splits like this — here’s 4200:

Selector 00 → use code’s base/bounds; 01 → heap; 11 → stack. The bottom 12 bits are the offset — no subtraction needed — and the offset eases the bounds check too: just compare it against the segment’s size. If base and bounds were arrays indexed by segment, the hardware would do:

// get top 2 bits of 14-bit VA
Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
// now get offset
Offset  = VirtualAddress & OFFSET_MASK
if (Offset >= Bounds[Segment])
    RaiseException(PROTECTION_FAULT)
else
    PhysAddr = Base[Segment] + Offset
    Register = AccessMemory(PhysAddr)

For our example: SEG_MASK = 0x3000, SEG_SHIFT = 12, OFFSET_MASK = 0xFFF. Watch the same arithmetic run in the translator above — the binary readout under the virtual address is this exact split.

Two costs come bundled with the convenience. With three segments and two bits, one selector pattern (10) backs no segment — a quarter of the virtual space, gone (some systems merged code into the heap’s segment and spent only one bit). And each segment gets a hard maximum size — here 4KB, a 16KB space chopped into four — so a heap or stack that wants to grow beyond it is out of luck.

There are other ways: in the implicit approach, the hardware infers the segment from how the address was formed — generated by the program counter? code segment. Based off the stack or base pointer? stack. Anything else? heap.

But wait — preset 15360 above already whispered it: the stack doesn’t even grow the same direction as everything else. That takes one more bit of hardware, next.