The Design of the UNIX Operating System (Maurice J. Bach) (z-library.sk, 1lib.sk, z-lib.sk)

AT&T `11=■• •■••■ THE DESIGN OF THE UNIX® OPERATING SYSTEM Maurice J. Bach PRENTICE-HALL, INC., Englewood Cliffs, New Jersey 07632

Copyright © 1986 by Bell Telephone Laboratories, Incorporated. Published by Prentice-Hall, Inc. A division of Simon & Schuster Englewood Cliffs, New Jersey 07632 Prentice-Hall Software Series Brian W. Kernighan, Advisor Cover Design Consultant: Sarah Bach UNIX® is a registered trademark of AT&T. DEC, PDP and VAX are trademarks of Digital Equipment Corp. Series 32000 is a trademark of National Semiconductor Corp. ®Ada is a registered trademark of the U.S. Government (Ada Joint Program Office). UNIVAC is a trademark of Sperry Corp. This document was set on an AUTOLOGIC, Inc. APS-5 phototypesetter driven by the TROFF formatter operating under the UNIX system on an AT&T 3B20 computer. The Publisher offers discounts on this book when ordered in bulk quantities. For more information write: Special Sales/College Marketing Prentice-Hall, Inc. College Technical and Reference Division Englewood Cliffs, New Jersey 07632 The author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The author and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this book. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs. All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writing from the publisher Prentice-Hall International (UK) Limited, London Prentice-Hall of Australia Pty. Limited, Sydney Prentice-Hall Canada Inc., Toronto Prentice-Hall Hispanoamericana, S.A., Mexico Prentice-Hall of India Private Limited, New Delhi Prentice-Hall of Japan, Inc., Tokyo Prentice-Hall of Southeast Asia Pte. Ltd., Singapore Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro

To my parents, for their patience and devotion, to my daughters, Sarah and Rachel, for their laughter, to my son, Joseph, who arrived after the first printing, and to my wife, Debby, for her love and understanding.

CONTENTS PREFACE xi CHAPTER 1 GENERAL OVERVIEW OF THE SYSTEM 1 1.1 History 1 1.2 System Structure 4 1.3 User Perspective 6 1.4 Operating System Services 14 1.5 Assumptions About Hardware 15 1.6 Summary 18 v

CHAPTER 2 INTRODUCTION TO THE KERNEL 19 2.1 Architecture of the UNIX Operating System 19 2.2 Introduction to System Concepts 22 2.3 Kernel Data Structures 34 2.4 System Administration 34 2.5 Summary and Preview 36 2.6 Exercises 37 CHAPTER 3 THE BUFFER CACHE 38 3.1 Buffer Headers 39 3.2 Structure of the Buffer Pool 40 3.3 Scenarios for Retrieval of a Buffer 42 3.4 Reading and Writing Disk Blocks 53 3.5 Advantages and Disadvantages of the Buffer Cache 56 3.6 Summary 57 3.7 Exercises 58 CHAPTER 4 INTERNAL REPRESENTATION OF FILES 60 4.1 Inodes 61 4.2 Structure of a Regular File 67 4.3 Directories 73 4.4 Conversion of a Path Name to an Inode 74 4.5 Super Block 76 4.6 Inode Assignment to a New File 77 4.7 Allocation of Disk Blocks 84 4.8 Other File Types 88 4.9 Summary 88 4.10 Exercises 89 vi

CHAPTER 5 SYSTEM CALLS FOR THE FILE SYSTEM 91 5.1 Open 92 5.2 Read 96 5.3 Write 101 5.4 File and Record Locking 103 5.5 Adjusting the Position of File I/0 — LSEEK 103 5.6 Close 103 5.7 File Creation 105 5.8 Creation of Special Files 107 5.9 Change Directory and Change Root 109 5.10 Change Owner and Change Mode 110 5.11 STAT and FSTAT 110 5.12 Pipes 111 5.13 Dup 117 5.14 Mounting and Unmounting File Systems 119 5.15 Link 128 5.16 Unlink 132 5.17 File System Abstractions 138 5.18 File System Maintenance 139 5.19 Summary 140 5.20 Exercises 140 CHAPTER 6 THE STRUCTURE OF PROCESSES 146 6.1 Process States and Transitions 147 6.2 Layout of System Memory 151 6.3 The Context of a Process 159 6.4 Saving the Context of a Process 162 6.5 Manipulation of the Process Address Space 171 6.6 Sleep 182 V"

6.7 Summary 188 6.8 Exercises 189 CHAPTER 7 PROCESS CONTROL 191 7.1 Process Creation 192 7.2 Signals 200 7.3 Process Termination 212 7.4 Awaiting Process Termination 213 7.5 Invoking Other Programs 217 7.6 The User ID of a Process 227 7.7 Changing the Size of a Process 229 7.8 The Shell 232 7.9 System Boot and the INIT Process 235 7.10 Summary 238 7.11 Exercises 239 CHAPTER 8 PROCESS SCHEDULING AND TIME 247 8.1 Process Scheduling 248 8.2 System Calls For Time 258 8.3 Clock 260 8.4 Summary 268 8.5 Exercises 268 CHAPTER 9 MEMORY MANAGEMENT POLICIES 271 9.1 Swapping 272 9.2 Demand Paging 285 9.3 A Hybrid System With Swapping and Demand Paging . . 307 9.4 Summary 307 9.5 Exercises 308

CHAPTER 10 THE I/O SUBSYSTEM 312 10.1 Driver Interfaces 313 10.2 Disk Drivers 325 10.3 Terminal Drivers 329 10.4 Streams 344 10.5 Summary 351 10.6 Exercises 352 CHAPTER 11 INTERPROCESS COMMUNICATION 355 11.1 Process Tracing 356 11.2 System V IPC 359 11.3 Network Communications 382 11.4 Sockets 383 11.5 Summary 388 11.6 Exercises 389 CHAPTER 12 MULTIPROCESSOR SYSTEMS 391 12.1 Problem of Multiprocessor Systems 392 12.2 Solution With Master and Slave Processors 393 12.3 Solution With Semaphores 395 12.4 The Tunis System 410 12.5 Performance Limitations 410 12.6 Exercises 410 CHAPTER 13 DISTRIBUTED UNIX SYSTEMS 412 13.1 Satellite Processors 414 13.2 The Newcastle Connection 422 13.3 Transparent Distributed File Systems 426 13.4 A Transparent Distributed Model Without Stub Processes . 429 ix

13.5 Summary 430 13.6 Exercises 431 APPENDIX—SYSTEM CALLS 434 BIBLIOGRAPHY 454 INDEX 458

PREFACE The UNIX system was first described in a 1974 paper in the Communications of the ACM [Thompson 741 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 781 and 1984 [BLTJ 841. 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 EKernighan 841 and Advanced UNIX Programming [Rochkind 851 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. xi

xii PREFACE 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 IKernighan 78]. 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

PREFACE xiii in the book, but not a complete reference manual. The book is organized as follows. Chapter 1 is the introduction, giving a brief, general description of system features as perceived by the user and describing the system structure. Chapter 2 describes the general outline of the kernel architecture and presents some basic concepts. The remainder of the book follows the outline presented by the system architecture, describing the various components in a building block fashion. It can be divided into three parts: the file system, process control, and advanced topics. The file system is presented first, because its concepts are easier than those for process control. Thus, Chapter 3 describes the system buffer cache mechanism that is the foundation of the file system. Chapter 4 describes the data structures and algorithms used internally by the file system. These algorithms use the algorithms explained in Chapter 3 and take care of the internal bookkeeping needed for managing user files. Chapter 5 describes the system calls that provide the user interface to the file system; they use the algorithms in Chapter 4 to access user files. Chapter 6 turns to the control of processes. It defines the context of a process and investigates the internal kernel primitives that manipulate the process context. In particular, it considers the system call interface, interrupt handling, and the context switch. Chapter 7 presents the system calls that control the process context. Chapter 8 deals with process scheduling, and Chapter 9 covers memory management, including swapping and paging systems. Chapter 10 outlines general driver interfaces, with specific discussion of disk drivers and terminal drivers. Although devices are logically part of the file system, their discussion is deferred until here because of issues in process control that arise in terminal drivers. This chapter also acts as a bridge to the more advanced topics presented in the rest of the book. Chapter 11 covers interprocess communication and networking, including System V messages, shared memory and semaphores, and BSD sockets. Chapter 12 explains tightly coupled multiprocessor UNIX systems, and Chapter 13 investigates loosely coupled distributed systems. The material in the first nine chapters could be covered in a one-semester course on operating systems, and the material in the remaining chapters could be covered in advanced seminars with various projects being done in parallel. A few caveats must be made at this time. No attempt has been made to describe system performance in absolute terms, nor is there any attempt to suggest configuration parameters for a system installation. Such data is likely to vary according to machine type, hardware configuration, system version and implementation, and application mix. Similarly, 1 have made a conscious effort to avoid predicting future development of UNIX operating system features. Discussion of advanced topics does not imply a commitment by AT&T to provide particular features, nor should it even imply that particular areas are under investigation. It is my pleasure to acknowledge the assistance of many friends and colleagues who encouraged me while I wrote this book and provided constructive criticism of the manuscript. My deepest appreciation goes to Ian Johnstone, who suggested

xiv PREFACE that I write this book, gave me early encouragement, and reviewed the earliest draft of the first chapters. Ian taught me many tricks of the trade, and I will always be indebted to him. Doris Ryan also had a hand in encouraging me from the very beginning, and I will always appreciate her kindness and thoughtfulness. Dennis Ritchie freely answered numerous questions on the historical and technical background of the system. Many people gave freely of their time and energy to review drafts of the manuscript, and this book owes a lot to their detailed comments. They are Debby Bach, Doug Bayer, Lenny Brandwein, Steve Buroff, Tom Butler, Ron Gomes, Mesut Gunduc, Laura Israel, Dean Jagels, Keith Kelleman, Brian Kernighan, Bob Martin, Bob Mitze, Dave Nowitz, Michael Poppers, Marilyn Safran, Curt Schimmel, Zvi Spitz, Tom Vaden, Bill Weber, Larry Wehr, and Bob Zarrow. Mary Fruhstuck provided help in preparing the manuscript for typesetting. I would like to thank my management for their continued support throughout this project and my colleagues, for providing such a stimulating atmosphere and wonderful work environment at AT&T Bell Laboratories. John Wait and the staff at Prentice-Hall provided much valuable assitance and advice to get the book into its final form. Last, but not least, my wife, Debby, gave me lots of emotional support, without which I could never have succeeded.

1 GENERAL OVERVIEW OF THE SYSTEM The UNIX system has become quite popular since its inception in 1969, running on machines of varying processing power from microprocessors to mainframes and providing a common execution environment across them. The system is divided into two parts. The first part consists of programs and services that have made the UNIX system environment so popular; it is the part readily apparent to users, including such programs as the shell, mail, text processing packages, and source code control systems. The second part consists of the operating system that supports these programs and services. This book gives a detailed description of the operating system. It concentrates on a description of UNIX System V produced by AT&T but considers interesting features provided by other versions too. It examines the major data structures and algorithms used in the operating system that ultimately provide users with the standard user interface. This chapter provides an introduction to the UNIX system. It reviews its history and outlines the overall system structure. The next chapter gives a more detailed introduction to the operating system. 1.1 HISTORY In 1965, Bell Telephone Laboratories joined an effort with the General Electric Company and Project MAC of the Massachusetts Institute of Technology to 1

2 GENERAL OVERVIEW OF THE SYSTEM develop a new operating system called Multics [Organick 72 1 . The goals of the Multics system were to provide simultaneous computer access to a large community of users, to supply ample computation power and data storage, and to allow users to share their data easily, if desired. Many people who later took part in the early development of the UNIX system participated in the Multics work at Bell Laboratories. Although a primitive version of the Multics system was running on a GE 645 computer by 1969, it did not provide the general service computing for which it was intended, nor was it clear when its development goals would be met. Consequently, Bell Laboratories ended its participation in the project. With the end of their work on the Multics project, members of the Computing Science Research Center at Bell Laboratories were left without a "convenient interactive computing service" [Ritchie 84a 1 . In an attempt to improve their programming environment, Ken Thompson, Dennis Ritchie, and others sketched a paper design of a file system that later evolved into an early version of the UNIX file system. Thompson wrote programs that simulated the behavior of the proposed file system and of programs in a demand-paging environment, and he even encoded a simple kernel for the GE 645 computer. At the same time, he wrote a game program, "Space Travel," in Fortran for a GECOS system (the Honeywell 635), but the program was unsatisfactory because it was difficult to control the "space ship" and the program was expensive to run. Thompson later found a little-used PDP-7 computer that provided good graphic display and cheap executing power. Programming "Space Travel" for the PDP-7 enabled Thompson to learn about the machine, but its environment for program development required cross-assembly of the program on the GECOS machine and carrying paper tape for input to the PDP-7. To create a better development environment, Thompson and Ritchie implemented their system design on the PDP-7, including an early version of the UNIX file system, the process subsystem, and a small set of utility programs. Eventually, the new system no longer needed the GECOS system as a development environment but could support itself. The new system was given the name UNIX, a pun on the name Multics coined by another member of the Computing Science Research Center, Brian Kernighan. Although this early version of the UNIX system held much promise, it could not realize its potential until it was used in a real project. Thus, while providing a text processing system for the patent department at Bell Laboratories, the UNIX system was moved to a PDP-11 in 1971. The system was characterized by its small size: 16K bytes for the system, 8K bytes for user programs, a disk of 512K bytes, and a limit of 64K bytes per file. After its early success, Thompson set out to implement a Fortran compiler for the new system, but instead came up with the language B, influenced by BCPL [Richards 691 B was an interpretive language with the performance drawbacks implied by such languages, so Ritchie developed it into one he called C, allowing generation of machine code, declaration of data types, and definition of data structures. In 1973, the operating system was rewritten in C, an unheard of step at the time, but one that was to have tremendous impact on its acceptance among outside users. The number of installations at Bell

1.1 HISTORY 3 Laboratories grew to about 25, and a UNIX Systems Group was formed to provide internal support. At this time, AT&T could not market computer products because of a 1956 Consent Decree it had signed with the Federal government, but it provided the UNIX system to universities who requested it for educational purposes. AT&T neither advertised, marketed, nor supported the system, in adherence to the terms of the Consent Decree. Nevertheless, the system's popularity steadily increased. In 1974, Thompson and Ritchie published a paper describing the UNIX system in the Communications of the ACM [Thompson 74], giving further impetus to its acceptance. By 1977, the number of UNIX system sites had grown to about 500, of which 125 were in universities. UNIX systems became popular in the operating telephone companies, providing a good environment for program development, network transaction operations services, and real-time services (via MERT [Lycklama 78a]). Licenses of UNIX systems were provided to commercial institutions as well as universities. In 1977, Interactive Systems Corporation became the first Value Added Reseller (VAR)' of a UNIX system, enhancing it for use in office automation environments. 1977 also marked the year that the UNIX system was first "ported" to a non-PDP machine (that is, made to run on another machine with few or no changes), the lnterdata 8/32. With the growing popularity of microprocessors, other companies ported the UNIX system to new machines, but its simplicity and clarity tempted many developers to enhance it in their own way, resulting in several variants of the basic system. In the period from 1977 to 1982, Bell Laboratories combined several AT&T variants into a single system, known commercially as UNIX System III. Bell Laboratories later added several features to UNIX System III, calling the new product UNIX System V, 2 and AT&T announced official support for System V in January 1983. However, people at the University of California at Berkeley had developed a variant to the UNIX system, the most recent version of which is called 4.3 BSD for VAX machines, providing some new, interesting features. This book will concentrate on the description of UNIX System V and will occasionally talk about features provided in the BSD system. By the beginning of 1984, there were about 100,000 UNIX system installations in the world, running on machines with a wide range of computing power from microprocessors to mainframes and on machines across different manufacturers' product lines. No other operating system can make that claim. Several reasons have been suggested for the popularity and success of the UNIX system. I. Value Added Resellers add specific applications to a computer system to satisfy a particular market. They market the applications rather than the operating system upon which they run. 2. What happened to System IV? An internal version of the system evolved into System V.

4 GENERAL OVERVIEW OF THE SYSTEM • The system is written in a high-level language, making it easy to read, understand, change, and move to other machines. Ritchie estimates that the first system in C was 20 to 40 percent larger and slower because it was not written in assembly language, but the advantages of using a higher-level language far outweigh the disadvantages (see page 1965 of [Ritchie 780. • It has a simple user interface that has the power to provide the services that users want. • It provides primitives that permit complex programs to be built from simpler programs. • It uses a hierarchical file system that allows easy maintenance and efficient implementation. • It uses a consistent format for files, the byte stream, making application programs easier to write. • It provides a simple, consistent interface to peripheral devices. • It is a multi-user, multiprocess system; each user can execute several processes simultaneously. • It hides the machine architecture from the user, making it easier to write programs that run on different hardware implementations. The philosophy of simplicity and consistency underscores the UNIX system and accounts for many of the reasons cited above. Although the operating system and many of the command programs are written in C, UNIX systems support other languages, including Fortran, Basic, Pascal, Ada, Cobol, Lisp, and Prolog. The UNIX system can support any language that has a compiler or interpreter and a system interface that maps user requests for operating system services to the standard set of requests used on UNIX systems. 1.2 SYSTEM STRUCTURE Figure 1.1 depicts the high-level architecture of the UNIX system. The hardware at the center of the diagram provides the operating system with basic services that will be described in Section 1.5. The operating system interacts directly3 with the hardware, providing common services to programs and insulating them from hardware idiosyncrasies. Viewing the system as a set of layers, the operating system is commonly called the system kernel, or just the kernel, emphasizing its 3. In some implementations of the UNIX system, the operating system interacts with a native operating system that, in turn, interacts with the underlying hardware and provides necessary services to the system. Such configurations allow installations to run other operating systems and their applications in parallel to the UNIX system. The classic example of such a configuration is the MERT system [Lycklama 78a 1 . More recent configurations include implementations for IBM System/370 computers [Felton 84 1 and for UNIVAC 1100 Series computers [Bodenstab 841.

1.2 SYSTEM STRUCTURE 5 Figure 1.1. Architecture of UNIX Systems isolation from user programs. Because programs are independent of the underlying hardware, it is easy to move them between UNIX systems running on different hardware if the programs do not make assumptions about the underlying hardware. For instance, programs that assume the size of a machine word are more difficult to move to other machines than programs that do not make this assumption. Programs such as the shell and editors (ed and vi) shown in the outer layers interact with the kernel by invoking a well defined set of system calls. The system calls instruct the kernel to do various operations for the calling program and exchange data between the kernel and the program. Several programs shown in the figure are in standard system configurations and are known as commands, but private user programs may also exist in this layer as indicated by the program whose name is a.out, the standard name for executable files produced by the C compiler. Other application programs can build on top of lower-level programs, hence the existence of the outermost layer in the figure. For example, the standard C compiler, cc, is in the outermost layer of the figure: it invokes a C preprocessor,