Modern Operating Systems

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 at the Vrije Universiteit in Amsterdam, The Netherlands, where he is head of the Computer Systems Department. He is also the 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. This research is being done together with Dr. Maarten van Steen. Together, all his research projects have led to over 90 refereed papers in journals and conference proceedings and five books. 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. His Ph.D. students have gone on to greater glory after getting their degrees. He is very proud of them. In this respect he resembles a mother hen. 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. His home page on the World Wide Web can be found at URL http://www.cs.vu.nl/~ast/.

1 INTRODUCTION

1.1 WHAT IS AN OPERATING SYSTEM?

1.1.1 The Operating System as an Extended Machine

1.1.2 The Operating System as a Resource Manager

1.2 HISTORY OF OPERATING SYSTEMS

1.2.1 The First Generation

1.2.2 The Second Generation

1.2.3 The Third Generation

1.2.4 The Fourth Generation

1.3 COMPUTER HARDWARE REVIEW

1.3.1 Processors

1.3.2 Memory

1.3.3 Disks

1.3.4 Tapes

1.3.5 I/O Devices

1.3.6 Buses

1.3.7 Booting the Computer

1.4 THE OPERATING SYSTEM ZOO

1.4.1 Mainframe Operating Systems

1.4.2 Server Operating Systems

1.4.3 Multiprocessor Operating Systems

1.4.4 Personal Computer Operating Systems

1.4.5 Handheld Computer Operating Systems

1.4.6 Embedded Operating Systems.

1.4.7 Sensor Node Operating Systems

1.4.8 Real-Time Operating Systems

1.4.9 Smart Card Operating Systems

1.5 OPERATING SYSTEM CONCEPTS

1.5.1 Processes

1.5.2 Address Spaces

1.5.3 Files

1.5.4 Input/Output

1.5.5 Protection

1.5.6 The Shell

1.5.7 Ontogeny Recapitulates Phylogeny

1.6 SYSTEM CALLS

1.6.1 System Calls for Process Management

1.6.2 System Calls for File Management

1.6.3 System Calls for Directory Management

1.6.4 Miscellaneous System Calls

1.6.5 The Windows Win32 API

1.7 OPERATING SYSTEM STRUCTURE

1.7.1 Monolithic Systems

1.7.2 Layered Systems

1.7.3 Microkernels

1.7.4 Client-Server Model

1.7.5 Virtual Machines

1.7.6 Exokernels

1.8 THE WORLD ACCORDING TO C

1.8.1 The C Language

1.8.2 Header Files

1.8.3 Large Programming Projects

1.8.4 The Model of Run Time

1.9 RESEARCH ON OPERATING SYSTEMS

1.10 OUTLINE OF THE REST OF THIS BOOK

1.11 METRIC UNITS

1.12 SUMMARY

 

2 PROCESSES AND THREADS

2.1 PROCESSES

2.1.1 The Process Model

2.1.2 Process Creation

2.1.3 Process Termination

2.1.4 Process Hierarchies

2.1.5 Process States

2.1.6 Implementation of Processes

2.1.7 Modeling Multiprogramming

2.2 THREADS

2.2.1 Thread Usage

2.2.2 The Classical Thread Model

2.2.3 POSIX Threads

2.2.4 Implementing Threads in User Space

2.2.5 Implementing Threads in the Kernel

2.2.6 Hybrid Implementations

2.2.7 Scheduler Activations

2.2.8 Pop-Up Threads

2.2.9 Making Single-Threaded Code Multithreaded

2.3 INTERPROCESS COMMUNICATION

2.3.1 Race Conditions

2.3.2 Critical Regions

2.3.3 Mutual Exclusion with Busy Waiting

2.3.4 Sleep and Wakeup

2.3.5 Semaphores

2.3.6 Mutexes

2.3.7 Monitors

2.3.8 Message Passing

2.3.9 Barriers

2.4 SCHEDULING

2.4.1 Introduction to Scheduling

2.4.2 Scheduling in Batch Systems

2.4.3 Scheduling in Interactive Systems

2.4.4 Scheduling in Real-Time Systems

2.4.5 Policy versus Mechanism

2.4.6 Thread Scheduling

2.5 CLASSICAL IPC PROBLEMS

2.5.1 The Dining Philosophers Problem

2.5.2 The Readers and Writers Problem

2.6 RESEARCH ON PROCESSES AND THREADS

2.7 SUMMARY

 

3 MEMORY MANAGEMENT

3.1 NO MEMORY ABSTRACTION

3.2 A MEMORY ABSTRACTION: ADDRESS SPACES

