Lesson 8.6: Segmentation

01 Introduction

Unit 8 has presented the classical approaches to memory management. Lesson 8.2 introduced the base-and-limit scheme, in which a process is a single contiguous region and the MMU translates by adding a base and checking against a limit. Lesson 8.4 presented the placement algorithms for dividing physical memory among such regions, and Lesson 8.5 presented the fragmentation that results. This final lesson presents segmentation, the scheme that generalises the base-and-limit idea from one region to many.

The motivation for segmentation comes from the observation that a process's address space is not a single homogeneous thing. It is a collection of logically distinct parts: the program's code, its global and static data, its heap, its stack, and often several shared libraries and memory-mapped files. Each part has its own size, its own pattern of access, and its own protection requirements. The code is read-only and shared; the data is private and writable; the heap grows dynamically; the stack grows downward and is private. Treating the whole address space as a single region conflates these distinctions and forces the operating system to handle them all in the same way.

Segmentation is the alternative: divide the address space into segments, one per logical part, and give each segment its own base and limit. Each segment can be placed independently in physical memory, so a process's memory need not be contiguous as a whole — only each segment must be contiguous. And each segment can have its own protection, so the code segment can be marked read-execute, the data segment read-write, and the stack segment read-write but not executable. The whole picture is a finer-grained version of the base-and-limit scheme, and it addresses two of the three requirements of Lesson 8.1 — allocation and protection — more flexibly.

This lesson presents segmentation in detail. It defines the segment table, describes segmented address translation, and shows how the segment table implements protection and sharing. It presents the x86 architecture's segment registers — historically the most commercially important implementation of segmentation — and explains why the architecture moved to a flat address model, in which segmentation is disabled or used only for compatibility. It presents segmentation with paging, the hybrid scheme used in the x86-64 architecture, where segmentation provides the logical view and paging provides the physical mapping. And it closes with a discussion of the relationship between segmentation and paging: how the two schemes differ, what each does better, and why every modern general-purpose system uses paging for its physical memory but retains segments as a logical abstraction.

Prerequisites

This lesson builds on the whole of Unit 8. The base-and-limit scheme from Lesson 8.2 is the direct precursor, and the discussion of fragmentation from Lesson 8.5 is the motivation for segmenting the address space. The process address space from Lesson 3.1 — code, data, heap, and stack — is the abstraction that segmentation realises. The page-table material that appears in section 4.7 is a preview of Unit 9 and is presented briefly; students unfamiliar with paging may read it as an introduction and return to it after Unit 9.

02 Learning objectives

By the end of this lesson you will be able to

Define a segment and describe how a segmented address space is organised.
Describe the segment table and trace a segmented address translation from logical to physical address.
Explain how segmentation implements protection and sharing at segment granularity.
Describe the x86 segment registers and explain why modern x86-64 uses a flat address model.
Explain segmentation with paging and describe the relationship between the two schemes.

This lesson contributes to U8.5 and U8.6, and to course learning outcomes CLO1, CLO4, and CLO6.

03 Required reading

Operating System Concepts — Chapter 9, Section 9.3, Segmentation. The standard treatment of segment tables, segmented address translation, and protection and sharing through segments.
Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.7, Segmentation. The historical development of segmentation, from the MULTICS architecture through the x86 segment registers to the modern flat model.
OSTEP — Chapter 16, Segmentation. The clearest available treatment of segmented address translation, from the base-and-bounds scheme to the general segmented scheme with per-segment base and bounds. The treatment of the segment table and the offset calculation is the basis for the worked example in this lesson.
Silberschatz et al. — Chapter 9, Section 9.3. Read the discussion of the x86 architecture's segmentation, which is the most commercially important implementation and is the one that shaped the modern transition to a flat model.
Bryant, R. E., & O'Hallaron, D. R. — Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 3, Machine-Level Representation of Programs, and Chapter 9, Virtual Memory. The x86 segment registers are discussed in the context of the architecture's history, and the modern flat model is presented in the memory chapter.
Intel Corporation. — Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3: System Programming Guide, Chapter 3, Protected-Mode Memory Management. The definitive reference for the x86 segmentation mechanism, including the GDT, LDT, segment descriptors, and the modern flat-model default.
Denning, P. J. — Virtual Memory. ACM Computing Surveys, 1970. The paper that framed the relationship between segmentation and paging for a generation of system designers. Read section 3 on segmentation.
Linux man pages: man 3 modify_ldt, man 5 proc (the /proc/<pid>/maps interface), man 2 arch_prctl (which sets the FS and GS segment bases on x86-64 for thread-local storage).

Reading strategy

Read the OSTEP chapter on segmentation first. Its treatment of the segment table and the offset calculation is the clearest available, and its worked examples are the basis for the worked example in this lesson. Then read the Tanenbaum section for the historical context, in particular the account of the x86 segment registers and the reasons the architecture moved to a flat model. Finally, skim the Intel manual chapter on protected-mode memory management if you want the full detail of the GDT, LDT, and segment descriptors; the manual is dense, but the section on the flat model and its relation to paging is worth understanding, because it is the mechanism that every x86-64 system uses today.

04 Core content

4.1 The segmentation model

In the base-and-limit scheme of Lesson 8.2, a process's entire address space is a single contiguous region. The process's logical address space runs from 0 to limit−1, and the MMU translates each logical address by adding the base register.

Segmentation generalises this by dividing the address space into segments. Each segment is a logically distinct part of the address space, with its own size and its own base. The process sees its address space not as a single flat sequence of bytes, but as a numbered collection of segments; a logical address is a pair (segment number, offset) — a segment identifier and a displacement within that segment.

The partition into segments follows the logical structure of the program. A typical C program has:

A code segment, containing the program's executable instructions.
A data segment, containing the program's global and static variables that have non-zero initial values.
A BSS segment, containing the global and static variables that are initialised to zero (from "Block Started by Symbol", a term from the IBM 7094 assembler).
A heap segment, containing dynamically allocated memory, which grows upward.
A stack segment, containing the call stack, which grows downward.

The compiler and the linker know these segments and arrange for the program's addresses to be expressed as (segment, offset) pairs. On x86, the CPU's segment registers hold the current values of the code, data, and stack segment selectors, and the addressing modes are either implicit (for the code segment, addressed by the program counter) or explicit (for the data and stack segments). The compiler emits instructions that use the segment registers, and the operating system sets the registers when a process starts and on each context switch.

