Segmentation

Waste of a Single Base-and-Bounds Pair

Relocating a whole virtual address space as one contiguous block still consumes physical RAM for the unused gap between heap and stack. On a 32-bit machine a typical program uses only megabytes yet the unused hole can be gigabytes, making the scheme both wasteful and inflexible.

Independent Base and Limit per Segment

The MMU now holds a separate base and limit for every logical segment. The OS may therefore locate code, heap and stack in completely different physical regions, allocating frames only for bytes that are actually referenced.

Segment Selection by High-Order Bits

The uppermost bits of a virtual address select which segment registers to use; the remaining bits form the offset. Hardware first compares the offset against the limit and raises a fault on overflow, otherwise adds the chosen base to produce the physical address.

Growth and External Fragmentation

Unused virtual ranges no longer occupy RAM, yet enlarging a segment still requires a sufficiently large contiguous physical hole. Over time physical memory becomes riddled with irregular free fragments, the classic remaining challenge of segmentation.

Pitfalls

• Adding the entire virtual address to the base instead of first extracting the offset
• Using high-order bits for segment selection permanently caps the maximum size of every segment

Minimum C11 · complete program · Download .c

#include <stdio.h>
#include <stdint.h>

int main(void) {
    const uint32_t base[3] = {32u * 1024, 34u * 1024, 28u * 1024};
    const uint32_t bounds[3] = {2u * 1024, 3u * 1024, 2u * 1024};
    const char *names[3] = {"code", "heap", "stack"};
    const uint32_t vas[3] = {100, 4200, 7168};
    for (int i = 0; i < 3; i++) {
        uint32_t va = vas[i];
        uint32_t seg = (va >> 12) & 3u;
        uint32_t offset = va & 0xFFFu;
        printf("VA %u (0x%x): ", va, va);
        if (seg > 2u) {
            printf("invalid segment\n");
            continue;
        }
        if (offset >= bounds[seg]) {
            printf("segmentation fault (offset %u >= %u in %s)\n",
                   offset, bounds[seg], names[seg]);
        } else {
            uint32_t pa = base[seg] + offset;
            printf("segment %s, offset %u -> PA %u\n",
                   names[seg], offset, pa);
        }
    }
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-16-segmentation.c -o example && ./example

Expected result

VA 100 (0x64): segment code, offset 100 -> PA 32868
VA 4200 (0x1068): segment heap, offset 104 -> PA 34920
VA 7168 (0x1c00): segmentation fault (offset 3072 >= 3072 in heap)

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

A 14-bit VA 0x0500 whose top two bits select the segment. Code base is 32768 and size is 2048. Give the physical address or state whether it faults.

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.