Operating Systems Design and Implementation

by Tanenbaum, Andrew S; Woodhull, Albert S

• ISBN13: 9780131429383
• ISBN10: 0131429388
• Edition: 3rd
• Format: Hardcover
• Copyright: 2006-01-04
• Publisher: Pearson

Summary

"The presentation is excellent. The book should be on the desk of any serious student of operating systems."--Dr. Samuel Kohn, Thomas Edison State College "I would give the authors very high grades for their writing style. Topics are explained in a clear and understandable manner. Presentations are well organized and they flow in logical fashion. The book provides the right depth and breadth of explanations with the appropriate amount of rigor and abstraction." --Gojko Babic, Department of Computer Science and Engineering, Ohio State University The definitive, up-to-date introduction to operating systems: Core principles plus hands-on examples with the new MINIX 3 operating system The worldrs"s best-selling introductory operating systems text has been thoroughly updated to reflect the latest advances in OS design and implementation. Offering an optimal balance of theory and practice, Operating Systems: Design and Implementation, Third Edition remains the best resource for anyone seeking a deep understanding of how operating systems work. This edition includes MINIX 3, more compact, more reliable, better suited for embedded applications and, above all, even easier to teach and learn from. Using MINIX, the authors introduce virtually every core concept needed to construct a working OS: system calls, processes, IPC, scheduling, I/O, deadlocks, memory management, threads, file systems, security, and more. NEW TO THIS EDITION Newly-released, significantly-improved MINIX 3 operating system on CD-ROM: giving students hands-on experience in modifying and rebuilding a contemporary operating system Expanded and reorganized coverage of processes and communication Revised and enhanced coverage of CPU scheduling, deadlocks, file system reliability, and security Includes more than 150 end of chapter problems ABOUT THE AUTHORS Andrew S. Tanenbaum has an S.B. degree from M.I.T. and a Ph. D. from the University of California at Berkeley. He is currently a Professor of Computer Science and Vrije Universiteit in Amsterdam, the Netherlands, where, for more than 30 years, he has taught operating systems, computer organization, and networking to thousands of students. Professor Tanenbaum is the winner of the ACM Karl V. Karlstrom Outstanding Educator Award and the ACM/SIGCSE Award for Outstanding Contributions to Computer Science Education. Albert S. Woodhull is Adjunct Associate Professor of Computer Science and Biology at the School of Natural Science, Hampshire College, Amherst, MA. He also served until recently as computer system administrator for the Department of Biology in the School of Natural Science and Mathematics at the University of Massachusetts, Amherst, MA. He holds an S.B. degree from M.I.T. and a Ph.D. the University of Washington. Supported by a Fulbright grant, he has taught at the Universidad Nacional de Ingenieria and the Universidad Nacional Autonoma de Nicaragua.

Author Biography

Andrew S. Tanenbaum has a B.S. Degree from M.I.T. and a Ph.D. from the University of California at Berkeley. He is currently a Professor of Computer Science at the Vrije Universiteit in Amsterdam, The Netherlands, where he heads the Computer Systems Group. He is also Dean of the Advanced School for Computing and Imaging, an interuniversity graduate school doing research on advanced parallel, distributed, and imaging systems. Nevertheless, he is trying very hard to avoid turning into a bureaucrat.

In the past, he has done research on compilers, operating systems, networking, and local-area distributed systems. His current research focuses primarily on the design of wide-area distributed systems that scale to a billion users. These research projects have led to five books and over 85 referred papers in journals and conference proceedings.

Prof. Tanenbaum has also produced a considerable volume of software. He was the principal architect of the Amsterdam Compiler Kit, a widely-used toolkit for writing portable compilers, as well as of MINIX, a small UNIX clone intended for use in student programming labs. Together with his Ph.D. students and programmers, he helped design the Amoeba distributed operating system, a high-performance microkernel-based distributed operating system. The MINIX and Amoeba systems are now available for free via the Internet..

Prof. Tanenbaum is a Fellow of the ACM, a Fellow of the IEEE, a member of the Royal Netherlands Academy of Arts and Sciences, winner of the 1994 ACM Karl V. Karlstrom Outstanding Educator Award, and winner of the 1997 ACM/SIGCSE Award for Outstanding Contributions to Computer Science Education. He is also listed in Who’s Who in the World.

 

Albert S. Woodhull was a faculty member in the School of Natural Science, Hampshire College, Amherst, MA for many years. He has taught at the University of Massachusetts and Smith College in the US, and he has been a visiting faculty member on multiple occasions at universities in Nicaragua, supported on two of these visits by Fulbright grants. He also served as a computer and network system administrator at the University of Massachusetts. He holds an B.S. degree from M.I.T. and a Ph.D. from the University of Washington. His home page on the web is at http://minix1.woodhull.com/asw/.

 

Table of Contents

