[CS61C FA20] Lecture 30.4 - Virtual Memory II: VM Performance — Transcript

Full transcript

1. 0:00[Music]
2. 0:10hello
3. 0:11and welcome back to our operating system
4. 0:13and virtual memory module
5. 0:17but now we know pretty well how does the
6. 0:20virtual memory
7. 0:21system work and even we even know how to
8. 0:24implement it so what is left is
9. 0:26to evaluate its performance and we even
10. 0:29actually know that
11. 0:30because we're going to be using the same
12. 0:32set of
13. 0:33principles that we have used for
14. 0:35evaluating the performance of
15. 0:37our cache so
16. 0:40to get started let's compare cache
17. 0:44and virtual memory system so whatever in
18. 0:46the cache version whatever we use to
19. 0:48call a block or a line
20. 0:50is going to correspond to a page in a
21. 0:52virtual memory system
22. 0:54cache misses correspond to page faults
23. 0:58block sizes and caches were 32 to 64
24. 1:01bytes
25. 1:02typical page size that we are dealing
26. 1:04with is 4 kb
27. 1:05um sometimes page sizes are a little bit
28. 1:09smaller 2 kb
29. 1:10can be larger 8 or 16 kb but we
30. 1:13typically deal with
31. 1:144 kb pages placement
32. 1:18in cache can be direct mapped or n-way
33. 1:21set associative
34. 1:23generally in
35. 1:26virtual memory systems our pages
36. 1:29are fully associative dlbs are fully
37. 1:33associative
38. 1:36replacement policy in cash can be least
39. 1:39recently used or random
40. 1:41or anything in between those two
41. 1:45in virtual memory system we
42. 1:48generally would like to go with the
43. 1:51leads
44. 1:52recently used but sometimes we'll
45. 1:53approximate it with something
46. 1:55that may end up being either a fifo or a
47. 1:58random
48. 2:01when we talk about
49. 2:05right back policy writing back to the
50. 2:09to dram in case of
51. 2:12a cache we can we we have options for
52. 2:16right throw and right back in virtual
53. 2:17memory systems
54. 2:19we only write back because the penalty
55. 2:22of writing back writing through
56. 2:26to the disk is so high
57. 2:29so we're ready to evaluate the
58. 2:31performance
59. 2:33performance in a virtual memory
60. 2:36system is going to be evaluated in the
61. 2:38same way how we evaluated the
62. 2:40performance
63. 2:41of our cache system uh virtual memory
64. 2:44is the level of memory that is
65. 2:48below the main memory in our previous
66. 2:50calculations
67. 2:51everything stopped at the main memory at
68. 2:53the dram level
69. 2:54now virtual memory extends the dram
70. 2:58into the cache through paging
71. 3:02our virtual memory extends the dram into
72. 3:06a disk by using paging
73. 3:10so although tlb comes before the cache
74. 3:14it affects the data you know data
75. 3:17transfers
76. 3:18from the disk to the main memory so
77. 3:22in our previous calculations main memory
78. 3:24was the lowest level
79. 3:26we just need to account
80. 3:29for cases where our data is actually not
81. 3:32in the dram but we have to go all the
82. 3:34way to a disk to retrieve it
83. 3:37so same metrics of cycles per
84. 3:40instruction
85. 3:41and average memory access times are
86. 3:44going to
87. 3:45apply but this time we are going to
88. 3:49uh treat our main memory as some kind of
89. 3:53an intermediate
90. 3:54level cache so we are going to go to l1
91. 3:57cache
92. 3:57hit misses speculations then
93. 4:01our calculations then l2 hits and misses
94. 4:04then we're going to hit into the drum or
95. 4:07miss and
96. 4:08end up in the disk so
97. 4:12here are some of the parameters that we
98. 4:14care about so
99. 4:15when we calculated you know in our
100. 4:17calculations we had cpu cache and the
101. 4:20primary memory
102. 4:21now we are going to have cpu primary
103. 4:24memory and the secondary memory
104. 4:26so when we're talking about the caches
105. 4:29we talked about the cache entry in
106. 4:32demand paging
107. 4:33we are dealing with page frames
108. 4:36cache blocks were 32 to 64 bytes as we
109. 4:39said before
110. 4:40pages are for kibi when we talk
111. 4:43about cache miss rate we were
112. 4:46generally happy when we get something
113. 4:48that was in single digits so it would be
114. 4:51typically
115. 4:52you know l1 caches would be like one
116. 4:54percent uh
117. 4:56hits and 20 percent perhaps 10 20
118. 4:59in l2 um
119. 5:02now page miss rates have to be much much
120. 5:06lower
121. 5:06uh typically uh one in ten thousand
122. 5:10or one in hundred thousand or lower than
123. 5:12that
124. 5:14cash hits um would
125. 5:18you know our cash was designed so well
126. 5:20that
127. 5:21and in most processor it will be that
128. 5:23basically
129. 5:24we get the data out of cache in one
130. 5:26cycle
131. 5:28cache miss corresponds to the page hit
132. 5:31in dram
133. 5:32so that will be from then a few tens of
134. 5:34cycles
135. 5:35to 100 cycles now page miss corresponds
136. 5:38to say 5 million
137. 5:40clock cycles because that's how much
138. 5:43does it take us
139. 5:44to go to the disk and corresponds to jim
140. 5:47gray's analogy
141. 5:48of going to pluto
142. 5:52so let's find out what is the impact of
143. 5:54paging on
144. 5:55average memory access time um
145. 5:58so let's assume that we have the
146. 6:00following memory parameters
147. 6:02that are reasonably common and we can
148. 6:04plug in any other numbers that you like
149. 6:06commonly we get to do that in
150. 6:09in our exams so um
151. 6:14let's say that the l1 cache it is
152. 6:18accomplished in one clock cycle and we
153. 6:21do that with
154. 6:2295 of accesses um
155. 6:25l2 cache it takes 10 clock cycles
156. 6:28and the hit rate is 60 of l1 misses
157. 6:34dram takes 200 clock cycles
158. 6:38say say 100 nanoseconds that's kind of
159. 6:40pessimistic for modern systems
160. 6:42um usually would be less but that's okay
161. 6:44for the current calculation
162. 6:46and finally disk takes 20 million clock
163. 6:48cycles
164. 6:49say 10 milliseconds i'll be faster if we
165. 6:52plug in
166. 6:52an ssd so
167. 6:56the average memory access time without
168. 6:59paging
169. 7:00is calculated as this time that if
170. 7:04we don't have a miss if we have a hit we
171. 7:07can do everything in one
172. 7:08clock cycle we get data out of the l1
173. 7:11cache in one clock cycle
174. 7:14and then we need to add the penalty of
175. 7:17missing
176. 7:18so we will miss with five percent
177. 7:20probability
178. 7:22uh l1 and that's going to cost us 10
179. 7:24clock cycles
180. 7:25and then we we miss um
181. 7:29in l2 there'll be five percent of a miss
182. 7:32in l1 times forty percent of a missing
183. 7:35l2 times 200 cycles that is going to
184. 7:37take us to get to dram
185. 7:39so that evaluates to 5.5 clock cycles
186. 7:45all right this is a bit pessimistic you
187. 7:47know modern systems are going to be
188. 7:49a little bit faster than that but
189. 7:52let's see how do we modify this to our
190. 7:55account
191. 7:56for the paged
192. 8:00memory system so to add paging
193. 8:03what we need to do we need to take this
194. 8:045.5
195. 8:09amat and add the impact of paging
196. 8:13um and so let's do that
197. 8:16so average memory access time with
198. 8:18paging
199. 8:19equals to our 5.5 cycles plus
200. 8:22five percent times forty percent five
201. 8:25percent
202. 8:26probability they're going to miss in l
203. 8:28one forty percent are
204. 8:29gonna miss l2 times one minus
205. 8:33the hit rate into the memory that our
206. 8:36data is not going to be in dram it is
207. 8:38going we we are going to have to go all
208. 8:40the way to a disk
209. 8:41and that's going to cost us 20 million
210. 8:43cycles now keep in mind
211. 8:4520 million is a huge number compared to
212. 8:47any other numbers
213. 8:49so this hit rate into memory better be
214. 8:54close to 1. so we mentioned it has to be
215. 8:57better than 99
216. 8:58but let's just take a look at what
217. 9:00happens if it is
218. 9:01just 99 so we plug that in
219. 9:045.5 plus 0.2 times 0.01
220. 9:08that is 1 minus 99 times 20 million
221. 9:12we have a mat of 4 000.
222. 9:15that's like 700 times slower machine
223. 9:19that's terrible that's a horrendous
224. 9:20performance by the way this does happen
225. 9:22in practice
226. 9:24we if we continuously
227. 9:27end up swapping pages
228. 9:30which happens if the if we are running
229. 9:32out of physical memory there are too
230. 9:34many processes
231. 9:35too many classes perhaps sharing a
232. 9:37machine
233. 9:39the machine continuously swaps every 100
234. 9:42cycles or so
235. 9:44is going to go to swap a page with the
236. 9:46disk
237. 9:47and that is called trashing and
238. 9:50typically
239. 9:51when a machine is trashing it's like a
240. 9:54hundred to a thousand times
241. 9:55slower than it normally it
242. 9:59is
243. 10:02so let's see what happens if you have a
244. 10:04little bit better
245. 10:05hit rate
246. 10:09so yeah what this is what we have seen
247. 10:11this is what happens when uh uh
248. 10:14a program is you know if too many people
249. 10:16are
250. 10:17sharing a machine a 10 second program
251. 10:19can take two hours
252. 10:21so what if the
253. 10:24hit rate is 99.9
254. 10:27well things get a little bit better but
255. 10:29not much better it's
256. 10:31still amat is 400
257. 10:34a lot worse than what we have had before
258. 10:36finally let's see
259. 10:37what if it is a more reasonable number
260. 10:40if
261. 10:40our heat rate or our miss into the dram
262. 10:44is one in 10 000
263. 10:46then our amat
264. 10:50gets increased from 5.5
265. 10:54to 5.9 which is more reasonable
266. 10:57and this is something that we will often
267. 10:59encounter
268. 11:02that's basically it what we need to do
269. 11:04for
270. 11:07in this module we can
271. 11:10take a quick break and then we are going
272. 11:12to see how
273. 11:14can we incorporate io devices
274. 11:17into this see you
275. 11:20a bit later