Concurrent Objects
Concurrent Objects Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit
Concurrent Computation
Art of Multiprocessor Programming 2 Concurrent Computation memory object object
Objectivism
Art of Multiprocessor Programming 3 Objectivism What is a concurrent object? How do we describe one? How do we implement one? How do we tell if we’re right ?
Objectivism
Art of Multiprocessor Programming 4 Objectivism What is a concurrent object? How do we describe one? How do we tell if we’re right ?
FIFO Queue: Enqueue Method
Art of Multiprocessor Programming 5 FIFO Queue: Enqueue Method q.enq( )
FIFO Queue: Dequeue Method
Art of Multiprocessor Programming 6 FIFO Queue: Dequeue Method q.deq()/
Lock-Based Queue
Art of Multiprocessor Programming 7 Lock-Based Queue head tail 0 2 1 5 4 3 y x capacity = 8 7 6
Lock-Based Queue
Art of Multiprocessor Programming 8 Lock-Based Queue head tail 0 2 1 5 4 3 y x capacity = 8 7 6 Fields protected by single shared lock
A Lock-Based Queue
class LockBasedQueue<T> { int head, tail; T[] items; Lock lock; public LockBasedQueue(int capacity) { head = 0; tail = 0; lock = new ReentrantLock(); items = (T[]) new Object[capacity]; } Art of Multiprocessor Programming 9 A Lock-Based Queue 0 1 capacity-1 2 head tail y z Fields protected by single shared lock
Lock-Based Queue
Art of Multiprocessor Programming 10 Lock-Based Queue head tail 0 2 1 5 4 3 Initially head = tail 7 6
A Lock-Based Queue
class LockBasedQueue<T> { int head, tail; T[] items; Lock lock; public LockBasedQueue( int capacity) { head = 0; tail = 0; lock = new ReentrantLock(); items = (T[]) new Object[capacity]; } Art of Multiprocessor Programming 11 A Lock-Based Queue 0 1 capacity-1 2 head tail y z Initially head = tail
Lock-Based deq()
Art of Multiprocessor Programming 12 Lock-Based deq() head tail 0 2 5 4 7 3 6 y x 1
Acquire Lock
Art of Multiprocessor Programming 13 Acquire Lock head tail 0 2 5 4 7 3 6 y x 1 Waiting to enqueue… My turn …
Implementation: deq()
public T deq() throws EmptyException { lock.lock(); try { if (tail == head) throw new EmptyException(); T x = items[head % items.length]; head++; return x; } finally { lock.unlock(); } } Art of Multiprocessor Programming 14 Implementation: deq() Acquire lock at method start 0 1 capacity-1 2 head tail y z
Check if Non-Empty
Art of Multiprocessor Programming 15 Check if Non-Empty head tail 0 2 5 4 7 3 6 y x 1 Waiting to enqueue…
Implementation: deq()
public T deq() throws EmptyException { lock.lock(); try { if (tail == head) throw new EmptyException(); T x = items[head % items.length]; head++; return x; } finally { lock.unlock(); } } Art of Multiprocessor Programming 16 Implementation: deq() If queue empty throw exception 0 1 capacity-1 2 head tail y z
Modify the Queue
Art of Multiprocessor Programming 17 Modify the Queue head tail 0 2 1 5 4 7 3 6 y x head Waiting to enqueue…
Implementation: deq()
public T deq() throws EmptyException { lock.lock(); try { if (tail == head) throw new EmptyException(); T x = items[head % items.length]; head++; return x; } finally { lock.unlock(); } } Art of Multiprocessor Programming 18 Implementation: deq() Queue not empty? Remove item and update head 0 1 capacity-1 2 head tail y z
Implementation: deq()
public T deq() throws EmptyException { lock.lock(); try { if (tail == head) throw new EmptyException(); T x = items[head % items.length]; head++; return x; } finally { lock.unlock(); } } Art of Multiprocessor Programming 19 Implementation: deq() Return result 0 1 capacity-1 2 head tail y z
Release the Lock
Art of Multiprocessor Programming 20 Release the Lock tail 0 2 1 5 4 7 3 6 y x head My turn!
Implementation: deq()
public T deq() throws EmptyException { lock.lock(); try { if (tail == head) throw new EmptyException(); T x = items[head % items.length]; head++; return x; } finally { lock.unlock(); } } Art of Multiprocessor Programming 21 Implementation: deq() Release lock no matter what! 0 1 capacity-1 2 head tail y z
Implementation: deq()
public T deq() throws EmptyException { lock.lock(); try { if (tail == head) throw new EmptyException(); T x = items[head % items.length]; head++; return x; } finally { lock.unlock(); } } Art of Multiprocessor Programming 22 Implementation: deq() Should be correct because modifications are mutually exclusive…
Now consider the following implementation
Art of Multiprocessor Programming 23 Now consider the following implementation The same thing without mutual exclusion For simplicity, only two threads One thread enq only The other deq only
Wait-free 2-Thread Queue
Art of Multiprocessor Programming 24 Wait-free 2-Thread Queue head tail 0 2 1 5 4 7 3 6 y x capacity = 8
Wait-free 2-Thread Queue
Art of Multiprocessor Programming 25 Wait-free 2-Thread Queue tail 0 2 5 4 7 3 6 y x 1 enq(z) deq() z head
Wait-free 2-Thread Queue
Art of Multiprocessor Programming 26 Wait-free 2-Thread Queue head tail 0 2 5 4 7 3 6 y 1 queue[tail] = z result = x z x
Wait-free 2-Thread Queue
Art of Multiprocessor Programming 27 Wait-free 2-Thread Queue tail 0 2 5 4 7 3 6 y 1 tail-- head++ z head x
Wait-free 2-Thread Queue
public class WaitFreeQueue { int head = 0, tail = 0; items = (T[]) new Object[capacity ]; public void enq(Item x) { if (tail-head == capacity) throw new FullException(); items[tail % capacity] = x; tail++; } public Item deq() { if (tail == head) throw new EmptyException(); Item item = items[head % capacity]; head++; return item; }} Art of Multiprocessor Programming 28 Wait-free 2-Thread Queue 0 1 capacity-1 2 head tail y z No lock needed !
Wait-free 2-Thread Queue
Wait-free 2-Thread Queue Art of Multiprocessor Programming 29 public T deq() throws EmptyException { lock.lock(); try { if (tail == head) throw new EmptyException(); T x = items[head % items.length]; head++; return x; } finally { lock.unlock(); } } How do we define “correct” when modifications are not mutually exclusive?
What is a Concurrent Queue?
Art of Multiprocessor Programming 30 What is a Concurrent Queue? Need a way to specify a concurrent queue object Need a way to prove that an algorithm implements the object’s specification Lets talk about object specifications …
Correctness and Progress
Correctness and Progress In a concurrent setting, we need to specify both the safety and the liveness properties of an object Need a way to define when an implementation is correct the conditions under which it guarantees progress Art of Multiprocessor Programming 31 Lets begin with correctness
Sequential Objects
Art of Multiprocessor Programming 32 Sequential Objects Each object has a state Usually given by a set of fields Queue example: sequence of items Each object has a set of methods Only way to manipulate state Queue example: enq and deq methods
Sequential Specifications
Art of Multiprocessor Programming 33 Sequential Specifications If (precondition) the object is in such-and-such a state before you call the method, Then (postcondition) the method will return a particular value or throw a particular exception. and (postcondition, con’t) the object will be in some other state when the method returns,
Pre and PostConditions for Dequeue
Art of Multiprocessor Programming 34 Pre and PostConditions for Dequeue Precondition: Queue is non-empty Postcondition: Returns first item in queue Postcondition: Removes first item in queue
Pre and PostConditions for Dequeue
Art of Multiprocessor Programming 35 Pre and PostConditions for Dequeue Precondition: Queue is empty Postcondition: Throws Empty exception Postcondition: Queue state unchanged
Why Sequential Specifications Totally Rock
Art of Multiprocessor Programming 36 Why Sequential Specifications Totally Rock Interactions among methods captured by side- effects on object state State meaningful between method calls Documentation size linear in number of methods Each method described in isolation Can add new methods Without changing descriptions of old methods
What About Concurrent Specifications ?
Art of Multiprocessor Programming 37 What About Concurrent Specifications ? Methods? Documentation? Adding new methods?
Methods Take Time
Art of Multiprocessor Programming 38 Methods Take Time time time
Methods Take Time
Art of Multiprocessor Programming 39 Methods Take Time time invocation 12:00 q.enq( ... ) time
Methods Take Time
Art of Multiprocessor Programming 40 Methods Take Time time Method call invocation 12:00 time q.enq( ... )
Methods Take Time
Art of Multiprocessor Programming 41 Methods Take Time time Method call invocation 12:00 time q.enq( ... )
Methods Take Time
Art of Multiprocessor Programming 42 Methods Take Time time Method call invocation 12:00 time void response 12:01 q.enq( ... )
Sequential vs Concurrent
Art of Multiprocessor Programming 43 Sequential vs Concurrent Sequential Methods take time? Who knew? Concurrent Method call is not an event Method call is an interval .
Concurrent Methods Take Overlapping Time
Art of Multiprocessor Programming 44 time Concurrent Methods Take Overlapping Time time
Concurrent Methods Take Overlapping Time
Art of Multiprocessor Programming 45 time Concurrent Methods Take Overlapping Time time Method call
Concurrent Methods Take Overlapping Time
Art of Multiprocessor Programming 46 time Concurrent Methods Take Overlapping Time time Method call Method call
Concurrent Methods Take Overlapping Time
Art of Multiprocessor Programming 47 time Concurrent Methods Take Overlapping Time time Method call Method call Method call
Sequential vs Concurrent
Art of Multiprocessor Programming 48 Sequential vs Concurrent Sequential: Object needs meaningful state only between method calls Concurrent Because method calls overlap, object might never be between method calls
Sequential vs Concurrent
Art of Multiprocessor Programming 49 Sequential vs Concurrent Sequential: Each method described in isolation Concurrent Must characterize all possible interactions with concurrent calls What if two enq s overlap? Two deq s? enq and deq ? …
Sequential vs Concurrent
Art of Multiprocessor Programming 50 Sequential vs Concurrent Sequential: Can add new methods without affecting older methods Concurrent: Everything can potentially interact with everything else
Sequential vs Concurrent
Art of Multiprocessor Programming 51 Sequential vs Concurrent Sequential: Can add new methods without affecting older methods Concurrent: Everything can potentially interact with everything else Panic!
The Big Question
Art of Multiprocessor Programming 52 The Big Question What does it mean for a concurrent object to be correct? What is a concurrent FIFO queue? FIFO means strict temporal order Concurrent means ambiguous temporal order
Intuitively…
Art of Multiprocessor Programming 53 Intuitively… public T deq() throws EmptyException { lock.lock(); try { if (tail == head) throw new EmptyException(); T x = items[head % items.length]; head++; return x; } finally { lock.unlock(); } }
Intuitively…
Art of Multiprocessor Programming 54 Intuitively… public T deq() throws EmptyException { lock.lock(); try { if (tail == head) throw new EmptyException(); T x = items[head % items.length]; head++; return x; } finally { lock.unlock(); } } All queue modifications are mutually exclusive
Intuitively
Art of Multiprocessor Programming 55 time Intuitively q.deq q.enq enq deq lock() unlock() lock() unlock() Behavior is “Sequential” enq deq Lets capture the idea of describing the concurrent via the sequential
Linearizability
Art of Multiprocessor Programming 56 Linearizability Each method should “take effect” Instantaneously Between invocation and response events Object is correct if this “sequential” behavior is correct Any such concurrent object is Linearizable™
Is it really about the object?
Art of Multiprocessor Programming 57 Is it really about the object? Each method should “take effect” Instantaneously Between invocation and response events Sounds like a property of an execution… A linearizable object : one all of whose possible executions are linearizable
Example
Art of Multiprocessor Programming 58 Example time time
Example
Art of Multiprocessor Programming 59 Example time q.enq(x) time
Example
Art of Multiprocessor Programming 60 Example time q.enq(x) q.enq(y) time
Example
Art of Multiprocessor Programming 61 Example time q.enq(x) q.enq(y) q.deq(x) time
Example
Art of Multiprocessor Programming 62 Example time q.enq(x) q.enq(y) q.deq(x) q.deq(y) time
Example
Art of Multiprocessor Programming 63 Example time q.enq(x) q.enq(y) q.deq(x) q.deq(y) linearizable q.enq(x) q.enq(y) q.deq(x) q.deq(y) time
Example
Art of Multiprocessor Programming 64 Example time q.enq(x) q.enq(y) q.deq(x) q.deq(y) Valid? q.enq(x) q.enq(y) q.deq(x) q.deq(y) time
Example
Art of Multiprocessor Programming 65 Example time
Example
Art of Multiprocessor Programming 66 Example time q.enq(x)
Example
Art of Multiprocessor Programming 67 Example time q.enq(x) q.deq(y)
Example
Art of Multiprocessor Programming 68 Example time q.enq(x) q.enq(y) q.deq(y)
Example
Art of Multiprocessor Programming 69 Example time q.enq(x) q.enq(y) q.deq(y) q.enq(x) q.enq(y)
Example
Art of Multiprocessor Programming 70 Example time q.enq(x) q.enq(y) q.deq(y) q.enq(x) q.enq(y) (5) not linearizable
Example
Art of Multiprocessor Programming 71 Example time time
Example
Art of Multiprocessor Programming 72 Example time q.enq(x) time
Example
Art of Multiprocessor Programming 73 Example time q.enq(x) q.deq(x) time
Example
Art of Multiprocessor Programming 74 Example time q.enq(x) q.deq(x) q.enq(x) q.deq(x) time
Example
Art of Multiprocessor Programming 75 Example time q.enq(x) q.deq(x) q.enq(x) q.deq(x) linearizable time
Example
Art of Multiprocessor Programming 76 Example time q.enq(x) time
Example
Art of Multiprocessor Programming 77 Example time q.enq(x) q.enq(y) time
Example
Art of Multiprocessor Programming 78 Example time q.enq(x) q.enq(y) q.deq(y) time
Example
Art of Multiprocessor Programming 79 Example time q.enq(x) q.enq(y) q.deq(y) q.deq(x) time
Art of Multiprocessor Programming 80 q.enq(x) q.enq(y) q.deq(y) q.deq(x) Comme ci Example time Comme ça multiple orders OK linearizable
Read/Write Register Example
Art of Multiprocessor Programming 81 Read/Write Register Example time read(1) write(0) write(1) write(2) time read(0)
Read/Write Register Example
Art of Multiprocessor Programming 82 Read/Write Register Example time read(1) write(0) write(1) write(2) time read(0) write(1) already happened
Read/Write Register Example
Art of Multiprocessor Programming 83 Read/Write Register Example time read(1) write(0) write(1) write(2) time read(0) write(1) write(1) already happened
Read/Write Register Example
Art of Multiprocessor Programming 84 Read/Write Register Example time read(1) write(0) write(1) write(2) time read(0) write(1) write(1) already happened not linearizable
Read/Write Register Example
Art of Multiprocessor Programming 85 Read/Write Register Example time read(1) write(0) write(1) write(2) time read(1) write(1) already happened
Read/Write Register Example
Art of Multiprocessor Programming 86 Read/Write Register Example time read(1) write(0) write(1) write(2) time read(1) write(1) write(2) write(1) already happened
Read/Write Register Example
Art of Multiprocessor Programming 87 Read/Write Register Example time read(1) write(0) write(1) write(2) time read(1) write(1) write(2) not linearizable write(1) already happened
Read/Write Register Example
Art of Multiprocessor Programming 88 Read/Write Register Example time write(0) write(1) write(2) time read(1)
Read/Write Register Example
Art of Multiprocessor Programming 89 Read/Write Register Example time write(0) write(1) write(2) time read(1) write(1) write(2)
Read/Write Register Example
Art of Multiprocessor Programming 90 Read/Write Register Example time write(0) write(1) write(2) time read(1) write(1) write(2) linearizable
Read/Write Register Example
Art of Multiprocessor Programming 91 Read/Write Register Example time read(1) write(0) write(1) write(2) time read(1)
Read/Write Register Example
Art of Multiprocessor Programming 92 Read/Write Register Example time read(1) write(0) write(1) write(2) time read(1) write(1)
Read/Write Register Example
Art of Multiprocessor Programming 93 Read/Write Register Example time read(1) write(0) write(1) write(2) time read(1) write(1) write(2)
Read/Write Register Example
Art of Multiprocessor Programming 94 Read/Write Register Example time read(1) write(0) write(1) write(2) time read(2) write(1) write(2) Not linearizable
Talking About Executions
Art of Multiprocessor Programming 95 Talking About Executions Why? Can’t we specify the linearization point of each operation without describing an execution? Not Always In some cases, linearization point depends on the execution
Formal Model of Executions
Art of Multiprocessor Programming 96 Formal Model of Executions Define precisely what we mean Ambiguity is bad when intuition is weak Allow reasoning Formal But mostly informal In the long run, actually more important Ask me why!
Split Method Calls into Two Events
Art of Multiprocessor Programming 97 Split Method Calls into Two Events Invocation method name & args q.enq(x) Response result or exception q.enq(x) returns void q.deq() returns x q.deq() throws empty
Invocation Notation
Art of Multiprocessor Programming 98 Invocation Notation A q.enq(x) (4)
Invocation Notation
Art of Multiprocessor Programming 99 Invocation Notation A q.enq(x) thread (4)
Invocation Notation
Art of Multiprocessor Programming 100 Invocation Notation A q.enq(x) thread method (4)
Invocation Notation
Art of Multiprocessor Programming 101 Invocation Notation A q.enq(x) thread object (4) method
Invocation Notation
Art of Multiprocessor Programming 102 Invocation Notation A q.enq(x) thread object method arguments (4)
Response Notation
Art of Multiprocessor Programming 103 Response Notation A q: void (2)
Response Notation
Art of Multiprocessor Programming 104 Response Notation A q: void thread (2)
Response Notation
Art of Multiprocessor Programming 105 Response Notation A q: void thread result (2)
Response Notation
Art of Multiprocessor Programming 106 Response Notation A q: void thread object result (2)
Response Notation
Art of Multiprocessor Programming 107 Response Notation A q: void thread object result (2) Method is implicit
Response Notation
Art of Multiprocessor Programming 108 Response Notation A q: empty() thread object (2) Method is implicit exception
History - Describing an Execution
Art of Multiprocessor Programming 109 History - Describing an Execution A q.enq(3) A q:void A q.enq(5) B p.enq(4) B p:void B q.deq() B q:3 Sequence of invocations and responses H =
Definition
Art of Multiprocessor Programming 110 Definition Invocation & response match if A q.enq(3) A q:void Thread names agree Object names agree Method call (1)
Object Projections
Art of Multiprocessor Programming 111 Object Projections A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 H =
Object Projections
Art of Multiprocessor Programming 112 Object Projections A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 H|q =
Thread Projections
Art of Multiprocessor Programming 113 Thread Projections A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 H =
Thread Projections
Art of Multiprocessor Programming 114 Thread Projections A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 H|B =
Complete Subhistory
Art of Multiprocessor Programming 115 Complete Subhistory A q.enq(3) A q:void A q.enq(5) B p.enq(4) B p:void B q.deq() B q:3 An invocation is pending if it has no matching respnse H =
Complete Subhistory
Art of Multiprocessor Programming 116 Complete Subhistory A q.enq(3) A q:void A q.enq(5) B p.enq(4) B p:void B q.deq() B q:3 May or may not have taken effect H =
Complete Subhistory
Art of Multiprocessor Programming 117 Complete Subhistory A q.enq(3) A q:void A q.enq(5) B p.enq(4) B p:void B q.deq() B q:3 discard pending invocations H =
Complete Subhistory
Art of Multiprocessor Programming 118 Complete Subhistory A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 Complete(H) =
Sequential Histories
Art of Multiprocessor Programming 119 Sequential Histories A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 A q:enq(5) (4)
Sequential Histories
Art of Multiprocessor Programming 120 Sequential Histories A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 A q:enq(5) match (4)
Sequential Histories
Art of Multiprocessor Programming 121 Sequential Histories A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 A q:enq(5) match match (4)
Sequential Histories
Art of Multiprocessor Programming 122 Sequential Histories A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 A q:enq(5) match match match (4)
Sequential Histories
Art of Multiprocessor Programming 123 Sequential Histories A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 A q:enq(5) match match match Final pending invocation OK (4)
Sequential Histories
Art of Multiprocessor Programming 124 Sequential Histories A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 A q:enq(5) match match match Final pending invocation OK (4) Method calls of different threads do not interleave
Well-Formed Histories
Art of Multiprocessor Programming 125 Well-Formed Histories H= A q.enq(3) B p.enq(4) B p:void B q.deq() A q:void B q:3
Well-Formed Histories
Art of Multiprocessor Programming 126 Well-Formed Histories H= A q.enq(3) B p.enq(4) B p:void B q.deq() A q:void B q:3 H|B= B p.enq(4) B p:void B q.deq() B q:3 Per-thread projections sequential
Well-Formed Histories
Art of Multiprocessor Programming 127 Well-Formed Histories H= A q.enq(3) B p.enq(4) B p:void B q.deq() A q:void B q:3 H|B= B p.enq(4) B p:void B q.deq() B q:3 A q.enq(3) A q:void H|A= Per-thread projections sequential
Equivalent Histories
Art of Multiprocessor Programming 128 Equivalent Histories H= A q.enq(3) B p.enq(4) B p:void B q.deq() A q:void B q:3 Threads see the same thing in both A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 G= H|A = G|A H|B = G|B
Sequential Specifications
Art of Multiprocessor Programming 129 Sequential Specifications A sequential specification is some way of telling whether a Single-thread, single-object history Is legal For example: Pre and post-conditions But plenty of other techniques exist …
Legal Histories
Art of Multiprocessor Programming 130 Legal Histories A sequential (multi-object) history H is legal if For every object x H|x is in the sequential spec for x
Precedence
Art of Multiprocessor Programming 131 Precedence A q.enq(3) B p.enq(4) B p.void A q:void B q.deq() B q:3 A method call precedes another if response event precedes invocation event Method call Method call (1)