《操作系统 设计及实现 第2版》求取 ⇩

1 INTRODUCTION1

1.1 WHAT IS AN OPERATING SYSTEM？3

1.1.1 The Operating System as an Extended Machine3

1.1.2 The Operating System as a Resource Manager4

1.2 HISTORY OF OPERATING SYSTEMS5

1.2.1 The First Generation（1945-55）Vacuum Tubes and Plugboards6

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

1.2.3 The Third Generation（1965-1980）：ICs and Multiprogramming8

1.2.4 The Fourth Generation（1 980-Present）：Personal Computers12

1.2.5 History ofMINIX13

CONTENTS15

PREFACE15

1.3 OPERATING SYSTEM CONCEPTS15

1.3.1 Processes15

1.3.2 Files17

1.3.3 The Shell20

1.4 SYSTEM CALLS21

1.4.1 System Calls for Process Management22

1.4.2 System Calls for Signaling26

1.4.3 System Calls for File Management28

1.4.4 System Calls for Directory Managemen t33

1.4.5 System Calls for Protection35

1.4.6 System Calls for Time Management36

1.5 OPERATING SYSTEM STRUCTURE37

1.5.1 Monolithic Systems37

1.5.2 Layered Systems39

1.5.3 Virtual Machines40

1.5.4 Client-Server Model42

1.7 SUMMARY44

1.6 OUTLINE OF THE REST OF THIS BOOK44

2.1 INTRODUCTION TO PROCESSES47

2 PROCESSES47

2.1.1 The Process Model48

2.1.2 Implementation of Processes52

2.1.3 Threads53

2.2 INTERPROCESS COMMUNICATION57

2.2.1 Race Conditions57

2.2.2 Critical Sections58

2.2.3 Mutual Exclusion with Busy Waiting59

2.2.4 Sleep and Wakeup63

2.2.5 Semaphores66

2.2.6 Monitors68

2.2.7 Message Passing72

2.3.1 The Dining Philosophers Problem75

2.3 CLASSICAL IPC PROBLEMS75

2.3.2 The Readers and Writers Problem77

2.3.3 The Sleeping Barber Problem80

2.4 PROCESS SCHEDULING82

2.4.1 Round Robin Scheduling84

2.4.2 Priority Scheduling85

2.4.3 Multiple Queues86

2.4.4 Shortest Job First87

2.4.5 Guaranteed Scheduling89

2.4.6 Lottery Scheduling89

2.4.7 Real-Time Scheduling90

2.4.8 Two-level Scheduling92

2.5 OVERVIEW OF PROCESSES IN MINIX93

2.5.1 The Internal Structure of MINIX93

2.4.9 Policy versus Mechanism93

2.5.2 Process Management in MINIX95

2.5.3 Interprocess Communication in MINIX97

2.5.4 Process Scheduling in MINIX98

2.6 IMPLEMENTATION OF PROCESSES IN MINIX98

2.6.1 Organization of the MINIX Source Code99

2.6.2 The Common Header Files102

2.6.3 The MINIX Header Files107

2.6.4 Process Data Structures and Header Files112

2.6.5 Bootstrapping MINIX120

2.6.6 System Initialization122

2.6.7 Interrupt Handling in MINIX128

2.6.8 Interprocess Communication in MINIX137

2.6.9 Scheduling in MINIX140

2.6.10 Hardware-Dependent Kernel Support142

2.6.11 Utilities and the Kernel Library145

2.7 SUMMARY147

3 INPUT/OUTPUT153

3.1 PRINCIPLES OF I/O HARDWARE154

3.1.1 I/O Devices154

3.1.2 Device Controllers155

3.1.3 Direct Memory Access （DMA）157

3.2 PRINCIPLES OF I/O SOFTWARE159

3.2.1 Goals ofthe I/O Software159

3.2.2 Interrupt Handlers161

3.2.3 Device Drivers161

3.2.4 Device-Independent I/O Software162

3.2.5 User-Space I/O Software164

3.3 DEADLOCKS166

3.3.1 Resources167

3.3.2 Principles of Deadlock168

3.3.3 The Ostrich Algorithm170

3.3.4 Detection and Recovery172

3.3.5 Deadlock Prevention173

3.3.6 Deadlock Avoidance175

3.4 OVERVIEW OF I/O IN MINIX179

3.4.1 Interrupt Handlers in MINIX180

3.4.2 Device Drivers in MINIX181

3.4.3 Device-Independent I/O Software in MINIX185

3.4.4 User-level I/O Software in MINIX185

3.4.5 Deadlock Handling in MINIX186

3.5 BLOCK DEVICES IN MINIX187

3.5.1 Overview of Block Device Drivers in MINIX187

3.5.2 Common Block Device Driver Software190

3.5.3 The Driver Library193

3.6 RAM DISKS195

3.6.1 RAM Disk Hardware and Software196

3.6.2 Overview of the RAM Disk Driver in MINIX197

3.6.3 Implementation of the RAM Disk Driver in MINIX198

3.7 DISKS200

3.7.1 Disk Hardware200

3.7.2 Disk Software202

3.7.3 Overview of the Hard Disk Driver in MINIX208

3.7.4 Implementation of the Hard Disk Driver in MINIX211

3.7.5 Floppy Disk Handling220

3.8 CLOCKS222

3.8.1 Clock Hardware223

3.8.2 Clock Software224

3.8.3 Overview of the Clock Driver in MINIX227

