Foundations of Shared Memory

1.

Foundations of Shared
Memory
Companion slides for
The Art of Multiprocessor Programming
by Maurice Herlihy, Nir Shavit, Victor
Luchangco, and Michael Spear

2.

Last Lecture
• Defined concurrent objects using
linearizability and sequential
consistency
• Fact: implemented linearizable objects
(Two thread FIFO Queue) in read-write
memory without mutual exclusion
• Fact: hardware does not provide
linearizable read-write memory
Art of Multiprocessor Programming
2

3.

Fundamentals
• What is the weakest form of
communication that supports mutual
exclusion?
• What is the weakest shared object that
allows shared-memory computation?
Art of Multiprocessor Programming
3

4.

Alan Turing
• Showed what is and is not computable on a
sequential machine.
• Still best model there is.
Art of Multiprocessor Programming
4

5.

Turing Computability
1
0 1 1 0 1 0
• Mathematical model of computation
• What is (and is not) computable
• Efficiency (mostly) irrelevant
Art of Multiprocessor Programming
5

6.

Shared-Memory
Computability?
Shared Memory
10011
• Mathematical model of concurrent computation
• What is (and is not) concurrently computable
• Efficiency (mostly) irrelevant
Art of Multiprocessor Programming
6

7.

Foundations of Shared Memory
To understand modern
multiprocessors we need to ask some
basic questions …
Art of Multiprocessor Programming
7

8.

Foundations of Shared Memory
To understand modern
What is the weakest useful form of
multiprocessors we need to ask some
shared memory?
basic questions …
Art of Multiprocessor Programming
8

9.

Foundations of Shared Memory
To understand modern
What is the weakest useful form of
multiprocessors
we can
needit to
ask some
What
do?
shared memory?
basic questions …
Art of Multiprocessor Programming
9

10.

Register*
Holds a
(binary) value
10011
* A memory location: name is historical
Art of Multiprocessor Programming
10

11.

Register
10011
Can be read
10011
Art of Multiprocessor Programming
11

12.

Register
Can be written
01100
10011
Art of Multiprocessor Programming
12

13.

Registers
public interface Register<T> {
public T read();
public void write(T v);
}
Art of Multiprocessor Programming
13

14.

Registers
public interface Register<T> {
public T read();
public void write(T v);
}
Type of register
(usually Boolean or m-bit Integer)
Art of Multiprocessor Programming
14

15.

Single-Reader/Single-Writer
Register
10011
01100
10011
Art of Multiprocessor Programming
15

16.

Multi-Reader/Single-Writer Register
10011
01100
10011
Art of Multiprocessor Programming
16

17.

Multi-Reader/Multi-Writer
Register
mumble
10011
10011
mumble
01010
mumble
10011
11011
Art of Multiprocessor Programming
17

18.

Jargon Watch
• SRSW
– Single-reader single-writer
• MRSW
– Multi-reader single-writer
• MRMW
– Multi-reader multi-writer
Art of Multiprocessor Programming
18

19.

Safe Register
write(1001)
OK if reads
and writes
don’t overlap
read(1001)
Art of Multiprocessor Programming
19

20.

Safe Register
write(1001)
Some valid value if
reads and writes do
overlap
read(????)
0000
1001
Art of Multiprocessor Programming
$*&v
1111
20

21.

Regular Register
write(0)
write(1)
read(1)
read(0)
• Single Writer
• Readers return:
– Old value if no overlap (safe)
– Old or one of new values if overlap
Art of Multiprocessor Programming
21

22.

Regular or Not?
write(0)
write(1)
read(1)
read(0)
Art of Multiprocessor Programming
22

23.

Regular or Not?
write(0)
write(1)
read(1)
read(0)
Overlap: returns new value
Art of Multiprocessor Programming
23

24.

Regular or Not?
write(0)
write(1)
read(0)
Overlap: returns old value
Art of Multiprocessor Programming
24

25.

Regular or Not?
write(0)
write(1)
read(1)
read(0)
Art of Multiprocessor Programming
25

26.

Regular ≠ Linearizable
write(0)
write(1)
read(1)
read(0)
can’t explain this!
write(1) already
happened
Art of Multiprocessor Programming
26

27.

Atomic Register
write(1001)
write(1010)
read(1001)
read(1010)
read(1010)
Linearizable to sequential safe
register
Art of Multiprocessor Programming
27

