WEBVTT

1
00:00:08.280 --> 00:00:20.760
William Cheng: Right. So, last I guess last session was the midterm exam. So we jumped from lecture 22 lecture 22 because like lecture 21 was supposed to be the exam.

2
00:00:21.420 --> 00:00:32.940
William Cheng: So the you know the lecture number is you know we we skip why now. Okay. Alright. So welcome to lecture 22 Colonel two is due Friday next week.

3
00:00:34.110 --> 00:00:42.270
William Cheng: So you still have, you know, more than a week and a half to finish. If you have code from a previous semester, don't look at them. Don't copy them. Because to get rid of it.

4
00:00:42.690 --> 00:00:57.090
William Cheng: Again, Colonel to is not as bad as other assignment. So there should be plenty of time to do it the grading guidelines that only will grey and we can only grow on the 1630 212 16.4 system.

5
00:00:57.720 --> 00:01:06.930
William Cheng: You need to pass all the tests in BFS test. I see. And then the next test is to test your VS code together with your

6
00:01:07.410 --> 00:01:16.590
William Cheng: Threat coding Colonel one. OK. So again, that's a sort of a different set of tests after submission and make sure you verify your kernel submission and also you need to start with.

7
00:01:16.980 --> 00:01:24.210
William Cheng: You know, copy your BFS Readme file into catering if our, you know, and deal with all the question marks here. So this is the same as before.

8
00:01:26.100 --> 00:01:37.140
William Cheng: You should try to correct you should try to finish a colonel to by the early submission deadline which is Tuesday next week on this way you can give yourself as much time as possible to do Colonel three

9
00:01:38.160 --> 00:01:47.010
William Cheng: So, you know, Colonel three, even though is allocated three weeks it's better that you have three and a half weeks because Colonel three is bigger than Colonel one and two combined. Okay.

10
00:01:47.730 --> 00:01:53.580
William Cheng: For Colonel to or you need to understand polymorphous them reference County and getting going to encounter a lot of reference counting bugs.

11
00:01:53.880 --> 00:02:03.720
William Cheng: You know, so feel free to discuss that in the classical group I should read the colonel FA to FAQ Colonel to FAQ, you know, check out the ones about make no dirt name be

12
00:02:04.440 --> 00:02:12.810
William Cheng: So again, there are major, you know, issues with turn MB with memory corruption, you know, bugs, you know, lots of people at those bugs will be very careful.

13
00:02:13.260 --> 00:02:25.260
William Cheng: And you know what you should do is that for Colonel to implement all the basic functionalities. I see people asking the class Google group about certain you know combinations of open, you know, are humans.

14
00:02:25.980 --> 00:02:33.420
William Cheng: So, you know, so again, check, check the code BFS tests if it's something that we have. So it doesn't doesn't test.

15
00:02:34.050 --> 00:02:38.940
William Cheng: Then whatever code that you write in the end you have to delete them or you have to write special test to test them.

16
00:02:39.540 --> 00:02:50.250
William Cheng: So either case that's really not good guys so, so my recommendation is to write only the basic functionality tried to get a VM FS test as soon as possible. And I mentioned before, you know, I guess a couple of weeks ago.

17
00:02:50.940 --> 00:02:56.790
William Cheng: You know what you need to do in order for you to, you know, get the basic functionality going and then just start running BFS test.

18
00:02:57.030 --> 00:03:02.700
William Cheng: If something doesn't work you fix your code and you move on. Right, only implement the minimal set of functionalities. Okay.

19
00:03:03.360 --> 00:03:12.480
William Cheng: All right. And also please remember that the greater when they try to grade your kernel assignment. Now the only command the greater is allowed to you is we makes you know minus

20
00:03:12.900 --> 00:03:19.170
William Cheng: Okay. So when x minus and over here. So, again, of course, the, the greatest not allow us to the debugger and also

21
00:03:19.470 --> 00:03:30.660
William Cheng: The minus as require minus SS started the winnings operating system with an empty desk. Where's wasn't empty desk right empty. This is it, this that has only one directory. And that's the root directory

22
00:03:31.470 --> 00:03:35.220
William Cheng: Okay, so therefore your kernel code, you have to assume they're going to start with the empty desk.

23
00:03:35.430 --> 00:03:41.250
William Cheng: If you ask the waiter to do anything else, the greater will have to refuse, or you can say, oh my, my co only works if you have already created this directory

24
00:03:41.550 --> 00:03:52.440
William Cheng: So again, those things are not allowed guys so, so, so, so you start with an empty houses, then you decrease Debbie's damning to create all the devices, you know, I said, those are the things that you are required to do. Okay.

25
00:03:53.850 --> 00:03:57.360
William Cheng: Alright, so again, those things needs to be done in idle progress. Right. Okay.

26
00:03:59.640 --> 00:04:07.710
William Cheng: All right, so last time we finished talking about our hashtag finish talking about page tables will get a page table.

27
00:04:08.190 --> 00:04:15.120
William Cheng: Is a kernel data structure that's used by the MMU or used by the CPU are used by the hard way. Okay, so it's a special data structure.

28
00:04:15.510 --> 00:04:21.690
William Cheng: We mentioned before, it's sort of part of the memory map because in order for you to implement memory map, you have to understand how the page table works.

29
00:04:22.020 --> 00:04:30.180
William Cheng: And you know the the the pace table, you know, since is used by the hardware you should consider that it's actually inside hardware abstraction layer because it depends on the CPU.

30
00:04:30.570 --> 00:04:40.080
William Cheng: Okay, so, so, so, so, so inside your kernel code when you try to modify the page table entries those codes, you know, you should think about them as if they're actually belong to the hardware.

31
00:04:40.680 --> 00:04:49.590
William Cheng: Layer. But again, the operating system, typically what they would do that. They will build a abstraction. So you can use sicko to update the page table entries. Okay.

32
00:04:50.340 --> 00:04:54.630
William Cheng: Alright, so we're done with a stable. The next thing we're going to look at. It's a special piece of hardware.

33
00:04:55.350 --> 00:05:03.480
William Cheng: Called the translation look inside buffer. So we mentioned before, when you are using the hash base pay stable, you know, the example that we saw.

34
00:05:03.900 --> 00:05:12.510
William Cheng: When they need to access memory ones. But now, since you are doing address translation are using using a hyperspace tape page table your overhead could be 600%

35
00:05:12.720 --> 00:05:19.020
William Cheng: And if the country is the collision resolution chain is really, really long. Well, then a performance going to be terrible, terrible. Okay.

36
00:05:19.440 --> 00:05:32.070
William Cheng: So again, all the stuff that we talked about, you know, improving the page table we're trying to shrink the size of the pace table and we saw that we can actually go from four megabytes to one megabyte to, you know, 16 kilobyte and the end to 48 bytes.

37
00:05:32.610 --> 00:05:41.910
William Cheng: So we did quite a lot. But every time when we make the table. A little smaller. The performance gets worse. Okay, so what we're going to do right now is I'm going to fix a performance problem only one shot. Yeah.

38
00:05:42.720 --> 00:05:50.910
William Cheng: Alright, so the special hardware that we're going to take a look at is called translation leukocyte buffer. So this will make all the performance problem just magically disappear. So it's great.

39
00:05:52.650 --> 00:05:58.620
William Cheng: Alright. So the basic idea over here is that, you know, when you need to go, you know, access the page table. The table is sitting across

40
00:05:59.460 --> 00:06:08.460
William Cheng: sitting across the bus city memory, right. So think about this picture over here inside memory or right here that's for your pace table is right. So every time, but we need to perform address translation.

41
00:06:08.670 --> 00:06:14.100
William Cheng: We need to get page table entry, the page table entries sitting across the bus. So therefore, we need to start a bus operation.

42
00:06:14.490 --> 00:06:25.500
William Cheng: Okay, so in the beginning, you know, if we don't do a translation, you just go across the bus and you get the data and now you're using a page table the overhead could be 100% could be 200% could be 600% can be really bad.

43
00:06:25.830 --> 00:06:33.540
William Cheng: Okay, so what we need to do over here is that we need to reduce the number of times we we need, we need to reduce the number of times we go across the bus.

44
00:06:34.410 --> 00:06:45.150
William Cheng: Okay, so how do you, you know, sort of reduce number of times to go across the bus. Well, what you can do is that every time. Will you read a page table entry, you are you implement a hard word crash and you catch that information inside the MMU

45
00:06:45.720 --> 00:06:56.490
William Cheng: Yeah, so, so get inside the CPU. Over here we have the inner core of the CPU and then we have the MMU in this picture over here I'm showing you that the MMU is replaced by translation focus I buffer.

46
00:06:57.150 --> 00:07:03.180
William Cheng: Okay so translation look us up over over here is a specialized cash. All it does is to catch cache page table entry.

47
00:07:03.810 --> 00:07:14.760
William Cheng: Because, again, the paper and two is four bytes long. So when you go across the bus to reach those four bytes. When you read those four bytes you catch them inside translation look us up over. So the translation locals that buffer is inside the mmm you

48
00:07:15.240 --> 00:07:20.010
William Cheng: Know guys are actually the translation, because that buffer is so big that the occupy the entire MMU

49
00:07:20.220 --> 00:07:28.500
William Cheng: Last time we talked about what's inside the MMU whereas the inside MMU is all the logic and the hardware logic. So again, if you don't know about hardware. It's kind of hard for you to imagine

50
00:07:28.800 --> 00:07:34.320
William Cheng: But for those of you have taken an architecture class, you need to create a lot of hardware and the hardware is the one that will

51
00:07:34.530 --> 00:07:39.810
William Cheng: You know, do the other translation, you will start a bus psycho go fetch the data to the comparison, all I kind of saw

52
00:07:40.020 --> 00:07:47.580
William Cheng: All those things are done is NAMM you get, but the amount of hardware that you need to perform those kind of operation is very, very small compared to a cash.

53
00:07:48.030 --> 00:07:53.520
William Cheng: Okay, so therefore, typically what we see is that inside the MMU the biggest part is that MMU is translation, because that offer

54
00:07:53.940 --> 00:08:02.760
William Cheng: That sort of translation. That was a buffer is a pretty big cash. Every time you go across the bus to get a page table entry you cash it in CMU right so so again for those of

55
00:08:03.090 --> 00:08:07.620
William Cheng: Those of you who are not familiar with cash, this is like a sort of a cat a computer science cash.

