The UNIX Time-Sharing System

How to read the original

1. Read The File System and distinguish a directory entry, an underlying file, and an open descriptor.
2. Follow process creation and the shell’s execution behavior rather than assuming the shell is part of the kernel.
3. Trace a pipeline through descriptor inheritance and closure; compare the 1974 text with later revisions only when their editions are labeled.

Small interfaces make independent tools composable

Ritchie and Thompson describe a system organized around hierarchical files, process mechanisms, and compatible input/output interfaces. The shell implements much interactive command behavior as an ordinary program using kernel facilities. This reading now links the 1974 article rather than a later revision mislabeled as the same text. Historical implementation details should still be distinguished from present-day operating-system contracts.

Consider an original pipeline: a producer emits text lines, a filter retains lines containing a chosen word, and a counter reports the number retained. The programs need not know one another’s source code. They agree on byte-stream interfaces and a record convention, such as newline-delimited text. The kernel transports bytes; the meaning of a line or a word belongs to the programs.

Trace descriptors rather than imagining a magic pipe

The shell creates a pipe with a read end and a write end. It starts a producer process whose standard output refers to the write end and a consumer whose standard input refers to the read end. It closes unused ends in both children and in itself. Each process has a descriptor table, and descriptors refer to kernel-managed objects rather than directly containing all file data.

Suppose the producer writes two lines and exits. The consumer reads them and eventually observes end-of-file only after every open reference to the pipe’s write side is closed. If the shell accidentally retains a write descriptor, the consumer can wait indefinitely for more input even though the producer has finished. This is a resource-lifetime bug, not evidence that pipes need a timeout to define completion.

For a three-stage pipeline, the middle program’s input and output connect to different pipes. Every process must release ends it does not use. A drawing of descriptor ownership often explains a hang more clearly than a list of process identifiers alone.

Process creation and program replacement differ

In the familiar Unix process model, creating a child and replacing a process’s program image are distinct operations. A shell can create the child, arrange its descriptors, and then execute the requested program. Redirection can therefore work without each application implementing special syntax for output files. The application writes to its normal output descriptor; the shell chooses what that descriptor refers to.

This separation also clarifies why changing directory is ordinarily a shell built-in. If a separate child changes only its own current directory and exits, the parent shell’s directory does not thereby change. The state that must persist across subsequent commands belongs to the shell process itself.

Uniformity has limits

A regular file may support seeking while a pipe does not. A read can return fewer bytes than requested. A byte stream does not preserve application message boundaries by itself, so a protocol needs framing. An interface can be uniform at the level of read and write while retaining important differences in behavior and capabilities.

Directory names also differ from file identity. Two links can name the same underlying file, and an open descriptor can retain access independently of a particular displayed path under the relevant system semantics. Confusing names with objects leads to mistakes in deletion, permissions, and resource cleanup.

The paper demonstrates how a compact set of mechanisms supports a rich environment. Its historical success is not a proof that every task fits byte streams or that every old security assumption remains appropriate. A sound reconstruction identifies exactly what the kernel guarantees, what the shell arranges, and what each application protocol must still define.

Reconstruction exercise

A miniature shell launches a producer and consumer connected by a pipe. The producer exits, but the consumer never receives end-of-file. The parent shell still holds a copy of the write end. Explain the failure, list which descriptors each process should close, and describe one test that distinguishes the fixed version from a timeout workaround. Then explain why implementing cd only as an external child program does not change the directory used by the next command launched by the parent shell.

Worked solution

End-of-file on the pipe depends on all write-side references being closed, not merely on one producer exiting. The producer should close the read end and close its write end when done; the consumer should close the write end and eventually its read end; the parent should close both pipe ends once the children have the references they need. A deterministic test can have the producer write a known short payload and exit, then require the consumer to read exactly that payload and receive end-of-file without waiting for an arbitrary timeout. Retaining the parent’s write end should reproduce the hang. For cd, a child has its own process state. Changing that child’s current directory does not update the parent’s directory. The shell must perform the directory-changing operation in its own process when the change is intended to affect later commands.

Test the limits and transfer the idea

1. Storage trace · allow 40 minutes

Calculate the historical file-addressing cost

Read the 1974 paper's specific file-system layout rather than substituting a current Unix layout. It describes 512-byte blocks, eight address slots in an inode, and, for a large ordinary file, indirect blocks holding 256 data-block addresses. Use that stated large-file scheme for an original file of 300 data blocks. Assume all blocks are allocated, metadata is initially uncached, and the inode has already been loaded.

Calculate file data size, number of indirect blocks, indirect-storage overhead, and address lookup for byte offset 140000. Use zero-based block indices. Determine the maximum file data size in this described scheme. Explain why these numbers do not describe every later Unix filesystem and why a returned write does not necessarily prove persistence to disk.

