Next up, lesson 3 on processes. So we're going to
start drilling down and looking at some of the structure and infrastructure
that surrounds processes. Let's start with the process
resources. We already looked at this in the previous lesson, but we're
now going to fill in some more of the details CPU time. We've
already talked about is basically boils down to scheduling, which we
will see more of in this section.
Asynchronous events, which are the external events. These are things like
the timers that are going off, the hardware exceptions that we've gotten,
not that any of your programs would have Hardware exceptions, but it's been known to happen
and external events. These are the events
arrival of data or stop and continue. All those kind of things.
And finally, we have I/O events. This is notification
of completion of I/O or availability of I/O or
exceptional.
Data coming on the network, Etc.
The memory we have again, we describe briefly
what we're going to now drill down and look at how that gets broken up.
We have the text and data that makes up the executable.
So when you run LS, let's say what ends up happening. Is we
go out, we find the file. That is the ls executable
and it has a little header on it. That describes, what kind of, you know, that it is an executable
and things that it needs like libraries and so on. But
primarily
It describes, the three pieces that make up that
executable. So there's what we call the text, which is actually the compiled
code. The thing that is going to actually execute on the machine.
And then there are two data areas uninitialized data area
and an uninitialized data area. So, the initialized data area
is all of your Global variables that you've declared that you gave an
initial value to. So, if you said in Foo, equals one
that says is
Will variable Foo, and when the program starts, it should have the value 1.
If you just said into bar with no initial
value, then that just says, when the program starts up, there's this Global variable bar
and I don't care what its value is, which is really a way of saying
it should start out as 0. Now. It would be possible
to compile code that would simply assign all of the different values
to all the global variables as the program started up. But there's a
much easier way of doing that.
And that is that the loader just sorts them all together. So it knows how they're laid out in
memory, and then it just creates a memory image with all the initial values in
it. So by simply reading that page from the disk into memory,
now, you have all of these variables with their initial values. So
what ends up being stored in the executable then is the compiled
text. And then this image of all the initialized variables.
And then we have also the uninitialized data, and we could just store
Huge block of zeros in the file, but turns out we know how to create those very quickly. And
so instead we just store the size of the uninitialized data area. And
so when it starts up we can just zero out that memory and everything will
have zero values.
So in theory, what would happen is when you started this
program running, then we would bring in the text.
We'd bring in the initialized data area. We'd zero out the uninitialized data area and then we could
start running it but we're very lazy. We
have this attitude of do not do today, what you can put off till tomorrow
and we'll just hope that tomorrow never comes and in fact in the case of
executables that works out extremely well. So what ends up happening
Thing is that instead of actually reading all this stuff in which for a large executable would take a
long time. Instead. We just allocate the virtual memory
areas and then we just say, oh if you need that, it's over here. And if you need that, it's on this place.
And if it's need that, there's erode stuff than well. Just 0 it for you.
And then we just say go. Okay, start running and you jump and wherever you jump won't be
there. So we will take an immediate page fault and we will go off and we'll bring
in the text and we'll try and execute that. And that probably will cause some more
painful.
Will take a few page faults and pretty quickly. We will have at least the stuff that we need to get up and
running and away we go.
Now, in addition to that text and data, we're going to, once we start running, we're going
to be allocating additional space with Malik typically.
And so when we do Malik's, we need to have an area that we can allocate
that from. And that area as we'll see when we talk about the virtual memory
layout, appears following the uninitialized data area.
And then, of course, we need our runtime stack and that's going to start at the top of memory
and grow downward.
Now, why does this whole business of just not allocating any of these
things to start and just letting it be allocated on the Fly work to our advantage? I
mean, instead of reading it all in and one solid read instead. We're going to be killed by a
Thousand Cuts with all these page faults. And that would be true if we actually
ended up bringing all these things into memory, but the fact the matter is that we
don't and in fact, the average executable never even touches half
of its address space.
Now that probably seems odd. I mean, what's what's all that
unused stuff? Well, let's take LS as an example.
How many options does Ls have actually, there was once a trivia
question, which is what are the three letters that are not options? Two Ls.
So basically every letter of the alphabet capital and lowercase along with most of the
numbers are actually options to LS. Every one of those options
has code, that implements it data structures that supported etcetera.
And the typical user, you know, power LS, user might use 2
or 3, l s- l IR some side of
small set of options. And so when we run LS,
we only need to bring in the text and data structures that support those options
and all this stuff text and data, for all the other options. We don't
touch it. We never bring it in the program exits and we're done.
And in fact, is, will see. When we look at the virtual memory. We actually keep track of the pages
that we have brought.
Into memory. So, that the next time you run LS, we don't have to bring those in off
the desk. We already have those in memory. We can just immediately attached to them.
So in fact, if you run Alice with the same options, chances are we won't
do any I/O at all. It'll just all be sitting around in memory and we will simply
grab it. So again, the
importance is, in the details of
how you implement these things, this sort of straightforward and obvious way of implementing a lot of these
things. In fact, would work.
But the system would be much slower if we were doing all this extra
I/O, tying up all this extra memory Etc. Okay. Finally,
we have iodophor scripters. We've already said, we've got file descriptors which
reference files. We've got pipes, which is a primitive form of interprocess
communication sockets, which are sort of a more
advanced form of interprocess communication. The thing with pipes is that the
two processes have to plan in advance that they want to be connected
versus sockets. You can create
Connections after the fact. So one way of looking at it is sockets is
really like pipes but you get to do your own Plumbing after the fact.
And then historically there were streams. This was the AT&T system
5 and later Sun Solaris. Although it was thought in the
80s that this was going to essentially replace sockets. Then suddenly
this large company in the Pacific Northwest of the United
States realized that the internet was a thing that they needed
and they decided
To call their implementation windsock, which was somewhat based on sockets.
And that sort of put the, the death Spike through streams. Because if you wanted portability
between Windows and Unix systems, then you use sockets. So
today streams aren't interesting footnote, but largely sockets is the
interface that people use
This next slide shows the BSD process structure.
And I put BSD in the top title of this slide because this
slide is very particular to
BSD pretty much everything we were talking about so far would be
equally applicable to Linux as it would be to be a Ste as it would be to
Solaris. Pick your favorite Unix flavor, but there are
some places where I'm going to drill down and really talk about things that are BSD
specific and I usually will put BSD in the heading of the
slide to let you know that this is
Something that is more specific to BSD. That being
said, in this particular picture, all the things that we've
shown need to be in every one of those systems. So the difference
between BSD or Linux say is simply where these things get placed.
So in the BSD world, we have a very small process entry and then all of the other
structures are actually separate sub structures, which are
referenced out of the process entry. So, the process entry itself is on the order of 5.
212. Bytes then all the rest of this stuff probably adds up to somewhere around eight
kilobytes, but we push them down into sub
structures so that we can take references to them if we
want to clone copies. So we want to make other threads or
other processes with a lot of sharing going on as we'll talk about shortly. It makes it
much easier to do where we just have to create the process entry and then just take references on most
of the substructures. So, if you were to look at Solaris or Linux, you would see
a
You are the substructures instead. They would be embedded in the process, entry itself. The fact,
the matter is, they're there. It's really just a question of how they end up being
organized. So, I want to just sort of go through and and briefly
talk about these because we're going to come back and look at most of these in a lot more detail.
So, starting at the top. We have the process group in
sessions. This is ways of organizing processes, which we'll see later in this lesson
of the credential, which it keeps track of who we are,
and
It's essentially our user ID and our set of groups that we're working with.
The VM space is the thing that describes our address space, which is actually made up
of a list of regions. Each region has some distinct
property. So there's the text region, the initialized data region, the uninitialized, data
region, the stack region. And so on again, we will see that in the
section when we talked about virtual memory file, descriptors will see this and
actually when we get to the iOS lesson, this is the way we keep track of
the
Descriptors that the process has open which in turn are going to
reference file entries, which is where the kernel tracks the information
about those file. Descriptors. We have resource limits, which allow us to control
the amount of resources that any given process is going to use.
We can control the amount of memory, the amount of I/O, the amount of
CPU time. There's there's many, many different resources, which we
do not detail in this particular class, but is described
quite thoroughly in the
Book, we have a system called Vector. Remember that I told you that
it was possible to run Linux binaries on a FreeBSD system. The problem, of
course, is that Linux uses different numbering schemes, sometimes different
parameter orderings or numbers of parameters for their system calls.
And so the easiest way to do that efficiently
is that we have a system called Vector which is
described the FreeBSD system, call convention.
There's another system called.
Actor that describes the Linux system call convention. And so when a
executable is started up we look in its header to see whether it is a FreeBSD binary
or a Linux binary and then we simply install the appropriate system
call Vector for that binary. So this way you can have some
processes that are running as FreeBSD and others that are running as Linux. And in
fact there have been other system called vectors done. So for example, one for
Solaris, we're in times past system, five single
actions.
Keeps track of what you want to do. For all the possible signals. We've talked about a bunch of them already.
So if you set up a signal Handler for a single arm because you want to
get a real-time event. This is where we store the information about what the
process would like done. We Gather a lot of statistics about what's going
on. These are the statistics that are typically dumped out when the process
exits, and then finally, in the BSD world. We have a
notion of multiple threads running within the same process.
Address space typically.
Process has all of the stuff that we've described so far and then a single
thread that's running around inside the process doing whatever the process is doing,
but it is possible to have multiple threads
running within the same process. It's a slightly different model than that
used by Linux. And in fact, I have a slide that's going to describe the differences between
those, but if you have multiple threads there, you'll have multiple
threads structures at the bottom, and the thread structure keeps track of information
that's specific to
To a thread of control. So how is it being scheduled
information that it's state block, which is where we store our example, all of the
register values if it's going to be put to sleep so that we can restore them when it
wants to run. Again, most importantly it's thread, stack. Every
thread has to have its own stack when it runs inside the kernel because they may run inside the
kernel, concurrently and then an area for any machine
dependent threat information, different architectures, have different sorts of stuff that they
want to keep about.
Ed's, so let's drill down now and look
at the difference between multiple threads running in a process
versus having multiple processes. The notion of having
multiple threads running within the same process
itself. You have one process structure and
then you have, as I said, different threads that are running within that process structure,
Okay, so
The benefit of this, is that switching between threads is very cheap,
because everything is in place. You don't have to change anything. All you have to do is load a new stack pointer, and a
new program counter and a set of registers
general-purpose registers and you're done it. You switch to it. And
so the cost of switching between one and the other is
tens of instructions.
The drawback to the K thread model is that you have only one address
space and so, because you have only one address
space and each thread wants it its own stack. You have to take the
traditional stack that we have for the process and break it up into
pieces, one for each of the threads. And so there's a lot more management of that
and you have to worry about one stack running down into the next stack. And
so it is certainly more complicated. So the
Benefit is that it's very cheap to switch between threads. The
drawback is that you have a more complex set of data structures that you need to
manage at the process level. So the approach that was taken
by Linux is what we call the our Fork model, the resource
fork. And if you recall from the data structure, we had all those various different
substructures. And with with our Fork it allows you to say
what you want to share and what you want to have private.
So in the, in the
A thread model. Everything is shared. The address space is shared. Descriptor shared. The signals are shared
everything in the our Fork model. You can say, well,
we're going to share the descriptors and we're going to share the resources,
but when it comes to the address space, we're going to share the text
and data area of it, but we want everyone to have their own
stack area. So now every single one
of these are forked processes is sharing all of the text
and data, but it has
sewn stack. So we don't have to have the K thread complexity of carving up the stack into
smaller pieces.
But the drawback to this is
that. Now when we want to switch from one thread to another, we no
longer just change a stack pointer and a program counter instead.
Now, we actually have to change address spaces and
as we will see, when we talk about context switching is a very heavy weight
operation, several thousand instructions to do. And
so, although we get the benefit of having each process
having its own stack.
Jack instead though. We pay the cost of switching from one to another.
So you can't have these sort of light weight thread to just sort of float around and do a little bit
on there. Each one instead, you tend to use the our Fork model
for things like an instance of a web server or an instance of a mail
server, something where you're going to do a fair amount of work to amortize
that cost of doing the context switch, that being said,
FreeBSD actually has both the our Fork model and the K thread model,
but because many
Applications have been written for Linux over the years than for FreeBSD. Our Fork model really
sort of needs to be a first-class citizens because that's what they are expecting.
And so the where the rubber meets the road is the thread library.
And because the most of the threaded applications live on top
of the thread library. And if the thread library is, is
targeted to the our Fork model, then it would be much easier for
those applications to be ported. Then if the thread library is pointed
at the K thread,
Do so at a system called level the FreeBSD supports both K threads and
our Fork bought at the threading Library level. It uses the our Fork
model and so, predominantly applications running on
FreeBSD are running in the artwork model. Next up. I want to
talk about process states. There are
four states that process. These may be in. So, this first
slide, we will talk about the two main ones. The first of these two is
the running State. And this is a
Where the process is sitting there with its program counter sitting
in front of an instruction that it would dearly like to execute. If only it could be on a
processor in running. And so, a runnable process is either, hopefully actually
running on a processor or it's sitting on a queue waiting for a
process or to become available so that it can run. So
it's the state of executing the other main
state is the sleeping State. And this is a process that
is sleeping way.
Waiting for typically some event to occur. A sleeping process will
always have a thing called the weight Channel or W. Chan, and that
keeps track of the resource that the process is waiting
for. And so, when a process goes to sleep and house to say, why
it's going to sleep, but can't just decide it wants to take a nap and go to sleep. It has to say,
I'm going to sleep, because I'm waiting for this thing to happen for this thing
to become available. And the reason it has to
say what it's waiting for.
Is because the only way it's ever going to not be sleeping is when it is
issued a wake up and the wake up is going to be because some particular
resource becomes available. So typically a process
comes into existence. It's in the Run state. It runs for a while and then it blocks
sleeping waiting for something like disk IO or network or the user to type something.
At some point, one of those events occurs the wake up
gets issued the sleeping processes. Then move back to the Run state
where will run until
oh, it's finished processing. Whatever that input is typically it will then block waiting for the next import
or waiting for output or whatever. The longer-term event is that it's waiting for,
if you look in a typical system, you'll often see maybe
5000 processes in the system
often with multiple threads inside them. But the number
of running processes typically far far smaller, maybe 10
or 20 or 30 out of the 5,000, the vast majority of processes.
In most systems are sleeping waiting for some particular thing to happen,
so they can proceed. So you think the web server it sitting there waiting for your web
request to come in. You asked for it. It finds it. It sends it, and it goes back waiting for you
to ask for the next thing. So, the
point is that the running processes are usually in the in the
minority and the vast set of things are sleeping. And if you actually look at what they're
doing, if you do a long listing of Pious, it'll actually show you all those.
Wait Channels with a descriptive text. So it'll say it's waiting for network IO or it's
waiting for disk I/O, or it's waiting for terminal I/O or whatever.
The the resource is that it's blocked waiting for. We then have to other
states for processes. The first of these is the stop State
and the this is used when we're doing either job
control or debugging. So, in the case of job control,
you can hit control Z and that says, stop the process and it will
extend be stopped.
Until such time as you send it a continuous signal saying you want it to start running again.
So, a process will move from either the sleeping or the running State into the
Stop State either because of job control, or in the case of the
debugger. It will put in Trace breakpoints. And
when, when you hit one of those trace breakpoints, the program moves into the Stop State,
and then add the bugger can sit there and examine it and decide what it wants to do. And at some point
it in the debugger, you can say, all right, start it running again, which point it will
tend to continue
Which again will take it out of the stop State, and put it into the running, or the sleeping state?
So stop state is one which is only ever entered
due to intervention either by the user directly with job control or indirectly
through a debugger. And once in the stop State, you will stay
in that state until whoever put you in that state, decides that it's time for you to start
again at which point you will then move back into the sleeping running
Continuum again, now, the issue is that you can
come to the stop State either from when you were
running or when you were
Sleeping. And in fact, you might have been sleeping in the event that you are waiting for
may have occurred. And so you may have been issued a wake up, but you will not suddenly
jump from stopped into the running Q because the stop State. As I said is
one where you only exit when told to do so, but we still need to keep track
of that because when you are told to continue, we need to know whether to
put you into the Sleep queue or into the Run queue. So,
if you're running, you're not waiting for anything. So your weight channel will be 0 if
you're sleeping, then,
Your weight channel has to be non zero, indicating what it is you're waiting for. So, in
fact, when we continue a stopped process, all we have to do
is look at the weight Channel. And if it is in
non zero, then we know it's sleeping. And we just say, okay, it's on the Sleep Q now and everything
was fine. And when whatever it's waiting for happens, it'll happen. If on the other
hand, that we see that the weight channel is 0, then we know that was
previously running or had been sleeping but with go
To be made running. And so at that point, we can take it and drop it, directly onto a run queue, which
will hopefully fairly shortly, cause it to be picked up and be run by
one of the CPUs. We then have a couple of minor
States, the new, which is where the process is first being
created. The only way to create a processes in the fork system call.
So your parent has to make a fork which makes a copy of the parent. Typically, that
will be followed fairly quickly by an exact, which will then overlay it with some other
process. So, if your shell,
No Forks, initially, you're running another copy of the shell, but then it overlays itself without
laughs, or emacs, or whatever. It is, that you've decided you want to run.
The main reason for new is just so that the kernel
where it's looking at. All say, all the processes for some reason comes across
one that's marked new. It knows that its embryonic and that
it may not. In fact be fully formed. Therefore. It is not safe
to try and track down some of it substructures because they may not exist yet.
So, as a
And you'll often see places in the kernel where it will switch on the state, you know, if it's
running do this, if it's sleeping, do that, if it stops something else and it sees new, it's almost
always continue, don't do anything because we just don't know what
what state that process is in a new process, doesn't
stay in the new state for very long. As soon as it's got all of its resources pulled
together. It will then be dropped into the Run queue and
begin running and doing whatever it is that it's going to do.
So, it's actually very
Rare to actually see a process marked as new when you do a PS, but
very very occasionally, you will see it. And it's just a process that hasn't been fully
created yet at the other end of the life cycle are the dreaded zombie processes.
These are processes that are in the state of
exiting so they have exited or been forced to
exit due to a signal of some sort that wasn't handled and
they are in this zombie State and there's two things that they need to
do before they can truly.
Away from the system. The first is they have to get rid of all their resources.
And you know, you'd say well that can't be very hard. You know,
you know, here's my memory. You know, here's here's my signal State. Here's this here's that
really the only one that's difficult to get rid of our, the I/O
descriptors because of course, for the I/O descriptors. We have to close any descriptors that
you have that are open. And for the most part, even, that's not too difficult,
the place where we get in trouble is for descriptors that reference
TCP.
Ins TCP connections have the property that they are reliable and
by reliable, we mean that if you have done a right system, call onto a socket
descriptor, then there is a promise that we will get
that data to the other end of the connection if it's at all
possible. And if it's all possible, means The Listener on the other end,
still has the connection open and the network in between is still
connected. And so what can happen is that you might
be output to.
To a remote login session, the user hit Ctrl q' to stop the
output. And then, you know, went to San Francisco for a week
to record a class. And so, until they get back, and they hit the
control. Yeah, control us to start it going.
Then it's just going to sit there. And so, it's going to sit on the Queue,
because it's already full of stuff at the destination of stuff to print.
And so, any extra that we've already accepted is sitting here on our socket that
We're trying to close if we close the socket and release the resources then
not going to drain, and it's going to get lost. It's not going to get pushed through. And
so we would not be reliable. So, we have to sit there
and keep that descriptor open until such time as we get it to the other end, which may be a
long time. So one of the reasons that you
see zombies is that they're unable to close their connection.
Once they got rid of all their resources, they can then return their
It's status to their parent. And so there's the weight system call,
which is what allows the parent to get the exit status
for its children. And so it reads in that information
and, you know, gets how much time it ran and resources that used and so on.
The other reason that you can not, you can stay as a zombie is if your
parent hasn't collected, your exit status, so you've managed to get rid of all your resources, but
now you just need your parent to do a weight system call. Well,
any application that's been written by people that know the
system will know that they need to collect the exit status of all their children.
So things like I netd or sshd, Etc, are
not going to make that mistake. So if you see one of those programs that
Sitting there with something in a zombie State it's because it's presumably
unable to close one of its connections. On the other hand.
If it's a new programmer to the system, they may have read only halfway through the manual. So they know about
fork and exec, but they haven't gotten to the W's yet to learn about weight. And so they just
keep creating new processes, but they never collect the exit status. And some of
them are such awful parents that they just up and
exit themselves, without ever collecting the exit, status of their parent, of their children.
And so,
So now you would have these zombie processes, wandering through the system forever more.
But luckily we actually have an orphanage process, which is processed one or
in it and it's in its role in life to sit around and wait
for these orphaned children. So, when a parent
exits without collecting its children's exit status, those children, all become
children of a net and now and it will sit there and collect the exit
status. Pat them on the head, throw it away. Collect the next exit status, Pat
them on the head, throw it away. What the
Is that all those children will then all those zombies will now go out of the system.
So in fact, if you're trying to figure out which kind of zombie, you have there,
if you do a long listing of PS, it'll show for every child, the
parent process ID. And so, if you see a whole bunch of zombies, and they all have a
common parent, that's not something like sshd, or I netd. You
know, it's a DOT out being owned by some new programmer.
You can test the theory by killing the parent killing the, a DOT out and now all of its children.
Children will suddenly be inherited by an it. And if they all go away, then you know, that was the
problem on the other hand, if they all become children of a net and they
all have, you know, they continue to just be zombies hanging there. Then, you
know, their problem is not that they didn't have their exit status collected, but rather
that they're having trouble getting rid of their resources.