3.2.1 The Notion of an Address Space

3.2.2 Swapping

3.2.3 Managing Free Memory

3.3 VIRTUAL MEMORY

3.3.1 Paging

3.3.2 Page Tables

3.3.3 Speeding Up Paging

3.3.4 Page Tables for Large Memories

3.4 PAGE LACEMENT ALGORITHMS

3.4.1 The Optimal Page Replacement Algorithm

3.4.2 The Not Recently Used Page Replacement Algorithm

3.4.3 The First-In, First-Out

3.4.4 The Second Chance Page Replacement Algorithm

3.4.5 The Clock Page Replacement Algorithm

3.4.6 The Least Recently Used

3.4.7 Simulating LRU in Software

3.4.8 The Working Set Page Replacement Algorithm

3.4.9 The WSClock Page Replacement Algorithm

3.4.10 Summary of Page Replacement Algorithms

3.5 DESIGN ISSUES FOR PAGING SYSTEMS

3.5.1 Local versus Global Allocation Policies

3.5.2 Load Control

3.5.3 Page Size

3.5.4 Separate Instruction and Data Spaces

3.5.5 Shared Pages

3.5.6 Shared Libraries

3.5.7 Mapped Files

3.5.8 Cleaning Policy

3.5.9 Virtual Memory Interface

3.6 IMPLEMENTATION ISSUES

3.6.1 Operating System Involvement with Paging

3.6.2 Page Fault Handling

3.6.3 Instruction Backup

3.6.4 Locking Pages in Memory

3.6.5 Backing Store

3.6.6 Separation of Policy and Mechanism

3.7 SEGMENTATION

3.7.1 Implementation of Pure Segmentation

3.7.2 Segmentation with Paging: MULTICS

3.7.3 Segmentation with Paging: The Intel Pentium

3.8 RESEARCH ON MEMORY MANAGEMENT

3.9 SUMMARY

 

4 FILE SYSTEMS

4.1 FILES

4.1.1 File Naming

4.1.2 File Structure

4.1.3 File Types

4.1.4 File Access

4.1.5 File Attributes

4.1.6 File Operations

4.1.7 An Example Program Using File System Calls

4.2 DIRECTORIES

4.2.1 Single-Level Directory Systems

4.2.2 Hierarchical Directory Systems

4.2.3 Path Names

4.2.4 Directory Operations

4.3 FILE SYSTEM IMPLEMENTATION

4.3.1 File System Layout

4.3.2 Implementing Files

4.3.3 Implementing Directories

4.3.4 Shared Files

4.3.5 Log-Structured File Systems

4.3.6 Journaling File Systems

4.3.7 Virtual File Systems

4.4 FILE SYSTEM MANAGEMENT AND OPTIMIZATION

4.4.1 Disk Space Management

4.4.2 File System Backups

4.4.3 File System Consistency

4.4.4 File System Performance

4.4.5 Defragmenting Disks

4.5 EXAMPLE FILE SYSTEMS

4.5.1 CD-ROM File Systems

4.5.2 The MS-DOS File System

4.5.3 The UNIX V7 File System

4.6 RESEARCH ON FILE SYSTEMS

4.7 SUMMARY

 

5 INPUT/OUTPUT

5.1 PRINCIPLES OF I/O HARDWARE

5.1.1 I/O Devices

5.1.2 Device Controllers

5.1.3 Memory-Mapped I/O

5.1.4 Direct Memory Access

5.1.5 Interrupts Revisited

5.2 PRINCIPLES OF I/O SOFTWARE

5.2.1 Goals of the I/O Software

5.2.2 Programmed I/O

5.2.3 Interrupt-Driven I/O

5.2.4 I/O Using DMA

5.3 I/O SOFTWARE LAYERS

5.3.1 Interrupt Handlers

5.3.2 Device Drivers

5.3.3 Device-Independent I/O Software

5.3.4 User-Space I/O Software

5.4 DISKS

5.4.1 Disk Hardware

5.4.2 Disk Formatting

5.4.3 Disk Arm Scheduling Algorithms

5.4.4 Error Handling

5.4.5 Stable Storage

5.5 CLOCKS

5.5.1 Clock Hardware

5.5.2 Clock Software

5.5.3 Soft Timers

5.6 USER INTERFACES: KEYBOARD, MOUSE, MONITOR

5.6.1 Input Software

5.6.2 Output Software

5.7 THIN CLIENTS

5.8 POWER MANAGEMENT

5.8.1 Hardware Issues

5.8.2 Operating System Issues:

