WEBVTT

1
00:00:01.979 --> 00:00:12.389
William Cheng: Okay, this is the second part of lecture 29 so we saw those three scheduling policy, we're going to look at the next one. You probably heard of it. It's called round robin

2
00:00:12.840 --> 00:00:21.210
William Cheng: It's also known as time slicing. So what happens is that when you try to serve these jobs, you know, what would you do is kind of like first come first serve.

3
00:00:21.810 --> 00:00:30.990
William Cheng: Before every job you only serve a time slice. Okay, so time size is also known as the quantum so it's called quantum because it's a small time slice

4
00:00:31.770 --> 00:00:39.330
William Cheng: Or a lot of system. I think a time slices like one milliseconds to 10 millisecond or something like that. Well, maybe that was own number

5
00:00:39.930 --> 00:00:41.940
William Cheng: So I don't know what the current you know number is

6
00:00:42.420 --> 00:00:50.310
William Cheng: So the time sizes is pretty small. So the first job, your, your server time size and then you move the first job to the end of the end around queue.

7
00:00:50.490 --> 00:00:55.110
William Cheng: And then you go to the second job you serve a time slides and he got to the end of the the the rank you

8
00:00:55.350 --> 00:01:03.360
William Cheng: He do this for all the jobs right and then you know when the first job comes to the head again, then your second, Sir. Sir, of the second time slice, you know, etc. Okay.

9
00:01:03.930 --> 00:01:10.260
William Cheng: Eventually when you finish, you know, serving out the remaining service time have a job, then the job will leave their IQ. Yeah.

10
00:01:11.550 --> 00:01:20.970
William Cheng: Alright, so that's typically one way to to to to to, sort of, you know, joy, it almost sounds like a first come first serve. But you have a, you know, you have this cycle that go back to it.

11
00:01:21.300 --> 00:01:24.450
William Cheng: Another way to joy is the way that I like to join it. Okay.

12
00:01:24.990 --> 00:01:32.910
William Cheng: So instead of sort of draw them like this. Right. So the t zero to 22. So these are the, the current remaining service time or the, you know, if you haven't started anything

13
00:01:33.390 --> 00:01:37.890
William Cheng: This will be the execution time. Okay, so t zero is the execution that with jobs zero

14
00:01:38.130 --> 00:01:45.990
William Cheng: P one is executing on which Job, Job one you said about we still use the same O notation as before that. So, the other way to look at them is to line them up.

15
00:01:46.260 --> 00:01:53.340
William Cheng: You know, based on the job right. So here is the job job and have a zero here. Job number 12345

16
00:01:54.000 --> 00:02:06.360
William Cheng: So the width of the job tells you how much remaining service time is right. So this one, you can see that the remaining service level t zero is bigger than Tier one and Tier one is the one with the smallest remaining service time, followed by T two to three.

17
00:02:08.250 --> 00:02:21.030
William Cheng: Etc. So the way that the CPU sort of serve the job is that it will go to the job zero we hear a serve a time slice right. Sometimes I was over here again is cute. So cute over will be gone. So the remaining service have what we t zero minus cute.

18
00:02:21.330 --> 00:02:29.220
William Cheng: Okay. And then what happened is that it goes to the next job over here and then serve tea out of it, right, what this one is done, the remains of his time will be T y minus q

19
00:02:29.460 --> 00:02:36.480
William Cheng: Go to the next one, go to the next one, go to the next one. Will you reach the end and it's going to go to the top again right and then it will start doing serving a time size.

20
00:02:38.190 --> 00:02:40.710
William Cheng: One one time slides out of every job again.

21
00:02:41.070 --> 00:02:54.600
William Cheng: OK. So the reason I like to look at this, you know, vertical Lee is because I can sort of think about the way that the time sliced scheduler works is the following. So what I'm trying to do over here is that he tried to slice Q Out of every, every job over here.

22
00:02:55.140 --> 00:03:00.630
William Cheng: Okay, in every round it was slice Q Out of every job. So he so anyway. It's kind of like a usually give us a really sharp knife.

23
00:03:00.870 --> 00:03:07.680
William Cheng: He would just cut it right here. So, Q is got right and now we're going to go back to the beginning again and then we're going to keep serving q at a time period of time to your time.

24
00:03:08.100 --> 00:03:09.720
William Cheng: So eventually, who's going to finish worse.

25
00:03:10.530 --> 00:03:21.270
William Cheng: What if you keep doing this, you will know that he won't have to finish first right because because we want to serve the same amount. Out of every job. So, therefore, you know, in this case, when every job got served to one.

26
00:03:21.780 --> 00:03:27.450
William Cheng: You know, whatever the time Munis one seconds of service time then at that time to I will be gone.

27
00:03:28.140 --> 00:03:32.430
William Cheng: Okay, so, you know, you know, which job is going to leave. First, right. So again, if you look at this picture over here.

28
00:03:32.760 --> 00:03:38.400
William Cheng: job. What number one over here will be the first one to leave right because everyone will be served exactly the same amount, you know,

29
00:03:38.970 --> 00:03:49.320
William Cheng: At all time. So eventually I want every job over here so key one, what then this pretty good job jobs gonna leave. Okay, so that's sort of the basic idea. I like to enjoy this way because I think it's more, you know,

30
00:03:50.820 --> 00:03:54.270
William Cheng: It gives you sort of more information when you look at it this way now.

31
00:03:55.710 --> 00:04:01.350
William Cheng: All right. Alright, so there are some extreme cases for the quantum the quantum of your damage is a time flies.

32
00:04:01.890 --> 00:04:11.760
William Cheng: When Q goes to zero. So, for those of you have taken classes, you probably have taken a queueing theory class on queueing theory I talk about a case called processor sharing

33
00:04:12.060 --> 00:04:17.070
William Cheng: Right. So in this case, you were a bunch of threads that are sharing the processor equally. So that's called process of sharing

34
00:04:17.490 --> 00:04:27.090
William Cheng: With times I go to zero. Right. So over here at the time slides, go to zero, then you're basically your CPU certainly have really, really fast. Okay, as if they are actually serving simultaneously.

35
00:04:27.510 --> 00:04:31.380
William Cheng: You know, some sort of service. I'm over here. It's going to disappear simultaneously.

36
00:04:31.710 --> 00:04:38.790
William Cheng: It's almost like water draining a train, out of these buckets. So if you take this picture you rotated 90 degrees, you think about this thing as bucket.

37
00:04:39.000 --> 00:04:44.910
William Cheng: There's like a whole at the bucket at the bottom of the bucket over here. So, all of them are draining out their service time exactly the same rate.

38
00:04:46.170 --> 00:04:53.640
William Cheng: Okay, so if q equal to zero. It's almost like water leaving the system, you're going to the right over here. Again, if you turn the picture, you'll be looking like gravity is working.

39
00:04:53.970 --> 00:05:00.660
William Cheng: So the water is going to go out. Okay, so let's go present sharing. It's an ideal life case because it's not realistic. Why is it not realistic, right.

40
00:05:00.930 --> 00:05:06.180
William Cheng: If you know so. So how can you make your smallest possible. Well, one way to do it is to make it one machine instruction.

41
00:05:06.660 --> 00:05:15.120
William Cheng: Okay, so if every time, will you finish executing one thread for one machine instruction. You go to the next word. Well, then in that case a translation look is that buffer will be totally useless.

42
00:05:15.750 --> 00:05:19.590
William Cheng: Okay, so, so of course they have all these two I belong to the same process that will be okay.

43
00:05:19.770 --> 00:05:30.690
William Cheng: But in this case, if they don't have different processes, every time when you go from 111 process to another, you're going to flush your translation, because that buffer. Also, in this case, your system is going to perform really really really terrible.

44
00:05:31.350 --> 00:05:34.890
William Cheng: Okay, because the translation. Notice that buffer is getting a hip probability of zero.

45
00:05:35.460 --> 00:05:41.940
William Cheng: Okay, so in that case is really going to be bad news. So therefore, any kind of a realistic CPU. There will never do to equal to zero.

46
00:05:42.840 --> 00:05:49.140
William Cheng: Okay. So, Q needs to be pretty big. So it needs to be pretty big because when you switch from one thread to another thread.

47
00:05:49.320 --> 00:05:57.150
William Cheng: What you're switching process even a first generation because I buffer. If you want to take advantage of the translation hooks that buffer your threat has to run for quite a

48
00:05:57.600 --> 00:06:02.850
William Cheng: While for for for quite a long time in order for the translation and notice that buffer here is going to get really hot.

49
00:06:03.450 --> 00:06:06.000
William Cheng: Right. How high is really high, but you want to be at least 90%

50
00:06:06.870 --> 00:06:14.220
William Cheng: Okay, so therefore Q needs to be large enough so when you switch from one to the other, it will run long enough so that the the the transition to say

51
00:06:14.580 --> 00:06:19.350
William Cheng: A buffer here is going to be pretty high. Well then, at that time, maybe you want to give this up to somebody else.

52
00:06:20.280 --> 00:06:25.140
William Cheng: Okay, so it's kind of a trade off. You want to have the illusion that all these threats are running parallel

53
00:06:25.530 --> 00:06:32.610
William Cheng: Right, because I'm and I'm serving this time. So it's really, really fast. Yeah, but you can be too fast, because otherwise the performance of the system is going to be really bad.

54
00:06:33.390 --> 00:06:43.710
William Cheng: Okay, so it's kind of hard to figure out. Right. So, Q is too small. That is no good. What accuse to large right if you look at this picture, what if what if this is the value of Q. This is about acute well then it become first come first serve.

55
00:06:44.910 --> 00:06:52.260
William Cheng: Okay, so we know that first come first serve is going to have, you know, performance problem, even though it's really, really fair but it but in that case it's as performance.

56
00:06:52.680 --> 00:07:07.290
William Cheng: So again, we are you know it's very difficult to figure out exactly what should be the value of cute. Okay. Some operating system to actually make cute dynamic so at runtime. When you run your optimism, a way to adjust cute. Okay, so, so if there was a, oh, you know,

57
00:07:09.150 --> 00:07:15.060
William Cheng: Why so so I guess maybe for a more advanced operating system class, they will tell you how to actually adjust you

58
00:07:15.390 --> 00:07:21.450
William Cheng: Okay but design introductory class, we're just going to say that, well, you know, some opportunities and we're just, you know, Q dynamically

59
00:07:21.780 --> 00:07:30.240
William Cheng: So this way, it will have better performance. Okay, we just leave it at that. Okay. All right, so, so, so we're going to assume, like, whew is small, but it's not too small. Right.

60
00:07:31.800 --> 00:07:40.680
William Cheng: Okay, so let's let's compute the average waiting. However, this is them. What is the, you know, so we know that job number one over here will be the first one to leave. What is the waiting time of job one

61
00:07:41.910 --> 00:07:55.200
William Cheng: Okay job one is going to leave when every job has executed 31 seconds right so so if job zero. Excuse me one second. Right. And job one over here. Excellent. One second. If every job over here. Excuse me one second. Well then job ones that really

62
00:07:55.620 --> 00:08:01.800
William Cheng: Okay, so there we can actually write a ride on a waiting time equation waiting time of one is equal to was six times t one, right.

63
00:08:03.000 --> 00:08:10.650
William Cheng: Okay, so, so we're slicing them off you know queue at a time right when when job one lead over here, you know, every job have served 31 seconds.

64
00:08:11.100 --> 00:08:25.260
William Cheng: Okay, so they have over here is if you wanted to go to 631 over here. So some people might ask why, why not t, you know, six times one minus four times queue, because we just finished servicing to one over here. All the other four job over here we have a sort of the last time slides yet.

65
00:08:26.490 --> 00:08:33.420
William Cheng: Okay, but so so the way we think about it is that Q is going to go to zero, even though it's not practical to do it, but we're doing analysis.

66
00:08:34.260 --> 00:08:46.050
William Cheng: Okay, so therefore we're going to assume t equals zero. Okay, so therefore we're doing calculus. We're not doing algebra. Right. So, therefore, to do the waiting time of job one is exactly six times to one because Q is as good as zero.

67
00:08:47.100 --> 00:08:57.600
William Cheng: Okay, alright. So, so the pictures are look like that. So after six times T one job number one is going to be right. What about the next job. Who's going to be next, right. So again, you're still slicing. You know, these five jobs.