56
00:08:08.610 --> 00:08:16.860
William Cheng: The basic idea over here is that next time when he tried to access the page table entry. The first thing that you will do is that you will look inside a translation looks at buffer to see if it's there.

57
00:08:17.190 --> 00:08:22.740
William Cheng: Well, if it's there, then you don't have to go across the bus. You just, you just accesses translation locals about translation because

58
00:08:23.490 --> 00:08:37.920
William Cheng: You just access the cash incentive translation, because I've offer. Okay, so why do you want to do that. The reason for that is that if you go inside the inside the MMU and to access the page table entry over here, the speed that he will take it 100 times faster than going across the bus.

59
00:08:39.360 --> 00:08:50.640
William Cheng: Okay, so, so, so, so for example if you go across the bus. It will take you 100 nanoseconds. When you try to access translation look as a buffer inside your CPU is going to be 100 times faster is going to be one nanosecond.

60
00:08:51.450 --> 00:09:01.920
William Cheng: Okay, so going across the bus 102nd going inside of CPU over here is going to be one hours ago. So therefore, even if you have a 600% overhead. Well, guess what is only going to cost you six nanosecond.

61
00:09:03.060 --> 00:09:06.330
William Cheng: Okay, so therefore all the performance happened that we saw before. Basically disappear.

62
00:09:07.020 --> 00:09:12.390
William Cheng: Okay, so, so it's important to implement this very, very good cat, the transition because that buffer. It's a cash.

63
00:09:12.570 --> 00:09:19.440
William Cheng: So every time you try to access transit up a stable energy you look inside of translation look as a buffer to see if it's there, if it's there, you're done.

64
00:09:19.860 --> 00:09:30.120
William Cheng: You just, you just read it enough and translate those above or your dad. If it's not there, what you would do that need to spend 100 nanoseconds go across the bus to read a page table entry, will you, will you finish reading

65
00:09:30.480 --> 00:09:35.550
William Cheng: The paper entry from across the bus. You can you make a copy, and you put it inside a translation, because I've offer

66
00:09:36.570 --> 00:09:44.580
William Cheng: Okay, so hopefully next time. Will you try to access the page table entry, you are you going to be able to find that page double entry inside the translation that was that buffer.

67
00:09:45.090 --> 00:09:50.700
William Cheng: Okay, so we're going to sort of use some, you know, hardware cash terminology to talk about insurance agent side buffer, because in the end.

68
00:09:50.910 --> 00:10:04.500
William Cheng: The translation look as a buffer is implemented using a hardware cash. Yeah. So, so what happened is that when you perform a sort of a lookup insert a translational beside buffer. If you can find it. It's called a cache hit. Ah it over here is cash it

69
00:10:04.950 --> 00:10:09.810
William Cheng: would rewrite it over here that so so so when the data is inside of transactions that Barbara. It's called a trend.

70
00:10:10.050 --> 00:10:19.170
William Cheng: Cash it. So in this case, it will only cost you one nanosecond if it turns out the data is not inside of translation looks about right. It's called a cache miss, right, or am I SS I'll be here.

71
00:10:19.650 --> 00:10:29.400
William Cheng: So, so if you get a translation, because I bought from this is going to cost you 100 nanoseconds to go across the bus fetch the data and then, you know, make a copy of that translated over that bar for

72
00:10:30.420 --> 00:10:39.510
William Cheng: Now, so therefore it's very, very crucial if you want to perform well you need to have a very, very high hit probability versus and also you have a very, very low Miss probability

73
00:10:40.170 --> 00:10:48.360
William Cheng: Okay, so most of the time, you know, you want to get hits so so so if you think about when we perform address translation. Okay, how you know what should be your expected rate.

74
00:10:49.020 --> 00:11:00.060
William Cheng: Okay, so let's say that we're, you know, we're running our code, we are inside of tech segment the tech stack men, you know, is made out a bunch of pages every page is four kilobytes long right four kilobytes long

75
00:11:00.600 --> 00:11:03.600
William Cheng: How many instructions are inside a call for particular kilobytes pages.

76
00:11:04.350 --> 00:11:13.710
William Cheng: All we saw before, you know that that some of the entire instruction is only one buys long two bites long sweet by song for Python. Five Eyes on. They're all different kinds of, you know, you know,

77
00:11:14.400 --> 00:11:19.140
William Cheng: The instruction sizes. So let's pretend that on the average instruction is four bytes wall.

78
00:11:19.590 --> 00:11:23.430
William Cheng: Okay, so therefore inside this four kilobytes pages will be here. How many instruction. Do we have

79
00:11:23.610 --> 00:11:36.540
William Cheng: We have on the average 1000 instructions there. So there's 1000 instruction. So when you try to perform a good translation for this particular page. Okay. The reason you need to go to go go across the bus to read a page table entry.

80
00:11:36.870 --> 00:11:41.670
William Cheng: Is because you use the virtual page number as a re index. And then you get one entry over here.

81
00:11:42.150 --> 00:11:47.370
William Cheng: So that entry is not in the transition because I buffer. So you go across the cache of the cocoa cost us to get together.

82
00:11:47.700 --> 00:11:51.840
William Cheng: Yeah, so therefore, will you try to access the first memory location instead is four kilobytes.

83
00:11:52.110 --> 00:12:00.960
William Cheng: Chances are you going to get a miss. Okay, so this way you're going to go across the bus and they need to catch that page table entry inside your translation, because I've offer okay and then

84
00:12:01.440 --> 00:12:10.590
William Cheng: After you finish fetching this instructions are the CPU and now your CPU is going to execute this particular instruction and the time when you execute this instruction, you're going to go across the bus and try to access the

85
00:12:12.150 --> 00:12:16.440
William Cheng: Try to go through to a defense next instruction, whereas the next instruction.

86
00:12:16.800 --> 00:12:26.040
William Cheng: The next instruction on the average is going to be four bytes below it. So it's going to be right inside the same page. So this time when you perform a translation, are you going to get a hint, or you're going to get that get a mess.

87
00:12:26.790 --> 00:12:34.110
William Cheng: Well, so in this case. Most likely you're going to get a hit. Because you know this page table entry is already inside you MMU right because every, you know, so

88
00:12:34.350 --> 00:12:42.780
William Cheng: Every memory location inside this four kilobytes page. They have exactly the same virtual page number. So once you catch the piece that we're entering English translation that buffer.

89
00:12:43.080 --> 00:12:47.160
William Cheng: Every memory access inside this four kilobytes pages over here is going to be a hit.

90
00:12:48.090 --> 00:12:58.260
William Cheng: Okay, so if there's 1000 instructions over here. That means that only one out of 1000 instruction, you will get a miss all of the other 999 instruction, you're going to get ahead.

91
00:12:59.100 --> 00:13:06.150
William Cheng: Okay, so there. Well, what does the hit ratio, the ratio is going to be 99.9%. So in this case, you hit ratio is going to be very, very high.

92
00:13:07.830 --> 00:13:13.140
William Cheng: Okay. So in this case, what is going to be the average performance right if 99.9% of the time.

93
00:13:13.380 --> 00:13:21.630
William Cheng: Where you need to you know what we asked us data, they already inside a casual in this case will be very, very high is the problem is gonna be really well.

94
00:13:21.780 --> 00:13:32.940
William Cheng: Okay, so let's look at our sort of a simple case over here. So let's say that you know your your head, Ray. I mean, in general, it's not going to be 99.9% because you know inside the Yoko. You're going to jump around you going to make system call

95
00:13:33.120 --> 00:13:42.960
William Cheng: So therefore you that you're not going to keep getting hits in the same page. Okay. So, therefore, so let's say that you know if you have 99 99% hit rate not 99.9 but 99% hit rate.

96
00:13:43.260 --> 00:13:53.730
William Cheng: That means that if you, you know, if you perform address translation 100 time 99 time is going to cost you one nanosecond. OK. And then one time is going to cost you 100 nanoseconds.

97
00:13:54.570 --> 00:14:00.000
William Cheng: Okay. So, therefore, what is the average performance, right, the average performance is that, again, you add these numbers up 99

98
00:14:00.300 --> 00:14:13.560
William Cheng: nanosecond plus 100,000 is gonna be 199 nanosecond and and this case you access memory 100 times. So if you do up to 100 time, on the average, your access time for doing other translation is going to be to nanosecond.

99
00:14:15.570 --> 00:14:26.940
William Cheng: Okay. So in this case, when you have a hit rate of 99%. Okay, on the average, when you try to access. We try to access pasted where energy is only going to cost you two nanosecond on the average

100
00:14:27.780 --> 00:14:35.040
William Cheng: OK, so again this is much, much better than $100 again. So even if you have 100% overhead and now your overheads going to be cut to only two nanosecond.

101
00:14:36.090 --> 00:14:42.870
William Cheng: Okay. So, therefore, you know, even if you have, you know, three years. If you have 300% overhead that it's going to be on the average is going to be a little slower but again.

102
00:14:43.890 --> 00:14:57.180
William Cheng: The. So in this case, you know it's gonna cost you to nanosecond to navigate, on the average, every time you deploy more accurate translation. So if you have a you know 200% overhead is going to cost you four nanosecond extra if you have a six.

103
00:14:57.540 --> 00:15:02.760
William Cheng: You know 600% overhead is going to cost you 1200 it's going to cost you 12 now second extra

104
00:15:03.780 --> 00:15:07.530
William Cheng: Okay, so this means that whenever you provide your transition most likely

105
00:15:07.890 --> 00:15:13.950
William Cheng: You'll pay table entry is going to be inside your translation, because I buffer. So, on the average, average transition is going to cause you to nanosecond.

106
00:15:14.100 --> 00:15:22.680
William Cheng: So India when you finish our transition and you need to get the data. Well, this data sitting across the bus when you go across the bus to get the actual data is going to cost you 100 nanoseconds.

107
00:15:23.730 --> 00:15:33.450
William Cheng: There. So therefore, the entire process of accessing data in memory now instead of causing just 100 nanoseconds is going to cost you 102,000 102 nanosecond.

108
00:15:33.840 --> 00:15:42.300
William Cheng: Depends on you know how many patient will enter you need to access. Okay, so remember for Intel Intel use the multi level page table the overheads 200%

109
00:15:42.900 --> 00:15:55.020
William Cheng: The over is 200% if we don't use translation looks out over now with translation logos that buffer every time you need to go across the but to access the final a memory location is going to cost you on the average 104 nanosecond.

