Segmentation: short notes (Operating Systems)

Introduction

A programmer does not think of a program as one linear array of bytes. It is a collection of logical units: the main code, a few library modules, global data, a heap and a stack, each of a different size and each able to grow on its own. Segmentation gives each such unit its own address space, called a segment, so that a logical address is a pair (segment number, offset).

Each segment is placed in physical memory as one contiguous block, exactly as a whole process is placed in Contiguous Memory Allocation and Fragmentation. The hardware therefore needs a base and a limit for every segment, kept in a segment table. Segmentation makes protection and sharing natural, because they apply to whole logical units, but it brings back external fragmentation. Combining it with Paging, Page Tables and TLB keeps the logical view and removes the fragmentation.

The segment table and address translation with its two traps, protection and sharing, fragmentation, segmentation with paging, and a comparison with pure paging are the standard facts.

Prerequisites

Contiguous Memory Allocation and Fragmentation: base and limit registers, placement strategies and external fragmentation, all of which now apply per segment.

Core concepts

Two-dimensional logical addresses

A logical address is $(s, d)$ : segment number $s$ and offset $d$ within the segment. With an address of $n$ bits split into $b_s$ segment bits and $b_d$ offset bits, a process can have up to $2^{b_s}$ segments and each segment can be at most $2^{b_d}$ bytes long. For example, a 16-bit address with a 4-bit segment number allows 16 segments of up to $2^{12} = 4{,}096$ bytes each.

Unlike a page number, the segment number is not just the high-order bits of a linear address chosen by the hardware: the compiler and linker assign code, data and stack to segments, and the offset is measured from the start of the segment.

The segment table

Each process has a segment table with one entry per segment:

Field	Meaning
Base	Starting physical address of the segment
Limit	Length of the segment in bytes
Protection bits	Read, write, execute (for example code: read and execute only)
Valid bit	The segment exists (and, with virtual memory, is in memory)

The segment-table base register (STBR) points to the table and the segment-table length register (STLR) holds the number of segments the process uses.

How translation works

For a logical address $(s, d)$ :

If $s \ge \text{STLR}$ , trap: invalid segment number.
Read entry $s$ of the segment table (base $B_s$ , limit $L_s$ ).
If $d \ge L_s$ , trap: segment overflow (addressing error). This check is on the offset, before any addition.
Check the protection bits against the kind of access; a violation traps.
The physical address is $B_s + d$ .

The arithmetic mapping below assumes the selected segment exists/is present and the requested access is permitted. Missing/present-bit and protection failures can trap in addition to the two size checks.

\text{physical}(s, d) = \begin{cases} B_s + d & \text{if } s < \text{STLR} \text{ and } d < L_s,\\ \text{trap} & \text{otherwise.} \end{cases}

Pseudocode for the hardware check, with 0-based segment numbers and offsets:

Text

TRANSLATE-SEGMENT(s, d, access):
    if s >= STLR then trap INVALID-SEGMENT
    (base, limit, prot, valid) <- SegmentTable[s]
    if not valid then trap INVALID-SEGMENT
    if d >= limit then trap SEGMENT-OVERFLOW
    if access not in prot then trap PROTECTION
    return base + d

Every reference costs one extra memory access for the segment-table entry unless the entry is cached; real hardware keeps recently used entries in registers (the x86 segment registers hold a descriptor copy) or in a small associative memory.

A segment table to work with

Segment	Base	Limit	Use
0	2,200	600	code (read, execute)
1	5,100	1,400	data (read, write)
2	900	300	stack (read, write)
3	7,000	1,200	heap (read, write)
4	3,600	950	library code (read, execute)

STLR is 5.

Logical address	Check	Result
(0, 430)	$430 < 600$	2,630
(1, 1400)	$1400 \not< 1400$	trap: segment overflow
(2, 299)	$299 < 300$	1,199
(3, 1250)	$1250 \not< 1200$	trap: segment overflow
(4, 0)	$0 < 950$	3,600
(5, 10)	$5 \not< 5$	trap: invalid segment number

Write to (0, 100): the offset is within the limit, but segment 0 is code without write permission, so the access traps as a protection violation even though the address is legal.

Segment-table translation with a limit check — Figure 1. Translating (0, 430) and (1, 1400) with the segment table above: offset 430 is below segment 0's limit of 600, so the physical address is $2200 + 430 = 2630$ ; offset 1400 equals segment 1's limit, so the comparison fails and the hardware traps.

Memory layout of the example

The five segments occupy 900 to 1,199, 2,200 to 2,799, 3,600 to 4,549, 5,100 to 6,499 and 7,000 to 8,199. They do not overlap, and the gaps between them are holes that later segments must fit into, which is external fragmentation exactly as in contiguous allocation. The total size of the five segments is 4,450 bytes.

Protection per segment. Code segments are read and execute only; a stack segment is read and write. Because each segment is one logical unit, one set of bits covers the whole unit. A paged system must instead set the bits on every page, and a page may mix code and data.
Sharing. Two processes share a segment by having entries with the same base and limit in their segment tables. A shared code segment that contains jumps to its own addresses must have the same segment number in every process that shares it, or it must use only offsets relative to the segment.
Growth. A segment can grow by raising its limit if the memory after it is free; otherwise the OS moves it, which needs only a new base in the segment table.

Fragmentation

