The Design of the UNIX Operating System

The UNIX system was first described in a 1974 paper in the Communications of the ACM Thompson 74 by Ken Thompson and Dennis Ritchie. Since that time, it has become increasingly widespread and popular throughout the computer industry where more and more vendors are offering support for it on their machines. It is especially popular in universities where it is frequently used for operating systems research and case studies.

Many books and papers have described parts of the system, among them, two special issues of the Bell System Technical Journal in 1978 BSTJ 78 and 1984 BLTJ 84. Many books describe the user level interface, particularly how to use electronic mail, how to prepare documents, or how to use the command interpreter called the shell; some books such as The UNIX Programming Environment Kernighan 84 and Advanced UNIX Programming Rochkind 85 describe the programming interface. This book describes the internal algorithms and structures that form the basis of the operating system (called the kernel) and their relationship to the programmer interface. It is thus applicable to several environments. First, it can be used as a textbook for an operating systems course at either the advanced undergraduate or first-year graduate level. It is most beneficial to reference the system source code when using the book, but the book can be read independently, too. Second, system programmers can use the book as a reference to gain better understanding of how the kernel works and to compare algorithms used in the UNIX system to algorithms used in other operating systems.

Finally, programmers on UNIX systems can gain a deeper understanding of how their programs interact with the system and thereby code more-efficient, sophisticated programs.

The material and organization for the book grew out of a course that I prepared and taught at AT&T Bell Laboratories during 1983 and 1984. While the course centered on reading the source code for the system, I found that understanding the code was easier once the concepts of the algorithms had been mastered. I have attempted to keep the descriptions of algorithms in this book as simple as possible, reflecting in a small way the simplicity and elegance of the system it describes. Thus, the book is not a line-by-line rendition of the system written in English; it is a description of the general flow of the various algorithms, and most important, a description of how they interact with each other. Algorithms are presented in a C-like pseudo-code to aid the reader in understanding the natural language description, and their names correspond to the procedure names in the kernel. Figures depict the relationship between various data structures as the system manipulates them. In later chapters, small C programs illustrate many system concepts as they manifest themselves to users. In the interests of space and clarity, these examples do not usually check for error conditions, something that should always be done when writing programs. I have run them on System V; except for programs that exercise features specific to System V, they should run on other versions of the system, too.

Many exercises originally prepared for the course have been included at the end of each chapter, and they are a key part of the book. Some exercises are straightforward, designed to illustrate concepts brought out in the text. Others are more difficult, designed to help the reader understand the system at a deeper level. Finally, some are exploratory in nature, designed for investigation as a research problem. Difficult exercises are marked with asterisks.

The system description is based on UNIX System V Release 2 supported by AT&T, with some new features from Release 3. This is the system with which I am most familiar, but I have tried to portray interesting contributions of other variations to the operating system, particularly those of Berkeley Software Distribution (BSD). I have avoided issues that assume particular hardware characteristics, trying to cover the kernel-hardware interface in general terms and ignoring particular machine idiosyncrasies. Where machine-specific issues are important to understand implementation of the kernel, however, I delve into the relevant detail. At the very least, examination of these topics will highlight the parts of the operating system that are the most machine dependent.

The reader must have programming experience with a high-level language and, preferably, with an assembly language as a prerequisite for understanding this book. It is recommended that the reader have experience working with the UNIX system and that the reader knows the C language. However, I have attempted to write this book in such a way that the reader should still be able to absorb the material without such background. The appendix contains a simplified description of the system calls, sufficient to understand the presentation in the book, but not a complete reference manual.

1. General Overview of the System
1. History
2. System Structure
3. User Perspective
4. Operating System Services
5. Assumptions About Hardware
6. Summary
2. Introduction to the Kernel
1. Architecture of the UNIX Operating System
2. Introduction to System Concepts
3. Kernel Data Structures
4. System Administration
5. Summary and Preview
6. Exercises
3. The Buffer Cache
1. Buffer Headers
2. Structure of the Buffer Pool
3. Scenarios for Retrieval of a Buffer
4. Reading and Writing Disk Blocks
5. Advantages and Disadvantages of the Buffer Cache
6. Summary
7. Exercises
4. Internal Representation of Files
1. Inodes
2. Structure of a Regular File
3. Directories
4. Conversion of a Path Name to an Inode
5. Super Block
6. Inode Assignment to a New File
7. Allocation of Disk Blocks
8. Other File Types
9. Summary
10. Exercises
5. System Calls for the File System
1. Open
2. Read
3. Write
4. File and Record Locking
5. Adjusting the Position of File I/O — lseek
6. Close
7. File Creation
8. Creation of Special Files
9. Change Directory and Change Root
10. Change Owner and Change Mode
11. Stat and fstat
12. Pipes
13. Dup
14. Mounting and Unmounting File Systems
15. Link
16. Unlink
17. File System Abstractions
18. File System Maintenance
19. Summary
20. Exercises
6. The Structure of Processes
1. Process States and Transitions
2. Layout of System Memory
3. The Context of a Process
4. Saving the Context of a Process
5. Manipulation of the Process Address Space
6. Sleep
7. Summary
8. Exercises
7. Process Control
1. Process Creation
2. Signals
3. Process Termination
4. Awaiting Process Termination
5. Invoking Other Programs
6. The User ID of a Process
7. Changing the Size of a Process
8. The Shell
9. System Boot and the INIT Process
10. Summary
11. Exercises
8. Process Scheduling and Time
1. Process Scheduling
2. System Calls For Time
3. Clock
4. Summary
5. Exercises
9. Memory Management Policies
1. Swapping
2. Demand Paging
3. A Hybrid System With Swapping and Demand Paging
4. Summary
5. Exercises
10. The I/O Subsystem
1. Driver Interfaces
2. Disk Drivers
3. Terminal Drivers
4. Streams
5. Summary
6. Exercises
11. Interprocess Communication
1. Process Tracing
2. System V IPC
3. Network Communications
4. Sockets
5. Summary
6. Exercises
12. Multiprocessor Systems
1. Problem of Multiprocessor Systems
2. Solution With Master and Slave Processors
3. Solution With Semaphores
4. The Tunis System
5. Performance Limitations
6. Exercises
13. Distributed Unix Systems
1. Satellite Processors
2. The Newcastle Connection
3. Transparent Distributed File Systems
4. A Transparent Distributed Model Without Stub Processes
5. System Calls
6. Summary
7. Exercises

A classic. If you want to say you know operating systems, and haven't read this: you're probably lying.