28.

Atomic Register
write(1001)
write(1010)
read(1001)
read(1010)
read(1010)
Art of Multiprocessor Programming
28

29.

Register Space
MRMW
MRSW
SRSW
m-valued
Boolean
Safe
Regular
Atomic
Art of Multiprocessor Programming
29

30.

Weakest Register
Single writer
1
Single reader
0 1
Safe Boolean register
Art of Multiprocessor Programming
30

31.

Weakest Register
Single writer
Single reader
0 1 0
flipflop
0 1 0
Get correct reading if not during state
transition
Art of Multiprocessor Programming
31

32.

Results
• From SRSW safe Boolean register
– All the other registers
– Mutual exclusion
• But not everything!
Foundations
of the field
– Consensus hierarchy
The really cool stuff …
Art of Multiprocessor Programming
32

33.

Locking within Registers
• Not interesting to rely on mutual exclusion
in register constructions
• We want registers to implement mutual
exclusion!
• It’s cheating to use mutual exclusion to
implement itself!
Art of Multiprocessor Programming
33

34.

Definition
An object implementation is wait-free if
every method call completes in a finite
number of steps
No mutual exclusion
– Thread could halt in critical section
– Build mutual exclusion from registers
Art of Multiprocessor Programming
34

35.

From Safe SRSW Boolean to
Atomic Snapshots
MRMW
MRSW
SRSW
M-valued
Boolean
Safe
Regular
Atomic
Snapshot
35
Art of Multiprocessor
Programming

36.

Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Art of Multiprocessor Programming
36

37.

Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Next
Art of Multiprocessor Programming
37

38.

Register Names
public class SafeBoolMRSWRegister
implements Register<Boolean> {
public boolean read() { … }
public void write(boolean x) { … }
}
Art of Multiprocessor Programming
38

39.

Register Names
public class SafeBoolMRSWRegister
implements Register<Boolean> {
public boolean read() { … }
public void write(boolean x) { … }
}
property
Art of Multiprocessor Programming
39

40.

Register Names
public class SafeBoolMRSWRegister
implements Register<Boolean> {
public boolean read() { … }
public void write(boolean x) { … }
}
property
type
Art of Multiprocessor Programming
40

41.

Register Names
public class SafeBoolMRSWRegister
implements Register<Boolean> {
public boolean read() { … }
public void write(boolean x) { … }
}
property
type
(3)
how many readers &
writers?
Art of Multiprocessor Programming
41

42.

Safe Boolean MRSW from
Safe Boolean SRSW
0
readers
0
0
zzz
0
0
0
0
writer
0
0
0
Art of Multiprocessor Programming
42

43.

Safe Boolean MRSW from
Safe Boolean SRSW
0
Let’s write 1!
0
0
0
0
0
0
0
0
0
Art of Multiprocessor Programming
43

44.

Safe Boolean MRSW from
Safe Boolean SRSW
0 or 1
0
0
1
0
0
0
0
0
0
Art of Multiprocessor Programming
44

45.

Safe Boolean MRSW from
Safe Boolean SRSW
1
0 or 1
0
1
0
1
0
0
0
0
Art of Multiprocessor Programming
45

46.

Safe Boolean MRSW from
Safe Boolean SRSW
1
1
0
1
0
1
0 or 1
0
0
0
1
Art of Multiprocessor Programming
46

47.

Safe Boolean MRSW from
Safe Boolean SRSW
1
Whew!
1
1
1
1
1
1
1
1
1
Art of Multiprocessor Programming
47

48.

Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements Register<Boolean> {
private SafeBoolSRSWRegister[] r =
new SafeBoolSRSWRegister[N];
public void write(boolean x) {
for (int j = 0; j < N; j++)
r[j].write(x);
}
public boolean read() {
int i = ThreadID.get();
return r[i].read();
}}
Art of Multiprocessor Programming
48

49.

Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private SafeBoolSRSWRegister[] r =
new SafeBoolSRSWRegister[N];
public void write(boolean x) {
for (int j = 0; j < N; j++)
r[j].write(x);
}
public boolean read() {
int i = ThreadID.get();
return r[i].read(); Each thread
}}
has own
safe SRSW register
Art of Multiprocessor Programming
49

