WEBVTT

1
00:00:12.240 --> 00:00:16.680
William Cheng: Right let's continue with the second part of lecture 19

2
00:00:18.090 --> 00:00:25.890
William Cheng: All right, so last time. We're here, we're talking about the two problem with a basic to level page table with first we're going to look at the solution.

3
00:00:26.310 --> 00:00:34.530
William Cheng: For shrinking the size of the page table. We're going to start out with four megabytes a page table and we're going to make it as simple as small as possible.

4
00:00:34.860 --> 00:00:42.330
William Cheng: And then again, there's a tight space time trade off things going to get worse for performance for a while. But India. We're going to fix all the problems.

5
00:00:43.920 --> 00:00:52.590
William Cheng: Alright, so the first one is the paid side pay sample sizes four megabytes. That's really too big. This is the general pay a scaling problem.

6
00:00:53.130 --> 00:01:02.310
William Cheng: Computer Science. People love scaling problem, what are the typical solution typical solution is to, you know, have a hierarchy or have a hash table right

7
00:01:02.820 --> 00:01:11.820
William Cheng: So, so, so we have an array of 1 million entries. So how to implement that. If you think about the pace table. Most of the pace table entries are actually

8
00:01:12.300 --> 00:01:18.630
William Cheng: Completely not used right if you have you have you have 4 million entry. If you have a small program that we saw before.

9
00:01:19.170 --> 00:01:29.070
William Cheng: I guess the you know the world from chapter four. We have three pages with tech segment one page but data plus BSS there's no heat and stabbed would need a few pages.

10
00:01:30.000 --> 00:01:36.450
William Cheng: So in the end, you know, so, so, so, you know, if it's small program. Maybe the stack. We only need now one of four kilobytes page.

11
00:01:36.960 --> 00:01:49.920
William Cheng: So in that case, we only we need a 20 kilobytes or we only need five pages. But in the end, if we allocate you know 1 million entries as a total waste of space that so that means that if you look at the table over here.

12
00:01:50.280 --> 00:01:56.940
William Cheng: You know, the, you know, the first four entries over here V is equal to one and the last one will be of equal to one and everything else equal to zero.

13
00:01:57.480 --> 00:02:06.630
William Cheng: Okay, so that's a complete waste of space, right. So we need to, you know, either contrast this out, or do something so typically again that this is the array data structure, it's a it's a linear list.

14
00:02:07.020 --> 00:02:11.040
William Cheng: Well, so again mean can think about array as a list. So I so again that's that's a linear data structure.

15
00:02:11.820 --> 00:02:17.460
William Cheng: The better data strategy will be using hash table or using a tree. So we're going to sort of take a look at both kind of solution.

16
00:02:18.300 --> 00:02:28.500
William Cheng: There's also some kind of a weird solutions over here. It's called a virtual linear paste table. Nobody use that anymore. So we're going to sort of briefly sort of talk about you know how to do that. Yeah.

17
00:02:28.890 --> 00:02:32.880
William Cheng: Alright, so again, the goal here is to shrink the size. The first Pro, you know,

18
00:02:33.810 --> 00:02:38.850
William Cheng: Solution over here is that, you know, instead of divided virtual address into two parts. Why don't we do it into three parts.

19
00:02:39.150 --> 00:02:45.480
William Cheng: Okay, so we're going to take the virtual page number split them into, you know, two parts. So this is called, it's called page segmentation.

20
00:02:46.110 --> 00:02:55.740
William Cheng: In this case, we have the leading four bits and that will be a segment. Sort of. Sort of a segment number and then followed by the middle power we hear is going to be the virtual page number

21
00:02:56.070 --> 00:03:02.190
William Cheng: So in this case, you know, if only have four bits of segment number. That means that we're going to end up with 422 to four. That means 16 segments.

22
00:03:02.490 --> 00:03:12.660
William Cheng: So over here, we're going to end up with a segment table the segment table only has 60 entry from zero to 15 right so the segment number over here will give an array index into the segment.

23
00:03:12.930 --> 00:03:16.380
William Cheng: You know table over here and he's had a segment table over here. We're going to have

24
00:03:16.950 --> 00:03:27.600
William Cheng: A segment table entry. So what does the second table entry look like, Well, you look exactly the same as page table entry. So as a validity bed. He has to read and write been and stuff like that. And also it has

25
00:03:28.200 --> 00:03:33.090
William Cheng: It has a physical page number, right. So if you take the physical page number you left shifted by 12 so

26
00:03:33.330 --> 00:03:44.610
William Cheng: That will give you a second level page table that will give you the base address of the second page of the local page table. So therefore, the second level page they bought the address is always, you know, the first memory location is always page line.

27
00:03:44.910 --> 00:03:54.690
William Cheng: Then, and then so they will give you the second level page table. So all we need to take the middle 16 bit over here, use that as an array back. So in this case, to, to the 16th at 64,000

28
00:03:54.900 --> 00:04:07.260
William Cheng: So the second level, the yellow page table over here is 64,000 entries. When is the middle part over here access. One of the, the, the, the page table entry over here. So again, the page table and you over here will look exactly the same as the previous page table.

29
00:04:07.890 --> 00:04:14.160
William Cheng: But the page table entry. So again, there's a validity bit. There is a rewrite bed and then there's a physical page number

30
00:04:14.370 --> 00:04:23.340
William Cheng: If you had the physical page number you left shift it by topic that will give you the base address or physical page and you add offset into it, or that again that you can perform better translation.

31
00:04:24.000 --> 00:04:30.120
William Cheng: Yeah. So in a way, using this Margaret, this is the general scheme is called multi level, you know, page table.

32
00:04:30.450 --> 00:04:33.540
William Cheng: So we're basically we're going to perform address translation twice.

33
00:04:33.780 --> 00:04:43.920
William Cheng: The first time we provider translation. We're gonna get we're gonna get a base address of a second level page table and then we're going to use that to perform another address translation and now we're going to get the base address

34
00:04:44.100 --> 00:04:52.200
William Cheng: For physical page where we can add the offset to it. Okay, so this is done a long time ago, you know, because in the end, it doesn't really say too much memory.

35
00:04:52.710 --> 00:05:04.890
William Cheng: The, you know, the middle page table over here. Each one of them has 64,000 entry each one of them is for baseball. So, so each one of them is 256 250 kilobytes.

36
00:05:05.820 --> 00:05:16.770
William Cheng: That. And then, you know, the first part over here. There's 60 entries over here. So if you think about a small program has a tech segment we're going to use the first entry B equals two, one. The second NGO will be good data plus BSS

37
00:05:17.100 --> 00:05:23.580
William Cheng: V also equals two, one and the last one over here in the stat be equal to one, all the other 13 entries over here.

38
00:05:24.000 --> 00:05:30.060
William Cheng: LDL venture over here and have equal to zero, then that means that the the second level page table. We don't need to have three

39
00:05:30.480 --> 00:05:39.390
William Cheng: Right. So, this way we will save some memory, each one of them is 256 kilobytes. Over here, we multiply that by three, we're going to end up with a little less than

