WIXLIB

Xiv6CONTENTSCONTENTSDEADLOCKS6.1 RESOURCES 4326.1.1 Preemptable and Nonpreemptable Resources 4326.1.2 Resource Acquisition 4336.2 INTRODUCTION TO DEADLOCKS 4356.2.1 Conditions for Resource Deadlocks 4366.2.2 Deadlock Modeling 4366.3 THE OSTRICH ALGORITHM 4396.4 DEADLOCK DETECTION AND RECOVERY 4406.4.1 Deadlock Detection with One Resource of Each Type 4406.4.2 Deadlock Detection with Multiple Resources of Each Type6.4.3 Recovery from Deadlock 4457MULTIMEDIA O P E R A T I N G S Y S T E M S7.1 INTRODUCTION TO MULTIMEDIA 4667.2 MULTIMEDIA FILES 4707.2.1 Video Encoding 4717.2.2 Audio Encoding 4747.3 VIDEO COMPRESSION 4767.3.1 The JPEG Standard 4767.3.2 The MPEG Standard 4797.4 AUDIO COMPRESSION .4827.5 MULTIMEDIA PROCESS SCHEDULING 4857.5.1 Scheduling Homogeneous Processes 4867.5.2 General Real-Time Scheduling 4867.5.3 Rate Monotonic Scheduling 4887.5.4 Earliest Deadline First Scheduling 4896.5 DEADLOCK AVOIDANCE 4466.5.1 Resource Trajectories 4476.5.2 Safe and Unsafe States 4486.5.3 The Banker's Algorithm for a Single Resource 4496.5.4 The Banker's Algorithm for Multiple Resources 4507.6 MULTIMEDIA FILE SYSTEM PARADIGMS 4917.6.1 VCR Control Functions 4927.6.2 Near Video on Demand 4947.6.3 Near Video on Demand with VCR Functions 4966.6 DEADLOCK PREVENTION 4526.6.1 Attacking the Mutual Exclusion Condition 4526.6.2 Attacking the Hold and Wait Condition 4536.6.3 Attacking the No Preemption Condition 4536.6.4 Attacking the Circular Wait Condition 4547.7 FILE PLACEMENT 4977.7.1 Placing a File on a Single Disk 4987.7.2 Two Alternative File Organization Strategies 4997.7.3 Placing Files for Near Video on Demand 5027.7.4 Placing Multiple Files on a Single Disk 5047.7.5 Placing Files on Multiple Disks 5066.7 OTHER ISSUES 4556.7.1 Two-Phase Locking 4556.7.2 Communication Deadlocks 4566.7.3 Livelock 4576.7.4 Starvation 4596.8 RESEARCH ON DEADLOCKS 4596.9 SUMMARY 4607.8 CACHING 5087.8.1 Block Caching 5097.8.2 File Caching 5107.9 DISK SCHEDULING FOR MULTIMEDIA 5117.9.1 Static Disk Scheduling 5117.9.2 Dynamic Disk Scheduling 5137.10 RESEARCH ON MULTIMEDIA 5147.11 SUMMARY 515

