WEBVTT

1
00:00:02.610 --> 00:00:13.019
William Cheng: Welcome to lecture 29 so Colonel three is do of course this week, or this Friday. If you have co from previous semester, don't look at them. Don't copy them best to get rid of that.

2
00:00:13.860 --> 00:00:20.880
William Cheng: Grading guideline is only will grade, you must copy K three Remi into VM readme and deal with all the question mark.

3
00:00:21.420 --> 00:00:30.120
William Cheng: And after submission and make sure you verify your kernel submission. So again, when you verify your submission, you need to follow the grading guidelines, step by step.

4
00:00:30.690 --> 00:00:37.950
William Cheng: And, guess I have a typo here retest retests retest everything

5
00:00:38.490 --> 00:00:43.650
William Cheng: To make sure right don't miss a thing. So again, you know, designate somebody to do it. There's a two people do.

6
00:00:43.860 --> 00:00:50.490
William Cheng: You spend a lot of time working on Colonel three, you got to make sure you don't make silly mistakes. Okay. Because, because there's nothing I can do after you make a submission

7
00:00:50.910 --> 00:00:59.550
William Cheng: After submission Della. Yeah, and you know the grading guidelines with how the greater to change config that MK. You know, a certain steps.

8
00:01:00.090 --> 00:01:07.710
William Cheng: So make sure that you do exactly the same thing. So you see exactly what the greater will see that because, again, the greater has to follow the grading islands. Yeah.

9
00:01:08.520 --> 00:01:19.410
William Cheng: Alright, just want to mention something about Keisha okay so so Colonel three. By default, the greater will assume that you're running a spin. And then, and you're running the user level show

10
00:01:19.860 --> 00:01:24.840
William Cheng: OK, so the grid is going to assume that you can get there. Okay, so if you can run a spin a net

11
00:01:25.530 --> 00:01:30.030
William Cheng: You know, so I gotta run a five minute proc around right so so in a problem that's all you do, you know, you

12
00:01:30.480 --> 00:01:40.110
William Cheng: Run a spinning it and go into the user space. And when it come down is going to come, come, come, come down a different place. Right. Okay. So in this case, there's no need for Keisha anywhere for k for Colonel three

13
00:01:40.920 --> 00:01:50.190
William Cheng: Okay, so, so, so if you if you can run it's been in it. Don't run Keisha at all. Alright, so, so please understand it. Right. So again, if you're not sure, you know, send me an email. Now,

14
00:01:51.120 --> 00:01:54.690
William Cheng: But if for some reason you cannot get a spin it to work.

15
00:01:55.680 --> 00:02:05.280
William Cheng: Okay, then what do you do right so then they you need to get as many points as you can. So here's my suggestion, right, if you can run it's been in it. Right. So if you can, if you can write has been in and then don't forget us

16
00:02:05.550 --> 00:02:16.980
William Cheng: And then they don't always know what I'm saying right now. But if you cannot run it's been in there usually use Kasia command just like one on one and two to run user space program, one at a time to the a partial credit

17
00:02:17.850 --> 00:02:23.130
William Cheng: OK, so again look at a grading and I read every single test, you need to make it into a separate case shall command.

18
00:02:23.520 --> 00:02:29.670
William Cheng: Okay, it's not an entire section being used to be one page document one section, be it needs to be. I don't remember how many it has. There are

19
00:02:30.030 --> 00:02:38.310
William Cheng: Because sometimes I add them into the that right so if there are five of them, you need five K shell command. And what would you call these K shell command I will call them be one B2B three before it's

20
00:02:38.640 --> 00:02:47.370
William Cheng: Called and something obvious. So the greater knows where they're dealing with. OK. And then, so you'll use one k shall command to run each user space program.

21
00:02:47.910 --> 00:02:59.370
William Cheng: Okay. So this guy's will be sub test in Section B and D of the grading. I want a Section C section sees Keisha if you cannot run. So Section C is usually that will show. So if you can or cannot run it's been in there. Well, then there's no point

22
00:03:00.150 --> 00:03:06.210
William Cheng: Okay, you will not get any credit, you know, for section. See if you cannot run user level shop. Okay.

23
00:03:07.290 --> 00:03:15.750
William Cheng: So, so don't don't run slash been such as such there directly because that doesn't count section. See, meaning that you can run you know SPF in it. Okay.

24
00:03:16.890 --> 00:03:22.110
William Cheng: So, so again, the way we run the grading gun on design, you know, every occasion coming up to create a child process.

25
00:03:22.380 --> 00:03:33.330
William Cheng: Inside the child process is where you call Colonel exactly right. Go into the user space and then run that one user space program and then it will come to the kernel. And then it was self terminate. Right. But in this case, when itself terminate.

26
00:03:34.050 --> 00:03:42.330
William Cheng: You know, it's a child process of the enterprise is the only that process with that. Okay. So will you read hello directly from it.

27
00:03:42.750 --> 00:03:48.030
William Cheng: In a program. Well, in that case, hello, is the inner process. And that's why when they come back and set a colonel, the environment, you can turn off.

28
00:03:48.810 --> 00:04:00.330
William Cheng: Okay, so what you're required to do is that if you if you cannot run. It's been an issue use medication command every case alchemy goes into user space when it comes down. Is that a colonel, you should go back to the issue. Go back to Asia.

29
00:04:01.620 --> 00:04:04.800
William Cheng: Alright, so, so, so, so, so again, that's where you have to do. Yeah.

30
00:04:05.610 --> 00:04:14.310
William Cheng: Alright, so, so remember that the greater cannot change your co one grading. Okay, so you can't really tell the greater today, you know, change this line and then re compile and then that's not allowed.

31
00:04:14.970 --> 00:04:25.440
William Cheng: Okay, so, so you wanted run user space program one command at a time. You have to use case command and every case document, you have to create a child process in the child process you're going to user space. Okay.

32
00:04:26.220 --> 00:04:30.120
William Cheng: All right. So in this case, again, my recommendation is that you should call those tests.

33
00:04:30.540 --> 00:04:42.330
William Cheng: V1, V2, V3 before and then do you want me to the 3D voice. And also remember you read a great guy. Very, very carefully. I think for Section D if you run them from from Keisha you can only get a most half the credit

34
00:04:43.590 --> 00:04:54.510
William Cheng: Alright, so again, people who can get as been as they will get more credit. Okay, so that's the way things are set up. So, so, you know, again, dude. My fairness policy, everybody will go get exactly the same rule. Yeah.

35
00:04:55.230 --> 00:05:01.830
William Cheng: Alright, so, so, this guy's you need to provide extensive documentation, the README file right if you remove it. You submit. There's a section for you to add anything

36
00:05:04.980 --> 00:05:13.260
William Cheng: Yeah, yeah. Anyways, you just find some place, you know, in the Reno, Nevada sale. And if you're not sure, you know, send me email and then we'll, we'll talk about it.

37
00:05:13.560 --> 00:05:23.250
William Cheng: Then, so you need to provide extensive documentation to do to do to tell the greater how to get how to get most points, how to get most partial credit points out of your submission

38
00:05:24.060 --> 00:05:34.110
William Cheng: Right, you really need to help the greater guys to give them as much information as possible. Okay, so it again. Every K shell commands you only run one user space program. Okay.

39
00:05:35.850 --> 00:05:42.480
William Cheng: Alright, so let's go back to scheduling. So it was okay for Colonel three be of question you know some email.

40
00:05:42.930 --> 00:05:52.140
William Cheng: So last time we'll talk about some of these, you know, performance metrics that we're going to pay attention to. As it turns out, when I got to pay attention to all these performers. We're going to pay attention to even

41
00:05:52.830 --> 00:05:59.700
William Cheng: Some specific wise, the ones that the textbook is talking about. Yeah. Alright so today we're going to look at some scheduling algorithm.

42
00:06:00.420 --> 00:06:10.500
William Cheng: So, today and tomorrow altogether. We're going to look at 10 scheduling algorithm that sounds like a lot. So over that bill, the deputy that that's going to be the plan.

43
00:06:11.280 --> 00:06:18.390
William Cheng: So we will focus on how the run by the way the categories. There are the basic scheduling out with them. There's a priority based scheduling algorithm.

