《分布式操作系统》

1 INTRODUCTION TO DISTRIBUTED SYSTEMS1

1.1　WHAT IS A DISTRIBUTED SYSTEM?2

1.2 GOALS3

1.2.1 Advantages of Distributed Systems over Centralized Systems3

1.2.2 Advantages of Distributed Systems over Independent PCs6

1.2.3 Disadvantages of Distributed Systems6

1.3 HARDWARE CONCEPTS8

1.3.1 Bus-Based Multiprocessors10

1.3.2 Switched Multiprocessors12

1.3.3 Bus-Based Multicomputers13

1.3.4 Switched Multicomputers14

1.4 SOFTWARE CONCEPTS15

1.4.1 Network Operating Systems16

Contents16

PREFACE　16

1.4.2 True Distributed Systems18

1.4.3 Multiprocessor Timesharing Systems20

1.5.1 Transparency22

1.5 DESIGN ISSUES22

1.5.2 Flexibility25

1.5.3 Reliability27

1.5.4 Performance28

1.5.5 Scalability29

1.6 SUMMARY31

2 COMMUNICATION IN DISTRIBUTED SYSTEMS34

2.1 LAYERED PROTOCOLS35

2.1.2 The Data Link Layer38

2.1.1 The Physical Layer38

2.1.3 The Network Layer40

2.1.4 The Transport Layer40

2.1.5 The Session Layer41

2.1.6 The Presentation Layer41

2.1.7 The Application Layer42

2.2 ASYNCHRONOUS TRANSFER MODE NETWORKS42

2.2.1 What Is Asynchronous Transfer Mode?42

2.2.2 The ATM Physical Layer44

2.2.3 The ATM Layer45

2.2.4 The ATM Adaptation Layer46

2.2.5 ATM Switching47

2.2.6 Some Implications of ATM for Distributed Systems49

2.3 THE CLIENT-SERVER MODEL50

2.3.1 Clients and Servers51

2.3.2 An Example Client and Server52

2.3.3 Addressing56

2.3.4 Blocking versus Nonblocking Primitives58

2.3.5 Buffered versus Unbuffered Primitives61

2.3.6 Reliable versus Unreliable Primitives63

2.3.7 Implementing the Client-Server Model65

2.4 REMOTE PROCEDURE CALL68

2.4.1 Basic RPC Operation68

2.4.2 Parameter Passing72

2.4.3 Dynamic Binding77

2.4.4 RPC Semantics in the Presence of Failures80

2.4.5 Implementation Issues84

2.4.6 Problem Areas95

2.5.1 Introduction to Group Communication99

2.5 GROUP COMMUNICATION99

2.5.2 Design Issues101

2.5.3 Group Communication in ISIS110

2.6 SUMMARY114

3 SYNCHRONIZATION IN DISTRIBUTED SYSTEMS118

3.1 CLOCK SYNCHRONIZATION119

3.1.1 Logical Clocks120

3.1.2 Physical Clocks124

3.1.3 Clock Synchronization Algorithms127

3.1.4 Use of Synchronized Clocks132

3.2 MUTUAL EXCLUSION134

3.2.1 A Centralized Algorithm134

3.2.2 A Distributed Algorithm135

3.2.3 A Token Ring Algorithm138

3.2.4 A Comparison of the Three Algorithms139

3.3 ELECTION ALGORITHMS140

3.3.1 The Bully Algorithm141

3.3.2 A Ring Algorithm143

3.4.1 Introduction to Atomic Transactions144

3.4 ATOMIC TRANSACTIONS144

3.4.2 The Transaction Model145

3.4.3 Implementation150

3.4.4 Concurrency Control154

3.5 DEADLOCKS IN DISTRIBUTED SYSTEMS158

3.5.1 Distributed Deadlock Detection159

3.5.2 Distributed Deadlock Prevention163

3.6 SUMMARY165

4.1 THREADS169

4 PROCESSES AND PROCESSORS IN DISTRIBUTED SYSTEMS169

4.1.1 Introduction to Threads170

4.1.2 Thread Usage171

4.1.3 Design Issues for Threads Packages174

4.1.4 Implementing a Threads Package178

4.1.5 Threads and RPC184

4.2 SYSTEM MODELS186

4.2.1 The Workstation Model186

4.2.2 Using Idle Workstations189

4.2.3 The Processor Pool Model193

4.2.4 AHybridModel197

4.3 PROCESSOR ALLOCATION197

4.3.1 Allocation Models197

