( [计算机科学经典著作].Prentice.Hall.Operating.Systems.Design.and.Implementation.p

本文采用开源的操作系统代码描述系统内核，更容易理解和加深理解系统运行机制，学习操作系统的好材料！vICONTENTS.S OPERATING SYSTEM STRUCTURE 371.5.1 Monolithic Systems 371.5.2 Layered Systems 391.5.3 Virtual Machines 401.5.4 Client-Server Model 421.6 OUTLINE OF THE REST OF THIS BOOK 441. SUMMARY 442 pROCesSES472.1 INTRODUCTION TO PROCESSES 472.1.1 The Process Model 482. 1.2 Implementation of Processes 522.1.3 Threads 532.2 INTERPROCESS COMMUNICATEN 572.2.1 Race Conditions 572.2.2 Critical Sections 582.2.3 Mutual Exclusion with Busy Waiting 592.2. 4 Sleep and Wakeup 632.2.5 Semaphores 662.2.6 Monitors 682.2.7 Message Passing 722, 3 CLASSICAL IPC PROBLEMS 752.3.1 The Dining Philosophers Problem 752.3.2 The Readers and writers Problem 772.3. 3 The Sleeping Barber Problem 802.4 PROCESS SCHEDULING 822.4.1 Round Robin Scheduling 842.4.2 Priority Scheduling 852. 4.3 Multiple queues 862.4.4 Shortest Job First 872.4.5 Guaranteed Scheduling 892.4.6 Lottery Scheduling 892.4.7 Real-Time Scheduling 902.4.8 Two-level Scheduling 922. 4.9 Policy versus Mechanism 93CONTENTS2.5 OVERVIEW OF PROCESSES IN MINIX 932.5. 1 The Internal Structure of minix 932.5.2 Process Management in MINIX 952.5.3 Interprocess Communication in MINIX 972.5.4 Process Scheduling in MINIX 982.6 IMPLEMENTATION OF PROCESSES IN MINIX 982.6. 1 Organization of the MINiX Source Code 992.6.2 The Common Header Files 1022.6.3 The MINIX Header Files 1072.6. 4 Process Data Structures and Header Files 1122.6.5 Bootstrapping MINIX 1202.6.6 System Initialization 1222.6.7 Interrupt Handling in MINIX 1282.6.8 Interprocess Communication in MINIX 1372.6.9 Scheduling in MINIX 1402.6.10 Hardware-Dependent Kermel Support 1422.6. 11 Utilities and the Kernel library 1452.7 SUMMARY 1473 INPUT/OUTPUT1533.1 PRINCIPLES OF IO HARDWARE 1543.】.1 1/0 Devices 1543. 1.2 Device Controllers 1553.1.3 Direct Memory Access(DMA)1573.2 PRINCIPLES OF IO SOFTWARE 1593.2.1 Goals of the yO Software 1593.2.2 Interrupt Handlers 1613.2.3 Device Drivers 1613.2. 4 Device-Independent 1O Software 1623.2.5 User-Space 1O Software 1643.3 DEADLOCKS 1663.3.1 Resources 1673.3.2 Principles of Deadlock 1683.3.3 The Ostrich Algorithm 1703.3.4 Detection and Recovery 1723.3.5 Deadlock Prevention 1733.3.6 Deadlock Avoidance 175XCONTENTS34 OVERVIEW OF LO IN MINIX 1793. 4. 1 Interrupt Handlers in MINIX 1803.4.2 Device Drivers in MINIX 1813. 4.3 Device-Independent 1/O Software in MINIX 1853. 4. 4 User-level 1O Software in MINIX 1853.4.5 Deadlock Handling in MINIX 1863. 5 BLOCK DEVICES IN MINIX 1873.5.1 Overview of Block Device Drivers in MINIX 1873.5.2 Common Block Device Driver Software 1903. 5. 3 The Driver Library 1933.6 RAM DISKS 1953.6.1 RAM Disk Hardware and Software 1963.6.2 Overview of the RAM Disk Driver in MINIX 1973.6.3 Implementation of the RAM Disk Driver in MINIX 1983.7 DISKS 2003.7.1 Disk hardware 2003.7.2 Disk Software 2023.7.3 Overyiew of the hard disk driver in minix 2083.7. 4 Implementation of the Hard Disk Driver in MINIX 2113.7.5 Floppy Disk Handling 2203. 8 CLOCKS 2223.8.1 Clock hardware 2233.8.2 Clock Software 2243.8.3 Overview of the Clock driver in MINIX 2273.8.4 Implementation of the Clock Driver in MINIX 2303.9 TERMINALS 2353.9.1 Terminal Hardware 2353.9.2 Terminal Software 2403.9.3 Overview of the Terminal Driver in MINIX 2493.9. 4 Implementation of the Device-Independent Terminal Driver 263.9.5 Implementation of the Keyboard Driver 2823.9.6 Implementation of the Display Driver 2883. 10 THE SYSTEM TASK IN MINIX 2963. 11 SUMMARY 304CONTENTS4 MEMORY MANAGEMENT3094.1 BASIC MEMORY MANAGEMENT 3104.1.1 Monoprogramming without Swapping or Paging 3104.1.2 Multiprogramming wiith Fixed Partitions 3114.2 SWAPPING 3134.2. 1 Memory Management with Bit Maps 3164.2.2 Memory Management with Linked Lists 3174.3 VIRTUAL MEMORY 3194.3.1 Paging 3194.3. 2 Page Tables 3224.3.3 TLBS-Translation Lookaside Buffers 3274.3.4 Inverted Page Tables 3304.4 PAGE REPLACEMENT ALGORITHMS 3314.4.1 The Optimal Page Replacement Algorithm 3314.4.2 The Not-Recently-Used Page Replacement Algorithm 3324.4.3 The First-In, First-Out(FIFO) Page Replacement Algorithm 3334.4.4 The Second Chance Page Replacement Algorithm 3334.4.5 The Clock Page Replacement Algorithm 3344.4.6 The Least Recently Used(LRU) Page Replacement Algorithm 3344.4.7 Simulating LrU in Software 3364.5 DESIGN ISSUES FOR PAGING SYSTEMS 33&4.5, 1 The Working Set Model 3384.5.2 Local versus Global Allocation Policies 3394.5.3 Page Size 3414.5.4 Virtual Memory Interface 3434.6 SEGMENTATIoN 3434.6.1 Implementation of Pure Segmentation 3474.6.2 Segmentation with Paging: MULTICS 3484.6.3 Segmentation with Paging: The Intel Pentium 3524.7 OVERVIEW OF MEMORY MANAGEMENT IN MINIX 3564.7.1 Memory Layout 3584.7.2 Message Handling 3614.7.3 Memory Manager Data Structures and Algorithms 3634.7.4 The FORK, EXIT, and WAIT System Calls 3674.7.5 The EXEC System Call 3684.7.6 The BRK System Call 3714.7.7 Signal Handling 3724.7. 8 Other System Calls 378CONTENTS4.8 IMPLEMENTATION OF MEMORY MANAGEMENT IN MINIX 3794.8.1 The Header Files and Data Structures 3794.8.2 The Main Program 3824.8.3 Implementation of FORK, EXIT, and WAIT 3824.4 Implementation of EXEC 3854.8.5 Implementation of BRK 3864.8.6 Implementation of Signal Handling 3874.8.7 Implementation of the Other System Calls 3934.8.8 Memory Manager Utilities 3944.9 SUMMARY 3965 FILE SYSTEMS5.1 FILES 4025.. File Naming 4025.1.2 File structure 4045.1.3 File Types 4055.1.4 File Access 4075.1.5 File Attributes 4085.1.6 File Operations 4095.2 DIRECTORIES 4105.2.1 Hierarchical Directory Systems. 4115.2.2 Path Names 4125.2.3 Directory Operations 4145. 3 FILE SYSTEM IMPLEMENTATION 4155.3.1 Implementing Files 4155.3.2 Implementing Directories 4195.3.3 Disk Space Management 42253. 4 File System Reliability 4245.3.5 File System Performance 4295.3.6 Log-Structured File Systems 4325.4 SECURITY 4345.4.i The Security Environment 4345.4.2 Famous Security Flaws 4365.4, 3 Generic security Attacks 4395.4. 4 Design Principles for Security 4415.4.5 User authentication 442ONTENTS5.5 PROTECTION MECHANISMS 4465.5.1 Protection Domains 4465.5.2 Access Control Lists 4485.5.3 Capabilities 4505.5.4 Covert Channels 4515.6 OVERVIEW OF THE MINIX FILE SYSTEM 4535.6.1 Messages 4545.6.2 File System Layout 4545.6.3 Bit Mapss4585.6.4 I-nodes 4605.6.5 The Block Cache 4615.6.6 Directories and Paths 4635.6.7 File Descriptors 4655.6.8 File Locking 4675.6.9 Pipes and Special Files 4675.6.10 An Example: The rEad System Call 4695. 7 IMPLEMENTATION OF THE MINIX FILE SYSTEM 4705.7.1 Header Files and Global Data Structures 4705.7.2 Table Management 4745.7.3 The Main Program 4825.7.4 Operations on Individual Files 4855.7.5 Directories and Paths 4935.7.6 Other System Calls 4985.7.7 The IO Device Interface 5015.7.8 General Utilities 5035. 8 SUMMARY 5036 READING LIST AND BIBLIOGRAPHY5076.1 SUGGESTIONS FOR FURTHER READING 5076. 1.1 Introduction and General Works 5076.1.2 Processes 5096.1.3 Input/Output 5106.1.4 Memory Management 5116.1.5 Flle Systems 5116.2 ALPHABETICAL BIBLIOGRAPHY 512INTRODUCTIONWithout its software, a computer is basically a useless lump of metal. Withits software, a computer can store, process, and retrieve information; display multimedia documents; search the Internet; and engage in many other valuable activi-ties to earn its keep Computer software can be divided roughly into two kindssystem programs, which manage the operation of the computer itself, and applica-tion programs. which perform the actual work the user wants. The most fundamental system program is the operating system, which controls all thecomputer's resources and provides the base upon which the application programscan be writtenA modern computer system consists of one or more processors, some mainmemory (often known as RAM-Random Access Memory), disks, printers, network interfaces, and other input/output devices. All in all, a complex systemWriting programs that keep track of all these components and use them correctly,let alone optimally, is an extremely difficult job. If every programmer had to beconcerned with how disk drives work, and with all the dozens of things that couldgo wrong when reading a disk block, it is unlikely that many programs could bewritten at allMany years ago it became abundantly clear that some way had to be found toshield programmers from the complexity of the hardware. The way that hasevolved gradually is to put a layer of software on top of the bare hardware, tomanage all parts of the system, and present the user with an interface or virtualINTRODUCTIONCHAP. Imachine that is easier to understand and program. This layer of software is theoperating system and forms the subject of this bookThe situation is shown in Fig. 1-1. At the bottom is the hardware, which, inmany cases, is itself composed of two or more layers. The lowest layer containsphysical devices, consisting of integrated circuit chips, wires, power supplies,cathode ray tubes, and similar physical devices. How these are constructed andhow they work is the province of the electrical engineerBankingAirlineWebApplication programssystem reservationrowserCompilers EditorsinterpreterSystemprOperating systemMachine languageMicroprogrammingHardwarePhysical devicesFIgure 1-1. A computer system consists of hardware, system programs, and ap-plication programsNext (on some machines) comes a layer of primitive software that directlycontrols these devices and provides a cleaner interface to the next layer. Thissoftware, called the microprogram, is usually located in read-only memory. It isactually an interpreter, fetching the machine language instructions such as ADD,MOVE, and JUMP, and carrying them out as a series of little steps. To carry outan ADD instruction, for example, the microprogram must determine where thenumbers to be added are located. fetch them, add them, and store the result somewhere. The set of instructions that the microprogram interprets defines themachine language which is not really part of the hard machine at all, but coputer manufacturers always describe it in their manuals as such, so many peoplethink of it as being the real"machineSome computers, called RISC (Reduced Instruction Set Computersmachines, do not have a microprogramming level. On these machines, theMotorola 680x0 has a microprogramming level, but the IBM PowerPC does nof ohardware executes the machine language instructions directly. As examples, theThe machine language typically has between 50 and 300 instructions, mostlyfor moving data around the machine, doing arithmetic, and comparing values. Inthis layer, the input/output devices are controlled by loading values into specialdevice registers. For example, a disk can be commanded to read by loading thevalues of the disk address, main memory address, byte count, and direction(READ or WRITE) into its registers. In practice, many more parameters are