44
00:06:18.840 --> 00:06:27.720
William Cheng: There's proportional shared scheduling algorithm. So those up for the sheer server, you want to be as fair as possible. We're going to talk about what to do there. And also there.

45
00:06:28.080 --> 00:06:34.770
William Cheng: We mentioned briefly about real time system as we're going to talk about what kind of schedulers are reasonable for real time systems. Yeah.

46
00:06:35.610 --> 00:06:41.460
William Cheng: We'll focus on how to run queue is manage that. So the rupture is going to get really complicated.

47
00:06:42.210 --> 00:06:47.580
William Cheng: Alright, so in Colonel you know winnings assignment that run through his first come first serve is really trivial.

48
00:06:48.540 --> 00:06:52.050
William Cheng: So, so, so we're going to see how difficult things can get

49
00:06:52.440 --> 00:07:01.050
William Cheng: So this is one of the reason you know when you get an interview. I'd like to ask your scheduling question because they want to make sure you understand what scheduling is all about how complicated things get

50
00:07:01.470 --> 00:07:02.460
William Cheng: So what about other cues.

51
00:07:02.730 --> 00:07:14.340
William Cheng: What about a dispute. What about the keyboard. Q. What about the graphics to if there's one, you know, whatever. There's lots of view out there, right. So, so again the CPU the wrong. She was the most complicated one. So they will go and look at the CPU scheduling algorithm. Okay.

52
00:07:14.730 --> 00:07:21.780
William Cheng: For this, there might be specialized scheduled for them. So again, we're not going to talk about that. Yeah. Alright so scheduling is actually a very big topic.

53
00:07:22.320 --> 00:07:29.280
William Cheng: In operating system. Okay, so some people, you know, you know, some people hope I have graduate level class just talk about scheduling. Yeah.

54
00:07:30.870 --> 00:07:38.880
William Cheng: All right, we're going to assume that you know all the schedulers they are work conserving right, which means that as long as their work to do. You have to do work.

55
00:07:39.630 --> 00:07:41.520
William Cheng: OK, so the opposite of a work can schedule.

56
00:07:42.330 --> 00:07:52.200
William Cheng: The opposite of a work conserving scheduler is a vacation in scheduler. So to begin with it. So what's a vacation scheduler. Right. It's like, it's like that you know that you have work to do, but you got to take a vacation.

57
00:07:52.560 --> 00:08:01.650
William Cheng: Okay, so in that case, those are vacation schedule. Okay, so our scheduler is going to be kept busy as long as there's work to do. Okay. Otherwise, it's not worth conserving yeah

58
00:08:02.880 --> 00:08:05.730
William Cheng: Alright so so anyways we're going to take

59
00:08:06.960 --> 00:08:15.990
William Cheng: So the way we're going to do this is that we're going to first look at the simplest scheduler. And we're going to talk about how to compute some of these performance metrics.

60
00:08:16.470 --> 00:08:22.680
William Cheng: What you should pay attention to and all these kinds of stuff. Well, what is going to be the best scheduler, you know, under certain conditions.

61
00:08:23.520 --> 00:08:37.230
William Cheng: So, you know, so that that's what that's what I'm going to first talk about so. So the first thing I'm going to start with is, is going to be numb preemptive. Okay, so once you get on the CPU you never get off. Nobody can bump you off RAM and you might still go to service interrupt, but

62
00:08:38.340 --> 00:08:40.680
William Cheng: When we talk about scheduler. We don't really care about interrupts

63
00:08:41.400 --> 00:08:47.340
William Cheng: Okay, we're going to assume that interrupt doesn't take any time you go to, you know, I become back where you were before. So this num num preemptive you know scheduler.

64
00:08:47.940 --> 00:08:54.060
William Cheng: It's also not interactive job. So there's no you know there's no interactive users sitting from your machine.

65
00:08:54.510 --> 00:09:01.650
William Cheng: Because we mentioned before, when there's interactive user, the interactive music become more important, so therefore we have to use party priority queuing

66
00:09:02.490 --> 00:09:06.330
William Cheng: Okay. So right now, there's no priority every job are treated exactly the same. Okay.

67
00:09:07.290 --> 00:09:17.730
William Cheng: So we're going to schedule all these job right, we mentioned before, what a job is right when you get on the run to your new job. And then at some point you're going to voluntarily give up the CPU. Next time you come back into the run to your new job.

68
00:09:18.360 --> 00:09:31.320
William Cheng: Okay, if it turns out that if we're doing preempted scheduling, you start running out of CPU and then you've got preempted, you get put back into around you. And so in that case if you get put back into around you because a preemptive scheduling, you're still the same job.

69
00:09:32.700 --> 00:09:38.370
William Cheng: Alright. So again, it's very important to remember that, you know, so that's what a definition of a job is, you know, for for

70
00:09:38.760 --> 00:09:43.530
William Cheng: For this class because later on. You take other classes. Maybe they have different definition. But as far as this causes concern.

71
00:09:43.770 --> 00:09:55.170
William Cheng: According to the definition of the textbook. That's what a job is, OK, if you get preempted, you're still the same job okay well you voluntarily give out the CPU. Next time you come back to the run que yo you are different job yeah

72
00:09:55.950 --> 00:10:01.320
William Cheng: Alright, so to John's gonna run one at a time. Why is that because there's no preemption. Right. So again, the first case, we're going to

73
00:10:01.620 --> 00:10:11.820
William Cheng: Take a look at is no no preemption. So once you start running out of CPU, you might get bumped off the service interrupt. But as soon as you know have a service you come back and you're still running the same job. Is that a CPU.

74
00:10:12.180 --> 00:10:17.040
William Cheng: Okay, so once you start running out of CPU. You'd never get put back into the run cute. All right.

75
00:10:18.720 --> 00:10:25.560
William Cheng: Also, we're going to make a big assumption over here. We're going to sort of take a look at the simplest case to say that, well, if we know the execution time

76
00:10:26.040 --> 00:10:35.940
William Cheng: You know of your job right. Your job going on around you when it goes into the CPU. We know exactly how many seconds of CPU and needs. Okay, so

77
00:10:36.840 --> 00:10:46.110
William Cheng: So, so this is unreasonable assumption, right, because you were the scheduler. We try to run a job, you know like what you do your kernel Samara we try to run a thread. You don't know how it's gonna run inside of CPU.

78
00:10:46.860 --> 00:10:55.500
William Cheng: OK. So again, this is a very, very unrealistic assumption we're going to make this assumption anyways because we want to see that if we know everything about every job. What will we do

79
00:10:56.850 --> 00:11:01.410
William Cheng: Okay, so we're trying to find the best scheduler while. So how do you measure the best scheduler. So first we're going to

80
00:11:01.800 --> 00:11:12.360
William Cheng: Assume that we know the execution time for every job and then we're going to say, well which performance metric you want to optimize and then maybe there's a scheduling algorithm that can actually maximize the performance metric right

81
00:11:13.320 --> 00:11:19.920
William Cheng: Alright, so, so this is not real estate. So what we're trying to figure out is that if you know the running every job. How would you schedule these jobs.

82
00:11:20.280 --> 00:11:26.160
William Cheng: Okay, and what kind of performance for mobile formats matches. Are you gonna. Are you going to optimize and

83
00:11:26.730 --> 00:11:32.580
William Cheng: Alright, so the first queuing discipline. I'm going to look at is the first, the easiest one where I first come, first served or

84
00:11:33.030 --> 00:11:43.740
William Cheng: You know, I guess, you know, so, so, so, or five, four or five is first in first out first thing for herself first come first serve. They're all the same thing, right. So we next is supposed to have a first. I mean, you know,

85
00:11:44.760 --> 00:11:53.550
William Cheng: Some people didn't implement when used correctly. Right, so they they end up with a non first come first serve schedule the discipline. I mean, just because you get the, you know, all the credit doesn't really mean that.

86
00:11:54.030 --> 00:12:02.130
William Cheng: You implemented the colonel correctly. Okay. Alright, so, so the weenies documentation says that they're supposed to do a first come first serve. Q. Why do we do first come first serve.

87
00:12:02.490 --> 00:12:09.720
William Cheng: Why does. You know, why does the order matter. Okay, so we're going to see, you know, one of the main reason why you know first come first serve. Well, well, well, well.

