Segmentation Vs Paging - Learning Module

Loading content...

0/240

Sharing Differences: Logical vs Physical Sharing

The Importance of Memory Sharing

Memory sharing is one of the most powerful optimization techniques in operating systems. By allowing multiple processes to share the same physical memory, systems can:

Reduce memory consumption: Why store 100 copies of libc when one suffices?
Enable inter-process communication: Shared memory is the fastest IPC mechanism
Improve cache efficiency: Shared data remains in CPU cache across context switches
Accelerate process creation: fork() with copy-on-write is nearly instantaneous

Both segmentation and paging support memory sharing, but they approach it from fundamentally different perspectives. Understanding these differences is essential for designing efficient systems and debugging sharing-related issues.

What You Will Master

By the end of this page, you will understand how segmentation enables logical, semantically meaningful sharing while paging provides flexible, fine-grained sharing. You'll learn about shared libraries, code sharing, copy-on-write implementation, and the trade-offs between the two approaches in real systems.

Conceptual Framework for Sharing

Before comparing the mechanisms, let's understand what "sharing" means in memory management and the different forms it takes.

Types of Memory Sharing:

Type	Description	Examples
Code Sharing	Multiple processes execute the same instructions	Shared libraries, common executables
Read-Only Data Sharing	Processes read the same constant data	String literals, lookup tables
Read-Write Data Sharing	Processes share mutable state	IPC shared memory, databases
Copy-on-Write Sharing	Sharing until modification triggers copy	fork(), memory-mapped files

The Fundamental Sharing Mechanism:

In both segmentation and paging, sharing is implemented by having multiple virtual address mappings point to the same physical memory:

Process A Virtual Space          Physical Memory          Process B Virtual Space
┌─────────────────┐                                        ┌─────────────────┐
│  Virtual Addr   │───────┐    ┌──────────────────┐   ┌────│ Virtual Addr    │
│  0x00400000     │       └───►│ Shared Code/Data │◄──┘    │ 0x00500000      │
│  (Segment/Page) │            │ Physical Addr:   │        │ (Segment/Page)  │
└─────────────────┘            │ 0x12340000       │        └─────────────────┘
                               └──────────────────┘

The difference lies in what "unit" of memory is shared and how the mapping is established.

Sharing in Segmented Systems

In segmented systems, sharing operates at the segment level—whole logical units are shared between processes. This aligns perfectly with how programmers conceptualize code and data organization.

Segment-Level Sharing Mechanism:

To share a segment between processes, both processes' segment tables contain entries pointing to the same physical memory region with the same base and limit:

segment_sharing.h
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
// Segment Sharing Example: Two text editors sharing code
 
// Process A (First instance of text editor)
SegmentTable ProcessA_SegmentTable[] = {
    // Segment 0: Shared code (read-only, executable)
    { .base = 0x10000000, .limit = 524288, .perms = R_X, .shared = true },
    
    // Segment 1: Private data (read-write)
    { .base = 0x20000000, .limit = 65536,  .perms = RW_, .shared = false },
    
    // Segment 2: Private stack (read-write)
    { .base = 0x30000000, .limit = 16384,  .perms = RW_, .shared = false },
};
 
// Process B (Second instance of text editor)
SegmentTable ProcessB_SegmentTable[] = {
    // Segment 0: SAME shared code - points to SAME physical location!
    { .base = 0x10000000, .limit = 524288, .perms = R_X, .shared = true },
    
    // Segment 1: Private data (different physical location)
    { .base = 0x21000000, .limit = 65536,  .perms = RW_, .shared = false },
    
    // Segment 2: Private stack (different physical location)
    { .base = 0x31000000, .limit = 16384,  .perms = RW_, .shared = false },
};
 
