WEBVTT

1
00:00:04.410 --> 00:00:15.630
William Cheng: Okay, this is the second part of lecture 22 so we're done with all the hardware stuff. And now we're going to look at operating system support have to use all those hardware. Yeah.

2
00:00:16.470 --> 00:00:23.100
William Cheng: So we're gonna be, I guess the first part over here is called general concerns. So we're going to take a look at a very high level picture.

3
00:00:23.670 --> 00:00:35.520
William Cheng: To see how you you know how you support virtual memory. And then so traditional the organism issues over here is that, you know, when you try to you know get the data from the desk guy so

4
00:00:36.540 --> 00:00:45.330
William Cheng: You know, so, so, so the picture over here, we start with data sitting on the desk over here. Right. And then we need to copy them into memory guys over here. This is our memory over here and then

5
00:00:46.110 --> 00:00:55.080
William Cheng: We transfer data from the, you know, on the disk into a memory. So the way it's just a little thing about is that every time when you get a page fall you copy data from. You don't want a distant memory.

6
00:00:55.530 --> 00:01:02.010
William Cheng: Okay, so what are the issues over here, right. The first one over here is called the fetch policy, when do you get this data from the desk into memory.

7
00:01:02.790 --> 00:01:08.940
William Cheng: Okay. So sounds like a kind of silly question. So we're going to see is what are the choices are and then we're going to sort of talk about when should you do it.

8
00:01:09.450 --> 00:01:16.740
William Cheng: The second one is called a placement policy will you bring data from the disk into memory one page at a time where do you put inside physical memory.

9
00:01:17.730 --> 00:01:23.850
William Cheng: And so, as it turns out that, you know, since we're using the buddy system, the buddy system. He doesn't really care where you put inside physical memory.

10
00:01:24.420 --> 00:01:27.930
William Cheng: So so so we mentioned before, when you try to put it on the desk.

11
00:01:28.350 --> 00:01:35.100
William Cheng: Then it kind of matter. You know what it did have gone to this is that this is really, really slow device there see Tom rotational they didn't see all that kind of stuff.

12
00:01:35.520 --> 00:01:43.530
William Cheng: So they don't in chapter six. Want to see see more about it. But now we put data into memory while since we are you know we're not using the first memory alligator.

13
00:01:44.040 --> 00:01:48.030
William Cheng: If you're using the first remember alligator that where you put the data will matter, right, because if

14
00:01:48.210 --> 00:01:56.010
William Cheng: You're near the beginning of the chain, the performance going to be a little better. If you knew the end of the link list and its performance gonna be really bad. But since we're using a buddy system.

15
00:01:56.400 --> 00:02:04.710
William Cheng: Then the performance doesn't really matter where you copy the data into that. So the replacement policy over here is actually not important. If you're using the buddy system.

16
00:02:05.460 --> 00:02:10.920
William Cheng: So when you bring a page from the disk into memory, you'll bring anywhere you want. And since we're using one level of indirection.

17
00:02:11.130 --> 00:02:17.130
William Cheng: In the page table entry. We're going to point to the physical page so it doesn't really matter where the physical page is located. If we point to it.

18
00:02:17.580 --> 00:02:19.140
William Cheng: The performance going to be exactly the same.

19
00:02:20.040 --> 00:02:30.660
William Cheng: Okay, so that's one of the beauty of using the pace table the are you using the patient but approval address translation, because we're using one level in direction the placement policy over here, no longer become an issue.

20
00:02:31.650 --> 00:02:39.960
William Cheng: Okay, so that's that's a great thing. The third policy over here is gone replacement policy, we try to bring data from this into memory. What if you run out of memory.

21
00:02:40.920 --> 00:02:49.680
William Cheng: Then when you are running out of memory, what you have to do is that you need to take some physical memory, what do you have to do with it. Right, we talked about before in chapter seven. Is that what you have to do is that you can just swap out the memory.

22
00:02:50.190 --> 00:03:00.900
William Cheng: Okay, so before we're swapping one memory segment at a time. Now we're doing paging you need to, you know, copy data into memory, you need to take one page swap it out to the desk. So this way you need to create a free page.

23
00:03:01.290 --> 00:03:05.760
William Cheng: Okay. And this way you can copy data into that free page, right. So again, the way the way we are talking about is that

24
00:03:05.940 --> 00:03:14.130
William Cheng: Where you are you find a piece of memory you write it out to the desk and now you end up the free page frame, right. So can we use the word page frame and pages.

25
00:03:14.370 --> 00:03:19.260
William Cheng: Interchangeably you're gonna have the previous page rank and now you can copy data into the three page right

26
00:03:20.100 --> 00:03:29.730
William Cheng: Okay, so, so, which one do you did you write it out to the swap says that's no as replacement policy right so we're gonna we're gonna take a look at all these issues. I'm at the point other than the placement policy. Yeah.

27
00:03:31.200 --> 00:03:39.420
William Cheng: All right, the Fed's policy over here. So we mentioned before, the one thing that you can do with swapping is that you can start your process of as if you have no page and memory.

28
00:03:40.020 --> 00:03:45.780
William Cheng: Okay, so we start running a program right here's this. Here's our program. Here's the tech side may use that data segment. Here's BSS

29
00:03:46.290 --> 00:03:50.670
William Cheng: Inside our memory. We're going to say that at the beginning. We don't read any data on this into memory.

30
00:03:51.600 --> 00:04:00.750
William Cheng: Okay, we, I mean, if you think about Microsoft Word Microsoft where the text is really, really big when you double click on word we actually, we don't want to bring anything from a distant memory because that will take too long.

31
00:04:01.800 --> 00:04:08.100
William Cheng: Okay. So, therefore, what we're gonna do is, I'm going to start process of with no pages and primary storage. Okay, so what we're doing is

32
00:04:08.520 --> 00:04:18.990
William Cheng: We're going to sit up, you know, data searching inside companies is them as if everything is swapped out. Okay, so now what we need to do that, we need to bring pages one page at a time only as we need it.

33
00:04:20.010 --> 00:04:28.470
William Cheng: Okay, so this is known as on demand paging okay or, you know, so, so when bring the page on demand, and only on demand. We don't try to bring the page, you know, anytime earlier.

34
00:04:29.160 --> 00:04:34.020
William Cheng: Okay, so only when we need it, that when we go to the go to this and get data. Okay.

35
00:04:34.530 --> 00:04:42.300
William Cheng: So this is known as the man page or on demand page and they're all the same thing. I'm going to defer the process that you absolutely have to do it. Okay, so why do we do this.

36
00:04:43.140 --> 00:04:48.930
William Cheng: Okay, so again we're going to use Microsoft Word as an example. This program is the Microsoft Word. Okay. It's a really big program has

37
00:04:49.200 --> 00:05:00.390
William Cheng: Really, really big tech side. Man, if we bring the entire tax everyone's gonna, it's going to be very slow, sometimes with the way we use Microsoft Word is that we open up a document and a one word and then do a save and then we quit the program.

38
00:05:01.320 --> 00:05:05.820
William Cheng: Okay, so in that case it would bring all this data from this into memory. Most of it is going to be a waste of time.

39
00:05:06.330 --> 00:05:18.420
William Cheng: Okay, so therefore we should bring the data that are only needed by Microsoft Word to modify that one word. Okay, so this word we bring the smallest amount of memory. So in this case, we're going to be as fast as possible.

40
00:05:19.680 --> 00:05:27.450
William Cheng: Alright, so, so, so we're going to defer processing until you absolutely have to do it. So when we access particular text segment that's when we bring the data yet.

41
00:05:27.810 --> 00:05:34.950
William Cheng: Okay, so we're going to bring the data in four kilobytes at a time. So if you try to fetch and instructions that attack segment for whining structure. We're going to bring the entire page.

42
00:05:35.250 --> 00:05:45.630
William Cheng: Okay, so next time when you jump around and your co you you you call a function or whatever, if it goes to a different page. We're going to bring that page. And we're going to bring these pages one at a time. Only when you absolutely need it.

43
00:05:47.160 --> 00:05:51.450
William Cheng: Okay, so this is this particular approach is also known as lazy evaluation.

44
00:05:52.230 --> 00:05:58.080
William Cheng: So when you do that, you're going to be for processing until as late as possible because if you wait long enough, maybe you don't have to do it at all.

45
00:05:58.380 --> 00:06:07.650
William Cheng: Okay, so again, if you think about Microsoft Word we if we only bring the stuff that we need all the others. The other stuff. We don't need, in the end, we're going to create a program. So they have. We don't have to do it at all.

46
00:06:08.550 --> 00:06:19.410
William Cheng: Okay. So in the end, the web is if you if you implement on demand page in your performance. The operating system actually looks really, really good. Right. So for example, if you double click on your desktop, something's going to happen look like something's

47
00:06:19.740 --> 00:06:22.890
William Cheng: Something's going on. So, especially if you start running Microsoft Word.

48
00:06:23.310 --> 00:06:29.280
William Cheng: What is trying to do is that I tried to run the initial code. It will only bring the pages that you need. And pretty soon we're going to start be able to editing stuff.

49
00:06:29.730 --> 00:06:32.850
William Cheng: All the other stuff you don't need that were never brought in front of this into memory.

50
00:06:33.540 --> 00:06:44.940
William Cheng: Okay, so therefore, India, your performance going to be very, very good. Because, because all the other junk that you don't need. They will never problem, the distinct memory that so these evaluation is actually a very important computer science principle.

51
00:06:46.110 --> 00:06:50.430
William Cheng: You know, whenever you try to have a design decision you sort of need to look at the total, sort of, you know,

52
00:06:50.850 --> 00:06:56.220
William Cheng: Think about whether you can do things in using lazy evaluation because it turns out that you can actually delay.

53
00:06:56.640 --> 00:07:05.010
William Cheng: The processing on to you absolutely have to Indiana, you might end up with very, very good performance, guys. So I don't know if you have taken at this data structure class.

54
00:07:05.460 --> 00:07:10.650
William Cheng: There are some data structure that they have infinite recursion there recursive data structure. They're infinitely recurs

55
00:07:11.370 --> 00:07:16.680
William Cheng: So that kind of data structure. What do you do with it while you can never evaluate that kind of a data structure because it will take you infinite amount of time.

56
00:07:17.220 --> 00:07:27.360
William Cheng: So the way evaluate these kind of data structure is they use lazy evaluation. So at the time, will you absolutely have to evaluate the data structure, you're going to evaluate this data structure only up to what you need.

57
00:07:27.930 --> 00:07:30.960
William Cheng: Okay, all the other stuff that you don't need. Don't even bother to evaluate them.

58
00:07:31.470 --> 00:07:38.460
William Cheng: OK. So again, you know, this way you perform much, much better. Because if you try to evaluate the entire data structure. It will take you infinite amount of time.

59
00:07:39.120 --> 00:07:45.780
William Cheng: Guys, okay. Instead, computer science, and one of the principle that that be used in software design is lazy evaluation.

60
00:07:46.320 --> 00:07:51.660
William Cheng: Lazy evaluation doesn't work all the time. Yeah. So sometimes it works really well sometimes works really poorly.

61
00:07:51.930 --> 00:07:58.440
William Cheng: As when you have a design decision to me, you can sort of think about is that, do I want the data right now. Or maybe I should defer until as late as possible.

62
00:07:59.190 --> 00:08:10.800
William Cheng: Guys, again, it's a choice that you have to me. Yeah, right. So, in all the modern ordinances them when they try to implement the fetch policy when to get data from the this into memory, they all do this as late as possible.

63
00:08:11.490 --> 00:08:20.190
William Cheng: Yeah, right. They're all they're all implement on demand agent. Yeah. All right. I'll play some policy we mentioned before, it doesn't really matter because we're using buddy system.

64
00:08:20.610 --> 00:08:27.270
William Cheng: What about the replacement policy, right, will you bring that this one of interpreting the patient at this in the memory. What if you don't have physical memory.

65
00:08:27.660 --> 00:08:31.380
William Cheng: guys forget what you need to do is that you swap out a page, which one do you pick

66
00:08:31.890 --> 00:08:34.050
William Cheng: Okay, so over here. One suggestion of yours or

67
00:08:34.290 --> 00:08:45.840
William Cheng: Why do you use the first in first out policy. Right. So the way you should think about is the using first female first our policies that you put all your page frame in the queue. Right. This is a key piece for him right page frame over here. Patient over here.

68
00:08:46.080 --> 00:08:52.500
William Cheng: The earliest one that you brought it. You got to put it on the head of the queue over here. And the one that you brought in just now the we put it at the end over here.

69
00:08:53.370 --> 00:09:01.350
William Cheng: Okay, so this way. What you would do is if you're using the first thing first, I'll policy, you will go to the header of the page that the head of the queue over here and you can write this one out to desk.

70
00:09:01.650 --> 00:09:05.460
William Cheng: Okay. And this way you create a new page for it. And now you can transfer data into the space, right.

71
00:09:06.060 --> 00:09:20.760
William Cheng: And so again, I'm using the word physical page a patient and we'll be hearing to change it because that's how we talked about, you know, memory, you know, operating system. Okay. So as it turns out, this, this first come first in first our policy can be a really terrible policy. Why is that

72
00:09:21.870 --> 00:09:28.230
William Cheng: Now, maybe this data that actually sitting at the head of the queue over here. What if this is the one that you use most of the time.

73
00:09:28.980 --> 00:09:32.940
William Cheng: Okay, if this is the one they use most of the time you're going to write it out to the desert, and pretty soon you have to bring it back.

74
00:09:33.630 --> 00:09:41.430
William Cheng: Okay, so in that case, you know, maybe all the, you know, all the page friends over here at the head of the skew maybe all of them. They are very popular.

75
00:09:41.790 --> 00:09:49.560
William Cheng: Guy. So, therefore, if you start, you know, writing it out to the desk, pretty soon you have to bring them back back. So in that case, you're going to waste all your time writing them after this

76
00:09:50.220 --> 00:10:03.390
William Cheng: Okay, so they don't want to sort of see what kind of policy for replacement policy over here are reasonable a policy to implement inside the operating system. Right, right. So first of all, what we need to do is that the focus on the fetch policy right now. Yeah.

77
00:10:05.370 --> 00:10:06.960
William Cheng: Alright, so I'll be here.

78
00:10:07.620 --> 00:10:15.120
William Cheng: Again, you know, inside the operating system over here, the operating system data showed you that you use to implement an address space again only the user portion of the address space.

79
00:10:15.330 --> 00:10:19.530
William Cheng: We use the data structure to represent them and the data structure is known as the virtual memory map.

80
00:10:19.740 --> 00:10:25.350
William Cheng: OK, so the virtual memory map data. So you look like this. Right. And this is the abstract and you're done you know this data structure.

81
00:10:25.560 --> 00:10:34.350
William Cheng: Implement the abstraction for the user space process. Yeah. So again, the colonel part of your space doesn't require any data search the represent because the colonel actually knows everything already

82
00:10:34.680 --> 00:10:44.580
William Cheng: Yeah, alright. So, again, the virtual memory map over here. It's a lingo some as region over here. Whenever you get a pace for whenever you get a pace while you get a virtual address so so so yeah