50.

Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private SafeBoolSRSWRegister[] r =
new SafeBoolSRSWRegister[N];
public void write(boolean x) {
for (int j = 0; j < N; j++)
r[j].write(x);
}
public boolean read() {
int i = ThreadID.get();
return r[i].read();
write method
}}
Art of Multiprocessor Programming
50

51.

Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private SafeBoolSRSWRegister[] r =
new SafeBoolSRSWRegister[N];
public void write(boolean x) {
for (int j = 0; j < N; j++)
r[j].write(x);
}
public boolean read() {
Write each
int i = ThreadID.get();
thread’s register
return r[i].read();
one at a time
}}
Art of Multiprocessor Programming
51

52.

Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private SafeBoolSRSWRegister[] r =
new SafeBoolSRSWRegister[N];
public void write(boolean x) {
for (int j = 0; j < N; j++)
r[j].write(x);
read
}
public boolean read() {
int i = ThreadID.get();
return r[i].read();
}}
Art of Multiprocessor Programming
method
52

53.

Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private SafeBoolSRSWRegister[] r =
new SafeBoolSRSWRegister[N];
public void write(boolean x) {
for (int j = 0; j < N; j++)
r[j].write(x);
}
public boolean read() {
int i = ThreadID.get();
Read my own
return r[i].read();
register
}}
Art of Multiprocessor Programming
53

54.

Safe Multi-Valued MRSW from
Safe Multi-Valued SRSW?
1011
1011
1000
1011
1000
1011
any value in range
1000
1000
1000
Art of Multiprocessor Programming
54

55.

Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
Questions?
MRMW atomic
Atomic snapshot
Art of Multiprocessor Programming
55

56.

Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Art of Multiprocessor Programming
Next
56

57.

Regular Boolean MRSW from
Safe Boolean MRSW
0
1
10
1
0
01
Art of Multiprocessor Programming
57

58.

Regular Boolean MRSW from
Safe Boolean MRSW
0
1
Uh, oh!
10
0
0
01
Art of Multiprocessor Programming
58

59.

Regular Boolean MRSW from
Safe Boolean MRSW
0
0
0
Last
written:
0
0
0
Art of Multiprocessor Programming
59

60.

Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register<Boolean> {
private boolean old;
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) {
value.write(x);
old = x;
}}
public boolean read() {
return value.read();
}}
Art of Multiprocessor Programming
60

61.

Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register<Boolean> {
threadLocal boolean old;
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) {
value.write(x);
old = x;
Last bit this thread
}}
(made-up syntax)
public boolean read() {
return value.read();
}}
Art of Multiprocessor Programming
wrote
61

62.

Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register<Boolean> {
threadLocal boolean old;
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) {
value.write(x);
old = x;
}}
public boolean read() {
return value.read();
Actual value
}}
Art of Multiprocessor Programming
62

63.

Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register<Boolean> {
threadLocal boolean old;
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) {
value.write(x);
old = x;
Is new value different
}}
last value I wrote?
public boolean read()from
{
return value.read();
}}
Art of Multiprocessor Programming
63

64.

Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register<Boolean> {
threadLocal boolean old;
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) {
value.write(x);
old = x;
}}
public boolean read() {
If so, change it
return value.read();
}}
(otherwise don’t!)
Art of Multiprocessor Programming
64

65.

Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register<Boolean>{
threadLocal boolean old;
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) { Overlap? What overlap?
value.write(x);
No problem
old = x;
either Boolean value works
}}
public boolean read() {
return value.read();
}}
Art of Multiprocessor Programming
65

66.

Regular Multi-Valued MRSW from
Safe Multi-Valued MRSW?
0101
0101
0101
Safe register can
return any value in
range when value
changes
Art of Multiprocessor Programming
Regular register can
return only old or new
when value changes
66

67.

Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Questions?
Atomic snapshot
Art of Multiprocessor Programming
67

68.

Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Art of Multiprocessor Programming
Next
68

69.

Representing m Values
Unary representation:
bit[i] means value i
11 0 0 0 0 0 0
Initially 0
01234567
Art of Multiprocessor Programming
69

70.

Writing m-Valued Register
Write 5
1 0 0 0 0
01234567
Art of Multiprocessor Programming
70

71.

Writing m-Valued Register
Write 5
Initially 0
0
1 0 0 0 1
01234567
Art of Multiprocessor Programming
71

72.

Writing m-Valued Register
Write 5
0
0
1 0 0 0 1
5
01234567
Art of Multiprocessor Programming
72

