[CS61C FA20] Lecture 05.4 - C Memory Management: Memory Management — Transcript

Full transcript

1. 0:00and welcome back so now that you know
2. 0:02about
3. 0:03static area the heap the stack
4. 0:06how much of that do you have to manage
5. 0:08how much of that does the system manage
6. 0:09let's actually dig deeper into that
7. 0:11so the heap is dynamic memory as you saw
8. 0:15before it's a large
9. 0:16pool it's not necessarily contiguous
10. 0:18although every memory request will
11. 0:19result in a contiguous region if i say
12. 0:22int i want a thousand inch it's going to
13. 0:24give you a thousand inch contiguously
14. 0:26then i want another thousand ins that
15. 0:28second thousand may be very far away or
16. 0:30very close to the original
17. 0:31maybe back to back maybe abutted maybe
18. 0:33far away you don't know those things
19. 0:34um as you saw before this is how you
20. 0:37call it you say malik the size you want
21. 0:39how many bytes you want and it returns
22. 0:41uninitialized memory all that's garbage
23. 0:42you didn't have to initialize it
24. 0:44and use it before i mean you have to
25. 0:45write to it before you read from it you
26. 0:46know that before
27. 0:48how did you how do you manage that
28. 0:50memory well code and static are easy
29. 0:51they don't grow and they're managed by
30. 0:53the operating system so don't worry
31. 0:54about it
32. 0:56the stack space is also easy every time
33. 0:57i make a function call a new frame is
34. 0:59created every time you return from a
35. 1:00function call
36. 1:01that frame goes away and that stack
37. 1:02pointer internally moves things around
38. 1:04and you can't get access to that
39. 1:05explicitly
40. 1:06um there are ways around if you really
41. 1:08know how to do it as a pro
42. 1:10but for the most part you know you don't
43. 1:11get access to that you don't you don't
44. 1:13control that
45. 1:14explicitly the system does um
46. 1:17you'll do when you're writing assembler
47. 1:18you'll actually will explicitly do that
48. 1:20but from the point of view
49. 1:21of c it's below your abstraction line um
50. 1:24managing the heap is tricky though uh
51. 1:26you don't have to do a lot of memory
52. 1:27management in terms of thinking about
53. 1:29um where to move things around again
54. 1:31that's that's the os is doing that
55. 1:33but you need to think about the requests
56. 1:35the size requests you make and how you
57. 1:37work with it so
58. 1:37let's actually talk about let's take a
59. 1:39little deeper into that you want malloc
60. 1:41and free to be fast
61. 1:42um stack allocation was really fast
62. 1:46here int ar open square bracket of a
63. 1:48million
64. 1:49really fast if it works if it doesn't
65. 1:50work it crashes but if it works it's
66. 1:52fast really so that's great but you want
67. 1:54malicking for you to be fast
68. 1:55you want to memorize memory overhead how
69. 1:57much overhead how much bookkeeping you
70. 1:59need to keep track of to do this
71. 2:00and you want to avoid fragmentation
72. 2:02you've probably heard of this with your
73. 2:03disk where you have
74. 2:04you know one file might be broken up
75. 2:06into lots of pieces
76. 2:08and that's an issue actually with malek
77. 2:09and that's probably the biggest issue so
78. 2:11how we deal with fragmentation is the
79. 2:12core problem with that
80. 2:14and technically we call this external
81. 2:15fragmentation because you have these
82. 2:16things there is something called
83. 2:17infernal fragmentation
84. 2:18we'll talk about that at some other time
85. 2:22so here's an example of what
86. 2:23fragmentation looks like so
87. 2:25you put a request r1 for 100 bytes boop
88. 2:27there's 100 bytes yay we got our space
89. 2:30then you make r2 for one byte there
90. 2:32there's a byte
91. 2:34then i free r1
92. 2:38fragmentation those two spots are now
93. 2:41your memory has been fragmented to two
94. 2:42areas and when you say request r3
95. 2:45where does r3 go does it go above does
96. 2:47it go below
97. 2:48how is it being smart about where to put
98. 2:50r3 thinking about what your past pattern
99. 2:52has been
100. 2:53and what you should do so this is an
101. 2:55interesting question how you manage this
102. 2:56memory
103. 2:57how the system manages memory you don't
104. 2:58have to worry about how the system will
105. 2:59manage memory for you
106. 3:02so if you want to read knr there's a
107. 3:04section 8.7 that talks about
108. 3:06some features that we're not going to
109. 3:07worry about um but it talks about some
110. 3:10idea that each block of memory actually
111. 3:12has a header that says the size of the
112. 3:14block
113. 3:14and i pointed to the next guy almost
114. 3:16like a linked list look at that
115. 3:18and it turns out it's a linked list
116. 3:20except we get to the end
117. 3:21in which it wraps around in the
118. 3:23beginning again so it's kind of a
119. 3:24continuous
120. 3:25circular linked list it's kind of neat
121. 3:27as a data structure
122. 3:28and all free blocks all the free blocks
123. 3:30are kept in there so initially in the
124. 3:32program before we had this one big area
125. 3:34and once i you know made a request and
126. 3:36then made a second request and freed it
127. 3:38now the sudden my f we call our free
128. 3:40list now has two elements in that
129. 3:42circular linked list
130. 3:43the top area and the bottom guy are now
131. 3:44two of those elements in matt circular
132. 3:46linked list kind of neat
133. 3:48how's malik work well malek says you've
134. 3:50given me a request
135. 3:52some size i have to now search my free
136. 3:54list to figure out do i have can i
137. 3:56can i uh serve you the memory you want
138. 3:59it
139. 4:00so it looks the free list and it walks
140. 4:02the free list remember it's a linked
141. 4:04list
142. 4:06slow right all the way around if not a
143. 4:09frown it says sorry nothing it returns
144. 4:11null
145. 4:12okay so that's important free
146. 4:15here's what free does here's here's a
147. 4:18here's a free space here's a free space
148. 4:21you're freeing the guy in the middle
149. 4:23well once you free the guy in the middle
150. 4:24shouldn't this coalesce into one big
151. 4:26free space
152. 4:27so free has to do some work so all of a
153. 4:28sudden you realize that malik is no
154. 4:30longer a mile it's a function call right
155. 4:32you know it's you're making a function
156. 4:33called amount so malik isn't like
157. 4:35instant return
158. 4:37ar of a million ar square bracket close
159. 4:39bracket a million that array
160. 4:40request is really fast like that next
161. 4:42line is instant
162. 4:44basically one clock cycle but malik
163. 4:46could take a long time first of all we
164. 4:48got the overhead of a function call
165. 4:49which we haven't talked about yet but
166. 4:50that's there's some overhead to that
167. 4:52and but you need to know at least you
168. 4:54know that the stack has to grow right
169. 4:56it's a function called every function
170. 4:57called grows the stack
171. 4:58so malek has a function the stack grows
172. 5:00just to call malik
173. 5:01it's kind of funny how the stack and
174. 5:02malik are both you know malick's going
175. 5:04to affect the heap but you've got to
176. 5:05grow the stack to even call a function
177. 5:07and that malick is a function
178. 5:09but malik has to then walk its freelance
179. 5:10has to look up its tables and do his
180. 5:12stuff and do its internal mechanics to
181. 5:14walk its
182. 5:14circular free circular list to find out
183. 5:16what you've got and maybe it's a lot of
184. 5:18slivers
185. 5:19wow you can imagine malik takes a long
186. 5:22time
187. 5:22to return null that's crazy in fact
188. 5:24that's the worst case right
189. 5:26it took all the time you paid the price
190. 5:28in terms of clock cycles
191. 5:29your program kind of stalls out and then
192. 5:31you won't see it but i mean internally
193. 5:33if i were
194. 5:33if you're living at the speed of a
195. 5:34gigahertz you'd be like i'm waiting here
196. 5:36i got some places to go
197. 5:38no time no time goes around and now i
198. 5:41waited all this time and then even then
199. 5:42you didn't give me anything really
200. 5:44so that's hard okay
201. 5:48so how do we choose a spot as i'm
202. 5:50searching how do i choose a spot here's
203. 5:52some
204. 5:53common ways to do this so best best fit
205. 5:56says
206. 5:57i go through everybody you ask for a
207. 5:59hundred and i say
208. 6:00of every single freeze block i have in
209. 6:03my circular list
210. 6:04which is closest to a hundred if i have
211. 6:07a hundred done
212. 6:07the first guy first i was looking at was
213. 6:09a hundred done here's the hundred
214. 6:11but if i have 101 well maybe i keep
215. 6:13looking to find a hundred okay
216. 6:14you can imagine that's a little you know
217. 6:16i could have given 101 but who knows if
218. 6:18i would have had a perfect fit later
219. 6:19it's almost like you're trying to close
220. 6:21it's not perfect but
221. 6:22kind of a little long here a little long
222. 6:23there no i want the perfect fit best fit
223. 6:25says the perfect i got to search
224. 6:26everybody to get that you can see the
225. 6:28trade-offs there but
226. 6:29but i will give you exactly the tightest
227. 6:31fit i can now what if i only what if i
228. 6:33had a gap
229. 6:34of 104 and you asked for 100 well i now
230. 6:36have a sliver of four
231. 6:38see that sliver they're gonna start to
232. 6:40accumulate so think about that at these
233. 6:41slivers become now that sliver is still
234. 6:43another element of my list
235. 6:44now i have i used to have a hundred now
236. 6:45i have a little sliver for only four and
237. 6:46so you might have a lot of these slivers
238. 6:48that make my list even bigger
239. 6:50oh yeah first fit says all right i come
240. 6:53into the list
241. 6:54i grab the first guy i can fast as i can
242. 6:56get in get out
243. 6:57bloop anybody bigger than 100 nope nope
244. 6:59yes pick 100 yours go
245. 7:02as i start to use that you might need to
246. 7:04see a lot of these slivers start to
247. 7:05happen at the beginning
248. 7:06right there's always a point to the
249. 7:07beginning of the circular list well you
250. 7:09can imagine the slivers
251. 7:10might start to grow in the front now i
252. 7:12have a lot of these slivers in the front
253. 7:13i keep doing first fit there's a lot of
254. 7:15action in there making a lot of pebbles
255. 7:16think about getting from here to the
256. 7:18deep ocean the pebbles are there like as
257. 7:19you walk to the pebbles to get to
258. 7:21the big rocks down low next fit
259. 7:24says it's like first fit first one that
260. 7:27fits
261. 7:28except that rather than always start the
262. 7:29beginning it rotates wherever i stopped
263. 7:31last time i'll remember that and that's
264. 7:32the next time i'll do it so next fit
265. 7:34says
266. 7:34remember where you were and go through
267. 7:36ah that's where i'll start next time
268. 7:38so then i'll do this so it kind of
269. 7:39distributes the pebbles if you think
270. 7:40about that around that
271. 7:42and that's kind of interesting resume
272. 7:43searching from where you stopped last
273. 7:44time
274. 7:46and there are trade-offs on all three of
275. 7:47them and you can think of workloads that
276. 7:49may make
277. 7:50each one of those three look really good
278. 7:51or really bad you can think of that as
279. 7:52well
280. 7:53in conclusion this is this semi-final
281. 7:56lecture in c
282. 7:56very exciting almost at the end c has
283. 7:58three pulls of memory
284. 8:00static storage the stack the heap
285. 8:03static doesn't move the stack grows and
286. 8:05shrinks with function calls
287. 8:07and it's where your temporary variables
288. 8:08are and your parameters and the heap is
289. 8:10where your malic action happens
290. 8:12okay that the free and malik action
291. 8:13happens three ways to deal with the free
292. 8:16list that malek's going to affect
293. 8:18best fit find the one that search
294. 8:20everybody until they find the one just
295. 8:21snugly fits the best
296. 8:23first fit always at the beginning the
297. 8:24first guy that matches that's bigger
298. 8:25that's
299. 8:26equal to or bigger than the space you're
300. 8:28asking for and best fit says
301. 8:30sorry and next fit says the same as neck
302. 8:32as first
303. 8:33except that you always remember where
304. 8:34you were and start there next time
305. 8:37see the next lecture we're almost there
306. 8:38folks take care