88
00:12:11.100 --> 00:12:19.770
William Cheng: Why does the order actually matter. Okay. Alright. So. So first you first. All right. If you have a job that comes in. Over here when I take the job jobs are lined up and they're in the wrong key right so this will be the wrong key right

89
00:12:20.010 --> 00:12:27.660
William Cheng: All these job lined up whenever the CPU CPU sitting right here. I will never CPU become you know available, it will take the first job and running out of CPU.

90
00:12:28.290 --> 00:12:32.820
William Cheng: Okay, it will run until the completion, you get interrupted by the, you know, service routine and he will come back.

91
00:12:33.450 --> 00:12:44.250
William Cheng: So again you finish this why you go to next. So this is like our warm up to right you have a server. You know what it will do is it will pick up a job from Q2 and there's are serving it okay so its first come first serve to that.

92
00:12:45.810 --> 00:12:51.510
William Cheng: Alright, so what can we talk, you know, so, so, so we're going to run an example from the textbook.

93
00:12:51.780 --> 00:12:59.280
William Cheng: Okay, and the kind of performance mentioned, we're going to look at what we're gonna look at two different performance metric. One is the throughput right so

94
00:12:59.610 --> 00:13:06.990
William Cheng: So what is the super, super we mentioned before, it's a number of jobs per second and the jobs we define them with the find them are defined them already.

95
00:13:07.560 --> 00:13:12.780
William Cheng: Okay, so therefore we're going to compute the throughput. And the third is the bigger the better. Right. Yeah.

96
00:13:13.380 --> 00:13:19.320
William Cheng: So the, the, the, the goodness criteria we here is jobs per hour because we're going to use the example in the textbook.

97
00:13:19.740 --> 00:13:32.940
William Cheng: The example in the textbook. There's one big job that's gonna run for 168 hours while I'm going to 60 hours is you know 24 times seven, so therefore it's a job that will run for one week okay and then followed by 168 one hour job.

98
00:13:33.420 --> 00:13:43.230
William Cheng: And so if you look at the wrong killer either monkey over here. So I'm going to draw sort of a big job. You know, if the execution of the job is really long. Right. So the first one will be here this is jobs zero over here.

99
00:13:43.500 --> 00:13:54.240
William Cheng: Right job zero is going to execute for 168 hours and then comes 168 these little jobs over here. Each one of them is going to run for one hour there and there's 168 of them right

100
00:13:55.170 --> 00:14:02.820
William Cheng: There. So when should the RUN TO BE BE BE BE CLEAR. Okay. We also going to look at a situation where there's no new arrival

101
00:14:03.300 --> 00:14:14.220
William Cheng: Okay, the job. And I mean, you know, like our warm up to write the warm up to jobs, keep coming. Right. So in this case, you know, the all the jobs are there at time equals zero and no more jobs can arrive.

102
00:14:15.000 --> 00:14:23.340
William Cheng: Or as a new way, you can call this sort of a closed system. Right. So once all the jobs are he will close the door. Nobody can come in and now we tried to finish serving these job using a different kind of

103
00:14:23.820 --> 00:14:36.990
William Cheng: Using several as scheduling discipline. Okay. All right. So Job zeros here job. One is your job to all the way to Job 168 right there's 169 Job, Job zero is big. All the other jobs I want our law.

104
00:14:37.860 --> 00:14:46.530
William Cheng: Okay, so when are you supposed to finish servicing all the job well at exactly the end of the two week the second week you finish all the all the job because this one will take you

105
00:14:47.040 --> 00:14:57.120
William Cheng: Will take it exactly when we, when we have to finish and then all the eligible to also take you, you know, 160 hour, which is one way to finish. Okay, so you know what exactly we're going to finish servicing all these jobs.

106
00:14:58.500 --> 00:15:05.130
William Cheng: Okay, so, so that much. You know already, right. So, so what else, don't you know what you don't know the super you don't know the average waiting time. You don't know all that kind of stuff. Right.

107
00:15:06.060 --> 00:15:14.520
William Cheng: Alright, so, so, so let's take a look at the throughput picture for the first come first serve scheduler. Okay, so. So while it is a

108
00:15:15.000 --> 00:15:23.880
William Cheng: It's a horizontal axis overhears time right the vertical axis over here, stupid defined by jobs per hour at time equals to one hour over here. How many jobs have you served

109
00:15:24.660 --> 00:15:30.930
William Cheng: Well, somebody was a zero, right, because the first one is still being service. But that's really not fair because zero, meaning that you haven't done anything

110
00:15:31.350 --> 00:15:39.660
William Cheng: Right. The first job will be this big job over here. How much of the first job. Did you finish well after one hour you finished one over 168 of the first job.

111
00:15:41.610 --> 00:15:54.450
William Cheng: Okay, so, so, so I for one hour you finished one over 160 of the first job right, and then how did you compete with throughput by jobs, divided by the last time. So the job over here is one of the one in 68 the labs time over here. It's going to be go to why

112
00:15:55.230 --> 00:16:04.800
William Cheng: Okay. So at time equals to one hour. Your throughput is right. So you can see that this one is a little bit above zero so this point right here is one over 168 yeah

113
00:16:05.700 --> 00:16:15.900
William Cheng: All right, what about time you go to two hours. How many, how many jobs, what was going to be a super how many jobs have you finished while you finish to over 168 and a total elapsed times over here is going to be two hours.

114
00:16:16.350 --> 00:16:27.300
William Cheng: Okay, so therefore the two cancels out. So he's still exactly the same thing time equals two, three, then you have three here and three here, they're still cancel out. So all the way up to 168 hours.

115
00:16:27.780 --> 00:16:32.760
William Cheng: Okay, time to go to 160 hours. How many jobs you finished you finished one job right and

116
00:16:33.210 --> 00:16:39.870
William Cheng: What's the total elapsed time elapsed times 160 days or so to, same thing. You're still the same point is. So at the beginning of year is completely

117
00:16:40.470 --> 00:16:52.350
William Cheng: Complete straight line. Okay. All right. What about a time you go to 169 how many jobs that you finish. Well you finish two jobs right you finish one large job and the other ones. So, so, by the way, we don't distinguish large or

118
00:16:52.770 --> 00:16:56.730
William Cheng: Small jobs jobs jobs because over here. What computing jobs per, per hour.

119
00:16:57.480 --> 00:17:06.840
William Cheng: Okay. So at time you go to 169 we finish on the numerator or finished two jobs, one plus one right one. Good job was my job and the total elapsed time is 168 plus one.

120
00:17:07.770 --> 00:17:17.790
William Cheng: Okay, so this number is going to be equal to y equal to two over 169 right to over 169 is a little smaller than to over 168 right

121
00:17:19.110 --> 00:17:29.670
William Cheng: Maybe there's one in 60 days a bigger denominator. So, therefore, this number is smaller than this. So what is what I'm saying. Over here that this point right here it's a little less than twice as the previous report.

122
00:17:30.990 --> 00:17:34.770
William Cheng: Okay. So I talked to 169 we don't get to come. Super.

123
00:17:36.900 --> 00:17:42.630
William Cheng: As a, as a, as in the beginning case. Okay, so it's a little less than two times

124
00:17:43.230 --> 00:17:47.070
William Cheng: Yeah. Alright. So again, that's important fact over here. It's not exactly twice a little less

125
00:17:47.370 --> 00:18:03.390
William Cheng: What about kind of go to 170 right. So the numerator become one plus two over here and the denominator is going to be 168 times two plus two, right. So that will be equal to three times 170 and this number is going to be less than three over 168

126
00:18:04.050 --> 00:18:15.600
William Cheng: Guys okay 368 is the the three times original value over here. So now again. This one is a little further away over here so you can see that this, this line that there's going to be traverse. It's actually not a straight line.

127
00:18:16.770 --> 00:18:28.800
William Cheng: Okay so Australia will be yours proportional right over here, this is not proportional. We have a strange for action going on at tango 271 is going to be one plus three divided by 168 plus three, there will be four divided by 171

128
00:18:29.160 --> 00:18:43.650
William Cheng: Right. So again, it's still less than four times 160 so, so, so, so, as it turns out that this curve right here. You know, this career is slightly comebacks, whereas what a comeback combat. It's like this. Okay, so this one is like almost like a straight line, but it's slightly comebacks

129
00:18:44.760 --> 00:18:47.160
William Cheng: Alright, so that's the characteristic of this particular curve.

