Operating SystemsSegmentation with Paging

Segmentation with Paging

LevelIntermediate

Duration90 mins

TopicSegmentation with Paging

4 / 5

Paged Segments

Segments Meet Pages

We've established that combined segmentation-paging divides each segment into pages, which are then independently mapped to physical frames. But how does this actually work in practice? How does the hardware coordinate segment translation with page translation? How does the operating system manage per-segment page tables?

This page bridges the conceptual understanding from previous sections with practical implementation details. We'll trace exactly how a logical address flows through both translation stages, examine the data structures the OS must maintain, and understand the memory overhead and performance implications of paged segments.

The beauty of paged segments lies in their separation of concerns: segmentation handles logical organization and protection semantics, while paging handles physical memory allocation. Neither needs to know the internal workings of the other—they compose cleanly through the linear address interface.

What You Will Learn

By the end of this page, you will understand the complete segment-to-page translation pipeline, how operating systems structure per-segment page tables, the memory overhead of paged segments, and the techniques used to optimize paged segment management.

Two-Stage Address Translation Dissected

In combined segmentation-paging, address translation occurs in two distinct stages. Understanding how these stages connect is fundamental to grasping how paged segments work.

Stage 1: Segmentation (Logical → Linear)

The first stage converts a logical address (segment selector + offset) into a 32-bit linear address:

Logical Address: [Selector 16 bits] : [Offset 32 bits]
                       ↓
              Segment Descriptor
                 (from GDT/LDT)
                       ↓
            Base Address (32 bits)
                       ↓
          Linear Address = Base + Offset

Stage 2: Paging (Linear → Physical)

The second stage converts the 32-bit linear address into a physical address:

Linear Address:  [Directory 10 bits] | [Table 10 bits] | [Offset 12 bits]
                        ↓                    ↓                ↓
                 Page Directory        Page Table          Unchanged
                 Entry (PDE)          Entry (PTE)
                        ↓                    ↓
                 Page Table Base      Frame Number
                        ↓                    ↓
Physical = Frame × 4096 + Page Offset

Converting Mermaid diagram...

Key Insight: The Linear Address Space

The linear address space serves as the interface between segmentation and paging. From segmentation's perspective, it produces linear addresses. From paging's perspective, it consumes linear addresses. Neither system needs to know about the other:

Segmentation doesn't know about pages. It simply adds a base to an offset and produces a 32-bit linear address. Whether that address will be paged is irrelevant to the segment translation.
Paging doesn't know about segments. It receives a 32-bit linear address and translates it to physical. The fact that this address originated from segment translation is irrelevant to the paging logic.

This clean separation is crucial. It means:

An OS can use segmentation without paging (CR0.PG = 0)
An OS can effectively disable segmentation and use only paging (flat segments with base=0)
An OS can use both simultaneously (combined mode)
The paging code doesn't need segment-specific logic

Linear Address = Virtual Address

In x86 terminology, the linear address is sometimes called the virtual address. In systems using flat segmentation (base=0 for all segments), the programmer's logical offset equals the linear/virtual address, which is then paged. Most modern OSes work in this mode, which is why 'virtual address' and 'linear address' are often used interchangeably.

Per-Segment vs. Unified Page Tables

A fundamental design decision in combined segmentation-paging is how to structure page tables. There are two main approaches, each with distinct trade-offs:

Approach 1: Per-Segment Page Tables

In this design, each segment has its own independent page table:

Segment descriptor contains pointer to segment's page table
Each segment's pages are indexed starting from 0
Page table size matches segment size
Logical address: [Segment | Page-within-segment | Offset]

Per-Segment Advantages

•Page table size matches segment size exactly
•No wasted PTEs for unused linear address space
•Natural isolation: segments have independent PTEs
•Easy to share entire segments (share page table)
•Segment permissions apply uniformly

Per-Segment Disadvantages

•Multiple page tables to manage
•Complex TLB tagging (needs segment identifier)
•More memory for per-segment page table structures
•Address translation requires segment lookup first
•Hardware complexity: segment→page table indirection

Approach 2: Unified Page Table (x86 Approach)

The x86 architecture takes a different approach: segmentation produces a linear address, and a single unified page table structure covers the entire linear address space:

One page directory per process (pointed to by CR3)
Page tables cover the full 4 GB linear address space
Segments are laid out within this unified space
Logical address: [Segment] → Base → [Linear] = [Dir | Table | Offset]

Linear Address Space Layout Example

Memory Layout

Unified Linear Address Space (x86 Example)
════════════════════════════════════════════════════════════════
 
Linear Address Range            Usage              Segment Base/Limit
─────────────────────────────────────────────────────────────────
0x00000000 - 0x000FFFFF        Reserved/Legacy     N/A
0x00100000 - 0x00FFFFFF        Kernel Code         CS: Base=0, Limit=4GB
0x01000000 - 0x0FFFFFFF        Kernel Data         DS: Base=0, Limit=4GB
0x10000000 - 0x7FFFFFFF        User Code+Data      CS/DS: Base=0, Limit=4GB
0x80000000 - 0xBFFFFFFF        Shared Libraries    Various segments
0xC0000000 - 0xFFFFFFFF        Kernel Space        Mapped kernel segments
 
Note: In flat model, all segments have base=0 and cover entire 4GB.
      The layout is achieved through PAGE TABLE configuration, not segments.
 
Alternative Segment-Based Layout (Non-flat):
─────────────────────────────────────────────────────────────────
Segment A: Base=0x10000000, Limit=0x1000000 (16MB)
  Offsets 0x00000000-0x00FFFFFF map to linear 0x10000000-0x1FFFFFFF
  
Segment B: Base=0x50000000, Limit=0x0800000 (8MB)
  Offsets 0x00000000-0x007FFFFF map to linear 0x50000000-0x57FFFFFF
  
Segment C: Base=0x40000000, Limit=0x0400000 (4MB)
  Offsets 0x00000000-0x003FFFFF map to linear 0x40000000-0x43FFFFFF
 
The unified page table handles all linear addresses regardless of
which segment produced them. Segment protection is checked BEFORE
paging; page protection is checked DURING paging.

Why x86 Chose Unified Page Tables:

Simpler Hardware: One page table walk mechanism, not segment-specific variants
Efficient TLB: TLB entries keyed by linear address only (after segment translation)
Flexible Layout: OS can organize linear space however desired
Paging Optional: If paging disabled, segments work independently
Flat Model Natural: When all segments base=0, programmer addresses = linear addresses

The downside is that in non-flat models, multiple segments may share linear address ranges, creating potential aliasing. This was acceptable given the trend toward flat address spaces.

