Segmentation 

Segmentation is a memory-virtualization technique that improves upon the simple base-and-bounds approach by dividing a process’s address space into logical pieces called segments.

Instead of treating the entire address space as one large block, segmentation treats:

• Code

• Heap

• Stack

as separate regions, each with its own base and bounds.

---

Why Segmentation Is Needed

With simple base and bounds:

• The entire virtual address space must be placed contiguously in physical memory.

• Even unused space (e.g., gap between heap and stack) occupies physical memory.

• Large address spaces (e.g., 4GB) waste huge amounts of memory.

• Hard to support sparse address spaces.

Problem:

👉 Too much wasted physical memory
👉 Poor flexibility

---

Core Idea of Segmentation

Instead of one base/bounds pair:

➡ Have one base and bounds pair per segment

Each segment:

• Is a contiguous region

• Has its own:

  • Base register

  • Bounds register

  • Growth direction

  • Protection bits

---

Logical Segments

Typical process layout:

Segment	Purpose
Code	Program instructions
Heap	Dynamic memory (malloc)
Stack	Function calls & local variables

Each can be placed independently in physical memory.

Table : Segment Register Values

Segment	Base Address	Size (Bounds)
Code	32 KB	2 KB
Heap	34 KB	2 KB
Stack	28 KB	2 KB

---

Hardware Support

The MMU maintains per-segment:

Segment	Base	Size (Bounds)	Grows Positive?	Protection
Code	32KB	2KB	Yes	Read + Execute
Heap	34KB	2KB	Yes	Read + Write
Stack	28KB	2KB	No	Read + Write

---

How Address Translation Works

A virtual address is divided into:

Segment Number | Offset

Example (14-bit address):

• Top 2 bits → segment selector

• Remaining 12 bits → offset

How Hardware Identifies the Segment

In segmentation, the hardware determines:

1. Which segment the address belongs to

2. The offset within that segment

---

Explicit Segmentation Approach

• The top few bits of the virtual address identify the segment.

• The remaining bits represent the offset inside that segment.

• This method was used in systems like VAX/VMS.

---

Example (14-bit Virtual Address)

Structure:

| Segment (2 bits) | Offset (12 bits) |

Since there are 3 segments (code, heap, stack):

• 2 bits are enough to select the segment.

Segment Selection:

• 00 → Code segment

• 01 → Heap segment

• 10 → Stack segment

---

Example Translation

Virtual address: 4200

• Top 2 bits = 01 → Heap segment

• Remaining 12 bits = offset = 104

---

Translation Algorithm

1. Extract segment number.

2. Extract offset.

3. Check:

   offset < bounds
   

4. If valid:

   Physical Address = Base[Segment] + Offset
   

5. Otherwise:
   → Raise segmentation fault.

---

Example Translation (Code Segment)

Virtual address = 100
Segment = Code
Base = 32KB

Physical address:

32KB + 100 = 32868

If offset exceeds segment size → protection fault.

---

Stack Segment (Negative Growth)

Stacks grow downward.

Example:

• Stack base = 28KB

• Virtual address = 15KB

• Offset must be converted to negative

Steps:

1. Compute offset inside stack

2. Convert to negative offset

3. Add to base

Example result:

28KB + (-1KB) = 27KB

Hardware must:

• Track growth direction

• Adjust offset calculation accordingly

---

Segmentation Fault

Occurs when:

• Offset ≥ segment size

• Writing to read-only segment

• Executing non-executable memory

Hardware traps to OS → process usually terminated.

---

Sharing Support

Segmentation allows efficient code sharing.

If code segment is:

• Read-only

• Executable

Multiple processes can share same physical memory for code.

Each process still believes it owns private memory.

---

Coarse vs Fine-Grained Segmentation

Coarse-Grained

• Few large segments (code, heap, stack)

• Simple

Fine-Grained

• Many small segments

• Requires segment tables

• Used in early systems like Multics

• More flexible but complex

---

OS Responsibilities

Segmentation improves memory efficiency, but it requires active operating system support. The OS must handle context switching, memory allocation, and fragmentation management.

---

1️⃣ Saving and Restoring Segment Registers

Each process has its own:

• Code segment (base + bounds)

• Heap segment (base + bounds)

• Stack segment (base + bounds)

During a Context Switch:

The OS must:

• Save the current process’s segment registers.

• Load the next process’s segment register values.

• Ensure correct base/bounds before execution resumes.

This guarantees:

• Proper address translation.

• Process isolation.

• Memory protection.

---

2️⃣ Allocating Physical Memory for Segments

Unlike the simple base-and-bounds model (one large contiguous block), segmentation requires:

• Multiple segments per process.

• Each segment may have a different size.

• Each must be placed contiguously in physical memory.

The OS must:

• Locate free physical space for each segment.

• Track allocated and free memory regions.

---

3️⃣ External Fragmentation Problem

Over time, memory becomes filled with:

• Many small, non-contiguous holes.

• Segments of varying sizes.

Even if total free memory is sufficient, it may not be contiguous.

Example Problem:

• 24KB total free memory.

• Split into three small holes.

• A process requests 20KB.

• Allocation fails due to lack of one contiguous block.

This is called external fragmentation.

---

4️⃣ Compaction

One solution is memory compaction.

The OS:

1. Stops running processes.

2. Copies segments to make them contiguous.

3. Updates segment base registers.

4. Creates one large free block.

Disadvantages:

• Memory copying is expensive.

• High CPU overhead.

• Poor performance impact.

---

5️⃣ Free-Space Management Algorithms

Instead of compaction, the OS often uses allocation algorithms to reduce fragmentation.

Common strategies:

Algorithm	Description
First-Fit	Allocate first block large enough
Best-Fit	Allocate smallest suitable block
Worst-Fit	Allocate largest available block
Buddy System	Split memory into power-of-two blocks

These aim to:

• Keep larger free regions available.

• Reduce fragmentation effects.

However:
👉 External fragmentation can never be completely eliminated.

---

6️⃣ Key Responsibilities of the OS

In segmentation, the OS must:

• Maintain segment tables.

• Save/restore segment registers on context switch.

• Allocate and deallocate segment memory.

• Track free memory regions.

• Handle external fragmentation.

• Possibly perform compaction.

• Enforce protection and isolation.

---

---

Advantages of Segmentation

✔ Reduces internal fragmentation
✔ Supports sparse address spaces
✔ Enables sharing
✔ Fast hardware translation
✔ Better than single base/bounds

---

Limitations

❌ External fragmentation
❌ Still requires contiguous physical memory per segment
❌ Not flexible for very sparse large heaps
❌ Memory management complexity increases

---

 Big Picture

Segmentation improves memory virtualization by:

• Splitting address space logically

• Allowing independent relocation

• Providing protection and sharing

However:

It still cannot completely solve memory fragmentation and flexibility issues.

👉 Which leads to the next major solution: Paging.

---

Summary

Segmentation =

Multiple base & bounds registers
One per logical region
Hardware selects segment
Offset added to base
Bounds + protection checked

It balances:

• Efficiency

• Protection

• Better memory usage

But does not eliminate fragmentation.