WEBVTT

1
00:00:03.149 --> 00:00:15.089
William Cheng: Okay, we're in the second part of lecture 22 and we're going to look at representative systems. So first, we're going to take a look at Linux. And then we're going to briefly.

2
00:00:15.780 --> 00:00:22.170
William Cheng: You know, look at windows because you know we don't we don't have the window source code so so anyways we're going to talk about Linux.

3
00:00:23.550 --> 00:00:38.880
William Cheng: Alright, so the, so this picture show you the Linux, x86 virtual memory layout. Right. So, you know, the, the, the smallest address is zero. The final address and the address space is a 32 bit address space right x86 meaning that

4
00:00:41.100 --> 00:00:49.440
William Cheng: I think x86 what we are so, so, so usually means 32 CPU. Right. So anyway, so look, the last address zero, F, F, F, F, F.

5
00:00:49.890 --> 00:00:57.360
William Cheng: F, F, F, F, right, because each letter represent forbids four times as you know 32 bits, right. So this is the last address

6
00:00:58.110 --> 00:01:06.060
William Cheng: For for Linux, the user space program can only use the first three gigabyte as here three gigabyte over here and the Colonel use one gigabyte.

7
00:01:06.720 --> 00:01:20.670
William Cheng: So the last possible user at virtual address is zero, x be F, F, F, F, F, F, and the first available Colonel virtual address is zero XE 0000000 okay

8
00:01:21.180 --> 00:01:31.710
William Cheng: So for this class, you got to get used to it before any class whenever you try to print an address, you should always use the hex notation. Okay so GDP is P slash x ray. If you want to print something

9
00:01:32.160 --> 00:01:40.170
William Cheng: Something you hex. Okay, you know, talking about addresses using decimal number just doesn't make sense. Okay, so make sure you you always use a, you know,

10
00:01:40.950 --> 00:01:46.350
William Cheng: You know heads notation right now because in excellent he can just see the bits that will help you a lot. Yeah.

11
00:01:46.740 --> 00:01:52.200
William Cheng: I don't know if you have tried that you warm up one asked you to put in the virtual address for, you know, for

12
00:01:52.950 --> 00:01:57.660
William Cheng: For list tests. Right. You should see that you know where you are printing local variables.

13
00:01:58.380 --> 00:02:08.070
William Cheng: You know function argument local variables, they are using the bottom part the outer space. You should see that the addresses are zero x BF something or something like that. So, so then the everything should make sense. Yeah.

14
00:02:08.520 --> 00:02:15.030
William Cheng: Alright, so the cardinal virtues right stuff I'm 0000000 you should notice that your kernel Simon

15
00:02:15.420 --> 00:02:24.120
William Cheng: What whenever you try to print an address of, you know, current Prague, or current third or something like that, you will see that the address is zero XE something that, again, you know, it kind of makes us

16
00:02:26.460 --> 00:02:33.660
William Cheng: Alright, so, so, so, you know, those on the left side is your virtual memory virtual memory. The address versus four gigabyte.

17
00:02:34.050 --> 00:02:39.750
William Cheng: The real physical memory. It depends on how much memory you have on your machine right could be four gigabyte could be 60 gigabytes.

18
00:02:40.380 --> 00:02:50.520
William Cheng: In my office. There is a netbook that has only one gigabytes of memory, right. So the idea here is that you need to map virtual addresses to physical address right we draw the picture of a memory map.

19
00:02:51.030 --> 00:03:00.660
William Cheng: So the virtual memory map. The purpose is to map, you know, virtual addresses somehow to keep to physical address. And also, that's how the colonel keep track of, you know, the how.

20
00:03:01.260 --> 00:03:08.370
William Cheng: The Colonel's will keep track of how the address space I implemented. Okay. And this is a very, very high level picture. There's a lot more detail right because we know that India.

21
00:03:08.790 --> 00:03:15.330
William Cheng: The virtual and the physical memory is managed by the buddy system, you know, and I said, right, right. So this is a very high level picture.

22
00:03:17.280 --> 00:03:28.890
William Cheng: All right, so for the user memory allocation, the user can really do in a physical memory allocation rapidly user, you know, everything is fake or so, therefore, you know, whatever you do in the user space program, they are all virtual memory allocation.

23
00:03:29.400 --> 00:03:39.960
William Cheng: Inside the Colonel, you can do virtual memory allocation. You can also do physical memory allocation. So when are you doing physical memory allocation. Okay, so, so the way should think about is that is that is that is that the buddy system was given

24
00:03:41.190 --> 00:03:46.770
William Cheng: You know all the physical memory to manage. So every time you call the buddy system you're allocating physical memory.

25
00:03:47.580 --> 00:03:53.640
William Cheng: Okay. Every time you call other kind of memory alligator we saw before, I guess last discussions, actually we saw came out.

26
00:03:54.390 --> 00:04:03.180
William Cheng: We also see the slab alligator. So anything you know allocate out of the slab or out of the other things. They are all virtual allocation. Okay, so for example if you tried to

27
00:04:04.530 --> 00:04:09.240
William Cheng: Guessing Colonel, you know, again, our wings kernel is kind of like the Linux kernel.

28
00:04:09.870 --> 00:04:17.970
William Cheng: So, you know, in the kernel one you call proc create right and then you call the slap alligator to allocate a process control block.

29
00:04:18.330 --> 00:04:28.530
William Cheng: So what kind of application is that while we allocate the process control blah, you, you, you use the slab alligator and the slap allocated just virtual allocation right because it doesn't allocate things one page at a time. Okay.

30
00:04:29.280 --> 00:04:38.940
William Cheng: So the real allocation attorneys are the kernel or over here it says when you get a pace fault right the way I described page fall is that you come into the kernel and the Colonel, as the buddy system for new page.

31
00:04:39.480 --> 00:04:44.130
William Cheng: Okay. So, therefore, you know, when you ask for new page you're doing physical allocation. All right. Okay.

32
00:04:45.390 --> 00:04:49.470
William Cheng: That's also pretty much anytime you allocate from buddy system you're doing you know the

33
00:04:49.950 --> 00:04:56.070
William Cheng: Real application. And also, I guess when you try to create a slab either the sub allocate it to beginnings, how to create an entire slap

34
00:04:56.370 --> 00:05:02.430
William Cheng: How to create an entire slap you ask the buddy system to say I want you know 16 pages that are contiguous or something like that.

35
00:05:02.670 --> 00:05:11.010
William Cheng: And then the buddy system so returned to you that big data structure. So at that point. Yeah, you're asking the buddy system to allocate memory. So your physical allocation. Okay.

36
00:05:13.170 --> 00:05:22.230
William Cheng: All right, so let's take a look at a very special case in Linux where you know you are. You have one gigabytes, a real memory. Okay, so. So in this case, it's just a matter

37
00:05:22.500 --> 00:05:36.180
William Cheng: Of the netbook in my office. He has exactly one gigabytes of physical memory. So in that case, what would you do, yeah. I mean, if you look at this picture over here, the user space virtual address is three gigabyte the kernel space virtual doesn't be as one gigabyte well one gigabyte.

38
00:05:37.230 --> 00:05:47.760
William Cheng: Code know virtual space and you have one gigabyte the physical memory, what it sounds really simple. I just map your every location in the kernel virtual address space, the physical the physical address

39
00:05:48.240 --> 00:06:01.320
William Cheng: Okay, so remember the first Colonel virtual address over here is a 00000000. So what I can do that. I can just take the colonel virtual address subtract 0000000 then I'll get a physical address

40
00:06:01.920 --> 00:06:08.850
William Cheng: Okay, so it's really simple. I can, I can map every Colonel virtual address directly to physical address by doing simply pointer math.

41
00:06:10.050 --> 00:06:17.970
William Cheng: Okay, so, so, so, so I could do that. So, so why do you want to do that. Well, this way. The Colonel can access physical memory easily. You just use a colonel virtual drives you subtract, you know,

42
00:06:18.450 --> 00:06:26.550
William Cheng: So if you try to access physical memory location. All you need to do is to add C 000 to it. Well, then the colonel can access that physical memory directly

43
00:06:27.960 --> 00:06:32.130
William Cheng: Okay, so, so, so, so if you can set up some sort of a mapping, then this will be done.

44
00:06:32.310 --> 00:06:43.290
William Cheng: But, but, you know, unfortunately, you know, things a little more complicated, you know. So conceptually. This can be done right. We can set up the pace table so that physical address is equal to the colonel virtual address minus 6000

45
00:06:43.800 --> 00:06:54.240
William Cheng: Okay, but this is not done, you know, in the real system for, you know, many reason because, you know, one of the reason is that because the physical memory is organized a little differently. You know, so, so therefore you won't do.

46
00:06:55.650 --> 00:07:04.350
William Cheng: You want to exactly like that now. Alright, so, but conceptually that can be done right, you can map every, you know, Colonel virtual address to physical address one for one

47
00:07:04.980 --> 00:07:15.390
William Cheng: Okay, because we have one gigabyte. So, Colonel virtual dress one gigabytes of physical memory, especially if you do that, the colonel can actually access, you know, any physical memory directly and easily.