83
00:10:45.030 --> 00:10:57.510
William Cheng: So for example, you know, a way to to perform address translation be equal to zero. So, in that case, instead me over here, we perform aggregations Asia, you got a page fall so they know exactly which virtual address cause the page Hall.

84
00:10:58.470 --> 00:11:07.170
William Cheng: Okay, so therefore, when you trapped inside the operating system, what you have is that obviously some as you're going to start with a virtual address and you try to sort of figure out whether you can fix this page for now.

85
00:11:07.890 --> 00:11:15.600
William Cheng: Okay, if you cannot fix this baseball, then the page fall turn into a segmentation fall and and in the end going to you're going to choose your user space program. Right.

86
00:11:15.810 --> 00:11:25.110
William Cheng: You know my may also going to see that there's no signal handled that kind of stuff. If there's a signal handler they have to do you know you have to signal delivery, all that kind of stuff. Right. But it turns out that, you know,

87
00:11:25.560 --> 00:11:31.110
William Cheng: That there's no way for you to resolve this page fall, then the page will turn into a segmentation ball. Okay. And then you're curious.

88
00:11:31.410 --> 00:11:39.510
William Cheng: Curious user space program that and how do you actually do this right, you take your virtual address over here, you know, walked on this linear listen as region.

89
00:11:40.500 --> 00:11:42.180
William Cheng: That. So as we can. Over here again.

90
00:11:42.600 --> 00:11:50.790
William Cheng: Every one of them represent a memory segment and the as region over here, they don't overlap, because your address space doesn't overlap right over the, over here, I just space over here.

91
00:11:51.000 --> 00:11:58.860
William Cheng: Are they, they are right after each other. But again, they don't overlap and we mentioned before, you know, maybe between the tech side when the PSS Agron there's a gap.

92
00:11:59.250 --> 00:12:07.680
William Cheng: Guys, again, there could be gap over here between the segments. Right. So what you would do that you will take your virtual address you walk down this linear list of as we try to sort of figure out where it belongs to

93
00:12:08.490 --> 00:12:16.980
William Cheng: Okay, so, so every you know as region has a start out dress has the address. So by looking at the virtual address over here, you start to find out which memory submit it belongs to

94
00:12:17.190 --> 00:12:22.110
William Cheng: And then you use a data structure over here to figure out whether you can actually repair this page or not.

95
00:12:22.440 --> 00:12:26.880
William Cheng: Okay, if you can do you will you will do and then you sort of figure out what your current data structure.

96
00:12:27.060 --> 00:12:34.650
William Cheng: And you fix all your page table and this one will you return to the user space program they use it for one will try it again. And this time, or hopefully it will be successful.

97
00:12:35.010 --> 00:12:40.740
William Cheng: Okay, if it turns out it was still not successful, you're going to end up with the second page file, you can set a current or maybe you have a fixed something else.

98
00:12:41.190 --> 00:12:48.450
William Cheng: Okay. Sometimes the patient can sometimes a patient can be fixing ya Shah, sometimes they actually require multiple iterations in order for people to get fix

99
00:12:48.900 --> 00:12:55.620
William Cheng: That right so the important part over here is that we need to use this data structure, you know, sort of figure out how to repair the page fall

100
00:12:56.070 --> 00:13:11.250
William Cheng: So this data starts up before we call them as region. So now we're in chapter seven. We sort of know that this is actually a virtual memory map, we're going to actually give you the real name for this data structure inside Linux there. Well, actually, we're not their head. Okay, so therefore

101
00:13:12.690 --> 00:13:20.940
William Cheng: I'm just going to give you a preview over here. So in this case, you know, these, you know, these as regional view again their address address space region.

102
00:13:21.450 --> 00:13:27.390
William Cheng: So inside your kernel assignment also inside Linux. This one is called a VM area VM underscore area.

103
00:13:28.170 --> 00:13:37.140
William Cheng: A R Ea over here, right. So what does an area on era is a segment. They're all the same thing. Okay. A segment your memory segment and then in the region.

104
00:13:37.800 --> 00:13:44.880
William Cheng: Area, they're all the same thing. They're contiguous virtual addresses that have them try to implement one of these memory segments.

105
00:13:45.480 --> 00:13:51.600
William Cheng: Yeah, so, so later on we're going to sort of see that instead of calling them as region. We're going to call it a VM area. Everything else, so exactly the same.

106
00:13:52.110 --> 00:13:56.070
William Cheng: Yeah, alright. So, what you would do is that whenever you get a page for you walked on this list of

107
00:13:56.520 --> 00:14:00.420
William Cheng: Lists up. Now we know, is there a VM area, you try to find out which one it belongs to

108
00:14:00.630 --> 00:14:10.050
William Cheng: A of the memory segment is swapped out we can get it on the desk. Right. So again, if you're inside a tech segment or data segment over here, you can go to the file system over here, try to get the data.

109
00:14:10.440 --> 00:14:13.980
William Cheng: If the data over here. You don't to the heap segment or, you know, or the

110
00:14:14.670 --> 00:14:23.940
William Cheng: Or the segment right underneath us as region over here, a VM area. There's an anonymous object because these, you know, these pages don't have file system names.

111
00:14:24.360 --> 00:14:29.160
William Cheng: Okay, so therefore, in this case we will ask the anonymous object, go to the swap space to get the data.

112
00:14:29.820 --> 00:14:35.790
William Cheng: Because remember, you know, every, you know, every page inside our address space, there's a place for them to go. That's called a backing store.

113
00:14:36.120 --> 00:14:48.270
William Cheng: Where so when you need to, you know, sort of data into your into your file system or so the data inside your swaps ways. You go to the back end store to store the data and the data swapped out and later on when you need them. You bring it back in for

114
00:14:49.710 --> 00:14:51.090
William Cheng: Bringing it back in from the back end store.

115
00:14:51.540 --> 00:14:59.940
William Cheng: There. So the back end story can use the file object to get it and also for some of the memories, like, man, you're going to use the anonymous object to get them. They are anonymous because they don't have a file system name.

116
00:15:00.300 --> 00:15:02.820
William Cheng: Now, again, the example that we saw before over here.

117
00:15:03.000 --> 00:15:13.200
William Cheng: This is the file you called the end map system called the map of fly into outer space. So in this case, will you need data, you ask the file object over here to go to the go, you'll go get the data and transfer that data on a distinct memory.

118
00:15:13.890 --> 00:15:22.650
William Cheng: OK. So again, when you are fetching the page use this particular data structure over here and you ask the right object to go to the right place to get a data for you. Okay.

119
00:15:24.930 --> 00:15:25.470
William Cheng: All right.

120
00:15:27.540 --> 00:15:33.420
William Cheng: So let's take a look at, you know, how do you actually do this guys are going to sort of simulate your program running over here.

121
00:15:33.780 --> 00:15:38.280
William Cheng: At the beginning, we're doing on demand pages. So in that case, none of the pages are in physical memory.

122
00:15:38.670 --> 00:15:43.230
William Cheng: Yeah. So, therefore, that means that if you go to the page table over here, the page that was full of zeros.

123
00:15:43.560 --> 00:15:54.600
William Cheng: Guys. Okay, this really easy to do. You take the page table user out the entire page table. So, therefore, you do that the validity bit inside every page table entry over here you go to zero. Right, so zero over here that we're seeing over here is equal

124
00:15:55.080 --> 00:16:02.280
William Cheng: Validity bit. Yeah, but every little bit over here we go zero. That means that the page table entries over here are completely invalid.

125
00:16:02.970 --> 00:16:08.400
William Cheng: OK. So again, the page table we work together with the virtual memory map.

126
00:16:08.760 --> 00:16:15.990
William Cheng: Okay, the pace table is a kernel data structure that's used by the hardware. So again, when you just talk about both the virtual memory map over here and also the page table. Yeah.