Each segment has its own base and limit. The base is the physical address at which the segment begins; the limit is the size of the segment. Because segments are independent, the base of each one can be different, and the segments need not be adjacent. This is the source of segmentation's flexibility: a process's address space can be scattered across physical memory in as many pieces as it has segments, so the memory allocation problem becomes a set of smaller problems — one per segment — instead of a single large one.

Figure 8.6 — The segmentation model. A process's address space is divided into logical segments — code, data, BSS, heap, stack — each with its own size and protection requirements. Each segment is placed independently in physical memory, so the process's memory need not be contiguous. The segment table records each segment's base, limit, and protection bits, and the MMU uses it to translate a logical address (segment number, offset) to a physical address.

4.2 The segment table

The operating system maintains a segment table for each process. The segment table is an array indexed by segment number, and each entry has at least three fields:

Base: The physical address at which the segment begins. When the MMU translates an address in this segment, it adds the offset to this base.
Limit: The size of the segment. The MMU checks the offset against this limit; if the offset is greater than or equal to the limit, the access is out of bounds and the MMU raises a fault.
Protection bits: A small set of bits that describe what operations are permitted on the segment. The typical bits are read, write, and execute; the exact encoding varies between architectures. The MMU checks the requested operation against these bits and raises a fault if the operation is not permitted.

Some architectures add additional fields to the segment table entry. The x86 segment descriptor, for example, includes the segment's privilege level (used to implement the protection rings), a present bit (indicating whether the segment is currently in memory), a granularity bit (whether the limit is measured in bytes or in pages), an accessed bit (for replacement policies), and other fields for system segments. The x86 descriptor is complex, but the essential fields — base, limit, protection — are the same as in any other architecture's segment table.

On most architectures, the segment table's base address is held in a dedicated register (the segment table base register or STBR, in the textbook's terminology), and the segment table's size is held in a companion register (the segment table length register or STLR). The MMU uses these to locate the table, and the operating system updates them on each context switch. On x86, the analogous registers are the GDTR (for the Global Descriptor Table) and the LDTR (for the Local Descriptor Table), and the table is loaded with the lgdt and lldt instructions, which are privileged.

4.3 Segmented address translation

The translation of a segmented logical address to a physical address is a four-step process, performed by the MMU on every memory access.

Extract the segment number and offset. The logical address is a pair (s, d) where s is the segment number and d is the offset within the segment. In the x86 architecture, the segment number is held in a segment register (or implied by the instruction), and the offset is computed by the addressing mode; on other architectures, the pair is encoded differently.
Check the segment number against the segment table length. If the segment number is greater than or equal to the number of segments in the table, the access is invalid — the program has referred to a segment that does not exist — and the MMU raises a fault. This is a protection check on the segment number, not on the offset.
Check the offset against the segment's limit. If the offset is greater than or equal to the segment's limit, the access is out of bounds — the program has tried to reach beyond the end of the segment — and the MMU raises a fault. This is the protection check that confines the process to its own segment.
Check the protection bits. If the access is a write and the segment is not writable, or if the access is an execute and the segment is not executable, the MMU raises a fault. This is the protection check that enforces the per-segment permissions.
Add the base to the offset. The physical address is base + offset. This is the translation, and the result is placed on the memory bus.

The four steps are similar in structure to the base-and-limit scheme of Lesson 8.2, but with two important extensions. First, the segment number introduces a level of indirection: the base and limit are not fixed registers but entries in a table, and the table is indexed by the segment number. This means the process can have many segments, each with its own base and limit, and the addressing modes that compute the segment number can choose among them. Second, the protection bits extend the protection model from the binary "inside or outside" of base-and-limit to a per-segment "what operations are permitted". The code segment can be executable but not writable; the data segment writable but not executable; the stack segment writable but not executable; the read-only data segment readable but not writable. The MMU enforces these restrictions at the hardware level, without any involvement from the operating system.

Figure 8.6b — Segmented address translation. The CPU produces a logical address as a pair of segment number and offset. The MMU uses the segment number to index the segment table, obtaining the segment's base, limit, and protection bits. It checks the offset against the limit and the requested operation against the protection bits, and if both are valid, it adds the base to the offset to produce the physical address. The example shows an access that faults — offset 500 is greater than the limit 64 — and a valid access that produces physical address 12338.

4.4 Protection and sharing through segments

Segmentation's protection model is more expressive than the base-and-limit scheme's. The limit check confines a process to its own memory, but the protection bits distinguish between the kinds of access. This lets the operating system enforce a fine-grained policy that matches the logical structure of the program.

Code is read-execute. The code segment is marked read-only and executable. An attempt to write to it — as would happen if the program tried to modify its own instructions, whether deliberately or through a buffer overflow — raises a fault. This is the hardware foundation of W^X (write-xor-execute), the modern security policy that no region of memory should be simultaneously writable and executable.
Data is read-write. The data segment is marked writable but not executable. An attempt to execute data — as would happen if a buffer overflow overwrote a function pointer and the program then called through it — raises a fault. This is the hardware foundation of the defence against return-oriented programming and similar attacks.
Constants are read-only. A segment of constant data can be marked read-only and non-executable. Any write to it raises a fault.
Segments can be shared. Two processes can have segment table entries that point to the same physical memory. The shared code segment of a library is a classic example: each process has its own data and stack segments, but the code segment is shared. The sharing is efficient because the code is not duplicated in physical memory.

The sharing capability is what made segmentation particularly attractive in the 1970s and 1980s, when physical memory was scarce. A system with segmentation could share a library's code among dozens of processes without paying the memory cost of duplication. This was the principal advantage of the MULTICS system and of the early x86 architectures, and it is the same advantage that shared libraries provide today (through a different mechanism — paging — as we will see in Unit 9).

4.5 The x86 segment registers

The x86 architecture has provided segmentation since the 80286 (introduced in 1982) and is the most commercially important implementation of the scheme. The architecture has six segment registers: CS for the code segment, DS for the data segment, SS for the stack segment, ES, FS, and GS for additional data segments. Each register holds a segment selector — a 16-bit value that indexes into one of two tables, the Global Descriptor Table (GDT) or the Local Descriptor Table (LDT).

