" .‘
`
`‘1'
`
`“'
`
`
`SILBERSCEQTZ. ‘
`g GAUNN
`
`-“‘5‘.GAGNEa;
`
`
`
`|PR2020-01288
`
`Sony EX1053 Page 1
`
`IPR2020-01288
`Sony EX1053 Page 1
`
`

`

`Opemfifly
`Sysfem 6'0fl6’8p7‘6’
`
`Seventh Edition
`
`ABRAHAM SILBERSCHATZ
`
`Yale University
`
`PETER BAER GALVIN
`
`Corporate Technologies, Inc.
`
`GREG GAGNE
`
`Westminster College
`
`WILEY
`
`JOHN WILEY & SONS. INC
`
`’Pw
`
`|PR2020-01288
`
`Sony EX1053 Page 2
`
`IPR2020-01288
`Sony EX1053 Page 2
`
`

`

`EXECUTIVE EDITOR
`
`Bill Zobrist
`
`SENIOR PRODUCTION EDITOR
`
`Ken Santor
`
`COVER DESIGNER
`
`Madelyn Lesure
`
`COVER ILLUSTRATION
`
`Susan St. Cyr
`
`TEXT DESIGNER
`
`Judy Allan
`
`This book was set in Palatino by the author using LaTeX and printed and bound by
`Von Hoffmann, Inc. The cover was printed by Von Hoffmann, Inc.
`
`This book is printed on acid free paper.
`
`00
`
`Copyright © 2005 John Wiley & Sons, Inc. All rights reserved.
`
`No part of this publication may be reproduced, stored in a retrieval system or transmitted
`
`in any form or by any means, electronic, mechanical, photocopying, recording, scanning
`or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States
`Copyright Act. without either the prior written permission of the Publisher, or
`
`authorization through payment of the appropriate per-copy fee to the Copyright
`Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax
`(978) 646-8600. Requests to the Publisher for permission should be addressed to the
`
`Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030,
`
`fl BY (225-5945).
`(201)748—601|,fax(201)748-6008., qfigfiq ‘
`10.3)
`‘
`To order books or for customer service please, Call
`t4;", L:'
`
` ISBN O-47l-69466-5
`
`
`
`
`A
`
`|PR2020-01288
`
`Sony EX1053 Page 3
`
`IPR2020-01288
`Sony EX1053 Page 3
`
`

`

