Combined Approach - Segmentation with Paging | OneNoughtOne

0/236

Operating SystemsSegmentation with Paging

Segmentation with Paging

LevelIntermediate

Duration90 mins

TopicSegmentation with Paging

1 / 5

Combined Approach

The Best of Both Worlds

Throughout our exploration of memory management, we've encountered two fundamentally different approaches: segmentation and paging. Each offers compelling advantages but comes with significant trade-offs. Segmentation provides a natural, programmer-friendly view of memory organized around logical units—code, data, stack—but suffers from external fragmentation. Paging eliminates external fragmentation through fixed-size allocation but loses the logical structure that makes programming intuitive.

What if we could combine these approaches? What if we could preserve segmentation's logical organization while eliminating its fragmentation problems through paging? This is precisely what the combined segmentation-paging approach achieves—and it's not merely theoretical. Real-world processors, most notably Intel's x86 architecture, have implemented this hybrid scheme for decades.

What You Will Learn

By the end of this page, you will understand why combining segmentation with paging provides superior memory management, how the two-level address translation works, the architectural motivations behind this design, and why this approach dominated computing for an entire era.

The Fundamental Problem: Why Neither Approach Alone Suffices

Before diving into the combined approach, let's crystallize why neither pure segmentation nor pure paging fully addresses modern memory management requirements. Understanding these limitations reveals why the hybrid approach became necessary.

Pure Segmentation's Achilles Heel:

Segmentation maps beautifully to how programmers think about programs. A program naturally divides into distinct segments: the code segment containing executable instructions, the data segment holding global variables, the heap for dynamic allocation, and the stack for function calls. Each segment can grow independently, have different protection attributes, and be shared selectively with other processes.

However, this elegance comes at a severe cost: external fragmentation. As processes are created, segments allocated, and processes terminated, memory becomes riddled with scattered holes. Even when total free memory exceeds a segment's requirements, no contiguous region may be large enough to accommodate it. The 50-percent rule suggests that one-third of memory may be wasted to fragmentation—an unacceptable overhead for resource-constrained systems.

Memory Management Approach Comparison
Characteristic	Pure Segmentation	Pure Paging	Combined Approach
Logical Organization	Excellent - natural program structure	Poor - flat address space	Excellent - preserves segments
External Fragmentation	Severe - variable-size segments	None - fixed-size pages	None - segments are paged
Internal Fragmentation	Minimal - exact allocation	Moderate - last page waste	Moderate - same as paging
Protection Granularity	Per-segment - natural boundaries	Per-page - may split logical units	Per-segment and per-page
Sharing Support	Excellent - share whole segments	Good - share pages	Excellent - share paged segments
Address Translation Complexity	Single lookup	Single lookup + TLB	Two lookups + TLB
Hardware Support Required	Segment registers and tables	Page tables and TLB	Both mechanisms integrated

Pure Paging's Limitations:

Paging solves the fragmentation problem elegantly. By dividing both logical and physical memory into fixed-size units (pages and frames), external fragmentation becomes impossible. Any free frame can accommodate any page. Memory allocation reduces to maintaining a simple free frame list.

But this simplicity sacrifices logical structure. In a pure paging system, the address space is a flat, undifferentiated sequence of pages. There's no natural concept of "the code region" or "the stack segment." Protection must be applied page-by-page, potentially requiring thousands of individual permission settings. Sharing becomes granular at the page level, making it awkward to share logical program units that span multiple pages.

Moreover, pure paging loses the ability to detect certain classes of errors. With segmentation, accessing beyond a segment's limit triggers an immediate trap. With pure paging, overrunning the stack might silently corrupt the heap if they happen to be adjacent pages in the flat address space.

The Design Tension

This creates a fundamental design tension: we want the logical organization and protection semantics of segmentation, but we need the fragmentation-free allocation of paging. The combined approach resolves this tension by using segmentation at the logical level while implementing physical allocation through paging.

The Combined Architecture: Segments Divided into Pages

The combined segmentation-paging approach is conceptually elegant: each segment is divided into pages, and those pages are mapped to physical frames independently. The programmer sees a segmented memory model with distinct code, data, and stack segments. But beneath this abstraction, the operating system and hardware work together to place each segment's pages into arbitrary physical frames.

Conceptual Model:

Consider a process with three segments:

Code segment: 12 KB (3 pages)
Data segment: 20 KB (5 pages)
Stack segment: 8 KB (2 pages)

