Operating System Concepts Essentials, 2nd Edition

OPERATINGSYSTEMCONCEPTSlsssEaitenSecond EditionAbraham SilberschatzPeter Baer GalvinGreg Gagne

OperatingSystem ConceptsEssential sSecond Edition

This page is intentionally left blank

OperatingSystem ConceptsEssential sSecond EditionABRAHAM SILBERSCHATZYale UniversityPETER BAER GALVINCorporate Technologies, Inc.GREG GAGNEWestminster College

Vice President & Executive PublisherExecutive EditorExecutive Marketing ManagerAssociate Production ManagerCover designerDon FowleyBeth Lang GolubChristopher RuelJoyce PohMadelyn LesureThis book was set in Palatino by the author using LaTeX and printed and bound by Courier Kendallville.The cover was printed by Courier Kendallville. This book is printed on acid free paper.Founded in 1807, John Wiley & Sons, Inc. has been a valued source of knowledge and understanding for morethan 200 years, helping people around the world meet their needs and fulfill their aspirations. Our company isbuilt on a foundation of principles that include responsibility to the communities we serve and where we live andwork. In 2008, we launched a Corporate Citizenship Initiative, a global effort to address the environmental, social,economic, and ethical challenges we face in our business. Among the issues we are addressing are carbon impact,paper specifications and procurement, ethical conduct within our business and among our vendors, and communityand charitable support. For more information, please visit our website: www.wiley.com/go/citizenship.Copyright 2014, 2011 John Wiley & Sons, Inc. All rights reserved. No part of this publication may bereproduced, 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 1976United States Copyright Act, without either the prior written permission of the Publisher, or authorizationthrough payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc. 222 Rosewood Drive,Danvers, MA 01923, website www.copyright.com. Requests to the Publisher for permission should be addressedto the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030-5774, (201)748-6011,fax (201)748-6008, website http://www.wiley.com/go/permissions.Evaluation copies are provided to qualified academics and professionals for review purposes only, for use in theircourses during the next academic year. These copies are licensed and may not be sold or transferred to a thirdparty. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructionsand a free of charge return mailing label are available at www.wiley.com/go/returnlabel. If you have chosen toadopt this textbook for use in your course, please accept this book as your complimentary desk copy. Outside ofthe United States, please contact your local sales representative.Printed in the United States of America10 9 8 7 6 5 4 3 2 1

To my children, Lemor, Sivan, and Aaronand my NicoletteAvi SilberschatzTo my wife, Carla,and my children, Gwen, Owen, and MaddiePeter Baer GalvinTo my wife, Pat,and our sons, Tom and JayGreg Gagne

This page is intentionally left blank

PrefaceOperating systems are an essential part of any computer system. Similarly,a course on operating systems is an essential part of any computer scienceeducation. This field is undergoing rapid change, as computers are nowprevalent in virtually every arena of day-to-day life —from embedded devicesin automobiles through the most sophisticated planning tools for governmentsand multinational firms. Yet the fundamental concepts remain fairly clear, andit is on these that we base this book.We wrote this book as a text for an introductory course in operating systemsat the junior or senior undergraduate level or at the first-year graduate level. Wehope that practitioners will also find it useful. It provides a clear description ofthe concepts that underlie operating systems. As prerequisites, we assume thatthe reader is familiar with basic data structures, computer organization, anda high-level language, such as C or Java. The hardware topics required for anunderstanding of operating systems are covered in Chapter 1. In that chapter,we also include an overview of the fundamental data structures that areprevalent in most operating systems. For code examples, we use predominantlyC, with some Java, but the reader can still understand the algorithms withouta thorough knowledge of these languages.Concepts are presented using intuitive descriptions. Important theoreticalresults are covered, but formal proofs are largely omitted. The bibliographicalnotes at the end of each chapter contain pointers to research papers in whichresults were first presented and proved, as well as references to recent materialfor further reading. In place of proofs, figures and examples are used to suggestwhy we should expect the result in question to be true.The fundamental concepts and algorithms covered in the book are oftenbased on those used in both commercial and open-source operating systems.Our aim is to present these concepts and algorithms in a general setting thatis not tied to one particular operating system. However, we present a largenumber of examples that pertain to the most popular and the most innovativeoperating systems, including Linux, Microsoft Windows, Apple Mac OS X, andSolaris. We also include examples of both Android and iOS, currently the twodominant mobile operating systems.The organization of the text reflects our many years of teaching courses onoperating systems, as well as curriculum guidelines published by the IEEEvii

