The Relative Power of Synchronization Operations
The Relative Power of Synchronization Operations Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit
Art of Multiprocessor Programming 2 Shared-Memory Computability • Mathematical model of concurrent computation • What is (and is not) concurrently computable • Efficiency (mostly) irrelevant 10011 Shared Memory
Wait-Free Implementation
Art of Multiprocessor Programming 3 Wait-Free Implementation • Every method call completes in finite number of steps • Implies no mutual exclusion
From Weakest Register
Art of Multiprocessor Programming 4 From Weakest Register 1 0 1 Single reader Single writer Safe Boolean register
All the way to a Wait-free Implementation of Atomic Snapshots
Art of Multiprocessor Programming 5 All the way to a Wait-free Implementation of Atomic Snapshots MRMW MRSW SRSW Saf e Regular Atomic M-valued Boolean Snapshot
Rationale for wait-freedom
Art of Multiprocessor Programming 6 Rationale for wait-freedom • We wanted atomic registers to implement mutual exclusion
Rationale for wait-freedom
Art of Multiprocessor Programming 7 Rationale for wait-freedom • We wanted atomic registers to implement mutual exclusion • So we couldn’t use mutual exclusion to implement atomic registers
Rationale for wait-freedom
Art of Multiprocessor Programming 8 Rationale for wait-freedom • We wanted atomic registers to implement mutual exclusion • So we couldn’t use mutual exclusion to implement atomic registers • But wait, there’s more!
Art of Multiprocessor Programming 9 Why is Mutual Exclusion so wrong?
Asynchronous Interrupts
Art of Multiprocessor Programming 10 Asynchronous Interrupts Swapped out back at ??? ???
Heterogeneous Processors
Art of Multiprocessor Programming 11 Heterogeneous Processors ??? ??? yawn supercomputer supercomputer toaster
Fault-tolerance
Art of Multiprocessor Programming 12 Fault-tolerance ??? ???
Machine Level Instruction Granularity
Art of Multiprocessor Programming 13 Machine Level Instruction Granularity Amdahl’s Law
Basic Questions
Art of Multiprocessor Programming 14 Basic Questions • Wait-Free synchronization might be a good idea in principle
Basic Questions
Art of Multiprocessor Programming 15 Basic Questions • Wait-Free synchronization might be a good idea in principle • But how do you do it …
Basic Questions
16 Basic Questions • Wait-Free synchronization might be a good idea in principle • But how do you do it … – Systematically? Art of Multiprocessor Programming
Basic Questions
17 Basic Questions • Wait-Free synchronization might be a good idea in principle • But how do you do it … – Systematically? – Correctly? Art of Multiprocessor Programming
Basic Questions
18 Basic Questions • Wait-Free synchronization might be a good idea in principle • But how do you do it … – Systematically? – Correctly? – Efficiently? Art of Multiprocessor Programming
FIFO Queue: Enqueue Method
19 FIFO Queue: Enqueue Method q.enq( ) Art of Multiprocessor Programming
FIFO Queue: Dequeue Method
20 FIFO Queue: Dequeue Method q.deq()/ Art of Multiprocessor Programming
Two-Thread Wait-Free Queue
21 Two-Thread Wait-Free Queue public class WaitFreeQueue { int head = 0, tail = 0; Item[QSIZE] items; public void enq(Item x) { while (tail - head == QSIZE) {}; items[tail % QSIZE] = x; tail++; } public Item deq() { while (tail - head == 0) {} Item item = items[head % QSIZE]; head++; return item; }} Art of Multiprocessor Programming 0 1 capacity-1 2 head tail y z
What About Multiple Dequeuers?
22 What About Multiple Dequeuers? Art of Multiprocessor Programming
Grand Challenge
23 Grand Challenge • Implement a FIFO queue Art of Multiprocessor Programming
Grand Challenge
24 Grand Challenge • Implement a FIFO queue – Wait-free Art of Multiprocessor Programming
Grand Challenge
25 Grand Challenge • Implement a FIFO queue – Wait-free – Linearizable Art of Multiprocessor Programming
Grand Challenge
26 Grand Challenge • Implement a FIFO queue – Wait-free – Linearizable – From atomic read-write registers Art of Multiprocessor Programming
Grand Challenge
27 Grand Challenge • Implement a FIFO queue – Wait-free – Linearizable – From atomic read-write registers – Multiple dequeuers Art of Multiprocessor Programming
Grand Challenge
28 Grand Challenge • Implement a FIFO queue – Wait-free – Linearizable – From atomic read-write registers – Multiple dequeuers Only new aspect Art of Multiprocessor Programming
Puzzle
29 Puzzle Art of Multiprocessor Programming While you are ruminating on the grand challenge … We will give you another puzzle … Consensus!
Consensus: Each Thread has a Private Input
Art of Multiprocessor Programming 30 Consensus: Each Thread has a Private Input 32 19 21
They Communicate
31 They Communicate Art of Multiprocessor Programming
They Agree on One Thread’s Input
Art of Multiprocessor Programming 32 They Agree on One Thread’s Input 19 19 19
Formally: Consensus
33 Formally: Consensus • Consistent: – all threads decide the same value Art of Multiprocessor Programming
Formally: Consensus
34 Formally: Consensus • Consistent: – all threads decide the same value • Valid: – the common decision value is some thread's input Art of Multiprocessor Programming
No Wait-Free Implementation of Consensus using Registers
Art of Multiprocessor Programming 35 No Wait-Free Implementation of Consensus using Registers ??? ???
Formally
36 Formally • Theorem – There is no wait-free implementation of n -thread consensus from read-write registers Art of Multiprocessor Programming
Formally
37 Formally • Theorem – There is no wait-free implementation of n -thread consensus from read-write registers • Implication – Asynchronous computability different from Turing computability Art of Multiprocessor Programming
Proof Strategy
Proof Strategy 38 Art of Multiprocessor Programming Assume otherwise … Reason about the properties of any such protocol … Derive a contradiction uod Q E rat D emonstrandum Enough to consider binary consensus and n =2
Protocol Histories as State Transitions
Art of Multiprocessor Programming 39 Protocol Histories as State Transitions time x.read() y.read() y.read(y ) x.write() time A B init state final state
Wait-Free Computation
Art of Multiprocessor Programming 40 Wait-Free Computation • Either A or B “moves” • Moving means – Register read – Register write A moves B moves
The Two-Move Tree
Art of Multiprocessor Programming 41 The Two-Move Tree Initial state Final states
Decision Values
Art of Multiprocessor Programming 42 Decision Values 1 0 0 1 1 1
Bivalent: Both Possible
43 Bivalent: Both Possible 1 1 1 bivalent 1 0 0 Art of Multiprocessor Programming
Univalent: Single Value Possible
44 Univalent: Single Value Possible 1 1 1 univalent 1 0 0 Art of Multiprocessor Programming
x-valent: x Only Possible Decision
45 x-valent: x Only Possible Decision 0 1 1 1 1-valent 0 1 Art of Multiprocessor Programming
Summary
46 Summary • Wait-free computation is a tree Art of Multiprocessor Programming
Summary
47 Summary • Wait-free computation is a tree • Bivalent system states – Outcome not fixed Art of Multiprocessor Programming
Summary
48 Summary • Wait-free computation is a tree • Bivalent system states – Outcome not fixed • Univalent states – Outcome is fixed – May not be “known” yet Art of Multiprocessor Programming
Summary
49 Summary • Wait-free computation is a tree • Bivalent system states – Outcome not fixed • Univalent states – Outcome is fixed – May not be “known” yet • 1 -Valent and 0 -Valent states Art of Multiprocessor Programming
Claim
50 Claim • Some initial state is bivalent Art of Multiprocessor Programming
Claim
51 Claim • Some initial state is bivalent • Outcome depends on – Chance – Whim of the scheduler Art of Multiprocessor Programming
Claim
52 Claim • Some initial state is bivalent • Outcome depends on – Chance – Whim of the scheduler • Multicore gods procrastinate … Art of Multiprocessor Programming
Claim
53 Claim • Some initial state is bivalent • Outcome depends on – Chance – Whim of the scheduler • Multicore gods procrastinate … • Let’s prove it … Art of Multiprocessor Programming
What if inputs differ?
Art of Multiprocessor Programming 54 What if inputs differ? 1 0
Must Decide 0
Art of Multiprocessor Programming 55 Must Decide 0 In this solo execution by A 0
Must Decide 1
Art of Multiprocessor Programming 56 Must Decide 1 1 In this solo execution by B
Mixed Initial State Bivalent
Art of Multiprocessor Programming 57 Mixed Initial State Bivalent • Solo execution by A must decide 0 • Solo execution by B must decide 1 0 1
Critical States
Art of Multiprocessor Programming 58 0-valent Critical States 1-valent critical
From a Critical State
Art of Multiprocessor Programming 59 From a Critical State c If A goes first, protocol decides 0 If B goes first, protocol decides 1 0-valent 1-valent
Reaching Critical State
60 Reaching Critical State C A C A C B c C B univalent univalent univalent univalent 0-valent 1-valent initially bivalent
Critical States
61 Critical States • Starting from a bivalent initial state Art of Multiprocessor Programming
Critical States
62 Critical States • Starting from a bivalent initial state • The protocol can reach a critical state Art of Multiprocessor Programming
Critical States
63 Critical States • Starting from a bivalent initial state • The protocol can reach a critical state – Otherwise we could stay bivalent forever – And the protocol is not wait-free Art of Multiprocessor Programming
Model Dependency
64 Model Dependency • So far, memory-independent! • True for – Registers – Message-passing – Carrier pigeons – Any kind of asynchronous computation Art of Multiprocessor Programming
Closing the Deal
Closing the Deal • Start from a critical state Art of Multiprocessor Programming
Closing the Deal
Closing the Deal • Start from a critical state • Each thread fixes outcome by – Reading or writing … – Same or different registers Art of Multiprocessor Programming
Closing the Deal
Closing the Deal • Start from a critical state • Each thread fixes outcome by – Reading or writing … – Same or different registers • Leading to a 0 or 1 decision … Art of Multiprocessor Programming
Closing the Deal
Closing the Deal • Start from a critical state • Each thread fixes outcome by – Reading or writing … – Same or different registers • Leading to a 0 or 1 decision … • And a contradiction. Art of Multiprocessor Programming
Possible Interactions
69 Possible Interactions x.read() y.read() x.write() y.write() x.read() ? ? ? ? y.read() ? ? ? ? x.write() ? ? ? ? y.write() ? ? ? ? Art of Multiprocessor Programming
Possible Interactions
70 Possible Interactions x.read() y.read() x.write() y.write() x.read() ? ? ? ? y.read() ? ? ? ? x.write() ? ? ? ? y.write() ? ? ? ? A reads x Art of Multiprocessor Programming
Possible Interactions
71 Possible Interactions x.read() y.read() x.write() y.write() x.read() ? ? ? ? y.read() ? ? ? ? x.write() ? ? ? ? y.write() ? ? ? ? A reads x A reads y Art of Multiprocessor Programming
Some Thread Reads
72 Some Thread Reads c Art of Multiprocessor Programming
Some Thread Reads
73 Some Thread Reads A runs solo, eventually decides 0 0 c Art of Multiprocessor Programming
Some Thread Reads
74 Some Thread Reads A runs solo, eventually decides 0 B reads x 0 c Art of Multiprocessor Programming
Some Thread Reads
75 Some Thread Reads A runs solo, eventually decides 0 B reads x 1 0 A runs solo, eventually decides 1 c Art of Multiprocessor Programming
Some Thread Reads
76 Some Thread Reads A runs solo, eventually decides 0 B reads x 1 0 A runs solo, eventually decides 1 c States look the same to A Art of Multiprocessor Programming
Some Thread Reads
77 Some Thread Reads A runs solo, eventually decides 0 B reads x 1 0 A runs solo, eventually decides 1 c States look the same to A Contradiction Art of Multiprocessor Programming
Possible Interactions
78 Possible Interactions x.read() y.read() x.write() y.write() x.read() no no no no y.read() no no no no x.write() no no ? ? y.write() no no ? ? Art of Multiprocessor Programming
Writing Distinct Registers
Art of Multiprocessor Programming 79 Writing Distinct Registers c
Writing Distinct Registers
80 Writing Distinct Registers A writes y c Art of Multiprocessor Programming
Writing Distinct Registers
81 Writing Distinct Registers A writes y c B writes x Art of Multiprocessor Programming
Writing Distinct Registers
82 Writing Distinct Registers A writes y c B writes x 0 Art of Multiprocessor Programming
Writing Distinct Registers
83 Writing Distinct Registers A writes y B writes x c B writes x 0 Art of Multiprocessor Programming
Writing Distinct Registers
Art of Multiprocessor Programming 84 Writing Distinct Registers A writes y B writes x c A writes y B writes x 0
Writing Distinct Registers
Art of Multiprocessor Programming 85 Writing Distinct Registers A writes y B writes x c A writes y B writes x 0 1
Writing Distinct Registers
86 Writing Distinct Registers A writes y B writes x c Same story A writes y B writes x 0 1
Writing Distinct Registers
87 Writing Distinct Registers A writes y B writes x c Same story A writes y B writes x 0 1 Contradiction
Possible Interactions
Art of Multiprocessor Programming 88 Possible Interactions x.read() y.read() x.write() y.write() x.read() no no no no y.read() no no no no x.write() no no ? no y.write() no no no ?
Writing Same Registers
Art of Multiprocessor Programming 89 Writing Same Registers States look the same to A A writes x B writes x 1 A runs solo, eventually decides 1 c 0 A runs solo, eventually decides 0 A writes x Contradiction
That’s All, Folks!
Art of Multiprocessor Programming 90 That’s All, Folks! x.read() y.read() x.write() y.write() x.read() no no no no y.read() no no no no x.write() no no no no y.write() no no no no QED
Recap: Atomic Registers Can’t Do Consensus
Art of Multiprocessor Programming 91 Recap: Atomic Registers Can’t Do Consensus • If protocol exists – It has a bivalent initial state – Leading to a critical state • What’s up with the critical state? – Case analysis for each pair of methods – As we showed, all lead to a contradiction
What Does Consensus have to do with Concurrent Objects?
Art of Multiprocessor Programming 92 What Does Consensus have to do with Concurrent Objects?
Consensus Object
Art of Multiprocessor Programming 93 Consensus Object public interface Consensus<T> { T decide(T value); }
Concurrent Consensus Object
Art of Multiprocessor Programming 94 Concurrent Consensus Object • We consider only one time objects: – each thread calls method only once • Linearizable to consensus object: – Winner’s call went first
Java Jargon Watch
Art of Multiprocessor Programming 95 Java Jargon Watch • Define Consensus protocol as an abstract class • We implement some methods • You do the rest …
Generic Consensus Protocol
Art of Multiprocessor Programming 96 Generic Consensus Protocol abstract class ConsensusProtocol<T> implements Consensus<T> { protected T[] proposed = new T[N]; protected void propose(T value) { proposed[ThreadID.get()] = value; } abstract public T decide(T value); }
Generic Consensus Protocol
Art of Multiprocessor Programming 97 abstract class ConsensusProtocol<T> implements Consensus<T> { protected T[] proposed = new T[N]; protected void propose(T value) { proposed[ThreadID.get()] = value; } abstract public T decide(T value); } Generic Consensus Protocol Each thread’s proposed value
Generic Consensus Protocol
Art of Multiprocessor Programming 98 abstract class ConsensusProtocol<T> implements Consensus<T> { protected T[] proposed = new T[N]; protected void propose(T value) { proposed[ThreadID.get()] = value; } abstract public T decide(T value); } Generic Consensus Protocol Propose a value
Generic Consensus Protocol
Art of Multiprocessor Programming 99 abstract class ConsensusProtocol<T> implements Consensus { protected T[] proposed = new T[N]; protected void propose(T value) { proposed[ThreadID.get()] = value; } abstract public T decide(T value); } Generic Consensus Protocol Decide a value: abstract method means subclass does the real work
Art of Multiprocessor Programming 100 Can a FIFO Queue Implement Consensus?
FIFO Consensus
Art of Multiprocessor Programming 101 FIFO Consensus proposed array FIFO Queue with red and black balls 8 Coveted red ball Dreaded black ball
Protocol: Write Value to Array
Art of Multiprocessor Programming 102 Protocol: Write Value to Array 0 1 0
Protocol: Take Next Item from Queue
Art of Multiprocessor Programming 103 0 Protocol: Take Next Item from Queue 0 1 8
Protocol: Take Next Item from Queue
Art of Multiprocessor Programming 104 0 1 Protocol: Take Next Item from Queue I got the coveted red ball, so I will decide my value I got the dreaded black ball, so I will decide the other’s value from the array 8
Consensus Using FIFO Queue
Art of Multiprocessor Programming 105 public class QueueConsensus<T> extends ConsensusProtocol<T> { private Queue queue; public QueueConsensus() { queue = new Queue(); queue.enq(Ball.RED); queue.enq(Ball.BLACK); } … } Consensus Using FIFO Queue
Initialize Queue
Art of Multiprocessor Programming 106 public class QueueConsensus extends ConsensusProtocol { private Queue queue; public QueueConsensus() { this .queue = new Queue(); this .queue.enq(Ball.RED); this .queue.enq(Ball.BLACK); } … } Initialize Queue 8
Who Won?
Art of Multiprocessor Programming 107 public class QueueConsensus<T> extends ConsensusProtocol<T> { private Queue queue; … public T decide(T value) { propose(value); Ball ball = queue.deq(); if (ball == Ball.RED) return proposed[i]; else return proposed[1-i]; } } Who Won?
Who Won?
Art of Multiprocessor Programming 108 public class QueueConsensus<T> extends ConsensusProtocol<T> { private Queue queue; … public T decide(T value) { propose(value); Ball ball = queue.deq(); if (ball == Ball.RED) return proposed[i]; else return proposed[1-ij]; } } Who Won? Race to dequeue first queue item
Who Won?
Art of Multiprocessor Programming 109 public class QueueConsensus<T> extends ConsensusProtocol<T> { private Queue queue; … public T decide(T value) { propose(value); Ball ball = this.queue.deq(); if (ball == Ball.RED) return proposed[i]; else return proposed[1-i]; } } Who Won? I win if I was first
Who Won?
Art of Multiprocessor Programming 110 public class QueueConsensus<T> extends ConsensusProtocol<T> { private Queue queue; … public T decide(T value) { propose(value); Ball ball = this.queue.deq(); if (ball == Ball.RED) return proposed[i]; else return proposed[1-i]; } } Who Won? Other thread wins if I was second
Why does this Work?
111 Why does this Work? • If one thread gets the red ball • Then the other gets the black ball • Winner decides her own value • Loser can find winner’s value in array – Because threads write array – Before dequeueing from queue Art of Multiprocessor Programming
Theorem
112 Theorem • We can solve 2 -thread consensus using only – A two-dequeuer queue, and – Some atomic registers Art of Multiprocessor Programming
Implications
Art of Multiprocessor Programming 113 Implications • Given – A consensus protocol from queue and registers • Assume there exists – A queue implementation from atomic registers • Substitution yields: – A wait-free consensus protocol from atomic registers contradiction
Corollary
114 Corollary • It is impossible to implement – a two-dequeuer wait-free FIFO queue – from read/write memory. Art of Multiprocessor Programming
Consensus Numbers
115 Consensus Numbers • An object X has consensus number n – If it can be used to solve n -thread consensus • Take any number of instances of X • together with atomic read/write registers • and implement n -thread consensus – But not ( n +1) -thread consensus Art of Multiprocessor Programming
Consensus Numbers
116 Consensus Numbers • Theorem – Atomic read/write registers have consensus number 1 • Theorem – Multi-dequeuer FIFO queues have consensus number at least 2 Art of Multiprocessor Programming
Consensus Numbers Measure Synchronization Power
117 Consensus Numbers Measure Synchronization Power • Theorem – If you can implement X from Y – And X has consensus number c – Then Y has consensus number at least c Art of Multiprocessor Programming
Synchronization Speed Limit
Art of Multiprocessor Programming 118 Synchronization Speed Limit • Conversely – If X has consensus number c – And Y has consensus number d < c – Then there is no way to construct a wait- free implementation of X by Y • This theorem will be very useful – Unforeseen practical implications! Theoretical Caveat: Certain weird exceptions exist
Earlier Grand Challenge
119 Earlier Grand Challenge • Snapshot means – Write any array element – Read multiple array elements atomically • What about – Write multiple array elements atomically – Scan any array elements • Call this problem multiple assignment Art of Multiprocessor Programming
Multiple Assignment Theorem
Art of Multiprocessor Programming 120 Multiple Assignment Theorem • Atomic registers cannot implement multiple assignment • Weird or what? – Single write/multi read OK – Multi write/multi read impossible
Proof Strategy
Art of Multiprocessor Programming 121 Proof Strategy • If we can write to 2/3 array elements – We can solve 2 -consensus – Impossible with atomic registers • Therefore – Cannot implement multiple assignment with atomic registers (1)
Proof Strategy
Art of Multiprocessor Programming 122 Proof Strategy • Take a 3 -element array – A writes atomically to slots 0 and 1 – B writes atomically to slots 1 and 2 – Any thread can scan any set of locations
Initially
Art of Multiprocessor Programming 126 Initially Writes to 0 and 1 Writes to 1 and 2 A B
Thread A wins if
Art of Multiprocessor Programming 127 Thread A wins if A B Thread B didn’t move
Thread A wins if
Art of Multiprocessor Programming 128 Thread A wins if A B Thread B moved later
Thread A loses if
Art of Multiprocessor Programming 129 Thread A loses if A B Thread B moved earlier
Summary
139 Summary • If a thread can assign atomically to 2 out of 3 array locations • Then we can solve 2 -consensus • Therefore – No wait-free multi-assignment – From read/write registers Art of Multiprocessor Programming
Read-Modify-Write Objects
140 Read-Modify-Write Objects • Method call – Returns object’s prior value x – Replaces x with mumble (x) Art of Multiprocessor Programming
Read-Modify-Write
141 public abstract class RMWRegister { private int value; public int synchronized getAndMumble() { int prior = value; value = mumble(value); return prior; } } Read-Modify-Write Art of Multiprocessor Programming
Read-Modify-Write
Art of Multiprocessor Programming 142 public abstract class RMWRegister { private int value; public int synchronized getAndMumble() { int prior = value; value = mumble(value); return prior; } } Read-Modify-Write Return prior value
Read-Modify-Write
Art of Multiprocessor Programming 143 public abstract class RMWRegister { private int value; public int synchronized getAndMumble() { int prior = value; value = mumble(value); return prior; } } Read-Modify-Write Apply function to current value
RMW Everywhere!
144 RMW Everywhere! • Most synchronization instructions – are RMW methods • The rest – Can be trivially transformed into RMW methods Art of Multiprocessor Programming
Example: Read
145 public abstract class RMWRegister { private int value; public int synchronized read() { int prior = value ; value = value ; return prior; } } Example: Read Art of Multiprocessor Programming
Example: Read
Art of Multiprocessor Programming 146 public abstract class RMW { private int value; public int synchronized read() { int prior = this.value; value = value ; return prior; } } Example: Read apply f(v)=v , the identity function
Example: getAndSet
147 public abstract class RMWRegister { private int value; public int synchronized getAndSet( int v) { int prior = value ; value = v; return prior; } … } Example: getAndSet Art of Multiprocessor Programming
Example: getAndSet (swap)
Art of Multiprocessor Programming 148 public abstract class RMWRegister { private int value; public int synchronized getAndSet(int v) { int prior = value ; value = v; return prior; } … } Example: getAndSet (swap) f(x )=v is constant
getAndIncrement
149 public abstract class RMWRegister { private int value; public int synchronized getAndIncrement() { int prior = value ; value = value + 1; return prior; } … } getAndIncrement Art of Multiprocessor Programming
getAndIncrement
Art of Multiprocessor Programming 150 public abstract class RMWRegister { private int value; public int synchronized getAndIncrement() { int prior = value ; value = value + 1; return prior; } … } getAndIncrement f(x ) = x+1
getAndAdd
151 public abstract class RMWRegister { private int value; public int synchronized getAndAdd( int a) { int prior = value ; value = value + a; return prior; } … } getAndAdd Art of Multiprocessor Programming
Example: getAndAdd
Art of Multiprocessor Programming 152 public abstract class RMWRegister { private int value; public int synchronized getAndIncrement(int a) { int prior = value ; value = value + a; return prior; } … } Example: getAndAdd f(x ) = x+a
compareAndSet
153 public abstract class RMWRegister { private int value; public boolean synchronized compareAndSet( int expected, int update) { int prior = value ; if (value ==expected) { value = update; return true ; } return false ; } … } compareAndSet Art of Multiprocessor Programming
compareAndSet
Art of Multiprocessor Programming 154 public abstract class RMWRegister { private int value; public boolean synchronized compareAndSet(int expected , int update) { int prior = value ; if ( value ==expected ) { value = update; return true; } return false; } … } compareAndSet If value is as expected , …
compareAndSet
Art of Multiprocessor Programming 155 public abstract class RMWRegister { private int value; public boolean synchronized compareAndSet(int expected, int update ) { int prior = value ; if (value ==expected) { value = update; return true; } return false; } … } compareAndSet … replace it
compareAndSet
Art of Multiprocessor Programming 156 public abstract class RMWRegister { private int value; public boolean synchronized compareAndSet(int expected, int update) { int prior = value ; if (value ==expected) { value = update; return true ; } return false; } … } compareAndSet Report success
compareAndSet
Art of Multiprocessor Programming 157 public abstract class RMWRegister { private int value; public boolean synchronized compareAndSet(int expected, int update) { int prior = value ; if (value ==expected) { value = update; return true; } return false ; } … } compareAndSet Otherwise report failure
Read-Modify-Write
Art of Multiprocessor Programming 158 public abstract class RMWRegister { private int value; public void synchronized getAndMumble() { int prior = value; value = mumble(value); return prior; } } Read-Modify-Write Lets characterize f(x )…
Definition
159 Definition • A RMW method – With function mumble(x) – is non-trivial if there exists a value v – Such that v ≠ mumble(v) Art of Multiprocessor Programming
Par Example
160 Par Example • Identity(x) = x – is trivial • getAndIncrement(x) = x+1 – is non-trivial Art of Multiprocessor Programming
Theorem
161 Theorem • Any non-trivial RMW object has consensus number at least 2 • No wait-free implementation of RMW registers from atomic registers • Hardware RMW instructions not just a convenience Art of Multiprocessor Programming
Reminder
162 Reminder • Subclasses of consensus have – propose(x) method • which just stores x into proposed[i] • built-in method – decide(object value) method • which determines winning value • customized, class-specific method Art of Multiprocessor Programming
Proof
163 Proof public class RMWConsensus extends ConsensusProtocol { private RMWRegister r = v; public T d ecide(T value) { propose(value); if (r.getAndMumble() == v) return proposed[i]; else return proposed[j]; }} Art of Multiprocessor Programming
Proof
Art of Multiprocessor Programming 164 public class RMWConsensus extends ConsensusProtocol { private RMWRegister r = v; public T decide(T value) { propose(value); if (r.getAndMumble() == v) return proposed[i]; else return proposed[j]; }} Proof Initialized to v
Proof
Art of Multiprocessor Programming 165 Proof public class RMWConsensus extends Consensus { private RMWRegister r = v; public T decide(T value) { propose(value); if (r.getAndMumble() == v) return proposed[i]; else return proposed[j]; }} Am I first?
Proof
Art of Multiprocessor Programming 166 public class RMWConsensus extends ConsensusProtocol { private RMWRegister r = v; public T decide(T value) { propose(value); if (r.getAndMumble() == v) return proposed[i]; else return proposed[j]; }} Proof Yes, return my input
Proof
Art of Multiprocessor Programming 167 public class RMWConsensus extends ConsensusProtocol { private RMWRegister r = v; public T decide(T value) { propose(value); if (r.getAndMumble() == v) return proposed[i]; else return proposed[j]; }} Proof No, return other’s input
Proof
168 Proof • We have displayed – A two-thread consensus protocol – Using any non-trivial RMW object Art of Multiprocessor Programming
Interfering RMW
169 Interfering RMW • Let F be a set of functions such that for all f i and f j , either – Commute: f i (f j (v))=f j (f i (v)) – Overwrite: f i (f j (v))=f i (v) • Claim: Any set of RMW objects that commutes or overwrites has consensus number exactly 2 Art of Multiprocessor Programming
Examples
Art of Multiprocessor Programming 170 Examples • “test-and-set” getAndSet(1) f(v)=1 • “swap” getAndSet(x) f(v,x)=x • “fetch-and-inc” getAndIncrement() f(v)=v+1 Overwrite f i (f j (v))=f i (v) Overwrite f i (f j (v))=f i (v) Commute f i (f j (v))= f j (f i (v))
Meanwhile Back at the Critical State
Art of Multiprocessor Programming 171 Meanwhile Back at the Critical State c 0-valent 1-valent A about to apply f A B about to apply f B
Maybe the Functions Commute
Art of Multiprocessor Programming 172 Maybe the Functions Commute c 0-valent A applies f A B applies f B A applies f A B applies f B 0 1 C runs solo C runs solo 1-valent
Maybe the Functions Commute
173 Maybe the Functions Commute c 0-valent A applies f A B applies f B A applies f A B applies f B 0 1 C runs solo C runs solo 1-valent These states look the same to C Contradiction Art of Multiprocessor Programming
Maybe the Functions Overwrite
Art of Multiprocessor Programming 174 Maybe the Functions Overwrite c 0-valent A applies f A B applies f B A applies f A 0 1 C runs solo C runs solo 1-valent
Maybe the Functions Overwrite
Art of Multiprocessor Programming 175 Maybe the Functions Overwrite c 0-valent A applies f A B applies f B A applies f A 0 1 C runs solo C runs solo 1-valent These states look the same to C Contradiction
Impact
176 Impact • Many early machines provided these “weak” RMW instructions – Test-and-set (IBM 360) – Fetch-and-add (NYU Ultracomputer) – Swap (Original SPARCs) • We now understand their limitations – But why do we want consensus anyway? Art of Multiprocessor Programming
compareAndSet
177 public abstract class RMWRegister { private int value; public boolean synchronized compareAndSet( int expected, int update) { int prior = value ; if (value ==expected) { value = update; return true ; } return false ; } … } compareAndSet Art of Multiprocessor Programming
compareAndSet
Art of Multiprocessor Programming 178 public abstract class RMWRegister { private int value; public boolean synchronized compareAndSet(int expected, int update) { int prior = this.value; if ( value ==expected ) { this.value = update; return true; } return false; } … } compareAndSet replace value if it’s what we expected, …
compareAndSet Has ∞ Consensus Number
Art of Multiprocessor Programming 179 public class RMWConsensus extends ConsensusProtocol { private AtomicInteger r = new AtomicInteger(-1); public T decide(T value) { propose(value); r.compareAndSet(-1,i); return proposed[r.get()]; } } compareAndSet Has ∞ Consensus Number
compareAndSet Has ∞ Consensus Number
Art of Multiprocessor Programming 180 public class RMWConsensus extends ConsensusProtocol { private AtomicInteger r = new AtomicInteger(-1); public T decide(T value) { propose(value) r.compareAndSet(-1,i); return proposed[r.get()]; } } compareAndSet Has ∞ Consensus Number Initialized to -1
compareAndSet Has ∞ Consensus Number
Art of Multiprocessor Programming 181 public class RMWConsensus extends ConsensusProtocol { private AtomicInteger r = new AtomicInteger(-1); public T decide(T value) { propose(value); r.compareAndSet(-1,i); return proposed[r.get()]; } } compareAndSet Has ∞ Consensus Number Try to swap in my id
compareAndSet Has ∞ Consensus Number
Art of Multiprocessor Programming 182 public class RMWConsensus extends ConsensusProtocol { private AtomicInteger r = new AtomicInteger(-1); public T decide(T value) { propose(value); r.compareAndSet(-1,i); return proposed[r.get()]; } } compareAndSet Has ∞ Consensus Number Decide winner’s preference
The Consensus Hierarchy
Art of Multiprocessor Programming 183 The Consensus Hierarchy 1 Read/Write Registers, Snapshots… 2 getAndSet, getAndIncrement, … ∞ compareAndSet,… . . .
Multiple Assignment
184 Multiple Assignment • Atomic k -assignment • Solves consensus for 2 k -2 threads • Every even consensus number has an object (can be extended to odd numbers) Art of Multiprocessor Programming
Lock-Freedom
185 Lock-Freedom • Lock-free: – in an infinite execution – infinitely often some method call finishes • Pragmatic approach • Implies no mutual exclusion Art of Multiprocessor Programming
Lock-Free vs. Wait-free
186 Lock-Free vs. Wait-free • Wait-Free: each method call takes a finite number of steps to finish • Lock-free: infinitely often some method call finishes Art of Multiprocessor Programming
Lock-Freedom
187 Lock-Freedom • Any wait-free implementation is lock-free . • Lock-free is the same as wait- free if the execution is finite. Art of Multiprocessor Programming
Lock-Free Implementations
188 Lock-Free Implementations • Lock-free consensus is as impossible as wait-free consensus • All these results hold for lock-free algorithms also. Art of Multiprocessor Programming
There is More: Universality
Art of Multiprocessor Programming 189 There is More: Universality • Consensus is universal • From n -thread consensus – Wait-free/Lock-free – Linearizable – n -threaded – Implementation – Of any sequentially specified object Stay tuned…
Art of Multiprocessor Programming 190   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.