Difficulty: Intermediate
What is segmentation? How does it differ from paging, and what is segmented paging?
Paging and segmentation both map logical addresses to physical ones, but they start from two very different philosophies. Paging divides memory into equal, arbitrary chunks that the programmer never sees. Segmentation divides memory into variable-size pieces that correspond to how programmers think about their program. A useful analogy is a book. Paging is like cutting a book into identical 10-page bundles regardless of chapter boundaries, so a chapter may get split across bundles. Segmentation is keeping each chapter as its own unit, chapters having different lengths.
In segmentation, a program is a collection of logical units called segments: the main program, functions, the stack, the heap, the symbol table, global data. A logical address is a pair (segment number, offset). The OS keeps a segment table for each process, where each entry holds a base (starting physical address of the segment) and a limit (length). Translation: use the segment number to find the entry, check that offset is less than limit (otherwise raise a segmentation fault trap), and compute physical address as base plus offset. Because segments correspond to program structure, it is natural to attach protection and sharing to them: mark the code segment read-only and executable, mark the stack non-executable, and share a library's code segment between processes.
Now the differences. Segment size is variable, whereas page size is fixed by hardware. Segmentation is visible to the programmer or compiler, paging is invisible and handled by the OS and hardware. Segmentation suffers from external fragmentation because variable-size chunks leave awkward holes in memory that may need compaction, whereas paging suffers from internal fragmentation in the last page. Paging address translation splits a single linear address by bit positions, while segmentation needs an explicit two-part address. Paging is better for efficient memory utilization and simple allocation, while segmentation is better for logical organization, protection and sharing.
Wait, does the address in a modern program have a segment? On x86-32, yes, hardware segment registers (CS, DS, SS) exist, but modern 64-bit operating systems use a flat memory model where segment bases are effectively zero and paging does all the real work. The term segmentation fault survives historically: it signals an invalid memory access, even though the mechanism is now a page fault that the OS cannot resolve.
The hybrid approach is segmented paging, used by the original Intel 80386 and Multics. The address space is first divided into segments, and each segment is then paged. A logical address is (segment, page, offset). The segment table entry points to a page table for that segment instead of a base address. This keeps the logical benefits of segmentation such as protection and sharing, while eliminating external fragmentation by allocating pages in fixed-size frames. The price is more table lookups per translation, which the TLB mitigates, and more table overhead.
If asked for a quick numerical example: with a segment table entry base = 1400 and limit = 1000 for segment 2, the logical address (2, 400) maps to 1400 + 400 = 1800, but (2, 1100) exceeds the limit and traps.
segmentation, paging, segment table, logical address, protection