《MODERN OPERATING SYSTEMS》求取 ⇩

1INTRODUCTION1

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 Manager5

1.2.HISTORY OF OPERATING SYSTEMS6

1.2.1.The First Generation (1945-55)6

1.2.2.The Second Generation (1955-65)7

1.2.3.The Third Generation (1965-1980)9

1.2.4.The Fourth Generation (1980-Present)13

1.2.5.Ontogeny Recapitulates Phylogeny16

1.3.THE OPERATING SYSTEM ZOO18

1.3.1.Mainframe Operating Systems18

1.3.2.Server Operating Systems19

1.3.3.Multiprocessor Operating Systems19

1.3.4.Personal Computer Operating Systems19

1.3.5.Real-Time Operating Systems19

1.3.6.Embedded Operating Systems20

1.3.7.Smart Card Operating Systems20

1.4.COMPUTER HARDWARE REVIEW20

1.4.1.Processors21

1.4.2.Memory23

1.4.3.I/O Devices28

1.4.4.Buses31

1.5.OPERATING SYSTEM CONCEPTS34

1.5.1.Processes34

1.5.2.Deadlocks36

1.5.3.Memory Management37

1.5.4.Input/Output38

1.5.5.Files38

1.5.6.Security41

1.5.7.The Shell41

1.5.8.Recycling of Concepts43

1.6.SYSTEM CALLS44

1.6.1.System Calls for Process Management48

1.6.2.System Calls for File Management50

1.6.3.System Calls for Directory Management51

1.6.4.Miscellaneous System Calls53

1.6.5.The Windows Win32 API53

1.7.OPERATING SYSTEM STRUCTURE56

1.7.1.Monolithic Systems56

1.7.2.Layered Systems57

1.7.3.Virtual Machines59

1.7.4.Exokemels61

1.7.5.Client-Server Model61

1.8.RESEARCH ON OPERATING SYSTEMS63

1.9.OUTLINE OF THE REST OF THIS BOOK65

1.10.METRIC UNITS66

1.11.SUMMARY67

2PROCESSES AND THREADS71

2.1.PROCESSES71

2.1.1.The Process Model72

2.1.2.Process Creation73

2.1.3.Process Termination75

2.1.4.Process Hierarchies76

2.1.5.Process States77

2.1.6.Implementation of Processes79

2.2.THREADS81

2.2.1.The Thread Model81

2.2.2.Thread Usage85

2.2.3.Implementing Threads in User Space90

2.2.4.Implementing Threads in the Kernel93

2.2.5.Hybrid Implementations94

2.2.6.Scheduler Activations94

2.2.7.Pop-Up Threads96

2.2.8.Making Single-Threaded Code Multithreaded97

2.3.INTERPROCESS COMMUNICATION100

2.3.1.Race Conditions100

2.3.2.Critical Regions102

2.3.3.Mutual Exclusion with Busy Waiting103

2.3.4.Sleep and Wakeup108

2.3.5.Semaphores110

2.3.6.Mutexes113

2.3.7.Monitors115

2.3.8.Message Passing119

2.3.9.Barriers123

2.4.CLASSICAL IPC PROBLEMS124

2.4.1.The Dining Philosophers Problem125

2.4.2.The Readers and Writers Problem128

2.4.3.The Sleeping Barber Problem129

2.5.SCHEDULING132

2.5.1.Introduction to Scheduling132

2.5.2.Scheduling in Batch Systems138

2.5.3.Scheduling in Interactive Systems142

2.5.4.Scheduling in Real-Time Systems148

2.5.5.Policy versus Mechanism149

2.5.6.Thread Scheduling150

2.6.RESEARCH ON PROCESSES AND THREADS151

2.7.SUMMARY152

3DEADLOCKS159

3.1.RESOURCES160

3.1.1.Preemptable and Nonpreemptable Resources160

3.1.2.Resource Acquisition161

3.2.INTRODUCTION TO DEADLOCKS163

3.2.1.Conditions for Deadlock164

3.2.2.Deadlock Modeling164

3.3.THE OSTRICH ALGORITHM167

3.4.DEADLOCK DETECTION AND RECOVERY168

3.4.1.Deadlock Detection with One Resource of Each Type168

