MODERN O - GitHub Pages

1 MODERNOPERATINGSYSTEMSFOURTHEDITIONT rademarksAMD, the AMD logo, and combinations thereof are trademarks of Advanced Micro Devices, and Google Web Search are trademarks of Google and Apple Macintosh are registered trademarkes of Apple , DESPOOL, DDT, LINK-80, MAC, MP/M, PL/1-80 and SID are trademarks of , RIM , Research In Motion and related trademarks, names and logos are theproperty of Research In Motion Limited and are registered and/or used in the and coun-tries around the Disc is a trademark owned by Blu-ray Disc Compact Disk is a trademark of 6600 is a trademark of Control Data and CP/NET are registered trademarks of Digital and PDP are registered trademarks of Digital Equipment is the owner of the eCos Trademark and eCos Logo, in the US and other countries.

2 Themarks were acquired from the Free Software Foundation on 26th February 2007. The Trademark andLogo were previously owned by Red GNOME logo and GNOME name are registered trademarks or trademarks of GNOME Foundationin the United States or other and Firefox OS are registered trademarks of the Mozilla is a trademark of IBM is a registered trademark of the FreeBSD 645 is a trademark of General Electric Core is a trademark of Intel Corporation in the and/or other is a trademark of Sun Microsystems, Inc., and refers to Sun s Java programming is the registered trademark of Linus Torvalds in the and other and Windows are registered trademarks of Microsoft Corporation in the United States and/orother Silent 700 is a trademark of Texas Instruments is a registered trademark of The Open and Z80 are registered trademarks of Zilog, TANENBAUMHERBERTBOSV rije UniversiteitAmsterdam,TheNetherlandsBost on Columbus Indianapolis New York San Francisco Upper Saddle RiverAmsterdam Cape Town Dubai London Madrid Milan Munich Paris Montr al TorontoDelhi Mexico City S o Paulo Sydney Hong Kong Seoul Singapore Taipei TokyoVice President and Editorial Director, ECS:MarciaHortonExecutive Editor.

3 TracyJohnsonProgram Management Team Lead:ScottDisannoProgram Manager:CaroleSnyderProject Manager:CamilleTrentacosteOperations Specialist:LindaSagerCover Design:BlackHorseDesignsCover art:JasonConsalvoMedia Project Manager:RenataButeraCopyright 2015, 2008 by Pearson Education, Inc., Upper Saddle River, New Jersey, 07458,Pearson Prentice-Hall. All rights reserved. Printed in the United States of America. This publicationis protected by Copyright and permission should be obtained from the publisher prior to anyprohibited reproduction, storage in a retrieval system, or transmission in any form or by anymeans, electronic, mechanical, photocopying, recording, or likewise. For information regardingpermission(s), write to: Rights and Permissions Prentice Hall is a trademark of Pearson Education, is a registered trademark of Pearson plcPrentice Hall is a registered trademark of Pearson Education, : 0-13-359162-XISBN-13: 978-0-13-359162-0To Suzanne, Barbara, Daniel, Aron, Nathan, Marvin, Matilde, and list keeps growing.

4 (AST)To Marieke, Duko, Jip, and Spot. Fearsome Jedi, all. (HB)This page intentionally left blank WHAT IS AN OPERATING SYSTEM? The Operating System as an Extended Machine The Operating System as a Resource Manager HISTORY OF OPERATING SYSTEMS The First Generation (1945 55): Vacuum Tubes Second Generation (1955 65): Transistors and Batch The Third Generation (1965 1980): ICs and Multiprogramming The Fourth Generation (1980 Present): Personal Computers The Fifth Generation (1990 Present): Mobile Computers COMPUTER HARDWARE REVIEW Processors Memory Disks I/O Devices Buses Booting the Computer THE OPERATING SYSTEM ZOO Mainframe Operating Systems Server Operating Systems Multiprocessor Operating Systems Personal Computer Operating Systems Handheld Computer Operating Systems Embedded Operating Systems Sensor-Node Operating Systems Real-Time Operating Systems Smart Card Operating Systems OPERATING SYSTEM CONCEPTS Processes Address Spaces Files Input/Output Protection The Shell Ontogeny Recapitulates Phylogeny SYSTEM CALLS System Calls for Process Management

5 System Calls for File Management System Calls for Directory Management Miscellaneous System Calls The Windows Win32 API OPERATING SYSTEM STRUCTURE Monolithic Systems Layered Systems Microkernels Client-Server Model Virtual Machines Exokernels THE WORLD ACCORDING TO C The C Language Header Files Large Programming Projects The Model of Run Time RESEARCH ON OPERATING SYSTEMS OUTLINE OF THE REST OF THIS BOOK METRIC UNITS SUMMARY 802 PROCESSES AND PROCESSES The Process Model Process Creation Process Termination Process Hierarchies Process States Implementation of Processes Modeling Multiprogramming THREADS Thread Usage The Classical Thread Model POSIX Threads Implementing Threads in User Space Implementing Threads in the Kernel Hybrid Implementations Scheduler Activations Pop-Up Threads Making Single-Threaded Code Multithreaded INTERPROCESS COMMUNICATION Race Conditions Critical Regions Mutual Exclusion with Busy Waiting Sleep and Wakeup Semaphores Mutexes Monitors Message Passing Barriers Avoiding Locks.