73.

MRSW Regular m-valued from
MRSW Regular Boolean
public class RegMRSWRegister implements Register{
RegBoolMRSWRegister[M] bit;
public void write(int x) {
this.bit[x].write(true);
for (int i=x-1; i>=0; i--)
this.bit[i].write(false);
}
public int read() {
for (int i=0; i < M; i++)
if (this.bit[i].read())
return i;
}}
Art of Multiprocessor Programming
73

74.

MRSW Regular m-valued from
MRSW Regular Boolean
public class RegMRSWRegister implements Register{
RegBoolMRSWRegister[M] bit;
public void write(int x) {
bit[x].write(true);
for (int i=x-1; i>=0; i--)
bit[i].write(false);
}
Unary representation:
bit[i] means value i
public int read() {
for (int i=0; i < M; i++)
if (bit[i].read())
return i;
}}
Art of Multiprocessor Programming
74

75.

MRSW Regular m-valued from
MRSW Regular Boolean
public class RegMRSWRegisterimplements Register {
RegBoolMRSWRegister[m] bit;
public void write(int x) {
bit[x].write(true);
for (int i=x-1; i>=0; i--)
bit[i].write(false);
}
public int read() {
for (int i=0; i < M; i++)
if (bit[i].read())
return i;
}}
set bit x
Art of Multiprocessor Programming
75

76.

MRSW Regular m-valued from
MRSW Regular Boolean
public class RegMRSWRegisterimplements Register {
RegBoolMRSWRegister[m] bit;
public void write(int x) {
bit[x].write(true);
for (int i=x-1; i>=0; i--)
bit[i].write(false);
}
public int read() {
for (int i=0; i < M; i++)
if (bit[i].read())
return i;
}}
Clear bits
from higher
to lower
Art of Multiprocessor Programming
76

77.

MRSW Regular m-valued from
MRSW Regular Boolean
public class RegMRSWRegisterimplements Register {
RegBoolMRSWRegister[m] bit;
public void write(int x) {
bit[x].write(true);
for (int i=x-1; i>=0; i--)
bit[i].write(false);
}
Scan from lower
to higher & return
first bit set
public int read() {
for (int i=0; i < M; i++)
if (bit[i].read())
return i;
}}
Art of Multiprocessor Programming
77

78.

Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Questions?
Atomic snapshot
Art of Multiprocessor Programming
78

79.

Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Art of Multiprocessor Programming
79

80.

Road Map (Slight Detour)
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
SRSW Atomic
MRSW atomic
MRMW atomic
Atomic snapshot
Art of Multiprocessor Programming
80

81.

SRSW Atomic From SRSW
Regular
Regular writer
1234
5678
Concurrent
Reading
1234
Regular
reader
Instead of 5678…
When is this a problem?
Art of Multiprocessor Programming
81

82.

SRSW Atomic From SRSW
Regular
Regular writer
1234
5678
Initially
1234
5678
Regular
reader
write(5678)
read(5678)
time
Art of Multiprocessor Programming
82

83.

SRSW Atomic From SRSW
Regular
Regular writer
1234
5678
1234
Regular
reader
Instead of 5678…
Initially
1234
write(5678)
read(1234)
time
Art of Multiprocessor Programming
83

84.

SRSW Atomic From SRSW
Regular
Regular writer
1234
5678
1234
Regular
reader
Instead of 5678…
Initially
1234
write(5678)
Reg read(5678)
Write
time5678
happened
read(1234)
Art of Multiprocessor Programming
84

85.

Timestamped Values
1234
1234
1:45
1:45
5678
5678
2:00
2:00
Writer writes
value and stamp
together
2:00
5678
Reader saves last
value & stamp read
returns new value only
if stamp is higher
Art of Multiprocessor Programming
85

86.

SRSW Atomic From SRSW
Regular
writer
reader
1:45
2:00
1234
5678
1:45 1234 < 2:00 5678
So stick with 5678
write(2:00 5678)
1:45 1234
read(2:00 5678)
read(1:45 1234)
time
Art of Multiprocessor Programming
86

87.

Atomic Single-Reader to Atomic
Multi-Reader
stamp
value
1:45
1:45
1:45
1:45
1234
1234
1234
1234
One per reader
Art of Multiprocessor Programming
87

88.