In pure segmentation, each segment would occupy contiguous physical memory. Finding three separate contiguous regions of 12 KB, 20 KB, and 8 KB becomes increasingly difficult as memory fragments.

In the combined approach, each segment has its own page table. The code segment's 3 pages might map to frames 42, 17, and 203. The data segment's 5 pages might map to frames 88, 12, 7, 156, and 91. It doesn't matter that these frames are scattered throughout physical memory—from the programmer's perspective, each segment remains a contiguous, logically organized unit.

Converting Mermaid diagram...

The Two-Level Structure:

The combined system maintains two levels of memory management data structures:

Level 1 - Segment Table: Contains one entry per segment in the process. Each entry includes:

Segment base: Points to that segment's page table (not to physical memory)
Segment limit: Maximum offset within the segment (in pages or bytes)
Protection bits: Read/write/execute permissions for the entire segment
Other flags: Presence bit, accessed bit, etc.

Level 2 - Per-Segment Page Tables: Each segment has its own page table containing entries for all pages in that segment. Each page table entry includes:

Frame number: Physical frame where this page resides
Valid bit: Whether the page is currently in memory
Protection bits: Page-level permissions (may refine segment permissions)
Dirty bit: Whether the page has been modified
Reference bit: Whether the page has been accessed recently

This two-level structure provides remarkable flexibility. Segments of different sizes each have appropriately-sized page tables. Large segments have large page tables; small segments have small ones. No memory is wasted on page table entries for non-existent pages.

Key Insight: Decoupling Logical and Physical

The profound insight of the combined approach is the complete decoupling of logical organization from physical placement. The segment table describes the logical structure (which segments exist, their sizes, their permissions). The page tables handle physical placement (where each piece actually resides in memory). This separation of concerns is a hallmark of elegant systems design.

The Address Translation Process

In the combined system, a logical address has three components, and translation requires multiple steps. Understanding this process in detail is essential for grasping both the power and the performance implications of the combined approach.

Logical Address Format:

A logical address in the combined system is structured as:

| Segment Number (s bits) | Page Number (p bits) | Offset (d bits) |

For example, with a 32-bit logical address:

Segment Number: 4 bits → supports up to 16 segments per process
Page Number: 12 bits → supports up to 4096 pages per segment
Offset: 16 bits → page size of 64 KB (2^16 bytes)

Or a more typical configuration:

Segment Number: 8 bits → up to 256 segments
Page Number: 10 bits → up to 1024 pages per segment
Offset: 12 bits → 4 KB pages

Address Translation Algorithm
Pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// Combined Segmentation-Paging Address Translation
 
function translate_address(logical_address):
    // Step 1: Extract address components
    segment_number = extract_bits(logical_address, s_start, s_end)
    page_number = extract_bits(logical_address, p_start, p_end)
    offset = extract_bits(logical_address, 0, offset_bits - 1)
    
    // Step 2: Access segment table (indexed by segment number)
    segment_entry = segment_table[segment_number]
    
    // Step 3: Check segment validity
    if not segment_entry.present:
        raise SEGMENT_NOT_PRESENT_FAULT
    
    // Step 4: Check segment bounds
    // Limit may be in pages or bytes depending on granularity bit
    effective_limit = segment_entry.limit
    if segment_entry.granularity == PAGE:
        effective_limit = segment_entry.limit * PAGE_SIZE
    
    if (page_number * PAGE_SIZE + offset) > effective_limit:
        raise SEGMENT_LIMIT_EXCEEDED_FAULT
    
    // Step 5: Check segment-level permissions
    if operation == WRITE and not segment_entry.writable:
        raise SEGMENT_PROTECTION_FAULT
    if operation == EXECUTE and not segment_entry.executable:
        raise SEGMENT_PROTECTION_FAULT
    
    // Step 6: Get page table base from segment entry
    page_table_base = segment_entry.page_table_base
    
    // Step 7: Access page table (indexed by page number within segment)
    page_entry = memory[page_table_base + page_number * PTE_SIZE]
    
    // Step 8: Check page validity
    if not page_entry.valid:
        raise PAGE_FAULT  // OS will load page from disk
    
    // Step 9: Check page-level permissions (may be more restrictive)
    if operation == WRITE and not page_entry.writable:
        raise PAGE_PROTECTION_FAULT
    
    // Step 10: Form physical address
    frame_number = page_entry.frame_number
    physical_address = (frame_number * PAGE_SIZE) + offset
    
    // Step 11: Update access bits
    page_entry.accessed = true
    if operation == WRITE:
        page_entry.dirty = true
    
    return physical_address
 
