now that we have simple commands let's
see if we can implement piped commands
and in order to do so we're going to
need to understand the pipe system call
before we get into pipe though let's
establish where we're at and set up a
diagram of what we're going to need to
accomplish in the next part of our lab
so we've got a process here I'm going to
name p0 that is a process of the TS
sorry the th SH the Tarheels shell ok so
this is our th SH process and this
process when we begin it we're waiting
at the terminal or we're waiting at
standard input for some input and we're
about ready to let's imagine we had
entered a piped command and where do we
go from here
are you well before we get into that
let's establish our file descriptors for
this process alright so our process p 0
is going to have file descriptors 0 1
and 2 corresponding to standard in
standard out in standard error right and
this is going to be a table aim and so
these values are going to the the actual
entries for each of these numeric
process descriptors is going to be
associated with some file in the
operating system so I'm gonna sort of
the file or remember this is we think of
this as just I Oh input output stream
table in the operating system alright
and the operating system is going to
have an entry for the terminal that
we're connected to for reading and so
I'm gonna say that standard output is 4
and let's just call this TR and terminal
is what will describe the size and then
standard out is terminal for writing and
then the standard ALP or certain
standard air is also going to be
attached to the terminal for writing
alright great so we've got our tables
set up here and this is at the operating
system level and then I'm gonna make a
quick note of that as well all right so
this is the operating system and this is
our processes 0 so when we get a command
I'm going to change colors for our
command here ok so let's try using blue
for this command let's say the command
is something like LS and then we're
gonna pipe LS into grep for the letter C
alright the resulting parse tree of this
write is going to be a pipe node and
it's going to have two children right a
left child which is going to be a
command node and that's going to be the
LS command and it's going to have a
right-hand side which is the another
command node which is going to be the
graph command right so the question is
when we go to execute this tree of of
commands how is it that we are going to
evaluate it step-by-step all right so
let's think about this and try and
imagine what it is we're going to need
to do before we go and implement this
program okay so we are going to process
this node tree step by step and let's
start at the root at the root here the
first node that we encounter is this
pipe node and when we encounter a pipe
node we we should probably handle that
we should set up a new pipe all right so
we're going to make a pipe system call
first and this is our first time seeing
the pipe system call so what does it do
when we call pipe the operating system
sets up a couple of new entries in its
file table right we have a pipe read and
so this is a pipe read in each time we
call this there would be a unique pipe
read and set up right so this is just a
this would be its own unique thing here
that would be separate from any other
pipes this is our pipe Reid and we're
going to also have a pipe right that
gets set up as a part of this right and
then the process is also going to be
it's its file descriptors are also going
to be extended with those two
descriptors so it's going to have at by
this example we'll assume that the
integer values are three and four
we'll learn that whatever these two
numbers are that are the processes
handles on this descriptor would be
returned back to us by the pipe function
call so they might not always be three
and four right like if we were setting
up multiple pipes they certainly
wouldn't be but let's just assume
there's three and four for now and three
would get the pipe read end I'll just do
PR and four would get the pipe right end
right and so now we have these two file
descriptors that if we were to write two
four or read from three we would be
reading and writing to this pipe in the
operating system we've made this
connection all right and maybe I'll just
label these pipe okay so we've set up
this pipe all right and the reason why
we need to do that first is when we go
to then process the the subsequent
commands of spinning up a child process
for LS and spinning up a child process
for a grep we're going to need to give
these file descriptors to them in order
for them to know how to overwrite their
particular standard input or output to
connect up to this pipe right okay so
we've handled this pipe and now what do
we do next well I'm gonna change colors
again and let's say we use in orange
here for the next part for this LS
command all right so next we're going to
look at this LS commence we're gonna
work left to right as we move through
our trees so the pipe was established as
part of processing this pipe node and
now we're ready to go process this
command node alright and what are we
going to give to that command well we're
going to need to give to
in some context about this pipe right
and we'll see that there's a little bit
of extra context we're going to need to
give to it as well but when we go to
process this command what we're going to
do is we're going to fork right so
ultimately when we process a command we
know that we need to fork and when we
fork we create a child process
and when this child process is created
before it goes to execute the LS command
we need to get its table set up
correctly so what happens when we fork
well remember when we fork we get a
second process out of it so now we're
going to have P 1 here and P 1 is going
to have duplicates entries for all of
these file descriptors initially right
so I'm going to copy these over all
right so it's going to have standard
input will still be connected to the
terminal read end output to the terminal
right end air to the terminal right end
and then file descriptors 3 & 4 will be
for the pipe read and the pipe right
okay so this happened automatically as
part of that fork process and we're
still connected to these same back end
file entries in the operating systems
file table ok so we learned about the
doop command or the system call in the
previous lecture and what that allows us
to do is actually establish the correct
connections in process ones or our child
processes file descriptors right because
we want if we're piping the output of LS
to the input of grep then that means we
want to change the standard output of p1
to be our pipe right we don't want it to
be the terminal that we're writing to we
want it to be the pipes right end that
we're writing to all right so we're
going to need to make a call to dupe -
right and what are we going to do with
doop - well we're going to overwrite
we're gonna take the prod the pipe right
and assign that to standard out right so
we would take file entry number 4 and
say hey make
entry number file descriptor entry
number one be the same as it so
effectively process one is going to have
PW as its entry for file descriptor 1
which is its standard output right so we
called dupe 2 to override and I'll just
make a note here for standard out
alright the next thing we want to do is
close the read end right so we're not
going to be reading on process ones pipe
so we're going to close the read end of
this pipe just to be a good citizen here
right so what we want to do is this so
we're going to close the the read end of
the pipe right ok
and now we're ready to say okay we've
set up our file descriptor table and we
want to hand off control to this LS
command right so we want to hand off
control to LS so what do we do well
that's when we call the exec function
right so we're going to exec LS alright
so that's going to be the exec system
call and we're going to exact the LS
command right so this would be us
processing that great so that's forked
for this child now one of the
interesting things about forking and in
executing a command is this is all
happening we don't necessarily know the
exact sequence in which these two
processes are going to run and I should
make a note of this is p1 which became
just now the LS process all right so the
the parent process p0r she'll still
needs to go for our child in it I want
to pause right here for to give a
conceptual introduction to something
that's important to understand notice
that all of this could have happened
before we began the grep function we
could have begun running LS before grep
was started up and why would that be
okay well we're writing it to this pipe
right and that pipe can fill up and when
that pipe fills up because no one is
reading it yet that will cause the LS
program to
pause right there to wait until it can
write more data to the pipe right so
each time you call right it's checking
to see hey can I even write is there
space in the buffer in this pipe for me
to write to and if not it'll pause that
process alright so what else does the
shell process need to do well now that
we've processed the left-hand side
let's go process the right-hand side
right so I'm gonna switch colors to
green here and let's process this
command grep all right so let's assume
now that we are going to fork again all
right so we're going to fork again for
this grep command and I'm gonna draw
this arrow by jumping over this one
alright and now we're setting up a
process to which is currently still thsh
right we haven't yet run the exact
command that would cause that process to
be replaced we know that when we fork we
get a copy of our file descriptors from
the process that we forked from Saudi
this copy is going to come from p0 right
because we forked from p0 okay so let me
enter these in really quickly so this
would be the terminal read end the
terminal right end the terminal right
and the process are sorry the pipe read
end and the pipe right end okay so these
were duplicated from p0 and now we want
to do like effectively the same sequence
of steps we did for the LS process we
need to do for the T the grant process
to set it up to be executed but we need
to be sure that we're careful in
connecting our pipes in the right way
that we expect right so what do we need
to do with this doop - right
so we're trying to once again make sure
that our our standard output of LS flows
into the standard input of grep alright
so in other words we want standard in
for process to this where we're
currently reading from the terminal just
on how this was set up by default we
want that to be reading from the pipe
instead all right so what we would do is
we would say doop - and we would give
three which is the pipe read file
descriptors ID and do overwrite file
descriptor 0 standard in right so
standard in for process 2 is going to be
the pipe read and write so PR is what
we're reading from on the pipe alright
and then we also want to be good
citizens and close the right end of this
pipe so we would close PW right because
we don't need the right end of this pipe
here and then we would go and we would
exact the grep command right so we're
going to exact grep and give it whatever
arguments that needed ok so now this is
no longer TS th sh this is now grep okay
all right so these programs are now
running they're communicating with each
other grep when it has output is going
to be writing to the terminal it's
reading its input from the pipe and the
LS command is is writing its outputs to
the pipe so these two things are
connected via these two processes are
connected via a pipe now what are we
doing back up in our parent process the
the shell program that we're writing
well we want to be good citizens and
close this pipe that we're no longer
using right so this pipe is no longer
open in our process so we would close
the right read end of the pipe and the
right end of the pipe in our parent
process all right so we're gonna close
these two things and I'm gonna change
colors to red and just indicate which of
these ends we're closing out okay so
we've closed out U and U and it closed
out you and you alright and the key
thing that we want to be sure of is just
that the pipe is while it's open and
while we're reading and writing from the
two ends of the pipe in each of these
processes only one of these processes
after this is all setup should have one
of them open and be able to read or
write from it all right now that we're
back up in the p0 what we want to do is
we want to
wait on these processes to complete now
we're not gonna get into the details of
weight in this course I mentioned to you
that we're giving it a an argument of
null which says just wait for any of my
children to finish in to complete but
one thing that we need to know is that
when you wait you're as soon as a single
child is exited or completed it will
return from that wait call and continue
on in the program
right so the first time we wait I'm
going to assume that the LS command was
or the LS process was the first of these
two processes to wait that would cause
we wouldn't continue on from the first
call to wait in our parent process until
after LS his process can completed but
we also need to wait again so we're
going to need to wait the same number of
times as there are children processes
which we spin up if we want to do this
in a blocking way which we are we would
want to wait again all right and then
our program would continue on and ask
the user for another command after we've
completed all of these things mean so
this is the strategy that we're going to
follow for setting up a pipe spinning up
a child process for the right end of the
pipe spinning up a child process for the
read end of the pipe and then waiting on
both of those processes to complete
before we prompt the user again for
another command right and the good news
here is that this strategy can be
followed by effectively taking our tree
structure here and first doing the work
that we needed to do on the pipe second
doing the work we need to do on our the
left hand side of the pipe and then
third doing the right hand side of the
pipe now I want to point out that this
command could be more complicated right
we could have had another pipe here
instead of a command that was made up of
two more commands and we would have
needed to recursively apply the same
process and what that means is when we
returned back from any node we're also
going to need to say as a return value
back up from our execution
strategy how many children are we
waiting on or how many children does the
parent need to wait on right so we're
going to need to return that information
back up as we are recursively descending
down this tree the the the information
we're going to return back up is how
many times will the parent process need
to wait in order to know that all of the
children have completed right and so in
the case where we have just two nodes in
this command nodes in this tree that
we're waiting on we would just have to
but again if we had a command where
let's imagine this were another pipe and
we had another command here and here how
many would we be waiting on well this
would return one this would return one
and then pipe is going to return the sum
of those two sides right so that would
return two and then two plus one would
give us we're gonna need to wait on
three commands two or three processes to
finish up in that example right so we're
going to need to structure our the the
functions which process a tree of nodes
in a clever way that allows us to do two
things one we're going to need to get
that information back from those those
function calls how many processes does
the parent need to wait on into we need
to pass as we're as we're moving down in
to the recursive parts of each of these
commands we're going to need to pass in
some context in the context that we're
going to need to pass in are some
instructions about like hey process one
here is the here the file descriptors
you should use for standard input and
standard output and what we're gonna do
is tell process one from our parent like
use the pipe right end to be your
standard output use that's what's going
to give it the inclination to call doop
two on that particular descriptor and
then we're also going to need to say
here is the descriptor that you need to
close that you're not gonna make use of
right and the same thing for a process
too so let's actually resolve some of
those details in code and jump into code