48
00:07:16.260 --> 00:07:24.270
William Cheng: Okay, in reality, we're going to sort of go through some mapping. Right. So inside of Colonel page table, we need to manipulate things a little bit. And also remember. I don't know if you've noticed that

49
00:07:24.660 --> 00:07:29.190
William Cheng: In our current assignment in Phoenix, we only have 256 megabytes of memory.

50
00:07:30.120 --> 00:07:40.980
William Cheng: Okay, if you only have 256 megabytes of memory that we cannot use the entire one gigabytes of address space where we can only use 256 megabytes of that. But again, we can map the first 256 megabytes inside the colonel virtual

51
00:07:41.460 --> 00:07:49.830
William Cheng: Space and then and then map and direct, direct into physical memory. Okay, so again, conceptually, this can be done, even though the reality is a little more involved. Okay.

52
00:07:50.580 --> 00:07:54.870
William Cheng: All right, so, so, so, so this way, the operating system can read any physical memory.

53
00:07:55.320 --> 00:08:03.150
William Cheng: Or you know location easily by using some simple point or math or use some kernel data structure to keep track of this. So this way you can modify, you know,

54
00:08:03.750 --> 00:08:09.240
William Cheng: physical memory using a colonel virtual dress. Good. So remember the colonel cannot use physical address

55
00:08:09.960 --> 00:08:13.080
William Cheng: Right, if you try to use physical address it doesn't work right because everything has to

56
00:08:13.500 --> 00:08:22.440
William Cheng: Address Translation. So even the current okay you can only use virtual address. So if you want to access physical memory. You have to figure out what kind of address virtual Jesse, you have to use

57
00:08:22.920 --> 00:08:29.640
William Cheng: Now, so, so when you're doing your assignment three. Keep that in mind. Okay, there's no way for you to use physical address directly. Yeah.

58
00:08:32.010 --> 00:08:32.310
William Cheng: Okay.

59
00:08:34.260 --> 00:08:45.750
William Cheng: Alright, so. So what we try to allocate page rank for user space memory pages. So let's say that the you you you are using on demand paging and the kind of data on this into memory.

60
00:08:46.200 --> 00:08:52.110
William Cheng: So, for example, you're right. The user space over here we have texted me and web data plus B says we have the heat. We have the stocks.

61
00:08:52.620 --> 00:09:03.600
William Cheng: Etc. And when we get our first page fall. We're going to bring in one page over here from the data into memory. Right. Okay. So, in that case, you're going to ask about buddy system for page right so we're, you know, so yeah.

62
00:09:04.650 --> 00:09:12.840
William Cheng: The buddy system to use the allocate physical memory. So when we allocate a page, you know, from the buddy system, we end up allocating four kilobytes of physical memory right here.

63
00:09:13.260 --> 00:09:17.430
William Cheng: Okay, so again this four kilobytes memory over here is for this four kilobytes of

64
00:09:18.120 --> 00:09:24.090
William Cheng: Of the tech segment. Okay, so this four kilobytes. And this four kilobytes needs to be map.

65
00:09:24.390 --> 00:09:32.490
William Cheng: You know, using this email address map data structure we saw before that data structure look like right it's a linked list of as region. It's a Windows VM area.

66
00:09:32.940 --> 00:09:39.000
William Cheng: Okay. So using that data structure you map this four kilobytes to this four kilobytes of a physical address

67
00:09:39.480 --> 00:09:45.480
William Cheng: Okay, but we already said that this four kilobytes all address has also has a kernel virtual address

68
00:09:46.140 --> 00:09:56.190
William Cheng: Right, because of the colonel virtual dresses mapping one for one from the colonel address space to the physical address space. So this will kilobytes is also in the kernel virtual just right here for for this for kilobytes.

69
00:09:58.260 --> 00:10:06.720
William Cheng: Okay, so, so this is kind of weird right this four kilobytes over here has to virtual addresses one is inside the colonel virtual address the what

70
00:10:07.440 --> 00:10:18.000
William Cheng: Okay, so you know this four kilobytes. Everybody inside the four kilobytes of physical memory has to virtual addresses one in the user address range and the other one in the kernel address range.

71
00:10:20.130 --> 00:10:26.400
William Cheng: Okay, this four kilobytes. Now it has to virtual addresses one is right here. One is right here. So again, if you look at the offset over here.

72
00:10:26.610 --> 00:10:34.320
William Cheng: This will be the offset to this address and this will be the opposite is address. So every memory location here instead of four kilobytes has to virtual addresses. Okay.

73
00:10:35.310 --> 00:10:47.340
William Cheng: Does that make sense. Okay, so, so, so the idea here is that when the user as the colonel say hey you know transfer some data to one of my buffer the colonel will use the colonel virtual address to copy data into the user space buffer.

74
00:10:47.790 --> 00:10:55.080
William Cheng: OK, so the colonel needs to know that, given this user space virtual address what current or virtual just to use to fill data into this page.

75
00:10:55.410 --> 00:11:00.750
William Cheng: Right because India is the job of the Colonel, to make sure that this page has right data before you go into the user space.

76
00:11:01.530 --> 00:11:09.630
William Cheng: Okay, so therefore the user will ask the colonel to put data in here where you come into the Colonel. The Colonel will use the kernel virtual address the right data into, you know, this four kilobytes.

77
00:11:09.840 --> 00:11:15.600
William Cheng: And then when you return back to the user space, the user space program will use the user space virtual address to access the same memory location.

78
00:11:17.220 --> 00:11:18.630
William Cheng: Alright, so this is how things are done.

79
00:11:18.960 --> 00:11:26.010
William Cheng: Okay, because inside the Colonel, we want to use the colonel virtual address inside user space program, you want to use the reasons why you use a virtual address

80
00:11:26.220 --> 00:11:32.190
William Cheng: And they will map to exactly the same place, right. So, so this map over here will allow you to map things, you know, into the same memory location.

81
00:11:33.270 --> 00:11:39.120
William Cheng: Okay. All right. So, so the audiences and can you can read any users based on my location directly

82
00:11:39.300 --> 00:11:49.410
William Cheng: Also the organism. Also, you know, right into user space memory directly because the colonel is very powerful. He knows everything that's going on. So when you're inside a kernel, you know exactly how to convert

83
00:11:49.590 --> 00:11:56.430
William Cheng: This user space virtual address into a kernel space virtual address or the colonel can use to rewrite memory that's part of the user address face.

84
00:11:57.360 --> 00:12:02.430
William Cheng: Now, or so over here. It's kind of a silly comments that assuming assuming nights map. If

85
00:12:03.000 --> 00:12:10.830
William Cheng: If this one is not map. What does that mean that means is not map. For example, you try to use memory location 01 then the Colonel. Can I help you, because maybe location zero over here.

86
00:12:11.040 --> 00:12:16.530
William Cheng: Doesn't match any physical memory location and so therefore if you access it. You got to try and set the Colonel. The Colonel will kill your program.

87
00:12:17.580 --> 00:12:26.490
William Cheng: Okay, so, so if it turns out that it's map. What that means that the you know that you have set something up inside this virtual memory map data structure. So the colonel know what to do. Okay.

88
00:12:28.890 --> 00:12:40.110
William Cheng: All right, so when a user thread become a kernel threat. It's still the same process, right, because the other the thread belong to the same process again. This is for Linux right for other, you know, maybe there's some weird operating system. It doesn't really do that.

89
00:12:40.470 --> 00:12:44.820
William Cheng: But typically, when we think about a regular operating system like Windows and Linux at this is typically true

90
00:12:45.360 --> 00:12:56.760
William Cheng: When the user become a kernel threat. It's still in the same process and every process owner has only one page table rather remember you already done in Colonel wine right every time we create a trial process, you make a copy of the pace table.

91
00:12:57.210 --> 00:13:10.170
William Cheng: You know by calling some PT I can remember for the function. So anyways, every process has a page table right instead of process control blah, you pointed the page table. He pointed page directory, who is the page table. Yeah.

92
00:13:10.830 --> 00:13:20.070
William Cheng: So so so therefore we have multiple processes the page table. You know, when I look like this. Okay, but instead you know when you're inside the Colonel, you still use exactly the same page table.

93
00:13:20.340 --> 00:13:26.280
William Cheng: Right. I mean, this picture, the way I talked about is, is that you are the blue process his own pace table the pink processes. Don't page there but

94
00:13:26.490 --> 00:13:32.970
William Cheng: The Colonel also has his own page table. Well, you know, when you're inside a colonel, you're still the same process. So therefore you should share the same page table.

95
00:13:33.540 --> 00:13:38.820
William Cheng: Yeah, so therefore, for Linux and also for when x inside the kernel, they actually look like this.

96
00:13:39.270 --> 00:13:46.530
William Cheng: Okay, every page table over here. The beginning, three quarters of the page table corresponding to the first three gigabytes of data space.

97
00:13:46.980 --> 00:13:48.450
William Cheng: They belong to the user process.

98
00:13:48.900 --> 00:13:56.640
William Cheng: Okay, and then the bottom one quarter of the page table over here again after the colonel virtual address. So therefore, the bottom part of your I should color is green.

