The UNIX Time-Sharing System

Take a folder of downloads with six files in it (our own example: invoice.pdf, notes.txt, paper.pdf, photo.jpg, slides.pdf, song.mp3). Type one line:

$ ls | grep pdf | wc -l
3

Three separate programs just worked as one. ls prints the names in a folder, grep pdf keeps the lines that contain "pdf", and wc -l counts lines. But ls has no idea how to count, and wc has never heard of a file name. How do programs that know nothing about each other snap together like this, and why does the same line still work more than 50 years later? The answer is an eleven-page paper by Dennis Ritchie and Ken Thompson of Bell Labs, published in July 1974.

The Machine in 1974

The Unix in the paper ran on a PDP-11/45 from Digital Equipment Corporation, with 144K bytes of core memory (the main memory programs run in). Unix itself took 42K. The authors write that Unix could run on hardware costing as little as $40,000, and that less than two man-years went into the main system software.

The abstract promises features "seldom found even in larger operating systems": a hierarchical file system with demountable volumes; compatible file, device and inter-process I/O; asynchronous processes; and a command language each user can choose. It names its first priority plainly: "The most important job of UNIX is to provide a file system." (p. 366)

A File Is a Row of Bytes

To Unix, a file is a sequence of bytes and nothing more. "No particular structuring is expected by the system. Files of text consist simply of a string of characters, with lines demarcated by the new-line character." There are no records and no fixed sizes; the program that uses a file decides what its bytes mean.

A program reaches a file through four calls, written in the paper's own notation:

filep = open (name, flag)
n = read(filep, buffer, count)
n = write(filep, buffer, count)
location = seek(filep, base, offset)

open hands back a file descriptor: "a small integer used to identify the file in subsequent calls". Think of it as the program's ticket for the open file. read copies up to count bytes and moves a pointer forward, so the next read starts where the last one stopped; a read that returns 0 bytes means the end of the file. write works the same way, and seek moves the pointer anywhere. Keep these calls in mind: the paper's plan is to reach devices and other programs through exactly the same ones.

Names and Directories

A directory is a file too: a list that maps each name to the file it stands for. Anyone with permission can read one, but ordinary programs cannot write to it, so the system controls what is inside. Directories hold directories, and together they form one tree from a single root.

The paper's own example is the path /alpha/beta/gamma: start at the root, find alpha, then beta inside it, then gamma inside that. A name without the leading slash starts from your current directory, so from inside alpha, beta/gamma reaches the same file. Every directory also holds . (itself) and .. (its parent, the directory it was created in). In 1974 a name had at most 14 characters.

I-nodes and Links

A directory entry holds just two things: a name and an i-number. The i-number is an index into a table on the disk, the i-list, and the row it finds is the file's i-node, where the file really lives: its owner, its protection bits, where its blocks sit on the disk, its size, when it last changed, how many directory entries point to it, and three one-bit flags (directory, special, large). There is no name in it. Names live only in directories.

That is what makes links possible. To give a file a second name, the system writes one more directory entry with the same i-number and raises the link count from 1 to 2. Both names are equal; neither is the original. Deleting one name erases that entry and lowers the count to 1, and the file is still there under the other name. Only when the count reaches 0 are the blocks and the i-node freed.

The blocks are 512 bytes each, and an i-node has room for eight block addresses. A small file uses them directly. A large file uses none of them directly: each of the eight points instead to an indirect block of 256 more addresses, each naming a 512-byte block.

Devices Are Files

The i-node's special bit marks what the paper calls "the most unusual feature of the UNIX file system". Every device has at least one special file, with entries in /dev: one for each communication line, each disk, each tape drive, and the core memory.

Special files are read and written just like ordinary disk files, but requests to read or write result in activation of the associated device. …

Thus, for example, to punch paper tape, one may write on the file /dev/ppt.

(p. 367)

For a special file the i-node holds a device type and a subdevice number instead of block addresses, and the system hands each read or write to that device's routine. The paper counts three wins: file and device I/O look the same, a device name works anywhere a program expects a file name, and devices get the same protection as files. (Ritchie later wrote that he believed device files were his contribution.)

That protection is seven bits per file: read, write and execute for the owner, the same three for everyone else, and a seventh, set-user-ID, which runs a program with its owner's identity. Even whole disks join the tree this way: mount takes a disk pack, named by its special file, and puts its whole tree in place of an ordinary file.