130
00:18:47.610 --> 00:18:52.710
William Cheng: So eventually, when times equal to 336 right so that's exactly two weeks.

131
00:18:52.980 --> 00:19:00.990
William Cheng: How many jobs have you have you finished well you finish 100 you know so. So the numerator is going to be one plus 168 right you finished all the jobs.

132
00:19:01.260 --> 00:19:09.210
William Cheng: The denominator over here is going to be 336 so this one is going to be able to 169 divided by 336

133
00:19:09.990 --> 00:19:19.590
William Cheng: Okay, so this number is a little bigger than 168 divided by 336. So what is 168 divide by 336 well that's equal to one half.

134
00:19:19.950 --> 00:19:26.970
William Cheng: Okay, so therefore this number is slightly bigger than a half. So that means that if you take this half point over here and draw straight line across

135
00:19:27.390 --> 00:19:31.980
William Cheng: The finish line over here will be slightly above 0.5

136
00:19:32.640 --> 00:19:46.710
William Cheng: Okay, so, so what's the significance of that right. So, so far, there's no significance significance if you just compute this one you know that I kind of go to 336 the the throughput is 169 divided by 330 say is going to be slightly bigger than a half

137
00:19:47.580 --> 00:19:50.670
William Cheng: Okay, so, so, so this is going to be the throughput curve right

138
00:19:51.150 --> 00:20:01.530
William Cheng: Okay, so how good is a super, super looks terrible. Right. You know, typically at the beginning my super is going to be zero almost zero. Right. And then in the end you know there's going to start getting better and better and better. Okay.

139
00:20:02.460 --> 00:20:12.750
William Cheng: Alright, so this is the characteristic of first come first serve. Okay. Alright, so let's take a look at, you know, what other things you can do. You can compute the average waiting time

140
00:20:13.170 --> 00:20:21.420
William Cheng: So again, the, the waiting time is that the waiting is basically the time you leave the system, right, because that time you go to zero, all the jobs are at the wrong. Q.

141
00:20:22.020 --> 00:20:27.240
William Cheng: Okay, so therefore, whenever you job leave that's going to be a waiting time right well also once a job either never come back into the rank you

142
00:20:28.560 --> 00:20:34.800
William Cheng: Guys are this case we have all the job and time to go to zero. We just need to sort of figure out what those job leave or that will that will give us waiting hot, they're

143
00:20:35.280 --> 00:20:49.260
William Cheng: Going to introduce some notation over here right job. J. I. Over here, we measure job 012 all the way to 168 so capital Jerry over here. That's the name of the job. Good. The execution time of the job at the CPU is going to be capital T. I.

144
00:20:50.280 --> 00:21:01.200
William Cheng: T is going to be actually using timer. So what do we have we have t zero equals 268 right T one is equal to 182 72 equals two to three all the way to 268 they're all equal to one.

145
00:21:02.160 --> 00:21:07.560
William Cheng: Okay, so those will be the execution time in order for us to compute the average waiting time for five fault.

146
00:21:08.400 --> 00:21:16.650
William Cheng: You know so. So again, this is not the same thing as the waiting time you warm up to, because we have to go with the textbooks definition right so let's say that job, J.

147
00:21:17.370 --> 00:21:24.960
William Cheng: Job. Jay, I started at time t is so time to be here is the start execution time over job that in this case one with the job we finished.

148
00:21:25.200 --> 00:21:35.760
William Cheng: Well, it's a little tip. Last couple of ti right so therefore loyalty i plus couple of Ti. That's when this job. This job will finish. So, therefore, that will give us the waiting time of job I

149
00:21:36.570 --> 00:21:42.480
William Cheng: OK, so the waiting I would die is, when does this job start executing inside of CPU, plus the execution time

150
00:21:42.690 --> 00:21:51.930
William Cheng: Well, so why is that because we have a non preemptive scheduler. Right. So once you start running out of CPU and if we assume that you know we don't care about interrupt. Then once you start then you know you

151
00:21:52.440 --> 00:21:56.220
William Cheng: You add your execution time that's going to be that that's going to be a time to eat the system.

152
00:21:56.850 --> 00:22:05.280
William Cheng: Okay, so, so, so therefore we have this relationship with the waiting time of it goes to a little tip plus capital T. I know what is a little tip.

153
00:22:06.120 --> 00:22:14.940
William Cheng: That a little tip is when your job start executing and what is your jobs are executing. Right. So if you think about a first come first serve a few over here. So here is my job I over here.

154
00:22:15.570 --> 00:22:24.900
William Cheng: Okay, what is my job start executing. Well, it's when all my all the job ahead of me when they finished running one then then then then then my jobs are executing

155
00:22:25.530 --> 00:22:42.270
William Cheng: Okay, so therefore little Ti is going to be the sum of the capital ti for GE capital T j for j go to zero minus y. Okay, so for all the job in front of me. If I just add up their service time or their execution time that's going to be my star, Tom.

156
00:22:43.440 --> 00:22:53.400
William Cheng: razon. Why is that true what because we have a we have a word concerning scheduler, a suit, you know, as long as there's work to do on our schedule has to keep the CV busy.

157
00:22:53.850 --> 00:23:00.390
William Cheng: Guy. So therefore, we know exactly when our job starts with all the if you add up all the service time for the job in front of us. That's going to be our start time

158
00:23:00.810 --> 00:23:11.010
William Cheng: Okay, so again the waiting for our job is going to be the start time of our job plus execution time. Right. So again, because, because we have a number, we have the scheduler. And we're ignoring all the interim either they interrupt time

159
00:23:11.970 --> 00:23:21.330
William Cheng: There. So now we have the waiting time for every job right. And can we compute the average waiting time why if you want the average waiting times that you add up all the waiting time and you divided by the number of jobs.

160
00:23:23.010 --> 00:23:35.730
William Cheng: Okay. So in this case, so, so, so, so let's go back to our example over here, right, what's going to be our average average waiting time. Right, so the waiting time of job number zero is what, what is the execution how which are number zero it's 168

161
00:23:36.870 --> 00:23:42.240
William Cheng: Okay, time to go to 168 jobs zero is going to be gone. Right. What am I waiting time with job number one over here.

162
00:23:42.450 --> 00:23:51.780
William Cheng: Why it's one hour later, right. So it's gonna be 169 right he has to wait for the first job to leave which take 168 hour and itself has one our execution time so it's going to plus wise wise.

163
00:23:52.080 --> 00:24:06.510
William Cheng: 69 waiting time of number two is going to be 170 waiting time of number three is gonna be 171 dot, dot, right, all the way to waiting time a 168. What is the way number 168 right it's going to go to 336 what everybody finishes.

164
00:24:07.920 --> 00:24:22.650
William Cheng: Okay. So in this case, what is the average waiting time right you add these numbers together right 168 plus 169 plus all the way to 336 right and then you divide by the number of job, who just 169. So what is this. Um, well, there's some it's a

165
00:24:23.700 --> 00:24:29.370
William Cheng: It's a sequence that you are one at a time. So, therefore, it's going to be the first term plus a plus the last term.

166
00:24:29.580 --> 00:24:37.170
William Cheng: multiplied by the number of terms of divided by two, right. So that's going to be 168 plus 336 right

167
00:24:37.410 --> 00:24:51.900
William Cheng: Multiply the number of terms over here is going to be 169 term right divided by two. That's going to be the numerator denominator is 168, you can see that wanders like the damage is 169 because you have 169 jobs. So the one is 69 cancels out.

168
00:24:52.140 --> 00:25:03.600
William Cheng: It's perfect right now guys on the numerator over here if you add these two number of is going to be 504 divided by two is going to be 270 sorry 252

169
00:25:04.950 --> 00:25:10.470
William Cheng: OK, so the average waiting times actually exactly 252 and you can actually do this by hand.

170
00:25:11.670 --> 00:25:15.780
William Cheng: OK, so the avenue anytime soon and 52. Well, what about the standard deviation

171
00:25:17.040 --> 00:25:24.210
William Cheng: While the standard deviation is harder to divide to do by hand over here. So what is the standard deviation. So remember the standard deviation is the square root of the various

172
00:25:24.450 --> 00:25:34.500
William Cheng: And the various of x and y is equal to the average of x square minus the square of the average right you have x over here and the whole thing square I hear that