99
00:13:56.820 --> 00:14:00.660
William Cheng: Because only the colonel can perform address translation using the bottom portion of the page table.

100
00:14:01.020 --> 00:14:09.630
William Cheng: Okay, what is the user profile. I tried to perform other translation using bottom, you know, using about in part why should get you should get a, get a peaceful a tribe into the Colonel. The Colonel should, you should tell your program.

101
00:14:10.050 --> 00:14:15.390
William Cheng: Okay, because the user program can only use from address zero all the way to zero XP F, F, F, F.

102
00:14:16.620 --> 00:14:30.300
William Cheng: Okay. And inside the Colonel. The Colonel will use zero XE 000000. So therefore, the first entry is over here in the green region or here is to perform address translation from C 00000 to whatever the physical page that you have assigned to

103
00:14:31.230 --> 00:14:38.280
William Cheng: You guys but again we're going to use the page table to map Colonel pages into physical memory. We don't really just do, do, do you know pointer math.

104
00:14:38.790 --> 00:14:47.550
William Cheng: Okay, so we're going to still use it the Colonel. The Colonel page table over here to map one page at a time to map from the colonel virtual address the physical right just like what we do in the user program.

105
00:14:48.600 --> 00:14:56.160
William Cheng: Okay, and you already did that in colonel colonel one and now you're doing Colonel to you're right you're really doing that. Okay, except that you didn't rewrite the code.

106
00:14:56.610 --> 00:15:00.870
William Cheng: You know the Brown University people wrote the code. So, so that this is happening. Okay.

107
00:15:01.620 --> 00:15:09.060
William Cheng: All right, so for the paint process over here. Again, the first three quarter, you know, are doing either translation for the first three gigabyte the address base.

108
00:15:09.240 --> 00:15:18.750
William Cheng: They belong to the pink process and the bottom part over a year also belong to the Colonel. Okay. So over here, there's another process over, he has a page table where the top three quarter are blank.

109
00:15:19.470 --> 00:15:31.950
William Cheng: OK. So the top three quarter of this page table is blank. So what, why is it what this is a colonel only process. OK, I can only process, this, this is what doesn't go into user space program. So your current one and two. This is all you have.

110
00:15:33.090 --> 00:15:40.260
William Cheng: Okay, so, so, yeah. Our current or seven current one and two is completing that occur. No, there's no user space component. When you have user space component, it will look like this.

111
00:15:40.890 --> 00:15:47.850
William Cheng: Okay, so your current one and two. They look like this. So, what is the copper why. Why is it white right will be here's is everything being equal to zero in the top bar over here.

112
00:15:48.870 --> 00:15:56.400
William Cheng: Okay, so therefore, when we're running our current process when we perform address translation. We're going to use the only the bottom one quarter of the colonel page table.

113
00:15:57.450 --> 00:16:04.050
William Cheng: Okay, so again, is that a carnal when you try to you know access memory when you try to fetch economic structure. We're still using the page table.

114
00:16:04.650 --> 00:16:17.370
William Cheng: Okay. So, therefore, you know, starting with 00000 all the way to the last mile, you know, virtual address were using the bottom part of a stable. Okay, so you're you're already using that you just didn't know that this is what it looks like now.

115
00:16:20.550 --> 00:16:25.410
William Cheng: All right, so, so again we're going to continue the example we have one get our gigabytes of physical

116
00:16:26.400 --> 00:16:38.190
William Cheng: physical memory, also called noises real memory anywhere. Why user process over here. The other user process over here, right, when we allocate pages over here, we allocate them in the physical memory. So when we allocate a page for the blue process.

117
00:16:38.400 --> 00:16:51.930
William Cheng: This, you know, physical page over here has to virtual address one is inside the blue process, the user space address and the other one is also inside Colonel right because the kernel part over here will map of the physical memory. You know, one for one

118
00:16:52.650 --> 00:17:02.430
William Cheng: Okay, so if you think about the blue process and the paint process at the bottom part over here where the operating system after physical memory this part and this part, they are map identically to the physical memory.

119
00:17:03.600 --> 00:17:10.980
William Cheng: Okay, the top part over here that are mapped differently, right, because the topper over here for the blue process this virtual address will map to this physical memory.

120
00:17:11.190 --> 00:17:19.590
William Cheng: For the pink process exactly the same virtual as well. They have to map with different physical memory, right, because otherwise the pink cross that will be able to access the blue process memory. So, therefore, that won't work.

121
00:17:20.250 --> 00:17:25.140
William Cheng: OK. So again, we're doing on demand paging you know when you start running your program and then you started started

122
00:17:25.290 --> 00:17:32.640
William Cheng: Something good at baseball. We're going to ask the buddy system to allocate our Wiki pages. We're going to allocate a page for the proof process. And we're going to set up the the memory map.

123
00:17:32.790 --> 00:17:39.240
William Cheng: So on the left hand side over here says page table plus virtual memory map again you can sort of think about page table as part of the virtual memory map.

124
00:17:39.420 --> 00:17:47.130
William Cheng: Where you can sort of think about the page table a separate data structure. I mean, doesn't really matter how you think about it then. So we're going to use all these Colonel data structure to map.

125
00:17:47.670 --> 00:17:55.170
William Cheng: The user page or we can into physical memory over here again you know if it's user virtual address you sort of point to one place in the physical

126
00:17:55.590 --> 00:18:00.540
William Cheng: physical memory and over here for the paint process you're going to ask the buddy system to allocate another page right here.

127
00:18:00.720 --> 00:18:14.520
William Cheng: And this one is pointed to buy the paint process as not wanting to buy the blue process. Yeah. But when you're inside the Colonel. The Colonel has access to all you know all physical memory location guys are the Colonel's very powerful. He can he can he can manipulate add you know he

128
00:18:15.630 --> 00:18:20.160
William Cheng: He can manipulate memory for the blue process. It can also manipulate memory for the paint process.

129
00:18:20.640 --> 00:18:27.390
William Cheng: Okay, we also saw a picture inside in chapter one to say that once you're inside the Colonel. The colonel, it just one giant process.

130
00:18:28.290 --> 00:18:35.550
William Cheng: Right. So, therefore, you know, the colonel part over here, they're exactly the same, right. So once you come out of control. It doesn't really matter if you're in the blue blue process or in the pink process.

131
00:18:35.970 --> 00:18:39.660
William Cheng: Because the Colonel, sort of, you know, the Colonel. No, no, knows what's going on right

132
00:18:40.500 --> 00:18:47.190
William Cheng: Alright, so let's read through some of this when you switch from one process to the other, the iOS code and data stay exactly where you were.

133
00:18:48.030 --> 00:18:55.590
William Cheng: Okay, so you can think about your current one. When you switch from one kernel process to another Colonel process to the global variable stay exactly where they are.

134
00:18:56.370 --> 00:19:07.860
William Cheng: Was one of the global variable, right. So we use, you know, we use our product right correct Prague in Colonel one right the current running process when you switch from one program to the other. If you print the address of corporate lawyer exactly the same.

135
00:19:09.210 --> 00:19:16.650
William Cheng: Okay, so any of your global data structure your slap a locator, you know, all these things are they all say exactly the same thing. When we look at the process control block.

136
00:19:16.890 --> 00:19:28.740
William Cheng: The press control but doesn't change address when you move from one process to the other. Right. Why is that well because the bottom part of the page table over here. They're all map identically where you go from one process to the other process.

137
00:19:29.760 --> 00:19:38.670
William Cheng: Okay. So, okay, you didn't write the code. But when you you know in Colonel one when you create a new process, you basically you copy the page table from the parent process. So the child process.

138
00:19:39.630 --> 00:19:50.910
William Cheng: Okay, so therefore, when we, when you copy the page table while you copy the pointer. They pointed exactly the same place. So, therefore, what you switch on one process to the other one. Well, you know, the colonel aerospace stays exactly the same.

139
00:19:52.260 --> 00:19:56.670
William Cheng: So that's why we don't really need an address space representation is that a cardinal because when you set up the first address

140
00:19:56.970 --> 00:20:05.640
William Cheng: He will he said the first process correctly, which is press zero from that point on, all you have to do is to copy the page table and then the Colonel. The Colonel will map exactly the same.

141
00:20:06.390 --> 00:20:20.160
William Cheng: Now, so the bottom one quarter of the page table for all processes are map identically so so yeah so so so if you look at a pace table over here for these two processes. If you do a if you do a memory compare of the bottom entries over here. They are map exactly the same thing.

142
00:20:21.300 --> 00:20:36.720
William Cheng: Okay, so for Colonel only processes, only the bottom, you know, the bottom one quarter of the patient about our map all the top three quarter, they will always have equal to zero. They're not mapped right so the equal to zero means that they are invalid, so therefore they are now, Matt. Yeah.

143
00:20:38.400 --> 00:20:45.180
William Cheng: So, how to set up the top three quarter of the page table for the user process while. So in this case, that's where the address space representation comes up.

144
00:20:45.660 --> 00:20:51.840
William Cheng: Okay, so you're going to use the VM app data structure the virtual memory of the map data structure that's a linear lists of as region or VM area.

