多线程、并行与分布式程序设计基础 影印版【2025|PDF下载-Epub版本|mobi电子书|kindle百度云盘下载】

多线程、并行与分布式程序设计基础 影印版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Chapter 1:The Concurrent Computing Landscape1

1.1 The Essence of Concurrent Programming2

1.2 Hardware Architectures4

1.2.1 Processors and Caches4

1.2.2 Shared-Memory Multiprocessors6

1.2.3 Distributed-Memory Multicomputers and Networks8

1.3 Applications and Programming Styles10

1.4 Iterative Parallelism:Matrix Multiplication13

1.5 Recursive Parallelism:Adaptive Quadrature17

1.6 Producers and Consumers:Unix Pipes19

1.7 Clients and Servers:File Systems21

1.8 Peers:Distributed Matrix Multiplication23

1.9 Summary of Programming Notation26

1.9.1 Declarations26

1.9.2 Sequential Statements27

1.9.3 Concurrent Statements,Processes,and Procedures29

Historical Notes31

1.9.4 Comments31

References33

Exercises34

Part 1:Shared-Variable Programming39

Chapter 2:Processes and Synchronization41

2.1 States,Actions,Histories,and Properties42

2.2 Parallelization:Finding Patterns in a File44

2.3 Synchronization:The Maximum of an Array48

2.4 Atomic Actions and Await Statements51

2.4.1 Fine-Grained Atomicity51

2.4.2 Specifying Synchronization:The Await Statement54

2.5 Producer/Consumer Synchronization56

2.6 A Synopsis of Axiomatic Semantics57

2.6.1 Formal Logical Systems58

2.6.2 A Programming Logic59

2.6.3 Semantics of Concurrent Execution62

2.7.1 Disjoint Variables65

2.7 Techniques for Avoiding Interference65

2.7.2 Weakened Assertions66

2.7.3 Global Invariants68

2.7.4 Synchronization69

2.7.5 An Example:The Array Copy Problem Revisited70

2.8 Safety and Liveness Properties72

2.8.1 Proving Safety Properties73

2.8.2 Scheduling Policies and Fairness74

Historical Notes77

References80

Exercises81

Chapter 3:Locks and Barriers93

3.1 The Critical Section Problem94

3.2 Critical Sections:Spin Locks97

3.2.1 Test and Set98

3.2.2 Test and Test and Set100

3.2.3 Implementing Await Statements101

3.3.1 The Tie-Breaker Algorithm104

3.3 Critical Sections:Fair Solutions104

3.3.2 The Ticket Algorithm108

3.3.3 The Bakery Algorithm111

3.4 Barrier Synchronization115

3.4.1 Shared Counter116

3.4.2 Flags and Coordinators117

3.4.3 Symmetric Barriers120

3.5 Data Parallel Algorithms124

3.5.1 Parallel Prefix Computations124

3.5.2 Operations on Linked Lists127

3.5.3 Grid Computations:Jacobi Iteration129

3.5.4 Synchronous Multiprocessors131

3.6 Parallel Computing with a Bag of Tasks132

3.6.1 Matrix Multiplication133

3.6.2 Adaptive Quadrature134

Historical Notes135

References139

Exercises141

Chapter 4:Semaphores153

4.1 Syntax and Semantics154

4.2 Basic Problems and Techniques156

4.2.1 Critical Sections:Mutual Exclusion156

4.2.2 Barriers:Signaling Events156

4.2.3 Producers and Consumers:Split Binary Semaphores158

4.2.4 Bounded Buffers:Resource Counting160

4.3 The Dining Philosophers164

4.4 Readers and Writers166

4.4.1 Readers/Writers as an Exclusion Problem167

4.4.2 Readers/Writers Using Condition Synchronization169

4.4.3 The Technique of Passing the Baton171

4.4.4 Alternative Scheduling Policies175

4.5 Resource Allocation and Scheduling178

4.5.1 Problem Definition and General Solution Pattern178