xvi8CONTENTSCONTENTSMULTIPLE P R O C E S S O R S Y S T E M S8.1 MULTIPROCESSORS 5248.1.1 Multiprocessor Hardware 5248.1.2 Multiprocessor Operating System Types 5328.1.3 Multiprocessor Synchronization 5368.1.4 Multiprocessor Scheduling 5408.2 MULTICOMPUTERS 5468.2.1 Multicomputer Hardware 5478.2.2 Low-Level Communication Software 5518.2.3 User-Level Communication Software 5538.2.4 Remote Procedure Call 5568.2.5 Distributed Shared Memory 5588.2.6 Multicomputer Scheduling 5638.2.7 Load Balancing 5638.3 VIRTUALIZATION 5668.3.1 Requirements for Virtualization 5688.3.2 Type I Hypervisors 5698.3.3 Type 2 Hypervisors 5708.3.4 Paravirtualization 5728.3.5 Memory Virtualization 5748.3.6 I/O Virtualization 5768.3.7 Virtual Appliances 5778.3.8 Virtual Machines on Multicore CPUs 5778.3.9 Licensing Issues 5788.4 DISTRIBUTED SYSTEMS 5788.4.1 Network Hardware 5818.4.2 Network Services and Protocols 5848.4.3 Document-Based Middleware 5888.4.4 File-System-Based Middleware 5898.4.5 Object-Based Middleware 5948.4.6 Coordination-Based Middleware 5968.4.7 Grids 6018.5 RESEARCH ON MULTIPLE PROCESSOR SYSTEMS 6028.6 SUMMARY 6035219SECURITY9.1 THE SECURITY ENVIRONMENT 6119.1.1 Threats 6119.1.2 Intruders 6139.1.3 Accidental Data Loss 6149.2 BASICS OF CRYPTOGRAPHY 6149.2.1 Secret-Key Cryptography 6159.2.2 Public-Key Cryptography 6169.2.3 One-Way Functions 6179.2.4 Digital Signatures 6179.2.5 Trusted Platform Module 6199.3 PROTECTION MECHANISMS 6209.3.1 Protection Domains 6209.3.2 Access Control Lists 6229.3.3 Capabilities 6259.3.4 Trusted Systems 6289.3.5 Trusted Computing Base 6299.3.6 Formal Models of Secure Systems 6309.3.7 Multilevel Security 6329.3.8 Covert Channels 6359.4 AUTHENTICATION 6399.4.1 Authentication Using Passwords 6409.4.2 Authentication Using a Physical Object 6499.4.3 Authentication Using Biometrics 6519.5 INSIDER ATTACKS 6549.5.1 Logic Bombs 6549.5.2 Trap Doors 6559.5.3 Login Spooling 6569.6 EXPLOITING CODE BUGS 6579.6.1 Buffer Overflow Attacks 6589.6.2 Format String Attacks 6609.6.3 Return to libc Attacks 6629.6.4 Integer Overflow Attacks 6639.6.5 Code Injection Attacks 6649.6.6 Privilege Escalation Attacks 665

xviiiCONTENTSCONTENTS9.7 MALWARE 6659.7.1 Trojan Horses 6689.7.2 Viruses 6709.7.3 Worms 6809.7.4 Spyware 6829.7.5 Rootkits 68610.3 PROCESSES IN LINUX 73510.3.1 Fundamental Concepts 73510.3.2 Process Management System Calls in Linux 73710.3.3 Implementation of Processes and Threads in Linux 74110.3.4 Scheduling in Linux 74810.3.5 Booting Linux 7519.8 DEFENSES 69010.4 MEMORY MANAGEMENT IN LINUX 75410.4.1 Fundamental Concepts 75410.4.2 Memory Management System Calls in Linux 75710.4.3 Implementation of Memory Management in Linux 75810.4.4 Paging in Linux 7649.8.1 Firewalls 69119.8.2 Antivirus and Anti-Antivirus Techniques 6939.8.3 Code Signing 6999.8.4 Jailing 7009.8.5 Model-Based Intrusion Detection 7019.8.6 Encapsulating Mobile Code 7039.8.7 Java Security 707 1§19.9 RESEARCH ON SECURITY 7099.10 SUMMARY 710 HvI10 CASE STUDY 1: LINUX10.1 HISTORY OF UNIX AND LINUX 71610.1.1 UNICS 71610.1.2 PDP-11 UNIX 71710.1.3 Portable UNIX 71810.1.4 Berkeley UNIX 71910.1.5 Standard UNIX 72010.1.6 MINTX 72110.1.7 Linux 722715f §JI10.2 OVERVIEW OF LINUX 72410.2.1 Linux Goals 72510.2.2 Interfaces to Linux 72610.2.3 The Shell 72710.5 INPUT/OUTPUT IN LINUX 76710.5.1 Fundamental Concepts 76810.5.2 Networking 76910.5.3 Input/Output System Calls in Linux 77110.5.4 Implementation of Input/Output in Linux 77110.5.5 Modules in Linux 77510.6 THE LINUX FILE SYSTEM 77510.6.1 Fundamental Concepts 77610.6.2 File System Calls in Linux 78110.6.3 Implementation of the Linux File System 78410.6.4 NFS: The Network File System 79210.7 SECURITY IN LINUX 79910.7.1 Fundamental Concepts 79910.7.2 Security System Calls in Linux 80110.7.3 Implementation of Security in Linux 80210.8 SUMMARY 80211 CASE STUDY 2: WINDOWS VISTA11.1 HISTORY OF WINDOWS VISTA 80911.1.1 1980s: MS-DOS 810U.1.2 1990s: MS-DOS-based Windows 811iU.32000s:NT-basedWmdows11.1.4 Windows Vista 81410.2.5 Kernel Structure 7321xixMl809