68
00:08:58.020 --> 00:09:05.640
William Cheng: Queue at a time. Right, so eventually job number four is going to be there. So in this case, when she job number for me. Okay, so the difference between

69
00:09:06.090 --> 00:09:12.090
William Cheng: You know, the, you know, this time over here. Okay. Every job over here is going to experience that amount of delay.

70
00:09:12.750 --> 00:09:20.550
William Cheng: Right. So what does that delay right that delay this delay over here is exactly T four minus T one right because T for us here this is the

71
00:09:21.180 --> 00:09:26.040
William Cheng: Original remaining service I'm of job number four. And he was right here. So over here, this is just the difference

72
00:09:26.670 --> 00:09:39.270
William Cheng: There. So I'm going to redraw this over here, this difference is exactly between here and here. It's exactly T four minus one, right, because before, is this right and Tier one is this. So, therefore, there are differences as one over here. So what is the waiting time

73
00:09:39.570 --> 00:09:51.660
William Cheng: Job number four. Okay, so we didn't have a job number four is going to be right. So we hear this time period over here, you can see that it's going to happen, five times, right, because every time I perform these time slides, I'm only going to be executing five jobs.

74
00:09:52.380 --> 00:09:57.900
William Cheng: Okay, so therefore after five rounds of tea for minus T one. Well, then, in this case to fall asleep.

75
00:09:58.650 --> 00:10:09.030
William Cheng: Okay, so therefore it's going to be five times T four minus t one, right. So that will be the sum of all the time over here. Plus, you also have to wait for the waiting time well job number one.

76
00:10:09.630 --> 00:10:14.580
William Cheng: Right, because we have to wait for gentlemen wanted to leave first and then you have five times of people minus T one.

77
00:10:15.540 --> 00:10:20.340
William Cheng: Okay, so therefore it will look like this. Right. It's gonna be five times T four minus t one plus the waiting time

78
00:10:21.120 --> 00:10:27.300
William Cheng: Job one over here. So again, if you want to replace this by sees a six times they'll be fine. But this is more convenient right because we

79
00:10:27.930 --> 00:10:32.730
William Cheng: We need to wait for job one to me first. And then we have to wait for five times t format to see what

80
00:10:33.690 --> 00:10:42.810
William Cheng: Okay, so therefore this picture show you that initially you start with this one. Right. And then after you wait for five times 1234 or five, five times, people might have see what the job done before somebody

81
00:10:44.190 --> 00:10:55.890
William Cheng: They're all right, who's going to be next, right. So if you look at this way, we're going to, we're going to continue to slide through time slicing right so so again this time every time, will you a cost one round, you're going to serve for jobs.

82
00:10:56.580 --> 00:11:03.570
William Cheng: Okay, because it only for jobs left, right, okay. So in this case, who's going to be first, what job number zero is going to leave. Right. So what is the way to now john number zero

83
00:11:03.840 --> 00:11:13.710
William Cheng: Right, it's going to be the waiting time of job is going to be the waiting time of job number four, right, that was also going to start with and then you're going to experience four times the difference between

84
00:11:14.130 --> 00:11:26.880
William Cheng: T zero N P for Reagan, this time difference over here is t zero minus 34 is going to be 123 and four, so therefore it's going to be four times zero minus T for right plus wouldn't have done. Number four.

85
00:11:27.390 --> 00:11:31.110
William Cheng: Okay, so therefore I will look like this right when when w

86
00:11:31.590 --> 00:11:42.300
William Cheng: wouldn't have a job zero happen over here. Then I initially initially started this way. Right. And then over here, t zero minus T for happen one times two times three times or four times.

87
00:11:42.630 --> 00:11:44.190
William Cheng: So therefore going to end up with jobs are leading

88
00:11:44.850 --> 00:11:46.650
William Cheng: Okay. All right, so there's

89
00:11:46.860 --> 00:11:53.610
William Cheng: Three jobs left right the next job is going to leave is going to be job number two, right. So, here again a job. Number two, what is the way to have a job number two. Right.

90
00:11:53.760 --> 00:12:04.050
William Cheng: So now you know that you're gonna, you know, when you do have slight you only going to be time slicing three three job so it's gonna be three times. Again, this difference is going to be t two minus t zero

91
00:12:04.620 --> 00:12:12.240
William Cheng: T zero is right here, which is the previous term over here and this one is going to be plus the waiting time zero, right, this you know all the shaded area we here's where you have zero

92
00:12:12.540 --> 00:12:17.490
William Cheng: Right, and then plus three times t to minus t zero that's going to be the way to tell john number two.

93
00:12:17.910 --> 00:12:28.350
William Cheng: There so therefore you will look like this. Now, you can actually see that the original boundaries, like here right and now extended three times right 123 over here for teacher Amanda Caesar.

94
00:12:28.800 --> 00:12:40.860
William Cheng: That if we continue right job number five is going to leave an X rays over here. Job number five over here. Again, this difference is going to be T five which is this one minus t tues right here. And again, this one we are going to experience.

95
00:12:41.190 --> 00:12:49.050
William Cheng: Twice. Because when we have two jobs left. So therefore, the waiting time with job number five is going to be close to two times two, five minus T two

96
00:12:49.350 --> 00:12:56.790
William Cheng: Plus the waiting time have to again the waiting time oh two is the current a great out area that. So, therefore, when you're done, it will look like this.

97
00:12:57.120 --> 00:13:00.120
William Cheng: Okay. And finally, there's only one job, left, right. So finally, you know,

98
00:13:00.360 --> 00:13:10.320
William Cheng: We didn't have a job number three is going to be the waiting to have a job number five plus one times, you know, T three minus T five right T three minus T five right so therefore they will look like this.

99
00:13:11.220 --> 00:13:18.210
William Cheng: Alright, alright, so we didn't have a three over here. It's going to be the time when everybody lead right. The one. Some people leave earlier but

100
00:13:19.410 --> 00:13:26.490
William Cheng: We didn't have. We didn't have a three, you know, every job has finished the service, right. So, therefore, what, what has to be waiting time of three.

101
00:13:26.760 --> 00:13:32.790
William Cheng: waiting time or three has to be the sum of one plus two plus the three plus three, four plus T five plus 36 right

102
00:13:32.970 --> 00:13:41.610
William Cheng: Because the waiting time with three over here is the greatest area you can add it the way we did it, or you can add a horizontal the over here and that will be exactly t zero plus one plus the two

103
00:13:41.850 --> 00:13:51.480
William Cheng: Or 336. Okay. You can also do this using this equation over here you can expand T five into this term and then expand it to use this term, you can stand bounty for you into this term.

104
00:13:51.660 --> 00:13:57.510
William Cheng: Expand he wanting this term over here and then you will see that everything is going to cancel out and Indiana going to end up with exactly the same equation.

105
00:13:58.830 --> 00:14:03.420
William Cheng: Or is over for round robin now you know how to compute the waiting time for every job.

106
00:14:04.020 --> 00:14:12.120
William Cheng: Guys. So again, you know, if I asked you this kind of question in the final exam. You need to be able to calculate it, you know, calculate correctly. Okay. Alright, so let's take a look at our

107
00:14:12.750 --> 00:14:21.960
William Cheng: textbook example over here, right. So again, there are 168 small job right. So we're going to line them all up 160 a small job over here right 012

108
00:14:22.170 --> 00:14:29.130
William Cheng: All there is 167. And then the last job over here is going to be the big job that's 168 hour right so this is job number one in 68

109
00:14:29.730 --> 00:14:41.820
William Cheng: Okay, so when she chopped zero. What, what's your job zero leap. Okay. So Job zeros execution time is one hour. So when every job received one hour service that's when job number zero leap.

110
00:14:42.240 --> 00:14:48.540
William Cheng: Okay. So, therefore, you know, waiting time of zero is going to be able to work is going to be equal to 169 right

111
00:14:48.780 --> 00:14:53.730
William Cheng: Because what how long the 69 job every job is going to execute for one hour. That's when job number zero is gonna lead

112
00:14:54.060 --> 00:15:00.870
William Cheng: Okay. Also, this will be the same for job number one also for job number two, right, because they all leave at the same time. Right. They all have one hour.

113
00:15:01.380 --> 00:15:05.520
William Cheng: Extra time. So, this one will be equal, all the way to the waiting time a 167

114
00:15:05.880 --> 00:15:12.360
William Cheng: Right. And then finally, the last job over here. We know the waiting time is going to be equal to 336 guys, okay, what is the average waiting time

115
00:15:12.600 --> 00:15:21.660
William Cheng: The average waiting time is going to be 169. How many times have we have over here at 168 terms right plus 336 over here.

116
00:15:22.020 --> 00:15:31.950
William Cheng: Okay, that will be the last job here and divided by 169 so again wondrous it's not cancel out. This will be 168 plus 336 divided by 169

117
00:15:32.190 --> 00:15:39.330
William Cheng: Again 336 divided by 168 is going to be equal to, so therefore this number is going to be slightly less than two.

118
00:15:39.810 --> 00:15:51.210
William Cheng: Guys. So in the end, if you add them together is going to be slightly less than 160 170. So as it turns out, the average waiting time is going to be 169.9 nice slightly different smaller than 170

119
00:15:52.320 --> 00:16:01.080
William Cheng: Okay, so. So do you remember all the other average waiting time I remember is the shortage offers are the average waiting time is about 6484 86 or something like that.

120
00:16:01.560 --> 00:16:15.060
William Cheng: So it's about half that this value. Okay, the worst case for first come first serve is going to be 252 right. So again, it's going to be, you know, three times as much as the the the shortage offers. So again, so it's about one one and a half times

121
00:16:16.530 --> 00:16:24.510
William Cheng: The average waiting time for round robin okay so round robin somewhere in the middle. Right. It's not as good as 200 it's not as good as you know 85 is also

122
00:16:24.990 --> 00:16:30.570
William Cheng: So, so, so I should eat if you think you think about this right at five is right here. This is for the shoulders choppers right

123
00:16:30.810 --> 00:16:36.690
William Cheng: Over here, and then round robin over here is 170 right right here twice as much

124
00:16:36.930 --> 00:16:42.660
William Cheng: And then the first come first serve in the worst case, right. Well, we're really unlucky that the jobs are beginning I'll be here.

125
00:16:42.900 --> 00:16:52.650
William Cheng: Is going to be on the order of 255 or something like that, right. So this is equal to this time three, so the round robin is exactly in the middle between the shortage out first. And the first compressor.

126
00:16:53.610 --> 00:16:59.700
William Cheng: That. So therefore, in this case, it's you know, it's not as good as one, but it's also not as bad as the other.

127
00:17:00.270 --> 00:17:06.720
William Cheng: The reason people like wrong Robin is the next performance metric is the average waiting time as how to compute the average rating. However, as okay

128
00:17:06.900 --> 00:17:13.380
William Cheng: You need a computer various the various is equal to the average of x square. So, in this case, you know, you have 169 square

129
00:17:13.830 --> 00:17:28.410
William Cheng: Times 268 times 336 square right and the other 169 that will give you the variants of x squared, right, and then you minus the square of the various as it turns out, the, you know, if you do that this case the various is going to be at five point 99

130
00:17:29.640 --> 00:17:36.360
William Cheng: Okay, I don't know if you remember that, you know, sorry. I gotta run. So as as obvious as

131
00:17:37.950 --> 00:17:44.010
William Cheng: Okay, I don't know if you remember for the first come first serve the average waiting time is 48 points something

132
00:17:44.400 --> 00:17:50.460
William Cheng: Okay, and for the shortage offers it's even bigger. It's 50 you know 50 or 52 I can't remember exactly. Maybe somewhere around 50 something

133
00:17:51.360 --> 00:17:56.250
William Cheng: Okay, so this one is four times better than the first come first serve in the worst case,

134
00:17:57.030 --> 00:18:03.900
William Cheng: Okay, it's also better than four times. Then the shortage offers right so Georgia. First, even though the shortest that the average waiting time is small.

135
00:18:04.080 --> 00:18:12.720
William Cheng: But again, the various is as large. So this one over here, the variance is actually pretty small. Right. So again, you know, shortage. Our first and look like this. This one, why should look like this.