// Example translation
// Logical address: 0x02001A3C
// Format: |8-bit segment|10-bit page|14-bit offset|
// Segment = 0x02 = 2
// Page = 0x006 = 6
// Offset = 0x1A3C = 6716
 
// Result after lookup:
// Segment 2 → Page table at physical 0x00050000
// Page table entry 6 → Frame 0x00123
// Physical address = 0x00123000 + 0x1A3C = 0x00124A3C

Step-by-Step Translation Example:

Let's trace through a concrete example. Assume:

32-bit logical addresses
4 bits for segment number
16 bits for page number
12 bits for offset (4 KB pages)

Logical Address: 0x2003AFEC

Binary: 0010 | 0000 0000 0011 1010 | 1111 1110 1100

Step 1: Parse the address:

Segment number = 0010₂ = 2
Page number = 0000000000111010₂ = 58
Offset = 111111101100₂ = 4076

Step 2: Access segment table entry 2:

Segment present: Yes
Segment limit: 100 pages
Permissions: Read/Execute
Page table base address: 0x00500000

Step 3: Bounds check:

Page 58 < limit of 100 pages ✓
Offset 4076 < page size 4096 ✓

Step 4: Permission check:

Operation is READ, segment allows READ ✓

Step 5: Access page table at 0x00500000:

Page table entry for page 58 at offset 58 × 4 bytes = 232
Read PTE from 0x005000E8
PTE contains: Frame 0x00042, Valid=1, R/W=0

Step 6: Form physical address:

Physical address = 0x00042000 + 0xFEC = 0x00042FEC

Performance Concern: Multiple Memory Accesses

Notice that translating a single logical address requires TWO memory accesses: one to read the segment table entry and one to read the page table entry. Combined with the actual data access, every memory reference becomes three memory references. Without hardware optimization (TLB), this triples effective memory latency—an unacceptable performance penalty that must be addressed.

Protection and Sharing in the Combined Scheme

The combined approach provides exceptionally flexible protection and sharing mechanisms by offering protection controls at both the segment and page levels. This dual-level protection enables security policies that are both intuitive and precise.

Segment-Level Protection:

At the segment level, protection reflects the logical purpose of each memory region:

Code Segment: Execute + Read, No Write
- Prevents buffer overflow attacks from modifying executable code
- Allows reading constants embedded in code
Data Segment: Read + Write, No Execute
- Permits modification of global and static variables
- Prevents code injection attacks via data regions
Stack Segment: Read + Write, No Execute
- Allows function calls and local variable manipulation
- Prevents stack-based code execution (stack smashing attacks)
Shared Library Segment: Execute + Read, No Write
- Multiple processes can share the same physical library pages
- Modifications are prevented to ensure consistency

Two-Level Protection Matrix Example
Segment	Segment Permissions	Page Permissions	Effective Result
Code Page 0	R + X	R + X	Read + Execute allowed
Code Page 1	R + X	R only	Read only (page restricts)
Data Page 0	R + W	R + W	Read + Write allowed
Data Page 1	R + W	R only	Read only (guard page)
Stack Page 0	R + W	R + W	Read + Write allowed
Stack Guard	R + W	None (invalid)	Access trap (stack overflow detection)

Page-Level Protection Refinement:

Page-level permissions can only restrict, never expand, segment-level permissions. This creates a hierarchical protection model:

If the segment allows Read+Write+Execute but a page is marked Read-Only, the page is Read-Only
If the segment is marked No-Execute, no page within it can be executed regardless of page permissions
If a page is marked invalid, it cannot be accessed even if the segment is valid

This hierarchy allows fine-grained protection within logically coherent regions. For example, a data segment might have most pages as Read+Write, but include a read-only guard page at the boundary to detect buffer overruns.

Sharing Mechanisms:

The combined approach enables sharing at two levels with different trade-offs:

Segment-Level Sharing

•Multiple processes point segment table entries to the same page table
•All pages in the segment are automatically shared
•Ideal for sharing entire code segments (libraries)
•Changes to page table entries affect all sharing processes
•Simple management: share entire logical unit

Page-Level Sharing