Get a starting hint

Divide the byte offset by 512, then divide its data-block index by 256. Keep data capacity separate from index-block overhead.

Compare your reasoning with the worked solution

The file contains 300×512=153600 data bytes. It needs ceil(300/256)=2 indirect blocks, using 1024 additional bytes for those index blocks, excluding the inode and any allocation metadata. One indirect block has 256 populated data addresses and the second has 44. The index-block overhead relative to data is 1024/153600=1/150, about 0.667%.

For byte offset 140000, division gives data-block index 273 and within-block offset 224 because 273×512=139776. Data-block index 273 lies in indirect block slot 1, at address entry 17, since 273=1×256+17. Starting with the inode already loaded and no relevant cached blocks, read that indirect block to obtain the data-block address, then read the data block and select byte 224. Those are two block reads for this lookup under the stated cache assumptions.

Eight indirect slots each reaching 256 data blocks give 8×256×512=1048576 bytes of maximum file data in the scheme described by this article. Do not replace this with the direct/single/double/triple arrangement of some later systems or infer a current universal Unix limit. The paper also describes buffering: a write may update a memory buffer and return before physical I/O completes. Successful return therefore permits reuse of the caller's buffer but does not alone establish crash durability. Addressability, caching, and persistence are different contracts.

Check your reasoning

• Calculates both data and metadata sizes without mixing them.
• Finds indirect slot 1, entry 17, byte 224 and the two-read assumption.
• Uses the article-specific maximum and distinguishes write completion from durability.

2. Filesystem state and invariant · allow 40 minutes

Trace two names for one file

Use the paper's distinction between directory entries and inodes. Start with directory entry alpha naming inode 42 with contents ABC and link count 1. Create hard link beta to alpha. Through beta, overwrite byte offset 1 with Z. Remove alpha, then create a new file named alpha with contents XYZ and a distinct inode 57. Assume no open descriptors, no failures, and successful operations.

After each step, give directory mappings, relevant contents, and link counts. Explain whether beta changes when alpha is recreated and why a path string alone cannot identify the original object across this history. Finally propose a consistency check connecting directory entries and inode link counts, stating which exceptional objects or implementation details your toy model excludes.

Get a starting hint

A hard link copies a name-to-inode association, not the file bytes. Reusing a deleted name creates a new association.

Compare your reasoning with the worked solution

Initially alpha→42, inode 42 contains ABC, and its link count is 1. Creating beta adds beta→42 and raises the count to 2; there is still one data object. Overwriting offset 1 through beta changes inode 42's contents to AZC. Reading through alpha at that moment sees the same AZC because both names select inode 42.

Removing alpha deletes only alpha→42 and reduces inode 42's count to 1. Beta remains and still reads AZC. Creating a new alpha yields alpha→57 with contents XYZ and count 1. Beta remains beta→42 with AZC and count 1. Reusing the spelling alpha does not reconnect beta to the new file. Names are lookup relationships whose targets can change; they are not permanent object identities.

For this simplified collection of ordinary files, scan all directory entries and count incoming references to each inode. Compare that number with the inode's stored link count and verify that every referenced inode is allocated. Also ensure allocated file blocks and free blocks are disjoint. A mismatch suggests inconsistent metadata, but repairs require identifying which information is authoritative and accounting for interruptions. The exercise excludes directories' special links, mounted filesystems, open-but-unlinked lifetime rules, concurrent mutation, and inode-number reuse. A durable object identifier across filesystems and time may therefore need more than the number 42. The original article's organization makes these checks possible without equating a file's identity with one chosen pathname.

Check your reasoning

• Tracks every mapping, shared write, and link count correctly.
• Explains why recreated alpha and beta name distinct objects.
• Proposes a scoped consistency invariant and states excluded lifetime/concurrency cases.

Check your understanding

Why can a pipe reader wait after the intended writer exits?

• Pipes never have end-of-file.
• Another process still holds an open write-side reference.
• The reader must know the writer’s executable filename.

Explanation

All write-side references must be closed before ordinary pipe EOF is observed.

Why can output redirection work for a program that knows nothing about shell syntax?

• The kernel parses every application’s command line.
• The program must rewrite itself.
• The shell arranges its output descriptor before executing it.

Explanation

Descriptor setup separates application I/O from command-line redirection policy.

Original paper and sources

Dennis M. Ritchie and Ken Thompson. The UNIX Time-Sharing System. Communications of the ACM 17(7), July 1974, pp. 365-375. Linked electronic reconstruction by Eric A. Brewer identifies the 1974 article; the previous Bell Labs cacm.pdf was the revised 1978 BSTJ version.

Read the original paper →

Read the primary paper: University of California, Berkeley

• The UNIX Time-Sharing System: University of California, Berkeley