Memory Segmentation in the x86 platform and elsewhere

[linguofreak]

...something like the bank switching that @linguofreak mentioned as well.

Exactly like. Bank switching was ubiquitous on machines with 16-bit address spaces and no paging or segmentation. The C64 is just one of many examples.

[Schol-R-LEA]

...something like the bank switching that @linguofreak mentioned as well.

Exactly like. Bank switching was ubiquitous on machines with 16-bit address spaces and no paging or segmentation. The C64 is just one of many examples.

True; the Apple III, //e, and //c all used it, as did the CoCo - according to Wikipedia, while the base models had between 4KiB and 32KiB built-in, the later model 3 running Level II OS-9 could load up to 3 MiB over the M6809's 64KiB address space, IIRC, though I never used one myself), and add-on bank-switched memory was available for several 8-bit systems.

They were also a significant step in the history of the IBM PC, as expanded memory could bank-switch larger amounts of memory on 16-bit PCs - it probably was a major factor in the persistence of XT-class systems into the early 1990s as low-cost business machines, as by then most of the critical business software such as Lotus 1-2-3 and WordPerfect would be effectively unusable on XT systems without it.

But it is very definitely a different matter from segmentation. It is something that is part of the memory bus sub-system, not the CPU architecture, and was something the OS and applications would need to manage - even on systems such as the C64, where it is a fundamental feature of the computer , it is still something kludged onto the memory bus, and the CPU itself is oblivious to it.

[StudlyCaps]

The NES console used bank switching as well, but it was a bit of a kludge. Basically game devs found themselves running up on memory limits for static data, so they got the cartridge manufacturers to add bank switching chips onto the carts themselves.

Think they went from an 8k default up to a whopping 1MB.

[OSwhatever]

I think bank switching due to address space/lines limitations is OT in this thread. When I think about segmentation I think about segments as a protection mechanism, like in early OS/2 or early UNIX variants.

I would call bank switching a workaround for an architecture that hasn't scaled in time. There are pretty many of examples of them in the history of computers. Good thing is that they are less common now and didn't give us any benefits and only headaches. Intel PSE-36/40 also falls into this category I think.

[linguofreak]

But it is very definitely a different matter from segmentation. It is something that is part of the memory bus sub-system, not the CPU architecture, and was something the OS and applications would need to manage - even on systems such as the C64, where it is a fundamental feature of the computer , it is still something kludged onto the memory bus, and the CPU itself is oblivious to it.

In general, yes, but recall that I mentioned it in the context of the AGC, where it's less clear whether the bank switching scheme is part of the CPU architecture or part of the "chipset", or even whether the two can be meaningfully distinguished.

[linguofreak]

I think bank switching due to address space/lines limitations is OT in this thread. When I think about segmentation I think about segments as a protection mechanism, like in early OS/2 or early UNIX variants.

Well, but when discussing segmentation on the x86 platform, you have to get into how real mode segmentation influenced the development of protected mode segmentation, and real mode segmentation is entirely an address-extension scheme with no protection component to it.

[Octocontrabass]

real mode segmentation is entirely an address-extension scheme with no protection component to it.

Not exactly. Although the 8086 and 8088 don't implement any protection, they do provide all of the signals necessary for an external MMU to provide segment-based protection. Altos made a handful of 8086-with-MMU computers, and as you may have guessed, the MMU provides segment-based protection. It checks segment limits, and restricts writes or accesses to individual segments. It also provides useful non-segment-related protection, like preventing user-mode programs from doing port I/O, disabling interrupts, or using the HLT instruction.

It also does paging.

[Qbyte]

Segmentation is underrated! That said, the x86 take on it is rather nauseating. I'm currently designing a virtual machine and I plan on using segmentation for the virtual memory scheme.

I think the best approach towards segmentation is to simply use a certain number of higher (or lower) order bits of the virtual address as a segment id and the remaining bits as the offset within that segment, with each segment having a base-and-bounds pair and a set of R/W/X permissions.

The main downside of segmentation is needing physical memory compaction every now and then, but these days that's not really a problem when a) it happens rarely (mainly when loading/terminating a program), b) RAM is plentiful (16+ GB) and c) the CPU is idle around 95% of the time anyway. Other advantages paging once enjoyed over segmentation (such as swapping) are rapidly evaporating as such concepts become obsolete.

The main problem is that segmentation hasn't had proper hardware support in a mainstream processor and therefore hasn't been able to realize its potential.

[Korona]

Multitasking operating system rely more (and not less) on paging today than they did a decade ago. I don't have time to write a detailed post but things that depend on paging are:

• Zero copy IPC (e.g. memfd_create(), modern socket implementations, IPC mechanisms in microkernels)
• Modern graphics pipelines that map VRAM (e.g. containing framebuffers or command buffers) directly into userspace applications
• Other accelerators (many-core expansion cards, FPGAs) that do the same
• Non-volatile memory (NVDIMM) that is directly mapped into userspace
• High-performance interconnects like Infiniband that implement networking partially in userspace