40
00:05:39.720 --> 00:05:50.310
William Cheng: It's going to be three quarters of a of a megabytes of memory now. So in that case, but what we what we did is that we start out with four megabytes of memory when we cut it down into three quarters of

41
00:05:51.540 --> 00:06:02.010
William Cheng: You know, three quarters of a megabyte I guess examples over here, this it if you have for memory segment. If you actually have a heap segment. Well, in that case, what we're going to end up with four of these second level page table.

42
00:06:02.250 --> 00:06:11.700
William Cheng: And each one of them is a quarter of a megabyte. So for them, it's going to be one megabyte well guys I in that case we cut down our says okay, the size really depends on you know

43
00:06:12.240 --> 00:06:20.430
William Cheng: How many segments that you have. So we can cut it down from four megabytes to one megabyte if we only have, you know, if we

44
00:06:21.840 --> 00:06:31.590
William Cheng: If we don't have for memory segment. So yeah, how can you get more memory segment. Again, if you have memory map. Are you going to end up with more segment. If he and now you're at 12 memory map out into it. We're going to end up

45
00:06:31.830 --> 00:06:42.660
William Cheng: The total page tables as over here. It's going to go back 24444 megabyte. Okay, so, so, so if you use up your entire virtual address space, of course, you're going to end up with four megabytes of

46
00:06:43.680 --> 00:06:44.190
William Cheng: A

47
00:06:45.360 --> 00:06:53.040
William Cheng: page table. So what are we really trying to say, well, because most of the time, you don't use up your entire address space. Okay, so when so so if you look at most of the program.

48
00:06:53.250 --> 00:07:01.530
William Cheng: Most of the program. The part of the address but they use are very, very small. So what we need to do is that we need to save the page table, the size over here when the program is small.

49
00:07:01.980 --> 00:07:13.590
William Cheng: Okay. All right. So, so again, so for regular program has four has for memory segment. So in the end, you cut you cut down the page that was asked from four megabytes to one megabyte that's really not a big deal. Yeah.

50
00:07:14.940 --> 00:07:19.080
William Cheng: Alright, the next one we're going to see over here is that this is actually one.us by Intel

51
00:07:19.380 --> 00:07:28.470
William Cheng: So Intel called this the form map at a stable or multi level page tables. But again, I still use that term already, you take the virtual address you cut them into three parts.

52
00:07:28.740 --> 00:07:36.630
William Cheng: So in this case, the first part of your is 10 bits long. SECOND PART OF YEARS 10 years old. So basically we take that 28 bit address we chop it into two parts right down the middle.

53
00:07:37.230 --> 00:07:48.750
William Cheng: There. So the first part over here. We're going to call it the page directly address. And so, sorry. The first 10 bit will give you a page directory number. So the table that he will access know as a page directory table.

54
00:07:49.050 --> 00:07:59.130
William Cheng: There as in this case, how many entries are there while they're 10 beers to to the tenants equal to, you know, 1024 entries over here go from 012 all the way to 1023

55
00:08:00.000 --> 00:08:05.400
William Cheng: There. So again, when you perform address translation, you're going to take the pace directly number over here.

56
00:08:05.670 --> 00:08:13.110
William Cheng: Use that as an array index and that will give you a pace directory entry. What does the page directory entry look like look exactly the same as a page table n g

57
00:08:13.320 --> 00:08:18.600
William Cheng: He has validity bit over here. It has, you know, return right over here. And it also has the physical page number

58
00:08:18.780 --> 00:08:24.690
William Cheng: You take the physical page number you left shifted by 12 beds and then you got to get a base address of a second level page table.

59
00:08:24.900 --> 00:08:32.580
William Cheng: Use the middle 10 beers over here to address it. So in this case, how big is this page table why it's 10 bits use templates access. So therefore, again,

60
00:08:32.790 --> 00:08:42.090
William Cheng: They also go from zero all the way to 1023 so there's you know 1024 entries over here and again use the middle part over here as array index.

61
00:08:42.300 --> 00:08:50.520
William Cheng: That will give you a page table entry, you check the BB check the reader access if everything checks out. You take the physical page number over here again you left shifted by 12 beds.

62
00:08:50.760 --> 00:08:56.700
William Cheng: And that will give you a page align address for a physical page you add the offset to into it and you get a memory location.

63
00:08:57.960 --> 00:09:00.690
William Cheng: Okay, so. So this guy's got you are still doing

64
00:09:01.110 --> 00:09:09.150
William Cheng: You know memory address translation twice right the first time, is that you take the pace directory number over here that will give you the base address of the second level paste table.

65
00:09:09.300 --> 00:09:14.820
William Cheng: And then he performs better translation and one more time. And then finally, you're going to get get get get get the physical address

66
00:09:15.540 --> 00:09:18.450
William Cheng: That. So in this case, what is the size of the pace directory table.

67
00:09:18.810 --> 00:09:28.140
William Cheng: Or the patriarchy table over here. It has 1024 entry each Angie over here is four bytes long so this data structure is for four kilobytes. Right. What about the page table over here.

68
00:09:28.350 --> 00:09:36.630
William Cheng: It's also has 20 1024 entries over here. So also, this is four kilobytes. Everything is four kilobytes. This is why we like four kilobytes so much

69
00:09:37.710 --> 00:09:41.760
William Cheng: Okay, because in this case, you know, every one of these data structure exactly four kilobytes.

70
00:09:42.210 --> 00:09:53.520
William Cheng: So if we go back to our small example what we have, you know, all the for memory segments over here. Why, in that case, you know, the first entry is over here V is equal to one. The second entry, are we here for the data. Data SPSS people. So one

71
00:09:53.730 --> 00:10:00.840
William Cheng: And that's why it's going to be the heat the equal to one and the last one over here vehicles to one or the ones in the middle. Over here equals to zero.

72
00:10:01.230 --> 00:10:14.700
William Cheng: Right. So again, the pace directory table has 1024 entry only four of them are being used all the other entries be equal to zero. So they're not use this means that the yellow page table we are, how many do we have, but we only have four of them were

73
00:10:16.320 --> 00:10:27.960
William Cheng: All right, so what is the minimum pays table overhead Razzle guy. There's an entry here. There's an entry here and there's entry in the end. And it's a minimum. So, in a program. We don't really have to have a heap segment right we need to take segment.

74
00:10:28.170 --> 00:10:33.540
William Cheng: We need the data segment, especially if you make any system call you need the air number that goes into the data plus VSS admin.

75
00:10:33.780 --> 00:10:46.200
William Cheng: You also need to use a stack. So in that case, we're going to end up only with three yellow page table over here and one purple pay say but this one is the page directory table. So the minimum page table over. So what do I call a particular overhead.

76
00:10:46.860 --> 00:10:53.400
William Cheng: Well, the reason is an overhead is that be, because if we don't do address translation. We don't need this data structure at all.