CONTENTSXX11.2 PROGRAMMING WINDOWS VISTA 81511.2.1 The Native NT Application Programming Interface 81811.2.2 The Win32 Application Programming Interface 82111.2.3 The Windows Registry 82511.3 SYSTEM STRUCTURE 82711.3.1 Operating System Structure 82811.3.2 Booting Windows Vista 84311.3.3 Implementation of the Object Manager 84411.3.4 Subsystems, DLLs, and User-Mode Services 85411.4 PROCESSES AND THREADS IN WINDOWS VISTA 85711.4.1 Fundamental Concepts 85711.A2 Job, Process, Thread, and Fiber Management API Calls 86211.4.3 Implementation of Processes and Threads 867:11.5 MEMORY MANAGEMENT 87511.5.1 Fundamental Concepts 87511.5.2 Memory Management System Calls 88011.5.3 Implementation of Memory Management 88111.6 CACHING IN WINDOWS VISTA 89011.7 INPUT/OUTPUT IN WINDOWS VISTA 89211.7.1 Fundamental Concepts 89311.7.2 Input/Output API Calls 89411.7.3 Implementation of I/O 89711.8 THE WINDOWS NT FILE SYSTEM 90211.8.1 Fundamental Concepts 90311.8.2 Implementation of the NT File System 90411.9 SECURITY IN WINDOWS VISTA 91411.9.1 Fundamental Concepts 91511.9.2 Security API Calls 91711.9.3 Implementation of Security 91811.10 SUMMARY 920CONTENTS12 CASE STUDY 3: SYMBIAN OS12.1 THE HISTORY OF SYMBIAN OS 92612.1.1 Symbian OS Roots: Psion and EPOC 92612.1.2 Symbian OS Version 6 92712.1.3 Symbian OS Version 7 92812.1A Symbian OS Today 92812.2 AN OVERVIEW OF SYMBIAN OS 92812.2.1 Object Orientation 92912.2.2 Microkernel Design 93012.2.3 The Symbian OS Nanokemel 93112.2.4 Client/Server Resource Access 93112.2.5 Features of a Larger Operating System 93212.2.6 Communication and Multimedia 93312.3 PROCESSES AND THREADS IN SYMBIAN OS 93312.3.1 Threads and Nanothreads 93412.3.2 Processes 93512.3.3 Active Objects 93512.3.4 Interprocess Communication 93612.4 MEMORY MANAGEMENT 93712.4.1 Systems with No Virtual Memory 93712.4.2 How Symbian OS Addresses Memory 93912.5 INPUT AND OUTPUT 94112.5.1 Device Drivers 94112.5.2 Kernel Extensions 94212.5.3 Direct Memory Access 94212.5.4 Special Case: Storage Media 94312.5.5 Blocking I/O 94312.5.6 Removable Media 94412.6 STORAGE SYSTExMS 94412.6.1 File Systems for Mobile Devices 94412.6.2 Symbian OS File Systems 94512.6.3 File System Security and Protection 94512.7 SECURITY IN SYMBIAN OS 946

xxiiCONTENTS12.8 COMMUNICATION IN SYMBIAN OS 94912.8.1 Basic Infrastructure 94912.8.2 A Closer Look at the Infrastructure 95012.9 SUMMARY 95313 OPERATING SYSTEM DESIGN13.1 THE NATURE OF THE DESIGN PROBLEM 95613.1.1 Goals 95613.1.2 Why Is It Hard to Design an Operating System? 95713.2 INTERFACE DESIGN 95913.2.1 Guiding Principles 95913.2.2 Paradigms 96113.2.3 The System Call Interface 96413.3 IMPLEMENTATION 96713.3.1 System Structure 96713.3.2 Mechanism versus Policy 97113.3.3 Orthogonality 97213.3.4 Naming 97313.3.5 Binding Time 97413.3.6 Static versus Dynamic Structures 97513.3.7 Top-Down versus Bottom-Up Implementation 97613.3.8 Useful Techniques 97713.4 PERFORMANCE 98313.4.1 Why Are Operating Systems Slow? 98313.4.2 What Should Be Optimized? 98413.4.3 Space-Time Trade-offs 98413.4.4 Caching 98713.4.5 Hints 98813.4.6 Exploiting Locality 98913.4.7 Optimize the Common Case 98913.5 PROJECT MANAGEMENT 99013.5.1 The Mythical Man Month 99013.5.2 Team Structure 991CONTENTSxxiii13.5.3 The Role of Experience 99313.5.4 No Silver Bullet 99413.6 TRENDS IN OPERATING SYSTEM DESIGN 99413.6.1 Virtualization 99513.6.2 Multicore Chips 99513.6.3 Large Address Space Operating Systems 99613.6.4 Networking 99613.6.5 Parallel and Distributed Systems 99713.6.6 Multimedia 99713.6.7 Battery-Powered Computers 99813.6.8 Embedded Systems 99813.6.9 Sensor Nodes 99913.7 SUMMARY 99914 READING LIST AND BIBLIOGRAPHY14.1 SUGGESTIONS FOR FURTHER READING14.1.1 Introduction and General Works 100414.1.2 Processes and Threads 100414.1.3 Memory Management 100514.1.4 Input/Output 100514.1.5 File Systems 100614.1.6 Deadlocks 100614.1.7 Multimedia Operating Systems 100614.1.8 Multiple Processor Systems 100714.1.9 Security 100814.1.10 Linux 101014.1.11 Windows Vista 101014.1.12 The Symbian OS 101114.1.13 Design Principles 101114.2 ALPHABETICAL BIBLIOGRAPHYINDEX1003100310121045