/*
 * Memory Map:
 * 
 * Physical Address   Content               Shared Status
 * ─────────────────────────────────────────────────────────
 * 0x10000000         Text Editor Code      SHARED (1 copy, 2 references)
 *    ↑                  (512 KB)           
 *    │                                     
 *    └─── Both Process A and Process B segment tables point here
 *    
 * 0x20000000         Process A Data        PRIVATE to A
 *                       (64 KB)
 *                       
 * 0x21000000         Process B Data        PRIVATE to B
 *                       (64 KB)
 *                       
 * 0x30000000         Process A Stack       PRIVATE to A
 *                       (16 KB)
 *                       
 * 0x31000000         Process B Stack       PRIVATE to B
 *                       (16 KB)
 *                       
 * Memory savings: 512 KB (one code copy instead of two)
 */

Advantages of Segment-Level Sharing:

Segmentation Sharing Strengths

•Semantic clarity: Sharing aligns with program structure—you share 'the code segment' or 'the data segment', not arbitrary pages
•Simple reference tracking: Count how many segment tables reference each physical segment
•Natural protection boundaries: Shared segments can enforce that code is read-only while data is private
•Efficient for large, coherent units: One segment table entry covers megabytes of shared code
•No false sharing: Unrelated data in separate segments stays separate

The MULTICS Legacy

MULTICS, the pioneering segmented operating system, used segment sharing as a fundamental organizing principle. Every subroutine library, every text editor, every system utility existed as a shared segment that any process could link into its address space. This created an elegant, capability-based sharing model that influenced security research for decades.

Sharing in Paged Systems

In paged systems, sharing operates at the page level—individual fixed-size blocks can be independently shared. This provides maximum flexibility at the cost of semantic organization.

Page-Level Sharing Mechanism:

To share pages between processes, multiple page tables contain entries pointing to the same physical frame:

page_sharing.h
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
// Page Sharing Example: Shared library (libc.so)
// Page size: 4KB, libc.so size: 2MB (512 pages)
 
// Physical frames containing libc.so: frames 0x1000 - 0x11FF
 
// Process A Page Table (relevant entries)
PageTableEntry ProcessA_PageTable[] = {
    // libc mapped at virtual address 0x7F000000
    // Virtual pages 0x7F000-0x7F1FF → Physical frames 0x1000-0x11FF
    [0x7F000] = { .frame = 0x1000, .present = 1, .rw = 0, .user = 1 },  // Shared
    [0x7F001] = { .frame = 0x1001, .present = 1, .rw = 0, .user = 1 },  // Shared
    // ... 510 more entries for libc pages ...
    [0x7F1FF] = { .frame = 0x11FF, .present = 1, .rw = 0, .user = 1 },  // Shared
    
    // Private data pages for Process A
    [0x10000] = { .frame = 0x5000, .present = 1, .rw = 1, .user = 1 },  // Private
    [0x10001] = { .frame = 0x5001, .present = 1, .rw = 1, .user = 1 },  // Private
};
 
// Process B Page Table (relevant entries)
PageTableEntry ProcessB_PageTable[] = {
    // libc mapped at DIFFERENT virtual address 0x7E000000 (flexible!)
    // But points to SAME physical frames!
    [0x7E000] = { .frame = 0x1000, .present = 1, .rw = 0, .user = 1 },  // Shared
    [0x7E001] = { .frame = 0x1001, .present = 1, .rw = 0, .user = 1 },  // Shared
    // ... 510 more entries ...
    [0x7E1FF] = { .frame = 0x11FF, .present = 1, .rw = 0, .user = 1 },  // Shared
    
    // Private data pages for Process B
    [0x10000] = { .frame = 0x6000, .present = 1, .rw = 1, .user = 1 },  // Private
    [0x10001] = { .frame = 0x6001, .present = 1, .rw = 1, .user = 1 },  // Private
};
 
/*
 * Key observations:
 * 
 * 1. libc is at virtual 0x7F000000 in Process A but 0x7E000000 in Process B
 *    → Paging allows different virtual addresses for same physical content
 *    → This flexibility is crucial for ASLR (Address Space Layout Randomization)
 *    
 * 2. 512 page table entries needed to share 2MB of libc
 *    → More overhead than one segment table entry
 *    → But allows partial sharing (not all-or-nothing)
 *    
 * 3. Each page independently controlled
 *    → Could share only some pages of a region if desired
 */