Another Scenario
Writer starts
write…
stamp
value
2:00
1:45
1:45
1:45
5678
1234
1234
1234
Art of Multiprocessor Programming
88

89.

Another Scenario
2:00, 5678
zzz…
stamp
value
2:00
1:45
1:45
1:45
5678
1234
1234
1234
reader
reads
later
reader
1:45 1234
Yellow was completely after Blue but
read earlier value…not linearizable!
Art of Multiprocessor Programming
89

90.

Multi-Reader Redux
one per thread
1
1:45
1:45
1:45
2
1234
1234
1234
1:45
1:45
1:45
3
1234
1234
1234
Art of Multiprocessor Programming
1:45
1:45
1:45
1234
1234
1234
1
2
3
90

91.

Writer writes
column…
2:00, 5678
Multi-Reader Redux
reader
reads row
1
1
1:45
2:00
1:45
2:00
2:00
1:45
2
1234
5678
1234
5678
5678
1234
1:45
1:45
1:45
2
3
1234
1234
1234
Art of Multiprocessor Programming
1:45
1:45
1:45
1234
1234
1234
1
2
3
91

92.

2:00, 5678
Multi-Reader Redux
zzz…after
second write
1
reader writes column to
notify others of what it
2
read
1
2
3
1:45
1234
1:45
1234
2:00
5678
1:45
1234 1
2:00
5678
1:45
1234
1:45
1234
2:00
5678
1:45
1234 2
2:00
5678
1:45
1234
2:00
1:45
5678
1234
1:45
1234 3
Yellow reader will read new value
in column written by earlier Blue
reader
Art of Multiprocessor Programming
92

93.

Can’t Yellow Miss Blue’s Update?
… Only if Readers Overlap…
1:45
1234
write(2:00 5678)
read(2:00 5678)
read(1:45 1234)
In
which case its
time
OK to read 1234
Art of Multiprocessor Programming
93

94.

Bad Case Only When Readers
Don’t Overlap
1:45
1234
write(2:00 5678)
read(2:00 5678)
In which case Blue will
complete writing 2:00
5678 to its
column
read(2:00 5678)
time
Art of Multiprocessor Programming
94

95.

Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
Next
MRMW atomic
Atomic snapshot
Art of Multiprocessor Programming
95

96.

Multi-Writer Atomic From MultiReader Atomic
Each writer
reads all
then writes
Max+1
to its register
stamp
value
1:45
1:45
2:00
1:45
2:15
1:45
1234
1234
5678
1234
XYZW
1234
Readers read all
and take max
(Lexicographic
like Bakery)
Max is 2:15,
return XYZW
Art of Multiprocessor Programming
96

97.

Atomic Execution
Means it is Linearizable
write(1)
Read(max= 2)
write(2)
Read (max = 1)
write(3)
write(2)
write(4)
Read(max = 3)
Read(max = 4)
time
time
Art of Multiprocessor Programming
97

98.

Linearization Points
write(1)
Read(max= 2)
write(2)
Read (max = 1)
write(3)
write(2)
write(4)
Read(max = 3)
Read(max = 4)
time
time
Art of Multiprocessor Programming
98

99.

Linearization Points
Look at Writes
First
write(1)
write(4)
write(2)
write(3)
write(2)
time
time
Art of Multiprocessor Programming
99

100.

Linearization Points
Order writes by
TimeStamp
write(1)
write(4)
write(2)
write(3)
write(2)
time
time
Art of Multiprocessor Programming
100

101.

Linearization Points
Order reads by
max stamp read
write(1)
Read(max= 2)
write(2)
Read (max = 1)
write(3)
write(2)
write(4)
Read(max = 3)
Read(max = 4)
time
time
Art of Multiprocessor Programming
101

102.

Linearization Points
Order reads by
max stamp read
write(1)
Read(max= 2)
write(2)
Read (max = 1)
write(3)
write(2)
write(4)
Read(max = 3)
Read(max = 4)
time
time
Art of Multiprocessor Programming
102

103.

Linearization Points
The linearization point depends on the
execution (not a line in the code)!
write(1)
Read(max= 2)
write(2)
Read (max = 1)
write(3)
write(2)
write(4)
Read(max = 3)
Read(max = 4)
time
time
Art of Multiprocessor Programming
103

104.

Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
Questions?
MRMW atomic
Atomic snapshot
Art of Multiprocessor Programming
104