136
00:18:14.040 --> 00:18:25.770
William Cheng: Okay, so, so, so why is it any good. Right. So. So again, if you look at the average over here, the average over here is equal to 170 right for the shortage. Our first over here, the average over here is 85

137
00:18:26.790 --> 00:18:31.080
William Cheng: Okay. So in this case, every job, what we hear they're waiting time is actually not very good.

138
00:18:31.740 --> 00:18:39.150
William Cheng: Okay but but but in the US, all these jobs to say well you know your your execution time is one your average waiting time is going to be 170

139
00:18:39.510 --> 00:18:50.730
William Cheng: Are you okay with that. Right. So the job is to do the job well said well I know my execution time is pretty bad. Right. But at least you know I'm actually doing pretty well because all the other job there the waiting time is about the same as me.

140
00:18:52.050 --> 00:18:58.980
William Cheng: Okay, so if you look at all the other job if you look at the actual number. All the other job actually have exactly the same waiting time right except for the big job.

141
00:18:59.370 --> 00:19:10.200
William Cheng: Okay, so again, the average, you know, it's kind of funny, right, because, because in this case all the waiting time are on one side and they have one job over here with a big way to time. So the average out to be 100 and, you know,

142
00:19:11.220 --> 00:19:18.510
William Cheng: The average out to be 170 but but for most of the job, you know, the extra weight happens to be 100 is going to 169

143
00:19:19.710 --> 00:19:26.490
William Cheng: Okay, so in this case the wrong Robin seems to be very, very fair because for every job even though the average is not very high.

144
00:19:26.850 --> 00:19:35.490
William Cheng: Concern is the average very, very low, but at least all these I feel like they are not being treated unfairly because all the other jobs suffered the same kind of fate.

145
00:19:36.750 --> 00:19:42.450
William Cheng: Okay, so, so, you know, again, the job is miserable but at least everybody else is also miserable. So therefore, it doesn't really feel so bad.

146
00:19:43.410 --> 00:19:50.520
William Cheng: Okay, so that's why we like round robin because appears to be more fair, you know, then you know storage offers offers compressor.

147
00:19:51.390 --> 00:20:02.640
William Cheng: Whereas the first one first survey, it is fair because every job eventually will get serve, but the round robin over here feel more some more fair because all the jobs you know they experience about the same waiting time

148
00:20:03.930 --> 00:20:10.590
William Cheng: Alright. So again, that's a different kinds of fairness. Right. Which one is more fair, right. We'll get you get to judge. Okay. All right.

149
00:20:11.370 --> 00:20:18.240
William Cheng: So, you know, round robin plus five for appears to be fair. So, so here's this. And typically what people will say is that round robin is five all

150
00:20:18.480 --> 00:20:27.870
William Cheng: Right. But as you can see that over here five boys really not that important. Right. And the. Why does it matter if I serve this job for us, or I served job number four for us as long as I'm doing time slicing

151
00:20:28.800 --> 00:20:36.600
William Cheng: Okay. Five, Four is really not important right, it could be last come first serve. It could be random, whatever, it doesn't really matter. Okay, what's important. Over here is round robin

152
00:20:37.440 --> 00:20:48.750
William Cheng: Okay, so we do round robin also, it's also fair by the same metric as first come first serve is fair because there can be no starvation. Right. Why is there no starvation, because in every round every job gets served

153
00:20:49.590 --> 00:21:00.540
William Cheng: Okay, so therefore it's impossible for a job to start. Okay, so that's why I sort of people, you know, like the ideal round robin so server. Maybe that's why you have heard of it. All right, because it's a sort of a popular scheduling discipline.

154
00:21:04.140 --> 00:21:12.240
William Cheng: Alright, so let's talk a little bit about fairness fairness has been studied to death because you know it was you know embed a long time ago.

155
00:21:12.990 --> 00:21:14.400
William Cheng: You know, even before COMPUTER SIGHS

156
00:21:14.820 --> 00:21:22.920
William Cheng: Economics, you know, the people they study fairness. Right. What did that the study of fairness, right, because one of the things that they do is that they advise you know the kings and

157
00:21:23.130 --> 00:21:33.150
William Cheng: Whatever. Right. So for example, if I'm a king, right, I have, you know, $1 million, I need to give it away to my citizens, right, what should be the right way to distribute my money to the citizens.

158
00:21:33.480 --> 00:21:41.310
William Cheng: Okay, so, so you will hire a economists economists would tell you what to do. Okay, so, so while we can do it as as a, you know, if I have 1000 citizens, I have $1 million

159
00:21:42.000 --> 00:21:51.330
William Cheng: gave out $1 million. How about this up to them. Right. One obvious way to do, is I'm not the 1 million by $1,000 everybody get $1,000. Is that fair

160
00:21:52.230 --> 00:21:59.160
William Cheng: I mean, how can it be not fair. Right. So. So again, if you do that, some people say well that's not fair. Okay. The problem is that fair and it's very, very difficult to define.

161
00:21:59.850 --> 00:22:07.260
William Cheng: Okay, so why would somebody said, Not fair. Right. So one person who said well you know that that person. He only wants you know you know he or she only wants $1

162
00:22:07.950 --> 00:22:12.600
William Cheng: Why do you give that person $1,000 you're wasting precious resource that's not fair.

163
00:22:13.410 --> 00:22:24.330
William Cheng: Okay, so you should find out what everybody wants right if that person only wants one $1 you are not allowed to give that person more than $1 because that will be unfair to the rest of us, because we need a lot more than $1

164
00:22:25.980 --> 00:22:32.070
William Cheng: Okay. So, therefore, if you give that person more than what that person want you'll be unfair to the rest of it is that a good argument.

165
00:22:33.060 --> 00:22:40.110
William Cheng: Was that again. So yeah, it's very difficult to figure out what fairness is right, because you know it's really tricky question.

166
00:22:40.440 --> 00:22:47.220
William Cheng: Okay. So people started to do that we're going to talk about one of the sort of the result on economics. Right. It's called max mean fairness that

167
00:22:47.550 --> 00:22:54.720
William Cheng: Are the descriptions little where it says a fair service that maximizes the service of the customer receiving the poor service.

168
00:22:55.110 --> 00:23:03.630
William Cheng: Where we're going to look at all the customers see which customer is going to receive the poorest service and we're going to make sure that that customer get as much as that customer desert.

169
00:23:04.020 --> 00:23:15.510
William Cheng: Well, so again if I'm the king over here, the customer over here with my citizens, right, I need to look at the customer who you know who's requesting the least amount because that person will receive the poor service.

170
00:23:15.900 --> 00:23:19.140
William Cheng: Okay, so therefore I need to make that person as happy as possible.

171
00:23:19.830 --> 00:23:33.600
William Cheng: Okay, so that's me. In fairness, okay, alright. So, maximum fairness has, you know, I guess people studies are dead. They actually come up with certain kind of criteria. So this way we can actually implement it. So number one, the first rule we hear is that no user received more than its request.

172
00:23:34.830 --> 00:23:41.490
William Cheng: Okay, so, so they already defined inside maximum fairness. If somebody asked for $1 you are not allowed to get that person to dollars.

173
00:23:42.450 --> 00:23:50.880
William Cheng: Okay, so if somebody asks for $1. Are you allowed to give that person and 50 cents, while he has. Yes. Right. Yeah, as long as you don't bother this rule. Nobody gets more than what they asked for.

174
00:23:51.480 --> 00:23:57.540
William Cheng: Okay. All right. So number two is it says no, it's really weird definition. No other allocation scheme satisfying condition one

175
00:23:57.750 --> 00:24:05.760
William Cheng: Has a higher minimum allocation, then the math mean fairness, right. So, so in some way. They're sort of talk about some kind of optimal condition that this is the best you can do.

176
00:24:06.240 --> 00:24:11.010
William Cheng: Okay, so in this case we're going to maximize again the minimal allocation. Right. That's why it's called maximum fairness.

177
00:24:11.220 --> 00:24:18.930
William Cheng: Okay, number three, it says condition to remaining recursive Lee true as we remove the minimum user and reduce the total resource accordingly.

178
00:24:19.290 --> 00:24:25.770
William Cheng: Okay, so, so if you know. So that's it. Oh, my citizen over here. Tell me, I asked him, so I have to tell me how much you want

179
00:24:26.280 --> 00:24:36.480
William Cheng: Okay. One person said, I only want $1 everybody asked for more than $1. So what I will do is, that was a while you are the least greedy person and you only last $1 so you're going to get your dollar. And now you can leave.

180
00:24:36.960 --> 00:24:53.550
William Cheng: Okay. So guys, what do I have left. I have one 1 million minus $1 and now I have 990 999 of people. LAUGH Okay, so I'm going to sort of started my algorithm again. Okay, I'm going to sort of find out you know who is the person that asked the least amount and then that person as

181
00:24:54.870 --> 00:25:02.130
William Cheng: That person is not very, very greedy and I can satisfy that person request. I'm going to satisfy that person first and then I'm going to keep doing this over and over again.

182
00:25:03.090 --> 00:25:05.220
William Cheng: Okay what if everybody ask for too much.

183
00:25:05.970 --> 00:25:16.290
William Cheng: Okay, so let's get started. As I started out with $1 million everything I have 1000 people everybody asked for $2,000. Okay. Some people ask for 2000 some new Apple threes out and some people ask for $1 million

184
00:25:16.920 --> 00:25:20.730
William Cheng: Okay, that's the person who asked the smallest amount is going to be a $2,000

185
00:25:21.660 --> 00:25:24.690
William Cheng: Okay, so in that case, how should they give money. Right. I mean, there's no way you know because

186
00:25:24.930 --> 00:25:35.880
William Cheng: I know that if I divide my my money equally everybody will only get $1,000 so even the person with the smallest requires more than the, the, the average. So in this case, everybody will get $1,000

187
00:25:36.780 --> 00:25:49.920
William Cheng: Is that fair. Well, some people say well that's not fair I because that person asked for $2,000 right. So, therefore, that person get 50% of what that person. Well, I want $1 million only if I only get you know 1000s of what I will ask, well, how can that be fair.

188
00:25:51.690 --> 00:25:57.390
William Cheng: Guys will get fairness is very, very difficult to define. Right, so, so, so in this case again according to max mean fairness.

189
00:25:58.020 --> 00:26:08.790
William Cheng: Okay, when I am in it. So if I take all my money evenly divided out by among all you know all the people asking for money if that's bigger than the minimum request, everybody will get the same

190
00:26:09.870 --> 00:26:13.650
William Cheng: Okay, that's how my algorithm work. If you're not happy about it. Too bad. Okay.

191
00:26:14.220 --> 00:26:22.380
William Cheng: Right, so, so, yeah, basically the idea is that if you need too much. Well, then in that case. In the end, if I don't have enough resources, you're going to suffer more if that's actually

192
00:26:23.220 --> 00:26:30.780
William Cheng: If that's actually what you if that's what you actually need right alright so so anyways this is the algorithm. Right, so

193
00:26:31.440 --> 00:26:44.010
William Cheng: If you apply this to to, you know, I guess I'm sort of a totally, you know, I can also do this right, so, so I'm going to start with my total capacity right my capacity over here is going to be $1 million over here.

194
00:26:44.310 --> 00:26:50.370
William Cheng: Okay, so I have 1000 jobs you know again well 1000 citizen over here. So, and it's going to go to 1000

195
00:26:50.670 --> 00:27:00.600
William Cheng: Yeah, so excited over here is going to be a request for job i right again this will be the request from Citizen number. I'll be here. So what I will do is I will sort them based on their request.

196
00:27:01.290 --> 00:27:07.800
William Cheng: Okay. So on the left hand side over here is going to be the person with the smallest request on the right hand side over here is going to be the person with the largest request.

197
00:27:08.220 --> 00:27:17.610
William Cheng: That. So in this case, what I would do is that I will take all my capacity all my $1 million over here, divide by 1000 I'm so see divided by n over here. I'm going to get it going to draw a line over here.

198
00:27:17.970 --> 00:27:24.750
William Cheng: Okay if everybody's involved that line right if everybody's request is above that line. Everybody getting getting caught him out. And then my algorithm is that