173
00:25:34.770 --> 00:25:43.590
William Cheng: Right, okay. The variance or whatever you're trying to measure is going to be the average of, you know, the, the x squared minus the square of the average

174
00:25:43.980 --> 00:25:50.670
William Cheng: Okay, the square. The average over here. We already have it right this is 252 square. Okay, what about the average of x square

175
00:25:51.510 --> 00:25:58.830
William Cheng: What the average of x squared is that instead of adding up x you adding up x squared. Right. So you go to this equation, your square every term over here that

176
00:25:59.700 --> 00:26:06.090
William Cheng: And then you say, and then you add up all the squares and you divide 169 now you get the, the, the average of x squared.

177
00:26:06.840 --> 00:26:13.560
William Cheng: Okay, so you take this number. So, how to compute this number, or you can do this by hand. Right. So, therefore, you have to do this. Okay, you do by hand.

178
00:26:14.370 --> 00:26:25.950
William Cheng: Maybe somebody know the formula or I don't know formula or you can add them together over here you maybe write a program. And again, I'll be here. Subtract 252 square, you get a various you take the square of the various you get the standard deviation

179
00:26:26.940 --> 00:26:40.260
William Cheng: Okay, the standard deviation be calculated this way you're going to get 48.79 or so is so that standard deviation. What is the measure right then measure how much variation you have okay is 48.79 is a big standard deviation

180
00:26:41.550 --> 00:26:46.770
William Cheng: Well, if you if you are the small job right you're small job you're executing time is one hour.

181
00:26:47.220 --> 00:26:54.930
William Cheng: Okay. So you actually have one are on the average, you have to wait for 252 hours. So you're going to be very miserable right if you're a small job, you actually have is

182
00:26:55.590 --> 00:27:05.970
William Cheng: The one hour, but you're on the avenue of the way 252 hour and also you know that there are other jobs that are that are actually do that does better than you, by almost 50 hours.

183
00:27:06.600 --> 00:27:11.850
William Cheng: Okay, so if your average job, your average job over here, you're, you know, you're waiting time is going to be 252

184
00:27:12.450 --> 00:27:25.920
William Cheng: Okay, so since this variation is very, very large. You know that some people is going to be, you know, some people on the average is gonna you know it's going to be, you know, around 300 hours and then some people is going to be around 200 hours.

185
00:27:27.570 --> 00:27:36.510
William Cheng: Okay, so if your average job. You're going to be pretty upset because because this is, you know, this look really unfair because some people received much better service and some, you know, some other job receive you know

186
00:27:37.320 --> 00:27:48.420
William Cheng: Somebody out of here. You see much better service and some other job will be here received much worse service, right. So at least you can sort of compare yourself to say, well, at least I'm not, you know, the one over here that doing doing much worse.

187
00:27:49.680 --> 00:27:57.390
William Cheng: Okay, so. So in this case, it seems very unfair. So, so, what I mean is that when you look at the standard deviation is also give you sort of a sense of fairness.

188
00:27:57.930 --> 00:28:07.410
William Cheng: Right, if you have a large standard deviation over here that typically that means that the distribution of waiting time has large variation. So, therefore, you know what every job is seeing is very, very different.

189
00:28:07.710 --> 00:28:16.650
William Cheng: Okay. On the other hand, if you guys are gonna have a very, very narrow standard deviation. Right. So in that case, that will mean that everybody seen about the same waiting time so that appears to be fair.

190
00:28:18.240 --> 00:28:23.520
William Cheng: Okay, so, so this picture sort of tells you that you know the why, in this case first come first serve actually look very unfair.

191
00:28:24.540 --> 00:28:34.320
William Cheng: Okay. All right. Because you know what this is actually not fair because, you know, we're just me unlucky, right, because the first job is actually the biggest job. One of the first job is actually

192
00:28:34.980 --> 00:28:42.180
William Cheng: The biggest job so so if you look up the wrong tree over here. Okay, the wrong key over here right way in the beginning over here. Here's job zero. Here's the big job.

193
00:28:42.630 --> 00:28:48.030
William Cheng: Okay, why can job zero be right here right jobs. Yo, can I just put it right here we have a bunch of small ones over here where a bunch of

194
00:28:48.630 --> 00:28:56.130
William Cheng: Small one of the end over here. So, in that case is our average is going to perform better is our standard deviation is going to be better. Well, we don't know really needs a computer.

195
00:28:57.000 --> 00:29:03.480
William Cheng: Okay. As it turns out, if you go through all the analysis, you will find out that what we saw over here is actually the worst case for first confessor.

196
00:29:04.320 --> 00:29:11.010
William Cheng: Okay, the worst case of a focus on first over here is job zeros at the beginning over here and all the other jobs. I actually I'll be at behind. So that will be the worst case.

197
00:29:11.220 --> 00:29:18.990
William Cheng: And if you move jobs zero RAL you're going to actually get all kinds of different values of average waiting time. Okay, and also the standard deviation of the waiting time

198
00:29:20.070 --> 00:29:29.010
William Cheng: Or. So what is the true picture of first come first serve. So, so the real announces actually much more difficult. So that's why we look at one simple case and say, that was the worst case.

199
00:29:29.520 --> 00:29:35.160
William Cheng: What is the performance of first come first serve right performance, you know, support is terrible average waiting times terrible

200
00:29:35.610 --> 00:29:38.100
William Cheng: standard deviations terrible everything's terrible. Okay.

201
00:29:38.490 --> 00:29:48.180
William Cheng: So in general, how do you actually find the real average wedding helpful first compressor. Right. So in that case, you need to analyze all possible placement of jobs zero right there can be at the beginning of year.

202
00:29:48.930 --> 00:29:54.000
William Cheng: I should say it differently. You need to look at all possible variation of where you put the big job.

203
00:29:54.720 --> 00:30:01.980
William Cheng: Okay, you need to look at, you know, this particular position for the big job. And you also need to compute the probability that the job is sitting right here.

204
00:30:02.850 --> 00:30:07.800
William Cheng: Okay, so then you compute the average rating time. And then finally, when you try to figure out what the real everyone can happen is

205
00:30:08.040 --> 00:30:15.330
William Cheng: You need to look at the probability of you know the the big job being in any position you multiply that by the average waiting time I you something all

206
00:30:15.720 --> 00:30:27.300
William Cheng: Right, so you have to do a way to some of the Agile every waiting time depends on the probability of a pretty good configuration. And then finally you average all you know overall possible configuration. And then you're going to end up with Ed actually

207
00:30:29.040 --> 00:30:39.360
William Cheng: Alright, so we're not going to do that right so you know so. So in general, actually have five boys more difficult to compute need to look at all possible ordering of jobs and the probability to get each particular order.

208
00:30:39.870 --> 00:30:51.150
William Cheng: Okay, and then even do a way to sell right okay so so that's first come first serve look horrible so far. Alright, so what if you want to minimize the average waiting time

209
00:30:52.020 --> 00:31:01.980
William Cheng: Okay, so let's say that you know you know you can end up not doing anything right now so so quick. And so after waiting time. Sometimes they are related. Sometime you know their relationship so clear.

210
00:31:02.940 --> 00:31:10.350
William Cheng: But if we want to minimize average waiting time. Well, what can we do, okay, we can go back to the equation, right, the average rating time over here with all the equations like this.

211
00:31:10.770 --> 00:31:18.690
William Cheng: Guy's over here again we have that equation over here I you add up all the waiting time you divide by n well and over here is a constant, right, in our case over here.

212
00:31:19.230 --> 00:31:26.490
William Cheng: We have a closed system. Right. So, and doesn't change. Right. So in this case you want to minimize the average Joe anytime. All we need to do is to minimize the song.

213
00:31:27.120 --> 00:31:33.930
William Cheng: That so so now we're gonna change our problem over here, we try to minimize some over here. Okay. So what does this look like, right. So, again, for

214
00:31:34.290 --> 00:31:41.880
William Cheng: The waiting time for jobs zero over here is equal to t zero right the waiting time of job one over here. It's going to be equal to waiting to have a job zero

215
00:31:42.150 --> 00:31:48.270
William Cheng: Plus the extreme have a job number one, right. So, this one will be equals two t zero plus t one, right.