The GDT is a per-system table that holds descriptors for the segments shared by all processes — the kernel's code and data, and the default segments used by user code. The LDT is a per-process table that holds descriptors for the process's private segments. The segment selector's high bit (the table indicator) indicates which table to use; the remaining bits index into that table.

Each descriptor in the GDT or LDT is an 8-byte structure with the fields described in section 4.2: base, limit, protection bits, privilege level, present bit, granularity bit, and a few others. When the MMU translates an address, it uses the appropriate segment register's selector to find the descriptor, loads the descriptor's base and limit, performs the checks, and produces the physical address.

The x86 protection model is built on top of segmentation. The architecture has four privilege levels (called rings), numbered 0 to 3, where ring 0 is the most privileged (the kernel) and ring 3 is the least (user applications). Each segment descriptor has a privilege level, and the MMU checks that the current privilege level is at least as privileged as the segment it is accessing. This is how the CPU enforces the distinction between kernel code and user code: the kernel runs in ring 0 and can access all segments; user applications run in ring 3 and cannot access the kernel's segments.

This privilege model was the principal motivation for segmentation in the x86 architecture. It provided a hardware mechanism for isolating the operating system from user applications, which was essential for the multitasking systems that the architecture was designed to support. When the 80386 was introduced in 1985, it added paging to the architecture, and the two mechanisms were designed to work together — segmentation provided the logical view of memory and the privilege model, and paging provided the physical mapping.

4.6 Modern x86-64: the flat model

The x86-64 architecture (introduced in 2003) largely abandons segmentation for its original purpose. In 64-bit mode, the segment registers are still present, but they are mostly ignored by the hardware. The CS, DS, ES, and SS registers have their base set to 0 and their limit set to the maximum, so that the segment number is effectively zero and the offset is used directly as the logical address. This is called the flat address model: the segment registers do not partition the address space, and the address space is a single flat sequence of bytes from 0 to the maximum.

The reason for the change is that segmentation, despite its advantages, has significant drawbacks.

External fragmentation. Segments are variable-sized, so allocating them from physical memory is subject to the same external fragmentation as any variable-size allocation scheme (Lesson 8.5). On a system with many processes and many segments, the fragmentation can be severe.
Complexity. The x86 segmentation mechanism is genuinely complex: the GDT, the LDT, the descriptors, the privilege levels, the far pointers (which include the segment selector in the pointer), and the various system-level features add significant complexity to the architecture, the compiler, and the operating system.
The compiler's burden. A program's addresses have to be expressed as (segment, offset) pairs, and the compiler has to choose which segment register to use for each reference. On the 16-bit x86 architecture, this was a real constraint: a program could have at most a few segments, and a single array could not exceed 64 KB. The 32-bit architecture relaxed this, but the compiler still had to emit segment-override prefixes on many references.
Paging provides the same benefits more effectively. The protection and sharing benefits of segmentation are provided by paging at finer granularity and without external fragmentation. A page-table entry can have the same protection bits as a segment descriptor, and pages can be shared between processes by mapping the same physical frame into multiple address spaces. Paging is simpler, more flexible, and less prone to fragmentation.

The result is that modern x86-64 systems use the flat model. The segment registers CS, DS, ES, and SS are set to descriptors with base 0 and limit 2⁶⁴−1, and every memory access uses offset = logical address. The FS and GS registers are retained for a specific purpose: they can be used to implement thread-local storage, because each thread can have a different base in its FS or GS register. This is the mechanism that Linux uses for its per-thread data (including errno, which we saw in Lesson 4.5). The segment registers, which once partitioned the entire address space, are now used for a single small purpose.

Why did the flat model win?

The flat model won because paging provides everything segmentation provides, at finer granularity, without the fragmentation and complexity. Segmentation's unique contribution was the logical view — the segment number made the program's structure visible to the hardware — but the compiler can provide the same view at the software level (by laying out the segments in the address space in a fixed pattern) without requiring hardware support. The hardware's job becomes simpler: it translates a single flat sequence of addresses to physical memory, using paging to provide protection, sharing, and overcommitment.

4.7 Segmentation with paging

Although modern x86-64 uses the flat model, the 32-bit x86 architecture used segmentation with paging. This hybrid is the historically important case, and understanding it clarifies the relationship between the two mechanisms.

In the hybrid scheme, address translation is a two-stage process. The CPU produces a logical address, which is a pair (segment number, offset). The MMU uses the segment number to look up the segment descriptor, checks the offset against the limit and the protection bits, and produces a linear address by adding the segment's base to the offset. The linear address is what Lesson 8.2 called a logical address in a paging system; it is not a physical address. The second stage translates the linear address to a physical address using the page table.

Figure 8.6c — Segmentation with paging: the two-stage translation used by the 32-bit x86 architecture. The first stage translates a logical address (segment number, offset) to a linear address by looking up the segment descriptor and adding the base. The second stage translates the linear address (page number, page offset) to a physical address by looking up the page table entry and combining the frame number with the offset. Each stage performs its own protection checks, and together they provide both logical segmentation and physical paging.

The two-stage translation has two important properties.

Segmentation provides the logical view and per-segment protection. The segment number identifies which logical part of the address space the access refers to, and the segment's protection bits enforce the per-segment permissions. This is the level at which the code is marked read-execute, the data read-write, and so on.
Paging provides the physical mapping and eliminates external fragmentation. The linear address is translated to a physical address by the page table, and the pages can be placed anywhere in physical memory. The external fragmentation that segmentation would otherwise suffer is eliminated, because the linear address space does not need to be contiguous in physical memory.

The hybrid scheme was used in the 32-bit x86 architecture from the 80386 through the early 2000s. Its principal limitation was that a process's linear address space was constrained by the segments: even with paging, the segments imposed a maximum size on the address space and a complex arrangement of segment registers. The 64-bit architecture's flat model removed this constraint by setting the segments to base 0 and limit 2⁶⁴−1, leaving paging as the only mechanism for address translation.

4.8 Segmentation versus paging

Segmentation and paging are the two classical approaches to memory management beyond the base-and-limit scheme. They differ in their unit of allocation, their unit of protection, and their treatment of the address space.

Segmentation versus paging
Aspect	Segmentation	Paging
Unit of allocation	Variable-size segments, sized to the logical parts of the program	Fixed-size pages, typically 4 KB
Logical view	The address space is a numbered collection of segments	The address space is a single flat sequence of bytes
Address form	(segment number, offset)	(page number, page offset)
Protection granularity	Per segment — matches the logical structure of the program	Per page — matches the physical layout, not the logical structure
External fragmentation	Present — the same problem as any variable-size allocation	Eliminated — any free page can hold any page
Internal fragmentation	Absent — a segment is exactly the size of the logical part	Present but bounded — the last page may be partially used
Sharing	Per segment — a shared code segment is the classic example	Per page — a shared library's pages can be mapped into many processes
Address space size	Constrained by the number and size of segments	Constrained by the page table's structure
Where used today	Historically in MULTICS and 32-bit x86; now used only for specific purposes (thread-local storage on x86-64)	Universally in every modern general-purpose system

The two schemes are not mutually exclusive. The segmentation-with-paging hybrid shows that they can be combined, with segmentation providing the logical view and protection, and paging providing the physical mapping and eliminating external fragmentation. In principle, this hybrid offers the best of both: the per-segment protection of segmentation, and the fragmentation-free physical mapping of paging. In practice, the complexity of maintaining both mechanisms has led every modern architecture to simplify by choosing paging alone.

The reason paging won is instructive. Segmentation's advantages are structural — the logical view, the per-segment protection, the natural sharing of code — but they can all be provided at the software level, without hardware support. The compiler can lay out the program's segments in a fixed pattern within the address space, the operating system can use pages to enforce the protection boundaries (by making the pages that hold constants read-only, for example), and the dynamic linker can share library pages among processes. The hardware only needs to provide one mechanism, and paging is the mechanism that works at the finest granularity, imposes no fragmentation, and is simplest to implement.

4.9 Common misconceptions

"Segmentation is a form of paging."

They are different schemes. Segmentation uses variable-size segments sized to the logical parts of the program; paging uses fixed-size pages. They can be combined, but they are different mechanisms with different properties.

"Segmentation is obsolete."

Segmentation is not used for its original purpose in modern general-purpose systems, but the segment registers on x86-64 still exist and are used for thread-local storage. And the idea of segmenting the address space by logical function is universal — every program has code, data, heap, and stack, even if the hardware does not provide segments for them.

"A segment can be arbitrarily large."

A segment's size is bounded by its limit field, which on x86 is at most 20 bits (up to 4 GB with a 4 KB granularity). In the 16-bit architecture, segments were limited to 64 KB, which was a real programming constraint.

"Segmentation eliminates fragmentation."

Segmentation has no internal fragmentation because segments are sized to the logical parts of the program, but it has external fragmentation because variable-size segments are allocated from physical memory. The external fragmentation is the same problem as in contiguous allocation.

"The flat model means the address space has no structure."

The flat model means the hardware sees the address space as a flat sequence of bytes. The program still has code, data, heap, and stack, and the operating system still marks the pages that hold each part with the appropriate protection bits.

"The x86 segment registers are unused on modern systems."

The CS, DS, ES, and SS registers are set to the flat descriptor and are not used for segmentation. But FS and GS are used for thread-local storage, and on Linux x86-64 the FS register holds the base of the current thread's thread-local area.

"Segmentation and paging do the same thing."

They both translate addresses and both enforce protection, but they do so at different granularities and with different properties. Segmentation provides a logical view and per-segment protection; paging provides a physical mapping without fragmentation.

"Multics used segmentation successfully, so it should be used everywhere."

MULTICS used segmentation because it provided the security and sharing that MULTICS was designed for. But MULTICS was also complex and expensive, and the simpler architectures that followed (including the x86 family) adopted paging as the primary mechanism because it was easier to implement and provided most of the same benefits.

05 Worked example

The following example traces the segmented address translation for several accesses, showing the segment table lookup, the protection checks, and the resulting physical address.

Segmented address translation, step by step

A process has five segments, described by the following segment table:

Segment	Name	Base	Limit	Protection
0	code	8192	128 KB	read, execute
1	data	12288	64 KB	read, write
2	BSS	16384	32 KB	read, write
3	heap	20480	128 KB	read, write
4	stack	24576	64 KB	read, write

We translate five accesses and determine the outcome of each.

Segment	Offset	Access type	Segment limit	Limit check	Protection check	Physical address
0	0	execute	128 KB	0 < 128: ok	execute: permitted	8192 + 0 = 8192
0	64	execute	128 KB	64 < 128: ok	execute: permitted	8192 + 64 = 8256
1	50	write	64 KB	50 < 64: ok	write: permitted	12288 + 50 = 12338
1	500	read	64 KB	500 ≥ 64: FAULT	—	—
0	32	write	128 KB	32 < 128: ok	write: NOT permitted	—
5	0	read	—	segment number out of range	—	—

The pattern is instructive. The first three accesses succeed: the offsets are within the limits, the access types are permitted by the segments' protection bits, and the resulting physical addresses are computed by adding the segment's base.

The fourth access faults because the offset is out of bounds. The data segment is 64 KB, so offset 500 — which would be 500 bytes past the start of the segment — is within the segment only if 500 < 64. It is not, so the access is rejected. In a 64 KB segment, the valid offsets are 0 through 63, so any offset of 64 or larger is a fault.

The fifth access faults for a different reason: the access type is not permitted. Writing to the code segment is forbidden, because the code is marked read-execute. This is the protection bit at work: the hardware catches the attempt to modify code, and the operating system would deliver a signal (typically SIGSEGV) to the process.

The sixth access faults because the segment number is greater than or equal to the size of the segment table. The process has only five segments, so segment number 5 does not exist. This check is the first thing the MMU does, before consulting the segment table.

Sharing between two processes

A second process P₂ runs the same program, and its segment table is arranged to share the code segment with P₁:

Segment	Name	Base	Limit	Notes
0	code	8192	128 KB	the same physical region as P₁'s code
1	data	32768	64 KB	P₂'s own data
2	BSS	36864	32 KB	P₂'s own BSS
3	heap	40960	128 KB	P₂'s own heap
4	stack	45056	64 KB	P₂'s own stack

P₂'s segment 0 has the same base (8192) and limit (128 KB) as P₁'s. The two processes share the code in physical memory: the bytes at physical addresses 8192 through 8192+128K−1 are the same for both. P₂'s data, BSS, heap, and stack are in different physical regions, so the two processes do not share their private data.

This sharing is achieved entirely through the segment tables. The operating system sets P₂'s segment 0 base to the same value as P₁'s, and the two processes share the code. Neither process is aware that the other exists; each sees only its own logical address space, and each accesses its code at segment 0, offset whatever. The MMU translates each process's accesses independently, using that process's segment table.

Protection in the shared segment

Because the code segment is shared, it must be marked read-execute for both processes. If either process could write to the code segment, the other process's execution would be affected — a catastrophic correctness failure, and a significant security hole. The protection bits in the segment table enforce this: neither process can write to the shared code, and any attempt to do so faults.

This is a general principle of sharing: when a region of memory is shared, its protection must be the intersection of the protections required by the sharers. A region that one process needs to write and another process needs to read can be marked read-write for the first process and read-only for the second, using different segment table entries with different protection bits. But a region that one process needs to write and another needs to execute cannot be shared safely, because the writer could modify the executor's instructions. The protection model catches this: the hardware enforces whatever the segment table says, and the operating system's job is to set the protection bits correctly for each sharing arrangement.

Compaction with segments

Segmentation affects the compaction problem from Lesson 8.5. In a base-and-limit scheme, compaction means moving the process's single region to a new physical location and updating its base register. In a segmented scheme, compaction means moving one or more segments to new physical locations and updating their entries in the segment table. Because segments are independent, the operating system can compact the memory partially: it can move a small segment to fill a small hole without moving the process's other segments. This gives segmentation a significant advantage over the base-and-limit scheme for fragmentation management: the granularity of compaction is smaller, so the cost of each compaction is smaller, and compaction can be performed more frequently.

The cost of segment-level compaction is that each process must be paused while its segments are moved, and its segment table entries must be updated. Because the number of segments is typically small (a handful per process), the cost per process is bounded, and the operating system can schedule compaction around the segments that need to be moved. This is an advantage that segmentation shares with paging: the smaller the unit of relocation, the cheaper the relocation.

Comparison with the base-and-limit scheme

The table below compares segmentation with the base-and-limit scheme of Lesson 8.2 on the same workload — a process with code, data, heap, and stack.

Aspect	Base-and-limit	Segmentation
Registers per process	2 (base, limit)	Segment table with one entry per segment
Contiguity requirement	The process's entire address space must be contiguous	Each segment must be contiguous, but the segments need not be adjacent
Protection granularity	One level (inside or outside the process)	Per segment (code, data, stack protected independently)
Sharing	Not possible	Per segment (code can be shared, data cannot)
Context switch cost	Write two registers	Write the segment table base register (one register)
External fragmentation	One large fragmentation problem	Many smaller fragmentation problems, one per segment

Segmentation improves on base-and-limit in several dimensions: finer protection, sharing, and fragmentation granularity. It pays for these improvements with a more complex mechanism — the segment table — and with the need to maintain the table on every context switch and every segment operation. The cost is worth it when the system needs the additional functionality; the base-and-limit scheme remains simpler and faster when the workload does not.

06 Interactive activity

Activity · implement a segment-based memory manager

The goal of this activity is to implement a segmented memory manager, simulate the translation of segmented addresses, and observe the protection checks. Work through the steps in your course VM.

Design a segment table. Write a small program that defines a segment table for a process with the segments used in the worked example: code, data, BSS, heap, and stack. Each entry should have a base, a limit, and a set of protection bits.

struct segment {
    const char *name;
    unsigned long base;
    unsigned long limit;
    unsigned int  prot;   /* bitmask: PROT_READ, PROT_WRITE, PROT_EXEC */
};

#define PROT_READ   0x1
#define PROT_WRITE  0x2
#define PROT_EXEC   0x4

struct segment table[] = {
    { "code",  8192,  128*1024, PROT_READ | PROT_EXEC },
    { "data",  12288,  64*1024, PROT_READ | PROT_WRITE },
    { "bss",   16384,  32*1024, PROT_READ | PROT_WRITE },
    { "heap",  20480, 128*1024, PROT_READ | PROT_WRITE },
    { "stack", 24576,  64*1024, PROT_READ | PROT_WRITE },
};

#define SEGMENT_COUNT (sizeof(table) / sizeof(table[0]))

Implement the translation. Write a function that translates a segmented logical address to a physical address, performing the three checks in order.

unsigned long translate(unsigned int seg,
                       unsigned long offset,
                       unsigned int access) {
    /* 1. check seg against SEGMENT_COUNT */
    if (seg >= SEGMENT_COUNT)
        return 0;       /* invalid segment */

    struct segment *s = &table[seg];

    /* 2. check offset against s->limit */
    if (offset >= s->limit)
        return 0;       /* out of bounds */

    /* 3. check access against s->prot */
    if ((access & s->prot) != access)
        return 0;       /* protection violation */

    /* 4. return base + offset */
    return s->base + offset;
}

Test with the worked example. Write a main program that tests the translate function with the six accesses from the worked example. Verify that the first three succeed and the last three fault.

struct test {
    unsigned int seg;
    unsigned long offset;
    unsigned int access;
    const char *desc;
} tests[] = {
    { 0,   0, PROT_EXEC,              "code fetch at offset 0" },
    { 0,  64, PROT_EXEC,              "code fetch at offset 64" },
    { 1,  50, PROT_WRITE,             "data write at offset 50" },
    { 1, 500, PROT_READ,              "data read at offset 500" },
    { 0,  32, PROT_WRITE,             "code write at offset 32" },
    { 5,   0, PROT_READ,              "invalid segment number" },
};

For each test, print the result: either the physical address or the reason for the fault.

Simulate two processes sharing code. Add a second segment table representing a second process, with the same code segment base but different data, heap, and stack segments. Verify that:
- An access to segment 0 in either process produces the same physical address.
- An access to segment 1 in process 1 and process 2 produces different physical addresses.
- A write to segment 0 in either process faults.
```
struct segment table2[] = {
    { "code",  8192,  128*1024, PROT_READ | PROT_EXEC },
    { "data",  32768,  64*1024, PROT_READ | PROT_WRITE },
    /* ... */
};
```
Model segment allocation. Extend the program to model the allocation of segments from a pool of physical memory. Each segment's base is chosen by a first-fit allocator from the free list. When the process terminates, its segments are freed and coalesced.
```
struct segment *alloc_segment(const char *name,
                              unsigned long size,
                              unsigned int prot) {
    /* find a hole large enough in the free list */
    /* place the new segment at the hole's start */
    /* split the hole and update the free list */
}
```
Run a simulation with several processes being created and terminated, and observe the fragmentation of the physical memory over time.
Observe the flat model in Linux. On a Linux x86-64 system, use gdb to inspect the segment registers of a running process.
```
gdb /bin/ls
(gdb) start
(gdb) info registers cs ds es ss fs gs
(gdb) info registers fs_base gs_base
(gdb) quit
```
The CS, DS, ES, and SS registers should all hold the same selector (a flat descriptor with base 0), while FS and GS have different bases. Confirm that the flat model is in use for the general-purpose segments.
Inspect thread-local storage. Write a program with two threads, each of which has a thread-local variable. Use pthread_getspecific or the C11 _Thread_local specifier. Use gdb to inspect the FS base register in each thread; the two threads should have different FS bases, because each thread's thread-local area is at a different address.
```
#include <pthread.h>
#include <stdio.h>

static _Thread_local int tls_var;

void *worker(void *arg) {
    tls_var = (int)(long)arg;
    printf("thread %ld: tls_var at %p = %d\n",
           (long)arg, (void*)&tls_var, tls_var);
    return NULL;
}
```
This demonstrates the modern use of the x86 segment registers: not for partitioning the address space, but for providing each thread with a private region of memory.
Read the Intel manual's section on segmentation. If you have access to the Intel Software Developer's Manual, read the first few pages of Chapter 3, Protected-Mode Memory Management. What does the manual say about the flat model? What does it say about the use of segment registers in 64-bit mode? Write a short summary.

Reflect: segmentation is the historical bridge between the simple base-and-limit scheme and the paging scheme of Unit 9. It provides finer protection, sharing, and fragmentation management than base-and-limit, at the cost of a more complex mechanism. And yet every modern system uses paging alone, with segmentation reduced to a single-purpose mechanism for thread-local storage. Why? What does paging do that segmentation cannot, and why does that matter more than the additional features that segmentation provides? What does this tell us about the direction of system design: toward simpler mechanisms with finer granularity, or toward more expressive mechanisms that are harder to implement?

07 Knowledge check

Check your understanding

Question 1

Describe the segmentation model. What is a segment, and how is a segmented logical address expressed? How does segmentation differ from the base-and-limit scheme of Lesson 8.2?

Show answer

In the segmentation model, a process's address space is divided into segments, each of which is a logically distinct part of the address space with its own size and its own base. A typical program has segments for code, data, BSS, heap, and stack, and may have additional segments for shared libraries and memory-mapped files. A segmented logical address is expressed as a pair (segment number, offset): the segment number identifies which segment the address belongs to, and the offset is the displacement within that segment. The segment number is used to index into the process's segment table, and the offset is used as the position within the segment. Segmentation differs from the base-and-limit scheme in four principal ways. First, base-and-limit treats the entire address space as one region, whereas segmentation divides it into many segments, each with its own base and limit. Second, base-and-limit requires the process's address space to be contiguous in physical memory; segmentation requires each segment to be contiguous, but the segments themselves can be scattered. Third, base-and-limit enforces only the boundary of the entire region, whereas segmentation allows each segment to have its own protection bits, so the code can be read-execute and the data read-write. Fourth, base-and-limit has no sharing capability, because the region is exclusive to one process; segmentation allows segments to be shared between processes, so a shared library's code can be mapped once and used by many. The cost of these improvements is the segment table: the operating system must maintain a table of segment entries for each process, and the MMU must consult the table on every access.

Question 2

Describe the segment table. What fields does each entry contain, and how are they used during address translation? What checks does the MMU perform, and in what order?

Show answer

The segment table is a per-process array indexed by segment number. Each entry contains at least three fields: the base, which is the physical address at which the segment begins; the limit, which is the size of the segment; and the protection bits, which describe what operations are permitted on the segment (typically read, write, and execute). Architectures may include additional fields; the x86 segment descriptor, for example, includes the segment's privilege level, a present bit, a granularity bit, and an accessed bit. The MMU performs four checks and one addition on each access, in the following order. (1) Check the segment number against the segment table length. If the segment number is greater than or equal to the number of segments, the access is invalid and the MMU raises a fault. (2) Check the offset against the segment's limit. If the offset is greater than or equal to the limit, the access is out of bounds and the MMU raises a fault. (3) Check the access type against the protection bits. If the access is a write and the segment is not writable, or an execute and the segment is not executable, or a read and the segment is not readable, the MMU raises a fault. (4) Add the base to the offset. The physical address is base + offset, and the result is placed on the memory bus. The order of the checks matters: the segment-number check must precede the table lookup (to avoid reading past the end of the table), and the limit and protection checks must precede the translation (to avoid computing a physical address for an invalid access). The MMU performs all of this in hardware, on every access, without any involvement from the operating system. The operating system's role is to set up the segment table when the process starts, to update it on context switches, and to handle the faults the MMU raises.

Question 3

How does segmentation implement protection and sharing? Give an example of each, and explain how the segment table encodes the required information.

Show answer

Segmentation implements protection through the protection bits in each segment table entry. Each segment can be marked with the operations permitted on it: read, write, execute. The MMU checks the access type against the segment's bits and raises a fault if the access is not permitted. The classic example is the code segment, which is marked read-execute (not writable). An attempt to modify the program's instructions — whether deliberate, as in self-modifying code, or accidental, as in a buffer overflow that overflows into the code segment — raises a fault. This is the hardware foundation of the W^X policy (write-xor-execute), which is a central security principle in modern systems. Another example is the stack segment, which is marked read-write (not executable) to prevent code-injection attacks. Segmentation implements sharing by allowing two processes' segment tables to point to the same physical memory. The classic example is a shared library: when a process uses the C library, its code segment is mapped into the process's address space at some base, and the segment table entry for that segment points to the library's code in physical memory. Multiple processes can have segment table entries with the same base, so they all share the same physical code. The shared code must be marked read-execute (not writable) for all sharers, so that no process can modify the instructions that another process is executing. The segment table encodes the sharing by having the same base value in multiple processes' entries for the shared segment. The operating system's role is to arrange the sharing, but the hardware does not distinguish between a segment that is shared and one that is private; the translation is the same in both cases. The sharing is therefore transparent to the processes themselves, which see only their own logical address spaces.