`To my children, Lemor, Sivan, and Aaron
`
`Avi Silberschatz
`
`To my wife, Carla,
`and my children, Gwen Owen and Maddie
`
`Peter Baer Galvin
`
`In memory of Uncle Sonny,
`Robert Ion Heileman 1933 — 2004
`
`Greg Gagne
`
`"KI-I
`
`.
`
`”Jr-1',
`
`.‘lgmmrma m d 31"”7“ »"(‘v"" i" ‘-
`1“,, Wu plum“ a lame numhv:
`v-anh};
`-'
`tr
`.
`'
`-
`‘v
`'mauwv.‘tlwnprrst'
`was: {up ’7
`:
`.V
`,
`.
`.-. -
`'
`“7".-
`‘
`I' .lmqwflum.“
`_'
`.;.n.'-."
`.._
`-1:
`Md .
`"1 _'..‘
`. afit't‘f“
`_,‘_.
`
`~0-
`
`,
`
`(K ___‘
`
`|PR2020-01288
`
`Sony EX1053 Page 4
`
`IPR2020-01288
`Sony EX1053 Page 4
`
`

`

`Preface
`
`Operating systems are an essential part of any computer system. Similarly,
`a course on operating systems is an essential part of any computer—science
`education. This field is undergoing rapid change, as computers are now
`prevalent in virtually every application, from games for children through the
`most sophisticated planning tools for governments and multinational firms.
`Yet the fundamental concepts remain fairly clear, and it is on these that we base
`this book.
`
`We wrote this book as a text for an introductory course in operating systems
`at the junior or senior undergraduate level or at the first-year graduate level.
`We hope that practitioners will also find it useful. It provides a clear description
`of the concepts that underlie operating systems. As prerequisites, we assume
`that the reader is familiar with basic data structures, computer organization,
`and a high-level language, such as C. The hardware topics required for an
`understanding of operating systems are included in Chapter 1. For code
`examples, we use predominantly C, with some Java, but the reader can still
`understand the algorithms without a thorough knowledge of these languages.
`Concepts are presented using intuitive descriptions. Important theoretical
`results are covered, but formal proofs are omitted. The bibliographical notes
`contain pointers to research papers in which results were first presented and
`proved, as well as references to material for further reading. In place of proofs,
`figures and examples are used to suggest why we should expect the result in
`question to be true.
`The fundamental concepts and algorithms covered in the book are often
`based on those used in existing commercial operating systems. Our aim
`is to present these concepts and algorithms in a general setting that
`is
`not tied to one particular operating system. We present a large number of
`examples that pertain to the most popular and the most innovative operating
`systems, including Sun Microsystems’ Solaris; Linux; Mach; Microsoft MS‘rDOS,
`Windows NT, Windows 2000, and Windows XP; DEC VMS and TOPSZO; IBM 05/2;
`and Apple Mac OS X.
`[n this text, when we refer to Windows XP as an example operating system,
`we are implying both Windows XP and Windows 2000. If a feature exists in
`Windows XP that is not available in Windows 2000, we will state this explicitly.
`
`vii
`
`J
`
`|PR2020-01288
`
`Sony EX1053 Page 5
`
`IPR2020-01288
`Sony EX1053 Page 5
`
`

`

`a.
`'
`
`I
`
`viii
`
`Preface
`
`If a feature exists in Windows 2000 but not in Windows XP, then we will refer
`
`specifically to Windows 2000.
`
`-
`
`Organization of This Book
`
`The organization of this text reflects our many years of teaching operating
`systems courses. Consideration was also given to the feedback provided by
`the reviewers of the text, as well as comments submitted by readers of earlier
`editions. In addition, the content of the text corresponds to the suggestions
`from Computing Curricula 2001 for teaching operating systems, published by
`the Joint Task Force of the IEEE Computing Society and the Association for
`Computing Machinery (ACM).
`On the supporting web page for this text, we provide several sample syllabi
`that suggest various approaches for using the text in both introductory and
`advanced operating systems courses. As a general rule, we encourage readers
`to progress sequentially through the chapters, as this strategy provides the
`most thorough study of operating systems. However, by using the sample
`syllabi, a reader can select a different ordering of chapters (or subsections of
`chapters).
`
`Content of This Book
`
`The text is organized in eight major parts:
`
`0 Overview. Chapters 1 and 2 explain what operating systems are, what
`they do, and how they are designed and constructed. They discuss what the
`common features of an operating system are, what an operating system .
`does for the user, and what it does for the computer-system operator. The
`presentation is motivational and explanatory in nature. We have avoided a
`discussion of how things are done internally in these chapters. Therefore}
`they are suitable for individual readers or for students in lower-level
`.
`.._‘
`who want to learn what an operating system is without getting into
`details of the internal algorithms.
`
`H
`0 Process management. Chapters 3 through 7 describe the process con
`and concurrency as the heart of modern operating systems. A . my
`is the unit of work in a system. Such a system consists of a'collecfi‘ag
`of concurrently executing processes, some of which are opemfingM_
`processes (those that execute system code) and the rest of which are use;
`processes (those that execute user code). These chapters cover methods for
`process scheduling, interprocess communication, process synchronization,
`and deadlock handling. Also included under this topic is a discussion of
`threads.
`
`
`
`
`
`
`0 Memory management. Chapters 8 and 9 deal with main memory man—
`agement during the execution of a process. To improve both the utilization
`of the CPU and the speed of its response to its users, the computer must
`keep several processes in memory. There are many different memory-
`management schemes, reflecting various approaches to memory man-
`agement, and the effectiveness of a particular algorithm depends on the
`situation.
`
`
`
`|PR2020-01288
`
`Sony EX1053 Page 6
`
`IPR2020-01288
`Sony EX1053 Page 6
`
`

`

