Operating System Concepts Essentials 2nd Edition

214477

OPERATINGSYSTEMCONCEPTS

Abraham Silberschatz

Peter Baer Galvin

Greg GagneSecond Edition

Cover Design Credit: Madelyn Lesure

Cover Images Credit: © Susan Cyr

Did you know this book is available as a

Wiley E-Text

E-textbooks offer the complete content of the printed textbook on the device of your preference - computer, iPad, tablet, or smartphone - giving you the freedom to read or study anytime, anywhere.

For Instructors:

Wiley E-Texts allow you to save your

teaching notes within the digital version of the printed textbook. Now you can have one digital library to take to and from the classroom for all of the courses you teach. For Students:

Wiley E-Texts offer a more affordable

alternative to traditional print. You can access course materials and content anytime, anywhere through a user experience that makes learning rewarding.

How Can Students Purchase E-textbooks?

Via your campus bookstore:

Wiley E-Text: Powered by VitalSource

ISBN 978-1-118-84392-5Directly from online retailers:

Including Wiley.com, Amazon,

Barnes & Noble, and CourseSmart

For information about this title, including additional ordering options and accompanying resources, visit:

www.wiley.com/college/silberschatz or contact your Wiley representative. ✓ Search content ✓ Take notes ✓ Highlight key materials ✓ Organize all your work in one place

Save At Least

50% Off Printed Textbook Costs!

Wiley'sDigital

Advantagewww.wiley.com/college/silberschatz

OPERATING SYSTEM CONCEPTS

Silberschatz Galvin Gagne

Second

Edition

9781118804926

90000

ISBN 978-1-118-804

92-6

Operating

System Concepts

Essentials

Second Edition

This page is intentionally left blank

ABRAHAM SILBERSCHATZ

PETER BAER GALVIN

GREG GAGNE

Operating

System Concepts

Essentials

Second Edition

Vice President & Executive Publisher Don Fowley

Executive Editor Beth Lang Golub

Executive Marketing Manager Christopher Ruel

Associate Production Manager Joyce Poh

Cover designer Madelyn Lesure

This 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 a cid free paper.

Founded in 1807, John Wiley & Sons, Inc. has been a valued source of knowledge and understanding for more

than 200 years, helping people around the world meet their needs and ful"ll their aspirations. Our com

pany is

built on a foundation of principles that include responsibility to the communities we serve and where we live and

work. 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 speci"cations and procurement, ethical conduct within our business and among our vendors, and co

mmunity

and 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 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 1

08 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, Inc. 222 Rosewood Drive,

Danvers, MA 01923, website www.copyright.com. Requests to the Publisher for permission should be addressed

to 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 quali"ed academics and professionals for review purposes only, for use in their

courses during the next academic year. These copies are licensed and may not be sold or transferred to a third

party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructions

and a free of charge return mailing label are available at www.wiley.com/go/returnlabel. If you have chosen to

adopt this textbook for use in your course, please accept this book as y our complimentary desk copy. Outside of the United States, please contact your local sales representative.

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

To my childe,Lemo,Siva,adAao

admyNicolee

Avi Silbeschaz

To my wife, Cala,

admychilde, Gwe,Owe,ad Maddie

PeeBaeGalvi

To my wife, Pa,

adousos, Tom adJay

Geg Gage

This page is intentionally left blank

Preface

concepts vii viiiPreface

Content of This Book

Overview

¥Process management

process concurrently

¥Memory management

¥Storage management

Prefaceix

¥Protection and security

¥Case studies

http://www.os-book.com

Operating System Essentials

Operating System Essentials Operating

System Concepts

Essentials

Operating System Essentials

Operating System Concepts

1. 2. 3. 4. 5.

Operating System Concepts

xPreface As we wrote this Second Edition ofOperating System Concepts Essentials,we were guided by the recent growth in the following fundamental areas that affect operating systems:

1.Multicore systems

2.Mobile computing

