A Berkeley Odyssey: Ten years of BSD history

by Marshall Kirk McKusick

from the January 1985 issue of Unix Review magazine

Ken Thompson and Dennis Ritchie presented the first UNIX paper at the Symposium on Operating Systems Principles at Purdue University in November, 1973. Professor Bob Fabry was in attendance and immediately became interested in obtaining a copy of the system to experiment with at Berkeley.

At the time, Berkeley had only large mainframe computer systems doing batch processing, so the first order of business was to get a PDP-11/45 suitable for running the then current Version 4 of UNIX. The Computer Science Department, together with the Mathematics Department and the Statistics Department were able to jointly purchase a PDP-11/45. In January, 1974, a Version 4 tape was delivered and UNIX was installed by graduate student Keith Standiford.

Although Ken Thompson was not involved in the installation — as he had been for most systems up to that time — his expertise was soon needed to determine the cause of several strange system crashes. Because Berkeley had only a 300 baud acoustic-coupled modem without auto answer capability, Thompson would call Standiford in the machine room and have him insert the phone into the modem; in this way Thompson was able to remotely debug crash dumps from New Jersey.

Many of the crashes were caused by the disk controller’s inability to reliably do overlapped seeks, contrary to the documentation. Berkeley’s 11/45 was among the first systems that Thompson had encountered that had two disks on the same controller! Thompson’s remote debugging was the first example of the cooperation that sprang up between Berkeley and Bell Labs. The willingness of the researchers at the Labs to share their work with Berkeley was instrumental in the rapid improvement of the software available at Berkeley.

Though UNIX was soon reliably up and running, the coalition of Computer Science, Mathematics, and Statistics began to run into problems; Math and Statistics wanted to run DEC’S RSTS system. After much debate, a compromise was reached in which each department would get an eight-hour shift; UNIX would run for eight hours followed by 16 hours of RSTS. To promote fairness, the time slices were rotated each day. Thus UNIX ran 8 am to 4 pm one day, 4 pm to midnight the next day, and midnight to 8 am the third day. Despite the bizarre schedule, students taking the Operating Systems course preferred to do their projects on UNIX rather than on the batch machine.

Professors Eugene Wong and Michael Stonebraker were both stymied by the confinements of the batch environment, so their Ingres database project was among the first groups to move from the batch machines to the interactive environment provided by UNIX. They quickly found the shortage of machine time and the odd hours on the 11/45 intolerable, so in the Spring of 1974, they purchased an 11/40 running the newly available Version 5. With their first distribution of Ingres in the Fall of 1974, the Ingres project became the first group in the Computer Science department to distribute its software. Several hundred Ingres tapes were shipped over the next six years, helping to establish Berkeley’s reputation for designing and building real systems.

Even with the departure of the Ingres project from the 11/45, there was still insufficient time available for the remaining students. To alleviate the shortage, Professors Michael Stonebraker and Bob Fabry set out in June, 1974, to get two instructional 11/45s for the Computer Science department’s own use. Early in 1975, the money was obtained. At nearly the same time DEC announced the 11/70, a machine that appeared to be much superior to the 11/45. Money for the two 11/45s was pooled to buy a single 11/70 that arrived in the Fall of 1975. Coincident with the arrival of the 11/70, Ken Thompson decided to take a one-year sabbatical as a visiting professor at his alma mater. Thompson, together with Jeff Schriebman and Bob Kridle, brought up the latest UNIX, Version 6, on the newly installed 11/70.

Also arriving in the Fall of 1975, were two unnoticed graduate students. Bill Joy and Chuck Haley; they both took an immediate interest in the new system. Initially they began working on a Pascal system that Thompson had hacked together while hanging around the 11/70 machine room. They expanded and improved the interpreter system to the point that it became the programming system of choice for students because of its excellent error recovery scheme and fast compile and execute time.

With the replacement of Model 33 teletypes by ADM-3 screen terminals, Joy and Haley began to feel stymied by the constraints of the ed editor. Working from an editor named em that they had obtained from Professor George Coulouris at Queen Mary’s College in London, they worked to produce the line-at-a-time editor ex.

With Ken Thompson’s departure at the end of the Summer of 1976, Joy and Haley begin to take an interest in exploring the internals of the UNIX kernel. Under Schriebman’s watchful eye, they first installed the fixes and improvements provided on the “fifty changes" tape from Bell Labs. Having learned to maneuver through the source code, they suggested several small enhancements to streamline certain kernel bottlenecks.

FIRST DISTRIBUTION

Meanwhile, interest in the error recovery work in the Pascal compiler brought in requests for copies of the system. Early in 1977, Joy put together the “Berkeley Software Distribution”. This first distribution included the Pascal system and — in an obscure subdirectory of the Pascal source — the editor ex. Over the next year, Joy, acting in the capacity of distribution secretary, sent out about 30 free copies of the system.

