Concurrent Objects

Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit

Concurrent Computation

memory

object
Art of Multiprocessor Programming

object
2

Objectivism
What is a concurrent object?
How do we describe one? How do we implement one? How do we tell if were right?

Art of Multiprocessor Programming

Objectivism
What is a concurrent object?
How do we describe one?
How do we tell if were right?

Art of Multiprocessor Programming

FIFO Queue: Enqueue Method

[Link]( )

Art of Multiprocessor Programming

FIFO Queue: Dequeue Method

[Link]()/

Art of Multiprocessor Programming

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

A Lock-Based Queue
head
0 capacity-1

tail
1

y z 2 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]; }

Queue fields protected by single shared lock

Art of Multiprocessor Programming 8

A Lock-Based Queue
head
0 capacity-1

tail
1

y z 2 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]; }

Initially head = tail

Art of Multiprocessor Programming

Implementation: Deq
head tail
0 1 2

public T deq() throws EmptyException capacity-1 { y z [Link](); try { if (tail == head) throw new EmptyException(); T x = items[head % [Link]]; head++; return x; } finally { [Link](); } }

Art of Multiprocessor Programming

10

Implementation: Deq
head
0 1

tail

public T deq() throws EmptyException capacity-1 { y z 2 [Link](); try { if (tail == head) throw new EmptyException(); T x = items[head % [Link]]; head++; return x; } finally { Method calls [Link](); mutually exclusive } }

Art of Multiprocessor Programming

11

Implementation: Deq
head
0 1

tail

public T deq() throws EmptyException capacity-1 { y z 2 [Link](); try { if (tail == head) throw new EmptyException(); T x = items[head % [Link]]; head++; return x; } finally { If queue empty [Link](); } throw exception }

Art of Multiprocessor Programming

12

Implementation: Deq
head
0 1

tail

public T deq() throws EmptyException capacity-1 { y z 2 [Link](); try { if (tail == head) throw new EmptyException(); T x = items[head % [Link]]; head++; return x; } finally { Queue not empty: [Link](); } remove item and update }

head

Art of Multiprocessor Programming

13

Implementation: Deq
head tail
0 1

public T deq() throws EmptyException capacity-1 { y z 2 [Link](); try { if (tail == head) throw new EmptyException(); T x = items[head % [Link]]; head++; return x; } finally { Return result [Link](); } }

Art of Multiprocessor Programming

14

Implementation: Deq
head
0 1

tail

public T deq() throws EmptyException capacity-1 { y z 2 [Link](); try { if (tail == head) throw new EmptyException(); T x = items[head % [Link]]; head++; return x; Release lock no } finally { matter what! [Link](); } }

Art of Multiprocessor Programming

15

Implementation: Deq
public T deq() throws EmptyException { [Link](); try { if (tail == head) throw new EmptyException(); T x = items[head % [Link]]; head++; return x; } finally { [Link](); } }

Art of Multiprocessor Programming

16

Now consider the following implementation

The same thing without mutual exclusion For simplicity, only two threads
One thread enq only The other deq only

Art of Multiprocessor Programming

17

Wait-free 2-Thread Queue

public class WaitFreeQueue { int head = 0, tail = 0; items = (T[]) new Object[capacity];
head
0 capacity-1

tail

y z

1 2

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 18
Programming

Wait-free 2-Thread Queue

public class WaitFreeQueue { int head = 0, tail = 0; items = (T[]) new Object[capacity];
head head
capacity-1 capacity-1 0 0

tail tail
1

yy zz

1
2 2

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 19
Programming

Wait-free 2-Thread Queue

public class WaitFreeQueue {
head
0 1 2 capacity-1

tail

y z 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(); Queue is updated without lock! Item item = items[head %a capacity]; head++; return item; }} Art of Multiprocessor 20
Programming

Defining concurrent queue implementations

Need a way to specify a concurrent queue object Need a way to prove that an algorithm implements the objects specification Lets talk about object specifications
Art of Multiprocessor Programming 21

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
Lets begin with correctness
Art of Multiprocessor Programming 22

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

Art of Multiprocessor Programming

23

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, cont) the object will be in some other state when the method returns,
Art of Multiprocessor Programming 24