Granted, some of those things could be made to work without paging, but they all clearly benefit from paging and disabling it will definitely hurt performance and increase implementation complexity here.

[OSwhatever]

Paging and segmentation are not mutually exclusive, they can live together. Apart from use cases Korona mentioned, paging must exist together with segmentation if the fragmentation problem is going to be solved. Try allocate 1GB of memory on a machine with 1.5GB memory if you have only segmentation. This will likely fail as you likely don't have 1GB consecutive memory after the OS has been running for a while. With pages of 4KB or even 16KB, you can build up your 1GB allocation and it will likely succeed, not to mention the benefits with demand paging.

I kind of like having a segment as a protection and paging unit. With a segment you can choose the page size on segment level. With only paging you can do this as well but you are likely to have to fulfill alignment requirements which are quite big for L2 (2MB or 4MB). That's one of my biggest objections against only paging, you have manage a "virtual" address space, something that doesn't need to exist to begin with.

[Qbyte]

Multitasking operating system rely more (and not less) on paging today than they did a decade ago.

All of the relevent features that paging provides can also be provided by segmentation. The primary reason to use segmentation instead of paging for these purposes is that it a) reduces the MMU critical path (only 1 table lookup per access vs 4) and b) has a much lower space overhead (only need 1 TLB entry per segment instead of potentially thousands of pages) which also reduces the TLB miss rate as the entries for all processes are practically guaranteed to be cached.

It's worth noting also that "Flat Segmentation" can exist. In this case, the virtual address space can be divided up into contiguous variable-sized segments which are mapped into corresponding variable-sized frames in physical memory. The MMU then has limit-offset pairs instead of base-and-bounds pairs indexed by a segment id. If the virtual address is within the range of addresses defined by a segment, the corresponding offset is added to the virtual address to form the physical address.

[StudlyCaps]

All of the relevent features that paging provides can also be provided by segmentation.

You have this the wrong way around I think, paging provides all the advantages of segmentation plus has additional benefits, like avoiding physical memory fragmentation and allowing overcommit. Having both segmentation and paging is a waste of resources and increases complexity, while really adding nothing.
The reason modern hardware neglects segments is that people don't use them. People don't use segments because paging is very useful, and if you have pages, you don't need segments.

[Qbyte]

You have this the wrong way around I think, paging provides all the advantages of segmentation plus has additional benefits, like avoiding physical memory fragmentation and allowing overcommit.

The most important aspects of virtual memory (protection, sharing, mapping) are common to both schemes. My argument is that segmentation can provide the most important features of virtual memory more efficiently than paging because it requires far less space and latency overhead. Instead of needing large, multi-level page tables, you only need as many TLB entries as there are distinct segments in the process. This can also, among other things, greatly speed up context switches, eliminate TLB flushes, page walks, etc. The subtle advantages of paging (no external fragmentation, etc) are becoming increasingly irrelevant as hardware is evolving and no longer justify the disadvantages it has compared to segmentation.

[zaval]

^ noone loves segmentation and everyone loves paging. What you are talking about, QByte, is just huge pages. And they are not flexible and only could have advantages when used rarely where they really needed. using only them is nothing but system memory wastage.

The subtle advantages of paging (no external fragmentation, etc) are becoming increasingly irrelevant as hardware is evolving and no longer justify the disadvantages it has compared to segmentation.

What's the "evolvement" you are talking about? RAM is evolving in that it becomes faster and consumes less power. But it remians the same very scarce flat array. Because SW is also "evolving" in eating up that bigger amounts of RAM, increasing amounts of an installed RAM on an average system doesn't really matter. And it's still important to allocate as small pieces of it for a process as possible. That's why fine granularity of pages is needed. Your huge pages are gonna eat up most of physical memory in vain. If you like this, try to use only huge pages and that's what you are talking about. then when you have some measurements done, you could deffend it with numbers on the hands. Now I see it only as the memory wastage and allocation nightmare.

[Qbyte]

What you are talking about, QByte, is just huge pages. And they are not flexible and only could have advantages when used rarely where they really needed. using only them is nothing but system memory wastage.

Segmentation is in fact less wasteful of system memory than paging. It doesn't require the overhead of large page tables for each process, which reduce the amount of physical memory available to user-space. Additionally, wasted memory from internal fragmentation is completely avoided; each process can be allocated precisely the amount of memory it needs down to a single byte. External fragmentation doesn't waste system memory, it merely means that you may need to occasionally compact some of the existing segments to form a contiguous region that can be used to satisfy a new allocation request. This is all beside the point anyway, which is that since we have such large amounts of physical memory now, these types of considerations are not as important as performance, and segmentation can provide better performance for the reasons I've stated earlier.

What's the "evolvement" you are talking about? RAM is evolving in that it becomes faster and consumes less power. But it remians the same very scarce flat array.

RAM hasn't just become faster and less power hungry, capacities have significantly increased as well. Modern systems now have 16 or 32 GB, so RAM isn't exactly scarce anymore and will continue to become less so.