•Individual page table entries point to the same frame
•Fine-grained: share specific pages, not entire segments
•Useful for copy-on-write implementations
•Enables partial sharing of data regions
•More complex management but greater flexibility

Sharing Example: Shared Library

Consider two processes both using the C standard library (libc):

Process A has segment 5 pointing to libc
Process B has segment 7 pointing to the same libc
Both segment table entries contain the same page table base address
All page table entries point to the same physical frames
Result: One copy of libc in physical memory, accessible to both processes

The key advantage is that each process can have a different segment number (5 vs. 7) based on their individual address space layout, yet they share the identical physical memory. This is achieved because the segment table entry contains a pointer to the page table, and both can point to the same page table.

Protection Ring Integration

In actual x86 implementations, segment-level protection integrates with the CPU's privilege ring system. Each segment has a Descriptor Privilege Level (DPL), and access is only permitted if the current privilege level (CPL) is equal to or more privileged than the DPL. This creates a comprehensive protection model spanning hardware privilege levels, segments, and pages.

Advantages and Trade-offs of the Combined Approach

The combined segmentation-paging approach represents a sophisticated engineering trade-off. It delivers significant benefits but at non-trivial costs. Understanding both sides of this equation is essential for appreciating both why it was adopted and why modern systems have evolved beyond it.

Definitive Advantages:

Benefits of Combined Segmentation-Paging

•Elimination of External Fragmentation: Since segments are divided into fixed-size pages, physical memory allocation never faces the fragmentation problems of pure segmentation. Any free frame can hold any page from any segment.
•Preservation of Logical Organization: Programmers and compilers continue to work with a segmented memory model. Separate code, data, and stack segments with independent protection remain first-class concepts.
•Flexible Segment Sizes: Segments can grow to arbitrary sizes (limited only by page table capacity) without requiring contiguous physical memory. A 100 MB segment poses no allocation challenge.
•Hierarchical Protection Model: Two levels of protection—segment and page—allow both coarse-grained policies (entire regions) and fine-grained controls (individual pages).
•Efficient Sharing: Both segment-level sharing (entire libraries) and page-level sharing (copy-on-write) are naturally supported.
•Virtual Memory Enablement: The page-level valid bits enable demand paging within the segmented model, bringing virtual memory benefits to segmented programs.
•Backward Compatibility: Programs written for pure segmentation continue to work; the paging layer is largely transparent to application code.

Significant Trade-offs:

Costs of Combined Segmentation-Paging

•Address Translation Complexity: Every memory access requires consulting both segment and page tables. Without TLB optimization, this doubles or triples effective memory latency.
•Memory Overhead: Maintaining both segment tables and per-segment page tables consumes more memory than either approach alone. Each segment, regardless of size, requires its own page table.
•Hardware Complexity: Processors must implement two translation mechanisms and integrate them coherently. This increases die area, power consumption, and validation complexity.
•TLB Design Challenges: The TLB must now cache combined segment+page translations or implement a two-level TLB hierarchy, increasing cache complexity.
•Internal Fragmentation Remains: Although external fragmentation is eliminated, the last page of each segment may be partially unused—and now this waste occurs for every segment independently.
•Operating System Complexity: The OS must manage both segment and page tables, handle faults from both levels, and coordinate between them.
•Context Switch Overhead: Switching between processes may require updating or flushing both segment and TLB state, potentially increasing context switch latency.

The Evolution Toward Pure Paging

These trade-offs explain why modern operating systems have largely moved to pure paging with flat address spaces. In contemporary x86-64 systems, segmentation is effectively disabled (all segments cover the entire address space), and memory management relies entirely on multi-level paging. The logical organization once provided by segments is now implemented through virtual memory mappings and protection attributes in page tables.

Historical Context: Why This Approach Emerged

The combined segmentation-paging approach didn't emerge in a vacuum. It resulted from specific historical circumstances, hardware limitations, and software requirements of its era. Understanding this context illuminates both its design and its eventual obsolescence.

The Intel 8086/8088 Legacy:

When IBM launched the PC in 1981 with the Intel 8088, it used pure segmentation with 16-bit segment registers addressing a 20-bit (1 MB) address space. Programs explicitly manipulated segment registers to access memory beyond 64 KB. An entire ecosystem of software—DOS, early Windows, countless applications—was built on this segmented model.

The 80286 Transition:

