操作系统：现代观点 英文版PDF电子书下载

Chapter 1 Introduction 1

1.1 Computers and Software 2

1.1.1 General System Software 2

1.1.2 Resource Abstraction 4

IN THE HANGAR:A Disk Device Abstraction 5

1.1.3 Resource Sharing 6

1.1.4 Computers Without System Software 7

1.2 Operating System Strategies 8

PERFORMANCE TUNING:Multiprogramming Systems 10

1.2.1 Batch Systems 10

IN THE HANGAR:Batch Files 13

1.2.2 Timesharing Systems 14

1.2.3 Personal Computers and Workstations 16

1.2.4 Process Control and Real-time Systems 18

1.2.5 Networks 19

1.2.6 The Genesis of Modern Operating Systems 20

IN THE HANGAR:The Evolution of Linux 21

IN THE HANGAR:The Microsoft Windows Family of Operating Systems 23

1.3 Summary 25

1.4 Exercises 26

Chapter 2 Using the Operating System 29

2.1 The Abstract Model of Computing 30

2.2 Resources 30

2.2.1 Files 30

IN THE HANGAR:POSIX Files 31

IN THE HANGAR:Windows Files 33

2.2.2 Other Resources 36

2.3 Processes 37

2.3.1 Creating Processes 39

IN THE HANGAR:Using FORK,JOIN,and QUIT 40

IN THE HANGAR:Creating Processes in UNIX 41

IN THE HANGAR:Creating Processes in Windows 44

2.4 Threads 46

IN THE HANGAR:C Threads 48

2.5 Objects 49

2.6 Summary 50

2.7 Exercises 50

LABORATORY EXERCISE:A Shell Program 53

Background 53

Attacking the Problem 58

LABORATORY EXERCISE:A Multithreaded Windows Console Application 61

Background 61

Attacking the Problem 65

Chapter 3 Operating System Organization 71

3.1 Factorsin OS Design 72

3.1.1 Performance 72

3.1.2 Protection and Security 73

3.1.3 Correctness 74

3.1.4 Maintainability 74

3.1.5 Commercial Influence on Operating Systems 74

3.1.6 Standards and Open Systems 75

3.2 Basic Functions 76

3.2.2 Process and Resource Management 77

3.2.1 Device Management 77

3.2.3 Memory Management 78

3.2.4 File Management 78

3.2.5 Functional Organization 79

3.3 Basic Implementation Considerations 80

3.3.1 Processor Modes 80

3.3.2 Kernels 81

3.3.3 Requesting Services from the Operating Systems 82

3.4 Summary 83

3.5 Exercises 84

Chapter 4 Computer Organization 85

4.1 The von Neumann Architecture 86

4.2.1 The Arithmetical-Logical Unit 88

4.2 The Central Processing Unit 88

4.2.2 The Control Unit 89

4.3 Memory 91

PERFORMANCE TUNING:Speeding up the Machine 92

PERFORMANCE TUNING:Parallel Processors 94

4.4 Devices 95

4.4.1 General Device Characteristics 96

4.4.2 Device Controllers 97

IN THE HANGAR:Asynchronous Serial Devices 98

4.4.3 Device Drivers 99

4.5 Interrupts 100

4.6 The Mode Bit Revisited:The Trap Instruction 103

4.7 Summary 104

4.8 Exercises 105

LABORATORY EXERCISE:Kernel Timers 109

Background 109

Attacking the Problem 113

Chapter 5 Device Management 119

5.1 Device Management Approaches 120

5.1.1 I/O System Organization 120

5.1.2 Direct I/O with Polling 121

5.1.3 Interrupt-driven I/O 123

PERFORMANCE TUNING:Interrupts Versus Polling 126

5.1.4 Memory-mapped I/O 127

5.1.5 Direct Memory Access 128

PERFORMANCE TUNING:I/O-Processor Overlap 129

5.2 Buffering 130

5.3 Device Drivers 134

5.3.1 The Device Driver Interface 134

5.3.2 CPU-device Interactions 137

5.3.3 I/O Optimization 138

5.4 Some Device Management Scenarios 138

5.4.1 Serial Communications 138

IN THE HANGAR:UNIX Device Drivers 139

5.4.2 Sequentially Accessed Storage Devices 141

5.4.3 Randomly Accessed Devices 142

PERFORMANCE TUNING:Optimizing Access on Rotating Devices 144

5.5 Summary 149

5.6 Exercises 150

