WEBVTT 1 00:00:06.690 --> 00:00:16.139 William Cheng: Well welcome to lecture 23 so Colonel to do this Friday. If you have cold from previous semesters, don't look at them. Don't copy them best to get rid of their 2 00:00:16.680 --> 00:00:23.430 William Cheng: Grading gamma is the only way to grade you to pass all the tests in BFS test Darcy and favor FS has that see 3 00:00:24.120 --> 00:00:29.430 William Cheng: Just like Colonel one all the output must be correct when you run paper episode has that see 4 00:00:30.240 --> 00:00:37.290 William Cheng: You must copy you know K to remain dot txt into VF as readme txt and deal with all the question marks. 5 00:00:37.650 --> 00:00:46.230 William Cheng: After submission. Make sure you verify your kernel sufficient. Yeah. And so again, you know, go through all the steps to all the README file that kind of stuff. 6 00:00:46.530 --> 00:01:01.170 William Cheng: Or you try to finish Colonel to by tomorrow this Tuesday. So you can start Colonel three as early as possible because Colonel three is bigger than Colonel wanting to combine by the end of today's lecture, you will have everything you need to finish Colonel three. Yeah. 7 00:01:03.540 --> 00:01:15.120 William Cheng: Alright, so. So last time we were here talking about talking about Linux, right. So this is a Linux page for a management, they divided into three different zones. 8 00:01:15.540 --> 00:01:21.480 William Cheng: Every zones, there is buddy system, there is the active page lists. There's an inactive page lists. 9 00:01:21.960 --> 00:01:32.100 William Cheng: We sort of went through the algorithm where you have to do if you, you know, use the clock algorithm decides page is not recently used and you have to make sure that the you know the page name is Mark busy. 10 00:01:32.670 --> 00:01:37.050 William Cheng: So this way that you know that the patient is being written out to the does. So therefore, nobody can use it. 11 00:01:37.290 --> 00:01:42.780 William Cheng: More importantly, if anybody tried to use it, they will get block inside Colonel until you finish reading the data to do this. 12 00:01:42.990 --> 00:01:49.650 William Cheng: Then that patient become clean once they become clean and there's somebody waiting for it. Then in this case you return it to back to the active page frame. 13 00:01:49.920 --> 00:01:58.080 William Cheng: Otherwise, if it turns out that nobody's waiting for the page is not clean you simply return it back to the buddy system. Yeah. Alright, so, so that's what we're talking about. 14 00:01:58.800 --> 00:02:07.410 William Cheng: Yeah, so we're still talking about Linux Linux has a, you know, again, though, I guess the way that you manage manage address space is that you have these memory segment. 15 00:02:07.680 --> 00:02:14.850 William Cheng: And this is where Linux actually changed the name right before we use as region. So this page. So to give you the real data structure. 16 00:02:15.180 --> 00:02:22.920 William Cheng: Linux what they call instead of calling a process control blog, they call it a test constructor. But again, the same idea. Instead of calling a 17 00:02:23.370 --> 00:02:33.480 William Cheng: address space representation. They call it the memory management structure, instead of calling them as region, the column VM areas. But again, it means that the concept exactly the same. Yeah. 18 00:02:34.110 --> 00:02:41.760 William Cheng: So again, every VM area they has a beginning virtual address and virtual address. You know what kind of, you know, a protection does it have 19 00:02:42.150 --> 00:02:48.270 William Cheng: Whether their shadow private and then, you know, coming out of these VM area they point to the anonymous object. 20 00:02:48.630 --> 00:02:56.610 William Cheng: Or they can complete the thought object. So again, the point of all these objects that they can go to the disk and get data for you either on the swap space or from the 21 00:02:57.270 --> 00:03:09.180 William Cheng: From the file system. Yeah, so I guess VM VM as drug is what we call as region. So I think when you are doing weeks when it's kind of like, you know, Linux, so it's called them VM area. 22 00:03:09.900 --> 00:03:15.390 William Cheng: A. So instead of calling VM underscore, underscore squad struck they call a VM area. Yeah. 23 00:03:15.870 --> 00:03:25.740 William Cheng: So so so basically you know area region memory segment. They all mean the same thing. These are contiguous, you know, virtual address virtual addresses. 24 00:03:26.160 --> 00:03:31.290 William Cheng: That have similar stuff that are put inside the memory segment. Right. So typically we think about a tech segment is your code. 25 00:03:31.530 --> 00:03:41.520 William Cheng: And then data and BSS you know these are your global variable and then you have the heap segment for that I make region. And then you have to stack for, you know, then. And then the last one of your stack. So again, 26 00:03:42.120 --> 00:03:50.280 William Cheng: The, you know, we mentioned before that the tech segment you you get the date the backing store is the file system for the heap segment and the 27 00:03:51.000 --> 00:03:56.970 William Cheng: The stack segment. They are anonymous because there's no file system path. So in that case, the backing store is going to be the swap space. 28 00:03:57.420 --> 00:04:02.070 William Cheng: The anonymous object is the one that they know where data is stored. So you can actually ask them to go. Go for it. 29 00:04:02.730 --> 00:04:07.710 William Cheng: That the data and BSS they're a little tricky, right, because in the beginning. They come from the desk. 30 00:04:08.250 --> 00:04:17.400 William Cheng: Okay, but once you bring them into memory. So now they become copy on. Right, right. So, therefore, in that case, at the beginning, they sort of they are managed by the object. But as soon as you bring 31 00:04:17.880 --> 00:04:24.720 William Cheng: You know, bring them to memory. And once you modify it so if they're exactly the same as sitting on the desk. Why, in that case, the back end stores the desk. 32 00:04:25.140 --> 00:04:33.630 William Cheng: Okay, but once you modify the package store needs to go into the heap segment. So in that case, later. All you have to sort of allocate anonymous object is sort of switch the anonymous object. 33 00:04:34.560 --> 00:04:44.520 William Cheng: Alright so this picture doesn't really capture as the story. What they show you what the initial state is before you do any copyright, but once you do copy on write this picture is to change a little bit. Yeah. Alright. So anyways, 34 00:04:45.060 --> 00:04:48.570 William Cheng: Will you do your kernel three. These are the things that you have to worry about. Yeah. 35 00:04:50.520 --> 00:05:01.920 William Cheng: Alright, so when you have a memory map out right. So then again you can add a memory segment over here and this one, you know, points to the file object because if you. And so in this example, we assume that you map a file into outer space. 36 00:05:02.160 --> 00:05:14.340 William Cheng: Of course you can also map anonymous option you can also map anonymous memory into your address base. If you do that, well then over here has to be point to anonymous object. Whereas, again, that's for obvious reasons. Yeah, you know. All right. 37 00:05:15.600 --> 00:05:24.630 William Cheng: For Linux when things get more complicated, right over here is you know that you can map 175 to address space you create, you know, three different Charles threads. 38 00:05:25.350 --> 00:05:27.750 William Cheng: Too much healthier, and over here. So, again, that 39 00:05:28.380 --> 00:05:36.570 William Cheng: That list of VM area now can become really, really long, right, because why because every time when you get when we get a paste. All right. If you go back to the previous picture over here. 40 00:05:36.870 --> 00:05:42.150 William Cheng: Every time when you get a pace fall, you're going to get a virtual address via via the ADR over here. 41 00:05:42.660 --> 00:05:49.500 William Cheng: This is a user space virtual address and the way that you fix the pace file is that you walk down this linear list of VM area. 42 00:05:49.620 --> 00:05:55.350 William Cheng: And find out which one it belongs to. And you look at all these data structure there down here, there are more data structure down below. 43 00:05:55.530 --> 00:06:02.280 William Cheng: You look at all these data structure. So, this is your virtual memory map using all your data struggling in order for you to figure out how to fix the, you know, 44 00:06:02.700 --> 00:06:09.810 William Cheng: How to fix this page fall. Yeah. So what if you're, you know, memory segment look like. That's why in that case you linear let's become really, really long. 45 00:06:10.260 --> 00:06:17.100 William Cheng: So therefore, in Linux, they get the typical way to sort of scale things either you build a tree data structure or you build a hash table. 46 00:06:17.580 --> 00:06:26.790 William Cheng: For Linux they decide to build a tree data structure, right. So again, if you start with the virtual address now you need to perform a lookup operation and find out which memory segment it belongs to. So again, 47 00:06:27.090 --> 00:06:36.720 William Cheng: This case, we use a binary tree and then the worst case performance going to be order login instead of order and so therefore it's going to be a lot better, guys. So again, this is you know the world Linux does 48 00:06:38.280 --> 00:06:44.460 William Cheng: All the Linux page management algorithm or they use a two hander clock out with them. We sort of talked about what that was before. 49 00:06:44.820 --> 00:06:50.730 William Cheng: They will apply to the zone in sequence, right. So, so what will you do, is that is that when the first page atiba 50 00:06:51.120 --> 00:07:03.390 William Cheng: Wakes up what he would do is it will go to the DMA zone, go to the normal zone, go to the high Meza said everything to, you know, to, to reference that equal to zero. Okay, and then go go go to sleep, and later on when the second 51 00:07:03.810 --> 00:07:11.280 William Cheng: The second page ADINA wakes up. What it will do is that I would change that will check all the reference there is a reference equals zero. That means that 52 00:07:11.460 --> 00:07:17.130 William Cheng: It wasn't recently us. So what it will do is that he will map to find the address space for all the program that is using it. 53 00:07:17.400 --> 00:07:25.950 William Cheng: add them to the the the dispute or it can be written out to this and also made the Patreon busy, all that kind of stuff we talked about before. Yeah. Alright, anyways, I'm not going to talk about again. 54 00:07:26.820 --> 00:07:37.560 William Cheng: So, so, and also they use global, you know, global allocation. Right. So in this case, you'd be have a memory hog and Linux. You're going to get all your other process. He has to compete with memory for the memory hog. 55 00:07:38.190 --> 00:07:43.350 William Cheng: So in a way, Linux is, you know, sometimes you have one memory hog can actually, you know, kill the entire 56 00:07:44.610 --> 00:07:52.500 William Cheng: Linux system so you know way Linux is, you know, this is this is their design decision. I don't know why they go with this way, you know, because windows. 57 00:07:52.920 --> 00:07:59.100 William Cheng: They use local allocation seems to be a little better. If you especially when you have memory Hawks. Yeah. So I don't know if you 58 00:07:59.820 --> 00:08:07.260 William Cheng: Why yeah I guess when you run, you know, virtual machine on the Mac right sometime you know the window become really, really slow. 59 00:08:07.770 --> 00:08:14.610 William Cheng: Maybe this is the problem I because they use global allocation, even when memory hog they use a lot of memory. It's really, really slow. Nothing else works. 60 00:08:15.120 --> 00:08:20.700 William Cheng: Okay, so, so again this is might be a design problem, you know, for for for four minutes. All right. 61 00:08:21.240 --> 00:08:32.160 William Cheng: The pace scan the algorithm. I mentioned before, right, you know, so, so again you have to how to clock out more than one goes down all these you know page friend, said the reference equal to zero. And when the second while wakes up the 62 00:08:32.550 --> 00:08:37.920 William Cheng: TTP side, whether they need to you know move the PageRank from the occupation page list to the inactive. 63 00:08:38.160 --> 00:08:44.670 William Cheng: List. Right. So again, all these memories are separate. So, therefore, you have three, you know, three different body systems three different actor page lists. 64 00:08:44.910 --> 00:08:52.650 William Cheng: And three different United States. That's where you know where you move a patient for the actor page to this to the next page list. So these are the ones that are picked up by the page on demand. 65 00:08:53.100 --> 00:09:02.820 William Cheng: There are not recently used if the page frame is clean, which means that is exactly the same data is on the desk by. In that case, you don't have to make them go into the inactive ageless, you can simply return it to the buddy system. 66 00:09:03.180 --> 00:09:07.710 William Cheng: Yeah, if it turns out the pages dirty. Whereas, in that case, while they need to write it back to the desk. 67 00:09:07.980 --> 00:09:14.490 William Cheng: So again, you need to remove it from the actor page, there's a map of all the address space for the program that are using this page for a 68 00:09:14.730 --> 00:09:22.500 William Cheng: Mark the patient and busy and then you append to this list again this list all the patients are written out to this one at a time. So it will take a very long time. 69 00:09:22.980 --> 00:09:31.200 William Cheng: Events. So when other pro and try to use that page, friend, they will find that the patient is busy so they are stuck inside a colonel waiting for the patient. The day clean 70 00:09:31.530 --> 00:09:40.410 William Cheng: Yeah, eventually, when the patient is clean. You want to see if any, you know, any process you that are waiting for. If there's no process waiting for it you return it back to the 71 00:09:40.860 --> 00:09:49.290 William Cheng: Buddy System. Otherwise this page is considered recently used in this case you that the patient is no longer busy and you add it back to the active patients. 72 00:09:50.370 --> 00:09:54.630 William Cheng: OK. So again, the picture over here sort of summarize what I just said. All right. 73 00:09:55.320 --> 00:10:05.280 William Cheng: So, so these are important Linux, you know, data structure over here. So again, sort of briefly review what typically happen. You know, when does Colonel use all these, you know, virtual memory data structure. 74 00:10:05.730 --> 00:10:10.710 William Cheng: So for every process over here, you know, again, we call the process control blog when it has their own terminology 75 00:10:11.070 --> 00:10:16.410 William Cheng: They have a virtual memory map. They also have the horror paste, Dave. All right. So Linux that are sort of put them in different category. 76 00:10:16.650 --> 00:10:21.120 William Cheng: The way that we've been talking about it. It's kind of like the hardware paste a boy is part of the virtual memory map. 77 00:10:21.390 --> 00:10:24.240 William Cheng: But again, some people will think that what the virtual the horror page table. 78 00:10:24.420 --> 00:10:33.810 William Cheng: They actually belong to the hardware abstraction layer. So therefore, they don't really belong to the virtual memory that right. So again, they are highly you know associated with each other. Whether you know they belong to the the 79 00:10:34.170 --> 00:10:40.110 William Cheng: The, the kernel or the hardware abstraction layer, it's you know, it's not that important. Yeah. So again, 80 00:10:40.740 --> 00:10:47.520 William Cheng: If you have to worry about, you know, different CPU or whatever, then, then the harbor page table needs to be implementing that right. Yeah. 81 00:10:48.330 --> 00:10:59.850 William Cheng: Right, so, you know, kudos, I mean, we don't really make that distinction, right, our virtual memory map include the page table. Yeah. Alright, so the virtual memory. Now over here is represent the user address space, right, it maps virtual you know 82 00:11:01.560 --> 00:11:04.920 William Cheng: Memory segment. Right. So again, they remember all these, you know, I'm 83 00:11:05.550 --> 00:11:20.610 William Cheng: Guessing implementation is the linear list of VM area using Linux terminology and every VM areas I'm every segment that memory segment or purity by into page. The page frames and then, you know, starting from the VM area, you need to point to some object that will manage all these 84 00:11:22.050 --> 00:11:31.560 William Cheng: Manage all these memory because it'll go the way you you manage a memory is that you put the physical memory inside pace friend. So, therefore, what you need to manage is a bunch of pastry objects. 85 00:11:32.250 --> 00:11:42.360 William Cheng: Okay, so, so starting with a VM area or region, you need to, you know, you need to be able to find a bunch of patient I'm object that implement that memory segment. 86 00:11:43.080 --> 00:11:47.370 William Cheng: Because, again, the way I describe this right. If you have a memory segment over here or 10 kilobytes law. 87 00:11:48.000 --> 00:11:53.700 William Cheng: Then every patient corresponding four kilobytes or you have one four kilobytes page ram over here, another four kilobyte patient over here. 88 00:11:53.910 --> 00:12:07.140 William Cheng: The last one cover the entire four kilobytes of RAM, so only the first two gigabyte is useful. The other two kilobytes over here are in its internal fragmentation. Right. So in this case, starting from the VM area, you better be a 89 00:12:07.590 --> 00:12:14.310 William Cheng: Certain amount of VM area. You need to be able to find these three page frames, right, because these three patients implement that memory segment. 90 00:12:15.390 --> 00:12:23.280 William Cheng: Right so yeah well you do in front of them and keep that in mind. Right. So, you know, so if you start with a VM area, you need to find the page frame that implement them every segment. 91 00:12:24.240 --> 00:12:29.760 William Cheng: Okay, so this way you know you know what what data to copy into it. And also, how do you perform copy on write all that kind of stuff. Okay. 92 00:12:31.260 --> 00:12:43.380 William Cheng: Alright, so you keep track of the page rank. Right. So you need to find all these paste rain for IBM area. You also need to find the backing store. So again, you need to go to the other, the pointer, starting from the VM area, they will point to anonymous offer their agenda. 93 00:12:44.370 --> 00:12:52.680 William Cheng: Or follow jack. So this way. Well, you need to get data from the package store he you know he you know where to get the data from yeah 94 00:12:53.280 --> 00:13:02.130 William Cheng: All right, globally, you know, they also share these data structure between all the processes. Right, so they are the, the free less, which is the buddy system. Right. So you can see that the buddy system. 95 00:13:02.310 --> 00:13:06.690 William Cheng: Is using the entire system. Right. So, therefore, we divide physical memory into all these zones. 96 00:13:07.170 --> 00:13:16.050 William Cheng: So therefore, the buddy system in every zone is shared by all the processes. Similarly, the occupation is the name back to paste this, they are all you know sort of shared by all the processes. 97 00:13:16.470 --> 00:13:23.100 William Cheng: Yeah, right. So their stuff coming from the press Control blah, and then they're all these other data structure their share buddy, bye bye bye all the processes. 98 00:13:24.060 --> 00:13:28.110 William Cheng: Alright, so let's go through some scenario of how to actually use all these data structure. 99 00:13:28.410 --> 00:13:35.220 William Cheng: The first example, we again we see this over and over and over again. So, you know, the reason I keep repeating is because you have to implement this in Colonel three 100 00:13:35.700 --> 00:13:41.670 William Cheng: So these are very, very important things that you have to sort of know by hand. So, therefore, what you try to implement a you sort of remember how to go 101 00:13:42.150 --> 00:13:50.370 William Cheng: Alright, so the first example via what happened, we get a pitfall right again. There are many reasonable pace for the one we're going to look at is equal to zero. When you prefer address translation. 102 00:13:50.820 --> 00:13:59.640 William Cheng: The page table entry over here is the invalid. So you try be inside the kernel. And then what the colonel will do is that it will walk down that linear list of VM area. 103 00:13:59.880 --> 00:14:11.430 William Cheng: See which you know VM every belongs to. And then, you know, if it doesn't belong to any DM area you killed the user space program because it turns into a segmentation, Vol. If you're able to find a VM area, you need to find the page frame. 104 00:14:12.180 --> 00:14:19.920 William Cheng: Okay, so if the pager and said this particular page is actually inside the backing store. And then what you need to do. So you need to bring the data in front, the back end storage memory, right. 105 00:14:20.070 --> 00:14:26.760 William Cheng: And that will. And again, the way you do this is that you ask the buddy system for new page rank depends on you know which which zone that you wanted to 106 00:14:27.030 --> 00:14:30.120 William Cheng: And then would you do that you look into the virtual memory map and then 107 00:14:30.420 --> 00:14:39.540 William Cheng: You know, for for equal to zero, you need to copy the data. So again, you need to, you know, follow the pointer over here as the object to transfer data from this into memory. Your Colonel 108 00:14:40.290 --> 00:14:49.650 William Cheng: The Colonel threads handling the space for all it will fall asleep. Yeah. And then the data transfer is gonna happen. And then you got to switch the CPU to run all the other processes are the threats. 109 00:14:50.040 --> 00:14:59.130 William Cheng: dimensionally when the data is, you know, transfers finish what it will do is that is that interrupt service routine you'll wake up your kernel through. So when a colonel says woken up 110 00:14:59.520 --> 00:15:04.950 William Cheng: The, you know, the data has been transferred. And then what you would do is that he will adjust all the pace table. 111 00:15:05.430 --> 00:15:15.270 William Cheng: All the colonel data center, including the page table, right, so before equal to zero. Now you need to save equals two, one. You also need to adjust, whether it's read only or rewrite FIGURE OUT WHAT ARE YOU DOING copy on right 112 00:15:15.630 --> 00:15:23.730 William Cheng: So again, this way you can actually set everything correctly and then point the physical page to the physical page inside the pace rain and then when when the kernel is imperfect. 113 00:15:24.060 --> 00:15:30.270 William Cheng: You know, it's a perfectly consistent day. And now you'll return back into the user space. So you can handle the next page. 114 00:15:31.500 --> 00:15:40.200 William Cheng: Okay, so again it's important that before you go into the user stories program everything needs to be perfect because you have no idea when you're going to come into the kernel. The next time. Yeah. 115 00:15:41.940 --> 00:15:49.470 William Cheng: So here, you know. So, things get a little complicated, because the pace frame may be shared by multiple user processes. Right, so, so, so, so again, 116 00:15:51.330 --> 00:16:00.540 William Cheng: You know that, you know, again, that you have implementing Colonel three. So keep that in mind. Every time you see a pace frames that oh, you know, what about sharing. Right, so, so, so, so, so therefore, in this case. 117 00:16:00.960 --> 00:16:06.960 William Cheng: Sometimes you don't have to ask the buddy system for pace, right, because if another process is using it, you can actually just 118 00:16:07.380 --> 00:16:15.870 William Cheng: Just, just just just pointed it a point to the same page. Right. Okay. Paste RAM, I think, a patient object can be shared by by by 119 00:16:16.770 --> 00:16:23.820 William Cheng: A patient magic can be shared by multiple processes. So, therefore, you know what you have to do is that before you decide to allocate a new page rank. 120 00:16:24.120 --> 00:16:27.750 William Cheng: What you need to do is that you first you have to look it up to see if it exists already 121 00:16:28.440 --> 00:16:35.010 William Cheng: Okay, so in my last discussion section I mentioned before every page frame is identify identify by two things right. 122 00:16:35.220 --> 00:16:39.780 William Cheng: One is which memory management object belongs to. And a second one is called a piece number 123 00:16:39.990 --> 00:16:47.010 William Cheng: Of the page numbers that array index. So using this two pieces of information you'll use hash table the hash table is the one that manage all the page rain. 124 00:16:47.340 --> 00:16:57.540 William Cheng: So use the highest able to say, look it up to see if it already exists if it's already exists, what they know, as you just use it. Okay, so if it doesn't exist. What do you have to do well in that case you need to create the patriot. 125 00:16:59.100 --> 00:17:06.480 William Cheng: Alright, so again, you know, so instead of current over here, since you have sharing it becomes a little more complicated. You can't just go allocate a new page, Ray. 126 00:17:06.840 --> 00:17:12.630 William Cheng: Because going to end up with the same page or and getting copy all over the place. So therefore you need to find it. First is, we can save memory. 127 00:17:13.560 --> 00:17:18.780 William Cheng: Right. Second example, your page on demand. So remember your page or demon, go to the global list. 128 00:17:19.020 --> 00:17:26.910 William Cheng: That are shared by all the processes over here it goes to the global list and then use the clock algorithm and pick out which one is recently use which has not recently us 129 00:17:27.120 --> 00:17:35.460 William Cheng: And if they decide that a pace frame is not recently used, but it's dirty or in that case you need to a map that he's reading from all the address spaces that are using it. 130 00:17:35.850 --> 00:17:39.510 William Cheng: Now, so this guy is you know why they went to page are demon wants to free up a page. 131 00:17:39.990 --> 00:17:50.430 William Cheng: pretty dirty page or 30 page also a modified page, right. Otherwise, the patient is clean. So if a patient is clean. It's the same thing as the data on the desk. So in this case, you don't have to do. You don't have to write it back to this. 132 00:17:50.730 --> 00:18:02.820 William Cheng: You can simply returns to the buddy system. So this example is that the patient is dirty. So you're going to find out, you know, from which process and address basis, the patient in belong to. So again, you have to do this because page friend can be shared. 133 00:18:03.750 --> 00:18:15.600 William Cheng: So in this case, once you find out which processing that belong to, then you can a map this page spread from all these page tables over here, right. So how do you map it right. Go to the page table entries over here said equal to zero. 134 00:18:17.130 --> 00:18:21.690 William Cheng: Okay, so why do you want to say equal to zero because now I'm going to make it busy. I need to write it out to this. 135 00:18:21.780 --> 00:18:31.860 William Cheng: So whenever you get out of the busy. Nobody can use. So, therefore, what I would do is I will set to zero. I will also send it the busy. So next time somebody else tried to use it, they will come out of Colonel, and then you will see that, you know, 136 00:18:32.400 --> 00:18:39.000 William Cheng: Equal to zero. So, they will not occur. Now when it comes to curl, you will see that this patient is busy so therefore they will have to go to sleep. 137 00:18:39.660 --> 00:18:49.140 William Cheng: Because what do they go to sleep. Right. As it turns out that you know every page rain has a queue. So if you're waiting for particular patient, and the patient is busy you sleep in the queue for that page, right. 138 00:18:49.680 --> 00:18:57.150 William Cheng: Okay, so this way when you're patient has been cleaned once the patient become clean. Would you do that you go to that cue to see if anybody is sleeping there. 139 00:18:57.360 --> 00:19:06.870 William Cheng: If there's somebody sleeping there, why not because you wake them all up and then you return back into the actor painless. Okay, if nobody sleeping there, why not case, you know, nobody's waiting for. So therefore, in this case. 140 00:19:07.290 --> 00:19:11.250 William Cheng: You make the patient on busy or you return the page train back to the buddy system. 141 00:19:12.540 --> 00:19:17.580 William Cheng: Alright. So again, these are important steps that you have to take. So, therefore, you have to, you know, you have to remember this. Yeah. 142 00:19:18.330 --> 00:19:23.220 William Cheng: All right over here in winnings over here. I'm going to ask you to look at a piece of code over here. 143 00:19:23.640 --> 00:19:33.480 William Cheng: This coke is called P frame removed from PTS there. So this operation is done by one function and we look at this code over here, the code is very, very simple. 144 00:19:33.990 --> 00:19:36.930 William Cheng: Okay, so why is it cold, very simple, because it's very, very tricky. 145 00:19:37.500 --> 00:19:45.870 William Cheng: Now guys, every time you see only a few lines ago is that how can a few lines can do so many things right. So again, you know, that's very, very tricky go so you should read this quote over here, even though at the beginning. 146 00:19:46.230 --> 00:19:56.280 William Cheng: In the beginning of Colonel three, you don't understand what it's doing, try to sort of figure out what is doing because later on when you set up your kernel data structure, you better make sure that this function works perfectly. 147 00:19:58.050 --> 00:20:06.330 William Cheng: Okay, so whenever you're sharing Patriot so so so this code over here. What it will do is that he will. He will find all the page frame that are, you know, so sorry. 148 00:20:06.750 --> 00:20:14.340 William Cheng: For a particular patient. It will find all process either are using it and what it will do is that they will a map the pace table entry from all these processes. 149 00:20:15.570 --> 00:20:20.820 William Cheng: OK. So again, a very, very powerful function, you got to make sure that you know when you implement your code that call has to 150 00:20:21.150 --> 00:20:29.790 William Cheng: You know, whatever you have whatever data structure you set up must make sure that this code works guys are this cause a little convoluted, feel free to discuss that in class Google group. 151 00:20:30.480 --> 00:20:41.820 William Cheng: And so again if you asked me what code, right. Can I tell you, but again if you, you know, have some questions that want to sort of has a higher level understanding of what this code is doing, feel free to just died in the hospital. Yeah. Also, feel free to ask me questions. Yeah. 152 00:20:43.320 --> 00:20:54.270 William Cheng: Alright, so once you have a map of all the address space. Set the patient. I'm too busy you find the corresponding backing store you know right back the page, you know, to, to, to this, you can use the following day, you can use the 153 00:20:54.780 --> 00:21:02.880 William Cheng: Anonymous object and then you need to mark the patient busy while you know they're being written out to this right so this way things work properly. Yeah. 154 00:21:03.180 --> 00:21:08.910 William Cheng: And then, you know, free the PageRank. You know, if know processes waiting for you what what we infinite when the page become 155 00:21:09.570 --> 00:21:16.560 William Cheng: From from busy or not busy. So in that case, you need to wake the see if anybody's waiting for if nobody's waiting for it, you can return back back to the buddy system. 156 00:21:16.800 --> 00:21:26.250 William Cheng: Right, otherwise this page has recently used to return it back to the active patient list again. Alright, so again this is a very important usage for using all these data structures. Okay. 157 00:21:28.530 --> 00:21:39.630 William Cheng: All right, so that's all we want to say about the the Linux system for Windows. Again, we don't have a window source code. So we can you know sort of get an understanding of what Windows is doing. 158 00:21:40.050 --> 00:21:46.890 William Cheng: By reading some papers published by Microsoft people right Microsoft right operating system they push publish papering operating system conferences. 159 00:21:47.310 --> 00:21:54.900 William Cheng: So by, you know, I guess the author is also, you know, I guess they also have our textbook up as adapter. He's a very well known researcher, he probably 160 00:21:55.290 --> 00:22:03.690 William Cheng: Read a lot of papers so so you can write about, you know what what what what what Microsoft is doing. So again, we don't really focus too much on Microsoft. We're going to briefly talk, talk about it. 161 00:22:04.380 --> 00:22:13.380 William Cheng: Alright, so one thing is that, you know, again, Microsoft is always more complicated because there are businesses that need to run in all different kinds of situation will, you know, for all their different kinds of customers. 162 00:22:13.950 --> 00:22:21.120 William Cheng: So number one, that's their address, there's just two different choices one look just like the next right the first part will be a three gigabyte. The other part of years one gigabyte. 163 00:22:21.360 --> 00:22:25.770 William Cheng: They also have another configuration, you have two gigabytes of user space and two gigabytes of Colonel 164 00:22:26.460 --> 00:22:33.420 William Cheng: Okay, so why do they do that right. I guess my guess is that the left pop configuration over here is probably more reasonable for 165 00:22:33.630 --> 00:22:42.480 William Cheng: For server ran for server. The server need to run many, many processes over here. So if you go with this pretty good approach over here. The Colonel can only be one one gigabyte. SIGHS 166 00:22:42.810 --> 00:22:47.820 William Cheng: Okay, what it costs to run out of space. Why, in that case, you have to do something else. So this is something else you can do. 167 00:22:47.940 --> 00:22:56.700 William Cheng: You can use a different configuration where the colonel address basis two gigabytes in size, right. So this way you can read many, many user processes because every user process required Colonel stack. 168 00:22:57.450 --> 00:23:04.050 William Cheng: You know. So in this case, all these are Colonel data structure. So, therefore, you know, if you need to support a lot of user processes you will choose the configuration on the left. 169 00:23:04.320 --> 00:23:11.070 William Cheng: On the right, most likely, this is for desktop you know configurations. Right. So again, I'm just guessing which, you know, probably makes sense. 170 00:23:12.600 --> 00:23:17.610 William Cheng: Here are also the windows paging strategy you know summaries are, again, we're just going to briefly over at 171 00:23:18.120 --> 00:23:30.330 William Cheng: Windows called this working set as it again, I mentioned before, they are also implement have an approximation of the working says by using local allocation. So every process is guarantee guarantee a small set of page brain. 172 00:23:30.600 --> 00:23:39.180 William Cheng: Guys, so therefore, these are private patient and they will not be shared by any other processes. Right. So, therefore, if your program is very, very small. All you requires a few page rain less than 173 00:23:39.420 --> 00:23:46.950 William Cheng: You know, the, the one that are reserved for you. So what happened is that what you progress are running. Once you get a pace fall for everyone for your patience. I'm over here. You never get another patient it again. 174 00:23:47.490 --> 00:23:53.520 William Cheng: Okay, so this way you will run very, very quickly, and he will finish a yo yo quit your program and you're free of all your 175 00:23:54.180 --> 00:23:56.130 William Cheng: Patient over here, back, back into Windows 176 00:23:56.790 --> 00:24:04.740 William Cheng: Okay, or if it turns out your, your ID, if you if you require more memory. You have to compete with anybody else or so. So you can use your, your reserve your reserve. 177 00:24:04.950 --> 00:24:12.090 William Cheng: Once you're finished, you'll have your research, you try to allocate new page for a while now. If there's a memory hog. Well, then in that case. In that case, you 178 00:24:12.840 --> 00:24:17.310 William Cheng: Know if you have a memory Hall running. Is that your system, you have to compete against all the other memory hearts. 179 00:24:18.240 --> 00:24:28.050 William Cheng: Alright, so again you know you so so again the windows philosophies that they encourage you to write very, very small program. They use a very tiny memory footprint. So this way you get a rubber very quickly. 180 00:24:28.590 --> 00:24:37.290 William Cheng: Because, again, it's a really good idea. Right. Yeah. They use a One Hand o'clock hour them again different phone Linux. We don't know why they make this decision. 181 00:24:37.770 --> 00:24:41.550 William Cheng: They also have a thread inside of Colonel know as a swapper thread. 182 00:24:42.060 --> 00:24:53.520 William Cheng: This threat was swap all the idle processes that so so so window has a sort of this philosophy that you know the the the the processes that are running. So, so, I mean, if you haven't used windows. 183 00:24:53.790 --> 00:25:02.370 William Cheng: A lot of the concepts over here, a copy from Windows every time when you click on a window, the window pop to the top of here when it pops to the top phobia that become the active window. 184 00:25:03.060 --> 00:25:13.020 William Cheng: Okay, so for Windows what it would do is that for the active window window wants to devote all the resources to the active with those. So the owner of the active window is the most happy person on that machine. 185 00:25:13.650 --> 00:25:20.160 William Cheng: Guys, a window really want to make the active window, very happy. Okay. So, therefore, whatever it is that it will give all the resources to the active window. 186 00:25:20.580 --> 00:25:30.450 William Cheng: So they use the swapper thread to say that if you are idle process that you have you have been inactive for 15 seconds. What it will do is that it would take all your address space and it was sweating all that 187 00:25:30.870 --> 00:25:41.490 William Cheng: Okay, so they're very they have sort of a sequence, they will swap out the colonel staffers and then they will swap or the working set and then you know again. So, what it will do that I'll stop all the memory. So they will give the memory to the active window. 188 00:25:42.120 --> 00:25:44.910 William Cheng: Okay, so again this is a very, very different philosophy from Linux. 189 00:25:45.330 --> 00:25:54.480 William Cheng: But also for Windows over here is that once you, you know. So as well as you swap out all the other processes. Right. I don't know if you actually use window will use all tabs, which are different talents different process. 190 00:25:54.690 --> 00:26:02.490 William Cheng: Sometimes it will take a very long time, right, because the entire process is sleeping on the desk so they will when you start bringing, bringing in from, you know, from this into memory. It will take you a long time. 191 00:26:03.120 --> 00:26:11.280 William Cheng: OK. So again, this is very different between Windows and Linux. You can actually feel the difference. We're using Windows, Linux, right, because they have complete different philosophy now. 192 00:26:11.820 --> 00:26:21.720 William Cheng: Windows. Again, they want to give all the memory to to the, you know, to an active windows. They're even willing to give our kernel memory there. So some of the kernel memory over here. They're actually paid out 193 00:26:22.170 --> 00:26:27.060 William Cheng: Okay, so this way again when their pace. Now you free of these memory over here. Okay. You give them all to the active 194 00:26:28.320 --> 00:26:38.760 William Cheng: Active window. Yeah. So in this case in inside the cardinal, you can actually go to get a colonel page fall in weeks. You see that inside, Colonel. If you get a paintball, you get a kernel panic and Kronos dad. 195 00:26:39.060 --> 00:26:45.540 William Cheng: In Linux. I think it's the same way as well. Yeah, these are the older Linux. I don't know if that's sort of the most up to date latest design over here. 196 00:26:45.930 --> 00:26:57.930 William Cheng: In the older Linux, you know, the Colonel. Can I get a pitfall. Okay, maybe the modern analytics, they are you know after 2.6 they have different kernel version, maybe in the version three they start doing something different. I have no idea. I'm not tracking 197 00:26:59.460 --> 00:27:05.220 William Cheng: Linux but windows inside the Colonel, you can actually get a portal patient and that's perfectly normal. 198 00:27:05.790 --> 00:27:13.650 William Cheng: What you can do that. You can take one of the kernel memory over year swap it out to the desk and then bring it back in. But you got to be very careful because if you swap out the page demon 199 00:27:13.980 --> 00:27:21.630 William Cheng: Who's going to bring the the piece back end. Well, nobody's going to bring the page back end. Right. So, therefore, again, you need to be able to, you know, locked out some of the patient over here. 200 00:27:21.930 --> 00:27:31.050 William Cheng: So this way. Well, you saw something out, you can always bring it back guys again windows, a little more complicated because they need to make or they need to make all kinds of application very happy. 201 00:27:31.980 --> 00:27:42.210 William Cheng: All right, window pays for him has, you know, you know, I guess for Linux. The only three states right he's a free active and inactive windows, a little more complicated. Again, we're gonna talk about. Yeah. 202 00:27:44.610 --> 00:27:54.090 William Cheng: Alright, so the next thing we're going to look at is copy on write and fork. So, so, so again, first I'm going to talk about for, you know, different kinds of implementation. 203 00:27:54.390 --> 00:28:00.600 William Cheng: As it turns out, you know, there's complication when you try to make copy on write work with fork. Right. So we're going to sort of first see 204 00:28:00.870 --> 00:28:06.630 William Cheng: Under what conditions, there's no problem. And then we're going to see what under what conditions, their problems and then we're going to see the solution for it. Yeah. 205 00:28:08.040 --> 00:28:16.290 William Cheng: All right, so, so let's talk about the fork system call right again the abstraction for the fourth system calls that when you make a forces and call your the user process. 206 00:28:16.470 --> 00:28:23.130 William Cheng: You try to create a child process and the way that I've talked about is that you're going to try things out the Colonel. The Colonel is going to make a copy of your 207 00:28:23.490 --> 00:28:25.080 William Cheng: Coffee or your address space. 208 00:28:25.260 --> 00:28:31.770 William Cheng: So conceptually, you need to copy every page rain right we mentioned before that there are shortcuts. Because, you know, for example, the tech Simon can be sure 209 00:28:31.860 --> 00:28:38.430 William Cheng: So therefore, there's really no reason for you to copy the text segment. Right. And what about all the other side. Man We've mentioned your copy on write all these kind of Syrah so again. 210 00:28:38.610 --> 00:28:44.280 William Cheng: The naive implementation or for the most straightforward way to do to do it is to copy that address space. 211 00:28:44.880 --> 00:28:47.670 William Cheng: Or guys have been clearly that's a lot of work. And then, of course, if you 212 00:28:47.850 --> 00:28:56.400 William Cheng: Feel comfortable process and then it turns out that you all you do is that you call it exact so all the work that you have done, you know, copy the address is not completely wasted, right, because when you call 213 00:28:56.880 --> 00:29:04.230 William Cheng: It comes out a kernel of your you wipe out the entire just way that you just copy as a total waste of time. Okay, so then now you have a limitation. Nobody does that anymore. 214 00:29:04.770 --> 00:29:10.440 William Cheng: Okay, so the question is that, what would you do, right. So there are different, you know, people actually come up with different different kinds of solution. Yeah. 215 00:29:11.850 --> 00:29:18.660 William Cheng: All right. One of the solution of yours is called the virtual fork the visual choreography is actually the quickest way. Will you try to implement for 216 00:29:19.200 --> 00:29:27.120 William Cheng: OK, so the way that you do it is that when the pan, a process, you know, call for you coming out the Colonel. What we can do is that it's okay if the child processes just 217 00:29:27.480 --> 00:29:35.850 William Cheng: Just going to call it called exact. So in this case, we need to copy as little as possible, right, the parent process over here, try to create shop so you come inside the colonel over here. 218 00:29:36.030 --> 00:29:40.710 William Cheng: But we try to create a child process. What can we do that that makes it the least amount of copy 219 00:29:41.340 --> 00:29:45.390 William Cheng: But there's a one way that you can do that. You can actually borrow the address space from the parent 220 00:29:46.080 --> 00:29:55.380 William Cheng: What does it mean to Bali outer space. Right. You know, so the parent over here. Again, there's a linear Lissa. You know as region over here. So what we can do is that instead of, you know, copying. 221 00:29:55.980 --> 00:30:01.950 William Cheng: copying this address space. We just borrow it. Because if we know that a child process over here will call exact right away. 222 00:30:02.130 --> 00:30:12.330 William Cheng: So in that case will borrow the aerospace over here, have the child process returned to the user space and what he will do the code exact when they called exactly what companies that have Colonel, and now we can return the address space back to the parent 223 00:30:13.620 --> 00:30:18.360 William Cheng: That. So this is a really, really good going to implement a fork right it's it's super fast. 224 00:30:18.780 --> 00:30:25.620 William Cheng: But in this case, you have to know that are the parents of the other the waiting for the trial process. It's because you want to do exactly 225 00:30:26.070 --> 00:30:28.110 William Cheng: Okay, if you don't call the exact don't do it this way. 226 00:30:28.890 --> 00:30:32.460 William Cheng: Okay, so therefore the application program at the application programmer knows 227 00:30:32.700 --> 00:30:44.190 William Cheng: Whether right right after for you're gonna you're going to do the exact or not. So therefore, the burden of whether you call before or the regular for the burden of deciding which one the call is falls on the application programmer. 228 00:30:45.060 --> 00:30:53.760 William Cheng: OK, so the application programmer would look at a co writes over here. You're going to call forth right at some point over here. You're going to call exact. Okay, so what happened between forget exactly 229 00:30:54.750 --> 00:31:06.750 William Cheng: Well, as it turns out, as a little bit tricky because because if he you know if over here instead of calling for you for a call before because you know that you're gonna call exact right away what you have to make sure is that you didn't change the address face. 230 00:31:07.980 --> 00:31:12.240 William Cheng: What if you change the address page right if you change the address spaces addresses is borrowed 231 00:31:12.420 --> 00:31:21.240 William Cheng: We return back into the parents. Parents gonna be surprised. So, so, for example, you know, we hear you change the global variable over here. Okay, so when the parent get the adversaries bank or the parents going to be really surprised. 232 00:31:21.720 --> 00:31:31.110 William Cheng: Okay, so therefore the burden is on the application programmer to make sure that you whatever you do, between the fork and exact you don't do anything to change address face. 233 00:31:32.070 --> 00:31:41.280 William Cheng: Yeah. As it turns out, this is very, very, very, very difficult to determine is too much burden for the application programmer. When the application programming and say, well, then in this case doesn't work. 234 00:31:41.670 --> 00:31:49.770 William Cheng: Okay, so therefore this your the advantage over here is is very efficient because you don't have to copy anything you don't have a copy paste rain. We don't have a copy the address but you just borrow it. 235 00:31:50.310 --> 00:32:01.830 William Cheng: Okay, so this is the best way to go, but the disadvantage is that there's only works if the child also do the do the exact system call and also the the application programmer must make sure that the the address space is not modified 236 00:32:02.550 --> 00:32:06.450 William Cheng: Because under what condition would you modify the outer space. What if you make a function called right here. 237 00:32:07.020 --> 00:32:12.060 William Cheng: Well, if you make a phone call or then again and you mess up the outer space, another parent process might be very, very upset. 238 00:32:12.330 --> 00:32:22.650 William Cheng: Right. So again, you gotta, you gotta be very, very careful if you make a function call and the function return over here in the financial return we store the the stack to what it was before. What, in that case, you didn't really modify anything 239 00:32:23.370 --> 00:32:32.910 William Cheng: OK. So again, all these burden are placed on the application programmer. In the end, the application programmer, it doesn't really like this at all. So, so today, nobody actually implement before even though is the fastest way to go. 240 00:32:33.780 --> 00:32:39.240 William Cheng: There. So today, you know, we actually what we what we do over here is, again, we're going to use a lazy evaluation. 241 00:32:39.420 --> 00:32:47.070 William Cheng: Right, we're going to do happy on right and we're going to try to share as much as possible. So the basic idea over years that the way you implement fork is that you come inside the Colonel. 242 00:32:47.760 --> 00:32:52.080 William Cheng: There. And then what we'll do is I'm going to share it. The entire address face okay so 243 00:32:52.830 --> 00:32:58.980 William Cheng: So what that means is a Shirt, shirt and hard to say. Right. So the parent of your company that occur know we have a linear list of as region over here. 244 00:32:59.190 --> 00:33:06.780 William Cheng: The child need to get a copy of the address space, but what it will do is that it was shared all the patients now so the child over it will take the status talking over here. 245 00:33:06.930 --> 00:33:16.890 William Cheng: Make this over here, this child process. We're going to make a duplicate of this outer space over here, but then you know this this VM area or this as region over here. Why, because they're going to share all the page framed right here. 246 00:33:17.670 --> 00:33:24.810 William Cheng: Okay, so this way you only copy the address space that you copy the pointer and they're showing everything right. So why are you sharing everything. Okay. 247 00:33:25.710 --> 00:33:31.050 William Cheng: Well, if you want to share the text document clearly that's okay. What about the data center. What about the heap. Second, what about this next segment. 248 00:33:31.320 --> 00:33:37.050 William Cheng: As long as you're doing copy on write, then you're okay, right. So what you do that, you need to set up your kernel data search over here to say 249 00:33:37.260 --> 00:33:42.990 William Cheng: I'm sharing this. So if you just want to read global variable, you just want to read the stag, you just want to read the 250 00:33:43.590 --> 00:33:52.560 William Cheng: The heat segment. Everything is fine, but when you write to that page for the first time we're going to try things out of Colonel, and we're going to perform copy on write. So this way. Depends on who is doing the copy 251 00:33:52.740 --> 00:34:03.240 William Cheng: If the parents doing the copy and apparel, get a private copy of that memory if the child is doing the copy of the child will get a private copy of that memory. So this case, you know, so, so we implement copy on write just write 252 00:34:03.510 --> 00:34:08.400 William Cheng: This way you can share all you want until you try to write it for the first time and he make a copy and right to the coffee. 253 00:34:09.570 --> 00:34:18.300 William Cheng: Okay, so therefore, in order so so for modern operating system. If you want to implement fork. You have to do copy on write together with fork that everything will be okay. 254 00:34:19.770 --> 00:34:29.520 William Cheng: Okay. So as it turns out, copying or right with for some time. They work together very, very well. Sometimes they don't work together very well. So we need to study the cases will copy on write to see under what condition they work. 255 00:34:29.700 --> 00:34:34.080 William Cheng: Under what condition they don't work. And so I know what it can do when they don't work. What do we have to do to fix it. 256 00:34:34.890 --> 00:34:38.250 William Cheng: Okay, so first so so first we're going to see, you know how to actually do this. Yeah. 257 00:34:39.210 --> 00:34:52.110 William Cheng: Alright, so, so to implement this better for it. Right. So, so, you know, if you do copy on write perfectly, then using this lazy evaluation mechanism with copy on write well then you implement exactly the same semantics as the original for 258 00:34:53.460 --> 00:35:07.770 William Cheng: Okay. So, therefore, this is what a good way to go. It's not as fast as before. But again, you know, it's the same systematic. It's as if you make a copy of the address space with all the PageRank because whatever you try to modify it for the first time that we're going to make a copy and 259 00:35:09.300 --> 00:35:11.040 William Cheng: Then the modification go into the copy 260 00:35:11.820 --> 00:35:25.080 William Cheng: Right. OK. So again, copy on write and going to read the definition here again. So now we're not doing segmentation. We're doing a paging so process. Get a private copy of a page after a thread in the process perform the right to that page for the first time. 261 00:35:26.430 --> 00:35:31.590 William Cheng: Okay, so therefore, in order for us to do copyright will have to do, right. So we need to make sure that that particular 262 00:35:31.770 --> 00:35:39.360 William Cheng: That particular page is read only. So we're going to set every page table entry PD sample page table entry right so it's one entry is that a giant page table. 263 00:35:39.540 --> 00:35:45.120 William Cheng: We're going to set a table over here to read only four pages that correspond to memory segment that is happy. All right. 264 00:35:46.080 --> 00:35:52.800 William Cheng: Where's. Okay. How do we know that hopping around simply we go to the VM area. If the VM area says that this memory segment is private. 265 00:35:53.100 --> 00:36:06.000 William Cheng: Guy It's also rewrite. So again, if we see that, you know, a VM area is rewrite and private right so in that case we know that we need to set up on copyright. Copyright rest. So again, for that particular patient, you know, without 266 00:36:06.690 --> 00:36:11.250 William Cheng: You know, a VM area. It's a memory segment the memory segment is implemented by multiple 267 00:36:11.520 --> 00:36:16.260 William Cheng: You know, a pace range right again example I always use is that it's a 10 kilobytes memory segment. 268 00:36:16.470 --> 00:36:21.870 William Cheng: There are three pace reigns over here. First one is four kilobytes per second and fourth pillar by the third one is four kilobytes. 269 00:36:22.140 --> 00:36:34.140 William Cheng: All these three page runs over here, a corresponding to a page table entry so therefore they are three page table entry over here, we need to set the equals zero equals two, one and then also we need to set on to read only. 270 00:36:35.070 --> 00:36:42.210 William Cheng: Okay, so this way when you try to read from the streams. There's three different pages over here really is going to be fine. That's okay. We're gonna assume that these three page random over here. 271 00:36:42.630 --> 00:36:48.450 William Cheng: They already there in memory as we you know we perform the forces them call the parent already have them. 272 00:36:49.260 --> 00:36:51.420 William Cheng: Okay, so now we just need to share with the child process. 273 00:36:51.630 --> 00:36:56.910 William Cheng: Right, so they were the way we share with the Chopra says is that is that for both the parent and the show, we need to set up a copy on write 274 00:36:57.090 --> 00:37:03.990 William Cheng: We need to go to those three page table entry that correspond to these three pages for him, and we're going to set them V host one and we're going to set up the read only. 275 00:37:05.370 --> 00:37:13.470 William Cheng: Okay, so this way. When we return back into the user space program for the parent Michelle if they just want to read these patriots, they can read all they want but when they write to him for the first time. 276 00:37:13.860 --> 00:37:17.640 William Cheng: Because vehicles to one and there we don't need. So therefore, in this case, we're talking is that outer 277 00:37:18.120 --> 00:37:28.680 William Cheng: Space will walk down our linear list of as region over here we find out which page where it belongs to. How do we find a way patiently answer. So remember, there's a page number. This one will be page number zero dissolve the page number one. 278 00:37:29.280 --> 00:37:31.500 William Cheng: Number two, we're going to look up this page rain. 279 00:37:31.770 --> 00:37:38.010 William Cheng: And then we realized that, oh, we're doing copy on. Right, right, because the memory segment over here. Tell us up with that it's private. It's rewrite 280 00:37:38.160 --> 00:37:47.730 William Cheng: So there will be copyright, so therefore we need to find the pace re make a copy of it. And then we're going to change the pace table entry point to the copy and now we're returning to the user space. Well, when 281 00:37:47.970 --> 00:37:57.180 William Cheng: The user say program will write to it for the first time and then this will be changed to the, this will be changed to rewrite over here. When you write to everything will work and it will write it all right to the page, right. 282 00:37:58.740 --> 00:38:05.040 William Cheng: Alright, so, so again, this guy, this is how we implement copy on write by first, you know, set the pace table entry over here to to to to 283 00:38:05.340 --> 00:38:14.730 William Cheng: to to to to read only. And then when you write it for the first time, you gotta fix everything. Yeah, yeah. Alright so copyright must work with for what, what will you know what will. 284 00:38:15.240 --> 00:38:18.870 William Cheng: What does something bad can happen, right. So first we're going to see the cases where it works. 285 00:38:19.650 --> 00:38:26.550 William Cheng: Yeah, the first case over here is that private mapping. I'm going to copy on write and this one will be done after you perform before 286 00:38:26.670 --> 00:38:34.620 William Cheng: I sort of, yeah, we're gonna perform a fork over here. And now we're going to share all the page from over here. So again, when you create a child process over here, what we will do is that will copy the page table. 287 00:38:34.860 --> 00:38:42.450 William Cheng: Right, because a child process also have a stable. So in this picture over here that we're showing them their appointed the same physical pages and also this picture. 288 00:38:43.050 --> 00:38:50.580 William Cheng: What I'm going to use the same picture over here to represent page friends because there's a one one to one correspondence between the physical page and a PageRank. 289 00:38:51.180 --> 00:39:05.130 William Cheng: Okay, so these patient. I'm going to call them X, Y, and Z and then their, their corresponding page table entries over here is going to be this is x, y, z on the on the child process over here again you know so. So we already for one copy or right over here. Now you know so so 290 00:39:06.720 --> 00:39:14.040 William Cheng: So sorry. We haven't proven copywriting over here. So basically we're going to create a critical process reset everything. And now we're going to perform copy. All right. 291 00:39:14.490 --> 00:39:23.820 William Cheng: Well, yeah. So in this case, the three page frame over here is the one that I mentioned before, maybe one of them is pay some zero, they are on page number one of the other page number to over here. They are shared by the parent child. 292 00:39:24.900 --> 00:39:36.060 William Cheng: Okay. Alright, so the mark everything read only over here, they're getting ready. Beautiful copy. Alright guys, so now if they all try to read them the address space over here. Everything is fine. What did they perform, you know, 293 00:39:37.170 --> 00:39:44.910 William Cheng: Right, for the first time, right. So how does that work, right. So, for example, the patent process and say data equal to seven. So let's say that data is actually sitting over here and page z. 294 00:39:45.360 --> 00:39:55.200 William Cheng: Okay so data is a global variable could be a local variable. So anyway, it doesn't really matter which memory segment it belongs to this memory segments mayor or three page frame. And then the last page over here is the one that has data. 295 00:39:55.920 --> 00:40:05.160 William Cheng: So data right now is zero. So if you ask both of your parents how they will say, oh, did I go to zero. And they all agree because you had just finished performing fork. They agree on exactly what the address faithful click 296 00:40:06.030 --> 00:40:09.690 William Cheng: OK, so now I'm going to put one copy on write the parents don't say, Did I go to 17 297 00:40:09.930 --> 00:40:19.050 William Cheng: So in this case, they, they were 17. This one is a right operation right is not compatible with read only. Right. So this one is on Page z. So, therefore, we're gonna put my address is Asian over here. 298 00:40:19.260 --> 00:40:24.510 William Cheng: The admissions agents over here says incompatible you trapped inside the Colonel. So what would the current I'll do 299 00:40:25.500 --> 00:40:30.960 William Cheng: That. So again, what a curl do over here is that they will walk down that linear list of as region over here or VM area over here. 300 00:40:31.140 --> 00:40:38.640 William Cheng: Find out that this very second over here, we are doing copied all right. Right. This one is a privately map me, second one over here. So, what it will do is that it will make a copy 301 00:40:39.000 --> 00:40:51.090 William Cheng: Okay, so over here. What it will do is is that it will call the buddy system for new page and then make a copy of errors over here, this is the copy. I'm going to copy. So I'm going to copy this one. So this is page see over here. So when I finished making a copy this one is also see 302 00:40:52.290 --> 00:40:59.850 William Cheng: Okay, so in this case. So, so let me go back a little bit over here, right. So over here, what happens is you try. These are the Colonel. The Colonel will ask the buddy system for new page over here. 303 00:41:00.090 --> 00:41:06.210 William Cheng: Make a copy from this page of this page. And now this one is going to be called z. And now this data of you're going to go to zero. 304 00:41:07.200 --> 00:41:12.570 William Cheng: Okay. So yeah, this will be the new copy over here. And then we need to apply change the pointer over here. The point of new page. 305 00:41:12.780 --> 00:41:19.650 William Cheng: We need to change this one to rewrite. We don't have to change the child process right because oh because over here parent is the one that perform copy on write 306 00:41:20.040 --> 00:41:28.800 William Cheng: Okay, so therefore we go to this entry over here. Change it to rewrite over here. Make sure the colonel data structure is all consistent and now we need to go back into the user space program. 307 00:41:29.100 --> 00:41:36.150 William Cheng: Okay, the user space worldwide now will perform the second this operation. The second time. Why does it do that well because we're going to paste fall 308 00:41:36.480 --> 00:41:42.660 William Cheng: Know, typically, again, people will turn into segmentation ball if you return it will try this operation. One more time. So when I started right so say 309 00:41:43.050 --> 00:41:54.030 William Cheng: This operation is equal to 17 there they go to 70 over here. Now this entry is valid or this one is rewrite over here. So, what it will do is that it will follow the pointer over here and change this one to 70 310 00:41:55.110 --> 00:42:02.760 William Cheng: Okay, so when this operation is done, it will look like this. I did a copy on write and this page trend is a private copy for the parent 311 00:42:03.420 --> 00:42:09.270 William Cheng: Okay, so from this point on, whenever the parent wants what will want to make changes to page z. 312 00:42:09.660 --> 00:42:18.660 William Cheng: There so please. He has lots of global variable over here, right. So when women process or the parent process. Try to modify any other data in pages over here. Would you get another piece off. 313 00:42:19.590 --> 00:42:24.390 William Cheng: Well, no, right, it only happened. You only get a page about. Will you try to write to this page rank for the first time. 314 00:42:24.960 --> 00:42:32.520 William Cheng: Okay, any new rights over here. Now this one, said the rewrites over here on this one on all the changes over here well right into the copy 315 00:42:33.090 --> 00:42:45.270 William Cheng: Right. So that's what I said about copy on write you can read all you want, right when you read, you read on this page, will you write it for the first time we make a copy and writing the copy and also on this one on all the new rights will go into the copy 316 00:42:46.560 --> 00:42:58.020 William Cheng: Or what about the child if you had a child, you know, what is data, the child said, Did I go to zero. Okay, so again this there's no problem in this case. So this private mapping and copy on write occurs after for everything is perfect. Yeah. 317 00:42:59.550 --> 00:43:06.570 William Cheng: Well, that's okay. Remember this procedure because, you know, Colonel three, you have to implement copy. All right. Yeah. All right. What have you ever share map. Okay. 318 00:43:07.110 --> 00:43:18.240 William Cheng: Because you have sure Matt and this again this memory segment over here is rewrite right so get inside the inside a VM area VM area over here, right. This one over here is rewrite and also it's shared 319 00:43:19.290 --> 00:43:23.700 William Cheng: Now, so if it's shared over here. We don't need to tell them to rewrite because we're not doing copy. All right. 320 00:43:24.330 --> 00:43:35.790 William Cheng: Well guys, and this is again this memory segment is implement using three page friend x y AMP Z. They are all we right over here. So if the parents that did I go to seven. This data is going to be changed. Should the child process be surprised. 321 00:43:37.440 --> 00:43:49.530 William Cheng: Okay, so in this case we are you know we are sharing this particular memory side one over here. So, well, you forgot to tell us as a child prizes also sharing yet. So in this case, when the parent change data that child process shouldn't be surprised desert in this case is probably okay. 322 00:43:51.300 --> 00:44:03.870 William Cheng: Alright, so again, you know, share, share mapping. No problem. So when can things go wrong. Okay, so are we here. This is the problem we're going to have private nappy copy all right happened before forth. So right now, there's no child process. 323 00:44:04.620 --> 00:44:12.930 William Cheng: Now, so it looks like this right now. Right. So in the beginning, you know, the current processes are running over here. Again, these are the patients are you doing copy on write maybe there are heaps of interest. 324 00:44:13.320 --> 00:44:20.940 William Cheng: And maybe the data side man doesn't really matter. It's part of the mapping copy on write and this memory segment is supported by three page right x, y, and z. And we're doing 325 00:44:21.510 --> 00:44:22.440 William Cheng: So so inside a 326 00:44:22.770 --> 00:44:32.940 William Cheng: VM area over here it's going to say this one is private. Right. And also just want to rewrite. OK, so the pace table entries over here is going to be rewrite and now we're going to do copy on write first and then we're going to fork over trial process that 327 00:44:33.180 --> 00:44:41.670 William Cheng: Alright, so again, what is copyright, you know, how does the word data equal to 17th on this page over here, incompatible with a read only. You come inside the current all 328 00:44:42.060 --> 00:44:47.430 William Cheng: We walked on that linear listen as region over here or VM area with another this one, we need to perform copy on write 329 00:44:47.550 --> 00:44:54.990 William Cheng: So therefore, we're going to ask the buddy system for new page copy this one. So, this will be the new z over here and data over here is going to be equal to zero. 330 00:44:55.200 --> 00:45:00.510 William Cheng: And then we point, this point a to point to as we change this want to rewrite exactly what we did before. There's no difference. 331 00:45:01.170 --> 00:45:05.790 William Cheng: Okay. Copyright is still copied on. Right, right. So when we finish off this operation will return back into user space for by 332 00:45:06.000 --> 00:45:14.340 William Cheng: The user space. But when did you go to 70 again. Now it's compatible with rewrite is going to change this one to 17 so therefore it will look exactly as the way it was before. 333 00:45:15.540 --> 00:45:18.510 William Cheng: Okay, so now we're going to perform a fork and that's where the problem happens 334 00:45:18.780 --> 00:45:24.090 William Cheng: Okay, so what we'll do is, I will come along for cooperation over here we're going to create a child process when we create a child process. 335 00:45:24.390 --> 00:45:28.470 William Cheng: Over here, I'm going to each other. We're also going to create a child page table. What do we do with the chat page table. 336 00:45:28.860 --> 00:45:39.120 William Cheng: Okay, I mentioned before, you can actually copy of on the parent page table. So if I make a copy over here, what will happen. Right, so, so, so therefore, what we should do. Is that what you need to determine, you know, should we actually just copy the pace able 337 00:45:39.660 --> 00:45:44.370 William Cheng: That. So one thing is that when you copy paste it over here at this point it will part right here is that the right thing to do. 338 00:45:44.640 --> 00:45:54.090 William Cheng: Okay. The other thing is that maybe we can remember the previous page table before the copy on right okay so there we go okay, is this page. The point of view or point of this place. Okay. Where should appoint you 339 00:45:54.570 --> 00:46:04.380 William Cheng: Guys, again, we will have two choices. Number one is that we can actually have this one so we just make a copy of, you know, do a meme copy. Right. It's a really big data structure would do and then copy it will copy the entire parent to child over here. 340 00:46:04.950 --> 00:46:17.370 William Cheng: Does this work now. So when we make this copy over here. What are you know what did the child over here due date. So again, at the time of the four if you asked us to trial process. What is data. The child was they did equal to 17, is that correct 341 00:46:18.360 --> 00:46:26.250 William Cheng: Well, yeah, that's correct. Go here, right, because at the time, will you make will you call forth the child process, get a copy of the address space inside the address space was apparent that equal 342 00:46:26.520 --> 00:46:36.570 William Cheng: To 17 so therefore the church. You also see there you go to 70 has perfect. Okay, so there but this one is correct. Right. Yeah. So charge. So what is data have your dinner 70 but what is the child says data equals two, five now. 343 00:46:37.830 --> 00:46:45.300 William Cheng: Okay, if the chance that they're equal to five, you know, writing is compatible with ruler over here, they will change this one to five. Now the parent process will be surprised. 344 00:46:46.650 --> 00:46:49.770 William Cheng: Okay, what is the parent says over here that data equals to, you know, 16 345 00:46:50.130 --> 00:46:58.740 William Cheng: In the parents did able to 716 obviously will change the water 60 and now this whole process is going to be surprised. So in this case, copying the page table here is the wrong thing to do. 346 00:46:59.610 --> 00:47:03.090 William Cheng: Okay, so therefore it doesn't work, right. So what about the other choice over here. 347 00:47:03.300 --> 00:47:14.070 William Cheng: If the parent before it does copyright to keep a copy of the original page table. And now we'll get a copy of it. I mean, clearly, this also doesn't work, whereas over here. What he has a child, what is the value of data. Well, the charts that did I go to zero. 348 00:47:14.580 --> 00:47:17.940 William Cheng: But at the time of the fourth data should be equal to 17 so therefore this is also doesn't work. 349 00:47:19.650 --> 00:47:24.990 William Cheng: Okay, so you copy the current paste a boy doesn't where you copy the previous spaceship or it doesn't work. So, therefore, what should you do 350 00:47:26.100 --> 00:47:34.440 William Cheng: Now, so therefore the solution over here. Is that what you have to do is that you should copy the page table over here. You also should reset for copy on write 351 00:47:34.740 --> 00:47:44.250 William Cheng: Okay, you go to every as region over here for all the errors region for all the patient over here if they are private, you need to go to every page table entries over here you just send it back to read only. 352 00:47:46.440 --> 00:47:56.280 William Cheng: Okay, so you need to go instead of it. We don't want. Why is that because, because from this point on, you're doing copy on write so therefore you can actually share all you want, but when you try to write it for the first time you need a 353 00:47:56.820 --> 00:48:06.240 William Cheng: Copy or I need to kick it. Okay. So, okay, well we do is they'll be here is that this pretty remember segment over here. Again, it has, you know, a 10 kilobytes over here is implement a three page frame over here. 354 00:48:06.420 --> 00:48:11.520 William Cheng: They are X, Y, and Z. We're going to find the page table entry for x, y AMP Z. We're going to send them all to read only. 355 00:48:12.420 --> 00:48:15.810 William Cheng: Okay, so, so I'm calling this reset for copy on write 356 00:48:16.530 --> 00:48:26.490 William Cheng: That. So we said, Go copyright all the spaceship. Weren't you no matter where they were before they will read only the rewrite, we need to change them all to read only because from this point on, we're going to start doing copy on write all over again. 357 00:48:26.940 --> 00:48:35.460 William Cheng: Okay, so this way. Why don't want to show us as data equals five. Well, that's what that will, you know, get over here, you know, the child's gonna say data equal to five. 358 00:48:36.000 --> 00:48:42.060 William Cheng: So what happened is that you know they they go to Fi is compatible with read only your tribe inside the Colonel. The Colonel walk on a linear list of 359 00:48:42.300 --> 00:48:48.510 William Cheng: You know VM area said I were doing copy on right so what it would do. So I asked the buddy system for patient and where do you copy it from 360 00:48:48.720 --> 00:48:56.880 William Cheng: You copy it from this page frame over here that's pointing to this over here. So, this will be the new see over here, right. So when you make a copy of this data equal to 17 over here. 361 00:48:57.060 --> 00:49:04.260 William Cheng: And then you change this point there's a point of this why you change this one to rewrite again exactly what you do with copy on write you go back into the user space program. 362 00:49:04.470 --> 00:49:11.400 William Cheng: The user space program says equal to five is compatible with the rewrite, you're going to change the data equal to five. Okay, it's not the right thing to do. 363 00:49:12.030 --> 00:49:17.160 William Cheng: Well, yes, it's the right thing to do because. Now from this point on the child will see daily equal to five and the parent will see, did I go to 17 364 00:49:17.640 --> 00:49:20.370 William Cheng: Okay, what is the parent says, Did I go to 16 right now. 365 00:49:20.790 --> 00:49:28.860 William Cheng: Because again, over here. There you go. The 16th incompatible read only your tribe inside the Colonel, you walk down the as region inside the parent process. 366 00:49:29.100 --> 00:49:37.920 William Cheng: And you see that you're doing copy on right so therefore you ask the buddy system in the parent process for new page, you make a copy of this one, this one, go to Z. Now data equal to 17 367 00:49:38.160 --> 00:49:44.460 William Cheng: And then you change this point at the point of this one. Again, same as what we did before, change this one to rewrite. You go back into your user space program. 368 00:49:44.640 --> 00:49:50.820 William Cheng: The user space and then I go to 61 more time and now it's compatible the rewrite you change one 216. Is that the right thing to do. 369 00:49:51.150 --> 00:49:57.330 William Cheng: Well yes now from the parent, you asked what data is the data, the parents gonna say, did they go to 16 and now the child was it did I go to five. 370 00:49:58.200 --> 00:50:05.880 William Cheng: Now, so, so when you perform forward if you reserve on copy on write well then in this case it you know it will work. Right. So again, what do you ever do. 371 00:50:06.060 --> 00:50:12.840 William Cheng: You made a copy of the page table and then you go to all the page table entries over here that corresponding to memory segment. 372 00:50:13.050 --> 00:50:19.890 William Cheng: That are doing copyright. There are there are privately and there are map robbery. Right. And then you go to all these paper and you're over here. You said them all to read only. 373 00:50:20.970 --> 00:50:25.260 William Cheng: OK. So again, there's a lot of work to it that you have to do. But, but if you do it this way, that everything will work. 374 00:50:26.970 --> 00:50:28.410 William Cheng: Okay. So then one more thing that we need to 375 00:50:29.790 --> 00:50:32.610 William Cheng: The one thing we need to address over here. Okay. So, okay, you look at 376 00:50:33.240 --> 00:50:44.820 William Cheng: That. So we start with one page see over here. And then we have original page. See, you made a copy. There's a pasty and they made a copy of the patients you help me here. We're gonna end up with so many pasty right. This one has zero does my 17. This one is 16 377 00:50:45.120 --> 00:50:50.790 William Cheng: This one has five next time when we provide copy on write. And if it's on page. See, what do we copy from 378 00:50:51.930 --> 00:51:02.910 William Cheng: That so you can set a while. Maybe we need a copy of from the page table over here, but remember the page table is a temporary data structure, the way we construct the page table over here is that we would constructive, you know, from, you know, 379 00:51:04.170 --> 00:51:09.870 William Cheng: You know, for the address space representation. Okay, we mentioned before, when you need to write it. You know, you know, 380 00:51:10.590 --> 00:51:20.070 William Cheng: You know, when the, when the page on demand need to write a pace to the this, it needs to make that pace ran busy and before it does that it needs to a map that page from the page table entry. 381 00:51:20.970 --> 00:51:30.450 William Cheng: Now, so in our case over here, all these something where we go to zero. Right. So again, you have a page for Mr. We have equal to zero. Now when you try to provide copyright over here, you can really copy it from the page table anymore. 382 00:51:31.800 --> 00:51:37.200 William Cheng: So, so again, when you come into the corner over here. What is equal to zero. Well, when we go to zero you actually you don't 383 00:51:37.710 --> 00:51:42.900 William Cheng: You don't know what to copy from that. So now we know that there are four pages over here on Wednesday. What do you copy a problem. 384 00:51:43.740 --> 00:51:49.560 William Cheng: Okay, so that would be another problem we need to solve it. So now we know how to perform copy or right after fourth because we need to 385 00:51:49.830 --> 00:51:56.070 William Cheng: receive a copy on write once we receive a copy on write some of the entries over here will be have equal to zero, where do you copy from 386 00:51:56.700 --> 00:52:03.150 William Cheng: Okay, so now we need something else. Okay, so this is actually a good time to break. So I guess over here gonna 387 00:52:03.930 --> 00:52:08.880 William Cheng: You know, go to this page over here. You know, you will show you that what we need is that we need to have a shadow objects. 388 00:52:09.150 --> 00:52:21.450 William Cheng: Okay, so we're going to break right now the second part of this lecture we're going to talk about shadow object and shadow object is why you have to implement your kernel three goes in your corner, three, you have to implement copy on write together with for now.