77
00:10:54.150 --> 00:11:05.730
William Cheng: Okay, so if we only allocate physical memory, which is really bad idea. You know, but but it but if that's what we, if that's what we do, then we don't need a stable at all. So therefore, the entire page table data structure as an overhead.

78
00:11:06.390 --> 00:11:15.840
William Cheng: Okay. So in this case, when you have only three memories that men are the tax data plus b S as in the stack segment. In this case, we have four kilobytes over here. And then we have three of these page table.

79
00:11:16.140 --> 00:11:20.700
William Cheng: Each one of them is four kilobyte the entire page table over here is going to be 16 kilobytes.

80
00:11:21.600 --> 00:11:31.980
William Cheng: Then, so therefore, for tip for for smallest program that you can write typically the page table appears 16 kilobyte so we just cut the page tables. I started with four megabytes into 16 kilobyte

81
00:11:32.430 --> 00:11:40.470
William Cheng: Right. So that's pretty good night. So that's, you know, we would we say almost 1000 times but it'd be nice if we say 250

82
00:11:40.980 --> 00:11:51.720
William Cheng: Scale is 250 to one. So that's pretty good guys or unless we have a really large programs in that case we can end up with a lot of people in the middle. Before typically were very small program we saved a lot of memory.

83
00:11:52.470 --> 00:12:01.260
William Cheng: Okay, so this is Intel and that's why you know like Intel because every process over here. You only have to use you know 1616 kilobyte serve up a stable right

84
00:12:01.560 --> 00:12:04.410
William Cheng: So think about the program that you have written for one more point and warm up to

85
00:12:05.340 --> 00:12:15.690
William Cheng: That I mean for those program, they will use very, very few entries over here in the pace directory table. I mean, unless you are you know your input is really large. In that case, or he will be very big. So in that case you need multiple pieces.

86
00:12:15.990 --> 00:12:25.500
William Cheng: Entry over here, but typically for small program. We only need one page. They weren't real here. Okay, so in that case we do save a lot of memory. Yeah. Alright, so this is Intel

87
00:12:26.580 --> 00:12:36.570
William Cheng: So the main job of this particular program we cut 1644 megabytes a page stable a stable size down to 16 kilobytes of page table, but now when we perform address translation.

88
00:12:37.170 --> 00:12:48.780
William Cheng: How many times is the EMEA has to go across the bus, right, in order for you to get this page directory entry. It's sitting across the bus, right, because this is the page directory table the page directory table is city inside of you know

89
00:12:49.860 --> 00:12:57.150
William Cheng: Sending across the memory. But, you know, the good part over here, this is four kilobytes. Right, so therefore we allocate one page. This page will be used for

90
00:12:57.570 --> 00:13:06.030
William Cheng: You know this page will be used for a page directory table. So you know that the base address over here would be page line because when you ask the buddy system for page.

91
00:13:06.540 --> 00:13:17.250
William Cheng: The address has to be patient line. Yeah, so this is sitting across the, you know, assisted and crossing the bus. So therefore, when you try to read a page directory table. Your MMU has to go across the bus ones and then

92
00:13:17.580 --> 00:13:21.750
William Cheng: When you try to promote other translation again inside the menu and then

93
00:13:22.110 --> 00:13:25.500
William Cheng: At some point, you're going to need the page table entry again that's sitting from across the bus.

94
00:13:25.740 --> 00:13:33.660
William Cheng: This page is also four kilobytes. Again, you need to go across the bus and then this case, you will get the page table n g. So, so the menu has got caught the bus twice.

95
00:13:33.960 --> 00:13:40.050
William Cheng: And India where you figure out what I find a physical address and now you have to go to the bus. The third time to read and write that memory location.

96
00:13:40.680 --> 00:13:47.130
William Cheng: OK. So again, you know, without address translation, you'd go to the bus only once. And now with address translation using a

97
00:13:47.400 --> 00:13:59.430
William Cheng: You know, multi level paste table, you have to go to the bus. A total of three times. Okay, so that's 200% overhead. So again, even though you save a lot of memory. So in the end you speed is going to be a lot worse as a good space time trade off.

98
00:14:01.440 --> 00:14:12.480
William Cheng: Alright us for x86 up a CPU. I mentioned before, you know, there's a car three register inside car through registers store the physical address of the corresponding entry inside your process control, blah.

99
00:14:12.960 --> 00:14:17.280
William Cheng: Again, our Colonel three is our process control blah, we have something called a p underscore

100
00:14:17.580 --> 00:14:28.020
William Cheng: Page dirt. Right. So now you know exactly what it is is pager. This one is a page directory table. So this is the virtual address, you know, for this page directory table.

101
00:14:28.320 --> 00:14:31.500
William Cheng: Whereas, oh yeah, it's a colonel virtual address why do you need a colonel virtual address

102
00:14:31.710 --> 00:14:39.240
William Cheng: Because the colonel is the one that need to set up this page table entries over here. So therefore, the colonel needs a virtual address to access this page table. Okay.

103
00:14:39.420 --> 00:14:44.010
William Cheng: But when you put this virtual address inside of CPU, you need a physical address why do you need a physical address

104
00:14:44.310 --> 00:14:50.250
William Cheng: Because you need the physical address of the pace directory entry in order for it to for you to go across the bus to read a page table entry.

105
00:14:50.460 --> 00:14:58.080
William Cheng: So therefore you need the physical address of the first memory location for the person, the pace directory table so right before you put the

106
00:14:58.800 --> 00:15:01.500
William Cheng: Page dirt value inside your process control block.

107
00:15:01.770 --> 00:15:13.980
William Cheng: Into the car three register, you have to first convert that into a physical address. Yeah. How do you do that you ask the page frame object to perform a for look up. So this way you can convert a virtual address to a physical address

108
00:15:14.400 --> 00:15:26.970
William Cheng: OK. So again, look at your kernel three co grab for see our three over here in lowercase and look to see exactly how this is not okay. And it also show you if you start with a virtual address how you convert that into a physical address

109
00:15:27.990 --> 00:15:31.650
William Cheng: Alright, because later on in some other part of Colonel, maybe you have to do the same thing. Yeah.

110
00:15:32.970 --> 00:15:44.130
William Cheng: Alright, so again in the x86 CPU. The car three register contain physical address of the base address of the page directory table of the current running process. So every time when you switch to a different process.

111
00:15:44.370 --> 00:15:52.980
William Cheng: You need to change the car through register or you need to convert pager into a physical address before you put it inside a car to register. Okay, what about the second level page table over here.

112
00:15:53.310 --> 00:16:04.140
William Cheng: Do I need another register. You don't need another register, because the physical page number over here instead of paste directory entry if you left shifted by 12 minutes, you get a physical address of a second directory page table.

113
00:16:04.530 --> 00:16:13.140
William Cheng: Okay, sorry, you get a second level page table over here, you get a physical address. So therefore, all you need is so, so, so in this case the enemy will register only require

114
00:16:13.620 --> 00:16:19.290
William Cheng: This again. So, so in this case the MMU register, there's only one register, and that's the CIC register.