5.8.3 Application Program Issues

5.9 RESEARCH ON INPUT/OUTPUT

5.10 SUMMARY

 

6 DEADLOCKS

6.1 RESOURCES

6.1.1 Preemptable and Nonpreemptable Resources

6.1.2 Resource Acquisition

6.2 INTRODUCTION TO DEADLOCKS

6.2.1 Conditions for Resource Deadlocks

6.2.2 Deadlock Modeling

6.3 THE OSTRICH ALGORITHM

6.4 DEADLOCK DETECTION AND RECOVERY

6.4.1 Deadlock Detection with One Resource of Each Type

6.4.2 Deadlock Detection with Multiple Resources of Each Type

6.4.3 Recovery from Deadlock

6.5 DEADLOCK AVOIDANCE

6.5.1 Resource Trajectories

6.5.2 Safe and Unsafe States

6.5.3 The Banker’s Algorithm for a Single Resource

6.5.4 The Banker’s Algorithm for Multiple Resources

6.6 DEADLOCK PREVENTION

6.6.1 Attacking the Mutual Exclusion Condition

6.6.2 Attacking the Hold and Wait Condition

6.6.3 Attacking the No Preemption Condition

6.6.4 Attacking the Circular Wait Condition

6.7 OTHER ISSUES

6.7.1 Two-Phase Locking

6.7.2 Communication Deadlocks

6.7.3 Livelock

6.7.4 Starvation

6.8 RESEARCH ON DEADLOCKS

6.9 SUMMARY

 

7 MULTIMEDIA OPERATING SYSTEMS

7.1 INTRODUCTION TO MULTIMEDIA

7.2 MULTIMEDIA FILES

7.2.1 Video Encoding

7.2.2 Audio Encoding

7.3 VIDEO COMPRESSION

7.3.1 The JPEG Standard

7.3.2 The MPEG Standard

7.4 AUDIO COMPRESSION

7.5 MULTIMEDIA PROCESS SCHEDULING

7.5.1 Scheduling Homogeneous Processes

7.5.2 General Real-Time Scheduling

7.5.3 Rate Monotonic Scheduling

7.5.4 Earliest Deadline First Scheduling

7.6 MULTIMEDIA FILE SYSTEM PARADIGMS

7.6.1 VCR Control Functions

7.6.2 Near Video on Demand

7.6.3 Near Video on Demand with VCR Functions

7.7 FILE PLACEMENT

7.7.1 Placing a File on a Single Disk

7.7.2 Two Alternative File Organization Strategies

7.7.3 Placing Files for Near Video on Demand

7.7.4 Placing Multiple Files on a Single Disk

7.7.5 Placing Files on Multiple Disks

7.8 CACHING

7.8.1 Block Caching

7.8.2 File Caching

7.9 DISK SCHEDULING FOR MULTIMEDIA

7.9.1 Static Disk Scheduling

7.9.2 Dynamic Disk Scheduling

7.10 RESEARCH ON MULTIMEDIA

7.11 SUMMARY

 

8 MULTIPLE PROCESSOR SYSTEMS

8.1 MULTIPROCESSORS

8.1.1 Multiprocessor Hardware

8.1.2 Multiprocessor Operating System Types

8.1.3 Multiprocessor Synchronization

8.1.4 Multiprocessor Scheduling

8.2 MULTICOMPUTERS

8.2.1 Multicomputer Hardware

8.2.2 Low-Level Communication Software

8.2.3 User-Level Communication Software

8.2.4 Remote Procedure Call

8.2.5 Distributed Shared Memory

8.2.6 Multicomputer Scheduling

8.2.7 Load Balancing

8.3 VIRTUALIZATION

8.3.1 Requirements for Virtualization

8.3.2 Type 1 Hypervisors

8.3.3 Type 2 Hypervisors

8.3.4 Paravirtualization

8.3.5 Memory Virtualization

8.3.6 I/O Virtualization

8.3.7 Virtual Appliances

8.3.8 Virtual Machines on Multicore CPUs

8.3.9 Licensing Issues

8.4 DISTRIBUTED SYSTEMS

8.4.1 Network Hardware

8.4.2 Network Services and Protocols

8.4.3 Document-Based Middleware

8.4.4 File System-Based Middleware

8.4.5 Object-Based Middleware

8.4.6 Coordination-Based Middleware

8.5 RESEARCH ON MULTIPLE PROCESSOR SYSTEMS

8.6 SUMMARY

 

9 SECURITY

9.1 THE SECURITY ENVIRONMENT

9.1.1 Threats

9.1.2 Intruders