105.

Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Next
Atomic snapshot
Art of Multiprocessor Programming
105

106.

Atomic Snapshot
update
Art of Multiprocessor Programming
scan
106

107.

Atomic Snapshot
• Array of SWMR atomic registers
• Take instantaneous snapshot of all
• Generalizes to MRMW registers …
Art of Multiprocessor Programming
107

108.

Snapshot Interface
public interface Snapshot {
public int update(int v);
public int[] scan();
}
Art of Multiprocessor Programming
108

109.

Snapshot Interface
Thread i writes v to its register
public interface Snapshot {
public int update(int v);
public int[] scan();
}
Art of Multiprocessor Programming
109

110.

Snapshot Interface
Instantaneous snapshot of all theads’ registers
public interface Snapshot {
public int update(int v);
public int[] scan();
}
Art of Multiprocessor Programming
110

111.

Atomic Snapshot
• Collect
– Read values one at a time
• Problem
– Incompatible concurrent collects
– Result not linearizable
Art of Multiprocessor Programming
111

112.

Clean Collects
• Clean Collect
– Collect during which nothing changed
– Can we make it happen?
– Can we detect it?
Art of Multiprocessor Programming
112

113.

Simple Snapshot
Put increasing labels on each entry
Collect
twice
Problem:
Scanner might not be
collecting
If both
agree, a snapshot!
– We’re done
• Otherwise,
– Try again
Collect 2
Collect 1
x
x
y
z
y
z
w
=
w
r
r
z
x
z
x
Art of Multiprocessor Programming
113

114.

Claim: WeBut
Must
Usesees
Labels
scanner
x and z
together!
x
z
x
z
Scanner
x
y
x
y
Updater
z
w
z
Updater
time
x and z are never
in memory
together 114
Art of Multiprocessor Programming

115.

Scanner reads x and z with
Must
Use
Labels
different labels and recognizes
collect not clean
1,x
1,z
3,x
3,z
Scanner
1,x
2,y
3,x
4,y
Updater
1,z
2,w
3,z
Updater
time
Art of Multiprocessor Programming
115

116.

Simple Snapshot
• Collect twice
• If both agree,
– We’re done
• Otherwise,
– Try again
Collect 2
Collect 1
1
1
22
1
22
1
7
=
7
13
13
18
12
18
12
Art of Multiprocessor Programming
116

117.

Simple Snapshot: Update
public class SimpleSnapshot implements Snapshot {
private AtomicMRSWRegister[] register;
public void update(int value) {
int i = Thread.myIndex();
LabeledValue oldValue = register[i].read();
LabeledValue newValue =
new LabeledValue(oldValue.label+1, value);
register[i].write(newValue);
}
Art of Multiprocessor Programming
117

118.

Simple Snapshot: Update
public class SimpleSnapshot implements Snapshot {
private AtomicMRSWRegister[] register;
public void update(int value) {
int i = Thread.myIndex();
LabeledValue oldValue = register[i].read();
LabeledValue newValue =
new LabeledValue(oldValue.label+1, value);
register[i].write(newValue);
}
One single-writer register per thread
Art of Multiprocessor Programming
118

119.

Simple Snapshot: Update
public class SimpleSnapshot implements Snapshot {
private AtomicMRSWRegister[] register;
public void update(int value) {
int i = Thread.myIndex();
LabeledValue oldValue = register[i].read();
LabeledValue newValue =
new LabeledValue(oldValue.label+1, value);
register[i].write(newValue);
}
Write each time with higher label
Art of Multiprocessor Programming
119

120.

Simple Snapshot: Collect
private LabeledValue[] collect() {
LabeledValue[] copy =
new LabeledValue[n];
for (int j = 0; j < n; j++)
copy[j] = this.register[j].read();
return copy;
}
Art of Multiprocessor Programming
120

121.

Simple Snapshot
private LabeledValue[] collect() {
LabeledValue[] copy =
new LabeledValue[n];
for (int j = 0; j < n; j++)
copy[j] = this.register[j].read();
return copy;
}
Just read each register into array
Art of Multiprocessor Programming
121

122.

Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();
collect: while (true) {
newCopy = collect();
if (!equals(oldCopy, newCopy)) {
oldCopy = newCopy;
continue collect;
}
return getValues(newCopy);
}}
Art of Multiprocessor Programming
122

123.

Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy; Collect
oldCopy = collect();
collect: while (true) {
newCopy = collect();
if (!equals(oldCopy, newCopy)) {
oldCopy = newCopy;
continue collect;
}
return getValues(newCopy);
}}
Art of Multiprocessor Programming
once
123

124.

Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy; Collect
oldCopy = collect();
collect: while (true) {
newCopy = collect();
if (!equals(oldCopy, newCopy)) {
oldCopy = newCopy;
continue collect;
}
return getValues(newCopy);
}}
once
Collect twice
Art of Multiprocessor Programming
124