199
00:27:25.890 --> 00:27:33.450
William Cheng: Okay, so that would be the easiest case if everybody if everybody is above it. That's then the smallest. You know, the one with the smallest request that one will be about it.

200
00:27:33.900 --> 00:27:41.010
William Cheng: Right. So all you have to do is check one case, if this one is above CRM that my algorithm as Terminator everybody gets to see over and

201
00:27:41.790 --> 00:27:49.980
William Cheng: Over again if it's not the case. What I will do is I will look for the person with the smallest request and that will always be x one, right, because I saw them already.

202
00:27:50.250 --> 00:27:59.940
William Cheng: Yeah. So in this case, I'm going to give a person citizen number one over here, all the, you know, all the money that person that has required as a request it. And then this person is going to be the system.

203
00:28:00.750 --> 00:28:04.950
William Cheng: Now. So now, how much money do I have left. Well, what I have left over here is going to be CD.

204
00:28:05.220 --> 00:28:14.070
William Cheng: Minus x one. That's my total capacity, left, right, how many cities in our lap while there's n minus one citizen are left. And now I'm going to continue to run my algorithm, you know, over and over again.

205
00:28:14.880 --> 00:28:20.970
William Cheng: Oh, that's okay, what would I do over here. So now I saw all my citizen over here by their request size right

206
00:28:21.120 --> 00:28:28.140
William Cheng: I device C minus x, y and divided divided by n minus one to online over here if everybody's involved the line. Everybody get exactly this amount

207
00:28:28.290 --> 00:28:40.320
William Cheng: If one person is below the slide I go to X to overhear satisfy excuse requests and that excuse me, the system over here. So now what is my remaining capacity is going to be c minus x one minus x two, right.

208
00:28:40.500 --> 00:28:45.450
William Cheng: And now, what's my population is going to be minus two. Right. And then I'm going to continue to do this over and over and over again.

209
00:28:46.680 --> 00:28:54.090
William Cheng: Okay, so this is maximum fairness. Okay, I'm gonna claim that this is exactly the same approach as round robin

210
00:28:55.410 --> 00:29:04.980
William Cheng: Okay, so why is that why why is this the equivalent to Robert right so so the other way I can give money over here. Right. So. So one way is I can run this out where that the other way is I can just give everybody one penny at a time.

211
00:29:05.310 --> 00:29:11.100
William Cheng: Then I'm going to give this person one penny. If there's a one penny. This person one penny. This person one penny all the way to end over here.

212
00:29:11.280 --> 00:29:20.610
William Cheng: And then we'll go to the beginning. Over here give everybody another penny penny penny penny. So basically I'm going to sort of slicing their request of one penny at a time, who's going to finish verse

213
00:29:21.090 --> 00:29:28.050
William Cheng: Well as one hope here is going to finish first right if x one is bigger than the average eventually I'm gonna run out of money. So get every will get exactly the same amount

214
00:29:28.710 --> 00:29:36.090
William Cheng: Okay. Otherwise, x, y is going to finish first right and then I'm going to continue this person, but I believe I'm going to continue slicing this you know one penny at a time.

215
00:29:36.300 --> 00:29:47.430
William Cheng: Eventually X two is going to lead actually zombie. And so this algorithm that I just run over here. It's exactly the same as round robin that's why people like round robin because Robin. Robin achieve max mean fairness.

216
00:29:48.690 --> 00:29:56.940
William Cheng: Okay, so is that the only kind of fair and so I'm unclear. Again, we would talk about how to define fairness, you know, you know this, but either way. Some people can object to that.

217
00:29:57.180 --> 00:30:09.720
William Cheng: Our definition. So in that case, yeah, we are those people want to be happy. Right. But if people think that this this fear is actually pretty good. Well then, you know, using process of sharing or using round robin we can actually achieve this kind of fairness.

218
00:30:10.680 --> 00:30:14.070
William Cheng: Okay, right. So, so anyways. So this basically you know process to. Sure. Okay.

219
00:30:15.780 --> 00:30:23.700
William Cheng: All right, so, so that's all you know Robin scheduler. So the next time. The next thing when I look at is scheduling for interactive jobs right so now

220
00:30:23.850 --> 00:30:31.410
William Cheng: There's somebody sitting in front of the terminal using the machine over here. And now we need to make that person as happy as possible, right. So this guy's we need to schedule job.

221
00:30:31.860 --> 00:30:42.840
William Cheng: You know, based on priority right any job that belong to the interactive user needs to be higher priority and any job that belong to the sort of the background job or they should get lower priority.

222
00:30:43.350 --> 00:30:50.910
William Cheng: Okay. And also we're going to assume that we don't know the length of the job anymore. Okay, so before we know the length of the job. Well, actually, for the round robin case.

223
00:30:51.300 --> 00:30:57.360
William Cheng: For the round robin case do we actually care, you know, what is the, you know, what is the service time for every job.

224
00:30:57.870 --> 00:31:07.650
William Cheng: Well, we don't really care. We just time slicing away. We don't really care. So as it turns out, we already see a scheme that doesn't really care about, you know, the, the, the, the execution time

225
00:31:08.130 --> 00:31:12.660
William Cheng: Guys, so that would be another big advantage around Robin that it doesn't really care about execution high

226
00:31:12.960 --> 00:31:21.660
William Cheng: Right, it would just slice away once. Time flies away 111 time size at a time, and eventually it's fair and everybody's happy. So so so yeah that's pretty good. Yeah.

227
00:31:22.230 --> 00:31:32.730
William Cheng: Alright, so now the entire job over here. The reason we sort of see say that interactive job, you know, we don't really know the extra time is that the interactive user when they're running commands. Nobody knows what the user is running.

228
00:31:33.270 --> 00:31:41.070
William Cheng: Okay, the user might pick up a game or my southern how the style. Right, so, so, so typically, you know, for the interactive user. We have no idea what the interactive user is going to do right

229
00:31:41.190 --> 00:31:50.010
William Cheng: So therefore, it's reasonable to consider the case where we don't know the execution type of job that. All right, so. So in this case, you know,

230
00:31:51.540 --> 00:32:00.720
William Cheng: The threat will give out the CPU, you know, voluntarily and they will block for user input. Right. So typically, the wiring is that when the user do something right. It's like, well, you're running a warm up on a warm up to

231
00:32:01.230 --> 00:32:07.980
William Cheng: You're doing something interactively right so you're going to run a program that will keep asking you for input. Okay, so most of the time, you know,

232
00:32:08.310 --> 00:32:11.190
William Cheng: You know, the interactive job, they will give up the CPU pretty quickly.

233
00:32:11.790 --> 00:32:18.900
William Cheng: Okay, we mentioned before I their CPU job bound job there IO bound job the CPU bound job can be reading from this. They can also be reading from the terminal.

234
00:32:19.410 --> 00:32:24.450
William Cheng: Okay, so one characteristic of interactive job is that, you know, they will actually block file.

235
00:32:25.440 --> 00:32:34.590
William Cheng: Okay, so the reason we're sort of trying to analyze this way is that we want to write our operating system without really knowing exactly, you know, which one is a fantastic job interactive job and which one is not

236
00:32:35.220 --> 00:32:39.060
William Cheng: Because, you know, it's kind of very difficult to actually figure out which one is impractical. Which one is not

237
00:32:40.050 --> 00:32:50.310
William Cheng: Okay, so therefore we can try to use some characteristic of a job. So if the job, you know, but basically give us if you right away and go sleep on a terminal. Well, then we know that most likely that's going to be an interactive job.

238
00:32:51.270 --> 00:32:57.930
William Cheng: Okay. But if that job go sleep on a dis que, is that an interactive job or not, whether we don't really know. Right. Because just like warm up to right warm up to, you know,

239
00:32:58.050 --> 00:33:03.450
William Cheng: You are interactive user you're running simulation, but you're, you know, the program that you run will take a long time for it to run

240
00:33:03.870 --> 00:33:16.530
William Cheng: So in a way, it's sort of become you know sometime it was I obi sometimes Seba. I mean, the point I'm trying to make is that it's very difficult to tell exactly, you know, we job is interactive, which I which belongs to the ppl to the background job.

241
00:33:17.790 --> 00:33:26.340
William Cheng: Okay, so. So for people who try to schedule for interactive says that if you want to make sure that the interactive user always received a response while then it become a little tricky.

242
00:33:27.180 --> 00:33:28.680
William Cheng: Okay. So you sort of need to, you know,

243
00:33:29.490 --> 00:33:38.970
William Cheng: You need to try to inactive user. The user job but you know the interactive user can also do something like the simulation. I will do a warm up to which will eat up the CPU for a very long time.

244
00:33:39.240 --> 00:33:44.730
William Cheng: Or they can even you know this, you know, I don't know if you have run you know program with the W people

245
00:33:45.450 --> 00:33:52.020
William Cheng: So what it will do, they will do the semi the BLS I simulation or something like that. Those things are memory hog and those things doesn't give up CPU.

246
00:33:52.500 --> 00:33:56.550
William Cheng: OK. So those things are completely CPU bound and they might be run by interactive user

247
00:33:57.330 --> 00:34:04.500
William Cheng: Okay, so therefore, it might not be a good idea to try to sort of figure out which appealing to the interactive user because the entire user might be do things in parallel.

248
00:34:04.650 --> 00:34:10.260
William Cheng: Some of the job, you know, turns out that they will actually use up a lot of CPU some good job over here. They're actually very nice to the CPU.

249
00:34:11.250 --> 00:34:19.830
William Cheng: OK, so maybe it's actually a good idea to look at the behavior of your job and determine, you know, you know, which which kind of a job will have higher priority and we kind of job will have low priority.

250
00:34:20.130 --> 00:34:28.710
William Cheng: Again, sort of forget the notion that you know, that sort of job be happy until the interactive user and if they've been to the interactive user, we have to make sure that they get high party.

251
00:34:29.250 --> 00:34:35.010
William Cheng: Okay, because if those VSS simulation job and nobody else will get the CPU. Okay. All right.

252
00:34:36.000 --> 00:34:42.480
William Cheng: So, so, so, again, the basic idea over here is I'm going to inspire the queuing okay but we need to sort of watch out for the behavior of jobs there.

253
00:34:43.350 --> 00:34:49.440
William Cheng: Or so. So one of the way that we can do this is that we're going to just round robin hood party because we because we know Robbins kind of fair

254
00:34:49.770 --> 00:34:56.310
William Cheng: Right have low variance and all these kind of good characteristic over here. You don't have to know the execution, how we were job. So it has all the right characteristics.

255
00:34:56.490 --> 00:35:03.480
William Cheng: And now can use three different priority queue. Right. This one will be high priority. This will be low priority. The middle one over here. Maybe middle party over here.

256
00:35:03.840 --> 00:35:09.360
William Cheng: Okay. So in this case, what happened is that when the Java right if it's high priority cutie. We're on here. If the media party. Q.

257
00:35:10.020 --> 00:35:22.080
William Cheng: Sorry immediate party job. You'll run here. It was a low priority job here at the bottom. Few over here. Then we're going to rush street party. That means that you are not allowed to touch the middle Q unless the high priority queue is completely empty.

258
00:35:23.250 --> 00:35:30.450
William Cheng: Okay, because, you know, we're really serious about party right so if there's a job that has high priority, it needs to run before any of the other jobs.

259
00:35:30.900 --> 00:35:37.500
William Cheng: Okay. Similarly, you are not allowed to touch the low level Q over here unless all the first to q over here. It's going to be completely empty.

260
00:35:39.150 --> 00:35:50.910
William Cheng: Okay, so in this case what the question is how do you actually assign a priority right if you let people to choose what party they want. What if they know that this is how you schedule the rank you everybody wants to be the high party. I have already job.

261
00:35:51.660 --> 00:35:56.730
William Cheng: Okay, so that's a problem. So, so actually in Microsoft programmers manual. They actually have something, how they actually right you

262
00:35:57.090 --> 00:36:04.890
William Cheng: Have a paragraph to say that, you know, well, you need to choose a party, you need to be nice with for the rest to the rest of the system, you need to choose a party level that's suitable for you.

263
00:36:05.550 --> 00:36:11.370
William Cheng: Okay, so guess what every program will choose, they will all choose the highest priority high because in the end they want their product to look the best.

