Why (not) segmentation?

Question

I am studying operating systems and the x86 architecture, and while I was reading about segmentation and paging I naturally was curious how modern OSes handle memory management. From what I found Linux and most other operating systems essentially shun segmentation in favor of paging. A few of the reasons for this that I found were simplicity and portability.

What practical uses are there for segmentation (x86 or otherwise) and will we ever see robust operating systems using it or will they continue to favor a paging based system.

Now I know this is a loaded question but I am curious how segmentation would be handled with newly developed operating systems. Does it make so much sense to favor paging that no one will consider a more 'segmented' approach? If so, why?

---

And when I say 'shun' segmentation I am implying that Linux only uses it as far as it has to. Only 4 segments for user and kernel code/data segments. While reading the Intel documentation I just got the feeling that segmentation was designed with more robust solutions in mind. Then again I was told on many occasions how over complicated the x86 can be.

---

I found this interesting anecdote after being linked to Linux Torvald's original 'announcement' for Linux. He said this a few posts later:

Simply, I'd say that porting is impossible. It's mostly in C, but most people wouldn't call what I write C. It uses every conceivable feature of the 386 I could find, as it was also a project to teach me about the 386. As already mentioned, it uses a MMU, for both paging (not to disk yet) and segmentation. It's the segmentation that makes it REALLY 386 dependent (every task has a 64Mb segment for code & data - max 64 tasks in 4Gb. Anybody who needs more than 64Mb/task - tough cookies).

I guess my own experimentation with x86 led me to ask this question. Linus didn't have StackOverflow, so he just implemented it to try it out.

Answer 1

With segmentation it would be, for example, possible to put each dynamically allocated object (malloc) in its own memory segment. Hardware would check segment limits automatically, and the whole class of security bugs (buffer overruns) would be eliminated.

Also, since all segment offsets start at zero, all compiled code would automatically be position independent. Calling into another DLL would boil down to a far call with constant offset (depending on the called function). This would greatly simplify linkers and loaders.

With 4 protection rings, it is possible to devise more fine-grained access control (with paging you have only 2 protection levels: user and supervisor) and more robust OS kernels. For example, only ring 0 has full access to the hardware. By separating the core OS kernel and device drivers into rings 0 and 1, you could make a more robust and very fast microkernel OS where most of the relevant access checks would be done by HW. (Device drivers could get access to hardware through I/O access bitmap in the TSS.)

However.. x86 is a bit limited. It has only 4 "free" data segment registers; reloading them is rather expensive, and it is possible to simultaneously access only 8192 segments. (Assuming you want to maximize the number of accessible objects, so the GDT holds only system descriptors and LDT descriptors.)

Now, with 64-bit mode segmentation is described as "legacy" and hardware limit checks are done only in limited circumstances. IMHO, a BIG mistake. Actually I don't blame Intel, I mostly blame developers, the majority of which thought that segmentation was "too complicated" and longed for flat address space. I also blame the OS writers who lacked the imagination to put segmentation to good use. (AFAIK, OS/2 was the only operating system which made full use of segmentation features.)

Answer 2

The short answer is that segmentation is a hack, used to make a processor with a limited ability to address memory exceed those limits.

In the case of the 8086, there were 20 address lines on the chip, meaning that it could physically access 1Mb of memory. However, the internal architecture was based around 16 bit addressing, probably due to the desire to retain consistency with the 8080. So the instruction set included segment registers that would be combined with the 16-bit indexes to allow addressing of the full 1Mb of memory. The 80286 extended this model with a true MMU, to support segment-based protection and addressing of more memory (iirc, 16Mb).

In the case of the PDP-11, later models of the processor provided a segmentation into Instruction and Data spaces, again to support the limitations of a 16-bit address space.

The problem with segmentation is simple: your program must explicitly work around the limitations of the architecture. In the case of the 8086, this meant that the largest contiguous block of memory that you could access was 64k. if you needed to access more than that, you would have to change your segment registers. Which meant, for a C programmer, that you had to tell the C compiler what sort of pointers it should generate.

It was a lot easier to program the MC68k, which had a 32-bit internal architecture and a 24-bit physical address space.

Answer 3

For 80x86 there are 4 options - "nothing", segmentation only, paging only, and both segmentation and paging.

For "nothing" (no segmentation or paging) you end up with no easy way to protect a process from itself, no easy way to protect processes from each other, no way to handle things like physical address space fragmentation, no way to avoid position independent code, etc. Despite all these problems it might (in theory) be useful in some situations (e.g. embedded device that only runs one application; or maybe something that uses JIT and virtualises everything anyway).

For segmentation only; it almost solves the "protect a process from itself" problem, but it takes a lot of work-arounds to make it usable when a process wants to use more than 8192 segments (assuming one LDT per process), which makes it mostly broken. You almost solve the "protect processes from each other" problem; but different pieces of software running at the same privilege level can load/use each other's segments (there's ways to work around that - modifying GDT entries during control transfers and/or using LDTs). It also mostly solves the "position independent code" problem (it can cause a "segment dependant code" problem but that's much less significant). It doesn't do anything for the "physical address space fragmentation" problem.

For paging only; it doesn't solve the "protect a process from itself" problem much (but let's be honest here, this is only really a problem for debugging/testing code written in unsafe languages, and there's much more powerful tools like valgrind anyway). It completely solves the "protect processes from each other" problem, completely solves the "position independent code" problem, and completely solves the "physical address space fragmentation" problem. As an added bonus it opens up some very powerful techniques that aren't anywhere near as practical without paging; including things like "copy on write", memory mapped files, efficient swap space handling, etc.

Now you'd think that using both segmentation and paging would give you the benefits of both; and in theory it can, except that the only benefit you gain from segmentation (that isn't done better by paging) is a solution to the "protect a process from itself" problem that nobody really cares about. In practice what you do get is the complexities of both and the overhead of both, for very little benefit.