9.1.3 Accidental Data Loss

9.2 BASICS OF CRYPTOGRAPHY

9.2.1 Secret-Key Cryptography

9.2.2 Public-Key Cryptography

9.2.3 One-Way Functions

9.2.4 Digital Signatures

9.2.5 Trusted Platform Module

9.3 PROTECTION MECHANISMS

9.3.1 Protection Domains

9.3.2 Access Control Lists

9.3.3 Capabilities

9.3.4 Trusted systems

9.3.5 Trusted Computing Base

9.3.6 Formal Models of Secure Systems

9.3.7 Multilevel Security

9.3.8 Covert Channels

9.4 AUTHENTICATION

9.4.1 Authentication Using Passwords

9.4.2 Authentication Using a Physical Object

9.4.3 Authentication Using Biometrics

9.5 INSIDER ATTACKS

9.5.1 Logic Bombs

9.5.2 Trap Doors

9.5.3 Login Spoofing

9.6 EXPLOITING CODE BUGS

9.6.1 Buffer Overflow Attacks

9.6.2 Format String Attacks

9.6.3 Return to libc Attacks

9.6.4 Integer Overflow Attacks

9.6.5 Code Injection Attacks

9.6.6 Privilege Escalation Attacks

9.7 MALWARE

9.7.1 Trojan Horses

9.7.2 Viruses

9.7.3 Worms

9.7.4 Spyware

9.7.5 Rootkits

9.8 DEFENSES

9.8.1 Firewalls

9.8.2 Antivirus and Anti-Antivirus Techniques

9.8.3 Code Signing

9.8.4 Jailing

9.8.5 Model-Based Intrusion Detection

9.8.6 Encapsulating Mobile Code

9.8.7 Java Security

9.9 RESEARCH ON SECURITY

9.10 SUMMARY

 

10 CASE STUDY 1: LINUX

10.1 HISTORY OF UNIX AND LINUX

10.1.1 UNICS

10.1.2 PDP-11 UNIX

10.1.3 Portable UNIX

10.1.4 Berkeley UNIX

10.1.5 Standard UNIX

10.1.6 MINIX

10.1.7 Linux

10.2 OVERVIEW OF LINUX

10.2.1 Linux Goals

10.2.2 Interfaces to Linux

10.2.3 The Shell

10.2.4 Linux Utility Programs

10.2.5 Kernel Structure

10.3 PROCESSES IN LINUX

10.3.1 Fundamental Concepts

10.3.2 Process Management System Calls in Linux

10.3.3 Implementation of Processes and Threads in Linux

10.3.4 Scheduling in Linux

10.3.5 Booting Linux

10.4 MEMORY MANAGEMENT IN LINUX

10.4.1 Fundamental Concepts

10.4.2 Memory Management System Calls in Linux

10.4.3 Implementation of Memory Management in Linux

10.4.4 Paging in Linux

10.5 INPUT/OUTPUT IN LINUX

10.5.1 Fundamental Concepts

10.5.2 Networking

10.5.3 Input/Output System Calls in Linux

10.5.4 Implementation of Input/Output in Linux

10.5.5 Modules in Linux

10.6 THE LINUX FILE SYSTEM

10.6.1 Fundamental Concepts

10.6.2 File System Calls in Linux

10.6.3 Implementation of the Linux File System

10.6.4 NFS: The Network File System

10.7 SECURITY IN LINUX

10.7.1 Fundamental Concepts

10.7.2 Security System Calls in Linux

10.7.3 Implementation of Security in Linux

10.8 SUMMARY

 

11 CASE STUDY 2: WINDOWS VISTA

11.1 HISTORY OF WINDOWS VISTA

11.1.1 1980s: MS-DOS

11.1.2 1990s: MS-DOS-based Windows

11.1.3 2000s: NT-based Windows

11.1.4 Windows Vista

11.2 PROGRAMMING WINDOWS VISTA

11.2.1 The Native NT Application Programming Interface

11.2.2 The Win32 Application Programming Interface

11.2.3 The Windows Registry

11.3 SYSTEM STRUCTURE

11.3.1 Operating System Structure

11.3.2 Booting Windows Vista

11.3.3 Implementation of the Object Manager

11.3.4 Subsystems, DLLs, and User-mode Services

11.4 PROCESSES AND THREADS IN WINDOWS VISTA

11.4.1 Fundamental Concepts

11.4.2 Job, Process, Thread and Fiber Management API Calls

11.4.3 Implementation of Processes and Threads

11.5 MEMORY MANAGEMENT