264
00:36:11.610 --> 00:36:21.840
William Cheng: And so therefore the actual hierarchy, right. So, so this is really not a good way to go if you let the user choose their watches the highest priority. Right. So in the end, you're only the Microsoft background job. There'll be running the low priority queue.

265
00:36:22.470 --> 00:36:33.090
William Cheng: Okay, so in the end what Microsoft did is that they use dynamic priority. Right. So I mentioned before you can you can you can have that I make, you know, a quantum a time slides. You can also have dynamic priority.

266
00:36:33.900 --> 00:36:43.320
William Cheng: So this is called a multi level feedback Q over here I have a higher priority queue have a low priority queue. And this one is medium high and this one is medium low. I mean, can use as many levels as you want.

267
00:36:43.860 --> 00:36:56.070
William Cheng: Okay, so the idea here is that I'm going to observe the behavior of these jobs if they are nice to the scheduler. I'm going to keep them and high priority, if they are nice if they are not nice to the scheduler. I'm the lowest party.

268
00:36:56.430 --> 00:37:01.170
William Cheng: Okay, what does that mean that are nice to be able to the to the scheduler. What that means that they want to use a lot of the CPU.

269
00:37:02.010 --> 00:37:05.490
William Cheng: Okay. So, therefore I'm going to, sort of, you know, look at the behavior of

270
00:37:06.210 --> 00:37:13.410
William Cheng: The jobs. Okay, if they try to hold on to the CPU to heart, well then I'm gonna I'm gonna actually I'm gonna be great. Then I'm going to lower their party.

271
00:37:13.830 --> 00:37:21.270
William Cheng: Okay. All right. So, so the top level one over here. This is going to be a time slice Q over here, right. So we're gonna have a bunch of job over here. When they arrived.

272
00:37:21.450 --> 00:37:28.890
William Cheng: We're going to do first come first serve. But again, we're applying time slicing. So we're gonna we're gonna for the first job over here, we're gonna we're gonna serve it for a time slice

273
00:37:29.160 --> 00:37:37.770
William Cheng: If this job doesn't leave you know if this job doesn't give up the CPU voluntarily. Then we're going to say that while this guy's you are a CPU bound job.

274
00:37:39.090 --> 00:37:47.970
William Cheng: Okay, so when you receive your first time slice. If you don't give up the CPU voluntarily. You are a CPU bound job. So therefore, we're going to schedule to the medium high poverty level.

275
00:37:48.360 --> 00:37:53.850
William Cheng: Okay, so therefore, in this case, instead of coming back to the high priority queue will you finish your time. So you're gonna you're gonna get downgraded

276
00:37:54.270 --> 00:38:01.710
William Cheng: Okay, so once you get down with that none of the job over here's a lot to execute until the high priority, you know, the queue up here is completely empty.

277
00:38:02.250 --> 00:38:11.760
William Cheng: Okay. So in this case, every job in the high priority here will get sir right either they leave the CPU right away when they leave the CPU voluntarily next time when it come back. It's going to be a high priority job again.

278
00:38:12.660 --> 00:38:19.590
William Cheng: Okay, if it turns out that it doesn't give up CPU, they will come. They'll get down with it and they will all go to the medium party queue. So, so it's

279
00:38:19.770 --> 00:38:26.310
William Cheng: The same time you're you're serving all the job in the high bar DQ all the other tools over here. There'll be completely frozen.

280
00:38:26.790 --> 00:38:37.800
William Cheng: Right, so they might get at it you know when when the job gets done greater. In the meantime, there are more job is going to be arrived, they all going to be a higher priority job. So therefore, it may be a while before you start serving jobs and low priority queue.

281
00:38:39.000 --> 00:38:49.410
William Cheng: That and then you know the high bar to kill over here is going to be completely empty. Right. So, and this guy's you start serving serving the middle part EQ over here again the medium high priority queue over here, right, medium, high party go yeah

282
00:38:49.800 --> 00:38:55.320
William Cheng: So in this case you get, again, you do the same thing you serve a job for a time slice it would give out the CPU. Great.

283
00:38:56.100 --> 00:39:02.700
William Cheng: Okay, then that job will leave and next time when it comes back into the regular they become a higher priority queue. Again, why does it become a high priority here.

284
00:39:03.150 --> 00:39:10.800
William Cheng: Well, again, it depends on the scheduler. Okay. Some scheduler will have a comeback as a highest barbecue. Some people actually remember the priority of this threat.

285
00:39:11.040 --> 00:39:17.820
William Cheng: Okay, so what, how do you remember what you put inside of threat control blah, right, so next time when this one. Come back, come back and visit. Thank you, they will actually remember to go back here.

286
00:39:18.300 --> 00:39:23.460
William Cheng: You guys will get their variation in this multi level feedback you and Microsoft also have their own variation

287
00:39:23.970 --> 00:39:35.670
William Cheng: Okay, so everybody. So a lot of people will use something similar to this video escape and not exactly this game. Yeah. Alright, yeah. The idea here is that every job over here with serve a time slides. If you voluntarily give up the CPU, while in that case.

288
00:39:36.240 --> 00:39:45.210
William Cheng: You know, you will leave the system. And when you come back, depending on the brand new policy and also when you're serving all these job over here. If a new job around over here. What's happened is that

289
00:39:45.660 --> 00:39:49.350
William Cheng: You know we can do either preemptive scheduling enough. We have the scheduling.

290
00:39:49.980 --> 00:39:59.730
William Cheng: You know, if you do practice scheduling. Well, then, in this case, you have the job, no SQL inside of CPU, they will get put back at the head of this Q over here and then you switch to the new job over here.

291
00:40:00.240 --> 00:40:05.250
William Cheng: Okay, if you're doing non previous scheduling because you want to, you know, give this this thread.

292
00:40:05.700 --> 00:40:15.660
William Cheng: Give this a chance to try to see where there's going to give up a CP voluntarily. So in this case you will wait until the time sizes over when the time size is over. You can you can you know that this one will lead the

293
00:40:16.500 --> 00:40:21.240
William Cheng: Lead ranking order will get done greater at that point, you go, sir, you know, sort of a high party here.

294
00:40:21.930 --> 00:40:26.280
William Cheng: Okay, so again, there's no one way of doing this different Japanese descent. They might, you know,

295
00:40:27.090 --> 00:40:37.980
William Cheng: Make a different kind of decision. Okay. Alright. So again, the idea here is that every job over here will get serve, and then we'll get that all done greater for the first two years completely empty, then you start serving the third Q over here and then continue on that.

296
00:40:39.180 --> 00:40:48.660
William Cheng: Alright, so this is called a multi level feedback queue. So Windows do some kind of a version of this body of the multi level feedback, you know. So again, there are very, you know,

297
00:40:49.740 --> 00:40:57.390
William Cheng: Alright, so the idea here is that when a threat arriving to the wrong kill it gets highest priority. Okay, we're going to the, you know, the scheduler observe what it does.

298
00:40:57.720 --> 00:41:01.740
William Cheng: If it uses up a full time side we're going to be clear that a CPU bound job and

299
00:41:02.430 --> 00:41:15.450
William Cheng: I'm going to downgrade at that otherwise if it blocks before you start to start to downsize with them. We're going to declare that this one is a IO bound job. So again, it will give us the CPU for muted. So I oh but the general terminology is that it's IO bound job.

300
00:41:16.080 --> 00:41:23.490
William Cheng: Okay, so that means that it gives you the CPU quickly. So in this case, we're going to update the 300 blog over here. Make a note to say hey you know this is a good job.

301
00:41:23.790 --> 00:41:29.250
William Cheng: Okay, so from this point on, maybe we need to treat this job extra special because we like IO bound jobs right

302
00:41:29.430 --> 00:41:37.200
William Cheng: Because as I Oban job come into the wrong key over here. If all the jobs that IO bound when there was, it was going to happen. The throughput at the wrong he was going to be really, really high.

303
00:41:38.280 --> 00:41:45.930
William Cheng: Right, because everybody wouldn't get on the run queue, you know, if they're if they're all about. That means that when they get into the CPU within a time size, they all give up CPU.

304
00:41:46.770 --> 00:41:52.200
William Cheng: Or so if we do that, this the schedule is going to look really really good because it's serving many, many jobs for a second.

305
00:41:52.830 --> 00:42:04.560
William Cheng: You know, and then, and that's what we want. Okay. So, therefore, we're going to actually tell all of the programmers to say that we're going to treat the IO bound job, you know, really, really nice. So therefore you should make your job. I'll bounce it this way.

306
00:42:05.610 --> 00:42:10.470
William Cheng: This way, we'll get really, you know, good good treatment at the schedule. Yeah. Alright.

307
00:42:11.970 --> 00:42:21.030
William Cheng: Alright, so, so, so over here you can update some information. You can keep track of a statistical good job to remember that this is actually, it was a good job. So maybe we should be treated better and better in the future as well. Yeah.

308
00:42:21.240 --> 00:42:28.710
William Cheng: There are many things you can do right when you start, start talking about, you know, using heuristic. You know, we start using white here so you can use any kind of here's a great one.

309
00:42:30.180 --> 00:42:35.490
William Cheng: All right, what about the job at the bottom over here. I mean, we said I, you know, you're not allowed to have starvation.

310
00:42:35.790 --> 00:42:42.690
William Cheng: Right. So if all these three shows over here, constantly. There are kind of busy. The jobs over here event. So in this case, they would never run

311
00:42:43.260 --> 00:42:47.490
William Cheng: Okay, so if you never run then know scheduler. And this is not acceptable to any scheduled

312
00:42:47.940 --> 00:42:52.320
William Cheng: Okay. So for people who implement multi level feedback you that you use this trick or agent.

313
00:42:52.590 --> 00:43:00.120
William Cheng: Guys, what they do is I set a timer. If a job hasn't been run for a very long car, what we're gonna do. We're going to increase his party, all the way to the highest party.

314
00:43:00.990 --> 00:43:05.970
William Cheng: Okay, if there's a job sitting over here for a long time. My we use agent when it's sitting there, you know,

315
00:43:06.480 --> 00:43:14.610
William Cheng: Getting older and older and older, all of a sudden, we're gonna you know time is going to go off, we're going to take this job over here we're going to move it to the highest party. Why do we move into the highest party.

316
00:43:15.210 --> 00:43:23.730
William Cheng: That, well, maybe this job, used to be a CPU bound job. And now if you run a one more time, instead of CPU maybe will turn into IO bound job.

317
00:43:24.360 --> 00:43:27.030
William Cheng: Okay, if you don't give this job, a chance you will never find that out.

318
00:43:27.720 --> 00:43:36.870
William Cheng: Okay. So, therefore, what we're gonna do is we're going to be nice as a job. We're going to promote it to the highest party if it turns out it was still a CPU bound job well pretty soon you're going to get to all the way to the bottom.

319
00:43:37.140 --> 00:43:48.210
William Cheng: You're gonna get to the bottom anyways. Okay, so therefore it's always okay to treat a job as if you know it's going to be IO bound job if it turns out a test fails. Well, pretty soon, they're going to come all the way to the bottom. Anyways,

320
00:43:49.320 --> 00:43:58.350
William Cheng: Okay, so definitely this case, you know, you know, bumping a job to the highest level, it doesn't really hurt you very much. Okay, all is going to cost us one extra time slice right

321
00:44:00.570 --> 00:44:08.370
William Cheng: All right, so, so this is this is the fear as scheduling our them. And clearly, this is not fair, right, because it's called party queuing, so therefore

322
00:44:08.550 --> 00:44:19.110
William Cheng: You know, something has higher priority than the other one. Right. Also, they get preferential treatment to job that give up the CPU quickly and that's exactly what we want. And that's why we want to use party queuing ok so again we are doing

323
00:44:19.470 --> 00:44:21.900
William Cheng: We're doing party queuing it's unfair scheduling.

324
00:44:22.800 --> 00:44:36.990
William Cheng: Policy. We're not trying to give you know the the good performance to interactive job because the interactive user can run, you know, very, very, you know, CPU bound jobs. Okay. So, therefore, maybe the right thing to do is to

325
00:44:37.590 --> 00:44:40.140
William Cheng: Use this kind of scheduling policy. Yeah.