110
00:15:55.740 --> 00:16:00.810
William Cheng: Okay. So in this case, your performance will only be 4% worse as opposed to 200% worse.

111
00:16:01.920 --> 00:16:07.410
William Cheng: Okay, so therefore the, you know, the sort of, you can actually see that using transitional because that buffer can make a big difference.

112
00:16:08.160 --> 00:16:14.280
William Cheng: Okay, so this is why you know sort of people use the translation. Look at that. But for the bigger the translation. Look at that. But for the higher the hit rate.

113
00:16:14.610 --> 00:16:22.530
William Cheng: So that's why in modern CPU, you will see that a lot of the CPU, you know, real estate is devoted to build translation focus that buffer. Yeah.

114
00:16:24.090 --> 00:16:30.600
William Cheng: All right, so, so, so, so there are different kinds of missus over here. I wanted to transition a little bit of buffer. And the other one is the page fall

115
00:16:31.020 --> 00:16:33.540
William Cheng: We before you know when you go to page four.

116
00:16:34.020 --> 00:16:41.580
William Cheng: Page is very different from translation will decide buffer, Mrs trends, look look inside buffer. Mrs. Is that what you tried to look look up this particular page stable energy

117
00:16:41.760 --> 00:16:46.950
William Cheng: It's not inside the transactional type offer that's called a translation of us have our premise. Right. What does the page fall

118
00:16:47.220 --> 00:16:57.420
William Cheng: The patient is that after you get a pay per entry, you see that P equals zero, then you gotta pay for that. And also, if you do anything compatible. You try to write to a read only, you know, pay stable entry.

119
00:16:58.800 --> 00:17:07.740
William Cheng: You try to write into a we read on the page. In that case, you also you also get paid for. So in that case, pays for is very, very expensive, right, because what is patient

120
00:17:08.400 --> 00:17:17.190
William Cheng: You execute execute code inside the user space CO, you get a pace while you try into the operating system, the organism has to do all kinds of stuff including going to the desk.

121
00:17:17.940 --> 00:17:24.450
William Cheng: Okay so well you have to go through this, the average performance is going to be on the order of milliseconds. So paste was actually very, very expensive.

122
00:17:25.050 --> 00:17:37.560
William Cheng: That the penalty for translation because apart from this is what you have to go to a, you have to go across the the bus fished a faster pace headway entry and you catch it into a translation that was that buffer. So, in the worst case is going to be 100 nanoseconds.

123
00:17:38.460 --> 00:17:42.420
William Cheng: Okay. So, therefore, you know, these two numbers are orders of magnitude, different from each other.

124
00:17:42.870 --> 00:17:49.500
William Cheng: Okay translation because apart from this is not a big deal. Okay. But again, if you want good performance, you need to have a very, very high rate.

125
00:17:49.950 --> 00:18:01.860
William Cheng: Okay, I'm using the number one nanosecond versus 100 nanoseconds. I mean, those are really, really old number today's memories lot faster. And today CPUs lot faster. But, you know, sort of the relative number are still about the same. Yeah.

126
00:18:03.510 --> 00:18:13.530
William Cheng: Alright, the next thing I'm going to talk about. So here again. So, so, so it is that you know he saw your physical memory over here. We're going to have

127
00:18:13.950 --> 00:18:23.370
William Cheng: You know, sort of all these different page table. There is a page table over here for the blue process at a pace a while here for the pink process. There's a page table be here for, you know, for even the operating system.

128
00:18:24.030 --> 00:18:31.290
William Cheng: Guess later I'm going to sort of see something a little different. And so, conceptually, it is possible that every different process, including operating system. They all have their own page table.

129
00:18:31.620 --> 00:18:44.880
William Cheng: Okay. So, therefore, if you're running inside the CPU. Right. So the way I draw this picture is that if the blue processes running inside of CPU, then the inner core of the CPU turns blue and now you're a caching page table entry for the, you know, for the blue process.

130
00:18:45.810 --> 00:18:56.100
William Cheng: Okay. So over here, all these entries over here pasted when they are copy from the physical memory and then you copy them into, you know, internet sensation look as a buffer one one page table entry at a time.

131
00:18:56.520 --> 00:19:08.730
William Cheng: Okay. So yeah, this is the very specialized cash because all it does is to cache page table entry. It doesn't catch anything else. Right. So if you're a web person you know about a lot of different kinds of caches. This is a very, very specialized cash. Yeah.

132
00:19:09.900 --> 00:19:20.580
William Cheng: All right. Ah, so, so, so what happened is that will be here is that when you need to modify page table entry. Okay, so we saw before, when you type into the operating system. Turns out that, you know, maybe the equal to zero.

133
00:19:21.180 --> 00:19:24.990
William Cheng: Maybe we're doing, you know, copy on write, we need to fix the page table entries over here.

134
00:19:25.200 --> 00:19:37.500
William Cheng: When we need to change one of the page table entries over here. If this entry is insider translation Lucas I buffer. Then if you modify the page table entry inside the page table in memory or then this pretty good entries over here is going to be wrong.

135
00:19:38.190 --> 00:19:43.050
William Cheng: Okay, so therefore every CPU, they gotta have a method to delete this entries over here inside of

136
00:19:43.380 --> 00:19:50.880
William Cheng: Inside of translation, because I've ever. Okay, so this is no as flushing the translational is our buffer or invalidate the translation. Always have offer

137
00:19:51.390 --> 00:19:58.260
William Cheng: Okay, so if you modify one page table entries over here. Well, you can do that. You can invalidate one of the paper entries over here. So how do you do that.

138
00:19:58.440 --> 00:20:03.780
William Cheng: But all you need to do is to provide a virtual address inside MMU what it will do is they'll take the virtual address convert

139
00:20:03.960 --> 00:20:11.490
William Cheng: You know, figure out what page virtual page number. It is. And then he would do a search instead of translation looks that buffer and then sort of invalidate that entry.

140
00:20:12.060 --> 00:20:19.980
William Cheng: Okay, so this way. Will you refer to the, the, the, the same page table entry again next time. Will you try to perform a look up, you know, translation looks out over

141
00:20:20.190 --> 00:20:27.810
William Cheng: It will fail. And then you will go across the bus copy this one intergenerational example for. So now what's inside your cash will be the same as what inside memory.

142
00:20:28.530 --> 00:20:37.350
William Cheng: Okay, so that's sort of one of the problem with the hardware caches that you always have to make sure that what's inside the cash is consistent with what's inside what what was inside physical memory.

143
00:20:37.710 --> 00:20:46.260
William Cheng: So every time when you change something that physical memory. You have to invalidate a translation looks like buffer entry over here, and every CPU has a machine sharpshooting that allow you to do that.

144
00:20:47.160 --> 00:20:53.970
William Cheng: Okay, so they don't want you working or you Colonel three major you find that instruction so that you can include invalidate translation, because I prefer that

145
00:20:54.360 --> 00:21:03.480
William Cheng: Transition was about where the shorthand is to to be. So right now, you can actually do it, or you can run grab on to be so if you look, look at, look for lowercase T. I'll be

146
00:21:03.840 --> 00:21:07.740
William Cheng: You can find inside the Colonel. There are quite a few places that will access the translation.

147
00:21:08.670 --> 00:21:16.860
William Cheng: Right. All right. What if you run a different process, whereas over here, the inner core of the CP over here, a change to a different process.

148
00:21:17.700 --> 00:21:23.010
William Cheng: All the information that you cash instead of transition looks out over there all wrong.

149
00:21:23.280 --> 00:21:30.690
William Cheng: Right, because he's translation looks out for our from the blue page table when you switch to the pink process. You need paste table over here from the pin process.

150
00:21:30.870 --> 00:21:35.640
William Cheng: If he keep all these things around while then we provider sensation. You're gonna perform the wrong address translation.

151
00:21:36.480 --> 00:21:41.490
William Cheng: Okay, so therefore, there needs to be a way to invalidate the entire translation little sub offer

152
00:21:42.060 --> 00:21:48.600
William Cheng: Okay, so this is the process of flushing the entire translation, because I buffer or invalidating the intelligence, they should look a buffer.

153
00:21:48.960 --> 00:21:55.290
William Cheng: For x86. This can be achieved by setting the car three register. Okay. So remember when you switch to a different process.

154
00:21:55.620 --> 00:22:03.900
William Cheng: You need to go to the menu and then change the car through register. So when you change the car through register. What it will do is that they will actually invalidate the entire translation. Notice I prefer

155
00:22:04.710 --> 00:22:11.040
William Cheng: Okay, so, so, so, so, so by simply changing the car three register the side effect is that the entire translational does have buffer.

156
00:22:12.150 --> 00:22:15.750
William Cheng: Is flushed. So, therefore, you don't have to do anything special. Okay.

157
00:22:23.940 --> 00:22:29.700
William Cheng: Alright, so the next thing we're looking at as briefly as a look at how to actually implement this translation look as a buffer in

158
00:22:31.020 --> 00:22:31.920
William Cheng: In hardware.

159
00:22:33.030 --> 00:22:41.670
William Cheng: So the way that we do this is that over here. Here is a data structure, you know, again, it's a cash, it's going to have a look up data structure. There's a time and tell you where they're coming from.

160
00:22:42.120 --> 00:22:48.000
William Cheng: What you do is that is that, you know, it's very similar to either translation. We're going to take the virtual page number we're going to sort of

161
00:22:48.810 --> 00:22:54.870
William Cheng: Try to perform a look of operation. Okay, there are different implementation of the translation, because I bought for

162
00:22:55.320 --> 00:22:59.370
William Cheng: Because it's a horror cash and we try to implement a hardware Castillo different approaches. OK.

163
00:22:59.970 --> 00:23:11.310
William Cheng: So again, the translation levels above where is often implement it as a simple a hash table inside hardware. OK. So the way this is done is that we're going to take the virtual patient number over here. And then we're going to take

164
00:23:12.450 --> 00:23:14.100
William Cheng: So, so be it really depends on

165
00:23:15.330 --> 00:23:25.290
William Cheng: Depends on how big your translations of this offer is. So for example, in this example. This is called direct mapping cash. Okay. It's a hardware a cash with 64

166
00:23:25.650 --> 00:23:34.770
William Cheng: So again, the hardware terminologies that these are called cache lines. This is again like we talked about a software, you know, hash table. These are called buckets.