With the arrival of some ADM-3a terminals offering screen-addressable cursors, Joy was finally able to write vi, bringing screen-based editing to Berkeley. He soon found himself in a quandary. As is frequently the case in universities strapped for money, old equipment is never replaced all at once. Rather than support code for optimizing the updating of several different terminals, he decided to consolidate the screen management by using a small interpreter to redraw the screen. This interpreter was driven by a description of the terminal characteristics, thus spawning the now famous termcap.

By mid-1978, the software distribution clearly needed to be updated. The Pascal system had been made markedly more robust through feedback from its expanding user community, and had been split into two passes so that it could be run on PDP-11/34s. The result of the update was the “Second Berkeley Software Distribution” that was quickly shortened to 2 BSD. Along with the enhanced Pascal system, vi and termcap for several terminals was included. Once again, Bill Joy single-handedly put together distributions, answered the phone, and incorporated user feedback into the system. Over the next year, nearly 75 tapes were shipped. Though Joy moved on to other projects the following year, the 2 BSD distribution continued to expand. Today the latest version of this distribution, 2.9 BSD, is a complete system for PDP-11s.

VAX UNIX

Early in 1978, Professor Richard Fateman began looking for a machine with a larger address space that he could use to continue his work on Macsyma that had started on a PDP-10. The newly announced VAX-11/780 seemed to fulfill the requirements and was available within budget. Fateman and 13 other faculty members put together an NSF proposal that they combined with some departmental funds to purchase a VAX.

Initially the VAX ran DEC’S operating system VMS, but the department had gotten used to the UNIX environment and wanted to continue using it. So, shortly after the arrival of the VAX, Fateman obtained a copy of the 32/V port of UNIX to the VAX by John Reiser and Tom London of Bell Labs.

Although 32/V provided a Version 7 UNIX environment on the VAX, it did not take advantage of the virtual memory capability of the VAX hardware. Like its predecessors on the PDP-11, it was entirely a swap-based system. For the Macsyma group at Berkeley, the lack of virtual memory meant that the process address space was limited by the size of the physical memory, initially 1 MB on the new VAX.

To alleviate this problem, Fateman approached Professor Domenico Ferrari, a member of the systems faculty at Berkeley, to investigate the possibility of having his group write a virtual memory system for UNIX. Ozalp Babaoglu, one of Ferrari’s students, set about to find some way of implementing a working set paging system on the VAX; his task was complicated because the VAX lacked reference bits.

As Babaoglu neared the completion of his first cut at an implementation, he approached Bill Joy for some help in understanding the intricacies of the UNIX kernel. Intrigued by Babaoglu’s approach, Joy joined in helping to integrate the code into 32/V and then with the ensuing debugging.

Unfortunately, Berkeley had only a single VAX for both system development and general production use. Thus for several weeks, the tolerant user community alternately found themselves logging into 32/V and “Virtual VAX/UNIX”. Often their work on the latter system would come to an abrupt halt, followed several minutes later by a 32/V login prompt. By January of 1979, most of the bugs had been worked out, and 32/V had been relegated to history.

Joy saw that the 32-bit VAX would soon obsolete the 16-bit PDP-11 and began to port the 2 BSD software to the VAX. While Peter Kessler and I ported the Pascal system, Joy ported the editors ex and vi, the C shell, and the myriad other smaller programs on 2 BSD. By the end of 1979, a complete distribution had been put together. This distribution included the virtual memory kernel, the standard 32/V utilities, and the additions from 2 BSD. In December, 1979, Joy shipped the first of nearly a hundred copies of 3 BSD, the first VAX distribution from Berkeley.

DARPA SUPPORT

Meanwhile, in the offices of the planners for the Defense Advanced Research Projects Agency, DARPA, discussions were being held that would have a major influence on the work at Berkeley. One of DARPA’s early successes had been to set up a nationwide computer network to link together all its major research centers. At that time, DARPA was finding that many of the computers at these centers were reaching the end of their useful lifetime and had to be replaced. The heaviest cost of replacement was the porting of the research software to the new machines. In addition, many sites were unable to share their software because of the diversity of hardware and operating systems.

Choosing a single hardware vendor was impractical because of the widely varying computing needs of the research groups and the undesirability of depending on a single manufacturer. Thus, the planners at DARPA decided that the best solution was to unify at the operating systems level. After much discussion, UNIX was chosen as a standard because of its proven portability.

