Содержание
- 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. Скачать презентацию