1 00:00:06,700 --> 00:00:10,500 The next subsection that we're going to talk about having to do with processes is 2 00:00:10,500 --> 00:00:12,000 scheduling. 3 00:00:14,500 --> 00:00:18,900 So we'll start with some of the high-level view of the different classes that 4 00:00:18,900 --> 00:00:22,200 we have available when we are doing scheduling 5 00:00:22,900 --> 00:00:26,800 in particular, the threads get divided into five different classes, 6 00:00:27,500 --> 00:00:31,900 so you can see on the left of this with a we've organized, the priorities. So 7 00:00:31,900 --> 00:00:35,800 every thread has a particular priority assigned to it, that 8 00:00:35,800 --> 00:00:39,900 priority may change over time, but the range that it's in will 9 00:00:39,900 --> 00:00:43,900 tell you what class it's in. So the priorities range from 0 to 2. 10 00:00:44,000 --> 00:00:48,800 It in 55 and Sub-Zero 247. As you can see, is the first 11 00:00:48,800 --> 00:00:52,600 grouping of the priorities and we call this the, I 12 00:00:52,600 --> 00:00:56,900 thread class. This is things that are running in the bottom half of the kernel. 13 00:00:56,900 --> 00:01:00,900 So, anything that's like an interrupt when it's running in 14 00:01:00,900 --> 00:01:04,900 that interrupt. It's going to have a priority that somewhere in this do 247 15 00:01:04,900 --> 00:01:05,700 priority range. 16 00:01:06,700 --> 00:01:10,400 Next up. We have 48 to 17 00:01:10,400 --> 00:01:14,800 79. These are the real time priorities and these are priorities that can be 18 00:01:14,800 --> 00:01:18,400 assigned by anybody that's running in the real-time 19 00:01:18,400 --> 00:01:22,300 scheduling class, which will talk a little bit about then we get 80 20 00:01:22,300 --> 00:01:26,600 219, which is Colonel priorities. And this is the top half of the kernel 21 00:01:26,600 --> 00:01:30,700 and those things are the ones that are doing the system calls. 22 00:01:30,700 --> 00:01:34,700 The priorities range from 0 being the 23 00:01:34,700 --> 00:01:35,800 highest priority to 24 00:01:36,700 --> 00:01:40,500 Five being the lowest priority. So, I threads are going to get 25 00:01:40,500 --> 00:01:44,700 precedence over real time. But real time are going to get frustums over the colonel. 26 00:01:45,200 --> 00:01:49,600 So if some application doing real-time sets one of its 27 00:01:49,600 --> 00:01:53,800 threads into one of the real time priorities, and then that thread goes into an infinite 28 00:01:53,800 --> 00:01:57,900 Loop, the entire system will just lock up. The only thing that'll be able to run. 29 00:01:57,900 --> 00:02:01,900 Other than that thread will be interrupts in the bottom half of the kernel. So your 30 00:02:01,900 --> 00:02:05,900 shell will stop your anything. Doing system calls will stop etcetera. 31 00:02:06,700 --> 00:02:10,300 So, you have to be very careful when you're assigning real-time priorities, 32 00:02:10,600 --> 00:02:14,900 that you do not put anything with a real-time priority. That's not going 33 00:02:14,900 --> 00:02:18,800 to preempt itself at some point. Because if it goes into an infinite loop, 34 00:02:18,900 --> 00:02:20,100 everything else is gone. 35 00:02:21,400 --> 00:02:25,700 For that reason, we don't normally run with the real-time. Instead. We have those 36 00:02:25,700 --> 00:02:29,900 things that are in the one 22 to 23, which is the time-sharing class. And 37 00:02:29,900 --> 00:02:33,800 this is the area where most processes actually run and this 38 00:02:34,000 --> 00:02:38,800 is the so-called time-sharing users. And this is managed by 39 00:02:38,800 --> 00:02:42,800 the time sharing schedulers, which is what we're going to talk about in the next few slides. 40 00:02:44,000 --> 00:02:48,500 Finally, we have a small group at the very top of the list, which are the lowest 41 00:02:48,500 --> 00:02:52,500 priority, which is the idle class and, like, the real 42 00:02:52,500 --> 00:02:56,800 time. These priorities are simply picked by the applications. But 43 00:02:56,800 --> 00:03:00,600 because they're the lowest priority, they don't preempt anything else. So they've 44 00:03:00,600 --> 00:03:04,800 truly only run. If there's nothing else to do. These are typically used for things 45 00:03:04,800 --> 00:03:08,900 like screen savers or other tasks that are of little 46 00:03:08,900 --> 00:03:12,600 importance and you know, just they run if there's nothing better to 47 00:03:12,600 --> 00:03:13,700 do but otherwise 48 00:03:13,700 --> 00:03:16,900 They won't run. And in general. It's actually 49 00:03:16,900 --> 00:03:20,800 from a power perspective, a good idea not to have a 50 00:03:20,800 --> 00:03:24,900 bunch of stuff sitting around in the idol class. Because if the CPU truly 51 00:03:24,900 --> 00:03:28,800 goes idle and doesn't have anything to do, then it will drop itself down into 52 00:03:28,800 --> 00:03:32,900 a lower power state. So you'll have less power either on the battery for 53 00:03:32,900 --> 00:03:36,100 your laptop or for the mains if you're in a data center, 54 00:03:36,100 --> 00:03:40,900 so it used to be that there was this feeling like well, there's nothing better to do just 55 00:03:40,900 --> 00:03:43,700 have a screensaver dancing around all the time. But if you do, 56 00:03:43,800 --> 00:03:47,700 ooh that you are keeping the CPU busy all the time and you are going to draw out more power and 57 00:03:47,700 --> 00:03:51,900 generate more Heat and the rest of it. So do you think a little bit about it 58 00:03:51,900 --> 00:03:54,100 if you're going to put stuff in the idol group? 59 00:03:55,600 --> 00:03:59,900 All right, so the scheduling classes as I already said the higher values of priority, do imply 60 00:03:59,900 --> 00:04:03,700 lower levels of service. So the the lower the number you have is your 61 00:04:03,700 --> 00:04:07,800 priority more likely. You are to run the I thread in the kernel 62 00:04:07,800 --> 00:04:11,900 class. Priorities are managed by the kernel. That is the colonel decides 63 00:04:11,900 --> 00:04:15,600 what the priority ought to be for all the interrupts threads. It decides what the 64 00:04:15,600 --> 00:04:19,200 priority should be for things doing system calls from the kernel 65 00:04:19,600 --> 00:04:23,700 level class. There is no ability to manipulate that by 66 00:04:23,700 --> 00:04:24,500 the, the you 67 00:04:25,500 --> 00:04:29,700 For the interrupt threads, it is possible for the system administrator to go and Fiddle with 68 00:04:29,700 --> 00:04:33,700 those. So if you decide for some reason that you want the network to have a higher 69 00:04:33,700 --> 00:04:37,800 priority, then the clock say you can make those changes. 70 00:04:38,000 --> 00:04:42,400 Generally speaking, that's not a recommended thing to do, but it is something that is 71 00:04:42,400 --> 00:04:46,800 possible. We also occasionally, see, this being done by people writing 72 00:04:46,800 --> 00:04:50,700 real time applications because they want to be able to 73 00:04:51,200 --> 00:04:54,400 control the amount of latency that comes from certain interrupt. 74 00:04:54,600 --> 00:04:58,800 And so on. But generally speaking the colonel, just manages both 75 00:04:58,800 --> 00:05:02,900 of those classes. The real time in idle classes are managed by 76 00:05:02,900 --> 00:05:05,500 the user processes. So the real-time, 77 00:05:05,500 --> 00:05:09,900 whatever the application sets it to be, that's what it is. 78 00:05:09,900 --> 00:05:13,200 Like the operating system does not modify that 79 00:05:13,200 --> 00:05:17,900 so, the issue there is that you need to be very cognizant when you 80 00:05:17,900 --> 00:05:21,300 set them up because if you have two things that are at different 81 00:05:21,300 --> 00:05:24,600 priorities, the higher priority, one is always going to run to the 82 00:05:24,500 --> 00:05:28,900 Domination of the lower Priority One, if you need two things that you 83 00:05:28,900 --> 00:05:31,300 want to guarantee or running at the same always running, 84 00:05:31,300 --> 00:05:35,900 if you assume you have multiple CPUs, then 85 00:05:35,900 --> 00:05:39,700 you can pin them to individual CPUs and put them at the same real-time priority. 86 00:05:39,700 --> 00:05:43,400 And that will make sure that they are never able to preempt each other. 87 00:05:43,400 --> 00:05:47,900 Similar to, the real-time class the idol classes are also managed entirely by the user-process, 88 00:05:47,900 --> 00:05:51,700 and are not manipulated by the kernel, but 89 00:05:51,700 --> 00:05:54,500 the, as I said before, 90 00:05:54,500 --> 00:05:58,700 Or because they're the lowest priority. They don't have the ability to impact anything 91 00:05:58,700 --> 00:06:02,900 else. So other than the fact that you might waste some power, you're never going to 92 00:06:02,900 --> 00:06:06,600 have any kind of negative connotation for the other things that are running. 93 00:06:07,100 --> 00:06:11,800 The timeshare class is the one that is managed by the kernel and with 94 00:06:11,800 --> 00:06:15,400 feedback from the user processes. So most 95 00:06:15,400 --> 00:06:19,300 processes that are running on Unix are in fact, running in this timeshare class. 96 00:06:19,800 --> 00:06:23,400 And so what we're going to predominantly focus on in this lecture 97 00:06:23,700 --> 00:06:24,500 are 98 00:06:24,800 --> 00:06:28,900 Timeshare scheduler tunable, as variables, 99 00:06:29,300 --> 00:06:32,000 essentially how it tick, what makes it work. 100 00:06:33,400 --> 00:06:37,500 So for scheduling choices, I've already said that. We have the real-time scheduler. 101 00:06:37,800 --> 00:06:41,900 You have to have appropriate privilege essentially root privilege. If you're going to be 102 00:06:41,900 --> 00:06:45,800 using the real time because it is, as I've said about three times 103 00:06:45,800 --> 00:06:48,800 already, very prone to causing trouble. 104 00:06:49,500 --> 00:06:53,900 So typically are not going to be using this, unless you have 105 00:06:53,900 --> 00:06:57,900 very tight constraints and it's normally only in things like embedded systems 106 00:06:58,300 --> 00:07:02,900 because the constraints once you start getting to general purpose systems are such that it's very, 107 00:07:02,900 --> 00:07:03,100 very difficult. 108 00:07:03,200 --> 00:07:07,900 Call to do real time and not get yourself in trouble. There are a couple 109 00:07:07,900 --> 00:07:11,100 places where you might need to use it. So, for example, 110 00:07:11,100 --> 00:07:15,800 when you have a laptop, if you doing video streaming, you 111 00:07:15,800 --> 00:07:19,700 probably are going to have some real time threads to make sure that the data for that real-time 112 00:07:19,700 --> 00:07:23,200 streaming gets to the screen at appropriate times 113 00:07:23,200 --> 00:07:27,800 because there's nothing worse than starting at compile running and suddenly having your 114 00:07:27,800 --> 00:07:31,800 YouTube videos become herky-jerky, you fine if the compiled yet turkey 115 00:07:31,800 --> 00:07:32,800 jerky, but you want the 116 00:07:33,200 --> 00:07:37,600 You tube video to look good. The main scheduler that we have 117 00:07:37,600 --> 00:07:41,400 for time-sharing is the so-called interactive scheduler 118 00:07:41,400 --> 00:07:45,800 whose name is Ule. The Ule scheduler came 119 00:07:45,800 --> 00:07:49,900 about actually in the 90s as we were ramping up with having 120 00:07:49,900 --> 00:07:53,600 multiprocessors. So to the earlier schedule, which I'll just 121 00:07:53,600 --> 00:07:57,900 talk about briefly at the end of this slide had really was tied to 122 00:07:57,900 --> 00:08:01,500 the notion that we were running on a unit processor. As soon as you have multiple 123 00:08:01,500 --> 00:08:03,000 processors, you have to deal. 124 00:08:03,300 --> 00:08:07,900 Things like processor Affinity the idea of processor Affinity 125 00:08:08,100 --> 00:08:12,400 is that? It is generally cheaper to run a process on the same 126 00:08:12,400 --> 00:08:16,600 process or that it ran on previously, then to pick some other 127 00:08:16,600 --> 00:08:20,500 random new processor. And the reason for this is that processors have 128 00:08:20,500 --> 00:08:24,400 caches. They have tlb cash a 129 00:08:24,900 --> 00:08:28,900 L1 and L2 memory cache. And at once you've run on 130 00:08:28,900 --> 00:08:32,600 that processor, you have got a lot of your state in those caches, 131 00:08:32,900 --> 00:08:33,100 so 132 00:08:33,200 --> 00:08:37,900 So assuming that you're running fairly soon after the last time you were on that processor, 133 00:08:38,300 --> 00:08:42,900 then much of the stuff that you need will already be in the caches and hence will be much quicker to 134 00:08:42,900 --> 00:08:46,900 run than if everything has to be dragged out of memory. If you get put on some 135 00:08:46,900 --> 00:08:50,900 different processor, that's been the one that you were on previously. Then you will typically 136 00:08:50,900 --> 00:08:54,500 not have any cash State and you will have to bring everything in from 137 00:08:54,500 --> 00:08:58,900 memory, bring in something from one of the caches is typically just a small number of 138 00:08:58,900 --> 00:09:02,700 Cycles. If you have to bring something all the way in from memory, it can often be 139 00:09:02,700 --> 00:09:03,000 10. 140 00:09:03,200 --> 00:09:07,700 Any 30 40 Cycles, while you're just sitting there, twiddling your thumbs waiting for this 141 00:09:07,700 --> 00:09:11,400 data to arrive. So there's a great deal of benefit 142 00:09:11,400 --> 00:09:15,800 from being able to have your data cached. So part of what you all he 143 00:09:15,800 --> 00:09:19,200 does, is keep track of which processors which things are run on. 144 00:09:19,200 --> 00:09:23,700 You can't just always run on the same processor because you could end up with one processor being 145 00:09:23,700 --> 00:09:27,800 wildly overloaded, and if there's some other processor, that's completely 146 00:09:27,800 --> 00:09:31,800 idle. It may be slow to get up to speed, but it's better than sitting there doing nothing 147 00:09:31,800 --> 00:09:33,200 which you would be, if you were sitting in 148 00:09:33,200 --> 00:09:37,800 in the wait, queue for the processor that you ran on previously. So Affinity 149 00:09:37,800 --> 00:09:41,300 had can be taken just so far. There needs to be some shuffling around 150 00:09:41,300 --> 00:09:45,900 periodically. And also, if you haven't run in a while, then any state that was likely 151 00:09:45,900 --> 00:09:49,700 left on the old processor is probably diminished away from other things, having filled the 152 00:09:49,700 --> 00:09:53,800 cash with their data. And so along something that's been sleeping for a 153 00:09:53,800 --> 00:09:57,600 long time. There's less reason to try and get it back on the processor. It was on 154 00:09:57,600 --> 00:09:58,300 previously. 155 00:09:59,600 --> 00:10:03,900 The priority is go up and down based on an interactivity score. And so 156 00:10:03,900 --> 00:10:07,600 if a process is acting as if it is very interactive 157 00:10:07,600 --> 00:10:11,700 than its priority, will generally be pushed up. If something is acting like, 158 00:10:11,700 --> 00:10:15,500 it's essentially a batch job, which doing a lot of 159 00:10:15,500 --> 00:10:19,600 computation with a lot of interaction with the user, then it will typically be 160 00:10:19,600 --> 00:10:23,600 pushed down to a lower priority. The idea being that users 161 00:10:23,600 --> 00:10:27,900 generally want their system to be Snappy that is to respond to 162 00:10:27,900 --> 00:10:29,000 the quickly when they 163 00:10:29,100 --> 00:10:33,600 Hi, Pat it and so by trying to figure out what are the programs that they're interacting 164 00:10:33,600 --> 00:10:37,900 with and giving them a higher priority that ensures that the 165 00:10:37,900 --> 00:10:41,700 system will seem Snappy even if it's got a lot of sort of Grudge work to do. 166 00:10:42,500 --> 00:10:46,800 So, you know, the canonical example is you start a big compile running 167 00:10:47,100 --> 00:10:51,900 and then you want to go in the web browser and look something up. You want the 168 00:10:51,900 --> 00:10:55,600 web browser to be quick and responsive to you 169 00:10:56,300 --> 00:10:58,800 even though you know, it's there. 170 00:10:59,000 --> 00:11:03,800 Going to slow the compiled down, you don't care that they compiled is going to take an extra 20 seconds, but you really 171 00:11:03,800 --> 00:11:07,900 hate it if your browser is being really sluggish. And so that's the 172 00:11:08,100 --> 00:11:12,600 purpose for having the interactivity score. The other scheduler that's 173 00:11:12,600 --> 00:11:16,700 available. And BSD is through traditional share scheduler often 174 00:11:16,700 --> 00:11:20,900 referred to as the for BSD scheduler. This is a schedule that was originally written 175 00:11:20,900 --> 00:11:24,900 back in the 1970s. When the BSD was first 176 00:11:24,900 --> 00:11:28,900 being put together. It is based on multi-level. 177 00:11:29,100 --> 00:11:33,700 Feedback cues. So, rather than trying to gauge interactivity as you 178 00:11:33,700 --> 00:11:37,400 Ellie. Does it simply looks at how much time you've accumulated 179 00:11:37,400 --> 00:11:41,800 recently? And if you've been accumulating a lot of time recently it decides that you should get a low 180 00:11:41,800 --> 00:11:45,700 priority and if you have been sleeping a lot waiting for 181 00:11:45,700 --> 00:11:49,800 input then it assumes your interactive and gives you a high priority. It's actually a 182 00:11:49,800 --> 00:11:53,800 very simple scheduler. It has no notion of processor Affinity, 183 00:11:54,000 --> 00:11:58,900 but it also doesn't have very many dead spots. So it's sort of 184 00:11:59,000 --> 00:12:03,800 Is. It's a very uniform sort of scheduling very predictable, what 185 00:12:03,800 --> 00:12:07,900 it's going to do like the Ule. It does change your priority 186 00:12:07,900 --> 00:12:11,800 based on the behavior. As I just described it in the FreeBSD. 187 00:12:12,300 --> 00:12:16,600 You have to pick which scheduling Paradigm you want at the time, you build your kernel. 188 00:12:16,900 --> 00:12:20,900 So in many parts of the system you have choices where you can pick to do one 189 00:12:20,900 --> 00:12:24,900 thing or another on the fly, in the case of the scheduler that is not the case. You 190 00:12:24,900 --> 00:12:28,900 have to decide at the time you build your Colonel. Do you want to run with for BSD or do you 191 00:12:28,900 --> 00:12:32,800 Run with you Ellie. And the real reason for this is that the 192 00:12:32,800 --> 00:12:36,700 two schedulers really do not interact well with each other and trying to switch 193 00:12:36,700 --> 00:12:40,900 back and forth between them. It was actually tried for a little while, but it was 194 00:12:40,900 --> 00:12:44,900 just it caused periods of transition where 195 00:12:44,900 --> 00:12:48,800 nothing worked very well. And so we just decided that rather than 196 00:12:48,800 --> 00:12:52,700 try and fix it. That you Ellie was going to almost certainly be the scheduler going 197 00:12:52,700 --> 00:12:56,700 forward. So we would just have you had to pick a scheduler and 198 00:12:56,700 --> 00:12:58,700 then we would just 199 00:12:59,000 --> 00:13:03,900 optimized to having a single scheduler. This is proved largely. Correct. It took longer 200 00:13:03,900 --> 00:13:07,800 than expected. Ule was first dropped into the system and the 201 00:13:07,800 --> 00:13:11,600 early 90s. It did not become the default schedule or until the late 90s 202 00:13:12,100 --> 00:13:16,800 and it didn't become the the schedule. It almost everybody used until the mid owes 203 00:13:18,200 --> 00:13:22,700 because it is more complicated. It has more Corner cases where it doesn't do 204 00:13:22,700 --> 00:13:26,800 things quite the way you want. And particularly for people that had 205 00:13:26,800 --> 00:13:28,200 very simple workloads. 206 00:13:29,300 --> 00:13:33,700 Read small embedded systems. They didn't need the complexity of you Ali and so they 207 00:13:33,700 --> 00:13:37,900 would still put for BSD back in because it is much smaller. Less 208 00:13:37,900 --> 00:13:41,900 resource-hungry today. The it's very rarely used but 209 00:13:41,900 --> 00:13:45,800 it is still there. It's still maintained and it still does the same old thing that 210 00:13:45,800 --> 00:13:49,800 it's always done. Finally we have the idol scheduler and I pretty much said 211 00:13:49,800 --> 00:13:53,800 it the administrator sets the priorities and the colonel doesn't mess with them. If you 212 00:13:53,800 --> 00:13:57,900 have to idle processes and their it different priorities than as long as the one 213 00:13:57,900 --> 00:13:58,800 with the higher priority. 214 00:13:58,900 --> 00:14:02,200 Artie wants to run. It will run. So if you, you have to 215 00:14:02,200 --> 00:14:06,900 screensavers and you put him at two different priorities, you're only going to ever see one of them because the other one 216 00:14:06,900 --> 00:14:08,500 is just never going to get a chance to run.