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 Ggeneration(1945-55)Vacuum Tubes and Plugboards                  
 1.2.2  The Second Generation(1995-65)Transistors and Batch Systems                  
 1.2.3  The Third Ggeneration(1965-1980):ICs and Multiprogramming                  
 1.2.4  The Ffourth Generation(1980-Present):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 Mmachines                  
 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.1.3  Tthreads                  
 2.2  INTERPROCESS COMMUNICATION                  
 2.2.1  Race Conditions                  
 2.2.2  Critical  Sections                  
 2.2.3  Mutual Exclusion with Bush Waiting                  
 2.2.4  Sleep and Wakeup                  
 2.2.5  Semaphores                  
 2.2.6  Monitors                  
 2.2.7  Message Passing                  
 2.3  CLASSICAL IPC PROBLEMS                  
 2.3.1 The Dinding Philosophers Problem                  
 2.3.2  The Readers and Writers Problem                  
 2.3.3  The Sleeping Barber Problem                  
 2.4  PROCESS SCHEDULING                  
 2.4.1  Roumd Robin Scheduling                  
 2.4.2  Priority Scheduling                  
 2.4.3  Multiple Queues                  
 2.4.4  Shortest Job First                  
 2.4.5  Guaranteed Scheduling                  
 2.4.6  Lottery Scheduling                  
 2.4.7  Real-Time Scheduling                  
 2.4.8  Two-level Scgeduling                  
 2.4.9  Policy versus Mechanism                  
 2.5  OVERVIEW OF PROESSES 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  IMPLIMENTATION OF PROCESSES IN MINIX                  
 2.6.1  Organization of the MINIX Source Code                  
 2.6.2  The Common Header Files                  
 2.6.3  The MINIX Header Files                  
 2.6.4  Process Data Structures and Header Files                  
 2.6.5  Bootstrapping MINIX                  
 2.6.6  System Initialization                  
 2.6.7  Interrupt Handling in MINIX                  
 2.6.8  Interprocess Communication in MINIX                  
 2.6.9  Scheduling in MINIX                  
 2.6.10  Hardware-Dependent Kernel Support                  
 2.6.11  Utilities and the Kernel Library                  
 2.7  SUMMARY                  
                   
 3  INPUT/OUPUT                  
 3.1  PRINCIPLES OF I/O HARDWARE                  
 3.1.1  I/O Devices                  
 3.1.2  Device Controllers                  
 3.1.3  Direct Memory Access(DMA)                  
 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  Principles of Deadlock                  
 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 MINIX                  
 3.4.1 Interrupt Handlers in MINIX                  
 3.4.2  Device Drivers in MINIX                  
 3.4.3  Device-Independent I/O Sofware in MINIX                  
 3.4.4  User-level I/O Software in MINIX                  
 3.4.5  Deadlock Handling in MINIX                  
 3.5  BLOCK DEVICES IN MINIX                  
 3.5.1  Overview of Block Device Drivers in MINIX                  
 3.5.2  Commoon Block Device Driver Software                  
 3.5.3  The Driver Library                  
 3.6  RAM DISKS                  
 3.6.1  RAM Disk Hardware and Sofware                  
 3.6.2  Overview of the RAM Disk Driver in MINIX                  
 3.6.3  Implementation of the RAM Disk Driver in MINIX                  
 3.7  DISKS                  
 3.7.1  Disk Hardware                  
 3.7.2  Disk Software                  
 3.7.3  Overview of the Hard Disk Driver in MINIX                   
 3.7.4  Implementation of the Hard Disk Driver in MINIX                  
 3.7.5  Floppy Disk Handling                  
 3.8  CLOCKS                  
 3.8.1  Clock Hardware                  
 3.8.2  Clock Software                  
 3.8.3  Overview of the Clock Driver in MINIX                  
 3.8.4  Implementation of the Clock Driver in MINIX                  
 3.9  TERMINALS                  
 3.9.1  Terminal Hardware                  
 3.9.2  Terminal Software                  
 3.9.3  Overview of the Terminal Driver in MINIX                  
 3.9.4  Implementation of the Device-Independent Terminal Driver                  
 3.9.5  Implementation of the Keyboard Driver                  
 3.9.6  Implementation of the Display Driver                  
 3.10  THE SYSTEM TASK IN MINIX                  
 3.11  SUMMARY                  
                   
 4  MEMORY MANAGEMENT                  
 4.1  BASIC MEMORY MANAGEMENT                  
 4.1.1 Monoprogramming without Swapping or Paging                  
 4.1.2  Multiprogramming with Fixed Partions                  
 4.2  SWAPPING                  
 4.2.1  Memory Management with Bit Maps                  
 4.2.2  Memory Management with Linked Lists                  
 4.3  VIRTUAL MEMORY                  
 4.3.1  Paging                  
 4.3.2 Page Tables                  
 4.3.3  TLBs-Transation Loodaside Buffers                  
 4.3.4  Inverted Page Tables                  
 4.4  PAGE REPLACEMENT ALHGORITHMS                  
 4.4.1  The Optimal Page Replacement Algorthm                  
 4.4.2  The Not-Recently-Used Page Replaceent Algorithm                  
 4.4.3  The First-In,First-Out(FIFO)Page Replacement Algorithm                  
 4.4.4  The Second Chance Page Replacement  Algorithm                  
 4.4.5  The Clock  Page Replacement Algorithm                  
 4.4.6  The Least Rrecently Used (LRU)Page Replacement Algorithm                  
 4.4.7  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  Virtual Memory Interface                  
 4.6  SEGMENTATION                  
 4.6.1  Implementation of Pure Segmentation                  
 4.6.2  Segmentation with Paging:MULTICS                  
 4.6.3  Segmentation with Paging:The Intel Pentum                  
 4.7  OVERVIEW OF MEMORY MANAGEMENT IN MINIX                  
 4.7.1  Memory Layout                  
 4.7.2  Message Handling                  
 4.7.3  Memory Manager Data Structures and Algorithms                  
 4.7.4  The FORK,EXIT,and WAIT System Calls                  
 4.7.5  The EXEC System Call                  
 4.7.6  The BRK System Call                  
 4.7.7  Signal Handling                  
 4.7.8  Other System Calls                  
 4.8  IMPLEMENTATION OF MEMORY MANAGEMENT IN MINIX                  
 4.8.1  The Header Files and Data Structures                  
 4.8.2  The Main Pprogram                  
 4.8.3  Implementation of FORK,EXIT,and WAIT                  
 4.8.4  Implementation of EXEC                  
 4.8.5  Implementation of BRK                  
 4.8.6  Implementation of  Signal Handling                  
 4.8.7  Implementation of the Other System Calls                  
 4.8.8  Memory Manager Utilities                  
 4.9  SUMMARY                  
                   
 5  FILE SYSTEMS                  
 5.1  FILES                  
 5.1.1  File Naming                  
 5.1.2 File Structure                  
 5.1.3  File Types                  
 5.1.4  File Access                  
 5.1.5  File Attributes                  
 5.1.6  File Operations                  
 5.2  DIRECTORIES                  
 5.2.1  Hierarchical Ddirectory Systems                  
 5.2.2  Path  Names                  
 5.2.3  Directory Operations                  
 5.3  FILE SYSTEM IMPLEMENTATION                  
 5.3.1  Implimenting Files                  
 5.3.2  Implementing Directories                  
 5.3.3  Disk Space Management                  
 5.3.4  File System Reliability                  
 5.3.5  File System Performance                  
 5.3.6  Log-Structrued File Systems                  
 5.4  SECURITY                  
 5.4.1  The Security Environment                  
 5.4.2  Famous Security Flaws                  
 5.4.3  Generic Secruity Attacks                  
 5.4.4  Desing Principlis 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  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  File Locking                  
 5.6.9  Pipes and Special Files                  
 5.6.10  An Example:The READ System Call                  
 5.7  IMPLEMENTATION OF THE MINIX FILE SYSTEM                  
 5.7.1  Header Ffiles and Global Data  Structrues                  
 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  MINIX AOURCE CODE LISTING                  
 B  INDEX TO FILES                  
 C  INDEX TO SYMBOLS                  
 INDEX