1 00:00:03,460 --> 00:00:08,697 So looking at our dynamic address translation slide here. 2 00:00:08,697 --> 00:00:15,594 Well, what was the motivation for this? Well, we wanted to start running multiple 3 00:00:15,594 --> 00:00:23,193 programs We want to be able to overlap computation with Io And this really leads 4 00:00:23,193 --> 00:00:25,957 us to, some form of multi, multiprogramming here. 5 00:00:25,957 --> 00:00:29,250 So we're going to run around two programs at the same time. 6 00:00:29,250 --> 00:00:33,484 Now, note these two programs might be run by the same user at this point. 7 00:00:33,484 --> 00:00:37,130 We're not really talking about multi-user, multiprogramming. 8 00:00:37,130 --> 00:00:42,011 That's well you probably want protection to do that, but right now we're just 9 00:00:42,011 --> 00:00:46,990 talking about translation. And one of the big challenges here is so 10 00:00:46,990 --> 00:00:53,285 you want two programs to run. What happens if those two programs, were 11 00:00:53,285 --> 00:00:57,583 linked at the same location. So they both want to run at the same 12 00:00:57,583 --> 00:01:03,204 location in memory or the data they want to access when you statically link these 13 00:01:03,204 --> 00:01:06,180 things are is at the same location in memory. 14 00:01:07,520 --> 00:01:15,192 Well, that's kind of inconvenient. So, one, one thing you can start think 15 00:01:15,192 --> 00:01:19,154 about is actually have some notion of relocation. 16 00:01:19,154 --> 00:01:25,058 You may not do this on a, sort of chunk by chunk basis but instead you do it on a 17 00:01:25,058 --> 00:01:31,504 program by program basis. So what we can do is you can have a base 18 00:01:31,504 --> 00:01:37,408 register, so that all addresses that come out of, let's say program one, get added a 19 00:01:37,408 --> 00:01:42,016 certain offset to it. All addresses out of program two get added 20 00:01:42,016 --> 00:01:46,768 a certain offset to it. And the all addresses that come out of the 21 00:01:46,768 --> 00:01:49,864 operating system have a zero added to them. 22 00:01:50,440 --> 00:01:56,344 Okay, well then we can just change this base register and it will effectively move 23 00:01:56,344 --> 00:02:01,259 where our programs are. And we're gonna call the address that we, 24 00:02:01,259 --> 00:02:04,638 when we start out that comes from the program the virtual address. 25 00:02:04,638 --> 00:02:08,120 And the physical address is where it actually is in physical memory. 26 00:02:10,280 --> 00:02:16,120 You can extend this a little bit and even actually add some notion of protection. 27 00:02:17,160 --> 00:02:23,684 So you can add something which says, program two here is only allowed to access 28 00:02:23,684 --> 00:02:27,401 up to this location, or this offset in itself. 29 00:02:27,401 --> 00:02:32,934 And past that point, it should, is not allowed to go access anything. 30 00:02:32,934 --> 00:02:39,376 Well that's actually a pretty easy go-do, and we're going to call that a bound 31 00:02:39,376 --> 00:02:44,584 register. Now, these base and these bound registers, 32 00:02:44,584 --> 00:02:47,322 we're going to look at in more detail in a second. 33 00:02:47,322 --> 00:02:51,812 But it's, you don't want the user program to go be able to change the base and the 34 00:02:51,812 --> 00:02:55,973 bound register.'Cuz if the user program goes and changes the base and bound 35 00:02:55,973 --> 00:03:00,244 register, it can basically re-map itself, or it can possibly make its bound big 36 00:03:00,244 --> 00:03:07,846 enough to go look at the other program. So what is, let's look at a, the hardware 37 00:03:07,846 --> 00:03:15,376 of a basic base and bound translation. So we have a, a program here. 38 00:03:15,376 --> 00:03:19,940 And it's going to do a untranslated address. 39 00:03:22,800 --> 00:03:26,092 That address is going to get added to it some base, 40 00:03:26,092 --> 00:03:31,257 And that's going to be the address you go to access your caches and your memory 41 00:03:31,257 --> 00:03:38,781 with. This address is compared to a bound 42 00:03:38,781 --> 00:03:42,420 register. And if it's bigger than some bound. 43 00:03:42,700 --> 00:03:46,267 It gets slapped on the hand, or it gets killed. 44 00:03:46,267 --> 00:03:52,255 You get some sort of violation. This actually still shows up in modern-day 45 00:03:52,255 --> 00:03:55,334 architecture. Yet it's not super-widely used, but in 46 00:03:55,334 --> 00:03:59,440 x-86, you actually have segments, which have base and bound registers. 47 00:03:59,980 --> 00:04:03,570 So there's some problems with base and bound registers, 48 00:04:03,766 --> 00:04:08,596 Which we'll talk about in a second. But otherwise, you know, this works okay. 49 00:04:08,596 --> 00:04:13,361 You can have different segments. You can have programs that are basically 50 00:04:13,361 --> 00:04:17,670 relocatable by the operating system. By setting this base register. 51 00:04:17,670 --> 00:04:21,130 You can protect memory by setting the bound register. 52 00:04:21,130 --> 00:04:27,070 And if the op, if the application tries to do anything outside of those parameters, 53 00:04:27,070 --> 00:04:31,700 it'll get killed. Questions so far? 54 00:04:32,160 --> 00:04:40,637 Sounds, sounds pretty, pretty good One of the cool things that you can do, is you 55 00:04:40,637 --> 00:04:45,884 can have not only one set of base and found registers, but you can actually 56 00:04:45,884 --> 00:04:48,962 think about having, Actually, before we start, 57 00:04:48,962 --> 00:04:56,160 Before we move off slide, I wanted to say something, something interesting here. 58 00:04:56,560 --> 00:05:04,300 What happens if you have two programs that want to share some data? 59 00:05:06,400 --> 00:05:09,631 Can we do that here? That's definitely an option, you might 60 00:05:09,631 --> 00:05:13,307 want to share data and not code. Or you might want to go the other way, 61 00:05:13,307 --> 00:05:17,262 which is actually more common, is you want to share code but not the data. 62 00:05:17,262 --> 00:05:20,215 So, for instance if you, modern UNIX systems do this. 63 00:05:20,215 --> 00:05:24,560 They, they don't necessarily use this, they use a more of a page based approach. 64 00:05:24,560 --> 00:05:29,128 But, if you launch 100 copies of LS at the same time, the code for LS will be the 65 00:05:29,128 --> 00:05:33,529 same between all 100 different versions. So what you can do is you can actually 66 00:05:33,529 --> 00:05:38,041 point the, the base register at the same location and same the, use the same piece 67 00:05:38,041 --> 00:05:41,726 of physical memory. So, that's a, that's a, that's a nice 68 00:05:41,726 --> 00:05:45,993 little trick here, is you can basically share the same code segments between all 69 00:05:45,993 --> 00:05:49,033 your programs and modern day systems actually do, do this. 70 00:05:49,033 --> 00:05:53,460 They, they share the code segments between all the same versions of the, the program 71 00:05:54,010 --> 00:05:59,308 Obviously if you have someone who's running version 1.2.7 of something, let's 72 00:05:59,308 --> 00:06:04,469 say LS, and someone else is running version 2.3.9 of LS, you can't share the, 73 00:06:04,469 --> 00:06:08,184 the code segment. But your OS will know that those are 74 00:06:08,184 --> 00:06:12,107 different codes. But if it is the exact same code, you can 75 00:06:12,107 --> 00:06:17,542 save a lot of memory by just only having one copy of it in RAM, and not, I don't 76 00:06:17,542 --> 00:06:24,301 know, a thousand copies of it in RAM. So that's, that's the big advantage of 77 00:06:24,301 --> 00:06:31,841 this separation, and in fact, this is actually used, pretty, recently, this is 78 00:06:31,841 --> 00:06:37,477 still used to send vestiges of those as I said as in x86 but the old Cray Vector 79 00:06:37,477 --> 00:06:42,042 super computers actually did not have a more advanced memory system but they more 80 00:06:42,042 --> 00:06:46,050 advanced memory system but instead just had base and bound registers. 81 00:06:46,050 --> 00:06:50,670 And this was actually to some extent okay for something like a supercomputer cause 82 00:06:50,670 --> 00:06:54,511 supercomputers don't typically run lots of programs at the same time. 83 00:06:54,511 --> 00:06:59,710 They typically run one really big program. So it's a little bit easier in that 84 00:06:59,710 --> 00:07:05,107 setting than using an architecture like this for something like general purpose, 85 00:07:05,822 --> 00:07:10,828 operating systems like, you know, your Linux desktop or something like that or 86 00:07:10,828 --> 00:07:14,859 Windows desktop. Okay, so let's take a look at how this 87 00:07:14,859 --> 00:07:19,277 fits into the pipeline here. So here's, here's the pipe line we wanna 88 00:07:19,277 --> 00:07:22,720 add, base and bound register. It's actually not so bad. 89 00:07:22,720 --> 00:07:28,743 We have to add our adder here to add in the base into the program counter. 90 00:07:28,743 --> 00:07:34,937 We need to add an adder for the database register, into all of our loads and 91 00:07:34,937 --> 00:07:38,025 stores. And then we need to add a comparator, 92 00:07:38,025 --> 00:07:43,498 here, a comparator there to check to make sure we, we don't fall outside of our 93 00:07:43,498 --> 00:07:48,059 balance. Now one of the interesting things about 94 00:07:48,059 --> 00:07:50,494 this though, is we're adding a extra adder. 95 00:07:50,494 --> 00:07:54,843 So you think this would slow down our clock frequency a lot, we're adding a 96 00:07:54,843 --> 00:07:57,278 whole another, let's say 32 bit wide adder. 97 00:07:57,278 --> 00:08:00,873 But conveniently, we can, we already have an adder in this path. 98 00:08:00,873 --> 00:08:05,570 We already have an adder in this path. So the adder in this path is basically our 99 00:08:05,570 --> 00:08:09,544 PC plus four calculation. So while we do the PC plus four, we can 100 00:08:09,544 --> 00:08:14,528 overlap that with the next edition. And you can actually have the, the carries 101 00:08:14,528 --> 00:08:19,900 basically happening at the same time and the cost of it is only one extra carry 102 00:08:19,900 --> 00:08:23,914 delay out of a full ladder. Similar sort of thing over here. 103 00:08:23,914 --> 00:08:30,286 It's kind of the same way that you would build a Multiplier or something like that. 104 00:08:30,286 --> 00:08:35,197 Where you actually overlap respective, additions in the multiplier concurrent. 105 00:08:35,197 --> 00:08:39,554 So it's kind of nice that, you know, you can do this relatively low cost. 106 00:08:39,554 --> 00:08:42,685 To some extent, you know, it just sort of melts away. 107 00:08:42,685 --> 00:08:45,631 You could even go faster. I think this node here. 108 00:08:45,815 --> 00:08:50,480 We talk about carry, carry save adders. You can always do carry select adders, 109 00:08:50,480 --> 00:08:55,758 which are even faster where you just have basically one bit that tells whether the 110 00:08:55,758 --> 00:08:59,380 last bit carries or not. But you, you can go quite fast here. 111 00:09:01,620 --> 00:09:07,160 Okay, so let's, let's talk about the challenges of base and bound. 112 00:09:12,760 --> 00:09:20,497 So let's say we have memory here, And we start off with three processes, 113 00:09:20,497 --> 00:09:26,053 User one, user two, user three. User one is sixteen kilobytes. 114 00:09:26,053 --> 00:09:30,949 User two is 24 kilobytes. User three is 32 kilobytes. 115 00:09:30,949 --> 00:09:36,316 And this sort of some open space. Free space here and here. 116 00:09:36,316 --> 00:09:43,190 So all of sudden, more users show up, and they start to run some processes. 117 00:09:43,190 --> 00:09:46,531 User four goes here and fills in this space here. 118 00:09:46,531 --> 00:09:52,122 User five goes down there because it can't fit in this eight kilobytes segment, so 119 00:09:52,531 --> 00:09:58,259 eight kilobytes segment or eight kilobytes free space here and it has to go down 120 00:09:58,259 --> 00:09:59,926 here. Okay. 121 00:09:59,926 --> 00:10:05,106 That's all well and good. Two and three kill their programs. 122 00:10:05,106 --> 00:10:09,611 They stop running their programs, so all of a sudden, this goes away. 123 00:10:09,611 --> 00:10:13,848 Oh, excuse me, two and five goes away. And, and this one goes away. 124 00:10:13,848 --> 00:10:18,353 So we start to get some holes showing up here, and some small holes. 125 00:10:18,353 --> 00:10:23,599 And if you repeat this, sort of, thousands and thousands of times, at some point, 126 00:10:23,599 --> 00:10:28,709 relatively high probability, you end up with lots of little chunks of memory, 127 00:10:28,709 --> 00:10:33,987 which are hard to go reclaim. And this is, this is, memory 128 00:10:34,651 --> 00:10:42,828 fragmentation. If, this is a, if you go look at something 129 00:10:42,828 --> 00:10:47,793 like a modern-day garbage collector, you'll actually try to re-squish all this 130 00:10:47,793 --> 00:10:50,891 data together. But that's hard to do when a program is 131 00:10:50,891 --> 00:10:53,540 running. It's, it's hard to go take these other 132 00:10:53,540 --> 00:10:57,440 programs and go re-squish them It's also possible that, depending on how the 133 00:10:57,440 --> 00:11:00,913 addresses are laid out, you just may not be able to do that. 134 00:11:00,913 --> 00:11:05,348 If you have base and bound, it's possible you might actually be able to go move the 135 00:11:05,348 --> 00:11:07,752 data. But you have to go copy all of the data. 136 00:11:07,752 --> 00:11:11,331 That, that takes time if you have to copy your entire memory system. 137 00:11:11,492 --> 00:11:15,766 This is why something like garbage collectors can be pretty inconvenient, cuz 138 00:11:15,766 --> 00:11:19,720 some of the garbage collectors actually require you to go copy everything. 139 00:11:20,600 --> 00:11:24,520 There're a couple different techniques you probably talked about in your Data 140 00:11:24,520 --> 00:11:27,687 Structures class about how to go do efficient garbage collector. 141 00:11:27,687 --> 00:11:30,100 But, let's say you want to avoid this completely. 142 00:11:30,860 --> 00:11:33,860 So can, can we go avoid this?