127
00:16:16.110 --> 00:16:24.450
William Cheng: So, so once you get a baseball. We're gonna so I'm not going to keep coming back to this page over and over again. So when I talk about the virtual memory map. Think about this data structure right here.

128
00:16:25.110 --> 00:16:28.950
William Cheng: Okay, so we're going to use a virtual address over here, walk down this list of as region or

129
00:16:29.190 --> 00:16:37.620
William Cheng: VM area over here and try to sort of find out you know which memory segment it belongs to. And then we need to figure out whether we can fix this pretty good page table the page power now.

130
00:16:38.580 --> 00:16:44.790
William Cheng: Okay, so now we're going to take a look at example to see on the main page it when you provide starts around. What is the first thing that you do.

131
00:16:45.480 --> 00:16:51.360
William Cheng: Okay, so, so let's say that you are you for coffee HR process child processes, the same address space was sharing the address space.

132
00:16:51.570 --> 00:16:58.500
William Cheng: The child process called exact then in this case we're going to start a new program, we're not going to bring any pages on this into memory. So we're going to

133
00:16:58.740 --> 00:17:06.990
William Cheng: Go to the page tables zero every page that went up over here. Okay, so now the first thing that we do from this point on, is that we're going to start execute our startup.

134
00:17:07.800 --> 00:17:19.200
William Cheng: The startup I'm shooting to start off on she's the one that caused me. Okay. So, therefore, where's the startup. I'm sure the startup function inside of tech segment over here. So we're going to start pitching structuring the tech stack, man. So this one is going over here is going to

135
00:17:20.310 --> 00:17:30.630
William Cheng: The test second over here. We're going to perform address translation, we're going to end up using one of the pace table entries over here and the pace table entries that we as equal to zero. So we're gonna we're gonna end up dropping into the kernel.

136
00:17:31.440 --> 00:17:40.110
William Cheng: Okay, so therefore, when you're using demand paging on the main page. And the first thing that happened to your user process when you make the exact same call is that you're going to pay for

137
00:17:40.890 --> 00:17:47.520
William Cheng: You guys okay you make the executives and call you come to the operating system kernel you wipe out the address space you replay the address base of the new way.

138
00:17:47.730 --> 00:17:52.860
William Cheng: And now when you return back into the user space. The first thing that you do is that you've got to get a paintball and boom, you're backing out of Colonel

139
00:17:54.150 --> 00:17:57.120
William Cheng: Okay, that's the reason for that is that you're doing on demand pager.

140
00:17:58.200 --> 00:18:06.660
William Cheng: Okay. I mean, some people when they're doing their Colonel three that only understand that and hope so, please understand that the first thing that happened, your user process is that it's going to be a pitfall.

141
00:18:07.770 --> 00:18:20.460
William Cheng: Okay. Alright, so we're here, we're going to address translation and this one over here pointed this page. The equals zero. Boom. You try things out of Colonel. OK. So again, the first thing happened over here is that you know that that

142
00:18:21.030 --> 00:18:28.140
William Cheng: That that equal to zero, the hardware will trap you know traveling into the kernel. OK. So again, you're going to transition from your users.

143
00:18:28.530 --> 00:18:31.110
William Cheng: Or users right contacts into the kernel three contacts.

144
00:18:31.290 --> 00:18:41.430
William Cheng: And what you will do is that is that instead of, instead of Colonel Sanders, you're going to know that you gotta, you gotta pace fall. So you walk down that linear listen as regional vs area you find out which one it belongs to

145
00:18:41.670 --> 00:18:51.060
William Cheng: You guys. So in this example over here. We're going to find out the virtual address that you are using belong to the tech segment and the organization says our tech segment I know exactly how to fix it or how do you fix it.

146
00:18:52.500 --> 00:19:03.120
William Cheng: That's okay if you go to this page over here, the way you fix this, is that you need to find out which page belongs to. And then you ask the file object to copy that the data from the desk into memory.

147
00:19:03.750 --> 00:19:14.910
William Cheng: That's okay, you know, in this case, you get a patient, he saw you executable code. We actually know about codes currently sitting on the desk. So therefore, you're going to ask the file object to transfer data from a distant memory your kernel that goes to sleep.

148
00:19:15.630 --> 00:19:22.800
William Cheng: So in that case, eventually, when it's done your corner is going to get woken up. Okay. So, by the way, how does the file object over here knows where to transfer the data to

149
00:19:23.310 --> 00:19:33.900
William Cheng: Okay, so before you ask the foreign object to to to to transfer data you need to allocate and four kilobytes of memory, guys. How do you do that while you call the buddy system say give me four kilobytes.

150
00:19:34.530 --> 00:19:42.360
William Cheng: OK. So again, I'm going to switch between these slides over here is going to get pretty confusing. So what you would do is that you called the buddy system over here to allocate a four kilobytes of memory.

151
00:19:42.570 --> 00:19:47.160
William Cheng: And now once is allocated over here, then you can transfer data into it. Okay, if

152
00:19:47.520 --> 00:19:52.710
William Cheng: You know the buddy system says, I have no physical page. So in this case, you have to execute a replacement policy.

153
00:19:52.890 --> 00:20:00.630
William Cheng: Again, we're going to talk about the replacement policy, a little later. So right now we're going to assume that when you ask the buddy system for page the buddy system say here's four kilobytes.

154
00:20:00.870 --> 00:20:08.370
William Cheng: Okay, so in that case, what you can do is that you can ask the file object to transfer data from the desk into memory your kernel that goes to sleep.

155
00:20:08.700 --> 00:20:17.880
William Cheng: You sleep on the IQ and now in the iOS device over here will transfer data from that this into memory when that operation is done. What it will do is that a will interrupt the CPU.

156
00:20:18.090 --> 00:20:23.460
William Cheng: He sent an email service. Okay, again, two things happen. You're going to wake up your kernel threat and you start an exile operation.

157
00:20:23.730 --> 00:20:30.810
William Cheng: Okay, so when our current author walks up wakes up, he will know that the data has been transferred from the distant memory. So what does have to do now.

158
00:20:31.320 --> 00:20:42.570
William Cheng: Okay. So, so what do we, what do we know at this point is that the pace for has been fixed. So what it will do is that it will set up the colonel data structure. Make sure everything is inconsistent state before going to the user space program.

159
00:20:43.410 --> 00:20:49.740
William Cheng: That is very, very important every time when you go into the user space program, you have to make sure that your kernel data structure is in a consistent day

160
00:20:49.920 --> 00:20:55.560
William Cheng: Because once you get into the user space program. You don't know when are you going to come come back into the current or the next time.

161
00:20:56.490 --> 00:21:01.860
William Cheng: Okay. So, therefore, you know, the next time we will we come inside of Colonel, maybe you're running a different program may be running

162
00:21:02.130 --> 00:21:07.560
William Cheng: Different software, you got to make sure that your kernel is in a perfect shape before you return to the user space.

163
00:21:07.800 --> 00:21:12.840
William Cheng: Okay, because otherwise next time when somebody companies that are Colonel, they will be surprised. And then you're going to end up crashing Colonel

164
00:21:13.440 --> 00:21:20.310
William Cheng: Okay, so what we need to do over here is that before you go back to the user space. Well, but we need to make sure that the Colonel, you know, data structure, you know,

165
00:21:20.760 --> 00:21:23.490
William Cheng: Isn't a good day. So therefore, we need to go to our

166
00:21:23.940 --> 00:21:31.920
William Cheng: You know, a virtual memory map update the data structures again what what data do you have to update. So later on in chapter seven. We're going to talk about all the data structure, you have to update