6 Read-Copy-Update SCHEDULING Introduction to Scheduling Scheduling in Batch Systems Scheduling in Interactive Systems Scheduling in Real-Time Systems Policy Versus Mechanism Thread Scheduling CLASSICAL IPC PROBLEMS The Dining Philosophers Problem The Readers and Writers Problem RESEARCH ON PROCESSES AND THREADS SUMMARY 1733 MEMORY NO MEMORY ABSTRACTION A MEMORY ABSTRACTION: ADDRESS SPACES The Notion of an Address Space Swapping Managing Free Memory VIRTUAL MEMORY Paging Page Tables Speeding Up Paging Page Tables for Large Memories PAGE REPLACEMENT ALGORITHMS The Optimal Page Replacement Algorithm The Not Recently Used Page Replacement Algorithm The First-In, First-Out (FIFO) Page Replacement Algorithm The Second-Chance Page Replacement Algorithm The Clock Page Replacement Algorithm The Least Recently Used (LRU)

7 Page Replacement Algorithm Simulating LRU in Software The Working Set Page Replacement Algorithm The WSClock Page Replacement Algorithm Summary of Page Replacement Algorithms DESIGN ISSUES FOR PAGING SYSTEMS Local versus Global Allocation Policies Load Control Page Size Separate Instruction and Data Spaces Shared Pages Shared Libraries Mapped Files Cleaning Policy Virtual Memory Interface IMPLEMENTATION ISSUES Operating System Involvement with Paging Page Fault Handling Instruction Backup Locking Pages in Memory Backing Store Separation of Policy and Mechanism SEGMENTATION Implementation of Pure Segmentation Segmentation with Paging: MULTICS Segmentation with Paging.

8 The Intel x86 RESEARCH ON MEMORY MANAGEMENT SUMMARY 253xiiCONTENTS4 FILE FILES File Naming File Structure File Types File Access File Attributes File Operations An Example Program Using File-System Calls DIRECTORIES Single-Level Directory Systems Hierarchical Directory Systems Path Names Directory Operations FILE-SYSTEM IMPLEMENTATION File-System Layout Implementing Files Implementing Directories Shared Files Log-Structured File Systems Journaling File Systems Virtual File Systems FILE-SYSTEM MANAGEMENT AND OPTIMIZATION Disk-Space Management File-System Backups File-System Consistency File-System Performance Defragmenting Disks EXAMPLE FILE SYSTEMS The MS-DOS File System The UNIX V7 File System CD-ROM File Systems RESEARCH ON FILE SYSTEMS SUMMARY 332 CONTENTS xiii5 PRINCIPLES OF I/O HARDWARE I/O Devices Device Controllers Memory-Mapped I/O Direct Memory Access Interrupts Revisited PRINCIPLES OF I/O SOFTWARE Goals of the I/O Software Programmed I/O Interrupt-Driven I/O I/O Using DMA I/O SOFTWARE LAYERS Interrupt Handlers Device Drivers Device-Independent I/O Software User-Space I/O Software DISKS Disk Hardware Disk Formatting

9 Disk Arm Scheduling Algorithms Error Handling Stable Storage CLOCKS Clock Hardware Clock Software Soft Timers USER INTERFACES: KEYBOARD, MOUSE, MONITOR Input Software Output Software THIN CLIENTS POWER MANAGEMENT Hardware Issues Operating System Issues Application Program Issues RESEARCH ON INPUT/OUTPUT SUMMARY RESOURCES Preemptable and Nonpreemptable Resources Resource Acquisition INTRODUCTION TO DEADLOCKS Conditions for Resource Deadlocks Deadlock Modeling THE OSTRICH ALGORITHM DEADLOCK DETECTION AND RECOVERY Deadlock Detection with One Resource of Each Type Deadlock Detection with Multiple Resources of Each Type Recovery from Deadlock DEADLOCK AV OIDANCE Resource Trajectories Safe and

10 Unsafe States The Banker s Algorithm for a Single Resource The Banker s Algorithm for Multiple Resources DEADLOCK PREVENTION Attacking the Mutual-Exclusion Condition Attacking the Hold-and-Wait Condition Attacking the No-Preemption Condition Attacking the Circular Wait Condition OTHER ISSUES Two-Phase Locking Communication Deadlocks Livelock Starvation RESEARCH ON DEADLOCKS SUMMARY 4647 VIRTUALIZATION AND THE HISTORY REQUIREMENTS FOR VIRTUALIZATION TYPE 1 AND TYPE 2 HYPERVISORS TECHNIQUES FOR EFFICIENT VIRTUALIZATION Virtualizing the Unvirtualizable The Cost of Virtualization ARE HYPERVISORS MICROKERNELS DONE RIGHT?