Segments vary in size, so placing them is a dynamic-storage-allocation problem with first fit or best fit, and memory develops external fragmentation. Compaction is possible because the base can be changed at run time. There is no internal fragmentation in pure segmentation: a segment gets exactly its length (apart from rounding to an allocation unit). External fragmentation is milder than in whole-process allocation because segments are smaller than processes, but it does not disappear.

Segmentation with paging

Paging each segment keeps the logical structure and removes external fragmentation. The offset $d$ is split into a page number within the segment and an offset within the page; each segment has its own page table, and the segment-table entry points to it instead of holding a base address.

Text

TRANSLATE-PAGED-SEGMENT(s, d, access):
    if s >= STLR then trap INVALID-SEGMENT
    (pt, limit, prot, valid) <- SegmentTable[s]
    if not valid then trap INVALID-SEGMENT
    if d >= limit then trap SEGMENT-OVERFLOW
    if access not in prot then trap PROTECTION-FAULT
    p <- floor(d / P); o <- d mod P             -- P is the page size
    (f, page_valid, page_prot) <- pt[p]
    if not page_valid then trap PAGE-FAULT
    if access not in page_prot then trap PROTECTION-FAULT
    return f * P + o

Example. Pages of 1 KB; segment 2 has limit 6,000, and entry 4 of its page table holds frame 17. For $(2, 5000)$ : $5000 < 6000$ , the page is $\lfloor 5000/1024 \rfloor = 4$ and the offset is $5000 - 4096 = 904$ , so the physical address is $17 \times 1024 + 904 = 18{,}312$ . For $(2, 6100)$ the limit check fails before paging is consulted.

Sizes. With 32-bit logical addresses, an 8-bit segment number and a 24-bit offset, a segment can be up to 16 MB. With 4 KB pages the 24-bit offset splits into a 12-bit page number and a 12-bit page offset, so a segment's page table has up to 4,096 entries, and each segment wastes on average half a page to internal fragmentation.

Historical systems. MULTICS paged its segments, and the Intel x86 in protected mode translates a selector and offset through a descriptor table into a 32-bit linear address, which the paging unit then translates (Tanenbaum 3.7.2 and 3.7.3). The 64-bit x86 mode keeps segmentation only in a vestigial form and relies on paging.

Paging versus segmentation

Aspect	Paging	Segmentation
Unit	Fixed-size page, chosen by the hardware	Variable-size segment, chosen by the program's structure
Visible to the programmer	No: one linear address space	Yes: addresses are (segment, offset)
Fragmentation	Internal (last page)	External (holes between segments)
Table entry	Frame number plus status bits	Base, limit and protection bits
Check per reference	Valid bit (and page number within the table length)	Segment number within STLR and offset below the limit
Protection and sharing	Per page; a page may mix kinds of data	Per logical unit, natural
Growing data structures	Need a large linear space	Each segment grows independently

Worked examples

Address fields

A machine has 20-bit logical addresses with a 4-bit segment number. A process may have at most $2^4 = 16$ segments and each segment may be up to $2^{16} = 65{,}536$ bytes. If a segment-table entry holds a 24-bit base, a 17-bit length limit (to represent 65,536) and 3 protection bits plus a valid bit, an entry needs 45 bits, rounded to 6 bytes, and a full table needs $16 \times 6 = 96$ bytes.

Which addresses are legal?

Using the table above, the legal offsets of segment 2 are 0 to 299 (physical 900 to 1,199). Logical (2, 300) traps, though the physical address 1,200 would exist; the hardware never computes it.

Important properties and observations

Two checks protect every reference: segment number against STLR and offset against the limit. Both compare logical quantities.
The offset equal to the limit is already outside the segment, because the limit is a length.
Segmentation alone has external fragmentation and no internal fragmentation; paged segmentation has internal fragmentation (half a page per segment on average) and none external.
Sharing and protection work on logical units, which is the main advantage over pure paging.

Common misconceptions.

"The limit is the last legal address." It is the length; the last legal offset is limit minus 1.
"A legal address cannot trap." A legal offset can still violate protection, for example a write to a read-only code segment.
"Segmentation removes fragmentation." It replaces process-sized holes with segment-sized holes; only paging removes external fragmentation.

GATE examination perspective

Translation tables. For each (s, d) check $s$ first, then $d < \text{limit}$ , then add the base. Watch offsets equal to the limit.
Field sizes. Segment bits give the number of segments; offset bits give the maximum segment size.
Paged segmentation. Do the limit check on the full offset, then split it into page and page offset.
Comparison questions. Internal versus external fragmentation, who chooses the unit, and where protection is applied.

Summary

Contiguous Memory Allocation and Fragmentation: prerequisite. Placement and external fragmentation of variable-size blocks.
Paging, Page Tables and TLB: related. Fixed-size pages, the alternative and the complement to segments.

Segmentation

Introduction

Prerequisites

Core concepts

Two-dimensional logical addresses

The segment table

How translation works

A segment table to work with

Memory layout of the example

Fragmentation

Segmentation with paging

Paging versus segmentation

Worked examples

Address fields

Which addresses are legal?

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Two-dimensional logical addresses

The segment table

How translation works

A segment table to work with

Memory layout of the example

Protection and sharing

Fragmentation

Segmentation with paging

Paging versus segmentation

Worked examples

Address fields

Which addresses are legal?

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps