When you write a program, you do not think of it as "page 0, page 1, page 2". You think of it as a few meaningful pieces: the code, the global variables, the heap, the stack, maybe a library or two. Each piece has its own size and its own purpose.
Paging, which we studied in the last two chapters, ignores this view completely. It chops everything into equal-sized pages, whether a page holds code, data or half of each.
Segmentation takes the opposite approach. It divides a process into variable-sized pieces that match the programmer's view of the program.
Segmentation is a memory-management scheme in which a process's logical address space is a collection of variable-sized segments (code, data, stack, heap, ...), and every logical address is a pair <segment number, offset>.
In this chapter we will see how a segment table translates addresses, work through exam-style numericals, compare segmentation with paging, look at how the two are combined (segmentation with paging), and finally see what is left of segmentation on a modern 64-bit Linux system.
The Programmer's View of Memory
Look at a typical C program:
int counter = 5; /* global data */
int square(int x) { /* code */
int result = x * x; /* local -> stack */
return result;
}
int main(void) {
int *arr = malloc(400); /* dynamic -> heap */
...
}The compiler and loader naturally produce a few separate regions:
Logical view of one process
+------------------+ segment 0 : code (read + execute)
| main, square |
+------------------+
+------------------+ segment 1 : global data (read + write)
| counter |
+------------------+
+------------------+ segment 2 : heap (grows as malloc is called)
| arr[0..99] |
+------------------+
+------------------+ segment 3 : stack (grows with function calls)
| result, x, ... |
+------------------+
Each segment has its own size, and they need not be next to each other.Notice three things about these regions:
Different sizes. The code might be 30 KB, the data 2 KB, the stack 8 KB.
Different permissions. Code should be read-only and executable; data should be writable but not executable.
Independent growth. The heap and stack grow and shrink on their own.
Segmentation makes each of these regions a separate unit of memory management, so the OS can place, protect, share and grow each one independently.
Logical Addresses in Segmentation
In paging, a logical address is a single number that the hardware splits into page number and offset. The programmer never sees the split.
In segmentation the address is two-dimensional: the program says which segment it means and how far into that segment it wants to go.
Logical address = < s , d >
s = segment number (which segment)
d = offset (how many bytes from the start of that segment)For example, <3, 120> means "byte 120 of segment 3 (the stack)". The compiler or linker decides which segment each variable and function belongs to.
If a logical address has n bits of which s bits are the segment number, then:
Maximum number of segments = 2s
Maximum size of one segment = 2n − s bytes
For a 16-bit logical address with a 4-bit segment number: up to 24 = 16 segments, each at most 212 = 4096 bytes. A segment can be smaller than the maximum; its real size is stored in the segment table.
The Segment Table
Each process has a segment table. It has one entry per segment, and each entry stores:
Field | Meaning |
|---|---|
Base | Physical address where the segment starts in memory |
Limit | Length of the segment in bytes |
Valid bit | Whether this segment exists / is in memory |
Protection bits | Read, write, execute permissions for this segment |
Two registers locate the table, just like the PTBR for paging:
STBR (Segment-Table Base Register): physical address of the current process's segment table.
STLR (Segment-Table Length Register): number of segments the process has.
On a context switch, the OS reloads STBR and STLR from the new process's PCB (see Process Control Block & Context Switching).
If you remember the base and limit registers from Memory Management Basics, segmentation is simply that idea repeated: instead of one base/limit pair for the whole process, there is one base/limit pair per segment.
How Address Translation Works
For every memory access with logical address <s, d>, the MMU does the following:
Check the segment number. If s ≥ STLR, the segment does not exist. Trap to the OS (addressing error).
Read the segment-table entry for s: get its base and limit.
Check the offset. If d ≥ limit, the access is outside the segment. Trap to the OS.
Check permissions. For example, a write to a read-only code segment traps.
Compute the physical address: physical address = base + d.
logical address
+-----+-----+
CPU ---> | s | d |
+-----+-----+
| |
| +-----------------------------+
v |
Segment table (at STBR) |
+-------+-------+ |
| limit | base | <-- entry s |
+-------+-------+ |
| | v
| | +-------------+
+-------|----------------------> | d < limit? |--- no ---> TRAP
| +-------------+
| | yes
v v
base ------------------------> (+) ---> physical addressNotice the key difference from paging: the offset is added to the base, not concatenated with a frame number. That is because a segment can start at any byte address, not only at a multiple of a fixed size.
Worked Example: Translating Addresses
A process has four segments with this segment table (all values in bytes, decimal):
Segment | Base | Limit | Physical range |
|---|---|---|---|
0 | 3000 | 600 | 3000 – 3599 |
1 | 8200 | 1400 | 8200 – 9599 |
2 | 1200 | 400 | 1200 – 1599 |
3 | 5000 | 2000 | 5000 – 6999 |
STLR = 4. Translate each logical address:
Logical address | Check | Result |
|---|---|---|
<1, 1020> | 1 < 4 ✓, 1020 < 1400 ✓ | 8200 + 1020 = 9220 |
<2, 450> | 2 < 4 ✓, 450 < 400 ✗ | Trap (offset beyond segment) |
<3, 0> | 3 < 4 ✓, 0 < 2000 ✓ | 5000 + 0 = 5000 |
<0, 599> | 0 < 4 ✓, 599 < 600 ✓ | 3000 + 599 = 3599 (last byte of segment 0) |
<3, 2000> | 3 < 4 ✓, 2000 < 2000 ✗ | Trap (valid offsets are 0 to 1999) |
<4, 10> | 4 < 4 ✗ | Trap (no segment 4) |
The two cases students get wrong most often are <0, 599> and <3, 2000>. A segment of length L has valid offsets 0 to L − 1, so the check is d < limit, not d ≤ limit.
Protection and Sharing
Protection Is Natural
Because each segment holds one kind of content, permissions fit neatly:
Segment | Typical permissions | What it prevents |
|---|---|---|
Code | Read + Execute | Buggy or malicious code overwriting instructions |
Constants | Read only | Modifying string literals |
Data, heap, stack | Read + Write (no execute) | Running injected code from a buffer |
With paging, one page may contain the end of the code and the start of the data, which makes per-page permissions awkward. With segmentation, the boundary is exactly where the programmer's logical boundary is. The limit check also catches array accesses that run past the end of a segment.
Sharing Is Natural Too
Suppose 50 students run the same text editor. The editor's code is identical for all of them. With segmentation, every process's segment table can point its code segment at the same base address:
Process A segment table Physical memory Process B segment table
seg 0 (code) base 40000 ---> +---------------+ <--- seg 0 (code) base 40000
seg 1 (data) base 12000 | editor code | seg 1 (data) base 70000
| (one copy) |
+---------------+
A's data at 12000, B's data at 70000: private.Only one copy of the code is in memory, but each process still has its own private data segment. The shared code segment must be read-only so that one process cannot change the code under another.
A subtle textbook point: if the shared code refers to itself using <segment, offset> addresses (for example a jump to <0, 200>), then every sharing process must use the same segment number for it, otherwise the jump would land in a different segment in some process.
The Big Problem: External Fragmentation
Segments have variable sizes, so placing them in physical memory is exactly the contiguous allocation problem from Contiguous Memory Allocation & Fragmentation, only with more, smaller pieces. The OS must find a hole big enough for each segment using first fit, best fit or worst fit.
Physical memory after segments come and go
| OS | A.code | free 3 KB | B.data | free 2 KB | A.stack | free 4 KB |
A new segment of 6 KB cannot be placed,
even though 3 + 2 + 4 = 9 KB is free. --> external fragmentationExternal fragmentation: yes. Free memory gets broken into holes between segments.
Internal fragmentation: essentially none. A segment gets exactly the bytes it needs (apart from tiny rounding to an allocation unit).
Compaction is possible because segments are relocated through the base field: move the segment, update its base, and the program does not notice. But copying large segments is slow.
Because each segment is smaller than a whole process, fragmentation is usually less severe than with one-block-per-process allocation. It is still the main reason pure segmentation lost to paging.
Paging vs Segmentation
Point | Paging | Segmentation |
|---|---|---|
Unit size | Fixed (pages/frames, e.g. 4 KB) | Variable (segments of any length) |
Division done by | Hardware/OS, invisible to programmer | Compiler/programmer, matches program structure |
Logical address | One-dimensional; split into p and d | Two-dimensional: <s, d> |
Translation | frame number concatenated with offset | base + offset, after checking limit |
Table entry | Frame number + bits | Base + limit + bits |
Internal fragmentation | Yes (last page) | Practically none |
External fragmentation | None | Yes |
Protection/sharing | Per page; possible but less natural | Per logical unit; very natural |
Growing a region | Easy: add pages anywhere | Hard: segment may need to be moved |
Free-space management | Simple free-frame list | Hole list with first/best fit |
In one sentence: paging is good for the machine (no external fragmentation, simple allocation), segmentation is good for the programmer (logical units, natural protection and sharing). The obvious next idea is to combine them.
Segmentation with Paging
In segmented paging (also called paged segmentation), the logical address space is divided into segments, and then each segment is itself paged. Each segment has its own page table, and the segment-table entry points to that page table instead of to a block of physical memory.
Logical address: | s | p | d |
| | |
| | +-------------------------------+
v | |
Segment table: entry s -> (page-table base, segment length)|
| |
v |
Page table of segment s: entry p -> frame f |
| |
v v
Physical address = | f | d |What we gain:
The logical structure (protection and sharing per segment) from segmentation.
No external fragmentation from paging: a segment's pages can sit in any free frames.
A small segment needs only a small page table, so we do not waste table space on unused parts of the address space.
What we pay: an extra table lookup, so more work on a TLB miss, and internal fragmentation in the last page of each segment. The historic Multics system used this design, and Intel's 32-bit x86 (IA-32) supported it in hardware.
Numerical: Paged Segmentation
A system allows up to 8 segments per process, each segment at most 64 KB. Pages are 4 KB and a page-table entry is 4 bytes.
Segment number bits = log2(8) = 3
Offset within a segment = log2(64 K) = 16 bits, split into 4 page bits (64 KB / 4 KB = 16 pages) and 12 offset bits
Logical address = 3 + 4 + 12 = 19 bits
Largest page table for one segment = 16 entries × 4 B = 64 bytes
Now translate offset 9300 inside segment 1: 9300 ÷ 4096 gives page 2, remainder 1108. Look up entry 2 in segment 1's page table; if it says frame 7, the physical address is 7 × 4096 + 1108 = 29780. Before all this, the hardware also checks 9300 against segment 1's length.
Segmentation on Real Hardware
32-bit x86 (IA-32)
IA-32 has full segmentation followed by paging:
logical address --> [segmentation unit] --> linear address --> [paging unit] --> physical address
(selector:offset) (32-bit)The segment is chosen by a 16-bit selector held in a segment register (CS for code, DS for data, SS for stack, plus ES, FS, GS).
The selector has a 13-bit index, 1 bit to choose the table (GDT, the Global Descriptor Table, shared by all processes, or LDT, the Local Descriptor Table, private to a process) and 2 bits of requested privilege level. So each table has up to 213 = 8192 descriptors.
Each segment descriptor holds a base, a limit and access rights, which is exactly the segment-table entry we described.
The Flat Model: What Linux and Windows Actually Do
Operating systems found that full segmentation added complexity without enough benefit once paging existed. Linux and Windows on x86 set code and data segments to base 0 and limit 4 GB, so the "linear address" equals the offset and segmentation is effectively switched off. This is called the flat memory model; all real protection is done by paging.
On x86-64 (64-bit mode) the hardware itself follows this: the bases of CS, DS, ES and SS are treated as 0 and their limits are not checked. Only FS and GS keep a usable base, which is used for per-thread and per-CPU data. For example, Linux on x86-64 points FS at the current thread's thread-local storage. ARM and RISC-V have no segmentation at all.
But the Idea Is Everywhere
The idea of segments survives in software. Linux keeps, for every process, a list of memory regions (called VMAs in the kernel), each with a start, an end and permissions: that is a base, a limit and protection bits, implemented on top of paging. You can see them in /proc/self/maps. This small program prints the address of a function, a global variable, a heap block and a local variable, and then prints its own memory map:
#include <stdio.h>
#include <stdlib.h>
int initialised = 5; /* .data */
int zeroed; /* .bss */
int main(void) {
int on_stack = 1;
int *on_heap = malloc(100 * 1024); /* 100 KiB from the heap */
printf("code (main) : %p\n", (void *)main);
printf("data (initialised) : %p\n", (void *)&initialised);
printf("bss (zeroed) : %p\n", (void *)&zeroed);
printf("heap (malloc) : %p\n", (void *)on_heap);
printf("stack (local var) : %p\n\n", (void *)&on_stack);
fflush(stdout);
FILE *f = fopen("/proc/self/maps", "r");
char line[512];
while (f && fgets(line, sizeof line, f)) fputs(line, stdout);
if (f) fclose(f);
free(on_heap);
return 0;
}Output on Ubuntu (WSL2, x86-64, GCC; the program was saved as /tmp/segdemo/maps), with the C library, loader and vDSO lines replaced by ... to save space:
code (main) : 0x5f7e58814249
data (initialised) : 0x5f7e58817010
bss (zeroed) : 0x5f7e58817024
heap (malloc) : 0x5f7e878c9010
stack (local var) : 0x7ffcd40d066c
5f7e58813000-5f7e58814000 r--p 00000000 00:29 282 /tmp/segdemo/maps
5f7e58814000-5f7e58815000 r-xp 00001000 00:29 282 /tmp/segdemo/maps
5f7e58815000-5f7e58816000 r--p 00002000 00:29 282 /tmp/segdemo/maps
5f7e58816000-5f7e58817000 r--p 00002000 00:29 282 /tmp/segdemo/maps
5f7e58817000-5f7e58818000 rw-p 00003000 00:29 282 /tmp/segdemo/maps
5f7e878c9000-5f7e87903000 rw-p 00000000 00:00 0 [heap]
...
7ffcd40b1000-7ffcd40d2000 rw-p 00000000 00:00 0 [stack]Read it like a segment table:
main(0x...14249) falls in ther-xpregion: the code "segment", readable and executable but not writable.initialisedandzeroedfall in therw-pregion: the data/bss "segment", writable but not executable.The heap and the stack are separate regions that can grow independently, with a huge unmapped gap between them.
Every region starts and ends on a multiple of 0x1000 (4096): underneath, it is all pages.
The addresses will be different every time you run it because of ASLR (address space layout randomisation), a security feature covered in Protection & Security.
Why Is It Called a "Segmentation Fault"?
The name comes from segmented machines, where touching an offset beyond a segment's limit caused a fault. On Linux today the signal SIGSEGV is raised when a program touches an address that is not in any of its memory regions, or accesses a region in a way its permissions forbid (for example writing to the r-xp code region). The check is now done with page tables, but the old name stayed.
Advantages and Disadvantages of Segmentation
Advantages | Disadvantages |
|---|---|
Matches the programmer's logical view | External fragmentation |
Easy per-segment protection | Allocation needs first/best fit and possibly compaction |
Easy sharing of code or libraries | A large segment must still fit in one contiguous hole |
No internal fragmentation | Growing a segment may require moving it |
Segment table is small (one entry per segment, not per page) | Variable sizes make swapping and memory management more complex |
Common Mistakes
Concatenating base and offset. In segmentation, physical address = base + offset. Concatenation is for paging (frame number and offset).
Using ≤ for the limit check. Valid offsets are 0 to limit − 1. An offset equal to the limit traps.
Forgetting the segment-number check. If s ≥ STLR (number of segments), the access traps before the table is even read.
Saying segmentation has internal fragmentation. Pure segmentation gives external fragmentation; paging gives internal fragmentation. Segmented paging can have internal fragmentation in the last page of each segment.
Thinking modern Linux uses segmentation for memory protection. On x86-64 it uses a flat model with paging; only FS/GS bases remain in use, mainly for thread-local and per-CPU data.
Confusing a "segment" in the program (text, data, bss) with hardware segmentation. Executable file sections and memory regions are loaded into paged memory on modern systems.
Interview Questions
What is segmentation?
A memory-management scheme where a process is divided into variable-sized logical units (code, data, stack, heap) called segments. A logical address is <segment number, offset>, translated using a per-process segment table of base and limit values.
What does a segment-table entry contain?
The base (starting physical address), the limit (length), and usually a valid bit and protection bits (read/write/execute).
How is a logical address translated in segmentation?
Check s < STLR, fetch entry s, check d < limit and permissions, then physical address = base + d. Any failed check causes a trap to the OS.
Which type of fragmentation does segmentation suffer from, and why?
External fragmentation, because segments have different sizes and leave holes of odd sizes between them when they are freed. There is practically no internal fragmentation because each segment gets exactly what it needs.
Why do segmentation and paging get combined?
Segmentation gives logical protection and sharing; paging removes external fragmentation and makes allocation simple. Paging each segment gets both benefits, at the cost of an extra lookup.
Does Linux use segmentation?
Only minimally. On x86 it uses a flat model (base 0, maximum limit), and on x86-64 the hardware ignores the bases of most segment registers. FS and GS are used for thread-local and per-CPU data. Memory protection is done by paging, while Linux keeps "segment-like" memory regions (VMAs) in software.
Why does a program crash with "segmentation fault"?
It touched memory it is not allowed to: an unmapped address such as a NULL or freed pointer, or a mapped region with the wrong permission such as writing to code. The kernel sends SIGSEGV. The name is historical, from limit violations on segmented machines.
Give one advantage of segmentation over paging for sharing.
A whole logical unit such as a library's code can be shared with one segment-table entry and protected as read-only, instead of sharing and protecting many separate pages, some of which may mix code and data.
Summary
Segmentation divides a process into variable-sized logical segments such as code, data, heap and stack.
A logical address is <s, d>. The segment table gives base and limit for each segment; STBR and STLR locate the table.
Translation: check s < STLR and d < limit, then physical = base + d; otherwise trap.
Protection and sharing are natural because each segment is one kind of content.
Segmentation suffers from external fragmentation; paging suffers from internal fragmentation.
Segmented paging pages each segment, combining logical structure with fragmentation-free allocation (Multics, IA-32).
Modern x86-64 Linux and Windows use a flat model: protection is done by paging, and segments survive as software memory regions you can see in
/proc/self/maps.Next, Virtual Memory & Demand Paging shows how the valid bit in the page table lets a process run even when only part of it is in RAM.