4.3.2 Design Issues for Processor Allocation Algorithms199

4.3.3 Implementation Issues for Processor Allocation Algorithms201

4.3.4 Example Processor Allocation Algorithms203

4.4 SCHEDULING IN DISTRIBUTED SYSTEMS210

4.5.1 Component Faults212

4.5 FAULT TOLERANCE212

4.5.2 System Failures213

4.5.3 Synchronous versus Asynchronous Systems214

4.5.4 Use of Redundancy214

4.5.5 Fault Tolerance Using Active Replication215

4.5.6 Fault Tolerance Using Primary-Backup217

4.5.7 Agreement in Faulty Systems219

4.6 REAL-TIME DISTRIBUTED SYSTEMS223

4.6.1 What Is a Real-Time System?223

4.6.2 Design Issues226

4.6.3 Real-Time Communication230

4.6.4 Real-Time Scheduling234

4.7 SUMMARY240

5 DISTRIBUTED FILE SYSTEMS245

5.1 DISTRIBUTED FILE SYSTEM DESIGN246

5.1.1 The File Service Interface246

5.1.2 The Directory Server Interface248

5.1.3 Semantics of File Sharing253

5.2 DISTRIBUTED FILE SYSTEM IMPLEMENTATION256

5.2.1 File Usage256

5.2.2 System Structure258

5.2.3 Caching262

5.2.4 Replication268

5.2.5 An Example:Sun's Network File System272

5.2.6 Lessons Learned278

5.3 TRENDS IN DISTRIBUTED FILE SYSTEMS279

5.3.1 New Hardware280

5.3.2 Scalability282

5.3.3 Wide Area Networking283

5.3.5 Fault Tolerance284

5.3.4 Mobile Users284

5.3.6 Multimedia285

5.4 SUMMARY285

6 DISTRIBUTED SHARED MEMORY289

6.1 INTRODUCTION290

6.2 WHAT IS SHARED MEMORY?292

6.2.1 On-Chip Memory293

6.2.2 Bus-Based Multiprocessors293

6.2.3 Ring-Based Multiprocessors298

6.2.4 Switched Multiprocessors301

6.2.5 NUMA Multiprocessors308

6.2.6 Comparison of Shared Memory Systems312

6.3 CONSISTENCY MODELS315

6.3.1 Strict Consistency315

6.3.2 Sequential Consistency317

6.3.3 Causal Consistency321

6.3.4 PRAM Consistency and Processor Consistency322

6.3.5 Weak Consistency325

6.3.6 Release Consistency327

6.3.7 Entry Consistency330

6.3.8 Summary of Consistency Models331

6.4 PAGE-BASED DISTRIBUTED SHARED MEMORY333

6.4.1 Basic Design334

6.4.2 Replication334

6.4.3 Granularity336

6.4.4 Achieving Sequential Consistency337

6.4.5 Finding the Owner339

6.4.6 Finding the Copies342

6.4.7 Page Replacement343

6.4.8 Synchronization344

6.5 SHARED-VARIABLE DISTRIBUTED SHARED MEMORY345

6.5.1 Munin346

6.5.2 Midway353

6.6 OBJECT-BASED DISTRIBUTED SHARED MEMORY356

6.6.1 Objects356

6.6.2 Linda358

6.6.3 Orca365

6.7 COMPARISON371

6.8 SUMMARY372

7 CASE STUDY 1:AMOEBA376

7.1 INTRODUCTION TO AMOEBA376

7.1.1 History of Amoeba376

7.1.2 Research Goals377

7.1.3 The Amoeba System Architecture378

7.1.4 The Amoeba Microkernel380

7.1.5 The Amoeba Servers382

7.2.1 Capabilities384

7.2 OBJECTS AND CAPABILITIES IN AMOEBA384

7.2.2 Obiect Protection385

7.2.3 Standard Operations387

7.3 PROCESS MANAGEMENT IN AMOEBA388

7.3.1 Processes388

7.3.2 Threads391

7.4 MEMORY MANAGEMENT IN AMOEBA392

7.4.1 Segments392

7.4.2 Mapped Segments393

7.5 COMMUNICATION IN AMOEBA393

7.5.1 Remote Procedure Call394

7.5.2 Group Communication in Amoeba398

7.5.3 The Fast Local Internet Protocol407

7.6 THE AMOEBA SERVERS415

7.6.1 The Bullet Server415

7.6.2 The Directory Server420

7.6.3 The Replication Server425

7.6.4 The Run Server425

