§16.3–16.7What About The Stack? … Summary

Three loose ends, and each one teaches something: the stack grows the wrong way, sharing wants one more bit of hardware, and variable-sized segments leave physical memory full of holes.

16.3 What About The Stack?

In Figure 16.2 the stack lives at physical 26–28KB — but it grows backwards: it “starts” at 28KB and grows toward lower addresses, backing virtual 16KB down to 14KB. Translation must proceed differently, and the hardware needs to know which way each segment grows — one extra bit (Figure 16.4: 1 = positive, 0 = backwards).

For a backwards segment, the hardware computes a negative offset: the raw offset minus the maximum segment size. Virtual 15KB (binary 11 1100 0000 0000): selector 11 → stack; raw offset 3KB; 3KB − 4KB = −1KB; physical = 28KB + (−1KB) = 27KB. The bounds check becomes |negative offset| ≤ current size (1KB ≤ 2KB ✓). Run it — then find the stack’s limits:

(Pedantic footnote, straight from the book: the stack’s “start” at 28KB is really the byte just below the backwards region — the first valid byte is 28KB−1. Saying it this way keeps the arithmetic clean: physical = base + negative offset, always.)

16.4 Support for Sharing

Segment registers made another economy possible: sharing — code sharing especially, common then and still in use today. The extra hardware is protection bits protection bits Per-segment permission bits (read / write / execute) checked by the hardware on every access; setting code read-only lets one physical copy be safely shared across processes. defined in ch. 16 — open in glossary per segment: may this program read, write, or execute these bytes? Set a code segment read-execute (Figure 16.5 — the Protection column above), and the same physical segment can be mapped into multiple address spaces: each process still believes the memory is private, while the OS secretly shares one immutable copy. The illusion holds precisely because no one can write it.

The hardware check grows accordingly: besides in bounds?, now also permissible? Writing a read-only segment, or executing a non-executable one, raises an exception and hands the offender to the OS.

16.5 Fine-grained vs. Coarse-grained Segmentation

Three big segments (code, heap, stack) is coarse-grained coarse-grained segmentation Segmentation with just a few large segments (code, heap, stack) — the address space is chopped into big, coarse chunks. defined in ch. 16 — open in glossary — the space is chopped into a few large pieces. Some early systems (Multics; the Burroughs B5000 with support for thousands of segments) went fine-grained fine-grained segmentation Segmentation with a large number of small segments (Multics, Burroughs B5000), requiring a segment table in memory; compilers chopped code and data into many pieces so the OS could place memory more flexibly. defined in ch. 16 — open in glossary : compilers chopped code and data into many small segments, and the hardware kept a segment table segment table An in-memory table of segment descriptors used when there are too many segments for dedicated registers — the hardware support behind fine-grained segmentation. defined in ch. 16 — open in glossary in memory to hold all those base/bounds pairs. The thinking: the more precisely the OS could see which pieces were in use, the better it could pack main memory.

16.6 OS Support

Segmentation hands the OS three new duties:

Context switches. The segment registers are per-process state now — saved and restored with everything else. Nothing surprising, but easy to forget: run process B with A’s segment registers and every access lands in A’s memory.

Segment growth. A malloc() that outgrows the heap turns into a negotiation with the OS:

And the big one: managing free space. Every address space used to be the same size — physical memory was a row of identical slots. Now each process brings several segments, each a different size, and physical memory quickly becomes full of little holes:

That failure — a 20KB request refused while 24KB sits free — is external fragmentation external fragmentation Free physical memory chopped into little non-contiguous holes by variable-sized allocations, so a request can fail even though enough total free space exists — e.g. 24KB free in three chunks cannot satisfy a 20KB segment. defined in ch. 16 — open in glossary , the sibling of chapter 15’s internal fragmentation internal fragmentation Wasted space INSIDE an allocated unit — e.g., the unused gap between heap and stack in a fixed base/bounds slot. defined in ch. 15 — open in glossary : that one wasted space inside an allocation; this one strands space between them. Compaction compaction Rearranging allocated segments into one contiguous region (stop the process, copy its data, update its segment registers) to cure external fragmentation — effective but memory- and CPU-expensive. defined in ch. 16 — open in glossary (right map) cures it by stopping processes, copying their segments together, and re-pointing their registers — but it’s expensive, and ironically it packs memory so tightly that growing a segment now forces yet more rearranging. The gentler path: a smarter free list free list The OS structure tracking unused physical memory ranges, searched at process creation and refilled at termination. defined in ch. 15 — open in glossary algorithm that tries to keep large extents available — best-fit, worst-fit, first-fit, the buddy algorithm, and literally hundreds more. They’re the next chapter’s whole subject; no matter how smart, external fragmentation still exists. A good algorithm merely minimizes it.

16.7 Summary

Segmentation earns its keep: sparse address spaces become affordable (the unused middle costs nothing), the arithmetic is fast and hardware-friendly, and read-only segments give us code sharing for free. But two problems stick. External fragmentation is fundamental to variable-sized allocation — manageable, never solvable. And segmentation still isn’t flexible enough: a large but sparsely-used heap in one segment must still be entirely resident. When the model of how memory is used doesn’t match the segments, segmentation stops helping. We need new solutions. Ready to find them?