Modern Flat Model

In modern operating systems, the 'per-segment page table' design appears conceptually but is implemented differently: each process has its own page table hierarchy (pointed to by CR3), and all segments share base=0. The 'segment' abstraction is maintained at the programming model level (code, data, stack regions), but mapped through the unified page table. Protection differences come from page-level permissions.

Operating System Page Table Management

Managing page tables for segmented processes requires careful coordination. The OS must maintain consistency between segment descriptors, page directory, and page tables. Let's examine the key operations:

Process Creation:

When creating a new process, the OS must:

Allocate page directory: One 4 KB page for the page directory
Initialize kernel mappings: Copy or share kernel page table entries
Create segment descriptors: Set up code, data, and stack segments
Allocate initial page tables: For regions the process will immediately use
Set up initial page mappings: Map the executable's code and data pages
Initialize stack: Allocate and map stack pages

Process Page Table Setup
C
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <stdint.h>
#include <stdbool.h>
 
// Page table entry flags
#define PTE_PRESENT     0x001
#define PTE_WRITE       0x002
#define PTE_USER        0x004
#define PTE_ACCESSED    0x020
#define PTE_DIRTY       0x040
 
// Page directory entry flags (same as PTE for x86)
#define PDE_PRESENT     0x001
#define PDE_WRITE       0x002
#define PDE_USER        0x004
 
#define PAGE_SIZE       4096
#define ENTRIES_PER_TABLE 1024
#define KERNEL_BASE     0xC0000000
 
// Physical memory allocator (simplified)
extern uint32_t alloc_physical_frame(void);
extern void free_physical_frame(uint32_t frame);
 
// Process address space structure
struct address_space {
    uint32_t *page_directory;  // Virtual address of page directory
    uint32_t pd_physical;      // Physical address of page directory (for CR3)
    // Per-segment tracking (for non-flat models)
    struct segment_mapping {
        uint32_t linear_base;  // Where segment is placed in linear space
        uint32_t limit;        // Segment size in bytes
        uint8_t  access;       // Segment access rights
        bool     allocated;    // Is this segment slot used?
    } segments[16];            // Support up to 16 segments per process
};
 
/**
 * Create new address space for a process.
 * Returns NULL on failure.
 */
struct address_space* create_address_space(void) {
    struct address_space* as = kmalloc(sizeof(*as));
    if (!as) return NULL;
    
    // Allocate page directory
    as->pd_physical = alloc_physical_frame();
    if (!as->pd_physical) {
        kfree(as);
        return NULL;
    }
    
    // Map page directory into kernel space for access
    as->page_directory = (uint32_t*)map_temporary(as->pd_physical);
    
    // Clear user-space entries
    for (int i = 0; i < 768; i++) {  // Entries 0-767 cover 0-3GB
        as->page_directory[i] = 0;
    }
    
    // Copy kernel page directory entries (entries 768-1023 cover 3-4GB)
    // This makes kernel space identical across all processes
    for (int i = 768; i < 1024; i++) {
        as->page_directory[i] = kernel_page_directory[i];
    }
    
    // Initialize segment mappings
    memset(as->segments, 0, sizeof(as->segments));
    
    return as;
}
 
/**
 * Map a linear address range to physical frames.
 * Used to set up segment pages in the address space.
 */
bool map_linear_range(
    struct address_space *as,
    uint32_t linear_start,
    uint32_t physical_start,
    uint32_t size,
    uint32_t flags
) {
    uint32_t linear_end = linear_start + size;
    
    for (uint32_t linear = linear_start, phys = physical_start;
         linear < linear_end;
         linear += PAGE_SIZE, phys += PAGE_SIZE) {
        
        // Calculate page directory and page table indices
        uint32_t pd_index = linear >> 22;
        uint32_t pt_index = (linear >> 12) & 0x3FF;
        
        // Check if page table exists, create if not
        if (!(as->page_directory[pd_index] & PDE_PRESENT)) {
            uint32_t pt_phys = alloc_physical_frame();
            if (!pt_phys) return false;
            
            // Clear new page table
            uint32_t *pt = (uint32_t*)map_temporary(pt_phys);
            memset(pt, 0, PAGE_SIZE);
            unmap_temporary(pt);
            
            // Insert page table into directory
            as->page_directory[pd_index] = pt_phys | PDE_PRESENT | PDE_WRITE | PDE_USER;
        }
        
        // Get page table
        uint32_t pt_phys = as->page_directory[pd_index] & 0xFFFFF000;
        uint32_t *pt = (uint32_t*)map_temporary(pt_phys);
        
        // Create page table entry
        pt[pt_index] = phys | flags;
        
        unmap_temporary(pt);
    }
    
    return true;
}
 
/**
 * Allocate and map a segment for a process.
 * Places the segment at an appropriate linear address.
 * Returns the segment's linear base address, or 0 on failure.
 */
uint32_t allocate_segment(
    struct address_space *as,
    uint32_t size,
    uint8_t access_rights  // Code, data, stack indicators
) {
    // Find free slot in segment table
    int slot = -1;
    for (int i = 0; i < 16; i++) {
        if (!as->segments[i].allocated) {
            slot = i;
            break;
        }
    }
    if (slot < 0) return 0;  // No free slots
    
    // Find free linear address range (simplified: scan for gap)
    uint32_t linear_base = find_free_linear_range(as, size);
    if (!linear_base) return 0;
    
    // Calculate number of pages
    uint32_t num_pages = (size + PAGE_SIZE - 1) / PAGE_SIZE;
    
    // Allocate physical frames and map pages
    uint32_t flags = PTE_PRESENT | PTE_USER;
    if (access_rights & SEG_WRITABLE) flags |= PTE_WRITE;
    
    for (uint32_t i = 0; i < num_pages; i++) {
        uint32_t frame = alloc_physical_frame();
        if (!frame) {
            // Cleanup on failure (unwind allocations)
            for (uint32_t j = 0; j < i; j++) {
                unmap_page(as, linear_base + j * PAGE_SIZE);
            }
            return 0;
        }
        
        if (!map_linear_range(as, linear_base + i * PAGE_SIZE, frame, PAGE_SIZE, flags)) {
            free_physical_frame(frame);
            // Cleanup...
            return 0;
        }
    }
    
    // Record segment in process structure
    as->segments[slot].linear_base = linear_base;
    as->segments[slot].limit = size;
    as->segments[slot].access = access_rights;
    as->segments[slot].allocated = true;
    
    return linear_base;
}

Segment Growth and Shrinking:

One advantage of paged segments is that segments can grow or shrink dynamically by allocating or deallocating pages:

Growing a Segment:

