Index
A
ABA problem
basic scenario, 235
load-linked–store-conditional, 237
and memory reclamation, 233–237
Abort, memory transactions, 422
Abstract
BaseHashSet class, 301
concurrent Cuckoo hashing, 318
contention manager, 432
Abstraction map
concurrent reasoning, 199
LockFreeList class, 216
Abstract value, concurrent reasoning, 198
Acquires
CLHLock class, 154
CompositeLock class, 161
definition, 23
FineList class, 203
HCLHLock lock, 173
Java concepts, 456
locks, 178
MCSLock class, 156
Active thread
in software combining, 260
termination detection barrier, 405
Addressing
closed-address hash sets, 300–302
concurrent closed-addressing, 325
definitions, 300
hardware concepts, 473
open-addressed hash set, 316–318
Algorithms
Bakery lock, 31–33
bitonic sorting, 288–289
Dynamic Software Transactional Memory, 448
fast path, 43
lock-based concurrent skiplist, 333–339
lock-free concurrent skiplist, 341–348
lock-free universal, 127
lock-free universal construction, 128
quicksort, 290
SkipList class, 349
Transactional Locking 2, 448
TTASLock, 147–149
wait-free universal construction, 131
Amdahl’s Law
definition, 13
in parallelization, 13–14
Announce event, wait-free universal construction, 130–132
Anonymous inner class
Java thread concepts, 454
software transactional memory, 426
Anonymous method, C# concepts, 460
Antisymmetric, timestamps, 34
Array-based bounded priority queues, implementation, 352–353
Array-based locks
implementation, 150–151
without false sharing, 152
Asynchronous
definition, 1
threads, 71
Atomic hardware step
compare-and-swap, 480
shared counter implementation, 5–6
Atomicity and transactions, 421–423
AtomicMarkableReference class
function, 234
function and methods, 213–215
AtomicMRSWRegister class, implementation, 83
Atomic objects
implementation, 433–434
lock-based, 438–445
obstruction-free, 434–438
software transactional memory, 429–431
Atomic primitives, problems, 418–420
AtomicReference class
function, 236
unbounded lock-free queue, 231
Atomic register
for consensus problem, 103–105
definition, 73
first definition, 93
history, 65
implementation considerations, 75–76
MRMW, 85–87
MRSW, 82–85
Atomic snapshots
construction, 93
correctness arguments, 90–93
definition, 87
and multiple assignment, 110
obstruction-free, 87–88
wait-free snapshot, 88–90
AtomicSRSWRegister class, implementation, 83
AtomicStampedReference class
bounded work-stealing dequeue, 383
function, 234
Atomic step, 456
Auxiliary variables, wait-free universal construction, 133–134
B
Backoff lock
contention manager, 432
hierarchical, 167–168
BackoffLock class
implementation, 148
problems, 149
Bakery lock
bounds, 39
in mutual exclusion, 31–33
as spin locks, 141
Balancer
counting networks, 270
operation, 271
sorting networks, 286–287
Balancer class, software bitonic counting network, 275
Balancing, work, 389–391
Balancing network, construction, 271–272
Barriers
combining tree, 400–402
definition, 398
implementation, 398–399
sense-serving, 399–400
static tree, 402–404
supporting concepts, 397–398
survey, 408
BaseHashSet class
implementation, 300–301
methods, 302
thresholds, 301
Batching, definition, 478
Benevolent side effect, lock-free lists, 217
Bitonic class, implementation, 276
Bitonic counting network
basic concepts, 273–274
proof of correctness, 276–278
recursive structure, 274
sequential execution, 272
software implementation, 274–276
Bitonic sorting algorithm, design and function, 288–289
Bivalence, protocol state, 102
Blocking
concurrent objects, 59
in Java memory model, 62–63
locks, 178
Block network, implementation, 281
Boolean register
atomic SRSW, 81–82
definition, 72
MRSW, 77–78
safe MRSW, 78–79
safe SRSW, 86
Bottom wires
counting networks, 270
sorting networks, 286
Bouncer class
array layout, 44
implementation, 43
Bounded, pool, 223
BoundedDEQueue class, implementation, 382–384
Bounded partial queue
considerations and drawbacks, 228–229
implementation, 225–227
BoundedQueue class
C# constructs, 462–463
fields and constructor, 225
list node, 227
methods, 226–227
Bounded-range priority queue
array-based, 352–353
definition, 351
tree-based, 353–355
Bounded transactional queue, implementation, 423
Bounded wait-free method, concurrent objects, 59
Bounded work-stealing double-ended queues
creator, 391
implementation, 382–386
Bucket
BaseHashSet class, 301
definition, 300
split-ordered hash set, 311
BucketList class, implementation, 312–313
Bucket threshold, BaseHashSet class, 301
Buffer, between producers and consumers, 223
Bursty, producers, 223
Bus
cache coherence, 446
definition, 145
Bus controller, 472
Busy–waiting, definition, 141
C
Cache
Cache blocks, definition, 474
Cache coherence
as BackoffLock problem, 149
hardware concepts, 474–476
hardware transactional memory, 446–447
Cache-coherent NUMA, 474
Cache hit, definition, 146
Cache lines, definition, 474
Cache miss, definition, 146
Callable object, definition, 371
Calls
atomic methods, 423
successful or unsuccessful, 196
Capacity
BaseHashSet class, 301
pool, 223
semaphore, 189
CAS, See Compare-and-swap (CAS) instruction
Church-Turing Thesis, 71
Clean double collect, obstruction-free snapshot, 88
CLHLock lock, creators, 174
CLH queue lock
hierarchical, 168–172
lock acquisition and release, 154
methods, 153
Closed-address hash sets, basic concepts, 300–302
Closed addressing, definition, 300
Cluster id, hierarchical locks, 167
Coarse-grained hash set, implementation, 302–303
Coarse-grained synchronization
definition, 195
implementations, 200–201
CoarseHashSet class, implementation, 302–303
CoarseList class, methods, 200–201
Collects
obstruction-free snapshot, 87–88
single-writer atomic snapshot class, 91
Collisions, hash sets, 300
Combining, software, 260–261
Combining phase, CombiningTree, 265
Combining status, definition, 261
Combining tree barrier
creators, 408
implementation, 400–402
CombiningTree class
combining status, 261–262
constructor, 262
disadvantages, 261
distribution phase, 267
methods, 264
Node class, 265–267
performance, 269
precombining phase, 262
robustness, 269
status, 268
Combining trees, original idea, 292
Common2 register
definition, 117
RMW, 114–116
Communication, and mutual exclusion, 9–10
Comparator, comparison network, 286
compareAndSet() operation
hardware synchronization, 480
synchronization primitives, 116–117
Compare-and-swap (CAS) instruction, hardware considerations, 480
Comparison network, definition, 286
CompositeFastPathLock class, methods, 166
Composite lock
advantages, 159–160
fast-path, 165–167
CompositeLock class
execution, 164
fields, constructor, and methods, 160
methods, 161–163
properties, 165
QNode class, 161
Compositional, correctness property, 51
Compositionality, problems, 420–421
Compositional linearizability, concurrent objects, 57–58
Concrete representation, concurrent reasoning, 198
Concurrency
concurrent objects, 45–48
reasoning, 198–200
Concurrent algorithm
challenges, 15
definition, 2
Concurrent closed-addressing schemes, creators, 325
Concurrent Cuckoo hashing, definition and implementation, 318–322
Concurrent heap
overview, 357–358
structure and implementation, 358–363
Concurrent objects
compositional linearizability, 57–58
concurrency, 45–48
correctness, 45–48
dependent progress conditions, 60–61
formal definitions, 55–57
nonblocking property, 58–59
progress conditions, 59–60
quiescent consistency, 49–51
sequential consistency, 51–54
sequential objects, 48–49
Concurrent priority queues, implementation, 351–352
Concurrent program
definition, 2
synchronization universality hierarchy, 126
Concurrent shared memory computing, definition, 71
Concurrent skiplists, overview, 348
Concurrent timestamping, Lock class, 34
Condition field, bounded partial queues, 225
Conditions objects
interface, 180
interrupts, 179
LockedQueue class, 182
lost wakeups, 181–183
usage example, 179–180
Consensus numbers
definition, 100
interface and definitions, 100–101
states and valence, 101–103
Consensus object
interface, 100
lock-free universal construction, 126–130
universality definition, 126
wait-free universal construction, 130–136
Consensus synchronization problem
atomic register solution, 103–105
Common2 registers, 114–116
consensus protocols, 106
definition, 100
FIFO queues, 106–109
Consenus protocols, generic, 106
Consistency, software transactional memory, 428–429
Consumers
naive synchronous queue, 237
pools, 223
Contention
definition, 147
high and low, 147
LockFreeStack, 248
Contention manager
greedy and karma, 448
implementation, 433
software transactional memory, 431–433
Context switch, definition, 472
Convoying, in locking, 417
Coordination protocol (OR Protocol), definition, 6
Copyable class, interface, 430
Correctness
bitonic counting network, 276–278
compositional, 51
concurrent objects, 45–48
Merger class, 277
Correctness arguments, atomic snapshots, 90–93
Counters
definition, 22
quiescient consistency, 269–270
as shared counter implementation, 4–5
Counting, shared, 259–260
Counting networks
basic concepts, 270
bitonic, 272–278
components, 270–273
invention, 292
performance, 280–281
periodic, 278–280
pipelining, 280–281
Critical-path length, parallelism, 376–377
Critical sections
as BackoffLock problem, 149
Java concepts, 456
in mutual exclusion, 22–24
C# construct concepts
creators, 466
monitors, 461–462
thread-local objects, 462–463
threads, 460–461
Cuckoo hashing
creators, 325
definition and implementation, 316–318
D
DAG, See Directed acyclic graph (DAG)
Data, and memory, 473
Data structure design
dual data structures, 239–241
SkipList class, 330
Deadlock
avoidance, 417–418
FineList class, 204
freedom from deadlock, 24
software transactional memory, 431
unbounded total queue, 230
Deadlock-freedom property
definition, 8
as dependent progress condition, 60
Filter lock, 31
Decision value, consensus numbers, 101
Delegate, C# concepts, 460
DEQueue, See Double-ended queue (DEQueue)
Deschedule, threads, 472
DiffractingBalancer class, implementation, 284
Diffracting trees
basic concept, 282
DiffractingBalancer, 284
implementation, 285
performance, 285
Prism, 283–284
Directed acyclic graph (DAG)
creators, 391
definition, 375
Fibonacci sequence, 375–376
steps, 380
Direct mapped cache, definition, 474
Direct-mapped caches, definition, 448
Dirty, definition, 478
Disjoint-access-parallelism
coining of term, 325
definition, 299
Dissemination barrier, creators, 408
Distributed coordination, overview, 291–292
Distribution phase, CombiningTree, 267
Doorway section, in Lock class, 31
Double-checked locking
in Java memory model, 61–62
and memory consistency, 479
Double-ended queue (DEQueue)
work stealing, 380–389
Down state, balancers, 271
Dual data structures
definition, 239
implementation, 239–241
reservation, 238–239
Dynamic Software Transactional Memory algorithm, creators, 448
E
Elimination, LockFreeStack, 248–249
EliminationBackoffStack class
basic concept, 249
efficiency, 255
elimination array, 251–254
lock-free exchanger, 249–251
methods, 253
structure, 248
EventListener class, incorrect example, 64
Events, in state machine, 21
Executor service, definition, 371
Exponential backoff
implementation, 149
TTASLock algorithm, 147–149
Extensible hashing, definition, 300
F
Factory, Lock interface, 178
Fairness
in mutual exclusion, 31
pools, 224
Fair readers–writers lock
fields, 185
fields and public methods, 186
inner read lock, 186
inner write lock, 187
False sharing
abscence in ALock, 152
array-based locks, 151
occurrence, 476
Fault-tolerance, in mutual exclusioin, 9
Fence, definition, 479
Fibonacci sequence
definition, 375
directed acyclic graph, 375–376
FibTask class
implementation, 375
FIFO queue, lock-based, 45–48
Filter lock
in mutual exclusion, 28–31
as spin locks, 141
Final fields, in Java memory model, 63–64
Final state, consensus numbers, 101
FineGrainedHeap class
creators, 366
implementation, 358–361
overview, 357–358
structure, 362
Fine-grained synchronization
basic concepts, 201–202
definition, 195
FineList class
deadlock, 204
hand-over-hand locking, 204
lock acquisitions, 203
methods, 202–203
FIRST, CombiningTree, 264–265
First-come-first-served
definition, 31
First-in-first-out (FIFO)
for consensus problem, 106–108
pool fairness, 224
via Pthreads, 466
quiescent consistency, 51
sequential objects, 48–49
FIRST status
CombiningTree, 268
definition, 261
Frames, definition, 397
Freedom from deadlock property, in Lock algorithm, 24
Freedom from starvation, in Lock algorithm, 24
Free list, for node recycling, 233–234
FreeObject class, structure, 436–438
Future interface, definition, 371
G
Ghost variables, See Auxiliary variables
Global queue, in HCLHLock queue, 168
Global state, definition, 37
Global threshold, BaseHashSet class, 301
Granularity, and cache, 474
Greedy
contention manager, 432
schedule, 379
Greedy contention manager, creators, 448
H
Hand-and-over-hand locking, FineList class, 204
Handlers, software transactional memory, 428
Hardware concepts
architectures, 477–479
basic considerations, 469–472
cache-conscious programming, 476–477
caches, 473–474
coherence, 474–476
interconnect, 472–473
memory, 473
processors and threads, 472
spinning, 476
synchronization instructions, 480–481
Hardware transactional memory (HTM)
cache coherence, 446–447
enhancements, 447–448
first proposal, 448
overview, 445–446
transactional cache coherence, 447
Hash function, definition, 300
Hashing, definition, 299
Hash sets
closed-address, 300–302
definition, 299–300
resizing, 305
HBOLock class, implementation, 168
HCLHLock queue
acquisition and release, 173
components, 168
fields and constructor, 169
global queue, 171
inner QNode class, 169
Head, definition, 224
Hierarchical backoff lock, implementation, 167–168
Hierarchical CLH queue lock, design, 168–172
Hierarchical locks, definition, 167
High contention, definition, 147
Hit rate, and cache, 474
Hit ratio, and cache, 474
Hits, in cache, 474
Hold, locks, 178
Hot spot, definition, 259–260
HTM, See Hardware transactional memory (HTM)
I
IDLE, CombiningTree, 264
Idle step, scheduler, 379
Inactive thread, termination detection barrier, 405
Initial state, consensus numbers, 101
Inner classes
anonymous, 426
definition, 183
tree nodes, 402
Inner read lock
fair readers–writers lock, 187
simple readers–writers lock, 184
Inner write lock
fair readers–writers lock, 187
simple readers–writers lock, 185
In-place array sorting, function, 288
Instantaneous events, in mutual exclusion, 22
Interference
concurrent reasoning, 198
optimistic synchronization, 207
Interrupts
Conditions objects, 179
definition, 9
Invariants, concurrent reasoning, 198
Invocation events
concurrent objects, 56
lock-free universal algorithm, 127
and register space, 76
Irreflexive, timestamps, 34
Items
hash sets, 300
priority queue, 351
PrioritySkipList class, 363
set definition, 196
software transactional memory, 426
J
Java construct concepts
creator, 466
monitors, 454–458
thread-local objects, 458–459
threads, 453–454
yielding and sleeping, 458
Java memory model
basic principles, 61–62
final fields, 63–64
locks and synchronized blocks, 62–63
volatile fields, 63
Join
C# constructs, 460
Join, Java threads, 454
K
Karma contention manager
characteristics, 432
creators, 448
Kernel maps, function, 378
k-way set associative, caches, 474
L
Labels
Bakery lock algorithm, 32
timestamps as, 34
Last-in-first-out (LIFO), StackT class, 245
Latency, definition, 259
Layer network, implementation, 279–280
Layout, distributed coordination, 292
Lazy
PrioritySkipList class, 363
unbounded lock-free queue, 231–232
LazyList class
fields, 214
linearizability, 212
methods, 209–210
LazySkipList class
creators, 348
overview, 331–333
Lazy synchronization
advantages, 213
basic concepts, 208–209
creators, 219
definition, 196
linearization, 211–212
methods, 209–210
Levels, in Filter lock, 28
Line, cache coherence, 446
Linearizability
applications, 45
concurrent priority queues, 351
concurrent reasoning, 199
first definition, 93
LazyList class, 212
wait-free universal construction, 133
Linearization points
concurrent objects, 55
fine-grained synchronization, 204
LazyList class, 211
Linear speedup, parallelism, 377
Linked lists
coarse-grained synchronization, 200–201
concurrent reasoning, 198–200
early work, 219
fine-grained synchronization, 201–205
lazy synchronization, 208–213
list-based sets, 196–198
lock-free list, 213–218
optimistic synchronization, 205–208
overview, 195–196
List-based sets, basic concepts, 196–198
List nodes
bounded partial queue, 227
lock-free stack, 247
unbounded lock-free queue, 230
Liveness property, definition, 2
Load-linked–store-conditional (LL/SC)
and ABA problem, 237
hardware synchronization, 480
origins, 136
Loads
definition, 37
Lock algorithm bounds, 37
in registers, 72
Locality, and cache, 474
Local spinning, definition, 147
Local state, definition, 37
Lock-based atomic object
consistency, 440–441
overview, 439–440
structure details, 441–445
Lock-based concurrent skiplist
algorithm, 333–339
overview, 331–333
Lock-based hash table, resizing, 305
Lock class
interface, 178–179
lower bounds, 37–40
for mutual exclusion, 141–144
timeout, 157
timestamping, 34
Lock coupling
definition, 202
invention, 219
LockedQueue class, with locks and conditions, 182
Lock-free concurrent skiplist
algorithm, 341–348
overview, 339–341
Lock-free exchanger
basic function, 249
implementation, 250
Lock-free hash set
basic concept, 309
BucketList class, 312–313
implementation, 313–315
recursive initialization, 316
recursive split-ordering, 309–312
LockFreeHashSet class, implementation, 313–315
LockFreeList class, methods, 217–219
Lock-free lists
abstraction maps, 216
AtomicMarkableReference, 213–215
basic concepts, 213–214
methods, 217–219
Window class, 216
Lock-free method
concurrent objects, 60
concurrent reasoning, 199
definition, 99
LockFreeQueue class
creators, 241
list node, 230
LockFreeQueueRecycle class, implementation, 236
LockFreeSkipList class
call structure, 340
creators, 348–349
overview, 339
LockFreeStack class
creators, 255
elimination, 248–249
implementation, 246–247
structure, 246
Lock-free universal construction
algorithm, 128
execution, 129
generic sequential object, 126–127
Locking
double-checked, in Java memory model, 61–62
execution, 47
hand-and-over-hand locking, FineList class, 204
problems, 417–418
LockOne class, for mutual exclusion, 25–26
Lockout-freedom property
definition, 8–9
as dependent progress condition, 60
in Lock algorithm, 24
in producer–consumer problem, 10–11
Locks
acquires, 178
array-based locks, 150–152
backoff lock, 167–168
block, 178
C# constructs, 461
definition, 22
fair readers–writers lock, 186–187
hardware concepts, 469
hierarchical backoff lock, 167–168
hierarchical CLH queue lock, 168–172
hierarchical locks, 167
hold, 178
interface, 23
Java concepts, 456
in Java memory model, 62–63
lock-based atomic object, 439
MCS queue lock, 154–156
queue locks, 149–159
readers–writers lock, 183–187
read lock, 183
reentrant lock, 187–189
releases, 178
simple readers–writers lock, 183–185
spin, 178
test-and-set locks, 144–146
write lock, 184
Lock striping, hash sets, 304
LockTwo class, for mutual exclusion, 26–27
Logical buckets, lock-free hash set, 309
Logical fields, obstruction-free atomic object, 435
Logical removal
PrioritySkipList class, 363
Loser thread, Common2 register, 114
Lost-wakeup problem
Conditions objects, 182–185
example, 183
Java concepts, 458
Low contention, definition, 147
M
Main cache, hardware transactional memory, 448
Matrix class, implementation, 372
Matrix multiplication, parallel, See Parallel matrix multiplication
MatrixTask class, implementation, 373–374
MCSLock class, creators, 174
MCS queue lock
fields and constructor, 154–155
lock acquisition and release, 156
methods, 155
QNode, 155–156
Memory consistency models
relaxed, 478–479
survey, 481
Memory contention
definition, 474
and shared counting, 260
Memory fence, See Memory barriers
Memory locations, lower bounds, 37–40
Memory reclamation, and ABA problem, 233–237
Merger class
correctness, 277
software bitonic counting network, 275
MERGER network, logical structure, 273
MESI protocol
Intel processors, 481
state transition examples, 475
Metalock, 174
Method calls
concurrent objects, 56
definition, 48
quiescent consistency, 49–50
and register space, 76
RMW registers, 112–113
Misses, in cache, 474
MMThread class, implementation, 370
Monitor locks
definitions, 178–179
execution, 180–181
invention, 190
Monitors
creators, 466
as C# constructs, 461–462
as Java constructs, 454–458
MRMW, See Multi-reader multiple-writer (MRMW)
MRSW, See Multi-reader single-writer (MRSW)
multiCompareAndSet, pseudocode, 419
Multi-core architecture, definition, 477–479
Multicores, programming challenges, 1
Multiple assignment objects, basic concept, 110
Multiprogrammed environment, work distribution, 381–382
Multi-reader multiple-writer (MRMW)
atomic register, 85–87
construction, 93
Multi-reader single-writer (MRSW)
atomic register, 82–85
Boolean register, 77–78
construction, 93
and register space, 73
regular Boolean register, 78–79
regular M-valued register, 79–81
safe registers, 78
write order, 76
Multi-threaded architecture, definition, 477–479
Mutexes, in Pthreads, 464–465
Mutual exclusion
Bakery lock algorithm, 31–33
bounded timestamps, 33–36
and communication, 9–10
in concurrent programming, 15
critical sections, 22–24
definition, 6
fairness, 31
fast path algorithm, 43
Filter lock, 28–31
Java concepts, 456
LockOne class, 25–26
LockTwo class, 26–27
number of locations, 37–40
Peterson Lock, 27–28
in producer–consumer problem, 10–11
properties, 8–9
real-world approach, 141–144
and register space, 73
time, 21–22
M-valued register
definition, 72
regular MRSW, 79–81
N
Naive synchronous queue
basic concepts, 237
implementation, 238
New version field, obstruction-free atomic object, 435
Node class
implementation, 127
StaticTreeBarrier class, 405
tree barriers, 400–402
Nodes
and free lists, 233–234
NUMA architecture, 472
predecessor nodes, 171
regular nodes, 197
Nonblocking methods, definition, 45
Nonblocking progress, concurrent objects, 59
Nonblocking property, concurrent objects, 58–59
Nonblocking synchronization, definition, 196
Non-transactional cache, hardware transactional memory, 448
Nonuniform memory access (NUMA) architecture
basic concepts, 472–473
spinning, 476
North wires
counting networks, 270
periodic network, 279
Notify, Java concepts, 457
O
Object, definition, 48
Obstruction-free atomic object
basis, 448
consistency, 436–437
operation details, 437
overview, 435
Obstruction-free property, as dependent progress condition, 60
Obstruction-free snapshot, collects, 87–88
OddEven sorting network, design, 288
Old version field, obstruction-free atomic object, 435
Open-addressed hash set, Cuckoo hashing, 316–318
Open addressing, definition, 300
Operator, definition, 455
Operator thread, definition, 455
OptimisticList class
implementation, 205
methods, 206–207
validation, 208
Optimistic synchronization
basic concepts, 205
class implementations, 205–207
definition, 195
validation, 207
Owner field, obstruction-free atomic object, 435
P
Parallelism
analysis, 375–378
definition, 1
and shared counting, 260
Parallelization, realities, 13–14
Parallel matrix multiplication
MatrixTask class, 373–374
overview, 369–370
Parallel programming, challenges, 15
Parallel sorting, basic concepts, 286
Partial method
creators, 241
pool, 224
Partial order, concurrent objects, 56
Passive thread, in software combining, 260
Pending
invocation, concurrent objects, 56
method calls, 50
Performance
CombiningTree, 269
counting networks, 280–281
diffracting trees, 285
hardware concepts, 471
Periodic counting networks
implementation, 281
software implementation, 279–280
structure, 278–279
Persistent communication, and mutual exclusion, 9
Peterson lock
bounds, 39
implementation, 142–143
in mutual exclusion, 27–28
PhasedCuckooHashSet class, implementation, 318–321
Phases
computation organization, 397
concurrent Cuckoo hashing, 318
Physical removal
PrioritySkipList class, 363
Pipelining, counting networks, 280–281
Pools
definition, 223
parallel matrix multiplication, 370
queues, 224
quiescently-consistent, 269–270
and shared counting, 259
termination detection barrier, 408
varieties, 223–224
work stealing, 406–407
Population-oblivious method, concurrent objects, 59
Postcondition, sequential objects, 48
Precedence graph, timestamps, 34
Precedence relation, in mutual exclusion, 22
Precombining phase, CombiningTree, 262
Precondition, sequential objects, 48
Predecessor nodes, HCLHLock queue, 172
Predecessor task, directed acyclic graph, 375
Priority
contention manager, 432
in priority queue, 351
Priority inversion, in locking, 417
Priority queues, definition, 351
PrioritySkipList class
implementation, 364
overview, 363
structure, 365
Prism
diffracting trees, 283
distributed coordination, 291
implementation, 284
Probabilistic data structure, SkipList class, 330
Probe sets, concurrent Cuckoo hashing, 318
Producer–consumer problem, example, 10–11
Producer–consumer property, in producer–consumer problem, 10–11
Producers
naive synchronous queue, 237
pools, 223
Program correctness (or Correctness), definition, 2
Program order, definition, 52
Program performance, definition, 2
Progress conditions
concurrent objects, 59–60
dependent, concurrent objects, 60–61
Progress property, concurrent objects, 45
Protocol state
bivalence and univalence, 102
consensus numbers, 101
Pthreads
basic functionality, 464
implementation, 467
invention, 466
thread-local storage, 465–466
Q
QNode class
CLH queue locks, 153
CompositeLock class, 161
HCLHLock queue, 169
MCS queue lock, 155–156
SynchronousDualQueue class, 239
timeout lock, 157–158
Queue locks
array-based, 150–151
CLH, 151–154
MCS, 154–157
overview, 149–150
with timeouts, 157–159
Queues
array-based bounded priority queues, 352–353
BoundedDEQueue class, 382–384
bounded partial queue, 225–229
BoundedQueue class, 225–227
bounded-range priority queue, 351–353
bounded transactional queue, 423
concurrent priority queues, 351–352
FIFO queue, 45–48
global queue, 168
HCLHLock queue, 168–173
hierarchical CLH queue lock, 168–172
LockedQueue class, 182
lock-free queue, 241
LockFreeQueueRecycle class, 236
locking queue, 47
MCS queue lock, 154–156
naive synchronous queue, 237–238
pool fairness, 224
priority queues, 351
SimpleTree priority queues, 353–354
skiplist-based unbounded priority queues, 363–366
SkipQueue class, 365–366
SynchronousDualQueue class, 239–240
SynchronousQueue class, 238
tree-based bounded priority queues, 353–355
unboundedDEQueue class, 386–388
unbounded heap-based priority queues, 357–363
unbounded lock-free queue, 230–233
UnboundedQueue class, 229
unbounded-range priority queue, 351
unbounded total queue, 229–230
unbounded transactional queue, 422
Quicksort algorithm, for sample sorting, 290
Quiescent consistency
applications, 45
concurrent objects, 49–51
concurrent priority queues, 351–352
pools and counters, 269–270
vs. sequential consistency, 52–53
shared counters, 270
R
Radix children, tree nodes, 402
Reachable, concurrent reasoning, 199
Readers–writers lock
basic concepts, 183
fair lock, 185–187
simple lock, 184–185
Readers–writers problem, example, 11–12
Read lock, definition, 183
Read–modify–write (RMW) registers
Common2 registers, 114–116
methods, 112–113
shared counter implementation, 5–6
source, 117
Read set, lock-based atomic object, 439
Realistic multiprocessor scheduling, definitions and operation, 378–380
Real-time order, vs. sequential consistency, 53
Rebalancing, definition, 329
Recursive initialization, lock-free hash set, 316
Recursive split-ordering, lock-free hash set, 309–312
Reentrant
BaseHashSet class, 301
Conditions objects, 180
Reentrant lock
definition, 187
methods, 188
Reference, BoundedDEQueue class, 383
Refinable concurrent Cuckoo hash set, 324–325
RefinableCuckooHashSet class, 324–325
RefinableHashSet class
implementation, 306–308
resizing, 305
RegBoolMRSWRegister class, implementation, 79
Registers
construction overview, 77–78
and mutual exclusion, 73
safe, 74–75
3D implementation space, 76
write order, 76
RegMRSWRegister class, implementation, 80
Regular nodes, list-based sets, 197
Regular registers
Boolean MRSW, 78–79
conditions, 77
definition, 75
first definition, 93
implementation considerations, 75–76
M-valued MRSW register, 79–81
safe, 75
RelaxedLock, 174
Releases
CLHLock class, 154
definition, 23
HCLHLock lock, 173
Java concepts, 456
locks, 178
MCSLock class, 156
Reordering, and memory consistency, 479
Replacement policy, and cache, 474
Representation invariant, concurrent reasoning, 198–199
Reservation object, dual data structures, 239
Response events
concurrent objects, 56
lock-free universal algorithm, 127
and register space, 76
RESULT status
CombiningTree, 267
definition, 262
Reverse tree barrier, implementation, 412–414
RMW, See Read–modify–write (RMW) registers
Robustness, CombiningTree, 269
ROOT status
CombiningTree, 265–266
definition, 262
Runnable object, Java thread concepts, 453–454
S
Safe
registers, 74–75
regular register, 75
SafeBoolMRSWRegister class, implementation, 78
Safe registers
first definition, 93
MRSW, 78
SRSW Boolean, 86
Safety property, definition, 2
Sample sorting
original ideas, 293
phases, 290–291
Saturation, counting networks, 280
Scan-and-label operations, timestamps, 34
Scheduler
function, 378
greedy, 379
idle step, 379
SECOND status
CombiningTree, 268
definition, 261
Semaphores, definition and implementation, 189
SenseBarrier class, constructor, 400
Sense-serving barrier, implementation, 399–400
Sentinel nodes
bounded partial queues, 225
list-based sets, 197
split-ordered hash set, 311
Sequential bottleneck
LockFreeStack, 248
and shared counting, 259
Sequential consistency
applications, 45
concurrent objects, 51–54
vs. quiescent consistency, 52–53
vs. real-time order, 53
SequentialHeap class, implementation, 356–357
Sequential objects
generic definition, 127
specifications, 48–49
SequentialRegister class, implementation, 73
Sequential skiplists, definition and design, 329–331
Sequential specification
concurrent objects, 56
definition, 49
Sequential timestamping, Lock class, 34
Serializable, transactional memory, 421
Sets
definition, 196
list-based, 196–198
Shared concurrent objects, and register space, 72
Shared counter
approach, 259–260
implementation, 4–5
quiescently consistent, 270
Shared-memory multiprocessors, programming challenges, 1
Shared objects, and synchronization, 3–6
Sharing, definition, 474
SimpleBarrier class, implementation, 399
SimpleLinear class
creators, 366
implementation, 352
Simple readers–writers lock
basic concepts, 184–185
fields and public methods, 184
inner read lock, 184
inner write lock, 185
SimpleTree priority queues
implementation, 354
structure, 353
Single-reader, single-writer (SRSW)
register space, 73
safe, 74
write order, 76
Single-writer atomic snapshot class
collect method, 91
update and scan methods, 91
SkipList class
algorithm, 349
levels, 330
Skiplists
invention, 348
LazySkipList class, 331–332
software transactional memory, 424–425
unbounded priority queues, 363–366
SkipListSet class, implementation, 425
SkipNode class, interface, 425
SkipQueue class
characteristics, 365–366
creators, 366
Sleeping, as Java construct, 458
Slot, array-based locks, 150
Snapshots
construction, 93
correctness arguments, 90–93
definition, 87
and multiple assignment, 110
obstruction-free, 87–88
wait-free snapshot, 88–90
Snooping
cache coherence, 446
interconnects, 472
Soft real-time application, definition, 397
Software combining, basic concepts, 260–261
Software implementation
bitonic network classes, 274–276
bitonic network proof of correctness, 276–278
periodic counting network, 279–280
Software transactional memory (STM)
atomic object implementation, 433–434
atomic objects, 429–431
contention manager, 431–433
dependent or independent, 431
first proposal, 448
lock-based atomic objects, 438–445
obstruction-free atomic object, 434–438
overview, 424–427
skip lists, 424–425
transactions and transactional threads, 427–428
TThread class, 426
zombies and consistency, 428–429
Sorting
bitonic algorithm, 288–289
parallel, 286
Sorting networks
designing, 287–288
OddEven design, 288
structure, 286–287
South wires
counting networks, 270
periodic network, 279
Spectulativeness, memory transactions, 422
Spin-locks
TAS-based, 146–147
Spinning
definition, 141
hardware concepts, 476
Splitters, sample sorting, 290
SRSW, See Single-reader, single-writer (SRSW)
SSkipNode class, implementation, 430
Stack class, definition, 245
Stamp
ABA problem, 234
BoundedDEQueue class, 383
lock-based atomic object, 439
Stamped snapshot class, implementation, 90
Start
C# constructs, 460
Java constructs, 454
Starvation, in Lock object, 24
Starvation-freedom property
definition, 8–9
as dependent progress condition, 60
in Lock algorithm, 24
in producer–consumer problem, 10–11
State
consensus numbers, 101–103
objects, 48
State machine, definition, 21
Static tree barrier, implementation, 402–404
StaticTreeBarrier class, Node class, 405
Step property
balancing networks, 272
bitonic counting network, 276
scheduler, 379
Tree class, 282
Steps, directed acyclic graph, 380
STM, See Software transactional memory (STM)
Store buffer, See Write buffer
definition, 478
Stores
definition, 37
Lock algorithm bounds, 37
in registers, 72
Striped concurrent Cuckoo hashing, 322–324
StripedCuckooHashSet class, 322–323
Striped hash set
basic concepts, 303–304
implementation, 304
lock striping, 304
StripedHashSet class
implementation, 304
lock-based hash table, 305
resizing, 306
Subhistory, concurrent objects, 56
Successful call, definition, 196
Successor state, consensus numbers, 101
Symmetric multiprocessing (SMP)
spinning, 476
Symmetric multiprocessing (SMP) architecture
basic concepts, 472–473
Synchronization
coarse-grained, 195
coarse-grained hash sets, 302
fine-grained, 195
hardware instructions, 480–481
instructions, memory barriers, 144
in Java memory model, 62
lazy, 196
nonblocking, 196
optimisitc, 195
and shared objects, 3–6
Synchronization primitives
atomic registers, 103–105
Common2 RMW registers, 114–116
compareAndSet() operation, 116–117
consensus numbers, 100–103
consensus protocols, 106
definition, 99–100
FIFO queues, 106–109
multiple assignment objects, 110–112
read–modify–write operations, 112–114
Synchronized blocks, in Java memory model, 62–63
SynchronousDualQueue class
method and constructor, 240
queue node, 239
Synchronous method, pool, 224
Synchronous queue
basic concepts, 237
creators, 241
implementation, 238
SynchronousQueue class, implementation, 238
T
Table
Cuckoo hashing, 316
definition, 299–300
Tail, definition, 224
Tasks, work distribution, 380–382
TASLock class
implementation, 144–145
performance, 146
Tentativeness, memory transactions, 422
Termination detection barrier
creators, 408
implementation, 404–408
Test-and-set locks
basic principles, 144
hardware concepts, 469
real-world processing, 145–146
Test-and-test-and-set
definition, 144–145
hardware concepts, 469
Thief, work stealing, 380–382
Thinlock, 174
Thread-local objects
as C# constructs, 462–463
as Java constructs, 458–459
Thread-local storage, Pthreads, 465–466
Thread-local variables, array-based locks, 150
Threads
as C# constructs, 460–461
definition, 71
hardware concepts, 472
as Java constructs, 453–454
Throughput, definition, 259
Time, in mutual exclusion, 21–22
Timeouts, in queue lock, 157–159
Timestamps
Bakery lock labels, 34
definition, 72
overview, 33
TOLock class
fields and constructor, 158
methods, 158
and timed-out nodes, 159
Top wires
counting networks, 270
sorting networks, 286
Total method, pool, 223
Total order, concurrent objects, 56
TourBarrier class
implementation, 410
information flow, 411
Tournament tree barrier, creators, 408
Transactional cache, hardware transactional memory, 448
Transactional cache coherence, hardware transactional memory, 447
Transactional Locking 2 algorithm, creators, 448
Transactional memory
atomic primitive problems, 418–420
compositionality problems, 420–421
definition, 3
locking problems, 417–418
overview, 417
transactions and atomicity, 421–423
Transactional threads, and transactions, 427–428
Transactions
and atomicity, 421–423
definition, 421
and transactional threads, 427–428
Transient communication, and mutual exclusion, 9
TreeBarrier class
combining tree, 403
implementation, 400–402
Tree-based bounded priority queues, structure and implementation, 353–355
Tree class, structure, 282
TSkipNode class, implementation, 434
TTASLock class
creators, 172
exponential backoff, 147–149
on shared-bus, 146–147
performance, 146
TThread class, software transactional memory, 426
U
unboundedDEQueue class, implementation, 386–388
Unbounded heap-based priority queues
concurrent heap, 357–363
definitions, 355
sequential heap, 356–357
Unbounded lock-free queue
implementation, 230–231
lazy, 231–232
step-wise operation, 232–233
Unbounded lock-free stack
definition, 245
implementation, 246–247
structure, 246
Unbounded pool, characteristics, 223
UnboundedQueue class, methods, 229
Unbounded-range priority queue, definition, 351
Unbounded total queue
deadlock, 230
implementation, 229–230
Unbounded transactional queue, implementation, 422
Unbounded work-stealing double-ended queues
creator, 392
implementation, 386–388
Univalence, protocol state, 102
Universality, definition, 126
Unlocks
CLHLock class, 154
hardware concepts, 469
HCLHLock lock, 173
interface, 23
Java concepts, 456–457
locks, 178
MCSLock class, 156
Unsuccessful call, definition, 196
Up state, balancers, 271
V
Valence, consensus numbers, 101–103
Validation
optimistic synchronization, 207
transaction handlers, 428
Version, lock-based atomic object, 439
Victim
unbounded work-stealing DEQueue, 390
work stealing, 380
Victim cache, hardware transactional memory, 448
Volatile fields, in Java memory model, 63
W
Wait-free method
concurrent objects, 59
concurrent reasoning, 199
definition, 99
history, 65
LazySkipList class, 335
LockFreeList class, 219
MRMW atomic register, 86
and register space, 73
Wait-free snapshot, construction, 88–90
Wait-free universal construction
algorithm, 131
auxiliary variables, 133–134
execution, 132
helping pattern, 130–131
linearizability, 133
modification considerations, 133
node announcement, 130–132
proof, 135–136
Waiting
Java concepts, 456
in Lock class, 31
in mutual exclusion, 15
in readers–writers problem, 12
Well-formed thread, requirements, 23
Window class, lock-free lists, 216
Winner thread, Common2 register, 114
Work, parallelism, 376
Work distribution
balancing, 389–391
bounded work-stealing dequeue, 382–386
overview, 380
unbounded work-stealing DEQueue, 386–388
work stealing, 380
yielding and multiprogramming, 380–382
Work sharing, creators, 391
WorkSharingThread class, implementation, 391
Work stealing
characteristics, 381
creators, 391
executor pool, 406–407
Work-stealing double-ended queues
bounded, 382–386
overview, 382
unbounded, 386–388
WorkStealingThread class, implementation, 382
Write absorption, definition, 478
Write buffer
definition, 478
shared memory writes, 143
Write lock, definition, 183
Write order
and register space, 76
SRSW and MRSW, 76
Write set, lock-based atomic object, 439
Y
Yielding
as Java construct concepts, 458
work distribution, 380–382
Z
Zombies, software transactional memory, 428–429
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.