How did Unix handle multiprocessing when virtual memory didn't exist?

Question

It seems the first "real" virtual memory management system was the i386 with its powerful paging system that totally isolates processes. How did Unix work before this, ensuring no process write in another's process region etc ?

Answer 1

Several points:

1. Process isolation does not require paged virtual memory. One possibility is a simple relocation register, where program-virtual addresses have the content of a relocation register added to get the physical address. Coupled with a limit register, complete process memory isolation can be obtained. This approach was common in computers intended for multiprocessing, from the 1950s on (link). One relocation register restricts you to a single-segment process. The PDP-11 had 8 such registers.

2. Unix originally ran on the PDP-7, and achieved process isolation by the simple expedient of having only one process in memory at any one time. I think it was possible to overwrite the kernel, since there was no 'privileged' processor mode.

3. The first paged virtual-memory Unix was 3BSD, derived from Unix-32V on the VAX-11/780. Really, there wasn't much point in having paged memory -- in the sense that you might have only part of the address space resident -- on the 16-bit systems.

4. It's unclear what you mean by the "first real virtual memory system", but the actual first VM system was the Atlas, in 1961 or so. Long before microprocessors.

5. Not relevant to Unix, but you can do multiprocessing without process isolation or relocation registers. Programs have to be linked for their specific runtime physical memory addresses (thus 'linking loader'). Usually, this was done by dividing memory into fixed partitions, and linking a program to execute in a specific partition. This requires planning what programs you want to have in memory simultaneously, of course.

Answer 2

Continuing on from another-dave's excellent answer, here is another strategy that was and still is actually employed in real-world systems to implement process isolation without virtual memory: Language-based Process Isolation

In Language-based Process Isolation, the ABI of the OS is not the real ISA of the underlying CPU but rather an intermediate language. This intermediate language can, for example, be made memory-safe by design, by simply not including instructions for directly manipulating memory. Or, it can require programs to carry a memory-safety proof which is then verified by a proof checker integrated into the OS.

The former strategy is used by the AS/400 and its successors, where the "native" ISA accessible to programs is actually an Abstract Machine called the Technology-independent Machine Interface (TIMI). On the AS/400 and its successors, "native" compilers do not target the instruction set of the underlying CPU (which originally was a custom 48 bit CISC CPU but has since been replaced with 64 bit POWER CPUs) but target the TIMI instead. The TIMI code is then translated by the System Licensed Internal Code (SLIC) to the native CPU instruction set. The SLIC is roughly equivalent in its usage to platform firmware such as the BIOS or UEFI, but its feature set is more like that of a traditional OS kernel. I.e. the SLIC is used by the "real" OS to access hardware – in this sense, it acts like a BIOS or UEFI – but it actually contains memory management, object-based single-level storage (it abstracts RAM and hard disks into a single, flat object space), and even a SQL database.

The TIMI, with its object-based storage, is designed in such a way that there simply are no instructions in the TIMI which would allow a process to break process isolation. For example, a process cannot construct pointers out of thin air, or manipulate pointers. It can only use pointers that are given to it by the TIMI. In fact, the term "pointer" is not even correct, since they aren't actually addresses into memory, they are 128 bit object identifiers.

Microsoft Research's Singularity Operating System also used Language-based Process Isolation for what they called Software-Isolated Processes (SIP). Similar to OS/400, there was an abstract instruction set, in this case based on .NET MSIL. The OS contained powerful APIs for message-based communication between SIPs. These APIs contained provisions for SIPs to present contracts to the OS about how these messages were used, and these contracts contained proofs of correctness. The OS contained a proof checker which would verify these proofs, and based on its knowledge of how the messages are going to be used, the OS could compile the message-based user-level code into native code that uses shared memory, thus eliminating the message passing overhead and recovering shared memory performance. In essence, giving you data exchange between SIPs with the performance of shared memory but the safety of message passing.

In Singularity, there was no (hardware-based) separation between the address spaces of different processes, there was no (hardware-based) separation between kernel space and user space, and all code was running in ring 0. All the isolation was software-based. There was no (hardware-based) virtual memory, instead storage virtualization was achieved via the garbage collector and the memory allocator / manager. (Actually, each SIP had its own garbage collector.)

As an experiment, the Singularity research group added hardware-based isolation:

• SIPs could be either marked as running in ring 0 or ring ring 3.
• SIPs could be either marked as running in a shared address space or in separate address spaces.

These two features allowed the group to simulate different levels of isolation, and independently measure the performance effects.

For example, they could measure the effect of only running the kernel in ring 0 and the user space in ring 3 but still running all code in the same address space. Or, they could measure the effect of only marking the kernel as running in a separate address space but running all user level code in the same address space. And they could also configure the system to have hardware isolation similar to Windows NT or Unix with the kernel running at ring 0 in its own address space, and each user level SIP running at ring 3 in its own address space.

I forgot the actual numbers, but the performance impact they measured was pretty dramatic. In order to make sure they weren't just measuring unrealistic "research code", they actually "borrowed" some developers from the Windows NT kernel team to implement their virtual memory subsystem, to ensure it has the same level of performance optimizations that a "real-world" industrial strength production OS has.

This shows that not only is hardware-based isolation (i.e. a MMU) not required, it is not even necessarily efficient.

So, there are several misconceptions in your question:

• Virtual memory didn't exist before the i386: that is false, the first virtual memory system was built in 1959, in the 1960s, IBM showed that virtual memory was consistently faster than manual controlled memory, and by the 1970s, pretty much all commercial computers had virtual memory.
• Virtual memory is the only way to achieve process isolation: that is false, there are many different ways of achieving process isolation.
• Process isolation needs hardware-support: that is false, process isolation can be done entirely in software.
• Process isolation needs hardware-support to be efficient: that is false, as Singularity has shown. Especially isolation based on compile-time features such as static types, static proofs, or simply not even having instructions that could break process isolation, trivially has zero runtime overhead.
• Multiprocessing requires process isolation: even that is technically false, since it works without, it's just that a process can easily crash another one. So, it "works" but is not nice to use.