167
00:23:35.220 --> 00:23:42.510
William Cheng: OK, so the, you know, I mean, we talked about the industry. These are called buckets. When you talk to the hardware people they call this, you know, a cache lines.

168
00:23:43.110 --> 00:23:54.510
William Cheng: So, so when you perform a look about ratio, what you will do is that you use the key and then you you feed it to a hash table and that will give you one of the entries over here. So what you do is that you compare the key against sorry

169
00:23:54.900 --> 00:24:04.110
William Cheng: You compare the leading, you know, leaving bits of the virtual page number over here against the tag, if they are equal. That means that the page table entries over here is what you're looking for.

170
00:24:05.190 --> 00:24:09.210
William Cheng: Guys on this guys, again, you know, depends on how big your translation look as a buffer so

171
00:24:09.420 --> 00:24:15.270
William Cheng: If I have 64 cache line, then what I have to do is I have to use six bits in order for me to pick it to figure out

172
00:24:15.480 --> 00:24:21.180
William Cheng: You know, which bucket of this okay inside our hardware that typically that they don't use the fantasy hash function.

173
00:24:21.450 --> 00:24:30.780
William Cheng: If you have actually implemented hydrangea you know the hash marks is it's kind of slow. Okay, so what they will do is that they will basically use the last six beers over here for the virtual case number or a index.

174
00:24:31.620 --> 00:24:39.120
William Cheng: Okay, so in this case the bucket number is exactly the last six page over here for the virtual page number and this will give you the entries over here for cash line.

175
00:24:39.630 --> 00:24:48.180
William Cheng: So instead of cash line over here, you need to remember this particular page entry. Where does it come from. So what you would do that you will compare this tag against this, the leading 14 busy over here.

176
00:24:48.390 --> 00:24:51.240
William Cheng: If they're the same, then this is the page table entry that you're looking for.

177
00:24:51.930 --> 00:24:58.830
William Cheng: Okay, so this particular architecture and always direct mapping the direct mapping over here is that you're getting. If you think about the software implementation.

178
00:24:59.040 --> 00:25:07.410
William Cheng: Inside the bucket. We have a collision resolution change the length of the collusion resolution change is always one. If you're using the direct, direct mapping cash.

179
00:25:08.940 --> 00:25:19.080
William Cheng: Okay. So in this case, what you have to do is since the size of the bucket is equal to one. You don't have to walk down the conflict resolution chain. There's only one item on this list, and this will be the one that you need to look for

180
00:25:19.620 --> 00:25:28.020
William Cheng: Okay, so again, let me clear this up a little bit. Right. You start with your virtual page number you take the lease a significant six six bit over here as an array, array index.

181
00:25:28.230 --> 00:25:38.910
William Cheng: That will give you a cache line you compare the leading 14 biz against the tag over here is there the same that this page table entries is what you're looking for. So, therefore, you avoid a trip or going across main memory.

182
00:25:39.360 --> 00:25:45.180
William Cheng: OK. So again, this access is going to cost you one nanosecond. And this is really, really great. Then what if this tag, and this time.

183
00:25:45.420 --> 00:25:49.470
William Cheng: What if the leading 14 business or your virtual page number is not equal to attack what

184
00:25:49.650 --> 00:25:57.630
William Cheng: That means that this is the wrong page table entry over here. So, therefore, what you have to do is that you have to start a bus psycho go across the bus to read that page table entry.

185
00:25:57.930 --> 00:26:05.760
William Cheng: Guys, but again, last time we talked about address translation, I show you how to actually compute a physical address. So, therefore, you know, again, sorry MMU

186
00:26:05.970 --> 00:26:11.460
William Cheng: You compute the physical address you put the address across the bus and you read a page table, you know, from, you know,

187
00:26:11.760 --> 00:26:19.680
William Cheng: From memory into the menu and then what you would do that you needed to leave the century when you delete this entry, you're going to replace them with a new page table entry.

188
00:26:20.070 --> 00:26:34.170
William Cheng: Okay, so therefore the new page table entry goes in here and the leading for biz over here, your virtual address you copy that over here over the attack, whereas what again. What this means is that this page table entry correspond to this leading four bits, instead of virtual patient number

189
00:26:35.550 --> 00:26:41.970
William Cheng: Okay, so this is called a direct, you know, this kind of direct mapping cash you know every bucket over here.

190
00:26:42.480 --> 00:26:48.000
William Cheng: You know, has the conflict resolution change and the length, length of the conflict resolution change. Exactly. Yeah.

191
00:26:48.900 --> 00:26:56.520
William Cheng: Alright. So in this case, when you get a translation logos that buffer hit that means that the tag inside the virtual address over here the exactly the same as

192
00:26:56.790 --> 00:27:07.140
William Cheng: The tag instead of transitional beside buffer if they're not equal, you get a TL Bemis guys and this case you ever go across the memory cost you 100 nanoseconds, you bring that the pace that we're entering into

193
00:27:07.500 --> 00:27:13.980
William Cheng: Into your translation logs are buffer. And then they they replace that page table entry. You also replace the tab.

194
00:27:15.030 --> 00:27:20.340
William Cheng: Okay, so this is the direct mapping cash. So typically direct path of mapping cash doesn't really perform very well.

195
00:27:20.970 --> 00:27:27.900
William Cheng: The second approach over here is called a, you know, set associative cash. I'm going to send associated cat there. There are different, I guess, you know,

196
00:27:28.140 --> 00:27:37.020
William Cheng: The Howard terminologies that there are something called a to a set of shoes associative case there is a four way said associate okay there's also the a way said associative cash, the number of

197
00:27:37.410 --> 00:27:46.260
William Cheng: You know the number of different ways is the site that is the depth of the depth of the bucket. Okay, or is it the length of the collision resolution chain.

198
00:27:46.710 --> 00:27:58.410
William Cheng: Okay. So this example is called a two way said associated cash inside every bucket. The conflict at the collision resolution chain. I mean, he using the term collision resolution and conflict resolution to me exactly the same thing.

199
00:27:58.740 --> 00:28:01.890
William Cheng: That's what this guy is again you're getting collision. You're getting complex

200
00:28:02.490 --> 00:28:08.310
William Cheng: The length of the collision resolution chance always equal to two and that's why it's called a twist that associative cash. Okay.

201
00:28:08.430 --> 00:28:17.490
William Cheng: So in this case, what you would do is that you do exactly the same thing. You use the last six minutes over here to give you an array index and this example, we still have 64 cache line or 64 bucket.

202
00:28:17.670 --> 00:28:22.320
William Cheng: Right. So in this case you will access. One of the bucket over here and there are two entries over here.

203
00:28:22.530 --> 00:28:31.110
William Cheng: The difference between this and a hash table is that this is done in hardware. So what you will do is it will compare the tag against these two tags simultaneously in hardware.

204
00:28:32.100 --> 00:28:39.090
William Cheng: Okay, so this is done in exactly one nanosecond right so this can be done really quickly you compare this tag against to have these tags over here.

205
00:28:39.300 --> 00:28:43.920
William Cheng: Because the death of the collision resolution chain equal to two. So, therefore, there are two types, you need to compare

206
00:28:44.130 --> 00:28:49.710
William Cheng: It. One of them is true, that means that one of them has a page table entry, you go to that page table entry. You don't have to go across the bus.

207
00:28:49.980 --> 00:28:54.750
William Cheng: Okay, if both of them. The comparison is false. Why, in that case, that means that both of them are wrong.

208
00:28:55.380 --> 00:29:07.740
William Cheng: Okay. So in this case, again, you need to go across the bus spend 100 nanoseconds, read the paper entry from across the bus. Okay, and then will you bring in to bring back to this as a as a buffer. And now you actually, you have a very difficult task to do

209
00:29:08.640 --> 00:29:18.690
William Cheng: That. So what you need to do is that you need to replace one of the, you know, one of the castle. You know, one of the entries over here. So which one do you replace you replace the first one on the top or the second one in the back.

210
00:29:19.500 --> 00:29:28.020
William Cheng: Okay, because now you read a new page that when she, you don't need to replace both of them and you replace one of them. Which one do you pick. Okay, so this is no s replacement policy.

211
00:29:28.380 --> 00:29:36.390
William Cheng: Okay, so instead of CPU or inside MMU they got to execute some kinds of replacing policy to figure out whether you replace the first one or you replace the second one.

212
00:29:36.990 --> 00:29:46.530
William Cheng: Okay, if you make the wrong decision. Your me was not gonna perform very well. So again, that's beyond the scope of this class, if you, you know, take a hardware class, there was sort of tell you how to actually implement this one.

213
00:29:47.250 --> 00:29:49.770
William Cheng: Night. Alright, so this is a two way said associative cash.

214
00:29:50.130 --> 00:29:56.940
William Cheng: Intel actually use it a way said associative cash. Okay, so again, you know, it depends on how many cashmere doesn't really matter how many cache line they have

215
00:29:57.180 --> 00:30:07.830
William Cheng: Every cache line has this collision resolution chain that the length is equal to eight. And then what you do is that you take the leading 14 biz over here compared yes all those a tax simultaneously hardware.

216
00:30:08.430 --> 00:30:18.690
William Cheng: That, again, those of you who knows about actually doing stuff in hardware, we need to compare things in parallel. It's actually very, very expensive in terms of, you know, building that on a chip.

217
00:30:19.320 --> 00:30:30.810
William Cheng: Okay, so that's why you know this this entire data structure their building hardware and then all of the comparison you have been done in parallel also need to be done in hardware. So this is, you know, this wise take up so much room, you know, inside. Inside you MMU

218
00:30:31.200 --> 00:30:42.000
William Cheng: Okay, so that's why the entire me you and yeah looks like all it has is transitional because I buffer, because all the logic that you need to implemented across the bus to get data those logic take up every little space. Yeah.

219
00:30:43.530 --> 00:30:54.030
William Cheng: All right, so this is a sort of a, you know, this is called said associative cash over here. Again, Intel use a way consider associated cash. So therefore, typical interaction perform really really well.

220
00:30:54.360 --> 00:31:04.800
William Cheng: Okay. So can you tell us the multi level page table if the transition look us up above where it doesn't perform very well. Well then, most of the time you need to go across the bus and then your CPU will behave as if it's really, really slow.