3.4.2.Deadlock Detection with Multiple Resource of Each Type171

3.4.3.Recovery from Deadlock173

3.5.DEADLOCK AVOIDANCE175

3.5.1.Resource Trajectories175

3.5.2.Safe and Unsafe States176

3.5.3.The Banker's Algorithm for a Single Resource178

3.5.4.The Banker's Algorithm for Multiple Resources179

3.6.DEADLOCK PREVENTION180

3.6.1.Attacking the Mutual Exclusion Condition180

3.6.2.Attacking the Hold and Wait Condition181

3.6.3.Attacking the No Preemption Condition182

3.6.4.Attacking the Circular Wait Condition182

3.7.OTHER ISSUES183

3.7.1.Two-Phase Locking183

3.7.2.Nonresource Deadlocks184

3.7.3.Starvation184

3.8.RESEARCH ON DEADLOCKS185

3.9.SUMMARY185

4MEMORY MANAGEMENT189

4.1.BASIC MEMORY MANAGEMENT190

4.1.1.Monoprogramming without Swapping or Paging190

4.1.2.Multiprogramming with Fixed Partitions191

4.1.3.Modeling Multiprogramming192

4.1.4.Analysis of Multiprogramming System Performance194

4.1.5.Relocation and Protection194

4.2.SWAPPING196

4.2.1.Memory Management with Bitmaps199

4.2.2.Memory Management with Linked Lists200

4.3.VIRTUAL MEMORY202

4.3.1.Paging202

4.3.2.Page Tables205

4.3.3.TLBs—Translation Lookaside Buffers211

4.3.4.Inverted Page Tables213

4.4.PAGE REPLACEMENT ALGORITHMS214

4.4.1.The Optimal Page Replacement Algorithm215

4.4.2.The Not Recently Used Page Replacement Algorithm216

4.4.3.The First-In, First-Out217

4.4.4.The Second Chance Page Replacement Algorithm217

4.4.5.The Clock Page Replacement Algorithm218

4.4.6.The Least Recently Used218

4.4.7.Simulating LRU in Software220

4.4.8.The Working Set Page Replacement Algorithm222

4.4.9.The WSClock Page Replacement Algorithm225

4.4.:Summary of Page Replacement Algorithms227

4.5.MODELING PAGE REPLACEMENT ALGORITHMS228

4.5.1.Belady's Anomaly229

4.5.2.Stack Algorithms229

4.5.3.The Distance String232

4.5.4.Predicting Page Fault Rates233

4.6.DESIGN ISSUES FOR PAGING SYSTEMS234

4.6.1.Local versus Global Allocation Policies234

4.6.2.Load Control236

4.6.3.Page Size237

4.6.4.Separate Instruction and Data Spaces239

4.6.5.Shared Pages239

4.6.6.Cleaning Policy241

4.6.7.Virtual Memory Interface241

4.7.IMPLEMENTATION ISSUES242

4.7.1.Operating System Involvement with Paging242

4.7.2.Page Fault Handling243

4.7.3.Instruction Backup244

4.7.4.Locking Pages in Memory246

4.7.5.Backing Store246

4.7.6.Separation of Policy and Mechanism247

4.8.SEGMENTATION249

4.8.1.Implementation of Pure Segmentation253

4.8.2.Segmentation with Paging: MULTICS254

4.8.3.Segmentation with Paging: The Intel Pentium257

4.9.RESEARCH ON MEMORY MANAGEMENT262

4.10.SUMMARY262

5INPUT/OUTPUT269

5.1.PRINCIPLES OF I/O HARDWARE269

5.1.1.I/O Devices270

5.1.2.Device Controllers271

5.1.3.Memory-Mapped I/O272

5.1.4.Direct Memory Access276

5.1.5.Interrupts Revisited279

5.2.PRINCIPLES OF I/O SOFTWARE282

5.2.1.Goals of the I/O Software283

5.2.2.Programmed I/O284

5.2.3.Interrupt-Driven I/O286

5.2.4.I/O Using DMA287

5.3.I/O SOFTWARE LAYERS287

5.3.1.Interrupt Handlers287

5.3.2.Device Drivers289

5.3.3.Device-Independent I/O Software292

5.3.4.User-Space I/O Software298

