WEBVTT 1 00:00:04.620 --> 00:00:13.410 William Cheng: Okay. Welcome to lecture 22 so for some reason. Last lecture I was confused. I thought last lecture was lecture 22 as it turns out it was actually 21 2 00:00:14.190 --> 00:00:22.800 William Cheng: So, sorry about that. So this is the actual lecture number 22 okay so Colonel to you have a little over 3 00:00:23.220 --> 00:00:28.350 William Cheng: Around a week and a half to finish. If you have come from previous semester, don't look at them. Don't copy them best to get rid of it. 4 00:00:28.890 --> 00:00:38.820 William Cheng: Grading guidelines. The only way we'll grey, you need to pass all the testing BFS test RC and favor FS test RC and also just like in Colonel one all the printout must be correct. 5 00:00:39.270 --> 00:00:44.280 William Cheng: When you run favorite FS test RC. So I think people in Colonel one 6 00:00:44.790 --> 00:00:54.810 William Cheng: Some people the printer is wrong, they don't you know as I mentioned before, you're allowed to exchange the printer of your program. The class Google rule and as other people if they see the same thing, I guess. 7 00:00:55.320 --> 00:01:01.260 William Cheng: Nobody did that so you know and anyways. Maybe you should consider doing it and 8 00:01:02.160 --> 00:01:12.450 William Cheng: As usual, after you make a submission and make sure you verify your current submission and you must copy K to Readme file into vs Readme file and then deal with all the question marks. Okay. 9 00:01:13.080 --> 00:01:22.080 William Cheng: You should try to finish Colonel to by next Tuesday. So this way you can start Colonel three as early as possible so that you can have about three and a half weeks to finish Colonel three now. 10 00:01:22.710 --> 00:01:34.920 William Cheng: By the end of the lecture next Monday. You will have everything you need anything, you need to know to finish Colonel three. Okay, so next lecture is going to be, you know, sort of the we're gonna wrap everything up. 11 00:01:36.720 --> 00:01:44.040 William Cheng: Okay, and also the next lecture, we're going to finish chapter seven, that, you know, that's why you have everything that you need to know to implement Colonel three. Yeah. 12 00:01:44.310 --> 00:01:54.390 William Cheng: All right, so last lecture, we were at the end over here we're sort of going over an example where you get a paintball and then as it turns out, your buddy system is rather page frames. 13 00:01:54.900 --> 00:02:00.000 William Cheng: So in that case, we need to write out a page on to the days right right right it back to the back end store. 14 00:02:00.240 --> 00:02:02.850 William Cheng: And then our current affair will go to sleep, wait for it to get done. 15 00:02:03.030 --> 00:02:12.780 William Cheng: And we finish getting it down. We need to go transfer data from this into into memory. So in this case, in that one page for out, we need to wait for the disk twice. Okay, we mentioned before that this is about 16 00:02:13.140 --> 00:02:21.690 William Cheng: The SSM is about 10 you know you know one millisecond to 10 millisecond. If you have to wait for this twice. I then you kind of performance is going to be really, really slow. 17 00:02:21.990 --> 00:02:31.080 William Cheng: Yeah so. So what is wrong with this approach. Well, what's wrong with this approach is that we're doing lazy evaluation and lazy evaluation in this particular case is actually the wrong thing to do. 18 00:02:31.500 --> 00:02:35.250 William Cheng: Guys okay there you know when we do on demand paging lazy value is great. 19 00:02:35.820 --> 00:02:40.860 William Cheng: But when you run a page frame while lazy evaluation is really bad, right. So why are we doing lazy evaluation. 20 00:02:41.160 --> 00:02:50.640 William Cheng: So in this case is lazy evaluation because we wait until our the buddy system run out of page frame and then we start writing it out to the desk. Okay, so maybe we should do something different. Okay. 21 00:02:52.410 --> 00:02:59.010 William Cheng: All right, so, so, so, so, so again, over here says a patient can result in this corporation and slow everything down. 22 00:02:59.490 --> 00:03:05.250 William Cheng: So we don't really want to wait for the desk, because this is too slow. Okay. So, therefore, you know, we need to reduce latency. 23 00:03:05.790 --> 00:03:10.560 William Cheng: So typically, there are two two things that you can do. Our number one is pre fetching okay 24 00:03:11.130 --> 00:03:17.220 William Cheng: So so pre fetching over here is our so that when you try to go fetch a page. Hopefully we are when it, when it comes to the time will you 25 00:03:17.550 --> 00:03:25.080 William Cheng: Will reach out to fetch your page, the page is already in memory as okay how do we do that while again, we use a cash instead of houses mobo we're going to be cash. 26 00:03:25.410 --> 00:03:31.290 William Cheng: So whenever we try to get data instead of getting only one page of data funded this, why don't we get a lot of pages on the desk. 27 00:03:31.830 --> 00:03:43.710 William Cheng: Okay, so this way you know this is so this way when we try to go face to perish. We're going to, we're going to end up the page is already memory, so we don't have to go to the disk, you know, the go through this a second time. 28 00:03:44.400 --> 00:03:48.930 William Cheng: Okay, so that that will help a little bit and the other solution over here is to use the page on demand. 29 00:03:49.410 --> 00:04:02.640 William Cheng: So in this case, when we try to write the pages to this. We're gonna do this using. We're going to do this not using lazy evaluation because lazy evaluation is very bad. We're gonna actually do the opposite the opposite of lazy evaluation is nice eager evaluation. 30 00:04:03.090 --> 00:04:10.920 William Cheng: Okay, so we're gonna we're gonna see what kind of approaches that, how would that help in this case now. Alright, so the first idea of years to do pre fetching 31 00:04:11.340 --> 00:04:18.960 William Cheng: You try to read a one or four kilobytes of data. Why don't you read 16 kilobytes of data. Okay, so this way you know after you 32 00:04:19.920 --> 00:04:22.050 William Cheng: After you finish using the do this particular page. 33 00:04:22.260 --> 00:04:32.550 William Cheng: Next time where you get a page for most likely you're going to go to your address space and you got to go to the next page, and then I tried to access data there. Right. So, therefore, we can actually read ahead get get all these data, you know, 34 00:04:33.360 --> 00:04:38.550 William Cheng: In into memory buffer. So next time, will you need this data over here. It's already there. 35 00:04:39.480 --> 00:04:42.810 William Cheng: Okay. So as it turns out, this help a little bit, but it doesn't really help too much. 36 00:04:43.230 --> 00:04:47.250 William Cheng: Because it's very difficult to predict exactly what is the page, what is the next place that you want. 37 00:04:47.550 --> 00:04:54.090 William Cheng: Right, because, you know, the way we run our program is that we are program I function. And we've got to make system call the system calls all over the place. 38 00:04:54.300 --> 00:04:56.970 William Cheng: Right. Because later on when the link or try to plan your address space. 39 00:04:57.180 --> 00:05:05.460 William Cheng: It would just take all these functions they pack them together into your address space. Some of them will on that. I mean this page. Some of them will end up in some other pages. They don't have to be contiguous 40 00:05:05.970 --> 00:05:11.490 William Cheng: Again, typically, our function is very, very small, we typically don't execute four kilobytes of CO until we make function call. 41 00:05:12.210 --> 00:05:23.040 William Cheng: Okay. So, therefore, this might help a little bit. But in the end, doesn't really help the the doesn't really help very much. And also, if you are doing pre fetching that means that you're going to use up the buddy system. 42 00:05:23.370 --> 00:05:32.430 William Cheng: You know, a free patrons very, very fast right every time you try to read one page rank or in this case going to read for page rank. So you're going to use up the buddy system four times faster. 43 00:05:33.150 --> 00:05:38.940 William Cheng: Okay, so this way you know it's going to be more likely the buddy system will run out of pace rain. So again, it doesn't really work very well. 44 00:05:39.270 --> 00:05:50.370 William Cheng: Okay, so some system, you know, they will use the intelligent pre fetch algorithms, try to sort of figure out where things are. But again, doing this itself is not alone doing this by itself is not enough. Right, so therefore we need to do something else. 45 00:05:52.170 --> 00:05:58.050 William Cheng: Alright, so, so let's talk about the replacement policy, right. So what happened is that when you bring the page frame in 46 00:05:58.620 --> 00:06:05.340 William Cheng: We try to bring a page from a distinct memory and you'd call the buddy system to allocate a new page Graham and now the buddy system says, I'm all out. 47 00:06:05.550 --> 00:06:11.460 William Cheng: So at this point you have to execute the replacement policy, right, you need to go to all the PageRank pick out one of them, and I tried to 48 00:06:13.290 --> 00:06:22.410 William Cheng: Write this one the read this one Autodesk well. But in this case, when you're doing this, you're doing lazy evaluation okay and lazy evaluation. The downside is that 49 00:06:22.890 --> 00:06:34.200 William Cheng: You know you're doing things that last moment. So you have to do it. Okay, there's no way to, to, to not to do it at that point because that's how you run out of pace frame. So you have to, you have to write one page out to the desk. 50 00:06:34.680 --> 00:06:40.890 William Cheng: Okay, so why should you should do is I usually I should do the opposite of lazy evaluation which is no as eager evaluation. 51 00:06:41.130 --> 00:06:51.030 William Cheng: We should perform as a separate concurrent activity inside the colonel what he will try to do is that it will actually try to go to the page rank all the time and write all the patient back to the desk. 52 00:06:51.840 --> 00:07:01.980 William Cheng: Okay, so this way every time. Will you try to ask for a patient from the buddy system, the buddy system always say, oh, I have plenty of page ranks. Okay, so this way when you get a pitfall. You never have to wait for a new patron. 53 00:07:03.090 --> 00:07:06.600 William Cheng: Okay. So that's the basic idea over here that we're going to do eager evaluation. 54 00:07:06.780 --> 00:07:15.810 William Cheng: We're going to write out these patients to the desk as early as possible. We're going to use a concurrent activity inside the kernel and the name of this concurrent activity is called page out demons. 55 00:07:16.110 --> 00:07:24.930 William Cheng: Right, you see that already in Colonel one so so now you know exactly what it is. Yeah. So we're going to use a certain set of Colonel called a page on demand to continuously and aggressively. 56 00:07:25.500 --> 00:07:32.880 William Cheng: You know, look for free pages, or how do you look up reply pages you use the page trend that are currently allocated and you read them rewrite them into the backend store. 57 00:07:33.930 --> 00:07:44.220 William Cheng: Or. So the question is that, you know, over here, again, you're doing replacement policy, but you're doing this, replacing policy earlier on. You see, you still need to sort of figure out which pays for him. You need to write to the desk. Yeah. 58 00:07:46.260 --> 00:07:55.650 William Cheng: Alright, so here's a picture of the page on demand. So if you think about, you know, on the left hand side over here. These are all the patients that are using. So we use some kind of a data show to the store or the pace ran 59 00:07:56.130 --> 00:08:01.830 William Cheng: The example that we saw before we keep the into array and keep them to link those you and keeping the hash table or treat data structure. 60 00:08:02.040 --> 00:08:10.200 William Cheng: Doesn't really matter how you do it. We're going to have the page out demon or skin all these pays rent and pick out which one that you want to write it back to the back end store. 61 00:08:10.590 --> 00:08:20.040 William Cheng: Okay, so what you will do is that, you know, on the desk over here, there's this Q over here, the page it man has a queue for itself. So what it will do is it will it will pick out some of these pages will be here. 62 00:08:20.250 --> 00:08:26.700 William Cheng: And we can talk about every person policy which one you pick out and then what we'll do see your schedule them over here to be written out to the desk. 63 00:08:26.910 --> 00:08:34.050 William Cheng: And then you write them to this one page at a time, will you finish writing down to the desk, you can return them back to the buddy system and now they become free patron. 64 00:08:34.260 --> 00:08:41.550 William Cheng: Right. So again, we're going to use the use the term over here, free page frame, even though we know that these are physical pages and they don't want to be on the inside of 65 00:08:41.910 --> 00:08:48.510 William Cheng: Page. Right. Okay. But again, this is what operating system people talking. They use the term page friend and physical page interchangeably. 66 00:08:48.960 --> 00:08:56.250 William Cheng: But alright so this page. I'll do over here is going to is going to scan the US page for him over here, whatever the data surgery is pick out the pace rain. 67 00:08:56.820 --> 00:09:05.280 William Cheng: You know, using the replacement policy and this scheduled them to be written out to the desk. Eventually when there are finished reading out of the day as you return it back to the buddy system. 68 00:09:05.550 --> 00:09:08.730 William Cheng: That. So this way, the buddy system always have plenty of page ranks. 69 00:09:09.420 --> 00:09:19.170 William Cheng: Okay, so this way you know whenever you get a PageRank. So whenever you get a page fall you as buddy system for new page. Read the buddies isn't always say, oh, I have a new patient for you. I don't have to wait, yeah. 70 00:09:19.950 --> 00:09:29.940 William Cheng: Alright, so I'm going to space right and to keep track of the physical pages over here, you know, we can also use multiple page on demand. So, so, so in this example won't have one page on demand. 71 00:09:30.660 --> 00:09:35.220 William Cheng: Right into it. So we can actually have multiple page on demand, or they will actually go through this list more aggressively. 72 00:09:35.820 --> 00:09:40.080 William Cheng: OK. So again, different avenues systemic. There are different design choices. Yeah. 73 00:09:40.890 --> 00:09:50.430 William Cheng: Alright, so we should be the right replacement policy guy. So here's how you know which you know pages are you supposed to do to replace we talked about before a fight for 74 00:09:50.940 --> 00:09:57.450 William Cheng: You know policy is really not not not good. How do you actually implement the final policy. Okay, so, so I'm sort of the sort of 75 00:09:58.170 --> 00:10:08.250 William Cheng: The, you know, take a take an example of the case that you know here is this. What if you have a DVD rack. I mean, I know that people don't have DVD rock anymore because now we have digital music 76 00:10:08.610 --> 00:10:16.920 William Cheng: So let's say that you are visiting your parents, your parents has a DVD rack. Okay. And then you bring you bring home a new DVD and you know they like to watch movies on dvd 77 00:10:17.400 --> 00:10:22.050 William Cheng: So obviously the DVD rugby is completely for guy over here is completely full of DVDs over here. 78 00:10:22.440 --> 00:10:29.430 William Cheng: You bring the new one. There's no space for it. Okay, which DVD that you will take it to the basement to create space for the new DVD. 79 00:10:30.090 --> 00:10:39.210 William Cheng: Okay, would you use the five for scheduling, if you would use the five for a policy. Right. What is the final policy right you saw all these DVD brace on the purchase date. 80 00:10:39.480 --> 00:10:45.330 William Cheng: And on the right hand side over here. This one will be the oldest DVD and on the left over here will be the newest dvd 81 00:10:46.320 --> 00:10:55.050 William Cheng: That. So if you use the first thing first, our policy over here. I'm going to store them based on a purchase day. So using the first in first out policy, I will take the oldest one over here taking the base, man. 82 00:10:55.230 --> 00:11:01.650 William Cheng: And this way. Everybody will move forward and then we'll shuffle, you know, to the front over here and now the new TV. I got over here, I will appended to the list. 83 00:11:02.340 --> 00:11:06.510 William Cheng: Okay, I'll do people actually do this well people actually don't do this. What, why not 84 00:11:06.900 --> 00:11:16.080 William Cheng: Well, because what are the oldest DVD over here is your parents favorite DVD. I mean, as soon as you put it down to the basement and pretty soon they will go back to the base, man. They were the 85 00:11:16.560 --> 00:11:21.810 William Cheng: They will bring it out. Okay, so, so the first thing first, our policy over here is a very bad policy. 86 00:11:22.200 --> 00:11:28.650 William Cheng: Because, you know, maybe the, the, yo, yo, your favorite DVDs actually at the head over here. Alright, so the first doesn't really work very well. Yeah. 87 00:11:29.070 --> 00:11:39.840 William Cheng: Alright, so first thing first are really bad idea. There is also a policy called the least frequently use policy. Yeah. So basically, the idea here is that every DVD over here. I'm going to market, how many times I have watched it. 88 00:11:40.380 --> 00:11:43.740 William Cheng: Okay. So on the right hand side over here will be the least frequently 89 00:11:44.040 --> 00:11:52.620 William Cheng: Least frequently watch DVD on the left hand side over here will be the most frequently watch DVD. Right. Okay, so we're on 11 so maybe this one has watched 100 times 90 00:11:52.800 --> 00:11:59.430 William Cheng: The next one over here will be at two times and they will be 75 times that other and the last one over here will be two times at one time at one time. 91 00:11:59.820 --> 00:12:09.780 William Cheng: Okay, so these are not very popular DVD over here. So in this case, what we'll do that. We'll take the one that has the least number of marks on her because your parents doesn't really like the movie they watch it was never watch it again. 92 00:12:10.410 --> 00:12:15.420 William Cheng: Okay, so therefore, in this case, we're going to put this one into the basement. So do you actually execute a policy. 93 00:12:16.350 --> 00:12:24.930 William Cheng: Around you know way we kind of do this mentally right we look at the movies we see which one is the one we will, you know, we would only watch very often. So, therefore, that would be the one that go to the basement. 94 00:12:25.620 --> 00:12:29.640 William Cheng: Okay, so we can actually implement this policy and this policy will be a good policy. 95 00:12:30.630 --> 00:12:33.090 William Cheng: You know, so you accept the question is how do you actually implement this. 96 00:12:33.300 --> 00:12:43.080 William Cheng: Okay, so, so for DVD. The DVD racks are very, very big, you can actually scan a you can actually sort them or something like that, it's possible you could do that. You can mark every one of these DVDs. But what are these are paste frames. 97 00:12:43.620 --> 00:12:51.750 William Cheng: Will get the pace for him. I mean, every time you access it. Maybe you can increment a reference count over here, we saw before, in the page table entry over here. There's only one bid for reference or not. 98 00:12:51.990 --> 00:12:57.930 William Cheng: Okay. So, therefore, we don't really keep a count on it. Okay. And also, every time we try to reference the bit. How do we actually increment the counter. 99 00:12:58.920 --> 00:13:06.600 William Cheng: Okay, so in that case will be very, very difficult to implement and also we need to talk about these lists and make them make sure they're sorta based on the number of time they are reference 100 00:13:06.930 --> 00:13:16.980 William Cheng: So, you know, you're going to go to your reference page frame all the time to keep them sorta that turns out to be very difficult. Okay. So even though this might be a good idea. Typically people will not 101 00:13:18.360 --> 00:13:28.320 William Cheng: People when I implement it. Okay. And also, you know, we bring in a new DVD or we hear the new DVD, you only watch wines. Right. So in this case, you know, what would you do that you will send it, you know, next time when you bring another dvd 102 00:13:28.740 --> 00:13:30.810 William Cheng: Even though the, the new DVD is pretty good. 103 00:13:31.110 --> 00:13:38.400 William Cheng: Right. But the only be watch one. So next time I'm gonna send you the basic right so that doesn't sound right. So what we can do is that we can actually take our DVD rack over here. 104 00:13:38.580 --> 00:13:46.530 William Cheng: divided into two parts. One of them are not subject to this request and policy and the other parts over here are receptive to the other. The replacement policy. 105 00:13:46.770 --> 00:13:51.420 William Cheng: As we bring in a newbie DVD, they will go to the zone that are not subject to to 106 00:13:51.840 --> 00:14:01.710 William Cheng: To replace them policy. So this way you will watch it for a few time you start labeling there. And pretty soon you can actually move them into the, the, the remaining part of the DVD rack, which are subject to the to this particular policy. 107 00:14:02.250 --> 00:14:07.650 William Cheng: Guys. So that would be one way to do that do this again for pays for and this is really not a, not a realistic policy. 108 00:14:08.400 --> 00:14:12.600 William Cheng: That the next one over here called the LR you policy called the least recently use policy. 109 00:14:13.080 --> 00:14:23.010 William Cheng: If you have taken CS 570 you probably already seen a prove to prove that PROVE TO SAY THEY ARE YOU policies. So this is my least recently use is called the policy, the 110 00:14:23.430 --> 00:14:27.060 William Cheng: Policy is actually the optimal replace them policy under certain conditions. 111 00:14:27.480 --> 00:14:35.100 William Cheng: Okay. So, under certain conditions, doesn't mean that it can actually use it in the operating system. Well, maybe not. Okay. But since its optimal condition condition. Maybe we should 112 00:14:35.340 --> 00:14:42.240 William Cheng: Take a look at it and to see if it's actually a suitable for the operating system. Then, as it turns out, there's actually a pretty good policy for the operating system. 113 00:14:42.510 --> 00:14:52.530 William Cheng: OK. So again, we're not optimal optimal the proof, but since this up under some condition we tried it on your bonuses them. And it turns out it works pretty well. Yeah. So the idea here is that again. 114 00:14:52.920 --> 00:15:02.310 William Cheng: When we look at a DVD rack over here. What is the least recently, use a use policy over here on the right hand side over here is going to be the least recently used 115 00:15:02.610 --> 00:15:06.870 William Cheng: You know, a DVD on the left hand side over here is going to be the most recently used dvd 116 00:15:07.170 --> 00:15:13.110 William Cheng: Okay, so how do you make sure that this list is sorted. Right. So what you will do is that every time when I pick out a DVD over here to watch it. 117 00:15:13.350 --> 00:15:22.680 William Cheng: When I finished watching that this movie become the least the most recently watched DVD, right, because I just watched that. So, therefore, this one will go to the end of the list over here. Everybody was shuffle to the front. 118 00:15:23.550 --> 00:15:30.750 William Cheng: Okay. And then next time I watch another DVD over here. Again, they will become the most recently was pretty soon. This data shorts, it will be self sorted 119 00:15:32.010 --> 00:15:42.630 William Cheng: Okay, so I don't really have to do anything special. I just need to keep watching them as shuffle them to the end of the list and and pretty soon. This you know this entire list will be sorta based on the last time you access that particular dvd 120 00:15:43.470 --> 00:15:51.570 William Cheng: Okay, so even if you have a gazillion, you know, a patient over here, we can actually do it. But again, you know, try to look for Patreon in a linear list is really not. Not a very good way to go. 121 00:15:51.900 --> 00:15:58.320 William Cheng: Okay, so even though the least recently us over here is a pretty reasonable policy to us. And again, under certain condition is actually can be proved to be 122 00:15:58.770 --> 00:16:00.600 William Cheng: You can you can actually prove it to be optimal. 123 00:16:01.170 --> 00:16:08.940 William Cheng: In the operating system. It's really they only typically using sort of at least recently used to store the entire list right because the worst. I mean how impatient. Do you have 124 00:16:09.150 --> 00:16:12.360 William Cheng: Well, you're gonna have millions of page for him. So he puts out a sorta it's going to be really 125 00:16:12.990 --> 00:16:20.520 William Cheng: Complicated that so inside the operating system. What they will do is that they will implement an approximation of the value algorithm. Yeah. 126 00:16:21.210 --> 00:16:23.850 William Cheng: Alright, so let's take a look at the approximations to see how this is done. 127 00:16:24.480 --> 00:16:33.330 William Cheng: So the way that this is done is that we're going to look at the reference bit inside of page table entries over here the reference page over here will tell you which patient has been recently reference 128 00:16:33.540 --> 00:16:45.540 William Cheng: So this many goals, one that means that this page was reference right if this page equal to zero because that means that this page is now reference. So therefore any page friend that's not being referenced it become you know least recently used 129 00:16:45.960 --> 00:16:56.760 William Cheng: Okay, any page or app that has been a reference recently they become the most frequently other the most recently us. Yeah. So the idea here is that you're going to take your all your patient over here, divide into two categories. 130 00:16:56.940 --> 00:17:06.690 William Cheng: One of them are equal to zero. Be here they are equal to one, right, or equal to one, that means that we're going to keep them inside memory or the one that are equal to zero, we send them into the vacuum store. 131 00:17:08.250 --> 00:17:11.130 William Cheng: Okay, so again, why because I'll be here again every time when a patient has 132 00:17:11.520 --> 00:17:19.410 William Cheng: Access over here, the hardware or the MMU over here was said this particular beer. So, therefore, you can actually tell whether you know some of the patient. Over here you have zero 133 00:17:19.620 --> 00:17:25.560 William Cheng: Other recently you reference and then some of the patient or here are not very recently recently reference that 134 00:17:26.400 --> 00:17:37.560 William Cheng: Alright, so, so basically using the single bit inside the inside of a stable entry, you can actually divide all your pace ran into these two categories. Now, so the the way that things are 135 00:17:38.670 --> 00:17:44.910 William Cheng: So bad. So, by the way, why would these some of these patient in my reference more, you know, more often more more recently than 136 00:17:45.390 --> 00:17:57.810 William Cheng: Than the other one. Okay, so if you think about is that your tech stack, man. Why are you cosign men. So what happened is that, you know, DO YOU THINK ABOUT ALL YOUR provide what is all your program do. Okay, pretty much all of your program. What they will do is that it will stay in the loop. 137 00:17:59.160 --> 00:18:03.480 William Cheng: Guys, what did they do that. Why, because that's where the right program will we need to do something that that's repetitive. 138 00:18:03.720 --> 00:18:15.360 William Cheng: So that's why all the program will do it will go in the loop right you see your warm up while you stay in the loop, you know, a reading, reading the data you stay in the loop writing data and then when you start a performance sword operation. You can also store as a loop. 139 00:18:15.690 --> 00:18:23.550 William Cheng: Your one off to you also stay in a loop every piece of poker they stay in the loop. Okay, so, so you will see that some of your program over here. So again, if you look at your program. 140 00:18:24.600 --> 00:18:28.740 William Cheng: Well, I guess, if you look at your program. Some of the page frame over here that 141 00:18:28.980 --> 00:18:36.450 William Cheng: You're saying that Hulu, they will be most recently used all the other ones you use a long time ago. So like your main function. Well, you probably never going to return to the main function. 142 00:18:37.020 --> 00:18:43.230 William Cheng: Okay, so therefore the main function we're called x function will call the wife is your y called z and now see is going to stay in that loop for a while. 143 00:18:43.350 --> 00:18:52.590 William Cheng: So therefore, all the patient that store the the code for the main function for x and y, you can actually see your software out to the backend store and this will only keep the stuff that are currently using. 144 00:18:53.400 --> 00:19:03.870 William Cheng: Okay, because that's, you know, I get this is this is called a referential real locality. Um, it's kind of a fancy name. Basically, they said about your program sometime you know some of the stuff are actually 145 00:19:04.770 --> 00:19:09.510 William Cheng: That has to be used a lot what the other part of your, your, your, your, your, your tech side, man. 146 00:19:09.900 --> 00:19:10.980 William Cheng: They will actually be untouched. 147 00:19:11.190 --> 00:19:20.190 William Cheng: Yeah. Similarly for your stack right so in again in the example of your, this is your stack over here at the bottom of your, is your main function main core x x call why why called z. 148 00:19:20.340 --> 00:19:26.340 William Cheng: And now she's gonna stay inside a little when you say is that a little the top of the stack right I'm over here is going to go up and down and up and down, up and now 149 00:19:26.520 --> 00:19:31.410 William Cheng: What the bottom of the stack, from what we hear that they actually did they will not change. 150 00:19:31.710 --> 00:19:40.770 William Cheng: OK. So again, if the bottom part of your stay in one page, you can actually take that page swap it out to the backing store and later on when you need it. We return from Z back to why then you bring it back on the desk. 151 00:19:41.790 --> 00:19:48.540 William Cheng: Okay, you know, so. So again, you know, for the organism. It's actually very, very difficult to predict exactly what your application. 152 00:19:48.720 --> 00:19:56.190 William Cheng: Is going to do so, therefore, the audience's needs to have a way to actually, you know, start trying to figure out, you know, what page you're not being used on a patient or not being used and then they will 153 00:19:56.970 --> 00:20:07.530 William Cheng: They will actually you know right out of the one that are now recently us right onto the back end store. Okay, so therefore the offices that was simply use the mechanism. When looking at the reference bit over here trying to figure out what to do next. 154 00:20:09.330 --> 00:20:19.410 William Cheng: Alright, so the way that you know they they implement this released recently use policy, again, again, again, again, we're going to implement an approximation of the lease reasons at least recently. 155 00:20:20.280 --> 00:20:29.160 William Cheng: Use policy by using something called a clock algorithm. Okay, so there are two different version or the clock out with them. One is called the 200 clock and the other one is called a One Hand o'clock. OK. 156 00:20:29.640 --> 00:20:32.340 William Cheng: So the to have a car over here we're going to use to pay out demon 157 00:20:32.790 --> 00:20:43.380 William Cheng: Okay, the first one, what it would do is, is get the idea of years that we're going to put all the Patriot around the clock face guys are all the patient over here that I mean again was, well, what does it mean to look around the clock face so 158 00:20:43.920 --> 00:20:46.740 William Cheng: Conceptually, you going to put them into a circular list. Yeah. 159 00:20:47.250 --> 00:20:53.160 William Cheng: So what happened is that every time when the first page or demon wakes up. What do you do that it will go to every one of these pages friend. 160 00:20:53.400 --> 00:20:58.770 William Cheng: And then what it will do is that they will go to the page table entry and set the pace label entry, said the reference with equal to zero. 161 00:20:59.730 --> 00:21:04.140 William Cheng: Okay, so over here. The first page audio via go to every page Ray said the reference 162 00:21:04.860 --> 00:21:12.150 William Cheng: Video of the zero. So, so this one, go go all the way when you go back to 12 o'clock position. The first page demon will go. Go to sleep. 163 00:21:13.020 --> 00:21:15.840 William Cheng: Okay, the second page or demon will wake up a little later how 164 00:21:16.260 --> 00:21:22.890 William Cheng: You know what I mean by a little bit later. Well, it depends on the operating system. I may be some organism over here the wake up one second later. 165 00:21:23.010 --> 00:21:33.090 William Cheng: Someone workout was a two seconds or five seconds later, it doesn't really matter. So what do you, what are the second page on demand. What he wakes up. What do you will do is that it will check the reference bit in the reference equal to one. What does that mean, 166 00:21:33.690 --> 00:21:39.240 William Cheng: What that means that since the last time you said the reference that equal to zero. This page has been recently referenced. 167 00:21:39.930 --> 00:21:48.540 William Cheng: Right because because last time we go around, you said every reference but equal to zero. How can it become one or they must means that some process into your into your organism over here. 168 00:21:48.900 --> 00:21:52.800 William Cheng: You know, I mean, some some processes that and machine over here at references particular page. 169 00:21:53.160 --> 00:21:58.140 William Cheng: Okay, because when they references pretty good a page inside the MMU there will set the pace able entry over here, equal to one. 170 00:21:58.560 --> 00:22:02.700 William Cheng: Okay, so therefore you will see that this one equal to one. So what you will do is that you would see the check the reference 171 00:22:03.180 --> 00:22:08.190 William Cheng: In the reference made over here is equal to zero, that means that this particular patient is not recently used 172 00:22:08.850 --> 00:22:21.360 William Cheng: That's all we hear, you know, I guess need declutter over here it says that if the reference made over here we go to zero. So, so again the, the second page on demand weeks are five seconds later, it means that this page frame has not been touched in the past five seconds. 173 00:22:21.810 --> 00:22:27.360 William Cheng: Okay, so therefore, by definition, is not recently used. So, therefore, we're going to remove this page, and then we're going to send it out to the page. 174 00:22:27.900 --> 00:22:31.590 William Cheng: Where we're going to schedule. Their to be written our backend store. 175 00:22:32.070 --> 00:22:35.910 William Cheng: Okay. And then the second phase of the moon continue we inspect every page friend. 176 00:22:36.210 --> 00:22:41.670 William Cheng: If it turns out the reference, we have over here is equal to one there recently used. So, therefore, the patient stay exactly where it was okay. 177 00:22:41.880 --> 00:22:50.040 William Cheng: Otherwise, if you go to zero, then they would the patient will be removed from this list and will be sent it out to the to the tissue and start writing out to this one page at a time. 178 00:22:51.240 --> 00:22:57.420 William Cheng: Okay, so this is a to Hancock out where that and when the second hand over here. Go back to the 12 o'clock. The second one will go to sleep again. 179 00:22:57.570 --> 00:23:04.140 William Cheng: And next time this different do. The first one is going to wake up maybe five second library maybe 10 seconds later, you're going to do this over and over again. 180 00:23:05.250 --> 00:23:08.280 William Cheng: Okay, so the 200 I'll wear them. It's actually not very, very aggressive 181 00:23:08.640 --> 00:23:13.560 William Cheng: There's also something called the wild one Henry, our them, you only have one page on demand. Right. So this is what it will do is 182 00:23:13.770 --> 00:23:20.310 William Cheng: When a wakes up, he will go to the 12 o'clock position over here. And then what it will do is that is that he will. He will inspect the reference there. 183 00:23:20.520 --> 00:23:29.820 William Cheng: If the reference made equal to zero, then that means that this page is not recently us. So what it will do is that they will again, they were scheduled that page to be written out to the desk and they will remove it from this particular less 184 00:23:30.090 --> 00:23:39.240 William Cheng: Otherwise, if the the reference interview equal to one, that means that this page or this page for me was, was recently used and what he will do is that it was said the reference went back to zero. 185 00:23:39.870 --> 00:23:49.590 William Cheng: Okay, so you were starting to talk on position if this page for Mr equals two, one, what it will do it as n equal to zero, and he will go to the next page rank in the next version, or we r equals one, what it was that equal to zero. 186 00:23:49.920 --> 00:23:55.260 William Cheng: And then we'll keep going. And when they see the patient over here the reference but equal to zero, then it will remove this page rank. 187 00:23:55.470 --> 00:24:00.780 William Cheng: And a schedule as we read other. This would it go back to the 12 o'clock position. Well, what should I do 188 00:24:01.020 --> 00:24:10.230 William Cheng: Well, one thing that you can do. You can actually go to sleep and wake up five seconds later, again, look at all these bits to see if they are recently used if they're recently us up. Then you again. You said reference it back to zero. 189 00:24:10.440 --> 00:24:18.630 William Cheng: And then, and they can do this over and over again. Okay. You can also when you go back to the 12 o'clock position. You don't stop you continue to go like this, you know, 190 00:24:19.560 --> 00:24:30.780 William Cheng: Like this very, very aggressively. So this way you can end up writing a lot of paste rain, you know about about back to their back end storage guys will get different companies to send the implemented different you know version of the clock. Okay. 191 00:24:33.390 --> 00:24:39.810 William Cheng: All right, for weeks, you know, for weenies the toy albinism. So the winning page on demand is actually a toy page of the man. 192 00:24:40.410 --> 00:24:45.810 William Cheng: So, so it doesn't do anything like this. The page or demon is only working out when it's out of memory. 193 00:24:46.260 --> 00:24:49.500 William Cheng: Okay, so basically we next page aren't even using lazy evaluation. 194 00:24:49.680 --> 00:25:00.720 William Cheng: When the buddy system ran out of paper and what he would do is, is that it will actually give a CPU to the page argue and say, Why don't you go to this list, figure out which one you want. You want to write into the back end store and then 195 00:25:00.960 --> 00:25:07.470 William Cheng: When you finished writing an absolute value store, you know, returned to the back to the buddy system. And now the buddy system will be able to allocate new page ramps. 196 00:25:08.280 --> 00:25:18.060 William Cheng: OK, so again this is ok for toy albinism in the real ordinances them though this particular implementation will be unacceptable. Okay, so it's okay yeah for winnings is perfectly fine. Yeah. 197 00:25:19.950 --> 00:25:25.560 William Cheng: Alright, the next thing was sort of want to briefly mentioned over here is that, you know, when you start allocating free page rain. 198 00:25:26.070 --> 00:25:31.050 William Cheng: You know, do you compete with other you know a processes to allocate free patriots. Okay. 199 00:25:31.500 --> 00:25:41.970 William Cheng: So, so, you know, whatever process use up all the patron right so so I call these processes memory hogs, you're gonna have memory. How's that will use up all the all the Patriots. What kind of program is memory hearts. 200 00:25:43.140 --> 00:25:49.500 William Cheng: So, you know, I guess, for those people who are W students are you probably have been running program. There are simulators. 201 00:25:49.800 --> 00:25:58.650 William Cheng: The simulators for, you know, for VMware side and those kind of stuff. Those are, you know, gigantic memory hog. So what it will do is that they will allocate a lot of memory, and they will take up all the physical memory. 202 00:25:59.070 --> 00:26:05.220 William Cheng: Okay. So in this case, all of the other program on your system. They only cooking, you know, every time when they allocate a new page rank. 203 00:26:05.790 --> 00:26:11.160 William Cheng: Then in this case what they have to do is they have to compete with this memory Hall. Okay, so in that case is really, really nice. 204 00:26:11.640 --> 00:26:16.260 William Cheng: So so obvious ism, you know, they actually have to sort of figure out how to allocate memory fairly 205 00:26:16.680 --> 00:26:23.100 William Cheng: So this way, you know, maybe they can punish the memory hall or they can do something different. Yeah. Alright. So basically there are two different kinds of philosophy. 206 00:26:23.370 --> 00:26:30.390 William Cheng: One is global allocation right global education to say that all processes will compare a company pays for him from a single pool. 207 00:26:30.990 --> 00:26:39.330 William Cheng: Okay. So in this case, the problem is that the memory hogs over here, you know, they're very aggressive they need all the memories. But again, if you use BLS as simulation, you know that they need all the memory. 208 00:26:39.570 --> 00:26:44.970 William Cheng: Okay, so the wife is that they will they will eat up all the memory over here. So all the other processes that will keep it getting paid Hall. 209 00:26:45.840 --> 00:26:54.120 William Cheng: Okay, so in that case, they're not being very, very nice. So if you have global location, you're going to worry about the DD, you have to worry about these memory hawks there. 210 00:26:54.660 --> 00:26:59.310 William Cheng: So you're gonna end up with a situation know as thrashing are going to sort of give you an example. One of fashion. Yes. 211 00:26:59.520 --> 00:27:05.580 William Cheng: thrashing or something that you know that that shouldn't really happen when thrashing happen your system performance will be really, really poor. 212 00:27:06.120 --> 00:27:16.680 William Cheng: Guy so so again if you use if using global allocation. It is, you know, you're going to end up with a higher probability of getting too flashy and then in that case your system will become unusable. The only thing you can do is to reboot the system. 213 00:27:17.400 --> 00:27:29.700 William Cheng: Because again, that's really, really bad. The other approaches to use local allocation is a local TV. I think I briefly mentioned. Now, you know, and that the chapter four is where you can do is that every process has his own private pool paste rapes 214 00:27:30.660 --> 00:27:40.170 William Cheng: Okay. So as it turns out, Mike Microsoft window actually does that. So what do we do that every process, they will allocate a private pool or face. Please read and these private pool will not be used by other processes. 215 00:27:41.010 --> 00:27:46.950 William Cheng: Okay, so why don't Microsoft do that. Okay, so basically what it will do is that every, you know, every process will have a pool of pastry. I'm over here. 216 00:27:47.130 --> 00:27:50.490 William Cheng: If your program are very, very nice only use a small number of pace. Right. 217 00:27:50.700 --> 00:28:01.200 William Cheng: Maybe your private pool is enough. So in this case, when you start running your program again you're doing on demand agent. Once you bring I bring all the memory that you need and then you know you're satisfied by your private pool. 218 00:28:01.590 --> 00:28:08.940 William Cheng: Is it turns out that if that's all you need. You can actually, you know, from this one. Are you will program and continue to run without getting a page Hall. 219 00:28:10.380 --> 00:28:17.580 William Cheng: Okay, so. So again, you know, if all the patient that you need are already assigned to you. So this way you don't have to compete with the memory. 220 00:28:17.850 --> 00:28:26.880 William Cheng: The memory hog and what are the memory hog that if you think about on the Microsoft Windows. Remember how it's going to be Microsoft Word is going to be PowerPoint is going to be all the Microsoft, you know, program, you know, like the 221 00:28:27.240 --> 00:28:37.080 William Cheng: Internet Explorer, or these kind of stuff. You don't have to compete with that you have a small pool of memory, you get paid for once for every one of these pastry and once they're applying to memory over here. You never get a page again. 222 00:28:37.800 --> 00:28:46.200 William Cheng: Okay, so this way when you're running a program you're gonna finish very quick quickly and when you finish running your program we go. Excellent. You're going to return all these patient back to the operating system. 223 00:28:47.040 --> 00:28:53.490 William Cheng: Okay. So Microsoft what they actually do is that they encourage people to write these tiny program because they are guaranteed to have a small set of page. 224 00:28:53.730 --> 00:28:58.530 William Cheng: Paste ramps that I don't really know what the Microsoft design is how many patients do they allocate per process. 225 00:28:59.010 --> 00:29:09.540 William Cheng: But this is basically a design philosophy. Yeah. So what if your program require more than the minimum allocation. Why not case if you need extra you know if you need more than the private pool. You have to compete with the global pool. 226 00:29:10.320 --> 00:29:16.470 William Cheng: Okay, so all those memory hog over here, they will start using their private pool. But once they go beyond that they have to compete with everybody else. 227 00:29:17.370 --> 00:29:25.890 William Cheng: OK. So again, different philosophy, you know, Microsoft window use this particular approaches. I think Linux actually use global allocation. Right, so go by allocation is a little easier to implement 228 00:29:26.280 --> 00:29:36.480 William Cheng: But in the end, you can end up with the possibility of fashion. Yeah. So the goal of a Windows will be here. They try to minimize the possibility of a thrashing by using this local application. 229 00:29:37.020 --> 00:29:44.850 William Cheng: Okay, so I guess I guess we'll be using the term slashing. I'm going to sort of talk about what flashing as a fraction is a very, very old term other words that was invented by IBM 230 00:29:45.300 --> 00:29:51.030 William Cheng: So the first time they use your sort of multi programming. They actually, you know, sort of see a fashion happening. 231 00:29:51.540 --> 00:30:02.940 William Cheng: So, so, you know, ever since then. People call it a fashion. Yeah. So we're going to use a very, very silly example to demonstrate what flashing means that, so consider a system that has exactly two page spread that are being usable by the application. 232 00:30:03.330 --> 00:30:10.920 William Cheng: Okay. I mean, of course, this is a really extreme case, use of all the PageRank. You only have to pay them available for your application. 233 00:30:11.340 --> 00:30:23.730 William Cheng: So you run into processes, a process am process be process. A nice exactly one page rank and process be exactly one page, right. So in this case, both of them are very, very happy right process as a has a page and Patreon. 234 00:30:24.030 --> 00:30:35.880 William Cheng: Free number one over here. So process is running using patient number one process be is running in patient. Number two, if this is all they need. They all eventually they will finish running the code and then there will, there will release the PageRank. 235 00:30:36.870 --> 00:30:40.290 William Cheng: Okay, so in that case it will be the best case scenario. So in this case, there is no flashing 236 00:30:40.560 --> 00:30:51.540 William Cheng: But it but but what it process, it will be here actually required to page ranks that. So in this case, you know, a one is over here sitting in patient number one over here. What does a to what he is in the back end store. 237 00:30:51.840 --> 00:30:56.970 William Cheng: Okay. So, therefore, the one with the picture. We're going to try that on the desk over here. We're going to have a second page over here is called a to 238 00:30:57.450 --> 00:31:04.470 William Cheng: OK, so now process. A. Are we here is running in patient number one. So, what it will do is that they will reference page for number two. 239 00:31:05.250 --> 00:31:13.920 William Cheng: Okay, so what's going to happen right now. Right. So, what it will do is that he would try to reference patient. Number two, you're gonna get a page for you trapped into the operating system over here and the audience is. And we're going to use the least 240 00:31:14.130 --> 00:31:17.610 William Cheng: Least recently use policy over here. Which one is the least recently use PageRank. 241 00:31:17.970 --> 00:31:23.610 William Cheng: What a one is the one on the patient. Number one over here is just being used by process. A over here. So, therefore, 242 00:31:23.880 --> 00:31:30.540 William Cheng: You know, pays for a number to over here will be the one has released recently us. Okay. So, therefore, what we're going to do is I'm going to take this page right we're going to 243 00:31:32.340 --> 00:31:32.550 William Cheng: We're 244 00:31:33.870 --> 00:31:39.930 William Cheng: Going to swap it out to the desk when we're swapping out to the desk over here, this patient become unusable right because this patient over here is going 245 00:31:40.410 --> 00:31:48.540 William Cheng: To actually take it, take it and write it out to the desk that will take you know several millisecond for this to happen in the same time over here, this patient become unusable. 246 00:31:49.110 --> 00:31:51.180 William Cheng: So process. A or B or can we run pass as a 247 00:31:51.690 --> 00:32:01.380 William Cheng: War president is actually waiting for page frame over here to to to go to patient number to over here but page number two is not available, so therefore processes not running. So what it will do is it will give a CPU to who 248 00:32:01.830 --> 00:32:11.430 William Cheng: Well so process. A over here. Can I run. So is there for you going to give them the partner the you know the other patient due process be process be also cannot run because as soon as you start running a process be 249 00:32:11.790 --> 00:32:15.030 William Cheng: This patient is not available, so therefore you going to end up traveling to the operating system. 250 00:32:16.290 --> 00:32:26.820 William Cheng: Okay, so in this case over here. We're basically what a way for this paper and to to go get swap out to, to, to the desk and when, if any, shopping out to this, you know, we're gonna we're going to bring in process, you know, a to over here. 251 00:32:28.140 --> 00:32:32.070 William Cheng: into memory and as soon as we're doing this we're going to switch to process. The process is going to 252 00:32:33.630 --> 00:32:42.540 William Cheng: Get ahead of pace fall. So in this case, the first page over here is going to get to the desk. So in this case, from this point on the operating system will do nothing but DuPont handling page fall 253 00:32:43.170 --> 00:32:49.860 William Cheng: Okay, both process and process be none of them will make any progress because they're all waiting for the right pace rain to get brought into memory. 254 00:32:51.210 --> 00:32:57.090 William Cheng: Okay, so this is called thrashing because you know when this happened in the first time you know the IBM computer scientists, notice that 255 00:32:57.510 --> 00:33:02.580 William Cheng: The disk over here is going crazy because all you're doing swapping the page out in and out of the desk. 256 00:33:02.970 --> 00:33:11.010 William Cheng: That this as you start shaking making a terrible noise. They call this terrible noise thrashing ever since then, this particular case is noise thrashing 257 00:33:11.940 --> 00:33:21.990 William Cheng: Okay, so why do you know why. What is this particular case happen right because the, you know, in order for these two processes to run. We need three patron won't have to pace ram that are available. 258 00:33:23.220 --> 00:33:32.760 William Cheng: Okay. So, therefore, the basic idea over here is that if we can keep the number of patients that require less than the total number of patients that are available. Well, in that case, we can never get into slashing 259 00:33:33.570 --> 00:33:43.620 William Cheng: OK. So again, if we add up all the demands for all our processes, if their demand is less than or equal to the number of patients that are available, then they become impossible to get into pace right to get into Thrasher. 260 00:33:44.310 --> 00:33:48.420 William Cheng: Okay. All right. So over here, if we if our demand is too high, we're going to get into thrashing 261 00:33:48.780 --> 00:33:56.190 William Cheng: As it turns out that this kind of thrashing stuff can happen in all kinds of men, a system that pretty much all kinds of computers, you know, computer sciences them. 262 00:33:56.610 --> 00:34:00.930 William Cheng: Actually going to happen. So over here we sort of have sort of a typical, you know, sort of a 263 00:34:01.710 --> 00:34:11.310 William Cheng: Curve for for thrashing on the horizontal axis over here. That's the amount of work that you try to bring into the system. So, this is called a load you try to bring the introduces me 264 00:34:11.910 --> 00:34:18.840 William Cheng: To do so much work. The vertical axis over here is how much work gets done right. It's called super, super there's a number of processing you finish per 265 00:34:19.200 --> 00:34:24.720 William Cheng: Year per second. So at the beginning. Over here we you try to increase the load this, you go into the linear region. 266 00:34:24.900 --> 00:34:33.030 William Cheng: The more work. You brought into the system. This isn't a very, very efficient right you don't have any slashing the more work you introducing this isn't, this isn't can finish all the work. 267 00:34:33.660 --> 00:34:38.250 William Cheng: Okay. So, therefore, you know, in the linear region over here when you double the low you have double the super 268 00:34:39.180 --> 00:34:50.280 William Cheng: Okay. So, typically in a system that's very, very, you know, not very busy. Then they all have they all exist exhibit exactly the same characteristic if you if you double know if you have doubled a super net if you triple 269 00:34:50.610 --> 00:35:00.270 William Cheng: Triple super so in the linear region at some point will you increase the load into your system, you try to add the system to more and more and more work, what's gonna happen or the system is going to become saturated 270 00:35:00.540 --> 00:35:05.070 William Cheng: Now, so therefore, at some point we're going to get out of this leaner region, and we're going to sort of sort of starting to 271 00:35:05.490 --> 00:35:16.590 William Cheng: Become. This isn't become saturated. At some point, I'm going to reach saturation. So what a saturation. When you reach saturation. Will you try to ask the system to do more work the sickness. The system can only produce so much Super 272 00:35:17.580 --> 00:35:28.770 William Cheng: Okay, so at this point you're super, super it's going to be a level off so you see them, but only finished so many processes per second that will be a maximum super and if you add the system to even more work at some point is going to fall. 273 00:35:29.580 --> 00:35:34.080 William Cheng: off the cliff and then are the, the overall system over here is going to become very, very inefficient. 274 00:35:34.530 --> 00:35:38.040 William Cheng: Okay, so this the Supers is I'm over here will be always become nothing 275 00:35:38.340 --> 00:35:50.790 William Cheng: Okay. And that's, that's exactly what we observed when we are we here, you know, operating system. When you get into thrashing you're at the European this curve at the cliff, and you fought. Fought you know you fall off the cliff and this is him become you know very 276 00:35:51.210 --> 00:35:59.190 William Cheng: Much doesn't do anything useful there. So once you get into the zone over here for the fashion. What can you do well, pretty much. There's nothing you can do but turn off the machine. 277 00:36:00.060 --> 00:36:09.870 William Cheng: Okay, well, he turned off the machine, the load is gonna go to zero. And next time when you restart. So, what you should do is that you try to keep away the system from the cliff, because as soon as you get close to the clip. It is possible, doing some 278 00:36:10.170 --> 00:36:15.960 William Cheng: Temporary fluctuation, you're gonna fall off the cliff and they're going to end up with, you know, flashing and this is really bad. 279 00:36:16.260 --> 00:36:27.660 William Cheng: That. So this can happen in all kinds of, you know, computer system it can happen inside the the Albany system it can happen in a database is that you could happen instead of multimedia system. You can even happen to the internet. 280 00:36:28.440 --> 00:36:32.820 William Cheng: Okay, so I guess in the 80s and the 90s. This actually happening to the internet, you know, 281 00:36:33.030 --> 00:36:44.670 William Cheng: You know, people try to send too much traffic into the internet, they brought the entire internet down and the only thing you can do is to reboot the internet. So this way you know that everything has been reset. Okay, so how do you actually keep away from your 282 00:36:46.350 --> 00:36:47.910 William Cheng: Keyboard your system on the clip over here. 283 00:36:48.150 --> 00:36:58.110 William Cheng: Right. I mean, those people who are WC that you probably, you know, learn some control theory, it's all you do is that you can actually, you know, sort of, you know, draw a line over here. And then you say, if I operate on the low line over here. 284 00:36:58.290 --> 00:37:04.200 William Cheng: Then in this case, the system will actually operate on the knee of the curve. So you can. So when you know when you try to 285 00:37:04.470 --> 00:37:09.390 William Cheng: Increase the load over here. There's going to be back pressure to tell you push you towards the knee of the curve. And when you 286 00:37:09.600 --> 00:37:19.950 William Cheng: You know, will we have more capacity or in this case, you will increase the demo of the system and you had operator needs occur because the Neil of curl, we hear is going to be the most efficient your spot inside your system. 287 00:37:20.940 --> 00:37:27.930 William Cheng: Okay, so this is one way to do it. You can actually control your operating system. So again, people will study control theory, they would have to do something like that. 288 00:37:28.500 --> 00:37:33.660 William Cheng: For the phone, computer scientists, they try to not to use, you know, these kind of control theory. 289 00:37:34.260 --> 00:37:45.000 William Cheng: So, so one solution over here was proposed by Peter Denning theater Danny was very famous computer scientists are they come with a solution, you know, for thrashing and this is known as the working set principle. 290 00:37:45.750 --> 00:37:52.440 William Cheng: Now, so the idea of here is what I just mentioned before, you look at the set of pages that are used by the program that's called the working set 291 00:37:53.010 --> 00:38:05.970 William Cheng: Okay, so, so, so we're here, we're going to do this by W. S. A. P of t, the working set that is Ws, so the working set for process over a time period of p is the other the pastry and that are used by this program. 292 00:38:06.660 --> 00:38:15.630 William Cheng: Okay, so if we take the absolute value over here, we can actually count the number of pages over here for this particular program if we add up the working set size for all of your program. 293 00:38:16.500 --> 00:38:22.260 William Cheng: Okay, if that size is less than the physical memory. Well done. In this case, if you can even actually even ever get into thrashing 294 00:38:23.640 --> 00:38:33.930 William Cheng: Okay, so let me say that again we add up the working the size of the working set for all the program that we're running on this machine is a total size is less than the amount of physical memory that you have. You can never get into fashion. 295 00:38:34.920 --> 00:38:40.860 William Cheng: Okay, so therefore your solution can be is that if I add up all the working sessions over here, as this is over here. So, 296 00:38:41.310 --> 00:38:51.600 William Cheng: This is it. This is the amount of my physical memory. Okay. So over time, I can actually add up. I'm working since I have all my process over here as long as they're below the size of my physical memory. I'm going to be okay. 297 00:38:51.990 --> 00:38:58.380 William Cheng: There. So what happened is that when you try to run a new program if if I run your new program. If I look at the working set for new program. 298 00:38:58.590 --> 00:39:05.730 William Cheng: If you add are working says I will be here now it's gonna, it's going to be more than the amount of physical memory. Now what do you do, you don't run the new program. 299 00:39:06.840 --> 00:39:11.640 William Cheng: Okay. So, therefore, this particular approach will give you a mission control policy to say that if a new program. 300 00:39:11.880 --> 00:39:22.920 William Cheng: That they want to start running, you look at the working set size if I, you know, if you add the working size, as I said, the current working said it was going to go beyond the size of the physical memory you refuse to run that program. 301 00:39:23.460 --> 00:39:27.270 William Cheng: Okay, so this way all the program that you need once they get there a page for they're going to have enough 302 00:39:27.600 --> 00:39:38.070 William Cheng: They're going to get all your page, right. So they will run very quickly and they will all finished. And then we'll release or Patreon once they release a page where you can actually see whether you can actually allow new program to be added. 303 00:39:39.780 --> 00:39:40.980 William Cheng: To be added into your system. 304 00:39:42.210 --> 00:39:52.230 William Cheng: OK. So the idea here is pretty good, but in reality over here. As it turns out, the working set size, the size of the working set for your program is very difficult to to actually predict that. So why is that 305 00:39:53.040 --> 00:39:59.700 William Cheng: Right. So if you think about your warm up one right. What is the size of your working set guys are using your, what is your 306 00:40:00.300 --> 00:40:09.150 William Cheng: The, the other. The one more wine. So on the horizontal axis over here is time. Right. The vertical axis over here is going to be the number of page frames that are used by the working set 307 00:40:09.510 --> 00:40:10.650 William Cheng: So in that case, what does it look like 308 00:40:11.190 --> 00:40:17.580 William Cheng: Okay. In the beginning of your program. What are you doing, right. Well, you won't find your reading the input file one at a time and you create a state of shock to 309 00:40:17.700 --> 00:40:23.760 William Cheng: Your LM to the list over here. So at the beginning over here that you actually you're you're increasing linearly with the size of the working set 310 00:40:24.330 --> 00:40:32.580 William Cheng: Okay, once you finish reading all your data, you put them in a list and now you have to sort it right. Well, you saw that you require additional memory buffer want again depends on what kind of 311 00:40:33.270 --> 00:40:39.900 William Cheng: sorting algorithm that you need that you use. If you use the right kind of our then maybe, in this case, the work is that over here is gonna stay constant 312 00:40:40.830 --> 00:40:47.220 William Cheng: Okay, and then you know when you finish sorting over here. Again, this will be here can stay a very long time if you if you're sort of 1 million, you know, records over here. 313 00:40:47.460 --> 00:40:54.000 William Cheng: When you finish over here. You're going to read the data out to the desk right me, you know, read the data to standard out. We've got a data center. Our right 314 00:40:54.840 --> 00:41:03.750 William Cheng: You want to read it to a file. Well, in that case over here every time when you finished writing the record, you can actually free up your memory. So we hear you're working. So as you will go over here will change a change over time. 315 00:41:05.070 --> 00:41:14.370 William Cheng: Okay, so therefore you know this is going to be the profile for your working set for your one on one. What's worse over here is that this particular you know this pretty occur depends on the data. 316 00:41:14.970 --> 00:41:22.470 William Cheng: Okay, if your data. So, so maybe this one is for 1 million records over here. So 1 million records, get a couple of like this. What did you improve not only has, you know, 317 00:41:22.860 --> 00:41:28.050 William Cheng: 100 records. Right. So in this case, it will look like this. You go up a little bit. And they ended up into something like that. 318 00:41:28.860 --> 00:41:30.720 William Cheng: Okay, so the working set over here is actually very, very 319 00:41:31.200 --> 00:41:39.120 William Cheng: Difficult to predict, because it depends on you know what kind of impact your policy, you're proposing a database, you know, then he goes to the database, you get your data. 320 00:41:39.240 --> 00:41:44.730 William Cheng: So in the end, you know, when you try to figure out what the work in search of your program much impossible. It's impossible to predict 321 00:41:46.110 --> 00:41:51.930 William Cheng: Okay, so therefore, even though this is a really good idea in reality is very difficult to implement now. Alright. 322 00:41:52.590 --> 00:42:02.820 William Cheng: So what is the solution over here, right. So the do the solution over here is that, you know, it's all we can do over here is that we can use the Microsoft approach over here the Microsoft, you know, what happened is that every process over here will guarantee 323 00:42:03.480 --> 00:42:09.750 William Cheng: You know, I guess, Microsoft actually called us working set up, they don't really use the work is that principle here. So again, every process will we 324 00:42:10.140 --> 00:42:19.350 William Cheng: Will have a minimum allocation. If you are using with your minimum allocation over here, then you get to finish your program pretty quickly. If you go beyond that, you have to share with everybody else. 325 00:42:19.770 --> 00:42:27.120 William Cheng: Okay, so what it will do is that is that they can't really, you know, prevent your system are going to thrashing because they don't do admission control over here. 326 00:42:27.540 --> 00:42:35.640 William Cheng: We're going to hook up already. But actually, you will actually, you know, see that once in a while, we try to run a program in Microsoft, they will say the out of memory, anything that you're not be able to to actually 327 00:42:36.360 --> 00:42:44.940 William Cheng: run that program. I think that's what earlier version of Windows. I don't really know what whether they can happen on today or not but but basically they're trying to use the work in and says I principle. 328 00:42:45.270 --> 00:42:54.120 William Cheng: So that you know every program will reserve a small amount of memory. So, so this way. They sort of sort of have an approximation of the working set size principle that 329 00:42:54.930 --> 00:43:00.780 William Cheng: So again against that, that that's the Microsoft claim is that they are using this work is that is that principle. Yeah. Alright. 330 00:43:01.320 --> 00:43:11.340 William Cheng: So I guess this is actually a good place to break. So this is the first part of the video for today and next time we're going to go to the next part over here and look at the representative system. Okay.