操作系统：设计与实现

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-55） Vacuum Tubes and Plugboards

1.2.2 The Second Generation （1955-65） Transistors and Batch Systems

1.2.3 The Third Generation （1965-1980） ICs and Multiprogramming

1.2.4 The Fourth Generation （1980-Present） Personal Computers

1.2.5 History of MINIX 3

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 Exokernels

1.5.5 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 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 Threads

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 Mutexes

2.2.7 Monitors

2.2.8 Message Passing

2.3 CLASSICAL IPC PROBLEMS

2.3.1 The Dining Philosophers Problem

2.3.2 The Readers and Writers Problem

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 OVERVIEW OF PROCESSES IN MINIX 3

2.5.1 The Internal Structure of MINIX 3

2.5.2 Process Management in MINIs 3

2.5.3 Interprocess C（）mmunlcation in MINIX 3

2.5.4 DOCeds SCheduling in MIDIs 3

2.6 IMPLEMENTAnON OF PROCESSES IN MINIX 3

2.6.1 orgamzation of [he MINIX 3 S,urcc COde

2.6.2 COmpiling and Annuling MINix 3

2.6.3 The Common Header Files

2.6.4 The MINIX 3 Header r.IIes

2.6.5 Process Data Srtuctures and Header FJles

2.6.6 BOOtstrapping MINLX 3

2.6.7 System initiaIIZation

2.6.8 InterrIIpt HanoIing in MINce 3

2.6.9 Interprocess Colnmunlcatlon in aleX 3

2.6.10 SCheduling in MINIX 3

2.6.11 Hardware Dependent Kernel Sllpport

2.6.12 Utilities and lhc Kernel Libl+ary

2.7 THE SYSTEM TASK IN MINIX 3

2.7.1 Overview of the System Task

2.7.2 Implementation ot the Syslern Task

2.7.3 hoplemelltaiion of the System Libarary

2.8 THE CLOCK TASK IN MINIX 3

2.8.1 Clock Hardware

2.8.2 ClOCk SOftware

2.8.3 Overview of the Clock Driver in MINix 3

2.8.4 Implementat）on of the ClOck Diver in MINIX 3

2.9 SUMMARY

3 INPUT/OUTPUT

3.1 PRINCLPLES OF CO HARDWARE

3.1.1 I/o Devices

3.1.2 Device COntrollers

3.1.3 MeInory-Mapped I/o

3.1.4 Interrupts

3.1.5 Direct Memory Access

3.2 PRINCIPLES OF I/O SOFTWARE

3.2.1 Coals of the UO Software

3.2.2 Interrupt IJandlers

3.2.3 Device Dnvers

3.2.4 Device-independent l/O Sotlware

3.2.5 User Space ilO Software

3.3 DEADLOCKS

3.3.1 Resources

3.3.2 Principles of DCadIOCk

3.3.3 The Ostrich Algorlthln

3.3.4 Detection and Rccovery

3.3.5 DCadIOCk WevenIIOn

3.3.6 DeadlOCk AVOIdance

3.4 OVERVIEW OF I/O IN MINIX 3

3.4.1 Interrupt HandIers in MINIX 3

3.4.2 DCVice 13rivers in MLNLX 3

3.4.3 Device-Independent CO SOftware in MINIX 3

3.4.4 USCr LeveI W SOftware in MINX 3

3.4.5 DeauIOCk HandlIng in MINIX 3

3.5 BLOCK DEVICES IN MINIX 3

3.5.1 OVerview of BlOCk Device Dnt/crs in MINix 3

3.5.2 Common Block Device Driver Soltwure

3.5.3 The Dnaal Librmp

3.6 DISKS

3.6.1 RAM Disk Hardwtire and Soltwarc

3.6.2 OVCrview of me AM Disk Driver in MINIX 3

3.6.3 ILnplementalLon of the RAM DLsk Dnver in MINLX 3

3.7 DISKS

3.7.1 DLsk HaTdware

3.7.2 RAID

3.7.3 DISk SO,tware

3.7.4 Overylew of the HaL+d Disk Dnver in MINce 3

3.7.5 Inlplemcntation ot the Had Disk DTiver in MINIX 3

3.7.6 FIOnpy DISk Handling

3.8 TErmINALS

3.8.1 Terminal HaTdwarc

3.8.2 TemlinaL Software

3.8.3 Overview of the Terminal Dnver 111 MINIX 3

3.8.4 Implementation of the Device-independent Terminal aliver CONTS Vii

3.8.5 Iruplemeotation of the Keyboard Driver

3.8.6 imPlementation of the DLsplny Dnver

3.9 SUMMARY

4 MEMORY MANAGEMENT

4.1 BASIC MEMORY MANAGEMENT

4.1.1 Monoprogramming without Swapping or Paging

4.1.2 Multiprograrnming with Fixed Parutions

4.1.3 Relocation and Pr（,tectlon

4.2 SWAPPING

4.2.1 Memory Management with Blimaps

4.2.2 Memory Management with Linked Lists

4.3 VIRTUAL MEMORY

4.3.1 PagIng

4.3.2 Page TabbIed

4.3.3 TLBS--Translation LOOkaside Bull.ers

4.3.4 Inverted Page Tables

4.4 PAGE REPLACEMENT ALGORITHMS

4.4.1 The Optinml Page Replacement Algorithms

4.4.2 The Nc）t Recently Used Page Replacement Algorithm

4.4.3 The First-in. FITSt-Ollt （FIFO） Page Rcplaccmcnt Algorithm

4.4.4 The Second Chance Pace Replacement Algorithm

4.4.5 The Clock Page Rcplaccmcnt ALgorithm

4.4.6 The Least Recently Used （LRU） Page Replacement Algorithm

4.4.7 Simulating LRU in Software

4.5 DESIGN ISSUES FOR PAGINC SYSTEMS

4.5.1 The WOrking Set MOdel

4.5.2 Local vereus Global Allocation POlicies

4.5.3 Pangs Size

4.5.4 Virtual Memory IntcrfMc

4.6 SEGMENTAnON 405

4.6.1 Implementation of pore Segmentation

4.6.2 Segmentation with Paging f The intel Pentium

4.7 OVERVIEW OIl rHE MINIX 3 PROCESS MANAGER

4.7.1 Memory Layout

4.7.2 Message Handling

4.7.3 Process Manager Data Smictules and AlgoTithms

4.7.4 The roax. and WAIT SystenI CallS

4.7.5 The EXEC System Call

4.7.6 The BRK SysteIn Call

4.7.7 Signal Handling

4.7.8 Other System Calls

4.8 IMPLEMENfATION OF THE MINIX 3 PROCESS MANAGER

4.8.1 The Header FLLes and Data Smictures

4.8.2 The Main program

4.8.3 Implementation of FORK, EXIT. and WArs

4.8.4 implementation of EXEC

4.8.5 lmplemenL3tion of BRK

4.8.6 Implementation of Signal Handling

4.8.7 Implementutjon of Other System Calls

4.8.8 Memory Management Utilities

4.9 SUARY

5 FILE SYSTEMS

5.1 m.ES

5.1.1 File Naming

5.1.2 File Structure

5.1.3 File Types

5.1.4 File ACCess

5.1.5 FIIC AttrIbutes

5.1.6 File OpeTaiions

5.2 DIreCTORIES

5.2.1 Simple Directones

5.2.2 Hierarchical Direct（lry Systems

5.2.3 Path Names

5.2.4 Directory Operahons

5.3 FILE SYSTEM IMPLEMENTATION

5.3.1 File System Lazoui

5.3.2 Implementing Files

5.3.3 Implementing Directories

5.3.4 Disk Space MtInageInent CO~NTS iX

5.3.5 File System ReIiabiIitv

5.3.6 File System Perf（lrmance

5.3.7 Log Structured File Systems

5.4 SECURITY

5.4.1 The Secuniy Envirollment

5.4.2 Genenc Security Attacks

5.4.3 Design Pnnciplcs for Sccunty

5.4.4 User Authentication

5.5 PROTECTION MECHANISMS

5.5.1 Protechon Domains

5.5.2 Access ColltrI l.ists

5.5.3 CanabiIities

5.5.4 Covert Channels

5.6 OVERVIEW OF TIlE MINIX 3 FILE SYSTEM

5.6.1 Messages

5.6.2 File System Layout

5.6.3 Bitmaps

5.6.4 1 NOdes

5.6.5 The BlOCk Cache

5.6.6 Directories and Pains

5.6.7 File Dcscnptors

5.6.8 File LOCking 561

5.6.9 Pipes and Special Files

5.6.10 An Example f The axAN System Call

5.7 IMPLEMENTATION OF THE MINIX 3 FILE SYSTEM

5.7.1 Header Files and Global Data Structures

5.7.2 Table Management

5.7.3 The Main Program

5.7.4 OperatIOns on individual Files

5.7.5 DITcctoncs and Paths

5.7.6 Other System Calls

5.7.7 The I/o Device interface

5.7.8 Additional System Call SuPPort

5.7.9 File System Utilities

5.7.10 Ottier MINJX 3 COmponents SUMMARY

6 BIBLIOGRAPHY

本书是著名作者Andrew S.Tanenbaum关于操作系统的权威教材。
多数操作系统的教材只重理论而轻实践，本书力图实现这两者之间的平衡。本书首先详细探讨了操作系统的基本原理，如进程、进程间通信、信号量、消息传递、调度算法、输入/输出、死锁、设备驱动程序、存储管理、调页算法、文件系统设计、安全和保护机制等，然后详细讨论了一个具体的操作系统MINIX3的实现，并给出了该系统的完整源代码，以便于读者仔细研究。这样不仅可以让读者掌握操作系统的基本原理，而且可让读者明白这些基本原理如何应用到实际操作系统设计中去，从而提供读者的实际设计和实现能力。
本书可以作为高等院校计算机及相关专业“操作系统”的双语教材，对程序开发人员、工程技术人员、系统架构师等专业人员也具有很高的参考价值。

本书全书共分6个部分，对操作系统的设计与实现作了介绍，具体包括进程、进程间通信、信号量、消息传递、调度算法、输入/输出、死锁等。该书可供各大专院校作为教材使用，也可供从事相关工作的人员作为参考用书使用。