[CS61C FA20] Lecture 30.3 - Virtual Memory II: TLBs in Datapath — Transcript

Full transcript

1. 0:00[Music]
2. 0:10hello
3. 0:11and welcome back to our operating system
4. 0:14and virtual memory module so far
5. 0:17we have figured out how do virtual
6. 0:20memory systems work
7. 0:22and we have seen the role of translation
8. 0:25leukocyte buffers or tlbs
9. 0:27in accelerating this translation from
10. 0:29virtual addresses to physical addresses
11. 0:31all what is left now is to just
12. 0:35implement that in our pipeline
13. 0:39so let's do that so it actually could be
14. 0:42left as an exercise to the listener but
15. 0:44we are nevertheless go ahead and
16. 0:46walk through the implementation
17. 0:49so here is our five-stage pipeline that
18. 0:51we have seen before
19. 0:54we obviously see one modification that
20. 0:57is in here
21. 0:58it is insertion of two tlbs
22. 1:02in front of the instruction cache and
23. 1:04the data cache
24. 1:06because we remember that
25. 1:09tlbs need to precede the cache our part
26. 1:12encounter
27. 1:13is going to issue virtual addresses tlb
28. 1:16is going to translate these virtual
29. 1:18addresses
30. 1:19into the physical addresses before they
31. 1:21go into the cache
32. 1:23similarly our data memory references are
33. 1:27going to be virtual
34. 1:29before they reach the tlb tlb is going
35. 1:32to translate them
36. 1:33to the physical ones now there are
37. 1:35several
38. 1:37events that these tlbs also
39. 1:40need to alert us to
40. 1:43whether we have a tlb miss was there a
41. 1:46page fault
42. 1:47and is there a protection violation
43. 1:51so how do we handle those
44. 1:55first let's take a look at tlb misses
45. 1:57handling a tlb
46. 1:58miss needs a harder or softer mechanism
47. 2:02to essentially walk the page tables and
48. 2:04update the tlp
49. 2:06in most current machines it is done
50. 2:09in hardware and it can be done fairly
51. 2:12quickly
52. 2:13it's essentially what we are looking at
53. 2:14is an implementation of a
54. 2:18straightforward perhaps not so simple
55. 2:20the
56. 2:21state machine that is going to do that
57. 2:24on the other hand handling a page fault
58. 2:29needs a precise trap and we have seen
59. 2:32how we implement those
60. 2:34so if there is a if there is a page
61. 2:38fault
62. 2:38we need to stop that um
63. 2:42and cancel that loader store instruction
64. 2:44because it is going to take forever
65. 2:47so we will perform a precise trap
66. 2:51cancel it and call the operating system
67. 2:54operating system will do something else
68. 2:56most likely
69. 2:57a context switch
70. 3:01so once when the
71. 3:06the page is available in dram will
72. 3:09resume
73. 3:11execution from exact that same
74. 3:14instruction
75. 3:15finally if there is a protection
76. 3:17violation
77. 3:18generally os needs to know about that
78. 3:21and
79. 3:22would typically abort the
80. 3:25current process that made the protection
81. 3:28violation
82. 3:30okay let's take a look
83. 3:33a bit at the practical implementation
84. 3:36here
85. 3:38so we can take our standard five-stage
86. 3:40pipeline that we have already worked
87. 3:42with
88. 3:42and what we need to do is add our tlps
89. 3:47now one thing to notice here is
90. 3:51we have added a memory controller memory
91. 3:53controller
92. 3:55works with the two caches the
93. 3:57instruction cache
94. 3:58and the data cache it is essentially
95. 4:04a digital a chunk of digital logic
96. 4:07that translates things from the
97. 4:10processor
98. 4:11speak to the dram speak so
99. 4:14it is a pretty large digital system that
100. 4:18essentially
101. 4:18knows how to work with the dram knows
102. 4:21how to
103. 4:22refresh it knows
104. 4:25how to issue reads and writes and how to
105. 4:29do
106. 4:30bursts and so on this is not something
107. 4:33that we are going to cover
108. 4:34in 61c or actually
109. 4:38anywhere in our curriculum this is
110. 4:40something that
111. 4:42commonly is a piece of ip intellectual
112. 4:45property
113. 4:46that you buy on the market to integrate
114. 4:48in your product
115. 4:50unless you're a really big company that
116. 4:52has their own
117. 4:54memory controllers okay but the things
118. 4:58that do need to exist in our
119. 4:59processor uh is the support
120. 5:02for handling
121. 5:06page misses so if there is a
122. 5:10miss in a tlb
123. 5:13what we need to do is we need to
124. 5:17walk the page tables and that is
125. 5:19typically done as a hardware state
126. 5:21machine
127. 5:22it starts from the page table base
128. 5:24register
129. 5:25that is set for every process that is
130. 5:28being executed
131. 5:29and page table walker goes and updates
132. 5:33the tlbs
133. 5:36as we have seen we essentially see in
134. 5:38the process
135. 5:39of that when that is done correctly we
136. 5:41see a translation from virtual addresses
137. 5:44to the physical addresses at appropriate
138. 5:46locations
139. 5:51a few other things we basically need to
140. 5:54signal if we
141. 5:55encounter a page fault or protection
142. 5:58violation
143. 5:59either in the instructions or in the
144. 6:03data tlp okay so
145. 6:07that's basically it
146. 6:11to put it all together here is how does
147. 6:14android
148. 6:15translation look like in a practical
149. 6:16system and we are
150. 6:18outlining here things that are done in
151. 6:20hardware
152. 6:22or in software or can be done in either
153. 6:25of those most of the the time nowadays
154. 6:28these
155. 6:29things are done in hardware that can be
156. 6:31done either in hardware and software
157. 6:34that's why we made them more like these
158. 6:37lime greenish than orange-ish so when we
159. 6:40start with a
160. 6:42virtual address we're going to go
161. 6:45through a tlb
162. 6:45lockup most of the time 99.9
163. 6:50something time you're going to have a
164. 6:52hit
165. 6:54if you have a hit we need to check those
166. 6:57bits that are in in our tlb
167. 7:00and whether we are permitted to
168. 7:04do the the operation that we wanted to
169. 7:06do read write or execute
170. 7:07if we are we issue a physical address
171. 7:10and that goes to the cache and we
172. 7:12proceed
173. 7:14further if we are denied we have a
174. 7:17protection fault
175. 7:18that is handled in software by the
176. 7:21operating system
177. 7:22and generally the user sees
178. 7:25a segfault error
179. 7:31now going back to a tlb lockup if we
180. 7:33have a
181. 7:34tlb miss we need to perform a page table
182. 7:38walk
183. 7:38that can be done in software hardware
184. 7:40but generally now is done in hardware
185. 7:43and if the page is in the memory
186. 7:46we'll update the tlb and carry on
187. 7:49that happens quickly a few clock cycles
188. 7:51and we're good
189. 7:52if the page is not in the memory it's in
190. 7:54the disk we
191. 7:56are going to issue a page fault so
192. 7:59and let os load the page and do
193. 8:02something else in the meantime
194. 8:03while that page is coming from the disk
195. 8:07and that's it so few other summary
196. 8:10points here
197. 8:11modern virtual memory systems are there
198. 8:14to provide an
199. 8:15illusion of a large private uniform
200. 8:18store and we have seen how we do that
201. 8:21how many of these mechanisms
202. 8:23go together to make sure that the data
203. 8:26always looks like it's right there
204. 8:28that is within one cycle even though
205. 8:31it could be on on pluto
206. 8:38so we are you know there are several
207. 8:40other things that they're implementing
208. 8:42implemented along the way protection and
209. 8:44privacy that several
210. 8:46um users and processes can
211. 8:50coexist in a processor and each one of
212. 8:52them is going to have their private
213. 8:54address space we do that through the
214. 8:57demand paging that provides the ability
215. 8:59to run programs
216. 9:01larger than the primary memory and that
217. 9:04is also very useful because it
218. 9:06hides differences in machine
219. 9:08configurations people can have different
220. 9:10hardware
221. 9:11and still run the same software
222. 9:17the price for doing that is in the
223. 9:20memory translation and what we do we use
224. 9:22tlbs to accelerate that
225. 9:25and they work seamlessly with the caches
226. 9:28to make our machines
227. 9:32look like they're infinitely fast and
228. 9:34work with infinitely large memory
229. 9:38finally now we actually know
230. 9:41how to define what is happening in a
231. 9:43context switch
232. 9:45so how does a processor run many
233. 9:47programs at once
234. 9:50it uses context switches they're
235. 9:52typically set
236. 9:53by the timer or by
237. 9:56could be done by some external event
238. 9:58like a page fault
239. 10:01that on the context switch the operating
240. 10:04system is going to change the internal
241. 10:06state of a processor
242. 10:09to switch between the processes it has
243. 10:11to save all the registers including the
244. 10:13pc
245. 10:15and change that
246. 10:18value in the supervisor table base
247. 10:20register
248. 10:22or that spt-br such that we can
249. 10:27point to a different set of page tables
250. 10:30what happens to the tlb well it's
251. 10:33invalid it corresponds to the
252. 10:34old process so it needs to be updated
253. 10:38and that's it after this we're going to
254. 10:40evaluate the
255. 10:42performance of our virtual memory system
256. 10:45and wrap up with the module move after
257. 10:48that
258. 10:48to io see you after our quick break