The next subsection that we're going to talk about having to do with processes is
scheduling.
So we'll start with some of the high-level view of the different classes that
we have available when we are doing scheduling
in particular, the threads get divided into five different classes,
so you can see on the left of this with a we've organized, the priorities. So
every thread has a particular priority assigned to it, that
priority may change over time, but the range that it's in will
tell you what class it's in. So the priorities range from 0 to 2.
It in 55 and Sub-Zero 247. As you can see, is the first
grouping of the priorities and we call this the, I
thread class. This is things that are running in the bottom half of the kernel.
So, anything that's like an interrupt when it's running in
that interrupt. It's going to have a priority that somewhere in this do 247
priority range.
Next up. We have 48 to
79. These are the real time priorities and these are priorities that can be
assigned by anybody that's running in the real-time
scheduling class, which will talk a little bit about then we get 80
219, which is Colonel priorities. And this is the top half of the kernel
and those things are the ones that are doing the system calls.
The priorities range from 0 being the
highest priority to
Five being the lowest priority. So, I threads are going to get
precedence over real time. But real time are going to get frustums over the colonel.
So if some application doing real-time sets one of its
threads into one of the real time priorities, and then that thread goes into an infinite
Loop, the entire system will just lock up. The only thing that'll be able to run.
Other than that thread will be interrupts in the bottom half of the kernel. So your
shell will stop your anything. Doing system calls will stop etcetera.
So, you have to be very careful when you're assigning real-time priorities,
that you do not put anything with a real-time priority. That's not going
to preempt itself at some point. Because if it goes into an infinite loop,
everything else is gone.
For that reason, we don't normally run with the real-time. Instead. We have those
things that are in the one 22 to 23, which is the time-sharing class. And
this is the area where most processes actually run and this
is the so-called time-sharing users. And this is managed by
the time sharing schedulers, which is what we're going to talk about in the next few slides.
Finally, we have a small group at the very top of the list, which are the lowest
priority, which is the idle class and, like, the real
time. These priorities are simply picked by the applications. But
because they're the lowest priority, they don't preempt anything else. So they've
truly only run. If there's nothing else to do. These are typically used for things
like screen savers or other tasks that are of little
importance and you know, just they run if there's nothing better to
do but otherwise
They won't run. And in general. It's actually
from a power perspective, a good idea not to have a
bunch of stuff sitting around in the idol class. Because if the CPU truly
goes idle and doesn't have anything to do, then it will drop itself down into
a lower power state. So you'll have less power either on the battery for
your laptop or for the mains if you're in a data center,
so it used to be that there was this feeling like well, there's nothing better to do just
have a screensaver dancing around all the time. But if you do,
ooh that you are keeping the CPU busy all the time and you are going to draw out more power and
generate more Heat and the rest of it. So do you think a little bit about it
if you're going to put stuff in the idol group?
All right, so the scheduling classes as I already said the higher values of priority, do imply
lower levels of service. So the the lower the number you have is your
priority more likely. You are to run the I thread in the kernel
class. Priorities are managed by the kernel. That is the colonel decides
what the priority ought to be for all the interrupts threads. It decides what the
priority should be for things doing system calls from the kernel
level class. There is no ability to manipulate that by
the, the you
For the interrupt threads, it is possible for the system administrator to go and Fiddle with
those. So if you decide for some reason that you want the network to have a higher
priority, then the clock say you can make those changes.
Generally speaking, that's not a recommended thing to do, but it is something that is
possible. We also occasionally, see, this being done by people writing
real time applications because they want to be able to
control the amount of latency that comes from certain interrupt.
And so on. But generally speaking the colonel, just manages both
of those classes. The real time in idle classes are managed by
the user processes. So the real-time,
whatever the application sets it to be, that's what it is.
Like the operating system does not modify that
so, the issue there is that you need to be very cognizant when you
set them up because if you have two things that are at different
priorities, the higher priority, one is always going to run to the
Domination of the lower Priority One, if you need two things that you
want to guarantee or running at the same always running,
if you assume you have multiple CPUs, then
you can pin them to individual CPUs and put them at the same real-time priority.
And that will make sure that they are never able to preempt each other.
Similar to, the real-time class the idol classes are also managed entirely by the user-process,
and are not manipulated by the kernel, but
the, as I said before,
Or because they're the lowest priority. They don't have the ability to impact anything
else. So other than the fact that you might waste some power, you're never going to
have any kind of negative connotation for the other things that are running.
The timeshare class is the one that is managed by the kernel and with
feedback from the user processes. So most
processes that are running on Unix are in fact, running in this timeshare class.
And so what we're going to predominantly focus on in this lecture
are
Timeshare scheduler tunable, as variables,
essentially how it tick, what makes it work.
So for scheduling choices, I've already said that. We have the real-time scheduler.
You have to have appropriate privilege essentially root privilege. If you're going to be
using the real time because it is, as I've said about three times
already, very prone to causing trouble.
So typically are not going to be using this, unless you have
very tight constraints and it's normally only in things like embedded systems
because the constraints once you start getting to general purpose systems are such that it's very,
very difficult.
Call to do real time and not get yourself in trouble. There are a couple
places where you might need to use it. So, for example,
when you have a laptop, if you doing video streaming, you
probably are going to have some real time threads to make sure that the data for that real-time
streaming gets to the screen at appropriate times
because there's nothing worse than starting at compile running and suddenly having your
YouTube videos become herky-jerky, you fine if the compiled yet turkey
jerky, but you want the
You tube video to look good. The main scheduler that we have
for time-sharing is the so-called interactive scheduler
whose name is Ule. The Ule scheduler came
about actually in the 90s as we were ramping up with having
multiprocessors. So to the earlier schedule, which I'll just
talk about briefly at the end of this slide had really was tied to
the notion that we were running on a unit processor. As soon as you have multiple
processors, you have to deal.
Things like processor Affinity the idea of processor Affinity
is that? It is generally cheaper to run a process on the same
process or that it ran on previously, then to pick some other
random new processor. And the reason for this is that processors have
caches. They have tlb cash a
L1 and L2 memory cache. And at once you've run on
that processor, you have got a lot of your state in those caches,
so
So assuming that you're running fairly soon after the last time you were on that processor,
then much of the stuff that you need will already be in the caches and hence will be much quicker to
run than if everything has to be dragged out of memory. If you get put on some
different processor, that's been the one that you were on previously. Then you will typically
not have any cash State and you will have to bring everything in from
memory, bring in something from one of the caches is typically just a small number of
Cycles. If you have to bring something all the way in from memory, it can often be
10.
Any 30 40 Cycles, while you're just sitting there, twiddling your thumbs waiting for this
data to arrive. So there's a great deal of benefit
from being able to have your data cached. So part of what you all he
does, is keep track of which processors which things are run on.
You can't just always run on the same processor because you could end up with one processor being
wildly overloaded, and if there's some other processor, that's completely
idle. It may be slow to get up to speed, but it's better than sitting there doing nothing
which you would be, if you were sitting in
in the wait, queue for the processor that you ran on previously. So Affinity
had can be taken just so far. There needs to be some shuffling around
periodically. And also, if you haven't run in a while, then any state that was likely
left on the old processor is probably diminished away from other things, having filled the
cash with their data. And so along something that's been sleeping for a
long time. There's less reason to try and get it back on the processor. It was on
previously.
The priority is go up and down based on an interactivity score. And so
if a process is acting as if it is very interactive
than its priority, will generally be pushed up. If something is acting like,
it's essentially a batch job, which doing a lot of
computation with a lot of interaction with the user, then it will typically be
pushed down to a lower priority. The idea being that users
generally want their system to be Snappy that is to respond to
the quickly when they
Hi, Pat it and so by trying to figure out what are the programs that they're interacting
with and giving them a higher priority that ensures that the
system will seem Snappy even if it's got a lot of sort of Grudge work to do.
So, you know, the canonical example is you start a big compile running
and then you want to go in the web browser and look something up. You want the
web browser to be quick and responsive to you
even though you know, it's there.
Going to slow the compiled down, you don't care that they compiled is going to take an extra 20 seconds, but you really
hate it if your browser is being really sluggish. And so that's the
purpose for having the interactivity score. The other scheduler that's
available. And BSD is through traditional share scheduler often
referred to as the for BSD scheduler. This is a schedule that was originally written
back in the 1970s. When the BSD was first
being put together. It is based on multi-level.
Feedback cues. So, rather than trying to gauge interactivity as you
Ellie. Does it simply looks at how much time you've accumulated
recently? And if you've been accumulating a lot of time recently it decides that you should get a low
priority and if you have been sleeping a lot waiting for
input then it assumes your interactive and gives you a high priority. It's actually a
very simple scheduler. It has no notion of processor Affinity,
but it also doesn't have very many dead spots. So it's sort of
Is. It's a very uniform sort of scheduling very predictable, what
it's going to do like the Ule. It does change your priority
based on the behavior. As I just described it in the FreeBSD.
You have to pick which scheduling Paradigm you want at the time, you build your kernel.
So in many parts of the system you have choices where you can pick to do one
thing or another on the fly, in the case of the scheduler that is not the case. You
have to decide at the time you build your Colonel. Do you want to run with for BSD or do you
Run with you Ellie. And the real reason for this is that the
two schedulers really do not interact well with each other and trying to switch
back and forth between them. It was actually tried for a little while, but it was
just it caused periods of transition where
nothing worked very well. And so we just decided that rather than
try and fix it. That you Ellie was going to almost certainly be the scheduler going
forward. So we would just have you had to pick a scheduler and
then we would just
optimized to having a single scheduler. This is proved largely. Correct. It took longer
than expected. Ule was first dropped into the system and the
early 90s. It did not become the default schedule or until the late 90s
and it didn't become the the schedule. It almost everybody used until the mid owes
because it is more complicated. It has more Corner cases where it doesn't do
things quite the way you want. And particularly for people that had
very simple workloads.
Read small embedded systems. They didn't need the complexity of you Ali and so they
would still put for BSD back in because it is much smaller. Less
resource-hungry today. The it's very rarely used but
it is still there. It's still maintained and it still does the same old thing that
it's always done. Finally we have the idol scheduler and I pretty much said
it the administrator sets the priorities and the colonel doesn't mess with them. If you
have to idle processes and their it different priorities than as long as the one
with the higher priority.
Artie wants to run. It will run. So if you, you have to
screensavers and you put him at two different priorities, you're only going to ever see one of them because the other one
is just never going to get a chance to run.