Index
A
ABA problem
load-linked–store-conditional,
237
Abort, memory transactions,
422
Abstract
concurrent Cuckoo hashing,
318
Abstraction map
concurrent reasoning,
199
Abstract value, concurrent reasoning,
198
Acquires
Active thread
in software combining,
260
termination detection barrier,
405
Addressing
concurrent closed-addressing,
325
Algorithms
Dynamic Software Transactional Memory,
448
lock-based concurrent skiplist,
333–339
lock-free concurrent skiplist,
341–348
lock-free universal construction,
128
Transactional Locking 2,
448
wait-free universal construction,
131
Amdahl’s Law
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
without false sharing,
152
Asynchronous
definition,
Atomic hardware step
shared counter implementation,
5–6
Atomicity and transactions,
421–423
AtomicMarkableReference class
AtomicMRSWRegister class, implementation,
83
Atomic objects
software transactional memory,
429–431
Atomic primitives, problems,
418–420
AtomicReference class
unbounded lock-free queue,
231
Atomic register
implementation considerations,
75–76
Atomic snapshots
correctness arguments,
90–93
and multiple assignment,
110
wait-free snapshot,
88–90
AtomicSRSWRegister class, implementation,
83
AtomicStampedReference class
bounded work-stealing dequeue,
383
Auxiliary variables, wait-free universal construction,
133–134
B
Backoff lock
BackoffLock class
Bakery lock
in mutual exclusion,
31–33
Balancer
Balancer class, software bitonic counting network,
275
Balancing network, construction,
271–272
Barriers
BaseHashSet class
Batching, definition,
478
Benevolent side effect, lock-free lists,
217
Bitonic class, implementation,
276
Bitonic counting network
sequential execution,
272
Bitonic sorting algorithm, design and function,
288–289
Bivalence, protocol state,
102
Blocking
in Java memory model,
62–63
Block network, implementation,
281
Boolean register
Bottom wires
Bouncer class
BoundedDEQueue class, implementation,
382–384
Bounded partial queue
considerations and drawbacks,
228–229
BoundedQueue class
fields and constructor,
225
Bounded-range priority queue
Bounded transactional queue, implementation,
423
Bounded wait-free method, concurrent objects,
59
Bounded work-stealing double-ended queues
Bucket
split-ordered hash set,
311
BucketList class, implementation,
312–313
Bucket threshold,
BaseHashSet class,
301
Buffer, between producers and consumers,
223
Bus
Busy–waiting, definition,
141
C
Cache
Cache blocks, definition,
474
Cache coherence
as
BackoffLock problem,
149
hardware transactional memory,
446–447
Cache hit, definition,
146
Cache lines, definition,
474
Cache miss, definition,
146
Callable object, definition,
371
Calls
successful or unsuccessful,
196
Capacity
Circular array, modulo,
unboundedDEQueue class,
46,
150,
387
Clean double collect, obstruction-free snapshot,
88
CLHLock lock, creators,
174
CLH queue lock
fields and constructor,
151,
153
lock acquisition and release,
154
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
CoarseHashSet class, implementation,
302–303
Collects
obstruction-free snapshot,
87–88
single-writer atomic snapshot class,
91
Collisions, hash sets,
300
Combining phase,
CombiningTree,
265
Combining status, definition,
261
Combining tree barrier
CombiningTree class
Combining trees, original idea,
292
Common2 register
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
CompositeLock class
fields, constructor, and methods,
160
Compositional, correctness property,
51
Compositionality, problems,
420–421
Compositional linearizability, concurrent objects,
57–58
Concrete representation, concurrent reasoning,
198
Concurrency
concurrent objects,
45–48
Concurrent algorithm
definition,
Concurrent closed-addressing schemes, creators,
325
Concurrent Cuckoo hashing, definition and implementation,
318–322
Concurrent heap
structure and implementation,
358–363
Concurrent objects
compositional linearizability,
57–58
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,
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
Consensus numbers
Consensus object
lock-free universal construction,
126–130
universality definition,
126
wait-free universal construction,
130–136
Consensus synchronization problem
Consenus protocols, generic,
106
Consistency, software transactional memory,
428–429
Consumers
naive synchronous queue,
237
Contention
Contention manager
software transactional memory,
431–433
Context switch, definition,
472
Convoying, in locking,
417
Coordination protocol (OR Protocol), definition,
Copyable class, interface,
430
Correctness
concurrent objects,
45–48
Correctness arguments, atomic snapshots,
90–93
Counters
as shared counter implementation,
4–5
Counting networks
Covering state,
Lock algorithm,
38,
40
Critical-path length, parallelism,
376–377
Critical sections
as
BackoffLock problem,
149
in mutual exclusion,
22–24
C# construct concepts
Cuckoo hashing
definition and implementation,
316–318
D
Data structure design
Deadlock
freedom from deadlock,
24
software transactional memory,
431
unbounded total queue,
230
Deadlock-freedom property
definition,
as dependent progress condition,
60
Decision value, consensus numbers,
101
Delegate, C# concepts,
460
DiffractingBalancer class, implementation,
284
Diffracting trees
Directed acyclic graph (DAG)
Direct mapped cache, definition,
474
Direct-mapped caches, definition,
448
Disjoint-access-parallelism
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)
Down state, balancers,
271
Dual data structures
Dynamic Software Transactional Memory algorithm, creators,
448
E
Elimination,
LockFreeStack,
248–249
EliminationBackoffStack class
EventListener class, incorrect example,
64
Events, in state machine,
21
Executor service, definition,
371
Expected value,
compareAndSet() operation,
116,
480
Exponential backoff
Extensible hashing, definition,
300
F
Factory,
Lock interface,
178
Fairness
Fair readers–writers lock
fields and public methods,
186
False sharing
Fault-tolerance, in mutual exclusioin,
Fibonacci sequence
FibTask class
FIFO queue, lock-based,
45–48
Filter lock
in mutual exclusion,
28–31
Final fields, in Java memory model,
63–64
Final state, consensus numbers,
101
FineGrainedHeap class
Fine-grained synchronization
FineList class
hand-over-hand locking,
204
First-come-first-served
Bakery lock algorithm,
31,
33
First-in-first-out (FIFO)
quiescent consistency,
51
sequential objects,
48–49
FIRST status
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
Fully-associative caches, definition,
448,
474
Future interface, definition,
371
G
Global queue, in
HCLHLock queue,
168
Global state, definition,
37
Global threshold,
BaseHashSet class,
301
Granularity, and cache,
474
Greedy
Greedy contention manager, creators,
448
H
Hand-and-over-hand locking,
FineList class,
204
Handlers, software transactional memory,
428
Hardware concepts
cache-conscious programming,
476–477
processors and threads,
472
synchronization instructions,
480–481
Hardware transactional memory (HTM)
transactional cache coherence,
447
Hash function, definition,
300
Hash sets
HBOLock class, implementation,
168
HCLHLock queue
acquisition and release,
173
fields and constructor,
169
Hierarchical backoff lock, implementation,
167–168
Hierarchical CLH queue lock, design,
168–172
Hierarchical locks, definition,
167
High contention, definition,
147
Hit ratio, and cache,
474
I
Idle step, scheduler,
379
Inactive thread, termination detection barrier,
405
Initial state, consensus numbers,
101
Inner classes
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
definition,
Invariants, concurrent reasoning,
198
Invocation events
lock-free universal algorithm,
127
Irreflexive, timestamps,
34
Items
PrioritySkipList class,
363
software transactional memory,
426
J
Java construct concepts
yielding and sleeping,
458
Java memory model
locks and synchronized blocks,
62–63
Join
K
Karma contention manager
Kernel maps, function,
378
k-way set associative, caches,
474
L
Labels
Bakery lock algorithm,
32
Last-in-first-out (LIFO),
StackT class,
245
Layer network, implementation,
279–280
Layout, distributed coordination,
292
Lazy
PrioritySkipList class,
363
LazyList class
LazySkipList class
Lazy synchronization
Levels, in
Filter lock,
28
Line, cache coherence,
446
Linearizability
concurrent priority queues,
351
concurrent reasoning,
199
wait-free universal construction,
133
Linearization points
fine-grained synchronization,
204
Linear speedup, parallelism,
377
Linked lists
coarse-grained synchronization,
200–201
fine-grained synchronization,
201–205
optimistic synchronization,
205–208
List-based sets, basic concepts,
196–198
List nodes
bounded partial queue,
227
unbounded lock-free queue,
230
Liveness property, definition,
Load-linked–store-conditional (LL/SC)
hardware synchronization,
480
Loads
Lock algorithm bounds,
37
Local spinning, definition,
147
Local state, definition,
37
Lock-based atomic object
Lock-based concurrent skiplist
Lock-based hash table, resizing,
305
Lock class
Lock coupling
LockedQueue class, with locks and conditions,
182
Lock-free concurrent skiplist
Lock-free exchanger
Lock-free hash set
recursive initialization,
316
LockFreeHashSet class, implementation,
313–315
LockFreeList class, methods,
217–219
Lock-free lists
Lock-free method
concurrent reasoning,
199
LockFreeQueue class
LockFreeQueueRecycle class, implementation,
236
LockFreeSkipList class
LockFreeStack class
Lock-free universal construction
Locking
double-checked, in Java memory model,
61–62
hand-and-over-hand locking,
FineList class,
204
LockObject class, implementation,
23,
440–445
LockOne class, for mutual exclusion,
25–26
Lockout-freedom property
as dependent progress condition,
60
in producer–consumer problem,
10–11
Locks
hierarchical CLH queue lock,
168–172
in Java memory model,
62–63
lock-based atomic object,
439
simple readers–writers lock,
183–185
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
lazy synchronization,
196,
208
PrioritySkipList class,
363
Loser thread, Common2 register,
114
Lost-wakeup problem
Low contention, definition,
147
M
Main cache, hardware transactional memory,
448
Main memory, hardware concepts,
471,
473
Matrix class, implementation,
372
MatrixTask class, implementation,
373–374
MCSLock class, creators,
174
MCS queue lock
lock acquisition and release,
156
Memory, hardware concepts,
471,
473
Memory barriers, definition,
53,
144,
479
Memory consistency models
Memory contention
Memory locations, lower bounds,
37–40
Memory reclamation, and ABA problem,
233–237
Merger class
software bitonic counting network,
275
MERGER network, logical structure,
273
MESI protocol
state transition examples,
475
Method calls
quiescent consistency,
49–50
MMThread class, implementation,
370
Monitor locks
Monitors
multiCompareAndSet, pseudocode,
419
Multi-core architecture, definition,
477–479
Multicores, programming challenges,
Multiple assignment objects, basic concept,
110
Multiprogrammed environment, work distribution,
381–382
Multi-reader multiple-writer (MRMW)
Multi-reader single-writer (MRSW)
regular Boolean register,
78–79
regular
M-valued register,
79–81
Multi-threaded architecture, definition,
477–479
Mutual exclusion
Bakery lock algorithm,
31–33
bounded timestamps,
33–36
in concurrent programming,
15
definition,
number of locations,
37–40
in producer–consumer problem,
10–11
M-valued register
N
Naive synchronous queue
New version field, obstruction-free atomic object,
435
Node class
StaticTreeBarrier class,
405
Nodes
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
North wires
Notify, Java concepts,
457
O
Obstruction-free atomic object
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
Optimistic synchronization
Owner field, obstruction-free atomic object,
435
P
Parallelism
definition,
Parallelization, realities,
13–14
Parallel matrix multiplication
Parallel programming, challenges,
15
Parallel sorting, basic concepts,
286
Partial method
Partial order, concurrent objects,
56
Passive thread, in software combining,
260
Pending
invocation, concurrent objects,
56
Performance
Periodic counting networks
Persistent communication, and mutual exclusion,
Peterson lock
in mutual exclusion,
27–28
PhasedCuckooHashSet class, implementation,
318–321
Phases
computation organization,
397
concurrent Cuckoo hashing,
318
Physical removal
lazy synchronization,
196,
208
PrioritySkipList class,
363
Pipelining, counting networks,
280–281
Pools
parallel matrix multiplication,
370
termination detection barrier,
408
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
Priority inversion, in locking,
417
Priority queues, definition,
351
PrioritySkipList class
Prism
distributed coordination,
291
Probabilistic data structure,
SkipList class,
330
Probe sets, concurrent Cuckoo hashing,
318
Processors, hardware concepts,
471,
472
Producer–consumer problem, example,
10–11
Producer–consumer property, in producer–consumer problem,
10–11
Producers
naive synchronous queue,
237
Program correctness (or Correctness), definition,
Program order, definition,
52
Program performance, definition,
Progress conditions
concurrent objects,
59–60
dependent, concurrent objects,
60–61
Progress property, concurrent objects,
45
Protocol state
bivalence and univalence,
102
Pthreads
Q
QNode class
SynchronousDualQueue class,
239
Queue locks
Queues
array-based bounded priority queues,
352–353
bounded-range priority queue,
351–353
bounded transactional queue,
423
concurrent priority queues,
351–352
hierarchical CLH queue lock,
168–172
LockFreeQueueRecycle class,
236
SimpleTree priority queues,
353–354
skiplist-based unbounded priority queues,
363–366
SynchronousDualQueue class,
239–240
SynchronousQueue class,
238
tree-based bounded priority queues,
353–355
unbounded heap-based priority queues,
357–363
UnboundedQueue class,
229
unbounded-range priority queue,
351
unbounded transactional queue,
422
Quicksort algorithm, for sample sorting,
290
Quiescent consistency
concurrent objects,
49–51
concurrent priority queues,
351–352
vs. sequential consistency,
52–53
R
Radix children, tree nodes,
402
Reachable, concurrent reasoning,
199
Readers–writers lock
Readers–writers problem, example,
11–12
Read lock, definition,
183
Read–modify–write (RMW) registers
shared counter implementation,
5–6
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
Reentrant lock
Reference,
BoundedDEQueue class,
383
Refinable concurrent Cuckoo hash set,
324–325
RefinableCuckooHashSet class,
324–325
RefinableHashSet class
RegBoolMRSWRegister class, implementation,
79
Registers
construction overview,
77–78
3D implementation space,
76
RegMRSWRegister class, implementation,
80
Regular nodes, list-based sets,
197
Regular registers
implementation considerations,
75–76
M-valued MRSW register,
79–81
Releases
Reordering, and memory consistency,
479
Replacement policy, and cache,
474
Representation invariant, concurrent reasoning,
198–199
Reservation object, dual data structures,
239
Response events
lock-free universal algorithm,
127
RESULT status
Reverse tree barrier, implementation,
412–414
Robustness,
CombiningTree,
269
ROOT status
Runnable object, Java thread concepts,
453–454
S
Safe
SafeBoolMRSWRegister class, implementation,
78
Safe registers
Safety property, definition,
Sample sorting
Saturation, counting networks,
280
Scan-and-label operations, timestamps,
34
Scheduler
SECOND status
Semaphores, definition and implementation,
189
SenseBarrier class, constructor,
400
Sense-serving barrier, implementation,
399–400
Sentinel nodes
bounded partial queues,
225
split-ordered hash set,
311
Sequential bottleneck
Sequential consistency
concurrent objects,
51–54
vs. quiescent consistency,
52–53
SequentialHeap class, implementation,
356–357
Sequential objects
SequentialRegister class, implementation,
73
Sequential skiplists, definition and design,
329–331
Sequential specification
Sequential timestamping,
Lock class,
34
Serializable, transactional memory,
421
Sets
Shared concurrent objects, and register space,
72
Shared counter
quiescently consistent,
270
Shared-memory multiprocessors, programming challenges,
Shared objects, and synchronization,
3–6
SimpleBarrier class, implementation,
399
SimpleLinear class
Simple readers–writers lock
fields and public methods,
184
SimpleTree priority queues
Single-reader, single-writer (SRSW)
Single-writer atomic snapshot class
update and scan methods,
91
SkipList class
Skiplists
software transactional memory,
424–425
SkipListSet class, implementation,
425
SkipNode class, interface,
425
SkipQueue class
Sleeping, as Java construct,
458
Slot, array-based locks,
150
Snapshots
correctness arguments,
90–93
and multiple assignment,
110
wait-free snapshot,
88–90
Snooping
Soft real-time application, definition,
397
Software combining, basic concepts,
260–261
Software implementation
bitonic network proof of correctness,
276–278
Software transactional memory (STM)
atomic object implementation,
433–434
dependent or independent,
431
obstruction-free atomic object,
434–438
transactions and transactional threads,
427–428
Sorting
Sorting networks
South wires
Spectulativeness, memory transactions,
422
Spin-locks
Spinning
Splitters, sample sorting,
290
SSkipNode class, implementation,
430
Stack class, definition,
245
Stamp
BoundedDEQueue class,
383
lock-based atomic object,
439
Stamped snapshot class, implementation,
90
Start
Starvation, in Lock object,
24
Starvation-freedom property
as dependent progress condition,
60
in producer–consumer problem,
10–11
State
State machine, definition,
21
Static tree barrier, implementation,
402–404
StaticTreeBarrier class, Node class,
405
Step property
bitonic counting network,
276
Steps, directed acyclic graph,
380
Stores
Lock algorithm bounds,
37
Striped concurrent Cuckoo hashing,
322–324
StripedCuckooHashSet class,
322–323
Striped hash set
StripedHashSet class
lock-based hash table,
305
Subhistory, concurrent objects,
56
Successful call, definition,
196
Successor state, consensus numbers,
101
Symmetric multiprocessing (SMP)
Symmetric multiprocessing (SMP) architecture
Synchronization
coarse-grained hash sets,
302
instructions, memory barriers,
144
Synchronization primitives
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
Synchronous method, pool,
224
Synchronous queue
SynchronousQueue class, implementation,
238
T
Table
TASLock class
Tentativeness, memory transactions,
422
Termination detection barrier
Test-and-set locks
Test-and-test-and-set
Thread-local objects
Thread-local storage, Pthreads,
465–466
Thread-local variables, array-based locks,
150
Threads
Throughput, definition,
259
Time, in mutual exclusion,
21–22
Timestamps
TOLock class
fields and constructor,
158
Top wires
Total order, concurrent objects,
56
TourBarrier class
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
definition,
transactions and atomicity,
421–423
Transactional threads, and transactions,
427–428
Transactions
Transient communication, and mutual exclusion,
TreeBarrier class
Tree-based bounded priority queues, structure and implementation,
353–355
Tree class, structure,
282
TSkipNode class, implementation,
434
TTASLock class
TThread class, software transactional memory,
426
U
unboundedDEQueue class, implementation,
386–388
Unbounded heap-based priority queues
Unbounded lock-free queue
Unbounded lock-free stack
Unbounded pool, characteristics,
223
UnboundedQueue class, methods,
229
Unbounded-range priority queue, definition,
351
Unbounded total queue
Unbounded transactional queue, implementation,
422
Unbounded work-stealing double-ended queues
Univalence, protocol state,
102
Universality, definition,
126
Unlocks
Unsuccessful call, definition,
196
Update value,
compareAndSet() operation,
116,
480
V
Valence, consensus numbers,
101–103
Validation
optimistic synchronization,
207
transaction handlers,
428
Version, lock-based atomic object,
439
Version clock, lock-based atomic object,
439,
441
Victim
unbounded work-stealing DEQueue,
390
Victim cache, hardware transactional memory,
448
Volatile fields, in Java memory model,
63
W
Wait-free method
concurrent reasoning,
199
Wait-free snapshot, construction,
88–90
Wait-free universal construction
modification considerations,
133
Waiting
in readers–writers problem,
12
Well-formed thread, requirements,
23
Window class, lock-free lists,
216
Winner thread, Common2 register,
114
Work distribution
bounded work-stealing dequeue,
382–386
unbounded work-stealing DEQueue,
386–388
yielding and multiprogramming,
380–382
Work sharing, creators,
391
WorkSharingThread class, implementation,
391
Work stealing
Work-stealing double-ended queues
WorkStealingThread class, implementation,
382
Write absorption, definition,
478
Write buffer
shared memory writes,
143
Write lock, definition,
183
Write order
Write set, lock-based atomic object,
439
Y
Yielding
as Java construct concepts,
458
Z
Zombies, software transactional memory,
428–429