Written: 2024-09-25
The design of Research Unix
I've been wanting for some time to write a series of articles on various operating systems. I find this sort of stuff fascinating; understanding their history, motives, personalities of the creators, and ultimately technical choices. A lot can be learned from this kind of analysis, both in terms of actual interesting designs, but also as design lessons from the classics.
Because everyone defaults to Unix-like as a basic model of what an operating system is, I think it's appropriate to start with the original.
For this article, I will be examining the Bell Labs research Unix, not its derivatives like the BSD and AT&T System III. Those have their own histories and sets of problems and solutions, but don't quite fit into the same design principles, as they were developed by entirely different teams, for somewhat different purposes.
Context
The Multics project began in 1965. It was, essentially, an attempt to create something like the modern idea of the cloud: always-available computing as a service. Bell Labs joined the project in the hope of getting an inexpensive time-sharing system by 1969, but it was an ambitious project, and suffered many delays until its eventual release in 1974. When '69 came and Multics was clearly going to take a few more years, Bell Labs pulled out of the project[a].
But Multics was revolutionary: it was a multi-user, time-sharing system, featured a hierarchical organization for files, a novel security scheme – ACLs – that's still a standard to this day, as well as some incredible reliability features, such as replacing disks and CPUs while the system was running (!).
The standard for computer interaction at the time was batch execution: submit your program as a stack of punched cards to the (human) operator, and a few hours-to-days later get the printouts. One mistake and you start the whole process again. The Bell Labs researchers who worked on Multics had known the ability to interact with their programs in real-time, debug them much more easily, edit and then re-run them immediately, and even send each other single-line messages if they were online. They really liked what they had, and didn't want to lose it[b].
[b] Much of this is based on Dennis Ritchie's account of early Unix history.
So when Ken Thompson made a little experimental file system, and then built an OS on it for testing, the OS he built was inspired by Multics. It was not, however, a copy of the design, but of the user-facing feature set: a multi-user, time-sharing system, with a hierarchical organization for files.
To justify computer purchases for the development of Unix, it was presented to the Bell Labs administration as a text preparation and typesetting system. So the "killer app" for Unix was troff's predecessor, roff, and its demo was the Unix manual.
The system was initially a single, live system, as used by the Bell Labs personnel. "Distributions" of it were ad-hoc copies of the current state of the system, and named according to the manual edition: "0th edition" before there was a manual, 6th edition was the first that was used outside of Bell Labs, 7th was the one the BSD and AT&T's System III were based on. The last research Unix was the 10th edition.
Unix, 7th edition
By version 7, Unix had achieved some wide distribution; it is this state of the system that most modern descendants are derived from. So it should be educative to examine it first, before getting to later versions.
The file system
The centerpiece of Unix – and most descendants – is the file system. It was the first part of the system to be written. A file is a series of bytes with a length, access permissions and some additional metadata such as access and modification times. A directory is a special file that contains a list of other files and their names. Notably, names are stored only in directories, not files; multiple directories can reference the same file under different names.
The alternatives, at the time, were varied: some had fixed-length lines (matching punched cards), some used a set of hierarchical records (matching physical paper files), one directory per user was pretty common (with no subdirectories)... if they had "files" at all. The Unix idea of a file system was lifted mostly from Multics. It could do what the others could, with more flexibility and less complexity. Thus why it was used for Unix, and why it's used in nearly all modern systems.
In order to read and write data to and from files, the streaming read/write/seek interface we know today was invented. Multics had a similar interface, but more often files were memory-mapped instead[a]. Research Unix never implemented memory-mapping, although most of its descendants do. Instead of having a fixed record size or some other complicated means of specifying how much to read, as in other early operating systems, Unix requires a simple length in bytes.
[a] Multics Virtual Memory – Tutorial and Reflections.
In Research Unix (and most of its descendants) "special files" are real files on disk, only instead of having contents, they are dynamically populated by the kernel. Some of these files link to terminals, some others to disks, one represents the whole system's memory. These avoided the need to invent a new interface to access terminals and disks, and made neat tricks like pipes and I/O redirection possible.
The idea of I/O redirection also came from Multics, although Multics didn't have a convenient syntax on its shell to do it. Multics, however, didn't have special files as such; streams were separate from files, and a file was only one kind of stream, alongside printers, terminals and so on. Unix merged these ideas, using only the stream I/O interface for everything, and the hierarchical file organization scheme for everything[b].
[b] Multics made all allocated memory accessible through the file system, so this might have inspired something like Unix' /dev/mem, and later Plan 9's /proc. It was really a different thing though; files and memory are just the same thing in Multics.
Processes
A somewhat unusual characteristic of Unix is the commands-as-processes model. Multics – and most other early time-sharing systems – provided one process per user session. This provided separation of address spaces without being too taxing on the system. With a paper terminal, it would be hard to create a user interface to multitask anyway. And you could always submit a job to be run by the batch processes when it got around to it.
Unix started out by doing that. The PDP-7 it was prototyped on didn't provide memory protection, so to switch between programs, it would simply write out the programs' memory[a] to disk, then load the next user's saved memory from disk, and resume execution. The PDP-7's disk was fast enough (rather, its CPU was slow enough, and with no DMA, had to be busy anyway) that it wasn't that much overhead.
[a] Only up to the address set by brk(). That's where that system call comes from.
This made it easy to implement the now-classic fork/exec process control model: fork simply expands the process table; the "copy" would be done anyway during the task switch. Exec was also just a matter of loading the executable into current memory, then jumping to it. Much simpler than Multics' dynamic linking.
As for signals and sessions, those were implemented to allow for Control-C to stop a program and return to the shell. The terminal sends a signal to any processes in its session, and each process can choose whether to crash (the default) or ignore it (what the shell does). The same mechanism could be used to handle some forms of crashes, such as division-by-zero. It was a fairly special-purpose system, but got significantly abused by Unix's descendants.
Terminals
The primary mode of interaction for computer systems of the early 70's was a "teletype", a paper terminal. This was, in modern terms, a very noisy mechanical printer attached to a keyboard. What the user typed was sent to the computer, and what the computer sent back was printed. This made it difficult to edit lines, because every character typed was printed on paper and couldn't be erased.
Early Unix provided a terminal driver that had two modes: raw and "cooked". In raw mode, any time a process reads from the terminal stream, any characters that had been received from the terminal are returned. In cooked mode, a line is only returned after newline had been sent; if a "#" was typed, the previous character was ignored. If an "@" was typed, the whole line was ignored.
There were other options, such as echo or no-echo. This mode solved the problem of typed passwords being printed on paper; the computer would simply not send back typed characters, and the typewriter would print nothing.
The shell
In most other operating systems, the shell was a part of the system that interprets commands. It was usually either a programming language (BASIC in DTSS, JOSS on the JOHNNIAC) or an ad-hoc command set for running programs (with something like an explicit RUN command).
On Multics, a command was a procedure to be called; any user could create a command by making a procedure that took the appropriate string arguments. On Unix, a command is a program to be run; any user can create one, in much the same way.
On Multics, there was a facility for redirecting the standard streams (iocall), but it was not standard and there never was special syntax to make it convenient, because the people who developed it were on a completely different team than the one responsible for the shell. On Unix, since the whole system was maintained by two people at this point (Ken Thompson and Dennis Ritchie), once one had the idea it was trivial to implement.
Pipes were particularly interesting; after Doug McIlroy insisted on it, they ended up being implemented in an afternoon. The utility was obvious, and in those early days pipelines were much more common than they seem to be today. Everything was text; everything was meant to be pipelined. Everything came and went through streams, and eventually to a terminal. Pipes were the most appropriate solution to the problem of program composition.
The shell was somewhat programmable, but became much more when the Bourne shell arrived; it solved many longstanding issues with the original shell, and added conditionals and loops and process substitution to the language.
This, along with familiarity everyone had from using the shell all the time to interact with the system, made it easier to hack together a pipeline than to drop down to C and write a complete program. If C was necessary, it would be only for a single step of the pipeline. Other steps could be reused.
Available programs
Ed was the standard text editor. It features a simple and usable user interface (for a typewriter) and a powerful command language. Unlike other editors of the time (notably TECO), it only had a small set of commands that could be learned easily.
Sed is a streaming version of ed; you provide a command to be executed first, and the data as input, instead of passing a file to edit first, and the commands later, as in ed. Grep was a commonly used ed command: g/re/p would match the regular expression /re/ (g)lobally and then (p)rint any matches.
Roff, and its later phototypesetter variant, troff, are high-quality typesetting systems, similar to TeX, but simpler. They were used to typeset the manual, as well as countless other Bell Labs documents. Their input is mostly line-based, which allowed for input preprocessors such as eqn and tbl. There were many such input preprocessors, as they provided for whatever flexibility troff's macro system lacked.
In fact, preprocessing was a big thing in the early Unix days; due to the nature of the typewriters, everything was text, so it was not unlikely than any problem for which an automated solution was desired could be solved by stringing together a pipeline. The fact that pipelines were so easy to set up made this even easier.
Late Unix
The 7th edition, released in 1979, was the basis for both BSD and AT&T's System III, and later System V. This is the one most modern systems derive from. But after V7, Research Unix kept being developed.
By the time V8 was finished, it was 1985. Many things had changed: paper terminals had been obsoleted by video terminals, the GUI had been invented, machines were now regularly networked. Home computing was starting to become practical. Unix had taken over the world, but it was designed for a previous era.
BSD and AT&T System V were adapted to this new world by the means we know today: termcap, curses, sockets and eventually X11. The creators of Unix weren't really satisfied with these solutions, so they started from a 4.1BSD base, but then replaced these solutions with their own.
Streams
BSD-style sockets, to this day, are a pain to use compared to regular pipes. They are file descriptors, but have different semantics and are interacted with through a completely different set of system calls than normal files and pipes. They don't compose nearly as well as regular pipes; you can't simply write to a socket. There are no "socket-lines".
V8 streams are two-way pipes (and can be created with the pipe() system call). Ioctl() could be used to push "line disciplines" on a stack. Those worked much like the terminal modes explained above. All line disciplines were implemented in the kernel. Not only terminals were supported, but also several networks, and a special line discipline that converted each message received into a control block, allowing ioctls and other control operations to be implemented in userspace.
Pseudo-terminals (from BSD) were also turned into streams, along with any network devices. This means that a terminal emulator or multiplexer could just capture certain ioctls with the appropriate configuration, and extend the "device" interface itself. This was used extensively for the Blit (see below).
In V9, mount was augmented to be able to give a name to a file descriptor. If that file descriptor was a stream, the effect was similar to a System V named FIFO, but full-duplex and much more ergonomic. File descriptors could also be sent through streams, much like BSD's Unix-domain sockets. But since they otherwise behaved like normal pipes, regular programs could use them without so much coordination[a].
[a] Dennis Ritchie, "Interprocess Communication in 9th Edition Unix".
/n
Ritchie's work on IO streams eventually made possible Weinberger's network file system, /n, which provided remote access through the kernel. [...] There is no manual page about how to use it because there is nothing to say. Remote file systems are "mounted" locally so that remote accesses look just like local accesses.
Network machines were mounted under /n/<machine>/. This directory contained the machine's publicly accessible files. It behaved exactly like a local file-system, and local programs could manipulate it transparently.
It's worth saying that the DNS wasn't really in wide use at the time; it was still in development. Remote machines were locally named on /etc/hosts. It was this local name that was used under /n.
The Blit
While earlier paper terminals were fine for text (and occasional printed pictures, if the printer supported that), they were noisy and wasted a lot of paper. So when memory prices lowered enough to store a screenful of text in memory and render it to a video screen, video terminals became possible, and useful as a cost-saving measure.
They did have the disadvantage that it was not possible to check what had been output if it scrolled off the screen. This was not a problem with paper terminals. But they also had the advantage that, with some additional processing, it was possible to move the cursor back and change what had been printed earlier, by sending special control codes. This made rudimentary bi-dimensional text-based interfaces possible.
Later, as memory became cheap enough to store a bit per pixel in memory, graphics became possible. One way to do graphics was to create a personal workstation, such as the Xerox Alto. This was a full computer with spinning disks and fans and so on that had to be administrated individually. Another was a "dumb terminal", which could understand a simple drawing protocol, but was mostly controlled by a mainframe. A third was a "smart terminal", which could understand a more complex drawing protocol, and even run programs, loaded from the mainframe. X11 and NeWS were both smart terminal protocols.
The Blit was Bell Labs' response to the GUI and video terminals. It was a smart terminal; a computer with only a Motorola 68000 CPU, 256KB of memory, a 24KB ROM chip and a screen. No noisy spinning disks. The ROM chip implemented a rudimentary terminal emulator, which upon receiving a control code (0x10, Data Link Escape) would enter "download mode" and load a program from the mainframe to the terminal's memory, and then run it[a].
[a] A lot of this is based on Rob Pike's 1983 paper describing it.
The program that was usually run was Rob Pike's mpx (or its later iteration, mux). Mpx was composed of two parts: a terminal multiplexer to run on the mainframe, and a small multitasking "operating system" for the terminal.
The "server part" received output from Unix processes, and sent it as packets to the terminal. The terminal would then add that output to the respective console window. These were like paper terminals, with a white background and scroll-back, but no escape sequences. Any typed input was sent back to the mainframe.
Just the ability to interact with multiple programs at once was already extremely useful, but with a ioctl, mpx would send a program to run on the terminal itself. This program could interact with its counterpart on the Unix server to access files and such, but could also display graphics on its console window. These "terminal parts" had to be specifically written for the Blit, as mpx's terminal side was not really Unix-compatible.
Jim was a text editor for the Blit. It was, essentially, ed, but you could see what you were doing. There were two windows: the top one is for typing commands, and the bottom one shows the text. It could be scrolled, and text could be selected with the mouse, edited directly, and copy-pasted. A contextual menu provided more options. The command window was relegated to complex editing operations. It was later rewritten as sam, with structural regular expressions as the major new feature.
In other Unixes, it was common for an interactive program to provide facilities for running a shell, a text editor and so on, for the user's convenience. On a Blit, you could just open a new window with the text editor or the shell instead. This made applications significantly simpler.
Plan 9
The Blit had its issues; writing programs in two parts was tricky and error-prone. It would be better if the Unix system could be run on the terminal itself. But Unix wasn't really well-suited for such a tiny machine; there were many difficulties porting it. So they created a more powerful terminal (with a 68020 CPU and more memory) and rewrote the entire system, taking the time to fix any remaining historical mistakes (such as creat → create). This became Plan 9.
Analysis
In a good interface design, programs can do one thing and do it well; if you need another thing, that's another program, and the interface between them is simple and convenient. A bad interface design encourages larger and more complicated programs so users can avoid the inconvenience of getting them to work together. In Research Unix, a lot of attention was put on making this kind of good interface.
The basic approach from Unix did not translate well into the world of graphics, especially with X11, but even the Blit was not a good design by this metric. Plan 9 unfortunately did not manage to completely solve this on the graphics front (not everything can be text, after all) but it made huge advances on networking with transparent file access. Which we have available today. On mainline Linux. And don't use for some reason.
But I won't spoil the Plan 9 article I intend to write.
My favorite thing about Research Unix is its personality. It is pragmatic: no problem was solved until (and unless) it actually became an issue. It is theoretically solid: its creators had extensive knowledge of theory and put it to good use. It is simple and comprehensible, good enough for most (period-appropriate) uses, and, most importantly, flexible. Unrelated programs can work together. This reflects the creators themselves: researchers, trying stuff out, seeing what sticks and what doesn't, figuring out better ways to do things.