Pre and PostConditions for Dequeue

Precondition:
Queue is non-empty

Postcondition:
Returns first item in queue

Postcondition:
Removes first item in queue

Art of Multiprocessor Programming

25

Pre and PostConditions for Dequeue

Precondition:
Queue is empty

Postcondition:
Throws Empty exception

Postcondition:
Queue state unchanged

Art of Multiprocessor Programming

26

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

Art of Multiprocessor Programming

27

What About Concurrent Specifications ?

Methods? Documentation? Adding new methods?

Art of Multiprocessor Programming

28

Methods Take Time

time
Art of Multiprocessor Programming 29

Methods Take Time

invocation 12:00
[Link](...)

time
Art of Multiprocessor Programming 30

Methods Take Time

invocation 12:00
[Link](...)

Method call time

Art of Multiprocessor Programming 31

Methods Take Time

invocation 12:00
[Link](...)

Method call time

Art of Multiprocessor Programming 32

Methods Take Time

invocation 12:00
[Link](...)

response 12:01
void Method call time
Art of Multiprocessor Programming 33

Sequential vs Concurrent
Sequential
Methods take time? Who knew?

Concurrent
Method call is not an event Method call is an interval.

Art of Multiprocessor Programming

34

Concurrent Methods Take Overlapping Time

time
Art of Multiprocessor Programming 35

Concurrent Methods Take Overlapping Time

Method call

time
Art of Multiprocessor Programming 36

Concurrent Methods Take Overlapping Time

Method call Method call time

Art of Multiprocessor Programming 37

Concurrent Methods Take Overlapping Time

Method call Method call time

Method call

Art of Multiprocessor Programming

38

Sequential vs Concurrent
Sequential:
Object needs meaningful state only between method calls

Concurrent
Because method calls overlap, object might never be between method calls

Art of Multiprocessor Programming

39

Sequential vs Concurrent
Sequential:
Each method described in isolation

Concurrent

Must characterize all possible interactions with concurrent calls

What if two enqs overlap? Two deqs? enq and deq?

Art of Multiprocessor Programming

40

Sequential vs Concurrent
Sequential:
Can add new methods without affecting older methods

Concurrent:
Everything can potentially interact with everything else

Art of Multiprocessor Programming

41

Sequential vs Concurrent
Sequential:
Can add new methods without affecting older methods

Concurrent:
Everything can potentially interact with everything else

Art of Multiprocessor Programming

42

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

Art of Multiprocessor Programming

43

Intuitively
public T deq() throws EmptyException { [Link](); try { if (tail == head) throw new EmptyException(); T x = items[head % [Link]]; head++; return x; } finally { [Link](); } }

Art of Multiprocessor Programming

44

Intuitively
public T deq() throws EmptyException { [Link](); try { if (tail == head) throw new EmptyException(); T x = items[head % [Link]]; head++; return x; } finally { All modifications [Link](); of queue are done } mutually exclusive }

Art of Multiprocessor Programming

45

Lets capture the idea of describing the concurrent via the sequential
lock()

Intuitively
[Link] deq

unlock()

[Link]
lock()

enq

unlock()

Behavior is Sequential

Art of Multiprocessor Programming

time enq

deq

46

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

Art of Multiprocessor Programming

47

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
Art of Multiprocessor Programming 48

Example

time
(6)

Art of Multiprocessor Programming

49

Example

[Link](x)

time
(6)

Art of Multiprocessor Programming

50

Example

[Link](x) [Link](y) time

(6)

Art of Multiprocessor Programming

51

Example

[Link](x) [Link](y) [Link](x) time

(6)

Art of Multiprocessor Programming

52

Example

[Link](x) [Link](y) [Link](x) time

(6)

[Link](y)

Art of Multiprocessor Programming

53

Example

[Link](x) [Link](y) [Link](x) time

(6)

[Link](y)

Art of Multiprocessor Programming

54

Example

[Link](x) [Link](y) [Link](x) time

(6)

[Link](y)

Art of Multiprocessor Programming

55

Example

time
(5)

Art of Multiprocessor Programming

56

Example

[Link](x)

time
(5)

Art of Multiprocessor Programming