LABORATORY EXERCISE:A Floppy Disk Driver 153

Background 154

Attacking the Problem 158

Chapter 6 Process Management 161

6.1 The System View of Processes and Resources 162

6.1.1 Implementing the Process Model 163

6.1.2 Implementing the Resource Model 164

6.2 Initializing the Operating System 165

6.3 Process Address Spaces 166

6.3.1 Creating the Address Space 167

6.3.2 Loading the Program 168

6.3.3 Maintaining Consistency in the Address Space 168

6.4.1 Process Descriptors 170

6.4 The Process Abstraction 170

6.4.2 Process State Diagram 172

6.5 The Resource Abstraction 173

6.6 Process Hierarchy 174

6.6.1 Refining the Process Manager 176

6.6.2 Specializing Resource Allocation Strategies 177

6.7 Summary 178

6.8 Exercises 179

LABORATORY EXERCISE:Observing OS Behavior 181

Background 182

Attacking the Problem 187

Chapter 7 Scheduling 189

7.1.1 The Process Scheduler Organization 190

7.1 Scheduling Mechanisms 190

7.1.2 Saving the Process Context 192

7.1.3 Voluntary CPU Sharing 192

7.1.4 Involuntary CPU Sharing 194

7.1.5 Performance 195

7.2 Strategy Selection 196

7.2.1 Partitioning a Process into Small Processes 199

7.3 Nonpreemptive Strategies 200

7.3.1 First-Come-First-Served 200

PERFORMANCE TUNING:Approximating System Load 201

7.3.2 Shortest Job Next 202

PERFORMANCE TUNING:Predicting Wait Times for FCFS 203

7.3.3 Priority Scheduling 204

7.3.4 Deadline Scheduling 206

7.4 Preemptive Strategies 207

7.4.1 Round Robin 207

7.4.2 Multiple-level Queues 210

7.5 Summary 212

7.6 Exercises 213

Chapter 8 Basic Synchronization Principles 217

8.1 Interacting Processes 218

IN THE HANGAR:Solving a System of Linear Equations 219

8.1.1 Critical Sections 220

8.1.2 Deadlock 224

8.2 Coordinating Processes 226

8.3 Semaphores 228

8.3.1 Principles of Operation 229

IN THE HANGAR:Examples Using Semaphore 231

8.3.2 Practical Considerations 237

8.4 Shared Memory Multiprocessors 241

8.5 Summary 242

8.6 Exercises 242

LABORATORY EXERCISE:Bounded Buffer Problem 249

Background 249

Attacking the Problem 255

Chapter 9 High-lever Synchronization 257

9.1 Alternative Synchronization Primitiyes 258

9.1.1 AND Synchronization 258

9.1.2 Events 259

IN THE HANGAR:Using Events 260

IN THE HANGAR:UNIX Signals 261

IN THE HANGAR:Windows 2000 Dispatcher Objects 263

9.2 Monitors 264

9.2.1 Principles of Operation 264

9.2.2 Condition Variables 266

IN THE HANGAR:Examples Using Monitors 269

9.2.3 Some Practical Aspects of Using Monitors 273

9.3 Interprocess Communication 273

9.3.1 Mailboxes 274

9.3.2 Message Protocols 276

9.3.3 Using the send and receive Operations 276

IN THE HANGAR:Synchronized IPC 278

9.3.4 Deferred Message Copying 278

9.4 Explicitly Ordering Event Execution 279

9.6 Exercises 281

9.5 Summary 281

LABORATORY EXERCISE:Refining the Shell 285

Background 285

Attacking the Problem 290

Chapter 10 Deadlock 291

10.1 Background 292

10.1.1 Prevention 294

10.1.2 Avoidance 295

10.1.3 Detection and Recovery 295

10.1.4 Manual Deadlock Management 295

10.2 A System Deadlock Model 296

IN THE HANGAR:Single Resource Type 297

10.3.1 Hold and Wait 299

10.3 Prevention 299

10.3.2 Circular Wait 301

10.3.3 Allowing Preemption 303

10.4 Avoidance 304

10.4.1 The Banker's Algorithm 306

IN THE HANGAR:Using the Banker's Algorithm 307

10.5 Detection and Recovery 309

10.5.1 Serially Reusable Resources 310

10.5.2 Consumable Resources 316

10.5.3 General Resource Systems 320

10.5.4 Recovery 321

10.6 Summary 321

10.7 Exercises 322

Chapter 11 Memory Management 325

11.1 The Basics 326