115
00:16:20.220 --> 00:16:29.490
William Cheng: Okay, so all you need to store the physical address of the page directory table and then the rest. You can actually, you know, you do pointer Matthew access memory location you get all the information. Yeah.

116
00:16:32.850 --> 00:16:41.790
William Cheng: Alright, so the next, you know, your current assignment runs on the x86 CPU. So I just said that. You know, this is done Intel right all the CRC register.

117
00:16:42.390 --> 00:16:45.870
William Cheng: You know, do you like to program, you know, your page table this way.

118
00:16:46.590 --> 00:16:52.590
William Cheng: Okay. As it turns out, it's going to be a lot of work. Right. And also, you don't need to know exactly how to set all these paper Angie over here correctly.

119
00:16:53.310 --> 00:17:07.440
William Cheng: So luckily the Brown University. He did all the work for you. So what he would do is that even though the x86 CPUs. Use a multi level page table the abstraction that the Brown University people bill for you is a two level page table.

120
00:17:08.460 --> 00:17:14.700
William Cheng: Okay. So, therefore, if you want to set a particular page table entries over here. What do you need. All you need is a virtual patient number

121
00:17:15.060 --> 00:17:20.820
William Cheng: Right, if you give a virtual page number using the functional interface that are built for you by the Brown University people

122
00:17:21.240 --> 00:17:31.650
William Cheng: Okay, or everything will get taken care of. Right. So the idea here is that the way, just think about is that, yeah. Inside, how're abstraction layer, they will convert this virtual page number into all these, you know,

123
00:17:32.190 --> 00:17:38.130
William Cheng: Hardware dependent par And then what it will do is that it will set the corresponding location inside the two levels of page table.

124
00:17:38.850 --> 00:17:40.920
William Cheng: Now, so when you're getting your kernel to

125
00:17:41.100 --> 00:17:54.450
William Cheng: All you need to do is, so you need to learn the the programming abstraction, which is basically assuming that you have a two level page table right the actual implementation over here knows that if you're dealing with x86 CPU, it will break that into multiple page tables.

126
00:17:54.870 --> 00:18:05.670
William Cheng: So this way. Would you should pay attention to is to look at the functional interface and figure out which function that you need to use. So all the function, you need to deal with this as a start with us with PT, so P stands for

127
00:18:05.940 --> 00:18:17.040
William Cheng: Paste a ball. So all the pace table function started with PT underscore followed by a you know a bunch of operation. So you need to find out which one you need to use and you can assume that all the other functions are perfect.

128
00:18:17.580 --> 00:18:26.190
William Cheng: Yeah, or so this way, your life is going to be easier because you know here is the abstraction which is much, much easier to deal with than the actual multi level page table.

129
00:18:31.530 --> 00:18:39.060
William Cheng: All right, we're going to briefly take a look at linear paste table. So linear paste. It was a little weird. It's used by Digital Equipment core again Digital Equipment core

130
00:18:39.270 --> 00:18:45.750
William Cheng: They were very successful with your mini computers and today we don't have many computers anymore. So therefore, we're going to sort of briefly talk about it.

131
00:18:46.350 --> 00:18:54.330
William Cheng: Yeah so. So what's weird about the linear paste a ball over here is that, you know, so, so this picture look familiar. You take the virtual drives you divided into three parts.

132
00:18:54.600 --> 00:19:03.210
William Cheng: In the good old days, the page pages or smaller, as in this case, the offset is only nine minutes long. So, therefore, a page is only half a kilobytes. Right, so I guess we talked about

133
00:19:03.450 --> 00:19:10.260
William Cheng: You know, I guess, older Unix. They have half a kilo by page. Well here's, here's one example of why it's only half of kilobytes.

134
00:19:10.950 --> 00:19:26.070
William Cheng: So the remaining part over here 32 minus nine equals 23 beds are the 23rd base is divided into two parts. The first part over here is no space. So since the only two beds. They can only have, you know, four different spaces 00011011

135
00:19:26.790 --> 00:19:32.790
William Cheng: Yeah, so the idea here is that, you know, when you use the first. So, so this is, again, this is look like a multi level page table.

136
00:19:32.970 --> 00:19:40.020
William Cheng: Use the first two bids over here that will give you the second level page table. And then the second level page there but you to perform one address translation. One more time.

137
00:19:40.230 --> 00:19:45.900
William Cheng: It will give you the physical address. Yeah. So what's funny about the Digital Equipment Corp design over here is that

138
00:19:46.080 --> 00:19:55.050
William Cheng: The page table over here in the middle we hear it doesnt sit in the physical address space, it actually sit in the virtual address space yet. So, therefore, if you look at one of the entries over here.

139
00:19:55.560 --> 00:20:01.290
William Cheng: So they potentially that can have four different page table, but in reality they only using three page table.

140
00:20:01.560 --> 00:20:05.100
William Cheng: Yeah, so they use the one in the 00 space to use the one zero white space.

141
00:20:05.310 --> 00:20:15.960
William Cheng: They also use the one in the one zero space, but the one, the one zero space is going to be a physical paste table what the first two spaces over here. Then we're going to give you a virtual page table because what is the virtual space enable

142
00:20:16.200 --> 00:20:27.300
William Cheng: The virtual taste pace, they will be here is that you don't have any the entire page table you only have part of the page table and also the page table entries over here instead of containing a physical page number it contained a virtual page number

143
00:20:28.290 --> 00:20:37.530
William Cheng: Okay, so it's a little different. What we see before. Obviously, before the pace a plant, you always have a physical base number. So for the Digital Equipment corporate design over here. They contain a virtual page number right here.

144
00:20:38.250 --> 00:20:40.590
William Cheng: That so often is that every program over here.

145
00:20:40.920 --> 00:20:49.320
William Cheng: You know, if you're a user space program you can only use space 00 and 01 if you try to use one zero over here, you can get a segmentation fault and obviously some affiliate program.

146
00:20:49.530 --> 00:20:55.110
William Cheng: There. So what do you do that it will start with 000 and zero y. So, y 000 won.

147
00:20:55.440 --> 00:21:05.730
William Cheng: Once again 00 parties, the lower party address space. If you look at this virtual address over here 00 that's low. So you're accessing your tech segment your data segment your heat segment that will be 00

148
00:21:05.910 --> 00:21:13.110
William Cheng: And then we prefer address translation. He will give you a virtual page number that you can use to access the one zero space table.

149
00:21:13.800 --> 00:21:21.870
William Cheng: Guys are the ones, the ones, your space table is the one that we saw before. He has a physical base address and when you access it using array index, you're going to end up getting

150
00:21:22.440 --> 00:21:28.560
William Cheng: You know, getting a physical page number you left shift it by nine bizarre. We can add the offset and that will give the final

151
00:21:30.090 --> 00:21:39.330
William Cheng: The final address. Okay, so every process has three page table we here 0001 is for the user program and the ones are over here is used by the the

152
00:21:42.000 --> 00:21:43.920
William Cheng: The, the BMS yeah