5.4.DISKS300

5.4.1.Disk Hardware300

5.4.2.Disk Formatting315

5.4.3.Disk Arm Scheduling Algorithms318

5.4.4.Error Handling322

5.4.5.Stable Storage324

5.5.CLOCKS327

5.5.1.Clock Hardware328

5.5.2.Clock Software329

5.5.3.Soft Timers332

5.6.CHARACTER-ORIENTED TERMINALS333

5.6.1.RS-232 Terminal Hardware334

5.6.2.Input Software336

5.6.3.Output Software341

5.7.GRAPHICAL USER INTERFACES342

5.7.1.Personal Computer Keyboard, Mouse, and Display Hardware343

5.7.2.Input Software347

5.7.3.Output Software for Windows347

5.8.NETWORK TERMINALS355

5.8.1.The X Window System356

5.8.2.The SLIM Network Terminal360

5.9.POWER MANAGEMENT363

5.9.1.Hardware Issues364

5.9.2.Operating System Issues365

5.9.3.Degraded Operation370

5.10.RESEARCH ON INPUT/OUTPUT371

5.11.SUMMARY372

6FILE SYSTEMS379

6.1.FILES380

6.1.1.File Naming380

6.1.2.File Structure382

6.1.3.File Types383

6.1.4.File Access385

6.1.5.File Attributes386

6.1.6.File Operations387

6.1.7.An Example Program Using File System Calls389

6.1.8.Memory-Mapped Files391

6.2.DIRECTORIES393

6.2.1.Single-Level Directory Systems393

6.2.2.Two-level Directory Systems394

6.2.3.Hierarchical Directory Systems395

6.2.4.Path Names395

6.2.5.Directory Operations398

6.3.FILE SYSTEM IMPLEMENTATION399

6.3.1.File System Layout399

6.3.2.Implementing Files400

6.3.3.Implementing Directories405

6.3.4.Shared Files408

6.3.5.Disk Space Management410

6.3.6.File System Reliability416

6.3.7.File System Performance424

6.3.8.Log-Structured File Systems428

6.4.EXAMPLE FILE SYSTEMS430

6.4.1.CD-ROM File Systems430

6.4.2.The CP/M File System435

6.4.3.The MS-DOS File System438

6.4.4.The Windows 98 File System442

6.4.5.The UNIX V7 File System445

6.5.RESEARCH ON FILE SYSTEMS448

6.6.SUMMARY448

7MULTIMEDIA OPERATING SYSTEMS453

7.1.INTRODUCTION TO MULTIMEDIA454

7.2.MULTIMEDIA FILES458

7.2.1.Audio Encoding459

7.2.2.Video Encoding461

7.3.VIDEO COMPRESSION463

7.3.1.The JPEG Standard464

7.3.2.The MPEG Standard467

7.4.MULTIMEDIA PROCESS SCHEDULING469

7.4.1.Scheduling Homogeneous Processes469

7.4.2.General Real-Time Scheduling470

7.4.3.Rate Monotonic Scheduling472

7.4.4.Earliest Deadline First Scheduling473

7.5. MULTIMEDIA FILE SYSTEM PARADIGMS475

7.5.1.VCR Control Functions476

7.5.2.Near Video on Demand478

7.5.3.Near Video on Demand with VCR Functions479

7.6.FILE PLACEMENT481

7.6.1.Placing a File on a Single Disk481

7.6.2.Two Alternative File Organization Strategies482

7.6.3.Placing Files for Near Video on Demand486

7.6.4.Placing Multiple Files on a Single Disk487

7.6.5.Placing Files on Multiple Disks490

7.7.CACHING492

7.7.1.Block Caching492

7.7.2.File Caching494

7.8.DISK SCHEDULING FOR MULTIMEDIA494

7.8.1.Static Disk Scheduling495

7.8.2.Dynamic Disk Scheduling496

7.9.RESEARCH ON MULTIMEDIA498

7.10.SUMMARY499

8MULTIPLE PROCESSOR SYSTEMS503

8.1. MULTIPROCESSORS506

8.1.1.Multiprocessor Hardware506

8.1.2.Multiprocessor Operating System Types513

8.1.3.Multiprocessor Synchronization516

8.1.4.Multiprocessor Scheduling521