One Process Becomes Two

An image is everything a running program has: its memory, its registers, its open files and its current directory. A process is an image being run. Apart from the very first process at start-up, there is exactly one way to make a new one:

When fork is executed by a process, it splits into two independently executing processes. The two processes have independent copies of the original core image, and share any open files.

(p. 370)

In the paper's description, the parent carries on right after the call, and the child starts at a label the program chose (processid = fork(label)). Their memory is separate, but both point at the same open files. Ritchie later wrote that on the PDP-7, fork took precisely 27 lines of assembly code.

Execute and Wait

The child then calls execute with the name of a program file, say ls. Execute throws away the child's code and data and reads in ls, but the open files and the current directory stay exactly as they were. If it works, it never returns: the paper compares it to a jump, not a subroutine call. Meanwhile the parent calls wait and stops until a child finishes. When ls calls exit, its image is destroyed, its files are closed, and its status goes back to the parent.

The important moment is the gap between fork and execute. The child is already a separate process, but it is still running the parent's code, and anything it changes in that moment, like which files are open, it keeps when the new program starts.

The Shell

The shell is the program you type commands into, and in Unix it is not part of the system: "the Shell operates as an ordinary, swappable user program". Its loop:

1. Type a prompt and read a line.
2. Split it into the command name and its arguments.
3. Fork.
4. The child executes the command, looking for the name as given and then in /bin.
5. The parent waits, then types the prompt again.

End a line with & and the shell skips the wait: the command runs in the background and the shell prints its process number (as source >output & in the paper). A ; runs two commands in turn (ls; ed), and because the shell is just a program, it can read its commands from a file (sh <tryout). It is even chosen per person: at login, init checks your name and password and starts the program your entry in the password file names, normally the shell, but for a secretarial editing system the editor ed, and for a game such as chess the game itself.

Standard Input and Output

Every program the shell starts already holds two open files: file 0, standard input, from your keyboard, and file 1, standard output, to your terminal, in 1974 a typewriter. ls writes its list to file 1 and never asks where file 1 goes.

On Multics, the system the authors had worked on before, Ritchie recalls that sending a listing to a file took three commands:

iocall attach user_output file xx
list
iocall attach user_output syn user_i/o

Unix does it in one line, ls >list.txt. In the gap between fork and execute, the child closes file 1 and creates list.txt. A new file always gets the smallest unused descriptor, which is now 1. Then the child executes ls, which writes to file 1 as always, and the list lands in the file. < does the same for file 0: ed <script reads editor commands from script.

Although the file name following "⟨" or "⟩" appears to be an argument to the command, in fact it is interpreted completely by the Shell and is not passed to the command at all.

(p. 371)

A puzzle: run ls >list.txt in our six-file folder and count the names in list.txt. It is seven, because the shell created list.txt before ls started, so ls lists it too (a real run, cat list.txt prints all seven).

The Shell's Own Code

The Fifth Edition shell source (usr/source/s2/sh.c, marked copyright 1973) does exactly this in the child:

616			i = creat(t[drit], 0666);
...
623			close(1);
624			dup(i);
625			close(i);

creat makes the file, close(1) frees file 1, and dup(i) gives the same open file a second descriptor, the lowest free number, which is now 1. A few lines down, lines 633 to 638 make the same move with a pipe's write end (dup(pf2[1])). The program being run never sees any of it.

Pipes

A pipe sends one program's output straight into another program. filep = pipe( ) returns a file descriptor for a channel between processes, and like any open file, fork passes it from parent to child. One process writes, the other reads, and "a read using a pipe file descriptor waits until another process writes using the file descriptor for the same pipe". In the paper's words, "neither process need know that a pipe, rather than an ordinary file, is involved." The paper also states a limit: the pipe "must be set up by a common ancestor of the processes involved", which on a command line is the shell.

The idea is older than Unix. In a 1964 Bell Labs memo, Doug McIlroy wrote: "We should have some ways of connecting programs like garden hose--screw in another segment when it becomes when it becomes necessary to massage data in another way." (the repeated phrase is in the original, Ritchie notes). Pipes arrived in Unix in 1972, "at the suggestion (or perhaps insistence) of M. D. McIlroy".