Advantages of Page-Level Sharing:

Paging Sharing Strengths

•Address flexibility: Same physical content can appear at different virtual addresses in different processes (essential for ASLR security)
•Fine-grained control: Share exactly the pages you want—not all-or-nothing like segments
•Partial sharing: Share some pages of a logical region while keeping others private
•Demand paging compatible: Pages can be shared and also paged in/out independently
•Copy-on-write friendly: Trivial to implement COW at page granularity

Copy-on-Write: A Deep Dive

Copy-on-Write (COW) is a deferred copying optimization that dramatically improves system performance. It's fundamental to efficient process creation (fork()) and memory-mapped files. Understanding how COW works in each scheme reveals important architectural differences.

COW in Paged Systems (The Natural Fit):

Paging's fixed-size pages make COW implementation elegant and efficient:

cow_paging.pseudo
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
// Copy-on-Write Implementation in Paged Systems
 
function fork():
    child = create_new_process()
    
    // Step 1: Copy page table structure (NOT the actual pages)
    child.page_table = copy_structure(parent.page_table)
    
    // Step 2: Mark all writable pages as read-only + COW flag
    for each pte in parent.page_table:
        if pte.present and pte.writable:
            pte.writable = false       // Read-only in parent
            pte.cow_flag = true        // Mark as copy-on-write
            
            child_pte = child.page_table[same_index]
            child_pte.writable = false  // Read-only in child
            child_pte.cow_flag = true   // Mark as copy-on-write
            
            // Both point to SAME physical frame!
            child_pte.frame = pte.frame
            
            // Increment reference count for this frame
            frame_ref_count[pte.frame]++
    
    // Step 3: Flush TLB entries for affected pages
    invalidate_tlb_entries()
    
    return child
 
// Fork is now O(page_table_size), not O(memory_size)!
// Most pages are never actually copied if child exec()s quickly
 
function handle_page_fault(faulting_address, fault_type):
    pte = lookup_page_table_entry(faulting_address)
    
    if fault_type == WRITE_FAULT and pte.cow_flag:
        // Copy-on-write triggered!
        
        old_frame = pte.frame
        ref_count = frame_ref_count[old_frame]
        
        if ref_count == 1:
            // We're the only user - no copy needed!
            pte.writable = true
            pte.cow_flag = false
        else:
            // Multiple users - must copy
            new_frame = allocate_frame()
            copy_frame(old_frame, new_frame)
            
            pte.frame = new_frame
            pte.writable = true
            pte.cow_flag = false
            
            frame_ref_count[old_frame]--
            frame_ref_count[new_frame] = 1
        
        // Update TLB
        invalidate_tlb_entry(faulting_address)
        
        // Restart the faulting instruction
        return RESTART_INSTRUCTION
 
/*
 * Performance characteristics:
 * 
 * fork() overhead:     O(page_table_entries) ≈ O(virtual_address_space / page_size)
 *                      For 1GB address space with 4KB pages: ~262,144 entries
 *                      With 2MB huge pages: only ~512 entries
 *                      
 * COW copy on write:   O(page_size) = O(4096 bytes) per fault
 * 
 * Best case (exec immediately after fork):
 *   - Few or no COW faults
 *   - Almost no memory copied
 *   - fork() + exec() is nearly free!
 *   
 * Worst case (parent and child heavily modify same pages):
 *   - Many COW faults
 *   - Approaches full-copy cost
 *   - Each fault has page-fault overhead
 */

COW in Segmented Systems (The Challenge):

In pure segmented systems, COW is more complex because segments have variable sizes:

cow_segmentation.pseudo
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
// Copy-on-Write in Segmented Systems (Simplified)
 
function fork_segmented():
    child = create_new_process()
    
    // Step 1: Copy segment table
    child.segment_table = copy(parent.segment_table)
    
    // Step 2: Mark writable segments read-only for COW
    for each ste in parent.segment_table:
        if ste.present and ste.writable:
            ste.writable = false
            ste.cow_flag = true
            
            child_ste = child.segment_table[same_index]
            child_ste.writable = false
            child_ste.cow_flag = true
            child_ste.base = ste.base      // Same physical base
            child_ste.limit = ste.limit
            
            segment_ref_count[ste.base]++
    
    return child
 