`Preface
`
`ix
`
`0 Storage management. Chapters 10 through 13 describe how the file system,
`mass storage, and 1/0 are handled in a modern computer system. The
`file system provides the mechanism for on-line storage of and access to
`both data and programs residing on the disks. These chapters describe
`the classic internal algorithms and structures of storage management.
`They provide a firm practical understanding of the algorithms used—
`the properties, advantages, and disadvantages. Since the [/0 devices that
`attach to a computer vary widely, the operating system needs to provide
`a wide range of functionality to applications to allow them to control all
`aspects of the devices. We discuss system I/O in depth, including I/O
`system design, interfaces, and internal system structures and functions.
`in many ways, [/0 devices are also the slowest major components of
`the computer. Because they are a performance bottleneck, performance
`issues are examined. Matters related to secondary and tertiary storage are
`explained as well.
`
`0 Protection and security. Chapters 14 and 15 discuss the processes in an
`operating system that must be protected from one another's activities.
`For the purposes of protection and security, we use mechanisms that
`ensure that only processes that have gained proper authorization from
`the operating system can operate on the files, memory, CPU, and other
`resources. Protection is a mechanism for controlling the access of programs,
`processes, or users to the resources defined by a computer system. This
`mechanism must provide a means of specifying the controls to be imposed,
`as well as a means of enforcement. Security protects the information stored
`in the system (both data and code),’as well as the physical resources of
`the computer system, from unauthorized access, malicious destruction or
`alteration, and accidental introduction of inconsistency.
`
`0 Distributed systems. Chapters 16 through 18 deal with a collection of
`processors that do not share memory or a clock—a distributed system. By
`providing the user with access to the various resources that it maintains, a
`distributed system can improve computation speed and data availability
`and reliability. Such a system also provides the user with a distributed file
`system, which is a file-service system whose users, servers, and storage
`devices are dispersed among the sites of a distributed system. A distributed
`system must provide various mechanisms for process synchronization and
`communication and for dealing with the deadlock problem and a variety
`of failures that are not encountered in a centralized system.
`
`0 Special-purpose systems. Chapters 19 and 20 deal with systems used for
`specific purposes, including real-time systems and multimedia systems.
`These systems have specific requirements that differ from those of the
`general—purpose systems that are the focus of the remainder of the text.
`Real-time systems may require not only that computed results be “correct”
`but also that the results be produced within a specified deadline period.
`Multimedia systems require quality-of-service guarantees ensuring that
`the multimedia data are delivered to clients within a specific time frame.
`
`0 Case studies. Chapters 21 through 23 in the book, and Appendices A
`through C on the website, integrate the concepts described in this book by
`describing real operating systems. These systems include Linux, Windows
`
`|PR2020-01288
`
`Sony EX1053 Page 7
`
`IPR2020-01288
`Sony EX1053 Page 7
`
`

`

`.A\
`
`
`
`.-23-._—“n'..:1
`
`:1
`
`Preface
`
`XP, FreeBSD, Mach, and Windows 2000. We chose Linux and FreeBSD
`because UNIX—at one time—was almost small enough to understand
`yet was not a “toy“ operating system. Most of its internal algorithms were
`selected for simplicity, rather than for speed or sophistication. Both Linux
`and FreeBSl) are readily available to computer-science departments, so
`many students have access to these systems. We chose Windows XP and
`Windows 2000 because they provide an opportunity for us to study a
`modern operating system with a design and implementation drastically
`different from those of UNIX. Chapter 23 briefly describes a few other
`influential operating systems.
`
`Operating-System Environments
`
`This book uses examples of many real-world operating systems to illustrate
`fundamental operating-system concepts. However, particular attention is paid
`to the Microsoft family of operating systems (including Windows NT, Windows
`2000, and Windows XP) and various versions of UNIX (including Solaris, BSD,
`and Mac OS x). We also provide a significant amount of coverage of the Linux
`operating system reflecting the most recent version of the kernel—Version 2.6
`—at the time this book was written.
`
`The text also provides several example programs written in C and
`Java. These programs are intended to run in the following programming
`environments:
`
`0 Windows systems. The primary programming environment for Wmdows
`systems is the Win32 API (application programming interface), which pro-
`vides a comprehensive set of functions for managing processes, threads,
`memory, and peripheral devices. We provide several C programs illustrat-
`ing the use of the Win32 API. Example programs were tested on systems
`running Windows 2000 and Mndows Xt’.
`
`'
`
`0 POSIX. t’OStX (which stands for Portable Operating System Interface) repre-
`sents a set of standards implemented primarily for UNIX-based operating
`systems. Although Windows XP and Windows 2000 systems can also run
`certain I’OSIX programs, our coverage of POStX focuses primarily on UNIX
`and Linux systems. POSIX-compliant systems must implement the POSDC
`core standard (POSIX.1)—Linux, Solaris, and Mac OS X are examples of
`POSlx-compliant systems. POSIX also defines several extensions to the
`standards, including real-time extensions (POStxlb) and an extension for
`a threads library (POSIX1.c, better known as Pthreads). We provide several
`programming examples written in C illustrating the POSIX base API, as well
`as Pthreads and the extensions for real-time programming. These example
`programs were tested on Debian Linux 2.4 and 2.6 systems, Mac OS X, and
`Solaris 9 using the gcc 3.3 compiler.
`
`‘ Java. java is a widely used programming language with a rich API and
`built-in language support for thread cr1_-1tion 111d management. java
`programs run on any operating sysle m.511,1,,111rti11 1Jav11 virtual machine
`(or JVM) We illustrate various ope runny sy1'lt 111 and networking concepts
`with several Java programs tested 113111,: the |.1vn I At
`|VM.
`
`
`
`|PR2020-01288
`
`Sony EX1053 Page 8
`
`IPR2020-01288
`Sony EX1053 Page 8
`
`

`

`Preface
`
`xi
`
`We have chosen these three programming environments because it is our
`opinion that they best represent the two most popular models of operating
`systems: Windows and UNIX / Linux, along with the widely used Java environ-
`ment. Most programming examples are written in C, and we expect readers to
`be comfortable with this language; readers familiar with both the C and Java
`languages should easily understand most programs provided in this text.
`In some instances—such as thread creation—we illustrate a specific
`concept using all
`three programming environments, allowing the reader
`to contrast the three different libraries as they address the same task.
`In
`other situations, we may use just one of the APIs to demonstrate a concept.
`For example, we illustrate shared memory using just the POSIX AP]; socket
`programming in TCP/IP is highlighted using the Java AP].
`
`The Seventh Edition
`
`As we wrote this seventh edition of Operating System Concepts, we were guided
`by the many comments and suggestions we received from readers of our
`previous editions, as well as by our own observations about the rapidly
`changing fields of operating systems and networking. We have rewritten the
`material in most of the chapters by bringing older material up to date and
`removing material that was no longer of interest or relevance.
`We have made substantive revisions and organizational changes in many of
`the chapters. Most importantly, we have completely reorganized the overview
`material in Chapters 1 and 2 and have added two new chapters on special-
`purpose systems (real-time embedded systems and multimedia systems).
`Because protection and security have become more prevalent in operating
`systems, we now cover these topics earlier in the text. Moreover, we have
`substantially updated and expanded the coverage of security.
`Below, we provide a brief outline of the major changes to the various
`chapters:
`
`0 Chapter 1, Introduction, has been totally revised. In previous editions, the
`chapter gave a historical view of the development of operating systems.
`The new chapter provides a grand tour of the major operating-system
`components, along with basic coverage of computer-system organization.
`
`is a revised version of old
`0 Chapter 2, Operating-System Structures,
`Chapter 3, with many additions, including enhanced discussions of system
`calls and operating-system structure. It also provides significantly updated
`coverage of virtual machines.
`
`0 Chapter 3, Processes, is the old Chapter 4. It includes new coverage of how
`processes are represented in Linux and illustrates process creation using
`both the POSIX and Win32 APls. Coverage of shared memory is enhanced
`with a program illustrating the shared-memory APl available for POSlX
`systems.
`
`0 Chapter 4, Threads, is the old Chapter 5. The chapter presents an enhanced
`discussion of thread libraries, including the POSIX, Win32 API, and Java
`thread libraries. It also provides updated coverage of threading in Linux.
`
`|PR2020-01288
`
`Sony EX1053 Page 9
`
`IPR2020-01288
`Sony EX1053 Page 9
`
`