3.8.4 Implementation of the Clock Driver in MINIX230

3.9.1 Terminal Hardware235

3.9 TERMINALS235

3.9.2 Terminal Software240

3.9.3 Overview of the Terminal Driver in MINIX249

3.9.4 Implementation of the Device-Independent Terminal Driver264

3.9.5 Implementation of the Keyboard Driver282

3.9.6 Implementation of the Display Driver288

3.10 THE SYSTEM TASK IN MINIX296

3.11 SUMMARY304

4 MEMORY MANAGEMENT309

4.1 BASIC MEMORY MANAGEMENT310

4.1.1 Monoprogramming without Swapping or Paging310

4.1.2 Multiprogramming wiith Fixed Partitions311

4.2 SWAPPING313

4.2.1 Memory Management with Bit Maps316

4.2.2 Memory Management with Linked Lists317

4.3 VIRTUAL MEMORY319

4.3.1 Paging319

4.3.2 Page Tables322

4.3.3 TLBs—Translation Lookaside Buffers327

4.3.4 Inverted Page Tables330

4.4 PAGE REPLACEMENT ALGORITHMS331

4.4.1 The Optimal Page Replacement Algorithm331

4.4.2 The Not-Recently-Used Page Replacement Algorithm332

4.4.3 The First-In，First-Out（FIFO）Page Replacement Algorithm333

4.4.4 The Second Chance Page Replacement Algorithm333

4.4.5 The Clock Page Replacement Algorithm334

4.4.6 The Least Recently Used（LRU）Page Replacement Algorithm334

4.4.7 Simulating LRU in Software336

4.5.1 The Working Set Model338

4.5 DESIGN ISSUES FOR PAGING SYSTEMS338

4.5.2 Local versus Global Allocation Policies339

4.5.3 Page Size341

4.5.4 Virtual Memory Interface343

4.6 SEGMENTATION343

4.6.1 Implementation of Pure Segmentation347

4.6.2 Segmentation with Paging：MULTICS348

4.6.3 Segmentation with Paging：The Intel Pentium352

4.7 OVERVIEW OF MEMORY MANAGEMENT IN MINIX356

4.7.1 Memory Layout358

4.7.2 Message Handling361

4.7.3 Memory Manager Data Structures and Algorithms363

4.7.4 The FORK，EXIT，and WAIT System Calls367

4.7.5 The EXEC System Call368

4.7.6 The BRK System Call371

4.7.7 Signal Handling372

4.7.8 Other System Calls378

4.8 IMPLEMENTATION OF MEMORY MANAGEMENT IN MINIX379

4.8.1 The Header Files and Data Structures379

4.8.2 The Main Program382

4.8.3 Implementation of FORK，EXIT，and WAIT382

4.8.4 Implementation of EXEC385

4.8.5 Implementation of BRK386

4.8.6 Implementation of Signal Handling387

4.8.7 Implementation of the Other System Calls393

4.8.8 Memory Manager Utilities394

4.9 SUMMARY396

5 FILE SYSTEMS401

5.1 FILES402

5.1.1 File Naming402

5.1.2 File Structure404

5.1.3 File Types405

5.1.4 File Access407

5.1.5 File Attributes408

5.1.6 File Operations409

5.2 DIRECTORIES410

5.2.1 Hierarchical Directory Systems411

5.2.2 Path Names412

5.2.3 Directory Operations414

5.3 FILE SYSTEM IMPLEMENTATION415

5.3.1 Implementing Files415

5.3.2 Implementing Directories419

5.3.3 Disk Space Management422

5.3.4 File System Reliability424

5.3.5 File System Performance429

5.3.6 Log-Structured File Systems432

5.4 SECURITY434

5.4.1 The Security Environment434

5.4.2 Famous Security Flaws436

5.4.3 Generic Security Attacks439

5.4.4 Design Principles for Security441

5.4.5 User Authentication442

5.5 PROTECTION MECHANISMS446

5.5.1 Protection Domains446

5.5.2 Access Control Lists448

5.5.3 Capabilities450

5.5.4 Cover Channels451

5.6 OVERVIEW OF THE MINIX FILE SYSTEM453

5.6.1 Messages454

5.6.2 File System Layout454

5.6.3 Bit Maps458

5.6.4 I-nodes460

5.6.5 The Block Cache461

5.6.6 Directories and Paths463

5.6.7 File Descriptors465

5.6.8 File Locking467

5.6.9 Pipes and Special Files467

5.6.10 An Example：The READ System Call469

5.7 IMPLEMENTATION OF THE MINIX FILE SYSTEM470

5.7.1 Header Files and Global Data Structures470

5.7.2 Table Management474

5.7.3 TheMainProgram482

5.7.4 Operations on Individual Files485

5.7.5 Directories and Paths493

5.7.6 Other System Calls498

5.7.7 The I/O Device Interface501

5.7.8 General Utilities503

5.8 SUMMARY503

6 READING LIST AND BIBLIOGRAPHY507

6.1 SUGGESTIONS FOR FURTHER READING507

6.1.1 Introduction and General Works507

6.1.2 Processes509

6.1.3 Input/Output510

6.1.4 Memory Management511

6.1.5 File Systems511

6.2 ALPHABETICAL BIBLIOGRAPHY512

APPENDICES521

A MINIX SOURCE CODE LISTING521

B INDEX TOFILES905

C INDEX TO SYMBOLS909

INDEX925