Question 4

Describe segmentation with paging. What does each stage of the translation contribute, and why is the hybrid useful? Why did modern architectures move to a flat model with paging alone?

Show answer

Segmentation with paging is a two-stage translation scheme used by the 32-bit x86 architecture. In the first stage, the CPU produces a logical address (segment number, offset), and the segmentation unit uses the segment number to look up the segment descriptor, checks the offset against the limit and the access type against the protection bits, and computes a linear address by adding the segment's base to the offset. In the second stage, the paging unit takes the linear address

(page number, page
                  offset)

, uses the page number to look up the page-table entry, checks the page's protection bits, and computes the physical address by combining the frame number with the page offset. Each stage contributes something distinct. Segmentation provides the logical view and the per-segment protection: the segment number identifies which logical part of the address space the access refers to, and the segment's protection bits enforce the per-segment permissions. Paging provides the physical mapping and eliminates external fragmentation: the linear address is translated to a physical address by the page table, and the pages can be placed anywhere in physical memory. The hybrid is useful because it offers the best of both: the per-segment protection and sharing of segmentation, and the fragmentation-free physical mapping of paging. In principle, this is exactly what a memory-management scheme should provide. In practice, the complexity of maintaining both mechanisms led every modern architecture to simplify. The 64-bit x86-64 architecture moved to a flat model, in which the segment registers are set to base 0 and limit 2⁶⁴−1, so the segmentation stage is effectively bypassed and paging alone does the translation. The reason is that segmentation's unique contributions can be provided at the software level: the compiler can lay out the program's segments in a fixed pattern within the flat address space, the operating system can use pages to enforce the protection boundaries (by making the pages that hold constants read-only, for example), and the dynamic linker can share library pages among processes. The hardware only needs to provide one mechanism, and paging is the mechanism that works at the finest granularity, imposes no fragmentation, and is simplest to implement.

Question 5

What is the flat address model, and how does x86-64 implement it? Why are the FS and GS segment registers still used, and what purpose do they serve?

Show answer

The flat address model is a memory model in which the address space is a single flat sequence of bytes, from 0 to the maximum addressable byte. There are no segments partitioning the address space; every access is to the flat space, and the operating system uses paging (rather than segmentation) to provide protection, sharing, and overcommitment. The x86-64 architecture implements the flat model by setting the CS, DS, ES, and SS segment registers to descriptors with base 0 and limit 2⁶⁴−1. With these values, the segmentation stage of the translation is a no-op: the segment's base is 0, so adding it to the offset produces the offset itself, and the limit is the maximum, so every offset is within bounds. The segmentation stage does nothing, and the translation is effectively performed by paging alone. The FS and GS registers are retained for a specific purpose: they can be given non-zero bases to provide a per-thread region of memory. Each thread of a process can have its own value in its FS or GS register, so each thread can have a private segment that another thread cannot access by the same offset. This is the mechanism that Linux uses for thread-local storage (TLS): variables declared with the C11 _Thread_local specifier, or with the __thread extension in GCC and Clang, are stored in the thread's TLS area, and each thread's TLS area is at a different address. The operating system sets the FS base register when a thread is created, and the FS register's value distinguishes one thread's TLS from another's. This is the modern use of the x86 segment registers: not for partitioning the address space, but for providing each thread with a private region, using a mechanism that was originally designed for a very different purpose.

08 Unit discussion

Discussion prompt

This lesson closes Unit 8, and it is worth reflecting on the unit as a whole. We started with the memory hierarchy (Lesson 8.1), which showed that memory is not one thing but a stack of storage levels with different characteristics. We then examined address binding (Lesson 8.2) and dynamic loading (Lesson 8.3), which showed how programs are loaded and relocated. We studied contiguous allocation (Lesson 8.4) and fragmentation (Lesson 8.5), which are the classical approaches to dividing physical memory among processes. And we have ended with segmentation (this lesson), the scheme that divides the address space into logical segments.

A theme runs through the unit: the tension between logical structure and physical layout. Programs have logical structure — code, data, heap, stack, thread-local storage, shared libraries — and the memory system has physical constraints: the hierarchy, the fragmentation, the cost of relocation. Each technique in the unit is an attempt to reconcile the two. Segments match the logical structure; paging matches the physical constraints. The flat address model, which x86-64 has settled on, has decided in favour of the physical constraints: the hardware sees a flat address space, and the logical structure is provided by the software on top of it.

Is this the right choice? Would segmentation, if it had not been abandoned, have produced better systems? Some researchers have argued that segmentation provides security benefits that paging alone cannot, because segments are structured by the program's logic and can enforce per-logical-region protection. Others have argued that the flat model with paging is sufficient, and that the complexity of segmentation was not worth the marginal benefit.

Unit 9 will present paging and virtual memory, the mechanism that the flat model relies on. Consider, as you read the next unit, what the flat model makes possible and what it makes harder. What would a system that preserved segmentation look like, and what would it gain? Would you design it differently if you were starting from scratch today? Post your response to the Unit 8 discussion forum and reply to at least two classmates. Supports CLO1, CLO4, and CLO6.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Unit 9. Aim to spend 60–90 minutes on it.