PREFACEPREFACEThe third edition of this book differs from the second edition in numerousways. To start with, the chapters have been reordered to place the central materialat the beginning. There is also now more of a focus on the operating system as thecreator of abstractions. Chapter 1, which has been heavily updated, introduces allthe concepts. Chapter 2 is about the abstraction of the CPU into multipleprocesses. Chapter 3 is about the abstraction of physical memory into addressspaces (virtual memory). Chapter 4 is about the abstraction of the disk into files.Together, processes, virtual address spaces, and files are the key concepts that operating systems provide, so these chapters are now placed earlier than they previously had been.Chapter 1 has been heavily modified and updated in many places. For example, an introduction to the C programming language and the C run-time model isgiven for readers familiar only with Java.In Chapter 2, the discussion of threads has been revised and expanded reflecting their new importance. Among other things, there is now a section on IEEEstandard Pthreads.Chapter 3, on memory management, has been reorganized to emphasize theidea that one of the key functions of an operating system is to provide the abstraction of a virtual address space for each process. Older material on memorymanagement in batch systems has been removed, and the material on the implementation of paging has been updated to focus on the need to make it handle thelarger address spaces now common and also the need for speed.xxivXXVChapters 4-7 have been updated, with older material removed and some newmaterial added. The sections on current research in these chapters have beenrewritten from scratch. Many new problems and programming exercises havebeen added.Chapter 8 has been updated, including some material on multicore systems.A whole new section on virtualization technology, hypervisors, and virtualmachines, has been added with VMware used as an example.Chapter 9 has been heavily revised and reorganized, with considerable newmaterial on exploiting code bugs, malware, and defenses against them.Chapter 10, on Linux, is a revision of the old Chapter 10 (on UNIX andLinux). The focus is clearly on Linux now, with a great deal of new material.Chapter 11, on Windows Vista, is a major revision of the old Chap. 11 (onWindows 2000). It brings the treatment of Windows completely up to date.Chapter 12 is new. I felt that embedded operating systems, such as thosefound on cell phones and PDAs, are neglected in most textbooks, despite the factthat there are more of them out there than there are PCs and notebooks. This edition remedies this problem, with an extended discussion of Symbian OS, which iswidely used on Smart Phones.Chapter 13, on operating system design, is largely unchanged from the secondedition.Numerous teaching aids for this book are available. Instructor supplementscan be found at www.prenhall.com/tanenbaum. They include PowerPoint sheets,software tools for studying operating systems, lab experiments for students, simulators, and more material for use in operating systems courses. Instructors usingthis book in a course should definitely take a look.In addition, instructors should examine GOAL (Gradiance Online AcceleratedLearning), Pearson's premier online homework and assessment system. GOAL isdesigned to minimize student frustration while providing an interactive teachingexperience outside the classroom. With GOAL'S immediate feedback, hints, andpointers that map back to the textbook, students will have a more efficient andeffective learning experience. GOAL delivers immediate assessment and feedback via two kinds of assignments: multiple choice Homework exercises andinteractive Lab work.The multiple-choice homework consists of a set of multiple choice questionsdesigned to test student knowledge of a solved problem. When answers are gradedas incorrect, students are given a hint and directed back to a specific section in thecourse textbook for helpful information.The interactive Lab Projects in GOAL, unlike syntax checkers and compilers,check for both syntactic and semantic errors. GOAL determines if the student'sprogram runs but more importantly, when checked against a hidden data set, verifies that it returns the correct result. By testing the code and providing immediatefeedback, GOAL lets you know exactly which concepts the students have graspedand which ones need to be revisited.