326
00:44:40.920 --> 00:44:51.300
William Cheng: Alright, so, by the way, the kind of party that we're using over here. Okay, it's a it's a dynamic priority right because it keeps keep changing where you go up and down, you know, the these cues, the priority keep changing

327
00:44:51.960 --> 00:44:57.930
William Cheng: It's kind of a short term priority right that you know the, you know, the way you give this party is based on the schedule it

328
00:44:58.410 --> 00:45:04.410
William Cheng: Okay, when we talk about, you know, one kind of job is more important than the other job, then what we're talking about is actually a long term party.

329
00:45:04.890 --> 00:45:13.320
William Cheng: Right, we're gonna say that, you know, for this kind of job, maybe for this kind of job they pay more money. Okay, so therefore this job. Jeff, higher, higher priority over another job.

330
00:45:14.160 --> 00:45:20.010
William Cheng: Okay, because, you know, the owner of the job pay twice as much as the other one. So therefore it should run in the CPU twice as often.

331
00:45:20.610 --> 00:45:27.570
William Cheng: Right. So in this case, we sort of need to modify our scheme yo be here to treat certain job. So definitely, right, because what we really want to achieve is that

332
00:45:27.930 --> 00:45:36.570
William Cheng: If somebody pays more than they should get higher priority or inside the CPU. Right. Alright. So again, it's important to know the difference between

333
00:45:36.990 --> 00:45:45.630
William Cheng: The party that's assigned by the scheduler, which is dynamic priority versus what we really want to do is to treat certain jobs special because they have long term priority.

334
00:45:46.530 --> 00:45:52.800
William Cheng: Okay. So in this case, you know, our scheduling policy over here doesn't really address that problem, guys. So later on we're going to see how to actually address that.

335
00:45:54.390 --> 00:46:03.870
William Cheng: All right, again, the sort of show you, you know, if you remember things that a threat control blog where he come back over here. Maybe you'll come back into different case, there can be many, many different kinds of variations. Yeah.

336
00:46:07.830 --> 00:46:16.380
William Cheng: Alright, so let's talk about, you know, sort of a little bit about general purpose you know scheduler right so in the general purpose audiences and we need to do a lot of stuff.

337
00:46:16.650 --> 00:46:23.520
William Cheng: Right you you need to be, you know, listening to music and you know even watching a video and silent or maybe

338
00:46:24.180 --> 00:46:31.410
William Cheng: Same time playing style, you might be compiling at the same time, you might be surfing the web here at the same time you do all these things at the same time.

339
00:46:31.680 --> 00:46:35.070
William Cheng: Is it possible to come up with the optimal scheduler for doing all these things.

340
00:46:35.550 --> 00:46:43.230
William Cheng: And the clear, so of course it's not is there's no, there's really no way for you to guarantee it's going to be optimal. Well, guys. So typically when they use is kind of a security stick

341
00:46:43.980 --> 00:46:50.790
William Cheng: You know, for general purposes, you know, operating system. Okay. So typically, the one that we see that are commenting and us. They all have this kind of characteristics.

342
00:46:51.180 --> 00:47:00.360
William Cheng: Their time slice right because we like come sizing right they are priority base because you know job give up the CPU quickly want to sort of treat them better. They also preemptive

343
00:47:00.870 --> 00:47:09.510
William Cheng: Okay, so if you have a really short job that you want to run for some reason you know that you want to be able to present that job. Right. And also, if you have somebody who pay extra money for higher priority job.

344
00:47:09.690 --> 00:47:14.490
William Cheng: Why, when that job come to the rescue. We wanted that job to be able to run first before any of the other job.

345
00:47:15.030 --> 00:47:23.430
William Cheng: Okay, so typically for interactive general purposes and like your laptop or your desktop, we see you know job over here. They're, they're usually have these kind of care.

346
00:47:23.880 --> 00:47:32.310
William Cheng: Okay, Christy. OK, so the multi level feedback you satisfy all these kind of characteristic right it's time slice is party based is preemptive

347
00:47:32.610 --> 00:47:38.130
William Cheng: What I mean you know so. So again, you know, you can actually preemptive you know all the threads over here immediately.

348
00:47:38.340 --> 00:47:45.420
William Cheng: Or at least after a content, you will preempt it right because after a quantum that time you can make another scheduling decision if there's high party.

349
00:47:45.630 --> 00:47:55.710
William Cheng: You know job over here that I just arrived. Well, then in that case you will serve the other job first because all the other job you haven't finished serving them yet, right. So, therefore, again, this is considered a preemptive scheduling policy.

350
00:47:56.100 --> 00:48:00.570
William Cheng: Okay, so you know way every time. Will you use a time slicing you are using a preemptive scheduler.

351
00:48:01.350 --> 00:48:07.830
William Cheng: Right, because you know you don't finish serving a job and they use switches over another job. Right. So again, that by definition that's that's pretty simple scheduling.

352
00:48:08.550 --> 00:48:15.870
William Cheng: Yeah, alright. So, so also you can also use all kinds of heuristics. Right. So for example, you can actually use the long term running history of a job.

353
00:48:16.110 --> 00:48:22.800
William Cheng: Well guys, so maybe you actually remember the name of the executable. Right. So we saw, you know, Colonel CO, you know, which processes running, you know, the executable found in

354
00:48:23.010 --> 00:48:27.540
William Cheng: Maybe we can actually build a database to try to observe the behavior. I mean, maybe use machine learning technique.

355
00:48:27.870 --> 00:48:38.940
William Cheng: Show to sort of figure out what is the best way to schedule this job, you know, if the job always run at 4am every day you know for 15 seconds, you know, maybe we need to come up with a way to make this job very, very happy.

356
00:48:39.450 --> 00:48:42.990
William Cheng: Okay, or maybe we know that, you know, maybe there's a group of job that always run at that time.

357
00:48:43.320 --> 00:48:54.360
William Cheng: Maybe we can actually use AI or something like that to try to figure out what to do, but that's okay. Once you start using the heuristic. You can use all kinds of heuristics, guys. Okay, we're not going to get too much into it because this is only a introductory class. Yeah.

358
00:48:56.160 --> 00:49:01.470
William Cheng: Alright, the next scheduled. We're going to see today, which is will be the last one is gonna look at today is, you know,

359
00:49:02.610 --> 00:49:06.270
William Cheng: Scheduling for fairness right if fairness is really, really important. And what would you do

360
00:49:06.660 --> 00:49:13.200
William Cheng: Okay, so, under what conditions fairness, really important. Right. So for example, if you buy, you know, one virtual machine instead of data center.

361
00:49:13.350 --> 00:49:19.950
William Cheng: Right, you're sharing with your sharing that machine with the other five people. Well, in that case, you want to make sure you get 5% you're going to get, you know, I guess.

362
00:49:20.760 --> 00:49:25.080
William Cheng: The other five people that you want to get one sixth of the CPU was Sixth Amendment one six of everything.

363
00:49:25.710 --> 00:49:36.540
William Cheng: Okay. So clearly you know when you try to schedule on the CPU. You want to make sure you get one sixth of the CPU, no matter if other you know the the other virtual machine, whether their CPU harbor now.

364
00:49:37.050 --> 00:49:45.300
William Cheng: Okay, if you are IO bound job and all the other job over here. Their CPU bound, you still want to own one sixth of the CPU. Okay. So the question is, how do you do that.

365
00:49:46.200 --> 00:49:57.630
William Cheng: Then, so the current the texts will use this example you and for your friends. Each contribute $1,000 towards a server, right. So everybody spent exactly the same amount. So, therefore, you think you are entitled to one fifth of this machine.

366
00:49:58.140 --> 00:50:04.230
William Cheng: Yeah. So, therefore, you know, rightfully you feel that your own 20% of the species, right, because everybody pay have that same amount

367
00:50:04.710 --> 00:50:11.220
William Cheng: Your friends or interest rates and you're not into through ads. Right. So they all run a 14 thread program. So they all run a forthright program.

368
00:50:11.430 --> 00:50:18.960
William Cheng: You run a one thread program. Right. So in this case, if we are using fairness based on threats wasn't in that case every server will get one 17th of the CPU.

369
00:50:19.620 --> 00:50:26.850
William Cheng: Okay, so in this case you will only get one 17th of the entire CPU and all your friends that will get for 17th of the CPU. So in that case, it's not fair.

370
00:50:27.540 --> 00:50:32.640
William Cheng: Okay, so your friend was said, well, why don't you use for threat or four threads program, you said I don't like multi threading.

371
00:50:33.450 --> 00:50:41.850
William Cheng: Okay, so, so nobody can force you to do multi threading. Right. So how can you actually get a fair share of the CPU. Okay, so that's what, that's the problem when he just saw. Okay.

372
00:50:42.630 --> 00:50:47.460
William Cheng: Right. As it turns out, the solutions that you're very simple. We're going to use something called lottery scheduling.

373
00:50:47.850 --> 00:50:57.000
William Cheng: Okay, so what we'll do is we're going to generate a 20 lottery tickets and you have five people. Everybody's going to get four tickets. Right. So, you know, you get four tickets. Everybody get four tickets over here.

374
00:50:57.240 --> 00:51:01.020
William Cheng: And now why is that every time when the, when the CPU become available then do a lottery.

375
00:51:01.440 --> 00:51:12.000
William Cheng: Okay, what to put all these 20 tickets into A into a box. We're going to randomly draw one of the lottery tickets, and we're going to sort of find out who owns this ticket who whoever owns a ticket gets run in the CPU.

376
00:51:13.080 --> 00:51:17.250
William Cheng: Okay, so every time when the CPU become available. We're going to do this lottery. So in the end, is this a fair policy.

377
00:51:17.460 --> 00:51:26.670
William Cheng: Well, yeah, right. Because, on the average, you're going to get four out of 20 chances to run the CPU and so as your friend right every, every time. And anybody they all get once

378
00:51:26.940 --> 00:51:31.620
William Cheng: You know 20% chance of running out of CPU. So if you're running only one threat. You keep running the same thread.

379
00:51:31.800 --> 00:51:40.140
William Cheng: Your, your friends, you know, maybe they will run different threads, they can decide what they want to do. But India. What's important is that you you will get you will get exactly 20% of CPU.

380
00:51:41.370 --> 00:51:45.690
William Cheng: Guys have a solution is very, very simple right to use lottery scheduling. But how do you implement lottery scheduling.

381
00:51:46.260 --> 00:51:52.230
William Cheng: Okay, so in the real you know in in the real opportunity. So what if we have 10,000 jobs over here.

382
00:51:52.560 --> 00:52:02.460
William Cheng: Okay, how do we actually do a lottery. Right. So we have 10,000 job over here. Everybody's going to get different number of lottery tickets. Right, so one thing with lottery tickets. We can do it easily is that if somebody pay twice as much

383
00:52:02.700 --> 00:52:05.670
William Cheng: They will own prices. Many lottery tickets as you do.

384
00:52:06.810 --> 00:52:20.490
William Cheng: Okay, so in this way, it's very, very easy to actually implement our scheduling policy to say that, you know, if you pay more, you're going to get more of the CPU, right, you're going to get proportional to the number of lottery tickets that you have that much that much more sure of the CPU.

385
00:52:22.110 --> 00:52:30.180
William Cheng: Okay, so this guy who will make that kind of decision. Very simple. Right. So again, let's go back to our case over here. If we're 10,000 job. So this is how do we perform lottery.

386
00:52:30.720 --> 00:52:41.400
William Cheng: Well, so again we need to, you know, find out how many tickets. They own over here, we need to put them into a long list. And every time when we try to run lottery. Lottery. We're going to generate a random number and then we're going to find out who owns it.

387
00:52:42.510 --> 00:52:45.570
William Cheng: Okay, so what is the complexity of this algorithm.

388
00:52:45.990 --> 00:52:54.690
William Cheng: Well, it's going to be order n. Alright, so, so maybe you can come up with, you know, some clever algorithms going to be auto login or something like that. But the bottom line is that it's going to be a very expensive algorithm.

389
00:52:55.500 --> 00:53:04.650
William Cheng: Okay, so when we are running out of scheduler. We are the scheduler, and they need to make scheduling decision all the time to schedule it has to run fast. So running the lottery scheme over here is going to be too slow.

