Segmentation Concepts

When you write a program, you don't think of memory as a flat, undifferentiated array of bytes. You think in terms of structure: your code goes in one place, your global variables in another, your stack grows downward, your heap grows upward, and your dynamically loaded libraries occupy their own regions. This is the programmer's natural view of memory—organized, structured, and meaningful.

But paging, despite its elegance in solving fragmentation, imposes a fundamentally different view. To a paging system, memory is a uniform collection of fixed-size pages—there's no distinction between a page holding code and one holding data. The logical structure of your program is invisible to the hardware.

Segmentation bridges this gap. It organizes memory into logical segments—variable-sized blocks that correspond to the meaningful units of a program. Each segment represents a complete, logically distinct unit: the main program's code, a library module, a symbol table, a stack, or a heap. This alignment between memory organization and program structure is what makes segmentation compelling.

A logical segment is a contiguous block of memory that represents a complete, meaningful unit of a program. Unlike pages, which are arbitrary fixed-size chunks created for hardware convenience, segments correspond to the logical divisions that programmers naturally create when writing software.

Consider a typical C program. When compiled and loaded, it consists of several distinct logical units:

• Text segment: The compiled machine code (instructions)
• Data segment: Initialized global and static variables
• BSS segment: Uninitialized global and static variables
• Heap segment: Dynamically allocated memory (malloc/free)
• Stack segment: Local variables, function call frames, return addresses
• Shared library segments: Code and data for dynamically linked libraries

Each of these is a logical segment—a coherent unit with its own purpose, access patterns, and lifetime. The key insight of segmentation is that memory management should respect these logical boundaries.

The Formal Definition:

Formally, a segment is defined by a tuple (segment_number, base_address, limit). The segment number uniquely identifies the segment within the process's address space. The base address indicates where the segment begins in physical memory. The limit specifies the segment's size, ensuring access remains within bounds.

An address in a segmented system is a two-component address: (segment_number, offset). To access memory, the hardware:

1. Uses the segment number to look up the segment's base and limit
2. Checks that the offset is less than the limit (bounds check)
3. Computes the physical address: base + offset

This two-dimensional addressing scheme is fundamental to how segmentation represents the programmer's view of memory.

Segmentation emerged in the 1960s as computer scientists grappled with fundamental questions about memory organization. The systems of that era faced challenges that made segmentation a natural solution.

The Problem with Flat Address Spaces

Early computers used flat, one-dimensional address spaces. A program was loaded starting at some base address, and all addresses were relative to that base. This simplicity came with significant problems:

• No logical structure: The hardware couldn't distinguish code from data, making protection difficult
• Relocation complexity: Moving a program in memory required patching all internal addresses
• Sharing difficulty: Two programs couldn't easily share a library without duplicating it entirely
• Programming burden: Programmers had to manually calculate offsets across module boundaries

The Multics Vision

The most influential early segmented system was Multics (Multiplexed Information and Computing Service), developed at MIT starting in 1964. Multics introduced a revolutionary concept: treat all of memory as a collection of named segments that persist independently of processes.

In Multics:

• Every file was a segment that could be mapped directly into memory
• Programs consisted of multiple segments that could be shared
• Each segment had individual access controls
• Segments could grow dynamically as needed
• The distinction between memory and files blurred—a radical idea

This vision was so ambitious that Multics was considered overengineered by some, leading Ken Thompson and Dennis Ritchie to create Unix as a simpler alternative. Yet the concepts pioneered by Multics—segments with attributes, protection domains, and the unification of files and memory—remain influential today.

Understanding the distinction between segments and pages is crucial for grasping why both exist and how they can complement each other. These two approaches to memory organization represent fundamentally different philosophies.

The Philosophical Divide

The segment-page dichotomy reflects a deeper tension in systems design: logical organization vs. physical efficiency.

Segmentation says: "Memory should be organized the way programmers think. Give each logical unit its own space, let it grow as needed, protect it according to its purpose."

Paging says: "Memory should be organized for efficient use. Divide everything into uniform chunks that can be shuffled, swapped, and managed without fragmentation."

Neither view is wrong—they're solving different problems. The insight of modern systems is that they can be combined: use segmentation at the logical level (for protection, sharing, and programmer convenience) and paging at the physical level (for memory management efficiency).

Where Each Excels:

In a segmented memory system, every address consists of two components: a segment selector (or segment number) and an offset within that segment. This two-dimensional addressing is fundamental to how segmentation works.

Advantages of Two-Dimensional Addressing

1. Natural Separation: Different segments occupy different address spaces. A reference to "segment 2, offset 100" and "segment 7, offset 100" access completely different memory locations, even though the offsets are identical.

2. Independent Relocation: Each segment can be moved in physical memory independently. Only the segment table entry needs updating; all offsets within the segment remain valid.

3. Natural Bounds Checking: Each segment has an associated limit. Any access beyond this limit generates a hardware trap, catching buffer overflows and pointer errors at the source.

4. Meaningful Addresses: Addresses carry semantic information. "Code segment, offset X" means instruction at position X. "Stack segment, offset Y" means stack location Y. This aids debugging and security.

The Translation Process

When a program issues a memory reference, the following occurs:

