Linked Lists: Locking, Lock-Free, and Beyond …
Linked Lists: Locking, Lock-Free, and Beyond … Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit
Last Lecture: Spin-Locks
Art of Multiprocessor Programming 2 Last Lecture: Spin-Locks CS Resets lock upon exit spin lock critical section . . .
Today: Concurrent Objects
Art of Multiprocessor Programming 3 Today: Concurrent Objects Adding threads should not lower throughput Contention effects Mostly fixed by Queue locks
Today: Concurrent Objects
Art of Multiprocessor Programming 4 Today: Concurrent Objects Adding threads should not lower throughput Contention effects Mostly fixed by Queue locks Should increase throughput Not possible if inherently sequential Surprising things are parallelizable
Coarse-Grained Synchronization
Art of Multiprocessor Programming 5 Coarse-Grained Synchronization Each method locks the object Avoid contention using queue locks
Coarse-Grained Synchronization
Art of Multiprocessor Programming 6 Coarse-Grained Synchronization Each method locks the object Avoid contention using queue locks Easy to reason about In simple cases
Coarse-Grained Synchronization
Art of Multiprocessor Programming 7 Coarse-Grained Synchronization Each method locks the object Avoid contention using queue locks Easy to reason about In simple cases So, are we done?
Coarse-Grained Synchronization
Art of Multiprocessor Programming 8 Coarse-Grained Synchronization Sequential bottleneck Threads “stand in line”
Coarse-Grained Synchronization
Art of Multiprocessor Programming 9 Coarse-Grained Synchronization Sequential bottleneck Threads “stand in line” Adding more threads Does not improve throughput Struggle to keep it from getting worse
Coarse-Grained Synchronization
Art of Multiprocessor Programming 10 Coarse-Grained Synchronization Sequential bottleneck Threads “stand in line” Adding more threads Does not improve throughput Struggle to keep it from getting worse So why even use a multiprocessor? Well, some apps inherently parallel …
This Lecture
Art of Multiprocessor Programming 11 This Lecture Introduce four “patterns” Bag of tricks … Methods that work more than once …
This Lecture
Art of Multiprocessor Programming 12 This Lecture Introduce four “patterns” Bag of tricks … Methods that work more than once … For highly-concurrent objects Concurrent access More threads, more throughput
First: Fine-Grained Synchronization
Art of Multiprocessor Programming 13 First: Fine-Grained Synchronization Instead of using a single lock … Split object into Independently-synchronized components Methods conflict when they access The same component … At the same time
Second: Optimistic Synchronization
Art of Multiprocessor Programming 14 Second: Optimistic Synchronization Search without locking …
Second: Optimistic Synchronization
Art of Multiprocessor Programming 15 Second: Optimistic Synchronization Search without locking … If you find it, lock and check … OK: we are done Oops: start over
Second: Optimistic Synchronization
Art of Multiprocessor Programming 16 Second: Optimistic Synchronization Search without locking … If you find it, lock and check … OK: we are done Oops: start over Evaluation Usually cheaper than locking, but Mistakes are expensive
Third: Lazy Synchronization
Art of Multiprocessor Programming 17 Third: Lazy Synchronization Postpone hard work Removing components is tricky Logical removal Mark component to be deleted Physical removal Do what needs to be done
Fourth: Lock-Free Synchronization
Art of Multiprocessor Programming 18 Fourth: Lock-Free Synchronization Don’t use locks at all Use compareAndSet() & relatives …
Fourth: Lock-Free Synchronization
Art of Multiprocessor Programming 19 Fourth: Lock-Free Synchronization Don’t use locks at all Use compareAndSet() & relatives … Advantages No Scheduler Assumptions/Support
Fourth: Lock-Free Synchronization
Art of Multiprocessor Programming 20 Fourth: Lock-Free Synchronization Don’t use locks at all Use compareAndSet() & relatives … Advantages No Scheduler Assumptions/Support Disadvantages Complex Sometimes high overhead
Linked List
Art of Multiprocessor Programming 21 Linked List Illustrate these patterns … Using a list-based Set Common application Building block for other apps
Set Interface
Art of Multiprocessor Programming 22 Set Interface Unordered collection of items
Set Interface
Art of Multiprocessor Programming 23 Set Interface Unordered collection of items No duplicates
Set Interface
Art of Multiprocessor Programming 24 Set Interface Unordered collection of items No duplicates Methods add(x) put x in set remove(x) take x out of set contains(x) tests if x in set
List-Based Sets
Art of Multiprocessor Programming 25 List-Based Sets public interface Set<T> { public boolean add(T x); public boolean remove(T x); public boolean contains(T x); }
List-Based Sets
Art of Multiprocessor Programming 26 List-Based Sets public interface Set<T> { public boolean add(T x); public boolean remove(T x); public boolean contains(T x); } Add item to set
List-Based Sets
Art of Multiprocessor Programming 27 List-Based Sets public interface Set<T> { public boolean add(T x); public boolean remove(T x); public boolean contains(Tt x); } Remove item from set
List-Based Sets
Art of Multiprocessor Programming 28 List-Based Sets public interface Set<T> { public boolean add(T x); public boolean remove(T x); public boolean contains(T x); } Is item in set?
List Node
Art of Multiprocessor Programming 29 List Node public class Node { public T item; public int key; public Node next; }
List Node
Art of Multiprocessor Programming 30 List Node public class Node { public T item; public int key; public Node next; } item of interest
List Node
Art of Multiprocessor Programming 31 List Node public class Node { public T item; public int key; public Node next; } Usually hash code
List Node
Art of Multiprocessor Programming 32 List Node public class Node { public T item; public int key; public Node next; } Reference to next node
The List-Based Set
Art of Multiprocessor Programming 33 The List-Based Set a b c Sorted with Sentinel nodes (min & max possible keys) -∞ +∞
Reasoning about Concurrent Objects
Art of Multiprocessor Programming 34 Reasoning about Concurrent Objects Invariant Property that always holds
Reasoning about Concurrent Objects
Art of Multiprocessor Programming 35 Reasoning about Concurrent Objects Invariant Property that always holds Established because True when object is created Truth preserved by each method Each step of each method
Specifically …
Art of Multiprocessor Programming 36 Specifically … Invariants preserved by add() remove() contains()
Specifically …
Art of Multiprocessor Programming 37 Specifically … Invariants preserved by add() remove() contains() Most steps are trivial Usually one step tricky Often linearization point
Interference
Art of Multiprocessor Programming 38 Interference Invariants make sense only if methods considered are the only modifiers
Interference
Art of Multiprocessor Programming 39 Interference Invariants make sense only if methods considered are the only modifiers Language encapsulation helps List nodes not visible outside class
Interference
Art of Multiprocessor Programming 40 Interference Invariants make sense only if methods considered are the only modifiers Language encapsulation helps List nodes not visible outside class
Interference
Art of Multiprocessor Programming 41 Interference Freedom from interference needed even for removed nodes Some algorithms traverse removed nodes Careful with malloc() & free() ! Garbage collection helps here
Abstract Data Types
Art of Multiprocessor Programming 42 Abstract Data Types Concrete representation: Abstract Type: { a , b } a b
Abstract Data Types
Art of Multiprocessor Programming 43 Abstract Data Types Meaning of rep given by abstraction map S( ) = { a , b } a b
Rep Invariant
Art of Multiprocessor Programming 44 Rep Invariant Which concrete values meaningful? Sorted? Duplicates? Rep invariant Characterizes legal concrete reps Preserved by methods Relied on by methods
Blame Game
Art of Multiprocessor Programming 45 Blame Game Rep invariant is a contract Suppose add() leaves behind 2 copies of x remove() removes only 1 Which is incorrect?
Blame Game
Art of Multiprocessor Programming 46 Blame Game Suppose add() leaves behind 2 copies of x remove() removes only 1
Blame Game
Art of Multiprocessor Programming 47 Blame Game Suppose add() leaves behind 2 copies of x remove() removes only 1 Which is incorrect? If rep invariant says no duplicates add() is incorrect Otherwise remove() is incorrect
Rep Invariant (partly)
Art of Multiprocessor Programming 48 Rep Invariant (partly) Sentinel nodes tail reachable from head Sorted No duplicates
Abstraction Map
Art of Multiprocessor Programming 49 Abstraction Map S( head ) = { x | there exists a such that a reachable from head and a.item = x }
Sequential List Based Set
Art of Multiprocessor Programming 50 Sequential List Based Set a c d a b c Add() Remove()
Sequential List Based Set
Art of Multiprocessor Programming 51 Sequential List Based Set a c d b a b c add () remove ()
Coarse-Grained Locking
Art of Multiprocessor Programming 52 Coarse-Grained Locking a b d
Coarse-Grained Locking
Art of Multiprocessor Programming 53 Coarse-Grained Locking a b d c
Coarse-Grained Locking
Art of Multiprocessor Programming 54 honk! Coarse-Grained Locking a b d c Simple but hotspot + bottleneck honk!
Coarse-Grained Locking
Art of Multiprocessor Programming 55 Coarse-Grained Locking Easy, same as synchronized methods “One lock to rule them all …”
Coarse-Grained Locking
Art of Multiprocessor Programming 56 Coarse-Grained Locking Easy, same as synchronized methods “One lock to rule them all …” Simple, clearly correct Deserves respect! Works poorly with contention Queue locks help But bottleneck still an issue
Fine-grained Locking
Art of Multiprocessor Programming 57 Fine-grained Locking Requires careful thought “Do not meddle in the affairs of wizards, for they are subtle and quick to anger”
Fine-grained Locking
Art of Multiprocessor Programming 58 Fine-grained Locking Requires careful thought “Do not meddle in the affairs of wizards, for they are subtle and quick to anger” Split object into pieces Each piece has own lock Methods that work on disjoint pieces need not exclude each other
Hand-over-Hand locking
Art of Multiprocessor Programming 59 Hand-over-Hand locking a b c
Hand-over-Hand locking
Art of Multiprocessor Programming 60 Hand-over-Hand locking a b c
Hand-over-Hand locking
Art of Multiprocessor Programming 61 Hand-over-Hand locking a b c
Hand-over-Hand locking
Art of Multiprocessor Programming 62 Hand-over-Hand locking a b c
Hand-over-Hand locking
Art of Multiprocessor Programming 63 Hand-over-Hand locking a b c
Removing a Node
Art of Multiprocessor Programming 64 Removing a Node a b c d remove(b)
Removing a Node
Art of Multiprocessor Programming 65 Removing a Node a b c d remove(b)
Removing a Node
Art of Multiprocessor Programming 66 Removing a Node a b c d remove(b)
Removing a Node
Art of Multiprocessor Programming 67 Removing a Node a b c d remove(b)
Removing a Node
Art of Multiprocessor Programming 68 Removing a Node a b c d remove(b)
Removing a Node
Art of Multiprocessor Programming 69 Removing a Node a c d remove(b) Why hold 2 locks?
Concurrent Removes
Art of Multiprocessor Programming 70 Concurrent Removes a b c d remove(c) remove(b)
Concurrent Removes
Art of Multiprocessor Programming 71 Concurrent Removes a b c d remove(b) remove(c)
Concurrent Removes
Art of Multiprocessor Programming 72 Concurrent Removes a b c d remove(b) remove(c)
Concurrent Removes
Art of Multiprocessor Programming 73 Concurrent Removes a b c d remove(b) remove(c)
Concurrent Removes
Art of Multiprocessor Programming 74 Concurrent Removes a b c d remove(b) remove(c)
Concurrent Removes
Art of Multiprocessor Programming 75 Concurrent Removes a b c d remove(b) remove(c)
Concurrent Removes
Art of Multiprocessor Programming 76 Concurrent Removes a b c d remove(b) remove(c)
Concurrent Removes
Art of Multiprocessor Programming 77 Concurrent Removes a b c d remove(b) remove(c)
Concurrent Removes
Art of Multiprocessor Programming 78 Concurrent Removes a b c d remove(b) remove(c)
Concurrent Removes
Art of Multiprocessor Programming 79 Concurrent Removes a b c d remove(b) remove(c)
Uh, Oh
Art of Multiprocessor Programming 80 Uh, Oh a c d remove(b) remove(c)
Uh, Oh
Art of Multiprocessor Programming 81 Uh, Oh a c d Bad news, c not removed remove(b) remove(c)
Problem
Art of Multiprocessor Programming 82 Problem To delete node c Swing node b ’s next field to d Problem is, Someone deleting b concurrently could direct a pointer to c b a c b a c
Insight
Art of Multiprocessor Programming 83 Insight If a node is locked No one can delete node’s successor If a thread locks Node to be deleted And its predecessor Then it works
Hand-Over-Hand Again
Art of Multiprocessor Programming 84 Hand-Over-Hand Again a b c d remove(b)
Hand-Over-Hand Again
Art of Multiprocessor Programming 85 Hand-Over-Hand Again a b c d remove(b)
Hand-Over-Hand Again
Art of Multiprocessor Programming 86 Hand-Over-Hand Again a b c d remove(b)
Hand-Over-Hand Again
Art of Multiprocessor Programming 87 Hand-Over-Hand Again a b c d remove(b) Found it!
Hand-Over-Hand Again
Art of Multiprocessor Programming 88 Hand-Over-Hand Again a b c d remove(b) Found it!
Hand-Over-Hand Again
Art of Multiprocessor Programming 89 Hand-Over-Hand Again a c d remove(b)
Removing a Node
Art of Multiprocessor Programming 90 Removing a Node a b c d remove(b) remove(c)
Removing a Node
Art of Multiprocessor Programming 91 Removing a Node a b c d remove(b) remove(c)
Removing a Node
Art of Multiprocessor Programming 92 Removing a Node a b c d remove(b) remove(c)
Removing a Node
Art of Multiprocessor Programming 93 Removing a Node a b c d remove(b) remove(c)
Removing a Node
Art of Multiprocessor Programming 94 Removing a Node a b c d remove(b) remove(c)
Removing a Node
Art of Multiprocessor Programming 95 Removing a Node a b c d remove(b) remove(c)
Removing a Node
Art of Multiprocessor Programming 96 Removing a Node a b c d remove(b) remove(c)
Removing a Node
Art of Multiprocessor Programming 97 Removing a Node a b c d remove(b) remove(c)
Removing a Node
Art of Multiprocessor Programming 98 Removing a Node a b c d Must acquire Lock for b remove(c)
Removing a Node
Art of Multiprocessor Programming 99 Removing a Node a b c d Cannot acquire lock for b remove(c)
Removing a Node
Art of Multiprocessor Programming 100 Removing a Node a b c d Wait! remove(c)
Removing a Node
Art of Multiprocessor Programming 101 Removing a Node a b d Proceed to remove(b)