Modern Operating Systems

by Tanenbaum, Andrew S.

• ISBN13: 9780130313584
• ISBN10: 0130313580
• Edition: 2nd
• Format: Hardcover
• Copyright: 2008-01-01
• Publisher: Prentice Hall

Summary

The widely anticipated revision of this worldwide best seller incorporates the latest developments in operating systems technologies. Hundreds of pages of new material on a wealth of subjects have been added. This authoritative, example-based reference offers practical, hands-on information in constructing and understanding modern operating systems. Continued in this second edition are the "big picture" concepts, presented in the clear and entertaining style that only Andrew S. Tanenbaum can provide. Tanenbaum's long experience as the designer or co-designer of three operating systems brings a knowledge of the subject and wealth of practical detail that few other books can match. FEATURES \ bull; bull;NEW-New chapters on computer security, multimedia operating systems, and multiple processor systems. bull;NEW-Extensive coverage of Linux, UNIXreg;, and Windows 2000trade; as examples. bull;NEW-Now includes coverage of graphical user interfaces, multiprocessor operating systems, trusted systems, viruses, network terminals, CD-ROM file systems, power management on laptops, RAID, soft timers, stable storage, fair-share scheduling, three-level scheduling, and new paging algorithms. bull;NEW-Most chapters have a new section on current research on the chapter's topic. bull;NEW-Focus on single-processor computer systems; a new book for a follow-up course on distributed systems is also available from Prentice Hall. bull;NEW-Over 200 references to books and papers published since the first edition. bull;NEW-The Web site for this book contains PowerPoint slides, simulators, figures in various formats, and other teaching aids.

Table of Contents

