Address Spaces & Segmentation

Here is the big idea, stated plainly: no process is allowed to see physical memory directly any more. Every address your program computes — the address of a variable, a function, a buffer you just malloc’d — is a virtual address, meaningful only inside your process. When the CPU actually goes to fetch or store at that address, a translation step converts it into a physical address, the real location in the RAM chips. Your program never learns the physical address and does not need to.

The payoff is that we can hand every process the same beautiful gift: a private address space that begins at 0 and runs up to some maximum, laid out exactly the same way every time — code down low, then initialised data, then the heap growing up, and the stack growing down from the top. Every process believes it owns this whole clean space by itself, starting at zero. Two processes can both use the address 0x400, and there is no conflict, because those are two different virtual addresses that translate to two different physical locations.

This is why the distinction between a logical (virtual) address and a physical address is the single most important vocabulary in this part of the course. A logical address is what your code sees and what the CPU emits. A physical address is what travels down the memory bus to the RAM. The job of everything that follows — segmentation here, paging next — is to build the machinery that maps one onto the other, correctly and fast, on every access.

Address space

The full set of addresses a process can name — its private view of memory, conventionally starting at 0 and running to a maximum.

Logical / virtual address

The address your program uses and the CPU generates. It is relative to the process, not to the physical machine.

Physical address

The actual location in the RAM hardware. Only the OS and hardware ever see these.

Address translation

The per-access conversion of a virtual address into a physical one, done in hardware while the program runs.

Once you interpose translation between programs and RAM, three hard problems from the previous chapter dissolve almost as side effects. It is worth being explicit about each, because together they are the contract that the rest of Part D exists to deliver.

The first is isolation. Because a process can only ever name addresses inside its own space, and the translation machinery simply has no mapping for anyone else’s memory, one process physically cannot reach another’s data — not by accident, not on purpose. The wall is not a rule the program is politely asked to obey; it is that the addresses to cross the wall do not exist for that process. This is the mechanism behind the user/kernel and process-to-process protection we have leaned on since the very first chapters.

The second is relocation for free. In ch20 a program had to be loaded at a known spot, or patched up as it moved. Now the program is written entirely in virtual addresses starting at 0, and where its bytes actually sit in RAM is purely a matter of what the translation says. The OS can place a process anywhere there is room, and even move it, without changing a single instruction — the program is blissfully unaware. Loading becomes trivial: pick any free physical space and set up the mapping.

The third is the illusion of abundant, contiguous memory. A program can be handed one long, tidy, contiguous address space even when the physical memory backing it is a patchwork of scattered chunks. The program sees a smooth stretch from here to there; the mapping fans those addresses out across whatever physical pieces happen to be free. That single trick is what will later let us over-commit memory and page pieces out to disk — but even now, before any of that, it means the OS is no longer forced to find one big contiguous physical hole for every program.

Isolation

A process cannot name, read, or corrupt another process’s memory, because the mappings to reach it simply do not exist in its address space.

Relocation

The program is written in virtual addresses; its physical placement is decided (and can be changed) entirely by the mapping, with no edits to the code.

Contiguity illusion

A contiguous virtual space can be backed by non-contiguous physical memory, so programs get a simple view of a messy resource.

Translation cannot be done in software on the side — it has to happen on every single memory access, billions of times a second, so it lives in hardware. The unit responsible is the Memory Management Unit, or MMU, which sits on the CPU between the core that generates addresses and the memory bus. Every virtual address the CPU produces flows through the MMU, which turns it into a physical address before it ever reaches RAM. Your program does nothing to invoke this; it is automatic and invisible.

The simplest possible MMU is one you have already met: the base-and-limit pair from ch20. Interpreted as a translator, its rule is two steps. First, check that the virtual address is within bounds — if it is greater than or equal to the limit, the access is illegal and the MMU raises a trap into the kernel instead of touching memory. Second, if it is in bounds, add the base register to it, and the sum is the physical address. Two operations, a compare and an add, cheap enough to do in hardware without slowing the CPU down.

That tiny scheme already delivers the whole contract. The program uses virtual addresses starting at 0; base handles relocation by shifting them to wherever the physical slab lives; limit enforces isolation by refusing any address that reaches past the slab. The OS keeps a base and limit value for every process, and part of a context switch is loading that process’s base and limit into the MMU’s registers — which is precisely how the same virtual address means different physical memory for different processes.

