Big idea
Segmentation attacks internal fragmentation: the unused gap inside a single base-and-bounds address space.
Mechanism
The MMU keeps multiple base/bounds pairs — typically one each for code, heap, and stack. Segments can sit in different places in physical memory instead of one contiguous blob.
Stack often grows “the other way” from heap/code; hardware needs a growth-direction bit. Protection bits differ too (e.g. code: read/execute; stack/heap: read/write).
Finding the segment
- Explicit — top bits of the address select the segment; remaining bits are the offset.
- Implicit — how the address was formed: PC → code, stack pointer → stack, otherwise heap.
Coarse-grained segmentation: a few large segments (code / stack / heap). Fine-grained: many smaller segments — more flexible, more bookkeeping.
External fragmentation
Free physical memory can be split into holes. A 20 KB process may not fit even if 24 KB is free overall, because no contiguous hole is large enough.
Dealing with it
- Compaction — slide segments together to make a large free region. Correct but expensive (copying + CPU).
- Free-list algorithms — best-fit, worst-fit, first-fit, buddy, etc. They reduce pain but do not eliminate external fragmentation.