Segmentation

Now translate eight addresses. Each line is base plus offset, after the limit test.

Three of the eight trap, and two of them trap on an offset exactly equal to the limit. The test is strictly less than, and a question will include exactly that case.

Notice the segments are not in order in physical memory: segment 1 is at 6300, above segment 4 at 4700. The operating system put each segment wherever there was a hole big enough, which is the freedom segmentation buys and the fragmentation it costs.

What segmentation is good at

Three things, and each is a real advantage over one block per process.

1. Each segment grows on its own. The stack growing does not threaten the heap: they are

different segments with different bases, and only the stack's own limit constrains it.

1. Protection is per segment, and can differ per segment. The code segment can be marked read

only and execute, the data segment read and write and not execute. A program that jumps into its data is caught. One base and limit for the whole process cannot express that at all.

1. Sharing is natural. Two processes running the same program can have segment 0 entries with

the same base, so one copy of the code serves both. That is Chapter fourteen of Module 1's shared text, implemented.

The third has a catch worth knowing: a shared code segment must be the same segment number in every process that shares it, because a jump inside the code contains a segment number. If it is segment 0 in one process and segment 2 in another, the jump goes to the wrong place.

What segmentation is bad at, and why paging replaced it

Segments are variable sized, so segmentation has external fragmentation, exactly as Chapter seventy's variable partitions do, and for the same reason: a hole must be found that is big enough for the whole segment.

Segmentation is better than one block per process, because the pieces are smaller and a smaller piece is easier to place. It is not a cure, because the pieces are still variable in size. Paging's insight is to make every piece the same size, and that removes external fragmentation entirely.

Which is why real machines did both: segmentation with paging, where each segment is itself paged. The Intel architecture worked exactly that way, and modern systems have dropped the segmentation half and kept the paging.

Distinctions that carry marks

The last two rows are the deepest difference and a question about it wants them. A segment has a limit because segments differ in size; a page needs none because every page is full. And the programmer chooses the segments, while pages are cut by the hardware wherever the page size falls.

What it does not mean

A segment is not a page. A segment is a logical piece of a program, of whatever size that piece is. A page is a fixed sized piece of an address space with no meaning at all.

Segmentation is not obsolete as an idea. Every program still has a code segment, a data segment and a stack, and the permissions on them are still different. What is obsolete is implementing those divisions with a segment table rather than with page permissions.

The segment number is not computed by the hardware. The program supplies it. That is the property that makes segmentation visible to the programmer and paging invisible.

Per segment limits do not remove the need for a stack limit. They give the stack its own limit, which is a much better thing than sharing the process's.

Quick revision

• Segmentation divides a program into its natural, variable sized pieces: code, data,

heap, stack, library.

• A logical address is a segment number and an offset, and the program supplies both.
• Each segment table entry holds a base and a limit, where the limit is a length.

Two registers give the table's position and its length.

• Translation: check the segment number against the table length; check the offset is

strictly less than the limit, or trap with an addressing error; then the physical address is base plus offset.

• Gains: each segment grows independently, protection is per segment and can differ, and

sharing one segment between processes is natural.

• A shared segment must have the same segment number in every process, because a jump carries

one.

• Segments are variable sized, so segmentation has external fragmentation. That is why

paging, whose pieces are all the same size, replaced it.

Test yourself

1. What is a segment, and what does a logical address look like? A logical, variable sized

piece of a program such as the code, the stack or an array. The address is a segment number together with an offset within that segment, both supplied by the program.

1. What does each segment table entry hold? A base, the physical address where the segment

begins, and a limit, the length of the segment.

1. Give the translation steps. Check the segment number is less than the segment table length

register; check the offset is strictly less than the segment's limit, trapping with an addressing error if not; then add the base to the offset.

1. Segment 2 has base 4300 and limit 400. Translate offsets 399 and 400. 399 is below the

limit, so 4300 + 399 = 4699. 400 is not strictly below 400, so it traps.

1. Give three advantages of segmentation over one block per process. Each segment grows

independently, so a growing stack cannot damage the heap; protection is per segment and can differ, so code can be read only and data non executable; and one segment can be shared between processes with the same base in each.

1. What must be true of a shared segment's number, and why? It must be the same number in

every process that shares it, because a jump within the code carries a segment number with it.

1. Why did paging replace segmentation? Segments are variable sized, so a hole big enough for

a whole segment must be found and external fragmentation results. Paging makes every piece the same size, so any free frame fits any page and external fragmentation disappears.