125.

Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy; Collect once
oldCopy = collect();
collect: while (true) {
newCopy = collect();
if (!equals(oldCopy, newCopy)) {
oldCopy = newCopy;
continue collect;
}
On mismatch,
return getValues(newCopy);
}}
Collect twice
try again
Art of Multiprocessor Programming
125

126.

Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy; Collect once
oldCopy = collect();
collect: while (true) {
newCopy = collect();
if (!equals(oldCopy, newCopy)) {
oldCopy = newCopy;
continue collect;
values
}
return getValues(newCopy);
}}
Collect twice
On match, return
Art of Multiprocessor Programming
126

127.

Simple Snapshot
• Linearizable
• Update is wait-free
– No unbounded loops
• But Scan can starve
– If interrupted by concurrent update
Art of Multiprocessor Programming
127

128.

Wait-Free Snapshot
• Add a scan before every update
• Write resulting snapshot together with
update value
• If scan is continuously interrupted by
updates, scan can take the update’s
snapshot
Art of Multiprocessor Programming
128

129.

Wait-free Snapshot
If A’s scan observes that B moved
twice, then B completed an update
while A’s scan was in progress
Collect
Collect
Collect
26
24
12
26
24
12
26
24
12
≠
≠
Update
B
time
Art of Multiprocessor Programming
129

130.

Wait-free Snapshot
Collect
Collect
Collect
26
24
12
26
24
12
26
24
12
A
B
≠
≠
Update
time
Art of Multiprocessor Programming
130

131.

Wait-free Snapshot
Collect
Collect
Collect
26
24
12
26
24
12
≠
26
24
12
Scan
Write
A
B
≠
Update
time
Art of Multiprocessor Programming
131

132.

Wait-free Snapshot
B’s 1st update must have written during 1st collect
Collect
Collect
Collect
26
24
12
26
24
12
≠
26
24
12
Scan
Write
A
Scan
B
≠
Write
So A can steal
result of B’s scan
So scan of B’s second update must
be within interval of A’s scan
time
Update
Art of Multiprocessor Programming
132

133.

Wait-free Snapshot
Collect
Collect
Collect
26
24
12
26
24
12
≠
26
24
12
Scan
Write
A
Scan
B
≠
Write
But no guarantee that scan
of B’s 1st update can be used…
Why?
time
Art of Multiprocessor Programming
133

134.

Once is not Enough
Collect
Collect
26
24
12
26
24
12
A
B
Scan
time
Update
≠
Write
Why can’t A steal B’s scan?
Update
Because another update
might have interfered
before the scan
Art of Multiprocessor Programming
134

135.

Someone Must Move Twice
Collect
Collect
Collect
26
24
12
26
24
12
26
24
12
≠
≠
Update
B
time
If we collect n times…some thread
must move twice (pigeonhole principle)
Art of Multiprocessor Programming
135

136.

Scan is Wait-free
scan
At
most
n-1
depth
update
scan
update
scan
So some thread must
have had clean collect
Art of Multiprocessor Programming
136

137.

Wait-Free Snapshot Label
public class SnapValue {
public int
label;
public int
value;
public int[] snap;
}
Art of Multiprocessor Programming
137

138.

Wait-Free Snapshot Label
public class SnapValue {
public int
label;
public int
value;
public int[] snap;
}
Counter incremented
with each snapshot
Art of Multiprocessor Programming
138

139.

Wait-Free Snapshot Label
public class SnapValue {
public int
label;
public int
value;
public int[] snap;
}
Actual value
Art of Multiprocessor Programming
139

140.

Wait-Free Snapshot Label
public class SnapValue {
public int
label;
public int
value;
public int[] snap;
}
most recent snapshot
Art of Multiprocessor Programming
140