11.1.1 Requirements on Primary Memory 326

11.1.2 Mapping the Address Space to Primary Memory 327

PERFORMANCE TUNING:Using Memory Hierarchies to Reduce Access Time 328

IN THE HANGAR:The Address Binding Procedure 330

11.1.3 Dynamic Memory for Data Structures 333

11.2 Memory Allocation 335

11.2.1 Fixed-partition Memory Strategies 336

11.2.2 Variable-partition Memory Strategies 337

11.2.3 Contemporary Allocation Strategies 340

PERFORMANCE TUNING:The Cost of Moving Programs 341

11.3 Dynamic Address Relocation 342

11.3.1 Runtime Bound Checking 346

IN THE HANGAR:Expanding Small Address Spaces 347

11.4 Memory Manager Strategies 348

11.4.1 Swapping 348

11.4.2 Virtual Memory 352

11.4.3 Shared-memory Multiprocessors 352

PERFORMANCE TUNING:Using Cache Memory 353

11.5 Summary 357

11.6 Exercises 357

Chapter 12 Virtual Memory 361

12.1 Address Translation 362

12.1.1 Address Space Mapping 362

12.1.2 Segmentation and Paging 364

12.2 Paging 365

12.2.1 Virtual Address Translation 367

PERFORMANCE TUNING:Page Table Implementations 370

12.3 Static Paging Algorithms 371

12.3.1 The Fetch Policy 372

12.3.2 Demand Paging Algorithms 372

12.3.3 Stack Algorithms 376

12.3.4 Implementing LRU 378

PERFORMANCE TUNING:Paging Performance 379

12.4 Dynamic Paging Algorithms 381

12.4.1 The Working Set Algorithm 381

IN THE HANGAR:Working Set Algorithm Example 383

12.4.2 Implementing the Working Set Algorithm 385

PERFORMANCE TUNING:Taking Advantage of Pages with IPC 387

IN THE HANGAR:Windows 2000 Virtual Memory 388

IN THE HANGAR:Linux Virtual Memory 392

12.5 Segmentation 393

12.5.1 Address Translation 394

12.5.2 Implementation 396

IN THE HANGAR:The Multics Segmentation System 399

12.6 Summary 401

12.7 Exercises 402

Chapter 13 File Management 405

13.1 Files 406

13.1.1 Low-level Files 408

13.1.2 Structured Files 412

13.1.4 Multimedia Storage 418

13.1.3 Database Management Systems 418

13.2 Low-level File Implementations 419

13.2.1 open and close Operations 420

IN THE HANGAR:UNIX open and close 420

13.2.2 Block Management 422

IN THE HANGAR:UNIX File Structure 425

13.2.3 Reading and Writing the Byte Stream 430

13.3 Supporting Other Storage Abstractions 431

13.3.1 Structured Sequential Files 431

13.3.2 Indexed Sequential Files 431

13.3.3 Database Management Systems 432

13.3.4 Multimedia Documents 432

13.4 Memory-mapped Files 433

IN THE HANGAR:Memory-mapped Files in Windows 2000 434

13.5 Directories 435

13.5.1 Directory Structures 436

IN THE HANGAR:Some Directory Examples 437

13.6 Directory Implementation 439

13.6.1 Device Directories 439

13.6.2 File Directory 440

13.6.3 Opening a File in a Hierarchical Directory 440

13.6.4 Mounting Removable File Systems 441

13.7 Summary 442

13.8 Exercises 442

LABORATORY EXERCISE:A Simple File Manager 445

Background 446

Attacking the Problem 449

Chapter 14 Protection and Security 453

14.1 Fundamentals 454

14.1.1 Policy and Mechanism 454

14.1.2 Implementing Policy and Mechanism 456

14.1.3 Authentication Mechanisms 456

14.1.4 Authorization Mechanisms 457

14.1.5 Encryption 458

14.2 Authentication 458

14.2.1 User Authentication 459

14.2.2 Authentication in Networks 459

IN THE HANGAR:Kerberos Network Authentication 461

14.3 Internal Access Authorization 463

14.3.1 A Model for Resource Protection 464

14.3.2 Changing the Protection State 466

14.3.3 The Cost of Protection Mechanisms 468

14.4 Implementing Internal Authorization 469

14.4.1 Protection Domains 469

14.4.2 Implementing the Access Matrix 471

14.5 Cryptography 476

14.6 Summary 477

14.7 Exercises 478

Chapter 15 Networks 481

15.1 From Computer Communications to Networks 482