viiiPrefaceComputing Society and the Association for Computing Machinery (ACM).Consideration was also given to the feedback provided by the reviewers ofthe text, along with the many comments and suggestions we received fromreaders of our previous editions and from our current and former students.Content of This BookThe text is organized in six major parts: Overview. Chapters 1 and 2 explain what operating systems are, whatthey do, and how they are designed and constructed. These chaptersdiscuss what the common features of an operating system are and what anoperating system does for the user. We include coverage of both traditionalPC and server operating systems, as well as operating systems for mobiledevices. The presentation is motivational and explanatory in nature. Wehave avoided a discussion of how things are done internally in thesechapters. Therefore, they are suitable for individual readers or for studentsin lower-level classes who want to learn what an operating system iswithout getting into the details of the internal algorithms. Process management. Chapters 3 through 6 describe the process conceptand concurrency as the heart of modern operating systems. A processis the unit of work in a system. Such a system consists of a collectionof concurrently executing processes, some of which are operating-systemprocesses (those that execute system code) and the rest of which are userprocesses (those that execute user code). These chapters cover methods forprocess scheduling, interprocess communication, process synchronization,and deadlock handling. Also included is a discussion of threads, as wellas an examination of issues related to multicore systems and parallelprogramming. Memory management. Chapters 7 and 8 deal with the management ofmain memory during the execution of a process. To improve both theutilization of the CPU and the speed of its response to its users, thecomputer must keep several processes in memory. There are many differentmemory-management schemes, reflecting various approaches to memorymanagement, and the effectiveness of a particular algorithm depends onthe situation. Storage management. Chapters 9 through 12 describe how mass storage,the file system, and I/O are handled in a modern computer system. Thefile system provides the mechanism for on-line storage of and accessto both data and programs. We describe the classic internal algorithmsand structures of storage management and provide a firm practicalunderstanding of the algorithms used —their properties, advantages, anddisadvantages. Since the I/O devices that attach to a computer vary widely,the operating system needs to provide a wide range of functionality toapplications to allow them to control all aspects of these devices. Wediscuss system I/O in depth, including I/O system design, interfaces, and

Prefaceixinternal system structures and functions. In many ways, I/O devices arethe slowest major components of the computer. Because they represent aperformance bottleneck, we also examine performance issues associatedwith I/O devices. Protection and security. Chapters 13 and 14 discuss the mechanismsnecessary for the protection and security of computer systems. Theprocesses in an operating system must be protected from one another’sactivities, and to provide such protection, we must ensure that onlyprocesses that have gained proper authorization from the operating systemcan operate on the files, memory, CPU, and other resources of the system.Protection is a mechanism for controlling the access of programs, processes,or users to computer-system resources. This mechanism must provide ameans of specifying the controls to be imposed, as well as a means ofenforcement. Security protects the integrity of the information stored inthe system (both data and code), as well as the physical resources of thesystem, from unauthorized access, malicious destruction or alteration, andaccidental introduction of inconsistency. Case studies. Chapter 15 in the text, along with Appendices A and B(which are available on http://www.os-book.com), present detailed casestudies of real operating systems, including Linux, FreeBSD, and Mach.Coverage of Linux is presented throughout this text; however, the casestudies provide much more detail.Operating System EssentialsWe have based Operating System Essentials on the Ninth Edition of OperatingSystem Concepts, published in 2012. Our intention behind developing thisEssentials edition is to provide readers with a textbook that focuses on thecore concepts that underlie contemporary operating systems. By focusing oncore concepts, we believe students are able to grasp the essential features of amodern operating system more easily and more quickly.To achieve this, Operating System Essentials omits the following coveragefrom the Ninth Edition of Operating System Concepts:1. We removed Chapter 7—Deadlocks—and instead offer a detailedoverview of deadlocks in Chapter 6.2. We removed Chapter 16—Virtual Machines.3. We removed Chapter 17—Distributed Systems.4. We removed Chapter 19—Windows 7.5. We removed Chapter 20—Influential Operating Systems.For those that wish to pursue a more comprehensive study of operatingsystems, we refer you to the Ninth Edition of Operating System Concepts, andin the following we describe the changes relevant to that edition.