57

Example

[Link](x)

[Link](y)

time
(5)

Art of Multiprocessor Programming

58

Example

[Link](x)

[Link](y) [Link](y) time

(5)

Art of Multiprocessor Programming

59

Example

[Link](x)

[Link](y)

[Link](y)
time
(5)

Art of Multiprocessor Programming

60

Example

[Link](x)

[Link](y)

[Link](y)
time
(5)

Art of Multiprocessor Programming

61

Example

time
(4)

Art of Multiprocessor Programming

62

Example

[Link](x)

time
(4)

Art of Multiprocessor Programming

63

Example

[Link](x)
[Link](x) time
(4)

Art of Multiprocessor Programming

64

Example

[Link](x)

[Link](x)
time
(4)

Art of Multiprocessor Programming

65

Example

[Link](x)

[Link](x)
time
(4)

Art of Multiprocessor Programming

66

Example

[Link](x)

time
(8)

Art of Multiprocessor Programming

67

Example

[Link](x) [Link](y) time

(8)

Art of Multiprocessor Programming

68

Example

[Link](x) [Link](y)

[Link](y)

time
(8)

Art of Multiprocessor Programming

69

Example

[Link](x) [Link](y)

[Link](y) [Link](x) time

(8)

Art of Multiprocessor Programming

70

Comme ci Example Comme a

[Link](x)

[Link](y)

[Link](y)
time

[Link](x)

Art of Multiprocessor Programming

71

Read/Write Register Example

write(0)

read(1) write(1) time

write(2) read(0)

(4)

Art of Multiprocessor Programming

72

Read/Write Register Example

write(0)

read(1) write(1)

write(2) read(0)

write(1) already happened time

(4)

Art of Multiprocessor Programming

73

Read/Write Register Example

write(0)

read(1) write(1)

write(2) read(0)

write(1) already happened time

(4)

Art of Multiprocessor Programming

74

Read/Write Register Example

write(0)

read(1) write(1)

write(2) read(0)

write(1) already happened time

(4)

Art of Multiprocessor Programming

75

Read/Write Register Example

write(0)

read(1) write(1)

write(2) read(1)

write(1) already happened time

(4)

Art of Multiprocessor Programming

76

Read/Write Register Example

write(0)

read(1) write(1)

write(2) read(1)

write(1) already happened time

(4)

Art of Multiprocessor Programming

77

Read/Write Register Example

write(0)

read(1) write(1)

write(2) read(1)

write(1) already happened time

(4)

Art of Multiprocessor Programming

78

Read/Write Register Example

write(0) write(1) time

(4)

write(2) read(1)

Art of Multiprocessor Programming

79

Read/Write Register Example

write(0) write(1) time

(4)

write(2) read(1)

Art of Multiprocessor Programming

80

Read/Write Register Example

write(0) write(1) time

(4)

write(2) read(1)

Art of Multiprocessor Programming

81

Read/Write Register Example

write(0)

read(1) write(1) time

write(2) read(1)

(2)

Art of Multiprocessor Programming

82

Read/Write Register Example

write(0)

read(1) write(1) time

write(2) read(1)

(2)

Art of Multiprocessor Programming

83

Read/Write Register Example

write(0)

read(1) write(1) time

write(2) read(1)

(2)

Art of Multiprocessor Programming

84

Read/Write Register Example

write(0)

read(1) write(1) time

write(2) read(2)

(2)

Art of Multiprocessor Programming

85

Talking About Executions

Why?
Cant we specify the linearization point of each operation without describing an execution?

Not Always
In some cases, linearization point depends on the execution

Art of Multiprocessor Programming

86

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!

Art of Multiprocessor Programming

87

Split Method Calls into Two Events

Invocation Response
method name & args [Link](x) result or exception [Link](x) returns void [Link]() returns x [Link]() throws empty
Art of Multiprocessor Programming 88

Invocation Notation
A [Link](x)

(4)

Art of Multiprocessor Programming

89

Invocation Notation
A [Link](x) thread

(4)

Art of Multiprocessor Programming

90

Invocation Notation
A [Link](x) thread method

(4)

Art of Multiprocessor Programming

91