function handle_segment_write_fault(segment_num, offset):
    ste = segment_table[segment_num]
    
    if ste.cow_flag:
        // Must copy ENTIRE segment - even if only 1 byte being written!
        
        old_base = ste.base
        segment_size = ste.limit
        
        // Problem: Need contiguous memory for new segment!
        new_base = allocate_contiguous_memory(segment_size)  // May fail!
        
        if new_base == NULL:
            // External fragmentation may prevent allocation
            // Options: compaction, swap out other segments, or fail
            trigger_compaction()
            new_base = allocate_contiguous_memory(segment_size)
            if new_base == NULL:
                return ALLOCATION_FAILED  // Serious problem!
        
        // Copy entire segment (potentially megabytes)
        memcpy(new_base, old_base, segment_size)
        
        ste.base = new_base
        ste.writable = true
        ste.cow_flag = false
        
        segment_ref_count[old_base]--
        
        return RESTART_INSTRUCTION
 
/*
 * Problems with segment-level COW:
 * 
 * 1. Granularity mismatch:
 *    - A 1-byte write to a 10MB segment copies all 10MB
 *    - Wasteful if only small portion modified
 *    
 * 2. Contiguous allocation required:
 *    - Must find contiguous hole for copied segment
 *    - External fragmentation may block COW
 *    - May require compaction mid-operation
 *    
 * 3. Copy cost:
 *    - Variable and potentially huge (O(segment_size))
 *    - Unpredictable latency
 *    
 * 4. All-or-nothing:
 *    - Can't partially copy a segment
 *    - No fine-grained optimization possible
 */

Why Paging Wins for COW

The fixed granularity of paging makes COW predictable (always copy exactly one page per fault) and allocation simple (any free frame works). Segmentation's variable sizes mean potentially copying megabytes for a single byte write, and finding contiguous space may fail due to external fragmentation. This is a decisive advantage for paging in fork-heavy systems like Unix.

Shared Libraries: A Case Study

Shared libraries (like libc.so, kernel32.dll) are one of the most important applications of memory sharing. Let's examine how each scheme handles them.

Shared Library Sharing Comparison:

Shared Library Implementation Comparison
Aspect	Segmentation	Paging
Mapping unit	Entire library as one segment	Library spans multiple pages
Virtual address	Same in all processes (typically)	Can differ (ASLR-compatible)
Table overhead	1 segment table entry	Many page table entries
Partial loading	All or nothing	Load pages on demand
Update granularity	Entire library	Individual pages
ASLR support	Difficult (fixed segment layout)	Natural (any virtual address)

Address Space Layout Randomization (ASLR):

ASLR is a critical security technique that randomizes where code and data are loaded in memory, making exploitation harder. This is where paging truly excels:

Paging + ASLR: Each process loads libc at a randomly chosen virtual address. The physical frames are still shared—only the virtual mapping changes. This is trivial with independent page tables.
Segmentation + ASLR: Much harder. If all processes must share the same segment, they must agree on its virtual address. Randomization would require either:
- Different physical copies (defeats sharing)
- Position-independent code with complex indirection (performance cost)
- Restricted randomization scope

aslr_comparison.txt
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
ASLR with Paging (How Modern Linux Works):
 
Process A:                           Process B:
┌────────────────────┐               ┌────────────────────┐
│ Virtual Address    │               │ Virtual Address    │
│ 0x7F3A_BC00_0000  │               │ 0x7F8E_1200_0000  │
│    (randomized)    │               │    (randomized)    │
└─────────┬──────────┘               └─────────┬──────────┘
          │                                    │
          │ Page Table A                       │ Page Table B
          │ Entry: frame=0x12345               │ Entry: frame=0x12345
          │                                    │
          └──────────────┬─────────────────────┘
                         │
                         ▼
              ┌──────────────────────┐
              │   Physical Frame     │
              │   0x12345000         │
              │   (libc code page)   │
              │                      │
              │   SHARED CONTENT     │
              │   (1 physical copy)  │
              └──────────────────────┘
 
