6.852: Distributed Algorithms Fall, 2009 Class 19Today’s plan z Techniques for implementing concurrent objects:  Coarse-grained mutual exclusion  Fine-grained locking (mutex and read/write)  Optimistic locking  Lock-free/nonblocking algorithms  “Lazy” synchronization  We illustrate on list-based sets, but the techniques apply toother data structures z Reading:  Herlihy, Shavit, Chapter 9 z Next:  Transactional memory  HS, Chapter 18  Guerraoui, KapalkaShared-memory model • Shared variables • At most one memory access per atomic step. • Read/write access • Synchronization primitives: – Compare-and-swap (CAS) – Load-linked/store-conditional (LL/SC) – Assume lock and unlock methods for every object. • Most (not all) of our algorithms use locking. • Memory management: – Allocate objects dynamically, assume unlimited supply. – In practice, would garbage collect and reuse, but we won’t worryabout this. • Assume no failures (mostly).Correctness guarantees • Linearizability (atomicity) of object operations. • Liveness properties: – Different guarantees for different algorithms. – Progress: • Some operations keep completing. – Lockout-freedom (AKA starvation-freedom): • Every operation completes. – “Nonblocking” conditions: • Wait-freedom: Even if other processes stop, a particular operation bya process that keeps taking steps eventually finishes. • Lock-freedom: Even if some processes stop, if some keep takingsteps, then some operation finishes. • Can think of the stopped processes as failing, or as going slowly. • Captures the idea that slow processes don’t block others. • Rules out locking strategies. • Performance – Worst-case (time bounds) vs. average case (throughput). – No good formal modelsList-based sets • Data type: Set S of integers (no duplicates) – S.add(x): Boolean: S := S ෽ {x}; return true iff x not already in S – S.remove(x): Boolean: S := S \ {x}; return true iff x in S initially – S.contains(x): Boolean: return true iff x in S (no change to S) • Simple ordered linked-list-based implementation – Illustrates techniques useful for pointer-based data structures. – Unless set is small, this is a poor data structure for this specificdata type--better to use arrays, hash tables, etc. head  1 4 9 Sequential list-based set head  14 9  add(3) 3 head 1 4 9  remove(4)Sequential list-based set S.add(x) pred := S.head curr := pred.next while (curr.key < x) pred := curr curr := pred.next if curr.key = x then return false else node := new Node(x) node.next := curr pred.next := node return true S.remove(x) pred := S.head curr := pred.next while (curr.key < x) pred := curr curr := pred.next if curr.key = x then pred.next := curr.next return true else return false S.contains(x) curr := S.head while (curr.key < x) curr := curr.next if curr.key = x then return true else return falseSequential list-based set head S.remove(x) pred := S.head 4 9 1 pred curr remove(4) curr := pred.next while (curr.key < x) pred := curr curr := pred.next if curr.key = x then pred.next := curr.next return true else return falseCorrectness • Assume algorithm queues up operations, runs themsequentially. • Atomicity (linearizability): – Show the algorithm implements a canonical atomic set object. – Use forward simulation relation: Set consists of those elements that are reachable from the head of the list via list pointers. – When do “perform” steps occur? • add(x): If successful, then when pred.next := node, else any timeduring the operation. • remove(x): If successful, then when pred.next := curr.next, else any time during the operation. • contains(x): Any time during the operation. – Proof uses invariants saying that the list is ordered and contains noduplicates. • Liveness: Lockout-free, but blocking (not wait-free or lock-free)Invariants • Keys strictly increase down the list. – List is ordered. – No duplicates. • Keys of first and last nodes (i.e., the “sentinels”) are ෱ and ෱ respectively. • pred.key < x • pred.key < curr.key • pred.next ำ null •…Allowing concurrent access z Can this algorithm tolerate concurrent execution of the operations by different processes? z What can go wrong? z How can we fix it?Concurrent operations (bad) head 9 1 4 pred curr remove(4) S.remove(x) pred := S.head curr := pred.next while (curr.key < x) pred := curr curr := pred.next if curr.key = x then pred.next := curr.next return true else return false pred curr remove(9)Techniques for managing concurrent operations • Coarse-grained mutual exclusion • Fine-grained locking • Optimistic locking • Lock-free/nonblocking algorithms • “Lazy” synchronizationCoarse-grained mutual exclusion • Each process acquires a global lock, for the entire time it is executing significant steps of an operation implementation.Coarse-grained locking S.add(x) Why can we unlock early here? S.lock() pred := S.head curr := pred.next while (curr.key < x) pred := curr curr := pred.next if curr.key = x then S.unlock() return false else node := new Node(x) node.next := curr pred.next := node S.unlock() return true S.lock() pred := S.head curr := pred.next while (curr.key < x) pred := curr curr := pred.next if curr.key = x then pred.next := curr.next S.unlock() return true else S.unlock() return false S.contains(x) S.lock() curr := S.head while (curr.key < x) curr := curr.next S.unlock() if curr.key = x then return true else return falseCorrectness • Similar to sequential implementation. • Atomicity: – Show the algorithm implements a canonical atomic set object. – Use forward simulation: S = elements that are reachable in the list – When do “perform” steps occur? • add(x): If successful, then when pred.next := node, else any time the lock is held. • remove(x): If successful, then when pred.next := curr.next, else any time the lock is held. • contains(x): Any time the lock is held. – Invariant: If an operation holds the lock, then any node it visits isreachable in the list. • Liveness: – Guarantees progress, assuming that the lock does. – May or may not be lockout-free, depending on whether the lock is. – Blocking (not wait-free or lock-free): • Everything comes to a halt if someone stops while