153
00:21:45.090 --> 00:21:45.960
William Cheng: Yeah, so

154
00:21:47.040 --> 00:21:47.970
William Cheng: The

155
00:21:49.140 --> 00:21:52.680
William Cheng: Z is used by the the the the the address translator.

156
00:21:53.580 --> 00:22:03.030
William Cheng: Alright, so the test will actually go to this really complicated example. So you are not responsible for it. OK. So again, the idea here. I'll be here that you start with 00 space or 01 space.

157
00:22:03.330 --> 00:22:07.590
William Cheng: And you will access the page table instead of a stable, you're going to have found a virtual page number

158
00:22:07.770 --> 00:22:16.230
William Cheng: And the virtual base number is used to index the second level page table which is in the one zero space. Okay. And that will finally give you a physical page number

159
00:22:16.440 --> 00:22:24.960
William Cheng: And the physical page number you you left shifted by 12 bits and you add the officer to it. And that's how you perform address translation that so that's the picture over here. Again, you don't have noted by the detail.

160
00:22:26.670 --> 00:22:33.300
William Cheng: Alright so this guy is helping are these tables that the first two table from the 00 space and 01 space. They are incomplete.

161
00:22:33.570 --> 00:22:37.980
William Cheng: Because typically, you know, the 00 space, yet the tech segment the data. Second, get a piece segment.

162
00:22:38.220 --> 00:22:48.090
William Cheng: Only the beginning entries are us. What, what about for the one zero space. The one zero space. Okay, if you look at address space over here at the stat goes this way and then on the top you have the tech side mean you have data segment.

163
00:22:48.330 --> 00:22:56.340
William Cheng: And you have to heat. The heat, bro. This way. Okay, so the middle part over here is completely empty. So this is the 00 space. This is the one. This is, this is a 01 space.

164
00:22:56.880 --> 00:23:07.710
William Cheng: Now, so, so, so in that case, you know, you don't have to. You don't need to have the entire page table. You only have to know what is the number of entries over here you need for the 00 space page that will add a zero space patient

165
00:23:08.190 --> 00:23:18.540
William Cheng: Okay, so what they call it the individual common core machine, they call them the inside the MMU there's the recipe. Mmm. Okay. I mean, the mm use it for the memory management unit.

166
00:23:19.230 --> 00:23:27.840
William Cheng: So over here, they have a link to register to tell you how many entry inside the 00 space, you know, there's a page a ball. How many of them are valid.

167
00:23:28.410 --> 00:23:39.360
William Cheng: Okay, so, so in addition every entry is over here has a validity bed you also you can also, you know, inside MMU you'll remember only the first few entries over here are valid. So this way. The 00 space.

168
00:23:39.810 --> 00:23:43.980
William Cheng: Space page table can be very, very small. Yeah, so that the patient will look like this.

169
00:23:44.490 --> 00:23:50.730
William Cheng: Now the 00 space over here the pace that, why don't you only have a few entry to cover the beginning part of the the memory said man.

170
00:23:50.910 --> 00:23:59.940
William Cheng: And the 01 space entries over here only only covered the bottom part. So again, only the few entries over here is valid and then you the length. I just show to tell you how many entries are valid.

171
00:24:00.270 --> 00:24:06.810
William Cheng: Yeah, so this actually works in the in the good old days when the UNIX address space is very, very simple. So I guess you know in the

172
00:24:07.260 --> 00:24:12.090
William Cheng: In the time of the digital equivalent core when you know I guess Unix was young.

173
00:24:12.720 --> 00:24:22.290
William Cheng: So in that case, they have the, you know, and that was before multi threading or the address space is actually the simple so this scheme is actually pretty good. So even though the second level paste table is still has

174
00:24:23.670 --> 00:24:31.620
William Cheng: It has to to the entry. So the second level page table is actually a megabytes in size, guys. Oh yeah, that's pretty big. It doesn't really say have any space.

175
00:24:32.010 --> 00:24:40.560
William Cheng: And again, that, that's another reason why nobody's using this anymore. Also, will you start having a multi threading. You can also start using memory map out

176
00:24:40.740 --> 00:24:48.510
William Cheng: Why, in that case, the bottom part of your address face you're going to start allocating many, many stack space. Every time will you create a quickly another child where

177
00:24:48.690 --> 00:24:55.140
William Cheng: You can end up allocating more stack space. So in the end, the even the first level page table and and also you can use memory map out

178
00:24:55.530 --> 00:25:01.170
William Cheng: If you create, create the memory map out in the middle of your address space or then the first level page table and the second level.

179
00:25:01.710 --> 00:25:05.310
William Cheng: The first little page table, they all become very, very big guys out in the end.

180
00:25:05.940 --> 00:25:15.690
William Cheng: The page table overhead. You know, it's going to be really, really big, you know, for the you know the the Digital Equipment core design. Yeah. So anyway, it's, it's not that important. Because nobody's using this anymore.

181
00:25:17.670 --> 00:25:28.710
William Cheng: Alright, so that's the hierarchy, right. So we see that we take the virtual address we chop them into parts and then we build a hierarchy. And we know that, you know, if you use a tree data structure, you can actually save quite a bit of space, right.

182
00:25:29.400 --> 00:25:31.440
William Cheng: So, all right. So that's one way to go. I mean,

183
00:25:31.920 --> 00:25:42.510
William Cheng: So the, the next approach, we're going to see is that use hash table was I gonna what what's a hash table right a hash table is a lookup function right here's a hash table over here. So what you do is that you use a key.

184
00:25:42.720 --> 00:25:47.850
William Cheng: Okay, and then you hash it right you hash the key. You said angel hash function where you

185
00:25:48.630 --> 00:25:51.150
William Cheng: I guess this is just like, you know, if you take on a day to start your class.

186
00:25:51.540 --> 00:26:00.120
William Cheng: Will you take a key you hash it, you're going to get a bucket number. So over here, there's a bunch of bucket over here I bucket zero bucket one all the way through the water. The last bucket. So

187
00:26:00.300 --> 00:26:05.940
William Cheng: So, so in this case. Well you perform a house. You don't give me one of the bucket instead of bucket, there's a conflict.

188
00:26:10.530 --> 00:26:15.630
William Cheng: The can't remember the name is there is a conflict resolution was a collision resolution chain.

189
00:26:16.200 --> 00:26:27.240
William Cheng: So, so, so a bunch of key, they can actually collide into the same bucket. Right. So there's a collision resolution chain. So you can sort of think about is that at this bucket over here, there's a link list. So what you do is that you go down this linguists

190
00:26:27.450 --> 00:26:31.830
William Cheng: Tried to look with the key and then when you find out what the inside a data structure is what you're looking for.

191
00:26:32.730 --> 00:26:40.860
William Cheng: Okay, so that's the beta basic data structure, you know, for a hash table that's using a data structure class. So now we're going to implement this in hardware.

192
00:26:41.640 --> 00:26:45.000
William Cheng: Okay, so, so, yeah, that, you know, we're going to build some data short, you're in

