rE e
`
`rr S
`
`oiST BESLS on4
`
`IPR2020-01288
`Sony EX1053 Page 1
`
`IPR2020-01288
`Sony EX1053 Page 1
`
`

`

`Operating
`System Concepis
`
`Seventh Edition
`
`ABRAHAM SILBERSCHATZ
`Yale University
`
`PETER BAER GALVIN
`Corporate Technologies, Inc.
`
`GREG GAGNE
`Westminster College
`
`WILEY
`
`JOHN WILEY & SONS. INC
`
`——F
`
`IPR2020-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 wasset in Palatino by the author using LaTeX and printed and bound by
`Von Hoffmann, Inc. The cover was printed by Von Hoffmann,Inc.
`
`This bookisprinted on acid free paper.
`
`«
`
`Copyright © 2005 John Wiley & Sons, Inc. All rights reserved.
`
`Nopart 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, withouteither the prior written permission of the Publisher, or
`authorization through paymentof 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,JohnWiley&asei11 Rivera5, Hoboken,NJ07030,
`ToorderbooksorforcustomerserviceDiscscallbielrueILEY(225-5945).
`(201) 748-6011, fax (201) 748-6008.
`‘ ‘}c
`
`
`
`
`ISBN 0-471-69466-5 _|
`
`IPR2020-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 mychildren, Gwen Owen and Maddie
`
`Peter Baer Galvin
`
`In memory of Uncle Sonny,
`Robert Jon Heileman 1933 — 2004
`
`Greg Gagne
`
`err
`
`6 Cae
`
`¥
`
`setting tat
`ulapesrete vr a gene
`erat
`embee esa‘teeha minnie
`noet pops
`eeeahveOperst
`oeonenothaptel¥..
`¢oeol +te
`ro:
`
`a B —|
`
`IPR2020-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
`prevalentin 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.
`Wewrotethis book as a text for an introductory course in operating systems
`at the junior or senior undergraduatelevelor at the first-year graduate level.
`We hopethatpractitionerswill also findit 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 canstill
`understand the algorithms without a thorough knowledgeof these languages.
`Concepts are presented using intuitive descriptions. Importanttheoretical
`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
`questionto 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-DOS,
`WindowsNT, Windows2000, and WindowsXP; DEC VMS and TOPS-20; IBM OS/2;
`and Apple Mac OS x.
`In this text, when werefer to WindowsXPas an example operating system,
`weare implying both Windows XP and Windows2000. If a feature exists in
`WindowsXP thatis not available in Windows2000, wewill state this explicitly.
`
`vii
`
`IPR2020-01 288
`Sony EX1053 Page 5
`
`IPR2020-01288
`Sony EX1053 Page 5
`
`