xxviPREFACEInstructors should contact their local Pearson Sales Representative for salesand ordering information for the GOAL Student Access Code and ModernOperating Systems, 3e Value Pack (ISBN: 0135013011).A number of people helped me with this revision. First and foremost I wantto thank my editor, Tracy Dunkelberger. This is my 18th book and I have wornout a lot of editors in the process. Tracy went above and beyond the call of dutyon this one, doing things like finding contributors, arranging numerous reviews,helping with all the supplements, dealing with contracts, interfacing to PH, coordinating a great deal of parallel processing, generally making sure things happened on time, and more. She also was able to get me to make and keep to a verytight schedule in order to get this book out in time. And all this while she remained chipper and cheerful, despite many other demands on her time. Thank you,Tracy. I appreciate it a lot. Ada Gavrilovska of Georgia Tech, who is an expert on Linux internals,updated Chap. 10 from one on UNIX (with a focus on FreeBSD) to one moreabout Linux, although much of the chapter is still generic to all UNIX systems.Linux is more popular among students than FreeBSD, so this is a valuable change.Dave Probert of Microsoft updated Chap. 11 from one on Windows 2000 toone on Windows Vista. While they have some similarities, they also have significant differences. Dave has a great deal of knowledge of Windows and enoughvision to tell the difference between places where Microsoft got it right and whereit got it wrong. The book is much better as a result of his work.Mike Jipping of Hope College wrote the chapter on Symbian OS. Not havinganything on embedded real-time systems was a serious omission in the book, andthanks to Mike that problem has been solved. Embedded real-time systems arebecoming increasingly important in the world and this chapter provides an excellent introduction to the subject.Unlike cla, Dave, and Mike, who each focused on one chapter, ShivakantMishra of the University of Colorado at Boulder was more like a distributed system, reading and commenting on many chapters and also supplying a substantialnumber of new exercises and programming problems throughout the book.Hugh Lauer also gets a special mention. When we asked him for ideas abouthow to revise the second edition, we weren't expecting a report of 23 singlespaced pages, but that is what we got. Many of the changes, such as the new emphasis on the abstractions of processes, address spaces, and files are due to his input.I would also like to thank other people who helped me in many ways, including suggesting new topics to cover, reading the manuscript carefully, making supplements, and contributing new exercises. Among them are Steve Armstrong, Jeffrey Chastine, John Connelly, Mischa Geldermans, Paul Gray, James Griffioen,Jorrit Herder, Michael Howard, Suraj Kothari, Roger Kraft, Trudy Levine, JohnMasiyowski, Shivakant Mishra, Rudy Pait, Xiao Qin, Mark Russinovich, KrishnaSivalingam, Leendert van Doom, and Ken Wong.PREFACExxviiThe people at Prentice Hall have been friendly and helpful as always, especially including Irwin Zucker and Scott Disanno in production and David AlickReeAnne Davies, and Melinda Haggerty in editorial.Finally, last but not least, Barbara and Marvin are still wonderful, as usualeach ma unique and special way. And of course, I would like to thank Suzannefor her love and patience, not to mention all the druiven and kersen, which havereplaced the sinaasappelsap in recent times.Andrew S. Tanenbaum

ABOUT THE AUTHORAndrew S. Tanenbaum has an S.B. degree from M.I.T. and a Ph.D. from theUniversity of California at Berkeley. He is currently a Professor of ComputerScience at the Vrije Universiteit in Amsterdam, The Netherlands, where he headsthe Computer Systems Group. He was formerly Dean of the Advanced School forComputing and Imaging, an interuniversity graduate school doing research onadvanced parallel, distributed, and imaging systems. He is now an Academy Professor of the Royal Netherlands Academy of Arts and Sciences, which has savedhim from turning into a bureaucrat.In the past, he has done research on compilers, operating syst

Operating Systems: Design and Implementation, 3rd edition This popular text on operating systems is the only book covering both the princi ples of operating systems and their application to a real system. All the traditional operating systems topics are