Universality of Consensus
Universality of Consensus Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit
Turing Computability
Turing Computability • A mathematical model of computation • Computable = Computable on a T-Machine 0 1 1 0 1 0 1 2 Art of Multiprocessor Programming
Shared-Memory Computability • Model of asynchronous concurrent computation • Computable = Wait-free/Lock-free computable on a multiprocessor cache shared memory cache cache 3 Art of Multiprocessor Programming
Consensus Hierarchy
Consensus Hierarchy 1 Read/Write Registers, Snapshots… 2 getAndSet, getAndIncrement, … ∞ compareAndSet,… . . . 4 Art of Multiprocessor Programming
Who Implements Whom?
Who Implements Whom? 1 Read/Write Registers, Snapshots… 2 getAndSet, getAndIncrement, … ∞ compareAndSet,… . . . no no no 5 Art of Multiprocessor Programming
Hypothesis
Hypothesis 1 Read/Write Registers, Snapshots… 2 getAndSet, getAndIncrement, … ∞ compareAndSet,… . . . yes? yes? yes? 6 Art of Multiprocessor Programming
Theorem: Universality
Theorem: Universality • Consensus is universal • From n -thread consensus build a – Wait-free – Linearizable – n -threaded implementation – Of any sequentially specified object 7 Art of Multiprocessor Programming
Proof Outline
Proof Outline • A universal construction – From n -consensus objects – And atomic registers • Any wait-free linearizable object – Not a practical construction – But we know where to start looking … 8 Art of Multiprocessor Programming
Like a Turing Machine
Like a Turing Machine • This construction – Illustrates what needs to be done – Optimization fodder • Correctness, not efficiency – Why does it work? (Asks the scientist) – How does it work? (Asks the engineer) – Would you like fries with that? (Asks the liberal arts major) 9 Art of Multiprocessor Programming
A Generic Sequential Object
A Generic Sequential Object public interface SeqObject { public abstract Response apply(Invocation invoc); } 10 Art of Multiprocessor Programming
A Generic Sequential Object
A Generic Sequential Object public interface SeqObject { public abstract Response apply (Invocation invoc); } Push:5, Pop:null 11 Art of Multiprocessor Programming
Invocation
Invocation public class Invoc { public String method; public Object[] args; } 12 Art of Multiprocessor Programming
Invocation
Invocation public class Invoc { public String method; public Object[] args; } Method name 13 Art of Multiprocessor Programming
Invocation
Invocation public class Invoc { public String method; public Object[] args; } Arguments 14 Art of Multiprocessor Programming
A Generic Sequential Object
A Generic Sequential Object public interface SeqObject { public abstract Response apply(Invocation invoc); } 15 Art of Multiprocessor Programming
A Generic Sequential Object
A Generic Sequential Object public interface SeqObject { public abstract Response apply(Invocation invoc); } OK, 4 16 Art of Multiprocessor Programming
Response
Response public class Response { public Object value; } 17 Art of Multiprocessor Programming
Response
Response public class Response { public Object value; } Return value 18 Art of Multiprocessor Programming
Universal Concurrent Object
19 Universal Concurrent Object public interface SeqObject { public abstract Response apply(Invocation invoc); } A universal concurrent object is linearizable to the generic sequential object 19 Art of Multiprocessor Programming
Start with Lock-Free Universal Construction
Start with Lock-Free Universal Construction • First Lock-free: infinitely often some method call finishes. • Then Wait-Free: each method call takes a finite number of steps to finish 20 Art of Multiprocessor Programming
Naïve Idea
Naïve Idea • Consensus object stores reference to cell with current state • Each thread creates new cell – computes outcome, – tries to switch pointer to its outcome • Sadly, no … – consensus objects can be used once only 21 Art of Multiprocessor Programming
Naïve Idea
Naïve Idea enq deq 22 Art of Multiprocessor Programming
Naïve Idea
head Naïve Idea deq Concurrent Object ? enq Decide which to apply using consensus 23 Art of Multiprocessor Programming No good. Each thread can use consensus object only once
Once is not Enough?
Once is not Enough? public T decide(T value) { propose(value); Ball ball = queue.deq(); if (ball == Ball.RED) return proposed[i]; else return proposed[1-i]; } Solved one-shot 2-consensus. Not clear how to reuse or reread … Queue based consensus 24 Art of Multiprocessor Programming
Improved Idea: Linked-List Representation
Improved Idea: Linked-List Representation enq enq enq tail deq Each node contains a fresh consensus object used to decide on next operation 25 Art of Multiprocessor Programming
Universal Construction
Universal Construction • Object represented as – Initial Object State – A Log: a linked list of the method calls 26 Art of Multiprocessor Programming
Universal Construction
Universal Construction • Object represented as – Initial Object State – A Log: a linked list of the method calls • New method call – Find end of list – Atomically append call – Compute response by replaying log 27 Art of Multiprocessor Programming
Basic Idea
Basic Idea • Use one-time consensus object to decide next pointer 28 Art of Multiprocessor Programming
Basic Idea
Basic Idea • Use one-time consensus object to decide next pointer • All threads update actual next pointer based on decision – OK because they all write the same value 29 Art of Multiprocessor Programming
Basic Idea
Basic Idea • Threads use one-time consensus object to decide which node goes next • Threads update actual next field to reflect consensus outcome – OK because they all write the same value • Challenges – Lock-free means we need to worry what happens if a thread stops in the middle 30 Art of Multiprocessor Programming
Basic Data Structures
public class Node implements java.lang.Comparable { public Invoc invoc; public Consensus<Node> decideNext; public Node next; public int seq; public Node(Invoc invoc) { invoc = invoc; decideNext = new Consensus<Node>() seq = 0; } Basic Data Structures 31 Art of Multiprocessor Programming
Basic Data Structures
public class Node implements java.lang.Comparable { public Invoc invoc; public Consensus<Node> decideNext; public Node next; public int seq; public Node(Invoc invoc) { invoc = invoc; decideNext = new Consensus<Node>() seq = 0; } Basic Data Structures Standard interface for class whose objects are totally ordered 32 Art of Multiprocessor Programming
Basic Data Structures
public class Node implements java.lang.Comparable { public Invoc invoc; public Consensus<Node> decideNext; public Node next; public int seq; public Node(Invoc invoc) { invoc = invoc; decideNext = new Consensus<Node>() seq = 0; } Basic Data Structures the invocation 33 Art of Multiprocessor Programming
Basic Data Structures
public class Node implements java.lang.Comparable { public Invoc invoc; public Consensus<Node> decideNext; public Node next; public int seq; public Node(Invoc invoc) { invoc = invoc; decideNext = new Consensus<Node>() seq = 0; } Basic Data Structures Decide on next node (next method applied to object) 34 Art of Multiprocessor Programming
Basic Data Structures
public class Node implements java.lang.Comparable { public Invoc invoc; public Consensus<Node> decideNext; public Node next; public int seq; public Node(Invoc invoc) { invoc = invoc; decideNext = new Consensus<Node>() seq = 0; } Basic Data Structures Traversable pointer to next node (needed because you cannot repeatedly read a consensus object) 35 Art of Multiprocessor Programming
Basic Data Structures
public class Node implements java.lang.Comparable { public Invoc invoc; public Consensus<Node> decideNext; public Node next; public int seq; public Node(Invoc invoc) { invoc = invoc; decideNext = new Consensus<Node>() seq = 0; } Basic Data Structures Seq number 36 Art of Multiprocessor Programming
Basic Data Structures
public class Node implements java.lang.Comparable { public Invoc invoc; public Consensus<Node> decideNext; public Node next; public int seq; public Node(Invoc invoc) { invoc = invoc; decideNext = new Consensus<Node>() seq = 0; } Basic Data Structures Create new node for this method invocation 37 Art of Multiprocessor Programming
Universal Object
Universal Object head 1 2 3 decideNext (Consensus Object) Ptr to cell w/highest Seq Num Seq number, Invoc tail node next 4 38 Art of Multiprocessor Programming
Universal Object
Universal Object head 1 2 3 All threads repeatedly modify head…back to where we started? tail node 4 39 Art of Multiprocessor Programming
The Solution
… The Solution head 1 2 3 tail node i 4 Make head an array Ref dto node at front Thread i updates location i Fdind head by finding Max of nodes referenced by head array 40 Art of Multiprocessor Programming
Universal Object
Universal Object public class Universal { private Node[] head; private Node tail = new Node(); tail.seq = 1; for ( int j=0; j < n; j++){ head[j] = tail } 41 Art of Multiprocessor Programming
Universal Object
Universal Object public class Universal { private Node[] head; private Node tail = new Node(); tail.seq = 1; for (int j=0; j < n; j++){ head[j] = tail } Head Pointers Array 42 Art of Multiprocessor Programming
Universal Object
Universal Object public class Universal { private Node[] head; private Node tail = new Node(); tail.seq = 1; for (int j=0; j < n; j++){ head[j] = tail } Tail is a sentinel node with sequence number 1 43 Art of Multiprocessor Programming
Universal Object
Universal Object public class Universal { private Node[] head; private Node tail = new Node(); tail.seq = 1; for ( int j=0; j < n; j++){ head[j] = tail } Initially head points to tail 44 Art of Multiprocessor Programming
Find Max Head Value
public static Node max(Node[] array) { Node max = array[0]; for ( int i = 1; i < array.length; i++) if (max.seq < array[i].seq) max = array[i]; return max; } Find Max Head Value 45 Art of Multiprocessor Programming
Find Max Head Value
public static Node max(Node[] array) { Node max = array[0]; for ( int i = 0; i < array.length; i++) if (max.seq < array[i].seq) max = array[i]; return max; } Find Max Head Value Traverse the array 46 Art of Multiprocessor Programming
Find Max Head Value
public static Node max(Node[] array) { Node max = array[0]; for (int i = 0; i < array.length; i++) if (max.seq < array[i].seq) max = array[i]; return max; } Find Max Head Value Compare the seq nums of nodes pointed to by the array 47 Art of Multiprocessor Programming
Find Max Head Value
public static Node max(Node[] array) { Node max = array[0]; for (int i = 0; i < array.length; i++) if (max.seq < array[i].seq) max = array[i]; return max; } Find Max Head Value Return node with maximal sequence number 48 Art of Multiprocessor Programming
Universal Application Part I
Universal Application Part I public Response apply(Invoc invoc) { int i = ThreadID.get(); Node prefer = new node(invoc); while (prefer.seq == 0) { Node before = Node.max(head); Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } … 49 Art of Multiprocessor Programming
Universal Application Part I
Universal Application Part I public Response apply(Invoc invoc) { int i = ThreadID.get(); Node prefer = new node(invoc); while (prefer.seq == 0) { Node before = Node.max(head); Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } … Apply has invocation as input and returns the appropriate response 50 Art of Multiprocessor Programming
Universal Application Part I
Universal Application Part I public Response apply(Invoc invoc) { int i = ThreadID.get(); Node prefer = new node(invoc); while (prefer.seq == 0) { Node before = Node.max(head); Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } … my ID 51 Art of Multiprocessor Programming
Universal Application Part I
Universal Application Part I public Response apply(Invoc invoc) { int i = ThreadID.get(); Node prefer = new node(invoc); while (prefer.seq == 0) { Node before = Node.max(head); Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } … My method call 52 Art of Multiprocessor Programming
Universal Application Part I
Universal Application Part I public Response apply(Invoc invoc) { int i = ThreadID.get(); Node prefer = new node(invoc); while (prefer.seq == 0) { Node before = Node.max(head); Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } … As long as I have not been threaded into list 53 Art of Multiprocessor Programming
Universal Application Part I
Universal Application Part I public Response apply(Invoc invoc) { int i = ThreadID.get(); Node prefer = new node(invoc); while (prefer.seq == 0) { Node before = Node.max(head); Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } … Head of list to which we will try to append 54 Art of Multiprocessor Programming
Universal Application Part I
Universal Application Part I public Response apply(Invoc invoc) { int i = ThreadID.get(); Node prefer = new node(invoc); while (prefer.seq == 0) { Node before = Node.max(head); Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } } Propose next node 55 Art of Multiprocessor Programming
Universal Application
Universal Application public Response apply(Invoc invoc) { int i = ThreadID.get(); Node prefer = new node(invoc); while (prefer.seq == 0) { Node before = Node.max(head); Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } } Set next field to consensus winner 56 Art of Multiprocessor Programming
Universal Application Part I
Universal Application Part I public Response apply(Invoc invoc) { int i = ThreadID.get(); Node prefer = new node(invoc); while (prefer.seq == 0) { Node before = Node.max(head); Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } … Set seq number (indicating node was appended) 57 Art of Multiprocessor Programming
Universal Application Part I
Universal Application Part I public Response apply(Invoc invoc) { int i = ThreadID.get(); Node prefer = new node(invoc); while (prefer.seq == 0) { Node before = Node.max(head); Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } … add to head array so new head will be found 58 Art of Multiprocessor Programming
Part 2 – Compute Response
Part 2 – Compute Response null enq( ) tail Red’s method call … deq() enq( ) return Private copy of object 59 Art of Multiprocessor Programming
Universal Application Part 2
Universal Application Part 2 ... //compute my response SeqObject MyObject = new SeqObject(); current = tail.next; while (current != prefer){ MyObject.apply(current.invoc); current = current.next; } return MyObject.apply(current.invoc); } 60 Art of Multiprocessor Programming
Universal Application Part II
Universal Application Part II ... //compute my response SeqObject MyObject = new SeqObject(); current = tail.next; while (current != prefer){ MyObject.apply(current.invoc); current = current.next; } return MyObject.apply(current.invoc); } Compute result by sequentially applying method calls in list to a private copy 61 Art of Multiprocessor Programming
Universal Application Part II
Universal Application Part II ... //compute my response SeqObject MyObject = new SeqObject(); current = tail.next; while (current != prefer){ MyObject.apply(current.invoc); current = current.next; } return MyObject.apply(current.invoc); } Start with copy of sequential object 62 Art of Multiprocessor Programming
Universal Application Part II
Universal Application Part II ... //compute my response SeqObject MyObject = new SeqObject(); current = tail.next; while (current != prefer){ MyObject.apply(current.invoc); current = current.next; } return MyObject.apply(current.invoc); } new method call appended after tail 63 Art of Multiprocessor Programming
Universal Application Part II
Universal Application Part II ... //compute my response SeqObject MyObject = new SeqObject(); current = tail.next; while (current != prefer){ MyObject.apply(current.invoc); current = current.next; } return MyObject.apply(current.invoc); } While my method call not linked … 64 Art of Multiprocessor Programming
Universal Application Part II
Universal Application Part II ... //compute my response SeqObject MyObject = new SeqObject(); current = tail.next; while (current != prefer){ MyObject.apply(current.invoc); current = current.next; } return MyObject.apply(current.invoc); } Apply current node’s method 65 Art of Multiprocessor Programming
Universal Application Part II
Universal Application Part II ... //compute my response SeqObject MyObject = new SeqObject(); current = tail.next; while (current != prefer){ MyObject.apply(current.invoc); current = current.next; } return MyObject.apply(current.invoc); } Return result after my method call applied 66 Art of Multiprocessor Programming
Correctness
Correctness • List defines linearized sequential history • Thread returns its response based on list order 67 Art of Multiprocessor Programming
Lock-freedom
68 Lock-freedom • Lock-free because – A thread moves forward in list – Can repeatedly fail to win consensus on “real” head only if another succeeds – Consensus winner adds node and completes within a finite number of steps 68 Art of Multiprocessor Programming
Wait-free Construction
Wait-free Construction • Lock-free construction + announce array • Stores (pointer to) node in announce – If a thread doesn’t append its node – Another thread will see it in array and help append it 69 Art of Multiprocessor Programming
Helping
Helping • “Announcing” my intention – Guarantees progress – Even if the scheduler hates me – My method call will complete • Makes protocol wait-free • Otherwise starvation possible 70 Art of Multiprocessor Programming
Wait-free Construction
… … Wait-free Construction head 1 2 3 tail i 4 announce Ref to cell thread i wants to append i 71 Art of Multiprocessor Programming
The Announce Array
public class Universal { private Node[] announce; private Node[] head; private Node tail = new node(); tail.seq = 1; for ( int j=0; j < n; j++){ head[j] = tail; announce[j] = tail }; The Announce Array 72 Art of Multiprocessor Programming
The Announce Array
public class Universal { private Node[] announce; private Node[] head; private Node tail = new node(); tail.seq = 1; for (int j=0; j < n; j++){ head[j] = tail; announce[j] = tail }; The Announce Array New field: announce array 73 Art of Multiprocessor Programming
The Announce Array
public class Universal { private Node[] announce; private Node[] head; private Node tail = new node(); tail.seq = 1; for (int j=0; j < n; j++){ head[j] = tail; announce[j] = tail }; The Announce Array All entries initially point to tail 74 Art of Multiprocessor Programming
A Cry For Help
public Response apply(Invoc invoc) { int i = ThreadID.get(); announce[i] = new Node(invoc); head[i] = Node.max(head); while (announce[i].seq == 0) { … // while node not appended to list … } A Cry For Help 75 Art of Multiprocessor Programming
A Cry For Help
public Response apply(Invoc invoc) { int i = ThreadID.get(); announce[i] = new Node(invoc); head[i] = Node.max(head); while (announce[i].seq == 0) { … // while node not appended to list … } A Cry For Help Announce new method call, asking help from others 76 Art of Multiprocessor Programming
A Cry For Help
public Response apply(Invoc invoc) { int i = ThreadID.get(); announce[i] = new Node(invoc); head[i] = Node.max(head); while (announce[i].seq == 0) { … // while node not appended to list … } A Cry For Help Look for end of list 77 Art of Multiprocessor Programming
A Cry For Help
public Response apply(Invoc invoc) { int i = ThreadID.get(); announce[i] = new Node(invoc); head[i] = Node.max(head); while (announce[i].seq == 0) { … // while node not appended to list … } A Cry For Help Main loop, while node not appended (either by me or helper) 78 Art of Multiprocessor Programming
Main Loop
Main Loop • Non-zero sequence # means success 79 Art of Multiprocessor Programming
Main Loop
Main Loop • Non-zero sequence # means success • Thread keeps helping append nodes 80 Art of Multiprocessor Programming
Main Loop
Main Loop • Non-zero sequence # means success • Thread keeps helping append nodes • Until its own node is appended 81 Art of Multiprocessor Programming
Main Loop
while (announce[i].seq == 0) { Node before = head[i]; Node help = announce[(before.seq + 1) % n]; if (help.seq == 0) prefer = help; else prefer = announce[i]; … Main Loop 82 Art of Multiprocessor Programming
Main Loop
while (announce[i].seq == 0) { Node before = head[i]; Node help = announce[(before.seq + 1) % n]; if (help.seq == 0) prefer = help; else prefer = announce[i]; … Main Loop Keep trying until my cell gets a sequence number 83 Art of Multiprocessor Programming
Main Loop
while (announce[i].seq == 0) { Node before = head[i]; Node help = announce[(before.seq + 1) % n]; if (help.seq == 0) prefer = help; else prefer = announce[i]; … Main Loop Possible end of list 84 Art of Multiprocessor Programming
Main Loop
while (announce[i].seq == 0) { Node before = head[i]; Node help = announce[(before.seq + 1) % n]; if (help.seq == 0) prefer = help; else prefer = announce[i]; … Main Loop Whom do I help? 85 Art of Multiprocessor Programming
Altruism
Altruism • Choose a thread to “help” 86 Art of Multiprocessor Programming
Altruism
Altruism • Choose a thread to “help” • If that thread needs help – Try to append its node – Otherwise append your own 87 Art of Multiprocessor Programming
Altruism
Altruism • Choose a thread to “help” • If that thread needs help – Try to append its node – Otherwise append your own • Worst case – Everyone tries to help same pitiful loser – Someone succeeds 88 Art of Multiprocessor Programming
Help!
Help! • When last node in list has sequence number k 89 Art of Multiprocessor Programming
Help!
Help! • When last node in list has sequence number k • All threads check … – Whether thread k +1 mod n wants help – If so, try to append her node first 90 Art of Multiprocessor Programming
Help!
Help! • First time after thread k +1 announces – No guarantees 91 Art of Multiprocessor Programming
Help!
Help! • First time after thread k +1 announces – No guarantees • After n more nodes appended – Everyone sees that thread k +1 wants help – Everyone tries to append that node – Someone succeeds 92 Art of Multiprocessor Programming
Sliding Window Lemma
Sliding Window Lemma • After thread A announces its node • No more than n other calls – Can start and finish – Without appending A ’s node 93 Art of Multiprocessor Programming
Helping
Helping head 1 2 3 Max head +1 = n +4 n +2 n +3 … announce Thread 4: Help me! 4 So all see and help append 4 tail 94 Art of Multiprocessor Programming
The Sliding Help Window
The Sliding Help Window head … announce 4 tail help 3 help 4 3 95 Art of Multiprocessor Programming 1 2 3 n +2 n +3
Sliding Help Window
while (announce[i].seq == 0) { Node before = head[i]; Node help = announce[(before.seq + 1) % n]; if (help.seq == 0) prefer = help; else prefer = announce[i]; … Sliding Help Window In each main loop iteration pick another thread to help 96 Art of Multiprocessor Programming
Sliding Help Window
while (announce[i].seq == 0) { Node before = head[i]; Node help = announce[(before.seq + 1) % n]; if (help.seq == 0) prefer = help; else prefer = announce[i]; … Sliding Help Window Help if help required, but otherwise it’s all about me! 97 Art of Multiprocessor Programming
Rest is Same as Lock-free
Rest is Same as Lock-free while (announce[i].seq == 0) { … Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } 98 Art of Multiprocessor Programming
Rest is Same as Lock-free
Rest is Same as Lock-free while (announce[i].seq == 0) { … Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } Call consensus to attempt to append 99 Art of Multiprocessor Programming
Rest is Same as Lock-free
Rest is Same as Lock-free while (announce[i].seq == 0) { … Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } cache consensus result for later use 100 Art of Multiprocessor Programming
Rest is Same as Lock-free
Rest is Same as Lock-free while (announce[i].seq == 0) { … Node after = before.decideNext.decide(prefer); before.next = after; after.seq = before.seq + 1; head[i] = after; } Tell world that node is appended 101 Art of Multiprocessor Programming
Finishing the Job
Finishing the Job • Once thread’s node is linked … 102 Art of Multiprocessor Programming
Finishing the Job
Finishing the Job • Once thread’s node is linked… • The rest same as lock-free algorithm 103 Art of Multiprocessor Programming
Finishing the Job
Finishing the Job • Once thread’s node is linked … • The rest same as lock-free algorithm • Compute result by – sequentially applying list’s method calls – to a private copy of the object – starting from the initial state 104 Art of Multiprocessor Programming
Then Same Part II
Then Same Part II ... //compute my response SeqObject MyObject = new SeqObject(); current = tail.next; while (current != announce[i]){ MyObject.apply(current.invoc); current = current.next; } return MyObject.apply(current.invoc); } 105 Art of Multiprocessor Programming
Universal Application Part II
Universal Application Part II ... //compute my response SeqObject MyObject = new SeqObject(); current = tail.next; while (current != prefer){ MyObject.apply(current.invoc); current = current.next; } return MyObject.apply(current.invoc); } Return result after applying my method 106 Art of Multiprocessor Programming
Shared-Memory Computability
Shared-Memory Computability Wait-free/Lock-free computable = Solving n -consensus 10011 Universal Construction 107 Art of Multiprocessor Programming
Swap (getAndSet) not Universal
public class RMWRegister { private int value; public boolean getAndSet( int update) { int prior = value ; value = update; return prior; } } Swap (getAndSet) not Universal 108 Art of Multiprocessor Programming
public class RMWRegister { private int value; public boolean getAndSet( int update) { int prior = value ; value = update; return prior; } } Consensus number 2 Swap (getAndSet) not Universal 109 Art of Multiprocessor Programming
public class RMWRegister { private int value; public boolean getAndSet( int update) { int prior = value ; value = update; return prior; } } Not universal for ≥3 threads Swap (getAndSet) not Universal 110 Art of Multiprocessor Programming
CompareAndSet is Universal
public class RMWRegister { private int value; public boolean compareAndSet( int expected, int update) { int prior = value ; if (value == expected) { value = update; return true ; } return false ; }} CompareAndSet is Universal 111 Art of Multiprocessor Programming
CompareAndSet is Universal
public class RMWRegister { private int value; public boolean compareAndSet( int expected, int update) { int prior = value ; if (value == expected) { value = update; return true; } return false; }} CompareAndSet is Universal Consensus number ∞ 112 Art of Multiprocessor Programming
CompareAndSet is Universal
public class RMWRegister { private int value; public boolean compareAndSet( int expected, int update) { int prior = value ; if (value == expected) { value = update; return true; } return false; }} CompareAndSet is Universal Universal for any number of threads 113 Art of Multiprocessor Programming
On Older Architectures
114 On Older Architectures • IBM 360 – testAndSet ( getAndSet ) • NYU UltraComputer – getAndAdd (fetchAndAdd) • Neither universal – Except for 2 threads 114 Art of Multiprocessor Programming
On Newer Architectures
115 On Newer Architectures • Intel x86, Itanium, SPARC – compareAndSet (CAS, CMPXCHG) • Alpha AXP, PowerPC – Load-locked/store-conditional • All universal – For any number of threads • Trend is clear … 115 Art of Multiprocessor Programming
Practical Implications
Practical Implications • Any architecture that does not provide a universal primitive has inherent limitations • You cannot avoid locking for concurrent data structures … 116 Art of Multiprocessor Programming
Shared-Memory Computability
117 Shared-Memory Computability Wait-free/Lock-free computable = Threads with methods that solve n-consensus 10011 Universal Object 117 Art of Multiprocessor Programming
Veni, Vidi, Vici
Veni, Vidi, Vici • We saw – how to define concurrent objects 118 118 Art of Multiprocessor Programming
Veni, Vidi, Vici
Veni, Vidi, Vici • We saw – how to define concurrent objects • We discussed – computational power of machine instructions 119 119 Art of Multiprocessor Programming
Veni, Vidi, Vici
Veni, Vidi, Vici • We saw – how to define concurrent objects • We discussed – computational power of machine instructions • Next – use these foundations to understand the real world 120 120 Art of Multiprocessor Programming
  creativecommons.org/licenses/by-nc-sa/2.5/ Creative Commons Attribution-NonCommercial-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. 121 Art of Multiprocessor Programming