Result: Full ASLR randomization + Full sharing!
Each process has unique virtual address layout.
Physical memory contains only one copy of libc.
Attackers can't predict addresses.
 
ASLR with Segmentation (Problematic):
 
Option A - Share with fixed address (No ASLR):
┌────────────────────┐               ┌────────────────────┐
│ Segment 5: libc   │               │ Segment 5: libc   │
│ Base: 0x40000000  │←──SAME───────→│ Base: 0x40000000  │
│ (fixed for sharing)│               │ (fixed for sharing)│
└────────────────────┘               └────────────────────┘
         ▼ Shares ▼                            ▼ Shares ▼
         └─────────────┬───────────────────────┘
                       ▼
              Physical libc segment at 0x40000000
              
Problem: Attacker knows libc is always at 0x40000000!
 
Option B - Randomize addresses (No sharing):
┌────────────────────┐               ┌────────────────────┐
│ Segment 5: libc   │               │ Segment 5: libc   │
│ Base: 0x40000000  │               │ Base: 0x60000000  │
│ (random A)         │               │ (random B)         │
└────────────────────┘               └────────────────────┘
         ▼                                     ▼
    Physical copy A                       Physical copy B
    at 0x40000000                         at 0x60000000
    
Problem: Two physical copies needed - defeats sharing!

Sharing Granularity Trade-offs

The choice of sharing granularity—segments vs pages—has profound implications.

The False Sharing Problem (Paging):

With page-level sharing, unrelated data in the same page may be "accidentally" shared, causing issues when one process modifies its portion:

false_sharing.txt
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
// False Sharing Example in Paged Systems
 
Shared Page (4KB) containing mixed data:
┌─────────────────────────────────────────────────────────────┐
│  Offset 0-1000: Shared read-only constants (OK to share)   │
│  Offset 1000-2000: Process A private data                  │
│  Offset 2000-3000: Process B private data                  │
│  Offset 3000-4096: More shared constants                   │
└─────────────────────────────────────────────────────────────┘
 
Problem: If Process A writes to offset 1500:
  1. Page is marked read-only (for sharing)
  2. Write causes protection fault
  3. OS must examine fault:
     - Is this a COW situation?
     - Or a genuine protection violation?
  4. If COW, entire page is copied
     - Including the shared constants (wasteful)
     - Including Process B's private data (wrong!)
 
This happens because paging doesn't understand program semantics.
A segment-based system would never mix private data from two
processes in the same segment.
 
Solution approaches in paged systems:
  1. Careful memory layout to avoid mixing
  2. Align shared regions to page boundaries
  3. Use larger pages for homogeneous data
  4. Compiler/linker awareness of sharing

Semantic Clarity vs Flexibility Trade-off:

Segmentation: Semantic Clarity

•Share meaningful units (code, data)
•No false sharing by design
•Simpler sharing semantics
•Natural protection boundaries
•Less metadata overhead per shared unit

Paging: Fine-Grained Flexibility

•Share any arbitrary pages
•Address flexibility (ASLR)
•Demand paging integration
•Predictable COW behavior
•Works with virtual memory naturally

Summary: Sharing Trade-offs

Key Takeaways

•Segmentation shares logical units (segments), providing semantic clarity and natural protection boundaries
•Paging shares physical units (pages), providing flexibility and fine-grained control
•Copy-on-Write is simpler and more efficient with paging due to fixed granularity and no contiguous allocation requirement
•ASLR is natural with paging (different virtual addresses, same physical frames) but problematic with pure segmentation
•False sharing is a paging concern that requires careful memory layout to avoid
•Modern systems prefer paging for sharing because flexibility and demand paging integration outweigh segmentation's semantic advantages

Sharing Mechanics Mastered

You now understand the fundamental differences in how segmentation and paging approach memory sharing. The next page explores protection differences—how each scheme enforces access control and prevents unauthorized memory access.