We have integrated relevant coverage throughout this new edition To empha- size these topics. Additionally, we have rewritten material in almost every chapter by bringing older material up to date and removing material that is no longer interesting or relevant. We have also made substantial organizational changes. For example, we have eliminated the chapter on real-time systems and instead have integrated appropriate coverage of these systems throughout the text. We have reordered the chapters on storage management and have moved up the presentation of process synchronization so that it appears before process scheduling. Most of these organizational changes are based on our experiences while teaching courses on operating systems. Below, we provide a brief outline of the major changes to the various chapters: ¥Chapter 1, Introduction,includes updated coverage of multiprocessor and multicore systems, as well as a new section on kernel data structures. Additionally, the coverage of computing environments now includes mobile systems and cloud computing. We also have incorporated an overview of real-time systems. ¥Chapter 2, Operating-System Structures,provides new coverage of user interfaces for mobile devices, including discussions of i

OSand Android,

and expanded coverage of Mac

OS Xas a type of hybrid system.

¥Chapter 3, Processes,now includes coverage of multitasking in mobile operatingsystems,supportforthemultiprocessmodelinGoogleÕsChrome web browser, and zombie and orphan processes in UNIX. ¥Chapter 4, Threads,supplies expanded coverage of parallelism and AmdahlÕs law. It also provides a new section on implicit threading, including Open

MPand AppleÕs Grand Central Dispatch.

¥Chapter 5, Process Synchronization(previously Chapter 6), adds a new section on mutex locks as well as coverage of synchronization using Open

MP,aswellasfunctionallanguages.

¥Chapter6,CPUScheduling(previouslyChapter5),containsnewcoverage oftheLinux CFSschedulerandWindowsuser-modescheduling.Coverage of real-time scheduling algorithms has also been integrated into this chapter. ¥Chapter 7, Main Memory,includes new coverage of swapping on mobile systems and Intel 32- and 64-bit architectures. A new section discusses

ARMarchitecture.

Prefacexi

Chapter 8, Virtual Memory,

¥Chapter9,Mass-StorageStructure

¥Chapter 10, File-System Interface

¥Chapter 11, File-System Implementation

¥Chapter12,I/O,

¥Chapter 13, Protection,

¥Chapter 14, Security,

OPERATINGSYSTEMCONCEPTS

Abraham Silberschatz

Peter Baer Galvin

Greg GagneSecond Edition

Cover Design Credit: Madelyn Lesure

Cover Images Credit: © Susan Cyr

Did you know this book is available as a

Wiley E-Text

E-textbooks offer the complete content of the printed textbook on the device of your preference - computer, iPad, tablet, or smartphone - giving you the freedom to read or study anytime, anywhere.

For Instructors:

Wiley E-Texts allow you to save your

teaching notes within the digital version of the printed textbook. Now you can have one digital library to take to and from the classroom for all of the courses you teach. For Students:

Wiley E-Texts offer a more affordable

alternative to traditional print. You can access course materials and content anytime, anywhere through a user experience that makes learning rewarding.

How Can Students Purchase E-textbooks?

Via your campus bookstore:

Wiley E-Text: Powered by VitalSource

ISBN 978-1-118-84392-5Directly from online retailers:

Including Wiley.com, Amazon,

Barnes & Noble, and CourseSmart

For information about this title, including additional ordering options and accompanying resources, visit:

www.wiley.com/college/silberschatz or contact your Wiley representative. ✓ Search content ✓ Take notes ✓ Highlight key materials ✓ Organize all your work in one place

Save At Least

50% Off Printed Textbook Costs!

Wiley'sDigital

Advantagewww.wiley.com/college/silberschatz

OPERATING SYSTEM CONCEPTS

Silberschatz Galvin Gagne

Second

Edition

9781118804926

90000

ISBN 978-1-118-804

92-6

Operating

System Concepts

Essentials

Second Edition

This page is intentionally left blank

ABRAHAM SILBERSCHATZ

PETER BAER GALVIN

GREG GAGNE

Operating

System Concepts

Essentials

Second Edition

Vice President & Executive Publisher Don Fowley

Executive Editor Beth Lang Golub

Executive Marketing Manager Christopher Ruel

Associate Production Manager Joyce Poh

Cover designer Madelyn Lesure