167
00:21:32.490 --> 00:21:36.300
William Cheng: So again, incredible three at the implement all this kind of thought. So you need to know exactly what they

168
00:21:36.600 --> 00:21:41.640
William Cheng: Need to be updated that alright so we're going up there. All the colonel data structure and also the page table. We also need to fix it.

169
00:21:42.120 --> 00:21:46.710
William Cheng: Right, because now you know this pretty prepared, you know, a physical page over here, we need to

170
00:21:47.040 --> 00:21:52.170
William Cheng: Go back to the original page table entry that cause the page, while we're going to have the physical page over here. The point of this one.

171
00:21:52.470 --> 00:22:00.180
William Cheng: Right. And also we're going to say equals zero. And then we're going to set this particular access right over here to be read only because it's the tech segment.

172
00:22:00.690 --> 00:22:05.730
William Cheng: Okay, so once we finished fixing everything over here, we're going to go back into the user space well glad

173
00:22:06.480 --> 00:22:15.600
William Cheng: So once we fixed up everything over here. I'm going to go back to the user space or when we say equals to one and return from the track and what the user space program. You know what it will do is that since

174
00:22:16.080 --> 00:22:25.950
William Cheng: You know, we're in the middle of the MMU operation wonderful address translation. So what it will do is that it will pick up on where you left off new and this case since you get a trap. You are supposed to, you're

175
00:22:26.250 --> 00:22:32.190
William Cheng: Supposed to die. As it turns out you returned back from the Colonel. So what you will do is it will try the operation. One more time.

176
00:22:32.970 --> 00:22:43.170
William Cheng: Okay, so again inside the CPU, it knows that when you perform address translation and if we try things out the Colonel. If you return for the Colonel. What it will do is it will perform the address translation. One more time.

177
00:22:44.130 --> 00:22:53.820
William Cheng: That the second I want to do that. It will again go to the executive, same place. Now the equals two, one and then the accident over here is going to be to be read only. So, what you will do that you will take the physical address

178
00:22:54.000 --> 00:23:02.190
William Cheng: Left shifted by by topic added to the page offset and then you can actually go across the physical memory over here and then festering structure into the CPU.

179
00:23:03.330 --> 00:23:10.230
William Cheng: OK. So again, this instruction was still on the desk you copy it four kilobytes on a desk put into physical memory and now will you finish.

180
00:23:10.530 --> 00:23:21.270
William Cheng: Your, your, your pace fall when you try to address translation. One more time. You're going to end our copy that you know that this four bytes of, you know, machine Saatchi into the CPU and now the CPU will be able to execute that machine traction

181
00:23:22.590 --> 00:23:28.530
William Cheng: There. So this is going to be your for your, your, your, your, your first first page fall and then what do you do from that point out

182
00:23:29.130 --> 00:23:37.380
William Cheng: Okay, I guess you haven't really seen the CO for the star booty. So what it will do is that A star routine over here is going to set up the the the the

183
00:23:38.310 --> 00:23:46.530
William Cheng: The, the stock space for the main function and then he will call me remember the startup. I'm sure will call me and take the return code for Matt and collects it

184
00:23:46.890 --> 00:23:54.210
William Cheng: Okay. So, therefore, the next thing that the startup function will do is that it will call me when it's hard to call me. It needs to push data onto the stack.

185
00:23:54.570 --> 00:23:59.730
William Cheng: Okay. So, therefore, what it will do is that I will actually access the stack that so. So once it's done.

186
00:24:00.330 --> 00:24:02.760
William Cheng: It will be executed a few instructions over here, you know, for

187
00:24:03.120 --> 00:24:09.390
William Cheng: Instance exact man so next few instruction, you know, hopefully it will not cause any peaceful because they're all sitting on the same page.

188
00:24:09.630 --> 00:24:19.530
William Cheng: then pretty soon is called the main function and then what it will do is that it will need to push data onto the stack. Right. Okay. So, therefore, the second page while you're supposed to get is going to be inside the stack segment.

189
00:24:20.580 --> 00:24:26.310
William Cheng: Okay, so in that case what will happen over here, right. So again, the same thing happened over here. Will you try to write data to the stack over here we're going to

190
00:24:26.580 --> 00:24:31.800
William Cheng: Address Translation and then we can we take the virtual page number the virtual page number is going to be really big.

191
00:24:32.640 --> 00:24:42.270
William Cheng: Right, because the address space that sack is actually at the bottom over here. So again, when we, when we access this page table entry this page, why be equal to zero. And boom, which happens at a carnal. Yeah.

192
00:24:43.530 --> 00:24:48.030
William Cheng: Yeah. So in this case, want to try things out of control over here. So in this case, what happened is that a kernel.

193
00:24:48.360 --> 00:24:56.160
William Cheng: Of so remember this particular memory segment is managed by the anonymous object. Right. So in this case, we don't have to go to the desk. The honor you anonymous

194
00:24:56.670 --> 00:25:00.420
William Cheng: Object over here, this particular page is not swap out to the disk yet.

195
00:25:00.690 --> 00:25:11.400
William Cheng: So therefore, the anonymous object. What it will do is it will actually ask the buddy system for page and this page you will be full of zero, right. So they're all in this object what it would do is that it was said this paid all to clear them out to the zero,

196
00:25:11.850 --> 00:25:17.550
William Cheng: So again, this depends on the operating system some optimism will clear out to the zero, click them all to be zero.

197
00:25:18.060 --> 00:25:25.680
William Cheng: There's opportunities have no a salary as we mentioned before sliders is actually a high performance optimism is hilarious. It will not zero. This page.

198
00:25:26.280 --> 00:25:33.810
William Cheng: Okay, for Linux and Linux. What it will do is that it was zero. This page. So every time when you get a new page you actually be very happy that the pages will have zero

199
00:25:34.230 --> 00:25:41.850
William Cheng: Okay. So whenever you get a star for him over here. The first time you use it the stack. The other, the particular page inside the stack. They're all be filled with zero

200
00:25:43.230 --> 00:25:53.520
William Cheng: So in this case, it will be pretty fast, right. You don't have to go to this. You don't have to wait for it. So in this case, we asked the buddy system for four kilobytes page. If the buddy system. So we're all allow we have to execute a replacement policy.

201
00:25:53.730 --> 00:26:03.450
William Cheng: Otherwise the buddy system will return you with a free page. So this guy is working quickly modify all the colonel data shark here to say that this particular page right now it's inside the colonel is no longer sitting on

202
00:26:04.500 --> 00:26:13.680
William Cheng: Is actually it's not in this office and we have created one over here. We're going to have the physical page number of your point of this that be equal to one and this case the access rights over here.

203
00:26:14.190 --> 00:26:20.550
William Cheng: What should the access. Right. The be over here. Okay, so if you're doing copy on raw, we can actually set it to read only over here.

204
00:26:20.880 --> 00:26:25.320
William Cheng: Okay. And then in this case we're doing copyright. So we're going to return back in the user's Facebook when

205
00:26:25.530 --> 00:26:35.730
William Cheng: We returned back into your users. First one over here and now the user space program will try the second time. So now when I tried to the second time over here. Be equal to zero, but now it's incompatible is read only.

206
00:26:37.410 --> 00:26:42.000
William Cheng: Okay. So, therefore, what happened is that you is going to end up traveling into the kernel again because of the page fault.

207
00:26:42.180 --> 00:26:55.260
William Cheng: Okay, so now the colonel will walk down a linear list of a VM area as region over here find again that you know that which memory segment it belongs to. And then it will see that, oh, you're performing the right operation and in this case.

208
00:26:55.860 --> 00:27:01.230
William Cheng: The, the private bit is set inside the as region over here. So, therefore I'm doing copy. All right.

