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)
Removing a Node
Art of Multiprocessor Programming 102 Removing a Node a b d remove(b)
Removing a Node
Art of Multiprocessor Programming 103 Removing a Node a b d remove(b)
Removing a Node
Art of Multiprocessor Programming 104 Removing a Node a d remove(b)
Removing a Node
Art of Multiprocessor Programming 105 Removing a Node a d
Remove method
Art of Multiprocessor Programming 106 Remove method public boolean remove(Item item) { int key = item.hashCode(); Node pred, curr; try { … } finally { curr.unlock(); pred.unlock(); }}
Remove method
Art of Multiprocessor Programming 107 Remove method public boolean remove(Item item) { int key = item.hashCode(); Node pred, curr; try { … } finally { curr.unlock(); pred.unlock(); }} Key used to order node
Remove method
Art of Multiprocessor Programming 108 Remove method public boolean remove(Item item) { int key = item.hashCode(); Node pred, curr; try { … } finally { currNode.unlock(); predNode.unlock(); }} Predecessor and current nodes
Remove method
Art of Multiprocessor Programming 109 Remove method public boolean remove(Item item) { int key = item.hashCode(); Node pred, curr; try { … } finally { curr.unlock(); pred.unlock(); }} Make sure locks released
Remove method
Art of Multiprocessor Programming 110 Remove method public boolean remove(Item item) { int key = item.hashCode(); Node pred, curr; try { … } finally { curr.unlock(); pred.unlock(); }} Everything else
Remove method
Art of Multiprocessor Programming 111 Remove method try { pred = this .head; pred.lock(); curr = pred.next; curr.lock(); … } finally { … }
Remove method
Art of Multiprocessor Programming 112 Remove method try { pred = this .head; pred.lock(); curr = pred.next; curr.lock(); … } finally { … } lock pred == head
Remove method
Art of Multiprocessor Programming 113 Remove method try { pred = this.head; pred.lock(); curr = pred.next; curr.lock(); … } finally { … } Lock current
Remove method
Art of Multiprocessor Programming 114 Remove method try { pred = this.head; pred.lock(); curr = pred.next; curr.lock(); … } finally { … } Traversing list
Remove: searching
Art of Multiprocessor Programming 115 Remove: searching while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true ; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false ;
Remove: searching
Art of Multiprocessor Programming 116 Remove: searching while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false; Search key range
Remove: searching
Art of Multiprocessor Programming 117 Remove: searching while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false; At start of each loop: curr and pred locked
Remove: searching
Art of Multiprocessor Programming 118 Remove: searching while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true ; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false; If item found, remove node
Remove: searching
Art of Multiprocessor Programming 119 Remove: searching while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true ; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false; If node found, remove it
Remove: searching
Art of Multiprocessor Programming 120 Remove: searching while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false; Unlock predecessor
Remove: searching
Art of Multiprocessor Programming 121 Remove: searching while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false; Only one node locked!
Remove: searching
Art of Multiprocessor Programming 122 Remove: searching while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false; demote current
Remove: searching
Art of Multiprocessor Programming 123 Remove: searching while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = currNode; curr = curr.next; curr.lock(); } return false; Find and lock new current
Remove: searching
Art of Multiprocessor Programming 124 Remove: searching while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = currNode; curr = curr.next; curr.lock(); } return false; Lock invariant restored
Remove: searching
Art of Multiprocessor Programming 125 Remove: searching while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false ; Otherwise, not present
Why remove() is linearizable
Art of Multiprocessor Programming 127 while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false; Why remove() is linearizable • pred reachable from head • curr is pred.next • So curr.item is in the set
Why remove() is linearizable
Art of Multiprocessor Programming 128 while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false; Why remove() is linearizable Linearization point if item is present
Why remove() is linearizable
Art of Multiprocessor Programming 129 while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true ; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false; Why remove() is linearizable Node locked, so no other thread can remove it ….
Why remove() is linearizable
Art of Multiprocessor Programming 130 while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false ; Why remove() is linearizable Item not present
Why remove() is linearizable
Art of Multiprocessor Programming 131 while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false ; Why remove() is linearizable • pred reachable from head • curr is pred.next • pred.key < key • key < curr.key
Why remove() is linearizable
Art of Multiprocessor Programming 132 while (curr.key <= key) { if (item == curr.item) { pred.next = curr.next; return true; } pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } return false; Why remove() is linearizable Linearization point
Adding Nodes
Art of Multiprocessor Programming 133 Adding Nodes • To add node e – Must lock predecessor – Must lock successor • Neither can be deleted – (Is successor lock actually required?)
Same Abstraction Map
Art of Multiprocessor Programming 134 Same Abstraction Map • S( head ) = – { x | there exists a such that • a reachable from head and • a.item = x – }
Rep Invariant
Art of Multiprocessor Programming 135 Rep Invariant • Easy to check that – tail always reachable from head – Nodes sorted, no duplicates
Drawbacks
Art of Multiprocessor Programming 136 Drawbacks • Better than coarse-grained lock – Threads can traverse in parallel • Still not ideal – Long chain of acquire/release – Inefficient
Optimistic Synchronization
Art of Multiprocessor Programming 137 Optimistic Synchronization • Find nodes without locking • Lock nodes • Check that everything is OK
Optimistic: Traverse without Locking
Art of Multiprocessor Programming 138 Optimistic: Traverse without Locking b d e a add(c) Aha!
Optimistic: Lock and Load
Art of Multiprocessor Programming 139 Optimistic: Lock and Load b d e a add(c)
Optimistic: Lock and Load
Art of Multiprocessor Programming 140 Optimistic: Lock and Load b d e a add(c) c
What could go wrong?
Art of Multiprocessor Programming 141 What could go wrong? b d e a add(c) Aha!
What could go wrong?
Art of Multiprocessor Programming 142 What could go wrong? b d e a add(c)
What could go wrong?
Art of Multiprocessor Programming 143 What could go wrong? b d e a remove(b)
What could go wrong?
Art of Multiprocessor Programming 144 What could go wrong? b d e a remove(b)
What could go wrong?
Art of Multiprocessor Programming 145 What could go wrong? b d e a add(c)
What could go wrong?
Art of Multiprocessor Programming 146 What could go wrong? b d e a add(c) c
What could go wrong?
Art of Multiprocessor Programming 147 What could go wrong? d e a add(c) Uh-oh
Validate – Part 1
Art of Multiprocessor Programming 148 Validate – Part 1 b d e a add(c) Yes, b still reachable from head
What Else Could Go Wrong?
Art of Multiprocessor Programming 149 What Else Could Go Wrong? b d e a add(c) Aha!
What Else Coould Go Wrong?
Art of Multiprocessor Programming 150 What Else Coould Go Wrong? b d e a add(c) add(b’)
What Else Coould Go Wrong?
Art of Multiprocessor Programming 151 What Else Coould Go Wrong? b d e a add(c) add(b’) b’
What Else Could Go Wrong?
Art of Multiprocessor Programming 152 What Else Could Go Wrong? b d e a add(c) b’
What Else Could Go Wrong?
Art of Multiprocessor Programming 153 What Else Could Go Wrong? b d e a add(c) c
Validate Part 2 (while holding locks)
Art of Multiprocessor Programming 154 Validate Part 2 (while holding locks) b d e a add(c) Yes, b still points to d
Optimistic: Linearization Point
Art of Multiprocessor Programming 155 Optimistic: Linearization Point b d e a add(c) c
Same Abstraction Map
Art of Multiprocessor Programming 156 Same Abstraction Map • S( head ) = – { x | there exists a such that • a reachable from head and • a.item = x – }
Invariants
Art of Multiprocessor Programming 157 Invariants • Careful : we may traverse deleted nodes • But we establish properties by – Validation – After we lock target nodes
Correctness
Art of Multiprocessor Programming 158 Correctness • If – Nodes b and c both locked – Node b still accessible – Node c still successor to b • Then – Neither will be deleted – OK to delete and return true
Unsuccessful Remove
Art of Multiprocessor Programming 159 Unsuccessful Remove a b d e remove(c) Aha!
Validate (1)
Art of Multiprocessor Programming 160 Validate (1) a b d e Yes, b still reachable from head remove(c)
Validate (2)
Art of Multiprocessor Programming 161 Validate (2) a b d e remove(c) Yes, b still points to d
OK Computer
Art of Multiprocessor Programming 162 OK Computer a b d e remove(c) return false
Correctness
Art of Multiprocessor Programming 163 Correctness • If – Nodes b and d both locked – Node b still accessible – Node d still successor to b • Then – Neither will be deleted – No thread can add c after b – OK to return false
Validation
Art of Multiprocessor Programming 164 Validation private boolean validate(Node pred, Node curry) { Node node = head; while (node.key <= pred.key) { if (node == pred) return pred.next == curr; node = node.next; } return false ; }
Validation
Art of Multiprocessor Programming 165 private boolean validate (Node pred, Node curr) { Node node = head; while (node.key <= pred.key) { if (node == pred) return pred.next == curr; node = node.next; } return false; } Validation Predecessor & current nodes
Validation
Art of Multiprocessor Programming 166 private boolean validate(Node pred, Node curr) { Node node = head; while (node.key <= pred.key) { if (node == pred) return pred.next == curr; node = node.next; } return false; } Validation Begin at the beginning
Validation
Art of Multiprocessor Programming 167 private boolean validate(Node pred, Node curr) { Node node = head; while (node.key <= pred.key) { if (node == pred) return pred.next == curr; node = node.next; } return false; } Validation Search range of keys
Validation
Art of Multiprocessor Programming 168 private boolean validate(Node pred, Node curr) { Node node = head; while (node.key <= pred.key) { if (node == pred) return pred.next == curr; node = node.next; } return false; } Validation Predecessor reachable
Validation
Art of Multiprocessor Programming 169 private boolean validate(Node pred, Node curr) { Node node = head; while (node.key <= pred.key) { if (node == pred) return pred.next == curr; node = node.next; } return false; } Validation Is current node next?
Validation
Art of Multiprocessor Programming 170 private boolean validate(Node pred, Node curr) { Node node = head; while (node.key <= pred.key) { if (node == pred) return pred.next == curr; node = node.next; } return false; } Validation Otherwise move on
Validation
Art of Multiprocessor Programming 171 private boolean validate(Node pred, Node curr) { Node node = head; while (node.key <= pred.key) { if (node == pred) return pred.next == curr; node = node.next; } return false ; } Validation Predecessor not reachable
Remove: searching
Art of Multiprocessor Programming 172 Remove: searching public boolean remove(Item item) { int key = item.hashCode(); retry: while ( true ) { Node pred = this .head; Node curr = pred.next; while (curr.key <= key) { if (item == curr.item) break ; pred = curr; curr = curr.next; } …
Remove: searching
Art of Multiprocessor Programming 173 public boolean remove(Item item) { int key = item.hashCode(); retry: while (true) { Node pred = this.head; Node curr = pred.next; while (curr.key <= key) { if (item == curr.item) break; pred = curr; curr = curr.next; } … Remove: searching Search key
Remove: searching
Art of Multiprocessor Programming 174 public boolean remove(Item item) { int key = item.hashCode(); retry: while ( true ) { Node pred = this.head; Node curr = pred.next; while (curr.key <= key) { if (item == curr.item) break; pred = curr; curr = curr.next; } … Remove: searching Retry on synchronization conflict
Remove: searching
Art of Multiprocessor Programming 175 public boolean remove(Item item) { int key = item.hashCode(); retry: while (true) { Node pred = this .head; Node curr = pred.next; while (curr.key <= key) { if (item == curr.item) break; pred = curr; curr = curr.next; } … Remove: searching Examine predecessor and current nodes
Remove: searching
Art of Multiprocessor Programming 176 public boolean remove(Item item) { int key = item.hashCode(); retry: while (true) { Node pred = this.head; Node curr = pred.next; while (curr.key <= key) { if (item == curr.item) break; pred = curr; curr = curr.next; } … Remove: searching Search by key
Remove: searching
Art of Multiprocessor Programming 177 public boolean remove(Item item) { int key = item.hashCode(); retry: while (true) { Node pred = this.head; Node curr = pred.next; while (curr.key <= key) { if (item == curr.item) break ; pred = curr; curr = curr.next; } … Remove: searching Stop if we find item
Remove: searching
Art of Multiprocessor Programming 178 public boolean remove(Item item) { int key = item.hashCode(); retry: while (true) { Node pred = this.head; Node curr = pred.next; while (curr.key <= key) { if (item == curr.item) break; pred = curr; curr = curr.next; } … Remove: searching Move along
On Exit from Loop
Art of Multiprocessor Programming 179 On Exit from Loop • If item is present – curr holds item – pred just before curr • If item is absent – curr has first higher key – pred just before curr • Assuming no synchronization problems
Remove Method
Art of Multiprocessor Programming 180 Remove Method try { pred.lock(); curr.lock(); if (validate(pred,curr) { if (curr.item == item) { pred.next = curr.next; return true ; } else { return false ; }}} finally { pred.unlock(); curr.unlock(); }}}
Remove Method
Art of Multiprocessor Programming 181 try { pred.lock(); curr.lock(); if (validate(pred,curr) { if (curr.item == item) { pred.next = curr.next; return true; } else { return false; }}} finally { pred.unlock(); curr.unlock(); }}} Remove Method Always unlock
Remove Method
Art of Multiprocessor Programming 182 try { pred.lock(); curr.lock(); if (validate(pred,curr) { if (curr.item == item) { pred.next = curr.next; return true; } else { return false; }}} finally { pred.unlock(); curr.unlock(); }}} Remove Method Lock both nodes
Remove Method
Art of Multiprocessor Programming 183 try { pred.lock(); curr.lock(); if (validate(pred,curr) { if (curr.item == item) { pred.next = curr.next; return true; } else { return false; }}} finally { pred.unlock(); curr.unlock(); }}} Remove Method Check for synchronization conflicts
Remove Method
Art of Multiprocessor Programming 184 try { pred.lock(); curr.lock(); if (validate(pred,curr) { if (curr.item == item) { pred.next = curr.next; return true ; } else { return false; }}} finally { pred.unlock(); curr.unlock(); }}} Remove Method target found, remove node
Remove Method
Art of Multiprocessor Programming 185 try { pred.lock(); curr.lock(); if (validate(pred,curr) { if (curr.item == item) { pred.next = curr.next; return true; } else { return false ; }}} finally { pred.unlock(); curr.unlock(); }}} Remove Method target not found
Optimistic List
Art of Multiprocessor Programming 186 Optimistic List • Limited hot-spots – Targets of add() , remove() , contains() – No contention on traversals • Moreover – Traversals are wait-free – Food for thought …
So Far, So Good
Art of Multiprocessor Programming 187 So Far, So Good • Much less lock acquisition/release – Performance – Concurrency • Problems – Need to traverse list twice – contains() method acquires locks
Evaluation
Art of Multiprocessor Programming 188 Evaluation • Optimistic is effective if – cost of scanning twice without locks is less than – cost of scanning once with locks • Drawback – contains() acquires locks – 90% of calls in many apps
Lazy List
Art of Multiprocessor Programming 189 Lazy List • Like optimistic, except – Scan once – contains(x) never locks … • Key insight – Removing nodes causes trouble – Do it “lazily”
Lazy List
Art of Multiprocessor Programming 190 Lazy List • remove() – Scans list (as before) – Locks predecessor & current (as before) • Logical delete – Marks current node as removed (new!) • Physical delete – Redirects predecessor’s next (as before)
Lazy Removal
Art of Multiprocessor Programming 191 Lazy Removal a a b c d
Lazy Removal
c Art of Multiprocessor Programming 192 Lazy Removal a a b d Present in list
Lazy Removal
c Art of Multiprocessor Programming 193 Lazy Removal a a b d Logically deleted
Lazy Removal
Art of Multiprocessor Programming 194 Lazy Removal a a b c d Physically deleted
Lazy Removal
Art of Multiprocessor Programming 195 Lazy Removal a a b d Physically deleted
Lazy List
Art of Multiprocessor Programming 196 Lazy List • All Methods – Scan through locked and marked nodes – Removing a node doesn’t slow down other method calls … • Must still lock pred and curr nodes.
Validation
Art of Multiprocessor Programming 197 Validation • No need to rescan list! • Check that pred is not marked • Check that curr is not marked • Check that pred points to curr
Business as Usual
Art of Multiprocessor Programming 198 Business as Usual a b c
Business as Usual
Art of Multiprocessor Programming 199 Business as Usual a b c
Business as Usual
Art of Multiprocessor Programming 200 Business as Usual a b c
Business as Usual
Art of Multiprocessor Programming 201 Business as Usual a b c remove(b)
Business as Usual
Art of Multiprocessor Programming 202 Business as Usual a b c a not marked
Business as Usual
Art of Multiprocessor Programming 203 Business as Usual a b c a still points to b
Business as Usual
Art of Multiprocessor Programming 204 Business as Usual a b c Logical delete
Business as Usual
Art of Multiprocessor Programming 205 Business as Usual a b c physical delete
Business as Usual
Art of Multiprocessor Programming 206 Business as Usual a b c
New Abstraction Map
Art of Multiprocessor Programming 207 New Abstraction Map • S( head ) = – { x | there exists node a such that • a reachable from head and • a.item = x and • a is unmarked – }
Invariant
Art of Multiprocessor Programming 208 Invariant • If not marked then item in the set • and reachable from head • and if not yet traversed it is reachable from pred
Validation
Art of Multiprocessor Programming 209 Validation private boolean validate(Node pred, Node curr) { return !pred.marked && !curr.marked && pred.next == curr); }
List Validate Method
Art of Multiprocessor Programming 210 private boolean validate(Node pred, Node curr) { return !pred.marked && !curr.marked && pred.next == curr); } List Validate Method Predecessor not Logically removed
List Validate Method
Art of Multiprocessor Programming 211 private boolean validate(Node pred, Node curr) { return !pred.marked && !curr.marked && pred.next == curr); } List Validate Method Current not Logically removed
List Validate Method
Art of Multiprocessor Programming 212 private boolean validate(Node pred, Node curr) { return !pred.marked && !curr.marked && pred.next == curr); } List Validate Method Predecessor still Points to current
Remove
Art of Multiprocessor Programming 213 Remove try { pred.lock(); curr.lock(); if (validate(pred,curr) { if (curr.key == key) { curr.marked = true ; pred.next = curr.next; return true ; } else { return false ; }}} finally { pred.unlock(); curr.unlock(); }}}
Remove
Art of Multiprocessor Programming 214 Remove try { pred.lock(); curr.lock(); if (validate(pred,curr) { if (curr.key == key) { curr.marked = true; pred.next = curr.next; return true; } else { return false; }}} finally { pred.unlock(); curr.unlock(); }}} Validate as before
Remove
Art of Multiprocessor Programming 215 Remove try { pred.lock(); curr.lock(); if (validate(pred,curr) { if (curr.key == key) { curr.marked = true; pred.next = curr.next; return true; } else { return false; }}} finally { pred.unlock(); curr.unlock(); }}} Key found
Remove
Art of Multiprocessor Programming 216 Remove try { pred.lock(); curr.lock(); if (validate(pred,curr) { if (curr.key == key) { curr.marked = true ; pred.next = curr.next; return true; } else { return false; }}} finally { pred.unlock(); curr.unlock(); }}} Logical remove
Remove
Art of Multiprocessor Programming 217 Remove try { pred.lock(); curr.lock(); if (validate(pred,curr) { if (curr.key == key) { curr.marked = true; pred.next = curr.next; return true; } else { return false; }}} finally { pred.unlock(); curr.unlock(); }}} physical remove
Contains
Art of Multiprocessor Programming 218 Contains public boolean contains(Item item) { int key = item.hashCode(); Node curr = this .head; while (curr.key < key) { curr = curr.next; } return curr.key == key && !curr.marked; }
Contains
Art of Multiprocessor Programming 219 Contains public boolean contains(Item item) { int key = item.hashCode(); Node curr = this .head; while (curr.key < key) { curr = curr.next; } return curr.key == key && !curr.marked; } Start at the head
Contains
Art of Multiprocessor Programming 220 Contains public boolean contains(Item item) { int key = item.hashCode(); Node curr = this.head; while (curr.key < key) { curr = curr.next; } return curr.key == key && !curr.marked; } Search key range
Contains
Art of Multiprocessor Programming 221 Contains public boolean contains(Item item) { int key = item.hashCode(); Node curr = this.head; while (curr.key < key) { curr = curr.next; } return curr.key == key && !curr.marked; } Traverse without locking (nodes may have been removed)
Contains
Art of Multiprocessor Programming 222 Contains public boolean contains(Item item) { int key = item.hashCode(); Node curr = this.head; while (curr.key < key) { curr = curr.next; } return curr.key == key && !curr.marked; } Present and undeleted?
Summary: Wait-free Contains
Art of Multiprocessor Programming 223 Summary: Wait-free Contains a 0 0 0 a b c 0 e 1 d Use Mark bit + list ordering 1. Not marked in the set 2. Marked or missing not in the set
Lazy List
Art of Multiprocessor Programming 224 Lazy List a 0 0 0 a b c 0 e 1 d Lazy add() and remove() + Wait-free contains()
Evaluation
Art of Multiprocessor Programming 225 Evaluation • Good: – contains() doesn’t lock – In fact, its wait-free! – Good because typically high % contains() – Uncontended calls don’t re-traverse • Bad – Contended add() and remove() calls do re- traverse – Traffic jam if one thread delays
Traffic Jam
Art of Multiprocessor Programming 226 Traffic Jam • Any concurrent data structure based on mutual exclusion has a weakness • If one thread – Enters critical section – And “eats the big muffin” • Cache miss, page fault, descheduled … – Everyone else using that lock is stuck! – Need to trust the scheduler….
Reminder: Lock-Free Data Structures
Art of Multiprocessor Programming 227 Reminder: Lock-Free Data Structures • No matter what … – Guarantees minimal progress in any execution – i.e. Some thread will always complete a method call – Even if others halt at malicious times – Implies that implementation can’t use locks
Lock-free Lists
Art of Multiprocessor Programming 228 Lock-free Lists • Next logical step – Wait-free contains() – lock-free add() and remove() • Use only compareAndSet() – What could go wrong?
Lock-free Lists
Art of Multiprocessor Programming 229 a 0 0 0 a b c 0 e 1 c Logical Removal Physical Removal Use CAS to verify pointer is correct Not enough! Lock-free Lists
Problem…
Art of Multiprocessor Programming 230 Problem… a 0 0 0 a b c 0 e 1 c Logical Removal Physical Removal 0 d Node added
The Solution: Combine Bit and Pointer
Art of Multiprocessor Programming 231 The Solution: Combine Bit and Pointer a 0 0 0 a b c 0 e 1 c Logical Removal = Set Mark Bit Physical Removal CAS 0 d Mark-Bit and Pointer are CASed together (AtomicMarkableReference) Fail CAS: Node not added after logical Removal
Solution
Art of Multiprocessor Programming 232 Solution • Use AtomicMarkableReference • Atomically – Swing reference and – Update flag • Remove in two steps – Set mark bit in next field – Redirect predecessor’s pointer
Marking a Node
Art of Multiprocessor Programming 233 Marking a Node • AtomicMarkableReference class – Java.util.concurrent.atomic package address F mark bit Reference
Extracting Reference & Mark
Art of Multiprocessor Programming 234 Extracting Reference & Mark Public Object get( boolean [] marked);
Extracting Reference & Mark
Art of Multiprocessor Programming 235 Extracting Reference & Mark Public Object get( boolean [] marked); Returns reference Returns mark at array index 0!
Extracting Mark Only
Art of Multiprocessor Programming 236 Extracting Mark Only public boolean isMarked(); Value of mark
Changing State
Art of Multiprocessor Programming 237 Changing State Public boolean compareAndSet( Object expectedRef, Object updateRef, boolean expectedMark, boolean updateMark);
Changing State
Art of Multiprocessor Programming 238 Changing State Public boolean compareAndSet( Object expectedRef, Object updateRef, boolean expectedMark, boolean updateMark); If this is the current reference … And this is the current mark …
Changing State
Art of Multiprocessor Programming 239 Changing State Public boolean compareAndSet( Object expectedRef, Object updateRef, boolean expectedMark, boolean updateMark); …then change to this new reference … … and this new mark
Changing State
Art of Multiprocessor Programming 240 Changing State public boolean attemptMark( Object expectedRef, boolean updateMark);
Changing State
Art of Multiprocessor Programming 241 Changing State public boolean attemptMark( Object expectedRef, boolean updateMark); If this is the current reference …
Changing State
Art of Multiprocessor Programming 242 Changing State public boolean attemptMark( Object expectedRef, boolean updateMark); .. then change to this new mark.
Removing a Node
b CAS Art of Multiprocessor Programming 243 Removing a Node a c d remove c
Removing a Node
Art of Multiprocessor Programming 244 Removing a Node a b d remove b remove c c failed CAS CAS
Removing a Node
Art of Multiprocessor Programming 245 Removing a Node a b d remove b remove c c
Removing a Node
Art of Multiprocessor Programming 246 Removing a Node a d remove b remove c
Traversing the List
Art of Multiprocessor Programming 247 Traversing the List • Q : what do you do when you find a “logically” deleted node in your path? • A : finish the job. – CAS the predecessor’s next field – Proceed (repeat as needed)
Lock-Free Traversal (only Add and Remove)
Art of Multiprocessor Programming 248 Lock-Free Traversal (only Add and Remove) a b c d CAS Uh-oh pred curr pred curr
The Window Class
Art of Multiprocessor Programming 249 The Window Class class Window { public Node pred; public Node curr; Window(Node pred, Node curr) { this .pred = pred; this .curr = curr; } }
The Window Class
Art of Multiprocessor Programming 250 The Window Class class Window { public Node pred; public Node curr; Window(Node pred, Node curr) { this.pred = pred; this.curr = curr; } } A container for pred and current values
Using the Find Method
Art of Multiprocessor Programming 251 Using the Find Method Window window = find(head, key); Node pred = window.pred; curr = window.curr;
Using the Find Method
Art of Multiprocessor Programming 252 Using the Find Method Window window = find(head, key); Node pred = window.pred; curr = window.curr; Find returns window
Using the Find Method
Art of Multiprocessor Programming 253 Using the Find Method Window window = find(head, key); Node pred = window.pred; curr = window.curr; Extract pred and curr
The Find Method
Art of Multiprocessor Programming© Herlihy-Shavit 2007 254 The Find Method Window window = find(item); At some instant, pred curr succ item or …
The Find Method
Art of Multiprocessor Programming© Herlihy-Shavit 2007 255 The Find Method Window window = find(item); At some instant, pred curr= null succ item not in list
Remove
Art of Multiprocessor Programming 256 Remove public boolean remove(T item) { Boolean snip; while ( true ) { Window window = find(head, key); Node pred = window.pred, curr = window.curr; if (curr.key != key) { return false ; } else { Node succ = curr.next.getReference(); snip = curr.next.compareAndSet(succ, succ, false true ); if (!snip) continue ; pred.next.compareAndSet(curr, succ, false , false ); return true ; }}}
Remove
Art of Multiprocessor Programming 257 Remove public boolean remove(T item) { Boolean snip; while ( true ) { Window window = find(head, key); Node pred = window.pred, curr = window.curr; if (curr.key != key) { return false; } else { Node succ = curr.next.getReference(); snip = curr.next.compareAndSet (succ, succ, false, true); if (!snip) continue; pred.next.compareAndSet(curr, succ, false, false); return true; }}} Keep trying
Remove
Art of Multiprocessor Programming 258 Remove public boolean remove(T item) { Boolean snip; while (true) { Window window = find(head, key); Node pred = window.pred, curr = window.curr; if (curr.key != key) { return false; } else { Node succ = curr.next.getReference(); snip = curr.next.compareAndSet (succ, succ, false, true); if (!snip) continue; pred.next.compareAndSet(curr, succ, false, false); return true; }}} Find neighbors
Remove
Art of Multiprocessor Programming 259 Remove public boolean remove(T item) { Boolean snip; while (true) { Window window = find(head, key); Node pred = window.pred, curr = window.curr; if (curr.key != key) { return false ; } else { Node succ = curr.next.getReference(); snip = curr.next.compareAndSet(succ, succ, false, true); if (!snip) continue; pred.next.compareAndSet(curr, succ, false, false); return true; }}} She’s not there …
Remove
Art of Multiprocessor Programming 260 Remove public boolean remove(T item) { Boolean snip; while (true) { Window window = find(head, key); Node pred = window.pred, curr = window.curr; if (curr.key != key) { return false; } else { Node succ = curr.next.getReference(); snip = curr.next.compareAndSet(succ, succ, false , true ); if (!snip) continue; pred.next.compareAndSet(curr, succ, false, false); return true; }}} Try to mark node as deleted
Remove
Art of Multiprocessor Programming 261 Remove public boolean remove(T item) { Boolean snip; while (true) { Window window = find(head, key); Node pred = window.pred, curr = window.curr; if (curr.key != key) { return false; } else { Node succ = curr.next.getReference(); snip = curr.next.compareAndSet(succ, succ, false, true); if (!snip) continue ; pred.next.compareAndSet(curr, succ, false, false); return true; }}} If it doesn’t work, just retry, if it does, job essentially done
Remove
Art of Multiprocessor Programming 262 Remove public boolean remove(T item) { Boolean snip; while (true) { Window window = find(head, key); Node pred = window.pred, curr = window.curr; if (curr.key != key) { return false; } else { Node succ = curr.next.getReference(); snip = curr.next.compareAndSet(succ, succ, false, true); if (!snip) continue; pred.next.compareAndSet(curr, succ, false , false ); return true ; }}} Try to advance reference (if we don’t succeed, someone else did or will). a
Add
Art of Multiprocessor Programming 263 Add public boolean add(T item) { boolean splice; while ( true ) { Window window = find(head, key); Node pred = window.pred, curr = window.curr; if (curr.key == key) { return false ; } else { Node node = new Node(item); node.next = new AtomicMarkableRef(curr, false ); if (pred.next.compareAndSet(curr, node, false , false )) { return true ;} }}}
Add
Art of Multiprocessor Programming 264 Add public boolean add(T item) { boolean splice; while (true) { Window window = find(head, key); Node pred = window.pred, curr = window.curr; if (curr.key == key) { return false ; } else { Node node = new Node(item); node.next = new AtomicMarkableRef(curr, false); if (pred.next.compareAndSet(curr, node, false, false)) {return true;} }}} Item already there.
Add
Art of Multiprocessor Programming 265 Add public boolean add(T item) { boolean splice; while (true) { Window window = find(head, key); Node pred = window.pred, curr = window.curr; if (curr.key == key) { return false; } else { Node node = new Node(item); node.next = new AtomicMarkableRef(curr, false ); if (pred.next.compareAndSet(curr, node, false, false)) {return true;} }}} create new node
Add
Art of Multiprocessor Programming 266 Add public boolean add(T item) { boolean splice; while (true) { Window window = find(head, key); Node pred = window.pred, curr = window.curr; if (curr.key == key) { return false; } else { Node node = new Node(item); node.next = new AtomicMarkableRef(curr, false); if (pred.next.compareAndSet(curr, node, false , false )) { return true ;} }}} Install new node, else retry loop
Wait-free Contains
Art of Multiprocessor Programming 267 Wait-free Contains public boolean contains(T item) { boolean marked; int key = item.hashCode(); Node curr = this .head; while (curr.key < key) curr = curr.next; Node succ = curr.next.get(marked); return (curr.key == key && !marked[0]) }
Wait-free Contains
Art of Multiprocessor Programming 268 Wait-free Contains public boolean contains(T item) { boolean marked; int key = item.hashCode(); Node curr = this.head; while (curr.key < key) curr = curr.next; Node succ = curr.next.get(marked); return (curr.key == key && !marked[0]) } Only diff is that we get and check marked
Lock-free Find
Art of Multiprocessor Programming 269 Lock-free Find public Window find(Node head, int key) { Node pred = null, curr = null, succ = null; boolean[] marked = { false }; boolean snip; retry: while ( true ) { pred = head; curr = pred.next.getReference(); while ( true ) { succ = curr.next.get(marked); while (marked[0]) { … } if (curr.key >= key) return new Window(pred, curr); pred = curr; curr = succ; } }}
Lock-free Find
Art of Multiprocessor Programming 270 Lock-free Find public Window find(Node head, int key) { Node pred = null, curr = null, succ = null; boolean[] marked = {false}; boolean snip; retry: while ( true ) { pred = head; curr = pred.next.getReference(); while (true) { succ = curr.next.get(marked); while (marked[0]) { … } if (curr.key >= key) return new Window(pred, curr); pred = curr; curr = succ; } }} If list changes while traversed, start over
Lock-free Find
Art of Multiprocessor Programming 271 public Window find(Node head, int key) { Node pred = null, curr = null, succ = null; boolean[] marked = {false}; boolean snip; retry: while (true) { pred = head; curr = pred.next.getReference(); while (true) { succ = curr.next.get(marked); while (marked[0]) { … } if (curr.key >= key) return new Window(pred, curr); pred = curr; curr = succ; } }} Lock-free Find Start looking from head
Lock-free Find
Art of Multiprocessor Programming 272 public Window find(Node head, int key) { Node pred = null, curr = null, succ = null; boolean[] marked = {false}; boolean snip; retry: while (true) { pred = head; curr = pred.next.getReference(); while ( true ) { succ = curr.next.get(marked); while (marked[0]) { … } if (curr.key >= key) return new Window(pred, curr); pred = curr; curr = succ; } }} Lock-free Find Move down the list
Lock-free Find
Art of Multiprocessor Programming 273 public Window find(Node head, int key) { Node pred = null, curr = null, succ = null; boolean[] marked = {false}; boolean snip; retry: while (true) { pred = head; curr = pred.next.getReference(); while (true) { succ = curr.next.get(marked); while (marked[0]) { … } if (curr.key >= key) return new Window(pred, curr); pred = curr; curr = succ; } }} Lock-free Find Get ref to successor and current deleted bit
Lock-free Find
Art of Multiprocessor Programming 274 public Window find(Node head, int key) { Node pred = null, curr = null, succ = null; boolean[] marked = {false}; boolean snip; retry: while (true) { pred = head; curr = pred.next.getReference(); while (true) { succ = curr.next.get(marked); while (marked[0]) { … } if (curr.key >= key) return new Window(pred, curr); pred = curr; curr = succ; } }} Lock-free Find Try to remove deleted nodes in path…code details soon
Lock-free Find
Art of Multiprocessor Programming 275 public Window find(Node head, int key) { Node pred = null, curr = null, succ = null; boolean[] marked = {false}; boolean snip; retry: while (true) { pred = head; curr = pred.next.getReference(); while (true) { succ = curr.next.get(marked); while (marked[0]) { … } if (curr.key >= key) return new Window(pred, curr); pred = curr; curr = succ; } }} Lock-free Find If curr key that is greater or equal, return pred and curr
Lock-free Find
Art of Multiprocessor Programming 276 public Window find(Node head, int key) { Node pred = null, curr = null, succ = null; boolean[] marked = {false}; boolean snip; retry: while (true) { pred = head; curr = pred.next.getReference(); while (true) { succ = curr.next.get(marked); while (marked[0]) { … } if (curr.key >= key) return new Window(pred, curr); pred = curr; curr = succ; } }} Lock-free Find Otherwise advance window and loop again
Lock-free Find
Art of Multiprocessor Programming 277 Lock-free Find retry: while ( true ) { … while (marked[0]) { snip = pred.next.compareAndSet(curr, succ, false , false ); if (!snip) continue retry; curr = succ; succ = curr.next.get(marked); } …
Lock-free Find
Art of Multiprocessor Programming 278 Lock-free Find retry: while (true) { … while (marked[0]) { snip = pred.next.compareAndSet(curr, succ, false , false ); if (!snip) continue retry; curr = succ; succ = curr.next.get(marked); } … Try to snip out node
Lock-free Find
Art of Multiprocessor Programming 279 Lock-free Find retry: while (true) { … while (marked[0]) { snip = pred.next.compareAndSet(curr , succ, false, false); if (!snip) continue retry; curr = succ; succ = curr.next.get(marked); } … if predecessor’s next field changed, retry whole traversal
Lock-free Find
Art of Multiprocessor Programming 280 Lock-free Find retry: while (true) { … while (marked[0]) { snip = pred.next.compareAndSet(curr, succ, false, false); if (!snip) continue retry; curr = succ; succ = curr.next.get(marked); } … Otherwise move on to check if next node deleted
Performance
Performance • Different list-based set implementaions • 16-node machine • Vary percentage of contains() calls Art of Multiprocessor Programming 281
High Contains Ratio
Art of Multiprocessor Programming 282 High Contains Ratio Lock-free Lazy list Coarse Grained Fine Lock-coupling
Low Contains Ratio
Art of Multiprocessor Programming 283 Low Contains Ratio Lock-free Lazy list Coarse Grained Fine Lock-coupling
As Contains Ratio Increases
Art of Multiprocessor Programming 284 As Contains Ratio Increases Lock-free Lazy list Coarse Grained Fine Lock-coupling % Contains()
Summary
Art of Multiprocessor Programming 285 Summary • Coarse-grained locking • Fine-grained locking • Optimistic synchronization • Lazy synchronization • Lock-free synchronization
“To Lock or Not to Lock”
Art of Multiprocessor Programming 286 “To Lock or Not to Lock” • Locking vs. Non-blocking: – Extremist views on both sides • The answer: nobler to compromise – Example: Lazy list combines blocking add() and remove() and a wait-free contains() – Remember: Blocking/non-blocking is a property of a method
Art of Multiprocessor Programming 287   creativecommons.org/licenses/by-sa/2.5/ Creative Commons Attribution-ShareAlike 2.5 License . • You are free: – to Share — to copy, distribute and transmit the work – to Remix — to adapt the work • Under the following conditions: – Attribution . You must attribute the work to “The Art of Multiprocessor Programming” (but not in any way that suggests that the authors endorse you or your use of the work). – Share Alike . If you alter, transform, or build upon this work, you may distribute the resulting work only under the same, similar or a compatible license. • For any reuse or distribution, you must make clear to others the license terms of this work. The best way to do this is with a link to – http://creativecommons.org/licenses/by-sa/3.0/. • Any of the above conditions can be waived if you get permission from the copyright holder. • Nothing in this license impairs or restricts the author's moral rights.