This 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 a cid free paper.

Founded in 1807, John Wiley & Sons, Inc. has been a valued source of knowledge and understanding for more

than 200 years, helping people around the world meet their needs and ful"ll their aspirations. Our com

pany is

built on a foundation of principles that include responsibility to the communities we serve and where we live and

work. 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 speci"cations and procurement, ethical conduct within our business and among our vendors, and co

mmunity

and 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 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 1

08 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, Inc. 222 Rosewood Drive,

Danvers, MA 01923, website www.copyright.com. Requests to the Publisher for permission should be addressed

to 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 quali"ed academics and professionals for review purposes only, for use in their

courses during the next academic year. These copies are licensed and may not be sold or transferred to a third

party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructions

and a free of charge return mailing label are available at www.wiley.com/go/returnlabel. If you have chosen to

adopt this textbook for use in your course, please accept this book as y our complimentary desk copy. Outside of the United States, please contact your local sales representative.

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

To my childe,Lemo,Siva,adAao

admyNicolee

Avi Silbeschaz

To my wife, Cala,

admychilde, Gwe,Owe,ad Maddie

PeeBaeGalvi

To my wife, Pa,

adousos, Tom adJay

Geg Gage

This page is intentionally left blank

Preface

concepts vii viiiPreface

Content of This Book

Overview

¥Process management

process concurrently

¥Memory management

¥Storage management

Prefaceix

¥Protection and security

¥Case studies

http://www.os-book.com

Operating System Essentials

Operating System Essentials Operating

System Concepts

Essentials

Operating System Essentials

Operating System Concepts

1. 2. 3. 4. 5.

Operating System Concepts

xPreface As we wrote this Second Edition ofOperating System Concepts Essentials,we were guided by the recent growth in the following fundamental areas that affect operating systems:

1.Multicore systems

2.Mobile computing

We have integrated relevant coverage throughout this new edition To empha- size these topics. Additionally, we have rewritten material in almost every chapter by bringing older material up to date and removing material that is no longer interesting or relevant. We have also made substantial organizational changes. For example, we have eliminated the chapter on real-time systems and instead have integrated appropriate coverage of these systems throughout the text. We have reordered the chapters on storage management and have moved up the presentation of process synchronization so that it appears before process scheduling. Most of these organizational changes are based on our experiences while teaching courses on operating systems. Below, we provide a brief outline of the major changes to the various chapters: ¥Chapter 1, Introduction,includes updated coverage of multiprocessor and multicore systems, as well as a new section on kernel data structures. Additionally, the coverage of computing environments now includes mobile systems and cloud computing. We also have incorporated an overview of real-time systems. ¥Chapter 2, Operating-System Structures,provides new coverage of user interfaces for mobile devices, including discussions of i

OSand Android,

and expanded coverage of Mac

OS Xas a type of hybrid system.

¥Chapter 3, Processes,now includes coverage of multitasking in mobile operatingsystems,supportforthemultiprocessmodelinGoogleÕsChrome web browser, and zombie and orphan processes in UNIX. ¥Chapter 4, Threads,supplies expanded coverage of parallelism and AmdahlÕs law. It also provides a new section on implicit threading, including Open

MPand AppleÕs Grand Central Dispatch.

¥Chapter 5, Process Synchronization(previously Chapter 6), adds a new section on mutex locks as well as coverage of synchronization using Open

MP,aswellasfunctionallanguages.

¥Chapter6,CPUScheduling(previouslyChapter5),containsnewcoverage oftheLinux CFSschedulerandWindowsuser-modescheduling.Coverage of real-time scheduling algorithms has also been integrated into this chapter. ¥Chapter 7, Main Memory,includes new coverage of swapping on mobile systems and Intel 32- and 64-bit architectures. A new section discusses

ARMarchitecture.

Prefacexi

Chapter 8, Virtual Memory,

¥Chapter9,Mass-StorageStructure

¥Chapter 10, File-System Interface

¥Chapter 11, File-System Implementation

¥Chapter12,I/O,

¥Chapter 13, Protection,

¥Chapter 14, Security,