The Design and Implementation of the 4.4Bsd Operating System - Hardcover

Bostic, Keith

Hardcover

ISBN 10: 0201549794 ISBN 13: 9780201549799

Publisher: Addison-Wesley, 1996

Synopsis

This book describes the design and implementation of the BSD operating system--previously known as the Berkeley version of UNIX. Today, BSD is found in nearly every variant of UNIX, and is widely used for Internet services and firewalls, timesharing, and multiprocessing systems. Readers involved in technical and sales support can learn the capabilities and limitations of the system; applications developers can learn effectively and efficiently how to interface to the system; systems programmers can learn how to maintain, tune, and extend the system. Written from the unique perspective of the system's architects, this book delivers the most comprehensive, up-to-date, and authoritative technical information on the internal structure of the latest BSD system.

As in the previous book on 4.3BSD (with Samuel Leffler), the authors first update the history and goals of the BSD system. Next they provide a coherent overview of its design and implementation. Then, while explaining key design decisions, they detail the concepts, data structures, and algorithms used in implementing the system's facilities. As an in-depth study of a contemporary, portable operating system, or as a practical reference, readers will appreciate the wealth of insight and guidance contained in this book.

Highlights of the book:

• Details major changes in process and memory management
• Describes the new extensible and stackable filesystem interface
• Includes an invaluable chapter on the new network filesystem
• Updates information on networking and interprocess communication

About this title

From the Inside Flap

This book is an extensive revision of the first authoritative and full-length description of the design and implementation of the research versions of the UNIX system developed at the University of California at Berkeley. Most detail is given about 4.4BSD, which incorporates the improvements of the previous Berkeley versions. Although 4.4BSD includes nearly 500 utility programs in addition to the kernel, this book concentrates almost exclusively on the kernel.

The UNIX System

The UNIX system runs on computers ranging from personal home systems to the largest supercomputers. It is the operating system of choice for most multiprocessor, graphics, and vector-processing systems, and is widely used for its original purpose of timesharing. It is the most common platform for providing network services (from FTP to WWW) on the Internet. It is the most portable operating system ever developed. This portability is due partly to its implementation language, C Kernighan & Ritchie, 1978 (which is itself one of the most widely ported languages), and partly to the elegant design of the system. Many of the system's features are imitated in other systems O'Dell, 1987.

Since its inception in 1969 Ritchie & Thompson, 1978, the UNIX system has developed in a number of divergent and rejoining streams. The original developers continued to advance the state of the art with their Ninth and Tenth Edition UNIX inside AT&T Bell Laboratories, and then their Plan 9 successor to UNIX. Meanwhile, AT&T licensed UNIX System V as a product, before selling it to Novell. Novell passed the UNIX trademark to X/OPEN and sold the source code and distribution rights to Santa Cruz Operation (SCO). Both System V and Ninth Edition UNIX were strongly influenced by the Berkeley Software Distributions produced by the Computer Systems Research Group (CSRG) of the University of California at Berkeley.

Berkeley Software Distributions

These Berkeley systems have introduced several useful programs and facilities to the UNIX community: 2BSD (the Berkeley PDP-11 system): the text editor vi 3BSD (the first Berkeley VAX system): demand-paged virtual-memory support 4.0BSD: performance improvements 4.1BSD: job control, autoconfiguration, and long C identifiers 4.2BSD and 4.3BSD: reliable signals; a fast filesystem; improved networking, including a reference implementation of TCP/IP; sophisticated interprocess-communication (IPC) primitives; and more performance improvements 4.4BSD: a new virtual memory system; a stackable and extensible vnode interface; a network filesystem (NFS); a log-structured filesystem, numerous filesystem types, including loopback, union, and uid/gid mapping layers; an ISO9660 filesystem (e.g., CD-ROM); ISO networking protocols; support for 68K, SPARC, MIPS, and PC architectures; POSIX support, including termios, sessions, and most utilities; multiple IP addresses per interface; disk labels; and improved booting