193
00:26:45.210 --> 00:26:52.320
William Cheng: You know, inside the ordinances them and this data structure will be understood by the hardware and the hardware is the ones going to implement this particular look up function.

194
00:26:52.560 --> 00:26:58.530
William Cheng: As on this guy's got, what, what, what, what are you looking at given a virtual paste number you want to return a physical page number

195
00:26:59.040 --> 00:27:03.510
William Cheng: That. So it's still exactly the same operations before. So the picture. So to look like this.

196
00:27:04.140 --> 00:27:11.490
William Cheng: Yeah. So here's a hash table as and they said, we take the virtual address over here, we chopped into two parts. The offset over here is 12 minutes long.

197
00:27:11.730 --> 00:27:17.520
William Cheng: The virtual page number over here is 20 minutes long. So now what we need to do is that we need to hash you're sending to a hash function.

198
00:27:17.790 --> 00:27:25.080
William Cheng: In this example, I mean, we're gonna, you know, we're going to have a hash table the hash into four different value and then inside, you know,

199
00:27:25.530 --> 00:27:35.100
William Cheng: So, so again, these are four different buckets. So here's bucket zero bucket one bucket to bucket three over here. Again, why do we have four rounds of the game. If you have a very simple address space.

200
00:27:35.490 --> 00:27:42.510
William Cheng: One of them is going to correspond to the tech segment the other ones come students have corresponding data plus BSS and the other one's going to correspond, the heat. And the last one is going to correspond

201
00:27:43.260 --> 00:27:49.050
William Cheng: To the stack. So hopefully the near the collision resolution chain that all is going to be very, very short.

202
00:27:49.530 --> 00:27:55.740
William Cheng: So this way we can improve the performance. Yeah. Alright, so here's an example. We take the virtual page number was sending to the hash function.

203
00:27:55.950 --> 00:28:05.430
William Cheng: The output of that hash values to best law in this case is going to return 01 so you don't go to this data structure. OK. So again, here's the link list of, you know,

204
00:28:06.540 --> 00:28:11.550
William Cheng: A collision resolution Chiang Mai. That's what you need to do is that you need to walk down this list and try to look for

205
00:28:11.790 --> 00:28:17.430
William Cheng: What, what are you looking for, you're going to look for the page table entry that correspond to a corresponding this virtual patient number

206
00:28:17.880 --> 00:28:20.760
William Cheng: Okay, so what you will do is that you will go to the first data structure over here.

207
00:28:21.090 --> 00:28:25.290
William Cheng: There's something called a tag. So then what does attack right. It's like when you go to supermarket, you want to buy stuff.

208
00:28:25.470 --> 00:28:33.330
William Cheng: People put tag on to remember where things came from. So it's like a, you know, like a like a barcode or something like that. So what you would do so you will compare this tag.

209
00:28:33.540 --> 00:28:38.820
William Cheng: Against the virtual page number if they're the same. That means that here's the page table that you're looking for.

210
00:28:40.140 --> 00:28:44.820
William Cheng: Okay. What if they are not the same. Well, if they're not the same. That means that this is the wrong one. So what you need to do is a

211
00:28:45.030 --> 00:28:49.200
William Cheng: Is a collision resolution chance. So you need to walk down the collision resolution chain.

212
00:28:49.410 --> 00:28:57.210
William Cheng: And this way you try to look up a particular a particular key there. So what you do is that you read the link field over here again. The link will point to the next guy on the link less

213
00:28:57.390 --> 00:29:05.040
William Cheng: You go to the next hour. We hear you compare the attack against the virtual page number over here if they're the same, then this is the page table entry that you're looking for.

214
00:29:05.310 --> 00:29:12.750
William Cheng: Otherwise, if they're if they are not the same, then you follow the link over here, go to the next one, you compute a tag against the virtual page number if they're the same.

215
00:29:12.990 --> 00:29:20.100
William Cheng: You're going to get. And then this will be the page table entry that you're looking for. Otherwise, you follow the link over here. So in this example, the link over here.

216
00:29:20.580 --> 00:29:29.010
William Cheng: Is going to point to the null pointer was in this case, you're going to get another segmentation fall again, you're gonna get a piece for you trappings of the operating system. The system has to figure out what to do.

217
00:29:30.060 --> 00:29:37.230
William Cheng: OK, so now you get if you get a new way to actually get a segment you get a new way to get there. Get a page files, right. So now you can get a patient

218
00:29:37.860 --> 00:29:43.230
William Cheng: Because be equal to zero can be like you're trying to write to a read only memory segment you try to execute some

219
00:29:43.980 --> 00:29:52.110
William Cheng: You try to execute something that doesn't have the FAQ bit sad, or in this case, when you fall off the collision resolution chat. You can also get a page for

220
00:29:52.890 --> 00:29:58.230
William Cheng: That alright so so what what is it turns out that you know the the tag over here is exactly

221
00:29:58.440 --> 00:30:06.660
William Cheng: The one that you're looking for. Over here, why not case the page table entry over here is what you need. You look at the BB, you look at the rewrite it over here. If everything checks out.

222
00:30:06.840 --> 00:30:14.040
William Cheng: You take the physical page number over here left shifted by 12 minutes at the offset to her and that will give you one minute memory location over here inside of the school page.

223
00:30:15.060 --> 00:30:18.360
William Cheng: Alright, so you can see that, you know, this particular case, you know,

224
00:30:19.680 --> 00:30:25.350
William Cheng: The other, the inside MMU then you need to actually feel all this logic to actually trigger this particular list.

225
00:30:25.620 --> 00:30:32.790
William Cheng: So again, it's going to get a little more complicated. Yeah. So, so again we need to sort of ask a question or the question we need to ask over here is that

226
00:30:33.150 --> 00:30:40.110
William Cheng: If we look at the smallest program that we run over here. What is going to be the overhead, you know, for you know for for our page table data structure.

227
00:30:40.920 --> 00:30:49.950
William Cheng: That the smallest over here, the smallest overhead will be, you know, the data structure over here. Every collision resolution chain. There's only one entry.

228
00:30:50.460 --> 00:30:58.650
William Cheng: Okay, because that would be the smallest, you know, the smallest case. So in this case, instead of like the picture that we saw over here we have a link list of three will only have a link this one.

229
00:30:59.040 --> 00:31:02.280
William Cheng: So in this case, or what it's going to be our pace table overhead, then

230
00:31:02.550 --> 00:31:11.700
William Cheng: Every data structures over here is how many bytes or the tag over here is four bytes. Right. The link over here is also for bias because it points to the base of the next memory location.

231
00:31:11.940 --> 00:31:25.590
William Cheng: Again, it's going to be four bytes long and then over here, the next one over here at the pace that branches over years, four bytes. So one of this data structure over here is 12 bytes. And when you have four of them. That's 48 bytes now 48 kilobytes for 48 bytes.

232
00:31:26.640 --> 00:31:40.410
William Cheng: Okay, so what we just saw here is that we started out with four megabytes a page table we cut it down into, you know, into 16 kilobytes for Intel and now if you use the hash page table, you know, the smallest program will only use 48 bytes.