This is why almost all OSs designed for 80x86 don't use segmentation for memory management (they do use it for things like per-CPU and per-task storage but that's mostly just for convenience to avoid consuming a more useful general purpose register for these things).

Of course CPU manufacturers aren't silly - they aren't going to spend time and money optimising something that they know nobody uses (they're going to optimise something that almost everyone uses instead). For this reason CPU manufacturers don't optimise segmentation, which makes segmentation slower than it could be, which makes OS developers want to avoid it even more. Mostly they only kept segmentation for backward compatibility (which is important).

Eventually, AMD designed long mode. There was no old/existing 64 bit code to worry, so (for 64-bit code) AMD got rid of as much segmentation as they could. This gave OS developers yet another reason (no easy way to port code designed for segmentation to 64-bit) to continue avoiding segmentation.

Answer 4

I'm rather stunned that in all the time since this question was posted that nobody has mentioned the origins of segmented memory architectures and the true power that they can afford.

The original system which either invented, or refined into useful form, all the features surrounding the design and use of segmented paged virtual memory systems (along with symmetric multi-processing and hierarchical filesystems) was Multics (and see also the Multicians site). Segmented memory allows Multics to offer a view to the user that everything is in (virtual) memory, and it allows the ultimate level of sharing of everything in direct form (i.e. directly addressable in memory). The filesystem becomes simply a map to all the segments in memory. When properly used in a systematic way (as in Multics) segmented memory frees the user from the many burdens of managing secondary storage, and sharing of data, and inter-process-communications. Other answers have made some hand-wavy claims that segmented memory is more difficult to use, but this is simply not true, and Multics proved that with resounding success decades ago.

Intel created a hobbled version of segmented memory the 80286 that although it is quite powerful, its limitations prevented it from being used for anything truly useful. The 80386 improved upon these limitations, but market forces at the time pretty much prevented the success of any system that could truly take advantage of these improvements. In the years since it seems all too many people have learned to ignore the lessons of the past.

Intel also tried early on to build a more capable super-micro called the iAPX 432 that would have far surpassed anything else at the time, and it had a segmented memory architecture and other features strongly oriented towards object oriented programming. The original implementation was just too slow though, and no further attempts were made to fix it.

A more detailed discussion of how Multics used segmentation and paging can be found in Paul Green's paper Multics Virtual Memory - Tutorial and Reflections

Answer 5

Some architectures (like ARM) don't support memory segments at all. If Linux had been source-dependent on segments, it couldn't have been ported to those architectures very easily.

Looking at the broader picture, the failure of memory segments has to do with the continuing popularity of C and pointer arithmetic. C development is more practical on an architecture with flat memory; and if you want flat memory, you choose memory paging.

There was a time around the turn of the 80's when Intel, as an organization, was anticipating future popularity of Ada and other higher-level programming languages. This is basically where some of their more spectacular failures, like the awful APX432 and 286 memory segmentation, came from. With the 386 they capitulated to flat memory programmers; paging and a TLB was added and the segments were made resizable to 4GB. And then AMD basically removed segments with x86_64 by making the base reg a dont-care/implied-0 (except for fs? for TLS I think?)

Having said that, the advantages of memory segments are obvious - switching address spaces without having to repopulate a TLB. Maybe someday someone will make a performance-competitive CPU that supports segmentation, we can program a segmentation-oriented OS for it, and programmers can make Ada/Pascal/D/Rust/another-langage-that-doesn't-require-flat-memory programs for it.

Answer 6

Segmentation was a hack / workaround to allow up to 1MB of memory to be addressed by a 16 bit processor - normally only 64K of memory would have been accessible.

When 32 bit processors came along you could address up to 4GB of memory with a flat memory model and there was no longer any need for segmentation - The segment registers were re-purposed as selectors for the GDT / paging in protected mode (although you can have protected mode 16-bit).

Also a flat memory mode is far more convenient for compilers - you can write 16-bit segmented programs in C, but its a tad cumbersome. A flat memory model makes everything simpler.

Answer 7

Segmentation is a huge burden for applications developers. This is where the big push came from to do away segmentation.

Interestingly I often wonder how much better i86 could be if Intel striped out all legacy support for these old modes. Here better would imply lower power and maybe faster operation.

I guess one could argue that Intel soured the milk with 16bit segments leading to a developer revolt of sorts. But let's face it a 64k address space is nothing especially when you look at modern app. In the end they had to do something because the competition could and did market effectively against the address space issues of i86.

Answer 8

Segmentation leads to slower page translations and swapping

For those reasons, segmentation was largely dropped on x86-64.

The main difference between them is that:

• paging splits memory into fixed sized chunks
• segmentation allows different widths for each chunk

While it might appear smarter to have configurable segment widths, as you increase memory size for a process, fragmentation is inevitable, e.g.:

|   | process 1 |       | process 2 |                        |
     -----------         -----------
0                                                            max

will eventually become as process 1 grows:

|   | process 1        || process 2 |                        |
     ------------------  -------------
0                                                            max

until a split is inevitable:

|   | process 1 part 1 || process 2 |   | process 1 part 2 | |
     ------------------  -----------     ------------------
0                                                            max

At this point:

• the only way to translate pages is to do binary searches over all pages of process 1, which takes an unacceptable log(n)
• a swap out of process 1 part 1 could be huge since that segment could be huge

With fixed sized pages however:

• every 32-bit translation does only 2 memory reads: directory and page table walk
• every swap is an acceptable 4KiB

Fixed sized chunks of memory are simply more manageable, and have dominated current OS design.

See also: https://stackoverflow.com/questions/18431261/how-does-x86-paging-work