Invocation Notation
A [Link](x) thread object
(4)

method

Art of Multiprocessor Programming

92

Invocation Notation
A [Link](x) thread object
(4)

method arguments
93

Art of Multiprocessor Programming

Response Notation
A q: void

(2)

Art of Multiprocessor Programming

94

Response Notation
A q: void thread

(2)

Art of Multiprocessor Programming

95

Response Notation
A q: void thread result

(2)

Art of Multiprocessor Programming

96

Response Notation
A q: void thread object
(2)

result

Art of Multiprocessor Programming

97

Response Notation
A q: void thread object
(2)

result

Art of Multiprocessor Programming

98

Response Notation
A q: empty() thread object
(2)

exception

Art of Multiprocessor Programming

99

History - Describing an Execution

A A A H = B B B B

[Link](3) q:void [Link](5) [Link](4) p:void [Link]() q:3

Art of Multiprocessor Programming

Sequence of invocations and responses

100

Definition
Invocation & response match if Thread names agree A q:void
(1)

Object names agree

Method call

A [Link](3)

Art of Multiprocessor Programming

101

Object Projections

H=

A A B B B B

[Link](3) q:void [Link](4) p:void [Link]() q:3

Art of Multiprocessor Programming 102

Object Projections

H|q =

A A B B B B

[Link](3) q:void [Link](4) p:void [Link]() q:3

Art of Multiprocessor Programming 103

Thread Projections

H=

A A B B B B

[Link](3) q:void [Link](4) p:void [Link]() q:3

Art of Multiprocessor Programming 104

Thread Projections

H|B =

A A B B B B

[Link](3) q:void [Link](4) p:void [Link]() q:3

Art of Multiprocessor Programming 105

Complete Subhistory
A A A H = B B B B [Link](3) q:void [Link](5) [Link](4) p:void [Link]() An invocation is q:3 pending if it has no matching respnse
106 Art of Multiprocessor Programming

Complete Subhistory
A A A H = B B B B [Link](3) q:void [Link](5) [Link](4) p:void [Link]() May or may not q:3 have taken effect
Art of Multiprocessor Programming 107

Complete Subhistory
A A A H = B B B B [Link](3) q:void [Link](5) [Link](4) p:void [Link]() q:3
Art of Multiprocessor Programming

discard pending invocations

108

Complete Subhistory
A [Link](3) A q:void Complete(H) = B B B B [Link](4) p:void [Link]() q:3
Art of Multiprocessor Programming 109

Sequential Histories

A A B B B B A

[Link](3) q:void [Link](4) p:void [Link]() q:3 q:enq(5)

(4)

Art of Multiprocessor Programming

110

Sequential Histories
match

A A B B B B A

[Link](3) q:void [Link](4) p:void [Link]() q:3 q:enq(5)

(4)

Art of Multiprocessor Programming

111

Sequential Histories
match

A A B B B B A

[Link](3) q:void [Link](4) p:void [Link]() q:3 q:enq(5)

(4)

match

Art of Multiprocessor Programming

112

Sequential Histories
match

A A B B B B A

[Link](3) q:void [Link](4) p:void [Link]() q:3 q:enq(5)

(4)

match
match

Art of Multiprocessor Programming

113

Sequential Histories
match

A A B B B B A

[Link](3) q:void [Link](4) p:void [Link]() q:3 q:enq(5)

(4)

match
match Final pending invocation OK
Art of Multiprocessor Programming 114

Sequential Histories
match

A A B B B B A

[Link](3) q:void [Link](4) p:void [Link]() q:3 q:enq(5)

(4)

match
match Final pending invocation OK
Art of Multiprocessor Programming 115

Well-Formed Histories

A B B H= B A B

[Link](3) [Link](4) p:void [Link]() q:void q:3

Art of Multiprocessor Programming

116

Well-Formed Histories
Per-thread projections sequential A B B H= B A B [Link](3) [Link](4) p:void [Link]() q:void q:3

B H|B= B B B

[Link](4) p:void [Link]() q:3

Art of Multiprocessor Programming

117

Well-Formed Histories
Per-thread projections sequential A B B H= B A B [Link](3) [Link](4) p:void [Link]() q:void q:3