233
00:31:42.150 --> 00:31:50.340
William Cheng: Alright, so again that's a very tiny paste a ball overhead. So this is really good. But again, there's no free lunch, right. So if it's if you said the outer space. How slow does it get

234
00:31:50.730 --> 00:31:58.080
William Cheng: What the example that we use. Over here we have a page table entries over here. So again, if you only one entry is so bad. If you have a linguist of three.

235
00:31:58.470 --> 00:32:01.800
William Cheng: We perform address translation, how many times you have to go across the bus.

236
00:32:02.070 --> 00:32:08.790
William Cheng: Right. So again, let's take a look at this picture over here, right. So let's say that the one that we're looking for. Over here. This one is the one we're looking for. We started out

237
00:32:09.120 --> 00:32:15.060
William Cheng: Perform the hash function that's inside the MMU. We don't have to go to the bus and then we need to read this data structures read attack.

238
00:32:15.510 --> 00:32:22.380
William Cheng: OK, so the tag is sitting across from across the bus. So we need to go to the bus once and then as it turns out it's not equal to the virtual page number

239
00:32:22.530 --> 00:32:31.290
William Cheng: So in that case, we need to access the link. So now we go to the bus twice. Right. And then we follow the link over here. Read the tag, go to the bus three times and it's not the same.

240
00:32:31.620 --> 00:32:37.560
William Cheng: As the virtual page number. So then we read the link will go to the bus for time and then we read attack again, you know,

241
00:32:37.950 --> 00:32:48.240
William Cheng: From across the bus. The five, the fifth time and this time, you know the the comparison over here inside me or be true. So therefore, for that six time we're going to go across the bus to read the page table entry.

242
00:32:49.590 --> 00:32:57.600
William Cheng: Okay, so this is when the collusion resolution change the length over here is equal to three, we need to have a 600% overhead. What is this

243
00:32:57.840 --> 00:33:05.490
William Cheng: Occlusion resolution chat over here is 10 why, in that case, we're going to actually go to go to memory 20 times I will perform at your translation.

244
00:33:06.450 --> 00:33:18.600
William Cheng: Okay. So clearly this is really, really bad. Okay, so, so, you know, so. So again, it's this one again clearly show you the space in the time trade off in order for us to save a lot of space. The performance is actually can be very, very terrible

245
00:33:19.110 --> 00:33:27.270
William Cheng: Okay. So one way is that is that, you know, the bucket number over here. Maybe we can have more podcasts. If we're more podcasts, then you know the number, the

246
00:33:27.570 --> 00:33:37.230
William Cheng: Collision resolution chain will be shorter so that the that there's what we should deal with that. And there's another approach over here. No as a cluster page table.

247
00:33:37.740 --> 00:33:41.520
William Cheng: Yeah, because if you look at the the hash table right so whenever use the highest a boy.

248
00:33:42.030 --> 00:33:52.080
William Cheng: Who have taken the data structure class, there was that I wanted the hash table works. The table works really, really well. If the keys are uniformly distributed. So, so will you hash, a key into a bucket.

249
00:33:52.650 --> 00:34:02.160
William Cheng: The bucket that you get have a uniform distribution. Okay. But in reality, when we are using that to implement an address space. The way we access our address space is that, you know,

250
00:34:03.540 --> 00:34:12.030
William Cheng: Whereas over here. Every one of the one of these entries over here is four kilobytes. Okay, your tech segment. If your tech segment is pretty big. You're going to end up using contiguous, you know,

251
00:34:12.360 --> 00:34:20.340
William Cheng: In the virtual address space. They're actually contiguous or so in that case, it's kind of a waste is that every what every time we can go to the next page, you have to hash it out and

252
00:34:21.210 --> 00:34:29.190
William Cheng: And go to a different bucket. Maybe there's a way we can actually they can save you know the the sort of the data structure over here, there

253
00:34:29.610 --> 00:34:35.640
William Cheng: So that solution over here is known as a customer page table over here. The reason for that is that the memory segment over here. They are not

254
00:34:36.090 --> 00:34:45.900
William Cheng: four kilobytes bay that typically bigger than four kilobytes. Okay. So, therefore, what we can do that. We can take the virtual you know the the virtual address over here will divide them into two parts of this example.

255
00:34:46.290 --> 00:34:55.830
William Cheng: The leading 717 bids over here that will that will be the one. Give us some sort of a page number and then the middle three bits over here will be used to access that data structure.

256
00:34:56.310 --> 00:35:05.490
William Cheng: Okay, so again, what we do is that we take the the beginning 17 bit over here, send it to a hash function. So in this case, we're going to give us give us this example only give us you know to two buckets.

257
00:35:05.700 --> 00:35:12.120
William Cheng: Bucket zero over here and Bucky once again. Why do we have to write just like the digital equivalent court case one of these

258
00:35:12.360 --> 00:35:17.010
William Cheng: You know, one of them is for the low part of your address space and the other one is for the high party address space, right.

259
00:35:17.190 --> 00:35:27.120
William Cheng: Because the the low part is tech segment the data segment plus BSS plus he they're actually packed right next to each other. So therefore, in that case, you know, maybe they will actually fit into one, one of the data structure. Oh, yeah.

260
00:35:27.570 --> 00:35:32.820
William Cheng: Yeah, and the stack segment over here. Typically, we're going to allocate more than four kilobytes. So again, we're gonna

261
00:35:33.420 --> 00:35:40.920
William Cheng: We're gonna have a date and other data starts you know keep track of it, right. So again, what we do is that we use the leading seven visit 17 busy over here.

262
00:35:41.310 --> 00:35:47.850
William Cheng: You know, send it to the hash function that will tell us which bucket or to go to. And then we're going to compare this tag against living seven bids over here.

263
00:35:48.090 --> 00:35:52.920
William Cheng: If they're the same. That means that the page table entry that we're looking for is one of these eight

264
00:35:53.430 --> 00:35:59.580
William Cheng: Okay, but which one of these A, or we're going to use the last three bits over here in the virtual page number and then use that as a re index.

265
00:36:00.030 --> 00:36:08.010
William Cheng: This one will be entry 012 all the way to seven. So this way we can use that to the final page table entry. Okay, so why do we

266
00:36:08.730 --> 00:36:16.890
William Cheng: Why are we doing things like this. Right. So if you do like this, the length of the collision resolution chain is going to be on the average eight times smaller than the previous approach.

267
00:36:17.910 --> 00:36:28.410
William Cheng: Okay, so again, there's a trade off. We use a larger data structure over here. So, this way we can actually we can improve in our in we can we can improve in speed. Then again to get out of space travel

268
00:36:30.600 --> 00:36:43.860
William Cheng: Alright, so there's one more page table was known as the inverter paste table that. So this one is actually used in the Mac, you know, long time ago. I guess before Mass switch the Intel. I mean, Mac, they're using into these days.