• ▸The CPU generates a virtual address for a load, store, or instruction fetch.
• ▸The MMU checks it against the limit; an out-of-bounds address becomes a trap into the kernel, not a memory access.
• ▸For a valid address, the MMU computes the physical address (in the simplest scheme, base + virtual).
• ▸The physical address goes out on the memory bus; the program never sees it.
• ▸On a context switch the OS reloads the MMU’s translation state for the newly running process.

A single base-and-limit forces the whole process into one contiguous block, which is wasteful. Think about the real layout of a process from ch07: a code segment that never changes size, a data segment, a heap that grows upward, and a stack that grows downward. Between the top of the heap and the top of the stack sits a vast expanse of addresses that are valid but empty. Under one base-and-limit, that empty middle has to be backed by real, reserved memory. That is absurd.

Segmentation’s insight is to give each of those logical pieces its own base and limit. Instead of one slab, the address space is a collection of segments — commonly code, data, heap, and stack — and each segment is placed independently in physical memory with its own size. The empty gap between heap and stack simply is not part of any segment, so it costs nothing. Beautifully, this matches how programmers already think about a program: not as one undifferentiated blob, but as distinct regions with distinct purposes.

To make this work, a virtual address is now read as two parts: a segment number that selects which segment, and an offset into that segment. The MMU keeps a segment table — one row per segment holding that segment’s base, its limit, and (as we will see next) its permission bits. Translating an address means: use the segment number to pick the row, check that the offset is below that segment’s limit, and if so add the segment’s base to the offset to get the physical address. It is base-and-limit again, but now chosen per segment.

// virtual address split into (segment number, offset)
seg    = virtual_addr >> OFFSET_BITS      // high bits pick the segment
offset = virtual_addr & OFFSET_MASK       // low bits are the offset

row = segment_table[seg]                  // base, limit, perms

if (offset >= row.limit)
    trap(SEGMENTATION_FAULT)              // offset past end of segment

physical_addr = row.base + offset         // the real RAM location

Notice what this buys us beyond saving the empty middle. Each segment can grow independently up to its own limit; the heap can expand without caring where the stack is, because they are separate rows with separate bases. And because segments are placed independently, the OS has more, smaller pieces to fit into physical memory rather than one giant slab — usually easier to satisfy. We are still, however, dealing in variable-sized contiguous chunks, and hold that thought, because it comes back to bite us shortly.

Segment

A logically distinct region of the address space (code, data, heap, stack), placed independently in physical memory with its own base and size.

Segment table

The per-process table the MMU consults; one row per segment, holding base, limit, and permission bits.

Segment + offset

A virtual address split into a segment selector (which region) and an offset (how far into it), translated via the table.

Per-segment limit

Each segment enforces its own bounds, so an offset past the end of one segment faults without affecting the others.

Because each segment already has its own row in the table, it is almost free to attach a few permission bits to that row: may this segment be read, written, executed? This is where segmentation stops being merely an accounting convenience and becomes a genuine protection mechanism, and the permissions map cleanly onto what each region is actually for.

• ▸The code segment is read and execute, but not write — so a bug (or an attacker) cannot overwrite your instructions while they run.
• ▸The data and heap segments are read and write, but not execute — so injected data cannot be run as code.
• ▸The stack is read and write, not execute — the same defence, which is exactly what modern "no-execute stack" protections enforce.

The MMU checks these bits on the same pass as the bounds check, at no extra cost. An instruction fetch from a non-executable segment, or a store into a read-only segment, is caught in hardware and turned into a trap before it can do any damage. Every memory access is thus checked for both "are you inside the segment?" and "are you allowed to do this here?" on every single reference.

Sharing falls out of the same design just as naturally. Because a segment is identified by a table row, two processes can have rows whose base points at the very same physical region. The classic case is a shared library like the C runtime: its code is read-only and identical for everyone, so there is no reason to keep a copy per process. Point every process’s code-library segment at one physical copy and you save that memory across the entire system. It is safe precisely because the shared segment is read-only — no process can modify what the others depend on.

Permission bits (r/w/x)