Filters

With pipes, the paper's own example is ls | pr −2 | opr: ls lists the files, pr paginates with dated headings (−2 means two columns), and opr spools the result for the printer. All three run at the same time. Without pipes the same job takes temporary files (ls >temp1, pr −2 <temp1 >temp2, opr <temp2, then delete both), and without redirection at all, ls itself would need options to paginate, print in columns and send its output to the printer.

Actually it would be surprising, and in fact unwise for efficiency reasons, to expect authors of commands such as ls to provide such a wide variety of output options.

(p. 371)

A program like pr, which copies its standard input to its standard output with processing, is a filter. Ritchie remembered that pipes were received with enthusiasm, the word filter was soon coined, and many commands were changed to work in pipelines. In 1978 the Bell System Technical Journal wrote the habit down as maxims, the first two beginning: "Make each program do one thing well." and "Expect the output of every program to become the input to another, as yet unknown, program."

Why It Worked

The authors give their own answer: "the success of UNIX is largely due to the fact that it was not designed to meet any predefined objectives." Thompson, dissatisfied with the computers available, found a little-used PDP-7 and set out to build a more hospitable environment. Looking back, they name three considerations:

They credit their sources too: fork "essentially as we implemented it" from the Berkeley time-sharing system, and from Multics the form of the I/O calls, the shell's name and functions, and a process for each command. In their words, "the success of UNIX lies not so much in new inventions but rather in the full exploitation of a carefully selected set of fertile ideas." (p. 374)

Where It Lives Today

Back to ls | grep pdf | wc -l. The shell makes a pipe between each pair of programs and forks a child per program. In the first child, file 1 is moved onto the first pipe before it executes ls; in the second, file 0 comes from that pipe and file 1 goes into the second pipe before it executes grep; in the third, file 0 comes from the second pipe and file 1 stays your terminal before it executes wc. All three run at once, and the shell waits for the last one, wc, to finish (the standard requires only that wait, though a shell may also wait for all three): six names, then three, then the count. None of them knows a pipe is involved; each reads file 0 and writes file 1.

Today's POSIX standard for the shell still spells out that wiring: "For each command but the last, the shell shall connect the standard output of the command to the standard input of the next command as if by creating a pipe and passing the write end of the pipe as the standard output of the command and the read end of the pipe as the standard input of the next command." (POSIX.1-2024, 2.9.2 Pipelines)

What Aged

The Fifth Edition shell in the source walkthrough already calls fork() and sets up file descriptor 2 for diagnostics. The table compares the paper's descriptions with current conventions.

The 14-character names and the one-megabyte file limit are 1974 limits too.

The Takeaway

Give every program the same small way to read and write, and let one ordinary program, the shell, decide where the bytes go. That is why ls never had to learn to count, and why grep and wc could join it in a line nobody had to plan.

A pipe just moves bytes and leaves their meaning to the programs at each end. So when bytes have to cross many machines, and something along the way can damage them, which part should make sure they arrived intact: the network in the middle, or the programs at the two ends? That is the question of End-to-End Arguments in System Design.

References

• Dennis M. Ritchie and Ken Thompson, "The UNIX Time-Sharing System", Communications of the ACM 17(7), July 1974, pp. 365 to 375. ACM Digital Library
• Dennis M. Ritchie, "The Evolution of the Unix Time-sharing System" (1979; AT&T Bell Laboratories Technical Journal 63(6), part 2, October 1984). nokia.com
• Dennis M. Ritchie, "Advice from Doug Mcilroy" (McIlroy's 1964 memo, retyped). nokia.com
• M. D. McIlroy, E. N. Pinson, B. A. Tague, "UNIX Time-Sharing System: Foreword", The Bell System Technical Journal 57(6), July-August 1978, pp. 1899 to 1904. archive.org
• Fifth Edition Unix shell source, usr/source/s2/sh.c. unix-history-repo
• Sixth Edition dup(II) manual page. TUHS
• Andrew Baumann, Jonathan Appavoo, Orran Krieger, Timothy Roscoe, "A fork() in the road", HotOS 2019. PDF
• POSIX.1-2024, Shell Command Language, 2.9.2 Pipelines. The Open Group
• Linux man-pages: fork(2), stdin(3), fifo(7), flock(2)