`

`"\
`
`i
`
`xii
`
`Preface
`
`Chapter 5, CPU Scheduling, is the old Chapter 6. The chapter offers a
`significantly updated discussion of scheduling issues for multiprocessor
`systems, including processor affinity and load-balancing algorithms. It
`also features a new section on thread scheduling, including Pthreads, and
`updated coverage of table-driven scheduling in Solaris. The section on
`Linux scheduling has been revised to cover the scheduler used in the 2.6
`kernel.
`
`is the old Chapter 7. We have
`Chapter 6, Process Synchronization,
`removed the coverage of two-process solutions and now discuss only
`Peterson’s solution, as the two-process algorithms are not guaranteed to
`work on modern processors. The chapter also includes new sections on
`synchronization in the Linux kernel and in the Pthreads API.
`
`is the old Chapter 8. New coverage includes
`Chapter 7, Deadlocks,
`a program example illustrating deadlock in a multithreaded Pthread
`program.
`
`
`
`Chapter 8, Main Memory, is the old Chapter 9. The chapter no longer
`covers overlays. In addition, the coverage of segmentation has seen sig- .
`nificant modification, including an enhanced discussion of segmentation
`in Pentium systems and a discussion of how Linux is designed for sucli
`segmented systems.
`
`Chapter 9, Virtual Memory, is the old Chapter 10. The Chapter fea .
`expanded coverage of motivating virtual memory as well as covera'
`
`
`
`
`
`shared memory (via memory-mapped files) using the Win32 API.»
`details of memory management hardware have been modernized. A.
`section on allocating memory within the kernel discusses the bu’va
`algorithm and the slab allocator.
`'
`
`
`
`
`Chapter 10, File-System Interface, is the old Chapter 11. It hé___
`updated and an example of Windows XP ACLs has been added,
`
`
`Chapter 11, File-System Implementation, is the old Chapter 12. A ‘
`include a full description of the WAFL file system and inclusion. )
`ZFS file system.
`a ' I ‘ '0
`Chapter 12, Mass-Storage Structure, is the old Chapter if' ‘
`coverage of modern storage arrays, including new RAID t7
`features such as thin provisioning.
`-
`Chapter 13, I10 Systems, is the old Chapter 13 updated with coverag '
`new material.
`‘
`
`
`
`2
`
`Chapter 14, Protection, is the old Chapter 18 updated with coverage of the
`principle of least privilege.
`
`Chapter 15, Security, is the old Chapter 19. The chapter has undergone
`a major overhaul, with all sections updated. A full example of a buffer-
`overflow exploit is included, and coverage of threats, encryption, and
`security tools has been expanded.
`
`Chapters 16 through 18 are the old Chapters 15 through [7, updated with
`coverage of new material.
`
`
`
`‘
`
`|PR2020-01288
`
`Sony EX1053 Page 10
`
`IPR2020-01288
`Sony EX1053 Page 10
`
`

`

`Preface
`
`xiii
`
`0 Chapter 19, Real-Time Systems, is a new chapter focusing on real—time
`and embedded computing systems, which have requirements different
`from those of many traditional systems. The chapter provides an overview
`of real-time computer systems and describes how operating systems must
`be constructed to meet the stringent timing deadlines of these systems.
`
`0 Chapter 20, Multimedia Systems, is a new chapter detailing developments
`in the relatively new area of multimedia systems. Multimedia data differ
`from conventional data in that multimedia data—such as frames of video
`
`——must be delivered (streamed) according to certain time restrictions. The
`chapter explores how these requirements affect the design of operating
`svstems.
`
`0 Chapter 21, The Linux System, is the old Chapter 20, updated to reflect
`changes in the 2.6 kernel—the most recent kernel at the time this text was
`written.
`
`0 Chapter 22, XP, has been updated.
`
`0 Chapter 22, Influential Operating Systems, has been updated.
`
`The old Chapter 21 (Windows 2000) has been turned into Appendix C. As in
`the previous edition, the appendices are provided online.
`
`Programming Exercises and Projects
`
`To emphasize the concepts presented in the text, we have added several
`programming exercises and projects that use the POSIX and Win32 APlsas well
`as Java. We have added over 15 new programming exercises that emphasize
`processes, threads, shared memory, process synchronization, and networking.
`In addition, we have added several programming projects which are more
`involved than standard programming exercises. These projects include adding
`a system call to the Linux kernel, creating a UNIX shell using the f orkO system
`call, a multithreaded matrix application, and the producer-consumer problem
`using shared memory.
`
`Teaching Supplements and Web Page
`
`The web page for the book contains such material as a set of slides to accompany
`the book, model course syllabi, all C and Java source code, and up-to—date
`errata. The web page also contains the book’s three case-study appendices and
`the Distributed Communication appendix. The URL is:
`
`http:/ /www.os-book.com
`
`New to this edition is a print supplement called the Student Solutions
`Manual. Included are problems and exercises with solutions not found in
`the text that should help students master the concepts presented. You can
`purchase a print copy of this supplement at Wiley’s website by going to
`http:/ /www.wiley.com/college/silberschatz and choosing the Student Solu—
`tions Manual link.
`
`|PR2020-01288
`
`Sony EX1053 Page 11
`
`IPR2020-01288
`Sony EX1053 Page 11
`
`

`