Preface	xvi
Introduction	1	(70)
What is an Operating System?	3	(3)
The Operating System as an Extended Machine	3	(2)
The Operating System as a Resource Manager	5	(1)
History of Operating Systems	6	(12)
The First Generation (1945-55)	6	(1)
The Second Generation (1955-65)	7	(2)
The Third Generation (1965-1980)	9	(4)
The Fourth Generation (1980-Present)	13	(3)
Ontogeny Recapitulates Phylogeny	16	(2)
The Operating System Zoo	18	(2)
Mainframe Operating Systems	18	(1)
Server Operating Systems	19	(1)
Multiprocessor Operating Systems	19	(1)
Personal Computer Operating Systems	19	(1)
Real-Time Operating Systems	19	(1)
Embedded Operating Systems	20	(1)
Smart Card Operating Systems	20	(1)
Computer Hardware Review	20	(14)
Processors	21	(2)
Memory	23	(5)
I/O Devices	28	(3)
Buses	31	(3)
Operating System Concepts	34	(10)
Processes	34	(2)
Deadlocks	36	(1)
Memory Management	37	(1)
Input/Output	38	(1)
Files	38	(3)
Security	41	(1)
The Shell	41	(2)
Recycling of Concepts	43	(1)
System Calls	44	(12)
System Calls for Process Management	48	(2)
System Calls for File Management	50	(1)
System Calls for Directory Management	51	(2)
Miscellaneous System Calls	53	(1)
The Windows Win32 API	53	(3)
Operating System Structure	56	(7)
Monolithic Systems	56	(1)
Layered Systems	57	(2)
Virtual Machines	59	(2)
Exokernels	61	(1)
Client-Server Model	61	(2)
Research on Operating Systems	63	(2)
Outline of the Rest of This Book	65	(1)
Metric Units	66	(1)
Summary	67	(4)
Processes and Threads	71	(88)
Processes	71	(10)
The Process Model	72	(1)
Process Creation	73	(2)
Process Termination	75	(1)
Process Hierachies	76	(1)
Process States	77	(2)
Implementation of Processes	79	(2)
Threads	81	(19)
The Thread Model	81	(4)
Thread Usage	85	(5)
Implementing Threads in User Space	90	(3)
Implementing Threads in the Kernel	93	(1)
Hybrid Implementations	94	(1)
Scheduler Activations	94	(2)
Pop-Up Threads	96	(1)
Making Single-Threaded Code Multithreaded	97	(3)
Interprocess Communication	100	(24)
Race Conditions	100	(2)
Critical Regions	102	(1)
Mutual Exclusion with Busy Waiting	103	(5)
Sleep and Wakeup	108	(2)
Semaphores	110	(3)
Mutexes	113	(2)
Monitors	115	(4)
Message Passing	119	(4)
Barriers	123	(1)
Classical IPC Problems	124	(8)
The Dining Philosophers Problem	125	(3)
The Readers and Writers Problem	128	(1)
The Sleeping Barber Problem	129	(3)
Scheduling	132	(19)
Introduction to Scheduling	132	(6)
Scheduling in Batch Systems	138	(4)
Scheduling in Interactive Systems	142	(6)
Scheduling in Real-Time Systems	148	(1)
Policy Versus Mechanism	149	(1)
Thread Scheduling	150	(1)
Research on Processes and Threads	151	(1)
Summary	152	(7)
Deadlocks	159	(30)
Resources	160	(3)
Preemptable and Nonpreemptable Resources	160	(1)
Resource Acquisition	161	(2)
Introduction to Deadlocks	163	(4)
Conditions for Deadlock	164	(1)
Deadlock Modeling	164	(3)
The Ostrich Algorithm	167	(1)
Deadlock Detection and Recovery	168	(7)
Deadlock Detection with One Resource of Each Type	168	(3)
Deadlock Detection with Multiple Resource of Each Type	171	(2)
Recovery from Deadlock	173	(2)
Deadlock Avoidance	175	(5)
Resource Trajectories	175	(1)
Safe and Unsafe States	176	(2)
The Banker's Algorithm for a Single Resource	178	(1)
The Banker's Algorithm for Multiple Resources	179	(1)
Deadlock Prevention	180	(3)
Attacking the Mutual Exclusion Condition	180	(1)
Attacking the Hold and Wait Condition	181	(1)
Attacking the No Preemption Condition	182	(1)
Attacking the Circular Wait Condition	182	(1)
Other Issues	183	(2)
Two-Phase Locking	183	(1)
Nonresource Deadlocks	184	(1)
Starvation	184	(1)
Research on Deadlocks	185	(1)
Summary	185	(4)
Memory Management	189	(80)
Basic Memory Management	190	(6)
Monoprogramming Without Swapping or Paging	190	(1)
Multiprogramming with Fixed Partitions	191	(1)
Modeling Multiprogramming	192	(2)
Analysis of Multiprogramming System Performance	194	(1)
Relocation and Protection	194	(2)
Swapping	196	(6)
Memory Management with Bitmaps	199	(1)
Memory Management with Linked Lists	200	(2)
Virtual Memory	202	(12)
Paging	202	(3)
Page Tables	205	(6)
TLBs---Translation Lookaside Buffers	211	(2)
Inverted Page Tables	213	(1)
Page Replacement Algorithms	214	(14)
The Optimal Page Replacement Algorithm	215	(1)
The Not Recently Used Page Replacement Algorithm	216	(1)
The First-In, First-Out	217	(1)
The Second Chance Page Replacement Algorithm	217	(1)
The Clock Page Replacement Algorithm	218	(1)
The Least Recently Used	218	(2)
Simulating LRU in Software	220	(2)
The Working Set Page Replacement Algorithm	222	(3)
The WSClock Page Replacement Algorithm	225	(2)
Summary of Page Replacement Algorithms	227	(1)
Modeling Page Replacement Algorithms	228	(6)
Belady's Anomaly	229	(1)
Stack Algorithms	229	(3)
The Distance String	232	(1)
Predicting Page Fault Rates	233	(1)
Design Issues for Paging Systems	234	(8)
Local Versus Global Allocation Policies	234	(2)
Load Control	236	(1)
Page Size	237	(2)
Separate Instruction and Data Spaces	239	(1)
Shared Pages	239	(2)
Cleaning Policy	241	(1)
Virtual Memory Interface	241	(1)
Implementation Issues	242	(7)
Operating System Involvement with Paging	242	(1)
Page Fault Handling	243	(1)
Instruction Backup	244	(2)
Locking Pages in Memory	246	(1)
Backing Store	246	(1)
Separation of Policy and Mechanism	247	(2)
Segmentation	249	(13)
Implementation of Pure Segmentation	253	(1)
Segmentation with Paging: MULTICS	254	(3)
Segmentation with Paging: The Intel Pentium	257	(5)
Research on Memory Management	262	(1)
Summary	262	(7)
Input/Output	269	(110)
Principles of I/O Hardware	269	(13)
I/O Devices	270	(1)
Device Controllers	271	(1)
Memory-Mapped I/O	272	(4)
Direct Memory Access	276	(3)
Interrupts Revisited	279	(3)
Principles of I/O Software	282	(5)
Goals of the I/O Software	283	(1)
Programmed I/O	284	(2)
Interrupt-Driven I/O	286	(1)
I/O Using DMA	287	(1)
I/O Software Layers	287	(13)
Interrupt Handlers	287	(2)
Device Drivers	289	(3)
Device-Independent I/O Software	292	(6)
User-Space I/O Software	298	(2)
Disks	300	(27)
Disk Formatting	315	(3)
Disk Arm Scheduling Algorithms	318	(4)
Error Handling	322	(2)
Stable Storage	324	(3)
Clocks	327	(6)
Clock Hardware	328	(1)
Clock Software	329	(3)
Soft Timers	332	(1)
Character-Oriented Terminals	333	(9)
RS-232 Terminal Hardware	334	(2)
Input Software	336	(5)
Output Software	341	(1)
Graphical User Interfaces	342	(13)
Personal Computer Keyboard, Mouse, and Display Hardware	343	(4)
Input Software	347	(1)
Output Software for Windows	347	(8)
Network Terminals	355	(8)
The X Window System	356	(4)
The SLIM Network Terminal	360	(3)
Power Management	363	(8)
Hardware Issues	364	(1)
Operating System Issues	365	(5)
Degraded Operation	370	(1)
Research on Input/Output	371	(1)
Summary	372	(7)
File Systems	379	(74)
Files	380	(13)
File Naming	380	(2)
File Structure	382	(1)
File Types	383	(2)
File Access	385	(1)
File Attributes	386	(1)
File Operations	387	(2)
An Example Program Using File System Calls	389	(2)
Memory-Mapped Files	391	(2)
Directories	393	(6)
Single- Level Directory Systems	393	(1)
Two-level Directory Systems	394	(1)
Hierarchical Directory Systems	395	(1)
Path Names	395	(3)
Directory Operations	398	(1)
File System Implementation	399	(31)
File System Layout	399	(1)
Implementing Files	400	(5)
Implementing Directories	405	(3)
Shared Files	408	(2)
Disks Space Management	410	(6)
File System Reliability	416	(8)
File System Performance	424	(4)
Log-Structured File Systems	428	(2)
Example File Systems	430	(18)
CD-ROM File Systems	430	(5)
The CP/M File System	435	(3)
The MS-DOS File System	438	(4)
The Windows 98 File System	442	(3)
The UNIX V7 File System	445	(3)
Research on File Systems	448	(1)
Summary	448	(5)
Multimedia Operating Systems	453	(50)
Introduction to Multimedia	454	(4)
Multimedia Files	458	(5)
Audio Encoding	459	(2)
Video Encoding	461	(2)
Video Compression	463	(6)
The JPEG Standard	464	(3)
The MPEG Standard	467	(2)
Multimedia Process Scheduling	469	(6)
Scheduling Homogeneous Processes	469	(1)
General Real-Time Scheduling	470	(2)
Rate Monotonic Scheduling	472	(1)
Earliest Deadline First Scheduling	473	(2)
Multimedia File System Paradigms	475	(6)
VCR Control Functions	476	(2)
Near Video on Demand	478	(1)
Near Video on Demand with VCR Functions	479	(2)
File Placement	481	(11)
Placing a File on a Single Disk	481	(1)
Two Alternative File Organization Strategies	482	(4)
Placing Files for Near Video on Demand	486	(1)
Placing Multiple Files on a Single Disk	487	(3)
Placing Files on Multiple Disks	490	(2)
Caching	492	(2)
Block Caching	492	(2)
File Caching	494	(1)
Disk Scheduling For Multimedia	494	(4)
Static Disk Scheduling	495	(1)
Dynamic Disk Scheduling	496	(2)
Research on Multimedia	498	(1)
Summary	499	(4)
Multiple Processor Systems	503	(80)
Multiprocessors	506	(20)
Multiprocessor Hardware	506	(7)
Multiprocessor Operating System Types	513	(3)
Multiprocessor Synchronization	516	(5)
Multiprocessor Scheduling	521	(5)
Multicomputers	526	(23)
Multicomputer Hardware	527	(4)
Low-Level Communication Software	531	(3)
User-Level Communication Software	534	(3)
Remote Procedure Call	537	(3)
Distributed Shared Memory	540	(4)
Multicomputer Scheduling	544	(1)
Load Balancing	545	(4)
Distributed Systems	549	(28)
Network Hardware	551	(2)
Network Service and Protocols	553	(5)
Document-Based Middleware	558	(1)
File System-Based Middleware	559	(6)
Shared Object-Based Middleware	565	(7)
Coordination-Based Middleware	572	(5)
Research on Multiple Processor Systems	577	(1)
Summary	577	(6)
Security	583	(1)
The Security Environment	584	(1)
Threats	584	(1)
Intruders	585	(1)
Accidental Data Loss	586	(1)
Basics of Cryptography	587	(1)
Secret-Key Cryptography	588	(1)
Public-Key Cryptography	588	(1)
One-Way Functions	589	(1)
Digital Signatures	590	(1)
User Authentication	591	(1)
Authentication Using Passwords	592	(1)
Authentication Using a Physical Object	601	(2)
Authentication Using Biometric	603	(3)
Countermeasures	606	(1)
Attacks From Inside the System	606	(1)
Trojan Horses	607	(1)
Login Spoofing	608	(1)
Logic Bombs	609	(1)
Trap Doors	610	(1)
Buffer Overflow	610	(3)
Generic Security Attacks	613	(1)
Famous Security Flaws	614	(2)
Design Principles for Security	616	(1)
Attacks From Outside the System	617	(1)
Virus Damage Scenarios	618	(1)
How Viruses Work	619	(7)
How Viruses Spread	626	(2)
Antivirus and Anti-Antivirus Techniques	628	(7)
The Internet Worm	635	(2)
Mobile Code	637	(5)
Java Security	642	(3)
Protection Mechanisms	645	(1)
Protection Domains	645	(2)
Access Control Lists	647	(3)
Capabilities	650	(3)
Trusted Systems	653	(1)
Trusted Computing Base	654	(1)
Formal Models of Secure Systems	655	(2)
Multilevel Security	657	(2)
Orange Book Security	659	(2)
Covert Channels	661	(4)
Research on Security	665	(1)
Summary	666