1. The CPU extracts the segment number from the address
2. The segment number indexes into the segment table (we'll cover this in detail later)
3. The segment table entry provides: base address, limit, and permissions
4. Hardware compares offset against limit
5. If offset ≥ limit: segmentation fault (trap to OS)
6. If permissions don't allow the access type: protection fault
7. If valid: physical_address = base + offset

The fundamental insight of segmentation is that programs are not amorphous blobs of data—they have structure. Segmentation makes this structure visible to the hardware, enabling memory management that respects the program's logical organization.

A Typical Program's Segment Structure:

When a program is compiled and linked, it naturally divides into segments that reflect different purposes and access patterns:

Why This Structure Matters for Memory Management:

1. Different Protection Requirements

   • Code should be executable but not writable (prevents code injection)
   • Data should be readable and writable but not executable (prevents data execution attacks)
   • Stack should be non-executable on modern systems
   • Read-only data should be read-only

2. Different Sharing Potential

   • Code segments can be shared among all processes running the same program
   • Read-only data can be shared similarly
   • Stack and heap are per-process and must never be shared
   • Shared library code is shared among all processes using that library

3. Different Growth Patterns

   • Code and data segments don't grow during execution
   • Heap grows dynamically with allocations
   • Stack grows and shrinks with function calls
   • The system must accommodate these patterns

4. Different Lifetime Requirements

   • A library segment might be loaded when first needed and shared indefinitely
   • A process's private pages are released when the process terminates
   • Some segments might be lazily loaded (loaded only when accessed)

One of segmentation's most elegant features is how naturally it enables memory sharing. Because segments correspond to logical program units, sharing segments means sharing meaningful components—not arbitrary pages that happen to overlap.

The Sharing Scenario:

Consider 50 users all running the same text editor. Without sharing:

• 50 copies of identical code in memory
• 50 copies of identical read-only data
• Massive memory waste

With segment sharing:

• ONE copy of the code segment, referenced by all 50 processes
• ONE copy of read-only data, shared by all
• Each process has its own stack and heap segments (private data)
• Memory savings: potentially 90% or more

How Sharing Works:

1. Segment Table Entries Point to Same Physical Memory

   • Each process has its own segment table
   • For shared segments, multiple segment table entries point to the same physical base address
   • Each process can have different permissions (e.g., read-only in one, read-write in another)

2. Reference Counting

   • The OS tracks how many processes reference each shared segment
   • When a process terminates, it decrements the reference count
   • Only when the count reaches zero is the segment physically deallocated

3. Copy-on-Write for Data Segments

   • Initially, even writable segments can be shared (marked read-only)
   • When a process tries to write, a segment fault occurs
   • The OS creates a private copy for that process
   • This optimization delays copying until absolutely necessary

What Can Be Shared:

Protection in a segmented system is remarkably natural because access control aligns with program structure. Each segment can have its own access permissions, and those permissions make semantic sense.

Segment-Level Protection Attributes:

Protection Scenarios:

Scenario 1: Preventing Code Injection

// Attacker tries to execute data as code
// Data segment has permissions: Read, Write, NO Execute
// Hardware blocks execution attempt → Protection Fault

Scenario 2: Preventing Code Modification

// Bug or attack tries to overwrite code
// Code segment has permissions: Read, Execute, NO Write
// Hardware blocks write attempt → Protection Fault

Scenario 3: Protecting Kernel Segments

// User process tries to access kernel data
// Kernel segment DPL = 0, User process CPL = 3
// DPL < CPL → General Protection Fault

Scenario 4: Stack Smashing Protection

// Buffer overflow on stack injects code
// Stack segment: Read, Write, NO Execute
// Even if injected, code cannot execute

These protections happen in hardware at every memory access, with no software overhead. The segment descriptor is cached in the segment register, so protection checks add zero cycles to most memory operations.

You might wonder: if paging solved fragmentation so elegantly, why do modern systems still use segments? The answer is nuanced. Pure segmentation has largely given way to paging, but segmentation concepts persist in important ways.

Current State of Segmentation:

Why Segmentation Retreated:

1. Implementation Complexity: Managing variable-size segments is harder than uniform pages
2. External Fragmentation: Unavoidable without compaction, which is expensive
3. Flat Memory Models: Programmers preferred simpler flat address spaces
4. 64-bit Addressing: With 64-bit virtual addresses, address space is practically unlimited; no need for segments to extend range
5. Page-Based Virtual Memory: Paging handles swapping elegantly; segment swapping is coarser

Where Segmentation Concepts Survive:

1. ELF Program Headers: Executables still define segments (loader maps to virtual memory)
2. Memory Protection: Even without hardware segments, regions have different permissions
3. Thread-Local Storage (TLS): x86-64 uses FS/GS segment registers for per-thread data
4. Address Space Layout: Programs still conceptually have text, data, heap, stack
5. Virtual Memory Regions: Linux's vm_area_struct and Windows's VAD trees track contiguous regions with segment-like properties
6. Language Runtimes: Managed languages often use segment-like concepts internally

This page has provided a comprehensive exploration of logical segments as the foundational concept of memory segmentation. Let's consolidate the key insights:

What's Next:

With the theoretical foundation established, the next page examines the specific segment types found in typical programs: code segments, data segments, and stack segments. We'll explore how these segments differ in their contents, access patterns, and management requirements—understanding that forms the basis for practical segmentation implementation.