`A‘s
`
`xiv
`
`Preface
`
`To obtain restricted supplements, such as the solution guide to the exercises
`in the text, contact your local John Wiley & Sons sales representative. Note that
`these supplements are avaialble only to faculty who use this text. You can
`find your representative at the “Find a Rep?" web page: http://www.jsw~
`edcv.wiley.com / college / findarep.
`
`Mailing List
`
`We have switched to the mailman system for communication among the users
`of Operating System Concepts. If you wish to use this facility, please visit the
`following URL and follow the instructions there to subscribe:
`
`httpz/ / mailman.cs.yale.edu / mailman/ listinfo/ os-book-list
`
`The mailman mailing-list system provides many benefits, such as an archive
`of postings, as well as several subscription options, including digest and Web»
`only. To send messages to the list, send e-mail to:
`
`os-book-list@cs.yale.edu
`
`Depending on the message, we will either reply to you personally or fo‘rw, i
`the message to everyone on the mailing list. The list is moderated, so you. ‘
`receive no inappropriate mail
`..
`Students who are using this book as a text for class should not use the T?
`to ask for answers to the exercises. They will not be provided.
`
`
`
`
`
`
`
`Suggestions
`
`We have attempted to clean up every error in this new Edi:
`
`__
`identify.
`'
`If you would like to suggest improvements Or to €611
`we would also be glad to hear from you. Please sendf:c_ ,
`os-book@cs.yale.edu.
`‘
`
`Acknowledgmentse.
`
`1-3 “00‘
`
`t
`
`,
`
`Ibis book is derived from the previous editions, the first three of which were
`coauthored by James Peterson. Others who helped us with previous editions
`include Hamid Arabnia, Rida Bazzi, Randy Bentson, David Black, Joseph
`Boykin, Jeff Brumf‘ield, Gael Buckley, Roy Campbell, P. C. Capon, John Car-
`penter, Gil Garrick, Thomas Casavant, Ajoy Kumar Datta, Joe Deck, Sudarshan
`K. Dhall, Thomas Doeppner, Caleb Drake, M. Racsit Eskicioglu, Hans Flack,
`Robert Fowler, G. Scott Graham, Richard Guy, Max Hailperin, Rebecca Hart-
`man, Wayne Hathaway, Christopher Haynes, Bruce Hillyer, Mark Holliday,
`Ahmed Kamel, Richard Kieburtz, Carol Kroll, Morty Kwestel, Thomas LeBlanc,
`John Leggett, Jerrold Leichter, Ted Leung, Gary Lippman, Carolyn Miller,
`
`
`
`|PR2020-01288
`
`Sony EX1053 Page 12
`
`IPR2020-01288
`Sony EX1053 Page 12
`
`

`

`Preface
`
`xv
`
`Michael Molloy, Yoichi Muraoka, Jim M. Ng, Banu Ozden, Ed Posnak, Boris
`Putanec, Charles Qualline, John Quarterman, Mike Reiter, Gustavo Rodriguez—
`Rivera, Carolyn J. C. Schauble, Thomas P. Skinner, Yannis Smaragdakis, Jesse
`St. Laurent, John Stankovic, Adam Stauffer, Steven Stepanek, Hal Stern, Louis
`Stevens, Pete Thomas, David Umbaugh, Steve Vinoski, Tommy Wagner, Larry
`L. Wear, John Werth, James M. Westall, J. S. Weston, and Yang Xiang
`Parts of Chapter 12 were derived from a paper by Hillyer and Silberschatz
`[1996]. Parts of Chapter 17 were derived from a paper by Levy and Silberschatx
`[1990]. Chapter 2] was derived from an unpublished manuscript by Stephen
`Tweedie. Chapter 22 was derived from an unpublished manuscript by Dave
`Probert, Cliff Martin, and Avi Silberschatz. Appendix C was derived from
`an unpublished manuscript by Cliff Martin. Cliff Martin also helped with
`updating the UNIX appendix to cover FreeBSl). Mike Shapiro, Bryan Cantrill,
`and Jim Mauro answered several Solaris—related questions. Josh Dees and Rob
`Reynolds contributed coverage of Microsoft’s .NET. The project for designing
`and enhancing the UNIX shell interface was contributed by John Trono of St.
`Michael's College in Winooski, Vermont.
`This edition has many new exercises and accompanying solutions, which
`were supplied by Arvind Krishnamurthy.
`We thank the following people who reviewed this version of the book: Bart
`Childs, Don Heller, Dean Hougen Michael Huangs, Morty Kewstel, Euripides
`Montagne, and John Sterling.
`Our Acquisitions Editors, Bill Zobrist and Paul Crockett, provided expert
`guidance as we prepared this edition. They were assisted by Simon Durkin,
`who managed many details of this project smoothly. The Senior Production
`Editor was Ken Santor. The cover illustrator was Susan Cyr, and the cover
`designer was Madelyn Lesure. Beverly Peavler copy-edited the manuscript.
`The freelance proofreader was Katrina Avery; the freelance indexer was Rose-
`mary Simpson. Marilyn Tumamian helped generate figures and presentation
`slides.
`
`Finally, we would like to add some personal notes. Avi is starting a new
`chapter in his life, returning to academia and partnering with Valerie. This
`combination has given him the peace of mind to focus on the writing of this text.
`Pete would like to thank his family, friends, and coworkers for their support
`and understanding during the project. Greg would like to acknowledge the
`continued interest and support from his family. However, he would like to
`single out his friend Peter Ormsby who—no matter how busy his life seems
`to be—always first asks, “How’s the writing coming along?"
`
`Abraham Silberschatz, New Haven, CT, 2004
`Peter Baer Galvin, Burlington, MA, 2004
`Greg Gagne, Salt Lake City, UT, 2004
`
`|PR2020-01288
`
`Sony EX1053 Page 13
`
`IPR2020-01288
`Sony EX1053 Page 13
`
`

`