221
00:31:05.340 --> 00:31:17.340
William Cheng: That. So in this way, this way for using a way. So I said associated cash. Most of the time when you try to, you know, perform a good translation, chances are your page table entry will be inside a translation of a buffer, then

222
00:31:18.870 --> 00:31:27.150
William Cheng: Finally, there's one more way. So in this case, there's only one bucket, the bucket has, you know, has many, many entries over here so so sorry.

223
00:31:27.570 --> 00:31:35.550
William Cheng: The, the collision resolution chain going to be very, very long. OK, so maybe you know this example over here. There might be 64, you know, you know,

224
00:31:36.480 --> 00:31:45.810
William Cheng: 64 data structure over here. So in this case collision resolution chance to be a 64 but again if you build this in hardware, you can do the comparison with all 64 then all in one shot.

225
00:31:46.350 --> 00:31:53.490
William Cheng: Okay, it's gonna cost you a lot in hardware. I mean, in some cases, you know, some people there your transition because of our site buffer is so big.

226
00:31:53.700 --> 00:32:02.520
William Cheng: And they don't want. They don't want to build so many a competitor. What they will do is that it will use something called a micro code. So inside of your inside the CPU, they will actually do run

227
00:32:03.360 --> 00:32:11.670
William Cheng: Run a little program that will go through this entries over here. One of the time, comparing the time against this tag over here to see which one is equal

228
00:32:11.820 --> 00:32:20.730
William Cheng: If one of them is equal, then that will be the pitch table entry that you need. So in that case, you will use it right away, like all of them are not equal one. Discuss. Can you go across the bus you read the entry of hearing.

229
00:32:21.120 --> 00:32:27.180
William Cheng: That, again, the replays on policy over here is going to be very tricky. Out of all the 64 inches over here. Which one do you replace

230
00:32:28.080 --> 00:32:35.070
William Cheng: Okay, so again I'm using 64 entries over here as an example. I don't. I have no idea what intel is using, you know, how many, how many buckets, they have

231
00:32:35.370 --> 00:32:45.810
William Cheng: So again, maybe you have to look at Intel manual and also maybe depends on how much money you want to spend, you know, maybe you can buy a CPU with more with a bigger translation or with about four or small chance

232
00:32:46.980 --> 00:32:47.310
William Cheng: That

233
00:32:48.840 --> 00:32:55.650
William Cheng: All right, so that's fully us you know the fully associative cash very expensive, you know, to actually build. Okay.

234
00:32:57.510 --> 00:33:07.500
William Cheng: Alright, so now we're going to talk a little bit about a special case with multiple CPU and every time we talk about more things more CPU things gets really messy. And now we sort of have a, you know, so this was

235
00:33:08.340 --> 00:33:17.910
William Cheng: A case that we need to sort of address in about four CPU case. Yeah. Alright, so, so the translation, because I buffer is inside the CPU. So when you have to CPU. How many translation opposite Barbara you have

236
00:33:18.300 --> 00:33:28.020
William Cheng: Was it was to CPU have to MMU every MMU has your translation will have that buffer. So we here is if you want has translated on cyber for CPU to has translation looks at buffer.

237
00:33:28.230 --> 00:33:35.610
William Cheng: What are they cash right so if if both of them are running the blue process, they are cashing the same page table entry on the same page table.

238
00:33:36.900 --> 00:33:51.270
William Cheng: Okay, so this translation look is that buffer is gonna catch all the blue entries over here and this one since it's running a different thread from the same process. Okay. So, therefore, what is caching over here again the data coming the data coming from the same page table.

239
00:33:52.680 --> 00:34:00.060
William Cheng: Alright. So in this case, what kind of problem can actually happen. Right. It is possible that you know you're you're running you're running coatings that processor one over here.

240
00:34:00.210 --> 00:34:06.210
William Cheng: You trapped inside the Colonel. The colonel. Try to modify. One of the paper entries over here. So again, why is the current modifier.

241
00:34:06.390 --> 00:34:13.500
William Cheng: Right, we mentioned before, right, you try to access the page table entry. The equals zero you trapped inside a colonel. The Colonel to all kinds of stuff. Wait for this.

242
00:34:13.710 --> 00:34:20.700
William Cheng: fix up everything when the colonel fix up the pace table over here. What it will do is it will actually change data over here to say the equals two, one

243
00:34:20.910 --> 00:34:26.730
William Cheng: Right. Also, you need to set the read and write and also need to have the physical page number pointed a page that are allocated.

244
00:34:27.150 --> 00:34:38.760
William Cheng: Okay. So, therefore, if you are CPU number one over here. What you can do that. You can flush all translation logos that buffer entry over here, you can go to the to be over here. You can invalidate the entry that correspond to a stable entry right here.

245
00:34:39.720 --> 00:34:52.530
William Cheng: Okay, so you can do that if you're a CPU. Number one, okay, CPU number one over here is going to be the one that changes this translate the page table n g inside the page table. You can also invalidated corresponding paints a big, but what about the second CPU.

246
00:34:54.180 --> 00:34:55.890
William Cheng: What a second CPU over here, you know,

247
00:34:56.640 --> 00:35:03.060
William Cheng: You know, we mentioned before, there's no way one CPU can tell the other CPU what to do right if you if you try to talk to the other CPU.

248
00:35:03.270 --> 00:35:10.680
William Cheng: The other CPU just ignore you. So, therefore, how can you ask the second CPU over here to to actually invalidated translate He looks out over

249
00:35:11.100 --> 00:35:14.820
William Cheng: Okay. So, by the way, why does the second CPU has to evaluate a chance, a little bit.

250
00:35:15.150 --> 00:35:26.610
William Cheng: About her what because the translation logs are buffer reflect what's actually inside the page table right so if you modify the page table. You got to make sure that every copy of the patient will entry, they are all up to date.

251
00:35:27.120 --> 00:35:35.670
William Cheng: Okay. So, therefore, if you modify this page table entries over here, you know, by CPU. Number one, you need to tell CPU number two is to say hey you know you should also invalidated entry.

252
00:35:36.780 --> 00:35:42.630
William Cheng: Okay, but we don't know how to do that, right, because there's no way for you to tell the CP what to do that. Alright, so what do you do

253
00:35:43.200 --> 00:35:48.060
William Cheng: As it turns out, a solution over here is that you need to run a distributed algorithm.

254
00:35:48.960 --> 00:36:00.840
William Cheng: Okay, we need to run an algorithm over here and not involve multiple CPU and then you know this algorithm is going to run in one CPU. We also need to implement some other algorithm in the other CPU now all the CPU or all work together.

255
00:36:01.140 --> 00:36:10.590
William Cheng: To make sure that that doesn't happen. Okay. So, therefore, you know, so, so, so what about the distributed algorithm this Jubilee algorithm is no as the to be shoot down algorithm.

256
00:36:11.610 --> 00:36:14.070
William Cheng: Okay, so what does he do yoga and things get a little messy.

257
00:36:14.520 --> 00:36:23.370
William Cheng: The picture over here we have a tank on CPU of one over here, what he will do is that he will actually invalidate the CPR. The translation, because that buffer inside the second CPU.

258
00:36:24.030 --> 00:36:35.100
William Cheng: Okay, so how does it do that right again CPU one. There's no way for you to top CPU what to do. So CPU number to over here has to will have your has to be willingly, you know, flushes old translational because I've ever

259
00:36:36.270 --> 00:36:44.340
William Cheng: Alright, so we're gonna take a look at this issue with the elbow elbow or then this needs to be done very, very carefully because multiple CPU things gets a little tricky. Yeah.

260
00:36:45.420 --> 00:36:51.810
William Cheng: Alright, so let's see how this one is done. We need to get a timing just right. We're going to look at the CO. So this one is known as a shooter.

261
00:36:52.230 --> 00:36:59.370
William Cheng: Guys over here, this is the one with a tank. So this one's gonna be shooter. This is one of those getting shot right so this is why it's called a shoe T sh.

262
00:36:59.760 --> 00:37:08.550
William Cheng: T. This is one is getting shot. We're going to look at a call for the shooter and the shoe a shoe t they need to work together in order for you for for this to happen now.

263
00:37:10.290 --> 00:37:16.560
William Cheng: Alright, so let's take a, you know, so, so, so what does the basic idea over here are the basic idea or we here is that

264
00:37:17.730 --> 00:37:27.240
William Cheng: You know the seat that the shooter, or we fear the shooter is not allowed to modify the patient when she's over here until the shoe D is is actually in a good state.

265
00:37:28.140 --> 00:37:32.700
William Cheng: Okay, so what do you, what do you have been inside. Inside your kernel before you modify the pace table entries over here. So,

266
00:37:33.240 --> 00:37:43.020
William Cheng: So we are really not allowed to modify it, because if as soon as we modify it. What if you know CPU to actually, you know, take a, take a copy as I'm putting a translation looks out over or in that case will be too late.

267
00:37:43.890 --> 00:37:57.030
William Cheng: Okay, so therefore we need to get the timing right so before we modify the pace table entries over here inside of the inside the page stable across the bus. What we have to do is that we need to make sure that none of the other CPU are using this page table entry.

268
00:37:58.350 --> 00:38:01.290
William Cheng: Great. So how do we make sure the other CPU don't use the paper entry.

269
00:38:02.130 --> 00:38:09.150
William Cheng: What if the other CPU is actually running. There's no if we just stop it. Right. So in this example, you know, we are both CPU are running threats on the same process.

270
00:38:09.450 --> 00:38:18.690
William Cheng: Okay, so therefore there's really no way for you to tell the CPU to stop what it's doing. Okay. There's only one thing you can do, you can force the second CPU to go to the interrupt contacts.

271
00:38:20.130 --> 00:38:30.870
William Cheng: Right, if you, for the second for the second second CPU to go to interrupt contacts will it be executing thread co in the user process. Well, no, they won't. Right. So, so if you interrupt the second CPU. The second CPU.

272
00:38:31.530 --> 00:38:41.070
William Cheng: Is going to go into interrupt service routine. What is inside interrupt service routine, the user threat and suspend their so therefore you know that the user program is not using this page table entry.

273
00:38:42.330 --> 00:38:52.650
William Cheng: Okay, so this is part of the shoot on algorithm over here. We're going to go to all the other CPU, we're going to pull this, you know, pull the special interrupt to interrupt all the other CPU, the force them all go into the internal contacts.