4.5.2 Shortest-Job-Next Allocation180

4.6 Case Study:Pthreads184

4.6.1 Thread Creation185

4.6.2 Semaphores186

4.6.3 Example:A Simple Producer and Consumer186

Historical Notes188

References190

Exercises191

Chapter 5:Monitors203

5.1 Syntax and Semantics204

5.1.1 Mutual Exclusion206

5.1.2 Condition Variables207

5.1.3 Signaling Disciplines208

5.1.4 Additional Operations on Condition Variables212

5.2 Synchronization Techniques213

5.2.1 Bounded Buffers:Basic Condition Synchronization213

5.2.2 Readers and Writers:Broadcast Signal215

5.2.3 Shortest-Job-Next Allocation:Priority Wait217

5.2.4 Interval Timer:Covering Conditions218

5.2.5 The Sleeping Barber:Rendezvous221

5.3 Disk Scheduling:Program Structures224

5.3.1 Using a Separate Monitor228

5.3.2 Using an Intermediary230

5.3.3 Using a Nested Monitor235

5.4 Case Study:Java237

5.4.1 The Threads Class238

5.4.2 Synchronized Methods239

5.4.3 Parallel Readers/Writers241

5.4.4 Exclusive Readers/Writers243

5.4.5 True Readers/Writers245

5.5 Case Study:Pthreads246

5.5.1 Locks and Condition Variables246

5.5.2 Example:Summing the Elements of a Matrix248

Historical Notes250

References253

Exercises255

Chapter 6:Implementations265

6.1 A Single-Processor Kernel266

6.2 A Multiprocessor Kernel270

6.3 Implementing Semaphores in a Kernel276

6.4 Implementing Monitors in a Kernel279

6.5 Implementing Monitors Using Semaphores283

Historical Notes284

References286

Exercises287

Part 2:Distributed Programming291

Chapter 7:Message Passing295

7.1 Asynchronous Message Passing296

7.2 Filters:A Sorting Network298

7.3 Clients and Servers302

7.3.1 Active Monitors302

7.3.2 A Self-Scheduling Disk Server308

7.3.3 File Servers:Conversational Continuity311

7.4 Interacting Peers:Exchanging Values314

7.5 Synchronous Message Passing318

7.6 Case Study:CSP320

7.6.1 Communication Statements321

7.6.2 Guarded Communication323

7.6.3 Example:The Sieve of Eratosthenes326

7.6.4 Occam and Modern CSP328

7.7 Case Study:Linda334

7.7.1 Tuple Space and Process Interaction334

7.7.2 Example:Prime Numbers with a Bag of Tasks337

7.8 Case Study:MPI340

7.8.1 Basic Functions341

7.8.2 Global Communication and Synchronization343

7.9 Case Study:Java344

7.9.1 Networks and Sockets344

7.9.2 Example:A Remote File Reader345

Historical Notes348

References351

Exercises353

Chapter 8:RPC and Rendezvous361

8.1 Remote Procedure Call362

8.1.1 Synchronization in Modules364

8.1.2 A Time Server365

8.1.3 Caches in a Distributed File System367

8.1.4 A Sorting Network of Merge Filters370

8.1.5 Interacting Peers:Exchanging Values371

8.2 Rendezvous373

8.2.1 Input Statements374

8.2.2 Client/Server Examples376

8.2.3 A Sorting Network of Merge Filters379

8.2.4 Interacting Peers:Exchanging Values381

8.3 A Multiple Primitives Notation382

8.3.1 Invoking and Servicing Operations382

8.3.2 Examples384

8.4 Readers/Writers Revisited386

8.4.1 Encapsulated Access387

8.4.2 Replicated Files389

8.5.1 Remote Method Invocation393

8.5 Case Study:Java393

8.5.2 Example:A Remote Database395

8.6 Case Study:Ada397

8.6.1 Tasks398

8.6.2 Rendezvous399

8.6.3 Protected Types401