B H|B= B B B

[Link](4) p:void [Link]() q:3

A [Link](3) H|A= A q:void

Art of Multiprocessor Programming 118

Equivalent Histories
Threads see the same thing in both A B B H= B A B [Link](3) [Link](4) p:void [Link]() q:void q:3

H|A = G|A H|B = G|B

[Link](3) q:void [Link](4) p:void [Link]() q:3
119

A A B G= B B B
Art of Multiprocessor Programming

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

Art of Multiprocessor Programming

120

Legal Histories
A sequential (multi-object) history H is legal if
For every object x H|x is in the sequential spec for x

Art of Multiprocessor Programming

121

Precedence
A B B A B B [Link](3) [Link](4) [Link] q:void [Link]() q:3

A method call precedes another if response event precedes invocation event

Method call Method call
122

(1)

Art of Multiprocessor Programming

Non-Precedence
A B B B A B [Link](3) [Link](4) [Link] [Link]() q:void q:3

Some method calls overlap one another

Method call
Method call

(1)

Art of Multiprocessor Programming

123

Notation
Given
History H method executions m0 and m1 in H m0 precedes m1
m0 m1

We say m0 H m1, if

Relation m0 H m1 is a

Partial order Total order if H is sequential

Art of Multiprocessor Programming 124

Linearizability
History H is linearizable if it can be extended to G by
Appending zero or more responses to pending invocations Discarding other pending invocations Legal sequential history S where G S
Art of Multiprocessor Programming

So that G is equivalent to

125

What is G S
G = {ac,bc} S = {ab,ac,bc}
a b G time
(8)

S
126

Art of Multiprocessor Programming

Remarks
Some pending invocations
Took effect, so keep them Discard the rest

Condition G S

Means that S respects real-time order of G

Art of Multiprocessor Programming

127

Example
A B B B B B [Link](3) [Link](4) q:void [Link]() q:4 q:enq(6)

A. [Link](3) [Link](4) [Link](4) time

Art of Multiprocessor Programming 128

B. [Link](6)

Example
A B B B B B [Link](3) [Link](4) q:void [Link]() q:4 q:enq(6) Complete this pending invocation

A. [Link](3) [Link](4) [Link](3) time

Art of Multiprocessor Programming 129

B. [Link](6)

Example
A B B B B B A [Link](3) [Link](4) q:void [Link]() q:4 q:enq(6) q:void
[Link](3) [Link](4) [Link](4) time
Art of Multiprocessor Programming 130

Complete this pending invocation

B. [Link](6)

Example
A B B B B B A [Link](3) [Link](4) q:void [Link]() q:4 q:enq(6) q:void
[Link](3) [Link](4) [Link](4) time
Art of Multiprocessor Programming 131

discard this one

B. [Link](6)

Example
A B B B B [Link](3) [Link](4) q:void [Link]() q:4

discard this one

A q:void
[Link](3) [Link](4) [Link](4) time
Art of Multiprocessor Programming 132

Example
A B B B B A [Link](3) [Link](4) q:void [Link]() q:4 q:void
[Link](3)
[Link](4) [Link](4)

Art of Multiprocessor Programming

time

133

Example
A B B B B A [Link](3) [Link](4) q:void [Link]() q:4 q:void B B A A B B
[Link](3)
[Link](4) [Link](4)

[Link](4) q:void [Link](3) q:void [Link]() q:4

Art of Multiprocessor Programming

time

134

Example
Equivalent sequential history A B B B B A [Link](3) [Link](4) q:void [Link]() q:4 q:void B B A A B B
[Link](3)
[Link](4) [Link](4)

[Link](4) q:void [Link](3) q:void [Link]() q:4

Art of Multiprocessor Programming

time

135

Composability Theorem
History H is linearizable if and only if
For every object x H|x is linearizable

We care about objects only!

(Materialism?)

Art of Multiprocessor Programming

141

Why Does Composability Matter?

Modularity Can prove linearizability of objects in isolation Can compose independently-implemented objects

Art of Multiprocessor Programming

142

Reasoning About Linearizability: Locking