8.2. MULTICOMPUTERS526

8.2.1.Multicomputer Hardware527

8.2.2.Low-Level Communication Software531

8.2.3.User-Level Communication Software534

8.2.4.Remote Procedure Call537

8.2.5.Distributed Shared Memory540

8.2.6.Multicomputer Scheduling544

8.2.7.Load Balancing545

8.3.DISTRIBUTED SYSTEMS549

8.3.1.Network Hardware551

8.3.2.Network Services and Protocols553

8.3.3.Document-Based Middleware558

8.3.4.File System-Based Middleware559

8.3.5.Shared Object-Based Middleware565

8.3.6.Coordination-Based Middleware572

8.4.RESEARCH ON MULTIPLE PROCESSOR SYSTEMS577

8.5.SUMMARY577

9SECURITY583

9.1.THE SECURITY ENVIRONMENT584

9.1.1.Threats584

9.1.2.Intruders585

9.1.3.Accidental Data Loss586

9.2.BASICS OF CRYPTOGRAPHY587

9.2.1.Secret-Key Cryptography588

9.2.2.Public-Key Cryptography588

9.2.3.One-Way Functions589

9.2.4.Digital Signatures590

9.3.USER AUTHENTICATION591

9.3.1.Authentication Using Passwords592

9.3.2.Authentication Using a Physical Object601

9.3.3.Authentication Using Biometrics603

9.3.4.Countermeasures606

9.4.ATTACKS FROM INSIDE THE SYSTEM606

9.4.1.Trojan Horses607

9.4.2.Login Spoofing608

9.4.3.Logic Bombs609

9.4.4.Trap Doors610

9.4.5.Buffer Overflow610

9.4.6.Generic Security Attacks613

9.4.7.Famous Security Flaws614

9.4.8.Design Principles for Security616

9.5.ATTACKS FROM OUTSIDE THE SYSTEM617

9.5.1.Virus Damage Scenarios618

9.5.2.How Viruses Work619

9.5.3.How Viruses Spread626

9.5.4.Antivirus and Anti-Antivirus Techniques628

9.5.5.The Internet Worm635

9.5.6.Mobile Code637

9.5.7.Java Security642

9.6.PROTECTION MECHANISMS645

9.6.1.Protection Domains645

9.6.2.Access Control Lists647

9.6.3.Capabilities650

9.7.TRUSTED SYSTEMS653

9.7.1.Trusted Computing Base654

9.7.2.Formal Models of Secure Systems655

9.7.3.Multilevel Security657

9.7.4.Orange Book Security659

9.7.5.Covert Channels661

9.8.RESEARCH ON SECURITY665

9.9.SUMMARY666

10 CASE STUDY 1: UNIX AND LINUX671

10.1.HISTORY OF UNIX672

10.1.1.UNICS672

10.1.2.PDP-11 UNIX673

10.1.3.Portable UNIX674

10.1.4.Berkeley UNIX675

10.1.5.Standard UNIX676

10.1.6.MINIX677

10.1.7.Linux678

10.2.OVERVIEW OF UNIX681

10.2.1.UNIX Goals681

10.2.2.Interfaces to UNIX682

10.2.3.The UNIX Shell683

10.2.4.UNIX Utility Programs686

10.2.5.Kernel Structure687

10.3.PROCESSES IN UNIX690

10.3.1.Fundamental Concepts690

10.3.2.Process Management System Calls in UNIX692

10.3.3.Implementation of Processes in UNIX699

10.3.4.Booting UNIX708

10.4.MEMORY MANAGEMENT IN UNIX710

10.4.1.Fundamental Concepts711

10.4.2.Memory Management System Calls in UNIX714

10.4.3.Implementation of Memory Management in UNIX715

10.5.INPUT/OUTPUT IN UNIX723

10.5.1.Fundamental Concepts724

10.5.2.Input/Output System Calls in UNIX726

10.5.3.Implementation of Input/Output in UNIX727

10.5.4.Streams730

10.6.THE UNIX FILE SYSTEM732

10.6.1.Fundamental Concepts732

10.6.2.File System Calls in UNIX736

10.6.3.Implementation of the UNIX File System740

10.6.4.NFS: The Network File System747