8.6.4 Example:The Dining Philosophers403

8.7.1 Resources and Globals406

8.7 Case Study:SR406

8.7.2 Communication and Synchronization408

8.7.3 Example:Critical Section Simulation409

Historical Notes411

References415

Exercises416

Chapter 9:Paradigms for Process Interaction423

9.1.1 Sparse Matrix Multiplication424

9.1 Manager/Workers(Distributed Bag of Tasks)424

9.1.2 Adaptive Quadrature Revisited428

9.2 Heartbeat Algorithms430

9.2.1 Image Processing:Region Labeling432

9.2.2 Cellular Automata:The Game of Life435

9.3 Pipeline Algorithms437

9.3.1 A Distributed Matrix Multiplication Pipeline438

9.3.2 Matrix Multiplication by Blocks441

9.4 Probe/Echo Algorithms444

9.4.1 Broadcast in a Network444

9.4.2 Computing the Topology of a Network448

9.5 Broadcast Algorithms451

9.5.1 Logical Clocks and Event Ordering452

9.5.2 Distributed Semaphores454

9.6 Token-Passing Algorithms457

9.6.1 Distributed Mutual Exclusion457

9.6.2 Termination Detection in a Ring460

9.6.3 Termination Detection in a Graph462

9.7 Replicated Servers465

9.7.1 Distributed Dining Philosophers466

9.7.2 Decentralized Dining Philosophers467

Historical Notes471

References474

Exercises477

Chapter 10:Implementations487

10.1 Asynchronous Message Passing488

10.1.1 Shared-Memory Kernel488

10.1.2 Distributed Kernel491

10.2 Synchronous Message Passing496

10.2.1 Direct Communication Using Asynchronous Messages497

10.2.2 Guarded Communication Using a Clearinghouse498

10.3 RPC and Rendezvous504

10.3.1 RPC in a Kernel504

10.3.2 Rendezvous Using Asynchronous Message Passing507

10.3.3 Multiple Primitives in a Kernel509

10.4 Distributed Shared Memory515

10.4.1 Implementation Overview516

10.4.2 Page Consistency Protocols518

Historical Notes520

References521

Exercises522

Part 3:Parallel Programming527

Chapter 11:Scientific Computing533

11.1.1 Laplace s Equation534

11.1 Grid Computations534

11.1.2 Sequential Jacobi Iteration535

11.1.3 Jacobi Iteration Using Shared Variables540

11.1.4 Jacobi Iteration Using Message Passing541

11.1.5 Red/Black Successive Over-Relaxation(SOR)546

11.1.6 Multigrid Methods549

11.2 Particle Computations553

11.2.1 The Gravitational N-Body Problem554

11.2.2 Shared-Variable Program555

11.2.3 Message-Passing Programs559

11.2.4 Approximate Methods569

11.3 Matrix Computations573

11.3.1 Gaussian Elimination573

11.3.2 LU Decomposition575

11.3.3 Shared-Variable Program576

11.3.4 Message-Passing Program581

Historical Notes583

References584

Exercises585

Chapter 12:Languages,Compilers,Libraries,and Tools591

12.1 Parallel Programming Libraries592

12.1.1 Case Study:Pthreads593

12.1.2 Case Study:MPI593

12.1.3 Case Study:OpenMP595

12.2 Parallelizing Compilers603

12.2.1 Dependence Analysis604

12.2.2 Program Transformations607

12.3 Languages and Models614

12.3.1 Imperative Languages616

12.3.2 Coordination Languages619

12.3.3 Data Parallel Languages620

12.3.4 Functional Languages623

12.3.5 Abstract Models626

12.3.6 Case Study:High-Performance Fortran(HPF)629

12.4.1 Performance Measurement and Visualization633

12.4 Parallel Programming Tools633

12.4.2 Metacomputers and Metacomputing634

12.4.3 Case Study:The Globus Toolkit636

Historical Notes638

References642

Exercises644

Glossary647

Index657