4.2BSD, 4.3BSD, and 4.4BSD are the bases for the UNIX systems of many vendors, and are used internally by the development groups of many other vendors. Many of these developments have also been incorporated by System V, or hav e been added by vendors whose products are otherwise based on System V.

The implementation of the TCP/IP networking protocol suite in 4.2BSD and 4.3BSD, and the availability of those systems, explain why the TCP/IP networking protocol suite is implemented so widely throughout the world. Numerous vendors have adapted the Berkeley networking implementations, whether their base system is 4.2BSD, 4.3BSD, 4.4BSD, System V, or even Digital Equipment Corporation's VMS or Microsoft's Winsock interface in Windows '95 and Windows/NT.

4BSD has also been a strong influence on the POSIX (IEEE Std 1003.1) operating-system interface standard, and on related standards. Several features--such as reliable signals, job control, multiple access groups per process, and the routines for directory operations--have been adapted from 4.3BSD for POSIX.

Material Covered in this Book

This book is about the internal structure of 4.4BSD Quarterman et al, 1985, and about the concepts, data structures, and algorithms used in implementing 4.4BSD's system facilities. Its level of detail is similar to that of Bach's book about UNIX System V Bach, 1986; however, this text focuses on the facilities, data structures, and algorithms used in the Berkeley variant of the UNIX operating system. The book covers 4.4BSD from the system-call level down--from the interface to the kernel to the hardware itself. The kernel includes system facilities, such as process management, virtual memory, the I/O system, filesystems, the socket IPC mechanism, and network protocol implementations. Material above the system-call level--such as libraries, shells, commands, programming languages, and other user interfaces--is excluded, except for some material related to the terminal interface and to system startup. Like Organick's book about Multics Organick, 1975, this book is an in-depth study of a contemporary operating system.

Where particular hardware is relevant, the book refers to the Hewlett-Packard HP300 (Motorola 68000-based) architecture. Because 4.4BSD was developed on the HP300, that is the architecture with the most complete support, so it provides a convenient point of reference.

Readers who will benefit from this book include operating-system implementors, system programmers, UNIX application developers, administrators, and curious users. The book can be read as a companion to the source code of the system, falling as it does between the manual CSRG, 1994 and the code in detail of treatment. But this book is specifically neither a UNIX programming manual nor a user tutorial (for a tutorial, see Libes & Ressler, 1988). Familiarity with the use of some version of the UNIX system (see, for example, Kernighan & Pike, 1984), and with the C programming language (see, for example, Kernighan & Ritchie, 1988) would be extremely useful.

Use in Courses on Operating Systems

This book is suitable for use as a reference text to provide background for a primary textbook in a second-level course on operating systems. It is not intended for use as an introductory operating-system textbook; the reader should have already encountered terminology such as memory management, process scheduling, and I/O systems Silberschatz & Galvin, 1994. Familiarity with the concepts of network protocols Tanenbaum, 1988; Stallings, 1993; Schwartz, 1987 will be useful for understanding some of the later chapters.

Exercises are provided at the end of each chapter. The exercises are graded into three categories indicated by zero, one, or two asterisks. The answers to exercises that carry no asterisks can be found in the text. Exercises with a single asterisk require a step of reasoning or intuition beyond a concept presented in the text. Exercises with two asterisks present major design projects or open research questions.

Organization

This text discusses both philosophical and design issues, as well as details of the actual implementation. Often, the discussion starts at the system-call level and descends into the kernel. Tables and figures are used to clarify data structures and control flow. Pseudocode similar to the C language is used to display algorithms. Boldface font identifies program names and filesystem pathnames. Italics font introduces terms that appear in the glossary and identifies the names of system calls, variables, routines, and structure names. Routine names (other than system calls) are further identified by the name followed by a pair of parenthesis (e.g., malloc() is the name of a routine, whereas argv is the name of a variable).

The book is divided into five parts, organized as follows:

Part 1, Overview

Three introductory chapters provide the context for the complete operating system and for the rest of the book. Chapter 1, History and Goals, sketches the historical development of the system, emphasizing the system's research orientation. Chapter 2, Design Overview of 4.4BSD, describes the services offered by the system, and outlines the internal organization of the kernel. It also discusses the design decisions that were made as the system was developed. Sections 2.3 through 2.14 in Chapter 2 give an overview of their corresponding chapter. Chapter 3, Kernel Services, explains how system calls are done, and describes in detail several of the basic services of the kernel.

