WEBVTT 1 00:00:01.860 --> 00:00:11.910 William Cheng: Welcome to the last lecture of the semester. So, Colonel three of courses do this Friday. If you have code from previous semester, don't look at them. Don't copy them best to get rid of it. 2 00:00:12.480 --> 00:00:23.130 William Cheng: Grading guidelines, the owner will grey and you must copy K through Remi into VM readme txt and deal with all the question marks after you make a submission and make, make sure you verify your kernel submission 3 00:00:23.670 --> 00:00:33.480 William Cheng: Form the grading guidelines, step by step, and then, you know, guess I still at the same time over here, you should read test retest everything 4 00:00:33.990 --> 00:00:43.980 William Cheng: To make sure and then you need to change company Diane K according to the grading gala, and because that's what the greater has to us. Okay, that you could avoid it doesn't have any choice the grid has to follow the grading guidelines. Okay. 5 00:00:44.880 --> 00:00:58.470 William Cheng: This Friday. You know, there's no discussion section. I don't do review sessions, because everything cover in this class. They're all important our lecture slides are a lot of details, you should use that as a study guide, similar to the mature. 6 00:00:59.700 --> 00:01:00.060 William Cheng: Alright. 7 00:01:01.170 --> 00:01:11.970 William Cheng: So for Colonel three and again this is very important. I last time I mentioned this already. By default, the greater will assume that you are running a spin in it. Okay, so if you're running has been in it. 8 00:01:12.810 --> 00:01:18.120 William Cheng: You know, so, so if we just started you know compile and run around weenies it will run ASP. NET. 9 00:01:18.600 --> 00:01:26.160 William Cheng: Then all the grading guidelines, you know that the greater than all the commands of greater will type. It simply following the grading guidelines, there'll be nothing special. 10 00:01:26.700 --> 00:01:31.200 William Cheng: Okay, so that will be the expected case right all the programs should be able to run from has been an ad 11 00:01:31.800 --> 00:01:41.190 William Cheng: So we don't have to do anything like a shower or something like that. Yeah, so you can run as fit in that, you know, run a five minute proc run. So in this case, there's no need for cash out anywhere. 12 00:01:41.790 --> 00:01:47.250 William Cheng: Okay, so, so, so in that case, I guess. Okay, this is the case, the greater will not will not run Keisha 13 00:01:48.030 --> 00:01:55.380 William Cheng: Okay, you only run Keisha if you're ready to do some points. Okay, using Keisha you're going to end up you know some of the stuff is only half the credit or something like that. 14 00:01:55.590 --> 00:02:02.760 William Cheng: So, so don't ask the crater. The greatest around Keisha unless you're ready to lose points. Okay. I hope I make I made this really, really clear. Yeah. 15 00:02:03.450 --> 00:02:13.830 William Cheng: All right. I, for some reason, you can spin it, then the best thing to do is run Keisha only if you cannot has been in it. Right, so use case. Y'all come in and every case shell commands to run one sub test. 16 00:02:14.280 --> 00:02:24.810 William Cheng: You know, integrating online. Okay, now run the entire test just one sub test. Okay, so this case you need to document them very, very carefully. So this way, the grid can give you as many points as possible. 17 00:02:25.590 --> 00:02:34.950 William Cheng: Okay. So in this case, they will only apply to Section B and D of the grading guidelines, because see is running user level shell. So if you cannot get a spin is run, you don't get any credit 18 00:02:35.520 --> 00:02:44.160 William Cheng: For section B and it's still possible to get full credit you're using this method for Section D, you will most get 50% of the the 19 00:02:45.240 --> 00:02:51.120 William Cheng: 50% of the points. Okay so running Keisha there's a penalty. Okay, so please understand, all right. 20 00:02:52.410 --> 00:02:58.920 William Cheng: OK. So again, if that's the case, you know, write it in the readme file as much detail as possible to make sure the greater knows how to grade. 21 00:03:00.060 --> 00:03:09.120 William Cheng: To grade your assignment. Okay. Right. So again, the greatest not allowed to deviate from the grading guideline but but again you need to get the girl, give them names and things like that for the for the for the commands to run 22 00:03:10.920 --> 00:03:20.130 William Cheng: Alright so final exam. We're going to have a take home exam, right, we're not doing an online exam because you know you're going to download the exam, just like the midterm, you work on it and then you submit it. Okay. 23 00:03:20.880 --> 00:03:26.910 William Cheng: So, so what's important is the first thing is important that you, you are not, you know, you cannot go take the exam, the wrong section. 24 00:03:27.510 --> 00:03:32.520 William Cheng: Alright, so, so some people I'm every semester. There's some people went to the wrong one example. I don't know how can this happen. 25 00:03:33.270 --> 00:03:37.680 William Cheng: Maybe because people don't pay attention to the cost webpage very clearly says 26 00:03:38.010 --> 00:03:45.330 William Cheng: That then sections are for these two section numbers right so you should know which you know which section, you're registered for and then find out which section at us. 27 00:03:46.020 --> 00:03:57.540 William Cheng: Okay, if you're registered for these tools to sexual. I call it a dance actually even though you know there's local and remote the kindness of the admin, not just when I call it if you register for these two section, you are a dense section student 28 00:03:58.230 --> 00:04:06.570 William Cheng: Okay, as a nutcase your final exam will be 9am to 9:40pm 9am to 9:30am on Friday, May 8 29 00:04:06.960 --> 00:04:20.070 William Cheng: Okay, if you register for 3031 I'll call out the AM section right your final exam. So again, the final exam time doesn't mean that's AM, PM, whatever. It just happened to be in this way. Yeah. So again, you know, a match all these numbers look at your 30 00:04:20.520 --> 00:04:29.430 William Cheng: registration information. The final which section you belong to. If you belong to the AM section then your exam is going to go from 999 O'clock 9:30am on Tuesday. 31 00:04:30.150 --> 00:04:39.660 William Cheng: May 12 and the PM section is that if you register for section 29971 of the example go from three o'clock to 3:30pm on Wednesday, you know, March 13 32 00:04:40.590 --> 00:04:48.870 William Cheng: Now, so if you have any doubt, if you have any doubt, you know, send me email ask for clarification, right, don't assume anything 33 00:04:49.170 --> 00:04:54.330 William Cheng: Okay, because you're going to end up you know getting zero in the final exam. Okay. There's nothing I can do. If you go to the wrong section. 34 00:04:54.690 --> 00:05:04.740 William Cheng: Okay, if the final exam calm. You say, Oh, I went to the wrong section. Can I take the exam in this other section. No, you cannot do that because the final exam is going to be different for all three sections. 35 00:05:05.760 --> 00:05:10.860 William Cheng: Okay, so, so, so every section good a separate curve. You cannot take the exam in the wrong section. 36 00:05:11.490 --> 00:05:17.790 William Cheng: All right. The only thing you can get as zero. If you go today. Take aroma. Okay. I hope I make myself very, very clear. Yeah. 37 00:05:18.570 --> 00:05:22.290 William Cheng: I mean, some people just don't take this thing seriously so that there's nothing I can do. Okay. All right. 38 00:05:22.740 --> 00:05:31.290 William Cheng: The final exam. There's new question type calculation question. You will need to be able to compute a schedule and calculate things like average waiting time standard deviation 39 00:05:32.070 --> 00:05:40.290 William Cheng: Without using a calculator. Okay, so, so, I mean, clearly, if you're able to take, you know, square root of some really weird number. I know you're, you know, 40 00:05:41.010 --> 00:05:43.920 William Cheng: You're cheating. So they don't do that. Okay. 41 00:05:44.370 --> 00:05:53.580 William Cheng: All right, so, so you can leave answer in the form of fractions and square roots. Okay. You don't have to be able to compute that right but but again you need to get the form right there. 42 00:05:53.820 --> 00:06:02.310 William Cheng: Any kind of addition and multiplication, you have to add them out. You have to multiply them out. Otherwise, you know, for every little mistake. You know, you're going to get the data at least half a point 43 00:06:03.030 --> 00:06:08.580 William Cheng: OK. So again, just like the mid term. Okay. Any little mistake at least have a plan of action. Okay. 44 00:06:08.970 --> 00:06:22.380 William Cheng: And last lecture, I mentioned Australia scheduling, you must use the algorithm mentioned in the last lecture, which is lecture 29 and not the one in the textbook. If you run the algorithm in a textbook, you will get zero credit for it. Okay. 45 00:06:23.910 --> 00:06:29.940 William Cheng: All right, so, so get the final exam is going to be, you know, the same format as the midterm. I'm going to send you you know 46 00:06:31.380 --> 00:06:40.170 William Cheng: You know, you're going to get a, get a private email that gives you a download link and download your version of the exam. And then there's answer sheet. You need to use, you know, I said. 47 00:06:40.590 --> 00:06:50.490 William Cheng: There's a formula that proper procedure and also in order to be eligible for the final exam, you are required to submit a new academic integrity on a co pledge. 48 00:06:51.030 --> 00:07:01.950 William Cheng: Okay, the mill. The one you mentioned recess for midterm. Right. So, there will be a separate one for the final exam and you have to promise me that you will not cheat, right, because if you cannot make that promise you will not be allowed to take the final exam. It's that simple. 49 00:07:03.390 --> 00:07:12.840 William Cheng: Alright, so I don't know why some people will do the last minute. Okay. And maybe you want to stress yourself out or something like that. If you miss the deadline, you are not eligible for the final exam, you're gonna get zero. 50 00:07:14.160 --> 00:07:17.610 William Cheng: Or so. So I'm going to do this, you know, run the beginning of next week. 51 00:07:17.850 --> 00:07:26.850 William Cheng: Okay, so I'm gonna give you plenty of time to do it. I highly recommend you to do it as early as possible and not as late as possible bed because because when the time or the final exam time come around. 52 00:07:27.120 --> 00:07:31.410 William Cheng: There is no pledge from you that guess what you are not getting a final exam, you'll get a zero. 53 00:07:32.010 --> 00:07:42.750 William Cheng: Okay. So remember, the only way to get excuse when the final exam is to have a documented illness or document a family emergency in that case you will get an incomplete and you take the final exam in the next semester. 54 00:07:43.560 --> 00:07:46.770 William Cheng: Okay, there is no other reason you are permitted to get incomplete. Great. 55 00:07:48.180 --> 00:07:53.880 William Cheng: Okay, so again, all these rules are set in stone. There's nothing I can change. Okay, so if you don't want to take this seriously and I'll get I'll be 56 00:07:54.420 --> 00:08:01.680 William Cheng: Getting a big zero in your final exam. There's nothing I can do. Yeah. All right. I just, I met her. We're going to have a rehearsal. So again, 57 00:08:02.220 --> 00:08:10.260 William Cheng: We're gonna see that the final exam, you know, the format is going to be basically the same. But there might be additional requirement, you have to do. Right. So again, you need to follow the instruction and then the 58 00:08:10.740 --> 00:08:17.430 William Cheng: To the rehearsal. Some people decide not to do the rehearsal, if you decide not to do really rehearsal, that's fine. If you do the final exam wrong and you get 59 00:08:17.970 --> 00:08:32.520 William Cheng: To get a big zero again. There's nothing I can do. All right. You have to do what's required of you when it comes to the exam, right. So again, I have one rule for everyone. I cannot make exceptions. Alright, so, so, so, um, yeah. I hope you're taking all these things very seriously. Okay. 60 00:08:34.350 --> 00:08:46.500 William Cheng: Okay, you have any questions about the final exam, you know, send me email. So after today's lecture, I will also post the final exam topics. So again, the final exam. We're not overlap with the midterm right i mean 61 00:08:46.890 --> 00:08:51.900 William Cheng: As far as the coverage is concerned, there's no overlap but but clearly the second semester material depends on the 62 00:08:52.200 --> 00:08:56.940 William Cheng: The, the second part of the semester, the material depends on the first part of the the the the 63 00:08:57.180 --> 00:09:06.390 William Cheng: Semester. So therefore, I will not say that, you know, I will only as things that are in the second semester because somebody will say, oh, that's one of the first the first part is semester. You are not allowed to ask that question. 64 00:09:07.170 --> 00:09:15.120 William Cheng: Okay i i don't want, I don't want that kind of stuff. So, therefore I'm going to say the final exam is going to be focused on the second half of the semester. 65 00:09:16.200 --> 00:09:24.240 William Cheng: Okay, so, so even though the coverage will not overlap. If I asked the question that you're supposed to know even though is based on the first part of the semester, that would be okay. 66 00:09:24.930 --> 00:09:32.670 William Cheng: Okay, because I don't want arguments that you are not allowed to ask questions like that. Right. Some people get really, you know, really defensive, you know. So anyways, I really don't want to go there. 67 00:09:34.170 --> 00:09:41.610 William Cheng: Okay, so, so, so we're going to, sort of, you know, first finish chapter five. So let's go back to, you know, scheduling. 68 00:09:42.150 --> 00:09:47.520 William Cheng: So last time we finished up strike scheduling and today we're going to look at the nanny part of chapter five. 69 00:09:48.000 --> 00:09:54.060 William Cheng: First, we're going to guess. We have two more schedulers to cover. So these are scheduling in real time systems. 70 00:09:54.720 --> 00:10:03.660 William Cheng: Now, so I mentioned. What's special about real time system right every job when they come to the rescue. They come with a deadline to say that this job has to finish before the deadline. 71 00:10:04.920 --> 00:10:11.460 William Cheng: Okay, so, otherwise you know catastrophe going to happen and we say that there are two different kind of system. There's a soft real time system. There's how real time says that 72 00:10:11.700 --> 00:10:16.650 William Cheng: The higher real conscious than the deadline is serious, right, because otherwise it will be catastrophe and all that kind of stuff. 73 00:10:16.920 --> 00:10:22.320 William Cheng: For the soft real time system. If you missed the deadline. It's really not a big deal right so it was never we're not going to pay attention to the soft 74 00:10:22.650 --> 00:10:26.490 William Cheng: Soft real time system. Okay, we're going to focus on the hardware time system. Okay. 75 00:10:26.910 --> 00:10:33.240 William Cheng: All right. So in this case, you know, the scheduling requirement over here, become you know not to sort of minimize waiting time on that kind of stuff. 76 00:10:33.510 --> 00:10:41.760 William Cheng: The requirements that we have to satisfy every deadline, right, because if we miss a deadline is going to be crashing people is going to die, so therefore that's not allowed to happen. 77 00:10:42.510 --> 00:10:49.980 William Cheng: Okay, we're going to look at to, you know, scheduler for for, you know, for, for the case when there's only a single CPU. 78 00:10:50.430 --> 00:11:00.870 William Cheng: Because typically for multiple CPU and in the, you know, the problem is so hard that is so, sort of, you know, research problem, the solution is going to be MP. MP completed be hard. 79 00:11:01.560 --> 00:11:06.780 William Cheng: So again, we're not going to look at those cases, because this is sort of introductory class I think even in 80 00:11:07.170 --> 00:11:16.200 William Cheng: Double E's they they they they also they offer you know real time, you know, system class. So if you're really into, you know, real time seven users take one of those class. Yeah. 81 00:11:16.920 --> 00:11:23.070 William Cheng: The two kinds of, you know, the scheduler. We're going to look at. One is called was a really fancy names called re monotonic scheduling. 82 00:11:23.760 --> 00:11:29.340 William Cheng: The other one is called earliest airline burst of the early deadlines. First, if you have taken CS 570 probably seen 83 00:11:29.640 --> 00:11:40.470 William Cheng: You seen that scheduler already, you also probably have seen a proof a mathematical proof to say that, under certain assumption the Earliest Deadline First scheduling policy is the optimal policy. 84 00:11:41.370 --> 00:11:52.950 William Cheng: Okay, so, so the case that we need to deal with. Do they satisfy that requirement. Well, maybe not right but but if you know that this particular scheduler is optimal under shouldn't certain condition or sometime you know it might be really good. 85 00:11:53.520 --> 00:11:58.890 William Cheng: Okay, so therefore, again, that should be one of the scheduling policy, we should consider, even though we might not work with we 86 00:11:59.400 --> 00:12:05.160 William Cheng: Might not meet all the requirements. Okay, so that's one of the one we're going to see, and the other one is called re Montana scheduling. 87 00:12:05.610 --> 00:12:10.500 William Cheng: This is the scheduler for for scheduling cyclic chores or periodic task. 88 00:12:10.920 --> 00:12:22.410 William Cheng: Okay, so these are the these are the sort of the nature of the task is that they are periodic guy. They need to be run every few seconds, every few minutes every few hours net so we're going to sort of define for every job. There are two parameters. 89 00:12:22.830 --> 00:12:31.530 William Cheng: One of them is called T capital T capital T is before this, the execution time of that job. Okay. But this job is going to come over, over and over and over again. How often do they 90 00:12:32.550 --> 00:12:46.200 William Cheng: Do they do they have to be executed. That will be the period, there is a PR RPi over here will be the period for this job there. So for example, if a job is required to execute two seconds, every six seconds. 91 00:12:47.790 --> 00:12:48.150 William Cheng: Okay. 92 00:12:52.110 --> 00:13:02.370 William Cheng: Okay, so you have a job required to execute two seconds, every six seconds. So in this case I will be equal to two, because that will be the per cycle exclusion time and then the period over here will be equal to six. 93 00:13:03.660 --> 00:13:09.120 William Cheng: Okay. So in this case, you know something about, you know, the scheduling already, if this is the only job that I run 94 00:13:09.930 --> 00:13:20.820 William Cheng: Okay, I will eat up one third of the CPU, right, because you know to divide by six is one third right every six seconds. I've spent two seconds on this job. So, therefore, you know, 31 third of my CPU is gone, just doing this job. 95 00:13:21.630 --> 00:13:30.450 William Cheng: Because, in a way, what you can do is they can sort of think about if I you know take ti divided by PGi right that's the percentage of the CPU that this pretty good job will take up 96 00:13:30.750 --> 00:13:37.170 William Cheng: Okay, if you add up all the ratio like this. Well, you better be less than one, right, if it's bigger than one, it will be impossible for me to schedule the job. 97 00:13:37.710 --> 00:13:46.440 William Cheng: Okay, so, so our goal over here is just try to try to figure out is there. Does it doesn't exist a schedule that will satisfy all the requirements. 98 00:13:47.160 --> 00:13:57.150 William Cheng: Right. Alright, so in this case the deadline is implied right so if you have to execute two seconds of work every six seconds, you have to finish the two seconds of work at the end of that six six second cycle. 99 00:13:58.260 --> 00:14:07.020 William Cheng: Alright, so, so, so again, so we're gonna we're gonna take a look at this. The scheduler, and also the earliest airline forever either early they live versus much simpler every job come with a lie. 100 00:14:07.470 --> 00:14:17.040 William Cheng: Okay, so in this case you want to, you know, the schedule and policy is very simple. You look at all the job at the wrong. Q You see which one has the Earliest Deadline or that will be the one that you scheduled to run next 101 00:14:18.240 --> 00:14:22.980 William Cheng: Yeah, alright. So, one of the difference between these two. One is that you know the amount of time and scheduling. 102 00:14:23.910 --> 00:14:29.100 William Cheng: So, so that one is a preemptive scheduler and the early deadline for it is a non preemptive scheduler. 103 00:14:29.400 --> 00:14:37.470 William Cheng: Okay, why don't you start running a job and CPU, they will run to a completion. Why do you do that, right, because that one is the one with the closest deadline. You don't really want to delay it 104 00:14:37.950 --> 00:14:43.860 William Cheng: Okay, so therefore once a job run inside the CPU. You don't want to preempt it you continue to go go from there. Yeah. 105 00:14:45.180 --> 00:14:55.440 William Cheng: Okay, so we're gonna make some assumptions over here, right, what am I interrupt interrupt is going to take up CPU time. There's also. So we're going to sort of assume that interrupt doesn't interfere with the schedule. 106 00:14:56.310 --> 00:15:01.950 William Cheng: Okay. The, the other way we can sort of think about is that will go to sort of figure out how much interrupt service routine. 107 00:15:02.250 --> 00:15:08.310 William Cheng: How much time we're going to spend his that interrupt service routine and then we can take away the CPU capacity by doing the interrupt service routine. 108 00:15:08.580 --> 00:15:16.560 William Cheng: Right, so therefore it's the remaining CPU CPU capacity, we need to run all these jobs. Okay. And then we try to sort of figure out whether there's a feasible solution or not. Okay. 109 00:15:17.310 --> 00:15:22.410 William Cheng: All right. The other thing that we need to as soon as that execution time we're going to assume that they are predictable. 110 00:15:22.920 --> 00:15:30.960 William Cheng: So in reality all the execution time are they predictable. Right. You know, so for example if you have a nuclear reactor, you have to take a temperature reading you know every 111 00:15:31.320 --> 00:15:37.500 William Cheng: Every second is going to take you. You know, I don't know 50 millisecond to to to to do that work is it going to take 50 milliseconds. 112 00:15:38.310 --> 00:15:45.300 William Cheng: Well, the answer is we don't know right because because you know in the CPU. There's caching you facts right you have a board. There's out to cashes out three cash. 113 00:15:45.480 --> 00:15:52.140 William Cheng: Inside the CPU. They're also cash. We don't really know the exact hit probability is so therefore we don't know the exact execution time 114 00:15:52.560 --> 00:15:58.170 William Cheng: Guys are typically what we do is that you know that we're gonna do we're gonna do a worst case assumption, right, or we're going to sort of perform something 115 00:15:58.410 --> 00:16:05.820 William Cheng: A little, you know, worse than the average case right so this work and actually perform some analysis. OK. So again, depending on our knowledge of the CPU. 116 00:16:06.240 --> 00:16:11.970 William Cheng: We can either to worst case assumption. The work is so typically, I guess if you want to be safe. You always do the worst case assumption. 117 00:16:12.780 --> 00:16:21.000 William Cheng: Okay. So, this way we can actually try to figure it out under the worst case, can we satisfy all the can we satisfy all the constraints. Okay. Alright. 118 00:16:21.840 --> 00:16:29.550 William Cheng: So let's take a look at the first case over here, this is the rate monotonic scheduler. So we're gonna we're going to execute periodic chores or cyclic tasks. 119 00:16:30.030 --> 00:16:41.130 William Cheng: The periods PCI right the per cycle processing time over here is going to be doing called tip that I mean clearly ti needs to be less than one equals 2pm because if Ti is bigger than a TI then we give up right 120 00:16:41.370 --> 00:16:49.080 William Cheng: Then even, you know, this pretty good job. We cannot, you know, run on the CPU. Okay, so, so, so in that case, what do you do well maybe you can get a faster CPU. 121 00:16:49.950 --> 00:16:52.110 William Cheng: Stuff on so over all over again. Yeah. 122 00:16:52.650 --> 00:17:08.670 William Cheng: So to repeat over here, this is the utilization, or the duty cycle for sure i by the example that we have over here it is equal to choose p is equal to six. Then you use that one third of the CPU or the duty cycle of this particular job is going to be 33.33% 123 00:17:09.600 --> 00:17:17.970 William Cheng: Okay so duty sounds like this right over here, you know, and then it will be idle and then it will up again. And so, so this is 33% right and though I don't want to 67% 124 00:17:18.390 --> 00:17:30.960 William Cheng: Then just running this job is going to eat up 33% of the CPU. Right. Alright, so, so, so one simple check is that, you know, if you have a bunch of job you have to run. You want to see if there's a feasible solution. The first thing that you should do is to add up all the 125 00:17:32.070 --> 00:17:37.110 William Cheng: Audio ization okay so some from I go to zero to n minus one to repeat 126 00:17:37.650 --> 00:17:44.970 William Cheng: Into some of the legislation is bigger than one, then then you give up. Right. There's no way for you to schedule all these job to run inside the CPU. 127 00:17:45.480 --> 00:17:55.200 William Cheng: Okay, so they have to be less than or equal to one. So, so, so what if they're they're bigger than one, right. So they're bigger than one, there are two choices. You can have. Number one is that you get a faster CPU. 128 00:17:55.650 --> 00:18:03.060 William Cheng: Right, if you get a faster CPU, then the execution time over here will decrease the period will stay the same, right. So in this case, the some over here might be less than one. 129 00:18:03.870 --> 00:18:11.340 William Cheng: Or less than equal to one. Okay. And the other the other choice over here is that you can you can talk to a customer. Just say, even though I have to run all these job, you'll give me any jobs and run 130 00:18:11.820 --> 00:18:18.780 William Cheng: Can I grow with you know and minus one job instead. Right. So again, if you remove one of the job over here, the total sum over here might get to be less than equal to one. 131 00:18:19.230 --> 00:18:26.610 William Cheng: So you go through this iteration and eventually you find out, you know, finally, you can read your algorithm to see whether you can satisfy that requirement or not. 132 00:18:27.480 --> 00:18:36.150 William Cheng: Yeah. Alright, so, so, so once you check that, you know, this equation is less than wise I mean clearly they're equal to one. Does that mean that you you're guaranteed to be able to find a solution. 133 00:18:36.570 --> 00:18:44.490 William Cheng: WHAT THE ANSWER IS NO guy, you know, because it has, you know, a lot of backgrounds in scheduling people trying to scheduling every since the IBM days and 1960s. 134 00:18:45.090 --> 00:18:51.810 William Cheng: So the computer science work day back all the way to 1968 which I people try to figure out how to go, Ha ha ha ha ha. 135 00:18:52.410 --> 00:19:00.660 William Cheng: Ha, how to do scheduling. Alright, so, so, so what do we do, is I, you know, first you need to add them up, make sure it's less than equal to one, right, and then you need to pick a scheduling over them. 136 00:19:00.900 --> 00:19:10.620 William Cheng: And then you try to see if you can actually satisfy all the requirements. Right. So again, the general problem of, you know, satisfying all the constraints over here for a real time system. It's a very hard problem. 137 00:19:11.190 --> 00:19:16.410 William Cheng: Okay, so therefore we're going to sort of talk about, you know, the these two to a pretty straightforward solutions. Yeah. 138 00:19:17.190 --> 00:19:23.790 William Cheng: All right. The first one is the raven scheduling. Right, so they are only used to to read the secret chores. Yeah. 139 00:19:24.480 --> 00:19:35.310 William Cheng: So in this case, the solution has turned out to be very, very simple decisions like this every chore I over here. Every single job. I'll be here is handled by a thread with party one over API. 140 00:19:36.780 --> 00:19:48.780 William Cheng: OK. So again, the highest priority over here is going to be the one that's going to PM. The low priority jobs. Okay. So in this case you just you just take the period right if the periods, be the party is low in the period, a small part is large. 141 00:19:49.980 --> 00:19:57.990 William Cheng: Well, or the periods periods small the parties. Hi. Okay, so you simply as party scheduling and use preempted scheduling and then you're done. 142 00:19:59.790 --> 00:20:07.710 William Cheng: Okay. And so in this case I will come up with the schedule so so so in this case, you know, we're going to use that example how to do this guy to to see that through your data. 143 00:20:08.250 --> 00:20:20.160 William Cheng: As it turns out, there's actually a requirement. Right. This only works this this very, very straightforward way only works if the some of the utilization of rehearse is less than or equal to this equation. 144 00:20:21.120 --> 00:20:29.550 William Cheng: Okay, so again, this is the sum of utilization for all the job and is the number of jobs you have if it's less than this equation then then re monotonic scheduling is guaranteed to work. 145 00:20:30.120 --> 00:20:40.530 William Cheng: Okay, so it's no brainer. You just scheduler, and it'll work. Yeah. So what is the equation over here on the right hand side, a list of some of the values over here for n equals two, one. This is just one. Okay, so basically that's 146 00:20:41.070 --> 00:20:53.550 William Cheng: This equation over here and when any closer to you can see that this number drops very very quickly to 0.8 and then you drop a 0.777576 and seven for something like that as and goes to infinity. 147 00:20:54.360 --> 00:21:05.040 William Cheng: Then this this equation over your approach natural log the natural log base of two. Okay, so that number is equal to 0.6931 148 00:21:05.670 --> 00:21:17.310 William Cheng: Okay, so what this is telling you that if you take up all the utilization for all the jobs if you add them together. If it turns out to be less than 0.6931 you can use Raimondo scheduling directly and it's guaranteed to work. 149 00:21:18.720 --> 00:21:27.420 William Cheng: Okay, if it's bigger than this equation. Well, then we don't really know if it's gonna work. So what we're going to do that. We're actually going to simulate report on hundred scheduling to actually figure out whether they can work at work or not. 150 00:21:27.660 --> 00:21:33.540 William Cheng: Once we once we simulate it. And we found that they can work well. That will be the scheduled a that that would be the schedule that you compute 151 00:21:34.830 --> 00:21:40.680 William Cheng: Okay, so we're going to see the example how to actually construct a schedule using the idea of a monotonic scheduling. Okay. 152 00:21:41.280 --> 00:21:49.020 William Cheng: Alright, so again, first check against the equation. If it's greater than, will you be greater than this equation. Well, then you have the simulator. Otherwise, you know, it will work for sure. Yeah. 153 00:21:49.950 --> 00:21:57.780 William Cheng: Alright, so let's take an example. We have three sickly chores you know their job. Number one, two and three are these are simply jobs job number one over here. 154 00:21:58.260 --> 00:22:05.610 William Cheng: These are the units guess it doesn't really matter what these units are, whether they're seconds. They're ours, doesn't really matter. So here, let's assume that there's seconds. 155 00:22:06.030 --> 00:22:16.140 William Cheng: Okay. So Job number one every time when you're running out of CPU, it will take up a 0.1 0.5 seconds, right. So, therefore, T one is equal to 0.5 156 00:22:16.560 --> 00:22:23.310 William Cheng: Okay, what about P one right P one is a period. This one repeat every one and a half seconds right over here as well, and a half seconds. 157 00:22:23.520 --> 00:22:31.620 William Cheng: So P one divided by one is equal to one third. So that's kind of like the job that we talked about before, right. Take two seconds, every six seconds. So do you know one third of the CPU. 158 00:22:32.280 --> 00:22:46.650 William Cheng: Okay. All right. What about the second job T to over here is also equal to 0.5 right now. This is 0.5 over here and P two is equal to four seconds right go to four seconds. So, therefore, to repeat to is going to be equal to 0.5 divided by a. That's one. Oh, right. 159 00:22:47.940 --> 00:22:56.220 William Cheng: Okay, so the second job all by itself is an E dot one eighth of the CPU. Then the third 123 is equal to one second, right, and then p three is equal to one. 160 00:22:56.820 --> 00:23:05.490 William Cheng: So this is equal to 2.5 seconds right so if we divide this one, you get one divided by 2.5 that would be the same as two divided by five, this will be equal to 40% 161 00:23:06.330 --> 00:23:12.000 William Cheng: Okay, so the last job over here, you know, if you only will run job number three over here. You're going to eat up 40% of CPU. 162 00:23:12.300 --> 00:23:22.350 William Cheng: Well, so again, the first thing you do is that you add up all the utilization, right, to see if you need you need to bother with scheduling or not. So, one third plus one eighth right plus 163 00:23:22.830 --> 00:23:25.350 William Cheng: You know, I guess this is to over five, right. What does that 164 00:23:25.740 --> 00:23:31.830 William Cheng: Right, so we're just going to multiply the denominator out right three times is 2424 times five is good 120 165 00:23:32.040 --> 00:23:45.540 William Cheng: The numerator eight times five is 40 right plus three. Time flies 15 right and then two times three times is going to be able to 48 right if you add this is going to be 103 divided by 128. This one is clearly less than one. 166 00:23:46.860 --> 00:24:02.250 William Cheng: Okay, but is it less than that equation, right. So in this case, any go to three right we have three threads over three jobs over here and equals two, three, then this equation has to be 0.77 right. So, so, you know, you can see that this number is bigger than 0.8 167 00:24:03.870 --> 00:24:11.580 William Cheng: Right. Why is it a given a zero point right so what does it require is 0.8 96 over 120 right so this number is bigger than zero point. So, therefore, 168 00:24:11.760 --> 00:24:17.160 William Cheng: We know for sure that this one is bigger than equation. So we don't know what a great amount of time scheduling will work or not. 169 00:24:18.060 --> 00:24:31.890 William Cheng: Okay, so therefore, in this case, we have to simulate it. And then we need to be convinced that every job will be there deadline using Raimondo hundred scheduling. Okay. Alright. So let's, let's do it. So if you're using a monotonic scheduling. This will be the schedule. 170 00:24:33.600 --> 00:24:43.710 William Cheng: Guys is very simple. Right, so go. We're going to schedule these job to run at this time. And then we're going to use preemption will also we're going to set our priority, where the property is going to be one over API. Right. 171 00:24:44.130 --> 00:24:45.870 William Cheng: So in this case, what would be one over API. 172 00:24:46.560 --> 00:24:55.410 William Cheng: OK, so again P one is equal to is equal to 1.5 right P two is equal to four p three equals two 2.5 173 00:24:55.650 --> 00:25:05.400 William Cheng: Okay. So the bigger the period, the lower though the party, the smaller the period at the higher the party. Right. So clearly, this one is the one with the smallest period. So this is the highest party. 174 00:25:05.880 --> 00:25:14.280 William Cheng: Okay, this is the one with the longest period of the longest period. So, therefore, this one has the lowest priority, and then the one in the middle is the one in the middle, right. So these will be the party. 175 00:25:15.000 --> 00:25:22.170 William Cheng: Okay, so yeah, we're doing strict party right if you have a higher priority job that needs to run up any other the current job and you run the higher party job. 176 00:25:22.410 --> 00:25:28.080 William Cheng: Okay. The lower priority job only runs when all the higher higher party job or not at the wrong cute. Okay. 177 00:25:28.950 --> 00:25:40.590 William Cheng: All right, so, so let's start simulating this right. So I'm going to sort of claim that you know job number one over here. They're the highest party that can never be bumped up the CPU. So whenever they decide around the CPU. They can run on CPU. 178 00:25:41.460 --> 00:25:51.390 William Cheng: Okay, so therefore I know this part of the schedule already job number one you know this is going to be the schedule. Okay, so let's look at the picture over here at the bottom of your. This will be the final schedule. 179 00:25:52.470 --> 00:25:57.180 William Cheng: Okay. So Job number one, when they, when they need to run it this time they will execute exactly at that time. 180 00:25:58.230 --> 00:26:01.650 William Cheng: Okay, so we're done with job number one, right. So now the second thing that we need to do is that 181 00:26:02.190 --> 00:26:06.000 William Cheng: Here is the medium priority. And here's the lowest priority, right. So, which one should we look at as 182 00:26:06.210 --> 00:26:15.270 William Cheng: Well, of course we have to look at the meeting party on an x, right, because you know the lowest part. It depends on the weather medium party jobs are right because of doing strict party scheduling. 183 00:26:15.690 --> 00:26:24.870 William Cheng: That ALRIGHT SO IF WE NEED TO RUN, RUN THE MEANING part of the job if we need to schedule them at this time. And we're using preemptive scheduling. When will this job start executing 184 00:26:25.590 --> 00:26:33.420 William Cheng: I mean, clearly the job will not be able to execute a time to go to zero because time you go to zero. What we have the CPU is busy are doing job number one job number has higher priority. 185 00:26:33.900 --> 00:26:43.260 William Cheng: Okay, so therefore this job only gets to run when the CPU is not busy with job number one. So, therefore, you actually run right here right job number three. Oh, we can run right here. 186 00:26:45.360 --> 00:26:53.550 William Cheng: Okay, so you just scheduled job number three to run a time to go to zero, they will actually start running over here, I get a little to pass over. Yeah, so this will actually run right here. 187 00:26:54.060 --> 00:27:02.790 William Cheng: Okay, right, because, you know, at time you go to zero or the CPU is busy servicing job number one. When job wise finish. Now, this one will will was running 188 00:27:03.180 --> 00:27:10.230 William Cheng: Okay, what about this one over here. What is that Ronnie, a time he goes to 2.5 it will start running right at time equal to three job number one is going to 189 00:27:10.500 --> 00:27:17.490 William Cheng: Arrive and then pre em this job. So we're going to save the contacts and then later on when to restore the contacts. Right, we're going to save the contact when I put this 190 00:27:17.700 --> 00:27:27.330 William Cheng: Job back into the queue. And now we're going to execute job number one job number one, nobody can stop it right so it's gonna continue to run over here. When jumping on one finish, we're going to finish out number three right here. 191 00:27:28.830 --> 00:27:34.380 William Cheng: Okay. So, by the way, the first time, will you delay job number three over here by half a second does job number three meet the deadline. 192 00:27:35.070 --> 00:27:42.510 William Cheng: What the answer is yes. Right, be the here's the end of the cycle, right, the requirement over here is that the job has finished by the end of the cycle. So this one actually be the della 193 00:27:43.440 --> 00:27:47.880 William Cheng: Okay, the second on when you run this job. You started out over here you finish right here. Again, this won't be the deadline. 194 00:27:48.630 --> 00:27:53.970 William Cheng: Okay. The third time you try to run this job, you will run right here right or wrong. Right here. Right. And then fourth time we run over here. 195 00:27:54.240 --> 00:28:00.570 William Cheng: So, by the way. Right now, we see that job number one and three. They start running at the same time. So now we can actually stop our simulation. 196 00:28:00.960 --> 00:28:09.660 William Cheng: Right, because we know that as far as Job number one and three is concerned, this pattern is going to repeat over and over and over again because now they start at the same time again. Well, then the pattern is going to repeat 197 00:28:11.010 --> 00:28:23.130 William Cheng: Okay, so therefore I cannot do. I'm convinced right now if you just run job number one and three. The schedule will look like this. Right. And this will be the seven and a half second schedule over here and this schedule will repeat over and over and over again. 198 00:28:24.660 --> 00:28:30.450 William Cheng: Alright, so now we just have to worry about your job number two. Number two, when you schedule that have to go to 01 would it get through on 199 00:28:30.840 --> 00:28:38.520 William Cheng: One, this guy's again it can only run when the CPU become available because it's the lowest party job. Right, so therefore he will run right here. JOHN. I'm just gonna right right right here. 200 00:28:38.880 --> 00:28:46.770 William Cheng: Does it did it be the deadline or the deadlines right here, right. So, therefore, this one Peter, they're like, okay, so when you run job number to over here, right here. Again, it will be there like 201 00:28:47.340 --> 00:28:53.940 William Cheng: This one. Oh, you're gonna run right here, over here, right. So, so now job number two. Does it start at the same time with one and three. 202 00:28:54.540 --> 00:29:03.300 William Cheng: Okay, so in this case we are not done with the simulation. I'm just run out of room on the high among the running room. Oh, my slide right. So how long do I have to simulate 203 00:29:04.140 --> 00:29:11.100 William Cheng: Let's remember the period of job number three is equal to 2.5 seconds right the period of job number one over here is equal to 1.5 seconds. 204 00:29:11.400 --> 00:29:20.490 William Cheng: Okay, so, so one of the common multiplier over here. Well, and we're scheduling the job on the increments or half a second, their common multiplier is going to be equal to 7.5 seconds right 205 00:29:20.790 --> 00:29:26.880 William Cheng: So that's why we simulate at 7.5 seconds. They're going to be done now, because now the pattern is going to repeat 206 00:29:27.300 --> 00:29:39.060 William Cheng: Okay. Job number for you know number to over here the cycles over here is four seconds. Right. So one thing that you can just multiply these two numbers together so you know that if I simulate up to 30 seconds. And now I know the pattern is going to repeat 207 00:29:40.350 --> 00:29:50.790 William Cheng: Okay, so can I actually do a little earlier, or the earlier be between 30 seconds over here is 15 seconds right a 32 by twos 1515 is not going to work because 15 divided by four. 208 00:29:51.180 --> 00:30:02.790 William Cheng: It's not a multiple you're going to end up with a fraction. Okay. So, therefore, in this case, if I want to keep going over here. I need to keep going until I see you know the time equal to 30 and then the entire schedule is gonna repeat 209 00:30:03.990 --> 00:30:12.840 William Cheng: Okay. So, therefore, you know, I guess you have to take my word for it. You could continue to simulate over here you will see that as it turns out, random on how to schedule is going to succeed. 210 00:30:14.040 --> 00:30:19.950 William Cheng: Okay. All right, so, so, so anyway, so choose gonna run theaters around here to the right here and we can keep going. Yeah. 211 00:30:21.330 --> 00:30:31.200 William Cheng: Alright, so therefore, in this case, if these are the only three job, you have to run doesn't rain Montana scheduler is going to succeed. And we schedule them just, you know, just put on there and then we simulate we were convinced that the schedule is going to work. 212 00:30:32.280 --> 00:30:33.930 William Cheng: Right so so very easy right 213 00:30:34.950 --> 00:30:42.510 William Cheng: Okay, so now we're going to make it more difficult to say, oh, well, you're gonna end up you can handle three job. How about for job we're going to add another job. 214 00:30:42.900 --> 00:30:53.040 William Cheng: T forest, you go to watch TV for is equal to 0.5 right p four is equal to the period is 4.5 4.5 over here. So the utilization of job number four is going to be one night. 215 00:30:53.820 --> 00:31:01.950 William Cheng: OK, so now if you sum up all the utilization. What do you get right before we have 103 divided by 120 right if you add one over nine to what do you get 216 00:31:02.580 --> 00:31:13.260 William Cheng: OK. So the numerator denominator. I'm just going to multiply them. I'm going to get 1080 over here, right, the numerator, I could just cross multiply again 927 plus 120 217 00:31:13.770 --> 00:31:23.250 William Cheng: So numerous going to be 1047 and then Domino is going to be 100 okay so this one is even, you know, still small and why. And so there's a possibility that this will work. 218 00:31:24.000 --> 00:31:27.570 William Cheng: Okay. And do I need to bother to check that equation. Well, I don't need to 219 00:31:28.140 --> 00:31:34.770 William Cheng: Check because even for n equal to three doesn't work anymore and equal to for that equation that would get smaller. And now we hear the utilization. I should get bigger. 220 00:31:35.220 --> 00:31:43.350 William Cheng: Okay, so therefore I know that I cannot blind me to re monetize scheduler. Okay. And also, I can see that if I simulate it. I also noticed that it's not going to work right away. 221 00:31:43.710 --> 00:31:51.630 William Cheng: Right because john number for over here when I start running a time to go to zero when we get to writing the CPU, he will get to run right here. So, therefore, he will miss the deadline. 222 00:31:53.940 --> 00:31:59.610 William Cheng: Okay. So, therefore, if you blindly use re model on the scheduler when I have for jobs like this ordinance are going to work. 223 00:32:00.150 --> 00:32:11.790 William Cheng: Okay, so therefore, right now I'm going to switch to a different scheduler, because we know that, you know, the shorter the earliest airline. First, the work it's optimal undershooting condition. Now, we don't really know what it's going to work for an apple should give it a try. 224 00:32:12.810 --> 00:32:19.560 William Cheng: Okay, so we're gonna we're gonna sort of simulate the situation over here using earlier. So line first to see if we can satisfy all right. 225 00:32:21.720 --> 00:32:34.110 William Cheng: All right, so I tend to go to zero, right. So what we're gonna do is like this is a non preemptive scheduler. Right. So once we decide to schedule a job that's running out of CPU and that will be the job with the earliest Li, then that job will run inside of CPU until 226 00:32:35.160 --> 00:32:40.740 William Cheng: until it's done right well in the CPU become available, then that will that will be the time would make the next next scheduling decision. 227 00:32:41.340 --> 00:32:47.340 William Cheng: Okay. Alright, so we're talking about a zero, who is at the wrong time. Go to zero. All these for jobs and run queue. So therefore, in this case, we're 228 00:32:47.910 --> 00:32:57.390 William Cheng: Looking for deadlines job number one the deadlines right here right job number two the deadlines right here. Job number three the deadlines right here. Job number for the lines right here. So which one has the earliest airline 229 00:32:57.690 --> 00:33:05.490 William Cheng: Right. So again, it's a very simple algorithm. Right. One is the winner over here. So I'm going to color this one by changing the color of the arrow to be a red arrow. Yeah. 230 00:33:09.030 --> 00:33:15.180 William Cheng: Okay, so this job over here is going to be the winner. So at time equal to zero, we're going to run job number one. Okay. 231 00:33:16.380 --> 00:33:24.420 William Cheng: Alright, so, so now job number one over here we're going to remove it from our schedule. Right. And also, now we know that kind of go to zero. We need to run this job right now. It will look like this. Okay. 232 00:33:25.050 --> 00:33:32.790 William Cheng: When this job is finished, then that will be our next scheduled the opportunity right we need to we need to look at who is that around queue. And then when these sort of figure out who has Earliest Deadline 233 00:33:33.360 --> 00:33:42.300 William Cheng: So, at this time, who is in the wrong cute right 234 I still had the wrong. Cute, right. So in this case, who has Earliest Deadline why job number three has earliest that line right so get three is going to be the winner over here. 234 00:33:42.660 --> 00:33:50.730 William Cheng: To read over here. And then we're going to end up scheduling job number three over here. Okay, so it's going to be like this over here. Right, so they will look like this. 235 00:33:51.270 --> 00:33:57.630 William Cheng: Okay, at time equals to 1.5 I'm even though if you have other job arrival. We're not allowed to reschedule anything, right, because we're doing 236 00:33:58.140 --> 00:33:59.040 William Cheng: Non preemptive scheduling. 237 00:33:59.520 --> 00:34:09.240 William Cheng: That time he goes to 1.5. Well, as it turns out, job one also arrive at the wrong queue. So therefore, we need to take that into consideration. So now we still have three jobs and rank you one, two and four. 238 00:34:09.450 --> 00:34:18.870 William Cheng: And one has a deadline right here to enforce like that. So again, it's easy to tell who's the early. It was the winner job number one is the winner over here. So we run going to run job number one right here. Yeah. 239 00:34:19.440 --> 00:34:27.120 William Cheng: So again, this. I mean, it looks like the schedule is the same as a remodel scheduler. Okay, the room is kind of scheduled actually doing pretty well. Okay. 240 00:34:27.510 --> 00:34:31.710 William Cheng: You know, other than the fact is going to miss job number four, right. So, so let's continue. 241 00:34:32.370 --> 00:34:40.950 William Cheng: Time you go to over here are. There's no more new arrivals, right, the only job at the wrong key is to him for two is clearly the winner. Right. So, therefore, we're going to schedule job number two right here. 242 00:34:41.070 --> 00:34:45.000 William Cheng: So again, we're going to follow exactly the rim on have scheduler over here at right now. 243 00:34:45.870 --> 00:34:59.490 William Cheng: Time equal to 2.5 over here and this guy job number three is on a. Right, right. So, therefore, we need to add it into the picture over here. Job number four is the winner will be here. So now job number four is the winner. So therefore, we need to run job number four, right here. 244 00:35:01.170 --> 00:35:09.090 William Cheng: Okay, so this will be the first time the re monetize scheduler disagree with a short other earliest airline first scheduler. Okay. Why is that 245 00:35:10.320 --> 00:35:23.190 William Cheng: Right. I mean, hopefully it's because the earliest design. First is a smarter scheduler actually makes a better decision, right. So in this case, Robin is that we can see that if you raise the user a Mon hundred scheduler at the end of this, you know, the 246 00:35:23.760 --> 00:35:27.600 William Cheng: Way at the end of seven points that goes over here. There are actually two idling slots. 247 00:35:28.530 --> 00:35:35.550 William Cheng: Okay, so which means that if you actually You sly, some of the jobs down a little bit gray, you actually can create room so he can run job for right here. 248 00:35:36.060 --> 00:35:43.860 William Cheng: Okay, and that's exactly what the earliest airline first algorithm found right there will be able to delay. Some of the jobs over here to be a half a second by second 249 00:35:44.310 --> 00:35:51.060 William Cheng: Okay, so in that case, they don't really change our deadline, right, because they're their lives to the same, they will meet their deadlines and now we also create room to run job for 250 00:35:52.380 --> 00:35:59.940 William Cheng: Okay. I mean, you know, you can you can see the algorithm is actually not doing that kind of thinking. The other than just happens to work out that way. Right. He by by looking at the earliest. And my first 251 00:36:00.780 --> 00:36:06.750 William Cheng: Okay, so I'll be here again we just look at the earliest. And I said, No, we need to run job number four, so four is running right here. So it would be like this. 252 00:36:07.530 --> 00:36:12.570 William Cheng: That. And again, we don't just continue to simulate right basically just blindly follow the algorithm over here. 253 00:36:12.870 --> 00:36:17.400 William Cheng: Have equal to three over here. Job number one also arrive. So now we have done. Number one, and 254 00:36:17.670 --> 00:36:21.780 William Cheng: You know, one in three at the wrong q one is clearly the winner over here we're going to turn to read 255 00:36:22.020 --> 00:36:34.440 William Cheng: Right here. So when I run job number one right here. So over here, Job number three, we actually with the lane for quite a bit, right, because you don't before they will actually beat them the deadline. Bye bye. Bye now Bye, one second. Okay. So, therefore, if we delayed a little bit 256 00:36:36.390 --> 00:36:47.940 William Cheng: It's going to be just just fine. Okay. So, therefore, at this point, when a rock job number one right here. So it would look like this and Tommy goes to 3.5, the only job at the wrong job he is going to be job number three. So, therefore, we're going to run job number three right here. 257 00:36:48.960 --> 00:36:56.820 William Cheng: Okay, so we're here three over here, you can see that, you know, guess three is the winner over here. So when I run through it here. So three over here. It's going to get delayed by half a second. 258 00:36:57.390 --> 00:37:07.830 William Cheng: Okay, so we're still meet the deadline, right, because deadlines right here. So it's no problem. Okay, and also in the middle of the the time job. Excellent job number three over here. Job number to arrive and I'm going to ignore it. 259 00:37:09.030 --> 00:37:12.990 William Cheng: Okay. Happy does you were doing non practice scheduling, you know, based on there, there's a lot 260 00:37:13.350 --> 00:37:19.500 William Cheng: Yeah, alright. So, so we know we're going to remember that the jobs that run queue. Right. So at time equals to 4.5 when the seafood become available. 261 00:37:19.740 --> 00:37:24.960 William Cheng: Who's at the wrong queue right one has arrived to as a ride for has arrived over here. So you need to look at these three jobs over here. 262 00:37:25.140 --> 00:37:32.130 William Cheng: And clearly job number one is the winner. So therefore, we're gonna make a term read over here and then we'll run job number one right here. So, we will look like this. Right. 263 00:37:32.580 --> 00:37:38.280 William Cheng: Time he goes to five job number four also has arrived over here. So again, we need to take that into consideration. Sorry. 264 00:37:38.700 --> 00:37:48.960 William Cheng: Gentlemen for Rob already so job number three also arrived. We need to take that job into consideration and now we have three jobs job number three is clearly the winner will be here. So we run job number three right here. 265 00:37:49.860 --> 00:37:59.940 William Cheng: Next time you go to six over here. Job number one also. Right, right. So, therefore, we need to take that into account and that one has the Earliest Deadline over here. So we're going to end up running job number one right here. 266 00:38:00.180 --> 00:38:05.670 William Cheng: Okay, can you go to 6.5 nobody else has arrived. We're going to look at number two and four over here to as the winner. 267 00:38:05.910 --> 00:38:16.890 William Cheng: So over here to the winner. So therefore, we're going to run this job right here so you can see that number to over here for the right amount of how to schedule it runs at this time and now it's delayed by, you know, by, by what 268 00:38:17.220 --> 00:38:21.240 William Cheng: By by one two by two and a half seconds is still meet the deadline. 269 00:38:22.380 --> 00:38:27.330 William Cheng: Okay, I'm included so I show you that the you know the early Deadline First algorithm seems to be a little smarter. 270 00:38:27.750 --> 00:38:37.020 William Cheng: Okay, so therefore Jada materials run right here time equal to 70 only job at the reviews job number four. So as it turns out, not only can you run one job number four, you can actually run twice. 271 00:38:37.770 --> 00:38:41.490 William Cheng: Guys over here we're going to run job. Now before I here and then you'll be the scheduled 272 00:38:41.790 --> 00:38:52.530 William Cheng: OK. So again, we're at this point right now. Right. Can we stop. We can't stop right because right now we need to continue to simulate for a job number 123 we need to simulate to 30 seconds. What about job number four. 273 00:38:52.830 --> 00:39:09.090 William Cheng: Job number four over here it's you know it's equal to 4.5 seconds. So in this case is 4.5 seconds over here is, you know, the 30 is not a. It's not a multiple 4.5 seconds, or is it. So this way, if you multiply by eight. It's going to be equals to know 274 00:39:10.350 --> 00:39:14.130 William Cheng: Yeah, so there's not a multiple over. So maybe you have to simulate all the way to 90 seconds. 275 00:39:15.060 --> 00:39:23.970 William Cheng: Well guys, okay. If we keep doing this. And then we need to convince ourselves that you know the Earliest Deadline First will actually schedule all the job again, there's no guarantee that earlier is that I'm first will always work. 276 00:39:24.630 --> 00:39:32.670 William Cheng: Great as possible. You know, the way that you are the length of the job will actually make it not be able to schedule it 277 00:39:33.690 --> 00:39:38.880 William Cheng: Okay, so we have no choice but to keep stimulating, so can I. What can I do this by hand, we have to actually write a program to do this. 278 00:39:39.150 --> 00:39:46.740 William Cheng: SO THIS WAY, WHEN WE SEEN THE UP TONIGHT 990. Second, we can convince ourselves that the earliest know I'm first actually if you do that every job satisfied Adela 279 00:39:47.760 --> 00:39:48.060 William Cheng: Yeah. 280 00:39:49.620 --> 00:39:52.170 William Cheng: All right, so, so if we keep doing this. 281 00:39:53.790 --> 00:40:01.260 William Cheng: Similarly, a little more over here. So I'm not going to do that right you should know how to do that. So EDF or success, you know, eventually, you know, for this example. Yeah. 282 00:40:02.430 --> 00:40:07.620 William Cheng: Alright, so, so, what sort of one legitimate question over here and say, Why do we actually start all the job over here at the same time. 283 00:40:08.880 --> 00:40:12.330 William Cheng: They maybe if I actually shift. One of the job by a little bit 284 00:40:12.660 --> 00:40:21.540 William Cheng: You know, maybe the red monotonic schedule will actually work. Right. So you've actually shift job number four over here. Maybe if I start right here and then again repeat using the same pattern over here, maybe. Why should it work. 285 00:40:22.530 --> 00:40:30.510 William Cheng: Okay, so this is why you know scheduling is so complicated, because in order for you to be convinced that certain thing doesn't work, you need to try all you need to try harder. 286 00:40:30.990 --> 00:40:37.800 William Cheng: Okay, you need to try all different possibility by shifting all these jobs left and right okay to try all possible combination of all the jobs. 287 00:40:38.130 --> 00:40:41.310 William Cheng: Okay. And eventually, you can convince yourself that. Oh, the mother is actually not gonna work. 288 00:40:41.730 --> 00:40:51.120 William Cheng: There. So this is known as the phase shift problem or the face problem, you can actually shift one of these jobs so they don't have to be, you know, all these job right now. They all start at the same time. That's called in phase. 289 00:40:51.540 --> 00:41:00.330 William Cheng: There's no requirement, they have to start in phase. So, therefore, you can actually start them with out of phase. You can be 90 degrees out of phase 130 35 degrees out of phase, any kind of phase that you want. 290 00:41:00.990 --> 00:41:04.260 William Cheng: Okay, so in reality, you know, this is why scheduling is such a hard problem. 291 00:41:04.770 --> 00:41:14.220 William Cheng: Okay. And then what about multi CPU. What do you have multi CPU, you know, for every job, you need to shift all the, you know, you need to try all the different phases and you also need to try to run on different CPUs. 292 00:41:14.640 --> 00:41:19.260 William Cheng: Okay, so that's why multi CPU K scheduling problem is going to be NPR right so anyways. 293 00:41:19.860 --> 00:41:27.150 William Cheng: We're not going to sort of talk about this at the textbooks, try to talk a little bit about us. Right. So if you're interested, you can look at the you can read textbook. Okay, so you're not responsible for it. 294 00:41:28.560 --> 00:41:32.700 William Cheng: I mean other than need to know the facts that you know that we didn't really take that into consideration. Yeah. 295 00:41:33.390 --> 00:41:43.650 William Cheng: Alright so so that so we finished our 10 you know schedulers so the the sort of pick a look at the remaining issues and we're going to look at Linux and look at windows to see what they do. Okay. 296 00:41:44.610 --> 00:41:50.430 William Cheng: All right. One of the problems over here is going to be the party and version problem that that we saw before. 297 00:41:51.120 --> 00:41:59.850 William Cheng: Before the kind of we have is that you know their user thread. There's Colonel threat right the user has your own party. The Colonel says the own priority. So when the user company started Colonel 298 00:42:00.090 --> 00:42:04.410 William Cheng: A high level high priority user thread might be scheduled on the low priority Colonel threat. 299 00:42:04.890 --> 00:42:14.280 William Cheng: OK, so now you know how this can happen right because inside the Colonel, there's this dynamic priority right so the Colonel's we actually will go to go to different party. So it is possible that your high level. 300 00:42:14.820 --> 00:42:19.170 William Cheng: User when it comes out of Colonel, they can get picked up by by by low party Colonel fair 301 00:42:20.190 --> 00:42:25.320 William Cheng: Okay, so, so, so, so, so, so that will be one kind of party version. Right. And as I mentioned before, 302 00:42:25.710 --> 00:42:32.670 William Cheng: Party in version that kind of a tricky problem once you fix one kind of party version we're going to end up with a different kind of party version problem. Yeah. 303 00:42:33.450 --> 00:42:39.120 William Cheng: Alright, so now we're going to sort of see a case where there's only Colonel thread only user threat, we can still end up with a party version problem. 304 00:42:39.210 --> 00:42:45.660 William Cheng: So in this case we don't require two different kinds of threats, right. So, so let's take a look at this case where let's assume that they're all you know they'll 305 00:42:46.200 --> 00:42:49.500 William Cheng: They'll Colonel threats. Right. And Colonel has these different kind of party. 306 00:42:50.040 --> 00:42:58.890 William Cheng: We're going to end up with other you know the other three of the three threats. Right. A has highest priority see has last party. He has the medium party that 307 00:42:59.310 --> 00:43:10.140 William Cheng: But in this case, you know, at the wrong time over here, we'll only have three a, b, and c guys are beside rocky over here. So be going into the meeting party Q and see is the one with the lowest party so therefore sequels until those barbecue. 308 00:43:10.620 --> 00:43:23.910 William Cheng: Okay. Hey, somehow it's blocked at me text you and this time, the music is actually owned by threat seat, guys. It's kind of a convoluted complicated example here. So as over here sitting at the meat AX few over here and see actually owns me attacks. 309 00:43:25.350 --> 00:43:28.080 William Cheng: Okay. So in this case, you know, you'll see, you see, you know, 310 00:43:28.620 --> 00:43:37.830 William Cheng: I guess I'll be here she's waiting to be excellent over here. But see, will not be able to run inside of CPU. Why is that why is because therapy over here has higher priority is blocking. So I see 311 00:43:38.460 --> 00:43:47.520 William Cheng: Okay, so therefore therapy over here is also indirectly blocking thread A ok so again in the operating system literature. They call this a party version problem. 312 00:43:48.750 --> 00:43:52.590 William Cheng: Okay, because thread A over here is blocked because thread be is using the CPU. 313 00:43:53.880 --> 00:43:59.880 William Cheng: Okay, so what was it, what is for a while right there. So I want see to run first right because you know see over here. 314 00:44:00.030 --> 00:44:08.970 William Cheng: You know C's blocking me. So in order for me to run. I'm more important than thread be. So, therefore, you know, I don't really care how you do it. But so I see need to be run we need run first. So this way. 315 00:44:09.390 --> 00:44:11.220 William Cheng: You know, I can go inside around cute. 316 00:44:12.150 --> 00:44:18.990 William Cheng: Okay. Some people will argue that what this is really not a party version problem because you are blocked by a by a thread with lower priority. That's your own problem. 317 00:44:19.230 --> 00:44:26.880 William Cheng: Okay, but again in the literature of operating system research. This is no as a priority version problem, right. So that's going to be the standard that we're going to go by now. 318 00:44:27.510 --> 00:44:38.970 William Cheng: So in this case, you know, you know, what is the solution over here. Okay, so, so a over here is blocked by see and sees block. Bye bye, baby. And he has a lower priority than si, si P has a little party than a 319 00:44:39.480 --> 00:44:42.900 William Cheng: We're going to end up with a party and version problem. So, this particular solution. Well, 320 00:44:43.590 --> 00:44:50.730 William Cheng: As it turns out, there's a human analogy to it, right. So, for example, your summer intern, you know, then, then I can see working for a company 321 00:44:51.120 --> 00:44:54.660 William Cheng: Your CEO asked you to go to Starbucks and buy coffee for the CEO. 322 00:44:55.020 --> 00:45:02.550 William Cheng: Guys will happen is that when you get to start out, you find out that there's a bunch of middle management people they're standing in front of you. They all cut in line, right, because they're higher priority that you are 323 00:45:03.000 --> 00:45:06.990 William Cheng: So they know the people who was making coffee they let them go first and then you're stuck at the end of the line. 324 00:45:07.560 --> 00:45:10.620 William Cheng: Okay, and then you get a phone call from the CEO to say, hey, where's my coffee. 325 00:45:11.070 --> 00:45:16.020 William Cheng: Okay, well you said a while there's all bunch know all these bunch of middle manager. And over here, there in front of me. That's why I cannot get your coffee. 326 00:45:16.650 --> 00:45:23.700 William Cheng: Okay, so what does the CEO going to do while the CEO is going to go to tell you to take your cell phone and give it to the people who are making the coffee to say, hey, 327 00:45:24.090 --> 00:45:35.100 William Cheng: This you know this person here, this person represent me okay so treat this person like me. So, therefore, you get in front of the queue. Over here you get your coffee and then in this case, you're going to bring bad coffee to the CEO. 328 00:45:35.940 --> 00:45:45.990 William Cheng: Okay, so in operating system. We can do exactly the same thing there. So this is no as party inheritance. Okay, so, so, so if you know. So in this case, what happened is I 329 00:45:46.500 --> 00:46:03.330 William Cheng: You know, I guess the base of executive solution that I just mentioned, right, if you know you know the stray over here is is blocked by three. I see three I see if I see is a lower priority. We're going to temporarily raise the party level of threat see to the same level or threading. 330 00:46:04.380 --> 00:46:10.050 William Cheng: Okay, so this way when threats, you get to get to the wrong key Elijah has a higher priority. So therefore it will run before everybody else. 331 00:46:11.010 --> 00:46:17.550 William Cheng: Okay, so this is known as party inheritance. Okay. When you get blocked by a low level threat than the low level threat and hair, your 332 00:46:18.180 --> 00:46:23.700 William Cheng: Hair your priority that as I mentioned before, if you saw this care. That's pretty good. Okay. The problem using the solution. 333 00:46:23.850 --> 00:46:30.720 William Cheng: Somebody can will, it will be able to come up with a with another case where there are four different party threads over here. And then in the in the decades. This solution is not going to work. 334 00:46:30.930 --> 00:46:37.620 William Cheng: And if you come up with a solution for that they will come up with another serum scenario where there are five different threads. And then in that case your solution is not going to work. 335 00:46:38.340 --> 00:46:45.810 William Cheng: Again, okay so priority and version is very, very tricky. Even today, if you read operating system conferences. People are still trying to solve poverty and version problem. 336 00:46:46.260 --> 00:46:53.460 William Cheng: Okay, so, so. Okay, so this is the introductory class. We're not going to get too much into it. Alright. So again, we're only going to talk about this, this one particular case. Yeah. 337 00:46:54.300 --> 00:47:03.510 William Cheng: All right. The other problem that we talked about sort of briefly mentioned before is that, you know, when you have multiple CPU, and I mentioned before, every time we have multiple CPUs, things get more complicated. 338 00:47:04.170 --> 00:47:07.950 William Cheng: Okay, so when you have multiple CPU HOW MANY REVIEWS, are you supposed to have 339 00:47:09.240 --> 00:47:15.540 William Cheng: Okay, do you, you have only one wrong queue or do you have, you know, multiple run cues. As it turns out, that was actually a design sort of a 340 00:47:16.860 --> 00:47:27.000 William Cheng: design decision problem. Okay. So, here there are two choices to choose from. Right. So what is this right you have four CPU over here you have one run queue and the other configuration is that you have four CPU have foreign to you. 341 00:47:27.630 --> 00:47:33.870 William Cheng: Okay, so, so what's the problem with the first approach over year. So, by the way, why would people come up with this particular approach. 342 00:47:34.650 --> 00:47:38.520 William Cheng: Okay, this is because people study queueing theory right if you according to queueing theory. 343 00:47:38.700 --> 00:47:46.680 William Cheng: If he ever a situation like this, in order for you to minimize your waiting time. The best thing you do that you should do is you use the wrong. So you use the single. Thank you. 344 00:47:47.070 --> 00:47:54.240 William Cheng: Okay, you see this kind of configuration at banks that when you go to the bank. There are many, many bank teller. How many shoes there. Have they don't have one cute. 345 00:47:55.050 --> 00:48:01.110 William Cheng: Okay, because you know people have studied this to death. This is the best way to minimize your waiting time right 346 00:48:01.860 --> 00:48:09.030 William Cheng: Right. As it turns out, this does work in the human society and works with a lot of different cases, but it doesn't really work very, very well with operating system. 347 00:48:09.360 --> 00:48:17.130 William Cheng: The reason being is because there's something about cash affinity. Okay, so let's say that you're a job over here. Your job over here and you get writing the first CPU. 348 00:48:17.430 --> 00:48:22.770 William Cheng: Why don't you run inside the first CPU. From this point on, you prefer to run in the first CPU. Well, why is that 349 00:48:23.340 --> 00:48:32.250 William Cheng: Okay, because when you run inside of CPU over here at the CPU has you know alto caches L three caches, you know, Ellen cash and all kinds of caches over here that goes with the CPU. 350 00:48:32.730 --> 00:48:37.560 William Cheng: And so typically in a multiple CPU case every CPU over here. They have their own cash. 351 00:48:38.190 --> 00:48:42.330 William Cheng: Okay, and then they sit on the bus over here and then across the the bus over here. That's the main memory. 352 00:48:42.750 --> 00:48:51.570 William Cheng: And so in this guy's once you start running is that one CPU you stop you stayed inside the cash over here. From this point on, if you run into the same CPU, you're gonna run a little faster. 353 00:48:52.740 --> 00:48:58.080 William Cheng: Okay, so again we haven't really talked about multi CPU cache coherence. See, you know, a protocol whatever again. 354 00:48:58.500 --> 00:49:03.630 William Cheng: That the, you know, if you take a double the class, they will address that in architecture class we we don't want to deal with that. 355 00:49:04.200 --> 00:49:11.340 William Cheng: Because that will take up too much time. So, so again, this guys you know what you need to understand is that once you run into one CPU, you will prefer to rise out of CPU. 356 00:49:11.610 --> 00:49:19.110 William Cheng: Okay, so next time when you come back over here if there's only one wrong to you if once you become available. You end up running inside different CPU. So you end up running slower. 357 00:49:20.940 --> 00:49:27.720 William Cheng: Okay, so even though you can minimize the waiting time on this case, you know, when you started running out of CPU and I was slower. So this is really not the only way to go. 358 00:49:27.900 --> 00:49:32.910 William Cheng: Right, if you'd go with this way over here. So I've been inside. Inside your CPA your process is that your threat control, blah. 359 00:49:33.120 --> 00:49:44.340 William Cheng: You will need to remember, you know, which CPU do I prefer. So if I'm this job over here the run and CPU number one over here instead of our control blog that will say that I will always run into number 00123 over here then. 360 00:49:44.640 --> 00:49:55.170 William Cheng: The other job will be here. They will also pick their favorite CPU, because once you run inside of them. That would be your favorite CPU. Okay, so this way you know there will be running much more efficiently. 361 00:49:56.220 --> 00:49:58.710 William Cheng: Okay, so what is the downside of the bottom approach over here. 362 00:49:59.460 --> 00:50:08.370 William Cheng: That. So let's about in the beginning, you're saying that you assign these three two CPUs over here evenly. Right. So we hear the queue length in all these four keys over here. They're about the same size. 363 00:50:08.730 --> 00:50:17.190 William Cheng: Okay, it is possible, you're unlucky that all these three kilos over here, they still maintained the same size, but all the threads that are running the four CPU. They're all died. 364 00:50:18.090 --> 00:50:26.760 William Cheng: Okay, so in this case the force kuopio will be completely empty. What the first three CPU. There are, there's going to be very, very busy. Okay. So in this case, if this happened right 365 00:50:27.870 --> 00:50:29.310 William Cheng: What can this happen. 366 00:50:30.390 --> 00:50:41.430 William Cheng: Well maybe it's not very, very likely. But again, the probability is there that this can happen. So when this happened, your CPU utilization will be what the CPU position will be will go down to 75% because the last CPU over here has nothing to do 367 00:50:42.510 --> 00:50:51.300 William Cheng: Okay, so therefore, why has to be the solution. Well, the solution over here is that we have to move jobs from the first three Q over here into the forest Q over here and we need to do this once in a while. 368 00:50:51.810 --> 00:51:01.680 William Cheng: Okay, so, so this is no as load balancing. Okay, so what happened is that if you use the second configuration over here, you need to sort of set a timer once in a while, you need to look at all these for cues, you know, sort of, 369 00:51:02.520 --> 00:51:05.820 William Cheng: At the same time, and to see if you're required to do load balancing. 370 00:51:06.210 --> 00:51:14.070 William Cheng: If it turns out that all these three kilos over here. They're about the same size. And the last one over here is completely empty. So what you would do that, it will go to every one of these for q over here. 371 00:51:14.250 --> 00:51:23.730 William Cheng: Take one quarter of the job from every one of these Q over here reassign them to to number four. Okay, so now all the humans are going to be exactly the same. And now you can continue from that, from that point on. 372 00:51:24.960 --> 00:51:34.440 William Cheng: Okay. So this guy's you got to pay in terms of once in a while, you have to do load balancing. Right. So you have to just stop everybody from doing whatever they were doing before shuffle these jobs around and then you'll let it go again. 373 00:51:35.640 --> 00:51:44.160 William Cheng: There's again there's there's really no free lunch there also extra stuff you have to do then, as it turns out, you know. So I think, you know, 374 00:51:45.630 --> 00:51:51.030 William Cheng: Microsoft, actually, you know, take the second approach over here, they adjusted the cash affinity issue over here. 375 00:51:51.720 --> 00:51:55.200 William Cheng: And typically Solaris albinism, or they tend to be more complicated. 376 00:51:55.890 --> 00:52:01.410 William Cheng: They why they actually decided to go somewhere in between these two approaches they use the idea of processor set 377 00:52:01.620 --> 00:52:06.510 William Cheng: Okay, so they will group, the process together so that they only have one rung. Q You know profile for 378 00:52:06.750 --> 00:52:15.960 William Cheng: For every process or should I said okay so you have four four CPU is maybe a group two of them together and then this case, you're going to end up with two wrong cues over here. So what do you use to refuse 379 00:52:16.350 --> 00:52:23.670 William Cheng: Why because he'd be willing to run cues, the probability that one of the keys over here will be completely empty is going to be much smaller than the previous case. 380 00:52:23.850 --> 00:52:30.420 William Cheng: By the period when they are foreign keys over here, the probability one of them will be completely empty. It's going to be much more likely than in this particular case. 381 00:52:30.840 --> 00:52:38.970 William Cheng: Okay. So in this case, we're actually going to design the CPU is that we're going to have these two CPU sitting on the same floor, they will be sharing the same hardware you know all this. 382 00:52:39.630 --> 00:52:49.230 William Cheng: I guess the outcast will use over here. There'll be sharing, sharing this the same to cash. So this way you know when you try to you know what went well. Well, when when a fairly why 383 00:52:49.590 --> 00:53:01.740 William Cheng: Wouldn't want a thread running. So one of the CPU. It doesn't really matter which one you choose. Okay, so, so, you know, some ecosystem there. The one that came up was hilarious. Right, so they designed the CPU war over here to actually address all these issues. Okay. 384 00:53:03.240 --> 00:53:11.280 William Cheng: All right, so, so again, typically Solaris is sort of higher performance audiences and they also have fancier hardware that can do all these kind of stuff. Yeah. 385 00:53:11.760 --> 00:53:22.350 William Cheng: All right. The last part of chapter five will be here with us or briefly take a look at what they do in Linux and where they doing windows. So again, windows, they can change all the time. We don't more about Linux because you know everybody have access to the source code. 386 00:53:23.070 --> 00:53:33.240 William Cheng: We need a Linux is positive compliant. Okay so positive is a UNIX system. Right. So, a long time ago, they sort of decide to have one standard for the UNIX system. So pretty much today. Any of the UNIX 387 00:53:33.810 --> 00:53:36.930 William Cheng: UNIX system that you can get your hands on. They are all positive compliant. Okay. 388 00:53:37.410 --> 00:53:40.080 William Cheng: My understanding is also even Windows is positive compliant. 389 00:53:40.350 --> 00:53:47.850 William Cheng: Guys, so therefore that's why we learned P threads, because once you learn piece where you can program it in any of the system that you would touch right Mac OS X is positive. 390 00:53:48.150 --> 00:53:55.290 William Cheng: Comply and Linux is plus compliant windows compliant and if you run any scenarios or any kind of a, you know, UNIX system. They're all positive compliant. 391 00:53:55.590 --> 00:54:03.540 William Cheng: Okay, so in the politics is there, they require the scheduler to be of a certain form. Okay, so they they require that you have have three levels of party. 392 00:54:03.750 --> 00:54:11.670 William Cheng: One is the highest priority, and the other one is the medium priority over here. And then there's the one is last party within every party, you can actually implement other party that that'll be fine. 393 00:54:12.030 --> 00:54:21.030 William Cheng: Okay, but the first two over here. They're actually well defined. Okay, the first one over here is the fivefold queuing scheduling the they have to use spiteful you know 394 00:54:22.590 --> 00:54:27.270 William Cheng: scheduling policy. This one is to use oil for scheduling real time jobs. 395 00:54:27.780 --> 00:54:36.660 William Cheng: Okay. So typically, you can sort of see the high speed real time jobs over here you know they have a stringent requirement over here. There'll be scheduled the highest party. Oh, yeah. And this one, they have infinite quantum because it's 396 00:54:37.080 --> 00:54:43.620 William Cheng: It's not wrong, Robert. Okay, so there's no wrong Robin at all. So we hear why she running out of CPU. You don't give it up on to you completely done 397 00:54:44.640 --> 00:54:47.130 William Cheng: Okay, so these are again for a full time job. 398 00:54:47.520 --> 00:54:55.020 William Cheng: So typically these are for, you know, audio and video, right. So, you know, these kind of self has a very, very strict requirement. When do you have to display a frame. 399 00:54:55.230 --> 00:54:59.340 William Cheng: When you have to, you know, play a sound and these kind of stuff. So again, they use higher priority to proper job. 400 00:55:00.150 --> 00:55:09.330 William Cheng: Yeah, the second the medium party over here. It's a round robin scheduler right this is also for scheduling real time job. So maybe the salt real time job over here that can be scheduled right here. 401 00:55:09.930 --> 00:55:19.440 William Cheng: Okay, so again you can sort of decide, you know, know you if you want to schedule video here or you can willing for the video to degrade quality or that you can actually use the ramen schedule it. Okay, so in this case. 402 00:55:20.040 --> 00:55:24.300 William Cheng: In the positive standard they specify that you can use adjustable time content. 403 00:55:24.660 --> 00:55:33.510 William Cheng: Right. So again, the time slides, you can actually change it over time. It doesn't the standard doesn't tell you how to change them. So every operating system vendor, they can do they can do their own thing. 404 00:55:34.290 --> 00:55:40.260 William Cheng: Yeah, the last one over here is they call it the normal scheduler right so this one is the one that Linux choose to use 405 00:55:40.530 --> 00:55:47.760 William Cheng: The scheduler or the completely fair scheduling policy right over here. And the third one over here because the first two Linux and I choose 406 00:55:48.150 --> 00:55:55.260 William Cheng: Okay. The first two are specified by the project standard. Yeah, so the bottom line over here, you can now basically can choose anything that you want. Yeah. 407 00:55:56.070 --> 00:56:02.910 William Cheng: All right, the textbook actually talks quite a bit about the older Linux scheduler. There's something called the O scheduler, which is really oh 408 00:56:03.180 --> 00:56:09.180 William Cheng: It's very, very simple. It doesn't scale very well with a lot of jobs and then come something called the order one scheduler. 409 00:56:09.570 --> 00:56:15.900 William Cheng: Okay so so order one schedule over here is, you know, sort of a previous generation of scheduler. And I mentioned before. 410 00:56:16.200 --> 00:56:24.810 William Cheng: You know, the, the, you know, the strike scheduler the performances order login right performance over years order login over here and it's a number of job at the wrong cute. 411 00:56:25.260 --> 00:56:31.980 William Cheng: OKAY, SO OTTER login sounds worse than order one. Right. So what did the learnings that you pick order login vs order one. 412 00:56:33.150 --> 00:56:40.710 William Cheng: Okay, so you can sort of imagine in order. Why, what kind of a schedule is going to be able to wine. Right. They must use some kind of a hash table to build a bunch of hash bucket. Right. So in this case, 413 00:56:40.890 --> 00:56:52.920 William Cheng: Even when they're order one. In the end, the performance is going to be proportional to the length of the conflict or the collision resolution check. Okay, so if the collision resolution chain is long line in that case, you know, order login may even be better. 414 00:56:54.210 --> 00:56:59.760 William Cheng: Okay so Linux to them a long time right then 12 years to eventually sort of figured out that you know going with strikes me is 415 00:57:00.870 --> 00:57:08.580 William Cheng: Sort of the best way to go. So they basically study to death, the trade off between the two system. Eventually, they'd be inside the otter login actually beats or two, one 416 00:57:09.300 --> 00:57:18.240 William Cheng: Okay. So guys, you shouldn't be surprised when Otter login catch up, or the one because otherwise. So it depends on the length of the the the collision resolution chain. Yeah. 417 00:57:20.160 --> 00:57:26.400 William Cheng: Alright, so the textbook talks quite a bit about the scheduler. Again, you're now responsible for it for the exam. 418 00:57:26.970 --> 00:57:37.590 William Cheng: The scheduling Windows. Windows typically is very, very complicated, right. So we're going to sort of briefly talked about it again windows can changes that anytime. So therefore, we don't really know if there's actually correspond to the current windows design. 419 00:57:38.370 --> 00:57:40.770 William Cheng: So they have 32 different priority classes. 420 00:57:41.670 --> 00:57:47.850 William Cheng: Okay, so again, they go crazy with the party causes over here. The first 16 over here are reserved for real time jobs. 421 00:57:48.000 --> 00:58:01.530 William Cheng: Near the bottom one over here for non real time jobs. Yeah. So the real time demo here they are running using strict party right you are not allowed to run a job at this level 34 unless all the other wrong level over here with higher party, they're completely empty. 422 00:58:02.610 --> 00:58:14.160 William Cheng: OK. So the top 16 over here are for scheduling real time job and the other ones over here. Again, they use the multi level feedback queue, but they have five different categories. One of them is the higher category. So you go up and down using these 423 00:58:14.520 --> 00:58:26.370 William Cheng: Guys over here 123455 different party levels there. And then there's the above normal go use the sort of overlapping, you know, five different levels over here. And then there's normal this below normal there's low 424 00:58:26.910 --> 00:58:38.490 William Cheng: Okay, so look at the windows programmers manual says used to use low if you can, as it turns out, everybody wants to use high. Okay, so. So in this case, in the end, only tho those sort of Windows program over here that we use the lower level. 425 00:58:39.750 --> 00:58:40.350 William Cheng: below poverty. 426 00:58:41.160 --> 00:58:52.290 William Cheng: Level. Okay. And then what the windows you know schedule does is that they look at all these party all at the same time and then do a straight party yes scheduling right there was run all the real time job first 427 00:58:52.470 --> 00:59:01.590 William Cheng: And then they will run all the high party job for us over here. Again, when you go to the you know the the, are these the these non real time job over here we are we're using 428 00:59:04.110 --> 00:59:05.730 William Cheng: We're using the 429 00:59:06.840 --> 00:59:18.240 William Cheng: The, the sort of the, I guess every level over here is as party right and they're all we're also going to downgrade them or if they, you know, if they don't give give up the CPU. 430 00:59:18.990 --> 00:59:25.200 William Cheng: That's what we're using that scheduling policy, but in that case, again, we need to look at. Take a look at all these five different categories simultaneously. 431 00:59:25.860 --> 00:59:35.070 William Cheng: OK. So again, Windows is pretty complicated. They do this one level, at a time when only the higher level is done, then we're going to serve the next level using the round robin scheduler for that particular level. 432 00:59:36.420 --> 00:59:45.180 William Cheng: OK. So, again, that I can remember that term is called multi level feedback you. So again, all these multi level feedback queue, but they scheduled them across all these different five categories. 433 00:59:45.780 --> 00:59:55.350 William Cheng: Yeah. Alright. So again, you know, the multi level feedback you also the textbook mentioned that they are not exactly the same as we mentioned before, again, because there are so many different variation 434 00:59:55.830 --> 01:00:05.910 William Cheng: So they will actually they will use their own algorithm. And we also don't know whether they're changing all the time now. Alright, so again this is just sort of a high level of description, what the window scheduling with them. Okay. 435 01:00:07.560 --> 01:00:24.330 William Cheng: Alright, so we are done with chapter five. So I think the only there's only one topic left that chapter three, with a dynamic Lincoln and OD, so we're going to take a break now for this. The last part of the lecture will be here. We're going to talk about, you know, dynamically loading. Okay.