1 00:00:03,320 --> 00:00:08,172 Okay, so, Now we have to look at the hardware we 2 00:00:08,172 --> 00:00:12,109 have to build to, in order to do this. Just to recap. 3 00:00:12,109 --> 00:00:16,360 We have a virtual address. The offset just goes straight through. 4 00:00:16,620 --> 00:00:20,317 The virtual page number goes through some sort of address translation through our 5 00:00:20,317 --> 00:00:22,436 page table. And we come up with a physical page 6 00:00:22,436 --> 00:00:26,284 number, and this is our physical address. Just like with the base and the bound 7 00:00:26,284 --> 00:00:28,500 register. We have a bound, we want to actually take 8 00:00:28,500 --> 00:00:32,046 the virtual address number, and stick it somewhere into something which does the 9 00:00:32,046 --> 00:00:35,278 protection check. So what do we want to check in our 10 00:00:35,278 --> 00:00:38,785 protection? Well, we want to check maybe whether it's 11 00:00:38,785 --> 00:00:43,512 a read or a write, cuz you might want to have some pages that are read only, or 12 00:00:43,512 --> 00:00:48,177 some pages that are write only? You may want to have some pages that maybe 13 00:00:48,177 --> 00:00:52,593 only the, the kernel can access. This is what I was saying about how you 14 00:00:52,593 --> 00:00:55,516 can map all the kernel into your address space. 15 00:00:55,516 --> 00:01:00,741 It's at the same location, but maybe you don't want the user to be able to access 16 00:01:00,741 --> 00:01:05,406 that, unless you're in kernel mode. So a lot of time, there's a bit that says, 17 00:01:05,406 --> 00:01:09,760 is this a kernel access, or is this a, Or an OS access or a user access. 18 00:01:12,200 --> 00:01:18,536 And, One of the challenge here is, is that you 19 00:01:18,536 --> 00:01:22,738 really want this address translation go fast, cuz you don't want to take every 20 00:01:22,738 --> 00:01:27,332 single load in store and turn something that was a one-cycle operation into a, you 21 00:01:27,332 --> 00:01:29,965 know, 10-cycle operation or however many levels. 22 00:01:30,133 --> 00:01:34,727 Unfortunately, you know, you could cache miss on your page cable access and have to 23 00:01:34,727 --> 00:01:37,360 go out to main memory, could even make it worse. 24 00:01:38,900 --> 00:01:45,671 So, We came up with a nice little structure to 25 00:01:45,671 --> 00:01:52,895 be able to solve this problem and this nice little structure here, is, a 26 00:01:52,895 --> 00:01:59,246 translation lookaside buffer or TLB. And what this is, is this is a cache of 27 00:01:59,246 --> 00:02:03,301 page table translations. So you, you shove into it a virtual 28 00:02:03,301 --> 00:02:08,456 address and out comes, er, excuse me. You shove into it a virtual page number 29 00:02:08,456 --> 00:02:14,331 and out comes a physical page number. So it is the direct map, but it's a small 30 00:02:14,331 --> 00:02:18,292 set of these, instead of having the entire, all, all of memory. 31 00:02:18,292 --> 00:02:23,573 So the most recently used, you might write some sort of most recently used algorithm 32 00:02:23,573 --> 00:02:28,966 and raise some other algorithm on this, that when you have a hit in your TLB all 33 00:02:28,966 --> 00:02:33,728 that happens is this, a single cycle. You stick your address in and an address 34 00:02:33,728 --> 00:02:36,944 comes out. If you have a miss, then you might have to 35 00:02:36,944 --> 00:02:41,891 go to some sort of slower case, which has to, let's say, go walk the page table or 36 00:02:41,891 --> 00:02:49,360 multi-level page table, for instance. Let's look at what's in this structure. 37 00:02:50,460 --> 00:02:55,548 You have a valid bit. You typically have a bit that says whether 38 00:02:55,548 --> 00:02:58,424 it's readable. You have a bit that says whether the page 39 00:02:58,424 --> 00:03:01,147 is writable. This allows you to have read-only memory. 40 00:03:01,147 --> 00:03:05,153 If you, for instance, only have the read bit turned on and the write bit turned 41 00:03:05,153 --> 00:03:07,413 off. It allows you to have write-only memory. 42 00:03:07,413 --> 00:03:10,135 Now, you might say write-only memory, is that possible? 43 00:03:10,135 --> 00:03:12,652 Well, yes, Actually this is a thing, if you have, 44 00:03:12,652 --> 00:03:16,247 let's say, two processes that are communicating and you want to have one 45 00:03:16,247 --> 00:03:19,688 process be able to communicate and only write to the other process. 46 00:03:19,688 --> 00:03:23,027 But not to have the other process communicate back the other way. 47 00:03:23,027 --> 00:03:26,520 So one directional channel. You can do this with write-only memory. 48 00:03:29,745 --> 00:03:34,057 Sometimes these, these are merged. Different architectures, some, some are, 49 00:03:34,057 --> 00:03:37,337 not all architectures have write, write-only memory. 50 00:03:37,337 --> 00:03:40,929 But, For, for completeness you want to have 51 00:03:40,929 --> 00:03:44,346 that. You have a, a D bit here, which is the 52 00:03:44,346 --> 00:03:49,132 dirty bit. Yes, this is, this is like the, the song 53 00:03:49,132 --> 00:03:54,430 by the Black Eyed Peas, Dirty Bits. Yes so it's a dirty bit here. 54 00:03:54,670 --> 00:04:00,931 The, the dirty bits allows you to know if the page has been accessed or not. 55 00:04:00,931 --> 00:04:07,433 So let's say you have a writable page and you want to know if that page has been 56 00:04:07,433 --> 00:04:12,932 accessed or written to. You can use this bits, this is similar to 57 00:04:12,932 --> 00:04:17,850 the dirty bits in caches, to know whether the data has to be written back to a 58 00:04:17,850 --> 00:04:23,560 higher level of cache or not. Well, if you think of memory, 59 00:04:23,560 --> 00:04:26,423 Or excuse me, What we have mapped into memory, as a 60 00:04:26,423 --> 00:04:31,118 cache of stuff that could possibly be on disk, we have to know whether to write it 61 00:04:31,118 --> 00:04:34,324 back out to disk. So we can use a, a dirty bit to do that 62 00:04:34,324 --> 00:04:41,424 and it's usually in the TLB structure. Now, there's different, different ways to 63 00:04:41,424 --> 00:04:44,892 build these caches. The most common way is to actually have 64 00:04:44,892 --> 00:04:48,772 them be fully associative. So, for fully associative, you have to do 65 00:04:48,772 --> 00:04:53,476 a tag check.'Cause there's a tag in here, which gets matched against the virtual 66 00:04:53,476 --> 00:04:56,474 page number. And it's associative, so it could be in 67 00:04:56,474 --> 00:04:59,942 any location in this TLB. And then, finally, this is the data 68 00:04:59,942 --> 00:05:03,000 payload, or the physical page number which comes out. 69 00:05:03,640 --> 00:05:10,844 So this is our, our base translation lookaside buffer and it's basically just a 70 00:05:10,844 --> 00:05:15,010 cache of the page table. And what we want to do is at some point 71 00:05:15,010 --> 00:05:18,654 when you take a, a miss in here, so the opposite of our hit, 72 00:05:18,654 --> 00:05:24,056 We're going to pull in a page table entry from our, walk the page table possibly do 73 00:05:24,056 --> 00:05:28,482 that multi-level resolution. We have to go and do multiple loads at a 74 00:05:28,482 --> 00:05:31,281 time and take that data and put it in here. 75 00:05:31,281 --> 00:05:36,878 And now the next time we go to access that same page it hits in here and doesn't take 76 00:05:36,878 --> 00:05:42,757 any more cycles. So is it usually fully associative? 77 00:05:42,757 --> 00:05:48,640 They're usually relatively small, sixteen to maybe a 128 entries. 78 00:05:50,280 --> 00:05:55,191 Sometimes you'll see multi-level version of these, where you have the fully 79 00:05:55,191 --> 00:06:00,168 associated one at the lowest level and then some short of level two, TOB the 80 00:06:00,168 --> 00:06:04,360 backs it, that's a lot bigger and possibly not fully associative. 81 00:06:05,340 --> 00:06:12,700 Couple different designs in here for how to go about replacing, 82 00:06:13,686 --> 00:06:20,657 Having something like true LRU can be hard if this gets large and it's possible that 83 00:06:20,657 --> 00:06:26,727 LRU is not even a good approach. Unlike caches, this is a very different 84 00:06:26,727 --> 00:06:32,866 access pattern. It's not necessarily spatially, there's 85 00:06:32,866 --> 00:06:36,820 not necessarily any spatial locality really going on here. 86 00:06:37,800 --> 00:06:41,805 You probably have temporal localities. So you, that might say that l or u might 87 00:06:41,805 --> 00:06:44,013 be good, But it's not like there is spacial 88 00:06:44,013 --> 00:06:48,172 locality of, because you access one page, there's any problem you can go access the 89 00:06:48,172 --> 00:06:51,972 page after it or the page before it. So lots of the techniques from caches, 90 00:06:51,972 --> 00:06:54,334 prefetching, etcetera doesn't really work here. 91 00:06:54,334 --> 00:06:58,339 But from a replacement perspective, people have tried lots of different things. 92 00:06:58,339 --> 00:07:01,574 Something that actually works surprisingly well, it's just random. 93 00:07:01,574 --> 00:07:05,220 You just randomly chose an entry, Kick something out and you replace it. 94 00:07:06,670 --> 00:07:12,049 Random is actually hard to do sometimes. Believe it or not. 95 00:07:12,361 --> 00:07:20,358 So a lot of times, what people will use is, what's called a clock algorithm, 96 00:07:20,358 --> 00:07:29,089 Where you basically have a free running counter which says where to go access in 97 00:07:29,089 --> 00:07:34,109 your TLB to go evict. And every cycle you go and you somehow 98 00:07:34,109 --> 00:07:39,966 change this counter, maybe increment it by one and there's a little hardware counter 99 00:07:39,966 --> 00:07:44,220 there that will actually do this. And that's not quite random, 100 00:07:44,540 --> 00:07:48,548 Because it's correlated somehow. And that's actually can be a good thing, 101 00:07:48,548 --> 00:07:52,389 cuz that can actually make it so that you can somehow test your processor. 102 00:07:52,389 --> 00:07:56,843 Having something that's true, than random, if you are trying to pick up like random 103 00:07:56,843 --> 00:08:01,464 noise from the atmosphere or true random number generator, that could be very hard 104 00:08:01,464 --> 00:08:03,914 to test. So instead, well, a lot of times what 105 00:08:03,914 --> 00:08:08,145 people will do is use a clock algorithm, such that on every instruction that 106 00:08:08,145 --> 00:08:12,149 executes, you increment the TLB replacement location by one and it rolls 107 00:08:12,149 --> 00:08:15,966 around when it gets to the, the full size of the TLB replacement size. 108 00:08:15,966 --> 00:08:20,558 And what's nice about this is if you reset that register to, let's say, be five, then 109 00:08:20,558 --> 00:08:24,873 you execute 100 instructions, you know what it's going to be 100 cycles in the 110 00:08:24,873 --> 00:08:27,473 future. So you have some predictability in that, 111 00:08:27,473 --> 00:08:31,622 but it looks like random because it doesn't, it doesn't increment, let's say, 112 00:08:31,622 --> 00:08:35,550 with every memory reference, Instead increments with every execution of 113 00:08:35,550 --> 00:08:40,945 an instruction. First in first out has some notion of 114 00:08:40,945 --> 00:08:46,040 locality that works okay, true or you, some people actually do here. 115 00:08:48,500 --> 00:08:52,380 So one of the good questions that comes up is, 116 00:08:53,660 --> 00:09:00,466 If we're trying to access a big array, Can we map enough memory with our TOB to 117 00:09:00,466 --> 00:09:04,300 access that big array without having to take a TOB miss? 118 00:09:06,700 --> 00:09:12,116 So we, we'll call this the reach of the TLB, of all the things you can map of the 119 00:09:12,116 --> 00:09:15,162 TLB. So let's say we have a relatively decent 120 00:09:15,162 --> 00:09:19,271 sized TLB here. We have 64 entry TLB four kilobyte pages. 121 00:09:22,380 --> 00:09:27,840 How much, can we, we go access? Well. 122 00:09:28,560 --> 00:09:36,540 We can go access 256 kilobytes. No, that's not small, but it's not huge. 123 00:09:38,200 --> 00:09:45,285 So it actually does bode for having more TOB entries, it also bodes for possibly 124 00:09:45,285 --> 00:09:50,953 having larger page sizes. Now, this is a traditional sort of trade 125 00:09:50,953 --> 00:09:55,720 off here for caches with block size that having larger page size. 126 00:09:56,220 --> 00:10:01,023 Makes you have larger reach. Makes you have fewer TLB entries. 127 00:10:01,023 --> 00:10:06,453 But it can increase your internal fragmentation and, you might have to pull 128 00:10:06,453 --> 00:10:12,091 more data off the disk if you go to sort of start up a new process, and has these 129 00:10:12,091 --> 00:10:15,154 large pages. And you don't have to use all of it, 130 00:10:15,154 --> 00:10:20,539 You don't want to use all of it. So something to think about is that the, 131 00:10:20,539 --> 00:10:26,900 the, the reach of the TLBs is important, If you don't want to get the OS involved. 132 00:10:28,780 --> 00:10:38,409 So a couple of extensions to the TOB, Something we haven't talked about up to 133 00:10:38,409 --> 00:10:44,268 this point is, what happens, when you have multiple processes running at the same 134 00:10:44,268 --> 00:10:48,852 time or time multiplex between them. What if you do the TLB? 135 00:10:48,852 --> 00:10:54,322 So we talked about changing the page table base pointer when you change to a new 136 00:10:54,322 --> 00:10:55,200 process. Well, 137 00:10:55,480 --> 00:11:00,535 The TLB is a cache of the page table. So when you go to change the page table 138 00:11:00,535 --> 00:11:04,540 base pointer, you're going to have to invalidate your entire TLB. 139 00:11:04,540 --> 00:11:09,316 And if you're doing this let's say, 100 times a second, like you do in modern day 140 00:11:09,316 --> 00:11:14,686 Linux, this can be, be pretty painful or many thousand times a second on some 141 00:11:14,686 --> 00:11:19,720 faster systems, you're going to be trashing your TLB pretty quickly. 142 00:11:20,000 --> 00:11:23,822 So that could be, that could be quite painful. 143 00:11:23,822 --> 00:11:30,702 So solution to this is you actually add extra bits into your TLB, which say, which 144 00:11:30,702 --> 00:11:36,461 process a particular entry in your TLB belongs to and we're going to call this an 145 00:11:36,461 --> 00:11:39,900 address space identifier. So it will get a little bit more general 146 00:11:39,900 --> 00:11:43,652 than a process identifier here. Sometimes some operating systems will 147 00:11:43,652 --> 00:11:47,925 actually use the same, some num, some bits of the process identifier as the address 148 00:11:47,925 --> 00:11:50,009 space identifier, Some, some people don't. 149 00:11:50,009 --> 00:11:54,074 Well, you can, you can leave this as a something which will uniquely identify the 150 00:11:54,074 --> 00:11:56,940 address space. So now, what we can do is we can c-mingle 151 00:11:56,940 --> 00:12:03,643 different processes TLB entries and this address space identifier takes part in the 152 00:12:03,643 --> 00:12:09,008 associative lookup in the TLB. So, our, our match operation checks the 153 00:12:09,008 --> 00:12:14,745 tag and it checks to make sure our address space identifier is equal to a special 154 00:12:14,745 --> 00:12:19,223 register which is on the side, Which, which is added, which is the 155 00:12:19,223 --> 00:12:22,791 address space ID for the currently running process. 156 00:12:22,791 --> 00:12:26,080 So we're actually going to check this and that. 157 00:12:26,940 --> 00:12:31,682 Now sometimes, you do want to actually ignore the address space identifier. 158 00:12:31,682 --> 00:12:35,399 So a good example of this is, like, Operating Systems pages. 159 00:12:35,399 --> 00:12:40,718 So if you have the Operating System mapped into every single process out there, you 160 00:12:40,718 --> 00:12:47,617 don't necessarily want to be polluting your TLB with separate copies of the page 161 00:12:47,617 --> 00:12:51,827 table entry for all the different Operating System pages. 162 00:12:51,827 --> 00:12:56,386 So a lot of times if you add an address space identifier, you also add a global 163 00:12:56,386 --> 00:13:00,771 bit that comes that into the match. And the global bit basically says, ignore 164 00:13:00,771 --> 00:13:05,100 the address space identifier and turns it back into the case we had before. 165 00:13:05,620 --> 00:13:09,140 This is traditionally only used for Operating Systems pages. 166 00:13:09,580 --> 00:13:14,210 And then finally, something I wanted to say as a sort of a need extension here is 167 00:13:14,210 --> 00:13:17,983 to have variable size pages. So instead of our basic TLB which has, 168 00:13:17,983 --> 00:13:22,442 let's say, one page size, four kilobytes or one megabyte or something like that. 169 00:13:22,442 --> 00:13:26,673 You have some bits in the page table entry, which actually say, this is not 170 00:13:26,673 --> 00:13:30,617 part of the match, well, actually this is part of the match, I guess. 171 00:13:30,617 --> 00:13:35,362 You do have to go to look this up cuz this is going to change how many bits of the 172 00:13:35,362 --> 00:13:39,371 tag to look at. When you're going to use this and you're 173 00:13:39,371 --> 00:13:42,912 going to say, oh, The output is a different page size, 174 00:13:42,912 --> 00:13:48,495 So we can have one megabyte pages and four kilobyte pages at the same time in our 175 00:13:48,495 --> 00:13:51,831 page table. And you can use large pages for large 176 00:13:51,831 --> 00:13:57,074 pieces of memory that you know are going to all be there and small pages for 177 00:13:57,074 --> 00:14:01,160 something where you're worried about internal fragmentation. 178 00:14:01,760 --> 00:14:05,817 So you can think about having the, the page size and most architectures do have 179 00:14:05,817 --> 00:14:08,694 page size. A lot of architectures have something like 180 00:14:08,694 --> 00:14:13,009 an address space identifier these days. And some architectures will actually have 181 00:14:13,009 --> 00:14:17,272 an address space identifier that's hidden from the Operating System or hidden from 182 00:14:17,272 --> 00:14:19,943 the programmer and it tries to figure it out itself. 183 00:14:20,097 --> 00:14:24,155 So it's not architecturally visible but the micro architecture effectively has 184 00:14:24,155 --> 00:14:25,440 address space identifier.