`
`
`Confe/Ifs
`
`PART ONE I OVERVIEW
`
`Chapter 1
`
`Introduction
`
`3
`1.1 What Operating Systems Do
`1.2 Computer—System Organization 6
`1.3 Computer—System Architecture
`12
`1.4 Operating-System Structure
`15
`1.5 Operating-System Operations
`17
`1.6 Process Management
`20
`1.7 Memory Management
`21
`1.8 Storage Management
`22
`
`26
`
`1.9 Protection and Security
`1.10 Distributed Systems
`28
`1.11 Special—Purpose Systems
`1.12 Computing Environments
`1.13 Summary 34
`Exercises
`36
`
`29
`31
`
`Bibliographical Notes
`
`38
`
`Chapter 2 Operating-System Structures
`
`39
`2.] Operating-System Services
`2.2 User Operating-System Interface
`2.3 System Calls
`43
`2.4 Types of System Calls
`2.5 System Programs
`55
`2.6 Operating-System Design and
`Implementation 56
`
`47
`
`2.7 Operating-System Structure
`2.8 Virtual Machines
`64
`
`58
`
`41
`
`2.9 Operating-System Generation 70
`2.10 System Boot
`71
`2.11 Summary 72
`Exercises
`73
`
`Bibliographical Notes
`
`78
`
`PART TWO I PROCESS MANAGEMENT
`
`Chapter 3 Processes
`
`81
`3.1 Process Concept
`3.2 ProcessScheduling 85
`90
`3.3 Operations on Processes
`3.4 lnterprocess Communication 96
`3.5 Examples ofll’C Systems
`102
`
`3.6 Communication in Client—
`
`Server Systems
`3.7 Summary
`115
`Exercises
`116
`
`108
`
`Bibliographical Notes
`
`125
`
`xvii
`
`|PR2020-01288
`
`Sony EX1053 Page 14
`
`IPR2020-01288
`Sony EX1053 Page 14
`
`

`

`
`
`
`
`xviii
`
`Contents
`
`Chapter 4 Threads
`
`4.1 Overview 127
`4.2 Multithreading Models
`4.3 Thread Libraries
`131
`
`129
`
`4.5 Operating-System Examples
`4.6 Summary 146
`Exercises
`146
`
`143
`
`4.4 Threading Issues
`
`138
`
`Bibliographical Notes
`
`151
`
`Chapter 5 CPU Scheduling
`
`153
`5.1 Basic Concepts
`157
`5.2 Scheduling Criteria
`158
`5.3 Scheduling Algorithms
`5.4 Multiple-Processor Scheduling 169
`5.5 Thread Scheduling 172
`
`5.6 Operating System Examples
`5.7 Algorithm Evaluation 181
`5.8 Summary 185
`Exercises
`186
`Bibliographical Notes
`
`173
`
`i
`
`189
`
`Chapter 6 Process Synchronization
`
`.
`
`191
`6.1 Background
`6.2 The Critical-Section Problem 193
`6.3 Peterson’s Solution
`195
`
`6.4 Synchronization Hardware
`6.5 Semaphores
`200
`6.6 Classic Problems of
`Synchronization 204
`
`197
`
`Chapter 7 Deadlocks
`
`245
`7.1 System Model
`7.2 Deadlock Characterization 247
`7.3 Methods for Handling Deadlocks
`7.4 Deadlock Prevention 253
`75 Deadlock Avoidance 256
`
`7.52
`
`
`
`I”
`6.7 Monitors 209
`6.8 Synchronization Examples 217
`6.9 Atomic Transactions 22 'l
`
`
`
`6.10 Summary 230
`,‘_
`Exercises
`231
`Bibliographical Notes 242
`
`
`
`7.6 DmdlockDetecli "
`7.7 Recovery From I -.,-,
`7.8 Summary 267'
`Exercises
`268"-,
`Bibliographical
`
`1
`
`
`
`PART THREE I MEMORY MANAGEMENT
`
`Chapter 8 Main Memory
`
`8.1 Background 275
`8.2 Swapping 282
`8.3 Contiguous Memory Allocation 284
`8.4 Paging 288
`8.5 Structure of the Page Table
`
`297
`
`302
`8.6 Segmentation
`8.7 Example: The Intel Pentium 305
`8.8 Summary
`309
`Exercises
`310
`Bibliographical Notes
`
`312
`
`A
`
`|PR2020-01288
`
`Sony EX1053 Page 15
`
`IPR2020-01288
`Sony EX1053 Page 15
`
`

