Segmentation

The programmer’s view of memory

A real program is not one flat blob of bytes. It has natural pieces: the code, the stack, the heap, global data, perhaps a shared library. Segmentation gives the OS the same view: memory is a collection of segments, each a contiguous block of its own length, and an address says which segment and where inside it.

This is different from paging, which chops memory into equal, invisible pieces. Segments are variable-sized and meaningful.

Logical address and segment table

A logical address is a pair

(s, d)    s = segment number,   d = offset inside that segment

The OS keeps a segment table for each process. Row s stores two numbers:

Field	Meaning
base	Where segment s starts in physical memory.
limit	The length of the segment in bytes.

The textbook example in the 3D model has five segments:

Segment	Base	Limit	Occupies physical addresses
0	1400	1000	1400 to 2399
1	6300	400	6300 to 6699
2	4300	400	4300 to 4699
3	3200	1100	3200 to 4299
4	4700	1000	4700 to 5699

Translating an address

The hardware (the MMU) performs three steps on every memory access:

1. Use s to look up base and limit in the segment table. If there is no row s, trap: invalid segment.
2. Protection check: if d ≥ limit, trap (a segmentation fault). Valid offsets run from 0 to limit − 1.
3. Otherwise the physical address is base + d.

Logical address	Check	Result
(2, 53)	53 < 400 ✓	4300 + 53 = 4353
(3, 852)	852 < 1100 ✓	3200 + 852 = 4052
(4, 0)	0 < 1000 ✓	4700
(0, 1222)	1222 ≥ 1000 ✗	trap
(1, 400)	400 ≥ 400 ✗	trap (one byte past the end)
(7, 5)	no segment 7	trap

Real tables also keep permission bits per segment (read, write, execute). That gives segmentation cheap protection: the code segment can be read-only and executable, the stack read-write but not executable. It also allows sharing: two processes can have table rows pointing to the same physical code segment.

One more cost: every memory reference first reads the segment table from memory, so it costs two memory accesses. Real CPUs keep recently used segment entries in fast registers or a cache, just as a TLB caches page-table entries.

Allocating segments, and external fragmentation

Because segments have different lengths, the OS must find a hole big enough for each one, exactly like the dynamic partitioning in memory allocation: first fit, best fit or worst fit.

The 3D layout starts with four holes: 1400, 800, 600 and 1300 bytes, 4100 bytes free in all. Now a process asks for a 2000-byte segment. No hole is large enough, although plenty of memory is free. This is external fragmentation: free space exists, but not in one piece.

There are two ways out:

• Compaction: slide all the segments to one end of memory, update every base in the segment tables, and merge all holes into one. It works because programs only see logical addresses, but it costs a lot of copying while the processes wait.
• Swap a segment out to disk, or fall back to paging.

After compaction in the model, the five segments sit at 0 to 3899 and one hole of 4100 bytes remains, so the 2000-byte request succeeds at base 3900.

Segmentation has no internal fragmentation: a segment is exactly as large as requested. Paging is the opposite: no external fragmentation, but the last page of each segment wastes space.

Segmentation versus paging

	Segmentation	Paging
Unit	Variable size, follows program structure	Fixed size (e.g. 4 KB), invisible to the program
Address	(segment, offset)	(page, offset) split by the hardware
Table entry	base and limit	frame number
External fragmentation	yes	no
Internal fragmentation	no	yes (last page)
Sharing and protection	natural, per segment	per page

Many systems combine them: segmentation with paging, as in MULTICS and the old 32-bit x86. The segment gives the logical structure, and each segment is divided into pages, so segments can be placed in non-contiguous frames. Modern 64-bit systems mostly use only paging.

Code

MEMORY = 8000
table = {0: (1400, 1000), 1: (6300, 400), 2: (4300, 400), 3: (3200, 1100), 4: (4700, 1000)}  # segment -> (base, limit)

def translate(s, d):
    """Logical address (segment s, offset d) -> physical address, or a trap."""
    if s not in table:
        return f'trap: no segment {s}'
    base, limit = table[s]
    if d >= limit:
        return f'trap: offset {d} is outside segment {s} (limit {limit})'
    return base + d

def holes():
    """The free gaps between segments, as (start, size)."""
    gaps, end = [], 0
    for base, limit in sorted(table.values()):
        if base > end:
            gaps.append((end, base - end))
        end = base + limit
    if end < MEMORY:
        gaps.append((end, MEMORY - end))
    return gaps

def allocate(size):
    """First fit: put a new segment into the first hole that is big enough."""
    for start, gap in holes():
        if gap >= size:
            seg = max(table) + 1
            table[seg] = (start, size)
            return seg, start
    free = sum(g for _, g in holes())
    return f'no single hole of {size} ({free} free in total: external fragmentation)'

def compact():
    """Slide every segment down to address 0, keeping their order."""
    nxt = 0
    for seg, (base, limit) in sorted(table.items(), key=lambda kv: kv[1][0]):
        table[seg] = (nxt, limit)
        nxt += limit

for s, d in [(2, 53), (3, 852), (0, 1222), (4, 0), (1, 400), (7, 5)]:
    print((s, d), '->', translate(s, d))
# (2, 53) -> 4353
# (3, 852) -> 4052
# (0, 1222) -> trap: offset 1222 is outside segment 0 (limit 1000)
# (4, 0) -> 4700
# (1, 400) -> trap: offset 400 is outside segment 1 (limit 400)
# (7, 5) -> trap: no segment 7
print('holes', holes(), 'free', sum(g for _, g in holes()))
# holes [(0, 1400), (2400, 800), (5700, 600), (6700, 1300)] free 4100
print(allocate(2000))
# no single hole of 2000 (4100 free in total: external fragmentation)
compact()
print(table)
# {0: (0, 1000), 1: (3500, 400), 2: (2100, 400), 3: (1000, 1100), 4: (2500, 1000)}
print('holes', holes())
# holes [(3900, 4100)]
print(allocate(2000))
# (5, 3900)
print(translate(5, 1999), translate(5, 2000))
# 5899 trap: offset 2000 is outside segment 5 (limit 2000)

Common mistakes

• Allowing d == limit. The valid offsets are 0 to limit − 1. The check is d < limit.
• Mixing up base and limit. The base is a location; the limit is a length. The upper end of a segment is base + limit − 1, not limit.
• Thinking segmentation has internal fragmentation. A segment is sized exactly, so it has none. Its problem is external fragmentation.
• Forgetting that compaction changes bases. After compaction every moved segment has a new base in the table, but the logical addresses in the program stay the same.
• Confusing a segment number with a page number. A segment is a variable-length logical piece chosen by the programmer or compiler; a page is a fixed-size piece chosen by the OS.