Segmentation vs Paging: A Comprehensive Comparison

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

// This program would typically have these segments:
// Segment 0: Code segment (machine instructions)
// Segment 1: Data segment (global/static variables)
// Segment 2: Stack segment (local variables, call frames)
// Segment 3: Heap segment (dynamically allocated memory)
// Segment 4: Shared library segment (libc, etc.)
 
#include <stdlib.h>
 
int global_counter = 0;        // Located in data segment (segment 1)
static int static_data[1000];  // Located in data segment (segment 1)
 
void recursive_function(int depth) {  // Code in segment 0
    int local_array[100];              // Stack allocation in segment 2
    
    if (depth > 0) {
        recursive_function(depth - 1);
    }
}
 
int main() {                           // Code in segment 0
    int* dynamic = malloc(1024);       // Heap allocation in segment 3
    recursive_function(10);
    free(dynamic);
    return 0;
}

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

// Segmentation Address Translation Algorithm
function translate_segmented_address(logical_address):
    // Extract components from logical address
    segment_number = extract_segment_number(logical_address)
    offset = extract_offset(logical_address)
    
    // Validate segment number
    if segment_number >= SEGMENT_TABLE_LENGTH:
        raise SEGMENTATION_FAULT("Invalid segment number")
    
    // Lookup segment table entry
    entry = segment_table[segment_number]
    
    // Check if segment is valid/present
    if not entry.valid:
        raise SEGMENTATION_FAULT("Segment not present")
    
    // CRITICAL: Bounds check - prevents buffer overflows
    if offset >= entry.limit:
        raise SEGMENTATION_FAULT("Offset exceeds segment limit")
    
    // Check protection bits against access type
    if access_type == WRITE and not entry.writable:
        raise PROTECTION_FAULT("Write to read-only segment")
    if access_type == EXECUTE and not entry.executable:
        raise PROTECTION_FAULT("Execute in non-executable segment")
    
    // Compute physical address
    physical_address = entry.base + offset
    return physical_address

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

// Paging Address Translation Algorithm
function translate_paged_address(virtual_address):
    // Extract components from virtual address
    page_number = virtual_address >> PAGE_OFFSET_BITS    // Upper bits
    page_offset = virtual_address & PAGE_OFFSET_MASK     // Lower bits
    
    // Validate page number
    if page_number >= PAGE_TABLE_SIZE:
        raise PAGE_FAULT("Invalid page number")
    
    // Lookup page table entry
    pte = page_table[page_number]
    
    // Check valid/present bit
    if not pte.valid:
        raise PAGE_FAULT("Page not in physical memory")
    
    // Check protection bits
    if access_type == WRITE and not pte.writable:
        raise PROTECTION_FAULT("Write to read-only page")
    if access_type == EXECUTE and not pte.executable:
        raise PROTECTION_FAULT("Execute in non-executable page")
    
    // Note: NO bounds check needed - offset is fixed size
    // and always valid within page boundaries
    
    // Compute physical address by concatenation
    frame_number = pte.frame_number
    physical_address = (frame_number << PAGE_OFFSET_BITS) | page_offset
    
    // Update accessed/dirty bits for page replacement
    pte.accessed = true
    if access_type == WRITE:
        pte.dirty = true
    
    return physical_address

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

// Segment Table Entry Structure
// Total size: typically 64 bits (8 bytes) or larger
 
struct SegmentTableEntry {
    // Core addressing fields
    uint32_t base;           // Starting physical address (32-64 bits)
    uint32_t limit;          // Segment size in bytes (allows variable sizes)
    
    // Protection and status bits
    uint8_t  valid      : 1; // Segment is present in memory
    uint8_t  readable   : 1; // Read access permitted
    uint8_t  writable   : 1; // Write access permitted  
    uint8_t  executable : 1; // Execute access permitted
    uint8_t  accessed   : 1; // Segment has been accessed
    uint8_t  dirty      : 1; // Segment has been modified
    uint8_t  privilege  : 2; // Ring level (0-3 for x86)
    
    // Additional metadata
    uint8_t  type       : 4; // Segment type (code, data, stack, etc.)
    uint8_t  granularity: 1; // Limit in bytes (0) or 4KB units (1)
    uint8_t  reserved   : 5;
};
 
// Example segment table for a simple process:
// Entry 0: Code segment  - base=0x00400000, limit=32768, R-X
// Entry 1: Data segment  - base=0x00410000, limit=65536, RW-
// Entry 2: Stack segment - base=0x7FFF0000, limit=16384, RW-
// Entry 3: Heap segment  - base=0x00800000, limit=262144, RW-

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

// Page Table Entry Structure (x86-64 example)
// Total size: 64 bits (8 bytes)
 
struct PageTableEntry {
    // Core addressing field
    uint64_t frame_number  : 40; // Physical frame number (up to 1TB RAM)
    
    // Protection and status bits (standard in most architectures)
    uint64_t present       : 1;  // Page is in physical memory
    uint64_t read_write    : 1;  // 0=read-only, 1=read-write
    uint64_t user_super    : 1;  // 0=supervisor only, 1=user accessible
    uint64_t write_through : 1;  // Write-through caching
    uint64_t cache_disable : 1;  // Disable caching for this page
    uint64_t accessed      : 1;  // Page has been read
    uint64_t dirty         : 1;  // Page has been written
    uint64_t page_size     : 1;  // Large page (2MB/1GB) indicator
    uint64_t global        : 1;  // Don't invalidate on CR3 change
    
    // Available for OS use
    uint64_t available     : 3;  // OS-defined bits
    
    // x86-64 specific
    uint64_t reserved      : 7;  // Must be zero
    uint64_t no_execute    : 1;  // NX bit - prevent code execution
};
 
// Note: Page table entries DON'T need a limit field!
// All pages are exactly PAGE_SIZE bytes (e.g., 4096)
//
// Example 4KB page table:
// Entry 0: frame=0x00000, present=1, RW=0, US=0  (kernel code)
// Entry 1: frame=0x00001, present=1, RW=1, US=0  (kernel data)
// Entry 2: frame=0x00123, present=1, RW=0, US=1  (user code)
// Entry 3: frame=0x00456, present=1, RW=1, US=1  (user data)