Part 2, Processes

The first chapter in this part--Chapter 4, Process Management--lays the foundation for later chapters by describing the structure of a process, the algorithms used for scheduling the execution of processes, and the synchronization mechanisms used by the system to ensure consistent access to kernel-resident data structures. In Chapter 5, Memory Management, the virtual-memory!=management system is discussed in detail.

Part 3, I/O System

First, Chapter 6, I/O System Overview, explains the system interface to I/O and describes the structure of the facilities that support this interface. Following this introduction are four c

About the Author

Marshall Kirk McKusick writes books and articles, consults, and teaches classes on UNIX- and BSD-related subjects. While at the University of California at Berkeley, he implemented the 4.2BSD fast file system, and was the research computer scientist at the Berkeley Computer Systems Research Group (CSRG) overseeing the development and release of 4.3BSD and 4.4BSD. He has twice served as the president of the board of the Usenix Association.

Keith Bostic is a member of the technical staff at Berkeley Software Design, Inc. He spent 8 years as a member of the CSRG, overseeing the development of over 400 freely redistributable UNIX-compatible utilities, and is the recipient of the 1991 Distinguished Achievement Award from the University of California, Berkeley, for his work to make 4.4BSD freely redistributable. Concurrently, he was the principle architect of the 2.10BSD release of the Berkeley Software Distribution for PDP-11s, and the coauthor of the Berkeley Log Structured Filesystem and the Berkeley database package (DB). He is also the author of the widely used vi implementation, nvi. He received his undergraduate degree in Statistics and his Masters degree in Electrical Engineering from George Washington University. He is a member of the ACM, the IEEE, and several POSIX working groups. In his spare time, he enjoys scuba diving in the South Pacific, mountain biking, and working on a tunnel into Kirk and Eric's specially constructed wine cellar. He lives in Massachusetts with his wife, Margo Seltzer, and their cats.

Michael J. Karels is the System Architect and Vice President of Engineering at Berkeley Software Design, Inc. He spent 8 years as the Principal Programmer of the CSRG at the University of California, Berkeley as the system architect for 4.3BSD. Karels received his Bachelor's degree in Microbiology from the University of Notre Dame. While a graduate student in Molecular Biology at the University of California, he was the principal developer of the 2.9BSD UNIX release of the Berkeley Software Distribution for the PDP-11. He is a member of the ACM, the IEEE, and several POSIX working groups. He lives with his wife Teri Karels in the backwoods of Minnesota.

John S. Quarterman is Senior Technical Partner at Texas Internet Consulting, which consults in networks and open systems with particular emphasis on TCP/IP networks, UNIX systems, and standards.He is the author of The Matrix: Computer Networks and Conferencing Systems Worldwide (Digital Press, 1990), and is a coauthor of UNIX, POSIX, and Open Systems: The Open Standards Puzzle (1993), Practical Internetworking with TCP/IP and UNIX (1993), The Internet Connection: System Connectivity and Configuration (1994), and The E-Mail Companion: Communicating Effectively via the Internet and Other Global Networks (1994), all published by Addison-Wesley. He is editor of Matrix News, a monthly newsletter about issues that cross network, geographic, and political boundaries, and of Matrix Maps Quarterly; both are published by Matrix Information and Directory Services, Inc. (MIDS) of Austin, Texas. He is a partner in Zilker Internet Park, which provides Internet access from Austin. He and his wife, Gretchen Quarterman, split their time among his home in Austin, hers in Buffalo, New York, and various other locations.

Edition details

• Publisher: Addison-Wesley
• Publication date: 1996
• ISBN 10: 0201549794
• ISBN 13: 9780201549799
• Binding: Hardcover
• Language: English
• Edition number: 1
• Number of pages: 580
• Editor: McKusick Marshall Kirk, Karels Michael J., Quaterman John S.