Design a segment table. Design a segment table for a process that uses the following logical parts: an 8 KB code segment, a 2 KB read-only data segment, a 4 KB read-write data segment, a 16 KB heap segment, a 4 KB stack segment, and a 32 KB shared library code segment. For each segment, specify the protection bits and the base address (you may choose the base addresses, but they must be valid physical addresses that do not overlap). Then compute the process's total physical memory footprint.
Trace segment translation. Using the segment table from question 1, translate the following logical addresses to physical addresses (or state that they fault and why):
- (0, 0) — read
- (0, 8000) — execute
- (1, 1000) — read
- (1, 1000) — write
- (2, 3000) — write
- (3, 20000) — read
- (4, 5000) — read
- (5, 40000) — execute
- (6, 0) — read
Design a sharing arrangement. Two processes, P₁ and P₂, both use the same shared library. P₁ is read-only against the library, and P₂ has a small writable region for its own state. Design segment tables for both processes that share the library's code and any other segments that can be shared, while keeping each process's private data separate. Explain the choices.
Explain the W^X policy. Write a short paragraph (150–200 words) explaining the W^X (write-xor-execute) policy. Why is it important for security? How does segmentation enforce it? How does paging enforce it? Give one example of an attack that W^X prevents.
Compare segmentation and paging. Fill in a table comparing segmentation and paging across the following dimensions: unit of allocation, address form, protection granularity, external fragmentation, internal fragmentation, sharing, complexity, and use in modern systems. For each dimension, state what each scheme does and which scheme is more advantageous. Then write a paragraph explaining which scheme you would choose for a hypothetical new architecture, and why.
Simulate the flat model. Write a program that simulates the flat address model's use of the segment registers. The program should have a function that takes a logical address and returns the physical address, using a "flat segment table" with base 0 and limit 2⁶⁴−1. Then modify the program to use a segment table with non-zero bases, and observe the difference in the translation.

Investigate TLS on your system. Use the following program to observe how the FS register is used for thread-local storage. Compile and run, and observe the different addresses of tls_var in each thread.

#include <pthread.h>
#include <stdio.h>

static _Thread_local int tls_var;

void *worker(void *arg) {
    long id = (long)arg;
    tls_var = (int)id;
    printf("thread %ld: &tls_var = %p, tls_var = %d\n",
           id, (void*)&tls_var, tls_var);
    return NULL;
}

int main(void) {
    pthread_t t[4];
    for (long i = 0; i < 4; i++)
        pthread_create(&t[i], NULL, worker, (void*)i);
    for (int i = 0; i < 4; i++)
        pthread_join(t[i], NULL);
    return 0;
}

The four threads should print four different addresses. Then use gdb to inspect the FS base register in each thread and confirm that they differ.

Reflect. In your own words, explain why segmentation was abandoned in favour of a flat model with paging. What did segmentation provide that paging does not, and why was that not enough to justify the complexity? Then describe one situation in your own experience — a program you have written or a system you have used — where the flat model's lack of logical structure was a limitation. What would a segmented system have done differently?

10 Summary

Segmentation divides a process's address space into logical segments, each with its own base, limit, and protection bits. The process's memory need not be contiguous as a whole; only each segment must be contiguous.
A segmented logical address is a pair (segment number, offset). The segment number indexes into the process's segment table, and the offset is the displacement within the segment.
The segment table is a per-process array indexed by segment number. Each entry contains a base, a limit, and protection bits. Additional fields (privilege level, present bit, granularity) are architecture-specific.
The MMU translates a segmented address in four steps: check the segment number against the table size, check the offset against the segment's limit, check the access type against the segment's protection bits, and add the base to the offset. Each check can raise a fault.
Segmentation's protection model is more expressive than base-and-limit's: each segment can have its own permissions, so code can be read-execute, data read-write, and the stack read-write but not executable. This is the hardware foundation of the W^X policy.
Segmentation supports sharing: two processes can have segment table entries with the same base, sharing the same physical memory. The classic example is a shared library's code segment.
The x86 architecture used segmentation from the 80286 onward, with six segment registers, the GDT and LDT, and four privilege levels. The 32-bit architecture added paging, and the two worked together in a two-stage translation.
The x86-64 architecture moved to a flat address model, in which the CS, DS, ES, and SS registers are set to base 0 and limit 2⁶⁴−1, effectively bypassing segmentation. The FS and GS registers are retained for thread-local storage.
The move to the flat model was motivated by segmentation's external fragmentation, its complexity, and the fact that paging provides most of its benefits at finer granularity. The logical structure that segmentation makes visible to the hardware can be provided at the software level, by the compiler and the operating system.
Segmentation with paging is a hybrid in which segmentation provides the logical view and per-segment protection, and paging provides the physical mapping and eliminates external fragmentation. It was used in the 32-bit x86 architecture, and the modern flat model can be understood as a degenerate case in which the segmentation stage is bypassed.
The relationship between segmentation and paging is instructive: segmentation's unique contributions are logical, and the logical structure can be provided by software. Paging's unique contributions are physical, and the physical mapping requires hardware. Every modern architecture has therefore chosen paging as its fundamental mechanism, leaving segmentation as a legacy feature.

Unit 8 complete

This closes Unit 8, the main-memory unit. You now have the full picture of the classical approaches: the memory hierarchy and locality (Lesson 8.1), address binding and the three binding times (Lesson 8.2), dynamic loading and its relationship to overcommitment (Lesson 8.3), contiguous allocation and the placement algorithms (Lesson 8.4), fragmentation and the techniques that reduce it (Lesson 8.5), and segmentation (this lesson). Unit 9 presents virtual memory: the paging mechanism, the page table, the translation lookaside buffer, demand paging, page faults, page replacement, and thrashing. It is the culmination of the ideas that this unit has introduced — the address-space abstraction, execution-time binding, and the separation of logical from physical addresses — and the mechanism that every modern general-purpose system uses to manage its memory.

11 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 9, Section 9.3.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Section 3.7.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 16, Segmentation. Available online at ostep.org.
Bryant, R. E., & O'Hallaron, D. R. Computer Systems: A Programmer's Perspective, 3rd ed., Chapters 3 and 9.
Intel Corporation. Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3: System Programming Guide, Chapter 3, Protected-Mode Memory Management. The definitive reference for the x86 segmentation mechanism, including the GDT, LDT, segment descriptors, and the flat-model default.
Daley, R. C., & Dennis, J. B. Virtual Memory, Processes, and Sharing in MULTICS. Communications of the ACM, 1968. The paper that introduced the MULTICS segmentation scheme, the most influential implementation of segmentation.
Denning, P. J. Virtual Memory. ACM Computing Surveys, 1970. The paper that framed the relationship between segmentation and paging.
Love, R. Linux Kernel Development, 3rd ed., Chapter 12, Memory Management. The Linux kernel's memory management in the modern flat model, including its use of the FS and GS registers for thread-local storage.
Drepper, U. ELF Handling for Thread-Local Storage. Red Hat, 2013. The definitive treatment of how thread-local storage is implemented on Linux, including the use of the segment registers.
Linux man-pages: man 2 arch_prctl, man 3 modify_ldt, man 5 proc, man 3 pthread_getspecific.