145
00:20:51.960 --> 00:21:04.590
William Cheng: Okay, so in order for you to implement the user address space. That's where you need to use the use of VMware data structure. Okay so VM app is only needed to manage the user portion or address address space in the kernel. You know, you copy the page tables everything set up already.

146
00:21:05.640 --> 00:21:05.910
William Cheng: Okay.

147
00:21:08.610 --> 00:21:13.800
William Cheng: Alright, so again, every physical address that's allocated to a user process. Right, so, so, so only physical

148
00:21:14.010 --> 00:21:20.130
William Cheng: Pages over here, allocate to us. But again, how do you do that right you call the buddy system, the advocate for kilobytes at a time.

149
00:21:20.310 --> 00:21:32.400
William Cheng: And that four kilobytes has to virtual addresses one is in the user's portion of the outer space. The other one is in the kernel portion of the outer space there. So, one for the colonel one for the user space which virtual address should the colonel us

150
00:21:33.810 --> 00:21:42.210
William Cheng: Okay, so. So again, this is, this is kind of a, you know, implementation issue when you're doing your kernel three, you got to watch out for that. So I have because if you're not very careful. You're going to give you don't you don't get a colonel paste fall

151
00:21:42.420 --> 00:21:50.070
William Cheng: I mean, you already see colonel colonel one and to rise. The Colonel pays for all that means that you're inside the colonel and you try to access. Use a portion of the address space.

152
00:21:51.270 --> 00:21:58.410
William Cheng: Okay, so instead of Colonel, why shouldn't you access the user portion where the outer space right for Colonel one and two is very obvious, right, if you look at a pace table over here.

153
00:21:58.680 --> 00:22:08.760
William Cheng: The bottom part of yours, map the top over here, equal to zero. So if you're inside the Colonel, you try to perform address translation using our user virtual address the equal to zero or you get a kernel panic.

154
00:22:10.050 --> 00:22:23.670
William Cheng: Okay. So, therefore, you know, we're inside a colonel colonel one and two. You are not allowed to use a user portion of the address base. If you use it that you get a kernel panic and then and then I guess when it stops running right

155
00:22:24.570 --> 00:22:35.100
William Cheng: There so inside the Colonel. So when you're running the code inside the colonel colonel virtual addresses right here. You should always use the colonel virtual address because you know that the colonel virtual address is always valid.

156
00:22:35.970 --> 00:22:47.640
William Cheng: Okay, so, so if you have access to the memory location over here, right, if you're inside the kernel issues, Colonel virtual just access memory. The reason you don't want to use user virtual address access memory. Is that what if this entry is over here for the patient will be equal to zero.

157
00:22:48.810 --> 00:22:56.850
William Cheng: Okay. And also, if you try to write as memory location of your, what is this one equal to zero. But, you know, the access right is read only. Well then that's in this case we don't get a kernel panic.

158
00:22:58.140 --> 00:23:08.070
William Cheng: Okay, so therefore, when you are, you know, when you're inside the Colonel, you should use the the colonel virtual address unless you know unless you know for sure that the user virtual address. You can use it.

159
00:23:09.360 --> 00:23:18.150
William Cheng: Okay. If you're not sure, you should cover the user virtual address into the cardinal virtues as and use the colonel virtual dress because the colonel virtual address is always safe to use by the Colonel.

160
00:23:19.260 --> 00:23:29.820
William Cheng: Okay, so, so, so one of the things that you needed encountering Colonel three is that whenever you get a user virtual address in here to find out what the corresponding Colonel virtual dresses. Okay, so that operation. You have to do it over and over and over again. Yeah.

161
00:23:31.470 --> 00:23:37.260
William Cheng: Alright, so again this is important point and tried to save you some trouble, you know, getting into Colonel three. Okay. So keep this in mind. Okay.

162
00:23:38.760 --> 00:23:45.210
William Cheng: All right, so when you try things out of Colonel, you're still the same thread and the same process, use the same page table is x86

163
00:23:45.750 --> 00:23:57.870
William Cheng: Instead of paper entry over here, it doesn't really look like the way we talked about before, by the way, we talked about before is that there's a validity bed. There is a reference there. There's a rabbit well so x86 CPU, you need to look up the x86 manual

164
00:23:58.650 --> 00:24:04.410
William Cheng: I don't think x86 has the reference bed. I also don't think that they have a modified bit there.

165
00:24:04.890 --> 00:24:14.430
William Cheng: So so so so inside x86 you know CPU manual this a inside the page table entry over here. There's also another bit to say whether it's user or Colonel

166
00:24:15.090 --> 00:24:22.770
William Cheng: Okay. So, so what you said on the page table over here. So again, this is the address pay. Here's the page table. The first three quarter over here or every page 10

167
00:24:23.040 --> 00:24:29.610
William Cheng: Page paper entry over here should say you equals two, one. Okay. That means that that page table entry over here is meant for the user program.

168
00:24:29.970 --> 00:24:36.930
William Cheng: Yeah. And then at the bottom. Over here you equal to zero, or you can also think about supervisor equal to one. So that means that that's being used by the Colonel.

169
00:24:37.470 --> 00:24:41.010
William Cheng: Okay. So I think in x86 they call Colonel they call the supervisor.

170
00:24:41.250 --> 00:24:53.640
William Cheng: I don't know why, why, you know, Intel does that. But anyway, that's terminology, they use. So the bottom portion of the the the the the the address is over here has user equal to zero and this is why when the user probiotics are the assets.

171
00:24:53.940 --> 00:24:58.470
William Cheng: Who would prefer address translation using the bottom one quarter of the page table, you're going to get

172
00:24:58.950 --> 00:25:04.500
William Cheng: You're gonna get a page for all right because they don't belong to the user page table. So therefore you trapped inside of Colonel

173
00:25:05.430 --> 00:25:09.510
William Cheng: Okay. So one of the reasons you might want to do this way is that maybe you can actually change the size of your

174
00:25:10.470 --> 00:25:15.630
William Cheng: Memory memory, memory. Memory mapping. So the user portion of address space can be smaller or bigger.

175
00:25:16.260 --> 00:25:27.900
William Cheng: Okay. But again, the typical either the way we should think about is that we think about Linux. The first three quarters of the page table. Have you equal to one and the last one quarter of the page. They both have equal zero, so therefore they are used by the carnal. Yeah.

176
00:25:29.250 --> 00:25:32.670
William Cheng: All right. The Colonel part of every page table or map identically.

177
00:25:33.330 --> 00:25:39.840
William Cheng: OK. So again, this part and and you know so so forth. The last part of the address space. So if you look at a page table over here. Here's a page table for the pink process.

178
00:25:40.080 --> 00:25:44.220
William Cheng: The bottom part will be here if you compare every memory location over here, they're exactly the same.

179
00:25:45.210 --> 00:25:57.720
William Cheng: Okay and here's one thing that's even more important. OK, so the colonel part of every page of our mapping, you know, map identically. If you have one gigabyte or less physical memory. Once this part is map, they will never change.

180
00:25:58.830 --> 00:26:00.000
William Cheng: Okay, so for Linux.

181
00:26:00.300 --> 00:26:12.450
William Cheng: Linux get started out to be a monolithic colonel. So once you bring the curve on this into memory and you set up the initial page table over here. So this oh so again process zero, you said on the bottom portion of the page table we hear

182
00:26:12.660 --> 00:26:19.380
William Cheng: From this point on, all you do is to copy that and you never modify, you know, the last part of your page table.

183
00:26:20.190 --> 00:26:33.510
William Cheng: Okay, so this is why in current one and two, you don't have to worry about it. Right. So are we next audiences and it's like the Linux operating system. Once you set up the bottom portion of the the the pace table, you never have to modify them because you know the IP.

184
00:26:34.530 --> 00:26:42.150
William Cheng: Because we have we have monolithic or no we, you know, why is the cursor Ronnie, you have everything that you have inside the Colonel. So therefore, the bottom part of your NEVER HAVE TO CHANGE.

185
00:26:43.740 --> 00:26:52.050
William Cheng: Okay, so this is why incarnate one and two, you don't have to worry about the page table, right, which is great. Okay. Because you really don't want to mess around with the page table when you're doing current one and two. Okay.

186
00:26:57.510 --> 00:27:04.410
William Cheng: All right, I'll vs as homework goes, you don't have to do the homework. So it's sort of a recommended recommended activity that you have to do.

187
00:27:05.370 --> 00:27:10.620
William Cheng: So the, the code to manage the page table is in Colonel M M stands for memory management.

188
00:27:11.130 --> 00:27:17.550
William Cheng: Paste it over here. See that that's all the code for the pace table. Okay. So the code over there is very convoluted.

189
00:27:17.790 --> 00:27:25.230
William Cheng: OK. So again, if you really want to know how exactly how the paperwork over here, spend five minutes and give up. Okay. The reason for that is that over this.

190
00:27:25.710 --> 00:27:43.650
William Cheng: The code inside this this particular this particular far what they're trying to do is that they try to try to present the, the two level page table extraction for the x86 up a table. Well guys, remember the x86 the Intel they use the multi level, you know, a page table.