10.7.SECURITY IN UNIX753

10.7.1.Fundamental Concepts753

10.7.2.Security System Calls in UNIX755

10.7.3.Implementation of Security in UNIX756

10.8.SUMMARY757

11 CASE STUDY 2: WINDOWS 2000763

11.1.HISTORY OF WINDOWS 2000763

11.1.1.MS-DOS763

11.1.2.Windows 95/98/Me764

11.1.3.Windows NT765

11.1.4.Windows 2000767

11.2.PROGRAMMING WINDOWS 2000771

11.2.1.The Win32 Application Programming Interface772

11.2.2.The Registry774

11.3.SYSTEM STRUCTURE778

11.3.1.Operating System Structure778

11.3.2.Implementation of Objects787

11.3.3.Environment Subsystems792

11.4.PROCESSES AND THREADS IN WINDOWS 2000796

11.4.1.Fundamental Concepts796

11.4.2.Job, Process, Thread and Fiber Management API Calls799

11.4.3.Implementation of Processes and Threads802

11.4.4.MS-DOS Emulation809

11.4.5.Booting Windows 2000810

11.5.MEMORY MANAGEMENT811

11.5.1.Fundamental Concepts812

11.5.2.Memory Management System Calls816

11.5.3.Implementation of Memory Management817

11.6.INPUT/OUTPUT IN WINDOWS 2000824

11.6.1.Fundamental Concepts824

11.6.2.Input/Output API Calls825

11.6.3.Implementation of I/O827

11.6.4.Device Drivers827

11.7.THE WINDOWS 2000 FILE SYSTEM830

11.7.1.Fundamental Concepts830

11.7.2.File System API Calls in Windows 2000831

11.7.3.Implementation of the Windows 2000 File System833

11.8.SECURITY IN WINDOWS 2000844

11.8.1.Fundamental Concepts845

11.8.2.Security API Calls847

11.8.3.Implementation of Security848

11.9.CACHING IN WINDOWS 2000849

11.10.SUMMARY851

12 OPERATING SYSTEM DESIGN855

12.1.THE NATURE OF THE DESIGN PROBLEM856

12.1.1.Goals856

12.1.2.Why is it Hard to Design an Operating Systems?857

12.2.INTERFACE DESIGN859

12.2.1.Guiding Principles859

12.2.2.Paradigms861

12.2.3.The System Call Interface864

12.3 IMPLEMENTATION867

12.3.1.System Structure867

12.3.2.Mechanism versus Policy870

12.3.3.Orthogonality871

12.3.4.Naming872

12.3.5.Binding Time874

12.3.6.Static versus Dynamic Structures875

12.3.7.Top-Down versus Bottom-Up Implementation876

12.3.8.Useful Techniques877

12.4.PERFORMANCE882

12.4.1.Why are Operating Systems Slow?882

12.4.2.What Should be Optimized?883

12.4.3.Space-Time Trade-offs884

12.4.4.Caching887

12.4.5.Hints888

12.4.6.Exploiting Locality888

12.4.7.Optimize the Common Case889

12.5.PROJECT MANAGEMENT889

12.5.1.The Mythical Man Month890

12.5.2.Team Structure891

12.5.3.The Role of Experience893

12.5.4.No Silver Bullet894

12.6.TRENDS IN OPERATING SYSTEM DESIGN894

12.6.1.Large Address Space Operating Systems894

12.6.2.Networking895

12.6.3.Parallel and Distributed Systems896

12.6.4.Multimedia896

12.6.5.Battery-Powered Computers896

12.6.6.Embedded Systems897

12.7.SUMMARY897

13 READING LIST AND BIBLIOGRAPHY901

13.1.SUGGESTIONS FOR FURTHER READING901

13.1.1.Introduction and General Works902

13.1.2.Processes and Threads902

13.1.3.Deadlocks903

13.1.4.Memory Management903

13.1.5.Input/Output903

13.1.6.File Systems904

13.1.7.Multimedia Operating Systems905

13.1.8.Multiple Processor Systems906

13.1.9.Security907

13.1.10.UNIX and Linux908

13.1.11.Windows 2000909

13.1.12.Design Principles910

13.2 ALPHABETICAL BIBLIOGRAPHY911

INDEX935