216
00:31:49.140 --> 00:31:58.260
William Cheng: Okay, so you need to add you're waiting time of all the waiting time in front of you right that's going to be a waiting time. Right, so the waiting time of two is going to be worse to t zero plus one plus t to

217
00:31:58.500 --> 00:32:02.730
William Cheng: The waiting time with job number three is going to be t zero plus one plus two.

218
00:32:03.300 --> 00:32:14.640
William Cheng: Plus two, three, you know, etc. And so you just need to add up all the job in front of you right the waiting time of the last job 168 is going to be t zero plus one, plus all the way to to 168

219
00:32:15.510 --> 00:32:21.150
William Cheng: Whereas, that's kind of obvious, right. So how do you minimize the, the sun, right, that you add them all up over here, right.

220
00:32:21.240 --> 00:32:28.650
William Cheng: So how do you add about right. So the way we've been adding them over here before was that we add up each row over here one row at a time and then we add them all up.

221
00:32:29.100 --> 00:32:38.790
William Cheng: Okay, there's another way to add a we're going to add one column at a time. Okay, so, so over here. How many times do you see t zero. Well, you see, t zero in every waiting time

222
00:32:39.420 --> 00:32:46.200
William Cheng: Okay. So, therefore, is going to be close to. So another way to write the some over here. It's going to be 169 times t zero right

223
00:32:47.580 --> 00:32:52.260
William Cheng: Okay, so, so you know what you can sort of think about is that every job experience the waiting time or the first job.

224
00:32:52.740 --> 00:33:03.570
William Cheng: Right. Because, because in order because we're doing first come first serve. Right. In order for you to get service. You have to, you know, wait for the, you know, everybody has to wait for the first job to finish, otherwise they will never get to finish. Okay, so therefore

225
00:33:03.960 --> 00:33:11.220
William Cheng: If you add up all the waiting time we're going to see T 01 hundred 69 times, right. What about to one one job number zero, it doesn't see to one.

226
00:33:11.490 --> 00:33:16.440
William Cheng: Right. But all the other job behind job number zero, they will all experienced the one they all have to wait together.

227
00:33:17.190 --> 00:33:25.680
William Cheng: You know, because there's no other way to wait because the first come first serve. Right. So then we're going to see 168 times t wine. Right. Okay. If you add up the number of them to one over here.

228
00:33:25.890 --> 00:33:31.650
William Cheng: The first one doesn't have to. Otherwise why and then you need to add 167 times the two

229
00:33:31.860 --> 00:33:44.220
William Cheng: And the 166 times two, three, and I said about. And then finally, the last one over here to 168 what only the last job well experienced 168 all the job in front of it. They will. They don't have to wait for 268

230
00:33:45.420 --> 00:33:55.950
William Cheng: Okay, so therefore you're gonna end up with the equation like that. So this is the equation of the average waiting time again and then you divide a 169 right so again that's a constant. We don't worry about it. So how do you minimize this expression.

231
00:33:57.210 --> 00:34:03.090
William Cheng: Okay. So in this case, what can you control. Right. The only thing you can control is t zero to 22 you can shuffle the jobs.

232
00:34:03.690 --> 00:34:15.720
William Cheng: Right in the beginning. Over here teaser over here is 168 because that's the biggest job we can move this job anywhere we want, right, if we're moving into the third job over here, then this be 168. What about t zero t zero become one.

233
00:34:16.440 --> 00:34:23.880
William Cheng: Okay, and why because all the other one become one. So we can, yeah, we can move these jobs are out there. So if you want to minimize this expression, what should we do

234
00:34:24.810 --> 00:34:34.800
William Cheng: Well, this, this. The other this number in front of it, they're not going to change. Right. It's going to be wanting to 69 time t zero. So, therefore, if you want to minimize the sun. She's zero need to be a small as possible.

235
00:34:35.940 --> 00:34:41.970
William Cheng: Okay. So out of all the T's teas over here, we need to find a smallest tea and they use that to multiply the laundry 69

236
00:34:42.180 --> 00:34:52.680
William Cheng: And we need to find a second smallest tea and then multiply that by 168 and use the third smallest to begin to multiply 167 if we do that, the entire expression is guaranteed to be minimized.

237
00:34:54.180 --> 00:35:03.570
William Cheng: Okay, so this is really not a formal Pro. I just give you an argument why order the job, according to their execution time from small to large will give you the minimal average waiting time

238
00:35:04.860 --> 00:35:11.730
William Cheng: Okay, so therefore, again, you know, this is this is a informal proof, but still it's approved to show you that if I want to minimize

239
00:35:12.030 --> 00:35:17.670
William Cheng: The average waiting time, all I need to do is to order the job from small to large according to their execution time

240
00:35:18.120 --> 00:35:29.550
William Cheng: Okay, so this scheduling policy is no shortage offers right because teaser over here is going to be the one with the shortest actually entitled smallest Asian time. So the scheduling policies that I want to schedule them right

241
00:35:29.880 --> 00:35:41.040
William Cheng: You know, so the smallest one. This one with the smallest. T, t, the smallest tea and then a second smallest the smallest tea. And I said, oh, line them up in the run queue over here. And now I can actually serve them first come first serve.

242
00:35:42.180 --> 00:35:49.110
William Cheng: Okay. So, but, but I need to sort them first, based on the exclusion and so this doesn't, that's why this. The other scheduling policies know as short as your first

243
00:35:50.250 --> 00:36:04.470
William Cheng: Okay, so you just saw proof to show you that if I want to minimize the average waiting time shorter job. First is the best scheduling policy, given all our assumptions right what our assumptions right no preemption know interactive job, all that kind of stuff. Okay.

244
00:36:06.630 --> 00:36:12.870
William Cheng: All right, so, so let's take a look at the shortest time job for us over here. So in this case, again go to go back to our

245
00:36:13.110 --> 00:36:24.270
William Cheng: Example, over here, right, all the job over here 126 11 they all ICU for one hour, right. So, therefore, this is all the one our job. And then the largest job is the weather run 468 hour. So this is the large job.

246
00:36:24.660 --> 00:36:31.890
William Cheng: Okay, so if you if you saw them like this. This is going to be the shortage offers right we still serve them one at a time. So now what's going to be the throughput characteristic

247
00:36:32.940 --> 00:36:36.810
William Cheng: Okay, at a time equals to one. How many jobs that you finish. When you finish one job.

248
00:36:37.230 --> 00:36:41.970
William Cheng: Okay. And then the last time is equal to one. So therefore, the throughput is why it's right here right now at this point over here.

249
00:36:42.360 --> 00:36:56.850
William Cheng: Time you go to you finish two jobs right over two hours. So God is equal to one time you go to three you finish three job in three hours before you finish for jogging for hours, got all the way to 168 you finished 168 job or 168 hours.

250
00:36:59.250 --> 00:37:06.450
William Cheng: So, so that that's what happens over here I well what so so this line is a straight line. Although 268. What about time you go to 169

251
00:37:07.080 --> 00:37:19.320
William Cheng: Well, in that case, how many jobs have you finished you finished one is 68 plus one over 168 right okay because we finished one over 168 of the biggest job and then the denominator over here is that we add another hour

252
00:37:20.700 --> 00:37:28.050
William Cheng: Okay, so this is this way is going to be 168 plus one over 168 divided by 169. So this number is clearly less than one.

253
00:37:28.890 --> 00:37:33.600
William Cheng: Right, because the denominator over here's 169 the numerator is one in 68 plus a little bit

254
00:37:34.230 --> 00:37:37.800
William Cheng: Okay, so therefore this curve is going to come down. What about time to go to 170

255
00:37:38.160 --> 00:37:44.790
William Cheng: Right. The numerator is going to be wanting to 68 plus to overwhelm the 68 denominator over here is gonna be 168 plus two.

256
00:37:45.060 --> 00:37:55.140
William Cheng: Is going to be 170. So again, this curve is going to come down a little more, a little more right having those 171 the numerator is going to be 168 plus three divided 168

257
00:37:55.350 --> 00:38:04.230
William Cheng: And the denominator is gonna be 168 plus three equals 170 wise. So again, you can see the squares are going to come down. Now what about time you go to 336

258
00:38:04.620 --> 00:38:16.290
William Cheng: Why not could enumerate over here is going to be 168 plus y is always going to be 169 the denominator over here is going to be wandering 68 plus 168 again. Are you going to equal to 236 we saw this number already