191
00:27:45.060 --> 00:27:54.750
William Cheng: What is a call. Yeah, they think they call it the North multi level page table right so so so there's a page directly table. And then there's the the

192
00:27:55.560 --> 00:28:07.350
William Cheng: Second Level pay stable. So there's two levels like a tree data structure. Okay, so you don't really want to write that code, right. So when you try to use the page table, you want to use a very simple page level abstraction. So the CO right there. Give you that abstraction.

193
00:28:07.950 --> 00:28:13.170
William Cheng: Now, guys. So, therefore, if you want to understand how it works. Again, you should read the code, but the code over there. Again, it's very, very convoluted.

194
00:28:13.440 --> 00:28:20.820
William Cheng: Okay, so all you actually need to do is to find out you know inside this page, take what I see function, which are the function, you have to use to implement Colonel three

195
00:28:21.210 --> 00:28:28.830
William Cheng: Okay, so most of the function. You don't have to touch it, you need to, you know, so for example, there's one of the function over here called page table in it you initialize the first page table.

196
00:28:30.030 --> 00:28:33.660
William Cheng: Okay. So yeah, this is what process 00 you know you got to create a patient

197
00:28:33.840 --> 00:28:43.050
William Cheng: page table, you need to initialize a stable. So if you read the code over here, you try to sort of, again, don't try to sort of understand exactly what it does, but we chose to understand, pretty much, you know, approximate is doing.

198
00:28:43.350 --> 00:28:52.050
William Cheng: You will see that you know is that this co you will show that the colonel texts and the data and the BSS then they start a virtual address zero XE 00000

199
00:28:52.290 --> 00:29:00.510
William Cheng: Yeah, so therefore inside your kernel whenever you try to print an address of a function. Right. So he says, Therefore, he's got a kernel. If you're using a debugger, you can actually assess print

200
00:29:01.620 --> 00:29:02.760
William Cheng: proc create

201
00:29:04.200 --> 00:29:14.700
William Cheng: The appropriate. Right. So again, what's appropriate procreate is the address of that function. So he said, Print procreate. You will see the appropriate has has an address near zero x Cesar zero

202
00:29:15.150 --> 00:29:21.840
William Cheng: Okay, if you try to print all the colonel functions, you will see that they're all they're all very, very near the beginning part of the original virtual dress.

203
00:29:22.230 --> 00:29:32.970
William Cheng: Okay. And then you can also try to print the colonel global variables, right, because right after the tech segment over here is going to be the data segment. So if you do print in GDP, so you should print address of car proc

204
00:29:34.170 --> 00:29:39.270
William Cheng: Okay address of corporate, you will see that the corporate address is bigger than all the colonel functions.

205
00:29:39.720 --> 00:29:47.670
William Cheng: As well. Yeah, because the provider space over here the beginning part is tech stack that followed by the data plus BSS right so yeah they all follow the same rule. Okay. And then the rest of it as well.

206
00:29:47.880 --> 00:30:01.170
William Cheng: The rest of it, you know, is the Colonel, the heap and all that kind of stuff. Right. So, so yeah what the colonel will do is that if you read the PD code over here is that after the tech side we end the data plus BSS and then it comes to kernels paste directory table.

207
00:30:02.550 --> 00:30:08.460
William Cheng: Okay, so therefore, before we give the, the remaining the remaining part of the physical memory to the buddy system.

208
00:30:08.730 --> 00:30:11.520
William Cheng: What the colonel will do is that they will allocate a pace directory table.

209
00:30:11.790 --> 00:30:21.270
William Cheng: Guys are getting a patient record table we talked about in chapter seven at the beginning part or the page table there. It was four kilobytes long, you will notice that the colonel actually use a data structure that's eight kilobytes wall.

210
00:30:22.140 --> 00:30:33.390
William Cheng: Over as a look kind of weird so against very tricky code. The first four kilobyte is the actual page directory table that we talked about in the first part of chapter seven. The second four kilobytes over here is Colonel data structure.

211
00:30:35.010 --> 00:30:45.720
William Cheng: Guys so again the colonel data showed you over here is that, is that what the colonel used to keep track of what what can actually put into, you know, all you know what to kind of put into this page directory

212
00:30:46.800 --> 00:30:57.360
William Cheng: Okay, so for every page directory entries over here. The key. The colonel. Try to keep track of some other information. So again, they use the second kilobytes four kilobytes over here to keep track of every entry, they put into the data structure in the

213
00:30:57.750 --> 00:31:06.540
William Cheng: In the first four kilobytes. OK. So again, if you try to understand exactly how that works. It will take you a long time. Right. So my recommendation is that you know take five minutes and forget about it.

214
00:31:06.930 --> 00:31:14.820
William Cheng: Okay. And then what happened is that right after that eight kilobytes. The Colonel continue to allocate memory, it will allocate all the turtle page tables.

215
00:31:15.000 --> 00:31:18.660
William Cheng: The Colonel know exactly how many patients, went to the money's right because the Colonel. He knows everything.

216
00:31:18.870 --> 00:31:25.320
William Cheng: Yeah. So again, and some people are talking about, you know, how do you compiler kernel. You remember the compiler, the compiler is going to create a carnal virtual

217
00:31:25.500 --> 00:31:36.300
William Cheng: The Colonel executable, put it on the desk. So at the time when you load the Colonel, you're going to take that file unfolded into, you know, into kernel memory and now every part of your kernel is in physical memory already

218
00:31:37.170 --> 00:31:43.260
William Cheng: Okay, so therefore the colonel know exactly how much memory in it, and it also knows exactly how to set up the space table okay because

219
00:31:43.740 --> 00:31:47.760
William Cheng: You know, because at that time you copy all the kernel code into memory already knows exactly what it looks like.

220
00:31:48.270 --> 00:31:54.060
William Cheng: Okay, so it doesn't really need any more data structure because the code over there. Well, actually, you know, so tell you it will actually know exactly

221
00:31:54.510 --> 00:32:06.960
William Cheng: You know how many, how many, how many, how many Colonel peacehaven needs to be allocated so you will see the code over here will allocate all the colonel page table and then once it finished doing that it will give the rest of the physical memory and give it to the buddy system.

222
00:32:08.610 --> 00:32:16.680
William Cheng: Okay, so that's how the page table initialization work alright so so so again read this code of, you know, sort of, so quickly sort of get an idea of how the colonel colonel.

223
00:32:17.610 --> 00:32:22.620
William Cheng: allocate memory and once the rest, give it to the buddy system over here so you can see that the colonel has tech segment that data segment.

224
00:32:22.830 --> 00:32:33.360
William Cheng: And then it has the first you know page table instead of current. All right. There are set it up so that they point to each other or that kind of stuff. And then the rest of it to give it to the buddy system. And now the buddy system so allocating four kilobytes at a time.

225
00:32:34.800 --> 00:32:42.690
William Cheng: Okay. All right. So, so in this way you can understand the how the first page table. He said, I'm inside a kernel and from this point on, it just copy, copy, copy, right.

226
00:32:42.840 --> 00:32:53.790
William Cheng: And understand that the Colonel, just like the user process can only use virtual address it can no longer. You cannot, you cannot use any physical address. Okay, so everything is set up over here. It's also used to Colonel virtual address now.

227
00:32:54.450 --> 00:33:07.950
William Cheng: We need says only 256 kilobytes physical memory. So the actual Colonel virtual address. You can use a zero X prize from zero XE 000000 and the last memory location over here is going to be C F, F, F, F, F, F, F.

228
00:33:08.370 --> 00:33:16.560
William Cheng: Okay, so there's no zero XD there's zero x either zero x F because they'd be yeah they they they they go beyond the 256 megabytes of physical memory.

229
00:33:17.550 --> 00:33:26.400
William Cheng: Well as it began to take the colonel virtual address space, use the first 256 megabytes over here map one for one from the colonel virtual address space to the physical memory space.

230
00:33:27.450 --> 00:33:43.470
William Cheng: Yeah, so I think you know when you're in Phoenix, and there's also a colonel debugging command. Right. So I guess the command called Colonel proc there also. So, so, so, so you should do. You were in GDP, you should type Colonel help and he will tell you what all the Colonel.

231
00:33:44.520 --> 00:33:51.210
William Cheng: You know that the colonel commands are so when you're working on, Colonel three, there's a way to actually print out what

232
00:33:52.470 --> 00:33:53.610
William Cheng: What the page table look like

233
00:33:54.540 --> 00:34:04.650
William Cheng: Okay, so you can actually, you can examine the paper. So again. Don't pay too much attention to her because we don't really care about physical memory local locations right as long as the page table is set up correctly, you know, and they never changed again.

234
00:34:05.010 --> 00:34:14.880
William Cheng: Instead of Colonel. So therefore, we don't have to worry about it. Right. I mean, you have to worry about. You know what you allocate user. The user space pages, but the kernel space pages would awkward. Yeah.

235
00:34:17.250 --> 00:34:19.830
William Cheng: Alright, so you mean as when an application called read

236
00:34:20.370 --> 00:34:25.650
William Cheng: You know, with a buffer address right so so we made resist them call, you know, again, the recent orders. Look, I read

