Slaidy.com- Foundations of Shared Memory
Содержание
- 2. Last Lecture Defined concurrent objects using linearizability and sequential consistency Fact: implemented linearizable objects (Two thread
- 3. Fundamentals What is the weakest form of communication that supports mutual exclusion? What is the weakest
- 4. Alan Turing Showed what is and is not computable on a sequential machine. Still best model
- 5. Turing Computability Mathematical model of computation What is (and is not) computable Efficiency (mostly) irrelevant 1
- 6. Shared-Memory Computability? Mathematical model of concurrent computation What is (and is not) concurrently computable Efficiency (mostly)
- 7. Foundations of Shared Memory To understand modern multiprocessors we need to ask some basic questions …
- 8. Foundations of Shared Memory To understand modern multiprocessors we need to ask some basic questions …
- 9. Foundations of Shared Memory To understand modern multiprocessors we need to ask some basic questions …
- 10. Register* 10011 Holds a (binary) value * A memory location: name is historical Art of Multiprocessor
- 11. Register Can be read 10011 Art of Multiprocessor Programming 10011
- 12. 10011 Register Can be written 01100 Art of Multiprocessor Programming
- 13. public interface Register { public T read(); public void write(T v); } Registers Art of Multiprocessor
- 14. public interface Register { public T read(); public void write(T v); } Registers Type of register
- 15. 10011 Single-Reader/Single-Writer Register 01100 10011 Art of Multiprocessor Programming
- 16. Multi-Reader/Single-Writer Register 10011 Art of Multiprocessor Programming 10011 01100
- 17. 10011 mumble mumble 11011 Multi-Reader/Multi-Writer Register mumble 10011 10011 01010 Art of Multiprocessor Programming
- 18. Jargon Watch SRSW Single-reader single-writer MRSW Multi-reader single-writer MRMW Multi-reader multi-writer Art of Multiprocessor Programming
- 19. Safe Register write(1001) read(1001) OK if reads and writes don’t overlap Art of Multiprocessor Programming
- 20. Safe Register write(1001) Some valid value if reads and writes do overlap read(????) 0000 1001 1111
- 21. Regular Register write(0) read(1) write(1) read(0) Single Writer Readers return: Old value if no overlap (safe)
- 22. Regular or Not? write(0) read(1) write(1) read(0) Art of Multiprocessor Programming
- 23. Regular or Not? write(0) read(1) write(1) read(0) Overlap: returns new value Art of Multiprocessor Programming
- 24. Regular or Not? write(0) write(1) read(0) Overlap: returns old value Art of Multiprocessor Programming
- 25. Regular or Not? write(0) read(1) write(1) read(0) regular Art of Multiprocessor Programming
- 26. Regular ≠ Linearizable write(0) read(1) write(1) read(0) write(1) already happened can’t explain this! Art of Multiprocessor
- 27. Atomic Register write(1001) read(1001) Linearizable to sequential safe register write(1010) read(1010) read(1010) Art of Multiprocessor Programming
- 28. Atomic Register write(1001) read(1001) write(1010) read(1010) read(1010) Art of Multiprocessor Programming
- 29. Register Space MRMW MRSW SRSW Safe Regular Atomic m-valued Boolean Art of Multiprocessor Programming
- 30. Weakest Register 1 0 1 Single reader Single writer Safe Boolean register Art of Multiprocessor Programming
- 31. Weakest Register Single reader Single writer Get correct reading if not during state transition 0 1
- 32. Results From SRSW safe Boolean register All the other registers Mutual exclusion But not everything! Consensus
- 33. Locking within Registers Not interesting to rely on mutual exclusion in register constructions We want registers
- 34. Definition An object implementation is wait-free if every method call completes in a finite number of
- 35. Art of Multiprocessor Programming From Safe SRSW Boolean to Atomic Snapshots MRMW MRSW SRSW Safe Regular
- 36. Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW
- 37. Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW
- 38. public class SafeBoolMRSWRegister implements Register { public boolean read() { … } public void write(boolean x)
- 39. public class SafeBoolMRSWRegister implements Register { public boolean read() { … } public void write(boolean x)
- 40. public class SafeBoolMRSWRegister implements Register { public boolean read() { … } public void write(boolean x)
- 41. public class SafeBoolMRSWRegister implements Register { public boolean read() { … } public void write(boolean x)
- 42. Safe Boolean MRSW from Safe Boolean SRSW 0 0 0 0 0 0 0 0 0
- 43. Safe Boolean MRSW from Safe Boolean SRSW 0 0 0 0 0 0 0 0 0
- 44. Safe Boolean MRSW from Safe Boolean SRSW 0 or 1 1 0 0 0 0 0
- 45. Safe Boolean MRSW from Safe Boolean SRSW 1 0 or 1 1 0 0 0 0
- 46. Safe Boolean MRSW from Safe Boolean SRSW 1 1 1 1 0 or 1 0 0
- 47. Safe Boolean MRSW from Safe Boolean SRSW 1 1 1 1 1 1 1 1 1
- 48. Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements Register { private SafeBoolSRSWRegister[] r
- 49. Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister { private SafeBoolSRSWRegister[] r
- 50. Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister { private SafeBoolSRSWRegister[] r
- 51. Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister { private SafeBoolSRSWRegister[] r
- 52. Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister { private SafeBoolSRSWRegister[] r
- 53. Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister { private SafeBoolSRSWRegister[] r
- 54. 1000 1000 1000 Safe Multi-Valued MRSW from Safe Multi-Valued SRSW? 1011 1011 1011 any value in
- 55. Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW
- 56. Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW
- 57. Regular Boolean MRSW from Safe Boolean MRSW 0 0 0 1 0 1 1 1 Art
- 58. Regular Boolean MRSW from Safe Boolean MRSW 0 0 0 0 0 1 1 1 Art
- 59. Regular Boolean MRSW from Safe Boolean MRSW 0 0 0 0 0 Last written: 0 Art
- 60. Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register { private boolean old;
- 61. Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register { threadLocal boolean old;
- 62. Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register { threadLocal boolean old;
- 63. Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register { threadLocal boolean old;
- 64. Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register { threadLocal boolean old;
- 65. Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register { threadLocal boolean old;
- 66. Regular Multi-Valued MRSW from Safe Multi-Valued MRSW? 0101 0101 Does not work! 0101 Art of Multiprocessor
- 67. Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW
- 68. Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW
- 69. Representing m Values 0 1 2 3 4 5 6 7 1 0 0 0 0
- 70. Writing m-Valued Register 1 0 0 0 0 1 Write 5 Art of Multiprocessor Programming 0
- 71. Writing m-Valued Register 1 1 0 0 0 0 Write 5 Initially 0 Art of Multiprocessor
- 72. 0 1 2 3 4 5 6 7 Writing m-Valued Register 1 1 0 0 0
- 73. MRSW Regular m-valued from MRSW Regular Boolean public class RegMRSWRegister implements Register{ RegBoolMRSWRegister[M] bit; public void
- 74. MRSW Regular m-valued from MRSW Regular Boolean public class RegMRSWRegister implements Register{ RegBoolMRSWRegister[M] bit; public void
- 75. MRSW Regular m-valued from MRSW Regular Boolean public class RegMRSWRegisterimplements Register { RegBoolMRSWRegister[m] bit; public void
- 76. MRSW Regular m-valued from MRSW Regular Boolean public class RegMRSWRegisterimplements Register { RegBoolMRSWRegister[m] bit; public void
- 77. MRSW Regular m-valued from MRSW Regular Boolean public class RegMRSWRegisterimplements Register { RegBoolMRSWRegister[m] bit; public void
- 78. Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW
- 79. Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW
- 80. Road Map (Slight Detour) SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW
- 81. Concurrent Reading SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 1234 5678 Instead of
- 82. SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 5678 5678 time write(5678) read(5678) Initially
- 83. SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 1234 5678 Instead of 5678… time
- 84. SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 1234 5678 Instead of 5678… time
- 85. Timestamped Values Writer writes value and stamp together Reader saves last value & stamp read returns
- 86. SRSW Atomic From SRSW Regular writer reader 1:45 1234 So stick with 5678 time write(2:00 5678)
- 87. Atomic Single-Reader to Atomic Multi-Reader 1:45 1234 stamp value One per reader Art of Multiprocessor Programming
- 88. Another Scenario 2:00 5678 stamp value Writer starts write… Art of Multiprocessor Programming
- 89. Another Scenario 2:00 5678 stamp value reader reads 2:00, 5678 zzz… 1:45 1234 later reader Yellow
- 90. Multi-Reader Redux one per thread 1 2 3 1 2 3 Art of Multiprocessor Programming
- 91. Multi-Reader Redux Writer writes column… reader reads row 2:00, 5678 1 1 2 3 1 2
- 92. Multi-Reader Redux reader writes column to notify others of what it read 1 1 2 3
- 93. Can’t Yellow Miss Blue’s Update? … Only if Readers Overlap… time write(2:00 5678) read(1:45 1234) 1:45
- 94. Bad Case Only When Readers Don’t Overlap time write(2:00 5678) read(2:00 5678) 1:45 1234 read(2:00 5678)
- 95. Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW
- 96. Multi-Writer Atomic From Multi-Reader Atomic 1:45 1234 stamp value Readers read all and take max (Lexicographic
- 97. Atomic Execution Means it is Linearizable time write(1) time Read(max= 2) write(4) write(2) write(3) Read(max =
- 98. Linearization Points time write(1) time Read(max= 2) write(4) write(2) write(3) Read(max = 3) Read (max =
- 99. Linearization Points time write(1) time Look at Writes First write(4) write(2) write(3) write(2) Art of Multiprocessor
- 100. Linearization Points time write(1) time write(4) write(2) write(3) write(2) Order writes by TimeStamp Art of Multiprocessor
- 101. Linearization Points time write(1) time write(4) write(2) write(3) write(2) Read(max= 2) Read(max = 3) Read (max
- 102. Linearization Points time write(1) time write(4) write(2) write(3) write(2) Read(max= 2) Read(max = 3) Read (max
- 103. Linearization Points time write(1) time write(4) write(2) write(3) write(2) Read(max= 2) Read(max = 3) Read (max
- 104. Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW
- 105. Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regular MRSW atomic MRMW
- 106. Atomic Snapshot update scan Art of Multiprocessor Programming
- 107. Atomic Snapshot Array of SWMR atomic registers Take instantaneous snapshot of all Generalizes to MRMW registers
- 108. Snapshot Interface public interface Snapshot { public int update(int v); public int[] scan(); } Art of
- 109. Snapshot Interface public interface Snapshot { public int update(int v); public int[] scan(); } Thread i
- 110. Snapshot Interface public interface Snapshot { public int update(int v); public int[] scan(); } Instantaneous snapshot
- 111. Atomic Snapshot Collect Read values one at a time Problem Incompatible concurrent collects Result not linearizable
- 112. Clean Collects Clean Collect Collect during which nothing changed Can we make it happen? Can we
- 113. Simple Snapshot Put increasing labels on each entry Collect twice If both agree, We’re done Otherwise,
- 114. Claim: We Must Use Labels time x y x y z z x z x z
- 115. Must Use Labels time 1,x 2,y 3,x 4,y 1,z 3,z 1,x 1,z 3,x 3,z Scanner Updater
- 116. Simple Snapshot Collect twice If both agree, We’re done Otherwise, Try again = Collect 2 Collect
- 117. Simple Snapshot: Update public class SimpleSnapshot implements Snapshot { private AtomicMRSWRegister[] register; public void update(int value)
- 118. Simple Snapshot: Update public class SimpleSnapshot implements Snapshot { private AtomicMRSWRegister[] register; public void update(int value)
- 119. Simple Snapshot: Update public class SimpleSnapshot implements Snapshot { private AtomicMRSWRegister[] register; public void update(int value)
- 120. Simple Snapshot: Collect private LabeledValue[] collect() { LabeledValue[] copy = new LabeledValue[n]; for (int j =
- 121. Simple Snapshot private LabeledValue[] collect() { LabeledValue[] copy = new LabeledValue[n]; for (int j = 0;
- 122. Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy = collect(); collect: while (true)
- 123. Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy = collect(); collect: while (true)
- 124. Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy = collect(); collect: while (true)
- 125. Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy = collect(); collect: while (true)
- 126. Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy = collect(); collect: while (true)
- 127. Simple Snapshot Linearizable Update is wait-free No unbounded loops But Scan can starve If interrupted by
- 128. Wait-Free Snapshot Add a scan before every update Write resulting snapshot together with update value If
- 129. Wait-free Snapshot If A’s scan observes that B moved twice, then B completed an update while
- 130. Wait-free Snapshot time A B Art of Multiprocessor Programming
- 131. Wait-free Snapshot time A B Update Art of Multiprocessor Programming
- 132. Wait-free Snapshot time A B Update B’s 1st update must have written during 1st collect So
- 133. Wait-free Snapshot time A B But no guarantee that scan of B’s 1st update can be
- 134. Once is not Enough time ≠ Update A B Why can’t A steal B’s scan? Because
- 135. Someone Must Move Twice time If we collect n times…some thread must move twice (pigeonhole principle)
- 136. Scan is Wait-free scan update So some thread must have had clean collect scan update scan
- 137. Wait-Free Snapshot Label public class SnapValue { public int label; public int value; public int[] snap;
- 138. Wait-Free Snapshot Label public class SnapValue { public int label; public int value; public int[] snap;
- 139. Wait-Free Snapshot Label public class SnapValue { public int label; public int value; public int[] snap;
- 140. Wait-Free Snapshot Label public class SnapValue { public int label; public int value; public int[] snap;
- 141. Wait-Free Snapshot Label 11011110101000101100…00 label value Last snapshot Art of Multiprocessor Programming
- 142. Wait-free Update public void update(int value) { int i = Thread.myIndex(); int[] snap = this.scan(); SnapValue
- 143. Wait-free Scan public void update(int value) { int i = Thread.myIndex(); int[] snap = this.scan(); SnapValue
- 144. Wait-free Scan public void update(int value) { int i = Thread.myIndex(); int[] snap = this.scan(); SnapValue
- 145. Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved = new boolean[n]; oldCopy =
- 146. Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved = new boolean[n]; oldCopy =
- 147. Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved = new boolean[n]; oldCopy =
- 148. Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved = new boolean[n]; oldCopy =
- 149. Mismatch Detected if (oldCopy[j].label != newCopy[j].label) { if (moved[j]) { // second move return newCopy[j].snap; }
- 150. Mismatch Detected if (oldCopy[j].label != newCopy[j].label) { if (moved[j]) { return newCopy[j].snap; } else { moved[j]
- 151. Mismatch Detected if (oldCopy[j].label != newCopy[j].label) { if (moved[j]) { // second move return newCopy[j].snap; }
- 152. Observations Uses unbounded counters can be replaced with 2 bits Assumes SWMR registers for labels can
- 153. Summary We saw we could implement MRMW multi valued snapshot objects From SRSW binary safe registers
- 154. Grand Challenge Snapshot means Write any one array element Read multiple array elements Art of Multiprocessor
- 155. Grand Challenge Writes to 0 and 1 Writes to 1 and 2 What about atomic writes
- 157. Скачать презентацию
Слайд 2Last Lecture
Defined concurrent objects using linearizability and sequential consistency
Fact: implemented linearizable objects
Last Lecture
Defined concurrent objects using linearizability and sequential consistency
Fact: implemented linearizable objects
Слайд 3Fundamentals
What is the weakest form of communication that supports mutual exclusion?
What is
Fundamentals
What is the weakest form of communication that supports mutual exclusion?
What is
Слайд 4Alan Turing
Showed what is and is not computable on a sequential machine.
Alan Turing
Showed what is and is not computable on a sequential machine.
Слайд 5Turing Computability
Mathematical model of computation
What is (and is not) computable
Efficiency (mostly) irrelevant
1
Art
Turing Computability
Mathematical model of computation
What is (and is not) computable
Efficiency (mostly) irrelevant
1
Art
Слайд 6Shared-Memory Computability?
Mathematical model of concurrent computation
What is (and is not) concurrently computable
Efficiency
Shared-Memory Computability?
Mathematical model of concurrent computation
What is (and is not) concurrently computable
Efficiency
Слайд 7Foundations of Shared Memory
To understand modern multiprocessors we need to ask
Foundations of Shared Memory
To understand modern multiprocessors we need to ask
Слайд 8Foundations of Shared Memory
To understand modern multiprocessors we need to ask
Foundations of Shared Memory
To understand modern multiprocessors we need to ask
Слайд 9Foundations of Shared Memory
To understand modern multiprocessors we need to ask
Foundations of Shared Memory
To understand modern multiprocessors we need to ask
Слайд 10Register*
10011
Holds a (binary) value
* A memory location: name is historical
Art of Multiprocessor
Register*
10011
Holds a (binary) value
* A memory location: name is historical
Art of Multiprocessor
Слайд 11Register
Can be read
10011
Art of Multiprocessor Programming
10011
Register
Can be read
10011
Art of Multiprocessor Programming
10011
Слайд 1210011
Register
Can be written
01100
Art of Multiprocessor Programming
10011
Register
Can be written
01100
Art of Multiprocessor Programming
Слайд 13public interface Register {
public T read();
public void write(T v);
}
Registers
Art
public interface Register Registers Art
public T read();
public void write(T v);
}
Слайд 14public interface Register {
public T read();
public void write(T v);
}
Registers
Type
public interface Register Registers Type
public T read();
public void write(T v);
}
Слайд 1510011
Single-Reader/Single-Writer Register
01100
10011
Art of Multiprocessor Programming
10011
Single-Reader/Single-Writer Register
01100
10011
Art of Multiprocessor Programming
Слайд 16Multi-Reader/Single-Writer Register
10011
Art of Multiprocessor Programming
10011
01100
Multi-Reader/Single-Writer Register
10011
Art of Multiprocessor Programming
10011
01100
Слайд 1710011
mumble
mumble
11011
Multi-Reader/Multi-Writer Register
mumble
10011
10011
01010
Art of Multiprocessor Programming
10011
mumble
mumble
11011
Multi-Reader/Multi-Writer Register
mumble
10011
10011
01010
Art of Multiprocessor Programming
Слайд 18Jargon Watch
SRSW
Single-reader single-writer
MRSW
Multi-reader single-writer
MRMW
Multi-reader multi-writer
Art of Multiprocessor Programming
Jargon Watch
SRSW
Single-reader single-writer
MRSW
Multi-reader single-writer
MRMW
Multi-reader multi-writer
Art of Multiprocessor Programming
Слайд 19Safe Register
write(1001)
read(1001)
OK if reads and writes don’t overlap
Art of Multiprocessor Programming
Safe Register
write(1001)
read(1001)
OK if reads and writes don’t overlap
Art of Multiprocessor Programming
Слайд 20Safe Register
write(1001)
Some valid value if reads and writes do overlap
read(????)
0000
1001
1111
$*&v
Art of Multiprocessor
Safe Register
write(1001)
Some valid value if reads and writes do overlap
read(????)
0000
1001
1111
$*&v
Art of Multiprocessor
Слайд 21Regular Register
write(0)
read(1)
write(1)
read(0)
Single Writer
Readers return:
Old value if no overlap (safe)
Old or one of
Regular Register
write(0)
read(1)
write(1)
read(0)
Single Writer
Readers return:
Old value if no overlap (safe)
Old or one of
Слайд 22Regular or Not?
write(0)
read(1)
write(1)
read(0)
Art of Multiprocessor Programming
Regular or Not?
write(0)
read(1)
write(1)
read(0)
Art of Multiprocessor Programming
Слайд 23Regular or Not?
write(0)
read(1)
write(1)
read(0)
Overlap: returns new value
Art of Multiprocessor Programming
Regular or Not?
write(0)
read(1)
write(1)
read(0)
Overlap: returns new value
Art of Multiprocessor Programming
Слайд 24Regular or Not?
write(0)
write(1)
read(0)
Overlap: returns old value
Art of Multiprocessor Programming
Regular or Not?
write(0)
write(1)
read(0)
Overlap: returns old value
Art of Multiprocessor Programming
Слайд 25Regular or Not?
write(0)
read(1)
write(1)
read(0)
regular
Art of Multiprocessor Programming
Regular or Not?
write(0)
read(1)
write(1)
read(0)
regular
Art of Multiprocessor Programming
Слайд 26Regular ≠ Linearizable
write(0)
read(1)
write(1)
read(0)
write(1) already happened
can’t explain this!
Art of Multiprocessor Programming
Regular ≠ Linearizable
write(0)
read(1)
write(1)
read(0)
write(1) already happened
can’t explain this!
Art of Multiprocessor Programming
Слайд 27Atomic Register
write(1001)
read(1001)
Linearizable to sequential safe register
write(1010)
read(1010)
read(1010)
Art of Multiprocessor Programming
Atomic Register
write(1001)
read(1001)
Linearizable to sequential safe register
write(1010)
read(1010)
read(1010)
Art of Multiprocessor Programming
Слайд 28Atomic Register
write(1001)
read(1001)
write(1010)
read(1010)
read(1010)
Art of Multiprocessor Programming
Atomic Register
write(1001)
read(1001)
write(1010)
read(1010)
read(1010)
Art of Multiprocessor Programming
Слайд 29Register Space
MRMW
MRSW
SRSW
Safe
Regular
Atomic
m-valued
Boolean
Art of Multiprocessor Programming
Register Space
MRMW
MRSW
SRSW
Safe
Regular
Atomic
m-valued
Boolean
Art of Multiprocessor Programming
Слайд 30Weakest Register
1
0
1
Single reader
Single writer
Safe Boolean register
Art of Multiprocessor Programming
Weakest Register
1
0
1
Single reader
Single writer
Safe Boolean register
Art of Multiprocessor Programming
Слайд 31Weakest Register
Single reader
Single writer
Get correct reading if not during state transition
0
1
0
0
1
0
Art of
Weakest Register
Single reader
Single writer
Get correct reading if not during state transition
0
1
0
0
1
0
Art of
Слайд 32Results
From SRSW safe Boolean register
All the other registers
Mutual exclusion
But not everything!
Consensus hierarchy
Foundations
Results
From SRSW safe Boolean register
All the other registers
Mutual exclusion
But not everything!
Consensus hierarchy
Foundations
Слайд 33Locking within Registers
Not interesting to rely on mutual exclusion in register constructions
We
Locking within Registers
Not interesting to rely on mutual exclusion in register constructions
We
Слайд 34Definition
An object implementation is wait-free if every method call completes in a
Definition
An object implementation is wait-free if every method call completes in a
Слайд 35Art of Multiprocessor Programming
From Safe SRSW Boolean to Atomic Snapshots
MRMW
MRSW
SRSW
Safe
Regular
Atomic
M-valued
Boolean
Snapshot
Art of Multiprocessor Programming
From Safe SRSW Boolean to Atomic Snapshots
MRMW
MRSW
SRSW
Safe
Regular
Atomic
M-valued
Boolean
Snapshot
Слайд 36Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Art
Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Art
Слайд 37Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Next
Art
Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Next
Art
Слайд 38public class SafeBoolMRSWRegister
implements Register {
public boolean read() { …
public class SafeBoolMRSWRegister
implements Register
public boolean read() { …
Слайд 39public class SafeBoolMRSWRegister
implements Register {
public boolean read() { …
public class SafeBoolMRSWRegister
implements Register
public boolean read() { …
Слайд 40public class SafeBoolMRSWRegister
implements Register {
public boolean read() { …
public class SafeBoolMRSWRegister
implements Register
public boolean read() { …
Слайд 41public class SafeBoolMRSWRegister
implements Register {
public boolean read() { …
public class SafeBoolMRSWRegister
implements Register
public boolean read() { …
Слайд 42Safe Boolean MRSW from
Safe Boolean SRSW
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
0
0
0
0
0
0
0
0
0
0
0
zzz
readers
writer
Art of Multiprocessor Programming
Слайд 43Safe 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
0
0
0
0
0
0
0
0
0
0
0
Let’s write 1!
Art of Multiprocessor Programming
Слайд 44Safe 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
0 or 1
1
0
0
0
0
0
0
0
0
0
Art of Multiprocessor Programming
Слайд 45Safe 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
1
0 or 1
1
0
0
0
0
0
0
0
1
Art of Multiprocessor Programming
Слайд 46Safe 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
1
1
1
1
0 or 1
0
0
0
0
0
1
Art of Multiprocessor Programming
Слайд 47Safe 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
1
1
1
1
1
1
1
1
1
1
Whew!
Art of Multiprocessor Programming
Слайд 48Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements Register {
private
Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements Register
private
Слайд 49Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private
Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private
Слайд 50Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private
Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private
Слайд 51Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private
Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private
Слайд 52Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private
Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private
Слайд 53Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private
Safe Boolean MRSW from
Safe Boolean SRSW
public class SafeBoolMRSWRegister
implements BooleanRegister {
private
Слайд 541000
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
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
Слайд 55Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Questions?
Art
Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Questions?
Art
Слайд 56Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Next
Art
Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Next
Art
Слайд 57Regular 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
0
0
0
1
0
1
1
1
Art of Multiprocessor Programming
Слайд 58Regular 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
0
0
0
0
0
1
1
1
Art of Multiprocessor Programming
Uh, oh!
Слайд 59Regular 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
0
0
0
0
0
Last written:
0
Art of Multiprocessor Programming
Слайд 60Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register {
Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register
Слайд 61Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register {
Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register
Слайд 62Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register {
Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register
Слайд 63Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register {
Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register
Слайд 64Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register {
Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register
Слайд 65Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register{
threadLocal
Regular Boolean MRSW from
Safe Boolean MRSW
public class RegBoolMRSWRegister
implements Register
threadLocal
Слайд 66Regular Multi-Valued MRSW from
Safe Multi-Valued MRSW?
0101
0101
Does not work!
0101
Art of Multiprocessor Programming
Safe
Regular Multi-Valued MRSW from
Safe Multi-Valued MRSW?
0101
0101
Does not work!
0101
Art of Multiprocessor Programming
Safe
Слайд 67Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Questions?
Art
Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Questions?
Art
Слайд 68Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Next
Art
Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Next
Art
Слайд 69Representing m Values
0 1 2 3 4 5 6 7
1
0
0
0
0
1
Initially 0
Unary
Representing m Values
0 1 2 3 4 5 6 7
1
0
0
0
0
1
Initially 0
Unary
Слайд 70Writing m-Valued Register
1
0
0
0
0
1
Write 5
Art of Multiprocessor Programming
0 1 2 3 4 5
Writing m-Valued Register
1
0
0
0
0
1
Write 5
Art of Multiprocessor Programming
0 1 2 3 4 5
Слайд 71Writing m-Valued Register
1
1
0
0
0
0
Write 5
Initially 0
Art of Multiprocessor Programming
0 1 2 3 4
Writing m-Valued Register
1
1
0
0
0
0
Write 5
Initially 0
Art of Multiprocessor Programming
0 1 2 3 4
Слайд 720 1 2 3 4 5 6 7
Writing m-Valued Register
1
1
0
0
0
0
Write 5
5
0
Art
0 1 2 3 4 5 6 7
Writing m-Valued Register
1
1
0
0
0
0
Write 5
5
0
Art
Слайд 73MRSW Regular m-valued from MRSW Regular Boolean
public class RegMRSWRegister implements Register{
RegBoolMRSWRegister[M]
MRSW Regular m-valued from MRSW Regular Boolean
public class RegMRSWRegister implements Register{
RegBoolMRSWRegister[M]
Слайд 74MRSW Regular m-valued from MRSW Regular Boolean
public class RegMRSWRegister implements Register{
RegBoolMRSWRegister[M]
MRSW Regular m-valued from MRSW Regular Boolean
public class RegMRSWRegister implements Register{
RegBoolMRSWRegister[M]
Слайд 75MRSW Regular m-valued from MRSW Regular Boolean
public class RegMRSWRegisterimplements Register {
RegBoolMRSWRegister[m]
MRSW Regular m-valued from MRSW Regular Boolean
public class RegMRSWRegisterimplements Register {
RegBoolMRSWRegister[m]
Слайд 76MRSW Regular m-valued from MRSW Regular Boolean
public class RegMRSWRegisterimplements Register {
RegBoolMRSWRegister[m]
MRSW Regular m-valued from MRSW Regular Boolean
public class RegMRSWRegisterimplements Register {
RegBoolMRSWRegister[m]
Слайд 77MRSW Regular m-valued from MRSW Regular Boolean
public class RegMRSWRegisterimplements Register {
RegBoolMRSWRegister[m]
MRSW Regular m-valued from MRSW Regular Boolean
public class RegMRSWRegisterimplements Register {
RegBoolMRSWRegister[m]
Слайд 78Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Questions?
Art
Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Questions?
Art
Слайд 79Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Art
Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Art
Слайд 80Road Map (Slight Detour)
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW
Road Map (Slight Detour)
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW
Слайд 81Concurrent
Reading
SRSW Atomic From SRSW Regular
1234
Regular writer
Regular
reader
1234
5678
Instead of 5678…
When is this
Concurrent
Reading
SRSW Atomic From SRSW Regular
1234
Regular writer
Regular
reader
1234
5678
Instead of 5678…
When is this
Слайд 82SRSW Atomic From SRSW Regular
1234
Regular writer
Regular
reader
5678
5678
time
write(5678)
read(5678)
Initially
1234
Art of Multiprocessor Programming
Same
SRSW Atomic From SRSW Regular
1234
Regular writer
Regular
reader
5678
5678
time
write(5678)
read(5678)
Initially
1234
Art of Multiprocessor Programming
Same
Слайд 83SRSW 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
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
Слайд 84SRSW 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
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
Слайд 85Timestamped Values
Writer writes
value and stamp
together
Reader saves last value &
Timestamped Values
Writer writes
value and stamp
together
Reader saves last value &
Слайд 86SRSW Atomic From SRSW Regular
writer
reader
1:45 1234 < 2:00 5678
So stick
SRSW Atomic From SRSW Regular
writer
reader
1:45 1234 < 2:00 5678
So stick
Слайд 87Atomic Single-Reader to Atomic Multi-Reader
1:45
1234
stamp
value
One per reader
Art of Multiprocessor Programming
Atomic Single-Reader to Atomic Multi-Reader
1:45
1234
stamp
value
One per reader
Art of Multiprocessor Programming
Слайд 88Another Scenario
2:00
5678
stamp
value
Writer starts write…
Art of Multiprocessor Programming
Another Scenario
2:00
5678
stamp
value
Writer starts write…
Art of Multiprocessor Programming
Слайд 89Another Scenario
2:00
5678
stamp
value
reader
reads
2:00, 5678
zzz…
1:45 1234
later
reader
Yellow was completely after Blue but read
Another Scenario
2:00
5678
stamp
value
reader
reads
2:00, 5678
zzz…
1:45 1234
later
reader
Yellow was completely after Blue but read
Слайд 90Multi-Reader Redux
one per thread
1
2
3
1
2
3
Art of Multiprocessor Programming
Multi-Reader Redux
one per thread
1
2
3
1
2
3
Art of Multiprocessor Programming
Слайд 91Multi-Reader Redux
Writer writes column…
reader
reads row
2:00, 5678
1
1
2
3
1
2
3
2
Art of Multiprocessor Programming
Multi-Reader Redux
Writer writes column…
reader
reads row
2:00, 5678
1
1
2
3
1
2
3
2
Art of Multiprocessor Programming
Слайд 92Multi-Reader Redux
reader writes column to notify others of what it read
1
1
2
3
1
2
3
2
zzz…after
Multi-Reader Redux
reader writes column to notify others of what it read
1
1
2
3
1
2
3
2
zzz…after
Слайд 93Can’t Yellow Miss Blue’s Update? … Only if Readers Overlap…
time
write(2:00 5678)
read(1:45 1234)
1:45
Can’t Yellow Miss Blue’s Update? … Only if Readers Overlap…
time
write(2:00 5678)
read(1:45 1234)
1:45
Слайд 94Bad Case Only When Readers
Don’t Overlap
time
write(2:00 5678)
read(2:00 5678)
1:45
1234
read(2:00 5678)
In
Bad Case Only When Readers
Don’t Overlap
time
write(2:00 5678)
read(2:00 5678)
1:45
1234
read(2:00 5678)
In
Слайд 95Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Next
Art
Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Next
Art
Слайд 96Multi-Writer Atomic From Multi-Reader Atomic
1:45
1234
stamp
value
Readers read all
and take max
(Lexicographic
like Bakery)
Each
Multi-Writer Atomic From Multi-Reader Atomic
1:45
1234
stamp
value
Readers read all
and take max
(Lexicographic
like Bakery)
Each
Слайд 97Atomic Execution
Means it is Linearizable
time
write(1)
time
Read(max= 2)
write(4)
write(2)
write(3)
Read(max = 3)
Read (max = 1)
write(2)
Read(max
Atomic Execution
Means it is Linearizable
time
write(1)
time
Read(max= 2)
write(4)
write(2)
write(3)
Read(max = 3)
Read (max = 1)
write(2)
Read(max
Слайд 98Linearization Points
time
write(1)
time
Read(max= 2)
write(4)
write(2)
write(3)
Read(max = 3)
Read (max = 1)
write(2)
Read(max = 4)
Art of Multiprocessor
Linearization Points
time
write(1)
time
Read(max= 2)
write(4)
write(2)
write(3)
Read(max = 3)
Read (max = 1)
write(2)
Read(max = 4)
Art of Multiprocessor
Слайд 99Linearization Points
time
write(1)
time
Look at Writes First
write(4)
write(2)
write(3)
write(2)
Art of Multiprocessor Programming
Linearization Points
time
write(1)
time
Look at Writes First
write(4)
write(2)
write(3)
write(2)
Art of Multiprocessor Programming
Слайд 100Linearization Points
time
write(1)
time
write(4)
write(2)
write(3)
write(2)
Order writes by TimeStamp
Art of Multiprocessor Programming
Linearization Points
time
write(1)
time
write(4)
write(2)
write(3)
write(2)
Order writes by TimeStamp
Art of Multiprocessor Programming
Слайд 101Linearization Points
time
write(1)
time
write(4)
write(2)
write(3)
write(2)
Read(max= 2)
Read(max = 3)
Read (max = 1)
Read(max = 4)
Order reads by
Linearization Points
time
write(1)
time
write(4)
write(2)
write(3)
write(2)
Read(max= 2)
Read(max = 3)
Read (max = 1)
Read(max = 4)
Order reads by
Слайд 102Linearization Points
time
write(1)
time
write(4)
write(2)
write(3)
write(2)
Read(max= 2)
Read(max = 3)
Read (max = 1)
Read(max = 4)
Order reads by
Linearization Points
time
write(1)
time
write(4)
write(2)
write(3)
write(2)
Read(max= 2)
Read(max = 3)
Read (max = 1)
Read(max = 4)
Order reads by
Слайд 103Linearization Points
time
write(1)
time
write(4)
write(2)
write(3)
write(2)
Read(max= 2)
Read(max = 3)
Read (max = 1)
Read(max = 4)
The linearization point
Linearization Points
time
write(1)
time
write(4)
write(2)
write(3)
write(2)
Read(max= 2)
Read(max = 3)
Read (max = 1)
Read(max = 4)
The linearization point
Слайд 104Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Questions?
Art
Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Questions?
Art
Слайд 105Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Next
Art
Road Map
SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot
Next
Art
Слайд 106Atomic Snapshot
update
scan
Art of Multiprocessor Programming
Atomic Snapshot
update
scan
Art of Multiprocessor Programming
Слайд 107Atomic Snapshot
Array of SWMR atomic registers
Take instantaneous snapshot of all
Generalizes to MRMW
Atomic Snapshot
Array of SWMR atomic registers
Take instantaneous snapshot of all
Generalizes to MRMW
Слайд 108Snapshot Interface
public interface Snapshot {
public int update(int v);
public int[] scan();
}
Art
Snapshot Interface
public interface Snapshot {
public int update(int v);
public int[] scan();
}
Art
![Snapshot Interface public interface Snapshot { public int update(int v); public int[]](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-107.jpg)
Слайд 109Snapshot Interface
public interface Snapshot {
public int update(int v);
public int[] scan();
}
Thread
Snapshot Interface
public interface Snapshot {
public int update(int v);
public int[] scan();
}
Thread
![Snapshot Interface public interface Snapshot { public int update(int v); public int[]](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-108.jpg)
Слайд 110Snapshot Interface
public interface Snapshot {
public int update(int v);
public int[] scan();
}
Instantaneous
Snapshot Interface
public interface Snapshot {
public int update(int v);
public int[] scan();
}
Instantaneous
![Snapshot Interface public interface Snapshot { public int update(int v); public int[]](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-109.jpg)
Слайд 111Atomic Snapshot
Collect
Read values one at a time
Problem
Incompatible concurrent collects
Result not linearizable
Art of
Atomic Snapshot
Collect
Read values one at a time
Problem
Incompatible concurrent collects
Result not linearizable
Art of
Слайд 112Clean Collects
Clean Collect
Collect during which nothing changed
Can we make it happen?
Can we
Clean Collects
Clean Collect
Collect during which nothing changed
Can we make it happen?
Can we
Слайд 113Simple Snapshot
Put increasing labels on each entry
Collect twice
If both agree,
We’re done
Otherwise,
Try again
=
Collect
Simple Snapshot
Put increasing labels on each entry
Collect twice
If both agree,
We’re done
Otherwise,
Try again
=
Collect
Слайд 114Claim: We Must Use Labels
time
x
y
x
y
z
z
x
z
x
z
Scanner
Updater
Updater
But scanner sees x and z together!
x and
Claim: We Must Use Labels
time
x
y
x
y
z
z
x
z
x
z
Scanner
Updater
Updater
But scanner sees x and z together!
x and
Слайд 115Must Use Labels
time
1,x
2,y
3,x
4,y
1,z
3,z
1,x
1,z
3,x
3,z
Scanner
Updater
Updater
2,w
Scanner reads x and z with different labels and recognizes
Must Use Labels
time
1,x
2,y
3,x
4,y
1,z
3,z
1,x
1,z
3,x
3,z
Scanner
Updater
Updater
2,w
Scanner reads x and z with different labels and recognizes
Слайд 116Simple Snapshot
Collect twice
If both agree,
We’re done
Otherwise,
Try again
=
Collect 2
Collect 1
Art of Multiprocessor Programming
Simple Snapshot
Collect twice
If both agree,
We’re done
Otherwise,
Try again
=
Collect 2
Collect 1
Art of Multiprocessor Programming
Слайд 117Simple Snapshot: Update
public class SimpleSnapshot implements Snapshot {
private AtomicMRSWRegister[] register;
public
Simple Snapshot: Update
public class SimpleSnapshot implements Snapshot {
private AtomicMRSWRegister[] register;
public
![Simple Snapshot: Update public class SimpleSnapshot implements Snapshot { private AtomicMRSWRegister[] register;](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-116.jpg)
Слайд 118Simple Snapshot: Update
public class SimpleSnapshot implements Snapshot {
private AtomicMRSWRegister[] register;
public
Simple Snapshot: Update
public class SimpleSnapshot implements Snapshot {
private AtomicMRSWRegister[] register;
public
![Simple Snapshot: Update public class SimpleSnapshot implements Snapshot { private AtomicMRSWRegister[] register;](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-117.jpg)
Слайд 119Simple Snapshot: Update
public class SimpleSnapshot implements Snapshot {
private AtomicMRSWRegister[] register;
public
Simple Snapshot: Update
public class SimpleSnapshot implements Snapshot {
private AtomicMRSWRegister[] register;
public
![Simple Snapshot: Update public class SimpleSnapshot implements Snapshot { private AtomicMRSWRegister[] register;](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-118.jpg)
Слайд 120Simple Snapshot: Collect
private LabeledValue[] collect() {
LabeledValue[] copy =
new LabeledValue[n];
for
Simple Snapshot: Collect
private LabeledValue[] collect() {
LabeledValue[] copy =
new LabeledValue[n];
for
![Simple Snapshot: Collect private LabeledValue[] collect() { LabeledValue[] copy = new LabeledValue[n];](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-119.jpg)
Слайд 121Simple Snapshot
private LabeledValue[] collect() {
LabeledValue[] copy =
new LabeledValue[n];
for (int
Simple Snapshot
private LabeledValue[] collect() {
LabeledValue[] copy =
new LabeledValue[n];
for (int
![Simple Snapshot private LabeledValue[] collect() { LabeledValue[] copy = new LabeledValue[n]; for](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-120.jpg)
Слайд 122Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();
Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();
![Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-121.jpg)
Слайд 123Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();
Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();
![Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-122.jpg)
Слайд 124Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();
Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();
![Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-123.jpg)
Слайд 125Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();
Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();
![Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-124.jpg)
Слайд 126Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();
Simple Snapshot: Scan
public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();
![Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-125.jpg)
Слайд 127Simple Snapshot
Linearizable
Update is wait-free
No unbounded loops
But Scan can starve
If interrupted by concurrent
Simple Snapshot
Linearizable
Update is wait-free
No unbounded loops
But Scan can starve
If interrupted by concurrent
Слайд 128Wait-Free Snapshot
Add a scan before every update
Write resulting snapshot together with update
Wait-Free Snapshot
Add a scan before every update
Write resulting snapshot together with update
Слайд 129Wait-free Snapshot
If A’s scan observes that B moved
twice, then B completed an
Wait-free Snapshot
If A’s scan observes that B moved
twice, then B completed an
Слайд 130Wait-free Snapshot
time
A
B
Art of Multiprocessor Programming
Wait-free Snapshot
time
A
B
Art of Multiprocessor Programming
Слайд 131Wait-free Snapshot
time
A
B
Update
Art of Multiprocessor Programming
Wait-free Snapshot
time
A
B
Update
Art of Multiprocessor Programming
Слайд 132Wait-free Snapshot
time
A
B
Update
B’s 1st update must have written during 1st collect
So scan of
Wait-free Snapshot
time
A
B
Update
B’s 1st update must have written during 1st collect
So scan of
Слайд 133Wait-free Snapshot
time
A
B
But no guarantee that scan
of B’s 1st update can be used…
Why?
Art
Wait-free Snapshot
time
A
B
But no guarantee that scan
of B’s 1st update can be used…
Why?
Art
Слайд 134Once is not Enough
time
≠
Update
A
B
Why can’t A steal B’s scan?
Because another update
might
Once is not Enough
time
≠
Update
A
B
Why can’t A steal B’s scan?
Because another update
might
Слайд 135Someone Must Move Twice
time
If we collect n times…some thread
must move twice
Someone Must Move Twice
time
If we collect n times…some thread
must move twice
Слайд 136Scan is Wait-free
scan
update
So some thread must have had clean collect
scan
update
scan
At
most
Scan is Wait-free
scan
update
So some thread must have had clean collect
scan
update
scan
At
most
Слайд 137Wait-Free Snapshot Label
public class SnapValue {
public int label;
public int
Wait-Free Snapshot Label
public class SnapValue {
public int label;
public int
Слайд 138Wait-Free Snapshot Label
public class SnapValue {
public int label;
public int
Wait-Free Snapshot Label
public class SnapValue {
public int label;
public int
Слайд 139Wait-Free Snapshot Label
public class SnapValue {
public int label;
public int
Wait-Free Snapshot Label
public class SnapValue {
public int label;
public int
Слайд 140Wait-Free Snapshot Label
public class SnapValue {
public int label;
public int
Wait-Free Snapshot Label
public class SnapValue {
public int label;
public int
Слайд 141Wait-Free Snapshot Label
11011110101000101100…00
label
value
Last snapshot
Art of Multiprocessor Programming
Wait-Free Snapshot Label
11011110101000101100…00
label
value
Last snapshot
Art of Multiprocessor Programming
Слайд 142Wait-free Update
public void update(int value) {
int i = Thread.myIndex();
int[]
Wait-free Update
public void update(int value) {
int i = Thread.myIndex();
int[]
![Wait-free Update public void update(int value) { int i = Thread.myIndex(); int[]](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-141.jpg)
Слайд 143Wait-free Scan
public void update(int value) {
int i = Thread.myIndex();
int[]
Wait-free Scan
public void update(int value) {
int i = Thread.myIndex();
int[]
![Wait-free Scan public void update(int value) { int i = Thread.myIndex(); int[]](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-142.jpg)
Слайд 144Wait-free Scan
public void update(int value) {
int i = Thread.myIndex();
int[]
Wait-free Scan
public void update(int value) {
int i = Thread.myIndex();
int[]
![Wait-free Scan public void update(int value) { int i = Thread.myIndex(); int[]](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-143.jpg)
Слайд 145Wait-free Scan
public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved =
Wait-free Scan
public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved =
![Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-144.jpg)
Слайд 146Wait-free Scan
public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved =
Wait-free Scan
public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved =
![Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-145.jpg)
Слайд 147Wait-free Scan
public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved =
Wait-free Scan
public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved =
![Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-146.jpg)
Слайд 148Wait-free Scan
public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved =
Wait-free Scan
public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved =
![Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-147.jpg)
Слайд 149Mismatch Detected
if (oldCopy[j].label != newCopy[j].label) {
if (moved[j]) { // second move
return
Mismatch Detected
if (oldCopy[j].label != newCopy[j].label) {
if (moved[j]) { // second move
return
![Mismatch Detected if (oldCopy[j].label != newCopy[j].label) { if (moved[j]) { // second](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-148.jpg)
Слайд 150Mismatch Detected
if (oldCopy[j].label != newCopy[j].label) {
if (moved[j]) {
return newCopy[j].snap;
}
Mismatch Detected
if (oldCopy[j].label != newCopy[j].label) {
if (moved[j]) {
return newCopy[j].snap;
}
![Mismatch Detected if (oldCopy[j].label != newCopy[j].label) { if (moved[j]) { return newCopy[j].snap;](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-149.jpg)
Слайд 151Mismatch Detected
if (oldCopy[j].label != newCopy[j].label) {
if (moved[j]) { // second move
return
Mismatch Detected
if (oldCopy[j].label != newCopy[j].label) {
if (moved[j]) { // second move
return
![Mismatch Detected if (oldCopy[j].label != newCopy[j].label) { if (moved[j]) { // second](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/839053/slide-150.jpg)
Слайд 152Observations
Uses unbounded counters
can be replaced with 2 bits
Assumes SWMR registers
for labels
can be
Observations
Uses unbounded counters
can be replaced with 2 bits
Assumes SWMR registers
for labels
can be
Слайд 153Summary
We saw we could implement MRMW multi valued snapshot objects
From SRSW
Summary
We saw we could implement MRMW multi valued snapshot objects
From SRSW
Слайд 154Grand Challenge
Snapshot means
Write any one array element
Read multiple array elements
Art of Multiprocessor
Grand Challenge
Snapshot means
Write any one array element
Read multiple array elements
Art of Multiprocessor
Слайд 155Grand Challenge
Writes to 0 and 1
Writes to 1 and 2
What about
atomic
Grand Challenge
Writes to 0 and 1
Writes to 1 and 2
What about
atomic
Reading. Focus 1
Peer Pressure
Personal prounouns. Game
Four in a row
Past simple regular
Глаголы повелительного наклонения - imperative
Порядковые числительные. Ordinal numbers
Презентация к уроку английского языка "Polar Bear" - 
Don’t or Doesn’t
Starters classroom language rules
Eating traditions and customs
Рast simple by Artem Morozov
Farm animals
United Kingdom environmental activities
5.3 Международные экономические организации 1. Международные правительственные (межгосударственные) экономические организации. 
Our autumn walk around Magnitogorsk
Путешествие в волшебную страну английского языка
Uni Life. Choosing a university
Thanksgiving traditions
Conditionals
List extra follow up
Used to
Prepositions. Предлоги
Present perfect
Let’s go
Spelling sound pattern -ar
Past Simple
Boat Race (Past Simple, Future Simple, Present Continuous, Present Perfect)