Systems Programming Practice: The Yalnix Shell
Handed out: January 21, 2000
Due in: End of January 28th, 2000
This project is a one week affair whose purposes are:
To get you to use the Solaris programming environment, especially make and the debugger(s) while it's still easy.
To make sure you understand the semantics of some of the system calls you will implement in project 3. These system calls control processes, including their creation, destruction, hierarchy, and file I/O.
To give you practice interpreting the system documentation (``man'' pages) regarding these syscalls, including caveats and behavioral exceptions. This is a skill that every programmer, and especially, every systems programmer, needs.
To face concurrency in an easy case. Concurrency will be the main difficulty of project 2.
This document is rather long, but don't despair; most of it is background material that you probably know already.
Your shell program need not be very large, and therefore you may not need the usual development tools to compile it and debug it. However, we will also ask that you use two development tools, make and one of the available debuggers. Even if you get the shell to work without the debugger, we will want to see evidence that you can use the debugger to stop, step, and explore the state of the program. This is because the debugger will be very useful in later projects and we want to remove any reticence you might have later when you have many other things to worry about.
Real shells (e.g, csh, sh, bash, tcsh) are quite large. We will only require that you implement a small subset of the functionality typically found in shells. Even within this subset, we have identified six sets of features of increasing difficulty. Make sure you complete the first before you embark upon the others.
The rest of this document is structured as follows: section goes over some review material and points out some facts about shells in general. Section describes the expected behavior of the Yalnix shell, in particular. Section offers some guidance regarding the Solaris features that you may want to use. Section briefly introduces development tools that will turn out to be useful later in the course. Finally, section suggests an order in which to implement the different features and section goes over some of the compiling and hand-in logistics.
The initialized data area: Contains initialized global variables. If, in C, you wrote int global = 5; outside the scope of any function, some part of the initialized data area would contain the integer 5.
The uninitialized data area: Allocates space for uninitialized global variables (in POSIX, these are initialized to zero.) If, in C, you wrote int global; outside the scope of any function, sizeof(int) bytes would be allocated in the uninitialized data area which would contain the value of the variable global during the execution of the program.
The stack: Contains the activation records produced as the result of procedure calls during the execution of the program. An activation record contains the data that is instantiated every time a function is called. Some of this data is specified by the program for each function, and some is required to implement the notion of ``procedure call''. Local variables are specified by the program, and are specific to each defined procedure. Return addresses, saved registers and other information describing the context of the calling procedure are all required to implement the semantics of procedures. These are all contained in the activation record. (Exercise: Why do local variables need to go on the stack rather than in the data areas? How does the compiler implement initialized local variables?)
This is the job of the loader. The loader can be considered to be part of the Operating System, though it is not part of the kernel. Executable files, which are, to a first approximation, generated by the linker from object files generated by the assembler/compiler, have a known format (e.g, a.out, COFF, ELF) that specifies all the different regions of the program that will be loaded into the different regions of memory (Exercise: Need all of the regions of a running program's memory be present in the file that stores the program when it is not running?)
The protection afforded by the process abstraction is even greater in systems with memory protection. In these systems (all common ones with the noteworthy exceptions of pre-96 Windows and pre-97 MacOS) each process is endowed with its own chunk (not necessarily contiguous) of memory, into which the program is loaded. Each program, loaded from an executable file, runs in its own process, in its own memory space. Just like the process abstraction gives each program the impression that it has the full attention of the CPU, the abstraction of memory space attached to a process gives the program the impression that it has full access to memory. Also, just as the process abstraction protects one process from the ambitions of another to monopolize the CPU, the memory space abstraction prevents one program from affecting the running image of another. The provision of these two abstractions is a fundamental goal of modern operating systems. You will understand this in depth when you implement your own kernel, in project 3.
Your shell has to manage sub-processes such as ls in the example. It has to start them, wait for them to exit(), and then continue. This task is greatly helped by the fact that, in Solaris, processes are arranged in families wherein a process may spawn (or fork, in UNIX parlance) child processes over which it has special control. An example of this special control is that a parent process can use the procedures in the wait() family (wait(), waitpid(), wait3(), etc) to block waiting for a child process to exit().
To poll for child termination, UNIX provides the flag WNOHANG that can be passed as an argument to some of the functions in the wait() family. You can look up the ``man'' pages for these functions to understand what this flag does. The mechanism that UNIX provides to set-up and handle signals is more complex and is considered later.
Several UNIX shells handle child termination synchronously, that is, by occasionally polling the system to see if any children have terminated since it last checked. tcsh is one such shell. Others do this asynchronously. For full credit, we will require that your implementation of ysh handle child termination asynchronously, that is, using signals. We require this because, as we will explain later, signals introduce a mild form of concurrency into your programs. Programming in the presence of concurrency is a frustrating, error-prone task, that is at the core of the difficulty of systems programming. You will have to deal with a more full-fledged form of concurrency in project 2, and we want you to practice with a much more tractable case in this project.
However, a shell that works with synchronous notification of job termination is much better than a shell that doesn't work, even while attempting to use signals to handle job termination. You should work on the more basic features of your shell before you try to use signals to handle the termination of background commands.
This kind of redirection is only possible because, in Solaris, as in most modern operating systems:
Each process has a separate table of currently opened files, so that, e.g, the input ``file'' of a process need not be the same as the input ``file'' of another process.
An open file can be shared among two or more processes, so that not only can two processes have the same input ``file'', but, e.g, the output ``file'' of a process can be the input ``file'' of another.
In some limited cases, the program may be able to pretend that it is giving you its undivided attention by checking for your input very frequently, but without waiting indefinitely for it. The time between checks can then be used to carry out other tasks. This technique is called ``polling''. The web browser may be polling for many events within the same loop; for instance, it may be polling for the arrival of network packets as it polls for mouse clicks. Similarly, your shell may poll for background job termination right before printing a new prompt, in the same loop that waits for foreground jobs to finish.
A problem of polling is that an event may not be noticed by the program until some time after the event has taken place. The less frequent the polling, the greater the potential delay. Increasing the polling frequency to minimize delay is not always possible or advisable, because it comes with an increase in overhad and program complexity.
Operating systems provide for this sort of event notification. UNIX implements it with a mechanism called ``signals.'' By telling the operating system that it wants to receive signals when some event occurs, the program can react almost immediately. The program ``receives'' signals by providing a signal handler function that will be invoked by the system when the event occurs. After the signal handler function returns, execution of the program reverts to the instruction it was executing immediately before the event took place. UNIX provides several signals, or event types; among them is the signal SIGCHLD which is triggered when a child process stops, continues, or exits. Note that, because the handler and the rest of your program are part of the same process, they both have access to the process' memory.
This introduces concurrency into your program. Without any safeguards, the handler may be invoked at almost any time, and may therefore encounter a variety of program states. For instance, your shell may need to upate a list of jobs in response to user commands. A handler for child process termination may also need to update this list. What might happen if the handler tries to manipulate a partially updated list? Care must be taken to ensure that the handler is not invoked when the list is updated only partially in a way that might break the invariants of the data structure. Concurrency may also cause trouble if the code for our signal handler is not re-entrant, that is, if two copies of the signal handler cannot corectly execute concurrently, since a signal may arrive while another signal is being processed. The common terminology for this is that we need to define critical sections of code during whose execution no other concurrent access to a data structure is allowed. In project 2 you will experiment with general ways of implementing sophisticated critical sections. For this project, you will only need the ability to mask signals, that is, to delay the invocation of a signal handler until your program is safely past the critical section in question. In doing this you have to be careful, because if you a signal is masked for too long your program will fail to work correctly. You can temporarily mask signals by manipulating the UNIX process signal mask. You can learn more about UNIX signal masks by reading the relevant ``man'' pages, e.g, man sigaction, man -s 5 signal, man sigprocmask.
Some of you will be tempted to use ``busy waits'' in you shells. A busy wait is a tight loop which does nothing but check for a particular condition to become true. You will soon see in lectures that this sort of loop is both inefficient and subject to starvation. Your shells should not do any busy waiting; any required waits in your code should be implemented with blocking system calls. A blocking system call is a call to the operating system which causes the calling process to be blocked, that is, that parks the calling process away from the CPU, until a condition changes. The system calls in the wait() family and also pause() and sigpause() are relevant examples of blocking system calls in Solaris.
When your yalnix shell is started (from the Solaris shell prompt,) it should perform any required initialization, and then enter a loop of printing a prompt, reading and parsing a command line, and carrying out the command. The prompt can be anything you want, for instance, ``yalnix > ''. In parsing a command line, you should ignore all white space (see man isspace, man strtok.)
The commands accepted by ysh are of two types: program executions and internal commands. Internal commands are satisfied by ysh itself without calling any other programs. There are five internal commands:
jobs: Prints a list of previously issued commands which are still running in the background, or which are stopped. You may format this list any way you like, but the command lines that initiated the backgrounded programs should be printed somewhere, and each command line should be associatd with an integer of your shell's choice.
echo $status: Prints the exit status of the last foreground child process to have exited.
fg %<int>: Continues executing the command line identified
by integer < int > .
The command line is from this point on executed in the foreground, that
is, your shell will wait for the command line to finish executing. The
association between integers and command lines is defined by your shell,
but is consistent with the output of the ``jobs'' command. This is an advanced
feature, make sure you get other things to work before you try to implement
this.
To do this, you will need to ensure that the processes spawned by your shell are in appropriate process groups. In general each collection of processes that are forked on the same command line and attached via pipes should be in a distinct process group. This is because the terminal driver will send the SIGTSTP to all processes in the foreground process group. Unless you create separate process groups for the spawned processes, they will be in the shell's process group and receive the signal along with the shell. This is an advanced feature, make sure you get other things to work before you try to implement this (see man -s 2 setpgid). You also need to ensure that the currently running foreground process's process group is the foreground process group (see man -s 2 tcsetgrp).
All other command lines specify the execution of program(s). The execution of a single program is specified by a sequence of space-separated strings. The first of these is the name of the executable file that contains the desired program (modulo a search path as explained in the execvp man page, see man -s 2 execvp) and the others are arguments passed to the program. The command is an error if the executable file named by the first word does not exist, or is not an executable.
A single program's excution specified in this manner may be followed by the meta-character `` < '' (`` > '',) which is in turn followed by a file name. In this case, the input (output) of the single program will be redirected from (to) the specified file name. If the output file does not exist, it should be created. If the input file does not exist, the command is an error.
Note that input/output redirection is probably harder to implement than simple foreground and background execution: you should not embark on it until you have these two more basic features working.
Several such single program invocations can be present in a single command line, when separated by the shell meta-character ``|''. In this case, the shell should fork all of them, chaining their outputs and inputs appropriately. For instance, the command line
A command line with one or more ``pipes'' is an error if any of its component program invocations is an error. A command line with ``pipes'' is an error if the input of any but the first command is redirected, or if the output of any but the last command is redirected. A command line with ``pipes'' is not considered to have completed until all of its component program invocations exit.
Note that pipes (together with the signal stuff) are probably harder to implement correctly than many other parts of your shell, and you should leave them until you have done the more basic parts of the shell, namely, simple foreground execution, simple background execution and input/output redirection.
A command line as specified so far may be followed by the meta-character ``&'', which specifies that all program invocations required by the command line are to be carried out in the background, that is, that the shell should not wait for the programs to finish before returning to read the next command. When the command finally completes a message to that effect must be printed, by the shell, to the terminal. This message should be printed as soon as the command completes, for full credit. However, we advise that you first get background execution to work correctly with synchronous notification, and to not add asynchronous notification until the simpler case is working perfectly.
The shell meta-characters ( < , > , |, and &) cannot occur inside strings representing programs, arguments, or files.
If a command is in error, the shell should print a message indicating the nature of the error.
CommandLine := NULL FgCommandLine FgCommandLine & FgCommandLine := SimpleCommand FirstCommand MidCommand LastCommand SimpleCommand := ProgInvocation InputRedirect OutputRedirect FirstCommand := ProgInvocation InputRedirect MidCommand := NULL | ProgInvocation MidCommand LastCommand := | ProgInvocation OutputRedirect ProgInvocation := ExecFile Args InputRedirect := NULL < STRING OutputRedirect := NULL > STRING ExecFile := STRING Args := NULL STRING ArgsIn any case, please realize that we don't care very much whether you can write a great parser. We assume that you have learned how to do this in other courses. Don't spend time on the parser, only get it to be good enough to service the other, more interesting, parts of your shell.
You have heard the term ``System Call'' before. Do you know what it means? As its name implies, a system call is a ``call'', that is, a transfer of control from one instruction to a distant instruction. A system call is different from a regular procedure call in that the callee is executed in a privileged state, i.e, that the callee is within the operating system. Because, for security and sanity, calls into the operating system must be carefully controlled, there is a well-defined and limited set of system calls. This restriction is enforced by the hardware through trap vectors: only those OS addresses entered, at boot time, into the trap (interrupt) vector are valid destinations of a system call. Thus, a system call is a call that trespasses a protection boundary in a controlled manner.
Since the process abstraction is maintained by the OS, ysh will need to make calls into the OS in order to control its child processes. These calls are system calls. In UNIX, you can distinguish system calls from user-level library (programmer's API) calls because system calls appear in section 2 of the ``manual'', whereas user-level calls appear in section 3 of the ``manual''. The ``manual'' is, in UNIX, what you get when you use the ``man'' command. For example, man fork will get you the ``man page'' in section 2 of the manual that describes the fork() syscall, and man -s 2 exec will get you the ``man page'' that describes the family of ``exec'' syscalls (a syscall, hence -s 2.)
The following UNIX syscalls will be especially relevant to the core of this project:
int execvp(const char * file, char * const argv[]): Loads
the executable file path, or a file found through a search path,
into the memory associated with the calling process, and starts executing
the program therein. It obliterates whatever program is currently running
in the calling process, if successful.
void exit(int status): Exits the calling program, destroying the calling process. It returns status as the exit value to the parent, should the parent be interested. The parent receives this exit value through the wait syscall, below. Note that the linker introduces an exit() call at the end of every program, for instance, at the end of a C main procedure, even if the C code doesn't explicitly have one.
pid_t wait(int *stat_loc): Returns the exit status of an exited child, if any. Returns error if there are no children running. Blocks the calling process until a child exits if there are children but they are all currently running.
pid_t waitpid(pid_t pid, int *stat_loc, int options): Similar to wait() but allows you to wait for a specific process of group of processes, and allows the specification of flags such as WNOHANG.
wait3(...), wait4(...) Similar to wait() but allow different combinations of parameters and flags.
int tcsetpgrp(int fildes, pid_t pgid_id) Sets the foreground process group id to be the foreground group associated with the controlling terminal. The controlling terminal is usually associated with stdin, stdout, and stderr (file descriptors 0, 1, and 2)
int setpgid(pid_t pid, pid_t pgid) Sets the process group ID of the process with ID pid to pgid.
Depending on how you wish to implement your ysh, and which features you wish to implement within it, you may or may not need to use more calls. You may also not need to use the calls listed above, depending on what implementation choices you make. As you will better notice later in the semester, in this course we tend to give you assignments that are perhaps less circumscribed than those of other courses. This is not only good practice for real-life situations, but it is endemic to the field of systems programming, in which it is common to find choices without clearly limited alternatives.
In particular, if you implement background execution with asynchronous notification, as is required for full credit, you will need to know how to use signals (see man -s 5 signal to start.) The signal that the OS sends to a parent process when a child exits is the SIGCHLD signal. To receive a signal, a process must tell the OS that it is interested in receiving it. The process does so via the sigaction() syscall. This call asks the OS to call a program-specified signal handler when the specified asynchronous signal arrives.
You will also need to use signals to implement the Control-Z feature that stops the current foreground command line's execution. In a correctly configured Solaris terminal, typing Control-Z triggers a SIGTSTP signal, which your shell can catch (handle) just like it would have to handle SIGCHLD. To ensure that your terminal is correctly configured in this regard, type ``stty susp ^z'' when you log in. You can check whether your terminal is properly configured by checking the value of susp in the output of ``stty -a''.
Let us again repeat at this point that you should not worry about signals until you get the other basic features working. The more basic features include simple foreground and background execution, input/output redirection, and pipes.
If you get as far as implementing input/output redirection and/or pipes, you will also need to know a bit about the way programs are associated with their default inputs and outputs, and about how files are opened. We presume you know this, if vaguely, but in the remainder of this section we'll briefly treat these topics.
Buffering is instead typically implemented in a user-level library, commonly referred to as the standard I/O library, or ``stdio'' for short. This library uses the raw syscalls, implements buffering and other things on top, and presents an enhanced interface to applications.
For instance, the system call open() is augmented by stdio, which provides the enhanced fopen() library call. Similarly, there are read() and write() syscalls that are present, through stdio, as fread() and fwrite(). You have probably used fopen() to open files from your C programs, but you may not have used open.
Just as fopen returns a pointer to an object of type FILE, open returns what is somewhat inexactly referred to as a file descriptor. A file descriptor is actually an integer index into an array of data structures, each of which contains data relevant to an open file. The array of (data structures representing) open files is maintained by the Operating System on behalf of each process. Each process has one such table.
When, through fork(), the Operating System starts a new process, it copies the open file table from the parent process to the child. This is why a child process, by default, shares the input and output files of the parent process, including its input and output terminals. To make the input or output of the child go to a different place, your shell will have to do two things: open the new place, and set the resulting file descriptor to be the default input or output of the child process. This has to be done only on the child, so it has to be done after the fork() call, but it has to be done before the program intended for the child starts executing via the execvp() call.
How do you set the default input and output file descriptors? In Solaris and UNIX in general, the default input and output descriptors are by convention the first and second in the open file table, respectively (as indicated by man stdio.) To set one of these special file descriptors to a file already opened (which therefore has a descriptor at a different location,) you can use the dup2 syscall (see man dup2.) For instance, if you wanted to redirect the output of a child process to file ``out'', and open(öut", ...) had returned 7, you would have to call dup2(7, 1), since 1 is the index into the second file descriptor entry, which happens to be the default output of the process. You would have to be careful to do this only on the child, and not on the parent.
You may still have one question: if you opened the new output or input file using the raw open, will the usual stdio functions such as printf() or fgets() work? The answer is yes, because the stdio objects stdout and stdin are pre-defined in the stdio library, and always refer to whatever open raw file is described in the second or first entry of the open file table, respectively.
Using this scheme, you can redirect the input and output of any child process. But to implement pipes you need yet another step: you need to link two file descriptors so anything output to one is available as input on the other. This can be achieved with the pipe() syscall (see man pipe.) You may find some problems trying to make pipes created by the pipe() syscall generate an end-of-file (EOF) when there is no further data to be transferred. It may help you to realize that both sides of a pipe are open for both reading and writing, and that a read won't return an EOF until the corresponding file descriptor on the other side of the pipe is close()d by all processes that have opened it. How many processes have opened a pipe file descriptor? Well, this depends on how you implement your pipes. For example, if you have a parent process that creates a pipe and then forks two child processes, each of the pipe's file descriptors will, at this point, be opened by 3 processes. EOF won't be sent until the descriptor is closed by all three processes. Note that when a process exits, it implicitly closes all its currently open file descriptors.
make is a program that accepts specifications of dependencies among source files, and uses these specifications to generate compile/link commands. make is great for large projects, because it finds the smallest sequence of compile commands that will bring the final executable(s) completely up to date. This can save a lot of time. But even for projects as small as this, make is useful because it saves a lot of typing.
In http://www.cs.cmu.edu/~412/projects/proj1/makeintro.psyou can find a link into a pamphlet that introduces make. Further information (much more detailed) can be found in the make man page, and in myriad books.
Debuggers are also very useful, for projects large and small. A debugger allows you to interactively step through a running program, stopping it at interesting points, and looking at its state at those points. It can help you find the onset of a problem whose effect may not become obvious until much later. We suggest that you use dbx or debugger (in /opt/SUNWspro/bin) if compiling with the native Solaris compiler (/opt/SUNWspro/bin/cc,) and that you use gdb if compiling with the GNU C compiler (gcc.) Both of these have reasonable on-line help facilities (accessed in both cases through the ``help'' command.) There are also graphical interfaces to both of these. If you are used to graphical tools you may find these more friendly, though possibly not as efficient. The Solaris graphical interface for dbx is debugger. There is also ddd which is a graphical interface that works with several debuggers, among them dbx and gdb.
We have to assume that you have used debuggers before arriving in this course but, if you haven't, we'll try to help you on a case by case basis.
An approximation to the grading criteria we will use will be posted shortly.
This course's projects are probably graded somewhat differently from projects in other courses. In particular, we seem to pay special attention to correct handling of unusual circumstances, and of general errors. This is because, in the operating system, unusual situations abound, and, if not handled properly, can have catastrophic effects. If you look at systems code of any kind you will see that a seemingly enormous portion of the effort is dedicated to detecting and handling errors correctly.
We don't pay a lot of attention to the prettiness of your code, and only expect comments that illustrate a particularly obtuse piece of work. We expect that, this far into your career, you will know how to write code that is maintainable (thus readable and well structured.) Writing cleanly (not the same as writing neatly) can save you many hours of work when you start having to make modifications. Another motivation to writing cleanly is that, if your program shows an error, and we have time, we often try to look at it to decide whether the mistake is trivial or bellies a serious misunderstanding; since we don't often have a lot of time, clean programs have a better chance of being given this sort of benefit-of-the-doubt attention. When writing code the first time you should try to imagine later changes and try to write to contain the extent of the changes required. A trivial example of this is that you should use include files and multiple files with delineated functionality.
Finally, in this course we expect you to understand your task and your solution at many levels, including the details of the code and the trade-offs involved in your solution. We expect you to justify your solutions rather than merely saying that it works.
We suggest that you proceed as follows:
Write detailed pseudo-code for a shell that can fork single program
invocations and wait for their completion.
Implement this pseudo-code and the command-line parser. Test it.
Add support for running programs in the background, with synchronous notification of job termination via polling. Include here the implementation of the jobs command.
Add input and/or output redirection
Add support for pipes.
Add asynchronous notification of background termination through the use of signals.
Add job control features - implement the behavior of Control-Z, fg and bg.
Dbx only works with programs compiled by gcc (the GNU compiler) if you compile such programs with -gcoff, and then not perfectly. Gdb does not work well with programs compiled by cc (the Solaris compiler.) Therefore, it is safer to debug with dbx if you prefer to use cc, and with gdb otherwise.
There is also a graphical debugger called ddd which can be used as an interface to both gdb and dbx. While some of us try to avoid the mouse as much as possible, those of you who can move hands quickly and are not prone to carpal tunnel syndrome may prefer to use this interface to the debuggers. To run ddd as a front end to dbx, execute ddd -dbx. To run it with gdb, simply type ddd.
The Solaris compiler is hidden. This is the result of a Sun business decision. To access both the compiler and dbx, do the following:
setenv PATH /opt/SUNWspro/bin:$PATH setenv MANPATH /opt/SUNWspro/man:/usr/contributed/man:/usr/manNote that if you don't set the PATH as above, cc will default to /usr/ucb/cc, a compiler that is as broken as any number of hearts.
To avoid the long message every time you start dbx, put the following line in the file .dbxrc in your work directory:
dbxenv suppress_startup_message 4.0
http://gigo.sp.cs.cmu.edu:8080/~cs412/cgi-bin/register_group.cgi
If you are having great difficulties finding a partner, send me (gkesden+@cs.cmu.edu) mail and I will try to play the part of a matchmaker. Please do try to find a partner before you do this.
Soon after everyone has formed a group, we will be creating the following directory:
/afs/andrew.cmu.edu/scs/cs/15-412/usr/grp<group number>At the deadline, your write access to these directories will be revoked. Any work that is not in the group directory when the access is revoked will not count towards your grade.
After the deadline, your directory should contain:
Source files that compile, by typing make, into an executable of name ysh.
Optionally, a file of name README that contains anything you wish to point out to us.