237
00:34:25.860 --> 00:34:34.710
William Cheng: Followed by file descriptor followed by buffer i and then followed by the size of the buffer size above right here. Okay, so this buffer over here is a user virtual address

238
00:34:35.640 --> 00:34:41.070
William Cheng: Right. I mean, if you run your use of this program, the buffer. You could be a local variable could be a local global variable.

239
00:34:41.550 --> 00:34:48.150
William Cheng: So in this case, it has a user space virtual dress somewhere over here, right. So again, sort of pretend that this virtual address is going to be my favorite address over here.

240
00:34:48.330 --> 00:34:55.170
William Cheng: 012345678 right your users virtual dress. Because this number is less than zero XP F, F, F, F, F, F, F, F. Now,

241
00:34:55.800 --> 00:35:02.850
William Cheng: So, so now this you just have a virtual dress zero x 12345678 is this bubble right here. Okay, maybe it's, you know,

242
00:35:03.210 --> 00:35:15.300
William Cheng: 124 24 bytes long maybe 200 finishes by someone doesn't really matter. So this one map to this physical address over here. So we know that inside the Colonel. There's also, you know, so let's say that this one is 1024 bytes long

243
00:35:15.840 --> 00:35:23.730
William Cheng: Right. So inside the code over here. What corner virtual address we have to use to to to to access to access this user space memory location.

244
00:35:24.690 --> 00:35:29.400
William Cheng: Okay, so, so again. Will you try things out the Colonel, right. You may receive mercy system call you try. These are the Colonel.

245
00:35:29.520 --> 00:35:36.720
William Cheng: So inside the Colonel, you're going to get all the function argument over here. So I mentioned before I let you go into the kernel, you're going to find the kernel version of the resistance call

246
00:35:37.290 --> 00:35:42.120
William Cheng: We, you know, before we say it's called K read right so now you know inside your Kronos could do we right

247
00:35:42.390 --> 00:35:45.000
William Cheng: So so inside corner. It's called do read. So instead we next

248
00:35:45.240 --> 00:35:53.490
William Cheng: The jury function over here again have exactly three arguments over here are the file descriptor over here. And then I think the argument over here. It's going to be a kernel virtual address

249
00:35:53.640 --> 00:36:01.410
William Cheng: So the question is, how do you actually start with a user space virtual jazz and cover the internal virtual dress. Okay, so. So inside your

250
00:36:01.950 --> 00:36:06.390
William Cheng: Your current assignment or there's another you know there's another Indian intermediate function costs. History

251
00:36:06.630 --> 00:36:17.250
William Cheng: As well as underscore, underscore, read. Okay, so, so that's the kernel version of the refund students that were you traveling so the Colonel, you're going to go to history since we also have exactly the same three arguments over here.

252
00:36:19.110 --> 00:36:28.890
William Cheng: Actually, I don't remember it has that same argument. So what's important. Over here is that inside situated over here, you're going to have the user space virtual dress and what you need to do is they need to convert that into the kernel space virtual address

253
00:36:29.730 --> 00:36:35.880
William Cheng: Okay, so in that case, what are we supposed to do, right. So again, you need to perform address translation and convert that into

254
00:36:36.450 --> 00:36:45.720
William Cheng: You know, can convert that into a physical address and maybe they do a reverse lookup for physical address. You want to find out what that will you know what the colonel virtual address to use in order for you.

255
00:36:46.770 --> 00:36:51.540
William Cheng: For you to find the corresponding current virtual dress. Yeah. Alright. So when you try. These are the current over here.

256
00:36:51.720 --> 00:36:59.730
William Cheng: You can actually look at this virtual rashes and why look at this virtual Josh is what is the Colonel virtual just that that I like I used to write it this memory location.

257
00:37:00.030 --> 00:37:13.110
William Cheng: There. So again, what you would do is that you have to go to your VM map. Yeah. Could you address great representation. It's a linear list of VM VM region. So it's a linear listed as region, you're going to use this kernel virtual address to find out which memory segment it belongs to

258
00:37:14.280 --> 00:37:20.550
William Cheng: Right. So again, the first one you need to find out which memory or segment belongs to you. So you take this virtual address you walk down that list of

259
00:37:20.880 --> 00:37:26.100
William Cheng: You know as region over here and find out which one it belongs to. In this example. So let's say that this one is the global variable.

260
00:37:26.760 --> 00:37:31.530
William Cheng: Okay, so this global variable. This one will be in the data in the data segment or in the PSS like man.

261
00:37:31.830 --> 00:37:36.810
William Cheng: If it turns out, this one's a local variable that you're going to find it. Instead of stagnant right it doesn't really matter what you find it. Okay.

262
00:37:36.990 --> 00:37:44.880
William Cheng: You're going to find the memory segment and then you need to sort of figure out, you know, what is kind of virtual address. So every memory segment is how how's the memory segment implemented.

263
00:37:45.360 --> 00:37:51.150
William Cheng: Right, so, um, every segment over here. So listen to your memory segment is you know your data segment is the pocket of eyes.

264
00:37:51.960 --> 00:37:56.400
William Cheng: Okay, or maybe we should use this number I say your memory. Second one over here is 10 kilobytes long

265
00:37:56.970 --> 00:38:04.770
William Cheng: OK. So again, when we try to implement a memory segment we're going to use pages. So if you have a tank kilobytes memory said, Man, how many pages, does it take to implement us

266
00:38:04.980 --> 00:38:12.990
William Cheng: What it's going to take you three to us different pages. The first page over here is four kilobytes long right and the second four kilobytes only implement the second kilobytes, and then

267
00:38:13.290 --> 00:38:21.150
William Cheng: The third four kilobytes over here. The first two kilobytes, the US to implement this memory sideman the last two kilobytes over here. There are waste of memory, their internal fragmentation.

268
00:38:22.320 --> 00:38:27.960
William Cheng: Okay, so therefore, in order for you to implement or 10 kilobytes memory segment you need three physical pages.

269
00:38:28.680 --> 00:38:37.050
William Cheng: Okay, so therefore, starting from your as region over here. You need to be able to find out, you know, given this virtual address over here which four kilobytes over here is the one that you need.

270
00:38:37.950 --> 00:38:47.220
William Cheng: Because how do you do that right okay you take this virtual address you divide them into two parts over here. Okay, the leading you know the the the the the the leading the leading

271
00:38:47.580 --> 00:38:53.940
William Cheng: 20 minutes over here will tell you which four kilobytes belong. Right, so it's hard enough to four kilobytes. Because what you do is that you take the leading to

272
00:38:54.150 --> 00:38:59.490
William Cheng: 20 minutes over here, you left shifted by 12 so you get a page aligned virtual address that will be the virtual just

273
00:38:59.970 --> 00:39:05.970
William Cheng: Sorry, that the, that will be the, the other the user space virtual address that corresponding to the beginning of every page.

274
00:39:06.360 --> 00:39:13.470
William Cheng: Right, so remember every page at the beginning, over here, and we'll call a page Atlanta address. So there's a user space virtual address over here that will point to a

275
00:39:13.980 --> 00:39:19.410
William Cheng: Particular page. So using the virtual a page number over here. You can find out which one. Oh, this one is belong to

276
00:39:19.890 --> 00:39:31.650
William Cheng: Okay, so maybe this one belongs to zero, x 12343 and the next one I'll be here is 012344 and the last one over here is zero, x 12345

277
00:39:32.130 --> 00:39:40.740
William Cheng: Okay, so therefore using this information over here. You said, oh, you know, this particular virtual address corresponding to the third, the third page inside this

278
00:39:41.490 --> 00:39:45.390
William Cheng: Inside this as region. Okay, so therefore you need to find the pastry and what we're here.

279
00:39:45.630 --> 00:39:55.230
William Cheng: Once you find the page rank. So remember the Patreon object has long information on it right one piece of information is tell you which physical page that actually points to, and the other information.

280
00:39:55.410 --> 00:40:10.200
William Cheng: That it tells you is that what cardinal virtues of address, you can use to write to this this particular page or to riff on this particular page. Okay. So using that information. The information is that a patriot. Now, you get the kernel version of this particular user space virtual dress.

281
00:40:11.850 --> 00:40:22.950
William Cheng: Alright, so again this is pretty convoluted. Right. So let me again try to describe this all over again. Right. You start with a kernel space virtual address, you get a page for you come into the kernel, you divide. There's two parts to this virtual guys into two parts.

282
00:40:23.190 --> 00:40:29.190
William Cheng: The first part over here is the virtual page number you try to find out which as region. It belongs to, once you find out

283
00:40:30.000 --> 00:40:32.640
William Cheng: As region as regions implement using multiple

284
00:40:32.970 --> 00:40:44.580
William Cheng: multiple pages, then again, he uses his virtual page number to find out whether it's in virtual page number. What number zero number one or number two Odyssey, which one it belongs to. And once you find out what the virtual the the

285
00:40:45.060 --> 00:40:57.480
William Cheng: The patient is you go to the pastry object. Find the colonel virtual address and then are you at the zero x 678 to have because that will be the offset into that page. And now you get a kernel space virtual dress.