274
00:38:53.160 --> 00:39:01.590
William Cheng: Because if there are, you know, interrupt contacts, then I know that there are not in the right context if there are nine to three contacts, they will not be able to access the patient Wednesday.

275
00:39:02.760 --> 00:39:09.900
William Cheng: Okay, so therefore I need to wait for them, all of them to go into the wrong contacts and then I can modify the spaceship or entry. Okay. Because then it will be safe for me to do that.

276
00:39:10.260 --> 00:39:22.020
William Cheng: Yeah. So let's take a look at the code over here. The top coat. Aubrey furious for the you know the the shooter Co. The bottom part over here is for the shoot. Ego and the shooting code over here is executed inside interrupt handler.

277
00:39:22.830 --> 00:39:31.050
William Cheng: Okay, so I don't know if you remember when we look at the Intel CPU interrupt priority right number 31 is IP a high number 30

278
00:39:31.620 --> 00:39:38.250
William Cheng: Is losing power number 29 is called into processor interrupt this is the inner processes interrupt.

279
00:39:38.820 --> 00:39:45.510
William Cheng: OK. So again, it's very, very high party because we are implementing a translation, because I buffer shoot down algorithm that

280
00:39:46.260 --> 00:39:51.690
William Cheng: Alright, so we're here. So what was the shooter what it will do that for all the CPU that are sharing the same address space.

281
00:39:51.990 --> 00:40:00.180
William Cheng: What the CPU is nice sheen, the same address space now that we don't really care about the pace ever entry, you can do whatever he wants right before the CPU are sharing the outer space.

282
00:40:00.390 --> 00:40:08.190
William Cheng: We need to make sure all those threats go into the right contacts. Okay, so what it will do is that will issue interrupt for Intel going to issue interrupt number 29

283
00:40:08.610 --> 00:40:13.380
William Cheng: So this way we can actually, you know, for all for all of them to go through the internal contacts.

284
00:40:13.800 --> 00:40:20.820
William Cheng: Okay, how do you do that. Why is it turns out Intel their specialized instruction for you to do that. Okay, so this way you can interrupt all the other CPUs. Yeah.

285
00:40:21.120 --> 00:40:30.570
William Cheng: Alright, so we're going to interrupt all their CPU. So when they were all the CPU. They are sharing the address space. And then what we need to do is that we need to wait for all of them to going to read off contacts. So how do we do that.

286
00:40:31.560 --> 00:40:37.320
William Cheng: Well, so this guy is, again, we're going to have serious I'm going well data structure inside. Inside the Colonel. We're going to look. Look at this, you know,

287
00:40:37.710 --> 00:40:46.290
William Cheng: This array this array, there's going to be one big for every CPU there and we're going to check if they got into the interrupt service routine if they haven't gone into raindrops obesity.

288
00:40:46.770 --> 00:40:55.320
William Cheng: So in this case, the interim will be here is interrupt number 29 right it's very, very high a party interrupt. Why would the other CPU not going to interrupt service routine right away.

289
00:40:55.800 --> 00:41:04.740
William Cheng: Well, maybe the other CPS you know up disabled, right, because if you have enough disable while you know if you try to generate you know by 29 there was still it was still become pending.

290
00:41:05.310 --> 00:41:11.100
William Cheng: So in that case, you know, you might take a while for the other CPU to get into enroll contacts. Okay. But we know that pretty soon, is to go into the

291
00:41:11.640 --> 00:41:16.260
William Cheng: Contacts, so you can disable you know for a little bit, but pretty soon you're going to enroll contacts. Yeah.

292
00:41:16.410 --> 00:41:27.300
William Cheng: So here what we need to do is that we need to stay inside a for loop wait for all the CPUs to going to enroll contacts there when they go into the inner up contacts. What they would do is that it was said noted for their CPU to equal to one.

293
00:41:27.720 --> 00:41:29.910
William Cheng: So as long as no equal to zero, then I will still

294
00:41:30.900 --> 00:41:41.640
William Cheng: Keep waiting. Okay, so when you finish with this info over here that you know that all the other CPU. They all have gone into the euro context, right. So if you look at the Internet service within code over here, they all get following

295
00:41:41.880 --> 00:41:52.770
William Cheng: This is the the the interrupt service routine for processor, J. Again, Jay is one of the shoot it over here in the previous slide. It was CPU. Number two, and then the shooter over here the shoot over here secret number one. Okay.

296
00:41:53.760 --> 00:41:58.260
William Cheng: So what they will do is that they will said know that i equals two, one. So we here.

297
00:42:02.640 --> 00:42:08.010
William Cheng: I think over here, it should be noted Jay was one. Okay, so there's a typo right here. Okay. So over here, basically, they say.

298
00:42:08.370 --> 00:42:14.040
William Cheng: You know, another RJ good one to say that I'm CPU number two. Now I'm inside interrupt service routine.

299
00:42:14.730 --> 00:42:24.630
William Cheng: Guys. Sorry about the type over here. So, so over here says CPU to is now inside interim number 29 service routine and now you know the the shooter over here can actually move forward there.

300
00:42:25.110 --> 00:42:34.830
William Cheng: So what should he will do over here is that, you know, CPU number to over here said. I said, said know that I know to jail be able to walk and that what it will do is that, you know,

301
00:42:38.040 --> 00:42:48.300
William Cheng: You know, sorry. Okay. All right. Let me clear some of yours to clutter over. Yeah, I think I misread this so the CPU that's doing the shooting over here CPU J.

302
00:42:48.870 --> 00:42:58.920
William Cheng: Okay, all the other CPU overhead costs CPU I so there's why shooter. So Jay is equal to shooter shooter over here and then all the I over here are the shooting right so shoot. He is. He

303
00:42:59.670 --> 00:43:09.420
William Cheng: Is right here the shooter code over here is a CPU J there. So when you receive an interrupt interrupt number 29 the CPU I O B or actually know who was actually doing the shooting.

304
00:43:09.840 --> 00:43:17.970
William Cheng: Okay. So, therefore, what it will do is that it will remember that, you know, the shooting this down from a CPU number one over here. And then what it will do is that for for CPU.

305
00:43:18.480 --> 00:43:29.850
William Cheng: Number. I'll be here, it will say that I now inside interrupt service routine. Okay so CPU to do the CPU three or those are CPU forward to this. If they are accessing through executing threat from the

306
00:43:30.540 --> 00:43:36.690
William Cheng: Same process. Yeah. And then what it will do is that they will wait for the shooter to be done right so shooter index over here is Jay

307
00:43:36.900 --> 00:43:42.870
William Cheng: So what it will do that. It will waive the shooter to be done. So if done of Jay equal to zero, that means that the shooters the shooter is not that

308
00:43:43.290 --> 00:43:53.400
William Cheng: OK, so now all the all the other CPU, they will get stuck inside interrupt service routine. They will not go back into the, the three contacts until or the shooter let them go.

309
00:43:54.240 --> 00:44:02.610
William Cheng: Okay, alright. So what would the shooter shooter will wait for all the other CPU to go into the normal routine what they would do now is to modify the page table.

310
00:44:03.000 --> 00:44:12.510
William Cheng: Okay, so we will get all the table modify all the pace table entry that that it needs to do. And then what he will do is it will update or flash the translation look is that buffer for CPU number one.

311
00:44:13.350 --> 00:44:18.090
William Cheng: Okay, well, what can I do to to the other CPU for all the other CPU CPU. No one can do anything with it.

312
00:44:18.300 --> 00:44:22.950
William Cheng: Man, so therefore CPU number one over here knows how many page table entry that and modify

313
00:44:23.100 --> 00:44:33.750
William Cheng: It. The only modify one page table entry. Well, in that case, you will validate one transitional was have our entry if you modify 10 different entries over here, what you will do is it will actually flush the entire translational. This is over.

314
00:44:34.440 --> 00:44:43.950
William Cheng: Okay, so only CPU one knows exactly what to do over here, so they can actually modify the page table entry over here and then decide to either invalidate one entry or invalidate the entire translation, because I prefer

315
00:44:44.310 --> 00:44:50.730
William Cheng: There. And then when this is all done right. So, what it will do is that they will release all the other CPU to go back into the fair contacts.

316
00:44:50.910 --> 00:44:57.960
William Cheng: It was a done me equals one. So me over here is going to j, right, because the CPU number one over here. So what do we do this as I'm done.

317
00:44:58.110 --> 00:45:05.490
William Cheng: And now all the other CPU. What it will do is that they will see that Don J. Go to equal one. Now, they were all you know, get out of the

318
00:45:05.790 --> 00:45:17.430
William Cheng: Blue and then what they will do is that they will flush the translation local server. Okay. What it will do is that they will flush the entire translating those above her because they have no idea which page table entries. If you want has modified

319
00:45:18.990 --> 00:45:29.280
William Cheng: Okay CPU, you know, to be number one over here and modify a few patient a plan to you, but nobody knows what they are. So for all the other CPU. They have no choice but to flush the entire translating those that buffer.

320
00:45:29.820 --> 00:45:36.660
William Cheng: So in a way, you know, maybe basically for all the other CPU. From this point on, when they perform address translation, they're gonna start getting Mrs.

321
00:45:37.590 --> 00:45:43.500
William Cheng: OK. So again, this will this will actually hurt the performance of the multiple, multiple CPU CPU system.

322
00:45:43.890 --> 00:45:58.530
William Cheng: There. So this is why when you have four different audience. This is a you're you're running a multi core, you know, since then, you have for a year, you have different for different color for different CPU. So in that case, your speed up cannot be cannot, cannot be 300%

323
00:45:59.550 --> 00:46:03.150
William Cheng: Okay. So, so what happened is that whenever you perform this

324
00:46:03.780 --> 00:46:06.930
William Cheng: This you know transition because it's a buffer, shoot, shoot an operation.

325
00:46:07.200 --> 00:46:19.050
William Cheng: The first of CPU the transitional because I bought her can perform very, very well what all the other CPU when you promote you as you're done, you're going to clear the and you gotta flush the entire translation goes up offer. So all the other three CPU, they

326
00:46:19.410 --> 00:46:24.420
William Cheng: Actually wipe us out with a provider sensation, they're going to start getting Mrs. And then there was as you take a longer

327
00:46:25.440 --> 00:46:35.310
William Cheng: Okay, so this way you know you're not going to get a kick out of four times performance is going to be three times something, you know, every time you perform perform this shutdown operation. Yeah.