In the Fall of 1979, Bob Fabry responded to DARPA’s interest in moving towards UNIX by writing a proposal suggesting that Berkeley develop an enhanced version of 3 BSD for the use of the DARPA community. Fabry took a copy of his proposal to a meeting of DARPA image processing and VLSI contractors, plus representatives from Bolt, Beranek, and Newman, the developers of the ARPAnet. There was some reservation whether Berkeley could produce a working system, but the release of 3 BSD in December, 1979, assuaged most of the doubts.

With the increasingly good reputation of the 3 BSD release to validate his claims, Bob Fabry was able to land an 18-month contract with DARPA beginning in April, 1980. This contract was to add features needed by the DARPA contractors. He immediately hired Laura Tong to handle the project administration. With the negotiations for the contract on track, Fabry turned his attention to finding a project leader to manage the software development. Fabry had assumed that since Joy had just passed his Ph.D. qualifying examination, he would rather concentrate on completing his degree than assume the software development position. But Joy had other plans. One night in early March he phoned Fabry at home to express interest in taking charge of the further development of UNIX. Though surprised by the offer, Fabry took little time to agree.

The project started promptly. Tong set up a distribution system that could handle a higher volume of orders than Joy’s previous distributions. Fabry managed to coordinate with Bob Guffy at AT&T, and lawyers at the University of California to formally release UNIX under terms agreeable to all. Joy incorporated Jim Kulp’s job control, added auto reboot, a 1K block file system, and support for the latest VAX machine, the VAX-11/750. By October, 1980, a polished distribution that also included the Pascal compiler, the Franz Lisp system, and an enhanced mail handling system was released as 4 BSD. During its nine-month lifetime, nearly 150 copies were shipped. The license arrangement was on a per institution basis rather than a per machine basis, thus the distribution ran on about 500 machines.

With the increasingly wide distribution and visibility of Berkeley UNIX, several critics began to emerge. David Kashtan at Stanford Research Institute wrote a paper describing the results of benchmarks he had run on both VMS and Berkeley UNIX. These benchmarks showed several severe performance problems with the UNIX system for the VAX. Setting his future plans aside for several months, Joy systematically began tuning up the kernel. Within weeks he had a rebuttal paper written showing that Kastan’s benchmarks could be made to run as well on UNIX as they could on VMS. Rather than continue shipping 4 BSD, the tuned up system with the addition of Robert Elz’s auto configuration code was released as 4.1 BSD in June, 1981. Over its two-year lifetime about 400 distributions were shipped.

4.2 BSD

With the release of 4.1 BSD, much of the furor over performance died down. DARPA was sufficiently satisfied with the results of the first contract that a new two-year contract was granted to Berkeley with funding almost five times that of the original. Half of the money went to the UNIX project, the rest to other researchers in the Computer Science department. The contract called for major work to be done on the system so the DARPA research community could better do its work.

Based on the needs of the DARPA community, goals were set and work began to define the modifications to the system. In particular, the new system was expected to include a faster file system that would raise throughput to the speed of available disk technology, would support processes with multigigabyte address space requirements, would provide flexible interprocess communication facilities that would allow researchers to do work in distributed systems, and would integrate networking support so that machines running the new system could easily participate in the ARPAnet.

To assist in defining the new system, Duane Adams, Berkeley’s contract monitor at DARPA, formed a group known as the “steering committee” to help guide the design work and ensure that the research community’s needs were addressed. This committee met twice a year between April, 1981 and June, 1983, and included Bob Fabry, Bill Joy, and Sam Leffler of the University of California at Berkeley; Alan Nemeth and Rob Gurwitz of Bolt, Beranek, and Newman; Dennis Ritchie of Bell Laboratories; Keith Lantz of Stanford University; Rick Rashid of Carnegie-Mellon University; Bert Halstead of Massachusetts Institute of Technology; Dan Lynch of The Information Sciences Institute; Duane Adams and Bob Baker of DARPA; and Jerry Popek of the University of California at Los Angeles. Beginning in 1984, these meetings were supplanted by workshops that were expanded to include many more people.

An initial document proposing facilities to be included in the new system was circulated to the steering committee and other people outside Berkeley in July, 1981, sparking many lengthy debates. In the Summer of 1981, I became involved with the project and took on the implementation of the new file system. During the summer, Joy concentrated on implementing a prototype version of the interprocess communication facilities. In the Fall of 1981, Sam Leffler joined the project as a fulltime staff member to work with Bill Joy.

When Rob Gurwitz released an early implementation of the TCP/IP protocols to Berkeley, Joy integrated it into the system and tuned its performance. During this work, it became clear to Joy and Leffler that the new system would need to provide support for more than just the DARPA standard network protocols. Thus, they redesigned the internal structuring of the software, refining the interfaces so that multiple network protocols could be used simultaneously.