259
00:38:16.980 --> 00:38:25.110
William Cheng: Right. So this number study bigger than a half so this point over here. It's exactly the same a curve aside this point over here is exactly the same point.

260
00:38:25.320 --> 00:38:39.150
William Cheng: As the first come first serve under the worst case. Okay, the first come first serve the curve like this, right. You go almost zero here, slightly above zero is very difficult to draw at like that when it gets 168 slightly comebacks over here and then they need exactly the same point.

261
00:38:40.320 --> 00:38:50.190
William Cheng: Where. So actually, no matter was scheduling discipline that you use, as long as you use a word conserving since then we started out at time to go to zero what the super to zero, right, and then

262
00:38:50.550 --> 00:38:55.350
William Cheng: Of course you to jump to one over here for you do your job for us. We also know that they always end right here.

263
00:38:56.070 --> 00:38:59.520
William Cheng: Okay, so that means that we're all the other curbside the other car might look like this.

264
00:39:00.390 --> 00:39:08.280
William Cheng: That might look like this. They might look like this. Right. Okay. They can look all kinds of weird shape, but we know where it started. And then we know exactly where it that's

265
00:39:08.670 --> 00:39:17.310
William Cheng: Okay, because we have a work conserving us a scheduler right so we know, we know exactly where it was going to right yeah so that's very helpful to know

266
00:39:20.520 --> 00:39:25.470
William Cheng: Okay. So in this case, what is the, you know, to let me clear this quarter. What is the average waiting time

267
00:39:26.130 --> 00:39:33.990
William Cheng: Where the waiting time of jobs zero be here is equal to what, waiting to have a job zero is equal to y, y is equal to one hour right waiting time to go to Egypt. One is you go to why

268
00:39:34.290 --> 00:39:47.400
William Cheng: Why it's two hours right you know after the first two job is done right the waiting time of job number two is going to be three hours, all the way to where the waiting time job 167 is going to be 160 68 hours.

269
00:39:48.150 --> 00:39:55.320
William Cheng: Okay, and then the law job over here takes the longest right the 168 over here, the waiting to have is going to be 230 36

270
00:39:56.490 --> 00:40:01.680
William Cheng: Okay, so what is the way I view waiting time. Yeah. You add them all together. Right. So it's going to be one plus two plus

271
00:40:02.220 --> 00:40:09.030
William Cheng: All the way to 168 right and then you add 336 and you divided by 169

272
00:40:09.600 --> 00:40:18.630
William Cheng: Okay, so what is the song right again. The first one is 68 terms over here it's incremental, you know, a series. Right. So it's going to be going to one plus 168 right

273
00:40:18.840 --> 00:40:27.180
William Cheng: The first term plus the last term multiplied by the number of terms we wandered 68 over here and then divided by two. Right, that's going to be the sum of this term right

274
00:40:27.510 --> 00:40:40.950
William Cheng: Plus 336 divided by 169 right this is 169 this one and this one, cancel out. So what you're going to end up with is 168 divided by two that will be 84 right plus

275
00:40:41.310 --> 00:40:49.710
William Cheng: 336 divided by 169 that 336 divided by 168 is what is equal to two.

276
00:40:50.070 --> 00:41:04.740
William Cheng: Okay, so this number is slightly less than two. So therefore 84 plus number slightly less than two is going to be slightly less than 86. Okay. As it turns out, if you do the actual computation over here, the average waiting time is going to be slightly less than 86 is going to be at 5.99

277
00:41:05.790 --> 00:41:16.020
William Cheng: Well, so again you can see that, you know, you can actually do this by hand and sort of figure out what it is. Right. So what about a standard deviation. Right. Again, you need to calculate the other, the average

278
00:41:16.560 --> 00:41:23.700
William Cheng: Size, the various the variance is the average of x square right so you square every term over here one square to square, all the way to 168 square

279
00:41:23.940 --> 00:41:36.300
William Cheng: And then 233 and 36 square you add up all the square divided by 169 you get average of x squared, right, and then you minus, you know, this one square. That will give you the various you take the square root, you get 52.6

280
00:41:37.200 --> 00:41:46.590
William Cheng: I don't know if you remember for the first come first serve case even under the worst case, the variance is about 48 points something almost 49 okay so this one is even worse.

281
00:41:47.700 --> 00:41:49.350
William Cheng: Okay, why isn't even worse.

282
00:41:51.270 --> 00:41:52.650
William Cheng: Well, so I'll be here right. It says

283
00:41:53.400 --> 00:41:58.950
William Cheng: Get the average rating number of years is much, much better. Right, so, so, so again the before, what would we have right

284
00:41:59.100 --> 00:42:08.340
William Cheng: We have a curve that looks like this. It's really awful we here. This is a, you know, I guess is what 252 right here on the average right and the variance is really big.

285
00:42:08.580 --> 00:42:19.710
William Cheng: So now the average waiting time is much smaller, right. This one is about one third of that right so you can do that by three you get at something right so it's about one third of that. But now the standard deviation over here is going to be even worse.

286
00:42:20.430 --> 00:42:21.570
William Cheng: Okay, why is it even worse.

287
00:42:22.410 --> 00:42:30.870
William Cheng: Well, because we give preferential treatment to small jobs. So this means that the waiting time for the Lord job is going to be worse, right. So, therefore, we are actually stretching out

288
00:42:31.110 --> 00:42:38.700
William Cheng: The distribution, the distribution of you're actually going to make it worse. Okay. Because we are preferring small jobs. So the small job they're going to have a small

289
00:42:39.480 --> 00:42:48.810
William Cheng: waiting time and the large jobs, therefore, they don't have a worst the worst waiting time. So if you ask the average them all together. Okay, you're going to end up with a sort of a bigger

290
00:42:50.280 --> 00:42:56.430
William Cheng: Sort of a bigger deviation. So get the deviation over here tells you how strict are spread out the data is

291
00:42:57.150 --> 00:43:07.500
William Cheng: OK. So, therefore, if you give preferential treatment to small job the larger boy longer and then you stretch out the distribution. Okay, I'm in the area under the curve are still the same, but now he's stretch out the distribution. Yeah.

292
00:43:08.340 --> 00:43:11.700
William Cheng: Alright, so the point over here is that this makes sense. Yeah.

293
00:43:12.990 --> 00:43:13.530
William Cheng: All right.

294
00:43:15.330 --> 00:43:20.940
William Cheng: So what if short jobs. Keep arriving guys always we will have a closest them as over here and you know

295
00:43:21.330 --> 00:43:27.150
William Cheng: So this is what the you know the large ones right here. The small job at the beginning, over here, right, we have a closed system.

296
00:43:27.450 --> 00:43:36.840
William Cheng: So in this case, the shorter job. First is going to be the optimal solution. It's optimizing the average waiting time. Okay, so there's no way to beat this average waiting time. Yeah.

297
00:43:37.410 --> 00:43:41.670
William Cheng: So, it asked a question or what if the short jobs, keep driving right so if I had a job arrivals.

298
00:43:42.090 --> 00:43:52.710
William Cheng: Okay, like our warm up to assignment right over here. You know, so after you know you start running your scheduler. What is more Java right over here. Okay, if we want to minimize the average waiting time. What should we do

299
00:43:53.730 --> 00:44:01.380
William Cheng: Okay, if you want to minimize our average waiting time, then we need to make sure that you know the run you over here is always sorted based on their execution time

300
00:44:02.250 --> 00:44:14.130
William Cheng: Right. So if all these jobs over here. Well, one our job. And then the last one of us 160 68 if the new job that comes in. Over here is, you know, they actually time is going to be one hour. What would you put it

301
00:44:15.000 --> 00:44:21.570
William Cheng: Why, again, if you want to minimize the average waiting time you will put this one in front of the 168 job over here and then put it right here. Right.

302
00:44:22.740 --> 00:44:34.950
William Cheng: Okay, because I need to make sure why wouldn't you put it in front of your other job because the job has been waiting already. It's kind of unfair to put in front of them, right. So, therefore, if they all tie over here for the waiting time over here. Then I'm going to put it, you know.

303
00:44:36.090 --> 00:44:43.590
William Cheng: At the end of all the one hour job that what is the job that are right over here, only the execution time is 0.5 hour

