Session 4.4 – Segmentation

Introduction to Segmentation

Segmentation is a memory management technique that supports the logical view of memory as perceived by users and programmers. Unlike paging, which divides memory into fixed-size blocks, segmentation divides memory into variable-size segments that correspond to logical units.

Segmentation Concepts

In segmentation, a logical address space is divided into segments, each representing a logical unit such as a procedure, array, or data structure.

Segment 0: Code Segment (0-5K)
  - main() function
  - helper functions
  - constant strings

Segment 1: Data Segment (0-2K)  
  - global variables
  - initialized data

Segment 2: Heap Segment (grows up)
  - malloc() allocations
  - dynamic data structures

Segment 3: Stack Segment (grows down)
  - local variables
  - function parameters

Segment Tables

The segment table maintains information about each segment, including its location in physical memory, size, and access permissions.

Segment Table Entry (64-bit):
┌────────────────────┬─────────────────┬──────────────┐
│    Base Address    │   Segment Limit │ Control Bits │
│     32 bits        │     20 bits     │   12 bits    │
└────────────────────┴─────────────────┴──────────────┘

Control Bits:
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│V│R│W│X│G│U│A│D│T│S│ Reserved │
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─────────┘

V = Valid bit (segment is loaded)
R = Read permission
W = Write permission
X = Execute permission
G = Growable segment
U = User/System access level
A = Accessed recently
D = Dirty (modified)
T = Type (code/data)
S = Shared segment

Address Translation in Segmentation

Address translation in segmentation involves mapping logical addresses (segment number, offset) to physical addresses using the segment table.

Segmented Address Translation:
1. Parse logical address into (segment#, offset)
2. Check if segment# < STLR (segment table length)
3. Calculate segment table entry address:
   STE_Address = STBR + segment# × entry_size
4. Read segment table entry from memory
5. Validate segment (check valid bit)
6. Check offset ≤ segment limit
7. Verify access permissions (R/W/X)
8. Calculate physical address:
   Physical_Address = Base + Offset

Logical Address Format:
┌─────────────────┬─────────────────────┐
│ Segment Number  │   Offset (d)        │
│   (s bits)      │   (remaining bits)  │
└─────────────────┴─────────────────────┘

Address: (2, 1024)
Segment: 2
Offset: 1024

Interpretation:
"Byte 1024 in 
 Segment 2"

Segment 2 Entry:
Base: 9300
Limit: 3072
Perms: RW-

Checks:
✓ 1024 ≤ 3072
✓ Valid bit = 1
✓ Read permitted

Calculation:
Base + Offset
= 9300 + 1024
= 10324

Result:
Physical address
10324

Protection and Sharing

Segmentation provides natural boundaries for protection and enables efficient sharing of code and data between processes.

Shared Code Example:
Process A: Segment 0 → Text Editor Code
Process B: Segment 1 → Text Editor Code
Process C: Segment 0 → Text Editor Code

All point to same physical memory:
Base Address: 15000
Only one copy loaded

Paging vs Segmentation

Both paging and segmentation solve memory management problems but take different approaches with distinct trade-offs.

Segmentation with Paging

Modern systems combine segmentation and paging to leverage the benefits of both approaches while minimizing their drawbacks.

Address Format (Segmented Paging):
┌─────────────┬─────────────┬─────────────────┐
│ Segment #   │ Page #      │ Page Offset     │
│  (s bits)   │ (p bits)    │    (d bits)     │
└─────────────┴─────────────┴─────────────────┘

Translation Process:
1. Use segment# to index segment table
2. Get page table base for this segment  
3. Use page# to index page table
4. Get frame# from page table entry
5. Combine frame# + offset = physical address

Benefits:
- Logical organization (segmentation)
- No external fragmentation (paging)  
- Flexible protection and sharing
- Support for large address spaces

Segment: 1
Page: 2  
Offset: 1024

Meaning:
"Page 2, byte 1024
 in Segment 1"

Frame 3 found
in page table

Physical Addr:
3 × 4096 + 1024
= 12288 + 1024  
= 13312

Practical Examples

Solution:

Address (1, 1500):
1. Segment 1: Base = 4500, Limit = 3000
2. Check bounds: 1500 ≤ 3000 ✓ (Valid)
3. Physical address = Base + Offset = 4500 + 1500 = 6000

Address (0, 1000) - Read access:
1. Segment 0: Base = 2000, Limit = 1500, Access = R-X
2. Check bounds: 1000 ≤ 1500 ✓
3. Check permission: Read allowed ✓
4. Physical address = 2000 + 1000 = 3000

Address (1, 3500) - Write access:  
1. Segment 1: Base = 4500, Limit = 3000, Access = RW-
2. Check bounds: 3500 ≤ 3000 ✗ (SEGMENTATION FAULT!)

Address (2, 1200) - Execute access:
1. Segment 2: Base = 8000, Limit = 2500, Access = RW-  
2. Check bounds: 1200 ≤ 2500 ✓
3. Check permission: Execute NOT allowed ✗ (PROTECTION FAULT!)

Paging Analysis:
Pages needed: ⌈12/4⌉ + ⌈8/4⌉ + ⌈4/4⌉ + ⌈6/4⌉ = 3 + 2 + 1 + 2 = 8 pages
Internal fragmentation: (8×4) - 30 = 2KB wasted
Page table entries: 2²⁰ = 1M entries (for full 32-bit space)
Page table size: 1M × 4 bytes = 4MB per process

Segmentation Analysis:
Segments needed: 4 (code, data, stack, heap)
External fragmentation: Depends on allocation history
Segment table entries: 4 entries
Segment table size: 4 × 12 bytes = 48 bytes per process

Memory Efficiency:
Paging: 30KB used, 2KB internal fragmentation (6.7% waste)
Segmentation: 30KB used, external fragmentation varies

Table Overhead:
Paging: 4MB (huge overhead for small programs)
Segmentation: 48 bytes (minimal overhead)

Session Summary