Operating Systems: Design and Implementation

PREFACE
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 (1945-1955): Vacuum Tubes and Plugboards
........1.2.2 The Second Generation (1955-1965): Transistors and Batch Systems
........1.2.3 The Third Generation (1965-1980): ICs and Multiprogramming
........1.2.4 The Fourth Generation (1980-1990): Personal Computers
........1.2.5 History of MINIX
....1.3 OPERATING SYSTEM CONCEPTS
........1.3.1 Processes
........1.3.2 Files
........1.3.3 The Shell
....1.4 SYSTEM CALLS
........1.4.1 System Calls for Process Management
........1.4.2 System Calls for Signaling
........1.4.3 System Calls for File Management
........1.4.4 System Calls for Directory Management
........1.4.5 System Calls for Protection
........1.4.6 System Calls for Time Management
....1.5 OPERATING SYSTEM STRUCTURE
........1.5.1 Monolithic Systems
........1.5.2 Layered Systems
........1.5.3 Virtual Machines
........1.5.4 Client-Server Model
....1.6 OUTLINE OF THE REST OF THIS BOOK
....1.7 SUMMARY
2. PROCESSES
....2.1 INTRODUCTION TO PROCESSES
........2.1.1 The Process Model
........2.1.2 Implementation of Processes
....2.2 INTERPROCESS COMMUNICATION
........2.2.1 Race Conditions
........2.2.2 Critical Sections
........2.2.3 Mutual Exclusion with Busy Waiting
........2.2.4 Sleep and Wakeup
........2.2.5 Semaphores
........2.2.6 Event Counters
........2.2.7 Monitors
........2.2.8 Message Passing
........2.2.9 Equivalence of Primitives
....2.3 CLASSICAL IPC PROBLEMS
........2.3.1 The Dining Philosophers Problem
........2.3.2 The Readers and Writers Problem
....2.4 PROCESS SCHEDULING
........2.4.1 Round Robin Scheduling
........2.4.2 Priority Scheduling
........2.4.3 Multiple Queues
........2.4.4 Shortest Job First
........2.4.5 Policy-Driven Scheduling
........2.4.6 Two-level Scheduling
....2.5 OVERVIEW OF PROCESSES IN MINIX
........2.5.1 The Internal Structure of MINIX
........2.5.2 Process Management in MINIX
........2.5.3 Interprocess Communication in MINIX
........2.5.4 Process Scheduling in MINIX
....2.6 IMPLEMENTATION OF PROCESSES IN MINIX
........2.6.1 Organization of the MINIX Source Code
........2.6.2 The Common Header Files
........2.6.3 Process Data Structures and Header Files
........2.6.4 System Initialization
........2.6.5 Interrupt Handling in MINIX
........2.6.6 The Kernel’s Assembly Code Utilities
........2.6.7 Interprocess Communication in MINIX
........2.6.8 Scheduling in MINIX
....2.7 SUMMARY
3. INPUT/OUTPUT
....3.1 PRINCIPLES OF NO HARDWARE
........3.1.1 I/O Devices
........3.1.2 Device Controllers
....3.2 PRINCIPLES OF I/O SOFTWARE
........3.2.1 Goals of the I/O Software
........3.2.2 Interrupt Handlers
........3.2.3 Device Drivers
........3.2.4 Device-Independent I/O Software
........3.2.5 User-Space I/O Software
....3.3 DEADLOCKS
........3.3.1 Resources
........3.3.2 Deadlock Modeling
........3.3.3 The Ostrich Algorithm
........3.3.4 Detection and Recovery
........3.3.5 Deadlock Prevention
........3.3.6 Deadlock Avoidance
....3.4 OVERVIEW OF I/O IN MINIX
........3.4.1 Interrupt Handlers in MINIX
........3.4.2 Device Drivers in MINIX
........3.4.3 Device-Independent I/O Software in MINIX
........3.4.4 User—level I/O Software in MINIX
........3.4.5 Deadlock Handling in MINIX
....3.5 RAM DISKS
........3.5.1 RAM Disk Hardware and Software
........3.5.2 Overview of the RAM Disk Driver in MINIX
........3.5.3 Implementation of the RAM Disk Driver in MINIX
....3.6 DISKS
........3.6.1 Disk Hardware
........3.6.2 Disk Software
........3.6.3 Overview of the Floppy Disk Driver in MINIX
........3.6.4 Implementation of the Floppy Disk Driver in MINIX
....3.7 CLOCKS
........3.7.1 Clock Hardware
........3.7.2 Clock Software
........3.7.3 Overview of the Clock Driver in MINIX
........3.7.4 Implementation of the Clock Driver in MINIX
....3.8 TERMINALS
........3.8.1 Terminal Hardware
........3.8.2 Terminal Software
........3.8.3 Overview of the Terminal Driver in MINIX
........3.8.4 Implementation of the Terminal Driver in MINIX
....3.9 THE SYSTEM TASK IN MINIX
....3.10 SUMMARY
4. MEMORY MANAGEMENT
....4.1 MEMORY MANAGEMENT WITHOUT SWAPPING OR PAGING
........4.1.1 Monoprogramming without Swapping or Paging
........4.1.2 Multiprogramming and Memory Usage
........4.1.3 Multiprogramming with Fixed Partitions
....4.2 SWAPPING
........4.2.1 Multiprogramming with Variable Partitions
........4.2.2 Memory Management with Bit Maps
........4.2.3 Memory Management with Linked Lists
........4.2.4 Memory Management with the Buddy System
........4.2.5 Allocation of Swap Space
........4.2.6 Analysis of Swapping Systems
....4.3 VIRTUAL MEMORY
........4.3.1 Paging
........4.3.2 Segmentation
....4.4 PAGE REPLACEMENT ALGORITHMS
........4.4.1 Optimal Page Replacement
........4.4.2 Not-Recently-Used Page Replacement
........4.4.3 First—In First-Out Page Replacement
........4.4.4 Least Recently Used Page Replacement
........4.4.5 Simulating LRU in Software
....4.5 DESIGN ISSUES FOR PAGING SYSTEMS
........4.5.1 The Working Set Model
........4.5.2 Local versus Global Allocation Policies
........4.5.3 Page Size
........4.5.4 Implementation Issues
....4.6 OVERVIEW OF MEMORY MANAGEMENT IN MINIX
........4.6.1 Memory Layout
........4.6.2 Message Handling
........4.6.3 Memory Manager Data Structures and Algorithms
........4.6.4 The FORK, EXIT, and WAIT System Calls
........4.6.5 The EXEC System Call
........4.6.6 The BRK System Call
........4.6.7 Signal Handling
........4.6.8 Other System Calls
....4.7 IMPLEMENTATION OF MEMORY MANAGEMENT IN MINIX
........4.7.1 The Header Files
........4.7.2 The Main Program
........4.7.3 Implementation of FORK, EXIT, and WAIT
........4.7.4 Implementation of EXEC
........4.7.5 Implementation of BRK
........4.7.6 Implementation of Signal Handling
........4.7.7 Implementation of the Other System Calls
........4.7.8 Memory Manager Utilities
....4.8 SUMMARY
5. FILE SYSTEMS
....5.1 THE USER VIEW OF THE FILE SYSTEM
........5.1.1 File Basics
........5.1.2 Directories
....5.2 FILE SYSTEM DESIGN
........5.2.1 Disk Space Management
........5.2.2 File Storage
........5.2.3 Directory Structure
........5.2.4 Shared Files
........5.2.5 File System Reliability
........5.2.6 File System Performance
....5.3 FILE SERVERS
........5.3.1 Interface Level
........5.3.2 Atomic Update
........5.3.3 Concurrency Control
........5.3.4 Transactions
........5.3.5 Replicated Files
....5.4 SECURITY
........5.4.1 The Security Environment
........5.4.2 Famous Security Flaws
........5.4.3 Generic Security Attacks
........5.4.4 Design Principles for Security
........5.4.5 User Authentication
....5.5 PROTECTION MECHANISMS
........5.5.1 Protection Domains
........5.5.2 Access Control Lists
........5.5.3 Capabilities
........5.5.4 Protection Models
........5.5.5 Covert Channels
....5.6 OVERVIEW OF THE MINIX FILE SYSTEM
........5.6.1 Messages
........5.6.2 File System Layout
........5.6.3 Bit Maps
........5.6.4 I-nodes
........5.6.5 The Block Cache
........5.6.6 Directories and Paths
........5.6.7 File Descriptors
........5.6.8 Pipes and Special Files
........5.6.9 An Example: The READ System Call
....5.7 IMPLEMENTATION OF THE MINIX FILE SYSTEM
........5.7.1 The Header Files
........5.7.2 Table Management
........5.7.3 The Main Program
........5.7.4 Operations on Individual Files
........5.7.5 Directories and Paths
........5.7.6 Other System Calls
........5.7.7 The I/O Device Interface
........5.7.8 General Utilities
....5.8 SUMMARY
6. READING LIST AND BIBLIOGRAPHY
....6.1 SUGGESTIONS FOR FURTHER READING
........6.1.1 Introduction and General Works
........6.1.2 Processes
........6.1.3 Input/Output
........6.1.4 Memory Management
........6.1.5 File Systems
....6.2 ALPHABETICAL BIBLIOGRAPHY
APPENDICES
....A. INTRODUCTION TO C
....B. INTRODUCTION TO THE IBM PC
....C. MINIX USERS’ GUIDE
....D. MINIX IMPLEMENTERS' GUIDE
....E. MINIX SOURCE CODE LISTING
....F. MINIX CROSS REFERENCE LISTING
INDEX