`

`or
`
`Viii
`
`Preface
`
`If a feature exists in Windows 2000 but not in WindowsXP, then wewill refer
`specifically to Windows2000.
`
`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 reviewersof the text, as well as comments submitted by readers ofearlier
`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 pagefor this text, we provide several sample syllabi
`that suggest various approaches for using the text in both introductory and
`advanced operating systemscourses. 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 readercan select a different ordering of chapters (or subsections of
`chapters).
`
`Content of This Book
`
`The text is organized in eight majorparts:
`e Overview. Chapters 1 and 2 explain what operating systems are, what
`they do, and howtheyare designed and constructed. They discuss whatthe
`commonfeatures of an operating system are, what an operating system
`
`doesfor the user, and whatit does for the computer-system operator. The
`presentation is motivational and explanatory in nature. We have avoideda
`
`discussion of how things are done internally in these chapters. Therefore,
`theyare suitable for individual readersor for students in lower-level
`classes"
`
`who want to learn whatan operating system is without getting into
`details of the internal algorithms.
`
`e Process management. Chapters 3 through 7 describe the process concept
`and concurrency as the heart of modern operating systems. A p oceess
`
`is the unit of work in a system. Such a system consists of a collection
`
`of concurrently executing processes, some of which are operati
`e m
`
`processes (those that execute system code) and the rest of which are user
`processes(those that execute user code). These chapters cover methodsfor
`process scheduling, interprocess communication, process synchronization,
`and deadlock handling. Also included underthis topic is a discussion of
`threads.
`
`¢ Memory management. Chapters 8 and 9 deal with main memory man-
`agement during the execution of a process. To improveboth theutilization
`of the CPU andthe speedofits response toits 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. afl
`
`IPR2020-01288
`Sony EX1053 Page 6
`
`IPR2020-01288
`Sony EX1053 Page 6
`
`

`

`Preface
`
`ix
`
`e Storage management. Chapters 10 through 13 describe how thefile system,
`mass storage, and I/O are handled in a modern computer system. The
`file system provides the mechanism for on-line storage of and access to
`both data and programsresiding 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 I/O devices that
`attach to a computer vary widely, the operating system needs to provide
`a wide rangeof functionality to applications to allow them to controlall
`aspects of the devices. We discuss system I/O in depth, including 1/O
`system design, interfaces, and internal system structures and functions.
`In many ways, I/O devices are also the slowest major components of
`the computer. Because they are a performance bottleneck, performance
`issues are examined. Matters related to secondary andtertiary storage are
`explained as well.
`
`e 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 mustprovide a means ofspecifying the controls to be imposed,
`as well as a meansof 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.
`
`* 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 accessto the various resourcesthatit 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, whichis a file-service system whose users, servers, and storage
`devices are dispersed amongthesites of a distributed system. A distributed
`system mustprovide various mechanismsfor process synchronization and
`communication and for dealing with the deadlock problem and a variety
`of failures that are not encountered in a centralized system.
`© 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 systemsthat are the focus of the remainderofthe text.
`Real-time systems may require not only that computedresults be “correct”
`butalso 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.
`® 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
`
`IPR2020-01 288
`Sony EX1053 Page 7
`
`IPR2020-01288
`Sony EX1053 Page 7
`
`

`

`
`
` -|
`
`x
`
`Preface
`
`A
`
`XP, FreeBSD, Mach, and Windows 2000. We chose Linux and FreeBsp
`because UNIX—at one time—was almost small enough to understand
`yet was not a “toy” operating system. Mostofits internal algorithms were
`selected for simplicity, rather than for speed or sophistication. Both Linux
`and FreeBSDare readily available to computer-science departments, so
`manystudents haveaccess to these systems. We chose WindowsXP and
`Windows2000 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.
`
`=eae=>-—@ASLS
`
`Operating-System Environments
`
`This book uses examples of many real-world operating systemsto illustrate
`fundamental operating-system concepts. However, particularattentionis paid
`to the Microsoft family of operating systems (including Windows NT, Windows
`2000, and WindowsXP) and various versions of UNIX (including Solaris, BSD,
`and MacOS X). Wealso provide a significant amountof coverage of the Linux
`operating system reflecting the most recent version of the kernel— Version 2.6
`—at the time this book waswritten.
`The text also provides several example programs written in C and
`Java. These programsare intended to run in the following programming
`environments:
`
`|
`
`¢ Windowssystems. The primary programming environment for Windows
`systemsis the Win32 API (application programming interface), which pro-
`vides a comprehensiveset 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 Windows2000 and WindowsxP.
`® POSIX. POSIX (which stands for Portable Operating System Interface) repre-
`sents a set of standards implemented primarily for UNIX-based operating
`systems. Although WindowsXP and Windows2000 systemscan also run
`certain POSIX programs, our coverage of POSIX focuses primarily on UNIX
`and Linux systems. POSIX-compliant systems must implement the POSIX
`core standard (POSIX.1)—Linux, Solaris, and Mac OS X are examples of
`POSIxX-compliant systems. POSIX also defines several extensions to the
`standards,including real-time extensions (POSIX1.b) and an extension for
`a threadslibrary (POSIX1.c, better known as Pthreads). We provideseveral
`programming examples written in C illustrating the POSIX base API, as well
`as Pthreads andthe extensions forreal-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 creation and management. Java
`programs run on any operating system supportiny, a Java virtual machine
`(or JVM). Weillustrate various operating system and networking concepts
`with several Java programstested using the Java 1.4 JVM.
`
`
`IPR2020-01 288
`Sony EX1053 Page 8
`
`IPR2020-01288
`Sony EX1053 Page 8
`
`

`

`Preface
`
`xi
`
`We have chosenthese three programming environments because it is our
`opinion that they best represent the two most popular models of operating
`systems: Windowsand 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 programsprovidedinthis text.
`In some instances—such as thread creation—weillustrate a specific
`concept using all
`three programming environments, allowing the reader
`to contrast the three different libraries as they address the sametask. In
`othersituations, we may use just one of the APIs to demonstrate a concept.
`For example, weillustrate shared memory using just the POSIX API; socket
`programmingin TCP/IP is highlighted using the Java API.
`
`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 longerofinterest or relevance.
`We have madesubstantive revisions and organizational changesin manyof
`the chapters. Most importantly, we have completely reorganized the overview
`material in Chapters 1 and 2 and have added two newchapters on special-
`purpose systems(real-time embedded systems and multimedia systems).
`Because protection and security have become more prevalent in operating
`systems, we now coverthese topics earlier in the text. Moreover, we have
`substantially updated and expandedthe coverageof security.
`Below, we provide a brief outline of the major changes to the various
`chapters:
`
`® Chapter 1, Introduction, has beentotally revised. In previouseditions, 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.
`¢ Chapter 2, Operating-System Structures,
`is a revised version of old
`Chapter 3, with manyadditions,including enhanceddiscussions of system
`calls and operating-system structure. It also providessignificantly updated
`coverage ofvirtual machines.
`* Chapter3, Processes,is the old Chapter4. It includes new coverage of how
`processes are represented in Linux andillustrates process creation using
`both the POSIX and Win32 APIs. Coverage of shared memory is enhanced
`with a program illustrating the shared-memory API available for POSIX
`systems.
`* Chapter 4, Threads,is the old Chapter 5, The chapter presents an enhanced
`discussion of thread libraries, including the POSIX, Win32 API, and Java
`threadlibraries. It also provides updated coverageof threading in Linux.
`
`IPR2020-01 288
`Sony EX1053 Page 9
`
`IPR2020-01288
`Sony EX1053 Page 9
`
`

`

`xii
`
`Preface
`
`Chapter 5, CPU Scheduling, is the old Chapter 6. The chapteroffers a
`significantly updated discussion of scheduling issues for multiprocessor
`systems, including processor affinity and load-balancing algorithms.It
`also features a newsectionon 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 modernprocessors. The chapter also includes new sections on
`synchronization in the Linux kernel and in the Pthreads API.
`Chapter 7, Deadlocks,
`is the old Chapter 8. New coverage includes
`
`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 systemsand a discussion of how Linux is designed for such
`segmented systems.
`
`Chapter 9, Virtual Memory, is the old Chapter 10. The chapter featu es
`expandes:-€coverage of motivating virtual memory as well as coverage
`
`shared memory (via memory-mapped files) using the Win32 API.
`
`details of memory management hardware have been modernized. A
`
`ZFS file system.
`
`Chapter 12, Mass-Storage Structure, is the old Chapter 14,yD
`coverage of modern storage arrays, including new RAIDtec
`features such as thin provisioning.
`
`Chapter 13, I/O Systems,is the old Chapter 13 updated with cOveraee of
`
`algorithm andthe slab allocator.
`Chapter 10, File-System Interface, is the old Chapter 11. It has”
`updated and an example of Windows XP ACLs has been added.
`
`
`new material.
`
`Chapter 14, Protection,is the old Chapter 18 updated with coverageof the
`principle of leastprivilege.
`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 17, updated with
`coverage of new material.
`
`
`
`mend
`IPR2020-01 288
`Sony EX1053 Page 10
`
`IPR2020-01288
`Sony EX1053 Page 10
`
`

`

`Preface
`
`xiii
`
`e Chapter 19, Real-Time Systems, is a new chapter focusing on real-time
`and embedded computing systems, which have requirements different
`from those of manytraditional systems. The chapter provides an overview
`of real-time computer systems and describes howoperating systems must
`be constructed to meet thestringent timing deadlines of these systems.
`
`e Chapter 20, Multimedia Systems,is a newchapter detailing developments
`in the relatively newarea of multimedia systems. Multimedia data differ
`from conventional data in that multimedia data—such as framesof video
`—mustbe delivered (streamed) according to certain timerestrictions. The
`chapter explores howthese requirements affect the design of operating
`systems.
`
`e Chapter 21, The Linux System,is the old Chapter 20, updatedto reflect
`changesin the 2.6 kernel—the mostrecent kernel at the time this text was
`written.
`
`e Chapter22, XP, has been updated.
`
`e 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 APIsas well
`as Java. We have added over 15 new programmingexercises that emphasize
`processes, threads, shared memory, process synchronization, and networking.
`In addition, we have added several programming projects which are more
`involved than standard programmingexercises. These projects include adding
`a system call to the Linux kernel, creating a UNIX shell using the fork () system
`call, a multithreaded matrix application, and the producer-consumer problem
`using shared memory.
`
`Teaching Supplements and Web Page
`
`The web pagefor the book contains such material asa set of slides to accompany
`the book, model course syllabi, all C and Java source code, and up-to-date
`errata. The web pagealso containsthe book’s three case-study appendices and
`the Distributed Communication appendix. The URLis:
`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.
`
`IPR2020-01288
`Sony EX1053 Page 11
`
`IPR2020-01288
`Sony EX1053 Page 11
`
`

`

`ay
`
`Preface
`
`To obtainrestricted supplements, suchasthe solution guideto the exercises
`in the text, contact your local John Wiley & Sonssales representative. Notethat
`these supplements are avaialble only to faculty who use this text. You can
`find your representative at the “Find a Rep?” web page: http://wwwjsw-
`edcv.wiley.com/college/findarep.
`
`Mailing List
`
`Wehave switched to the mailman system for communication amongthe users
`of Operating System Concepts. If you wish to use this facility, please visit the
`following URL andfollow the instructions there to subscribe:
`http:/ /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 messagesto the list, send e-mail to:
`os-book-list@cs.yale.edu
`Depending on the message, we will either reply to you personally or forward
`the message to everyone on the mailinglist. The list is moderated, so you will
`receive no inappropriatemail.
`d
`Students whoare using this bookasa text for class should notuse thelist
`to ask for answersto the exercises. They will not be provided.
`
`
`
`
`
`
`
`Suggestions
`
`We have attempted to clean up every error in this new edit iC
`aetie
`,
`If you would like to suggest improvementsor to con rib
`we would also be glad to hear from you. Please sendc ;
`os-book@cs.yale.edu.
`
`Acknowledgments
`
`i hie
`
`:
`
`r
`
`This bookis derived from the previouseditions, 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 Brumfield, Gael Buckley, Roy Campbell, P. C. Capon, John Car-
`penter, Gil Carrick, 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,
`
`
`
`IPR2020-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, ThomasP. 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 Silberschatz
`[1990]. Chapter 21 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 FreeBSD. Mike Shapiro, Bryan Cantril,
`and Jim Mauro answeredseveral 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 TronoofSt.
`Michael’s College in Winooski, Vermont.
`This edition has many new exercises and accompanying solutions, which
`were supplied by Arvind Krishnamurthy.
`Wethank the following people whoreviewed 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 manydetails 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 Turnamian helped generate figures and presentation
`slides.
`Finally, we would like to add somepersonal notes. Avi is starting a new
`chapter in his life, returning to academia and partnering with Valerie. This
`combination hasgiven him the peace of mindto 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 busyhis life seems
`to be—alwaysfirst 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
`
`IPR2020-01 288
`Sony EX1053 Page 13
`
`IPR2020-01288
`Sony EX1053 Page 13
`
`

`

`
`
`Contents
`
`PART ONE #@ OVERVIEW
`
`Chapter1 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
`
`Chapter2 Operating-System Structures
`2.7 Operating-System Structure
`2.1 Operating-System Services
`39
`2.8 Virtual Machines
`64
`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
`
`41
`
`47
`
`58
`
`2.9 Operating-System Generation 70
`2.10 System Boot
`71
`2.11 Summary 72
`Exercises
`73
`Bibliographical Notes
`
`78
`
`PARTTWO & PROCESS MANAGEMENT
`
`Chapter3 Processes
`3.1 Process Concept
`81
`3.2 Process Scheduling 85
`90
`3.3 Operations on Processes
`34 InterprocessCommunication 96
`3.5 Examples of IPC Systems
`102
`
`3.6 Communication in Client-
`
`Server Systems
`3.7 Summary
`115
`Exercises
`116
`
`108
`
`Bibliographical Notes
`
`125
`
`xvii
`
`IPR2020-01288
`Sony EX1053 Page 14
`
`IPR2020-01288
`Sony EX1053 Page 14
`
`

`

`
`
`xviii
`
`Contents
`
`Chapter4 Threads
`4.1 Overview 127
`4.2 Multithreading Models
`4.3 Thread Libraries
`131
`4.4 Threading Issues
`138
`
`129
`
`4.5 Operating-System Examples
`4.6 Summary 146
`Exercises
`146
`Bibliographical Notes
`
`151
`
`143
`
`Chapter5 CPU Scheduling
`5.1 Basic Concepts
`153
`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
`
`|
`
`189
`
`
`
`Chapter6 Process Synchronization
`ts
`6.1 Background
`191
`6.7 Monitors 209
`6.2 The Critical-Section Problem 193
`6.8 Synchronization Examples 217.
`6.3 Peterson’s Solution
`195
`6.9 Atomic Transactions 222
`6.4 Synchronization Hardware
`6.10 Summary 230
`~
`6.5 Semaphores 200
`Exercises
`231
`6.6 Classic Problems of
`Bibliographical Notes 242
`Synchronization 204
`
`197
`
`Chapter 7 Deadlocks
`7.1 System Model
`245
`7.2 Deadlock Characterization 247
`7.3 Methods for Handling Deadlocks 252
`7.4 Deadlock Prevention 253
`7.5 Deadlock Avoidance 256
`
`7.6 Deadlock Detectior
`7.7 Recovery From Dea
`7.8 Summary 267
`Exercises 268 —
`Bibliographical Not
`
`
`
`PART THREE_® MEMORY MANAGEMENT
`
`Chapter8 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: TheIntel Pentium 305
`8.8 Summary
`309
`Exercises
`310
`Bibliographical Notes
`
`312
`
`
`
`ad
`IPR2020-01 288
`Sony EX1053 Page 15
`
`IPR2020-01288
`Sony EX1053 Page 15
`
`

`

`Contents
`
`xix
`
`Chapter9 Virtual Memory
`9.1 Background
`315
`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-MappedFiles 348
`
`9.8 Allocating Kernel Memory 353
`9.9 Other Considerations
`357
`9.10 Operating-System Examples
`9.11 Summary 365
`Exercises
`366
`
`363
`
`Bibliographical Notes
`
`370
`
`PART FOUR HM STORAGE MANAGEMENT
`
`Chapter 10 File-System Interface
`10.6 Protection 402
`10.1 File Concept
`373
`10.2 Access Methods
`
`382
`
`10.7 Summary 407
`Exercises
`408
`
`385
`10.3. Directory Structure
`10.4 File-System Mounting 395
`10.5 FileSharing 397
`
`Bibliographical Notes
`
`409
`
`Chapter 11 File-System Implementation
`11.8 Log-Structured File Systems
`11.1 File-System Structure
`411
`11.9 NFS 438
`11.2 File-System Implementation 413
`11.3 Directory Implementation 419
`11.4 Allocation Methods
`421
`
`437
`
`11.10 Example: The WAFLFile System 444
`11.11 Summary 446
`Exercises
`447
`
`429
`11.5 Free-Space Management
`11.6 Efficiency and Performance
`431
`11.7 Recovery
`435
`
`Bibliographical Notes
`
`449
`
`Chapter 12 Mass-Storage Structure
`12.7 RAID Structure
`468
`12.1 Overview of Mass-Storage
`Structure
`451
`12.8 Stable-Storage Implementation 477
`454
`12.2 Disk Structure
`12.9 Tertiary-Storage Structure
`478
`12.3 Disk Attachment
`455
`12.10 Summary 488
`Exercises
`489
`12.4 Disk Scheduling 456
`12.5 Disk Management 462
`Bibliographical Notes
`12.6 Swap-Space Management 466
`
`493
`
`I/O Systems
`Chapter 13
`13.1 Overview 495
`496
`13.2 I/O Hardware
`13.3 Application I/O Interface
`13.4 KernelI/O Subsystem 511
`13.5 Transforming I/O Requests to
`Hardware Operations
`518
`
`505
`
`13.6 STREAMS 520
`13.7 Performance
`522
`13.8 Summary 525
`Exercises
`526
`Bibliographical Notes
`
`527
`
`IPR2020-01 288
`Sony EX1053 Page 16
`
`IPR2020-01288
`Sony EX1053 Page 16
`
`

`

`ah
`
`XX
`
`Contents
`
`PART FIVE @® PROTECTION AND SECURITY
`
`Chapter 14 Protection
`14.1 Goals of Protection
`531
`14.2 Principles of Protection 532
`14.3 Domainof 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
`
`Chapter15 Security
`15.1 The Security Problem 559
`15.2 Program Threats
`563
`571
`15.3 System and Network Threats
`15.4 Cryptographyas a Security Tool
`576
`15.5 User Authentication 587
`15.6 Implementing Security Defenses
`15.7 Firewalling to Protect Systems and
`Networks
`599
`
`592
`
`15.8 Computer-Security
`Classifications
`600
`15.9 An Example: Windows XP 602
`15.10 Summary 604
`Exercises
`604
`Bibliographical Notes
`
`606
`
`
`
`
`
`
`PART SIX HM DISTRIBUTED SYSTEMS
`ia
`-r
`
`
`
`Chapter 16 Distributed System Structures
`16.1 Motivation 611
`16.7 Robustness
`631
`16.2 Types of Distributed Operating
`16.8 Design Issues 633
`Systems
`613
`16.9 An Example: Networking 636
`16.3 Network Structure 617
`16.10 Summary 637
`16.4 Network Topology 620
`Exercises
`638
`16.5 Communication Structure
`Bibliographical Notes
`16.6