390
00:53:05.790 --> 00:53:10.920
William Cheng: Okay, so, so, India, we need a different version of the lottery scheduling. Yeah.

391
00:53:11.520 --> 00:53:17.940
William Cheng: Alright, so I'm going to talk about a scheme know, as you know, so this is called proportional share it right if you have twice as many share as a as

392
00:53:18.120 --> 00:53:24.330
William Cheng: A person you need to run twice as often. Is that a CPU completed the other one, right. So this is called proportional share scheduling.

393
00:53:25.050 --> 00:53:36.750
William Cheng: One solution over here was proposing 1995 by by some operators that researcher call strikes scheduling scheduling is an approximation of the lottery scheduling algorithm.

394
00:53:37.350 --> 00:53:46.260
William Cheng: Okay Linux actually like so much after after 12 years 12 years later, let it decide to pick this scheduling algorithm as well.

395
00:53:47.280 --> 00:53:55.290
William Cheng: As your own scheduling out where that they call this one the completely fair scheduling Alberta. Okay, so they like it so much. They call this completely fair

396
00:53:55.860 --> 00:54:00.930
William Cheng: Okay, so again, can somebody say this is not fair. Of course, it always gonna be somebody who says I'm fair

397
00:54:01.170 --> 00:54:12.330
William Cheng: Okay, because fear is very difficult to define. So we're going to sort of show you what the scheduling algorithm is that how does it approximate a lot we scheduled with them and hopefully you'll be convinced that this is actually pretty fair. Yeah.

398
00:54:13.890 --> 00:54:24.600
William Cheng: All right, so in the textbook. There's something called a meter processor. Okay so so often. Is that a professor Cabinda taught this topic, you know, when he first, you know, use this textbook.

399
00:54:24.870 --> 00:54:31.290
William Cheng: And you know I was co teaching with him. I like the way he presented it alright so therefore, when I asked you a final exam about

400
00:54:31.620 --> 00:54:38.310
William Cheng: You know strike scheduling, you have to use the one in the lecture and not the way in the textbook. Okay. If you follow the one in place where you going to get zero credit

401
00:54:38.880 --> 00:54:45.150
William Cheng: Okay, alright, so I hope I made that very, very clear. Okay. Alright, so let's welcome meter processor, we're not doing it that way. Yeah.

402
00:54:46.110 --> 00:54:56.520
William Cheng: OK, so the story is going to go though it's time slides priority based preventive and that's why Linux user because it satisfy you know these requirements for general purpose operating system.

403
00:54:57.210 --> 00:55:07.890
William Cheng: The schedule policies various about. Okay, so we're going to use a priority base right so we're going to use a priority based scheduling algorithm over here. Okay. Every time slice pick the thread with the highest party run

404
00:55:08.790 --> 00:55:15.000
William Cheng: OK. So again, it's a very simple algorithm. Right. You, you, you, you have a party Q over here, you pick the one with the highest party over here.

405
00:55:15.420 --> 00:55:24.180
William Cheng: So even though you know for the scheduling over them. They don't call it a priority level, they actually call it the past value because they want the one with the smallest pass value to go first.

406
00:55:24.420 --> 00:55:29.640
William Cheng: Yeah, so he will. He will in the wrong. Q. Every, every job over here will carry them with the past value.

407
00:55:29.970 --> 00:55:42.480
William Cheng: Pa SS right called a pass it over here. The one with the smallest is the one at the head of the rank you guys over here. Maybe this one is to this one is five by 1118 2580 to 112 or something like that.

408
00:55:42.990 --> 00:55:49.770
William Cheng: Okay, so they are sort of business or pass value. Okay. The job with the smallest size that you get to run in the CPU. Yeah.

409
00:55:50.670 --> 00:55:54.000
William Cheng: Alright, so, so, so, so what it would do is, I know.

410
00:55:54.420 --> 00:56:05.580
William Cheng: Let's get your pauses very, very simple. Every time slice you pick the first job over here running out of CPU when the time size is over. So you don't do preemption when the time size is over. What you would do is that

411
00:56:05.880 --> 00:56:11.340
William Cheng: You need to move this job over here. Back in the queue. So the question is, where would you move it back.

412
00:56:12.300 --> 00:56:19.830
William Cheng: Okay, if this job has a lot of lottery tickets, we're, we're, we're, we're sort of moving back to where if the job has a

413
00:56:20.220 --> 00:56:23.880
William Cheng: Has a lot of lottery ticket what he would do is that they should take a very small strike.

414
00:56:24.180 --> 00:56:28.800
William Cheng: It will get close to the beginning of the Ron Kuby if it has a lot of lottery tickets, because he needs to run more often.

415
00:56:29.130 --> 00:56:34.590
William Cheng: If this job has very business very, very few lottery tickets. So in this case, and he's got all the way back to the end.

416
00:56:35.370 --> 00:56:42.960
William Cheng: OK. So again, if you have small number of lottery tickets you make a big stride. If you have a lot of lottery tickets over here, you're going to end up with a

417
00:56:43.410 --> 00:56:53.340
William Cheng: With a waste of a small strike. Okay, so in a way where you can think about is that the number of lottery tickets that you have, if you multiply them by your stray issue be equal to a constant.

418
00:56:54.390 --> 00:57:02.370
William Cheng: Okay, so this way, the more lottery tickets that you have. You're going to make the smallest dry and smaller longer do you have going to end up with the biggest. Right, right. If you multiply them together, you get a constant.

419
00:57:02.760 --> 00:57:06.750
William Cheng: Then in this case, we can also treat every job using the same mechanism. Right.

420
00:57:07.590 --> 00:57:14.190
William Cheng: Alright, so the strike values over here, a computer, according to the distribution of tickets, you know, using the heuristic. And I just mentioned over here.

421
00:57:14.850 --> 00:57:25.740
William Cheng: So and also one of the requirement over here is that since the scheduling need to run as fast as possible the stripe values over here are required to be integers because using floating point operations. They can be too slow.

422
00:57:27.000 --> 00:57:35.070
William Cheng: Okay. So inside a CSR schedule over here. We don't want to deal with floating point numbers, everything has be integers. Okay, so that's gonna be our requirement, where you run the strike schedule that

423
00:57:35.520 --> 00:57:39.660
William Cheng: Alright, so it's good to go. It's very, very simple in every iteration over here. Every time slice

424
00:57:39.840 --> 00:57:49.470
William Cheng: We're going to schedule the thread with the smallest possible value which is at the head of the wrong key over here. And then we're also going to remember the girl said the global group has value to be the past value of the threat.

425
00:57:50.010 --> 00:57:54.450
William Cheng: Okay, it's almost like if you go to like a government agency over here, you going to take a number right when

426
00:57:54.930 --> 00:58:04.950
William Cheng: You know, when the the the the the agent is serving serving a customer, they will ask you to put it on the board over here says now serving customer number 12356 or something like that.

427
00:58:05.670 --> 00:58:11.130
William Cheng: Okay, so here they will post the blood Goma pause rounding. Just say no I'm serving the job with this past value. Okay.

428
00:58:11.940 --> 00:58:23.460
William Cheng: Alright, so that's all it does. And then it starts early is inside the CPU after the time sizes over here. We're going to increment the stress past value by destroy value. So therefore, the code. We're going to execute. It's like this.

429
00:58:24.330 --> 00:58:30.450
William Cheng: Okay, so this is why it's so fast right past value. Plus, he will destroy. So again, the past value store insider threat control blog that

430
00:58:30.690 --> 00:58:42.300
William Cheng: Drive value over here is going to destroy inside of slack on your blog. So this is all you do to to to to update the past in the past value and then we're going to have this thread go back into the wrong tool and then it goes to the right place.

431
00:58:43.410 --> 00:58:48.900
William Cheng: Okay, and then we loop that's all we do. Okay, so again, this is why people like so we're going to sort of

432
00:58:50.520 --> 00:58:57.510
William Cheng: Convince you that this particular algorithm basically implement the strike scheduling of the implement the lottery scheduling algorithm.

433
00:58:58.740 --> 00:59:02.430
William Cheng: OK, so now it's kind of hard to see. Right. But as it turns out, this one actually works. Yeah.

434
00:59:03.390 --> 00:59:15.120
William Cheng: Alright, we're going to, I'm going to do this using the example I destroyed over here. Again, we're going to sort of have inversely proportional to the number of tickets. So the strike multiplied by the number of tickets over here is going to be equals to a concert

435
00:59:15.540 --> 00:59:19.110
William Cheng: Okay. So for example, we have three threads over here at the wrong. Q.

436
00:59:19.710 --> 00:59:23.820
William Cheng: Thread he has three tickets. So I'd be has two tickets or I see has one tick is over here.

437
00:59:24.000 --> 00:59:31.020
William Cheng: So in that case, what should be the strike right so again if you want them to watch another straight over here will be one third. This will be one hot. This will be one.

438
00:59:31.230 --> 00:59:35.610
William Cheng: If you multiply all of them together, right, this will be able to one this will be able to why. So this will be the one

439
00:59:36.030 --> 00:59:40.320
William Cheng: Okay. But again, we don't like fractions over here. So we're going to make them into integers.

440
00:59:40.590 --> 00:59:48.390
William Cheng: So the first step over here is that we make them inversely proportional to the number of tickets that you have. And then how do we make this to be integers.

441
00:59:48.780 --> 01:00:02.940
William Cheng: Right, we multiply by the small smallest common multiplier of the denominator, right. So we're here to dominate over the years is going to be three, two and one. The smallest common multiplier is going to be able to six. So we multiply every one of them by six.

442
01:00:04.200 --> 01:00:11.490
William Cheng: OK, so again if I asked you a question like this in exam. You have to do it this way. Okay, so in this guy, this will be one third times six is going to be able to to

443
01:00:11.970 --> 01:00:15.930
William Cheng: One how time seems to be three one time six over here is going to go to six.

444
01:00:16.410 --> 01:00:26.520
William Cheng: Okay, so therefore, when we're done over here, this will be the show values. Okay. You can do a sanity check. Right. You multiply those two you got six you modify this to he's going to be going to six, you multiply this equal to six.

445
01:00:26.940 --> 01:00:39.150
William Cheng: OK. So again, so this is one step of the check. You know, you got to make sure that the strike number over here needs to be as small as possible, right by multiplying by the smallest common multiplier of it'd be non nominator you get this result. Yeah.

446
01:00:40.560 --> 01:00:50.580
William Cheng: Alright, so, so now we know destroy value, all we need to know is that when we start running our algorithm. What's going to be the initial value for all our threats, guys. Okay, again, in this case over here.

447
01:00:51.000 --> 01:00:54.510
William Cheng: We're going to see our reviews right here. Right, here's our CPU over here.

448
01:00:54.930 --> 01:01:03.540
William Cheng: So for every three over here is going to be a, b, and c any order that you want. Right. And they'll be here in this case we're going to randomly assign them to to be a initial pass value.

449
01:01:04.320 --> 01:01:11.280
William Cheng: Okay, the initial pass value overcoming anything we want. Because it's an initial state right when you initialize global variable, you can initialize to whatever you want.

450
01:01:11.700 --> 01:01:19.050
William Cheng: So I'm going to use one two and three right here. Okay. So, for the sake of the exam if I if I give you any other number. You need to be able to make it work.

451
01:01:19.470 --> 01:01:24.300
William Cheng: Okay, there's no requirement to have a sub was working on two or three they can start with any number that I want.

452
01:01:24.810 --> 01:01:35.820
William Cheng: Okay, so again this is that over here. We're going to schedule them into 123 over here guy and then all the right hand side over here. I'm going to keep track of every iteration. Every time slice, who is going to be running out of CPU.

453
01:01:36.690 --> 01:01:41.010
William Cheng: Alright, so now I'm going to run this scheduling I'll wear them again. It's a very, very simple scheduling I'll wear them.

454
01:01:41.250 --> 01:01:51.300
William Cheng: Every time the CPU become available. You take the first job with the smallest pass value running out of CPU when a time size is over you increment the past value by destroy value and then, you know,

455
01:01:52.530 --> 01:01:58.710
William Cheng: Okay, very simple algorithm. Right. OK. So now time you go to zero or we're iteration number one over here, who is the winner. Right.