328
00:46:36.600 --> 00:46:41.130
William Cheng: Alright, so again, multiple CPU turns out to be always a little tricky. Yeah.

329
00:46:44.460 --> 00:46:52.530
William Cheng: Alright, so I'm going to try to explain this picture over here. So we saw all these different you know hallway element. And if you know if you have, you know, even

330
00:46:53.400 --> 00:47:01.140
William Cheng: A purchase a machine, you will see that you know the CPU has all kinds of caches. They out to caches L three cash. There's the

331
00:47:01.470 --> 00:47:07.410
William Cheng: physical memory is typically know is ran by the RAM is the one that you have four gigabyte a gigabyte 16 gigabyte on your laptop.

332
00:47:08.160 --> 00:47:15.630
William Cheng: There are also other you know you know so. So the story says them right we mentioned, we mentioned the term before, you know, primary storage and secondary storage.

333
00:47:16.020 --> 00:47:19.560
William Cheng: They're all these different kind of storage element inside the storage hierarchy.

334
00:47:20.340 --> 00:47:32.340
William Cheng: There. So, so what we can sort of think about is that when you're running your program, where is the actual data for your program. Okay, so one, you know, one we just have to think about is that the actual data for your program is actually stored inside. Inside the cloud.

335
00:47:33.600 --> 00:47:41.460
William Cheng: Okay. I mean, you know, when will you pack up data into the cloud, right. So, just in case your machine crash when your machine crash. What do you do you go back to the car and you get all the data from the cloud.

336
00:47:41.850 --> 00:47:46.560
William Cheng: Okay, so you know where we should think about is that the cloud is the the you know the cloud is where you have the actual data.

337
00:47:46.980 --> 00:47:52.920
William Cheng: Is already in order for you to access data on the cloud. What do you do, are you cache the data inside your local disk.

338
00:47:53.790 --> 00:48:02.130
William Cheng: Okay, so therefore you can sort of think about inside your file system, your file system is actually a cash for the cloud. So you bring the data from the cloud, you know, into your into your hard drive.

339
00:48:02.340 --> 00:48:09.690
William Cheng: And then whenever you try to copy data on the disk into memory, you're attaching the data from the this into your into your physical memory.

340
00:48:10.470 --> 00:48:24.240
William Cheng: Okay. And then once you you know get data from from physical memory over here. So, in that case. So what happened is that, you know, again, if you have a fancy CPU says that there's going to be all kinds of hardware caches. So the way you sort of think about is that

341
00:48:25.470 --> 00:48:34.260
William Cheng: Instead of CPU over here, we actually have translational because I prefer to translate station look as a buffer is a specialized cash all the sketches page table entry.

342
00:48:34.950 --> 00:48:39.960
William Cheng: There's also something called out to cash again when you buy the new computer you can actually look it up to see if there's any

343
00:48:40.650 --> 00:48:48.420
William Cheng: Out to catch over here. Typically the outcast sizes on the order of 256 kilobytes over here again, over time, it gets bigger and bigger and bigger.

344
00:48:48.960 --> 00:48:57.510
William Cheng: But, but in this table over here. They sort of show you what is the relative size of, you know, one of these caches and also just show you what the access time is

345
00:48:57.810 --> 00:49:07.260
William Cheng: It guys we mentioned before, the translation looks out over, over here, the access time is on the order of one nanosecond and the size over here is typically on the size of 64 kilobytes.

346
00:49:07.590 --> 00:49:13.290
William Cheng: That there's an L to catch over here in imagine this one cash, you know, inside the CPU over here.

347
00:49:13.830 --> 00:49:17.850
William Cheng: So again, there, there are sort of more specialized, you know, catch over here and there's Alan caching.

348
00:49:18.120 --> 00:49:24.690
William Cheng: Caching is that the CPU out to catch over here the access time is for on the order of four times slower than a translation. That was a buffer.

349
00:49:24.900 --> 00:49:34.110
William Cheng: And we can also see that the size over here is typically bigger. Yeah. So again, the closer that the closer you are to the CPU core the access time is going to be a faster.

350
00:49:34.320 --> 00:49:43.200
William Cheng: But then the cache size over here is going to be a little smaller than. So you probably have never, you know, seem able to catch unless your hardware person. So again, we're not gonna talk too much about it.

351
00:49:44.040 --> 00:49:52.650
William Cheng: Outside of the CPU over here. It's on the it's on the motherboard guys at the motherboard. There are some system out there, the motherboard actually has something called L three cash.

352
00:49:53.340 --> 00:49:59.820
William Cheng: There. So again, the picture that you see over here is that inside the CPU right here that the CPU over here is actually has an L three cash.

353
00:50:00.450 --> 00:50:04.530
William Cheng: So if you have multiple CPU every CPU has as a separate Alfred cash.

354
00:50:05.160 --> 00:50:12.300
William Cheng: OK. So again, if you take a hardware clause that will tell you exactly what to do LTV cash, you need to make sure that all the LTV cash that all have coherent data.

355
00:50:12.630 --> 00:50:22.200
William Cheng: Because they all cost you from, you know, from the physical memory. So again, lots of protocol that you need to implement new hardware to make sure that all the data in a consistent. So get out of the scope of this class.

356
00:50:22.650 --> 00:50:26.910
William Cheng: But what's important to understand is that every CPU potentially can have an L three cash.

357
00:50:27.120 --> 00:50:40.260
William Cheng: The access time or the author casual here that these memory are implemented using fast memory devices as I'm sorry fast memory chips, so therefore the assets time over here is the order of 10 on nanosecond or 10 times slower than inside a CPU.

358
00:50:40.620 --> 00:50:46.770
William Cheng: Yeah, so in this case the sides of the aisle three cards over here could be on the order of megabytes. So in this case over here. So to show you the I'll see

359
00:50:47.160 --> 00:50:50.730
William Cheng: I'll see casual we here for every CPU, the size that around two megabytes.

360
00:50:51.300 --> 00:50:56.310
William Cheng: Okay, and then we go across the bus over here. That's your physical memory over here. So again, this is your RAM.

361
00:50:56.580 --> 00:51:09.870
William Cheng: The size of the RAM over here. It's going to be on the order of 10 gigabyte rises somewhere between, you know, four gigabytes and 16 gigabyte. So on the average over here is is Tiger by the assets time over here. It's going to be 100 times slower than inside the CPU.

362
00:51:10.740 --> 00:51:17.370
William Cheng: Guys. Okay, this picture. So, you know, this is what you're showing over here inside the CPU. There's I want cache to cache there translation, because that buffer.

363
00:51:17.640 --> 00:51:27.600
William Cheng: Outside the CPU on the side of the CPU. There's an L three cash across the bus. There's the, the, there's a memory, a memory as much of a slower than or the author cash.

364
00:51:28.380 --> 00:51:38.250
William Cheng: Then the next level over here in the cache hierarchy over here is is actually the the the SSD the SSD is a storage device that much faster than the hard drive.

365
00:51:38.640 --> 00:51:47.370
William Cheng: Okay. I mean, today we like SSD. So here again, these are your a solid state disk, right. It's like your flash drive like your SSD on your, your machine over here.

366
00:51:47.820 --> 00:51:52.200
William Cheng: The performance on the system. They are there 1000 times slower than memory.

367
00:51:53.010 --> 00:52:05.310
William Cheng: Okay, so here's this 100 microseconds. Why are they 100 times 1000 times slower than then the memory because SSD is a device in order for you to transfer data from the device, you have to use the device driver.

368
00:52:05.940 --> 00:52:10.260
William Cheng: Guys, but again this devices over here is 1000 times smaller than physical memory.

369
00:52:10.710 --> 00:52:16.560
William Cheng: But in this case would have more than right so we can have on the order of 100 gigabyte now again today we have a lot more than that.

370
00:52:17.040 --> 00:52:24.030
William Cheng: But again, in the old days is 100 gigabyte. And then other next day in the cache hierarchy of year is called remote RAM. So what's the remote wrap

371
00:52:24.360 --> 00:52:31.920
William Cheng: The remote RAM is a, it's a physical memory on the machine sitting next to you. Okay, so if you're sitting inside a data center.

372
00:52:32.370 --> 00:52:42.330
William Cheng: Okay, be sitting inside the data center. The machine Webster, you are typically configure the same way as you are. So when you run out of memory. You can actually store data in the realm of another another machine.

373
00:52:42.750 --> 00:52:54.420
William Cheng: Because typically, that's really not feasible, but it but if it's not available, you can actually have, you know, sort of architecture like that. There. So the speed of the remote ram over here is on the order of the same as the SSD.

374
00:52:54.810 --> 00:53:02.790
William Cheng: Right, because again you need to go through, you know, it's sitting on a different machine. So, therefore, you have to go to networking protocol in order for you to get data from another machine.

375
00:53:03.210 --> 00:53:12.300
William Cheng: These the networking so fast you can actually access the remote, you know, the data on the remote memory and the speed that you get. Same thing as as as an SSD.

376
00:53:12.900 --> 00:53:18.660
William Cheng: Right. So, therefore, in this case, we're going to see that the speed is about the same. And then the storage capacity on the on the machine.

377
00:53:18.870 --> 00:53:24.060
William Cheng: If you're inside a local area where you can actually access the memory of all the other machine if they're willing to help you out.

378
00:53:24.450 --> 00:53:30.840
William Cheng: Okay. So in this case, your storage capacity over here can actually be pretty big gap. But again, if you're in the workstation room, you know,

379
00:53:31.320 --> 00:53:38.760
William Cheng: The person sitting next to you, they're not going to let you access their their their physical memory. That's okay. This is politically typically inside the data center.

380
00:53:39.120 --> 00:53:47.340
William Cheng: You need a special hardware architecture in order for you to actually use the RAM, you know, on the other machine. Yeah. The next, you know,

381
00:53:47.940 --> 00:53:53.430
William Cheng: The next step inside of cash hierarchy over here is your desk resident. This is the device. Imagine that is really, really slow.

382
00:53:53.700 --> 00:54:00.660
William Cheng: So in this case, the assets time over here is the on the order of one to 10 milliseconds. So typically was thinking about that, as several millisecond.

383
00:54:00.930 --> 00:54:11.490
William Cheng: So guys typically kind of consistent over here and now the storage capacity can go to one terabyte. I think some of you actually have, you know, a hard drive. That's two terabytes of three terabytes. So again, you know,