Increase segment limit in descriptor
Allocate additional physical frames
Map new pages at the end of segment's linear range
Zero-fill new pages (security requirement)

Shrinking a Segment:

Unmap pages from the end of segment's linear range
Free the physical frames
Decrease segment limit in descriptor
Flush TLB entries for removed pages

Note: In x86 unified page table model, there's no explicit 'segment page table'—all segments share the process's page table hierarchy. The segment's 'pages' are simply those PTEs covering the linear address range from segment base to base+limit.

TLB Consistency

When modifying page table entries for an existing segment, the OS must ensure TLB consistency. Changing a PTE without flushing the TLB can lead to stale mappings, causing security vulnerabilities (accessing freed pages) or crashes. x86 provides INVLPG to invalidate individual TLB entries and MOV CR3 to flush the entire TLB.

Page Faults in Segmented Systems

In combined segmentation-paging, memory access errors can arise from either stage of translation. Understanding the difference between segment faults and page faults is crucial for implementing correct exception handlers.

Segmentation Faults (Before Paging):

These occur during the segment translation phase and raise General Protection Fault (#GP) or Segment Not Present (#NP):

Condition	Exception	Error Code Info
Null selector (index 0) used	#GP	Selector value
Index beyond GDT/LDT limit	#GP	Selector value
Offset beyond segment limit	#GP	Selector value
Type mismatch (data selector in CS)	#GP	Selector value
Privilege violation (DPL check)	#GP	Selector value
Segment not present (P=0)	#NP	Selector value

Page Faults (During Paging):

These occur during the paging phase and raise Page Fault (#PF):

Page Fault Causes and Error Code Bits
Error Code Bit	Meaning When Set	Meaning When Clear
Bit 0 (P)	Protection violation	Page not present
Bit 1 (W)	Write access caused fault	Read access caused fault
Bit 2 (U)	User mode access	Supervisor mode access
Bit 3 (RSVD)	Reserved bit set in PTE	Not a reserved bit issue
Bit 4 (I)	Instruction fetch	Data access
Bit 5 (PK)	Protection key violation	Not a protection key issue

Page Fault Handler Considerations:

In a paged-segment system, the page fault handler must consider segment context:

CR2 contains linear address, not logical: The handler knows which linear address faulted, but not directly which segment was being accessed. It must examine the faulting instruction to determine the segment.
Segment limit affects validity: Even if the OS would like to extend a segment (grow the stack), the segment limit must be updated in the descriptor, not just the page tables.
Multiple segments might map to the same linear range: In non-flat models, overlapping segments create aliasing. A page fault might be accessed through different segments with different permissions—the handler must check which segment register was in use.
Protection is hierachical: A page can never have MORE permissions than its containing segment. If the segment is read-only, marking the page read-write accomplishes nothing.

Page Fault Handler with Segment Awareness
C
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// Page fault handler with segment-aware logic
void page_fault_handler(struct interrupt_frame *frame) {
    // Read faulting linear address from CR2
    uint32_t fault_addr;
    __asm__ volatile("mov %%cr2, %0" : "=r"(fault_addr));
    
    // Parse error code
    uint32_t error = frame->error_code;
    bool page_present = error & 0x1;
    bool write_access = error & 0x2;
    bool user_mode = error & 0x4;
    bool reserved_bit = error & 0x8;
    bool instruction_fetch = error & 0x10;
    
    // Reserved bit violation is always fatal (corrupt page table)
    if (reserved_bit) {
        panic("Reserved bit set in page table entry!");
    }
    
    // Get current process
    struct process *proc = current_process();
    
    // Determine which segment was being accessed
    // This requires examining the faulting instruction (complex)
    // Or we can use segment ranges we've recorded
    struct segment_mapping *seg = find_segment_for_linear(proc->as, fault_addr);
    
    if (!seg) {
        // Address not within any valid segment - definitely invalid
        if (user_mode) {
            signal_process(proc, SIGSEGV);
            return;
        } else {
            panic("Kernel accessed invalid linear address: 0x%x", fault_addr);
        }
    }
    
    // Check segment-level permission
    uint32_t offset_in_segment = fault_addr - seg->linear_base;
    if (offset_in_segment > seg->limit) {
        // Beyond segment limit - segment fault, not page fault
        // (shouldn't happen if segments configured correctly)
        signal_process(proc, SIGSEGV);
        return;
    }
    
    // Handle page not present: demand paging
    if (!page_present) {
        // Check if this is a valid page or truly invalid access
        if (is_valid_but_not_loaded(proc->as, fault_addr)) {
            // Demand paging: load the page from disk or allocate
            if (is_mapped_file(proc->as, fault_addr)) {
                load_page_from_file(proc->as, fault_addr);
            } else if (is_zero_fill(proc->as, fault_addr)) {
                allocate_and_zero_page(proc->as, fault_addr);
            } else if (is_swap(proc->as, fault_addr)) {
                load_page_from_swap(proc->as, fault_addr);
            }
            return;
        } else {
            // Truly invalid access
            signal_process(proc, SIGSEGV);
            return;
        }
    }
    
    // Page is present but protection violation
    if (write_access) {
        // Check for copy-on-write
        if (is_copy_on_write(proc->as, fault_addr)) {
            handle_cow(proc->as, fault_addr);
            return;
        }
        
        // Check segment allows write
        if (!(seg->access & SEG_WRITABLE)) {
            // Segment doesn't allow write - segment-level protection
            signal_process(proc, SIGSEGV);
            return;
        }
        
        // Page marked read-only but segment allows write
        // This might be a mprotect'd region or error
        signal_process(proc, SIGSEGV);
        return;
    }
    
    // Read/execute violation on present page
    if (instruction_fetch && !(seg->access & SEG_EXECUTABLE)) {
        // Trying to execute non-executable segment
        signal_process(proc, SIGSEGV);
        return;
    }
    
    // Unknown violation
    signal_process(proc, SIGSEGV);
}

Demand Paging for Segments

With paged segments, demand paging works at the page level within segments. A segment might have some pages resident and others swapped out or not yet faulted in. The segment descriptor's present bit (P) typically remains set—individual page PTEs control presence. Only if the entire segment is swapped out would the segment-level P bit be cleared, but this coarse-grained swapping is rarely used in modern systems.

Memory Overhead of Paged Segments

Combined segmentation-paging incurs memory overhead from both the segment tables and page tables. Understanding this overhead helps explain why modern systems have moved toward pure paging with minimal segmentation.

Segment Table Overhead:

Each process may have:

GDT overhead: Shared by all processes, contains ~5-10 entries typically (40-80 bytes total, negligible)
LDT overhead (if used): Per-process LDT, typically small (8 bytes per descriptor, plus LDT descriptor in GDT)

Segmentation overhead is generally small because descriptors are compact (8 bytes each) and most systems use few segments per process.

Page Table Overhead:

Page table overhead is more significant:

Page Table Overhead Calculation

Analysis

Page Table Overhead Analysis (32-bit x86)
════════════════════════════════════════════════════════════════
 
Constants:
  Page Directory: 1024 entries × 4 bytes = 4 KB (always allocated)
  Page Table: 1024 entries × 4 bytes = 4 KB each
  Page Size: 4 KB
  Addressable Memory per PD: 4 GB (1024 × 1024 × 4KB)
 
Overhead Formula:
  For memory usage M:
    Page Directory: 4 KB (fixed)
    Page Tables: ceil(M / (4 MB)) × 4 KB
    
  Where 4 MB = 1024 pages × 4 KB = coverage of one page table
 
Examples:
─────────────────────────────────────────────────────────────────
Process using 4 MB:
  Page Directory: 4 KB
  Page Tables: 1 × 4 KB = 4 KB
  Total: 8 KB overhead for 4 MB = 0.2%
 
Process using 100 MB:
  Page Directory: 4 KB
  Page Tables: ceil(100/4) × 4 KB = 25 × 4 KB = 100 KB
  Total: 104 KB overhead for 100 MB ≈ 0.1%
 
Process using 1 GB:
  Page Directory: 4 KB
  Page Tables: 256 × 4 KB = 1024 KB = 1 MB
  Total: 1028 KB overhead for 1 GB ≈ 0.1%
 
Full 4 GB address space (theoretical):
  Page Directory: 4 KB
  Page Tables: 1024 × 4 KB = 4 MB
  Total: 4100 KB = 4 MB overhead = 0.1%
 
════════════════════════════════════════════════════════════════
 
With Per-Segment Page Tables (Alternative Model):
  Each segment has independent page table(s)
  No sharing of page table entries across segments
  
  Example: 3 segments of 10 MB each:
    Segment 1: 1 PD + 3 PTs = 16 KB
    Segment 2: 1 PD + 3 PTs = 16 KB  
    Segment 3: 1 PD + 3 PTs = 16 KB
    Total: 48 KB (vs ~16 KB with unified page table)
    
  Per-segment model has higher overhead for many small segments

Fragmentation in Page Tables:

The discrete nature of page tables creates a form of internal fragmentation:

Each page table covers exactly 4 MB of linear address space
Using even one page in a 4 MB region requires allocating the entire 4 KB page table
A sparse address space can waste significant memory on mostly-empty page tables

Example of Sparse Overhead:

A process with code at 0x00400000 and stack at 0xBFF00000:

Two 4 MB regions used
Two page tables required (8 KB)
But only a few KB in each are actually mapped
Most of the 8 KB is unused entries

Optimization: Lazy Page Table Allocation:

Modern OS implementations allocate page tables lazily:

Page directory entries initially marked not present
On first access to a new 4 MB region, #PF occurs
Handler allocates page table, installs PDE, resumes
Only accessed regions have page tables in memory

This dramatically reduces overhead for sparse address spaces.

Multi-Level Paging Reduces Overhead

The overhead analysis assumes two-level paging. Modern 64-bit systems use four or five levels, which greatly reduces overhead for sparse address spaces. With multi-level paging, interior tables are only allocated when needed, limiting overhead to O(log(address space size)) rather than O(address space size).

Sharing Paged Segments Between Processes

One of the most powerful features of paged segments is the ability to share memory between processes at either the segment or page level. This enables shared libraries, inter-process communication, and efficient fork() implementations.

Segment-Level Sharing:

In the per-segment page table model:

Two processes can point to the same page table for a segment
All pages in that segment are automatically shared
Changes to page table entries affect both processes
Useful for read-only shared libraries where all pages are shared

In the unified page table model (x86):

Two processes map the same linear address range
Page table entries point to the same physical frames
May be at different linear addresses in each process (via different segment bases)

Example: Shared Library Mapping:

Shared Library Mapping

Process Layout

Shared Library (libc.so) in Physical Memory:
═══════════════════════════════════════════════════════════════
 
Physical Frames:
  Frame 0x1000: libc code page 0
  Frame 0x1001: libc code page 1
  Frame 0x1002: libc code page 2
  ...
  Frame 0x1100: libc data page 0 (read-only portion)
  Frame 0x1101: libc data page 1
 
═══════════════════════════════════════════════════════════════
 
Process A Address Space:
  Linear 0x40000000 → Frame 0x1000 (libc page 0, R-X)
  Linear 0x40001000 → Frame 0x1001 (libc page 1, R-X)
  Linear 0x40002000 → Frame 0x1002 (libc page 2, R-X)
  Linear 0x40100000 → Frame 0x1100 (libc data, R--)
  Linear 0x40101000 → Frame 0x2001 (Process A private, R-W, CoW copy)
 
Process B Address Space:
  Linear 0x40000000 → Frame 0x1000 (same physical frame!)
  Linear 0x40001000 → Frame 0x1001 (same physical frame!)
  Linear 0x40002000 → Frame 0x1002 (same physical frame!)
  Linear 0x40100000 → Frame 0x1100 (same physical frame!)
  Linear 0x40101000 → Frame 0x2002 (Process B private, CoW copy)
 
═══════════════════════════════════════════════════════════════
 
Memory Savings:
  Without sharing: 2 processes × 200 KB libc = 400 KB
  With sharing: 1 copy × 200 KB = 200 KB (50% savings)
  With 100 processes: 200 KB vs 20 MB (99% savings)

Page-Level Sharing and Copy-on-Write:

Within shared segments, individual pages can have different sharing properties:

Fully shared pages: Multiple processes read the same physical page (code, read-only data)
Copy-on-write pages: Initially shared, copied when written (writable data)
Private pages: Never shared, each process has its own copy (stack, heap after modification)

Copy-on-Write Implementation:

Both processes' PTEs point to same frame
Both PTEs marked READ-ONLY (even for writable segments)
When either process writes, page fault occurs
Handler allocates new frame, copies original content
Update faulting process's PTE to point to new frame, mark R/W
Original frame remains shared with read-only access

This enables efficient fork():

Child shares ALL parent pages initially
All marked copy-on-write
Pages copied only when actually modified
If child exec()s immediately, minimal copying occurs

Sharing Mechanisms Comparison
Mechanism	Sharing Scope	When Copied	Use Case
Segment sharing	Entire segment	Never (always shared)	Read-only shared libraries
Page sharing	Individual pages	Never (always shared)	Shared memory IPC, file mappings
Copy-on-write	Individual pages	On first write	fork(), shared init data
Private mapping	Individual pages	Always private	Stack, heap allocations

Reference Counting

Shared pages require reference counting to track how many processes are using each frame. When a process exits or unmaps a shared page, the reference count decrements. The physical frame is freed only when the count reaches zero. This accounting adds complexity but is essential for correct memory management.

Summary: Paged Segments

We've explored the practical mechanics of paged segments—how the hardware and operating system work together to provide segments that are internally divided into pages. Let's consolidate the key insights:

Key Takeaways

•Two-stage translation — Segmentation produces linear addresses; paging translates linear to physical. The linear address space is the clean interface between them.
•Unified vs per-segment page tables — x86 uses unified page tables covering the full linear address space. Segments are laid out within this space, sharing the page table hierarchy.
•OS manages both layers — The operating system must maintain consistency between segment descriptors and page table entries, handling growth, shrinkage, and protection changes.
•Page faults vs segment faults — Segment violations (#GP, #NP) occur before paging; page violations (#PF) occur during. Handlers must distinguish and respond appropriately.
•Memory overhead is modest — About 0.1% overhead for page tables, plus minimal segment descriptor overhead. Lazy allocation reduces overhead for sparse address spaces.
•Sharing operates at both levels — Entire segments can be shared (shared libraries) or individual pages (copy-on-write). This enables efficient process creation and memory utilization.
•Protection is hierarchical — Page permissions cannot exceed segment permissions. Both layers must allow an operation for it to succeed.

What's Next:

The final page of this module examines modern implementations—how contemporary operating systems handle the legacy of combined segmentation-paging, why the trend has moved toward pure paging, and what segmentation artifacts remain in modern x86-64 systems.

Page Complete

You now understand how paged segments work in practice, from the two-stage address translation through OS page table management, exception handling, overhead analysis, and sharing mechanisms. This practical knowledge complements the architectural understanding from previous pages.

4 / 5

Loading learning content...

Operating SystemsSegmentation with Paging

Segmentation with Paging

LevelIntermediate

Duration90 mins

TopicSegmentation with Paging

4 / 5

Paged Segments

Segments Meet Pages

What You Will Learn

Two-Stage Address Translation Dissected

In combined segmentation-paging, address translation occurs in two distinct stages. Understanding how these stages connect is fundamental to grasping how paged segments work.

Stage 1: Segmentation (Logical → Linear)

The first stage converts a logical address (segment selector + offset) into a 32-bit linear address:

Logical Address: [Selector 16 bits] : [Offset 32 bits]
                       ↓
              Segment Descriptor
                 (from GDT/LDT)
                       ↓
            Base Address (32 bits)
                       ↓
          Linear Address = Base + Offset

Stage 2: Paging (Linear → Physical)

The second stage converts the 32-bit linear address into a physical address:

Linear Address:  [Directory 10 bits] | [Table 10 bits] | [Offset 12 bits]
                        ↓                    ↓                ↓
                 Page Directory        Page Table          Unchanged
                 Entry (PDE)          Entry (PTE)
                        ↓                    ↓
                 Page Table Base      Frame Number
                        ↓                    ↓
Physical = Frame × 4096 + Page Offset

Converting Mermaid diagram...

Key Insight: The Linear Address Space

Segmentation doesn't know about pages. It simply adds a base to an offset and produces a 32-bit linear address. Whether that address will be paged is irrelevant to the segment translation.
Paging doesn't know about segments. It receives a 32-bit linear address and translates it to physical. The fact that this address originated from segment translation is irrelevant to the paging logic.

This clean separation is crucial. It means:

An OS can use segmentation without paging (CR0.PG = 0)
An OS can effectively disable segmentation and use only paging (flat segments with base=0)
An OS can use both simultaneously (combined mode)
The paging code doesn't need segment-specific logic

Linear Address = Virtual Address

Per-Segment vs. Unified Page Tables

A fundamental design decision in combined segmentation-paging is how to structure page tables. There are two main approaches, each with distinct trade-offs:

Approach 1: Per-Segment Page Tables

In this design, each segment has its own independent page table:

Segment descriptor contains pointer to segment's page table
Each segment's pages are indexed starting from 0
Page table size matches segment size
Logical address: [Segment | Page-within-segment | Offset]

Per-Segment Advantages

•Page table size matches segment size exactly
•No wasted PTEs for unused linear address space
•Natural isolation: segments have independent PTEs
•Easy to share entire segments (share page table)
•Segment permissions apply uniformly

Per-Segment Disadvantages

•Multiple page tables to manage
•Complex TLB tagging (needs segment identifier)
•More memory for per-segment page table structures
•Address translation requires segment lookup first
•Hardware complexity: segment→page table indirection

Approach 2: Unified Page Table (x86 Approach)

The x86 architecture takes a different approach: segmentation produces a linear address, and a single unified page table structure covers the entire linear address space:

One page directory per process (pointed to by CR3)
Page tables cover the full 4 GB linear address space
Segments are laid out within this unified space
Logical address: [Segment] → Base → [Linear] = [Dir | Table | Offset]

Linear Address Space Layout Example

Memory Layout

Unified Linear Address Space (x86 Example)
════════════════════════════════════════════════════════════════
 
Linear Address Range            Usage              Segment Base/Limit
─────────────────────────────────────────────────────────────────
0x00000000 - 0x000FFFFF        Reserved/Legacy     N/A
0x00100000 - 0x00FFFFFF        Kernel Code         CS: Base=0, Limit=4GB
0x01000000 - 0x0FFFFFFF        Kernel Data         DS: Base=0, Limit=4GB
0x10000000 - 0x7FFFFFFF        User Code+Data      CS/DS: Base=0, Limit=4GB
0x80000000 - 0xBFFFFFFF        Shared Libraries    Various segments
0xC0000000 - 0xFFFFFFFF        Kernel Space        Mapped kernel segments
 
Note: In flat model, all segments have base=0 and cover entire 4GB.
      The layout is achieved through PAGE TABLE configuration, not segments.
 
Alternative Segment-Based Layout (Non-flat):
─────────────────────────────────────────────────────────────────
Segment A: Base=0x10000000, Limit=0x1000000 (16MB)
  Offsets 0x00000000-0x00FFFFFF map to linear 0x10000000-0x1FFFFFFF
  
Segment B: Base=0x50000000, Limit=0x0800000 (8MB)
  Offsets 0x00000000-0x007FFFFF map to linear 0x50000000-0x57FFFFFF
  
Segment C: Base=0x40000000, Limit=0x0400000 (4MB)
  Offsets 0x00000000-0x003FFFFF map to linear 0x40000000-0x43FFFFFF
 
The unified page table handles all linear addresses regardless of
which segment produced them. Segment protection is checked BEFORE
paging; page protection is checked DURING paging.

Why x86 Chose Unified Page Tables:

Simpler Hardware: One page table walk mechanism, not segment-specific variants
Efficient TLB: TLB entries keyed by linear address only (after segment translation)
Flexible Layout: OS can organize linear space however desired
Paging Optional: If paging disabled, segments work independently
Flat Model Natural: When all segments base=0, programmer addresses = linear addresses

The downside is that in non-flat models, multiple segments may share linear address ranges, creating potential aliasing. This was acceptable given the trend toward flat address spaces.

Modern Flat Model

Operating System Page Table Management

Process Creation:

When creating a new process, the OS must:

Allocate page directory: One 4 KB page for the page directory
Initialize kernel mappings: Copy or share kernel page table entries
Create segment descriptors: Set up code, data, and stack segments
Allocate initial page tables: For regions the process will immediately use
Set up initial page mappings: Map the executable's code and data pages
Initialize stack: Allocate and map stack pages

Process Page Table Setup
C
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <stdint.h>
#include <stdbool.h>
 
// Page table entry flags
#define PTE_PRESENT     0x001
#define PTE_WRITE       0x002
#define PTE_USER        0x004
#define PTE_ACCESSED    0x020
#define PTE_DIRTY       0x040
 
// Page directory entry flags (same as PTE for x86)
#define PDE_PRESENT     0x001
#define PDE_WRITE       0x002
#define PDE_USER        0x004
 
#define PAGE_SIZE       4096
#define ENTRIES_PER_TABLE 1024
#define KERNEL_BASE     0xC0000000
 
// Physical memory allocator (simplified)
extern uint32_t alloc_physical_frame(void);
extern void free_physical_frame(uint32_t frame);
 
// Process address space structure
struct address_space {
    uint32_t *page_directory;  // Virtual address of page directory
    uint32_t pd_physical;      // Physical address of page directory (for CR3)
    // Per-segment tracking (for non-flat models)
    struct segment_mapping {
        uint32_t linear_base;  // Where segment is placed in linear space
        uint32_t limit;        // Segment size in bytes
        uint8_t  access;       // Segment access rights
        bool     allocated;    // Is this segment slot used?
    } segments[16];            // Support up to 16 segments per process
};
 
/**
 * Create new address space for a process.
 * Returns NULL on failure.
 */
struct address_space* create_address_space(void) {
    struct address_space* as = kmalloc(sizeof(*as));
    if (!as) return NULL;
    
    // Allocate page directory
    as->pd_physical = alloc_physical_frame();
    if (!as->pd_physical) {
        kfree(as);
        return NULL;
    }
    
    // Map page directory into kernel space for access
    as->page_directory = (uint32_t*)map_temporary(as->pd_physical);
    
    // Clear user-space entries
    for (int i = 0; i < 768; i++) {  // Entries 0-767 cover 0-3GB
        as->page_directory[i] = 0;
    }
    
    // Copy kernel page directory entries (entries 768-1023 cover 3-4GB)
    // This makes kernel space identical across all processes
    for (int i = 768; i < 1024; i++) {
        as->page_directory[i] = kernel_page_directory[i];
    }
    
    // Initialize segment mappings
    memset(as->segments, 0, sizeof(as->segments));
    
    return as;
}
 
/**
 * Map a linear address range to physical frames.
 * Used to set up segment pages in the address space.
 */
bool map_linear_range(
    struct address_space *as,
    uint32_t linear_start,
    uint32_t physical_start,
    uint32_t size,
    uint32_t flags
) {
    uint32_t linear_end = linear_start + size;
    
    for (uint32_t linear = linear_start, phys = physical_start;
         linear < linear_end;
         linear += PAGE_SIZE, phys += PAGE_SIZE) {
        
        // Calculate page directory and page table indices
        uint32_t pd_index = linear >> 22;
        uint32_t pt_index = (linear >> 12) & 0x3FF;
        
        // Check if page table exists, create if not
        if (!(as->page_directory[pd_index] & PDE_PRESENT)) {
            uint32_t pt_phys = alloc_physical_frame();
            if (!pt_phys) return false;
            
            // Clear new page table
            uint32_t *pt = (uint32_t*)map_temporary(pt_phys);
            memset(pt, 0, PAGE_SIZE);
            unmap_temporary(pt);
            
            // Insert page table into directory
            as->page_directory[pd_index] = pt_phys | PDE_PRESENT | PDE_WRITE | PDE_USER;
        }
        
        // Get page table
        uint32_t pt_phys = as->page_directory[pd_index] & 0xFFFFF000;
        uint32_t *pt = (uint32_t*)map_temporary(pt_phys);
        
        // Create page table entry
        pt[pt_index] = phys | flags;
        
        unmap_temporary(pt);
    }
    
    return true;
}
 
/**
 * Allocate and map a segment for a process.
 * Places the segment at an appropriate linear address.
 * Returns the segment's linear base address, or 0 on failure.
 */
uint32_t allocate_segment(
    struct address_space *as,
    uint32_t size,
    uint8_t access_rights  // Code, data, stack indicators
) {
    // Find free slot in segment table
    int slot = -1;
    for (int i = 0; i < 16; i++) {
        if (!as->segments[i].allocated) {
            slot = i;
            break;
        }
    }
    if (slot < 0) return 0;  // No free slots
    
    // Find free linear address range (simplified: scan for gap)
    uint32_t linear_base = find_free_linear_range(as, size);
    if (!linear_base) return 0;
    
    // Calculate number of pages
    uint32_t num_pages = (size + PAGE_SIZE - 1) / PAGE_SIZE;
    
    // Allocate physical frames and map pages
    uint32_t flags = PTE_PRESENT | PTE_USER;
    if (access_rights & SEG_WRITABLE) flags |= PTE_WRITE;
    
    for (uint32_t i = 0; i < num_pages; i++) {
        uint32_t frame = alloc_physical_frame();
        if (!frame) {
            // Cleanup on failure (unwind allocations)
            for (uint32_t j = 0; j < i; j++) {
                unmap_page(as, linear_base + j * PAGE_SIZE);
            }
            return 0;
        }
        
        if (!map_linear_range(as, linear_base + i * PAGE_SIZE, frame, PAGE_SIZE, flags)) {
            free_physical_frame(frame);
            // Cleanup...
            return 0;
        }
    }
    
    // Record segment in process structure
    as->segments[slot].linear_base = linear_base;
    as->segments[slot].limit = size;
    as->segments[slot].access = access_rights;
    as->segments[slot].allocated = true;
    
    return linear_base;
}

Segment Growth and Shrinking:

One advantage of paged segments is that segments can grow or shrink dynamically by allocating or deallocating pages:

Growing a Segment:

Increase segment limit in descriptor
Allocate additional physical frames
Map new pages at the end of segment's linear range
Zero-fill new pages (security requirement)

Shrinking a Segment:

Unmap pages from the end of segment's linear range
Free the physical frames
Decrease segment limit in descriptor
Flush TLB entries for removed pages

TLB Consistency

Page Faults in Segmented Systems

Segmentation Faults (Before Paging):

These occur during the segment translation phase and raise General Protection Fault (#GP) or Segment Not Present (#NP):

Condition	Exception	Error Code Info
Null selector (index 0) used	#GP	Selector value
Index beyond GDT/LDT limit	#GP	Selector value
Offset beyond segment limit	#GP	Selector value
Type mismatch (data selector in CS)	#GP	Selector value
Privilege violation (DPL check)	#GP	Selector value
Segment not present (P=0)	#NP	Selector value

Page Faults (During Paging):

These occur during the paging phase and raise Page Fault (#PF):

Page Fault Causes and Error Code Bits
Error Code Bit	Meaning When Set	Meaning When Clear
Bit 0 (P)	Protection violation	Page not present
Bit 1 (W)	Write access caused fault	Read access caused fault
Bit 2 (U)	User mode access	Supervisor mode access
Bit 3 (RSVD)	Reserved bit set in PTE	Not a reserved bit issue
Bit 4 (I)	Instruction fetch	Data access
Bit 5 (PK)	Protection key violation	Not a protection key issue

Page Fault Handler Considerations:

In a paged-segment system, the page fault handler must consider segment context:

CR2 contains linear address, not logical: The handler knows which linear address faulted, but not directly which segment was being accessed. It must examine the faulting instruction to determine the segment.
Segment limit affects validity: Even if the OS would like to extend a segment (grow the stack), the segment limit must be updated in the descriptor, not just the page tables.
Multiple segments might map to the same linear range: In non-flat models, overlapping segments create aliasing. A page fault might be accessed through different segments with different permissions—the handler must check which segment register was in use.
Protection is hierachical: A page can never have MORE permissions than its containing segment. If the segment is read-only, marking the page read-write accomplishes nothing.

Page Fault Handler with Segment Awareness
C
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// Page fault handler with segment-aware logic
void page_fault_handler(struct interrupt_frame *frame) {
    // Read faulting linear address from CR2
    uint32_t fault_addr;
    __asm__ volatile("mov %%cr2, %0" : "=r"(fault_addr));
    
    // Parse error code
    uint32_t error = frame->error_code;
    bool page_present = error & 0x1;
    bool write_access = error & 0x2;
    bool user_mode = error & 0x4;
    bool reserved_bit = error & 0x8;
    bool instruction_fetch = error & 0x10;
    
    // Reserved bit violation is always fatal (corrupt page table)
    if (reserved_bit) {
        panic("Reserved bit set in page table entry!");
    }
    
    // Get current process
    struct process *proc = current_process();
    
    // Determine which segment was being accessed
    // This requires examining the faulting instruction (complex)
    // Or we can use segment ranges we've recorded
    struct segment_mapping *seg = find_segment_for_linear(proc->as, fault_addr);
    
    if (!seg) {
        // Address not within any valid segment - definitely invalid
        if (user_mode) {
            signal_process(proc, SIGSEGV);
            return;
        } else {
            panic("Kernel accessed invalid linear address: 0x%x", fault_addr);
        }
    }
    
    // Check segment-level permission
    uint32_t offset_in_segment = fault_addr - seg->linear_base;
    if (offset_in_segment > seg->limit) {
        // Beyond segment limit - segment fault, not page fault
        // (shouldn't happen if segments configured correctly)
        signal_process(proc, SIGSEGV);
        return;
    }
    
    // Handle page not present: demand paging
    if (!page_present) {
        // Check if this is a valid page or truly invalid access
        if (is_valid_but_not_loaded(proc->as, fault_addr)) {
            // Demand paging: load the page from disk or allocate
            if (is_mapped_file(proc->as, fault_addr)) {
                load_page_from_file(proc->as, fault_addr);
            } else if (is_zero_fill(proc->as, fault_addr)) {
                allocate_and_zero_page(proc->as, fault_addr);
            } else if (is_swap(proc->as, fault_addr)) {
                load_page_from_swap(proc->as, fault_addr);
            }
            return;
        } else {
            // Truly invalid access
            signal_process(proc, SIGSEGV);
            return;
        }
    }
    
    // Page is present but protection violation
    if (write_access) {
        // Check for copy-on-write
        if (is_copy_on_write(proc->as, fault_addr)) {
            handle_cow(proc->as, fault_addr);
            return;
        }
        
        // Check segment allows write
        if (!(seg->access & SEG_WRITABLE)) {
            // Segment doesn't allow write - segment-level protection
            signal_process(proc, SIGSEGV);
            return;
        }
        
        // Page marked read-only but segment allows write
        // This might be a mprotect'd region or error
        signal_process(proc, SIGSEGV);
        return;
    }
    
    // Read/execute violation on present page
    if (instruction_fetch && !(seg->access & SEG_EXECUTABLE)) {
        // Trying to execute non-executable segment
        signal_process(proc, SIGSEGV);
        return;
    }
    
    // Unknown violation
    signal_process(proc, SIGSEGV);
}

Demand Paging for Segments

Memory Overhead of Paged Segments

Segment Table Overhead:

Each process may have:

GDT overhead: Shared by all processes, contains ~5-10 entries typically (40-80 bytes total, negligible)
LDT overhead (if used): Per-process LDT, typically small (8 bytes per descriptor, plus LDT descriptor in GDT)

Segmentation overhead is generally small because descriptors are compact (8 bytes each) and most systems use few segments per process.

Page Table Overhead:

Page table overhead is more significant:

Page Table Overhead Calculation

Analysis

Page Table Overhead Analysis (32-bit x86)
════════════════════════════════════════════════════════════════
 
Constants:
  Page Directory: 1024 entries × 4 bytes = 4 KB (always allocated)
  Page Table: 1024 entries × 4 bytes = 4 KB each
  Page Size: 4 KB
  Addressable Memory per PD: 4 GB (1024 × 1024 × 4KB)
 
Overhead Formula:
  For memory usage M:
    Page Directory: 4 KB (fixed)
    Page Tables: ceil(M / (4 MB)) × 4 KB
    
  Where 4 MB = 1024 pages × 4 KB = coverage of one page table
 
Examples:
─────────────────────────────────────────────────────────────────
Process using 4 MB:
  Page Directory: 4 KB
  Page Tables: 1 × 4 KB = 4 KB
  Total: 8 KB overhead for 4 MB = 0.2%
 
Process using 100 MB:
  Page Directory: 4 KB
  Page Tables: ceil(100/4) × 4 KB = 25 × 4 KB = 100 KB
  Total: 104 KB overhead for 100 MB ≈ 0.1%
 
Process using 1 GB:
  Page Directory: 4 KB
  Page Tables: 256 × 4 KB = 1024 KB = 1 MB
  Total: 1028 KB overhead for 1 GB ≈ 0.1%
 
Full 4 GB address space (theoretical):
  Page Directory: 4 KB
  Page Tables: 1024 × 4 KB = 4 MB
  Total: 4100 KB = 4 MB overhead = 0.1%
 
════════════════════════════════════════════════════════════════
 
With Per-Segment Page Tables (Alternative Model):
  Each segment has independent page table(s)
  No sharing of page table entries across segments
  
  Example: 3 segments of 10 MB each:
    Segment 1: 1 PD + 3 PTs = 16 KB
    Segment 2: 1 PD + 3 PTs = 16 KB  
    Segment 3: 1 PD + 3 PTs = 16 KB
    Total: 48 KB (vs ~16 KB with unified page table)
    
  Per-segment model has higher overhead for many small segments

Fragmentation in Page Tables:

The discrete nature of page tables creates a form of internal fragmentation:

Each page table covers exactly 4 MB of linear address space
Using even one page in a 4 MB region requires allocating the entire 4 KB page table
A sparse address space can waste significant memory on mostly-empty page tables

Example of Sparse Overhead:

A process with code at 0x00400000 and stack at 0xBFF00000:

Two 4 MB regions used
Two page tables required (8 KB)
But only a few KB in each are actually mapped
Most of the 8 KB is unused entries

Optimization: Lazy Page Table Allocation:

Modern OS implementations allocate page tables lazily:

Page directory entries initially marked not present
On first access to a new 4 MB region, #PF occurs
Handler allocates page table, installs PDE, resumes
Only accessed regions have page tables in memory

This dramatically reduces overhead for sparse address spaces.

Multi-Level Paging Reduces Overhead

Sharing Paged Segments Between Processes

Segment-Level Sharing:

In the per-segment page table model:

Two processes can point to the same page table for a segment
All pages in that segment are automatically shared
Changes to page table entries affect both processes
Useful for read-only shared libraries where all pages are shared

In the unified page table model (x86):

Two processes map the same linear address range
Page table entries point to the same physical frames
May be at different linear addresses in each process (via different segment bases)

Example: Shared Library Mapping:

Shared Library Mapping

Process Layout

Shared Library (libc.so) in Physical Memory:
═══════════════════════════════════════════════════════════════
 
Physical Frames:
  Frame 0x1000: libc code page 0
  Frame 0x1001: libc code page 1
  Frame 0x1002: libc code page 2
  ...
  Frame 0x1100: libc data page 0 (read-only portion)
  Frame 0x1101: libc data page 1
 
═══════════════════════════════════════════════════════════════
 
Process A Address Space:
  Linear 0x40000000 → Frame 0x1000 (libc page 0, R-X)
  Linear 0x40001000 → Frame 0x1001 (libc page 1, R-X)
  Linear 0x40002000 → Frame 0x1002 (libc page 2, R-X)
  Linear 0x40100000 → Frame 0x1100 (libc data, R--)
  Linear 0x40101000 → Frame 0x2001 (Process A private, R-W, CoW copy)
 
Process B Address Space:
  Linear 0x40000000 → Frame 0x1000 (same physical frame!)
  Linear 0x40001000 → Frame 0x1001 (same physical frame!)
  Linear 0x40002000 → Frame 0x1002 (same physical frame!)
  Linear 0x40100000 → Frame 0x1100 (same physical frame!)
  Linear 0x40101000 → Frame 0x2002 (Process B private, CoW copy)
 
═══════════════════════════════════════════════════════════════
 
Memory Savings:
  Without sharing: 2 processes × 200 KB libc = 400 KB
  With sharing: 1 copy × 200 KB = 200 KB (50% savings)
  With 100 processes: 200 KB vs 20 MB (99% savings)

Page-Level Sharing and Copy-on-Write:

Within shared segments, individual pages can have different sharing properties:

Fully shared pages: Multiple processes read the same physical page (code, read-only data)
Copy-on-write pages: Initially shared, copied when written (writable data)
Private pages: Never shared, each process has its own copy (stack, heap after modification)

Copy-on-Write Implementation:

Both processes' PTEs point to same frame
Both PTEs marked READ-ONLY (even for writable segments)
When either process writes, page fault occurs
Handler allocates new frame, copies original content
Update faulting process's PTE to point to new frame, mark R/W
Original frame remains shared with read-only access

This enables efficient fork():

Child shares ALL parent pages initially
All marked copy-on-write
Pages copied only when actually modified
If child exec()s immediately, minimal copying occurs

Sharing Mechanisms Comparison
Mechanism	Sharing Scope	When Copied	Use Case
Segment sharing	Entire segment	Never (always shared)	Read-only shared libraries
Page sharing	Individual pages	Never (always shared)	Shared memory IPC, file mappings
Copy-on-write	Individual pages	On first write	fork(), shared init data
Private mapping	Individual pages	Always private	Stack, heap allocations

Reference Counting

Summary: Paged Segments

Key Takeaways

•Two-stage translation — Segmentation produces linear addresses; paging translates linear to physical. The linear address space is the clean interface between them.
•Unified vs per-segment page tables — x86 uses unified page tables covering the full linear address space. Segments are laid out within this space, sharing the page table hierarchy.
•OS manages both layers — The operating system must maintain consistency between segment descriptors and page table entries, handling growth, shrinkage, and protection changes.
•Page faults vs segment faults — Segment violations (#GP, #NP) occur before paging; page violations (#PF) occur during. Handlers must distinguish and respond appropriately.
•Memory overhead is modest — About 0.1% overhead for page tables, plus minimal segment descriptor overhead. Lazy allocation reduces overhead for sparse address spaces.
•Sharing operates at both levels — Entire segments can be shared (shared libraries) or individual pages (copy-on-write). This enables efficient process creation and memory utilization.
•Protection is hierarchical — Page permissions cannot exceed segment permissions. Both layers must allow an operation for it to succeed.

What's Next:

Page Complete

4 / 5