Excerpts

PREFACE The world has changed a great deal since the first edition of this book appeared in 1992. Computer networks and distributed systems of all kinds have become very common. Small children now roam the Internet, where previously only computer professionals went. As a consequence, this book has changed a great deal, too. The most obvious change is that the first edition was about half on single-processor operating systems and half on distributed systems. I chose that format in 1991 because few universities then had courses on distributed systems and whatever students learned about distributed systems had to be put into the operating systems course, for which this book was intended. Now most universities have a separate course on distributed systems, so it is not necessary to try to combine the two subjects into one course and one book. This book is intended for a first course on operating systems, and as such focuses mostly on traditional single-processor systems. I have coauthored two other books on operating systems. This leads to two possible course sequences. Practically-oriented sequence: Operating Systems Design and Implementation by Tanenbaum and Woodhull Distributed Systems by Tanenbaum and Van Steen Traditional sequence: Modern Operating Systems by Tanenbaum Distributed Systems by Tanenbaum and Van Steen The former sequence uses MINIX and the students are expected to experiment with MINIX in an accompanying laboratory supplementing the first course. The latter sequence does not use MINIX. Instead, some small simulators are available that can be used for student exercises during a first course using this book. These simulators can be found starting on the author's Web page:www.cs.vu.nl/~ast/by clicking on Software and supplementary material for my books. In addition to the major change of switching the emphasis to single-processor operating systems in this book, other major changes include the addition of entire chapters on computer security, multimedia operating systems, and Windows 2000, all important and timely topics. In addition, a new and unique chapter on operating system design has been added. Another new feature is that many chapters now have a section on research about the topic of the chapter. This is intended to introduce the reader to modern work in processes, memory management, and so on. These sections have numerous references to the current research literature for the interested reader. In addition, Chapter 13 has many introductory and tutorial references. Finally, numerous topics have been added to this book or heavily revised. These topics include: graphical user interfaces, multiprocessor operating systems, power management for laptops, trusted systems, viruses, network terminals, CDROM file systems, mutexes, RAID, soft timers, stable storage, fair-share scheduling, and new paging algorithms. Many new problems have been added and old ones updated. The total number of problems now exceeds 450. A solutions manual is available to professors using this book in a course. They can obtain a copy from their local Prentice Hall representative. In addition, over 250 new references to the current literature have been added to bring the book up to date. Despite the removal of more than 400 pages of old material, the book has increased in size due to the large amount of new material added. While the book is still suitable for a one-semester or two-quarter course, it is probably too long for a one-quarter or one-trimester course at most universities. For this reason, the book has been designed in a modular way. Any course on operating systems should cover chapters 1 through 6. This is basic material that every student show know. If additional time is available, additional chapters can be covered. Each of them assumes the reader has finished chapters 1 through 6, but Chaps.