384
00:54:12.120 --> 00:54:22.740
William Cheng: Today, that this capacity become very, very big there. You can also do the same thing with a real remote this you can actually access the data on the machine sitting right next to you and access the disk on that machine.

385
00:54:23.280 --> 00:54:35.280
William Cheng: Okay, so this is known as remote this the remote discovery here, the access happens going to be even slower because not only you have to, you know, go go go through networking protocol. You also have to go through remote file system protocol.

386
00:54:36.780 --> 00:54:42.510
William Cheng: Okay, so I don't think we actually, you know, use some some some shared machine that are, you know,

387
00:54:42.900 --> 00:54:52.890
William Cheng: The your laptop. So in that case, typically the file system, you try to access actually sitting on a different machine. So in this case, you're going to go through a file system protocol that go to another machine over here to fetch data.

388
00:54:53.130 --> 00:54:58.440
William Cheng: There's going to be much, much slower up. But again, you can actually access a lot more storage inside your machine room.

389
00:54:58.860 --> 00:55:06.660
William Cheng: So in this case, instead of cloud. We're going to see that the storage capacity now become on the order of 1000 terabytes on the Order one one exabytes

390
00:55:07.410 --> 00:55:15.300
William Cheng: OK. And then at the end, in the end over here. Again, this is your car stories you grow go across the internet, maybe your data is stored on Mars, you can actually go across planets.

391
00:55:15.720 --> 00:55:22.470
William Cheng: To access data. So again, you know, the internet is very, very big the access have will take a very, very long time, especially if your data store on Mars.

392
00:55:22.920 --> 00:55:28.770
William Cheng: But the size over here because we don't really know. You know how you how kind of storage capacity, you can actually reach

393
00:55:29.550 --> 00:55:32.340
William Cheng: Yeah so. So again, this is one way to think about, you know,

394
00:55:33.000 --> 00:55:40.890
William Cheng: Your memory hierarchy, you have, you know, primary storage right here for your RAM. Right. So inside your CPU all these Alto and elsewhere. Now on casual we here.

395
00:55:41.190 --> 00:55:50.310
William Cheng: They are now your primary storage or they are caches and then your RAM is your primary storage your desk is the secondary storage and then maybe your store data on a tape drive

396
00:55:50.850 --> 00:55:53.520
William Cheng: You know, maybe in the cloud. Those are your tertiary storage.

397
00:55:54.270 --> 00:56:05.760
William Cheng: Okay, so, so, so, so again, when things are closer to the CPU, then they become faster, but the, you know, become faster, there's a trade off the size typical is much much smaller other things are far away.

398
00:56:06.030 --> 00:56:15.180
William Cheng: That when you go into the cloud storage capacity can become very reading that plan. So I guess these days when we go to our Google Drive on Google Drive. Can I just do a lot of data. Right.

399
00:56:16.980 --> 00:56:25.740
William Cheng: All right, so that's all I want to say about translation looks out over the next thing we're going to sort of briefly talk about our 64 bit issues so

400
00:56:26.280 --> 00:56:33.540
William Cheng: Most of the time we're talking about 32 bit CPU. So what. Yeah, what do we do with 64 bit there. So this is the end

401
00:56:34.230 --> 00:56:43.590
William Cheng: You know address translation, you know, scheme. So what they do is that they have a multi level, you know, format. Right. They take the 64 bit address over here, they're going to talk to multiple parts.

402
00:56:43.980 --> 00:56:50.160
William Cheng: Okay, so, so we're going to perform address translation multiple times. Yeah. So, so it's kind of interesting that you know even

403
00:56:50.520 --> 00:57:01.050
William Cheng: These days for the Intel CPU. They actually they're using the format of the competitor, the other competitors amp D. So this one x86 64. This one is actually an MD format.

404
00:57:01.410 --> 00:57:03.540
William Cheng: Okay, so what do we do that, it will take the virtual address

405
00:57:03.930 --> 00:57:13.530
William Cheng: So the virtual address over here is 64 bits law. And then, you know, to the 64 that's astronomical. The large number, whoever you know that nobody will ever need to address space at 64 bit long.

406
00:57:14.280 --> 00:57:21.900
William Cheng: Okay, so what it will do is that it will throw away the first 16 bits over here. There's nobody that long. So therefore, the biggest address that you ever use is a 48 bit address

407
00:57:22.230 --> 00:57:27.420
William Cheng: Okay so out of the 48 bit address over here instead of chopping into three parts. They will chop into five parts.

408
00:57:27.780 --> 00:57:33.090
William Cheng: They create these funny names were the first part of yours or a index to access the page map table.

409
00:57:33.540 --> 00:57:42.180
William Cheng: Get this map as I'm going to do our map this just Intel terminology and then again the case table. Ensure that the page map table entries over here look exactly the same as page.

410
00:57:42.420 --> 00:57:48.840
William Cheng: Entry you perform one level pay advertisers, you know, be here. So there's a physical page number you left shifted by how many been

411
00:57:49.170 --> 00:57:55.560
William Cheng: Never been busy. You get you're gonna get a second level page table. And this one is called a page directory pointed table.

412
00:57:56.100 --> 00:58:05.370
William Cheng: So again you access the page directory pointer table entry over here compared the validity bit compared to access rights over here. If everything is compatible, you get the physical

413
00:58:05.640 --> 00:58:08.340
William Cheng: Page number over here again left ship I have any business that you want.

414
00:58:08.520 --> 00:58:15.600
William Cheng: And get the third level page table over here. Use the third part of this part over here. So the third part of the page table is the same thing as a 32 bit I CPU.

415
00:58:15.720 --> 00:58:26.640
William Cheng: Is known as a page directory table. So again, you take the middle bits over here user as RE. RE index, check the validity big chat, the rewrite this over here. And then you do the next level and translation to the next station.

416
00:58:27.510 --> 00:58:41.100
William Cheng: There. So this one. Again, it's very, very important to have a good performance translational was about her, because if you don't now every time we providers ization how many pages until you have access 1234 so in this case the overhead will be 400%

417
00:58:41.550 --> 00:58:47.100
William Cheng: Okay, so for a 32 bit CPU. The over has 200% for 64 bit CPU is going to be 400%

418
00:58:47.490 --> 00:58:57.300
William Cheng: Because again, I will be too expensive. So if you have a way set associative cash hopefully all these pages table and you will be found is that a translation or was that buffer. So they have all you access this

419
00:58:57.720 --> 00:59:02.490
William Cheng: The overheads can be only for nanosecond instead of 400 nanoseconds. Okay.

420
00:59:03.330 --> 00:59:16.350
William Cheng: All right for me. There's another format on this format to over here. So again, they try to cut down one level address translation by combining the last two over here. So now your page size over here is very, very big. It's going to be two megabytes in size.

421
00:59:16.710 --> 00:59:24.180
William Cheng: So every time we get a pace fall, you need to go across the bus and reforming other two megabytes of two megabytes of data instead of four kilobytes of data.

422
00:59:24.630 --> 00:59:34.470
William Cheng: Okay, so I don't really know anybody is using, you know, which form I do people actually use so so again if you have a ruler of the high performance. This you can actually be a you

423
00:59:35.130 --> 00:59:42.960
William Cheng: Can transfer data at a very, very high speed, maybe you can actually use format to if you have a regular desktop. Most likely you're going to use format. Number one, yeah.

424
00:59:45.270 --> 00:59:51.900
William Cheng: All right, so what is the entire actually use guys so Intel there 64 bit architecture is no as I A 60 for

425
00:59:52.500 --> 01:00:04.500
William Cheng: Those of you probably have, you know, if you have read some literature you will see the is 64 people stop using it around 2012 the last company who use it is HP and HP has an architecture that

426
01:00:09.780 --> 01:00:15.420
William Cheng: Somebody started with the I can remember what you know what it's called iridium Itanium or something like that.

427
01:00:15.930 --> 01:00:21.810
William Cheng: Yeah, I think, I think called Itanium architecture. So it in America, Asia, they use intel is 64 architecture.

428
01:00:22.140 --> 01:00:31.050
William Cheng: Okay, so I 64 the basic structure is like the Digital Equipment Corporation approach, have you know pays table in the virtual address space. Okay.

429
01:00:31.380 --> 01:00:35.040
William Cheng: We're not going to talk too much about it because pretty soon to realize that this is a big mistake.

430
01:00:35.430 --> 01:00:43.200
William Cheng: We mentioned before, you know that the Digital Equipment court. They also don't perform very well Intel made the same mistake going in that particular direction.

431
01:00:43.530 --> 01:00:56.730
William Cheng: In the end, in 2012 everybody gave up on it and nobody uses pretty good architecture anymore, right. So that's why in today's Intel they're using our D amp D format. There are certain words. We're not going to talk about this, you know, at all.

432
01:00:59.400 --> 01:01:07.140
William Cheng: All right. The last part over here is virtualization. So this is chapter seven. So they assume that you have to talk about chapter four.

433
01:01:07.800 --> 01:01:14.520
William Cheng: Chapter four, there's a section called virtualization. We haven't really talked about that yet. So we're going to skip the other last part of

434
01:01:14.910 --> 01:01:20.160
William Cheng: You know the horsepower, we hear from virtualization when we finished talking about chapter for a

435
01:01:20.430 --> 01:01:28.500
William Cheng: Book about my virtual machine. Once you finish talking about virtual machine. We're going to come back to chapter seven and then talk about the hardware issue in implementing virtualization.

436
01:01:28.950 --> 01:01:34.470
William Cheng: OK, so again you know all your CPU you turn on the virtualization, you know, bit, you know, especially if you have a, you know,

437
01:01:34.890 --> 01:01:44.010
William Cheng: If you're running Windows, you can actually manipulate the virtual you know virtualization flat inside your CMOS i don't i don't think the Mac allow you to do that. So again, if you're using

438
01:01:44.460 --> 01:01:50.880
William Cheng: If you're running Windows, you will, you know, you know, you'll be late. Those kind of this. So again, I'm going to see what that's all about. Yeah.

439
01:01:51.750 --> 01:01:58.470
William Cheng: Alright, so now I finished the whole report. We're going to skip all the other stuff over here. I'm gonna take a break for video number one.

440
01:01:58.890 --> 01:02:07.740
William Cheng: And video number one here right now the video, part number two we're going to start looking at the the operating system support to use all these hard work. Yeah.