286
00:40:58.410 --> 00:41:05.460
William Cheng: Or so that's how you convert a user finish virtual address so kernel space virtual address. Yeah. Alright. So you're going to get very familiar with this, the, the other step.

287
00:41:05.970 --> 00:41:13.560
William Cheng: When you start improving your kernel three. So once you start improving a kernel three so again come back to the slide and then review what I just said that hopefully everything will make more sense that

288
00:41:15.420 --> 00:41:23.550
William Cheng: Okay, so again that's a very important process. What if it turns out that you have more than one gigabytes of memory, because as it turns out, a little more complicated when you have more memory over here.

289
00:41:23.970 --> 00:41:30.120
William Cheng: So for Linux. What it will do is it will take us okay they will take the kernel space virtual just this one gigabyte. Okay.

290
00:41:30.330 --> 00:41:40.650
William Cheng: The first Seven, eighth of the one gigabyte. The first Seven, eighth or that one. Goodbye. They will map again one for one to physical memory. So the 78th of a one megabyte one gigabyte is 896 megabytes.

291
00:41:41.310 --> 00:41:47.850
William Cheng: OK. So again, this is a Seven, eighth of a gigabyte right here. Yeah. And then the rest of is is one eighth of a gigabyte.

292
00:41:48.390 --> 00:41:59.280
William Cheng: So what the, what the lenders will do is that the last one eighth of the gigabyte over here, there will use a special Colonel data structure and they will change the Colonel, they would change the colonel pay stable so that we can map to anywhere except physical

293
00:42:00.630 --> 00:42:02.730
William Cheng: They can map into anywhere is a physical memory.

294
00:42:03.960 --> 00:42:12.030
William Cheng: OK, so again inside. If you look at the page table for this user process. The first three quarter over here belong to the user program.

295
00:42:12.240 --> 00:42:21.150
William Cheng: The last one quarter we have, we don't have the Colonel. The Colonel is going to take this part of the page table entries over here, divide them into the first seven eighth of this one.

296
00:42:21.390 --> 00:42:28.530
William Cheng: They will map or two to do to the first you know 156 megabytes of the physical memory and this map will never change.

297
00:42:29.100 --> 00:42:38.070
William Cheng: Okay, the last part over here inside the colonel pay stable over here the last part over here. The Colonel will change it all the time so that the last part of your can map to any you know

298
00:42:40.260 --> 00:42:54.150
William Cheng: Any physical pages. Okay so increase in Linux. This one's called a map or the colonel map. So the colonel Matt can be adjusted point here. The point here why anywhere. So this way. The Colonel can can be able to access any part of his memory. Yeah.

299
00:42:55.500 --> 00:43:06.030
William Cheng: Alright, so we're here when the colonel tried to access different memory over here, they need to change the bottom, you know, one quarter one eighth of the one quarter of the table in order to access any part of the physical memory.

300
00:43:07.200 --> 00:43:18.930
William Cheng: Okay so so lineage have different name for different part of the physical memory over here. So, so, so, so, so, so, so let's go to the next page over here so so Linux. What it will do is that when you have more than

301
00:43:20.100 --> 00:43:25.170
William Cheng: Will we have more than one gigabytes of memory. So there's actually have a physical memory allocation scheme over here.

302
00:43:25.590 --> 00:43:31.620
William Cheng: The first part of your physical memory over here is known as the DMA zone. Okay. So then we'll take the physical memory of your divided into three zones.

303
00:43:31.890 --> 00:43:41.940
William Cheng: The first part over here called the Amazon, the Amazon is the memory location go from zero to somewhere less than, you know, zero x 0000 F, F, F, F, F, F, F, F.

304
00:43:42.930 --> 00:43:54.810
William Cheng: 0000 and there's six at follow at. Okay, so this is no as DMA zone. The reason for that is a Linux was meant to run on Intel the Intel architecture was very, very old. So in the good old days.

305
00:43:55.230 --> 00:43:59.220
William Cheng: Some of the DMA devices. They can only use 24 bit a physical address

306
00:43:59.760 --> 00:44:06.330
William Cheng: Okay, so therefore, when they transfer data into physical memory. They can only transfer data into the, the other the beginning part of the physical address

307
00:44:06.660 --> 00:44:16.080
William Cheng: Okay. So, therefore, you know, Linux, basically follow you know will follow windows or doors. The make sure that the beginning part over here that the memory is only used by device drivers.

308
00:44:16.650 --> 00:44:24.840
William Cheng: Okay, so therefore this is used by the call it the Amazon is for data transfer from the desk into memory or so in our case, typical whatever it is that we transfer data from the distant memory.

309
00:44:25.020 --> 00:44:29.580
William Cheng: The Colonel will need to copy this data from the DMA zone into other parts is that Colonel data structure.

310
00:44:30.510 --> 00:44:35.250
William Cheng: Okay, so therefore, again, you know, this is a well inside, Colonel. You have to a lot of these copy. Yeah.

311
00:44:35.970 --> 00:44:44.940
William Cheng: Alright so beyond the DNA is over here is called a normal zone. So the normal zone go from the end of the DMA zone, all the way to the end of the Andhra 96 megabytes.

312
00:44:45.120 --> 00:44:51.960
William Cheng: Okay, so this is one called a normal zone, it's normal zone for the Colonel. So all the operating system data structure must reside in this range.

313
00:44:53.160 --> 00:45:00.960
William Cheng: Okay. So in a way, you know, the colonel data storage has to fit inside of Seven, eighth of a gigabyte minus, you know, the size of the other the DNS. Oh.

314
00:45:01.350 --> 00:45:11.610
William Cheng: Yeah. So in a way, you know, when you are using only one gigabytes of memory. The Colonel can actually use one gigabyte of memory where you have more physical memory. The Colonel actually can only use seven eight gigabytes of memory.

315
00:45:12.690 --> 00:45:16.650
William Cheng: Okay, so the corrections become smaller. Okay, you know, we have actually more physical memory now.

316
00:45:17.340 --> 00:45:25.350
William Cheng: The user pages may result in this range right so against up to the Colonel, the Linux kernel decide whether to to allow the user space program user

317
00:45:25.740 --> 00:45:34.410
William Cheng: The data structure to allocate your pages over here, not the rest of it, starting from, you know, 896 megabyte all the way to end a physical memory. This is no as high memes. Oh.

318
00:45:34.950 --> 00:45:39.390
William Cheng: So this one is strictly used for user. The user pages. Okay. So, therefore, when you're

319
00:45:40.350 --> 00:45:50.520
William Cheng: You know when you run out of kernel memory. You can really use you use this memory over here, this user does memory, you know, beyond the first seven eighth of a gigabyte. They are strictly reserved for user pages.

320
00:45:50.880 --> 00:46:02.520
William Cheng: Okay, so, so you know when the user allocated page over here and the Colonel wants to access to the memory location over here. The Colonel have to adjust a map to point to it and then currently use it. Okay, so there is a little more complicated. We have more memory. Okay.

321
00:46:04.740 --> 00:46:14.250
William Cheng: All right. Um, what else is here so so so inside Linux, the way that's that they manage all these pages frame is that

322
00:46:14.790 --> 00:46:22.140
William Cheng: So the buddy system is the one that keeps you up for the free page rank. Right. So over here, this is the free patient data structure, they are implemented using the buddy system.

323
00:46:22.620 --> 00:46:28.800
William Cheng: So, so let me somehow they decided to do them to to implement, you know, one buddy scissor for each of these zones.

324
00:46:29.100 --> 00:46:35.940
William Cheng: Okay, so there's one buddy system for the DMA zone. There's one buddies. So basically what it will do is that they will actually separate the mount memory allocation for all the different zones.

325
00:46:36.210 --> 00:46:45.210
William Cheng: OK, so the DMA don't get their own memory alligator. The normal don't get their own memory alligator and the high meme zone, get their own me alligator. Okay, it's over here that's three memory alligator over here.

326
00:46:45.660 --> 00:46:55.830
William Cheng: So so so for every zone over here, you started on your page frame is inside the buddy system over here. These are the three pages. I told them in the blue car. So again, there's color has nothing to do with the blue process of the pink process.

327
00:46:56.190 --> 00:47:07.200
William Cheng: The blue. The blue part over here means that they're free. And then the pink over here. That means that you're allocating. Yeah. So when you ask the buddy system for a page. Now we allocate one page over here we're going to remove them from the free list.

328
00:47:07.890 --> 00:47:13.020
William Cheng: Even though I said free list that we're using the buddy system. So again, you know, once a free list. It's the buddy system.

329
00:47:13.530 --> 00:47:22.890
William Cheng: Okay, we're gonna we're going to move this page ram over here into the active page less. So the actor page lists over here is going to be a data structure that keep track of all the allocated pages.

330
00:47:23.490 --> 00:47:33.480
William Cheng: Okay. They also have the inactive page there. So what are the like energy pages over here the active pages over here are the ones that are picked up by the by the clock algorithm that's not recently used

331
00:47:34.470 --> 00:47:37.590
William Cheng: That so so so so remember what the clock out with them do right because