15.1.1 Communication Subnetworks 483

15.1.2 Network Communication Protocols 484

15.2 The ISO OSI Network Architecture Model 485

15.2.1 The Evolution of Network Protocols 485

15.2.2 The ISO OSI Model 487

15.3 Low-level Protocols 490

15.3.1 The Physical Layer 491

PERFORMANCE TUNING:Fast Physical Layers 492

15.3.2 The Data Link Layer 493

15.3.3 Contemporary Networks 494

15.4 The Network Layer 496

15.4.1 Addressing 498

15.4.2 Routing 499

15.4.3 Using the Network Layer 501

15.5 The Transport Layer 502

15.5.1 Communication Ports 502

15.5.2 Data Types 503

15.5.3 Reliable Communication 504

PERFORMANCE TUNING:Datagrams and Virtual Circuits 505

15.6 Using the Transport Layer 506

15.6.1 Naming 506

IN THE HANGAR:The Domain Name System 508

15.6.2 The Client-server Model 509

15.7 Summary 511

15.8 Exercises 512

LABORATORY EXERCISE:Using TCP/IP 515

Background 515

Attacking the Problem 523

Chapter 16 Remote Files 525

16.1 Sharing Information Across the Network 526

16.1.1 Explicit File Copying Systems 527

16.1.2 Implicit File Sharing 528

16.1.3 The Remote Storage Interface 530

16.1.4 Distributing the Work 531

16.2 Remote Disk Systems 533

16.2.1 The Remote Disk Operation 534

16.2.2 Performance Considerations 535

16.2.3 Reliability 536

16.2.4 The Future of Remote Disks 539

16.3 Remote File Systems 539

16.3.1 The General Architecture 540

16.3.2 Block Caching 542

16.3.3 Crash Recovery 544

IN THE HANGAR:The Andrew File System 548

16.4 File-level Caching 548

IN THE HANGAR:The LOCUS File System 549

16.5 Directory Systems and Their Implementations 551

16.5.1 Filenames 552

16.5.2 Opening a File 554

16.6 Summary 555

16.7 Exercises 556

Chapter 17 Distributed Computing 559

17.1 Distributing Process Management 560

17.1.1 Partitioning the Work 560

17.1.2 Supporting Partitioned Computation 562

17.1.3 General Process Management 563

17.1.4 Scheduling 563

PERFORMANCE TUNING:Process Migration and Load Balancing 564

17.1.5 Coordinating Processes 565

17.2 Message Passing 568

17.2.1 Message-passing Interfaces 570

17.2.2 Computing Paradigms 572

17.3 Remote Procedure Call 573

17.3.1 How Does RPC Work? 573

17.3.2 Implementing RPC 575

17.4 Distributed-memory Management 579

17.4.1 Remote Memory 583

IN THE HANGAR:Examples of Distributed Memory 583

17.4.2 Distributed Virtual Memory 586

17.4.3 Distributed Objects 588

17.6 Exercises 589

17.5 Summary 589

Chapter 18 Strategies and Examples 591

18.1 OS Components and Relationships 592

18.2 General Organizational Issues 593

18.2.1 Software Organization 594

18.2.2 Managing Distributed Hardware 599

18.3 The Traditional UNIX Kernel 601

18.3.1 The Kernel 602

18.3.2 The Monolithic Organization 603

18.3.3 Conclusion 604

18.4 The Linux Kernel 604

18.4.1 Kernel Organization 604

18.4.2 Process and Resource Management 609

18.4.3 Memory Manager 615

18.4.4 File Management 616

18.5 Choices:An Object-oriented OS 618

18.5.1 Frameworks 618

18.5.2 Using a Framework for the Memory Manager 618

18.5.3 Conclusion 620

18.6 Microsoft Windows NT 621

18.6.1 General Architecture 621

18.6.2 The Hardware Abstraction Layer(HAL) 624

18.6.3 The NT Kernel 624

18.6.4 The NT Executive 626

18.6.5 NT Subsystems 631

18.7 The Mach Operating System 632

18.7.1 Process Management 633

18.7.2 Message Passing 635

18.7.3 Memory Management 638

18.7.4 Conclusion 640

18.8 The CHORUS Operating System 640

18.8.1 Process Management 642

18.8.2 Interprocess Communication 643

18.8.3 Memory Management 643

18.8.4 Conclusion 644

18.9 Summary 644

18.10 Exercises 644

Glossary 647

Bibliography 659

Index 663