The 80286 (1982) introduced protected mode with proper segment-based memory protection, but it retained the segmented architecture. Protected mode segments had explicit limits and privilege levels, enabling multitasking and memory protection. However, important software continued to require real mode (8086 compatibility), creating a dual-mode architecture.

The 80386 Revolution:

The 80386 (1985) introduced paging alongside segmentation, creating the first mainstream combined system. Intel's engineers recognized that:

Existing software expected segmentation
Operating systems needed paging for efficient virtual memory
Both could coexist if paging was layered beneath segmentation

This pragmatic engineering decision allowed:

DOS programs to run in Virtual 8086 mode
Protected mode programs to use full segmentation
Modern operating systems to use paging for memory management
All three models to coexist on the same processor

Evolution of Intel x86 Memory Architecture
Processor	Year	Address Bits	Memory Model	Key Innovation
8086/8088	1978-79	20-bit (1 MB)	Pure Segmentation	Segment:offset addressing
80286	1982	24-bit (16 MB)	Protected Segmentation	Segment descriptors, privilege levels
80386	1985	32-bit (4 GB)	Segmentation + Paging	Page tables, combined translation
Pentium Pro	1995	32/36-bit	Segmentation + Paging	PAE (Physical Address Extension)
x86-64	2003	48/64-bit	Flat + Paging	Segmentation effectively disabled

Why Segments Mattered Then:

In the 1980s and early 1990s, segmentation provided tangible benefits:

Limited Compiler Technology: Compilers couldn't easily optimize for flat address spaces. Segmentation provided natural boundaries that matched compilation units.
Explicit Memory Management: Without sophisticated garbage collectors or memory allocators, programmers manually managed segments. The segment model matched their mental model.
Position-Independent Code Challenges: Creating truly position-independent code was difficult. Segments allowed code to be relocated by simply changing the segment base.
Object-Oriented Design Mapping: Early object-oriented systems mapped objects to segments naturally. Each object became a segment with its own protection.
Capability-Based Security Interest: Segment selectors functioned as capabilities—unforgeable tokens granting access to memory regions. This supported capability-based security research.

The Shift Away:

By the late 1990s, these advantages had eroded:

Compilers became sophisticated enough to handle flat address spaces efficiently
Position-independent code became standard through better compilation techniques
Capability-based security shifted to software-based implementations
The overhead of segment management outweighed its benefits
Portability became crucial, and other architectures (RISC) used flat models

Modern x86-64 acknowledges this shift: while segment registers still exist for compatibility, the operating system sets all segment bases to 0 and limits to maximum, effectively creating a flat address space managed purely through paging.

Lessons for System Design

The rise and fall of combined segmentation-paging illustrates a fundamental principle: the best solutions balance current needs against future flexibility. Intel's engineers made pragmatic choices that served their era well, enabling a smooth transition from segmented DOS programs to modern flat-address systems. The combined mode served as a bridge technology, not a destination.

Summary: The Combined Approach

We've explored the combined segmentation-paging approach in depth, understanding both its elegant design and its practical trade-offs. Let's consolidate the key insights:

Key Takeaways

•Segments are divided into pages — Each segment has its own page table, allowing non-contiguous physical allocation while preserving logical segment organization.
•Two-level address translation — A logical address contains segment number, page number, and offset. Translation requires accessing both segment table and page table.
•Hierarchical protection — Segment-level permissions define coarse access rights; page-level permissions refine but cannot expand them.
•External fragmentation eliminated — Paging beneath segments removes the fragmentation problems of pure segmentation while keeping the logical model.
•Sharing at multiple levels — Entire segments can be shared via segment table entries; individual pages can be shared via page table entries.
•Historical significance — This approach dominated x86 computing for nearly two decades, bridging segmented DOS to modern flat-address systems.
•Evolution continues — Modern x86-64 effectively disables segmentation, relying on pure paging, but the combined mode remains available for compatibility.

What's Next:

The following pages dive deeper into specific aspects of combined segmentation-paging:

Intel x86 Example: Detailed examination of how x86 protected mode implements combined memory management
Segment Descriptors: The structure and fields of x86 segment descriptors and their role in protection
Paged Segments: How segments are divided into pages and managed by the operating system
Modern Implementations: How contemporary systems handle the legacy of combined memory management

Page Complete

You now understand the fundamental architecture of combined segmentation-paging, why it was developed, how address translation works through both levels, and the trade-offs that led to its eventual deprecation. This foundation prepares you to examine the concrete Intel x86 implementation in the next page.