456
01:01:58.920 --> 01:02:08.820
William Cheng: He is the winner over here is going to get running out of CPU over here with the past value equal to one. So we're going to declare a winner, if I remember right here. Right, so therefore it's going to be like this.

457
01:02:09.330 --> 01:02:13.290
William Cheng: Okay, is running out of CPU over here, we remember he is the winner of the first round.

458
01:02:13.710 --> 01:02:26.880
William Cheng: Ok and now when a time sizes over what do we do, we're going to increment as past value by the strike values are the strike value over here for a is equal to two. So, one plus two over here is going to be equal to three. We're going to put it back into the rank your worship ago

459
01:02:28.050 --> 01:02:30.780
William Cheng: Okay, should he get in front of job see over here.

460
01:02:32.610 --> 01:02:44.940
William Cheng: Well, I mean, the job see over here sitting in the wrong key already, right, it seems unfair. If we put a in front of it. So what we're gonna do is, I'm going to say that if there's a tie in the past value that you get behind the thread that's already inside of you.

461
01:02:45.660 --> 01:02:56.640
William Cheng: Guys, again if I ask you the same kind of question in the exam. This is the way you have to do it right. So in this case, he has to go here, right. Hey, with us go here. Hey, can I go in front of seed, because that will be rude.

462
01:02:57.720 --> 01:03:03.780
William Cheng: Okay, so therefore you're gonna according to our, our, then he has run this way. Right. So when when this one is done, it will look like this.

463
01:03:04.350 --> 01:03:09.390
William Cheng: Okay, so now we're at time slides to right again very simple take this one. Running out of CPU.

464
01:03:09.630 --> 01:03:15.030
William Cheng: Is going to be like this. And I'm going to remember these going to be the winner in second round. Right, so therefore it will look like this.

465
01:03:15.240 --> 01:03:27.030
William Cheng: When the time size is over. We're going to increment BS past value by the stripe value be stripe value is equal to three. So this one is going to go to fire when this case will be really easy right to determine over here. So we will go here with a value of five.

466
01:03:28.680 --> 01:03:36.150
William Cheng: Okay. Alright, so now it will look like this. Right. So, you know. So in this case, next time sees going to get running out of CPU and the next time slides over here.

467
01:03:36.330 --> 01:03:42.420
William Cheng: And we're going to remember at iteration three over here see is going to be the winner. I mean, so far it looks really boring. We're just doing round robin

468
01:03:42.750 --> 01:03:50.490
William Cheng: Okay, so nothing special over here. When the time is over. We're going to increment sees past value by destroy value. See, strawberries, go to six.

469
01:03:50.670 --> 01:03:57.450
William Cheng: We're going to change this one into an eye and again so easy decision. See, we'll go here with the past value of nice what it will look like this.

470
01:03:57.780 --> 01:04:05.430
William Cheng: Right iteration number four is going to run inside of CPU is going to go inside over here. When declared as the winner over here, it will look like this.

471
01:04:05.730 --> 01:04:11.550
William Cheng: When a time size is over. We're going to increment air over here by destroy value is equal to two. So this one is go to five.

472
01:04:11.730 --> 01:04:19.680
William Cheng: So, where's your ego right and now needs to go between B and C because there's a high five is equal to five. So again, you have to, you have to get behind.

473
01:04:20.070 --> 01:04:24.150
William Cheng: Whoever that high with you. So, therefore, is going to be right here with the past value of five.

474
01:04:24.450 --> 01:04:30.240
William Cheng: Okay, so when we're done. It will look like this right BS here. First, as your next and then sees that the end over here.

475
01:04:30.420 --> 01:04:39.990
William Cheng: And now in iteration five over here. He's going to run inside the CPU. We're going to remember. He is the winner over here. Again, if you look on the right hand side of yours reborn is look like round robin over here.

476
01:04:40.260 --> 01:04:51.300
William Cheng: When the time sizes over to increment BS by the past value over here is going to be equal to eight right is going to get between A and C. So he's going to be right here and is going to be right here. So when we're done. It will look like this.

477
01:04:51.720 --> 01:04:57.570
William Cheng: Okay iteration number six over here is going to running out of CPU over here, right. So, therefore, is going to be the winner right here.

478
01:04:58.230 --> 01:05:11.250
William Cheng: So to look like this when the time flies is over is going to get incremental by two. So as I pass value is going to go to sever, where do you put back a is going to be at the head of the runtime over here because he now has the smallest past value.

479
01:05:12.420 --> 01:05:16.410
William Cheng: Right, so it's gonna be like this over here. Okay, so I'm gonna

480
01:05:16.920 --> 01:05:22.410
William Cheng: I'm gonna claim that from this point on the scheduler is going to repeat what it did before, over and over again.

481
01:05:22.740 --> 01:05:27.240
William Cheng: Right, because this, this configuration is exactly the same as where we started.

482
01:05:27.450 --> 01:05:36.510
William Cheng: Where do we start right at the beginning, over here, followed by being followed by see and as cost value is going to be one, two and three over here. So what what's important to note over here is that

483
01:05:36.780 --> 01:05:42.780
William Cheng: These past value is one bigger than a and sees past values one bigger than be so right over here, a beast has value.

484
01:05:43.800 --> 01:05:48.300
William Cheng: Is going to be one bigger than a as these past value over here, it's gonna be one bigger than be

485
01:05:48.840 --> 01:05:57.480
William Cheng: Okay, if we take everybody inside around. Q. If we subtract the same amount of past value from that, for example, to be good if we subtract everybody by six.

486
01:05:58.410 --> 01:06:08.670
William Cheng: Is that okay, well we're allowed to do that. Right. So if we if we subtract everybody from from of by by six over here. We're going to get back to the initial configuration over here and everything will actually works out.

487
01:06:09.270 --> 01:06:17.040
William Cheng: Okay, so it's okay to death to to detriment. Everybody has value better. Same amount because when this one all you'll make exactly the same route to say says scheduling decision.

488
01:06:18.210 --> 01:06:25.530
William Cheng: Okay, so if we do that will notice that this is exactly the same as the initial state. And now we're going to repeat our scheduling decision over and over again.

489
01:06:26.250 --> 01:06:35.610
William Cheng: Okay, so what is our scheduled indecision scheduling decision over here is this particular scheduling decision and from this point now it will repeat every cycle look exactly like this.

490
01:06:36.240 --> 01:06:39.540
William Cheng: Okay, so therefore, in this case, how many times does a run in every cycle.

491
01:06:39.840 --> 01:06:53.670
William Cheng: A run three times over here, and every cycle and be run two times every cycle and see Ron only one time, every cycle there. So, therefore, in the, in this case in the air. If we start repeating from here, over here, it's going to conform to the distribution of the number of tickets

492
01:06:54.750 --> 01:07:07.110
William Cheng: Okay, so this is why people like start scheduling over here, right, because, oh, this one is that you can see that this one over here. Exactly. You know, you know, you're going to run as many fans as the number of tickets that you have

493
01:07:08.370 --> 01:07:12.270
William Cheng: Okay, so that's why Linda is called a completely fair scheduling algorithm. Okay.

494
01:07:13.680 --> 01:07:16.980
William Cheng: All right. Alright, last issues over here. What if you have a newsletter that arrived.

495
01:07:17.730 --> 01:07:25.080
William Cheng: Okay, so here it says when a new theater right it will allocate the global pass value. Right, so you don't bump off the one that's running out of CPU.

496
01:07:25.260 --> 01:07:33.390
William Cheng: But you're going to basically put it all the way to the front of the CPU as close to the header rank as possible. Okay. So in this case, this threat will run first

497
01:07:33.810 --> 01:07:43.290
William Cheng: OK, so again this is okay, right, because if it turns out that this doesn't have too many lottery ticket. It will only run one threat and so you only run one time slots and then it will go to the right place.

498
01:07:44.160 --> 01:07:53.430
William Cheng: Okay, so therefore it will be the right decision to make every time somebody coming to run to you first, you run them first, but as soon as you run at one time. You know that they will go to the right place. Okay.

499
01:07:54.330 --> 01:07:57.720
William Cheng: All right. And we also want to be able to reward a thread that actually

500
01:07:58.350 --> 01:08:07.110
William Cheng: Treat the CPU. Well, right. So in this case, again, our case doesn't really cover that. Because what to imagine a case, what, what if somebody actually give us the CPU very, very quickly.

501
01:08:07.710 --> 01:08:19.230
William Cheng: Okay, so in that case, you know. So let's say that you will use a fraction of the time slides. So let's say F over here is equal to 10%. So if you use up 10% of your time size instead of increment, your, your past value.

502
01:08:19.740 --> 01:08:29.460
William Cheng: By destroy value. We're going to increment the past value by only a fraction of the dry. So what should be the fracture, what should be the fraction of the, the, the, the quantum that the

503
01:08:29.940 --> 01:08:38.010
William Cheng: The fraction of the content that you use, right. So if you only use 10% of the content when this guy Robin said next time we come back into CPU while we're going to

504
01:08:39.030 --> 01:08:42.240
William Cheng: We're going to increment Australia by a proportional amount

505
01:08:42.840 --> 01:08:52.800
William Cheng: Right. So in this case, even if you have a very, very large shy. If it turns out you're very, very nice sort of see the to the scheduler you give up a CP right away. Well, next time, will you come back you will be very, very close to the head of the wrong to you.

506
01:08:53.940 --> 01:09:03.900
William Cheng: Guys, again using the scheduling. We can easily adjust them so that a new arriving, so I can run inside the CPU wise and also if you're a nice to the scheduler, you get to run closer to the head of recruit

507
01:09:05.250 --> 01:09:09.240
William Cheng: Right. Is this better, better than the multi level feedback you

508
01:09:10.170 --> 01:09:19.170
William Cheng: Know what I mean. So, so again, this one, you know, again, we sort of need to figure out how do you actually assign dollar amount to all these threats. Right. You need to know how you know what the owner pays over here.

509
01:09:19.560 --> 01:09:24.150
William Cheng: You should have the same same problem with how do you actually allocate of the lottery tickets

510
01:09:24.960 --> 01:09:29.040
William Cheng: Okay, so we don't really know. You know, if you have an interactive job. How many lottery tickets that you have to give

511
01:09:29.280 --> 01:09:33.180
William Cheng: So, India, typically what we do is everybody, we're going to assume that they have the same lottery tickets

512
01:09:33.510 --> 01:09:41.070
William Cheng: Okay, so unless you're going to actually show that certain job need to be have preferential treatment. So again, in that case, we're good idea if we know that somebody I should pay twice as much

513
01:09:41.280 --> 01:09:48.240
William Cheng: And in that case, will give that threat twice as many lottery tickets. Okay, so, potentially, you know, this doesn't work out pretty well. Right.

514
01:09:49.140 --> 01:09:54.840
William Cheng: So, all right. So, so, you know, by the way, sorting the past value is it kind of slow

515
01:09:55.200 --> 01:10:02.820
William Cheng: Okay, if you have taken CSI 70 right if you have seen our implementation or barbecue the priority queue where you try to insert something into the party que

516
01:10:03.030 --> 01:10:09.690
William Cheng: There's a data structure that you can use is also known as a heap. It's a heat data structure of the performance is going to be order login

517
01:10:09.990 --> 01:10:15.720
William Cheng: OK, so again login over here. So it's actually pretty good. Right. And it's a large number login over here is going to be pretty small.

518
01:10:16.020 --> 01:10:24.630
William Cheng: Okay. Also, when you remove the first element over here from the priority queue over here is also going to cause your Otter login so in this case the performance

519
01:10:25.500 --> 01:10:32.910
William Cheng: Is there is there of course all the ones going to be best, but Otter login. If it's locked based to over here. It's actually not so bad. Yeah.

520
01:10:34.470 --> 01:10:42.030
William Cheng: All right, so, so I guess we're done with a strike scheduling. So it's a good point to break. So next I'm going to continue and look at all the other scheduling.

521
01:10:42.330 --> 01:10:53.070
William Cheng: Algorithm. So the next lecture of you will be the last lecture for this semester. So we need to cover the remaining scheduled for that. And also we need to go back to chapter three and look at dynamic Lincoln and loading.