Segment‑Paging Memory Management: How Segments and Pages Join Forces

Introduction

The author uses a moving‑box analogy: pure paging scatters items into numbered boxes, making it hard to locate a specific object, while pure segmentation groups items by room, leading to low space utilization; segment‑paging first divides memory into segments (rooms) and then fills each segment with pages (boxes), achieving a perfect combination.

Core Concept

Segment‑Paging Principle

logical address = segment number + page‑in‑segment + offset

// Diagram of address conversion omitted for brevity

Segment Table and Page Table

# segment_table structure
segment_table = {
    0: {"base": 1000, "limit": 500, "page_table": {...}},
    1: {"base": 2000, "limit": 1000, "page_table": {...}},
    2: {"base": 3000, "limit": 2000, "page_table": {...}}
}
# page_table structure (each segment has its own page table)
page_table = {
    0: 5,   # virtual page 0 → physical frame 5
    1: 12,  # virtual page 1 → physical frame 12
    2: 3    # virtual page 2 → physical frame 3
}

def translate(logical_addr):
    segment_num = logical_addr >> 12          # high bits: segment number
    page_in_segment = (logical_addr >> 6) & 0x3F # middle bits: page within segment
    offset = logical_addr & 0x3F               # low bits: offset within page
    seg_entry = segment_table[segment_num]
    page_frame = seg_entry["page_table"][page_in_segment]
    physical_addr = (page_frame << 6) | offset
    return physical_addr

Address Translation Process

Step 1: Split logical address into segment, page, and offset.
Step 2: Look up the segment table to obtain the corresponding page table.
Step 3: Use the page‑in‑segment index to retrieve the physical page frame from the page table.
Step 4: Combine the page frame with the offset to form the physical address.

Two‑Level Page Tables

To reduce the memory occupied by page tables, a two‑level hierarchy is used. The first‑level table (4 KB, 1024 entries) points to second‑level tables, each also 4 KB with 1024 entries. Logical addresses are interpreted as [first‑level index][second‑level index][offset].

Advantages:
- Allocate second‑level tables only when needed.
- Save memory.

Linux Implementation

Linux actually combines segmentation and paging. On x86 the segment registers (CS, DS, SS) are essentially fixed to user or kernel space. The translation flow is:

// Logical address → linear address (segment base added)
// Linear address → physical address (page translation via two‑level page tables)

Practical Applications

Scenario 1: Inspect Process Memory Layout

# View a process's memory map on Linux
cat /proc/$(pidof bash)/maps
# Sample output:
00400000-004c2000 r-xp ... /bin/bash (code segment)
00621000-00629000 r--p ... /bin/bash (read‑only data)
00629000-00633000 rw-p ... /bin/bash (data segment)
00c00000-00c15000 rw-p ... /bin/bash (heap)
7ffd80000000-7ffd80200000 rw-p ... [stack] (stack)

Scenario 2: Memory Fragmentation

Pure paging can leave free pages that are too small for a large contiguous object, while pure segmentation suffers from internal fragmentation. Segment‑paging solves this by using segments for large objects (continuous space) and pages for small objects (fine‑grained allocation).

Scenario 3: Memory Protection

typedef struct {
    unsigned present   :1;   // page present flag
    unsigned rw        :1;   // read/write permission
    unsigned user      :1;   // user/kernel mode flag
    unsigned accessed  :1;   // accessed flag
    unsigned dirty     :1;   // dirty flag
    unsigned unused    :7;   // unused bits
    unsigned frame     :20;  // physical frame number
} page_entry_t;

Summary

Segment‑paging merges logical segmentation with physical paging.

Address format: segment + page‑within‑segment + offset.

Advantages: segment‑level protection and page‑level flexible allocation.

Drawbacks: higher address‑translation overhead and implementation complexity.

Compared with pure segment or pure page schemes, segment‑paging offers the best of both worlds at the cost of added complexity.

Linux uses a two‑level page table and largely fixes segment registers, relying on page tables for protection.