`

`Contents
`
`xix
`
`Chapter 9 Virtual Memory
`
`315
`9.1 Background
`319
`9.2 Demand Paging
`325
`9.3 Copy-on-Write
`327
`9.4 Page Replacement
`9.5 Allocation of Frames
`340
`
`9.6 Thrashing 343
`9.7 Memory-Mapped Files
`
`348
`
`9.8 Allocating Kernel Memory 353
`9.9 Other Considerations
`357
`9.10 Operating-System Examples
`9.1] Summary 365
`Exercises
`366
`
`363
`
`Bibliographical Notes
`
`370
`
`PART FOUR I STORAGE MANAGEMENT
`
`Chapter 10 File-System Interface
`
`373
`10.1 File Concept
`382
`10.2 Access Methods
`10.3 Directory Structure
`385
`10.4 File-System Mounting 395
`10.5 FileSharing 397
`
`10.6 Protection 402
`10.7 Summary 407
`Exercises
`408
`Bibliographical Notes
`
`409
`
`Chapter 11 File-System Implementation
`
`411
`11.1 File-System Structure
`11.2 File-System Implementation 413
`11.3 Directory Implementation 419
`11.4 Allocation Methods
`421
`429
`11.5 Free'Space Management
`11.6 Efficiency and Performance
`431
`11.7 Recovery
`435
`
`437
`
`11.8 Log-Structured File Systems
`11.9 NFS 438
`11.10 Example: The WAFL File System 444
`11.11 Summary 446
`Exercises
`447
`Bibliographical Notes
`
`449
`
`Chapter 12 Mass-Storage Structure
`
`121 Overview of Mass-Storage
`Structure
`45]
`454
`12.2 Disk Structure
`12.3 Disk Attachment
`455
`12.4 Disk Scheduling 456
`12.5 Disk Management
`462
`12.6 Swap-Space Management 466
`
`Chapter 13 U0 Systems
`13.1 Overview 495
`13-2 [/0 Hardware
`
`496
`
`13.3 Application I/O Interface
`13.4 Kernel I/O Subsystem 511
`13.5 Transforming I/O Requests to
`Hardware Operations
`518
`
`505
`
`468
`12.7 RAID Structure
`12.8 Stable-Storage Implementation 477
`12.9 Tertiary-Storage Structure
`478
`12.10 Summary 488
`Exercises
`489
`Bibliographical Notes
`
`493
`
`13.6 STREAMS 520
`13.7 Performance
`522
`
`13.8 Summary 525
`Exercises
`526
`Bibliographical Notes
`
`527
`
`|PR2020-01288
`
`Sony EX1053 Page 16
`
`IPR2020-01288
`Sony EX1053 Page 16
`
`

`

`.13
`
`XX
`
`Contents
`
`PART FIVE I PROTECTION AND SECURITY
`
`Chapter 14 Protection
`14.1 Goals of Protection
`531
`
`14.2 Principles of Protection 532
`14.3 Domain of Protection 533
`14.4 Access Matrix 538
`14.5 Implementation of Access Matrix 542
`14.6 Access Control
`545
`
`546
`14.7 Revocation of Access Rights
`547
`14.8 Capability-Based Systems
`14.9 Language-Based Protection 550
`14.10 Summary 555
`Exercises
`556
`Bibliographical Notes
`
`557
`
`Chapter 15 Security
`
`1