2

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 ?

10
  • 14
    The i386 was by no means the first CPU with memory management and protection. For example, gunkies.org/wiki/PDP-11_Memory_Management Dec 12, 2021 at 22:14
  • 6
    You might find this question interesting, it gives references describing virtual-memory-equipped computers going back to the early 60s, with prototypes in 1959... Dec 12, 2021 at 22:14
  • 8
    And the PDP-11 in Greg’s comment above is significant because it played a huge role in the development and popularisation of Unix. Dec 12, 2021 at 22:15
  • 6
    Even if you’re only interested in x86 systems, 286s included all the features needed to run Unix. There were also Unix variants for MMU-equipped 8086-based systems, which isn’t surprising. Perhaps your real question is about Xenix-86, which appears to have been available for MMU-less 8086/8088 PCs... Dec 12, 2021 at 22:23
  • 2
    @Spud - 'multiprogramming' would be the contemporary term. Dec 16, 2021 at 13:49

2 Answers 2

26

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.

10
  • there wasn't much point in having paged memory on the 16-bit systems Why not? Being able to have more working sets of different processes in RAM, each of which was less than 64Kb (or 128 Kb in split instruction/data address spaces), would be quite helpful for performance.
    – Leo B.
    Dec 13, 2021 at 2:41
  • 1
    On 16-bit systems, they used to bank switch the memory. Basically the extra memory was used as a disk and banks would be switched in.
    – cup
    Dec 13, 2021 at 7:23
  • To wit, regarding my previous comment: gunkies.org/wiki/KT11-B_Paging_Option
    – Leo B.
    Dec 13, 2021 at 8:22
  • 1
    Regarding "...multiprocessing without process isolation or relocation registers. Programs have to be linked for their specific runtime physical memory addresses...": OS-9/68000 used a different approach, position-independent code, allowing only relative branches and address-register relative data access. A program could be loaded to any physical address without any binary modification. Dec 16, 2021 at 8:41
  • 2
    At about the same time that unix was written for the PDP-7, there was a control program for the PDP-6 called, simply, "the monitor" that could run more than one program concurrently. Isolation was through two registers, the protection and relocation registers. Also ITS at project MAC later ported to the PDP-10. Dec 16, 2021 at 11:43
19

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.
5
  • 1
    SLIC does a lot more than the JVM, but would it be fair to say that the JVM (Java Virtual Machine) is another, better-known example of LPI? Dec 13, 2021 at 8:26
  • Other examples are Bell Labs’ Inferno, and of course, the fictitious METAL. Dec 13, 2021 at 9:23
  • The supposedly-fictitious METAL is basically a real thing if you look at projects like Jor1k. A full linux kernel, with X Windows, and compilers, running under asm.js in your web browser. And much sooner than 2035. The only problem is it's emulating a virtual machine instead of using shims.
    – Andrakis
    Dec 16, 2021 at 15:29
  • @Andrakis The point is not to run it inside, but instead of a browser. Dec 16, 2021 at 18:35
  • 1
    The Pilot OS (Xerox PARC) implemented virtual memory without process isolation - i.e., all code ran in one address space. I believe the language, Mesa, was designed such that it (or at least the type-safe subset) would prevent process interference. Dec 17, 2021 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy