The Art of Multiprocessor Programming

Front Cover......Page 1
The Art of Multiprocessor Programming......Page 4
Copyright......Page 5
Dedication......Page 6
Table of Contents......Page 8
Acknowledgments......Page 18
Preface......Page 22
Practitioner Track......Page 24
CS Major Track......Page 25
1 Introduction......Page 26
1.1 Shared Objects and Synchronization......Page 28
1.2 A Fable......Page 31
1.2.1 Properties of Mutual Exclusion......Page 33
1.2.2 The Moral......Page 34
1.3 The Producer–Consumer Problem......Page 35
1.4 The Readers–Writers Problem......Page 37
1.5 The Harsh Realities of Parallelization......Page 38
1.7 Chapter Notes......Page 40
1.8 Exercises......Page 41
I Principles......Page 44
2.1 Time......Page 46
2.2 Critical Sections......Page 47
2.3 2-Thread Solutions......Page 49
2.3.1 The LockOne Class......Page 50
2.3.2 The LockTwo Class......Page 51
2.3.3 The Peterson Lock......Page 52
2.4 The Filter Lock......Page 53
2.6 Lamport\'s Bakery Algorithm......Page 56
2.7 Bounded Timestamps......Page 58
2.8 Lower Bounds on the Number of Locations......Page 62
2.9 Chapter Notes......Page 65
2.10 Exercises......Page 66
3.1 Concurrency and Correctness......Page 70
3.2 Sequential Objects......Page 73
3.3 Quiescent Consistency......Page 74
3.4 Sequential Consistency......Page 76
3.4.1 Remarks......Page 77
3.5 Linearizability......Page 79
3.6 Formal Definitions......Page 80
3.6.2 Compositional Linearizability......Page 82
3.6.3 The Nonblocking Property......Page 83
3.7 Progress Conditions......Page 84
3.7.1 Dependent Progress Conditions......Page 85
3.8 The Java Memory Model......Page 86
3.8.1 Locks and Synchronized Blocks......Page 87
3.8.3 Final Fields......Page 88
3.9 Remarks......Page 89
3.10 Chapter Notes......Page 90
3.11 Exercises......Page 91
4 Foundations of Shared Memory......Page 96
4.1 The Space of Registers......Page 97
4.2 Register Constructions......Page 102
4.2.2 A Regular Boolean MRSW Register......Page 103
4.2.3 A Regular M-Valued MRSW Register......Page 104
4.2.4 An Atomic SRSW Register......Page 106
4.2.5 An Atomic MRSW Register......Page 107
4.2.6 An Atomic MRMW Register......Page 110
4.3.1 An Obstruction-Free Snapshot......Page 112
4.3.2 A Wait-Free Snapshot......Page 113
4.3.3 Correctness Arguments......Page 115
4.4 Chapter Notes......Page 118
4.5 Exercises......Page 119
5 The Relative Power of Primitive Synchronization Operations......Page 124
5.1 Consensus Numbers......Page 125
5.1.1 States and Valence......Page 126
5.2 Atomic Registers......Page 128
5.4 FIFO Queues......Page 131
5.5 Multiple Assignment Objects......Page 135
5.6 Read–Modify–Write Operations......Page 137
5.7 Common2 RMW Operations......Page 139
5.8 The compareAndSet() Operation......Page 141
5.9 Chapter Notes......Page 142
5.10 Exercises......Page 143
6.1 Introduction......Page 150
6.3 A Lock-Free Universal Construction......Page 151
6.4 A Wait-Free Universal Construction......Page 155
6.5 Chapter Notes......Page 161
6.6 Exercises......Page 162
II\nPractice......Page 164
7.1 Welcome to the Real World......Page 166
7.2 Test-And-Set Locks......Page 169
7.3 TAS-Based Spin Locks Revisited......Page 171
7.4 Exponential Backoff......Page 172
7.5 Queue Locks......Page 174
7.5.1 Array-Based Locks......Page 175
7.5.2 The CLH Queue Lock......Page 176
7.5.3 The MCS Queue Lock......Page 179
7.6 A Queue Lock with Timeouts......Page 182
7.7 A Composite Lock......Page 184
7.7.1 A Fast-Path Composite Lock......Page 190
7.8.1 A Hierarchical Backoff Lock......Page 192
7.8.2 A Hierarchical CLH Queue Lock......Page 193
7.10 Chapter Notes......Page 198
7.11 Exercises......Page 199
8.1 Introduction......Page 202
8.2 Monitor Locks and Conditions......Page 203
8.2.1 Conditions......Page 204
8.2.2 The Lost-Wakeup Problem......Page 206
8.3 Readers–Writers Locks......Page 208
8.3.1 Simple Readers–Writers Lock......Page 209
8.3.2 Fair Readers–Writers Lock......Page 210
8.4 Our Own Reentrant Lock......Page 212
8.6 Chapter Notes......Page 214
8.7 Exercises......Page 215
9.1 Introduction......Page 220
9.2 List-Based Sets......Page 221
9.3 Concurrent Reasoning......Page 223
9.4 Coarse-Grained Synchronization......Page 225
9.5 Fine-Grained Synchronization......Page 226
9.6 Optimistic Synchronization......Page 230
9.7 Lazy Synchronization......Page 233
9.8 Non-Blocking Synchronization......Page 238
9.9 Discussion......Page 243
9.11 Exercises......Page 244
10.1 Introduction......Page 248
10.2 Queues......Page 249
10.3 A Bounded Partial Queue......Page 250
10.4 An Unbounded Total Queue......Page 254
10.5 An Unbounded Lock-Free Queue......Page 255
10.6 Memory Reclamation and the ABA Problem......Page 258
10.6.1 A Naïve Synchronous Queue......Page 262
10.7 Dual Data Structures......Page 263
10.9 Exercises......Page 266
11.2 An Unbounded Lock-Free Stack......Page 270
11.3 Elimination......Page 273
11.4.1 A Lock-Free Exchanger......Page 274
11.4.2 The Elimination Array......Page 276
11.5 Chapter Notes......Page 279
11.6 Exercises......Page 280
12.2 Shared Counting......Page 284
12.3 Software Combining......Page 285
12.3.1 Overview......Page 286
FIRST......Page 289
ROOT......Page 290
12.3.2 An Extended Example......Page 292
12.4 Quiescently Consistent Pools and Counters......Page 294
12.5.1 Networks That Count......Page 295
12.5.2 The Bitonic Counting Network......Page 298
A Software Bitonic Counting Network......Page 299
Proof of Correctness......Page 301
A Periodic Counting Network......Page 303
A Software Periodic Counting Network......Page 304
12.5.3 Performance and Pipelining......Page 305
12.6 Diffracting Trees......Page 307
12.8 Sorting Networks......Page 311
12.8.1 Designing a Sorting Network......Page 312
A Bitonic Sorting Algorithm......Page 313
12.9 Sample Sorting......Page 315
12.10 Distributed Coordination......Page 316
12.11 Chapter Notes......Page 317
12.12 Exercises......Page 318
13.1 Introduction......Page 324
13.2 Closed-Address Hash Sets......Page 325
13.2.1 A Coarse-Grained Hash Set......Page 327
13.2.2 A Striped Hash Set......Page 328
13.2.3 A Refinable Hash Set......Page 330
13.3.1 Recursive Split-Ordering......Page 334
13.3.2 The BucketList Class......Page 337
13.3.3 The LockFreeHashSet Class......Page 338
13.4.1 Cuckoo Hashing......Page 341
13.4.2 Concurrent Cuckoo Hashing......Page 343
13.4.3 Striped Concurrent Cuckoo Hashing......Page 347
13.4.4 A Refinable Concurrent Cuckoo Hash Set......Page 349
13.5 Chapter Notes......Page 350
13.6 Exercises......Page 351
14.2 Sequential Skiplists......Page 354
14.3.1 A Bird\'s-Eye View......Page 356
14.3.2 The Algorithm......Page 358
14.4.1 A Bird\'s-Eye View......Page 364
14.4.2 The Algorithm in Detail......Page 366
14.6 Chapter Notes......Page 373
14.7 Exercises......Page 374
15.1.1 Concurrent Priority Queues......Page 376
15.2 An Array-Based Bounded Priority Queue......Page 377
15.3 A Tree-Based Bounded Priority Queue......Page 378
15.4 An Unbounded Heap-Based Priority Queue......Page 380
15.4.1 A Sequential Heap......Page 381
Bird\'s-Eye View......Page 382
In Detail......Page 383
15.5 A Skiplist-Based Unbounded Priority Queue......Page 388
15.7 Exercises......Page 391
16.1 Introduction......Page 394
16.2 Analyzing Parallelism......Page 400
16.3 Realistic Multiprocessor Scheduling......Page 403
16.4.1 Work Stealing......Page 405
16.4.2 Yielding and Multiprogramming......Page 406
16.5.1 A Bounded Work-Stealing Dequeue......Page 407
16.5.2 An Unbounded Work-Stealing DEQueue......Page 411
16.5.3 Work Balancing......Page 414
16.6 Chapter Notes......Page 416
16.7 Exercises......Page 417
17.1 Introduction......Page 422
17.2 Barrier Implementations......Page 423
17.3 Sense-Reversing Barrier......Page 424
17.4 Combining Tree Barrier......Page 425
17.5 Static Tree Barrier......Page 427
17.6 Termination Detecting Barriers......Page 429
17.7 Chapter Notes......Page 433
17.8 Exercises......Page 434
18.1.1 What is Wrong with Locking?......Page 442
18.1.2 What is Wrong with compareAndSet()?......Page 443
18.1.3 What is Wrong with Compositionality?......Page 445
18.2 Transactions and Atomicity......Page 446
18.3 Software Transactional Memory......Page 449
18.3.1 Transactions and Transactional Threads......Page 452
18.3.2 Zombies and Consistency......Page 453
18.3.3 Atomic Objects......Page 454
18.3.5 Contention Managers......Page 456
18.3.6 Implementing Atomic Objects......Page 458
18.3.7 An Obstruction-Free Atomic Object......Page 459
Bird\'s-Eye View......Page 460
Why It Works......Page 461
In Detail......Page 462
18.3.8 A Lock-Based Atomic Object......Page 463
Bird\'s-Eye View......Page 464
Why It Works......Page 465
In Detail......Page 466
18.4 Hardware Transactional Memory......Page 470
18.4.1 Cache Coherence......Page 471
18.4.3 Enhancements......Page 472
18.5 Chapter Notes......Page 473
18.6 Exercises......Page 474
III Appendix......Page 476
A.2.1 Threads......Page 478
A.2.2 Monitors......Page 480
A.2.4 Thread-Local Objects......Page 483
A.3.1 Threads......Page 485
A.3.2 Monitors......Page 486
A.3.3 Thread-Local Objects......Page 487
A.4 Pthreads......Page 489
A.4.1 Thread-Local Storage......Page 490
A.5 Chapter Notes......Page 491
B.1 Introduction (and a Puzzle)......Page 494
B.3 Interconnect......Page 497
B.5 Caches......Page 498
B.5.1 Coherence......Page 499
B.6 Cache-Conscious Programming, or the Puzzle Solved......Page 501
B.7 Multi-Core and Multi-Threaded Architectures......Page 502
B.7.1 Relaxed Memory Consistency......Page 503
B.8 Hardware Synchronization Instructions......Page 504
B.10 Exercises......Page 506
Bibliography......Page 508
A......Page 520
C......Page 521
E......Page 523
H......Page 524
L......Page 525
N......Page 527
P......Page 528
R......Page 529
S......Page 530
U......Page 532
Z......Page 533