Next:
14.1 Avoiding Locks
Up:
2.1 <
Previous:
13.6 Hardware Considerations
Contents
14
. Advanced Synchronization
Subsections
14
.
1
Avoiding Locks
14
.
2
Memory Barriers
14
.
2
.
1
Memory Ordering and Memory Barriers
14
.
2
.
2
If B Follows A, and C Follows B, Why Doesn't C Follow A?
14
.
2
.
3
Variables Can Have More Than One Value
14
.
2
.
4
What Can You Trust?
14
.
2
.
4
.
1
Self-References Are Ordered
14
.
2
.
4
.
2
Single-Variable Memory Consistency
14
.
2
.
4
.
3
Pair-Wise Memory Barriers
14
.
2
.
4
.
4
Pair-Wise Memory Barriers: Portable Combinations
14
.
2
.
4
.
4
.
1
Pairing 1.
14
.
2
.
4
.
4
.
2
Pairing 2.
14
.
2
.
4
.
4
.
3
Pairing 3.
14
.
2
.
4
.
5
Pair-Wise Memory Barriers: Semi-Portable Combinations
14
.
2
.
4
.
5
.
1
Ears to Mouths.
14
.
2
.
4
.
5
.
2
Stores ``Pass in the Night''.
14
.
2
.
4
.
6
Pair-Wise Memory Barriers: Non-Portable Combinations
14
.
2
.
4
.
6
.
1
Ears to Ears.
14
.
2
.
4
.
6
.
2
Mouth to Mouth, Ear to Ear.
14
.
2
.
4
.
6
.
3
Only One Store.
14
.
2
.
4
.
7
Semantics Sufficient to Implement Locking
14
.
2
.
5
Review of Locking Implementations
14
.
2
.
6
A Few Simple Rules
14
.
2
.
7
Abstract Memory Access Model
14
.
2
.
8
Device Operations
14
.
2
.
9
Guarantees
14
.
2
.
10
What Are Memory Barriers?
14
.
2
.
10
.
1
Explicit Memory Barriers
14
.
2
.
10
.
1
.
1
Write Memory Barriers
14
.
2
.
10
.
1
.
2
Data Dependency Barriers
14
.
2
.
10
.
1
.
3
Read Memory Barriers
14
.
2
.
10
.
1
.
4
General Memory Barriers
14
.
2
.
10
.
2
Implicit Memory Barriers
14
.
2
.
10
.
2
.
1
LOCK Operations
14
.
2
.
10
.
2
.
2
UNLOCK Operations
14
.
2
.
10
.
3
What May Not Be Assumed About Memory Barriers?
14
.
2
.
10
.
4
Data Dependency Barriers
14
.
2
.
10
.
5
Control Dependencies
14
.
2
.
10
.
6
SMP Barrier Pairing
14
.
2
.
10
.
7
Examples of Memory Barrier Pairings
14
.
2
.
10
.
8
Read Memory Barriers vs. Load Speculation
14
.
2
.
11
Locking Constraints
14
.
2
.
12
Memory-Barrier Examples
14
.
2
.
12
.
1
Locking Examples
14
.
2
.
12
.
1
.
1
LOCK Followed by UNLOCK:
14
.
2
.
12
.
1
.
2
LOCK-Based Critical Sections:
14
.
2
.
12
.
1
.
3
Ordering with Multiple Locks:
14
.
2
.
12
.
1
.
4
Ordering with Multiple CPUs on One Lock:
14
.
2
.
13
The Effects of the CPU Cache
14
.
2
.
13
.
1
Cache Coherency
14
.
2
.
14
Where Are Memory Barriers Needed?
14
.
3
Non-Blocking Synchronization
14
.
3
.
1
Simple NBS
14
.
3
.
2
Hazard Pointers
14
.
3
.
3
Atomic Data Structures
14
.
3
.
4
``Macho'' NBS
Paul E. McKenney 2011-12-16