11.5.1 Fundamental Concepts

11.5.2 Memory Management System Calls

11.5.3 Implementation of Memory Management

11.6 CACHING IN WINDOWS VISTA

11.7 INPUT/OUTPUT IN WINDOWS VISTA

11.7.1 Fundamental Concepts

11.7.2 Input/Output API Calls

11.7.3 Implementation of I/O

11.8 THE WINDOWS NT FILE SYSTEM

11.8.1 Fundamental Concepts

11.8.2 Implementation of the NT File System

11.9 SECURITY IN WINDOWS VISTA

11.9.1 Fundamental Concepts

11.9.2 Security API Calls

11.9.3 Implementation of Security

11.10 SUMMARY

 

12 CASE STUDY 3: SYMBIAN OS

12.1 THE HISTORY OF SYMBIAN OS

12.1.1 Symbian OS Roots: Psion and EPOC

12.1.2 Symbian OS Version 6

12.1.3 Symbian OS Version 7

12.1.4 Symbian OS Today

12.2 AN OVERVIEW OF SYMBIAN OS

12.2.1 Object Orientation

12.2.2 Microkernel Design

12.2.3 The Symbian OS Nanokernel

12.2.4 Client/Server Resource Access

12.2.5 Features of a Larger Operating System

12.2.6 Communication and Multimedia

12.3 PROCESSES AND THREADS IN SYMBIAN OS

12.3.1 Threads and Nanothreads

12.3.2 Processes

12.3.3 Active Objects

12.3.4 Interprocess Communication

12.4 MEMORY MANAGEMENT

12.4.1 Systems with No Virtual Memory

12.4.2 How Symbian OS Addresses Memory

12.5 INPUT AND OUTPUT

12.5.1 Device Drivers

12.5.2 Kernel Extensions

12.5.3 Direct Memory Access

12.5.4 Special Case: Storage Media

12.5.5 Blocking I/O

12.5.6 Removable Media

12.6 STORAGE SYSTEMS

12.6.1 File systems for Mobile Devices

12.6.2 Symbian OS File systems

12.6.3 File system Security and Protection

12.7 SECURITY IN SYMBIAN OS

12.8 COMMUNICATION IN SYMBIAN OS

12.8.1 Basic Infrastructure

12.8.2 A Closer Look at the Infrastructure

12.9 SUMMARY

 

13 OPERATING SYSTEMS DESIGN

13.1 THE NATURE OF THE DESIGN PROBLEM

13.1.1 Goals

13.1.2 Why is it Hard to Design an Operating System?

13.2 INTERFACE DESIGN

13.2.1 Guiding Principles

13.2.2 Paradigms

13.2.3 The System Call Interface

13.3 IMPLEMENTATION

13.3.1 System Structure

13.3.2 Mechanism versus Policy

13.3.3 Orthogonality

13.3.4 Naming

13.3.5 Binding Time

13.3.6 Static versus Dynamic Structures

13.3.7 Top-Down versus Bottom-Up Implementation

13.3.8 Useful Techniques

13.4 PERFORMANCE

13.4.1 Why Are Operating Systems Slow?

13.4.2 What Should Be Optimized?

13.4.3 Space-Time Trade-offs

13.4.4 Caching

13.4.5 Hints

13.4.6 Exploiting Locality

13.4.7 Optimize the Common Case

13.5 PROJECT MANAGEMENT

13.5.1 The Mythical Man Month

13.5.2 Team Structure

13.5.3 The Role of Experience

13.5.4 No Silver Bullet

13.6 TRENDS IN OPERATING SYSTEM DESIGN

13.6.1 Virtualization

13.6.2 Multicore Chips

13.6.3 Large Address Space Operating Systems

13.6.4 Networking

13.6.5 Parallel and Distributed Systems

13.6.6 Multimedia

13.6.7 Battery-Powered Computers

13.6.8 Embedded Systems

13.6.9 Sensor Nodes

13.7 SUMMARY

 

14 READING LIST AND BIBLIOGRAPHY

14.1 SUGGESTIONS FOR FURTHER READING

14.1.1 Introduction and General Works

14.1.2 Processes and Threads

14.1.3 Memory Management

14.1.4 Input/Output

14.1.5 File Systems

14.1.6 eadlocks

14.1.7 Multimedia Operating Systems

14.1.8 Multiple Processor Systems

14.1.9 ecurity

14.1.10 Linux

14.1.11 Windows Vista

14.1.12 The Symbian OS

14.1.13 Design Principles

14.2 ALPHABETICAL BIBLIOGRAPHY

 

INDEX