Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 16, Arpaci-Dusseau & Arpaci-Dusseau

Segmentation

So far each process’s entire address space sits in physical memory behind one base/bounds pair. That wastes RAM on the unused gap between heap and stack (Figure 16.1). A 32-bit (4 GB) sparse space would demand the whole space resident even if the program only uses megabytes.

Crux: how support a large address space with lots of free space between stack and heap?

Segmentation: generalized base/bounds

Segmentation (early 1960s [H61, G62]): instead of one base/bounds pair, give the MMU a pair per logical segment.

A segment is a contiguous piece of the address space of a given length. The canonical layout has three:

Segment	Role
Code	Instructions
Heap	malloc / dynamic data
Stack	Calls, locals

Place each segment independently in physical memory (Figure 16.2) — unused virtual gap need not occupy physical RAM. That enables sparse address spaces.

Example register values (Fig 16.3)

Segment	Base	Size
Code	32 KB	2 KB
Heap	34 KB	2 KB
Stack	28 KB	2 KB

Code at physical 32 KB (size 2 KB); heap at 34 KB (size 2 KB). Only used memory is allocated.

Translation examples

Code, virtual address 100 (instruction fetch):

• Offset into code = 100
• Physical = 100 + 32 KB = 32868
• Bounds check: 100 < 2 KB → OK

Heap, virtual address 4200:

Do not add 4200 + 34 KB (that gives the wrong 39016). The heap starts at virtual 4 KB, so:

• Offset = 4200 − 4096 = 104
• Physical = 104 + 34 KB = 34920

Illegal (e.g. virtual 7 KB) past the heap → hardware raises an exception → OS usually kills the process.

Segmentation fault

The term segmentation fault / violation comes from illegal access on a segmented machine. It stuck even on machines without segmentation — and still ruins your day when you cannot find the bug.

Which segment are we referring to?

Explicit approach (VAX/VMS [LL82])

Chop the address space with the top bits of the virtual address. Three segments → need two bits. For a 14-bit VA:

[ 2-bit segment | 12-bit offset ]
 bits 13–12         bits 11–0

Top bits	Segment
00	Code
01	Heap
11	Stack

Virtual 4200 in binary: 01 0000 0110 1000 → segment 01 (heap), offset 0x068 = 104.

Hardware sketch:

Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT;  // 0x3000, shift 12
Offset  = VirtualAddress & OFFSET_MASK;              // 0xFFF
if (Offset >= Bounds[Segment])
    RaiseException(PROTECTION_FAULT);
else
    PhysAddr = Base[Segment] + Offset;

Quiz

Rank the sequence

1 / 1

Order the hardware steps for translating a virtual address with explicit (top-bit) segmentation.

OrderDrag the handle to rearrange — top should be first.

1. ⋮⋮1Check whether the offset is within that segment's bounds; raise a protection fault if not
2. ⋮⋮2Add the offset to that segment's base register to form the physical address
3. ⋮⋮3Extract the offset from the remaining low bits of the virtual address
4. ⋮⋮4Extract the segment number from the top bits of the virtual address

Drag items into the correct order (or use ↑↓), then check.

With only three segments, one top-bit pattern is unused. Some systems put code + heap in one segment and use a single select bit [LL82]. Top-bit chopping also caps each segment’s max size (here 4 KB per quarter of a 16 KB space).

Implicit approach

Infer the segment from how the address was formed:

• From the PC (instruction fetch) → code
• From stack / base pointer → stack
• Anything else → heap

What about the stack?

The stack is at physical 28 KB but grows backwards (toward lower addresses): physical 28 KB → 26 KB maps virtual 16 KB → 14 KB.

Hardware needs a grows positive? bit (Figure 16.4):

Segment	Base	Size	Grows +?
Code	32 KB	2 KB	1
Heap	34 KB	2 KB	1
Stack	28 KB	2 KB	0

Example: virtual 15 KB → physical 27 KB.

• Binary 11 1100 0000 0000 (0x3C00) → segment 11, raw offset 3 KB
• Negative offset = 3 KB − 4 KB (max segment size) = −1 KB
• Physical = 28 KB + (−1 KB) = 27 KB
• Bounds: |negative offset| must be within the segment’s current size

Support for sharing

Protection bits per segment (read / write / execute). Set code to read-execute only → the same physical code can be shared across processes while each still sees a private address space (Figure 16.5).

Writes to read-only, or execute from non-executable → exception.

Fine-grained vs coarse-grained

Style	Idea	Example
Coarse	Few large segments (code, heap, stack)	This chapter’s model
Fine	Many smaller segments + segment table in memory	Multics [CV65, DD68], Burroughs B5000 [RK68]

Fine-grained systems expected compilers to chop programs into many segments so the OS could track usage more precisely.

OS support

1. Context switch — save/restore all segment registers for the process.
2. Free-space management — segments are variable-sized; physical memory fills with holes (external fragmentation, Figure 16.6).

Example: 24 KB free total, but in three non-contiguous chunks → a 20 KB request fails.

Approach	Idea	Cost
Compaction	Stop processes, copy segments together, update bases	Expensive (memory + CPU)
Free-list policies	Best-fit, worst-fit, first-fit, buddy [K68], …	Still cannot eliminate external fragmentation

If 1000 solutions exist, no great one does

Many allocator algorithms exist because there is no best fix for external fragmentation. The real escape (later): never allocate variable-sized chunks — paging.

Interactive

Try: sparse physical layout · code/heap/stack translations · external fragmentation vs compaction.

Check your understanding

Quiz

Segmentation

1 / 6

Segmentation improves on single base/bounds mainly by…

Pick an answer to see if you are right.

Coding challenges

Homework lab: segmentation.py

Use the OSTEP segmentation homework (segmentation.py). Predict translations before -c.

Lab

Homework: segmentation.py

0/5 started

Loading lab…

Summary

Idea	One line
Segments	Code / heap / stack each have base + bounds
Sparse spaces	Don’t allocate physical gap between heap and stack
Explicit select	Top bits → segment register
Stack	Negative growth needs extra MMU bit
Sharing	Read-only code segments mapped into many ASes
Cost	External fragmentation; compaction expensive
Limit	Still not flexible enough for sparse heaps → paging

Previous: Address Translation

Next: Free-Space Management — split, coalesce, and allocation policies.

Further Reading

• Remzi & Andrea Arpaci-Dusseau — Operating Systems: Three Easy Pieces Ch. 16
• OSTEP vm-segmentation PDF
• OSTEP segmentation.py homework
• Wilson et al. [W+95] — allocator survey; Randell [R69] — fragmentation