[CS61C FA20] Lecture 34.4 - Thread-Level Parallelism II: Synchronization — Transcript

Full transcript

1. 0:00and welcome back in this final lecture
2. 0:03in this series we're going to learn
3. 0:04about
4. 0:04how to synchronize this how do we
5. 0:06prevent that race condition we saw
6. 0:08in the last video synchronization
7. 0:12how can we have some software maybe even
8. 0:14hardware support for that
9. 0:16so the idea is i've got a single
10. 0:19re-shared resource and this by the way
11. 0:20this is true for any parallel system
12. 0:23this isn't just wall it's in c and
13. 0:24openmp and how to do this no
14. 0:26any in life in computational thinking
15. 0:28you've got some resource
16. 0:29that's being trying to be requested be
17. 0:32used by parallel workers parallel actors
18. 0:35how do you limit access to that parallel
19. 0:37resource in a way that won't give you
20. 0:39the wrong value won't do the wrong thing
21. 0:42for example how do you prevent two
22. 0:44people from editing the same editing
23. 0:45of one file at the same time uh this is
24. 0:48true
25. 0:49dropbox you know i log into two
26. 0:51different laptops and i try to modify
27. 0:53the same file
28. 0:54in different ways this one i write a
29. 0:55this one i write b i say they're both
30. 0:56files what happens how does dropbox
31. 0:58handle that
32. 0:59a dropbox handler says there's a
33. 1:01conflicted copy so that
34. 1:03is a way to tell me that there's no do i
35. 1:04get a notification no but the point is
36. 1:06there's a
37. 1:06way for them to deal with the shared
38. 1:08resource so this is true for you know
39. 1:10the
40. 1:10writ large in some sense of the of any
41. 1:12share any paralyzed system
42. 1:15otherwise things can get mixed up um
43. 1:17here's a solution
44. 1:18just take turns maybe if i'm in dropbox
45. 1:21if i'm
46. 1:22opening a file and editing it i can't
47. 1:23even open it now it certainly lets me
48. 1:25but i can say you know what you can't
49. 1:26open this file somebody else has the
50. 1:27file open so maybe that means when you
51. 1:28open a file you might you write a secret
52. 1:30thing
53. 1:30or something that says this file's open
54. 1:32and when you try to open a file every os
55. 1:34would look to see if that secret thing
56. 1:35is set and therefore it says you can't
57. 1:36open it now what happens when there's a
58. 1:37raise to that
59. 1:38so there's all this conversation how do
60. 1:40you prevent the race to this
61. 1:41both of us exactly the same time go grab
62. 1:44it they both looked and
63. 1:45so there's a whole issue of how to
64. 1:46prevent that but we've got to think
65. 1:47about synchronization in a deeper way
66. 1:50for example all controlling your
67. 1:51microphone and trying to talk at once so
68. 1:53someone gets the microphone and once
69. 1:54they grab it they have to release it
70. 1:56it's a good practice for kind of
71. 1:57controlling uh conversations in
72. 1:59classrooms as well
73. 2:00so the word for use in the parallel
74. 2:02distributed computing world is called a
75. 2:04lock
76. 2:05and we have to lock out we use a lock to
77. 2:07prevent
78. 2:08other elements from accessing a shared
79. 2:11resource
80. 2:12um so this is also by the way known as a
81. 2:14semaphore so semaphores unlocks are both
82. 2:16usually used in the same way
83. 2:17and the idea for this and we'll just see
84. 2:20if i have a variable called a lock
85. 2:22when it's set to zero it's unlocked when
86. 2:24it's set to one it's locked
87. 2:25okay so if ever one it means it's locked
88. 2:27and someone has control of it okay
89. 2:29let's do it let's play with it let's
90. 2:30actually code this in c here we go
91. 2:32so i have a little lope little loop that
92. 2:34says while the lock is not
93. 2:36zero so while i'm waiting for the lock
94. 2:38to be while
95. 2:39while the lock is is being taken i'm
96. 2:42just going to sit and spin this is
97. 2:43called spin waiting so i'm spin waiting
98. 2:45for lock
99. 2:46to be released well lock is not zero so
100. 2:48i'm going to sit
101. 2:49do nothing while lock is set to one or
102. 2:51or grabbed
103. 2:52okay now it's zero the moment it's
104. 2:54released i'm unlocked and what i want to
105. 2:56do
106. 2:56i one of the threads i'm gonna grab it
107. 2:59i'm gonna set the lock
108. 3:00lock equals one now i've got the lock
109. 3:02whatever that share resource
110. 3:04is maybe here it's pi the summation i'm
111. 3:06going to say now let me do
112. 3:07i may contribute my stuff to pi so i do
113. 3:09my shared resource
114. 3:11and i that's all sequential by the way
115. 3:13because only one person is
116. 3:14accessing that at one time but that's
117. 3:16okay if the other guy other 99 999
118. 3:18people are still computing their stuff i
119. 3:20grab the lock nobody's looking nobody
120. 3:22needs to write to pie great there's no
121. 3:23loss of time really because nobody's
122. 3:25trying to grab it if somebody else
123. 3:26supposed to go oh i went to grab it now
124. 3:27i'm just waiting it's been waiting just
125. 3:28like i was been waiting before
126. 3:31i contribute my con my contribution into
127. 3:33pi i kind of put my my value into the
128. 3:35final
129. 3:36accumulator and then i have to release
130. 3:38the lock so the next person can do that
131. 3:39so lock equals zero okay that's what i'm
132. 3:41doing
133. 3:42so i spin weight until the lock is free
134. 3:44it's zero i grab it set it to one
135. 3:46do my stuff and then i release it that's
136. 3:48this kind of this kind of code you're
137. 3:49gonna see
138. 3:50all throughout now let's see how this
139. 3:52might work i've got two different
140. 3:53threads
141. 3:54you all run in the same you know the
142. 3:56same stream of execution so they both do
143. 3:58this
144. 3:59one spins awaits the next one spins and
145. 4:01waits now here's the problem
146. 4:05this the thread two finds the lock is
147. 4:08not set
148. 4:09before thread one sets it i talked about
149. 4:12before
150. 4:13how do you handle the fact that these
151. 4:14guys come out of order and in fact
152. 4:16how much time thread one got versus
153. 4:18thread two you know thread one
154. 4:20did one thing and then releases it and
155. 4:22then goes here so
156. 4:24in the time watch this this is this is
157. 4:25by the way just make sure you understand
158. 4:27this is time which that means
159. 4:31this guy was spin waiting until it
160. 4:33became free
161. 4:35then okay it went to go slow motion i'm
162. 4:38going to
163. 4:39set lock one
164. 4:42in that slow motion time thread two
165. 4:44jumped in there
166. 4:45it was spin waiting and it saw that it
167. 4:48was free
168. 4:48now they're both going can you feel it
169. 4:51the race condition to go
170. 4:52set it they both thread one wakes up
171. 4:55sets it to one
172. 4:56thread one thinks i've got control of
173. 4:58the lock
174. 4:59thread two thinks the same thing
175. 5:04and they both now have control of the
176. 5:06lock so that little code that i showed
177. 5:08in the previous slide which looked
178. 5:09really clean and really good you know
179. 5:11spin weight for it then set it do my
180. 5:13private work on it
181. 5:14and then release it stan it doesn't seem
182. 5:17like there was anything wrong with that
183. 5:18except when they interleave in a way
184. 5:20that two different threads
185. 5:22thought they were waiting for it they
186. 5:23both wake up and they both
187. 5:25grab for the look and they both said it
188. 5:29and they both think that they controlled
189. 5:30it what's going to happen is you're
190. 5:32going to lose one of those values
191. 5:33each one of those is going to contribute
192. 5:34their stuff into some and one is going
193. 5:36to be overwritten by the other guy
194. 5:38that contribution is lost now this is
195. 5:40trouble
196. 5:41this is real trouble so
197. 5:44this is an issue both believe both
198. 5:46threads believe they got the lock
199. 5:48and by the way try as you like there's
200. 5:50no solution to this you know as you try
201. 5:52to hit that bullseye
202. 5:53you're going to continue well let's what
203. 5:55if you had two locks and one grabs
204. 5:57no i don't care how clever you're going
205. 5:59to be we can't solve this at this
206. 6:01at this level we can't solve this go
207. 6:04ahead good luck
208. 6:04i'll wait pause the video go ahead i'll
209. 6:07wait
210. 6:08it's not going to happen you're not
211. 6:09going to find a solution c to solve this
212. 6:11problem
213. 6:12this is deeper it's deeper there's
214. 6:14something more fundamental we have to
215. 6:15add
216. 6:15at a lower level so we have to add some
217. 6:17new instructions
218. 6:18only way to do that we'll see that in
219. 6:20the next lecture so
220. 6:22last slide on this series i'm very
221. 6:23excited this is the second part of tlp
222. 6:25tlp2 openmp we love
223. 6:28very simple parallel extension to see
224. 6:30like how many more lines like an include
225. 6:32line and in a parallel
226. 6:33you know pragma and you've got a
227. 6:35parallelization we love it go play with
228. 6:37it
229. 6:37stop this video and start playing with
230. 6:39this that's wonderful all you do is say
231. 6:40parallel forward there
232. 6:42c is easy to learn uh not very high
233. 6:44level so it's easy to get in trouble
234. 6:46so by living in c rather than say going
235. 6:48to go and trying to do the same thing
236. 6:49try to compute you know parallel try to
237. 6:52try to add up uh some values of pi
238. 6:54in go and see what explore how how
239. 6:56different different or difficult or easy
240. 6:57it is to do that
241. 6:58compared to doing it doing it in c here
242. 7:00with with the openmp
243. 7:02we also saw that race conditions are an
244. 7:04issue we try to introduce locks and
245. 7:05semi-fours as a way to do that but we
246. 7:07saw that we can do at the sea level
247. 7:09we have to go even deeper to the
248. 7:10assembly level to be able to work with
249. 7:12that so we need some new instructions
250. 7:13we're going to see how to do that in the
251. 7:14next
252. 7:15next series of lectures okay we'll see
253. 7:17you then