7.6.6 The TCP/IP Server427

7.6.5 The Boot Server427

7.6.7 Other Servers428

7.7 SUMMARY428

8 CASE STUDY 2:MACH431

8.1 INTRODUCTION TO MACH431

8.1.1 History of Mach431

8.1.2 Goals of Mach433

8.1.3 The Mach Microkernel433

8.1.4 The Mach BSD UNIX Server435

8.2.1 Processes436

8.2 PROCESS MANAGEMENT IN MACH436

8.2.2 Threads439

8.2.3 Scheduling442

8.3 MEMORY MANAGEMENT IN MACH445

8.3.1 Virtual Memory446

8.3.2 Memory Sharing449

8.3.3 External Memory Managers452

8.3.4 Distributed Shared Memory in Mach456

8.4.1 Ports457

8.4 COMMUNICATION IN MACH457

8.4.2 Sending and Receiving Messages464

8.4.3 The Network Message Server469

8.5 UNIX EMULATION IN MACH471

8.6 SUMMARY472

9 CASE STUDY 3:CHORUS475

9.1 INTRODUCTION TO CHORUS475

9.1.1 History of Chorus476

9.1.2 Goals of Chorus477

9.1.3 System Structure478

9.1.4 Kernel Abstractions479

9.1.5 Kernel Structure481

9.1.6 The UNIX Subsystem483

9.1.7 The Object-Oriented Subsystem483

9.2 PROCESS MANAGEMENT IN CHORUS483

9.2.1 Processes484

9.2.2 Threads485

9.2.3 Scheduling486

9.2.4 Traps,Exceptions,and Interrupts487

9.2.5 Kernel Calls for Process Management488

9.3 MEMORY MANAGEMENT IN CHORUS490

9.3.1 Regions and Segments490

9.3.2 Mappers491

9.3.3 Distributed Shared Memory492

9.3.4 Kernel Calls for Memory Management493

9.4 COMMUNICATON IN CHORUS495

9.4.1 Messages495

9.4.2 Ports495

9.4.3 Communication Operations496

9.4.4 Kernel Calls for Communication498

9.5 UNIX EMULATION IN CHORUS499

9.5.1 Structure of a UNIX Process500

9.5.2 Extensions to UNIX500

9.5.3 Implementation of UNIX on Chorus501

9.6 COOL:AN OBJECT-ORIENTED SUBSYSTEM507

9.6.1 The COOL Architecture507

9.6.2 The COOL Base Layer507

9.6.3 The COOL Generic Runtime System509

9.6.4 The Language Runtime System509

9.7 COMPARISON OF AMOEBA,MACH,AND CHORUS510

9.6.5 Implementation of COOL510

9.7.1 Philosophy511

9.7.2 Obiects512

9.7.3 Processes513

9.7.4 Memory Model514

9.7.5 Communication515

9.7.6 Servers516

9.8 SUMMARY517

10.1.1 History of DCE520

10 CASE STUDY 4:DCE520

10.1 INTRODUCTION TO DCE520

10.1.2 Goals of DCE521

10.1.3 DCE Components522

10.1.4 Cells525

10.2 THREADS527

10.2.1 Introduction to DCE Threads527

10.2.2 Scheduling529

10.2.3 Synchronization530

10.2.4 Thread Calls531

10.3 REMOTE PROCEDURE CALL535

10.3.1 Goals of DCE RPC535

10.3.2 Writing a Client and a Server536

10.3.3 Binding a Client to a Server538

10.3.4 Performing an RPC539

10.4 TIME SERVICE540

10.4.1 DTS Time Model541

10.4.2 DTS Implementation543

10.5 DIRECTORY SERVICE544

10.5.1 Names546

10.5.2 The Cell Directory Service547

10.5.3 The Global Directory Service549

10.6 SECURITY SERVICE554

10.6.1 Security Model555

10.6.2 Security Components557

10.6.3 Tickets and Authenticators558

10.6.4 Authenticated RPC559

10.6.5 ACLs562

10.7 DISTRIBUTED FILE SYSTEM564

10.7.1 DFS Interface565

10.7.2 DFS Components in the Server Kernel566

10.7.3 DFS Components in the Client Kernel569

10.7.4 DFS Components in User Space571

10.8 SUMMARY573

11 BIBLIOGRAPHY AND SUGGESTED READINGS577

11.1 SUGGESTED READINGS577

11.2 ALPHABETICAL BIBLIOGRAPHY584

INDEX603