141.

Wait-Free Snapshot Label
11011110101000101100…00
label
value
Art of Multiprocessor Programming
Last
snapshot
141

142.

Wait-free Update
public void update(int value) {
int i = Thread.myIndex();
int[] snap = this.scan();
SnapValue oldValue = r[i].read();
SnapValue newValue =
new SnapValue(oldValue.label+1,
value, snap);
r[i].write(newValue);
}
Art of Multiprocessor Programming
142

143.

Wait-free Scan
public void update(int value) {
int i = Thread.myIndex();
Take scan
int[] snap = this.scan();
SnapValue oldValue = r[i].read();
SnapValue newValue =
new SnapValue(oldValue.label+1,
value, snap);
r[i].write(newValue);
}
Art of Multiprocessor Programming
143

144.

Wait-free Scan
public void update(int value) {
int i = Thread.myIndex();
Take scan
int[] snap = this.scan();
SnapValue oldValue = r[i].read();
SnapValue newValue =
new SnapValue(oldValue.label+1,
value, snap);
r[i].write(newValue);
Label value with scan
}
Art of Multiprocessor Programming
144

145.

Wait-free Scan
public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved = new boolean[n];
oldCopy = collect();
collect: while (true) {
newCopy = collect();
for (int j = 0; j < n; j++) {
if (oldCopy[j].label != newCopy[j].label) {
…
}}
return getValues(newCopy);
}}}
Art of Multiprocessor Programming
145

146.

Wait-free Scan
public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved = new boolean[n];
oldCopy = collect();
collect: while (true) {
newCopy = collect();
for (int j = 0; j < n; j++) {
if (oldCopy[j].label != newCopy[j].label) {
…
Keep track of who moved
}}
return getValues(newCopy);
}}}
Art of Multiprocessor Programming
146

147.

Wait-free Scan
public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved = new boolean[n];
oldCopy = collect();
collect: while (true) {
newCopy = collect();
for (int j = 0; j < n; j++) {
if (oldCopy[j].label != newCopy[j].label) {
…
}}
return getValues(newCopy);
}}}
Repeated double collect
Art of Multiprocessor Programming
147

148.

Wait-free Scan
public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved = new boolean[n];
oldCopy = collect();
collect: while (true) {
newCopy = collect();
for (int j = 0; j < n; j++) {
if (oldCopy[j].label != newCopy[j].label) {
…
}}
return getValues(newCopy);
}}}
If mismatch detected…
Art of Multiprocessor Programming
148

149.

Mismatch Detected
if (oldCopy[j].label != newCopy[j].label) {
if (moved[j]) {
// second move
return newCopy[j].snap;
} else {
moved[j] = true;
oldCopy = newCopy;
continue collect;
}}}
return getValues(newCopy);
}}}
Art of Multiprocessor Programming
149

150.

Mismatch Detected
if (oldCopy[j].label != newCopy[j].label) {
if (moved[j]) {
return newCopy[j].snap;
} else {
moved[j] = true;
oldCopy = newCopy;
continue collect;
If thread moved twice,
}}}
just steal its second
return getValues(newCopy);
snapshot
}}}
Art of Multiprocessor Programming
150

151.

Mismatch Detected
if (oldCopy[j].label != newCopy[j].label) {
if (moved[j]) {
// second move
return newCopy[j].snap;
} else {
moved[j] = true;
Remember that
oldCopy = newCopy;
thread moved
continue collect;
}}}
return getValues(newCopy);
}}}
Art of Multiprocessor Programming
151

152.

Observations
• Uses unbounded counters
– can be replaced with 2 bits
• Assumes SWMR registers
– for labels
– can be extended to MRMW
Art of Multiprocessor Programming
152

153.

Summary
• We saw we could implement MRMW multi
valued snapshot objects
• From SRSW binary safe registers (simple
flipflops)
• But what is the next step to attempt with
read-write registers?
Art of Multiprocessor Programming
153

154.

Grand Challenge
• Snapshot means
– Write any one array element
– Read multiple array elements
Art of Multiprocessor Programming
154

155.

Grand Challenge
What about
atomic writes to
multiple
locations?
Writes to
0 and 1
Writes to
1 and 2
Write many and
snapshot
Art of Multiprocessor Programming
155

156.

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
– 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.
Art of Multiprocessor Programming
156