ONLINE ACCESS Thank you for purchasing a new copy of Modern Operating Systems, Fourth Edition, Global Edition. Your textbook includes twelve months of prepaid access to the book’s Companion Website. This prepaid subscription provides you with full access to the following student support areas: • Online Chapters • Lab Experiments • Online Exercises • Simulation Exercises Use a coin to scratch off the coating and reveal your student access code. Do not use a knife or other sharp object as it may damage the code.
To access the Modern Operating Systems, Fourth Edition, Global Edition, Companion Website for the first time, you will need to register online using a computer with an Internet connection and a web browser. The process takes just a couple of minutes and only needs to be completed once. Go to www. Click on your book.
Click on Companion Website. Click on the Register button. On the registration page, enter your student access code* found beneath the scratch- off panel. Do not type the dashes.
You can use lower- or uppercase. Follow the on-screen instructions. If you need help at any time during the online registration process, simply click the Need Help? icon. Once your personal Login Name and Password are confirmed, you can begin using the Modern Operating Systems Companion Website! To log in after you have registered: You only need to register for this Companion Website once.
After that, you can log in any time at www.com/Tanenbaum by providing your Login Name and Password when prompted. *Important: The access code can only be used once. This subscription is valid for twelve months upon activation and is not transferable. If this access code has already been revealed, it may no longer be valid.
If this is the case, you can purchase a subscription by going to www.com/Tanenbaum and following the on-screen instructions.indd 1 7/14/14 3:41 PM MODERN OPERATING SYSTEMS FOURTH EDITION GLOBAL EDITION Trademarks AMD, the AMD logo, and combinations thereof are trademarks of Advanced Micro Devices, Inc. Android and Google Web Search are trademarks of Google Inc. Apple and Apple Macintosh are registered trademarkes of Apple Inc. ASM, DESPOOL, DDT, LINK-80, MAC, MP/M, PL/1-80 and SID are trademarks of Digital Research.
BlackBerry®, RIM®, Research In Motion® and related trademarks, names and logos are the property of Research In Motion Limited and are registered and/or used in the U. and coun- tries around the world. Blu-ray Disc™ is a trademark owned by Blu-ray Disc Association. CD Compact Disk is a trademark of Phillips.
CDC 6600 is a trademark of Control Data Corporation. CP/M and CP/NET are registered trademarks of Digital Research. DEC and PDP are registered trademarks of Digital Equipment Corporation. eCosCentric is the owner of the eCos Trademark and eCos Logo, in the US and other countries.
The marks were acquired from the Free Software Foundation on 26th February 2007. The Trademark and Logo were previously owned by Red Hat. The GNOME logo and GNOME name are registered trademarks or trademarks of GNOME Foundation in the United States or other countries. Firefox® and Firefox® OS are registered trademarks of the Mozilla Foundation.
Fortran is a trademark of IBM Corp. FreeBSD is a registered trademark of the FreeBSD Foundation. GE 645 is a trademark of General Electric Corporation. Intel Core is a trademark of Intel Corporation in the U.
and/or other countries. Java is a trademark of Sun Microsystems, Inc., and refers to Sun’s Java programming language. Linux® is the registered trademark of Linus Torvalds in the U. and other countries.
MS-DOS and Windows are registered trademarks of Microsoft Corporation in the United States and/or other countries. TI Silent 700 is a trademark of Texas Instruments Incorporated. UNIX is a registered trademark of The Open Group. Zilog and Z80 are registered trademarks of Zilog, Inc.
MODERN OPERATING SYSTEMS FOURTH EDITION GLOBAL EDITION ANDREW S. TANENBAUM HERBERT BOS Vrije Universiteit Amsterdam, The Netherlands Boston Columbus Indianapolis New York San Francisco Upper Saddle River Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montréal Toronto Delhi Mexico City São Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo Vice President and Editorial Director, ECS: Marcia Horton Executive Editor: Tracy Johnson Program Management Team Lead: Scott Disanno Program Manager: Carole Snyder Project Manager: Camille Trentacoste Operations Specialist: Linda Sager Head of Learning Asset Acquisition, Global Edition: Laura Dent Assistant Acquisitions Editor, Global Edition: Aditee Agarwal Project Editor, Global Edition: Amrita Naskar Media Producer, Global Edition: Vikram Kumar Senior Manufacturing Controller, Production, Global Edition: Trudy Kimber Cover art: Pavel K/Shutterstock Media Project Manager: Renata Butera Pearson Education Limited Edinburgh Gate Harlow Essex CM20 2JE England and Associated Companies throughout the world Visit us on the World Wide Web at: www.com © Pearson Education Limited 2015 The rights of Andrew S. Tanenbaum and Herbert Bos to be identified as the authors of this work have been as- serted by them in accordance with the Copyright, Designs and Patents Act 1988. Authorized adaptation from the United States edition, entitled Modern Operating Systems, 4th edition, ISBN 978-0-13-359162-0, by Andrew S.
Tanenbaum and Herbert Bos, published by Pearson Education © 2015. 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 or otherwise, without either the prior written permission of the publisher or a license permitting restricted copying in the United Kingdom issued by the Copyright Licensing Agency Ltd, Saffron House, 6–10 Kirby Street, London EC 1N 8TS. All trademarks used herein are the property of their respective owners.The use of any trademark in this text does not vest in the author or publisher any trademark ownership rights in such trademarks, nor does the use of such trademarks imply any affiliation with or endorsement of this book by such owners.
ISBN 10: 1-292-06142-1 ISBN 13: 978-1-292-06142-9 British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library 10 9 8 7 6 5 4 3 2 1 14 13 12 11 10 Printed and bound by Courier Westford in The United States of America To Suzanne, Barbara, Daniel, Aron, Nathan, Marvin, Matilde, and Olivia. The list keeps growing. (AST) To Marieke, Duko, Jip, and Spot. Fearsome Jedi, all.
(HB) CONTENTS PREFACE xxiii 1 INTRODUCTION 1 1.1 WHAT IS AN OPERATING SYSTEM? 3 1.1 The Operating System as an Extended Machine 4 1.2 The Operating System as a Resource Manager 5 1.2 HISTORY OF OPERATING SYSTEMS 6 1.1 The First Generation (1945–55): Vacuum Tubes 7 1.2 The Second Generation (1955–65): Transistors and Batch Systems 8 1.3 The Third Generation (1965–1980): ICs and Multiprogramming 9 1.4 The Fourth Generation (1980–Present): Personal Computers 14 1.5 The Fifth Generation (1990–Present): Mobile Computers 19 1.3 COMPUTER HARDWARE REVIEW 20 1.6 Booting the Computer 34 vii viii CONTENTS 1.4 THE OPERATING SYSTEM ZOO 35 1.1 Mainframe Operating Systems 35 1.2 Server Operating Systems 35 1.3 Multiprocessor Operating Systems 36 1.4 Personal Computer Operating Systems 36 1.5 Handheld Computer Operating Systems 36 1.6 Embedded Operating Systems 36 1.7 Sensor-Node Operating Systems 37 1.8 Real-Time Operating Systems 37 1.9 Smart Card Operating Systems 38 1.5 OPERATING SYSTEM CONCEPTS 38 1.7 Ontogeny Recapitulates Phylogeny 46 1.1 System Calls for Process Management 53 1.2 System Calls for File Management 56 1.3 System Calls for Directory Management 57 1.4 Miscellaneous System Calls 59 1.5 The Windows Win32 API 60 1.7 OPERATING SYSTEM STRUCTURE 62 1.4 Client-Server Model 68 1.8 THE WORLD ACCORDING TO C 73 1.3 Large Programming Projects 75 1.4 The Model of Run Time 76 CONTENTS ix 1.9 RESEARCH ON OPERATING SYSTEMS 77 1.10 OUTLINE OF THE REST OF THIS BOOK 78 1.12 SUMMARY 80 2 PROCESSES AND THREADS 85 2.1 The Process Model 86 2.6 Implementation of Processes 94 2.2 The Classical Thread Model 102 2.4 Implementing Threads in User Space 108 2.5 Implementing Threads in the Kernel 111 2.8 Pop-Up Threads 114 2.9 Making Single-Threaded Code Multithreaded 115 2.3 Mutual Exclusion with Busy Waiting 121 2.4 Sleep and Wakeup 127 2.10 Avoiding Locks: Read-Copy-Update 148 2.1 Introduction to Scheduling 149 2.2 Scheduling in Batch Systems 156 2.3 Scheduling in Interactive Systems 158 2.4 Scheduling in Real-Time Systems 164 2.5 Policy Versus Mechanism 165 2.5 CLASSICAL IPC PROBLEMS 167 2.1 The Dining Philosophers Problem 167 2.2 The Readers and Writers Problem 169 2.6 RESEARCH ON PROCESSES AND THREADS 172 2.7 SUMMARY 173 3 MEMORY MANAGEMENT 181 3.1 NO MEMORY ABSTRACTION 182 3.2 A MEMORY ABSTRACTION: ADDRESS SPACES 185 3.1 The Notion of an Address Space 185 3.3 Managing Free Memory 190 3.3 Speeding Up Paging 201 3.4 Page Tables for Large Memories 205 CONTENTS xi 3.4 PAGE REPLACEMENT ALGORITHMS 209 3.1 The Optimal Page Replacement Algorithm 209 3.2 The Not Recently Used Page Replacement Algorithm 210 3.3 The First-In, First-Out (FIFO) Page Replacement Algorithm 211 3.4 The Second-Chance Page Replacement Algorithm 211 3.5 The Clock Page Replacement Algorithm 212 3.6 The Least Recently Used (LRU) Page Replacement Algorithm 213 3.7 Simulating LRU in Software 214 3.8 The Working Set Page Replacement Algorithm 215 3.9 The WSClock Page Replacement Algorithm 219 3.10 Summary of Page Replacement Algorithms 221 3.5 DESIGN ISSUES FOR PAGING SYSTEMS 222 3.1 Local versus Global Allocation Policies 222 3.4 Separate Instruction and Data Spaces 227 3.9 Virtual Memory Interface 232 3.1 Operating System Involvement with Paging 233 3.2 Page Fault Handling 234 3.4 Locking Pages in Memory 236 3.6 Separation of Policy and Mechanism 239 3.1 Implementation of Pure Segmentation 243 3.2 Segmentation with Paging: MULTICS 243 3.3 Segmentation with Paging: The Intel x86 247 3.8 RESEARCH ON MEMORY MANAGEMENT 252 3.9 SUMMARY 253 xii CONTENTS 4 FILE SYSTEMS 263 4.7 An Example Program Using File-System Calls 273 4.1 Single-Level Directory Systems 276 4.2 Hierarchical Directory Systems 276 4.3 FILE-SYSTEM IMPLEMENTATION 281 4.1 File-System Layout 281 4.5 Log-Structured File Systems 293 4.6 Journaling File Systems 294 4.7 Virtual File Systems 296 4.4 FILE-SYSTEM MANAGEMENT AND OPTIMIZATION 299 4.1 Disk-Space Management 299 4.2 File-System Backups 306 4.3 File-System Consistency 312 4.4 File-System Performance 314 4.5 EXAMPLE FILE SYSTEMS 320 4.1 The MS-DOS File System 320 4.2 The UNIX V7 File System 323 4.3 CD-ROM File Systems 325 4.6 RESEARCH ON FILE SYSTEMS 331 4.7 SUMMARY 332 CONTENTS xiii 5 INPUT/OUTPUT 337 5.1 PRINCIPLES OF I/O HARDWARE 337 5.4 Direct Memory Access 344 5.2 PRINCIPLES OF I/O SOFTWARE 351 5.1 Goals of the I/O Software 351 5.3 Device-Independent I/O Software 361 5.4 User-Space I/O Software 367 5.3 Disk Arm Scheduling Algorithms 379 5.6 USER INTERFACES: KEYBOARD, MOUSE, MONITOR 394 5.1 Hardware Issues 418 xiv CONTENTS 5.2 Operating System Issues 419 5.3 Application Program Issues 425 5.9 RESEARCH ON INPUT/OUTPUT 426 5.1 Preemptable and Nonpreemptable Resources 436 6.2 INTRODUCTION TO DEADLOCKS 438 6.1 Conditions for Resource Deadlocks 439 6.3 THE OSTRICH ALGORITHM 443 6.4 DEADLOCK DETECTION AND RECOVERY 443 6.1 Deadlock Detection with One Resource of Each Type 444 6.2 Deadlock Detection with Multiple Resources of Each Type 446 6.3 Recovery from Deadlock 448 6.2 Safe and Unsafe States 452 6.3 The Banker’s Algorithm for a Single Resource 453 6.4 The Banker’s Algorithm for Multiple Resources 454 6.1 Attacking the Mutual-Exclusion Condition 456 6.2 Attacking the Hold-and-Wait Condition 456 6.3 Attacking the No-Preemption Condition 457 6.4 Attacking the Circular Wait Condition 457 6.1 Two-Phase Locking 458 6.2 Communication Deadlocks 459 CONTENTS xv 6.8 RESEARCH ON DEADLOCKS 464 6.9 SUMMARY 464 7 VIRTUALIZATION AND THE CLOUD 471 7.2 REQUIREMENTS FOR VIRTUALIZATION 474 7.3 TYPE 1 AND TYPE 2 HYPERVISORS 477 7.4 TECHNIQUES FOR EFFICIENT VIRTUALIZATION 478 7.1 Virtualizing the Unvirtualizable 479 7.2 The Cost of Virtualization 482 7.5 ARE HYPERVISORS MICROKERNELS DONE RIGHT? 483 7.9 VIRTUAL MACHINES ON MULTICORE CPUS 494 7.1 Clouds as a Service 496 7.2 Virtual Machine Migration 496 7.12 CASE STUDY: VMWARE 498 7.1 The Early History of VMware 498 7.2 VMware Workstation 499 xvi CONTENTS 7.3 Challenges in Bringing Virtualization to the x86 500 7.4 VMware Workstation: Solution Overview 502 7.5 The Evolution of VMware Workstation 511 7.