With the internal restructuring completed and the TCP/IP protocols integrated with the prototype IPC facilities, several simple applications were created to provide local users access to remote resources. These programs, rcp, rsh, rlogin, and rwho, were intended to be temporary tools that would eventually be replaced by more reasonable facilities (hence the use of the distinguishing r prefix). This system, called 4.1a, was first distributed in April, 1982 for local use; it was never intended that it would have wide circulation, though bootleg copies of the system proliferated as sites grew impatient waiting for the 4.2 release.

The 4.1a system was obsolete long before it was frozen. However, its construction and feedback from users provided valuable information that was used to create a revised proposal for the new system called the “4.2 BSD System Manual”. This document was circulated in February, 1982 and contained a concise description of the proposed user interface to the system facilities that were to be part of 4.2 BSD.

Concurrent with the 4.1a development, I completed the implementation of the new file system, and by June of 1982 had fully integrated it into the 4.1a kernel. The resulting system was called 4.1b and ran on only a few select development machines at Berkeley. Joy felt that with significant impending changes to the system, it was best to avoid even a local distribution, particularly since it required every machine’s file systems to be dumped and restored to convert from 4.1a to 4.1b. Once the file system proved to be stable, Leffler proceeded to add the new file system-related system calls, while Joy worked on revising the interprocess communication facilities.

In late Spring 1982, Joy announced he was joining Sun Microsystems. Over the summer, he split his time between Sun and Berkeley, spending most of his time polishing his revisions to the interprocess communication facilities and reorganizing the UNIX kernel sources to isolate machine dependencies. Pauline Schwartz was hired to take over the distribution duties. David Mosher was hired as a technical manager to resolve problems from users in the field and to handle ordering, installation, and running of the project’s hardware.

With Joy’s departure, Leffler took over responsibility for completing the project. Certain deadlines had already been established and the release had been promised to the DARPA community for the Spring of 1983. Given the time constraints, the work remaining to complete the release was evaluated and priorities were set. In particular, the virtual memory enhancements and the most sophisticated parts of the interprocess communication design were relegated to low priority (and later shelved completely). Also, with the implementation more than a year old and the UNIX community’s expectations heightened, it was decided an intermediate release should be put together to hold people until the final system could be completed. This system, called 4.1c, was distributed in April, 1983; many vendors used this release to prepare for ports of 4.2 to their hardware.

In June, 1983, Bob Fabry turned over administrative control of the project to Professors Domenico Ferrari and Susan Graham to begin a sabbatical free from the frantic pace of the previous four years. Leffler continued the completion of the system, implementing the new signal facilities, adding to the networking support, redoing the standalone I/O system to simplify the installation process, integrating the disk quota facilities from Robert Elz, updating all the documentation, and tracking the bugs from the 4.1c release. In August, 1983, the system was released as 4.2 BSD.

When Leffler left Berkeley for Lucasfilm following the completion of 4.2, he was replaced by Mike Karels. Karels’s previous experience with the 2.9 BSD software distribution provided an ideal background for his new job. The popularity of 4.2 BSD was impressive; within 18 months, more copies of 4.2 BSD had been shipped than of all the previous Berkeley software distributions combined.

As with 4 BSD, commentary of the vociferous critics was quick in coming. Most of the complaints indicated that the system ran too slowly. The problem, not surprisingly, was that the new facilities had not been tuned and that many of the kernel data structures were not well suited to their new uses. Karels’ first year on the project was spent tuning and polishing the system. An anticipated release of the polished system early in 1985 is expected to quell many of the performance complaints — much as the 4.1 BSD release quelled many of the complaints about 4 BSD.

After completing my Ph.D. in December 1984, I joined Mike Karels on the project. We hope that other researchers will continue to share their work with Berkeley. By incorporating the work of other researchers uniformly into the UNIX system at Berkeley, we can continue to offer the UNIX community a widely available state-of-the-art UNIX system.

ACKNOWLEDGEMENTS

I thank Bill Joy, Sam Leffler, Eric Allman, and Professors Bob Fabry, Richard Fateman, and Domenico Ferrari for providing the historical information presented in this article. Unfortunately, space constraints prevent me from describing the enormous amount of work that went into the user level software. I thank those people whose accomplishments have not been mentioned, but nevertheless have contributed much to the system’s vitality. For the last five years, I have been supported by the National Science Foundation under grant MCS80-05144, and the Defense Advance Research Projects Agency (DoD) under ARPA Order No. 4031 monitored by Naval Electronic System Command under Contract No. N00039-82-C-0235.

---

Kirk McKusick is involved in the development of Berkeley UNIX as a Research Computer Scientist for the Computer Systems Research Group at the University of California. While a graduate student, he implemented the fast file system distributed on 4.2 BSD and worked on the Berkeley Pascal system.