Preface	xiv
Introduction	1	(54)
What is an Operating System?	4	(2)
The Operating System as an Extended Machine	4	(1)
The Operating System as a Resource Manager	5	(1)
History of Operating Systems	6	(13)
The First Generation (1945--55) Vacuum Tubes and Plugboards	7	(1)
The Second Generation (1955--65) Transistors and Batch Systems	7	(2)
The Third Generation (1965--1980) ICs and Multiprogramming	9	(5)
The Fourth Generation (1980--Present) Personal Computers	14	(2)
History of MINIX 3	16	(3)
Operating System Concepts	19	(7)
Processes	20	(2)
Files	22	(3)
The Shell	25	(1)
System Calls	26	(16)
System Calls for Process Management	27	(4)
System Calls for Signaling	31	(2)
System Calls for File Management	33	(5)
System Calls for Directory Management	38	(2)
System Calls for Protection	40	(2)
System Calls for Time Management	42	(1)
Operating System Structure	42	(9)
Monolithic Systems	42	(3)
Layered Systems	45	(1)
Virtual Machines	46	(3)
Exokernels	49	(1)
Client-Server Model	49	(2)
Outline of the Rest of This Book	51	(1)
Summary	51	(4)
Processes	55	(166)
Introduction to Processes	55	(14)
The Process Model	56	(1)
Process Creation	57	(2)
Process Termination	59	(1)
Process Hierarchies	60	(1)
Process States	60	(2)
Implementation of Processes	62	(2)
Threads	64	(5)
Interprocess Communication
Race Conditions	69	(1)
Critical Sections	70	(1)
Mutual Exclusion with Busy Waiting	71	(5)
Sleep and Wakeup	76	(2)
Semaphores	78	(3)
Mutexes	81	(1)
Monitors	81	(4)
Message Passing	85	(3)
Classical IPC Problems	88	(5)
The Dining Philosophers Problem	89	(3)
The Readers and Writers Problem	92	(1)
Scheduling	93	(19)
Introduction to Scheduling	94	(5)
Scheduling in Batch Systems	99	(3)
Scheduling in Interactive Systems	102	(7)
Scheduling in Real-Time Systems	109	(1)
Policy versus Mechanism	110	(1)
Thread Scheduling	110	(2)
Overview of Processes in MINIX 3	112	(13)
The Internal Structure of MINIX 3	112	(4)
Process Management in MINIX 3	116	(4)
Interprocess Communication in MINIX 3	120	(2)
Process Scheduling in MINIX 3	122	(3)
Implementation of Processes in MINIX 3	125	(67)
Organization of the MINIX 3 Source Code	125	(3)
Compiling and Runniing MINIX 3	128	(2)
The Common Header Files	130	(8)
The MINIX 3 Header Files	138	(8)
Process Data Structures and Header Files	146	(10)
Bootstrapping MINIX 3	156	(4)
System Initialization	160	(7)
Interrupt Handling in MINIX 3	167	(11)
Interprocess Communication in MINIX 3	178	(4)
Scheduling in MINIX 3	182	(3)
Hardware-Dependent Kernel Support	185	(5)
Utilities and the Kernel Library	190	(2)
The System Task in MINIX 3	192	(12)
Overview of the System Task	194	(3)
Implementation of the System Task	197	(3)
Implementation of the System Libarary	200	(4)
The Clock Task in MINIX 3	204	(10)
Clock Hardware	204	(2)
Clock Software	206	(2)
Overview of the Clock Driver in MINIX 3	208	(4)
Implementation of the Clock Driver in MINIX 3	212	(2)
Summary	214	(7)
Input/Output	221	(152)
Principles of I/O Hardware	222	(7)
I/O Devices	223	(2)
Device Controllers
Memory-Mapped I/O	225	(1)
Interrupts	226	(1)
Direct Memory Access	227	(2)
Principles of I/O Software	229	(8)
Goals of the I/O Software	229	(2)
Interrupt Handlers	231	(1)
Device Drivers	231	(2)
Device-Independent I/O Software	233	(3)
User-Space I/O Software	236	(1)
Deadlocks	237	(15)
Resources	238	(1)
Principles of Deadlock	239	(3)
The Ostrich Algorithm	242	(2)
Detection and Recovery	244	(1)
Deadlock Prevention	245	(2)
Deadlock Avoidance	247	(5)
Overview of I/O in MINIX 3	252	(9)
Interrupt Handlers in MINIX 3	252	(4)
Device Drivers in MINIX 3	256	(3)
Device-Independent I/O Software in MINIX 3	259	(1)
User-level I/O Software in MINIX 3	260	(1)
Deadlock Handling in MINIX 3	260	(1)
Block Devices in MINIX 3	261	(10)
Overview of Block Device Drivers in MINIX 3	262	(3)
Common Block Device Driver Software	265	(4)
The Driver Library	269	(2)
Ram Disks	271	(7)
RAM Disk Hardware and Software	271	(2)
Overview of the RAM Disk Driver in MINIX 3	273	(1)
Implementation of the RAM Disk Driver in MINIX 3	274	(4)
Disks	278	(24)
Disk Hardware	278	(2)
RAID	280	(1)
Disk Software	281	(6)
Overview of the Hard Disk Driver in MINIX 3	287	(3)
Implementation of the Hard Disk Driver in MINIX 3	290	(10)
Floppy Disk Handling	300	(2)
Terminals	302	(64)
Terminal Hardware	303	(4)
Terminal Software	307	(9)
Overview of the Terminal Driver in MINIX 3	316	(15)
Implementation of the Device-Independent Terminal Driver	331	(19)
Implementation of the Keyboard Driver	350	(7)
Implementation of the Display Driver	357	(9)
Summary	366	(7)
Memory Management	373	(108)
Basic Memory Management	374	(4)
Monoprogramming without Swapping or Paging	374	(1)
Multiprogramming with Fixed Partitions	375	(2)
Relocation and Protection	377	(1)
Swapping	378	(5)
Memory Management with Bitmaps	380	(1)
Memory Management with Linked Lists	381	(2)
Virtual Memory	383	(13)
Paging	384	(4)
Page Tables	388	(4)
TLBs---Translation Lookaside Buffers	392	(3)
Inverted Page Tables	395	(1)
Page Replacement Algorithms	396	(8)
The Optimal Page Replacement Algorithm	397	(1)
The Not Recently Used Page Replacement Algorithm	398	(1)
The First-In, First-Out (FIFO) Page Replacement Algorithm	399	(1)
The Second Chance Page Replacement Algorithm	399	(1)
The Clock Page Replacement Algorithm	400
The Least Recently Used (LRU) Page Replacement Algorithm	40	(361)
Simulating LRU in Software	401	(3)
Design Issues for Paging Systems	404	(6)
The Working Set Model	404	(2)
Local versus Global Allocation Policies	406	(2)
Page Size	408	(2)
Virtual Memory Interface	410	(1)
Segmentation	410	(10)
Implementation of Pure Segmentation	414	(1)
Segmentation with Paging: The Intel Pentium	415	(5)
Overview of the MINIX 3 Process Manager	420	(27)
Memory Layout	422	(3)
Message Handling	425	(1)
Process Manager Data Structures and Algorithms	426	(6)
The FORK, EXIT, and WAIT System Calls	432	(1)
The EXEC System Call	433	(4)
The BRK System Call	437	(1)
Signal Handling	438	(8)
Other System Calls	446	(1)
Implementation of the MINIX 3 Process Manager	447	(28)
The Header Files and Data Structures	447	(3)
The Main Program	450	(5)
Implementation of FORK, EXIT, and Wait	455	(3)
Implementation of EXEC	458	(3)
Implementation of BRK	461	(1)
Implementation of Signal Handling	462	(9)
Implementation of Other System Calls	471	(2)
Memory Management Utilities	473	(2)
Summary	475	(6)
File Systems	481	(130)
Files	482	(9)
File Naming	482	(2)
File Structure	484	(1)
File Types	485	(3)
File Access	488	(1)
File Attributes	488	(2)
File Operations	490	(1)
Directories	491	(6)
Simple Directories	491	(1)
Hierarchical Directory Systems	492	(1)
Path Names	493	(3)
Directory Operations	496	(1)
File System Implementation	497	(29)
File System Layout	497	(2)
Implementing Files	499	(3)
Implementing Directories	502	(7)
Disk Space Management	509	(3)
File System Reliability	512	(7)
File System Performance	519	(5)
Log-Structured File Systems	524	(2)
Security	526	(11)
The Security Environment	526	(5)
Generic Security Attacks	531	(1)
Design Principles for Security	532	(1)
User Authentication	533	(4)
Protection Mechanisms	537	(11)
Protection Domains	537	(2)
Access Control Lists	539	(3)
Capabilities	542	(3)
Covert Channels	545	(3)
Overview of the MINIX 3 File System	548	(18)
Messages	549	(1)
File System Layout	549	(4)
Bitmaps	553	(2)
I-Nodes	555	(2)
The Block Cache	557	(2)
Directories and Paths	559	(2)
File Descriptors	561	(2)
File Locking	563	(1)
Pipes and Special Files	563	(2)
An Example: The Read System Call	565	(1)
Implementation of the MINIX 3 File System	566	(45)
Header Files and Global Data Structures	566	(4)
Table Management	570	(9)
The Main Program	579	(4)
Operations on Individual Files	583	(8)
Directories and Paths	591	(5)
Other System Calls	596	(1)
The I/O Device Interface	597	(6)
Additional System Call Support	603	(2)
File System Utilities	605	(1)
Other MINIX 3 Components	606	(1)
Summary	606	(5)
Reading List and Bibliography	611	(424)
Suggestions for Further Reading	611	(7)
Introduction and General Works	611	(3)
Processes	614	(1)
Input/Output	614	(1)
Memory Management	615	(1)
File Systems	616	(2)
Alphabetical Bibliography	618	(11)
APPENDICES
A. Installing MINIX 3	629	(10)
B. MINIX 3 Source Code Listing	639	(394)
C. Index to Files	1033	(2)
Index	1035