Segmentation

Overview

The Virtual memory discussed so far consisted of virtual addresses going from 0 to some maximum address, i.e there was a single consolidated address space.
For many problems, having more than one address spaces is a much better solution. Consider an example where the compiler procedure call stack grows and shrinks with time but has been allocated contiguous virtual memory addresses.
We need for the program to be free of worries involving the contraction and shrinking of tables storing variables in a way which is similar to how virtual memory handles the problem by dividing it into overlays.
A general solution for this is to divide the virtual memory space into completely independent address spaces called segments. Every segment consists of a linear address space starting from 0 to some maximum.
The maximum may vary for each segment as segments may have variable lengths.
Because each segment constitutes a different address space, the segment may grow or shrink independently without affecting each other.

Segmentation differs from paging in a very essential way. Page sizes are fixed and are allocated frames which are also of the same fixed sized. On the other hand, the basic premise of segmentation says that segment sizes are variable.
Every process is divided into a number of chunks where each chunk is called a segment
Each process is loaded by bringing all of its segments into main memory. Every segment of the process is loaded into main memory by creating partitions dynamically matching the size of each segment. This creates an exact fit for every segment.
Segmentation is free of internal fragmentation.
Suffers from external fragmentation.
Every program/process may occupy more than one non-contiguous segment, similar to dynamic partitioning.
Consider a case where if a larger segment is evicted and a segment which is smaller is put in its place.
As the new segment is smaller it leaves an area in the segment which remains unused. This is called external fragmentation.
The 'holes' created by external fragmentation are dealt with by implementing a process called 'compaction'. This is a costly process with a large overhead and hence must not be called very often.

This is a combination of segmentation and paging which tries to take advantage of the befits of both segmentation and paging.
User's address space is divided into segments.
Each segment is further divided into equal sized pages where every page is the same size as a memory frame.
Logical address space contains the following:
- Segment number: used to index segment table who's entry gives starting address of page number.
- Page number: used to index page table.
- offset: used to indicate offset within frame.
Advantages of Segmentation with paging
- Reduces memory as opposed to paging.
- Most advantages of paging are retained while gaining segmentation advantages.
- Efficiency of pagin is combined with protection and sharing capabilities of segmentation

Quiz

Answers

1. b; 2. a; 3. a;

Based on notes by Professor Daniel Katz (professor at NYU Tandon School of Engineering).