332
00:47:38.160 --> 00:47:45.240
William Cheng: What it does is that what it will do is that it will go through the active pace ram over here. Pick out patients that are not recently us. And then what it would do is I write

333
00:47:45.660 --> 00:47:51.480
William Cheng: A mapping and find the address space and then move them into in in occupation list, right. So now these pages are going to enact page lists.

334
00:47:51.690 --> 00:48:01.860
William Cheng: And then you can actually combine all the entire page list together because this is kind of slow, you can only write white page one page at a time. And now that is what it will do is that they were ready and occupation as one at a time.

335
00:48:02.430 --> 00:48:11.190
William Cheng: You know, one, one of the time you know onto the desk when they finished reading them up. Back to this. What it will do is that it will return the space frame over here. We turn into the buddy system.

336
00:48:12.180 --> 00:48:24.150
William Cheng: Okay, so in a way you can sort of think about this as recycling. Right. So once we decided, one of the patient. I'm over here. It's not recently us, we added to the inactive patients for recycling eventually when I finished recycling, it will return it back to the free patrons.

337
00:48:25.230 --> 00:48:26.700
William Cheng: Okay, so, so, so that

338
00:48:27.600 --> 00:48:35.130
William Cheng: I guess that's what next size over here about so every zone patient my divided into three different lessons over here, there is a free list again that are managed by the buddy system over here.

339
00:48:35.310 --> 00:48:47.040
William Cheng: They're inactive patron. These are the ones that are picked up by the o'clock hour them as now recently us. And also, you know, so when you take a look at that, you know, if this particular patient is not recently used, but it has not been modified

340
00:48:48.030 --> 00:48:54.300
William Cheng: There. So if a patient has not been modified, that means that this data on this page rank is exactly the same as the data on the desk.

341
00:48:55.410 --> 00:49:03.450
William Cheng: So remember, instead of a single entry over here. We said there's a big called modify right so if the patient has been modified. That means that the data is different from the data. So therefore, we have the right to this.

342
00:49:03.780 --> 00:49:08.700
William Cheng: Right. What is the page frame over here has not been modified. Well, in that case, we can return it to the buddy system right away.

343
00:49:10.110 --> 00:49:17.310
William Cheng: Okay, so again the cargo them over here. I need to be a little smart right when it looked at a pastry and say, oh, this patient is not modify. So, therefore I'm going to directly return to the buddy system.

344
00:49:17.550 --> 00:49:26.820
William Cheng: As it turns out that if that patient is modify the terminology that we use over here is that this patient is dirty or this person is modify. Well, then we need to schedule it to be written out to the desk.

345
00:49:27.450 --> 00:49:36.270
William Cheng: Okay. So in this case, what we need to do over here is that what if it's getting written out to the days we are now we shouldn't allow the application to modify the this particular

346
00:49:36.480 --> 00:49:43.800
William Cheng: This particular page, right. So what we need to do is that we need to mark this and I think I mentioned in the previous lecture, we're going to mark this page rank as busy.

347
00:49:44.130 --> 00:49:48.300
William Cheng: Okay, we also need to map it from all the processes are sharing the space rapes

348
00:49:48.870 --> 00:49:59.850
William Cheng: Guys again. Well, how do you map it for all the outer space over here, right. So what we do is that we need to go to the page table entry over there. And I said, we go to zero. So, this way when those program a while we were sushi another program to

349
00:50:00.810 --> 00:50:05.700
William Cheng: Run because because our current where I got my my fall asleep when the other three I tried to access that page over here.

350
00:50:05.910 --> 00:50:11.220
William Cheng: These equal to zero. And what it will do is it will come into the kernel when they come into the kernel when it find this page rank.

351
00:50:11.460 --> 00:50:22.740
William Cheng: Using the outward. And as I mentioned before, will eventually find this page right, it needs to see if this paper is busy or not. Okay, if this patient is busy. That means that the disc is using this page. So therefore, they have to wait.

352
00:50:23.940 --> 00:50:29.580
William Cheng: Okay, so if a patient is busy. That means that this might be using. So, of course, you know, when you. I mean, if you look at this picture over here.

353
00:50:29.820 --> 00:50:37.050
William Cheng: There are many pages over here. There are busy, only one of them is speeding being actively right now to do this all the other ones that are busy, but you are not allowed to use it.

354
00:50:38.010 --> 00:50:46.800
William Cheng: Okay, so therefore, when you try things out the current all we have when you're ready to use a page, right, you better make sure that it's not busy. Because if it's if it's busy, you start using it. What then the data can be modified.

355
00:50:48.150 --> 00:50:56.550
William Cheng: There. So therefore, when you when you look up a patient, and the patient handler is a pay for him is busy. You must wait until that this operation is finished, you must you must go to sleep.

356
00:50:57.510 --> 00:51:05.550
William Cheng: Okay, so eventually when this page is written out to the desk and now there's pay. Yeah. So when a page get written other this the terminology we use as these other patient become clean

357
00:51:06.330 --> 00:51:09.660
William Cheng: Right, because that now the patient has exactly the same data, you know, as

358
00:51:09.990 --> 00:51:19.050
William Cheng: The patient has exactly the same data as as the date on this. So now we need to modify the colonel data starts to say now. Now, this will be more patient, and now it's clean. It also is no longer busy.

359
00:51:19.440 --> 00:51:26.190
William Cheng: Yeah, so if you go back to the previous page over here guys over here is a lesson that this is the patient that you're that you're actually writing out to the desk.

360
00:51:26.400 --> 00:51:35.340
William Cheng: So, this one says busy equals one right now. You finished writing out to the desk and now you know that there's a kernel threads waiting for this page rank when this guy. You should not return to the buddy system.

361
00:51:35.520 --> 00:51:41.490
William Cheng: You should actually return it to the occupation list. Now, why do you have to do that because now this page is recently used

362
00:51:42.480 --> 00:51:51.210
William Cheng: Right, because you have what you have a colonel throughout waiting. Waiting to access, you know, accidents pace ran so therefore they are most recently reference. So you need to return it back to the occupation list.

363
00:51:52.080 --> 00:51:56.790
William Cheng: Okay, so he said, in reality, the page list management over here is a little more complicated, right.

364
00:51:57.240 --> 00:52:07.830
William Cheng: Because there are these things that gets involved. Yeah. And finally, the occupation list. These are the one that I picked up by the clock. Our them as recently us. Yeah. Alright, so I'm going to review the studio. This is the single one more time.

365
00:52:08.610 --> 00:52:14.610
William Cheng: Yeah. When you ask the buddy system to allocate a PageRank right you allocate a page over here. Are you moving into actually pays less

366
00:52:14.820 --> 00:52:18.000
William Cheng: And then the page are demons going to scan the occupation less over here.

367
00:52:18.210 --> 00:52:23.550
William Cheng: And find out which one is recently used, which is not recently used if they are recently years they stay in the advocates list.

368
00:52:23.730 --> 00:52:28.440
William Cheng: If they are not recently used what it will do is that you will you will remove it from the occupation. Yes.

369
00:52:28.650 --> 00:52:37.530
William Cheng: And you will add it to the inactive page list over here. You will also a map this page friend from all the address spaces that are using this PageRank rats because because they actually the patient can be shared.

370
00:52:38.130 --> 00:52:42.690
William Cheng: So so so once you add, you know, added to the occupation is over here. You're going to set the busy.

371
00:52:42.990 --> 00:52:53.550
William Cheng: Busy, busy, busy to equal one. So now all the, you know, all the inactive page list over here. So all the patient. And over here, they are busy guy. So now, are the desk. What this will do is that they will write this down this data to the

372
00:52:54.180 --> 00:52:56.790
William Cheng: To the, to this one at a time, then

373
00:52:57.150 --> 00:53:04.230
William Cheng: Eventually when a. So, so, so, so, you know, as there have been written out to this if another user process tried to access the patron.

374
00:53:04.410 --> 00:53:12.120
William Cheng: That's in the inactive page lists, since we have already a map on the address space. And now the current author will fall asleep, waiting for the patient to because I'm busy.

375
00:53:12.510 --> 00:53:18.060
William Cheng: Now, so I was that eventually when this patient. I'm over here is going to be written after this, this patient has been cleaned

376
00:53:18.300 --> 00:53:24.570
William Cheng: We're gonna, you know, we're going to say that this page RAM is no longer dirty. Now it's clean. It also busy going to be go to zero.

377
00:53:24.720 --> 00:53:33.600
William Cheng: And then we're going to see if there's any Colonel threat waiting for this piece rain is there is then we return it back to the actor page less if there's no kernels are waiting for it then would return it back to that buddy system.

378
00:53:35.130 --> 00:53:42.030
William Cheng: Alright, so this is what you also need to do you know what you're doing your kernel three to manage all these patients. Yeah. All right, so

379
00:53:42.690 --> 00:53:50.820
William Cheng: You know, I'm actually exactly where I were supposed to be compared to previous semester. So, therefore I'm going to stop you know lecture 22 so niche and 23

380
00:53:51.390 --> 00:53:57.420
William Cheng: Is going to be given next Monday. So lecture 23 I'm gonna give you everything that you need to know to finish your kernel three. Okay.