209
00:27:02.010 --> 00:27:07.770
William Cheng: Okay, so what it will do instead of going over here is that when you come back into the kernel. The second time what he would do is have proven copy. All right.

210
00:27:07.950 --> 00:27:14.640
William Cheng: He will ask the the buddy system for another page. Make a copy over here. So, this the original page over here is going to be read only.

211
00:27:14.850 --> 00:27:20.010
William Cheng: And this one is going to be set to rewrite right so in this case over here, they would change the point of the point that new one over here.

212
00:27:20.280 --> 00:27:29.400
William Cheng: Change the actual is right over here to rewrite and then again it will go back to the user space. The second time and the user space, you know, again, you know, the trappings out of CPU, you have to

213
00:27:29.820 --> 00:27:39.720
William Cheng: Perform either translation of the third time. So in this case, equals two, one and rewrite over he'll be compatible with right so in this case what it would do is they go right to the memory location right here.

214
00:27:40.500 --> 00:27:48.210
William Cheng: Okay, so the page full of zeros over here will stay full of zero and this page over here will have one main one memory location over yes we modify

215
00:27:48.720 --> 00:27:58.410
William Cheng: You know, after you. You know, you come into the kernel after you come to the colonel twice the third time, will you provider translation will be successful and you modify the memory location right here.

216
00:28:00.180 --> 00:28:10.260
William Cheng: Okay. So, therefore, you know, the stack over here. The you know what you do on demand paging are the behavior for the tech segment and the behavior for the stack segment over here is actually very, very different.

217
00:28:10.710 --> 00:28:23.610
William Cheng: Okay, so one of the reason for them to be very different is that, you know, the segments. I stopped. They are private memories, like, man, we're performing copy on write. OK. So again, when you're doing your kernel Simon, you got to make sure you implement things this way. Okay.

218
00:28:25.740 --> 00:28:32.280
William Cheng: All right. Ah, so what if the later your program over here. So let's say that you are you know your progress the whole world program.

219
00:28:32.550 --> 00:28:37.800
William Cheng: Okay, so there would, you would need to do is that you need to print out the Hello World message onto the screen. So whereas hello world.

220
00:28:38.100 --> 00:28:46.770
William Cheng: Right, we saw before. In chapter three, your string constant are stored inside the data segment. So, pretty soon you actually perform an operation to read the data from, you know,

221
00:28:47.400 --> 00:28:54.840
William Cheng: To to to read a story for the data segment. So again, the same thing is going to happen right when you provide your transit translation over here V going to be

222
00:28:55.290 --> 00:28:59.040
William Cheng: The best go to the pre. Okay. All right. Anyway, so here when it comes to the data segment over here.

223
00:28:59.580 --> 00:29:10.020
William Cheng: We're going to be equal to zero you trappings are the Colonel, you're going to allocate a page over here. So if you are accessing the string constant over here the string cousin is still inside is sitting at a desk.

224
00:29:10.680 --> 00:29:17.880
William Cheng: Browser. Remember your executable file has tech segment you also data segment. So in this case, we also have to start a new operation over here.

225
00:29:18.000 --> 00:29:27.390
William Cheng: To read the data segment over here front of this into memory over here and there are currently has going to fall asleep insane web servers routine. We're going to wake up over here. And now we're gonna end up with this memory segment.

226
00:29:28.350 --> 00:29:35.910
William Cheng: That's what again this memory segment over here. What should we said the access right to be right. So the obvious need to be set equal to zero.

227
00:29:36.180 --> 00:29:41.730
William Cheng: The physical page number of your point of this page. But in this case, again, we are doing copy on write for the data.

228
00:29:42.300 --> 00:29:46.740
William Cheng: For the data segment. Okay. The data segment over here. It's a string constant at the beginning.

229
00:29:47.250 --> 00:29:56.940
William Cheng: Okay, but now since we copy them into memory, we need to perform copy on write. OK. So again, this particular page over here will be read only. So we're going to set the pace a bunch over here. There'll be read only.

230
00:29:57.330 --> 00:30:00.540
William Cheng: Since you are reading a string constant. It's okay to to share all you want.

231
00:30:00.990 --> 00:30:08.430
William Cheng: Okay, so therefore again. And this is what we're going to return back into your users Facebook when the user space program over here will try to read the stream constant again.

232
00:30:08.880 --> 00:30:17.010
William Cheng: Then this time you will be successful and very will continue to run. Okay, so we can see that three different memory segment behavior. Behavior is very different.

233
00:30:17.460 --> 00:30:21.750
William Cheng: For the text segment over here. You read the data, you know, from from this you have to wait for

234
00:30:21.990 --> 00:30:29.580
William Cheng: For the data and the BSS segment. At this point it look exactly the same, but later on if you write it to a global variable inside the segment over here.

235
00:30:29.760 --> 00:30:33.570
William Cheng: Again, you're going to end up a trappings that a kernel and the Colonel will realize that

236
00:30:33.840 --> 00:30:38.130
William Cheng: We're doing copy on write because this memory, the memory section over here will be private.

237
00:30:38.250 --> 00:30:48.660
William Cheng: So therefore, he needs to make a copy and right into the copy. So therefore, the string constant, even though they're inside the original page over here and now you make a copy. You can modify global variables inside a memory segment.

238
00:30:49.440 --> 00:30:56.430
William Cheng: That all right. And instead of stacks. I'm going over here again to behave very differently because the first time. Will you try to write data into the second segment.

239
00:30:56.550 --> 00:31:02.070
William Cheng: You are not reading data from the front. What is that you're actually writing data interest of the stack. So we hear you.

240
00:31:02.790 --> 00:31:10.500
William Cheng: You're going to allocate a page of zero you return back in your usual space and you said it to read only. And now the user space. But when is going to try to push something onto the stack again.

241
00:31:10.710 --> 00:31:19.260
William Cheng: You tried to write into the sex. I've managed to get a second pitfall. And then again you fix it by doing copy on write and then you reach them back to the user space program, one more time and this time you will do the right thing.

242
00:31:20.340 --> 00:31:24.510
William Cheng: OK. So again, three different memory segment that they actually perform very, very differently.

243
00:31:26.820 --> 00:31:31.650
William Cheng: All right, so. So remember, you know, our Colonel, it's actually pretty complicated.

244
00:31:32.010 --> 00:31:40.800
William Cheng: You know some of the memories segment over here are shared. If you fall call HR process the data structure a shared over here. So there are many, many user process many, you know,

245
00:31:41.310 --> 00:31:49.080
William Cheng: You know, maybe. I mean, I've got a safe spaces and every user process has a separate page table. But some of these pages table can point to the same page frame.

246
00:31:49.260 --> 00:31:58.650
William Cheng: Right, the data structure that you saw it over here, even though the way I've been describing them. They are they are physical pages over here. You can also think about a sense there's a one to one correspondence

247
00:31:58.830 --> 00:32:12.030
William Cheng: Between physical page and paste rent. These are also page frame objects. And then these patients object are being shared by multiple processes. Okay. So, therefore, instead of current over here that data structures lot more complicated because they're sharing going on that.

248
00:32:13.110 --> 00:32:14.430
William Cheng: All right. And over here is another

249
00:32:15.390 --> 00:32:20.970
William Cheng: Message over here to remind you in Colonel three, you need to make sure that every time. Will you go back into the user space.

250
00:32:21.150 --> 00:32:28.950
William Cheng: You make sure that the colonel is in a consistent day because once you go into the user space. You have no idea. When are you going to come back into the kernel.

251
00:32:29.370 --> 00:32:35.220
William Cheng: Okay, even come back into the kernel when another program is running or maybe you come in your kernel. We got a highway interrupt.