Per-segment flags checked by the MMU on every access: readable, writable, executable. A violation traps into the kernel.

W^X (write xor execute)

The policy that no segment is both writable and executable — the reason code is not writable and the stack is not executable.

Shared segment

One physical region reached by segment-table rows in multiple processes; used for read-only shared code to save memory.

Segmentation carries the same disease we diagnosed with ch20’s variable partitions, and for the same reason: segments are variable-sized contiguous chunks. As processes start and exit, and as segments are placed and freed, physical memory fills with holes of assorted sizes between the segments still in use. This scattering of free space into unusable gaps is external fragmentation, and it is the Achilles heel of every variable-size allocation scheme.

The painful part is how the failure shows up. You may have plenty of free memory in total — more than enough to hold a new segment — and still be unable to load it, because that free memory is split across several holes and no single hole is large enough to hold the segment contiguously. The requirement that each segment be one continuous physical region is exactly what turns "enough free memory" into "cannot allocate". Choosing which hole to use (first-fit, best-fit, worst-fit) only shuffles the problem around; it never removes it.

There is a cure — compaction — but it is brutal. To reclaim the holes you slide the live segments together to squeeze the free space into one big region, which means physically copying potentially large amounts of memory and then updating every affected segment’s base in the segment tables. That is slow, and during it the affected processes cannot run. Compaction treats the symptom at real cost; it does not touch the underlying cause.

So designers asked the question that defines the next chapter: what if we banned variable sizes entirely? If every chunk of memory were exactly the same fixed size, then any free chunk could hold any piece of any process, and a request could always be satisfied by any free chunk — external fragmentation would be impossible by construction. That fixed-size chunk is called a page, and pursuing this idea is the whole of the paging chapter to come.

External fragmentation

Free memory broken into scattered holes between allocations, so a request can fail even when the total free memory would suffice.

Compaction

Relocating live segments to merge scattered holes into one region; effective but expensive, since memory must be copied and bases updated.

The root cause

Variable-sized contiguous allocation. Remove the "variable" and "contiguous" and the fragmentation problem removes itself.

Lay the two schemes side by side. Segmentation gives variable-sized regions that map onto the logical structure of a program, which makes protection and sharing intuitive — a whole meaningful region at a time. Its cost is external fragmentation. Paging, the subject of the next chapter, chops memory into fixed-size pages: it cannot suffer external fragmentation, and its translation is uniform and simple, but a page boundary means nothing to the program, and each region wastes a little space at the end of its last page (internal fragmentation). The trade is real regions with messy memory versus tidy memory with meaningless boundaries.

History picked paging, and the clearest evidence is the x86 line itself. The original 8086 used segmentation out of necessity, to reach more memory than a 16-bit address could name. The 80286 and 386 kept segmentation but added paging alongside it, and operating systems increasingly leaned on paging and treated segmentation as a thin formality. By the time we reach x86-64 (long mode), the hardware essentially neutralises segmentation: for the main data and code segments the base is forced to 0 and the limit checks are disabled, so a virtual address passes through segmentation unchanged and paging does all the real translation. The segment registers still exist, but they no longer carve up your address space.

So why do we still study segmentation, and why does its name haunt every C programmer? Because the concept did not vanish — it flattened into paging, which inherited its protection idea (per-page permission bits instead of per-segment) while dropping its fragmentation problem. And the vocabulary stuck. When your program dereferences a bad pointer, the access has no valid mapping or violates the permissions the memory system enforces, the hardware raises a fault, and the kernel delivers the signal named SIGSEGV — a "segmentation fault". The historical name reaches straight back to the scheme in this chapter: an access that fell outside a legal segment. The mechanism today is usually paging, but the word is a fossil of segmentation.

Segmentation

Variable-size, program-meaningful regions; intuitive protection and sharing, but prone to external fragmentation.

Paging

Fixed-size pages; no external fragmentation and uniform translation, at the price of program-opaque boundaries and small internal waste.

x86-64 flattening

In long mode the main segment bases are 0 and limit checks are off, so segmentation is effectively bypassed and paging does the translation.

Segmentation fault (SIGSEGV)

The signal for an illegal memory access; the name is inherited from segmentation, though the enforcing mechanism today is usually the paging hardware.