Foundations of Shared Memory
Foundations of Shared Memory Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit Art of Multiprocessor Programming
Last Lecture
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
Fundamentals
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
Alan Turing
4 Alan Turing Showed what is and is not computable on a sequential machine. Still best model there is. Art of Multiprocessor Programming
5 Turing Computability Mathematical model of computation What is (and is not) computable Efficiency (mostly) irrelevant 0 1 1 0 1 0 1 Art of Multiprocessor Programming
6 Shared-Memory Computability? Mathematical model of concurrent computation What is (and is not) concurrently computable Efficiency (mostly) irrelevant 10011 Shared Memory Art of Multiprocessor Programming
Foundations of Shared Memory
7 Foundations of Shared Memory To understand modern multiprocessors we need to ask some basic questions … Art of Multiprocessor Programming
Foundations of Shared Memory
8 Foundations of Shared Memory To understand modern multiprocessors we need to ask some basic questions … What is the weakest useful form of shared memory? Art of Multiprocessor Programming
Foundations of Shared Memory
9 Foundations of Shared Memory To understand modern multiprocessors we need to ask some basic questions … What is the weakest useful form of shared memory? What can it do? Art of Multiprocessor Programming
Register*
10 Register* 10011 Holds a (binary) value * A memory location: name is historical Art of Multiprocessor Programming
Register
11 Register Can be read 10011 Art of Multiprocessor Programming 10011
Register
10011 12 Register Can be written 01100 Art of Multiprocessor Programming
Registers
13 public interface Register<T> { public T read(); public void write(T v); } Registers Art of Multiprocessor Programming
Registers
14 public interface Register <T> { public T read(); public void write( T v ); } Registers Type of register (usually Boolean or m -bit Integer) Art of Multiprocessor Programming
Single-Reader/Single-Writer Register
10011 15 Single-Reader/Single-Writer Register 01100 10011 Art of Multiprocessor Programming
Multi-Reader/Single-Writer Register
16 Multi-Reader/Single-Writer Register 10011 Art of Multiprocessor Programming 10011 01100
Multi-Reader/Multi-Writer Register
10011 17 mumble mumble 11011 Multi-Reader/Multi-Writer Register mumble 10011 10011 01010 Art of Multiprocessor Programming
Jargon Watch
18 Jargon Watch SRSW Single-reader single-writer MRSW Multi-reader single-writer MRMW Multi-reader multi-writer Art of Multiprocessor Programming
Safe Register
19 Safe Register write( 1001 ) read( 1001 ) OK if reads and writes don’t overlap Art of Multiprocessor Programming
Safe Register
20 Safe Register write( 1001 ) Some valid value if reads and writes do overlap read( ???? ) 0000 1001 1111 $*&v Art of Multiprocessor Programming
Regular Register
21 Regular Register write( 0 ) read( 1 ) write( 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
Regular or Not?
22 Regular or Not? write( 0 ) read( 1 ) write( 1 ) read( 0 ) Art of Multiprocessor Programming
Regular or Not?
23 Regular or Not? write( 0 ) read( 1 ) write( 1 ) read(0) Overlap: returns new value Art of Multiprocessor Programming
Regular or Not?
24 Regular or Not? write( 0 ) write( 1 ) read( 0 ) Overlap: returns old value Art of Multiprocessor Programming
Regular or Not?
25 Regular or Not? write( 0 ) read( 1 ) write( 1 ) read( 0 ) regular Art of Multiprocessor Programming
Regular ≠ Linearizable
26 Regular ≠ Linearizable write( 0 ) read( 1 ) write( 1 ) read( 0 ) write(1) already happened can’t explain this! Art of Multiprocessor Programming
Atomic Register
27 Atomic Register write( 1001 ) read( 1001 ) Linearizable to sequential safe register write( 1010 ) read( 1010 ) read( 1010 ) Art of Multiprocessor Programming
Atomic Register
28 Atomic Register write(1001) read(1001) write(1010) read(1010) read(1010) Art of Multiprocessor Programming
Register Space
29 Register Space MRMW MRSW SRSW Safe Regular Atomic m -valued Boolean Art of Multiprocessor Programming
Weakest Register
30 Weakest Register 1 0 1 Single reader Single writer Safe Boolean register Art of Multiprocessor Programming
Weakest Register
31 Weakest Register Single reader Single writer Get correct reading if not during state transition flipflop 0 1 0 0 1 0 Art of Multiprocessor Programming
Results
32 Results From SRSW safe Boolean register All the other registers Mutual exclusion But not everything! Consensus hierarchy Foundations of the field The really cool stuff … Art of Multiprocessor Programming
Locking within Registers
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
Definition
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
From Safe SRSW Boolean to Atomic Snapshots
Art of Multiprocessor Programming 35 From Safe SRSW Boolean to Atomic Snapshots MRMW MRSW SRSW Saf e Regular Atomic M-valued Boolean Snapshot
Road Map
36 Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW atomic Atomic snapshot Art of Multiprocessor Programming
Road Map
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
Register Names
38 public class SafeBoolMRSWRegister implements Register< Boolean > { public boolean read() { … } public void write( boolean x) { … } } Register Names Art of Multiprocessor Programming
Register Names
39 public class SafeBoolMRSWRegister implements Register<Boolean> { public boolean read() { … } public void write(boolean x) { … } } Register Names property Art of Multiprocessor Programming
Register Names
40 public class SafeBoolMRSWRegister implements Register<Boolean> { public boolean read() { … } public void write(boolean x) { … } } Register Names property type Art of Multiprocessor Programming
Register Names
41 public class SafeBoolMRSWRegister implements Register<Boolean> { public boolean read() { … } public void write(boolean x) { … } } (3) Register Names property type how many readers & writers? Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
42 Safe Boolean MR SW from Safe Boolean SR SW 0 0 0 0 0 0 0 0 0 0 0 zzz readers writer Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
43 Safe Boolean MRSW from Safe Boolean SRSW 0 0 0 0 0 0 0 0 0 0 0 Let’s write 1! Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
44 Safe Boolean MRSW from Safe Boolean SRSW 0 or 1 1 0 0 0 0 0 0 0 0 0 Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
45 Safe Boolean MRSW from Safe Boolean SRSW 1 0 or 1 1 0 0 0 0 0 0 0 1 Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
46 Safe Boolean MRSW from Safe Boolean SRSW 1 1 1 1 0 or 1 0 0 0 0 0 1 Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
47 Safe Boolean MRSW from Safe Boolean SRSW 1 1 1 1 1 1 1 1 1 1 Whew! Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
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
Safe Boolean MRSW from Safe Boolean SRSW
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
Safe Boolean MRSW from Safe Boolean SRSW
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
Safe Boolean MRSW from Safe Boolean SRSW
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() { int i = ThreadID.get(); return r[i].read(); }} Write each thread’s register one at a time Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
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); } public boolean read() { int i = ThreadID.get(); return r[i].read(); }} read method Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
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(); return r[i].read(); }} Read my own register Art of Multiprocessor Programming
Safe Multi-Valued MRSW from Safe Multi-Valued SRSW?
54 1000 1000 1000 Safe Multi-Valued MRSW from Safe Multi-Valued SRSW? 1011 1011 1011 any value in range 1000 1000 Yes, it works! 1011 Art of Multiprocessor Programming
Road Map
55 Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW atomic Atomic snapshot Questions? Art of Multiprocessor Programming
Road Map
56 Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW atomic Atomic snapshot Next Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
57 Regular Boolean MRSW from Safe Boolean MRSW 0 0 0 1 0 1 1 1 Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
58 Regular Boolean MRSW from Safe Boolean MRSW 0 0 0 0 0 1 1 1 Art of Multiprocessor Programming Uh, oh!
Regular Boolean MRSW from Safe Boolean MRSW
59 Regular Boolean MRSW from Safe Boolean MRSW 0 0 0 0 0 Last written: 0 Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
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
Regular Boolean MRSW from Safe Boolean MRSW
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; }} public boolean read() { return value.read(); }} Last bit this thread wrote (made-up syntax) Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
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
Regular Boolean MRSW from Safe Boolean MRSW
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; }} public boolean read() { return value.read(); }} Is new value different from last value I wrote? Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
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() { return value.read(); }} If so, change it (otherwise don’t!) Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
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) { value.write(x); old = x; }} public boolean read() { return value.read(); }} Overlap? What overlap ? No problem either Boolean value works Art of Multiprocessor Programming
Regular Multi-Valued MRSW from Safe Multi-Valued MRSW?
66 Regular Multi-Valued MRSW from Safe Multi-Valued MRSW ? 0101 0101 Does not work! 0101 Art of Multiprocessor Programming Safe register can return any value in range when value changes Regular register can return only old or new when value changes
Road Map
67 Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW atomic Atomic snapshot Questions? Art of Multiprocessor Programming
Road Map
68 Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW atomic Atomic snapshot Next Art of Multiprocessor Programming
Representing m Values
69 Representing m Values 0 1 2 3 4 5 6 7 1 0 0 0 0 1 Initially 0 Unary representation: bit[i] means value i 0 0 Art of Multiprocessor Programming
Writing m-Valued Register
70 Writing m -Valued Register 1 0 0 0 0 1 Write 5 Art of Multiprocessor Programming 0 1 2 3 4 5 6 7
Writing m-Valued Register
71 Writing m -Valued Register 1 1 0 0 0 0 Write 5 Initially 0 Art of Multiprocessor Programming 0 1 2 3 4 5 6 7
Writing m-Valued Register
0 1 2 3 4 5 6 7 72 Writing m -Valued Register 1 1 0 0 0 0 Write 5 5 0 Art of Multiprocessor Programming
MRSW Regular m-valued from MRSW Regular Boolean
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
MRSW Regular m-valued from MRSW Regular Boolean
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); } public int read() { for (int i=0; i < M; i++) if (bit[i].read()) return i; }} Unary representation: bit[i] means value i Art of Multiprocessor Programming
MRSW Regular m-valued from MRSW Regular Boolean
75 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); } public int read() { for (int i=0; i < M; i++) if (bit[i].read()) return i; }} set bit x Art of Multiprocessor Programming
MRSW Regular m-valued from MRSW Regular Boolean
76 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 ); } 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
MRSW Regular m-valued from MRSW Regular Boolean
77 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); } public int read() { for ( int i=0; i < M; i++) if (bit[i].read()) return i; }} Scan from lower to higher & return first bit set Art of Multiprocessor Programming
Road Map
78 Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW atomic Atomic snapshot Questions? Art of Multiprocessor Programming
Road Map
79 Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW atomic Atomic snapshot Art of Multiprocessor Programming
Road Map (Slight Detour)
80 Road Map (Slight Detour) SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW atomic Atomic snapshot SRSW Atomic Art of Multiprocessor Programming
SRSW Atomic From SRSW Regular
Concurrent Reading 81 SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 1234 5678 Instead of 5678 When is this a problem ? Art of Multiprocessor Programming
SRSW Atomic From SRSW Regular
82 SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 5678 5678 time write( 5678 ) read( 5678 ) Initially 1234 Art of Multiprocessor Programming Same as Atomic
SRSW Atomic From SRSW Regular
83 SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 1234 5678 Instead of 5678… time write( 5678 ) read( 1234 ) Initially 1234 Same as Atomic Art of Multiprocessor Programming
SRSW Atomic From SRSW Regular
84 SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 1234 5678 Instead of 5678… time write( 5678 ) read( 1234 ) Initially 1234 Reg read( 5678 ) not Atomic! Write 5678 happened Art of Multiprocessor Programming
Timestamped Values
85 Timestamped Values Writer writes value and stamp together Reader saves last value & stamp read returns new value only if stamp is higher 1234 1:45 5678 2:00 5678 2:00 Art of Multiprocessor Programming 1234 1:45 5678 2:00
SRSW Atomic From SRSW Regular
86 SRSW Atomic From SRSW Regular writer reader 1:45 1234 < 2:00 5678 So stick with 5678