252
00:32:35.550 --> 00:32:43.560
William Cheng: Okay, you're going to make sure that the colonel is in a really, really, the state. Okay. Anything that's messed up inside the colonel next time he comes out a colonel, you might cause a colonel.

253
00:32:44.640 --> 00:32:48.960
William Cheng: Colonel page ball. So in that case, are you going to end up crashing or colonel. All right.

254
00:32:52.320 --> 00:33:05.010
William Cheng: Okay, so, so let's talk about the others page part again. So this is, you know, there are many ways to come into the kernel for baseball right B equals zero. You tried to write to a read only page will you traverse to the end of

255
00:33:06.120 --> 00:33:11.550
William Cheng: You know, a collision resolution chain instead of hash table again there are many, many ways companies that have carnal.

256
00:33:12.000 --> 00:33:22.770
William Cheng: The one example that we saw it over here. Be equal to zero that you how he comes out of it all. So again, these are the review of these five steps. I think I've gone through this step, many, many times, right, even in the earlier chapter

257
00:33:23.370 --> 00:33:31.050
William Cheng: So the reason I sort of keep doing this that because these are the things you have to implement your kernel three. Okay, so you're going to get very, very familiar with the process of a pitfall.

258
00:33:31.500 --> 00:33:33.330
William Cheng: Yeah. Alright, so we're going to start with the

259
00:33:33.630 --> 00:33:43.470
William Cheng: You know the trafficker you come inside the Colonel. What you do that you walked on the linear list of as region or VM area. Try to find out which one it belongs to. And then you try to sort of figure out how

260
00:33:43.710 --> 00:33:50.460
William Cheng: You know, what are some things repairable or not. If it turns out the virtual just like give you a page, fall, fall between the gaps of the VM area.

261
00:33:50.910 --> 00:33:59.340
William Cheng: Okay, well, in that case, you have to kill your user process because it means that the memory location or access doesn't really exist. For example, if you go to the memory location zero

262
00:33:59.730 --> 00:34:07.740
William Cheng: You're supposed to get a, you know, second digital. Do you get you get a paintball and this page all will turn into a segmentation fault or you kill us or Facebook. Yeah.

263
00:34:08.550 --> 00:34:17.640
William Cheng: Alright, so otherwise if it turns out that you can actually fix it what you will do is that you need to find a physical pay a physical page over here and what you do. So you ask the buddy system for physical page.

264
00:34:18.000 --> 00:34:24.360
William Cheng: And if it turns out you know the buddy system has run out of physical page, you need to write a page out into the backing store.

265
00:34:24.540 --> 00:34:31.380
William Cheng: This one you free up a page train and then you can actually copy data into it that. And then finally, what you do is that you perform the fetch operation.

266
00:34:31.590 --> 00:34:36.690
William Cheng: The fetches copying data from the does into memory and now you have a free page frame, you can actually copy the data into

267
00:34:36.930 --> 00:34:46.080
William Cheng: And then eventually, what you do is that without pushing is finished, next time when you Colonel throw wakes up, you're going to fix up all the colonel data this data structure and you go back into the user space program. Yeah.

268
00:34:47.010 --> 00:34:54.240
William Cheng: Alright, so in step two over here, you know, what you do is that when you try to find a free Patreon, we call the buddy system for you.

269
00:34:54.600 --> 00:35:04.800
William Cheng: To do instead of three over here where and how do you find it the easiest physical page route to the desk. Okay, so this is where you execute your page replacement policy that

270
00:35:07.170 --> 00:35:17.610
William Cheng: All right, so, so we're going to sort of again look at an example over here. When do you actually run out of memory that. So this example of your were three user program. I'm going to enter silly, silly example.

271
00:35:18.090 --> 00:35:24.600
William Cheng: Instead of physical memory over here, we're gonna we're sort of pretend that we have 10, you know, a 10 page frames.

272
00:35:24.840 --> 00:35:34.440
William Cheng: That are used by the user space program. Right. So again, I'm using the word page friend physical memory interchangeable eat right, so these are called P zero P of one, there are the pace ran

273
00:35:34.740 --> 00:35:40.170
William Cheng: Inside pastry. I'm over there is physical physical page number and this was a page number of points of physical memory.

274
00:35:40.920 --> 00:35:45.300
William Cheng: OK, so again we have 10 physical patient and they're usable by the user space program.

275
00:35:45.690 --> 00:35:53.310
William Cheng: The first application over here. Again, it has an address space. He has a page table instead of a stable over here, three entries over here is going to have equals two, one

276
00:35:53.580 --> 00:35:59.580
William Cheng: All the other ones will be equal to zero. So again, if you follow the pointer, he will show you that this one is being used by

277
00:35:59.850 --> 00:36:05.220
William Cheng: by by by process. Number one over here. This one is also used by process. Number one is also used by process. Number one,

278
00:36:05.610 --> 00:36:12.750
William Cheng: Process. Number two, has the address space has a page table over here for the entries over here or be used again you can follow the point of, you know,

279
00:36:13.110 --> 00:36:24.300
William Cheng: Find them process. Number three. Also use, you know, three page table entries over here to point the physical page table over here. So altogether. They point to 10 different pages and they're not sharing any of these these physical pages.

280
00:36:24.780 --> 00:36:30.180
William Cheng: Okay, so in this case all the physical memory over here are us. So what if we run a fourth program.

281
00:36:31.170 --> 00:36:36.630
William Cheng: Okay, if we run a fourth program, you know, so, so I'm going to fork over user process. We're going to share the page rank.

282
00:36:36.870 --> 00:36:43.290
William Cheng: And pretty soon we're going to run the exact same call where we go to the executives and Paul, we're going to wipe out the address space, build a new address base.

283
00:36:43.530 --> 00:36:47.970
William Cheng: And now we're going to, we're going to execute the celebrity and its opposite is going to get a baseball

284
00:36:48.360 --> 00:36:56.070
William Cheng: Okay, so in this case we're going to assume that's a different program. So therefore, we can I share any of the pace ran from the other user process. Yeah. So over here.

285
00:36:56.580 --> 00:37:04.740
William Cheng: You know, we run the fourth process over here and and in the beginning. Over here we doing on demand paging every page table entries over here is going to be equal to zero.

286
00:37:05.340 --> 00:37:15.240
William Cheng: So be equal to zero for every page every entry. So when we access this page that branches over here would come inside the colonel and now we ask the buddy system for PageRank devices. I said, I'm all out.

287
00:37:15.930 --> 00:37:22.560
William Cheng: Okay, so therefore, at this point, we need to execute the page. Page replacing policy so. So in this case, what should we do

288
00:37:23.490 --> 00:37:32.850
William Cheng: That we are inside the colonel be here. So if you look at this picture, there are two things you can do one thing is that you can walk down this list, find one of the page right over here and replace it.

289
00:37:33.960 --> 00:37:39.090
William Cheng: Okay, so one thing you can do is you can walk out this patient. I'm over here in the patient, you're going to store instead of some kind of a data structure.

290
00:37:39.270 --> 00:37:50.340
William Cheng: So you can walk down the data search for the PageRank one at a time and then you say, oh, you know, what do I want to replace this one we want to replace this one we want to replace this why you can find out one of them, and that will be your replacement policy.

291
00:37:50.730 --> 00:37:55.860
William Cheng: Okay, so, so again, next lecture, we're talking about requests and policy. Now, for some reason, you find out this one.

292
00:37:56.100 --> 00:38:05.400
William Cheng: Then the other thing that you can do that. You can actually go to the address page representation over here. Look at which one is being used over here right over here, you can see that the page table entries over here.

293
00:38:05.730 --> 00:38:15.330
William Cheng: They have these patients over here for equal to zero. Okay. So again, if you look at the virtual memory map over here the virtual memory. Now, which tells you which pays table entries over here. It's been said to one.

