Segmentation and segmented paging

Why it exists

Paging splits a program into equal pieces that mean nothing to the programmer. But a program is naturally made of parts: the main code, a library, a stack, a heap, a table of data. Each part has its own size, its own protection (code is read-only, data is writable) and may be shared. Segmentation makes these parts visible to the hardware: a logical address names a segment and an offset within it, and each segment has its own base and limit. It matches the programmer's view, makes protection and sharing natural, and brings back the problem paging solved: segments have different sizes, so memory fragments externally. Segmentation combined with paging uses the strengths of both. GATE asks for translations with a segment table, for the trap conditions, and for comparisons with paging.

Prerequisites

You need the translation by table and the page-table calculations from paging.

Precise definitions

Segment. A logical unit of a program (the main program, a procedure, a stack, the symbol table, an array), of variable size. The user view of memory is a collection of segments. The compiler or loader numbers them.

Logical address. A pair $(s, d)$: the segment number $s$ and the offset $d$ within the segment. In binary it is $s$ followed by $d$; if the address has $m$ bits of which $b$ are the segment number, there are $2^b$ segments of at most $2^{m-b}$ bytes each.

Segment table. One entry per segment, holding the segment's base (the physical address where it starts) and its limit (its length). The segment-table base register (STBR) points to the table in memory and the segment-table length register (STLR) gives the number of segments the process uses.

Translation of $(s, d)$.

1. If $s \ge \text{STLR}$ the segment does not exist: trap.
2. Read the entry $(\text{base}_s, \text{limit}_s)$.
3. If $d \ge \text{limit}_s$: trap (the offset lies beyond the end of the segment: a segmentation fault).
4. Otherwise the physical address is $\text{base}_s + d$.

The legal offsets are $0, \ldots, \text{limit}_s - 1$.

Protection and sharing. Each entry can carry protection bits (read, write, execute) so that the code segment is read-only; a segment can be shared by giving the same base in several processes' segment tables (the code of an editor, a library); sharing is at the level of whole logical units.

Fragmentation. Segments are variable in size and each needs contiguous physical memory, so segmentation suffers from external fragmentation (the same problem as variable partitions, memory management basics), with the same placement rules and compaction; it has no internal fragmentation (a segment takes just what it needs).

Segmentation compared with paging.

Segmentation with paging. Each segment is itself divided into pages. A logical address is $(s, d)$ where the offset $d$ is split into a page number within the segment and an offset in the page. The segment table entry holds, instead of a base, the address of that segment's page table (and its limit); then the page table gives the frame. This removes external fragmentation (frames are all the same size) and keeps the logical structure. It costs more memory accesses per reference (segment table, page table, data: three, without a TLB) and some internal fragmentation in the last page of each segment. A segment of $L$ bytes in pages of $P$ bytes needs $\lceil L/P \rceil$ pages and wastes $(-L) \bmod P$ bytes. This is the scheme of the MULTICS system, and in a modified form of the Intel IA-32 architecture, where the segmentation unit turns a logical address into a linear address that the paging unit translates.

How it works

The segment table has four segments with bases 2200, 6100, 4000 and 9000 and limits 800, 350, 500 and 1200. The animation translates six addresses $(s, d)$: the logical address is a 3-bit segment number followed by an 11-bit offset. Look at the boundary case $(1, 350)$: the limit of segment 1 is 350, so the legal offsets are 0 to 349; offset 350 traps. The last address names segment 4, which does not exist (STLR is 4).

Worked examples

#include <stdio.h>
 
struct seg { unsigned base, limit; };
 
int main(void) {
    struct seg table[4] = {{2200, 800}, {6100, 350}, {4000, 500}, {9000, 1200}};
    unsigned n = 4;
    unsigned pairs[6][2] = {{0, 120}, {1, 349}, {1, 350}, {2, 0}, {3, 1199}, {4, 10}};
    for (int i = 0; i < 6; i++) {
        unsigned s = pairs[i][0], d = pairs[i][1];
        if (s >= n) { printf("(%u, %4u): no such segment -> trap\n", s, d); continue; }
        if (d >= table[s].limit) { printf("(%u, %4u): offset beyond the limit %u -> trap\n", s, d, table[s].limit); continue; }
        printf("(%u, %4u): base %u + %u = %u\n", s, d, table[s].base, d, table[s].base + d);
    }
    return 0;
}

(0,  120): base 2200 + 120 = 2320
(1,  349): base 6100 + 349 = 6449
(1,  350): offset beyond the limit 350 -> trap
(2,    0): base 4000 + 0 = 4000
(3, 1199): base 9000 + 1199 = 10199
(4,   10): no such segment -> trap

Cheat box

Traps and GATE patterns

Connections

Segmentation is the logical-unit view where paging is the fixed-size one, and it inherits the external fragmentation of contiguous allocation. The program's text, data, heap and stack of a C program (C memory layout) are natural segments. Combining the two uses a page table per segment (page table structures). The base-limit hardware of process address space is a segment table of one entry.

PYQs

Self-check

Revision card

References