public T deq() throws EmptyException { 1 capacity-1 y z [Link](); try { if (tail == head) throw new EmptyException(); T x = items[head % [Link]]; head++; return x; } finally { [Link](); } }
0

head

tail
2

Art of Multiprocessor Programming

143

Reasoning About Linearizability: Locking

public T deq() throws EmptyException { [Link](); try { if (tail == head) throw new EmptyException(); T x = items[head % [Link]]; head++; return x; } finally { Linearization points [Link](); are when locks are } } released

Art of Multiprocessor Programming

144

More Reasoning: Wait-free

public class WaitFreeQueue { int head = 0, tail = 0; items = (T[]) new Object[capacity];
head head
capacity-1 capacity-1 0 0

tail tail
1

yy zz

1
2 2

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 145
Programming

More Reasoning: Wait-free

public class WaitFreeQueue { int head = 0, items = (T[])

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 146
Programming

Linearization order is y z tail = 0; order head and tail new Object[capacity]; fields modified
0 1 capacity-1 2

head

tail

Strategy
Identify one atomic step where method happens
Critical section Machine instruction

Doesnt always work

Might need to define several different steps for a given method

Art of Multiprocessor Programming

147

Linearizability: Summary
Powerful specification tool for shared objects Allows us to capture the notion of objects being atomic Dont leave home without it

Art of Multiprocessor Programming

148

Alternative: Sequential Consistency

History H is Sequentially Consistent if it can be extended to G by
Appending zero or more responses to pending invocations Discarding other pending invocations Legal sequential history S

So that G is equivalent to a
Where G S
Art of Multiprocessor Programming

Differs from linearizability

149

Sequential Consistency
No need to preserve real-time order
Cannot re-order operations done by the same thread Can re-order non-overlapping operations done by different threads

Often used to describe multiprocessor memory architectures

Art of Multiprocessor Programming 150

Example

time
(5)

Art of Multiprocessor Programming

151

Example

[Link](x)

time
(5)

Art of Multiprocessor Programming

152

Example

[Link](x)

[Link](y)

time
(5)

Art of Multiprocessor Programming

153

Example

[Link](x)

[Link](y) [Link](y) time

(5)

Art of Multiprocessor Programming

154

Example

[Link](x)

[Link](y)

[Link](y)
time
(5)

Art of Multiprocessor Programming

155

Example

[Link](x)

[Link](y)

[Link](y)
time
(5)

Art of Multiprocessor Programming

156

Example

[Link](x)

[Link](y)

[Link](y)
time
(5)

Art of Multiprocessor Programming

157

Theorem
Sequential Consistency is not a local property
(and thus we lose composability)

Art of Multiprocessor Programming

158

FIFO Queue Example

[Link](x) [Link](x) [Link](y)

time
Art of Multiprocessor Programming 159

FIFO Queue Example

[Link](x) [Link](x) [Link](y)

[Link](y)

[Link](y)

[Link](x)

time
Art of Multiprocessor Programming 160

FIFO Queue Example

[Link](x) [Link](x) [Link](y)

[Link](y)

[Link](y)

[Link](x)

History H
time
Art of Multiprocessor Programming 161

H|p Sequentially Consistent

[Link](x) [Link](x) [Link](y)

[Link](y)

[Link](y)

[Link](x)

time
Art of Multiprocessor Programming 162

H|q Sequentially Consistent

[Link](x) [Link](x) [Link](y)

[Link](y)

[Link](y)

[Link](x)

time
Art of Multiprocessor Programming 163

Ordering imposed by p

[Link](x)

[Link](x)

[Link](y) [Link](x)

[Link](y)

[Link](y)

time
Art of Multiprocessor Programming 164

Ordering imposed by q

[Link](x)

[Link](x)

[Link](y) [Link](x)

[Link](y)

[Link](y)

time
Art of Multiprocessor Programming 165

Ordering imposed by both

[Link](x)

[Link](x)

[Link](y) [Link](x)

[Link](y)

[Link](y)

time
Art of Multiprocessor Programming 166

Combining orders

[Link](x)

[Link](x)

[Link](y) [Link](x)

[Link](y)

[Link](y)

time
Art of Multiprocessor Programming 167

Fact
Most hardware architectures dont support sequential consistency Because they think its too strong Heres another story

Art of Multiprocessor Programming

168

The Flag Example

[Link](1) [Link](0) [Link](0)

[Link](1)

time
Art of Multiprocessor Programming 169

The Flag Example

[Link](1) [Link](0) [Link](0)

[Link](1)

Each threads view is sequentially consistent

It went first
time
Art of Multiprocessor Programming 170

The Flag Example

[Link](1) [Link](0) [Link](0)

[Link](1)

Entire history isnt sequentially consistent

Cant both go first
Art of Multiprocessor Programming 171

time

The Flag Example

[Link](1) [Link](0) [Link](0)

[Link](1)

Is this behavior really so wrong?

We can argue either way
time
Art of Multiprocessor Programming 172

Opinion1: Its Wrong

This pattern Is exactly the flag principle
Beloved of Alice and Bob Heart of mutual exclusion
Peterson Bakery, etc.

Write mine, read yours

Its non-negotiable!
Art of Multiprocessor Programming 173

Opinion2: But It Feels So Right

Many hardware architects think that sequential consistency is too strong Too expensive to implement in modern hardware OK if flag principle
violated by default Honored by explicit request

Art of Multiprocessor Programming

174

Memory Hierarchy
On modern multiprocessors, processors do not read and write directly to memory. Memory accesses are very slow compared to processor speeds, Instead, each processor reads and writes directly to a cache
Art of Multiprocessor Programming 175

Memory Operations
To read a memory location,
load data into cache.

To write a memory location

update cached copy, lazily write cached data back to memory

Art of Multiprocessor Programming

176

While Writing to Memory

A processor can execute hundreds, or even thousands of instructions Why delay on every memory write? Instead, write back in parallel with rest of the program.

Art of Multiprocessor Programming

177

Revisionist History
Flag violation history is actually OK
processors delay writing to memory until after reads have been issued.

Otherwise unacceptable delay between read and write instructions. Who knew you wanted to synchronize?

Art of Multiprocessor Programming

178

Who knew you wanted to synchronize?

Writing to memory = mailing a letter Vast majority of reads & writes
Not for synchronization No need to idle waiting for post office

If you want to synchronize

Announce it explicitly Pay for it only when you need it

Art of Multiprocessor Programming

179

Explicit Synchronization
Memory barrier instruction
Flush unwritten caches Bring caches up to date

Compilers often do this for you

Entering and leaving critical sections

Expensive

Art of Multiprocessor Programming

180

Volatile
In Java, can ask compiler to keep a variable up-to-date with volatile keyword Also inhibits reordering, removing from loops, & other optimizations

Art of Multiprocessor Programming

181

Real-World Hardware Memory

Weaker than sequential consistency But you can get sequential consistency at a price OK for expert, tricky stuff
assembly language, device drivers, etc.

Linearizability more appropriate for high-level software

Art of Multiprocessor Programming 182

Linearizability
Linearizability
Operation takes effect instantaneously between invocation and response Uses sequential specification, locality implies composablity Good for high level objects

Art of Multiprocessor Programming

183

Correctness: Linearizability
Sequential Consistency
Not composable Harder to work with Good way to think about hardware models

We will use linearizability as in the remainder of this course unless stated otherwise

Art of Multiprocessor Programming

184

Progress
We saw an implementation whose methods were lock-based (deadlockfree) We saw an implementation whose methods did not use locks (lock-free) How do they relate?

Art of Multiprocessor Programming

185

Progress Conditions
Deadlock-free: some thread trying to acquire the lock eventually succeeds. Starvation-free: every thread trying to acquire the lock eventually succeeds. Lock-free: some thread calling a method eventually returns. Wait-free: every thread calling a method eventually returns.

Art of Multiprocessor Programming

186

Progress Conditions
Non-Blocking Everyone makes progress Someone makes progress Blocking

Wait-free Lock-free

Starvation-free Deadlock-free

Art of Multiprocessor Programming

187

Summary
We will look at linearizable blocking and non-blocking implementations of objects.

Art of Multiprocessor Programming

188

This work is licensed under a Creative Commons AttributionShareAlike 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 [Link] 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.

Art of Multiprocessor Programming

189