294
00:38:15.900 --> 00:38:22.290
William Cheng: Okay. So, by looking at the virtual memory map again. I joined the address space where you see the address patients, you think about the virtual memory map.

295
00:38:22.500 --> 00:38:28.770
William Cheng: By looking at the virtual memory map over here. I will see you know which memory segment over here is using which which page.

296
00:38:29.250 --> 00:38:34.800
William Cheng: OK, so maybe by by looking at a virtual memory segment over here. Maybe I will see that, oh, you are this particular process.

297
00:38:34.980 --> 00:38:44.820
William Cheng: Is not using the heap segment for some reason. So therefore I can follow the pointer over here and then try to say that, oh, this particular one action. Actually, I can actually read it out to the back end store.

298
00:38:46.200 --> 00:38:59.700
William Cheng: Okay, so again that's, again, that's part of the replacement policy, the replacement policy either scan things this way or they will need to scan the virtual memory map over here, all these processes in order for you to determine which you know which page trying to replace right

299
00:39:01.110 --> 00:39:07.800
William Cheng: All right, so let's say that that. So we're going to use the pay the page replacement policy.

300
00:39:08.160 --> 00:39:13.320
William Cheng: To execute that. So in this case, what to find out that piece patient. Number five is the one we need to swap out to the desk.

301
00:39:13.590 --> 00:39:24.000
William Cheng: Okay, so now what our current also has to do is to write this data out over here into the backing store. Okay, so again the terminology that we use that we're going to swap this particular page out into the back end store.

302
00:39:24.360 --> 00:39:34.500
William Cheng: There and this example. If this one over here is the heap side, man. So in this guy, they will go into the spa space. So again, depending on which object you're using those object knows where the back end story is

303
00:39:34.920 --> 00:39:38.760
William Cheng: So why is this data, you know, so, so, so, what it will do is they'll start at this operation.

304
00:39:39.030 --> 00:39:49.380
William Cheng: Transfer that data into the back in the store or Colonel three is gonna is gonna go to sleep. Eventually when the data is finished. What it will do is it will wake up your kernel threat and now you could also note that the data has been

305
00:39:51.900 --> 00:40:02.850
William Cheng: Has been copied into the back end store and what it will also do that is that when they perform this operation over here, what it needs to do is that it needs to make sure that the pace table entries over here is going to upset to invalid.

306
00:40:04.290 --> 00:40:07.920
William Cheng: Yeah, so this particular operation over here is that, you know,

307
00:40:09.810 --> 00:40:20.670
William Cheng: The is that is that we need to invalidate this particular entry inside of a stable entry and now the terminology that we use over here is going to be that we're going to assume that this particular page table entry from our virtual

308
00:40:21.810 --> 00:40:24.060
William Cheng: You know, for for our virtual memory map.

309
00:40:25.080 --> 00:40:34.140
William Cheng: Okay. So over here, what we need to do is that is that we need to say that this particular entries over here, no longer map to the state over here because this data is being trashed for you go to the back end store.

310
00:40:34.830 --> 00:40:45.510
William Cheng: Guys okay inside of the colonel data structure there should be a way for you to say that, you know, this one over here is on its way to the desk when this data is on its way to the, this is your application program allowed to modify the data right here.

311
00:40:46.650 --> 00:40:54.000
William Cheng: Okay. So, therefore, the answer is no, when you're when you're copying this patient will be here on to this, you got to make sure that nobody's working on this page right

312
00:40:54.960 --> 00:41:02.910
William Cheng: OK, so the way that we do this that we're going to remove this page for inform your address space. So this way we approve and try to access this particular patient was going to have a

313
00:41:03.420 --> 00:41:13.650
William Cheng: While you're going to get a page for even a trapeze. Not a colonel. Are you going to end up waiting inside the cardinal okay so therefore the terminology that we use is that this particular patient. I'm over here is going to become busy.

314
00:41:15.540 --> 00:41:18.600
William Cheng: Guy remember somebody talking about the busy paste rain instead of

315
00:41:18.990 --> 00:41:28.710
William Cheng: Instead of classical go girl, way ahead of Colonel three guys over here, this pretty good patient is on its way to the desk. So, therefore, this page right NOBODY'S ALLOWED TO TOUCH IT. WE'RE GOING TO

316
00:41:29.070 --> 00:41:37.830
William Cheng: Map this page frame from all the address space that are using this particular page, right. So in this case, there will be no accident, no user process will be using this PageRank.

317
00:41:38.520 --> 00:41:46.110
William Cheng: Okay, so we're going to set this patient and to be busy, meaning that it's going to this at this point. So our current of threads going to go to sleep. Eventually when the operation is done.

318
00:41:46.290 --> 00:41:50.670
William Cheng: We know that this patient over here has been written out to the database. And now this patient has gone

319
00:41:51.960 --> 00:41:57.600
William Cheng: Okay, so therefore you know of equal to zero again next time. Will you try to access this page over here, you're going to end up

320
00:41:58.290 --> 00:42:02.070
William Cheng: You know tribe inside operating system. You have to wait for it again. Okay.

321
00:42:02.850 --> 00:42:07.860
William Cheng: All right, so what does all this operation is done over here. Now you have a you have a free page rain.

322
00:42:08.040 --> 00:42:16.230
William Cheng: And now you're going to copy the data from what you're supposed to copy this group page. Right, right. So your current affair got woken up, you're gonna fix up all these Colonel data structures and say that

323
00:42:16.410 --> 00:42:22.680
William Cheng: This patient has really gone is no longer busy, but now I need to transfer data from another page into this, into this page right

324
00:42:23.010 --> 00:42:28.230
William Cheng: There. So, therefore, this patient now become free and then all these data storage over here is going to be consistent.

325
00:42:28.440 --> 00:42:36.360
William Cheng: And then what we will do over here is that we're going to start the next IO operation over here to transfer the data from the process. Number four, and then transfer that into memory.

326
00:42:36.840 --> 00:42:48.240
William Cheng: Okay, so we're going to start in another operation over here. We're going to set the pace room over here again too busy. SO THIS WAY NOBODY'S ALLOWED TO USE IT, including a process. Number four, because we're fixing the page frame over here for presses. Number four.

327
00:42:48.600 --> 00:42:55.200
William Cheng: Now, so this operation. Eventually, we'll get down again our Colonel threads going to go to sleep with the operations. Now our current author is going to get woken up

328
00:42:55.410 --> 00:43:06.810
William Cheng: When it's woken up, then we know that this page now has his data. So what it will do is it will fix up all the colonel data structure and also change the validity of it over here equals two, one, you know, said the three dot over here to

329
00:43:07.590 --> 00:43:14.460
William Cheng: Read Only over here. So again, we're going to also make this page rank no longer busy and now we can return it back into user space.

330
00:43:14.670 --> 00:43:25.920
William Cheng: You know, for the user base to provide the run and now our, our program over here. So in this example, it's a tech segment. So, therefore, what it will do is that it will start executing co using the data inside the space, right.

331
00:43:27.960 --> 00:43:38.730
William Cheng: Okay, so this is our sort of simple example of, you know, we run out of physical, you know, physical memory. And what would you do so again later on. And the next lecture, we're going to talk about the actual replacement policy. Yeah.

332
00:43:41.130 --> 00:43:42.480
William Cheng: Uh, alright.

333
00:43:47.550 --> 00:44:00.540
William Cheng: Okay, alright. So, so I guess this is sort of a good place to to to to stop. So next time we're going to talk about replacing policy, so that will be on Wednesday guys so, so, so, so Wednesday we're going to go. We're gonna go to lecture 23 okay