Paging and Segmentation

To solve the severe external fragmentation problems caused by contiguous memory allocation, modern operating systems use non-contiguous memory allocation schemes. The two most prominent techniques are Paging and Segmentation.

1. Paging

Paging is a memory-management scheme that permits the physical address space of a process to be non-contiguous. It completely eliminates external fragmentation.

How Paging Works

1. Physical Memory (Frames): The physical RAM is broken into fixed-sized blocks called frames.
2. Logical Memory (Pages): The logical memory (the process size) is broken into blocks of the exact same size called pages.
3. Execution: When a process is to be executed, its pages are loaded into any available memory frames from the backing store (disk).

The Page Table

Because the pages of a single process can be scattered randomly across physical memory, the OS needs a way to track them. It maintains a Page Table for every process.

• The CPU generates a Logical Address, which is divided into two parts: a Page Number ($p$) and a Page Offset ($d$).
• The Page Number is used as an index into the Page Table. The Page Table contains the base physical address (the Frame Number) where that page is actually stored in RAM.
• The Frame Number is combined with the Page Offset to define the exact physical memory address.

2. Segmentation

While paging views memory as a flat array of fixed-size blocks (which is how the computer hardware views it), Segmentation is a memory-management scheme that supports the programmer's view of memory.

A logical address space is a collection of segments. Each segment has a name and a length. For example, a C program is typically compiled into several distinct segments:

• The Code/Text Segment
• The Data Segment (global variables)
• The Heap Segment
• The Stack Segment
• Standard C library Segment

How Segmentation Works

Instead of breaking the program up into arbitrary fixed-size pages, the program is broken into these logical segments, which are of variable length.

• The CPU generates a logical address consisting of a Segment Number ($s$) and an Offset ($d$).
• A Segment Table maps the two-dimensional logical address to a one-dimensional physical address.
• Each entry in the segment table has a segment base (the starting physical address) and a segment limit (the length of the segment).

If the offset $d$ is legally between 0 and the segment limit, the physical address is calculated as base + offset. If the offset is greater than the limit, the OS throws a Segmentation Fault (a very common error in C/C++ programming).

3. Paged Segmentation

Modern OS architectures (like Intel x86) combine both methods. The logical address space is divided into segments, but then each segment is further divided into fixed-size pages. This provides the programmer-friendly logical view of segmentation, while utilizing the hardware-friendly fragmentation prevention of paging.