269
00:36:44.910 --> 00:36:52.740
William Cheng: You know, I'm talking about like the what he called the Mac machine, the power book or something like that. I mean, not, not the iPhone.

270
00:36:53.340 --> 00:37:05.130
William Cheng: So, so for for the powerful they're using Intel your CPU before that they use the CPU core Power PC, the RPC CPU. I think they are. They were using the inverted page table there. But again, that's

271
00:37:06.510 --> 00:37:09.720
William Cheng: That's a while back. So how do we actually improve on the hash.

272
00:37:11.190 --> 00:37:16.590
William Cheng: Hash page table right the hash table over here is very small already, but every process has to have a hash.

273
00:37:17.490 --> 00:37:26.160
William Cheng: Hash page stable and as I mentioned before, many program, they will actually share the same page for him. So in that case, you can actually can merge all the the the paste it over here together.

274
00:37:26.610 --> 00:37:34.830
William Cheng: There. So when you're using the inverted page table over here, we'll only have one page table that's shared by all the processes inside your inside the system.

275
00:37:35.430 --> 00:37:40.860
William Cheng: Okay, so this way you know because of because I'm sharing, we're going to end up with the overall smaller page table. Yeah.

276
00:37:41.490 --> 00:37:47.880
William Cheng: So here's the inverter patient about there's only one of them, right. So if you if you Google the term inverter page table.

277
00:37:48.510 --> 00:37:53.610
William Cheng: You're going to see the descriptions to say that the page table here is indexed by a physical page number

278
00:37:54.300 --> 00:38:04.680
William Cheng: Yeah, for the life of me I cannot figure out what that means. Okay. Because India we perform a look up operation, you need a virtual page number. How can you look something up using the physical page number. Yeah. So anyway,

279
00:38:04.980 --> 00:38:10.740
William Cheng: I think that's just the way they describe this particular you know data structure. But India, what you will do is that you are

280
00:38:11.040 --> 00:38:16.590
William Cheng: You need to send your virtual page number you know into, you know, into a hash function.

281
00:38:16.950 --> 00:38:26.760
William Cheng: Yeah. But in this case, since you are sharing this page, they will among all the user processes. Another thing that you need to feed into the page table into the hash function is going to be your process ID.

282
00:38:27.360 --> 00:38:38.940
William Cheng: Okay. Alright. So. So over here, there's only one data structure over here. Sure, by all the processes over here. So now inside the the entries over here. Now, we also need to know whether this page table entries over here which processes are belong to

283
00:38:39.420 --> 00:38:48.420
William Cheng: Okay, so therefore, instead of pasting branches over here. We're gonna have a process ID when I have the are going to have a virtual page number. And then we also going to have a physical page number. Yeah.

284
00:38:49.200 --> 00:38:53.550
William Cheng: Alright, so the example is like this, right, when we perform address translation, we're gonna

285
00:38:54.450 --> 00:39:03.690
William Cheng: We're going to take the virtual page number again over here is 20 beds and probably is over here we're going to combine with the process ID. We're going to send it to a hash function. And now this one will point to

286
00:39:04.200 --> 00:39:11.820
William Cheng: Again, we're going to use one level in direction over here or point to the beginning pointer over here instead of, instead of hash table that will actually point to

287
00:39:12.600 --> 00:39:23.310
William Cheng: Point to a limitless a point to the collision resolution chain inside inverter page table. Yeah, so I'll be here. So you perform the hash function over here is going to give you, again, here's a

288
00:39:24.300 --> 00:39:27.030
William Cheng: Bunch of packets over here and that will give you one of the entries over here.

289
00:39:27.210 --> 00:39:33.810
William Cheng: If you follow the pointer over here that will give you a paper entries that inverter page table. So what should you do right so again.

290
00:39:33.990 --> 00:39:40.050
William Cheng: You need to check the validity Bay, you need to check the rewrite this over here. And then you also need to check the tag. But in this case.

291
00:39:40.200 --> 00:39:47.970
William Cheng: The tag over here correspond to the virtual page number. You also need to store the process ID to see this one now. So even though you have the same virtual page number

292
00:39:48.150 --> 00:39:52.140
William Cheng: One of the actually belongs to a different process, right. So, therefore, you have to compute a computer, both of them.

293
00:39:52.470 --> 00:39:57.240
William Cheng: You compare the pit passes it over here. Again, the process ID of the one that's running out of CPU.

294
00:39:57.450 --> 00:40:05.640
William Cheng: Computer tag over here against the virtual page number if they are the same, then that means that this is the page table entry that you're looking for. So again, the entire data structure for to

295
00:40:06.120 --> 00:40:14.460
William Cheng: Perform a look up. So now when you perform a look up, you need the process identifier, plus the virtual page number and what you need to do that, you need to return the physical patient number

296
00:40:14.820 --> 00:40:19.980
William Cheng: Yeah. So again, the process ID equals to this process ID, the tango P equals a virtual page number

297
00:40:20.220 --> 00:40:28.020
William Cheng: Then this is the paper entry that you're looking for. If it's not, you follow the link pointer over here. Go to the next entry inside a collision resolution change.

298
00:40:28.200 --> 00:40:32.460
William Cheng: You're going to find another process ID and compare against this way you're going to find another time American this one.

299
00:40:32.730 --> 00:40:41.220
William Cheng: If they are equal, then this is the patient but entry that you're looking for. Otherwise, if all the pointer, go to the next one. I go to the next one. I go to the next one, until you reach the end of the conflict resolution chain.

300
00:40:42.330 --> 00:40:51.450
William Cheng: Alright, so again, in this case, you're sharing the pay you sharing the page table or my all the user process. So, this way, this is the one with the smallest page table read

301
00:40:52.140 --> 00:40:57.390
William Cheng: Guys, but again the performance over here might be poor, because the conflict resolution chain might be very, very long.

302
00:40:57.720 --> 00:41:09.900
William Cheng: OK, so I'll get, how do you cut down a conflict resolution chain, the hash table over here. The first level how patient well here can be, you know, have more entries over here. So this way, the length of the conflict resolution channel will be shorter. Yeah.

303
00:41:11.220 --> 00:41:20.670
William Cheng: Alright, so that's the inverter page table. So I guess this is actually a good place to break. So this will be the end of lecture 19

304
00:41:21.120 --> 00:41:36.330
William Cheng: So next time. That's not sure we're going to start looking at the other important you know hardware inside MMU and then we're going to look at some of the 64 bit each issue. And then we're going to go to the second part of chapters seven. Let's look at the colonel support, you know, for

305
00:41:38.250 --> 00:41:51.540
William Cheng: The Colonel support, you know, for virtual memory and how to use all this hardware that we just talked about. Yeah. So again the next lecture will be next week because this week the Wednesday and Thursday. We don't have a lecture because we have a midterm exam.

306
00:41:52.620 --> 00:42:08.190
William Cheng: Alright, so again you know you should read all my email in the class Google Classroom Google about the dimension and logistics and then we'll, we'll we're going to do the midterm exam on Thursday FROM 4PM to 4:40pm yeah