304
00:44:44.970 --> 00:44:47.520
William Cheng: Okay, so in that case, I have a job running out of CPU over here.

305
00:44:47.820 --> 00:44:58.050
William Cheng: So in this case, again, what I want to do is I want to minimize the average waiting time. So in that case, I still need to sort all the job base on. So in this case, you know, if I'm allowed to pre empty jar from the CPU.

306
00:44:58.320 --> 00:45:01.710
William Cheng: And so, so far we talked about know preemption. What if you allow preemption.

307
00:45:02.580 --> 00:45:11.250
William Cheng: That if the job that you're running out of CPU you finish only point one hour. So, this one has a remaining service time right i mean service is how much more time it will take for you to finish.

308
00:45:11.400 --> 00:45:18.960
William Cheng: Is going to be 0.9 hours right and a new job over here is going to be 0.5 hour. What I would need to do is I will actually put this one back on the wrong you

309
00:45:19.140 --> 00:45:29.400
William Cheng: Are as a drunk over here is going to have a 0.9 job sitting over here, followed by all these one hour job over here and then followed by the 160 our job. And then inside the CPU over here. I'm going to run the 0.5 our job.

310
00:45:29.640 --> 00:45:32.820
William Cheng: Why do I need to do that because I want to minimize the average waiting time

311
00:45:34.380 --> 00:45:43.770
William Cheng: Alright, so, so the equation that we saw saw previously the or the proof that we saw before, is still valid. Right. So, therefore, if you want to minimize average waiting time you know exactly what needs to be done.

312
00:45:45.330 --> 00:45:57.420
William Cheng: Okay. All right. So, so I'll be here. I ALSO WANT WANT WANT WANT WANT WANT TO MENTION over here that if you have a small jobs. Keep arriving, then this large job will never get to run right under what condition would never get around.

313
00:45:58.050 --> 00:46:05.040
William Cheng: Okay, if we go back to the notation to warm up to write the arrival readers called, it's called lambda, the service right over here is color is going to call me.

314
00:46:05.280 --> 00:46:15.510
William Cheng: If lambda squared is greater than or equal to meet you, then what happened is that the queue over here can actually start building up to infinite Tulane or in that case the large job. I never get a chance to execute

315
00:46:16.380 --> 00:46:20.970
William Cheng: It. So, therefore, if you are the owner of this larger you're going to be very upset. You're going to be very upset.

316
00:46:21.510 --> 00:46:27.150
William Cheng: Okay. You say, Well, how come you know all the small job getting front of me. I never get to run. So, therefore I'm going to go to a different vendor.

317
00:46:27.690 --> 00:46:37.530
William Cheng: Okay, so this is how you're going to lose customer. Yeah. So, therefore, if you have starvation job never get the runs out of CPU. This is unacceptable for scheduling policy.

318
00:46:39.390 --> 00:46:44.580
William Cheng: Or so. So in. So in the real world, we've got to be very careful because shorter job. First is really unusable.

319
00:46:45.270 --> 00:46:53.100
William Cheng: Guys, especially if you if you allow a rival. Right. So one thing that we can do is I'm going to actually close the door. Why, in that case, we don't have to worry about arrival. So because sooner or later this job will get to run

320
00:46:53.430 --> 00:46:58.680
William Cheng: Right, so maybe that will be a minor modification. You can make them a shortage offers. Okay. All right.

321
00:46:59.790 --> 00:47:08.760
William Cheng: You know, in the case if you allow preemption. Right. Yeah, we're going to do shortage offers. But in this case, we're going to use a different name, right, because the shortage. Our first is

322
00:47:09.420 --> 00:47:13.350
William Cheng: The shortage of first is reserved for the case where there's no new arrival

323
00:47:13.980 --> 00:47:19.530
William Cheng: Ok we have new arrival and also if you allow preemption preemption, then you know the basic idea is short offers

324
00:47:19.950 --> 00:47:25.440
William Cheng: But the Q AMP discipline or the scheduler is actually called something else is called the shortest remaining time next

325
00:47:26.340 --> 00:47:32.730
William Cheng: We're going to look at the remaining service time. Oh, well, the job and then we're going to make sure that we execute the job with the smallest remaining service time

326
00:47:33.240 --> 00:47:41.580
William Cheng: Whereas, in a way, this is the dynamic version of the shortage offers right because now you're wrong. So why, why is it dynamic right but the jobs a lot to arrive.

327
00:47:41.760 --> 00:47:52.800
William Cheng: When the job arrived and you also allow preemption. You might have to bump off the job or running out of CPU, put it back in the queue. This way, you know, if the new job that arrive at smaller service time or then that job has to go first.

328
00:47:53.970 --> 00:47:58.800
William Cheng: Or is it again, you know, shorter job. First is only used for the case when it's non preemptive

329
00:47:59.670 --> 00:48:13.380
William Cheng: Okay. And also you have a closest them. So even if you have open to say you have preemption. Well, then we have to use a different name the SRT no shortage remaining service service time. Next, that's the one that gives you the minimize the minimal average waiting time

330
00:48:14.580 --> 00:48:14.820
Okay.

331
00:48:16.650 --> 00:48:17.880
William Cheng: All right, uh,

332
00:48:19.380 --> 00:48:22.890
William Cheng: Alright, so let's talk a little bit about, you know, the idea of fairness.

333
00:48:23.880 --> 00:48:33.060
William Cheng: So when you go to the bank, you see a first come first serve. Cute, right when you go to the supermarket, you see a first come first serve. Q. Why do people like first come first serve. Q. We just saw that the performance is terrible.

334
00:48:33.750 --> 00:48:42.030
William Cheng: Right. I mean, you probably experienced that, you know, like, well, you go to the supermarket right you you get in line and then turns out your way forever because the first person that's being served takes forever.

335
00:48:42.330 --> 00:48:44.970
William Cheng: Right. They say, oh, I'm really unlucky. Maybe I should go into a different line.

336
00:48:46.140 --> 00:48:50.370
William Cheng: Okay, but, you know, so why, why do we say I took the first conference over here is fair.

337
00:48:51.600 --> 00:49:03.570
William Cheng: What because sooner or later you're going to get served right okay there's there's absolutely no way for you to start even though you might wait for a very long time. But first come first serve guarantee that you will always get service as long as you stay inside the wrong. Q.

338
00:49:04.830 --> 00:49:08.100
William Cheng: Okay, so every job eventually gets processed right what

339
00:49:08.400 --> 00:49:20.400
William Cheng: Is that fair. What if that's your only measure of fairness, what I see is very, very fair. Right. So sometimes we all want to want to look at other kind of stuff in term Fair. Fair. And as for example the, the other standard deviation of the waiting time right that you might look at that.

340
00:49:21.630 --> 00:49:28.770
William Cheng: As fairness. Right. They use a first come first serve is not fair because some people service time is really, you know, waiting time is really sure some people will have really long.

341
00:49:29.040 --> 00:49:34.320
William Cheng: But if you only look at the, you know, whether you eventually don't get server. Now, one of the first come first serve is very fair.

342
00:49:34.980 --> 00:49:42.960
William Cheng: Okay, so when you get into the supermarket. All you need to do is to choose the line right and then you know you are literally sooner or later you're going to get, sir.

343
00:49:44.190 --> 00:49:49.710
William Cheng: Okay, same thing when you go into the bank right sometime bank only have one queue. So you get into the Q sooner or later you sooner or later.

344
00:49:50.700 --> 00:50:03.030
William Cheng: You're gonna get sir. Yeah. All right, there's a shortage of first and this shows remaining service service time. Next, the long job might have to wait in definitely okay so therefore they are really not acceptable.

345
00:50:04.470 --> 00:50:08.190
William Cheng: Alright, so, so here. So the asked, you know, what is the good measure of fairness.

346
00:50:08.430 --> 00:50:20.070
William Cheng: As it turns out, there's actually some some good very difficult, difficult to define. So later on I'm going to sort of try to define that. And the aisle, because people study this to death because it's very, very important for a scheduler. To be fair, yeah.

347
00:50:21.720 --> 00:50:32.070
William Cheng: All right, so I think this is a good time to break so you know it's 15 minutes into, you know, just the first video, so we're gonna come back and want to talk about some more scheduling policy right. All right.